On 06/14/2013 03:13 PM, Martin Flyvbjerg wrote:
Dear Community
I am a young engineer (not software or math, please bare with me) with some
suggestions regarding erasure codes. I never used Ceph before or any other
distributed file system.
I stumped upon the suggestion for adding erasure codes to Ceph, as
described in this article
http://wiki.Ceph.com/01Planning/02Blueprints/Dumpling/Erasure_encoding_as_a_storage_backend
first I would like to say great initiative to add erasure codes to Ceph.
Ceph needs its own implementation and it have to be done right, I cannot stress
this enough, suggested software mentioned in that article would result in very
low performance.
Why?
Reed-Solomon is normally something regarded as being very slow compared to
other erasure codes, because the underlying Galois-Field multiplication is
slow. Please see video at usenix.org forexplanation.
The implementations of Zfec library and other suggested software the others
rely on the Vandermonde matrix, a matrix used in in Reed-Solomon erasure codes,
a faster approach would be to use the Cauchy-Reed-Solomon implementation.
Please see [1,2,3]
Although there is something even better, by using the Intel SSE2/3 SIMD
instructions it is possible to do the as fast as any other XOR based erasure
codes (RaptorQ LT-codes, LDPC etc.).
The suggested FECpp lib uses the optimisation but with a relative small
Galois-field only 2^8, since Ceph aimes at unlimited scalability increasing the
size of the Galois-Field would improve performance [4]. Of course the
configured Ceph Object Size and/or Stripe width have to be taken into account.
Please see
https://www.usenix.org/conference/fast13/screaming-fast-galois-field-arithmetic-using-sse2-extensions
The solution
Using the GF-Complete open source library [4] to implement Reed-Solomon in Ceph
in order to allow Ceph to scale to infinity.
James S. Plank the author of GF-complete have developed a library implementing
various Reed-Solomon codes called Jerasure.
http://web.eecs.utk.edu/~plank/plank/www/software.html
Jerasure 2.0 using the GF-complete artimetric based in Intel SSE SIMD
instructions, is current in development expected release august 2013. Will be
released under the new BSD license. Jerasure 2.0 also supports arbitrary
Galois-field sizes 8,16,32,64 or 128 bit.
The limit of this implementation would be the processors L2/L3 cache not the
underlying arithmetic.
Thanks for all the info and the links Martin! It would be useful to sit
down and figure out how much overhead we'd expect to see with each
implementation. I'm definitely in favour of looking at
Cauchy-Reed-Solomon (and any specific SSE/SIMD implementations) assuming
there's not a lot of additional complexity or other downsides. I won't
be doing the development work though, so it's easy for me to say that. ;)
Mark
Best Regards
Martin Flyvbjerg
[1] http://web.eecs.utk.edu/~plank/plank/papers/CS-05-569.pdf
[2] http://web.eecs.utk.edu/~plank/plank/papers/CS-08-625.pdf
[3] http://web.eecs.utk.edu/~plank/plank/papers/FAST-2009.pdf
[4] http://web.eecs.utk.edu/~plank/plank/papers/FAST-2013-GF.pdf
--
To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
