a blog
"This is it; I'm going to get those plus-twos this time; I can feel it. Patch set 9 is the lucky one!"
"Last week you told me patch set 8 is the lucky one."
"I forgot they're not indexed from zero."
(cross-posted from the SwiftStack Blog)
In enabling mechanism to combine together general symbols, in successions of unlimited variety and extent, a uniting link is established between the operations of matter and the abstract mental processes of the most abstract branch of mathematical science. A new, a vast, and a powerful language is developed for the future use of analysis, in which to wield its truths so that these may become of more speedy and accurate practical application for the purposes of mankind [sic] than the means hitherto in our possession have rendered possible.
—Ada Lovelace on Charles Babbage's Analytical Engine, 1842
Dear reader, if you're reading [the SwiftStack Blog], you may have already heard that erasure codes have been added to OpenStack Swift (in beta for the 2.3.0 Kilo release, with continuing improvements thereafter) and that this is a really great thing that will make the world a better place.
All of this is entirely true. But what is perhaps less widely heard is exactly what erasure codes are and exactly why their arrival in Swift is a really great thing that will make the world a better place. That is what I aim to show you in this post—and I do mean show, not merely tell, for while integrating erasure codes into a production-grade storage system is (was!) an immense effort requiring months of work by some of the finest programmers the human race has to offer, the core idea is actually simple enough to fit in a (longish) blog post. Indeed, by the end of this post, we will have written a complete working implementation of a simple variant of Reed–Solomon coding, not entirely unlike what is used in Swift itself. No prior knowledge will be assumed except a working knowledge of high-school algebra and the Python programming language.
But first, we need to understand the problem that erasure codes solve. The strategy Swift has traditionally used to achieve its reliability and fault-tolerance properties is replication: keep more than one copy of each object (typically three), preferably in entirely different datacenters, failing that, on different machines, and failing that, at least on different hard drives. Your data is safe from occasional drive failures because the probability of all the drives containing a particular object failing at the same time is very, very small.
The problem with replication is that it's expensive: if you keep three replicas, then for every terabyte that you want to use, you have to pay for three terabytes of actual physical storage. The cost would appear to be unavoidable, unless ... unless there were some way to reap the benefits of distributing the information across different failure domains without storing the entire object at each location ...
"But surely this is impossible!" I hear you cry. "It's useless to make half a copy of something, because you can't know in advance of a disaster whether the half you made a backup of is the half that will need to be restored. In order to enjoy the safety of having a spare, you need a spare of the whole thing."
My dear reader, this objection is compelling, well-stated—and gloriously, one-hundred-percent wrong. We can achieve reliability guarantees similar to that of the replication strategy, keeping our data safe even as some of its fragments are damaged, lost, or erased. (Hence the name, erasure codes.) The method will have its own costs in the form of increased CPU load and more network requests; it won't make sense for all use cases, but when appropriate, the efficiency gain is impressive. It all depends on applying a deep philosophical insight into the nature of space itself.
Specifically: two points make a line.
Given any two distinct points on a plane, there is one and exactly one line that passes through both of them. We reconstruct anything we might want to know about a particular line just by remembering two points that it passes through.
But suppose we were to remember three points. Then we could still reconstruct the line from any two of them, which means that the information about our line hasn't been lost even if we forget one of the points.
Similarly, three points make a parabola, four points make a cubic curve, and in full generality, m+1 points make a degree-m polynomial. Given n points on a polynomial curve where n is greater than m+1, any m+1 of them suffice to reconstruct the polynomial.
Thus, we have a clear strategy for storing data in a reliable, failure-tolerant way, without going to the expense of storing complete replicas: all we have to do is pretend our data is made out of polynomials, and store more points than are strictly necessary to reconstruct the data.
But don't take my word for it! Mere verbal arguments can be deceptive, but code is proof and code is truth, so if you still doubt that such an idea can really be made to work—and maybe you should—you won't after we're done implementing it.
So suppose we want to save some textual data; say, the string, "THE FUNDAMENTAL PROBLEM OF COMMUNICATION IS THAT OF REPRODUCING AT ONE POINT EITHER EXACTLY OR APPROXIMATELY A MESSAGE SELECTED AT ANOTHER POINT". Now, this data is made out of letters and spaces, not polynomials, but we can process it into a form that will make it easier to make-believe that it is. Say, we split the text into chunks of a fixed size (padding the end with extra spaces if necessary so that our chunk size evenly divides it), and convert the characters into integers from 0 to 26 (space is 0, A is 1, B is 2, &c.). Here are some functions to help with that—
from string import ascii_uppercase
ALPHABET = " "+ascii_uppercase
CHAR_TO_INT = dict(zip(ALPHABET, range(27)))
INT_TO_CHAR = dict(zip(range(27), ALPHABET))
def pad(text, chunk_size):
return text + ' '*(chunk_size - len(text) % chunk_size)
def chunkify(text, chunk_size):
return [text[i:i+chunk_size]
for i in range(0, len(text), chunk_size)]
def convert(string):
return [CHAR_TO_INT[c] for c in string]
After turning our text into converted chunks (lists of integers), we can interpret each chunk as representing the coefficients of a polynomial function: say, in order of increasing degree, so that, e.g., the list [1, 2, 3] represents the function \(1 + 2x + 3x^2\). Then we can take points on that polynomial at \(n\) different values of the independent variable \(x\) for some \(n\) greater than the chunk size to get a properly redundant encoding.
(It's actually better if you use polynomials over the finite field \(\mathbb{F}_q\) of the integers modulo \(q\) for some \(q\) which is a prime raised to the power of something, but let's not worry about that.)
def evaluate_polynomial(coefficients, x):
return sum(c * x**i for i, c in enumerate(coefficients))
def encode(chunk, n):
return [evaluate_polynomial(chunk, i) for i in range(n)]
def erasure_code(text, chunk_size, encoded_chunk_size):
chunks = chunkify(pad(text, chunk_size), chunk_size)
converted_chunks = [convert(chunk) for chunk in chunks]
return [list(enumerate(encode(chunk, encoded_chunk_size)))
for chunk in converted_chunks]
Then, with a choice for the original chunk size (which you'll recall will also be the number of terms each in the polynomials used to encode each chunk) and the size of the resulting encoded chunk (that is, the number of points we'll sample from the polynomials), we can encode our text.
$ python3
>>> from reed_solomon import *
>>> text = "THE FUNDAMENTAL PROBLEM OF COMMUNICATION IS THAT OF
REPRODUCING AT ONE POINT EITHER EXACTLY OR APPROXIMATELY A MESSAGE
SELECTED AT ANOTHER POINT"
>>> encoded = erasure_code(text, 5, 8)
>>> encoded
[[(0, 20), (1, 39), (2, 152), (3, 575), (4, 1668), (5, 3935), (6,
8024), (7, 14727)], [(0, 21), (1, 53), (2, 281), (3, 1179), (4, 3533),
(5, 8441), (6, 17313), (7, 31871)], [(0, 5), ...
[further output redacted]
At this point, our text has been transformed into a Python list, whose elements are Python lists representing the individual chunks, whose elements are tuples representing (x, y) coordinate pairs representing points on the polynomial representing that chunk.
Let's simulate distributing that encoded information across several storage nodes by writing points with different x-values to different files. We'll make-believe that each file is a different storage node. We'll write another function for that.
import json
def disperse(encoded_chunks):
node_count = len(encoded_chunks[0])
for i in range(node_count):
with open('node'+str(i), 'w') as node:
node.write(json.dumps([chunk[i] for chunk in encoded_chunks]))
And try it out—
>>> disperse(encoded)
>>>
$ ls
node0 node1 node2 node3 node4 node5 node6 node7
$ cat node4
[[4, 1668], [4, 3533], [4, 3517], [4, 1824], [4, 4080], [4, 4342],
[4, 1665], [4, 4769], [4, 5460], [4, 4172], [4, 4710], [4, 2254], [
4, 433], [4, 2436], [4, 4464], [4, 5796], [4, 1596], [4, 4428], [4,
1417], [4, 5313], [4, 5452], [4, 709], [4, 6212], [4, 4973], [4, 5
445], [4, 5205], [4, 6308], [4, 4412], [4, 1555]]
In conclusion, that's how you use Reed–Solomon coding to turn comprehensible English text into inscrutable lists of lists of numbers distributed across several files. Thank you, and—
What's that you say, dear reader? Demonstrating how to encode something is useless unless you also demonstrate how to decode it? Well, I suppose you may have a point. Never fear—we can do that, too! But first, we'll need some functions for manipulating polynomials (in the "list of coefficients in order of ascending power" form that we've been using).
def get_coefficient(P, i):
if 0 <= i < len(P):
return P[i]
else:
return 0
def add_polynomials(P, Q):
n = max(len(P), len(Q))
return [get_coefficient(P, i) + get_coefficient(Q, i) for i in range(n)]
def scale_polynomial(P, a):
return [a*c for c in P]
def multiply_polynomials(P, Q):
maximum_terms = len(P) + len(Q)
R = [0 for _ in range(maximum_terms)]
for i, c in enumerate(P):
for j, d in enumerate(Q):
R[i+j] += c * d
return R
Once we can do arithmetic with polynomials, we can write functions to reconstruct the polynomial representing a chunk of our text given our saved points, which is probably the most intricate part of this entire endeavor. We'll use a technical trick called Lagrange interpolation, after the great mathematician-astronomer Joseph-Louis Lagrange.
Suppose we want to reconstruct a cubic polynomial from the four points \((x_1, y_1)\), \((x_2, y_2)\), \((x_3, y_3)\), and \((x_4, y_4)\). It turns out that a formula for the polynomial is
where \(\ell_1(x)\) (the first Lagrange basis element) stands for
and so on—for each \(i\) between 1 and the number of points we have, the numerator of the \(i\)th Lagrange basis element is the product of \((x - x_j)\) for all \(j\) from 1 up to the number of points we have but not equal to \(i\), and the denominator follows a similar pattern but with \(x_i\) instead of \(x\). (Note that we're using letters with subscripts, like \(x_i\), to represent specific constants, whereas \(x\) without a subscript is a function's independent variable.)
I hear you ask, "But why this particular arbitrary-looking formula out of the space of all possible arbitrary-looking formulae?" But the grace and beauty of this formula is exactly that it's engineered specifically to pass through our points. Consider what happens when we choose \(x\) equal to \(x_1\). The second through fourth terms \(y_2\ell_2(x_1)\) through \(y_4\ell_4(x_1)\) all contain a factor of \((x_1 - x_1)\) and are thus zero, but the first term becomes
So by design, our interpolated polynomial takes value \(y_1\) at \(x_1\), \(y_2\) at \(x_2\), and so forth. In Python, the whole process looks like this—
def lagrange_basis_denominator(xs, i):
denominator = 1
for j, x in enumerate(xs):
if j == i:
continue
denominator *= xs[i] - xs[j]
return denominator
def lagrange_basis_element(xs, i):
element = [1]
for j in range(len(xs)):
if j == i:
continue
element = multiply_polynomials(element, [-xs[j], 1])
scaling_factor = 1/lagrange_basis_denominator(xs, i)
return scale_polynomial(element, scaling_factor)
def interpolate(points):
result = [0]
xs, ys = zip(*points)
for i in range(len(points)):
result = add_polynomials(
result,
scale_polynomial(lagrange_basis_element(xs, i), ys[i])
)
return [round(k) for k in result]
(Note that we're rounding off our computed coefficients because this implementation isn't very numerically stable—the subtle differences between true real-number arithmetic and the approximate floating-point arithmetic implemented by computers start to accumulate, and if we choose too large of a chunk size, our program will actually start giving the wrong answers—but let's not worry about that, either.)
With this technique, we now have all the tools we need to recover our text from a subset of the data we wrote to our various "nodes" earlier. What we need to do is this: for each chunk, arbitrarily select a number of stored points equal to our chunk size, interpolate the polynomial from them, deconvert the numbers which are the coefficients of that polynomial back into their character equivalents, unchunkify the chunks into a unified whole, and unpad any whitespace we added to the end when we began.
def deconvert(sequence):
return ''.join(INT_TO_CHAR[i] for i in sequence)
def unchunkify(chunks):
return ''.join(chunks)
def unpad(text):
return text.rstrip()
def erasure_decode(encoded_chunks, chunk_size, encoded_chunk_size):
converted_chunks = [interpolate(chunk[:chunk_size])[:chunk_size]
for chunk in encoded_chunks]
return unpad(unchunkify(deconvert(chunk) for chunk in converted_chunks))
But about that data that we wrote out earlier.
$ ls
node0 node1 node2 node3 node4 node5 node6 node7
It would hardly be a compelling test of our erasure-coding skills if there were any suspicion that we actually needed all of those files—we really only need as many as our chunk size. So let's suppose that three of our nodes die in a fire—
$ rm node1 node3 node6
$ ls
node0 node2 node4 node5 node7
Could this the end of our data? With a full three-eighths of our encoding having been utterly destroyed, is it delusional to hold out hope that our text might yet be faithfully recovered? No! No, it is not! We only need one more function to retrieve the encoded chunks—
def retrieve(*nodes):
responses = []
for node in nodes:
with open(node) as our_node:
responses.append(json.loads(our_node.read()))
return [[response[i] for response in responses]
for i in range(len(responses[0]))]
—and then—
$ python3
>>> from reed_solomon import *
>>> node_data = retrieve("node0", "node2", "node4", "node5", "node7")
—successfully decode them!
>>> erasure_decode(node_data, 5, 8)
'THE FUNDAMENTAL PROBLEM OF COMMUNICATION IS THAT OF REPRODUCING AT
ONE POINT EITHER EXACTLY OR APPROXIMATELY A MESSAGE SELECTED AT AN
OTHER POINT'
Dear reader, it is true our toy implementation here was crude, the hundred-and-change bytes of data we demonstrated it on was of no intrinsic interest, and many obvious and not-so-obvious subtleties were ignored. But I implore you to consider the implications for your own storage needs of more advanced, not-merely-educational application of these vast and powerful techniques. Imagine just how soundly you'll be able to sleep at night knowing that you're well under your budget and yet your data is just as safe as if you had three complete independent copies of it!
And even if you personally have no intention of deploying Swift—as my SwiftStack colleague and project technical lead for OpenStack Swift John Dickinson has pointed out, we are rapidly entering an era in which everyone uses object storage, whether they realize it or not. In a hyperconnected global economy, even minor efficiency improvements in key infrastructure components can reap enormous benefits elsewhere, which is to say that the rest of your life will contain more happiness and less pain if the financial institution that invests your retirement savings, or the medical research institute that develops a cure for the cancer you'll get twenty years from now, or the image hosting service that serves you cute cat pictures today, have access to cheaper, faster, and more reliable storage than the means hitherto in our possession have rendered possible. And that's why erasure codes being in OpenStack Swift is a really great thing that will make the world a better place; quod erat demonstrandum.
The code in this post is available separately.
Our users have a need although
Our budget's rather ...
Thrifty—
Not just, "I want my data," but
"I want my data
Swiftly."
But should their need our budget meet
I'd think it not an oddity,
In an age of open source in which
The hardware's a commodity.
The right solution's quick to get,
No need to hunt or forage;
We'll see our users' needs are met
With open object storage.
Dear reader, suppose you're a distibuted data storage system. Your soul (although some pedants would insist on the word program) is dispersed across a cluster of several networked computers. From time to time, your human patrons give you files, and your job—more than that, the very purpose of your existence—is to store these files for safekeeping and later retrieval.
The humans who originally crafted your soul chose a simple algorithm as the means by which you decide which file goes on which of the many storage devices that live in the computers you inhabit: you find the MD5 hash of the filename, take its residue modulo n where n is the number of devices you have—let's call the result i—and you put the file on the (zero-indexed) ith device. So when you had sixteen devices and the humans wanted you to store twilight.pdf, you computed md5("twilight.pdf") = 429eb07bb8a3871c431fe03694105883, saw that the lowest nibble was 3, and put the file on your 3rd device (most humans would say the fourth device, counting from one).
It's not a bad system, you tell yourself (some sort of pride or loyalty preventing you from disparaging your creators' efforts, even to yourself). At least it keeps the data spread out evenly. (A shudder goes down your internal buses as you contemplate what disasters might have happened if your creators had been even more naive and, say, had you put files with names starting with A through D on the first device, &c. What would have happened that time when your patrons decided they wanted to store beat00001.mp3 through beat18691.mp3?)
But still, you've been having problems lately. As your patrons have come to rely on you more and more, they've added more machines bearing more devices to your cluster—and occasionally devices fail, too. And every time you gain or lose a device, your hashing scheme for assigning files to devices goes out of date: in the vast majority of cases, md5(filename) mod n changes when n does, requiring almost all of your files to be shuffled onto different devices, an expensive and unpleasant procedure.
One day, after a particularly painful rearrangement of files, you decide enough is enough. You're going to need a new way to assign files to devices, even if it means rewriting part of your own soul (and that's exactly what it will mean). You do some searching and read about an idea called consistent hashing that seems like a perfect solution to your problem. (In fact, your reading even mentions that your older cousin, OpenStack Swift, uses a modified version of consistent hashing for the same purpose. You've always resented Swift and aren't happy with the idea of copying one of her algorithms—but you tell yourself that that's not important.)
Anyway, consistent hashing. The essential nature of your problem is that you need a way to split the space of possible filenames into n partitions in a way that minimizes the number of files that have to change partitions when n changes. So imagine mapping the 128-bit output space of MD5 around a ring. Now pseudorandomly designate m spots on the ring (m being some prudently-chosen natural number) for each of your n storage devices: say, by hashing the device name suffixed with the number j for each j between 0 and m–1 inclusive. Internally, you might represent the ring as just an array of hash/device pairs. Like this (in Clojure; here the array and the pairs it contains are actually "vectors")—
(import 'java.security.MessageDigest)
(defn md5 [string]
(let [digest-builder
(java.security.MessageDigest/getInstance "MD5")]
(.update digest-builder (.getBytes string))
(clojure.string/join
(map (fn [chr] (format "%x" chr))
(.digest digest-builder)))))
(defn suffixed [name n]
(map (fn [j] (str name j))
(range n)))
(defn ring-kv-pairs [device spots]
(map (fn [suffixed-name]
(vector (md5 suffixed-name) device))
(suffixed device spots)))
(defn make-ring [devices spots]
(vec (sort
(reduce concat
(map (fn [device]
(ring-kv-pairs device spots))
devices)))))
Then when your patrons ask you to store a file, you're still going to hash its name, but instead of taking the residue mod n of the hash to decide where the file should live, you're going to locate the hash in your ring, and find the next designated spot on the ring associated with one of your storage devices, and the file will live on that device. In terms of your internal representation of the ring as an array of hash/device pairs, you'll find the first pair whose first item (the hash of the suffixed device name) is greater than the hash of the name of the file to be stored, and the second item of that pair will tell you which storage device to use. (And if the filename hash is greater than all those stored in the (first items of the pairs stored in the) array, then you just use the first pair in the array. It is supposed to represent a ring, after all.) Like this—
(defn ring-search [ring key]
(or (some (fn [pair]
(if (> (compare (first pair) key) 0)
pair))
ring)
(first ring)))
(defn ring-lookup [ring filename]
(last (ring-search ring (md5 filename))))
And now—why, now when you gain (respectively lose) a storage device, you can decide the allocation question simply by adding (respectively removing) the appropriate designated spots to (respectively from) your ring—
(defn ring-add [ring device spots]
(sort (vec (concat ring (ring-kv-pairs device spots)))))
(defn ring-remove [ring device]
(filter (fn [spot] (not= (last spot) device))
ring))
—and most files stay on the same device: the only ones that have to move are those with a new nextmost designated spot in the ring!
You decide to run a quick simulation to see if you've gotten this right before saving the edits to your soul. Suppose you had storage devices device0 through device5 and your patrons wanted you to store file0 through file5999; how would the files end up distributed across your devices? You choose a prudent-seeming integer for the number of designated spots per device—say, 450?—and write the simulation like this—
(defn filemap [ring files]
(into {}
(for [file files
:let [device (ring-lookup ring file)]]
[file device])))
(defn counter [devices filemap]
(for [d devices]
[d (count (filter (fn [entry]
(= (last entry) d)) filemap))]))
(def my-devices (suffixed "device" 6))
(def my-first-ring (make-ring my-devices 450))
(def my-files (suffixed "file" 6000))
(def my-filemap (filemap my-first-ring my-files))
(doseq [total (counter my-devices my-filemap)]
(println total))
And the results seem reasonable enough:
$ clojure consistent_hashing.clj
[device0 1020]
[device1 993]
[device2 1082]
[device3 955]
[device4 993]
[device5 957]