Zfec – Efficient, portable erasure coding tool(github.com)
github.com
Zfec – Efficient, portable erasure coding tool
https://github.com/tahoe-lafs/zfec
37 comments
One of the authors of Tahoe-LAFS and the original creator of zfec, Zooko, co-authored a paper on the performance of such codes.
http://nisl.wayne.edu/Papers/Tech/code-pf-fast09.pdf
Luigi Rizzo is the original author of the fec C library.
I co-maintain zfec (and the Debian package of it) along with Zooko. A new release of zfec is planned to be out soonish.
edit: removing the <> delimiters around the URL. Sorry!
http://nisl.wayne.edu/Papers/Tech/code-pf-fast09.pdf
Luigi Rizzo is the original author of the fec C library.
I co-maintain zfec (and the Debian package of it) along with Zooko. A new release of zfec is planned to be out soonish.
edit: removing the <> delimiters around the URL. Sorry!
HN sadly does not support <> URL delimiters, so your link ends up 404. Here is it without delimiters:
http://nisl.wayne.edu/Papers/Tech/code-pf-fast09.pdf
http://nisl.wayne.edu/Papers/Tech/code-pf-fast09.pdf
Thanks. Updated the link.
I don't know of any cross-library comparison benchmark. Also, if a library does ship with an internal benchmark, it usually uses a different number of data/parity shards and different shard size, compared to other library benchmarks, which makes comparison difficult.
I wrote an MIT-licensed ReedSolomon module for Node [1], with native C++ multi-core throughput. The internal benchmark (node benchmark.js) provides latency and throughput measurements for data=10, parity=4 for a variety of shard sizes, and the number of data/parity shards can be adjusted for comparison.
It's not yet using optimized assembler or SIMD like Klaus Post's implementation, but it is compatible and also based on Backblaze's implementation, as well as including a pure Javascript implementation for browser use.
[1] https://github.com/jorangreef/reed-solomon
I wrote an MIT-licensed ReedSolomon module for Node [1], with native C++ multi-core throughput. The internal benchmark (node benchmark.js) provides latency and throughput measurements for data=10, parity=4 for a variety of shard sizes, and the number of data/parity shards can be adjusted for comparison.
It's not yet using optimized assembler or SIMD like Klaus Post's implementation, but it is compatible and also based on Backblaze's implementation, as well as including a pure Javascript implementation for browser use.
[1] https://github.com/jorangreef/reed-solomon
I ported Klaus' library to Haskell, and redid the whole SIMD implementation (see below for the extras this brings): https://github.com/NicolasT/reedsolomon/
In my library, the SSSE3 code also has AVX and AVX2 equivalents, providing higher throughput. There are also implementations with specific optimized instructions for ARM NEON, ARM64, PPC64/AltiVec and Power8. All of this in C (with intrinsics), not ASM, so making use of your C compiler's instruction scheduling, loop unrolling,... See https://github.com/NicolasT/reedsolomon/blob/master/cbits/re...
In my library, the SSSE3 code also has AVX and AVX2 equivalents, providing higher throughput. There are also implementations with specific optimized instructions for ARM NEON, ARM64, PPC64/AltiVec and Power8. All of this in C (with intrinsics), not ASM, so making use of your C compiler's instruction scheduling, loop unrolling,... See https://github.com/NicolasT/reedsolomon/blob/master/cbits/re...
The one you linked to is excellent. It has hand crafted SSE3 assembler for enormous speed. It is a bit difficult to compare the benchmarks from the one in the original posting to Klaus's as they aren't done at the same (N,K) parameters though.
[deleted]
Papers usually compare against jerasure:
http://jerasure.org/jerasure/jerasure
I find liberasurecode more interesting
https://github.com/openstack/liberasurecode
BSD licensed
Pluggable erasure coding backends, and supports Intel's ISA-L
There is also a Python library available https://bitbucket.org/kmgreen2/pyeclib
BSD licensed
Pluggable erasure coding backends, and supports Intel's ISA-L
There is also a Python library available https://bitbucket.org/kmgreen2/pyeclib
PyECLib upstream is now at https://github.com/openstack/pyeclib
Another tool that is the de-facto standard on usenet for erasure coding is .par2 https://en.wikipedia.org/wiki/Parchive
I'm not sure PAR2 really counts as erasure coding rather than a more general FEC. I've tried zfec in the past but it's not really set up for backup uses such as creating an archive to burn to a set of BD disks.
For backups, what you want to generate additional files, par2 style, which can be combined with the regular archive files (eg like in duplicity, GPG-encrypted tarballs) to repair any bitrot or lost fractions of those archives. But with zfec, as I understood it, it only works if you turn them entirely into erasure-coded shares and assume you'll lose entire shares and wind up using m-of-n shares in recovery/restoration (as opposed to PAR2 which will handle losing individual archive files but also arbitrary corruption in any of those archive files, as long as the total does not exceed the redundancy %). So you would have to do something like create a single giant archive file, and if you wanted the equivalent of 50% redundancy, you'd use zfec to turn it into '50-of-100' shares and backup the 100 shares (or do 500-of-1000 etc).
Then any shares which aren't bit-identical to get tossed out at restoration and you hope you have enough shares left to reconstruct the original giant archive file. But you might not - your shares might be mostly good but missing a few chunks, which is something a PAR2 setup could cope with (if the chunks are in the archive files, they get repaired normally, and if they're in the PAR2 redundancy, they don't matter). This is fine in the Taho-LAFS or datacenter setup where you assume your storage nodes will store perfectly or fail entirely (since given any live errors, you can just scrub the entire machine and rebuild an additional copy from the erasure-coded shares). Not so much in a backup setting.
Ultimately, while zfec is way faster than par2, I found this setup squirrely enough that I wasn't convinced to switch.
For backups, what you want to generate additional files, par2 style, which can be combined with the regular archive files (eg like in duplicity, GPG-encrypted tarballs) to repair any bitrot or lost fractions of those archives. But with zfec, as I understood it, it only works if you turn them entirely into erasure-coded shares and assume you'll lose entire shares and wind up using m-of-n shares in recovery/restoration (as opposed to PAR2 which will handle losing individual archive files but also arbitrary corruption in any of those archive files, as long as the total does not exceed the redundancy %). So you would have to do something like create a single giant archive file, and if you wanted the equivalent of 50% redundancy, you'd use zfec to turn it into '50-of-100' shares and backup the 100 shares (or do 500-of-1000 etc).
Then any shares which aren't bit-identical to get tossed out at restoration and you hope you have enough shares left to reconstruct the original giant archive file. But you might not - your shares might be mostly good but missing a few chunks, which is something a PAR2 setup could cope with (if the chunks are in the archive files, they get repaired normally, and if they're in the PAR2 redundancy, they don't matter). This is fine in the Taho-LAFS or datacenter setup where you assume your storage nodes will store perfectly or fail entirely (since given any live errors, you can just scrub the entire machine and rebuild an additional copy from the erasure-coded shares). Not so much in a backup setting.
Ultimately, while zfec is way faster than par2, I found this setup squirrely enough that I wasn't convinced to switch.
I was going to ask if this was like PAR.
Slightly offtopic (although the title contains "portable"): it often saddens me that purely mathematical functions like these are so tightly coupled to implementation language (even though there are three different language bindings here). Shouldn't the programming community have advanced past that point by now?
I'm not sure it's a thing to be advanced past. Using a language to implement a given pure function is inherent to deploying it.
You could develop one universal way to create and deploy functions to different languages, but now you've introduced one more language to get people to use.
And in practical terms, migrating this sort of thing from one language to another when necessary is generally a good enough solution.
You could develop one universal way to create and deploy functions to different languages, but now you've introduced one more language to get people to use.
And in practical terms, migrating this sort of thing from one language to another when necessary is generally a good enough solution.
Can you give an example of what you mean?
Maybe he has this in mind:
Imagine a high-level, straightforward imperative language X whose only purpose is to specify libraries and data structures. This X has strong typing, memory safety and maybe also memory alignment directives but abstracts away as much as possible from any actual environment/platform/CPU layout. It has a precise semantics and even some ways of specifying pragmatics (e.g. big O runtime behavior of functions). In X you write "pure" algorithms that do not access (m)any OS-dependent features. Libraries in this language are then transpiled to various target languages and platforms.
To use all libraries that have ever been written for X, someone only needs to write a transpiler-backend for the target language/platform once.
LLVM intermediate language is similar but too low-level. Think about a high-level counterpart.
Imagine a high-level, straightforward imperative language X whose only purpose is to specify libraries and data structures. This X has strong typing, memory safety and maybe also memory alignment directives but abstracts away as much as possible from any actual environment/platform/CPU layout. It has a precise semantics and even some ways of specifying pragmatics (e.g. big O runtime behavior of functions). In X you write "pure" algorithms that do not access (m)any OS-dependent features. Libraries in this language are then transpiled to various target languages and platforms.
To use all libraries that have ever been written for X, someone only needs to write a transpiler-backend for the target language/platform once.
LLVM intermediate language is similar but too low-level. Think about a high-level counterpart.
Just guessing at the parent's intent, but the specification of a function can be decoupled from the production of an optimized implementation of that function, especially if the structure of the function is constrained in some way.
This approach is used to some degree in producing, for example, optimized BLAS implementations and other similar routines:
http://view.eecs.berkeley.edu/wiki/Autotuners
Of course, you do then need to juggle multiple languages. Different languages can be better at expressing different things, though (e.g., "what the function does" versus "how the function does it"), so it's not inherently crazy.
This approach is used to some degree in producing, for example, optimized BLAS implementations and other similar routines:
http://view.eecs.berkeley.edu/wiki/Autotuners
Of course, you do then need to juggle multiple languages. Different languages can be better at expressing different things, though (e.g., "what the function does" versus "how the function does it"), so it's not inherently crazy.
While FECs are useful, I really wish there was a free and good implementation of fountain codes [1].
[1]: https://en.m.wikipedia.org/wiki/Fountain_code
[1]: https://en.m.wikipedia.org/wiki/Fountain_code
Here is an implementation of RaptorQ (a fountain code). It is in alpha and actively developed: https://github.com/LucaFulchir/libRaptorQ
The standard: https://tools.ietf.org/html/rfc6330
The standard: https://tools.ietf.org/html/rfc6330
I believe fountain codes are patented so you are unlikely to see a free and open implementation.
According to this comment: https://news.ycombinator.com/item?id=2684488
Qualcomm now owns the patents.
According to this comment: https://news.ycombinator.com/item?id=2684488
Qualcomm now owns the patents.
Are software patents a thing outside US? Surely plenty of hackers in EU could use such a library.
I believe that software can be patented in the EU if you have a clever patent agent...
From wikipedia: https://en.wikipedia.org/wiki/Software_patents_under_the_Eur...
> Under the EPC, and in particular its Article 52,[1] "programs for computers" are not regarded as inventions for the purpose of granting European patents,[2] but this exclusion from patentability only applies to the extent to which a European patent application or European patent relates to a computer program as such.[3] As a result of this partial exclusion, and despite the fact that the EPO subjects patent applications in this field to a much stricter scrutiny[4] when compared to their American counterpart, that does not mean that all inventions including some software are de jure not patentable.
Going back to the original question, I certainly wouldn't want to start an open source project knowing that Qualcomm might sue me for patent infringement. Defending their intellectual property is part of their core business strategy.
From wikipedia: https://en.wikipedia.org/wiki/Software_patents_under_the_Eur...
> Under the EPC, and in particular its Article 52,[1] "programs for computers" are not regarded as inventions for the purpose of granting European patents,[2] but this exclusion from patentability only applies to the extent to which a European patent application or European patent relates to a computer program as such.[3] As a result of this partial exclusion, and despite the fact that the EPO subjects patent applications in this field to a much stricter scrutiny[4] when compared to their American counterpart, that does not mean that all inventions including some software are de jure not patentable.
Going back to the original question, I certainly wouldn't want to start an open source project knowing that Qualcomm might sue me for patent infringement. Defending their intellectual property is part of their core business strategy.
Yes, but patent process is more strict.
http://www.europeansoftwarepatents.com/howtos/software-paten...
https://en.wikipedia.org/wiki/Software_patents_under_the_Eur...
http://www.europeansoftwarepatents.com/howtos/software-paten...
https://en.wikipedia.org/wiki/Software_patents_under_the_Eur...
Wirehair is a hybrid LDPC code which can be used like a Fountain code. It has astonishingly low overhead for one.
https://github.com/catid/wirehair/
https://github.com/catid/wirehair/
In face of cheap TB disks erasure coding seems to be a far better option than RAID.
http://www.computerweekly.com/feature/Erasure-coding-versus-...
Is there any empirical data which zfec parameters are recommended for which device? AFAIK reliability is DVD < Blueray < SSD < HD < tape < cloud.
http://www.computerweekly.com/feature/Erasure-coding-versus-...
Is there any empirical data which zfec parameters are recommended for which device? AFAIK reliability is DVD < Blueray < SSD < HD < tape < cloud.
Never seen this licence before : https://github.com/tahoe-lafs/zfec/blob/master/COPYING.TGPPL...
Anyone knows more details?
Anyone knows more details?
Seems to exist since 2010: https://thunk.org/tytso/blog/2010/01/20/the-transitive-grace...
Originals version of the license: http://zooko.com/tgppl.html
Seems like the goal was to keep the product under copyright for some time, giving it a opportunity to recover costs or integrated exclusively inside a product for a while, giving some advantage over competitors, but making it a public-license after the period.
Also found this explanation: https://tahoe-lafs.org/~zooko/tgppl.pdf
Originals version of the license: http://zooko.com/tgppl.html
Seems like the goal was to keep the product under copyright for some time, giving it a opportunity to recover costs or integrated exclusively inside a product for a while, giving some advantage over competitors, but making it a public-license after the period.
Also found this explanation: https://tahoe-lafs.org/~zooko/tgppl.pdf
Zfec is really slow compared to state of the art CRS codes like cm256: https://github.com/catid/cm256
Another plug for https://math.stackexchange.com/questions/663643/discover-par... given n inputs & outputs of a reed solomon function is it possible to derive the parameters?
Is it like https://en.wikipedia.org/wiki/Tornado_code ?
They were used for reliable data distribution, being able to recover from loss of packets without requesting the packets be sent again.
They were used for reliable data distribution, being able to recover from loss of packets without requesting the packets be sent again.
Just curious: any similar libraries for the other class of erasure codes, the fountain codes?
Can anyone explain to me, what is the usage of `erasure code` ?
As a quick answer, the name comes from being able to recover data when some of it is "erased".
The only way to durably store data so that it survives a hardware failure (e.g. drive dying) is to store more than one copy. Full replicas are the simplest way to do this, but you've got a relatively high overhead (e.g. Store 1GB of data with 3x replicas, and you store 3GB of data). Erasure codes are a way to effectively store fractional replicas, so you only use 1.5x or 1.7x of the original data.
Erasure codes are great when you've got a lot of data and you need high durability but don't want to pay for the storage space required for full replicas.
Why don't we always use erasure codes for everything? EC isn't great when you've got small bits of data, and since there's a bit of math involved in reading and writing the EC data, EC has higher latency than simple replicas.
https://www.swiftstack.com/blog/2015/04/20/the-foundations-o... is a great into to how erasure codes work.
The only way to durably store data so that it survives a hardware failure (e.g. drive dying) is to store more than one copy. Full replicas are the simplest way to do this, but you've got a relatively high overhead (e.g. Store 1GB of data with 3x replicas, and you store 3GB of data). Erasure codes are a way to effectively store fractional replicas, so you only use 1.5x or 1.7x of the original data.
Erasure codes are great when you've got a lot of data and you need high durability but don't want to pay for the storage space required for full replicas.
Why don't we always use erasure codes for everything? EC isn't great when you've got small bits of data, and since there's a bit of math involved in reading and writing the EC data, EC has higher latency than simple replicas.
https://www.swiftstack.com/blog/2015/04/20/the-foundations-o... is a great into to how erasure codes work.
The project behind it, Tahoe-LAFS deserves some love.
Basically, spread your data across many cloud storage providers and built a super fast soft-RAID.
Basically, spread your data across many cloud storage providers and built a super fast soft-RAID.
I tried Tahoe-LAFS, the setup seems a bit weird and from trying it on that public gateway a bit, there seem to be some issues in relation to what happens if you loose that link to your folder.
There seems to be no way of using it to simply attach and have a list of your data only.
I'm favoring Camlistore over Tahoe, though Camli has no good encryption yet and no erasure encoding. The basis of Camli seems to be better.
There seems to be no way of using it to simply attach and have a list of your data only.
I'm favoring Camlistore over Tahoe, though Camli has no good encryption yet and no erasure encoding. The basis of Camli seems to be better.
I believe it's compatible with the Java implementation used by Backblaze and others.