{"id":33651,"date":"2015-06-16T07:59:56","date_gmt":"2015-06-16T14:59:56","guid":{"rendered":"https:\/\/www.backblaze.com\/blog\/?p=33651"},"modified":"2023-04-26T11:54:33","modified_gmt":"2023-04-26T18:54:33","slug":"reed-solomon","status":"publish","type":"post","link":"https:\/\/www.backblaze.com\/blog\/reed-solomon\/","title":{"rendered":"Backblaze Open-sources Reed-Solomon Erasure Coding Source Code"},"content":{"rendered":"

\"Reed<\/p>\n

At Backblaze we have built an extremely cost-effective storage system that enables us to offer a great price on our online backup service<\/a>. Along the path to building our storage system, we have used time-tested technologies off the shelf, but we have also built in-house technologies ourselves when things weren\u2019t available, or when the price was too high.<\/p>\n

We have taken advantage of many open-source projects, and want to do our part in contributing back to the community. Our first foray into open-source was our original Storage Pod design<\/a>, back in September of 2009.<\/p>\n

Today, we are releasing our latest open-source project: Backblaze Reed-Solomon, a Java library for erasure coding.<\/p>\n

An erasure code<\/a> takes a \u201cmessage,\u201d such as a data file, and makes a longer message in a way that the original can be reconstructed from the longer message even if parts of the longer message have been lost. Reed-Solomon<\/a> is an erasure code with exactly the properties we needed for file storage, and it is simple and straightforward to implement. It ensures that an entire data element can be recovered even when part or parts of the original stored data element are lost or unavailable.<\/p>\n

\n

Download the Open-Source Code<\/h4>\n

You can find the source code for Backblaze Reed-Solomon on GitHub<\/a>. <\/p>\n

The code is licensed with the MIT License<\/a>, which means that you can use it in your own projects for free. You can even use it in commercial projects. We’ve put together a video titled: “Reed-Solomon Erasure Coding Overview”<\/a> to get you started.\n<\/div>\n

Erasure Codes and Storage<\/h2>\n

Erasure coding is standard practice for systems that store data reliably, and many of them use Reed-Solomon coding.<\/p>\n

The RAID system built into Linux uses Reed-Solomon. It has a carefully tuned Reed-Solomon implementation in C that is part of the RAID module. Microsoft Azure uses a similar, but different, erasure coding strategy. We\u2019re not sure exactly what Amazon S3 and Google Cloud Storage<\/a> use because they haven\u2019t said, but it\u2019s bound to be Reed-Solomon or something similar. Facebook\u2019s new cold storage system also uses Reed-Solomon.<\/p>\n

If you want reliable storage that can recover from the loss of parts of the data, then Reed-Solomon is a well-proven technique.<\/p>\n

Backblaze Vaults Utilize Erasure Coding<\/h2>\n

Earlier this year, I wrote about Backblaze Vaults<\/a>, our new software architecture that allows a file to be stored across multiple Storage Pods, so that the file can be available for download even when some Storage Pods are shut down for maintenance.<\/p>\n

To make Backblaze Vaults work, we needed an erasure coding library to compute<\/a> \u201cparity\u201d and then use it to reconstruct files. When a file is stored in a Vault, it is broken into 17 pieces, all the same size. Then three additional pieces are created that hold parity, resulting in a total of 20 pieces. The original file can then be reconstructed from any 17 of the 20 pieces.<\/p>\n

We needed a simple, reliable, and efficient Java library to do Reed-Solomon coding, but didn\u2019t find any. So we built our own. And now we are releasing that code for you to use in your own projects.<\/p>\n

Performance<\/h2>\n

Backblaze Vaults store a vast amount of data and need to be able to ingest it quickly. This means that the Reed-Solomon coding must be fast. When we started designing Vaults, we assumed that we would need to code in C to make things fast. It turned out, though, that modern Java virtual machines are really good, and the just-in-time compiler produces code that runs fast.<\/p>\n

Our Java library for Reed-Solomon is as fast as a C implementation, and is much easier to integrate with a software stack written in Java.<\/p>\n

A Vault splits data into 17 shards, and has to calculate three parity shards from that, so that\u2019s the configuration we use for performance measurements. Running in a single thread on Storage Pod<\/a> hardware, our library can process incoming data at 149 megabytes per second. (This test was run on a single processor core, on a Pod with an Intel Xeon E5-1620 v2, clocked at 3.70GHz, on data not already in cache memory.)<\/p>\n

Reed-Solomon Encoding Matrix Example<\/h2>\n

Feel free to skip this section if you aren\u2019t into the math.<\/p>\n

We are fortunate that mathematicians have been working on matrix algebra, group theory, and information theory for centuries. Reed and Solomon used this body of knowledge to create a coding system that seems like magic. It can take a message, break it into n pieces, add k \u201cparity\u201d pieces, and then reconstruct the original from n of the (n+k) pieces.<\/p>\n

The examples below use a \u201c4+2\u201d coding system, where the original file is broken into four pieces, and then two parity pieces are added. In Backblaze Vaults, we use 17+3 (17 data plus three parity). The math\u2014and the code\u2014works with any numbers as long as you have at least one data shard and don\u2019t have more than 256 shards total. To use Reed-Solomon, you put your data into a matrix. For computer files, each element of the matrix is one byte from the file. The bytes are laid out in a grid to form a matrix. If your data file has \u201cABCDEFGHIJKLMNOP\u201d in it, you can lay it out like this:<\/p>\n

The Original Data<\/strong>
\n\"The<\/div>\n

In this example, the four pieces of the file are each four bytes long. Each piece is one row of the matrix. The first one is \u201cABCD.\u201d The second one is \u201cEFGH.\u201d And so on.
\nThe Reed-Solomon algorithm creates a coding matrix that you multiply with your data matrix to create the coded data. The matrix is set up so that the first four rows of the result are the same as the first four rows of the input. That means that the data is left intact, and all it\u2019s really doing is computing the parity.<\/p>\n

Applying the Coding Matrix<\/strong>
\n\"Erasure<\/div>\n

The result is a matrix with two more rows than the original. Those two rows are the parity pieces.<\/p>\n

Each row of the coding matrix produces one row of the result. So each row of the coding matrix makes one of the resulting pieces of the file. Because the rows are independent, you can cross out two of the rows and the equation still holds.<\/p>\n

Data Loss: Two of the Six Rows Are “Lost”<\/strong>
\n\"Data<\/div>\n

With those rows completely gone, it looks like this:<\/p>\n

Data Loss: The Matrix Without the Two “Lost” Rows<\/strong>
\n\"Data<\/div>\n

Because of all the work that mathematicians have done over the years, we know the coding matrix, the matrix on the left, is invertible. There is an inverse matrix that, when multiplied by the coding matrix, produces the identity matrix. As in basic algebra, in matrix algebra you can multiply both sides of an equation by the same thing. In this case, we\u2019ll multiply on the left by the identity matrix:<\/p>\n

Multiplying Each Side of the Equation by the Inverse Matrix<\/strong>
\n\"MultiplyingThe Inverse Matrix and the Coding Matrix Cancel Out<\/strong>
\n\"The<\/div>\n

This leaves the equation for reconstructing the original data from the pieces that are available:<\/p>\n

Reconstructing the Original Data<\/strong>
\n\"Reconstructing<\/div>\n

So to make a decoding matrix, the process is to take the original coding matrix, cross out the rows for the missing pieces, and then find the inverse matrix. You can then multiply the inverse matrix and the pieces that are available to reconstruct the original data.<\/p>\n

Summary<\/h2>\n

That was a quick overview of the math. Once you understand the steps, it\u2019s not super complicated. The Java code goes through the same steps outlined above.<\/p>\n

There is one small part of the code that does the actual matrix multiplications that has been carefully optimized for speed. The rest of the code does not need to be fast, so we aimed more for simple and clear.<\/p>\n

If you need to store or transmit data, and be able to recover it if some is lost, you might want to look at Reed-Solomon coding. Using our code is an easy way to get started.<\/p>\n","protected":false},"excerpt":{"rendered":"

At Backblaze we have built an extremely cost-effective storage system that enables us to offer a great price on our online backup service. Along the path to building our storage system, we have used time-tested technologies off the shelf, but we have also built in-house technologies ourselves when things weren\u2019t available, or when the price… Continue reading Backblaze Open-sources Reed-Solomon Erasure Coding Source Code<\/span><\/a><\/p>\n","protected":false},"author":15,"featured_media":33681,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"content-type":"","footnotes":""},"categories":[7],"tags":[468,373,161],"class_list":["post-33651","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cloud-storage","tag-b2cloud","tag-developer","tag-vaults","entry"],"acf":[],"yoast_head":"\nErasure Coding: Backblaze Open Sources Reed-Solomon Code<\/title>\n<meta name=\"description\" content=\"Today we are releasing our latest open-source project: Backblaze Reed-Solomon Java library for erasure coding. Click for details on how to use and download.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.backblaze.com\/blog\/reed-solomon\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Backblaze Releases the Reed-Solomon Java Library for Free\" \/>\n<meta property=\"og:description\" content=\"Today we are releasing our latest open-source project: Backblaze Reed-Solomon Java library for erasure coding. Click for details on how to use and download.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/\" \/>\n<meta property=\"og:site_name\" content=\"Backblaze Blog | Cloud Storage & Cloud Backup\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/backblaze\" \/>\n<meta property=\"article:published_time\" content=\"2015-06-16T14:59:56+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-04-26T18:54:33+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/backblazeprod.wpenginepowered.com\/wp-content\/uploads\/2015\/06\/blog-reed-solomon-header.png\" \/>\n\t<meta property=\"og:image:width\" content=\"720\" \/>\n\t<meta property=\"og:image:height\" content=\"335\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Brian Beach\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:title\" content=\"Download the Backblaze Reed-Solomon erasure encoding Java library for free\" \/>\n<meta name=\"twitter:creator\" content=\"@backblaze\" \/>\n<meta name=\"twitter:site\" content=\"@backblaze\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Brian Beach\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"8 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Erasure Coding: Backblaze Open Sources Reed-Solomon Code","description":"Today we are releasing our latest open-source project: Backblaze Reed-Solomon Java library for erasure coding. Click for details on how to use and download.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.backblaze.com\/blog\/reed-solomon\/","og_locale":"en_US","og_type":"article","og_title":"Backblaze Releases the Reed-Solomon Java Library for Free","og_description":"Today we are releasing our latest open-source project: Backblaze Reed-Solomon Java library for erasure coding. Click for details on how to use and download.","og_url":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/","og_site_name":"Backblaze Blog | Cloud Storage & Cloud Backup","article_publisher":"https:\/\/www.facebook.com\/backblaze","article_published_time":"2015-06-16T14:59:56+00:00","article_modified_time":"2023-04-26T18:54:33+00:00","og_image":[{"width":720,"height":335,"url":"https:\/\/backblazeprod.wpenginepowered.com\/wp-content\/uploads\/2015\/06\/blog-reed-solomon-header.png","type":"image\/png"}],"author":"Brian Beach","twitter_card":"summary_large_image","twitter_title":"Download the Backblaze Reed-Solomon erasure encoding Java library for free","twitter_creator":"@backblaze","twitter_site":"@backblaze","twitter_misc":{"Written by":"Brian Beach","Est. reading time":"8 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/#article","isPartOf":{"@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/"},"author":{"name":"Brian Beach","@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/#\/schema\/person\/fb38313d53b0e0c4158402c310badac1"},"headline":"Backblaze Open-sources Reed-Solomon Erasure Coding Source Code","datePublished":"2015-06-16T14:59:56+00:00","dateModified":"2023-04-26T18:54:33+00:00","mainEntityOfPage":{"@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/"},"wordCount":1338,"commentCount":25,"publisher":{"@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/#organization"},"image":{"@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/#primaryimage"},"thumbnailUrl":"https:\/\/backblazeprod.wpenginepowered.com\/wp-content\/uploads\/2015\/06\/blog-reed-solomon-header.png","keywords":["B2Cloud","Developer","Vaults"],"articleSection":["Cloud Storage"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/","url":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/","name":"Erasure Coding: Backblaze Open Sources Reed-Solomon Code","isPartOf":{"@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/#primaryimage"},"image":{"@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/#primaryimage"},"thumbnailUrl":"https:\/\/backblazeprod.wpenginepowered.com\/wp-content\/uploads\/2015\/06\/blog-reed-solomon-header.png","datePublished":"2015-06-16T14:59:56+00:00","dateModified":"2023-04-26T18:54:33+00:00","description":"Today we are releasing our latest open-source project: Backblaze Reed-Solomon Java library for erasure coding. Click for details on how to use and download.","breadcrumb":{"@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/#primaryimage","url":"https:\/\/backblazeprod.wpenginepowered.com\/wp-content\/uploads\/2015\/06\/blog-reed-solomon-header.png","contentUrl":"https:\/\/backblazeprod.wpenginepowered.com\/wp-content\/uploads\/2015\/06\/blog-reed-solomon-header.png","width":720,"height":335,"caption":"Backblaze Reed-Solomon Erasure Coding"},{"@type":"BreadcrumbList","@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/reed-solomon\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Backblaze Open-sources Reed-Solomon Erasure Coding Source Code"}]},{"@type":"WebSite","@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/#website","url":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/","name":"Backblaze Cloud Solutions Blog","description":"Cloud Storage & Cloud Backup","publisher":{"@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/#organization","name":"Backblaze","url":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/#\/schema\/logo\/image\/","url":"https:\/\/i0.wp.com\/www.backblaze.com\/blog\/wp-content\/uploads\/2017\/12\/backblaze_icon_transparent.png?fit=512%2C512&ssl=1","contentUrl":"https:\/\/i0.wp.com\/www.backblaze.com\/blog\/wp-content\/uploads\/2017\/12\/backblaze_icon_transparent.png?fit=512%2C512&ssl=1","width":512,"height":512,"caption":"Backblaze"},"image":{"@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/backblaze","https:\/\/x.com\/backblaze","https:\/\/www.youtube.com\/user\/Backblaze","https:\/\/en.wikipedia.org\/wiki\/Backblaze"]},{"@type":"Person","@id":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/#\/schema\/person\/fb38313d53b0e0c4158402c310badac1","name":"Brian Beach","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/backblazeprod.wpenginepowered.com\/wp-content\/uploads\/2019\/04\/brian_beach-150x150.png","url":"https:\/\/backblazeprod.wpenginepowered.com\/wp-content\/uploads\/2019\/04\/brian_beach-150x150.png","contentUrl":"https:\/\/backblazeprod.wpenginepowered.com\/wp-content\/uploads\/2019\/04\/brian_beach-150x150.png","caption":"Brian Beach"},"description":"Brian has been writing software for three decades at HP Labs, Silicon Graphics, Netscape, TiVo, and now Backblaze. His passion is building things that make life better, like the TiVo DVR and Backblaze Online Backup.","url":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/author\/brianb\/"}]}},"jetpack_featured_media_url":"https:\/\/backblazeprod.wpenginepowered.com\/wp-content\/uploads\/2015\/06\/blog-reed-solomon-header.png","_links":{"self":[{"href":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/wp-json\/wp\/v2\/posts\/33651","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/wp-json\/wp\/v2\/users\/15"}],"replies":[{"embeddable":true,"href":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/wp-json\/wp\/v2\/comments?post=33651"}],"version-history":[{"count":0,"href":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/wp-json\/wp\/v2\/posts\/33651\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/wp-json\/wp\/v2\/media\/33681"}],"wp:attachment":[{"href":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/wp-json\/wp\/v2\/media?parent=33651"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/wp-json\/wp\/v2\/categories?post=33651"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/backblazeprod.wpenginepowered.com\/blog\/wp-json\/wp\/v2\/tags?post=33651"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}