Hi Loic, I am happy to contribute with some clarifications. In fact, erasure/reliability concepts are not blocking my progress with the reliability model at ceph. It is the ceph model itself that has some parts not clear to me, and nobody had time yet to review the state model diagram that I published on the wiki. :( Anyway, regarding coefficients here is a bit of background. Coefficients are the numbers that multiply your variables inside an equation. In a toy example, to solve the equation ax^2+bx+c=0 you need to find the coefficients a,b,c that make the equation valid. In the context of Reed Solomon, the definition of coefficients is a bit more confusing. In the original design, the message x is interpreted as coefficients of a polynomial p. But in subsequents interpretations the message x is seen as the values of the polynomial p evaluated at the first k points a1..ak. Such interpretation is apparently a bit less efficient but desirable because you can construct a systematic code. In the context of xorbas, you are constructing a code on top of Reed Solomon. The codewords are seen as values, and the idea is to get coefficients c1..c10 that also satisfy s1+s2+s3=0 (take this as a missing introduction to my previous message) Cheers, koleosfuscus ________________________________________________________________ "My reply is: the software has no known bugs, therefore it has not been updated." Wietse Venema On Sun, Jun 29, 2014 at 8:44 PM, Loic Dachary <loic@xxxxxxxxxxx> wrote: > Hi koleofuscus, > > Thanks for the explanation : it is very conforting to know that you understand this :-) At the risk of being thick, I must say that the very notion of "coefficient" eludes me. What are they ? > > Cheers > > On 29/06/2014 20:38, Koleos Fuscus wrote: >> Hello Loic, >> Dimakis (one of the authors of xorbas) is talking about coefficients >> because they want to find a way to reduce the storage overhead used >> with LRC. In the simple case used in Fig. 2, a RS (k=10, m=4) has >> 14/10 storage overhead but when using LRC, the overhead increases to >> 17/10 because you also need to store s1, s2 and s3. Basically, the >> idea is to find specific coefficients c1..c10 that permit to obtain s3 >> through s1 and s2. In other words, get some s1 and s2 that when xored >> together give s3. If you find such coefficients, you don't need to >> store s3 and the storage overhead of LRC is 1.6x instead of 1.7x. >> >> Dimakis said that for the Reed Solomon implementation used in HDFS >> RAID they can simple set all coefficients with value '1' and use xor. >> >> This cannot be the case of the Reed Solomon implemented by you (I >> understood is the jerasure library by Plank) but that I am not sure. I >> guess we need the help of a mathematician or at least check and >> compare both implementations. >> >> Finally, apparently for xorbas they only implemented the configuration >> RS(10,4) and not other combinations. Unfortunately, the wiki page of >> the project is empty http://wiki.apache.org/hadoop/ErasureCode and the >> main page says 'erasure coding under development'. >> >> I recommend you to watch the xorbas presentation video >> http://smahesh.com/HadoopUSC/ (a very clear explanation of xorbas) and >> use the Dimakis wiki page to check the large collection of paper they >> have: http://storagewiki.ece.utexas.edu/ >> >> Best, >> >> koleosfuscus >> >> ________________________________________________________________ >> "My reply is: the software has no known bugs, therefore it has not >> been updated." >> Wietse Venema >> >> >> On Sun, Jun 29, 2014 at 11:30 AM, Loic Dachary <loic@xxxxxxxxxxx> wrote: >>> Hi Andreas, >>> >>> In http://anrg.usc.edu/~maheswaran/Xorbas.pdf I get the idea of computing local coding chunks the way it is implemented in https://github.com/ceph/ceph/pull/1921 (i.e. delegating encoding / decoding to other plugins). However, there are theoretical aspects of the paper that I do not understand and I'm hoping you can shed some light on it. In particular, I don't know what "coefficients" are about. For instance in the context of Figure 2 caption : "The main theoretical challenge is to choose the coeffi cients c(i) to maximize the fault tolerance of the code." >>> >>> Would you recommend a paper to read to better understand this ? Also I'd like to understand what "coefficients" mean in the context of jerasure or if they do not apply. >>> >>> Thanks for you help :-) >>> >>> -- >>> Loïc Dachary, Artisan Logiciel Libre >>> > > -- > Loïc Dachary, Artisan Logiciel Libre > -- To unsubscribe from this list: send the line "unsubscribe ceph-devel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
