1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
============================
Erasure Code developer notes
============================
Introduction
------------
Each chapter of this document explains an aspect of the implementation
of the erasure code within Ceph. It is mostly based on examples being
explained to demonstrate how things work.
Reading and writing encoded chunks from and to OSDs
---------------------------------------------------
An erasure coded pool stores each object as K+M chunks. It is divided
into K data chunks and M coding chunks. The pool is configured to have
a size of K+M so that each chunk is stored in an OSD in the acting
set. The rank of the chunk is stored as an attribute of the object.
Let's say an erasure coded pool is created to use five OSDs ( K+M =
5 ) and sustain the loss of two of them ( M = 2 ).
When the object *NYAN* containing *ABCDEFGHI* is written to it, the
erasure encoding function splits the content in three data chunks,
simply by dividing the content in three : the first contains *ABC*,
the second *DEF* and the last *GHI*. The content will be padded if the
content length is not a multiple of K. The function also creates two
coding chunks : the fourth with *YXY* and the fifth with *GQC*. Each
chunk is stored in an OSD in the acting set. The chunks are stored in
objects that have the same name ( *NYAN* ) but reside on different
OSDs. The order in which the chunks were created must be preserved and
is stored as an attribute of the object ( shard_t ), in addition to its
name. Chunk *1* contains *ABC* and is stored on *OSD5* while chunk *4*
contains *YXY* and is stored on *OSD3*.
::
+-------------------+
name | NYAN |
+-------------------+
content | ABCDEFGHI |
+--------+----------+
|
|
v
+------+------+
+---------------+ encode(3,2) +-----------+
| +--+--+---+---+ |
| | | | |
| +-------+ | +-----+ |
| | | | |
+--v---+ +--v---+ +--v---+ +--v---+ +--v---+
name | NYAN | | NYAN | | NYAN | | NYAN | | NYAN |
+------+ +------+ +------+ +------+ +------+
shard | 1 | | 2 | | 3 | | 4 | | 5 |
+------+ +------+ +------+ +------+ +------+
content | ABC | | DEF | | GHI | | YXY | | QGC |
+--+---+ +--+---+ +--+---+ +--+---+ +--+---+
| | | | |
| | | | |
| | +--+---+ | |
| | | OSD1 | | |
| | +------+ | |
| | +------+ | |
| +------>| OSD2 | | |
| +------+ | |
| +------+ | |
| | OSD3 |<----+ |
| +------+ |
| +------+ |
| | OSD4 |<--------------+
| +------+
| +------+
+----------------->| OSD5 |
+------+
When the object *NYAN* is read from the erasure coded pool, the
decoding function reads three chunks : chunk *1* containing *ABC*,
chunk *3* containing *GHI* and chunk *4* containing *YXY* and rebuild
the original content of the object *ABCDEFGHI*. The decoding function
is informed that the chunks *2* and *5* are missing ( they are called
*erasures* ). The chunk *5* could not be read because the *OSD4* is
*out*.
The decoding function could be called as soon as three chunks are
read : *OSD2* was the slowest and its chunk does not need to be taken into
account. This optimization is not implemented in Firefly.
::
+-------------------+
name | NYAN |
+-------------------+
content | ABCDEFGHI |
+--------+----------+
^
|
|
+------+------+
| decode(3,2) |
| erasures 2,5|
+-------------->| |
| +-------------+
| ^ ^
| | +-----+
| | |
+--+---+ +------+ +--+---+ +--+---+
name | NYAN | | NYAN | | NYAN | | NYAN |
+------+ +------+ +------+ +------+
shard | 1 | | 2 | | 3 | | 4 |
+------+ +------+ +------+ +------+
content | ABC | | DEF | | GHI | | YXY |
+--+---+ +--+---+ +--+---+ +--+---+
^ . ^ ^
| TOO . | |
| SLOW . +--+---+ |
| ^ | OSD1 | |
| | +------+ |
| | +------+ |
| +-------| OSD2 | |
| +------+ |
| +------+ |
| | OSD3 |-----+
| +------+
| +------+
| | OSD4 | OUT
| +------+
| +------+
+------------------| OSD5 |
+------+
Erasure code library
--------------------
Using `Reed-Solomon <https://en.wikipedia.org/wiki/Reed_Solomon>`_,
with parameters K+M, object O is encoded by dividing it into chunks O1,
O2, ... OM and computing coding chunks P1, P2, ... PK. Any K chunks
out of the available K+M chunks can be used to obtain the original
object. If data chunk O2 or coding chunk P2 are lost, they can be
repaired using any K chunks out of the K+M chunks. If more than M
chunks are lost, it is not possible to recover the object.
Reading the original content of object O can be a simple
concatenation of O1, O2, ... OM, because the plugins are using
`systematic codes
<http://en.wikipedia.org/wiki/Systematic_code>`_. Otherwise the chunks
must be given to the erasure code library *decode* method to retrieve
the content of the object.
Performance depend on the parameters to the encoding functions and
is also influenced by the packet sizes used when calling the encoding
functions ( for Cauchy or Liberation for instance ): smaller packets
means more calls and more overhead.
Although Reed-Solomon is provided as a default, Ceph uses it via an
`abstract API <https://github.com/ceph/ceph/blob/v0.78/src/erasure-code/ErasureCodeInterface.h>`_ designed to
allow each pool to choose the plugin that implements it using
key=value pairs stored in an `erasure code profile`_.
.. _erasure code profile: ../../../erasure-coded-pool
::
$ ceph osd erasure-code-profile set myprofile \
crush-failure-domain=osd
$ ceph osd erasure-code-profile get myprofile
directory=/usr/lib/ceph/erasure-code
k=2
m=1
plugin=jerasure
technique=reed_sol_van
crush-failure-domain=osd
$ ceph osd pool create ecpool 12 12 erasure myprofile
The *plugin* is dynamically loaded from *directory* and expected to
implement the *int __erasure_code_init(char *plugin_name, char *directory)* function
which is responsible for registering an object derived from *ErasureCodePlugin*
in the registry. The `ErasureCodePluginExample <https://github.com/ceph/ceph/blob/v0.78/src/test/erasure-code/ErasureCodePluginExample.cc>`_ plugin reads:
::
ErasureCodePluginRegistry &instance =
ErasureCodePluginRegistry::instance();
instance.add(plugin_name, new ErasureCodePluginExample());
The *ErasureCodePlugin* derived object must provide a factory method
from which the concrete implementation of the *ErasureCodeInterface*
object can be generated. The `ErasureCodePluginExample plugin <https://github.com/ceph/ceph/blob/v0.78/src/test/erasure-code/ErasureCodePluginExample.cc>`_ reads:
::
virtual int factory(const map<std::string,std::string> ¶meters,
ErasureCodeInterfaceRef *erasure_code) {
*erasure_code = ErasureCodeInterfaceRef(new ErasureCodeExample(parameters));
return 0;
}
The *parameters* argument is the list of *key=value* pairs that were
set in the erasure code profile, before the pool was created.
::
ceph osd erasure-code-profile set myprofile \
directory=<dir> \ # mandatory
plugin=jerasure \ # mandatory
m=10 \ # optional and plugin dependant
k=3 \ # optional and plugin dependant
technique=reed_sol_van \ # optional and plugin dependant
Notes
-----
If the objects are large, it may be impractical to encode and decode
them in memory. However, when using *RBD* a 1TB device is divided in
many individual 4MB objects and *RGW* does the same.
Encoding and decoding is implemented in the OSD. Although it could be
implemented client side for read write, the OSD must be able to encode
and decode on its own when scrubbing.
|
