CRUSH Placement: Deterministic Mapping Over a Weighted Hierarchy

A placement function has to answer one question many times per second: given an object and a cluster description, which devices hold it. A lookup table answers it precisely and becomes a bottleneck, because the table must be stored, replicated, and updated on every topology change. A hash of the object identifier answers it without state and cannot respect topology. CRUSH is a hash-based function that threads the needle by hashing the object together with a description of the hierarchy, so the answer is computed rather than looked up, and the description changes rarely.

The map as a tree of buckets

The cluster is described as a tree. Leaves are devices, each with a weight, usually its capacity in terabytes. Interior nodes are buckets (host, rack, row, room), each with a bucket type and a list of children. A placement rule names a sequence of bucket types to descend through, and the number of replicas to take at each stage.

Placing one replica is a descent. The object identifier, the replica number, and the current bucket’s identifier are hashed to produce a pseudorandom value, which selects a child of the bucket. The descent continues until a device is reached. The replica number is part of the hash input, which is what makes the second replica choose a different path than the first: the same object, hashed with r = 0 and r = 1, produces unrelated choices at every level.

The consequence is that placement is a pure function of the object name, the replica number, and the map. Any client holding a copy of the map computes the same answer as any other, with no communication and no lookup table. The map is a few kilobytes of structured metadata for a large cluster, and it is distributed as part of the cluster’s state rather than per-object metadata.

rule replicated_rule {
    id 0
    type replicated
    step take root
    step chooseleaf firstn 0 type host
    step emit
}

The rule above says: start at the root, take as many leaves as there are replicas (the 0 means “as many as the pool’s replica count”), descending to the first host-level bucket and taking a device within it. Because the descent stops at the host level and then picks a device, no two replicas share a host. Changing host to rack produces a placement that only guarantees rack diversity, and the operator’s choice of type is the choice of which failure domain is being defended against.

Bucket types and the selection problem

Each interior node must choose among its children with probability proportional to weight, but the choice has to be deterministic given the hash input and must tolerate children being added or removed. Several algorithms have been used for this, and the evolution between them is instructive.

The simplest is uniform selection: hash to an index, take that child. It ignores weights entirely, so a bucket with one large device and three small ones distributes a quarter of the objects to each.

List selection walks the children in a fixed order, accumulating weights, and picks the first child whose cumulative weight exceeds the hash value scaled to the total. Adding a child at the end changes the selection only for hash values in the new child’s range, which is the consistent-hashing property applied within a bucket. But the choice is biased by order: children early in the list are selected by smaller hash values, and the distribution over a small number of objects can be uneven. Removing a child from the middle shifts every subsequent child’s range, which moves a large fraction of the bucket’s objects.

Tree selection arranges children as a binary tree and chooses a subtree by weight at each node, recursing. It behaves better than list selection under insertion and removal but requires a balanced tree and more hash computations per choice.

Straw selection gives every child a straw and keeps the longest, where the length is derived from a uniform variate $u$, obtained by hashing the child’s identifier together with the input, and the child’s weight $w$. Written as a minimisation, the winner is the child with the smallest $-\ln(u)/w$; its reciprocal is the straw length, so the longest straw and the smallest quotient are the same choice, and the selection is weight-proportional because a race between exponential variates of rate $w$ is won by child $i$ with probability $w_i / \sum_j w_j$. Because each child’s straw is computed independently, removing one child does not change any other child’s straw, so only the objects that chose the removed child move. That is the property list selection lacks, and it is why straw is the default for buckets with a modest number of children.

The cost is $O(n)$ hash computations per bucket with n children, against $O(\log n)$ for tree selection. For a bucket with a hundred children, that is a hundred short hashes per placement decision, which is acceptable when placement decisions are cached or batched and unacceptable when they are on a per-request critical path. This is the trade that explains why different bucket types exist rather than one universal algorithm: the choice is between insertion stability and per-decision cost.

Topology change and the data that moves

Editing the map is the operation that matters operationally. Adding a device to a bucket changes the straw lengths in that bucket only; objects whose winning straw was the new device’s move, and the rest stay. With straw selection the moved fraction is proportional to the new device’s weight share, which is the minimum possible.

Adding a whole host is a larger event, because it introduces a new bucket and a new path. Objects whose descent previously picked a different host may now pick the new one, and the fraction that moves is bounded by the new host’s share of its parent bucket. Removing a host moves exactly the objects that were on it, plus the small fraction whose straws shift within the parent.

The subtle case is changing the rule rather than the tree. Changing the failure domain from host to rack changes the descent for every object, so the entire dataset moves even though no device was added. The change is correct, since the new placement genuinely differs, but its cost is a full rebalancing, and there is no way to make it incremental because the function itself changed.

A second subtlety is the map version. Two clients with different map versions compute different answers for the same object, and a client with a stale map writes to a device that the current map does not assign. The store must either reject writes from stale clients or treat the write as a misdirected operation to be forwarded. This is the same membership propagation problem that a ring has, in a form where the map is versioned explicitly rather than inferred from the ring.

Failure and the retry path

CRUSH computes a placement; it does not know which devices are alive. When a chosen device is down, the client must retry, and the retry must produce a different device without changing the placement for objects that are fine. The mechanism is to mark the failed device out of the map, which changes the straw lengths in its bucket and moves the objects that were on it to their next-best choices. That is a map edit, so it is a cluster-wide operation with a version bump, not a per-request decision.

The alternative used in practice is a retry that rehashes with an incremented attempt number, taking the next candidate in a deterministic sequence. The sequence must be defined by the placement function so that every client generates the same fallback order; otherwise two clients retrying the same failed device diverge to different replacements, and the store ends up with more copies of the object than its replication factor. The fallback order is part of the placement specification, and its absence is a common source of replica-count drift after failures.

Degraded placement interacts with the durability arithmetic in a way worth stating: while a device is out and its objects sit on fallback targets, the objects have the right number of copies but the wrong failure-domain diversity, because the fallback target was chosen by the retry sequence rather than by the rule’s bucket descent. The rule guarantees host diversity among the primary choices; it does not guarantee it among fallbacks. A cluster that stays in a degraded state for long accumulates objects whose copies are less diverse than the rule promises, which is an argument for making the fallback path consult the failure domain rather than just the attempt counter.

Weights, reweighting, and the rebalancing storm

Weight is the knob that controls how much data a device receives, and it is also the knob that produces the most disruptive maintenance. Raising a device’s weight increases its straw lengths, so it wins more selections, and objects move onto it. Lowering a weight moves objects off. The moved fraction is proportional to the weight change, which makes small adjustments cheap and large ones expensive.

The reweighting storm is the operational pattern where an operator raises the weight of several new devices at once to absorb capacity. Each device’s change moves a fraction of objects, the fractions add, and the cluster spends the following hours migrating. Because migration competes with foreground traffic, the cluster’s latency degrades exactly when the operator is trying to improve capacity, which is why reweighting is usually staged: one device at a time, with the migration rate capped, and with a pause long enough for the repair and backfill paths to drain before the next change.

The final property worth noting is that CRUSH’s determinism is also its rigidity. A placement that is computed from a map cannot express a per-object exception. Pinning a particular object to a particular device requires either a special rule or a namespace that maps to one. Systems that need per-object placement control end up with a lookup layer in front of the hash, which reintroduces the metadata they were trying to avoid, and the trade is the same one the ring made: state for precision, or hashing for scale.