Ceph Under the Hood: CRUSH, Maps, Authentication and PGs

8-1 Before you start#

8-1-1 What questions does this chapter answer?#

So far we have seen Ceph from the outside: commands, services and interfaces. This chapter goes inside. Every important decision in designing and troubleshooting Ceph (why the data is where it is, why a PG is stuck, why a CRUSH rule does not work) comes back to a few basic mechanisms, which we examine in this chapter:

• How does data find its place without a central table?
• What structure does the CRUSH map have, and how do we write rules?
• What are tunables, and why does the "non-optimal tunables" warning appear?
• Which cluster maps are there, and how do the MONs stay available?
• How does cephx work, and how do we restrict capabilities?
• What is the path of a write from the client to the disk, and what states do PGs have?
• How do we place a pool on specific OSDs?

8-2 Scaling without a central table#

8-2-1 The placement problem#

Most older distributed storage systems had a metadata server or lookup table that said where each block was. At large scale this table has three problems: it becomes a performance bottleneck, it is a single point of failure, and it must be updated with every hardware change. Ceph has removed this table: every client and every OSD computes the location of the data itself. The inputs to this computation are only the object name, the pool id and the cluster map, which everyone has.

8-2-2 The two mapping stages#

1. 1. Object to PG: the object name is hashed, and its remainder modulo the pool's PG count (more precisely, with the stable mod algorithm) gives the PG number. A PG id combines the pool number and the PG number, such as 3.1f.
2. 2. PG to OSD: the CRUSH algorithm, given the PG id, the CRUSH map and the pool's rule, returns an ordered list of OSDs. The first active OSD is the primary.

ceph osd map rbd rbd_data.12ab.0000000000000004
# osdmap e1234 pool 'rbd' (3) object '...' -> pg 3.8c7e1b1f (3.1f) -> up ([12,4,27], p12) acting ([12,4,27], p12)
ceph pg map 3.1f

8-2-3 up and acting#

The up set is CRUSH's pure output. The acting set is the set that actually serves requests. The two are usually identical; a difference means Ceph is temporarily using other OSDs (for example pg_temp during backfill until the new OSD has all the data) or an explicit upmap has changed CRUSH's result for that PG.

8-3 The CRUSH mechanism#

8-3-1 The hierarchy#

The CRUSH map consists of two parts: the hierarchy (a tree of buckets showing the physical location of each OSD) and the rules, which say how to spread replicas across this tree. The default bucket types, from bottom to top, are osd, host, chassis, rack, row, pdu, pod, room, datacenter, zone, region and root. You do not need to use all of them; define only the levels that really are independent failure domains.

ceph osd crush tree --show-shadow
ceph osd crush add-bucket rack1 rack
ceph osd crush move rack1 root=default
ceph osd crush move ceph-node1 rack=rack1
ceph osd crush set-device-class nvme osd.20
ceph osd crush class ls

8-3-2 Weight#

Each OSD has a CRUSH weight (by default equal to its capacity in terabytes), and each bucket's weight is the sum of its children's weights. CRUSH spreads data in proportion to weight. There is also another weight called reweight (between 0 and 1) that used to be used to correct the distribution temporarily; today the balancer does this more precisely with upmap.

ceph osd crush reweight osd.20 3.49309     # permanent CRUSH weight
ceph osd reweight 20 0.9                   # temporary correction (prefer the balancer)

8-3-3 The bucket algorithm#

CRUSH has an algorithm for choosing a child in each bucket. Today in practice only straw2 is used (since Hammer, the default for new buckets). The key advantage of straw2 is that changing one item's weight moves data only between that item and the rest, not among the other items; that is, the minimum necessary movement.

8-3-4 Rules#

A CRUSH rule defines the selection steps. Most of the time you do not need to write a rule by hand; the helper commands are enough:

# Replicated: replicas on different hosts, SSD only
ceph osd crush rule create-replicated rep-ssd-host default host ssd
# Replicated with a rack failure domain
ceph osd crush rule create-replicated rep-rack default rack
# EC from a profile
ceph osd erasure-code-profile set ec42-rack k=4 m=2 crush-failure-domain=rack crush-device-class=hdd
ceph osd crush rule create-erasure ec42-rack ec42-rack
ceph osd crush rule ls
ceph osd crush rule dump rep-ssd-host

For more complex cases, extract the map, edit it and test it before applying:

