Erasure Coding

[Alex Elsayed]

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