{"id":1561,"date":"2015-04-23T05:00:24","date_gmt":"2015-04-23T12:00:24","guid":{"rendered":"http:\/\/zackmdavis.net\/blog\/?p=1561"},"modified":"2015-04-21T22:14:14","modified_gmt":"2015-04-22T05:14:14","slug":"the-foundations-of-erasure-codes","status":"publish","type":"post","link":"http:\/\/zackmdavis.net\/blog\/2015\/04\/the-foundations-of-erasure-codes\/","title":{"rendered":"The Foundations of Erasure Codes"},"content":{"rendered":"

(cross-posted from the SwiftStack Blog<\/em>)<\/a><\/p>\n

\nIn 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<\/em>] than the means hitherto in our possession have rendered possible.\n<\/p><\/blockquote>\n

\n\u2014Ada Lovelace<\/a> on Charles Babbage's Analytical Engine<\/a>, 1842\n<\/div>\n

<\/p>\n

Dear reader, if you're reading [the SwiftStack Blog<\/em><\/a>], you may have already heard that<\/a> erasure codes<\/em> have been added to<\/a> OpenStack Swift (in beta<\/a> 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.<\/p>\n

All of this is entirely true. But what is perhaps less widely heard is exactly<\/em> what erasure codes are and exactly<\/em> 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\u2014and I do<\/em> 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\u2013Solomon coding<\/a>, 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.<\/p>\n

<\/p>\n

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<\/em>: keep more than one copy of each object (typically three), preferably<\/a> in entirely different datacenters, failing that, on different machines, and failing that, at least<\/em> on different hard drives. Your data is safe from occasional drive failures because the probability of all<\/em> the drives containing a particular object failing at the same time is very, very small.<\/p>\n

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<\/em> terabytes of actual physical storage. The cost would appear<\/em> to be unavoidable, unless ... unless<\/em> there were some way to reap the benefits of distributing the information across different failure domains without storing the entire<\/em> object at each location ...<\/p>\n

"But surely this is impossible!" I hear you cry. "It's useless to make half<\/em> 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<\/em>."<\/p>\n

My dear reader, this objection is compelling, well-stated\u2014and gloriously, one-hundred-percent wrong<\/em>. We can<\/em> 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<\/em>.) 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.<\/p>\n

Specifically: two points make a line<\/em>.<\/p>\n

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.<\/p>\n

But suppose we were to remember three<\/em> 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.<\/p>\n

\"polynomial\"<\/a><\/p>\n

Similarly, three points make a parabola, four points make a cubic curve, and in full generality, m<\/em>+1 points make a degree-m<\/em> polynomial. Given n<\/em> points on a polynomial curve where n<\/em> is greater than m<\/em>+1, any<\/em> m<\/em>+1 of them suffice to reconstruct the polynomial.<\/p>\n

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.<\/p>\n

But don't take my<\/em> word for it! Mere verbal arguments can be deceptive, but code is proof<\/a> and code is truth, so if you still doubt that such an idea can really be made to work\u2014and maybe you should\u2014you won't after we're done implementing it.<\/p>\n

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<\/em> is 1, B<\/em> is 2, &c.<\/em>). Here are some functions to help with that\u2014<\/p>\n