ceph osd getcrushmap -o crush.bin
crushtool -d crush.bin -o crush.txt
# edit crush.txt
crushtool -c crush.txt -o crush.new
crushtool -i crush.new --test --rule 1 --num-rep 3 --show-statistics --show-bad-mappings
ceph osd setcrushmap -i crush.new

An example of a hand-written rule that puts two replicas in one datacenter and the third in another datacenter:

rule rep-2dc {
    id 5
    type replicated
    step take default
    step choose firstn 2 type datacenter
    step chooseleaf firstn 2 type host
    step emit
}

8-3-5 Device classes and the shadow tree#

Since Luminous each OSD has a device class (hdd, ssd, nvme or any name you like). CRUSH builds a shadow tree for each class, for example default~ssd, containing only the OSDs of that class. A rule with a class runs on that shadow tree. This feature replaces the old trick from the 2019 book of building two separate roots to separate SSDs and HDDs.

8-4 Tunables#

8-4-1 Why tunables?#

CRUSH was not perfect from the start. In some hierarchies (for example small trees, or when many OSDs are out) it could not find enough replicas for every PG, or it moved a lot of data for small changes. Fixing these behaviours changes the mapping result, so they could not be applied silently: every client must compute the same result the OSDs compute. Ceph's solution is tunables: flags in the CRUSH map that determine the algorithm's behaviour, grouped into profiles named after releases.

ceph osd crush show-tunables
ceph osd crush tunables optimal       # causes data movement!
ceph features                         # version and features of connected clients
ceph osd get-require-min-compat-client

8-4-2 The non-optimal warning#

If the cluster's tunables lag behind the optimal profile of the current release, the OLD_CRUSH_TUNABLES warning is shown. You can fix it by updating the tunables or, if you have old clients you cannot upgrade, silence it temporarily with mon_warn_on_legacy_crush_tunables=false. A similar warning, OLD_CRUSH_STRAW_CALC_VERSION, appears when the map still uses the old, buggy version of the weight calculation in straw buckets.

# convert straw buckets to straw2 with minimal movement
ceph osd crush set-all-straw-buckets-to-straw2

8-5 Cluster maps and MONs#

8-5-1 The maps#

The cluster state is kept in several maps, all versioned with an epoch (an increasing version number):

8-5-2 MON availability#

MONs reach consensus with the Paxos algorithm: a map change is valid only when a majority of MONs (a quorum) accepts it. One MON is the leader and the rest are peons.

ceph mon stat
ceph quorum_status -f json-pretty
ceph mon dump
ceph tell mon.ceph-node1 mon_status

8-6 Inside the code: placement, authentication and messaging#

8-6-1 From object name to OSD#

The first stage happens in pg_pool_t::hash_key() (src/osd/osd_types.cc): the object name, together with the namespace if there is one, is turned into a 32-bit number with the pool's hash function (rjenkins by default). This number is then mapped to the PG range with ceph_stable_mod(). This small function is one of the cleverest pieces of Ceph:

/* from ceph/ceph, LGPL — src/include/rados.h (excerpt) */
static inline int ceph_stable_mod(int x, int b, int bmask)
{
	if ((x & bmask) < b)
		return x & bmask;
	else
		return x & (bmask >> 1);
}

b is the number of PGs and bmask is the smallest power of 2 minus one that is at least b. If pg_num is not a power of 2 (for example 12 with bmask=15), the values 12 to 15, which have no corresponding PG, are "folded" into the lower half (4 to 7). The important result: when pg_num grows from 12 to 13, only the objects that went to PG 5 and whose hash falls on 13 move; that is, PG splitting is local and the data is not all reshuffled. This property is what made gradual pg_num increases (since Nautilus) possible.

8-6-2 straw2: choosing by drawing exponential lots#

bucket_straw2_choose() in src/crush/mapper.c computes a "draw" for each bucket item and chooses the largest. The core of the computation:

/* from ceph/ceph, LGPL — src/crush/mapper.c, generate_exponential_distribution() (excerpt) */
unsigned int u = crush_hash32_3(type, x, y, z);
u &= 0xffff;
__s64 ln = crush_ln(u) - 0x1000000000000ll;
return div64_s64(ln, weight);

