Erasure Coding for Storage Efficiency

13-1 Before you start#

13-1-1 What questions does this chapter answer?#

Three-way replication is simple and fast, but it consumes three terabytes of disk for every terabyte of user data. Erasure coding (EC) brings the overhead down to about 1.5 times or less, with the same or even a higher level of fault tolerance. The price is more complexity, CPU usage and higher latency for small writes. From 2019 to today, EC in Ceph has gone through two major changes: ISA-L became the default instead of Jerasure, and FastEC arrived in Tentacle.

• What is EC, and what do the parameters k and m mean?
• How is EC implemented inside Ceph: stripe, shard and chunk?
• How do the plugins (ISA, Jerasure, LRC, SHEC, CLAY) differ?
• Where should we use EC, and where not?
• How do we create an EC pool and enable overwrites and FastEC?
• Where does the famous "2147483647" error come from?

13-2 What is EC?#

13-2-1 k+m#

In EC, data is split into k data chunks, and m parity chunks are computed from them. Any k of the k+m chunks are enough to rebuild the data completely; so up to m simultaneous failures can be tolerated.

ceph osd erasure-code-profile set prof-4-2 plugin=isa k=4 m=2 crush-failure-domain=host
ceph osd pool create ecpool erasure prof-4-2
ceph osd pool set ecpool allow_ec_overwrites true   # RBD, CephFS

13-2-2 The mathematics in plain terms#

Reed-Solomon codes (which ISA-L and Jerasure implement) work over a Galois field (usually $\mathrm{GF}(2^8)$): each byte is a field element, and addition is XOR. Treat k data bytes as a vector d; the shards are the product of a (k+m)×k generator matrix G and d. The first k rows of G are the identity matrix (so the data shards are the data itself), and the next m rows are the parity coefficients. To rebuild, we take the k×k submatrix that corresponds to any k available shards and invert it. The condition for this to work is that every k×k submatrix is invertible; Vandermonde (reed_sol_van) and Cauchy (cauchy) matrices have this property.

shard_i = Σ_j  G[i][j] ⊗ d_j      (⊗ multiplication in GF(2^8), Σ is XOR)
for i < k:  G[i] = e_i  →  shard_i = d_i
decode:  d = (G_S)^-1 · shards_S     (S: any k available indices)

13-3 EC inside Ceph#

13-3-1 Stripe, shard and chunk#

In an EC pool, each PG has shards instead of "replicas": OSD number i in the acting set is shard i and keeps only its own chunk. The object is split into stripes of size k × stripe_unit (stripe_unit defaults to four kilobytes). For each stripe, k data chunks and m parity chunks are built, and chunk i is stored on shard i. So on each OSD the object appears as a "shard object" that contains all the i-th chunks of that object.

13-3-2 The primary in EC#

In an EC pool the primary is responsible for encoding and decoding: the client talks only to the primary, and the primary encodes the data and sends the chunks to the shards. On reads, the primary gathers the needed chunks from the shards and decodes if necessary. This means EC's CPU and network load is concentrated on the primaries.

13-3-3 Partial writes and overwrites#

EC originally (before Luminous) supported only appends and could not be used for RBD and CephFS. The allow_ec_overwrites flag (from Luminous; the old outline tied it to Kraken) made overwrites possible. But in the old implementation, overwriting 4 kilobytes in the middle of a stripe meant a full read-modify-write: reading the rest of the stripe, encoding again and writing all the shards.

13-4 Plugins and profiles#

13-4-1 Creating a profile and a pool#

ceph osd erasure-code-profile ls
ceph osd erasure-code-profile get default
ceph osd erasure-code-profile set ec42 plugin=isa technique=reed_sol_van k=4 m=2 \
     crush-failure-domain=host crush-device-class=hdd
ceph osd pool create ecpool erasure ec42
ceph osd pool set ecpool allow_ec_overwrites true     # for RBD and CephFS
ceph osd pool application enable ecpool rgw

13-4-2 LRC and CLAY#

# LRC: k=4 data, m=2 global parity, l=3 → one local parity for every 3 chunks
ceph osd erasure-code-profile set lrc42 plugin=lrc k=4 m=2 l=3 crush-failure-domain=host
# CLAY: d is the number of shards that take part in recovering one shard
ceph osd erasure-code-profile set clay42 plugin=clay k=4 m=2 d=5 crush-failure-domain=host

