Lower Layers (6): CRUSH at the Bit Level, from rjenkins to upmap

28-1 Introduction: how does CRUSH "compute"?#

In chapters 1 and 8 we saw CRUSH as an algorithm that determines the location of each PG without a central table. This chapter goes down to the bit level: the rjenkins hashes that make every decision deterministic, the straw2 algorithm with its fixed-point logarithm table, the step-by-step execution of crush_do_rule, the retries on collisions, and finally how choose_args, weight-set and upmap correct CRUSH's raw result. We follow a complete example from the object name to the choice of host, with numbers computed by compiling Ceph's own C code (src/crush/hash.c and mapper.c, LGPL) into a small test program.

28-2 From the object name to x#

ceph_stable_mod(x, b, bmask) is defined in include/rados.h: if x & bmask is less than b it returns that, otherwise x & (bmask >> 1). This function is "stable" because when pg_num grows from 128 to 192, only the PGs that have the new bit move (split) and the rest keep their number. This is the mathematical reason a split moves only part of the data.

28-2-1 The rjenkins hash#

crush_hashmix(a, b, c) is nine rounds of subtraction, XOR and shift on three 32-bit words, taken from Bob Jenkins's mixing function. The three-input version crush_hash32_rjenkins1_3(a, b, c) starts with hash = 1315423911 ^ a ^ b ^ c (the crush_hash_seed constant) and runs mix five times with the constants x = 231232 and y = 1232. Its important property is complete determinism on all architectures: it uses only unsigned 32-bit integer operations, no floating point. That is why the Linux kernel client (which has the same file in net/ceph/crush/) and librados get exactly the same result.

28-3 straw2: an exponential draw#

Suppose each item i with weight w_i draws an exponential random variable with rate w_i. The probability that item i has the smallest value is exactly $w_i / \sum w$. straw2 implements exactly this without floating-point numbers:

straw2 (the logic of mapper.c, LGPL; a simplified rendering by this book)
  for each item i in bucket:
      u    = crush_hash32_3(bucket.hash, x, id_i, r) & 0xFFFF       # 16 bits
      ln   = crush_ln(u) − 2^48          # ≈ 2^44 · log2((u+1)/2^16) ≤ 0
      draw = ln / weight_i                # weight in 16.16 fixed point
  return item with max draw              # the smallest −ln/w = exponential with rate w

crush_ln(x) computes $2^{44} \cdot \log_2(x+1)$ with two tables, __RH_LH_tbl and __LL_tbl (in crush_ln_table.h), using only integer operations. It first normalizes the input (the exponent), then looks up the top 8 bits of the mantissa in the first table (an approximation of 1/x and log2) and the next 8 bits in the second table (the correction). The results in our test program: crush_ln(0) = 0, crush_ln(0x7FFF) = 0xF00000000000 (that is $15 \cdot 2^{44}$) and crush_ln(0xFFFF) = 0xFFFFF0000000 (about $16 \cdot 2^{44} = 2^{48}$).

Checking the distribution: in the same program, with three items of weights 1, 1 and 2 and 300,000 values of x, the winner counts were 75,274, 74,753 and 149,973, that is 25%, 25% and 50%, just as the theory predicts.

28-4 crush_do_rule step by step#

A rule is an array of steps (crush_rule_step with op, arg1 and arg2). crush_do_rule has a working vector w and an output vector o:

numrep: if arg1 ≤ 0, numrep = result_max + arg1. So 0 means "as many as size" and -1 means "size minus one". This is used for rules such as "one in the first DC, the rest in the second DC".

28-4-1 firstn versus indep#

In firstn, order does not matter. If the second replica becomes unavailable, the third replica takes its place and everything shifts forward by one. For replication this is optimal, because only one new copy is needed. In indep, position r is always shard r. If the OSD of one shard is lost, only that position is chosen again with a new r (r + numrep · ftotal), and the other shards do not move. For EC this is vital, because shards are not interchangeable.

ceph osd getcrushmap -o cm.bin && crushtool -d cm.bin -o cm.txt
crushtool -i cm.bin --test --rule 0 --num-rep 3 --min-x 0 --max-x 1023 --show-utilization
crushtool -i cm.bin --test --rule 0 --num-rep 3 --x 0x36d15c32 --show-mappings
crushtool -i cm.bin --test --show-bad-mappings --rule 0 --num-rep 3
ceph osd map rbd rbd_data.10ab2c3d4e5f.0000000000000000     # pg and up/acting

