Copysets and the Tail of Random Placement

Independent random placement is the default because it is simple and, per object, it looks good. Choose three nodes uniformly at random from a cluster, and the probability that all three sit in the same failure domain is small. The per-object view is the wrong view. The quantity that matters is how much data a single failure event destroys, and that is a property of the placement distribution’s tail over the whole population, not of any one object.

The arithmetic of one bad event

Take a cluster of N nodes with three replicas per object, placed uniformly at random with no constraint. Suppose a failure event removes a set of nodes of size s, such as a rack losing power, a switch rebooting a subnet. An object is lost if all three of its replicas are inside that set. For one object, the probability is $(s/N)^3$. With N = 1000 and s = 10, that is $10^{-6}$, which reads as negligible.

Multiply by the number of objects. A cluster holding 10 million objects loses about ten of them, on average, from a single event that took out one percent of its nodes. Ten objects lost is not a rounding error; it is a data-loss incident with a cause, and the same event on a slightly different cluster, with a larger population or a larger failure set, loses thousands.

The cubic term is what makes the tail steep. Doubling the size of the failure set multiplies the loss count by eight. A cluster designed against a single-node failure is not designed against a rack failure, and the difference is a factor of $s^3$ rather than $s$.

Why random placement is worse than it looks

The calculation above assumes replicas are chosen uniformly and independently, and real systems do not do that. Most placement schemes choose replicas by walking a preference list: the ring successors of a key’s position, or the first candidates returned by a placement rule, which correlates the choices. Three replicas chosen as the first three successors on a ring are three specific nodes, and the probability that they share a failure domain is not the product of independent probabilities but a function of how the ring distributes nodes across domains.

The ring case has a well-known failure mode. If nodes are assigned ring positions uniformly at random and the cluster’s nodes are themselves grouped by rack, then the three successors of a random point are three nodes chosen from the ring, and the chance that two of them are in the same rack is the birthday problem applied to a rack population. With a hundred racks and three successors, the chance of a collision is small per object, but over a million objects it is a large number of objects whose replicas share a rack. The per-object probability is small; the population makes it a certainty that some objects are badly placed.

This is the observation the copyset work formalises. Random or ring-based placement produces a distribution over replica sets, meaning the set of nodes that hold some object’s copies, and that distribution has a tail of sets that are entirely inside one failure domain. Every object in such a set is lost by one event. The number of distinct sets is much smaller than the number of objects, so the sets are shared: a bad set is not a single unlucky object but a class of objects that all fail together.

N = 1000 nodes, R = 3 replicas, S = 10000000 objects
rack failure of size s = 10:  P(object lost) = (s/N)^3 = (0.01)^3 = 1e-6
expected objects lost to one such event = S * 1e-6 = 10

with ring placement and 100 racks of 10 nodes:
the triples that matter are the rack-internal ones, 100 * C(10,3) = 12000
every object assigned to one of those triples fails together in a rack loss

The last line is the point. The expected-loss arithmetic per object understates the damage when losses are correlated across objects, because the events are not independent across objects: one rack failure takes out every object whose set was that rack’s triple.

Bounded placement

The remedy is to bound the number of distinct replica sets, and to ensure that no set lies inside a failure domain. Copyset placement does exactly this: partition the nodes into groups of size equal to the replica count, form the sets from a fixed number of random permutations of the group, and assign each object to one of the resulting sets. The number of distinct sets is a small multiple of the number of groups, and by construction no two members of a set are in the same failure domain if the grouping respects the domain boundaries.

The trade is granularity. Bounding the number of sets means that recovery after a node loss is constrained: the objects that were on the lost node can only move to nodes that appear in the same sets, which limits how evenly the rebuilt data can be spread. With a small set count, the replacement for a lost node is one of a small number of partners, and those partners receive a disproportionate share of the rebuild. With a large set count, the spread improves but the tail returns.

The second cost is that the placement is no longer a pure function of the key. It becomes a function of the key and of the set assignment, which is metadata the cluster must store and propagate. This is the same state-for-precision trade that consistent hashing avoids and that CRUSH-style placement avoids differently. The metadata is small, a few bytes per object or a per-range assignment, but it is not zero, and it must be reconstructed after a cluster-wide event.

The rack as the unit that actually fails

The choice of failure domain is the assumption the whole analysis rests on, and it is worth being explicit about which domains have historically dominated. Individual drive failure is the most common event and the least damaging, because a scheme with any redundancy handles it. Power loss, network failure, and cooling failure are rarer and remove a set of nodes at once. Operator error, such as a maintenance script applied to the wrong host group, a firmware update rolled to a rack, is rarer still and removes a set according to the operator’s grouping rather than the hardware’s.

The last category is the one that placement cannot fully defend against, because the grouping is chosen at the time of the event. A cluster that spreads replicas across racks is protected against a rack failure and unprotected against a change-management action that touches one node per rack in a rolling fashion. The defence against that is not placement but pacing: a rolling change must not proceed faster than the repair path can restore redundancy, which ties the change rate to the degraded window.

The size of the domain is also a design input. A rack of ten nodes losing power removes ten nodes; a row of twenty racks sharing a power feed removes two hundred. Placement that separates replicas by rack and not by power feed has satisfied the letter of the constraint and not its purpose, which is why real policies declare several overlapping domain types rather than one hierarchy level.

Interaction with erasure coding

Erasure coding changes the arithmetic but not the structure of the problem. A k-of-n code with m = n-k loses an object when m+1 fragments are inside the failure set. For a set of size s in a cluster of N nodes, the probability for one object is the hypergeometric probability of drawing at least m+1 fragments from the set when placing n fragments:

$$P(\text{loss}) = \sum_{j=m+1}^{n} \frac{\binom{s}{j}\binom{N-s}{n-j}}{\binom{N}{n}}$$

The tail behaviour is the same shape and worse in one respect: a stripe has n fragments, so it has n chances to be hit rather than three, and the combinatorial sum has more terms. A stripe that places its fragments with a placement rule guaranteeing rack diversity is safe from a single rack failure by construction; a stripe placed randomly has a probability of containing m+1 fragments from the same rack that grows with n and with m.

The practical consequence is that erasure-coded clusters need the domain constraint more than replicated ones, not less, because the code’s tolerance is expressed in fragments and the placement’s job is to ensure that a domain failure costs at most one fragment. A code that tolerates four fragment losses is worth nothing if a rack failure removes five fragments of the same stripe, and random placement makes that outcome a matter of probability rather than design.

What the tail means for the durability claim

The durability figures discussed in the replication arithmetic are computed per object under an independence assumption. The copyset analysis shows that the assumption fails at the population level: the expected number of objects lost in a single event is the sum over objects of a small probability, and when the probabilities are correlated the sum is dominated by the few objects that share a bad set rather than spread evenly.

The right framing is in terms of events, not objects. A cluster’s durability is the probability that no event occurs which removes a full replica set for any object. Bounding the number of distinct sets and ensuring each set is domain-diverse makes the event analysis tractable: there are a small number of sets, each is checked once, and an event that does not contain a set loses nothing. Without that bound, the analysis requires enumerating a distribution over sets that is large and has a tail, which is the same as not having an analysis at all.

The remaining exposure after bounded placement is the set count itself. If the cluster has G groups and P permutations, it has G·P sets, and a failure set that happens to contain one of them loses all the objects assigned to it. The probability of that depends on the size of the failure set relative to the cluster, and it cannot be reduced to zero without reducing the set count to a point where placement is no longer flexible. The design question is where on that curve the deployment sits, and the answer is a choice about what failure the operator is willing to lose data to, not a choice that can be made by the storage engine alone.