13-5 Where EC and where replication?#

rbd create rbd/vm01 --size 200G --data-pool ecpool
rbd info rbd/vm01 | grep data_pool

13-6 FastEC in Tentacle#

13-6-1 What changed?#

Tentacle added a new implementation of the EC I/O path, collectively called FastEC: partial reads (only the needed shards), partial writes, parity delta writes, removal of zero padding and space savings for small objects. It is enabled with a per-pool flag:

ceph osd pool set ecpool allow_ec_optimizations true
ceph osd pool get ecpool allow_ec_optimizations
# the default for new pools
ceph config set global osd_pool_default_flag_ec_optimizations true

The limitations, according to the documentation:

• All MONs and OSDs must be Tentacle or newer; clients do not need upgrading.
• Once enabled, the flag cannot be turned off, because it changes how data is stored.
• It works only with ISA-L, or Jerasure with reed_sol_van; CLAY, LRC and SHEC are rejected.
• stripe_unit must be a multiple of 4 kilobytes; the documentation recommends 16 kilobytes for most workloads and up to 256 kilobytes for mostly-read workloads.

ceph osd erasure-code-profile set ec42fast plugin=isa technique=reed_sol_van k=4 m=2 \
     stripe_unit=16K crush-failure-domain=host
ceph osd pool create rbd-ec erasure ec42fast
ceph osd pool set rbd-ec allow_ec_overwrites true
ceph osd pool set rbd-ec allow_ec_optimizations true

13-7 Troubleshooting: the 2147483647 error#

In the output of ceph pg dump or ceph pg map for an EC pool you sometimes see the number 2147483647 instead of an OSD number. This number is the constant CRUSH_ITEM_NONE:

/* from ceph/ceph, LGPL — src/crush/crush.h */
#define CRUSH_ITEM_NONE   0x7fffffff

It means CRUSH could not find an OSD for that shard position. In a replicated pool an empty position is simply dropped; but in EC each shard's position has meaning (shard 3 must stay shard 3), so instead of being dropped it is filled with NONE. Common causes:

• Fewer failure domains than k+m (for example 4+2 with five hosts).
• OSDs that are out or down and have emptied a domain.
• A CRUSH rule with the wrong device class or root.
• Too few CRUSH tries, which give no result in an unbalanced hierarchy (set_choose_tries).

ceph pg ls-by-pool ecpool | grep -c 2147483647
ceph osd crush rule dump ecpool
ceph osd getcrushmap -o cm && crushtool -i cm --test --rule <id> --num-rep 6 --show-bad-mappings

13-8 Inside the EC backend: writes, rollback and recovery#

This section is a bridge to chapter 27 ("The mathematics of erasure coding"). Here, instead of the mathematics, we examine the OSD mechanics: how an EC write is coordinated between shards, what happens if a failure occurs halfway, and exactly what recovery reads and writes. The related classes in src/osd/ on the main branch are ECBackend, ECCommon, ECTransaction, ECUtil and their "L" (legacy) versions, between which ECSwitch chooses based on a pool flag.

13-8-1 Why does EC need rollback?#

In replication, each replica is a full copy. If a write commits on only some replicas, recovery can copy the new version from one replica to the others. In EC, no shard has all the data. If a write has committed on 3 of 6 shards and then the primary dies, neither the old nor the new version can be rebuilt from any consistent set of k shards. Ceph's solution is to make changes "reversible": each EC pg log entry has an ObjectModDesc, and after peering, shards that are ahead of the agreed point roll back their changes.

pg_log_t has two boundaries: can_rollback_to (entries newer than it can be rolled back) and rollback_info_trimmed_to (stash information has been deleted up to there). When the primary is sure an entry has committed on all shards, can_rollback_to moves forward, and the stashed data (for example the old ROLLBACK_EXTENTS extents) can be deleted. This is why overwrites in old EC need temporary space and extra writes compared with replication.

13-8-2 The default min_size and the reason for it#

In OSDMonitor::prepare_pool_size, the default for EC pools is min_size = k + min(1, m − 1) (and size = num_zones × (k + m)). So for k=4, m=2, min_size is 5: the pool accepts writes as long as at least 5 shards are available. Therefore, after one shard is lost, there is still a spare shard to tolerate the next failure. For m=1, min_size = k, and any second failure during recovery means data loss. That is why m=1 is not recommended for important data.