28-5 choose_args, weight-set and upmap#

choose_args: in bucket_straw2_choose, the function get_choose_arg_weights uses weight_set[position] instead of item_weights if a weight_set exists. position is the number of the replica being chosen. This makes it possible to fix a subtle problem: in straw2 with unequal weights, the second and third replicas deviate slightly from the weight ratio, because the earlier choices have been excluded. The weight-set gives slightly different weights for each position. There are also substitute ids, so that the hash can be changed without changing the bucket's real id.

upmap: OSDMap::_apply_upmap first checks pg_upmap (replacing the whole list), then pg_upmap_items (from→to pairs) and finally pg_upmap_primaries (only setting the primary, for the read balancer). Upmaps that violate the CRUSH rule (for example two replicas on one host) are checked and removed by the mon (clean_pg_upmaps).

ceph osd pg-upmap-items 3.15 4 11        # replace osd.4 with osd.11 for PG 3.15
ceph osd rm-pg-upmap-items 3.15
ceph osd crush weight-set ls
ceph balancer status && ceph balancer eval
ceph osd dump | grep -E '^pg_upmap(_items|_primary)?' | head

28-6 is_out and reweight: a numerical example#

is_out in mapper.c interprets an OSD's reweight value (a 16.16 number between 0 and 0x10000) like this: if the weight is full, the OSD is in. If it is zero, it is out. Otherwise crush_hash32_2(x, osd) & 0xFFFF is compared with the weight, and if it is smaller, the OSD is in for this x. So a reweight of 0.5 means roughly half of the PGs CRUSH had given to this OSD are rejected and go elsewhere on retry.

28-7 Device classes and the shadow tree#

When OSDs have classes (hdd, ssd, nvme), CrushWrapper builds for each bucket and each class a "shadow" with a new negative id and a name such as default~ssd that contains only the OSDs of that class. A rule such as step take default class ssd is in fact a TAKE on the shadow id. Because the shadows have their own ids, the straw2 hash (which includes the item id) for the shadows is independent of the main tree. Adding an hdd OSD does not move any PG in the ssd pools.

ceph osd crush tree --show-shadow
ceph osd crush rule create-replicated fast default host ssd
ceph osd crush class ls-osd ssd

28-8 Three other bucket types: uniform, list and tree#

straw2 is the default today, but CRUSH had five bucket algorithms from the start: uniform, list, tree, straw and straw2. Each is a trade-off between selection speed and the amount of data movement on change. Old mappings and hand-written maps may still contain them. To understand why straw2 won, we ran all three with the real rjenkins hash. All the numbers in this section were computed with a small C program that takes hash.c and crush_ln from the Ceph code.

28-8-1 uniform: a pseudo-random permutation#

pseudocode (taken from bucket_perm_choose)
pr = r mod size
if x changed:
    if pr == 0: return items[hash3(x, bucket_id, 0) mod size]        # common shortcut
    perm = [0..size-1]; perm_n = 0
while perm_n ≤ pr:                         # incremental Fisher–Yates with a hash instead of random
    p = perm_n
    if p < size-1:
        i = hash3(x, bucket_id, p) mod (size − p)
        swap(perm[p], perm[p+i])
    perm_n += 1
return items[perm[pr]]

uniform only works correctly when all items have equal weight, because the weight is not part of the calculation at all. The bigger problem is that changing size changes the modulus of every hash. Our simulation shows that adding a fifth item to four items moves 80% of the inputs, while the minimum needed is 20%. This bucket was designed for hardware that is always bought and replaced all at once and in identical sizes.

28-8-2 list: walking from the end#

for i = size-1 down to 0:
    h = hash4(x, items[i], r, bucket_id) & 0xFFFF                   # a 16-bit number
    if (h × sum_weights[i]) >> 16 < item_weights[i]: return items[i]
return items[0]
# sum_weights[i] = Σ_{j ≤ i} item_weights[j]  ⇒ probability of choosing i given we reach it = w_i / sum_i

