Skip to content

Erasure coding and replication

Replication keeps whole copies of each object; erasure coding splits it into k data chunks plus m parity chunks, and with Reed-Solomon any k chunks rebuild it. The choice trades storage cost against read, write and repair cost.

On this page

What it is

Both are ways to keep data readable when disks and hosts fail. Replication stores each block as several complete copies on different machines. HDFS 3.3.5 replicates three times by default, a 200% overhead in disk space and in network bandwidth as well. For warm and cold data the extra copies are seldom read during normal operation, yet each costs as much as the first.

Erasure coding splits an object into K data chunks of equal size and computes M coding (parity) chunks from them. Concatenating the data chunks gives the original object back; a coding chunk is used to rebuild a lost chunk. The recovery rule is simple: in Ceph Reef (since the Octopus release) a pool can recover as long as at least K of its K+M chunks remain, and with fewer than K the data is gone. Raw space per unit of user data is (K+M)/K, so a 4+2 profile uses 1.5 GiB for 1 GiB, against 3.0 for three-way replication. The default profile there, k=2 m=2, survives two overlapping OSD losses, the same as three replicas, while using 2 TB rather than 3 TB to hold 1 TB.

The usual code is Reed-Solomon, which Wikipedia lists as the most common erasure code in storage systems, with implementations in the Linux RAID-6 driver, Microsoft Azure, Facebook's cold storage and Backblaze Vaults, among others. In HDFS 3.3.5 a policy is named by codec, data blocks, parity blocks and cell size, for example RS-6-3-1024k; RS(6,3) is the one enabled out of the box, and XOR-2-1-1024k is a built-in alternative. Data is striped: consecutive cells of a file go to different data nodes within a block group, so a client reads from several nodes in parallel.

Repair is where the two differ most. When a striped block is lost, the name node hands a reconstruction task to a data node, which reads the minimum number of input blocks it needs in parallel, decodes all the missing data and parity blocks together, then ships the results to target nodes; encoding and decoding take extra CPU on clients and data nodes, and extra network. Recovery in a coded pool works the same way, reading from the remaining shards, reconstructing and writing new ones, and the performance cost is significant on HDDs and during recovery or backfill.

When to use it

Erasure-code large, cold, write-once data. That is the case the feature was built for in big-data file systems: warm and cold datasets with little I/O, where replicas sit idle but still cost disk. Ceph sketches the same split for an object store, with the index and default bucket pools replicated on fast SSDs and larger, colder objects directed to erasure-coded pools on QLC SSDs or HDDs; if you need a starting profile, it suggests k=4 m=2, which doubles usable space compared with three replicas at a write and recovery cost it calls tolerable.

Check the cluster is wide enough. A striped RS(6,3) file needs at least nine data nodes, one per chunk, and its chunks are spread across racks, which makes most reads and writes cross-rack and puts weight on bisection bandwidth. A coded pool needs at least k+m failure domains (hosts or racks), ideally k+m+1; k above 8 is discouraged, and so are k above 4 or m above 2 without a clear reason, because the space gain flattens while the performance cost keeps growing.

When not to

Replicate data that is rewritten in place or read with tight latency. Ceph erasure-coded pools by default accept full-object writes and appends; partial overwrites need a per-pool setting and BlueStore OSDs, and the pools have no omap, so block devices and file systems built on them keep metadata in a replicated pool and put bodies in the coded one. In HDFS 3.3.5, hflush, hsync, append, truncate, concat and setReplication are unsupported on erasure-coded files. Neither system presents erasure coding as a free lunch: the sharpest cost falls on HDDs and during recovery.

Replicate small objects. Deployments with many very small files can see considerable extra space amplification in a coded pool, so the real saving is smaller than the (k+m)/k figure suggests. Small files can take over three quarters of storage in typical clusters, which is why some systems stripe the cells of a file across nodes rather than waiting for a file to fill a whole block group.

Replicate when the cluster is too small for the profile. With fewer failure domains than k+m, two chunks of one group share a domain, so a single failure costs two chunks at once. And skip m=1: it is strongly discouraged for production, with unavailability expected during maintenance and data loss when failures overlap. A min_size of K+1 or more is also recommended, so that writes are not accepted with no margin left.

Compared

QuestionThree replicasErasure coding, k data + m parityWhen replication is the right call

Raw disk per 1 GiB

3 GiB

(k+m)/k: 1.5 GiB for 4+2

The data set is small enough that disk is not the bill

Losses survived

2

m (2 for 4+2, 3 for 6+3)

Two is enough and the cluster is small

A read

One host holds the whole object

k hosts, mostly off-rack

Hot, latency-sensitive reads

A write or update

Copy to three hosts; append and overwrite supported

Encode first; appends and partial overwrites restricted or unsupported

Data rewritten in place

Repair after one loss

Copy one block from a surviving replica

Read k chunks, decode, write the missing ones

Many disks fail per day or the links are slow

Small objects

Three copies, as for any object

Extra space amplification

Millions of tiny files

Hosts needed

3

Usually at least k+m failure domains (hosts or racks), better k+m+1

A rack or a handful of hosts

In a picture

1 GiB objectCut into 4 datachunksCompute 2 paritychunks6 chunks on 6hosts, 1.5 GiBTwo hosts failRead the 4remaining chunksDecode, write 2new chunks
A 4+2 group survives two lost hosts: the four survivors are enough to decode the object and rewrite the missing chunks elsewhere.

How to say it in an interview

The common mistake

Quiz

A pool uses a 4 data + 2 parity profile. How much raw disk does 1 GiB of user data take?
A 6+3 Reed-Solomon group has lost four of its nine chunks. Can the object be rebuilt?
Which of these belongs on three replicas rather than in an erasure-coded pool?
Why does replacing one failed disk usually cost more network traffic with erasure coding than with replication?

Questions that use this

Related

Sources

  1. Apache Hadoop 3.3.5: HDFS Erasure Coding
  2. Ceph Reef documentation: Erasure code
  3. Wikipedia: Erasure code
Sign in to report a mistake