ceph/ceph — pull request #1142 by dachary (2014-01-25 23:15:41+00:00)
Title: erasure code pyramid plugin

An erasure code plugin providing an implementation of
ErasureCodeInterface. The caller can specify how to recursively apply
erasure coding to the chunks to control the placement of the erasure
coded chunks.

For instance with a crush ruleset containing the following steps:

take root
set choose datacenter 2
set choose devices 5

An erasure coded pool is given 10 OSDs ( 0123456789 ) the first five (
01234 ) are in a datacenter, the last five ( 56789 ) are in another
datacenter.

Creating a pyramidal layout by which recovering from the loss of a
single OSD does not require getting data from an OSD located in another
datacenter can be done with:

[
{ "plugin": "jerasure",
"technique": "cauchy_good",
"k": "6",
"m": "2",
"mapping": "^-ABCDEF-^",
},

{ "plugin": "xor",
"k": "3",
"m": "1",
"type": "datacenter",
"size": 2,
"mapping": "-^ABCDEF^-",
},
]

The object is first encoded in six data chunks ( "k": "6" ) and two
coding chunks ( "m": "2" ) by the first layer of the pyramid, using the
jerasure plugin ( "plugin": "jerasure" ). The jerasure plugin creates a
total of eight chunks ( k=6 + m=2 == 8 ) and ensures that the first six
contain the original data. If the data chunks were designated by letters
and the coding chunks by ^, it could be something like ABCDEF^^

If used outside of the context of the pyramid plugin, the jerasure
plugin would spread data and coding chunks as follows ( the dash -
designates a chunk that is not being used ):

01324 56789
ABCDE F^^--

i.e. with the first five data chunks in a datacenter ( the crush ruleset
above provides OSDs 01234 in one datacenter and 56789 in another ) and
the remaining chunks in another datacenter. The pyramid plugin remaps it (
"mapping": "^-ABCDEF-^" ) and the chunk placement becomes :

01234 56789
^-ABC DEF-^

which is more evenly distributed, with three data chunks and a coding
chunk in one datacenter plus three data chunks and a coding chunk in
another datacenter.

The next level of the pyramid is expected to create coding chunks that
allows recovery without crossing datacenter boundaries, using a XOR
coding ( "plugin": "xor" ) supporting the loss of a single chunk ( "m":
"1" ) out of the three ( "k": "3" ) found in a given datacenter. It
starts by splitting the chunks in two ( "size": 2 ), starting with:

01234
^-ABC

The XOR plugin is given ABC as an input and creates ABC^ which are
remapped into

01234
-^ABC

as specified in the first half of the mapping ( "mapping": "-^ABCDEF^-"
). The coding chunk of the previous level of the pyramid is left
undisturbed because the dash ( - ) in the mapping requires that it is
not used.

The same logic can be applied to three levels with:

take root
set choose datacenter 2
set choose rack 2
set choose devices 5

^-ABC-DEF--GHI-JKL-^
-^ABC-DEF--GHI-JKL^- datacenter
--ABC^DEF^^GHI^JKL-- rack

http://tracker.ceph.com/issues/7238 Fixes: #7238