The mathematics behind it (in this book's words): suppose U is uniform on (0, 1]. Then −ln(U) / w is an exponential variable with rate w. The minimum of several independent exponential variables with rates w₁ to wₙ belongs to item i with probability wᵢ / Σw. Because ln(U) is negative, ln(U)/w is largest for the same item for which −ln(U)/w is smallest. Therefore:

draw_i = ln(u_i / 65536) / w_i          (u_i = hash(x, id_i, r) mod 2^16)
choose argmax_i draw_i   ⇒   P(i) = w_i / Σ_j w_j

crush_ln() approximates the logarithm with fixed-point tables (no floating point, because the same code also runs in the Linux kernel); its output is in the range [0, 2⁴⁸), and subtracting 2⁴⁸ turns it into the negative value equivalent to ln(u/65536). Weights are in 16.16 fixed-point format (0x10000 means 1.0).

8-6-3 Retrying: collision and reject#

crush_choose_firstn() descends through a bucket for each replica (rep) until it reaches the desired type. If the chosen item has already been chosen (collide) or the OSD is out or overfull (reject), the ftotal counter is incremented and the choice is repeated with r' = r + ftotal, up to the choose_total_tries limit (a tunable, default 50 in the newer profiles).

pseudocode: crush_choose_firstn (this book's summary)
  for rep in 0..numrep-1:
      ftotal = 0
      loop:
          r = rep + ftotal
          item = descend(bucket, x, r) until type matches     # straw2 at each level
          collide = item in out[0..rep-1]
          reject  = is_out(item, x) or (chooseleaf and leaf selection failed)
          if not collide and not reject: out[rep] = item; break
          ftotal += 1
          if ftotal >= choose_total_tries: give up on this rep

The is_out() function is interesting: an OSD with a reweight between 0 and 1 is rejected probabilistically; hash(x, item) & 0xffff is compared with the reweight value (16.16). So ceph osd reweight 12 0.8 means that about 20% of the PGs CRUSH gave to osd.12 go to another OSD after a retry. This is why reweight differs from the CRUSH weight (which changes the share in straw2).

8-6-4 cephx: tickets and rotating keys#

The main structures are defined in src/auth/cephx/CephxProtocol.h: CephXServerChallenge, CephXAuthenticate, CephXTicketBlob, CephXServiceTicket, CephXServiceTicketInfo and CephXAuthorizer. The three main request types are identified by the constants CEPHX_GET_AUTH_SESSION_KEY (0x0100), CEPHX_GET_PRINCIPAL_SESSION_KEY (0x0200) and CEPHX_GET_ROTATING_KEY (0x0400).

• The client's shared key is never sent over the network; the client only proves that it has it (by answering a challenge).
• The service ticket is encrypted with the service's rotating key, which the MON changes periodically and the OSDs fetch; so the OSD does not need to contact the MON to check a ticket.
• Ticket lifetimes are controlled by auth_mon_ticket_ttl (default 72 hours) and auth_service_ticket_ttl (default 1 hour); the client renews before expiry.

8-6-5 msgr2: frames and secure mode#

In src/msg/async/frames_v2.h, each frame starts with a preamble_block_t holding the tag (enum class Tag: HELLO, AUTH_REQUEST, AUTH_REQUEST_MORE, ..., SESSION_RECONNECT, MESSAGE, KEEPALIVE2, COMPRESSION_REQUEST and so on), the number of segments (at most MAX_NUM_SEGMENTS = 4) and the length and alignment of each segment. Separating the data segment with a specific alignment lets the data buffer reach BlueStore directly without copying (zero-copy).

ceph config get mon ms_cluster_mode          # crc or secure (and the order of preference)
ceph config get mon ms_service_mode
ceph config get mon ms_client_mode
ceph config set global ms_cluster_mode "secure"   # encrypt traffic between OSDs
ceph mon dump | grep -E "v2:|v1:"                 # the addresses of the two protocols

8-7 Data movement by the numbers: adding a host and changing a weight#

This section answers two practical questions with real CRUSH mappings: "how much data moves when a host is added?" and "what moves when an OSD's weight changes?". The map was built with crushtool --build --num_osds 132 … host straw2 12 root straw2 0. The ten-host version of the same map was obtained with --remove-item so that the ids of all buckets and OSDs stay fixed, because straw2 uses the item id in the hash. A three-replica pool with 8192 PGs was defined with osdmaptool --createsimple 256 --pg-bits 5 --pgp-bits 5, and the mapping of each case was taken with --test-map-pgs-dump. The tools were from Ceph 18.2.7 and the tunables were the defaults: chooseleaf_vary_r 1, chooseleaf_stable 1 and choose_total_tries 50.

8-7-1 Adding a host#

pseudocode
A = up(pg) with the old map ; B = up(pg) with the new map          # for each pg in [0, pg_num)
moved = Σ_pg |set(B[pg]) − set(A[pg])|                         # new placements, ignoring order
to_new = Σ_pg |{o ∈ B[pg] − A[pg] : o on the new host}|
ideal = pg_num × size × (new host weight / total weight)               # 24576 × 12/132

Result. Of 24576 replica placements, 2184 (8.89%) went to the new host. The ideal is 2234 (9.09%). This is exactly the behaviour straw2 guarantees: each item has an independent "draw" ln(u)/w (the generate_exponential_distribution function), and adding an item changes the winner only where the new item's draw is higher.

But another 328 placements (1.33%) moved between old OSDs. A real example from this mapping: PG 1.58 went from [76, 113, 46] to [76, 125, 116]. The new host took the second position and host 9 was pushed to the third. In crush_choose_firstn the leaf within a host is chosen with sub_r = r >> (vary_r − 1), i.e. it depends on the position's r. So within the same host 9, osd.116 was chosen instead of osd.113. The practical consequence is that adding capacity causes about 15% more movement than the ideal (2512 versus 2234). Take this into account when estimating backfill time.

8-7-2 Changing an OSD's weight#

pseudocode
for each new placement y ∈ B[pg] − A[pg]:
    if osd.5 is the incoming or outgoing OSD of this PG      → "osd.5 itself"
    else if the incoming or outgoing OSD is on host0       → "other OSDs of host0"   (host0's weight in root changed)
    else                                          → "unrelated hosts"   (position/r shift)

Result. When osd.5's weight goes from 1.0 to 2.0, 411 placements change: 214 are osd.5 itself, 169 are other OSDs of host0 and 28 are unrelated hosts. When the weight drops to 0.8, 84 placements change: 42, 40 and 2.

The large "other OSDs of host0" share is not a flaw of straw2. crushtool --reweight-item also raises host0's weight in the root from 12 to 13, and host0 gets a larger share of the PGs. straw2 spreads this share within host0 in the ratio 2/13 for osd.5 and 1/13 for each other OSD.

In this experiment the old straw algorithm gave almost the same result (400 versus 411 for weight 2.0), because all items but one had equal weights. The documented flaw of old straw (movement between the other items of the same bucket when one item's weight changes) shows up in buckets with unequal weights. Even so, straw2 is the only algorithm that guarantees this property for any weight distribution.

8-8 Authentication and authorisation#

8-8-1 cephx#

Ceph uses the cephx protocol for mutual authentication between clients and daemons. Its idea is similar to Kerberos: the secret key is never sent over the network, and the MON, as the authority, issues time-limited tickets with which the client talks directly to OSDs and MDSs.

8-8-2 Users and capabilities#

Every identity in Ceph has the form type.id (for example client.backup or osd.3) and has a key and a set of capabilities. Capabilities are defined separately for each daemon type:

ceph auth ls
ceph auth get client.admin
# a user for RBD in one pool only
ceph auth get-or-create client.vmhost mon 'profile rbd' osd 'profile rbd pool=vms' mgr 'profile rbd pool=vms'
# a read-only user for monitoring
ceph auth get-or-create client.monitor mon 'allow r' mgr 'allow r'
# a user restricted to one namespace
ceph auth get-or-create client.tenant1 mon 'allow r' osd 'allow rw pool=shared namespace=tenant1'
ceph auth caps client.vmhost mon 'profile rbd' osd 'profile rbd pool=vms, profile rbd-read-only pool=images'
ceph auth rm client.old-app

8-8-3 Key rotation and encryption#

• A user's key can be rotated with ceph auth rotate (in recent releases) or by creating a new key and replacing it gradually.
• Umbrella hardened cephx: the new AES256KRB5 cipher became the default in place of older key types, and online key rotation was added. Before upgrading, check the compatibility of old clients (especially kernel clients).
• To encrypt network traffic, enable secure mode in msgr2 (ms_cluster_mode, ms_service_mode, ms_client_mode). This mode has CPU overhead; measure it on real hardware.

ceph config set global ms_client_mode secure
ceph config set global ms_service_mode secure
ceph config get mon ms_cluster_mode

8-9 The I/O path and PGs#

8-9-1 The path of a write#

1. 1. The client (librados) computes the PG and the primary with the map it has.
2. 2. It sends the request only to the primary.
3. 3. The primary records the operation in that PG's log and sends it to the secondaries in parallel.
4. 4. Each OSD commits the transaction in BlueStore.
5. 5. The primary acks the client after receiving confirmation from all OSDs in the acting set.

So write latency equals the slowest OSD in the acting set plus two network round trips. This is why one slow disk slows down the whole cluster (chapter 17). In an EC pool the primary splits the data into k data chunks and m parity chunks and sends each chunk to one OSD (chapter 13).

8-9-2 PG states#

ceph pg stat
ceph pg dump_stuck inactive
ceph pg dump_stuck unclean
ceph pg ls degraded
ceph pg 3.1f query | jq '.recovery_state'

8-9-3 min_size and size#

size is the number of replicas and min_size is the minimum number of healthy replicas a PG needs to accept I/O. For a three-way replicated pool, min_size=2 is standard. Lowering it to 1 keeps the cluster "available" during a failure but sharply raises the risk of data loss, because a write might exist on only one disk.

8-10 A pool on specific OSDs#

The modern way to place a pool on a specific group of OSDs is the device class. If the default classes are not enough (for example you want to set aside the NVMe disks of a particular model for one tenant), define a custom class:

for id in 30 31 32 33 34 35; do
  ceph osd crush rm-device-class osd.$id
  ceph osd crush set-device-class fastnvme osd.$id
done
ceph osd crush rule create-replicated fast-host default host fastnvme
ceph osd pool create tenant-a-db 64 64 replicated fast-host
ceph osd pool application enable tenant-a-db rbd
ceph pg ls-by-pool tenant-a-db | head

8-11 Supplementary and up to date#

• Device classes and the shadow tree (Luminous) replaced the separate SSD/HDD roots seen in older sources.
• upmap and the balancer have replaced manual reweighting (chapter 7).
• The MSR rule (Squid) gives more flexibility for EC.
• cephx in Umbrella: the AES256KRB5 cipher as the default and online key rotation.
• MON RocksDB backup (Umbrella).
• The read balancer (Reef) for distributing primaries.

8-12 Hands-on exercise#

1. 1. Run ceph osd map for three different objects and compare the PG and OSD paths with ceph pg map.
2. 2. Build a two-rack hierarchy, move the hosts, and apply the rep-rack rule to a test pool. Observe the amount of movement.
3. 3. Extract the CRUSH map, add the two-datacenter rule, and check the distribution with crushtool --test before applying it.
4. 4. Create a user with profile rbd for one pool only and prove that it has no access to another pool.
5. 5. Stop an OSD and record the PG states over time with ceph pg stat.
6. 6. Using a custom device class, create a pool on three specific OSDs and check the PG distribution.

8-13 Review questions#

1. 1. What are the two stages of mapping an object to an OSD, and why is the PG needed?
2. 2. What is the difference between the up set and the acting set?
3. 3. What is the advantage of straw2 over the earlier algorithms?
4. 4. Why does changing tunables cause data movement, and what must be checked beforehand?
5. 5. Why do four MONs not tolerate more failures than three?
6. 6. Where do OSDs receive the new map from?
7. 7. Why does cephx use tickets?
8. 8. Why does write latency depend on the slowest OSD in the acting set?
9. 9. How do the incomplete and inconsistent states differ?
10. 10. What is the recommended way to place a pool on specific OSDs?

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

8-14 Sources for this chapter#

• CRUSH maps
  https://docs.ceph.com/en/latest/rados/operations/crush-map/
• CRUSH map edits
  https://docs.ceph.com/en/latest/rados/operations/crush-map-edits/
• Placement groups
  https://docs.ceph.com/en/latest/rados/operations/placement-groups/
• PG states
  https://docs.ceph.com/en/latest/rados/operations/pg-states/
• Monitoring OSDs and PGs
  https://docs.ceph.com/en/latest/rados/operations/monitoring-osd-pg/
• User management
  https://docs.ceph.com/en/latest/rados/operations/user-management/
• Cephx config
  https://docs.ceph.com/en/latest/rados/configuration/auth-config-ref/
• Messenger v2
  https://docs.ceph.com/en/latest/rados/configuration/msgr2/
• Architecture
  https://docs.ceph.com/en/latest/architecture/
• Health checks
  https://docs.ceph.com/en/latest/rados/operations/health-checks/
• Read balancer
  https://docs.ceph.com/en/latest/rados/operations/read-balancer/
• Squid release notes
  https://docs.ceph.com/en/latest/releases/squid/
• Umbrella release notes
  https://docs.ceph.com/en/latest/releases/umbrella/
• Weil et al., CRUSH (SC 2006
  https://ceph.io/assets/pdfs/weil-crush-sc06.pdf