Hi Andreas, Here is a preliminary implementation https://github.com/ceph/ceph/pull/1921 . It does not have tests yet, nor does it run but but it compiles and I think it makes sense. It is indeed simpler than the previous implementation.
It would be great if you could quickly browse https://github.com/dachary/ceph/commit/5661c72864eca04c5dac9494a3f7e7a13515fca6 and let me know if you have any concerns. Cheers On 31/05/2014 19:10, Loic Dachary wrote: > Hi Andreas, > > After a few weeks and a fresh eye, I revisited the way pyramid erasure code > could be described by the system administrator. Here is a proposal that is > hopefully more intuitive than the one from the last CDS ( > http://pad.ceph.com/p/cdsgiant-pyramid-erasure-code ). > > These are the steps to create all coding chunks. The upper case letters are > data chunks and the lower case letters are coding chunks. > > "__ABC__DE_" data chunks placement > > Step 1 > "__ABC__DE_" > "_yVWX_zYZ_" K=5, M=2 > "_aABC_bDE_" > > Step 2 > "_aABC_bDE_" > "z_XYZ_____" K=3, M=1 > "caABC_bDE_" > > Step 3 > "caABC_bDE_" > "_____zXYZ_" K=3, M=1 > "caABCdbDE_" > > Step 4 > "caABCdbDE_" > "_____WXYZz" K=4, M=1 > "caABCdbDEe" > > The interpretation of Step 3 is as follows: > > Given the output of the previous step ( "caABC_bDE_" ), the bDE chunks are > considered to be data chunks at this stage and they are marked with XYZ. A > K=3, M=1 coding chunk is calculated and placed in the chunk marked with z ( > "_____zXYZ_" ). The output of this coding step is the previous step plus the > coding chunk that was just calculated, named d ( "caABCdbDE_" ). > > This gives the flexibility of deciding wether or not a coding chunk from a > previous step is used as data to compute the coding chunk of the next step. > It also allows for unbalanced steps such as step 4. > > For decoding, the steps are walked from the bottom up. If E is missing, it > can be reconstructed from dbD.e in step 4 and the other steps are skipped > because it was the only missing chunk. If AB are missing, all steps that have > not be used to encode it are ignored, up to step 2 that will fail to recover > them because M=1 and yeild to step 1 that will use a..CbDE successfully > because M=2. > > Giving up the recursion and favor iteration seems to simplify how it can be > explained. And I suspect the implementation is also simpler. What do you > think ? > > Cheers > -- Loïc Dachary, Artisan Logiciel Libre
signature.asc
Description: OpenPGP digital signature
