Ceph

h1. Erasure coded storage backend (step 2)

h3. Summary

See also the [[|transcript]] of the "session":https://www.youtube.com/watch?v=-K8bSHx7zJ0&t=30m00s and the associated "pad":http://pad.ceph.com/p/osd-erasure-coding.

As of "Dumpling":http://tracker.ceph.com/versions/160 Ceph keeps copies of objects to not loose them when hardware fails. It is an efficient solution for Ceph block storage but when performances are less important than cost, "erasure codes"http://en.wikipedia.org/wiki/Erasure_code achieves significant savings. For instance, instead of buying 3PB to store 1PB, it is enough to buy 1.5PB and have better resilience. Erasure coding an object works by splitting it in K data chunks ( let say 10 ) and computing M parity chunks ( let say 3 ). By storing each of the 13 chunks on different disks, it is possible to rebuild the original object even if 3 of them fail. It is better than the resilience provided by three copies and requires only half the space, but it comes at a price : it uses more CPU, bandwidth and is more complex to design.

The use cases of "Genomic data":http://www.annaisystems.com/, "backups":http://dachary.org/?p=2087 or others requiring cheap hardware, extremely resilient storage, written once or twice and rarely read are perfect matches for an erasure coded storage backend. Ceph was originaly designed to include "RAID4":https://github.com/ceph/ceph/blob/71531edd8a645a249f5edc984e5d8be85317abf7/src/osd/OSD.cc#L1356 as an alternative to replication and the work suspended during years was resumed after the [[Erasure encoding as a storage backend|first Ceph summit in May 2013.]]

h3. Owners

* Loic Dachary

* Samuel Just (Inktank)

h3. Current Status

* Scheduled for "Firefly ( Feb 2014 )":http://www.redhat.com/en/technologies/storage/ceph

* Loic Dachary full time developer

* Samuel Just "specifications":https://github.com/ceph/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst and code review

* Placement group code refactoring being worked on

* High level design "being worked on":https://github.com/ceph/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst with a "PGBackend interface":https://github.com/ceph/ceph/blob/wip-erasure-coding-doc/src/osd/PGBackend.h

* "Erasure code API design":https://github.com/dachary/ceph/blob/wip-4929/doc/dev/osd_internals/erasure-code.rst#erasure-code-library-abstract-api complete

h3. Detailed Description

Design Doc: https://github.com/ceph/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst

Currently wip PGBackend interface: https://github.com/ceph/ceph/blob/wip-erasure-coding-doc/src/osd/PGBackend.h

Developer notes : https://github.com/dachary/ceph/blob/wip-4929/doc/dev/osd_internals/erasure-code.rst

Erasure coding or replication ( pg_pool_t::TYPE_REP ) is a property of a pool and is currently implemented PG.{cc,h} and ReplicatedPG.{cc,h}. The implementation of erasure coding requires a refactoring to allow multiple backends. The first step is to factor out code from ReplicatedPG that is independant of the resilience policy.

* PGLog is mostly done, it includes missing set as well as the logic to merge during recovery. It already is in master but does not yet have a sensible API.

* PGRegistry groups the ObjectContext, SnapSetContext and Watchers registry. The API is mostly good and the implementation is being cleaned up. The erasure code backend won't use the SnapSetContext because it is not supported. PG knows nothing about this registry. Once the #5510 "pull request":https://github.com/ceph/ceph/pull/414 is merged, it will be ready to be moved to a PGBackend base class.

Other parts of the code need to be reworked so that ReplicatedPG only contains the part specific to replication. Some code needs to be moved to or from ReplicatedPG and PG. If moving the code is not enough, it will be refactored to isolate the parts that belong to ReplicatedPG only. The "design document":https://github.com/ceph/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst contains an inventory of what needs to be abstracted to PGBackend and the associated rationale.

Once the ReplicatedPG implementation for a given concept ( backfill, recovery, scrub, peering, read, write ) is reasonably free of code that is common to both erasure coding and replication, the PG implementation will be severed from the ReplicatedPG sub class and changed to use a PGBackend data member and will not be aware of the resilience policy.

The erasure code plugin library can be implemented with the following API and the jerasure library:

* erasure_coding_t "*":https://github.com/dachary/ceph/blob/wip-4929/doc/dev/osd_internals/erasure-code.rst#id1 create_erasure_code_context(g_conf)

