Skip to main content

Erasure Coding

Erasure Coding (EC) is the redundancy format in which a chunk is stored as data parts and parity parts instead of whole copies.

What it is​

Under EC, MooseFS divides a chunk into a fixed number of data parts and computes parity parts from them. Each part is stored on a Chunkserver of its own. Two parts of one chunk on one server is a condition that MooseFS repairs. When a part is lost, no data is lost as long as enough of the other parts remain. The chunk stays in EC. The missing part is computed back from the remaining parts. A missing parity part does not affect reads. The Redundancy Level that the class requires is the number of parts that may be lost at once.

EC is the alternative to copies. The format that a chunk uses is not a property of the chunk itself. The format is a property of the definition that the chunk's Storage Class gives to the storage state that the chunk is in. MooseFS accepts an EC expression only in the ARCHIVE and TRASH definitions of a class. A class that requires EC in CREATE or KEEP is rejected.

A format pairs a number of data parts with a number of parity parts, written @4+n and @8+n. MooseFS offers two widths of data parts, four and eight, and n parity parts on top. Both editions store data in EC. n runs from one to nine PRO (PRO Edition only) in PRO. The Community Edition takes a single parity part.

Why it matters​

Parity costs a fraction of a chunk, not a multiple of it. Reaching a given Redundancy Level with copies means storing the whole chunk that many times over. Reaching the same level with EC means adding one part per tolerated failure. Over an archive of any size, that difference in raw space is the reason to use EC at all.

EC is not free. Writing a chunk in EC costs more I/O than writing a copy, because the parts are computed first and then distributed. A read that finds a missing data part waits while that part is rebuilt. EC suits data that is written once and then read or left alone. For this reason, the format is tied to the archive states.

EC also raises the number of Chunkservers that you need. Every part takes a server of its own. MooseFS keeps a chunk in EC only as long as there are enough servers to hold all of its parts. Below that number, MooseFS converts the chunk back to copies on its own.

How MooseFS implements it​

Conversion to EC is a split. The Master Server picks one Chunkserver that already holds a copy of the chunk. When that Chunkserver is able to split a chunk itself, the Chunkserver computes the parts from its own copy. Otherwise, the missing parts are built on other Chunkservers. Each of those Chunkservers reads the copy over the network. The whole copies are deleted only once the full set of parts exists. Between the split and the spreading of the parts, several parts are stored on one server.

A part that goes missing is rebuilt from the surviving parts by a recover. The reverse of the split is a join. A join reads the parts back and writes out a whole chunk again. A join runs whenever a chunk has to leave EC: the definition of the chunk's current state no longer requires EC, a client writes to the chunk, or too few Chunkservers are left to hold its parts. Erasure Coding: part layout covers what the split and the join each cost, and what waits for what.

  • Copy: the other redundancy format, and the format a chunk returns to.
  • Redundancy Level: how many parts a chunk can lose and still be served.
  • Storage Class: the policy that requires EC.
  • Storage states: the two states in which EC is allowed.
  • Chunkserver: the component holding one part of a chunk.