ceph osd pool set ecpool fast_read 1
ceph pg 5.1as2 query | jq '.info | {last_update, last_complete, log_tail}'   # shard 2 of PG 5.1a
ceph pg 5.1a list_unfound
ceph daemon osd.4 dump_ops_in_flight | jq '.ops[] | select(.description|test("ECSub"))'

13-9 Erasure coding by the numbers: the Reed-Solomon matrix, the MDS limit, parity-delta updates and the cost of rebuilding#

This section runs the mathematics behind the ISA plugin on real bytes. References are to src/erasure-code/isa in main (November 2026) and to the gf_gen_rs_matrix function in the ISA-L library (erasure_code/ec_base.c). $\mathrm{GF}(2^8)$ arithmetic with the polynomial 0x11d was reimplemented in Python and checked against the gff_base table in ISA-L.

13-9-1 Encoding and decoding one byte column#

pseudocode
G[0..k−1] = I_k                        # systematic: the data shards are the data itself
gen = 1
for i in k .. k+m−1: G[i][j] = gen^j ; gen = gen × 2      (in GF(2^8))
parity_i = ⊕_j G[i][j] ⊗ d_j
decoding: choose k healthy rows ← B ; d = B⁻¹ × (healthy shards)

Numerical example (k = 4, m = 2, the bytes "ABCD"). Row P0 is all ones, so P0 = 0x41 ⊕ 0x42 ⊕ 0x43 ⊕ 0x44 = 0x04. Row P1 is 1, 2, 4 and 8: 2 ⊗ 0x42 = 0x84, 4 ⊗ 0x43 = 0x11 and 8 ⊗ 0x44 = 0x1a, so P1 = 0xce. If d1 and d3 are lost, the rows d0, d2, P0 and P1 form a 4×4 matrix whose inverse gives back 0x42 and 0x44. All 15 cases of losing two shards in 4+2 can be decoded.

13-9-2 Why does ISA sometimes fall back to Cauchy?#

pseudocode
for each e from 1 to m, each subset L of e data shards and P of e parity rows:
    rows = (healthy data) ∪ P
    if det = 0 in GF(2^8): pattern L cannot be decoded
the code is MDS if no pattern fails

The result of our full check. For 4+2 and 21+4 there is no failing pattern. For 22+4 there are two patterns, for example losing d0, d10, d21 and P2, which do not give the data back despite m = 4. For 8+5 there are six patterns (for example d0, d2, d5, P1 and P2). For 4+5 no problem was found. So the code's rule, switching to Cauchy for m > 4 or m = 4 with k > 21, is exactly the failure boundary at m = 4 and is conservative for m > 4. Take its warning message when a profile is created ("switching to Cauchy technique") seriously: the pool's real technique differs from what you wrote.

13-9-3 Parity-delta updates#

pseudocode
delta = old_d ⊕ new_d                       # encode_delta
for each parity i: P_i ⊕= G[i][j] ⊗ delta    # apply_delta; for m=1 only XOR
choice in the OSD (ec_pdw_write_mode = 0):
    conv = shards a conventional RMW must read ; pdw = changed shard + the parities
    if |pdw| ≥ k: conventional
    elif pdw needs a rebuild: conventional ; elif only conventional needs a rebuild: pdw
    else: pdw if |pdw| ≤ |conv|  (tie ← pdw)

Numerical example. d2 changes from 0x43 to 0x5a. delta = 0x19, so P0 = 0x04 ⊕ 0x19 = 0x1d and P1 = 0xce ⊕ (4 ⊗ 0x19 = 0x64) = 0xaa, which is the same result as a full re-encode. For overwriting 4K of one shard: in 4+2, a conventional RMW reads the three other data shards, and PDW reads the old d2 and two parities, i.e. 3 against 3. On a tie PDW is chosen. In 8+3 the comparison is 7 against 4, in favour of PDW. In 2+2 the comparison is 1 against 3, and the conventional path wins. This path is active only in a pool with FastEC (allow_ec_optimizations, Tentacle onwards) and a plugin that has the paritydelta flag (ISA and Jerasure).

13-9-4 The cost of rebuilding one shard: RS, LRC and CLAY#