return an object configured to encode and decode according to a given algorithm and a given set of parameters as specified in g_conf. Parameters must be prefixed with erasure-code to avoid name collisions

<pre>ceph osd pool set-erasure-code <pool> m 10 ceph osd pool set-erasure-code <pool> k 3 ceph osd pool set-erasure-code <pool> algorithm Reed-Solomon</pre> 

The following are methods of erasure_coding_t.

* set<int> minimum_to_decode(const set<int> &want_to_read, const set<int> &available_chunks);

returns the smallest subset of available_chunks that needs to be retrieved in order to successfully decode want_to_read chunks.

* set<int> minimum_to_decode_with_cost(const set<int> &want_to_read, const map<int, int> &available)

returns the minimum cost set required to read the specified chunks given a mapping of available chunks to costs. The costs might allow to consider the difference between reading local chunks vs remote chunks.

* map<int, buffer> encode(const set<int> &want_to_encode, const buffer &in)

encode the content of in and return a map associating the chunk number with its encoded content. The map only contains the chunks contained in the want_to_encode set. For instance, in the simplest case M=2,K=1 for a buffer containing AB, calling

<pre>encode([1,2,3], 'AB') => { 1 => 'A', 2 => 'B', 3 => 'Z' }</pre>

If only the parity chunk is of interest, calling

<pre>encode([3], 'AB') => { 3 => 'Z' }</pre>

* map<int, buffer> decode(const set<int> &want_to_read, const map<int, buffer> &chunks)

decode chunks to read the content of the want_to_read chunks and return a map associating the chunk number with its decoded content. For instance, in the simplest case M=2,K=1 for an encoded payload of data A and B with parity Z, calling

<pre>decode([1,2], { 1 => 'A', 2 => 'B', 3 => 'Z' }) => { 1 => 'A', 2 => 'B' }</pre>

If however, the chunk B is to be read but is missing it will be:

<pre>decode([2], { 1 => 'A', 3 => 'Z' }) => { 2 => 'B' }</pre>

h3. Work items

h3. Coding tasks

The following list of tasks is either an issue item in the "Ceph tracker":http://tracker.ceph.com/ or a a link to the "erasure code design document":https://github.com/ceph/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst in which links to the tracker can be found for individual tasks. All tasks can be displayed from the "Erasure encoded placement group":http://tracker.ceph.com/issues/4929 feature request.

# Common PG components refactoring:

## "Factor out PG logs":http://tracker.ceph.com/issues/5487 (difficulty: medium)

## "Factor out ObjectContext SnapSetContext":http://tracker.ceph.com/issues/5487 (difficulty: medium)

# "Factor out object writing/replication logic":http://tracker.ceph.com/issues/5433

## "Peering and PG logs":https://github.com/dachary/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst#peering-and-pg-logs (difficulty: hard)

## "Distinguished acting set positions":https://github.com/dachary/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst#distinguished-acting-set-positions (difficulty: hard)

## "Scrub":https://github.com/dachary/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst#scrub (difficulty: hard)

## "Recovery":https://github.com/dachary/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst#recovery (difficulty: hard)

## "Backfill":https://github.com/dachary/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst#backfill (difficulty: hard)

# "Plugable erasure coding library":http://tracker.ceph.com/issues/5877

## "plugin mechanism and abstract API":http://tracker.ceph.com/issues/5878 (difficulty: easy)

## "jerasure plugin":http://tracker.ceph.com/issues/5879 (difficulty: easy)

## "erasure coding library plugin API documentation, including a simple example":http://tracker.ceph.com/issues/5880 (difficulty: easy)

# Write integration tests https://github.com/ceph/ceph-qa-suite

h3. Build / release tasks

# Add a wip-erasure-code branch to http://github.com/ceph/ceph/

# Schedule the branch to be run by teuthology http://ceph.com/gitbuilder.cgi

# Watch the tests results on a daily basis and fix the problems

h3. Documentation tasks

# "Erasure code internal documentation":https://github.com/dachary/ceph/blob/wip-4929/doc/dev/osd_internals/erasure-code.rst

# "erasure code design document":https://github.com/ceph/ceph/blob/wip-erasure-coding-doc/doc/dev/osd_internals/erasure_coding.rst

# "erasure coding library plugin API documentation, including a simple example":http://tracker.ceph.com/issues/5880