Erasure Coding

[Alex Elsayed]

Alex Elsayed wrote:

> David Vorick wrote:
> 
>> Hi, I've started working on a project that's similar to Tahoe-LAFS, in
>> that it's a distributed cluster of machines hosting a bunch of files.
>> 
>> Erasure coding is important, but I've been having trouble learning about
>> the different types of erasure coding to be confident that I'll be able
>> to pick the best for my needs. I was hoping you could point to some
>> links, papers, or otherwise help out.
>> 
>> Ideally (in order of importance):
>> 
>> + machines can participate in many clusters simultaneously (and many
>> clusters can exist simultaneously)
>> + 100s - 1000s of machines per cluster
>> + if a machine corrupts or is otherwise lost, it's portion of the file
>> can be replaced quickly and without using many network resources
>> + low redundancy
>> 
>> less important but still important:
>> 
>> + cluster size can expand or shrink dynamically
>> + some machines only need to be online some of the time
>> 
>> I've looked at Reed-Solomon coding, which seems to be useful but not
>> ideal (too expensive to replace lost nodes)
>> I've also looked at raptor codes, which seem promising but I don't
>> understand them, and there seem to be patent issues.
>> 
>> In general, I've been unsuccessful at finding resources to learn about
>> erasure codes, but persistence has been slowly turning up useful
>> resources.
> 
> Regarding Reed-Solomon codes, there are a number of options out there in
> terms of making it faster. James Plank has a high-performance
> implementation called GF-Complete[1] which is planned for use in Ceph, and
> there is a current thread on the btrfs & linux RAID mailing lists on using
> Cauchy Reed- Solomon codes to offer arbitrary parity with high performance
> while retaining compatibility with the existing raid5/6 implementation[2].
> 
> The IPR disclosure on RFC 6330[3]  ("RaptorQ Forward Error Correction
> Scheme for Object Delivery") indicates that implementing RFC 6330 is safe,
> but since I'm guessing you want this for the actual stored data that's
> likely not sufficent for you.
> 
> Hope this helps!
> 
> [1] http://web.eecs.utk.edu/~plank/plank/papers/CS-13-703.html
> [2] http://thread.gmane.org/gmane.comp.file-systems.btrfs/30159
> [3] http://tools.ietf.org/html/rfc6330

In fact, several of Plank's other papers may be of interest to you. The list 
is here: http://web.eecs.utk.edu/~plank/plank/papers/

The ones I'd recommend in particular:

"Assessing the Performance of Erasure Codes in the Wide-Area"

"Optimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Network Storage 
Applications"

"Rethinking Erasure Codes for Cloud File Systems: Minimizing I/O for 
Recovery and Degraded Reads"

"SD Codes: Erasure Codes Designed for How Storage Systems Really Fail"