Why is this correct? The probability of choosing the last item is w₂/(w₀+w₁+w₂) = 2/4. If it is rejected, the probability of the middle item is w₁/(w₀+w₁) = 1/2. So P(21) = (1 − 1/2) × 1/2 = 1/4 and P(20) = 1/4. A count over 400 thousand inputs gave the same 1:1:2 ratio (100336, 99970, 199694). Adding an item at the end moves only the necessary data (20.1%). But removing an item from the middle breaks the order (36% instead of 25% in our simulation).

28-8-3 tree: a weighted binary tree#

node(i) = 2(i+1) − 1   (leaves are odd); height(n) = number of trailing zeros of n
n = num_nodes / 2                          # the root
while n is even:                           # an internal node
    t = (hash4(x, n, r, bucket_id) × node_weights[n]) >> 32     # a uniform number in [0, w)
    n = t < node_weights[left(n)] ? left(n) : right(n)
return items[n >> 1]

The elegant trick of tree is its node numbering. Because the hash depends on the node number, and the numbers of existing nodes do not change as the tree grows (the old root n4 becomes the left child of n8 in an eight-leaf tree), adding a fifth item moved exactly 20% of the data. But removing from the middle and rebuilding the tree changes the layout of the leaves, and in our simulation it caused 54% movement.

28-8-4 Comparing movement#

28-9 The balancer in upmap mode: calc_pg_upmaps#

The mgr balancer in upmap mode (chapter 19) hands the main work to OSDMap::calc_pg_upmaps in C++. This function makes a copy of the OSDMap, experiments with pg_upmap_items pairs and returns the result in an Incremental.

ppw = total_pgs / Σ weight
dev(osd) = pgs(osd) − weight(osd) × ppw
bal_score = Σ weight × (dev / target)²                  # 0 means perfect
repeat up to max times:
    overfull  = {dev > max_deviation};   more_overfull  = {0 < dev ≤ max_deviation}
    underfull = {dev < −max_deviation};  more_underfull = {−max_deviation ≤ dev < 0}
    if overfull and underfull both empty: break
    for osd in OSDs by dev descending (dev > max_deviation):
        if try_drop_remap_overfull(osd): goto test       # first take back old upmaps
        for pg on osd (without a manual pg_upmap):
            out = try_pg_upmap(pg, overfull, underfull)   # rerun CRUSH with zero weight for the overfull ones
            pos = find_best_remap(orig, out)            # the single best replacement
            if pos ≥ 0: add pair (orig[pos] → out[pos]); goto test
    for osd in underfull: try_drop_remap_underfull(osd) → test
    break
test: if new_bal_score > bal_score: reject (skip that PG)  else: apply