from string import ascii_uppercase\r\n\r\nALPHABET = " "+ascii_uppercase\r\nCHAR_TO_INT = dict(zip(ALPHABET, range(27)))\r\nINT_TO_CHAR = dict(zip(range(27), ALPHABET))\r\n\r\ndef pad(text, chunk_size):\r\n    return text + ' '*(chunk_size - len(text) % chunk_size)\r\n\r\ndef chunkify(text, chunk_size):\r\n    return [text[i:i+chunk_size]\r\n            for i in range(0, len(text), chunk_size)]\r\n\r\ndef convert(string):\r\n    return [CHAR_TO_INT[c] for c in string]<\/code><\/pre>\n
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.<\/em>, the list [1, 2, 3] represents the function 1 + 2x<\/em> + 3x<\/em>2<\/sup>. Then we can take points on that polynomial at n<\/em> different values of the independent variable x<\/em> for some n<\/em> greater than the chunk size to get a properly redundant encoding.<\/p>\n
(It's actually better if you use polynomials over the finite field<\/em> 𝔽q<\/em><\/sub> of the integers modulo q<\/em> for some q<\/em> which is a prime raised to the power of something, but let's not worry about that.)<\/p>\n
def evaluate_polynomial(coefficients, x):\r\n    return sum(c * x**i for i, c in enumerate(coefficients))\r\n\r\ndef encode(chunk, n):\r\n    return [evaluate_polynomial(chunk, i) for i in range(n)]\r\n\r\ndef erasure_code(text, chunk_size, encoded_chunk_size):\r\n    chunks = chunkify(pad(text, chunk_size), chunk_size)\r\n    converted_chunks = [convert(chunk) for chunk in chunks]\r\n    return [list(enumerate(encode(chunk, encoded_chunk_size)))\r\n            for chunk in converted_chunks]<\/code><\/pre>\n
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.<\/p>\n
$ python3\r\n>>> from reed_solomon import *\r\n>>> text = "THE FUNDAMENTAL PROBLEM OF COMMUNICATION IS THAT OF\r\nREPRODUCING AT ONE POINT EITHER EXACTLY OR APPROXIMATELY A MESSAGE\r\nSELECTED AT ANOTHER POINT"\r\n>>> encoded = erasure_code(text, 5, 8)\r\n>>> encoded\r\n[[(0, 20), (1, 39), (2, 152), (3, 575), (4, 1668), (5, 3935), (6,\r\n8024), (7, 14727)], [(0, 21), (1, 53), (2, 281), (3, 1179), (4, 3533),\r\n(5, 8441), (6, 17313), (7, 31871)], [(0, 5), ...<\/code><\/pre>\n
[further output redacted]<\/em><\/p>\n
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<\/em>, y<\/em>) coordinate pairs representing points on the polynomial representing that chunk.<\/p>\n
Let's simulate distributing that encoded information across several storage nodes by writing points with different x<\/em>-values to different files. We'll make-believe that each file is a different storage node. We'll write another function for that.<\/p>\n
import json\r\n\r\ndef disperse(encoded_chunks):\r\n    node_count = len(encoded_chunks[0])\r\n    for i in range(node_count):\r\n        with open('node'+str(i), 'w') as node:\r\n            node.write(json.dumps([chunk[i] for chunk in encoded_chunks]))<\/code><\/pre>\n
And try it out\u2014<\/p>\n
>>> disperse(encoded)\r\n>>>\r\n$ ls\r\nnode0  node1  node2  node3  node4  node5  node6  node7\r\n$ cat node4\r\n[[4, 1668], [4, 3533], [4, 3517], [4, 1824], [4, 4080], [4, 4342],\r\n[4, 1665], [4, 4769], [4, 5460], [4, 4172], [4, 4710], [4, 2254], [\r\n4, 433], [4, 2436], [4, 4464], [4, 5796], [4, 1596], [4, 4428], [4,\r\n 1417], [4, 5313], [4, 5452], [4, 709], [4, 6212], [4, 4973], [4, 5\r\n445], [4, 5205], [4, 6308], [4, 4412], [4, 1555]]<\/code><\/pre>\n
In conclusion, that's how you use Reed\u2013Solomon coding to turn comprehensible English text into inscrutable lists of lists of numbers distributed across several files. Thank you, and\u2014<\/p>\n
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\u2014we 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).<\/p>\n
def get_coefficient(P, i):\r\n    if 0 <= i < len(P):\r\n        return P[i]\r\n    else:\r\n        return 0\r\n\r\ndef add_polynomials(P, Q):\r\n    n = max(len(P), len(Q))\r\n    return [get_coefficient(P, i) + get_coefficient(Q, i) for i in range(n)]\r\n\r\ndef scale_polynomial(P, a):\r\n    return [a*c for c in P]\r\n\r\ndef multiply_polynomials(P, Q):\r\n    maximum_terms = len(P) + len(Q)\r\n    R = [0 for _ in range(maximum_terms)]\r\n    for i, c in enumerate(P):\r\n        for j, d in enumerate(Q):\r\n            R[i+j] += c * d\r\n    return R<\/code><\/pre>\n
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<\/em>, after the great mathematician-astronomer Joseph-Louis Lagrange<\/a>.<\/p>\n
Suppose we want to reconstruct a cubic polynomial from the four points (x1<\/sub><\/em>, y1<\/sub><\/em>), (x2<\/sub><\/em>, y2<\/sub><\/em>), (x3<\/sub><\/em>, y3<\/sub><\/em>), and (x4<\/sub><\/em>, y4<\/sub><\/em>). It turns out that a formula for the polynomial is<\/p>\n
y1<\/sub><\/em>\u21131<\/sub>(x<\/em>) + y2<\/sub><\/em>\u21132<\/sub>(x<\/em>) + y3<\/sub><\/em>\u21133<\/sub>(x<\/em>) + y4<\/sub><\/em>\u21134<\/sub>(x<\/em>)<\/p>\n
where \u21131<\/sub>(x<\/em>) (the first Lagrange basis element<\/em>) stands for<\/p>\n
((x<\/em> \u2013 x<\/em>2<\/sub>)(x<\/em> \u2013 x<\/em>3<\/sub>)(x<\/em> \u2013 x<\/em>4<\/sub>)) \/ ((x<\/em>1<\/sub> \u2013 x<\/em>2<\/sub>)(x<\/em>1<\/sub> \u2013 x<\/em>3<\/sub>)(x<\/em>1<\/sub> \u2013 x<\/em>4<\/sub>))<\/p>\n
and so on\u2014for each i<\/em> between 1 and the number of points we have, the numerator of the i<\/em>th Lagrange basis element is the product of (x<\/em> \u2013 x<\/em>j<\/em><\/sub>) for all j<\/em> from 1 up to the number of points we have but not equal to i<\/em>, and the denominator follows a similar pattern but with x<\/em>i<\/em><\/sub> instead of x<\/em>. (Note that we're using letters with subscripts, like x<\/em>i<\/em><\/sub>, to represent specific constants, whereas x<\/em> without a subscript is a function's independent variable.)<\/p>\n
I hear you ask, "But why this particular<\/em> 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<\/em> equal to x<\/em>1<\/sub>. The second through fourth terms y<\/em>2<\/sub>\u21132<\/sub>(x<\/em>1<\/sub>) through y<\/em>4<\/sub>\u21134<\/sub>(x<\/em>1<\/sub>) all contain a factor of (x<\/em>1<\/sub> \u2013 x<\/em>1<\/sub>) and are thus zero, but the first term becomes<\/p>\n
y<\/em>1<\/sub> ((x<\/em>1<\/sub> \u2013 x<\/em>2<\/sub>)(x<\/em>1<\/sub> \u2013 x<\/em>3<\/sub>)(x<\/em>1<\/sub> \u2013 x<\/em>4<\/sub>)) \/ ((x<\/em>1<\/sub> \u2013 x<\/em>2<\/sub>)(x<\/em>1<\/sub> \u2013 x<\/em>3<\/sub>)(x<\/em>1<\/sub> \u2013 x<\/em>4<\/sub>))<\/p>\n
= y<\/em>1<\/sub>(1)<\/p>\n
= y<\/em>1<\/sub>.<\/p>\n
So by design, our interpolated polynomial takes value y<\/em>1<\/sub> at x<\/em>1<\/sub>, y<\/em>2<\/sub> at x<\/em>2<\/sub>, and so forth. In Python, the whole process looks like this\u2014<\/p>\n
def lagrange_basis_denominator(xs, i):\r\n    denominator = 1\r\n    for j, x in enumerate(xs):\r\n        if j == i:\r\n            continue\r\n        denominator *= xs[i] - xs[j]\r\n    return denominator\r\n\r\ndef lagrange_basis_element(xs, i):\r\n    element = [1]\r\n    for j in range(len(xs)):\r\n        if j == i:\r\n            continue\r\n        element = multiply_polynomials(element, [-xs[j], 1])\r\n    scaling_factor = 1\/lagrange_basis_denominator(xs, i)\r\n    return scale_polynomial(element, scaling_factor)\r\n\r\ndef interpolate(points):\r\n    result = [0]\r\n    xs, ys = zip(*points)\r\n    for i in range(len(points)):\r\n        result = add_polynomials(\r\n            result,\r\n            scale_polynomial(lagrange_basis_element(xs, i), ys[i])\r\n        )\r\n    return [round(k) for k in result]<\/code><\/pre>\n
(Note that we're rounding off our computed coefficients because this implementation isn't very numerically stable<\/em>\u2014the 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\u2014but let's not worry about that, either.)<\/p>\n
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<\/em> the polynomial from them, deconvert<\/em> the numbers which are the coefficients of that polynomial back into their character equivalents, unchunkify<\/em> the chunks into a unified whole, and unpad<\/em> any whitespace we added to the end when we began.<\/p>\n
def deconvert(sequence):\r\n    return ''.join(INT_TO_CHAR[i] for i in sequence)\r\n\r\ndef unchunkify(chunks):\r\n    return ''.join(chunks)\r\n\r\ndef unpad(text):\r\n    return text.rstrip()\r\n\r\ndef erasure_decode(encoded_chunks, chunk_size, encoded_chunk_size):\r\n    converted_chunks = [interpolate(chunk[:chunk_size])[:chunk_size]\r\n                        for chunk in encoded_chunks]\r\n    return unpad(unchunkify(deconvert(chunk) for chunk in converted_chunks))<\/code><\/pre>\n
But about<\/em> that data that we wrote out earlier.<\/p>\n
$ ls\r\nnode0  node1  node2  node3  node4  node5  node6  node7<\/code><\/pre>\n
It would hardly be a compelling test of our erasure-coding skills if there were any suspicion that we actually needed all<\/em> of those files\u2014we really only need as many as our chunk size. So let's suppose that three of our nodes die in a fire\u2014<\/p>\n
$ rm node1 node3 node6\r\n$ ls\r\nnode0  node2  node4  node5  node7<\/code><\/pre>\n
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\u2014<\/p>\n
def retrieve(*nodes):\r\n    responses = []\r\n    for node in nodes:\r\n        with open(node) as our_node:\r\n            responses.append(json.loads(our_node.read()))\r\n    return [[response[i] for response in responses]\r\n            for i in range(len(responses[0]))]<\/code><\/pre>\n
\u2014and then\u2014<\/p>\n
$ python3\r\n>>> from reed_solomon import *\r\n>>> node_data = retrieve("node0", "node2", "node4", "node5", "node7")<\/code><\/pre>\n
\u2014successfully decode them!<\/p>\n
>>> erasure_decode(node_data, 5, 8)\r\n'THE FUNDAMENTAL PROBLEM OF COMMUNICATION IS THAT OF REPRODUCING AT\r\n ONE POINT EITHER EXACTLY OR APPROXIMATELY A MESSAGE SELECTED AT AN\r\nOTHER POINT'<\/code><\/pre>\n
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!<\/p>\n
And even if you personally have no intention of deploying Swift\u2014as 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<\/em>.<\/p>\n
The code in this post is available separately<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
(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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[20],"tags":[73,21],"_links":{"self":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1561"}],"collection":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/comments?post=1561"}],"version-history":[{"count":6,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1561\/revisions"}],"predecessor-version":[{"id":1568,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1561\/revisions\/1568"}],"wp:attachment":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/media?parent=1561"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/categories?post=1561"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/tags?post=1561"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}