Failure-Domain Placement: Keeping Replicas Out of the Same Blast Radius

Three replicas protect against one failure only if the failures cannot take two of them at once. A replication factor is a count of copies, not a statement about independence, and the gap between the two is where data loss actually happens. Placement is the mechanism that turns a count into a guarantee, and it is constrained by a topology the storage software usually did not design: racks, power feeds, switches, and the correlation between them.

Independence is a property of the failure, not of the node

Two nodes are independent with respect to a failure mode if that failure cannot affect both. They are independent with respect to a disk failure if they have separate disks. They are not independent with respect to a rack-level power loss, because both draw from the same feed. They are not independent with respect to a switch failure if they hang off the same top-of-rack switch, and they are not independent with respect to an operator error if the same script configures both.

The consequence is that the effective replication factor is mode-specific. Three copies spread across three racks give a factor of three against disk failure and rack power loss, a factor of one against a data-centre-wide event, and whatever the cross-region layout provides against a regional outage. A design that states “replication factor 3” without naming the failure mode has stated nothing measurable.

The standard response is to declare a hierarchy of failure domains and to require that replicas of a given key be spread across distinct domains at some level. HDFS makes the rack the default domain: with a replication factor of three, two replicas go on one rack and the third on another, which trades one unit of rack tolerance for better write throughput, since the second replica can be written locally. That choice is explicit in the architecture and is worth reading as a deliberate weakening: three racks would cost a cross-rack write for every block.

Placing without a coordinator

A central allocator that assigns every key’s replicas has two problems. It is a single point of failure for placement, and it must hold a map of every placement decision, which grows with the dataset and must be updated on every topology change.

CRUSH avoids both by making placement a pure function of the key and the cluster map. The cluster map describes a hierarchy of devices grouped into hosts, hosts into racks, racks into rows, and rows into data centres, with weights and a rule specifying how many replicas to place at which level. Placement hashes the object identifier and the replica number, then walks the hierarchy using a deterministic pseudo-random function, choosing a device at each step and rejecting any that shares a failure domain with an already-selected replica at the required level.

The properties that follow are worth stating precisely:

• Deterministic. Any client holding the cluster map computes the same placement for the same key. No lookup, no coordinator.
• Minimal disruption. When a device is added or removed, the algorithm’s rejection sampling moves only the objects that mapped to the affected device, typically a fraction proportional to the change in weight rather than a rehash of everything.
• Weighted. Devices with more capacity receive proportionally more objects, so heterogeneous hardware is usable without separate pools.

The cost is that the rule is not capacity-optimal in a global sense. It is statistically balanced, and the balance depends on the hash function distributing keys evenly and on the rejection sampling not systematically preferring some branches. A cluster map with a badly skewed weight distribution produces a placement that is deterministic and unbalanced, and rebalancing requires changing the weights or the rule.

The correlated-failure problem that placement cannot fix

Random spread across independent domains does not bound the number of keys that share a replica set. Consider a cluster of many nodes, each key placed on three of them chosen pseudo-randomly. There are on the order of n³ possible replica sets, and each key lands on one of them. If a particular combination of three nodes fails together (a rack, a correlated reboot, a shared power circuit), every key whose set is exactly that triple is lost.

The number of such keys is small in expectation, but the distribution has a tail, and the tail is the data loss. The Copysets work makes this concrete: with purely random placement and a large replication factor, the probability that some failure combination destroys a meaningful fraction of the data is higher than the per-key analysis suggests, because the loss is concentrated in the keys that happen to share the failed set. The proposed fix is to constrain placement to a limited set of predefined copysets rather than all combinations, which reduces the number of distinct failure combinations that can cause loss while keeping the load balanced.

The trade is between spreading and bounding. Spreading across all combinations maximises the diversity of replica sets, which helps against independent failures. Bounding the combinations reduces the chance that a single correlated failure aligns exactly with many keys’ sets. Neither is free: bounding reduces the effective placement freedom and can worsen balance and rebuild traffic.

Capacity, rebuild, and the third constraint

Placement also determines rebuild cost. When a node dies, every key it held must be re-replicated, and the replacement must be chosen so that the new replica does not land in a domain already occupied by the surviving two. If the surviving two are on the same rack, as they are under the HDFS two-plus-one policy, the replacement can only go to a different rack, which concentrates rebuild traffic across the rack boundary.

Rebuild traffic is the constraint that most often forces a placement change. Reconstructing a replica requires reading from the surviving copies and writing the full object, so a single node loss can generate network traffic proportional to the data it held. Spreading replicas widely makes the reads come from many peers, which parallelises the rebuild but also means the rebuild competes with foreground traffic on many links. Keeping replicas close makes the rebuild local and fast but increases the chance that the next failure takes a second copy.

The usual compromise is a hierarchy with at least three levels (host, rack, data centre) and a rule that requires distinct hosts always, distinct racks when the cluster has enough, and distinct data centres only for the subset of data that must survive a regional event. Enforcing a level the topology cannot satisfy produces a placement failure or a silent relaxation, and the relaxation is the dangerous outcome: the system reports success while placing two replicas in the same domain.

Reading the topology rather than assuming it

The failure domains that matter are the ones the infrastructure actually has, and they are frequently not the ones the cluster map declares. Two racks on the same uninterruptible power supply are one domain. Two hosts on the same blade chassis share a chassis-level failure. A container scheduler that spreads pods across nodes but not across availability zones has spread nothing at the zone level.

Declaring the map correctly is therefore a prerequisite for the placement algorithm to mean anything, and it is the part that requires knowledge from outside the storage system. The practical discipline is to enumerate the failure modes that have actually occurred in the environment (power, switch, cooling, operator error, network policy change) and to check that the placement rule separates replicas for each. A rule that separates racks but not power feeds is a rule that protects against the failures the operators thought of and not the ones that happen.

The same reasoning applies to the quorum arithmetic. A quorum of two out of three tolerates one failure, and if the three replicas are in two racks, a rack failure can take two of them and stop writes. The topology must be chosen so that the majority survives the failure modes the system claims to tolerate, which is a joint constraint on N, W, and the domain layout. The counting is in quorum intersection and stale reads.

Placement as a schedule, not a setting

Because the map changes as nodes are added, racks re-cabled, and data centres commissioned, placement is a continuing process rather than a one-time assignment. Three operations recur: initial placement, rebalancing after a weight change, and repair after a loss.

Initial placement is cheap because it is a function evaluation. Rebalancing is expensive because it moves data, and the amount moved must be bounded or the rebalance saturates the cluster. Repair is the most urgent and the most disruptive, because it must complete before the next failure, and its priority competes with the foreground workload.

The scheduling decision that matters is the order in which repair runs relative to rebalance. Repairing a lost replica restores the redundancy the cluster claims; rebalancing improves distribution but does not change the failure tolerance of any individual key. A cluster that rebalances before repairing is spending its bandwidth on balance while running at reduced redundancy, which is the state in which the next failure is most damaging. Repair first, then rebalance, is the ordering that keeps the stated replication factor true.

What placement cannot do is compensate for a replication factor that is too low for the failure rate. Three copies tolerate one simultaneous failure per key set; if the environment produces correlated failures that take two, the answer is more copies, more domains, or a different durability mechanism such as erasure coding, whose trade-offs are a separate design problem from where the fragments sit. The related operational hazard is the period when a replacement replica is being filled: during bootstrap from a snapshot and log tail the key set has one fewer copy than the configuration states, and placement cannot restore redundancy that the copy has not yet delivered.