pseudocode
RS:   read = k chunks
LRC:  read = l chunks (local group) ; raw overhead = (k + m + (k+m)/l) / k
CLAY: q = d − k + 1 ; each of the d helpers sends 1/q of a chunk ; read = d / q chunks
      condition: k + 1 ≤ d ≤ k + m − 1 ; sub-chunks = q^t

Numerical example. In 4+2, an RS rebuild reads four chunks. LRC with l = 3 reads three chunks, but its raw overhead is 2.0, not 1.5. CLAY with d = 5 (q = 2, t = 3 and 8 sub-chunks) reads only 2.5 chunks and keeps the 1.5 overhead. In 8+4, the numbers for RS, LRC (l = 4, overhead 1.875) and CLAY (d = 11, q = 4, 64 sub-chunks) are 8, 4 and 2.75 chunks respectively. CLAY's cost is in fragmented reads: each helper sends scattered sub-chunks, so on HDDs the number of seeks goes up.

13-10 Inside the code: EC in the OSD#

13-10-1 File map#

13-10-2 The plugin interface#

Each plugin is a class that implements ErasureCodeInterface. The key functions (signatures abbreviated):

• init(profile, ss): reads the profile parameters and builds the matrix.
• get_chunk_count() and get_data_chunk_count(): k+m and k.
• minimum_to_decode(want_to_read, available, minimum): the smallest set of shards for the requested read.
• encode(want_to_encode, in, encoded) and decode(want_to_read, chunks, decoded).
• get_supported_optimizations(): the flags FastEC bases its decisions on.

// from ceph/ceph, LGPL — src/erasure-code/ErasureCodeInterface.h (excerpt)
FLAG_EC_PLUGIN_PARTIAL_READ_OPTIMIZATION = 1<<0,
FLAG_EC_PLUGIN_PARTIAL_WRITE_OPTIMIZATION = 1<<1,
FLAG_EC_PLUGIN_ZERO_INPUT_ZERO_OUTPUT_OPTIMIZATION = 1<<2,
FLAG_EC_PLUGIN_ZERO_PADDING_OPTIMIZATION = 1<<3,
FLAG_EC_PLUGIN_PARITY_DELTA_OPTIMIZATION = 1<<4,

These flags explain why FastEC works only with some plugins: each optimization needs a particular mathematical property. For example, "zero in, zero out" means that encoding an all-zero block gives all-zero parity (true for linear codes), so writing zero padding can be skipped. Parity delta relies on the code being linear: if the data of shard j changes from d to d', the new parity equals the old parity plus G[i][j]⊗(d ⊕ d').

13-10-3 ECSwitch: a gradual transition#

The comment at the top of ECSwitch.h is explicit: this class is a "temporary switcher" between the legacy and optimized implementations until the new implementation is trusted enough. ECSwitch holds both objects, ECLegacy::ECBackendL legacy and ECBackend optimized, and routes requests to one of them based on the pool flag (allow_ec_optimizations). This is why the flag is irreversible: once data is written in the new format, the old implementation cannot read it.

13-10-4 The RMW or parity-delta decision#

In ECTransaction.cc a plan is built for each write. The selection logic, simplified:

// from ceph/ceph, LGPL — src/osd/ECTransaction.cc (excerpt, simplified indentation)
if (sinfo.supports_parity_delta_writes() && !object_in_cache &&
    orig_size == projected_size && !reads.empty() && !op.truncate) {
  ...
  if (pdw_write_mode != 0) {
    do_parity_delta_write = (pdw_write_mode == 2);
  } else if (pdw_read_shards.size() >= sinfo.get_k()) {
    do_parity_delta_write = false;
  } else if (!shard_id_set::difference(pdw_read_shards, readable_shards).empty()) {
    do_parity_delta_write = false;
  } else if (!shard_id_set::difference(read_shards, readable_shards).empty()) {
    do_parity_delta_write = true;
  } else {
    do_parity_delta_write = pdw_read_shards.size() <= read_shards.size();
  }
}

Reading it: parity delta only makes sense when the object size does not change, there is no truncate and the data is not in the cache. If parity delta needs k reads or more, it has no advantage; if parity delta needs a rebuild, it is set aside; if the conventional RMW needs a rebuild but parity delta does not, parity delta is chosen; otherwise the method with fewer reads wins (preferring parity delta on a tie). The pdw_write_mode variable makes it possible to force one of the two methods for testing.

