The CRUSH algorithm — computing placement from the map

Why this matters in production

CRUSH is the reason Ceph has no metadata bottleneck, and it is the reason topology changes move data. Both follow from it being a computation rather than a table.

The two stages

stage 1:  object name  →  hash  →  PG id
          pg = hash(name) % pg_num,  prefixed with the pool id

stage 2:  PG id + CRUSH map + rule  →  ordered OSD list

Stage one is a plain hash and depends only on the object name and the pool’s pg_num. Stage two is CRUSH proper.

ceph osd map rbd-vms myobject
# pg 7.b1f2c3d (7.3d) -> up ([12,47,83], p12) acting ([12,47,83], p12)

The 7.b1f2c3d is the full hash; 7.3d is it masked to pg_num.

How CRUSH walks the map

The rule directs a descent through the bucket hierarchy:

step take default                  enter at the root bucket
step chooseleaf firstn 0 type host descend, picking distinct hosts,
                                   then a leaf OSD within each
step emit                          return the result

At each bucket, CRUSH selects a child using a hash of the PG id, the bucket id, and an attempt number, weighted by the children’s weights. The straw2 algorithm is used for this selection.

Determinism comes from the inputs: the same PG id against the same map produces the same result, everywhere, every time. No coordination is needed because there is nothing to coordinate.

What CRUSH optimises for

1. Even distribution, weighted by capacity.
2. Minimal movement on change — adding capacity should move only what belongs on the new capacity.
3. Failure-domain separation as directed by the rule.
4. Speed — the computation runs on every client for every operation.

The second property is why straw2 replaced earlier bucket algorithms. Under straw2, adding an OSD moves approximately its fair share of data and no more.

Reproducing placement manually

# what PG does this object map to?
ceph osd map rbd-vms rbd_data.abc123.0000000000000002

# what OSDs hold that PG?
ceph pg map 7.3d

# where are those OSDs?
ceph osd find 12
ceph osd tree

Four commands, and they answer any “where is my data” question without a lookup service existing anywhere in the system.

Quiz

Production discipline

Validate every CRUSH change offline before applying it: crushtool --test --show-bad-mappings proves the rule is satisfiable and osdmaptool --test-map-pgs-dump estimates the movement, both without touching the cluster. Save the current map first, since reverting is possible but expensive. And read undersized PGs on a healthy cluster as an unsatisfiable rule, because CRUSH exhausts its retries silently rather than reporting which constraint it could not meet.

Cross-course references

• Ceph: Part XV (CRUSH Maps and Rules) for authoring the rules.
• Ceph: Part XIV (CRUSH Failure Domains) for choosing the domain.
• Ceph: Part VII (RADOS) for where CRUSH sits in the write path.