Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Placement, rebuild time and erasure coding

Where should the copies live, how fast must they rebuild, and when does erasure coding beat replication?

Placement across failure domains

Spreading the copies across is the cheap gain, and it has a price of its own. Rack awareness is usually explained as one idea. It is two, and they conflict.

  1. Failure-domain separation pushes replicas apart. Replicas in one rack share a switch, a power feed and a maintenance window. Replicas in one AZ share a building. Sharing fate makes R a lie: the availability arithmetic assumed independence, and the physical layout supplied correlation.
  2. Bandwidth locality pulls replicas together. Cross-rack bandwidth is oversubscribed relative to intra-rack bandwidth: historically 3:1 to 10:1, better in modern leaf-spine networks but never free. In the cloud, cross-AZ transfer is billed per GB, so every replica across a zone boundary adds a metered term to every write.

HDFS's default is the compromise you would derive from these two: one replica on the local node, the other two on a single different rack. Losing any one rack loses at most two of three, so durability survives. A write crosses the rack boundary exactly once and is then pipelined (passed on from node to node) within the far rack. It is not a heuristic. It is the minimum cross-domain transfer that still satisfies the separation constraint. The same derivation in cloud units gives a different answer: two replicas in one AZ plus a witness elsewhere. The bandwidth term acquired a price in dollars, and the separation term only needs a vote, not a copy.

Copysets: the frequency-versus-blast-radius dial

A counterintuitive result: spreading replicas randomly over many nodes maximises the probability that a correlated multi-node failure loses something. With thousands of partitions on N nodes at R = 3, the set of distinct node-triples actually used approaches the full C(N,3) (the number of ways to choose 3 nodes from N). So almost any simultaneous loss of three nodes lands on some triple that holds a complete replica set.

RelationshipCopysets: frequency against blast radius →
nodes
Principle: Independence is assumed →

Constraining placement to a small number of fixed copysets (fixed groups of nodes that hold replicas together) cuts the probability of any loss by orders of magnitude, while increasing how much you lose when it happens. Neither setting is correct. It is a dial between frequent small losses and rare large ones. The right position depends on whether your cost is per event or per byte. Correlation is pessimistic about frequency and optimistic about (the amount lost per event); here it is a deliberate design parameter rather than an accident.

Rebuild time is the real durability variable

Loss requires f+1 failures within the rebuild window. A second failure only matters if it happens before the first lost copy has been rebuilt. So durability scales with data volume ÷ rebuild bandwidth. This is the most underrated number in the field.

This is also the hidden cost of below: its makes every rebuild slower, so it widens the very window that durability depends on.

What a durability figure promises

Cloud object stores state their durability in nines. Amazon S3, for example, is designed for 99.999999999% ("eleven nines") durability of objects over a year. Read it with the arithmetic above: an expected loss of 10⁻¹¹ of your objects per year.

Three things the figure is not:

  • Not a measurement. It is a design target computed from a failure model like the one in this article, so it inherits that model's assumptions about independence and repair time. (No observation could check it: zero losses only bound the rate, and what can be measured are the inputs.)
  • Not a contract. Service agreements for object stores pay credits for availability (monthly uptime), not for lost objects.
  • Not about you. It covers the provider losing bytes it acknowledged. A delete, an overwrite, a job that writes wrong data, a stolen credential or a lifecycle rule that expires the only copy are carried out with the same eleven nines of fidelity. Those are rung 6 problems (Surviving your own mistakes).

Erasure coding versus replication

Replication keeps full copies: 3 copies = 3× storage, and tolerates 2 lost copies.

Erasure coding (EC) splits an object into k data chunks and computes m extra parity chunks, so that any k of the n = k + m chunks can rebuild the object. Storage overhead is .

The price is repair amplification. To rebuild one lost chunk you must read k chunks from other machines. In the 10+4 code, losing one chunk of 1 GB means reading 10 GB over the network to rebuild 1 GB: repair traffic is 10× the lost data. With replication, rebuilding 1 GB means copying 1 GB. So:

  • EC is unattractive for hot or small objects. Small objects waste space in chunks and every read or repair touches many machines.
  • EC is nearly required for cold, large objects, where the 2× saving is large and access is rare.
  • Local reconstruction codes (LRC) exist to reduce the repair cost: they add a few local parity chunks over small groups, so that one lost chunk can be rebuilt from a small group (for example, 5 chunks) instead of all k.

Notice how the same two themes return: (the chain-length trade again), and the failure-domain assumption sits under every number.