Erasure Coding: part layout
A chunk is stored as data parts and parity parts instead of whole copies when its Storage Class definition for the current storage state requires Erasure Coding (EC). This page describes the mechanism. The page covers what a part is to the placement machinery, when the cluster converts a chunk between copies and parts, and what reads and writes cost while the chunk is stored in parts.
The part, not the chunk, is placed
An EC expression @N+X names N data parts (four or eight) and X parity parts. To the Master Server, each part is a separate object on a separate Chunkserver. The Master Server's record of the chunk is a list of server and part pairs. Every replication, recovery, and deletion order names one part and one destination. An order that copies a part that still exists therefore moves one part's worth of data, not the chunk. An order that rebuilds a lost part writes one part as well, but reads a full set of parts to compute the missing part. The class's label expression decides which Chunkservers may hold a part. An EC expression may give separate expressions to the data parts and to the parity parts. The page on label expressions and matching covers how expressions are matched to servers.
Parts take no writes. A client that writes to an EC chunk is answered with a busy status while the chunk is joined back into copies. The first write into a chunk stored in parts costs that reassembly.
A read never forces a join. A missing data part is rebuilt from the surviving parts, parity included. The chunk stays in EC.
N+2X and N+X are thresholds, not formats
A class specifies one format, @N+X. Whether the format is applied depends on the cluster. The Master Server makes that decision from two Chunkserver counts:
- With N+2X or more Chunkservers to count on, chunks are converted from copies to EC.
- With N+X or more, chunks already in EC stay in EC, but no new ones are converted.
- Below N+X, chunks in EC are converted back to whole copies under the class's
KEEPdefinition.
The gap between the thresholds is the format's own redundancy. A cluster of N+2X servers can lose X of them and still offer the N+X distinct servers that a full set of parts needs. The class's labels mode decides which servers count toward the thresholds: all of them, or only those that match the class's labels. The page on label expressions and matching covers that mode.
The thresholds decide the format, never the availability of data. A chunk on the wrong side of a threshold is not refused anything. The chunk is held as copies under the class's KEEP definition until the count recovers. The chunk is then converted, not lost. The EC definition itself is read as a copy definition only when no server matches the KEEP definition. That copy definition has one copy more than the parity count.
Conversion is a split, local where possible
The chunk loop moves a chunk between the two formats once the chunk's state and the class's definitions require the change. To convert a chunk to EC, the Master Server picks one Chunkserver that already holds a copy. When that Chunkserver can split a chunk itself, the order is a local split. The Chunkserver computes the parts from its own copy and registers all of them on itself. No data crosses the network. When the Chunkserver cannot split the chunk itself, the Master Server orders other Chunkservers to build the missing parts instead. Each of those Chunkservers reads the copy over the network. Either way, the order lists the parts that the chunk is missing, so parts that already exist elsewhere are not created again. The source copy is kept. Whole copies are deleted only after the full set of parts exists.
After a local split, the parts spread through the ordinary replication that replication priorities describes. Parts of one chunk that share a Chunkserver are one of the conditions that the repair queues drain. Until the queues have drained that condition, several parts are stored on one server. The placement that a STRICT class requires is therefore briefly not satisfied. That brief mismatch is part of the split, not a fault.
Conversion into EC is the slower direction, for a reason other than the pace of the chunk loop. Erasure Coding is required only by an ARCHIVE or a TRASH definition. A chunk of a live file therefore first waits for the file loop to set the chunk's archive flag. That pass is the longest wait in the sequence. Assigning a class with an EC definition therefore says nothing about when the chunk changes format.
A join rebuilds a whole copy, never locally
A chunk leaves EC through a join. A join is the opposite of the split in every respect. One Chunkserver is ordered to build a whole copy. The order to that Chunkserver is a list of part locations. The Chunkserver reads the full set of data parts over the network from the servers that hold them, and writes out the copy. The Master Server orders one join for each copy that the class requires. Each join goes to a different Chunkserver. The parts are deleted only after the copies exist.
A join runs whenever the chunk has to leave EC. The chunk has to leave EC when the definition of its current state no longer requires the format, when the Chunkserver count fell below N+X, or when a client is waiting to write. A join needs every data part. When a data part is missing, a recover runs first. In a recover, one Chunkserver rebuilds the missing data part from the surviving parts, parity included. The joins proceed only after that. Of the three conditions, only a redefinition of the class itself waits for the chunk loop. Changing a definition changes no chunk, so the loop queues the affected chunks when the loop reaches them. Every other condition adds the chunk to a repair queue at once. A chunk that a client is waiting for goes to the first queue of all. The Master Server drains those queues many times a second.
A write waits for the join
Parts take no writes. A client that asks to write to a chunk stored in EC is not refused. The client is stalled while the chunk leaves the format. The Master Server clears both of the chunk's flags. Clearing the flags returns the chunk to the KEEP state. The Master Server then orders the joins at once, without waiting for the chunk loop. The Master Server answers the request with a busy status. The client repeats the request. Every repeat is answered the same way until a whole copy exists. Then the write proceeds on the copies, the same way as on any other chunk. The write raises the chunk's version, so any parts that remain have the old version and are discarded.
The first write into a chunk archived into EC therefore costs a full reassembly across the network before the first byte is written. The class, not the write, decides whether the chunk later returns to EC. The chunk is back in KEEP and is converted again when the archive condition holds again.
A read is served from the data parts
Reading converts nothing. The Master Server answers a read request with the locations of the data parts. The client reads from those Chunkservers directly. Parity parts receive no read traffic. The data parts hold the chunk in turn, 256 KiB at a time. A read therefore takes data from as many data parts as its range spans, and from no more than N. A read shorter than 256 KiB that stays within one stretch takes data from one Chunkserver, the same as a read from a whole copy. A short read that crosses a boundary takes data from two. A read long enough to cross the whole rotation takes data from all N. Before any data is read, however, the client opens or reuses a connection to the Chunkserver of every data part. A read therefore needs all N of those servers to be reachable from the client. A server that the client cannot reach stops even a read that takes no data from that server.
When a data part is missing, the read waits the way a write does. The Master Server orders a recover at once and answers with a busy status until the part is available again. The client retries. A read never forces a join. Instead, the missing part is rebuilt. The chunk stays in EC.
Small files cost more in EC than copies
EC saves space on large files and costs space on small ones. Below a size that depends on N and X, a file stored as parts uses more space than the same file stored as whole copies. For this reason, a class can be set to keep files under a given size out of the ARCHIVE state altogether. The Master Server's accounting also treats every file as large. The accounting scales a file's size by the redundancy of its format, as if a part took no space beyond its share of the data. realsize is an estimate rather than a measurement. Under EC, the estimate is least accurate for exactly those small files. The page on quota covers what the figure measures, and the quota limits and the free space reports that use it.