1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2014 Cloudwatt <libre.licensing@cloudwatt.com>
7 * Copyright (C) 2014 Red Hat <contact@redhat.com>
9 * Author: Loic Dachary <loic@dachary.org>
11 * This library is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Lesser General Public
13 * License as published by the Free Software Foundation; either
14 * version 2.1 of the License, or (at your option) any later version.
21 #include "include/str_map.h"
22 #include "common/debug.h"
23 #include "crush/CrushWrapper.h"
24 #include "osd/osd_types.h"
25 #include "include/stringify.h"
26 #include "erasure-code/ErasureCodePlugin.h"
27 #include "json_spirit/json_spirit_writer.h"
29 #include "ErasureCodeLrc.h"
31 // re-include our assert to clobber boost's
32 #include "include/assert.h"
34 #define dout_context g_ceph_context
35 #define dout_subsys ceph_subsys_osd
37 #define dout_prefix _prefix(_dout)
41 static ostream& _prefix(std::ostream* _dout)
43 return *_dout << "ErasureCodeLrc: ";
46 int ErasureCodeLrc::create_rule(const string &name,
50 if (crush.rule_exists(name)) {
51 *ss << "rule " << name << " exists";
54 if (!crush.name_exists(rule_root)) {
55 *ss << "root item " << rule_root << " does not exist";
58 int root = crush.get_item_id(rule_root);
59 if (rule_device_class.size()) {
60 if (!crush.class_exists(rule_device_class)) {
61 *ss << "device class " << rule_device_class << " does not exist";
64 int c = crush.get_class_id(rule_device_class);
65 if (crush.class_bucket.count(root) == 0 ||
66 crush.class_bucket[root].count(c) == 0) {
67 *ss << "root item " << rule_root << " has no devices with class "
71 root = crush.class_bucket[root][c];
75 for (rno = 0; rno < crush.get_max_rules(); rno++) {
76 if (!crush.rule_exists(rno) && !crush.ruleset_exists(rno))
80 int steps = 4 + rule_steps.size();
82 int max_rep = get_chunk_count();
84 ret = crush.add_rule(rno, steps, pg_pool_t::TYPE_ERASURE,
89 ret = crush.set_rule_step(rno, step++, CRUSH_RULE_SET_CHOOSELEAF_TRIES, 5, 0);
91 ret = crush.set_rule_step(rno, step++, CRUSH_RULE_SET_CHOOSE_TRIES, 100, 0);
93 ret = crush.set_rule_step(rno, step++, CRUSH_RULE_TAKE, root, 0);
95 // [ [ "choose", "rack", 2 ],
96 // [ "chooseleaf", "host", 5 ] ]
97 for (vector<Step>::const_iterator i = rule_steps.begin();
98 i != rule_steps.end();
100 int op = i->op == "chooseleaf" ?
101 CRUSH_RULE_CHOOSELEAF_INDEP : CRUSH_RULE_CHOOSE_INDEP;
102 int type = crush.get_type_id(i->type);
104 *ss << "unknown crush type " << i->type;
107 ret = crush.set_rule_step(rno, step++, op, i->n, type);
110 ret = crush.set_rule_step(rno, step++, CRUSH_RULE_EMIT, 0, 0);
112 crush.set_rule_name(rno, name);
116 int ErasureCodeLrc::layers_description(const ErasureCodeProfile &profile,
117 json_spirit::mArray *description,
120 if (profile.count("layers") == 0) {
121 *ss << "could not find 'layers' in " << profile << std::endl;
122 return ERROR_LRC_DESCRIPTION;
124 string str = profile.find("layers")->second;
126 json_spirit::mValue json;
127 json_spirit::read_or_throw(str, json);
129 if (json.type() != json_spirit::array_type) {
130 *ss << "layers='" << str
131 << "' must be a JSON array but is of type "
132 << json.type() << " instead" << std::endl;
133 return ERROR_LRC_ARRAY;
135 *description = json.get_array();
136 } catch (json_spirit::Error_position &e) {
137 *ss << "failed to parse layers='" << str << "'"
138 << " at line " << e.line_ << ", column " << e.column_
139 << " : " << e.reason_ << std::endl;
140 return ERROR_LRC_PARSE_JSON;
145 int ErasureCodeLrc::layers_parse(string description_string,
146 json_spirit::mArray description,
150 for (vector<json_spirit::mValue>::iterator i = description.begin();
151 i != description.end();
153 if (i->type() != json_spirit::array_type) {
154 stringstream json_string;
155 json_spirit::write(*i, json_string);
156 *ss << "each element of the array "
157 << description_string << " must be a JSON array but "
158 << json_string.str() << " at position " << position
159 << " is of type " << i->type() << " instead" << std::endl;
160 return ERROR_LRC_ARRAY;
162 json_spirit::mArray layer_json = i->get_array();
163 ErasureCodeProfile profile;
165 for (vector<json_spirit::mValue>::iterator j = layer_json.begin();
166 j != layer_json.end();
169 if (j->type() != json_spirit::str_type) {
170 stringstream element;
171 json_spirit::write(*j, element);
172 *ss << "the first element of the entry "
173 << element.str() << " (first is zero) "
174 << position << " in " << description_string
175 << " is of type " << (*j).type() << " instead of string" << std::endl;
176 return ERROR_LRC_STR;
178 layers.push_back(Layer(j->get_str()));
179 Layer &layer = layers.back();
180 layer.chunks_map = j->get_str();
181 } else if(index == 1) {
182 Layer &layer = layers.back();
183 if (j->type() != json_spirit::str_type &&
184 j->type() != json_spirit::obj_type) {
185 stringstream element;
186 json_spirit::write(*j, element);
187 *ss << "the second element of the entry "
188 << element.str() << " (first is zero) "
189 << position << " in " << description_string
190 << " is of type " << (*j).type() << " instead of string or object"
192 return ERROR_LRC_CONFIG_OPTIONS;
194 if (j->type() == json_spirit::str_type) {
195 int err = get_json_str_map(j->get_str(), *ss, &layer.profile);
198 } else if (j->type() == json_spirit::obj_type) {
199 json_spirit::mObject o = j->get_obj();
201 for (map<string, json_spirit::mValue>::iterator i = o.begin();
204 layer.profile[i->first] = i->second.get_str();
208 // ignore trailing elements
215 int ErasureCodeLrc::layers_init(ostream *ss)
217 ErasureCodePluginRegistry ®istry = ErasureCodePluginRegistry::instance();
218 for (unsigned int i = 0; i < layers.size(); i++) {
219 Layer &layer = layers[i];
221 for(std::string::iterator it = layer.chunks_map.begin();
222 it != layer.chunks_map.end();
225 layer.data.push_back(position);
227 layer.coding.push_back(position);
228 if (*it == 'c' || *it == 'D')
229 layer.chunks_as_set.insert(position);
232 layer.chunks = layer.data;
233 layer.chunks.insert(layer.chunks.end(),
234 layer.coding.begin(), layer.coding.end());
235 if (layer.profile.find("k") == layer.profile.end())
236 layer.profile["k"] = stringify(layer.data.size());
237 if (layer.profile.find("m") == layer.profile.end())
238 layer.profile["m"] = stringify(layer.coding.size());
239 if (layer.profile.find("plugin") == layer.profile.end())
240 layer.profile["plugin"] = "jerasure";
241 if (layer.profile.find("technique") == layer.profile.end())
242 layer.profile["technique"] = "reed_sol_van";
243 int err = registry.factory(layer.profile["plugin"],
254 int ErasureCodeLrc::layers_sanity_checks(string description_string,
259 if (layers.size() < 1) {
260 *ss << "layers parameter has " << layers.size()
261 << " which is less than the minimum of one. "
262 << description_string << std::endl;
263 return ERROR_LRC_LAYERS_COUNT;
265 for (vector<Layer>::const_iterator layer = layers.begin();
266 layer != layers.end();
268 if (chunk_count != layer->chunks_map.length()) {
269 *ss << "the first element of the array at position "
270 << position << " (starting from zero) "
271 << " is the string '" << layer->chunks_map
272 << " found in the layers parameter "
273 << description_string << ". It is expected to be "
274 << chunk_count << " characters long but is "
275 << layer->chunks_map.length() << " characters long instead "
277 return ERROR_LRC_MAPPING_SIZE;
283 int ErasureCodeLrc::parse(ErasureCodeProfile &profile,
286 int r = ErasureCode::parse(profile, ss);
290 return parse_rule(profile, ss);
293 const string ErasureCodeLrc::DEFAULT_KML("-1");
295 int ErasureCodeLrc::parse_kml(ErasureCodeProfile &profile,
298 int err = ErasureCode::parse(profile, ss);
299 const int DEFAULT_INT = -1;
301 err |= to_int("k", profile, &k, DEFAULT_KML, ss);
302 err |= to_int("m", profile, &m, DEFAULT_KML, ss);
303 err |= to_int("l", profile, &l, DEFAULT_KML, ss);
305 if (k == DEFAULT_INT && m == DEFAULT_INT && l == DEFAULT_INT)
308 if ((k != DEFAULT_INT || m != DEFAULT_INT || l != DEFAULT_INT) &&
309 (k == DEFAULT_INT || m == DEFAULT_INT || l == DEFAULT_INT)) {
310 *ss << "All of k, m, l must be set or none of them in "
311 << profile << std::endl;
312 return ERROR_LRC_ALL_OR_NOTHING;
315 const char *generated[] = { "mapping",
319 for (int i = 0; i < 3; i++) {
320 if (profile.count(generated[i])) {
321 *ss << "The " << generated[i] << " parameter cannot be set "
322 << "when k, m, l are set in " << profile << std::endl;
323 return ERROR_LRC_GENERATED;
328 *ss << "k + m must be a multiple of l in "
329 << profile << std::endl;
330 return ERROR_LRC_K_M_MODULO;
333 int local_group_count = (k + m) / l;
335 if (k % local_group_count) {
336 *ss << "k must be a multiple of (k + m) / l in "
337 << profile << std::endl;
338 return ERROR_LRC_K_MODULO;
341 if (m % local_group_count) {
342 *ss << "m must be a multiple of (k + m) / l in "
343 << profile << std::endl;
344 return ERROR_LRC_M_MODULO;
348 for (int i = 0; i < local_group_count; i++) {
349 mapping += string(k / local_group_count, 'D') +
350 string(m / local_group_count, '_') + "_";
352 profile["mapping"] = mapping;
354 string layers = "[ ";
358 for (int i = 0; i < local_group_count; i++) {
359 layers += string(k / local_group_count, 'D') +
360 string(m / local_group_count, 'c') + "_";
362 layers += "\", \"\" ],";
365 for (int i = 0; i < local_group_count; i++) {
367 for (int j = 0; j < local_group_count; j++) {
369 layers += string(l, 'D') + "c";
371 layers += string(l + 1, '_');
373 layers += "\", \"\" ],";
375 profile["layers"] = layers + "]";
377 ErasureCodeProfile::const_iterator parameter;
378 string rule_locality;
379 parameter = profile.find("crush-locality");
380 if (parameter != profile.end())
381 rule_locality = parameter->second;
382 string rule_failure_domain = "host";
383 parameter = profile.find("crush-failure-domain");
384 if (parameter != profile.end())
385 rule_failure_domain = parameter->second;
387 if (rule_locality != "") {
389 rule_steps.push_back(Step("choose", rule_locality,
391 rule_steps.push_back(Step("chooseleaf", rule_failure_domain,
393 } else if (rule_failure_domain != "") {
395 rule_steps.push_back(Step("chooseleaf", rule_failure_domain, 0));
401 int ErasureCodeLrc::parse_rule(ErasureCodeProfile &profile,
405 err |= to_string("crush-root", profile,
408 err |= to_string("crush-device-class", profile,
412 if (profile.count("crush-steps") != 0) {
414 string str = profile.find("crush-steps")->second;
415 json_spirit::mArray description;
417 json_spirit::mValue json;
418 json_spirit::read_or_throw(str, json);
420 if (json.type() != json_spirit::array_type) {
421 *ss << "crush-steps='" << str
422 << "' must be a JSON array but is of type "
423 << json.type() << " instead" << std::endl;
424 return ERROR_LRC_ARRAY;
426 description = json.get_array();
427 } catch (json_spirit::Error_position &e) {
428 *ss << "failed to parse crush-steps='" << str << "'"
429 << " at line " << e.line_ << ", column " << e.column_
430 << " : " << e.reason_ << std::endl;
431 return ERROR_LRC_PARSE_JSON;
435 for (vector<json_spirit::mValue>::iterator i = description.begin();
436 i != description.end();
438 if (i->type() != json_spirit::array_type) {
439 stringstream json_string;
440 json_spirit::write(*i, json_string);
441 *ss << "element of the array "
442 << str << " must be a JSON array but "
443 << json_string.str() << " at position " << position
444 << " is of type " << i->type() << " instead" << std::endl;
445 return ERROR_LRC_ARRAY;
447 int r = parse_rule_step(str, i->get_array(), ss);
455 int ErasureCodeLrc::parse_rule_step(string description_string,
456 json_spirit::mArray description,
459 stringstream json_string;
460 json_spirit::write(description, json_string);
465 for (vector<json_spirit::mValue>::iterator i = description.begin();
466 i != description.end();
468 if ((position == 0 || position == 1) &&
469 i->type() != json_spirit::str_type) {
470 *ss << "element " << position << " of the array "
471 << json_string.str() << " found in " << description_string
472 << " must be a JSON string but is of type "
473 << i->type() << " instead" << std::endl;
474 return position == 0 ? ERROR_LRC_RULE_OP : ERROR_LRC_RULE_TYPE;
476 if (position == 2 && i->type() != json_spirit::int_type) {
477 *ss << "element " << position << " of the array "
478 << json_string.str() << " found in " << description_string
479 << " must be a JSON int but is of type "
480 << i->type() << " instead" << std::endl;
481 return ERROR_LRC_RULE_N;
491 rule_steps.push_back(Step(op, type, n));
495 int ErasureCodeLrc::init(ErasureCodeProfile &profile,
500 r = parse_kml(profile, ss);
504 r = parse(profile, ss);
508 json_spirit::mArray description;
509 r = layers_description(profile, &description, ss);
513 string description_string = profile.find("layers")->second;
515 dout(10) << "init(" << description_string << ")" << dendl;
517 r = layers_parse(description_string, description, ss);
525 if (profile.count("mapping") == 0) {
526 *ss << "the 'mapping' profile is missing from " << profile;
527 return ERROR_LRC_MAPPING;
529 string mapping = profile.find("mapping")->second;
530 data_chunk_count = 0;
531 for(std::string::iterator it = mapping.begin(); it != mapping.end(); ++it) {
535 chunk_count = mapping.length();
537 r = layers_sanity_checks(description_string, ss);
542 // When initialized with kml, the profile parameters
543 // that were generated should not be stored because
544 // they would otherwise be exposed to the caller.
546 if (profile.find("l") != profile.end() &&
547 profile.find("l")->second != DEFAULT_KML) {
548 profile.erase("mapping");
549 profile.erase("layers");
551 ErasureCode::init(profile, ss);
555 set<int> ErasureCodeLrc::get_erasures(const set<int> &want,
556 const set<int> &available) const
559 set_difference(want.begin(), want.end(),
560 available.begin(), available.end(),
561 inserter(result, result.end()));
565 unsigned int ErasureCodeLrc::get_chunk_size(unsigned int object_size) const
567 return layers.front().erasure_code->get_chunk_size(object_size);
570 void p(const set<int> &s) { cerr << s; } // for gdb
572 int ErasureCodeLrc::minimum_to_decode(const set<int> &want_to_read,
573 const set<int> &available_chunks,
576 dout(20) << __func__ << " want_to_read " << want_to_read
577 << " available_chunks " << available_chunks << dendl;
579 set<int> erasures_total;
580 set<int> erasures_not_recovered;
581 set<int> erasures_want;
582 for (unsigned int i = 0; i < get_chunk_count(); ++i) {
583 if (available_chunks.count(i) == 0) {
584 erasures_total.insert(i);
585 erasures_not_recovered.insert(i);
586 if (want_to_read.count(i) != 0)
587 erasures_want.insert(i);
594 // When no chunk is missing there is no need to read more than what
597 if (erasures_want.empty()) {
598 *minimum = want_to_read;
599 dout(20) << __func__ << " minimum == want_to_read == "
600 << want_to_read << dendl;
607 // Try to recover erasures with as few chunks as possible.
609 for (vector<Layer>::reverse_iterator i = layers.rbegin();
613 // If this layer has no chunk that we want, skip it.
616 set_intersection(want_to_read.begin(), want_to_read.end(),
617 i->chunks_as_set.begin(), i->chunks_as_set.end(),
618 inserter(layer_want, layer_want.end()));
619 if (layer_want.empty())
622 // Are some of the chunks we want missing ?
624 set<int> layer_erasures;
625 set_intersection(layer_want.begin(), layer_want.end(),
626 erasures_want.begin(), erasures_want.end(),
627 inserter(layer_erasures, layer_erasures.end()));
628 set<int> layer_minimum;
629 if (layer_erasures.empty()) {
631 // The chunks we want are available, this is the minimum we need
634 layer_minimum = layer_want;
637 set_intersection(i->chunks_as_set.begin(), i->chunks_as_set.end(),
638 erasures_not_recovered.begin(), erasures_not_recovered.end(),
639 inserter(erasures, erasures.end()));
641 if (erasures.size() > i->erasure_code->get_coding_chunk_count()) {
643 // There are too many erasures for this layer to recover: skip
644 // it and hope that an upper layer will be do better.
649 // Get all available chunks in that layer to recover the
652 set_difference(i->chunks_as_set.begin(), i->chunks_as_set.end(),
653 erasures_not_recovered.begin(), erasures_not_recovered.end(),
654 inserter(layer_minimum, layer_minimum.end()));
656 // Chunks recovered by this layer are removed from the list of
657 // erasures so that upper levels do not attempt to recover
660 for (set<int>::const_iterator j = erasures.begin();
663 erasures_not_recovered.erase(*j);
664 if (erasures_want.count(*j))
665 erasures_want.erase(*j);
669 minimum->insert(layer_minimum.begin(), layer_minimum.end());
671 if (erasures_want.empty()) {
672 minimum->insert(want_to_read.begin(), want_to_read.end());
673 for (set<int>::const_iterator i = erasures_total.begin();
674 i != erasures_total.end();
676 if (minimum->count(*i))
679 dout(20) << __func__ << " minimum = " << *minimum << dendl;
688 // The previous strategy failed to recover from all erasures.
690 // Try to recover as many chunks as possible, even from layers
691 // that do not contain chunks that we want, in the hope that it
692 // will help the upper layers.
694 set<int> erasures_total;
695 for (unsigned int i = 0; i < get_chunk_count(); ++i) {
696 if (available_chunks.count(i) == 0)
697 erasures_total.insert(i);
700 for (vector<Layer>::reverse_iterator i = layers.rbegin();
703 set<int> layer_erasures;
704 set_intersection(i->chunks_as_set.begin(), i->chunks_as_set.end(),
705 erasures_total.begin(), erasures_total.end(),
706 inserter(layer_erasures, layer_erasures.end()));
708 // If this layer has no erasure, skip it
710 if (layer_erasures.empty())
713 if (layer_erasures.size() > 0 &&
714 layer_erasures.size() <= i->erasure_code->get_coding_chunk_count()) {
716 // chunks recovered by this layer are removed from the list of
717 // erasures so that upper levels know they can rely on their
720 for (set<int>::const_iterator j = layer_erasures.begin();
721 j != layer_erasures.end();
723 erasures_total.erase(*j);
727 if (erasures_total.empty()) {
729 // Do not try to be smart about what chunks are necessary to
730 // recover, use all available chunks.
732 *minimum = available_chunks;
733 dout(20) << __func__ << " minimum == available_chunks == "
734 << available_chunks << dendl;
739 derr << __func__ << " not enough chunks in " << available_chunks
740 << " to read " << want_to_read << dendl;
744 int ErasureCodeLrc::encode_chunks(const set<int> &want_to_encode,
745 map<int, bufferlist> *encoded)
747 unsigned int top = layers.size();
748 for (vector<Layer>::reverse_iterator i = layers.rbegin();
752 if (includes(i->chunks_as_set.begin(), i->chunks_as_set.end(),
753 want_to_encode.begin(), want_to_encode.end()))
757 for (unsigned int i = top; i < layers.size(); ++i) {
758 const Layer &layer = layers[i];
759 set<int> layer_want_to_encode;
760 map<int, bufferlist> layer_encoded;
762 for (vector<int>::const_iterator c = layer.chunks.begin();
763 c != layer.chunks.end();
765 layer_encoded[j] = (*encoded)[*c];
766 if (want_to_encode.find(*c) != want_to_encode.end())
767 layer_want_to_encode.insert(j);
770 int err = layer.erasure_code->encode_chunks(layer_want_to_encode,
773 derr << __func__ << " layer " << layer.chunks_map
774 << " failed with " << err << " trying to encode "
775 << layer_want_to_encode << dendl;
782 int ErasureCodeLrc::decode_chunks(const set<int> &want_to_read,
783 const map<int, bufferlist> &chunks,
784 map<int, bufferlist> *decoded)
786 set<int> available_chunks;
788 for (unsigned int i = 0; i < get_chunk_count(); ++i) {
789 if (chunks.count(i) != 0)
790 available_chunks.insert(i);
795 set<int> want_to_read_erasures;
797 for (vector<Layer>::reverse_iterator layer = layers.rbegin();
798 layer != layers.rend();
800 set<int> layer_erasures;
801 set_intersection(layer->chunks_as_set.begin(), layer->chunks_as_set.end(),
802 erasures.begin(), erasures.end(),
803 inserter(layer_erasures, layer_erasures.end()));
805 if (layer_erasures.size() >
806 layer->erasure_code->get_coding_chunk_count()) {
807 // skip because there are too many erasures for this layer to recover
808 } else if(layer_erasures.size() == 0) {
809 // skip because all chunks are already available
811 set<int> layer_want_to_read;
812 map<int, bufferlist> layer_chunks;
813 map<int, bufferlist> layer_decoded;
815 for (vector<int>::const_iterator c = layer->chunks.begin();
816 c != layer->chunks.end();
819 // Pick chunks from *decoded* instead of *chunks* to re-use
820 // chunks recovered by previous layers. In other words
821 // *chunks* does not change but *decoded* gradually improves
822 // as more layers recover from erasures.
824 if (erasures.count(*c) == 0)
825 layer_chunks[j] = (*decoded)[*c];
826 if (want_to_read.count(*c) != 0)
827 layer_want_to_read.insert(j);
828 layer_decoded[j] = (*decoded)[*c];
831 int err = layer->erasure_code->decode_chunks(layer_want_to_read,
835 derr << __func__ << " layer " << layer->chunks_map
836 << " failed with " << err << " trying to decode "
837 << layer_want_to_read << " with " << available_chunks << dendl;
841 for (vector<int>::const_iterator c = layer->chunks.begin();
842 c != layer->chunks.end();
844 (*decoded)[*c] = layer_decoded[j];
846 if (erasures.count(*c) != 0)
849 want_to_read_erasures.clear();
850 set_intersection(erasures.begin(), erasures.end(),
851 want_to_read.begin(), want_to_read.end(),
852 inserter(want_to_read_erasures, want_to_read_erasures.end()));
853 if (want_to_read_erasures.size() == 0)
858 if (want_to_read_erasures.size() > 0) {
859 derr << __func__ << " want to read " << want_to_read
860 << " with available_chunks = " << available_chunks
861 << " end up being unable to read " << want_to_read_erasures << dendl;