Numerical example. Four equal-weight OSDs, one pool with 64 PGs and size=3, so 192 copies and a target of 48 per OSD. The counts are [56, 50, 44, 42] and the deviations [+8, +2, −4, −6]. With upmap_max_deviation=5 (the balancer module's default): overfull={osd.0}, underfull={osd.3}. Score = (64 + 4 + 16 + 36)/48² = 0.0521.

After step 3, no OSD deviates by more than 5, so overfull and underfull are empty and the loop ends. From step 2 on, underfull is empty and the replacements come from more_underfull. Three pg_upmap_items entries are recorded in the OSDMap. Each change adds only one pair. The code comment says this is deliberately "slow", so that every small step really moves the distribution toward the perfect state. This example assumes the CRUSH rule allows these replacements (for example, the OSDs are on different hosts). If a replacement breaks the failure-domain rule, try_pg_upmap rejects it.

28-10 MSR rules: several OSDs per failure domain#

In EC with k+m larger than the number of hosts (for example 4+2 on three hosts), the classic rule choose indep 3 type host followed by chooseleaf indep 2 type osd has a problem. If an OSD goes out, the second step looks for a replacement only in the same host. If that host has no other healthy OSD, the shard is left unplaced, because classic CRUSH cannot go back to the previous step. MSR (Multi-Step Retry) rules, from Squid, with the types msr_firstn and msr_indep and the choosemsr step, solve this: the whole descent from the root is retried.

pseudocode
total = Π(arg1 of choosemsr steps)      # for example 3 × 2 = 6
for descent in 0 .. msr_descents-1 while the output is not complete:
    crush_msr_choose(root, [0, total), step0, tryno = descent)
crush_msr_choose(bucket, [start, end), step):
    num_strides = step.arg1 (or result_max if 0)
    stride_length = (end − start) / num_strides
    for each stride:
        if all indexes of the stride are filled: continue
        for local_try in 0 .. msr_collision_tries-1:
            r = ((descent × result_max + index) << 16) + local_try
            cand = crush_msr_descend(bucket, step.type, r)          # straw2 etc. down to the target type
            if cand is used in another stride (collision): continue
            if last step: if the OSD is out ⇒ leave the index empty (undo after the round)
            else: crush_msr_choose(cand, [stride], step+1) for the next level

Numerical example. With choosemsr 3 host and choosemsr 2 osd, total_descendants = 6, num_strides = 3 and stride_length = 2. In the recursive call for each host, total_descendants = 2 and stride_length = 1 (these are the same numbers as in the comment above crush_msr_choose in the code). The try value for descent=1, result_max=6, index=3 and local_try=0 is ((1×6+3) ≪ 16) + 0 = 9 × 65536 = 589824. So the hashes are completely different in each round. The guarantee of the choosemsr 3 host step is "at least" three hosts, not "exactly" three: one stride may use two hosts after an OSD goes out, provided those hosts are not in other strides.

28-11 Supplementary and up to date#

• MSR rules (CRUSH_RULE_CHOOSE_MSR and the types CRUSH_RULE_TYPE_MSR_FIRSTN and MSR_INDEP) exist in the Squid and main code and are not in Reef. Their goal is placing several shards in one failure domain with precise control (for example EC 8+6 on 4 racks).
• The Linux kernel has the same mapper.c, hash.c and crush_ln_table.h in net/ceph/crush/. Its support for new CRUSH features (such as MSR) depends on the kernel version, and the cluster's features must be aligned with ceph osd set-require-min-compat-client.

28-12 Hands-on exercise#

1. 1. Rebuild this chapter's test program: take hash.c and crush_ln_table.h from the Ceph code and run bucket_straw2_choose for a bucket with five items and arbitrary weights. Measure the distribution for one million x.
2. 2. Map a few objects with ceph osd map and match ps against a manual calculation of ceph_stable_mod.
3. 3. Increase the weight of one host by 10% in a test map and use crushtool --compare to see the number of PGs moved and their destinations (they should move only to that host).
4. 4. Create a manual pg-upmap-items that puts two replicas on one host and see what the mon does with it.

28-13 Review questions#

1. 1. How does ceph_stable_mod limit data movement when pg_num is increased?
2. 2. Why is HASHPSPOOL needed?
3. 3. Why does CRUSH use only integer operations?
4. 4. In straw2, how is the draw computed and why does the largest draw win?
5. 5. What does crush_ln return, and with what precision?
6. 6. Why does straw2 have minimal movement, and why did the old straw not?
7. 7. How is a collision resolved in firstn, and what is its limit?
8. 8. What is the difference between firstn and indep for EC?
9. 9. What problem does the weight-set in choose_args solve?
10. 10. What is the order in which upmaps are applied, and what does the mon do with an invalid upmap?

Answers to these questions are in Appendix E: Answers to Review Questions. Answers to this chapter's questions →

28-14 Sources for this chapter#

• The CRUSH paper (Weil et al., SC 2006
  https://ceph.io/assets/pdfs/weil-crush-sc06.pdf
• mapper.c
  https://github.com/ceph/ceph/blob/main/src/crush/mapper.c
• hash.c
  https://github.com/ceph/ceph/blob/main/src/crush/hash.c
• CRUSH maps
  https://docs.ceph.com/en/latest/rados/operations/crush-map/
• Editing a CRUSH map
  https://docs.ceph.com/en/latest/rados/operations/crush-map-edits/
• upmap
  https://docs.ceph.com/en/latest/rados/operations/upmap/
• balancer
  https://docs.ceph.com/en/latest/rados/operations/balancer/
• crushtool
  https://docs.ceph.com/en/latest/man/8/crushtool/
• Bob Jenkins's hash function
  https://burtleburtle.net/bob/hash/doobs.html