13-10-5 Why is shard 0 not always the primary?#

In optimized pools, some data shards are not updated on every I/O (a partial write touches only the changed shard and the parities). Such a shard cannot become the primary, because the primary must have the PG's complete log. But the primary selection logic in the OSDMap cannot be changed without upgrading clients. The solution is OSDMap::pgtemp_primaryfirst(): when setting pg_temp, the OSDMonitor reorders it so that the shards allowed to be primary come first.

// from ceph/ceph, LGPL — src/osd/OSDMap.cc (comment excerpt)
 * Example: Optimized EC pool 4+2
 * acting_set = {NONE, 6, 7, 8, 9, 10}
 * non_primary_shards = {1, 2, 3} # data shards other than shard 0
 * pg_temp = {NONE, 9, 10, 6, 7, 8} # non-primary shards at end
 * primary will be OSD 9(1)

13-10-6 Pseudocode of a degraded read#

read(obj, off, len):
  want = shards_covering(off, len)                 # ECUtil: logical range → shard extents
  avail = shards_up_and_not_missing(obj)
  if want ⊆ avail:                                  # partial read (FastEC)
     return gather(want)
  need = ec_impl.minimum_to_decode(want, avail)     # k shards
  chunks = gather(need)
  return ec_impl.decode(want, chunks)[off:len]

13-11 Supplementary and up to date#

• Luminous: allow_ec_overwrites and RBD and CephFS support on EC.
• Tentacle: FastEC with allow_ec_optimizations; ISA-L the default for new clusters; fixes to truncate+write planning.
• Squid: the MSR CRUSH rule type for more flexible EC configurations.
• Current code: osd_pool_default_flag_ec_optimizations=false (FastEC is not turned on automatically for new pools).

13-12 Hands-on exercise#

1. 1. Create 2+1, 4+2 and 8+3 profiles and compare them with ceph osd erasure-code-profile get. Which can run on your cluster?
2. 2. Create a 4+2 pool, write an object and use ceph osd map to see which OSD each shard is on. Stop one OSD and read the object.
3. 3. Use an EC pool as the data-pool of an RBD image, and compare 4-kilobyte random writes with fio against a replicated pool.
4. 4. On a test Tentacle cluster, repeat the same test with allow_ec_optimizations and stripe_unit=16K.
5. 5. Create a 4+2 pool on a cluster with five hosts and observe 2147483647 in ceph pg dump; then confirm with crushtool --test.
6. 6. In the code, read the pgtemp_primaryfirst function and predict its output with your own example (8+3).

13-13 Review questions#

1. 1. What are the overhead and fault tolerance of EC 8+3 compared with three-way replication?
2. 2. Why must every k×k submatrix of the generator matrix be invertible?
3. 3. What is the difference between a shard in EC and a replica in replication?
4. 4. Why were small writes expensive in old EC?
5. 5. What mathematical property does parity delta rely on?
6. 6. What are the limitations on enabling FastEC?
7. 7. Why is the allow_ec_optimizations flag irreversible?
8. 8. How do CLAY and LRC reduce recovery traffic?
9. 9. What does the number 2147483647 in a PG mapping mean, and what are its common causes?
10. 10. Why is the primary not always shard 0 in an optimized pool?

Answers to these questions are in Appendix E: Answers to Review Questions. Answers to this chapter's questions →

13-14 Sources for this chapter#

• Erasure code
  https://docs.ceph.com/en/latest/rados/operations/erasure-code/
• Erasure code profiles
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-profile/
• ISA plugin
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-isa/
• LRC plugin
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-lrc/
• CLAY plugin
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-clay/
• SHEC plugin
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-shec/
• Tentacle release notes
  https://docs.ceph.com/en/latest/releases/tentacle/
• Source: src/erasure-code
  https://github.com/ceph/ceph/tree/main/src/erasure-code
• Source: src/osd/ECTransaction.cc, ECSwitch.h, OSDMap.cc
  https://github.com/ceph/ceph/tree/main/src/osd
• Intel ISA-L
  https://github.com/intel/isa-l
• Plank, "A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems"
  https://web.eecs.utk.edu/~jplank/plank/papers/CS-96-332.pdf