Lower Layers (2): BlueStore and BlueFS On-Disk Format

24-1 Introduction: what does BlueStore write on disk?#

In chapter 23 we saw how bytes get from a bufferlist to io_submit. This chapter shows where and in what format those bytes land on disk: from the device's first 4 kilobytes (the label) to the superblock and the BlueFS log, and from the RocksDB keys that hold the onode and extent map to the freelist bits and the in-memory cache structure. All structures were extracted from the main branch of the Ceph code (src/os/bluestore/). Wherever behaviour depends on the version, it is marked.

24-2 The device label: bluestore_bdev_label_t#

The constants are defined in bluestore_common.h: BDEV_FIRST_LABEL_POSITION = 0, BDEV_LABEL_BLOCK_SIZE = 4096, BLUEFS_SUPER_POSITION = 4096 and SUPER_RESERVED = 8192. The label's content, in order:

# reading the label (read-only; the OSD can be running)
ceph-bluestore-tool show-label --dev /dev/ceph-xxx/osd-block-yyy
dd if=/dev/ceph-xxx/osd-block-yyy bs=4096 count=1 2>/dev/null | hexdump -C | head -5

24-3 Compact encodings: varint, lowz and lba#

Before going to the structures, you need to know three encodings defined in include/denc.h and used everywhere in BlueStore metadata:

Step-by-step lowz example for 0x10000: this number has 16 trailing zero bits, that is 4 nibbles, but the cap is 3. So 0x10000 >> 12 = 0x10 and (0x10 << 2) | 3 = 0x43, which fits in one byte.

lba example for 0x12340000: this number has 18 trailing zero bits, that is 4 full nibbles. So t = 4 − 3 = 1, and the "remove 16 bits" mode with prefix 01 is chosen: 0x12340000 >> 16 = 0x1234 and word = 0b01 | (0x1234 << 2) = 0x48D1. The output is four little-endian bytes: d1 48 00 00. We computed these values with an independent Python implementation based on the logic of denc.h.

24-4 BlueFS: a file system for RocksDB#

RocksDB needs a file system (SST, WAL, MANIFEST and CURRENT files). Instead of ext4 or XFS, BlueStore has its own small file system, BlueFS, connected to RocksDB through BlueRocksEnv. BlueFS implements only what RocksDB needs: a few flat directories, append-only files, rename, unlink and fsync.

24-4-1 Structures#

pseudocode: BlueFS mount (this book's summary)
  super = decode(read(bdev[DB or SLOW], 0x1000, 4096)); verify crc
  log_reader = open(super.log_fnode)
  pos = 0
  repeat:
      read header at pos; if uuid != super.uuid or seq != expected → end of log
      t = decode(bluefs_transaction_t); verify crc
      for op in t.op_bl:
          INIT        → nothing
          DIR_CREATE  → dir_map[name] = {}
          DIR_LINK    → dir_map[d][f] = ino
          FILE_UPDATE → file_map[ino].fnode = fnode
          FILE_UPDATE_INC → merge extents into file_map[ino].fnode
          FILE_REMOVE → release extents (unless shared)
          JUMP/JUMP_SEQ → pos/seq = ...
      pos = next block-aligned boundary
  # at the end, each bdev's allocator is built from the extents of all fnodes

24-4-2 Log compaction and envelope mode#

_should_start_compact_log_L_N() compares the current log size with _estimate_log_size_N(). If both conditions in the table above hold, _compact_log_async_LD_LNF_D() runs: a complete image of the metadata (all directories and fnodes) is written into a new log, the superblock is updated with the new log_fnode and a higher seq, and the old log's extents are freed. The order of these steps is such that a crash at any moment leaves either the old log intact or the new log complete.

ceph-bluestore-tool bluefs-bdev-sizes --path /var/lib/ceph/osd/ceph-4      # OSD stopped
ceph-bluestore-tool bluefs-log-dump --path /var/lib/ceph/osd/ceph-4
ceph daemon osd.4 bluefs stats                         # admin socket on the OSD host
ceph-bluestore-tool bluefs-export --path ... --out-dir /tmp/bluefs   # RocksDB files for ldb

24-5 The full map of KV prefixes#

All of BlueStore's metadata lives in RocksDB. The first character of each key is its "prefix", defined in BlueStore.cc:

24-6 The onode: from key to extent#

24-6-1 The object key#

The key is built so that a sequential RocksDB scan gives exactly the order of a PG's objects. So collection_list (used in scrub and backfill) becomes a simple range scan:

24-6-2 bluestore_onode_t#

The main fields: nid (a local numeric ID for omap keys), size, attrs (xattrs such as _ for object_info_t and snapset), extent_map_shards (a list of {offset, bytes}), expected_object_size, expected_write_size, alloc_hint_flags, segment_size and flags (FLAG_OMAP=1, FLAG_PGMETA_OMAP=2, FLAG_PERPOOL_OMAP=4, FLAG_PERPG_OMAP=8). If extent_map_shards is empty, the whole extent map is stored inline after the onode in the same value.

24-6-3 The extent map and its compact encoding#

Each lextent has four numbers: logical_offset, length, blob_offset and a reference to a blob. ExtentMap::encode_some avoids repeating information with four flags in the low bits of the blobid:

The remaining bits (after BLOBID_SHIFT_BITS = 4) are the blob ID. If the blob is local and appears for the first time in this shard, zero is written as the ID and the decoder infers it from its own counter.

Numerical example: an RBD image with a 4M object that has received two consecutive 64K writes at offsets 0 and 0x10000, each in a new blob:

After each lextent, if the blob is new, the blob itself is also encoded: flags, pextents (about 5 bytes each) and the checksum array. For a 64K blob with crc32c and a 4K chunk, the checksum array is 16 × 4 = 64 bytes. So checksums are the dominant part of an onode's size, not the addresses. With bluestore_csum_type=crc32c_16 this volume is halved.

24-6-4 Shared blobs and clones#

When rbd snap or clone_range shares a blob between two onodes, the FLAG_SHARED flag is set on the blob and it gets an sbid. The reference counts of its physical extents (bluestore_extent_ref_map_t: offset → {length, refs}) are stored under key X + sbid. Deleting one of the clones only decrements refs. The physical space is freed when refs reaches zero.

24-7 Deferred writes on disk#

For writes smaller than bluestore_prefer_deferred_size (64K on HDD), BlueStore first writes the data into RocksDB together with the metadata transaction. Its structure:

pseudocode: the deferred cycle (this book's summary)
  txc: kv.set("L" + seq, encode(deferred_txn)); kv.submit_sync()     # RocksDB's WAL = durability
  ack → client
  deferred_queue: gather until bluestore_deferred_batch_ops or throttle pressure (128M)
  _deferred_submit: aio_write(extents, data) on the main device (no separate fsync)
  _deferred_aio_finish → in the next txc: kv.rmkey("L" + seq)     # after the device flush
  mount after a crash: _deferred_replay() rewrites all L* to disk (idempotent)

24-8 The allocator: who knows the free space?#

24-8-1 The fragmentation score#

Allocator::get_fragmentation_score() returns a number between 0 (one contiguous piece) and 1 (all free space in single-block pieces). The idea is that a 2X-byte piece is more valuable than two X-byte pieces. For pieces smaller than 1M, each doubling of length gets 1.2 times the weight; this factor falls linearly to 1 by 128M and stays constant above that. The score is computed like this:

score(len) ≈ an increasing convex function (linear interpolation between 2^k and 2^(k+1) with the factors above)
ideal    = score(sum)                          # all free space in one piece
terrible = (sum / block_size) × score(block_size)
actual   = Σ score(len_i)
fragmentation = (ideal − actual) / (ideal − terrible)

ceph daemon osd.4 bluestore allocator score block       # {"fragmentation_rating": 0.27...}
ceph daemon osd.4 bluestore allocator fragmentation histogram block
ceph-bluestore-tool free-score --path /var/lib/ceph/osd/ceph-4    # OSD stopped

24-8-2 The freelist and freelist-less mode#

In BitmapFreelistManager, bytes_per_block equals the allocation unit (min_alloc_size) and blocks_per_key = bluestore_freelist_blocks_per_key = 128. So each b key, with a 16-byte value, covers 128 units (with a 4K unit, 512K of disk). Allocation and release are both an XOR with a mask (XorMergeOperator named bitwise_xor). So without reading the previous value, only one merge is sent to RocksDB.

The bluestore_allocation_from_file option has existed since Quincy (it is not in Pacific), and on main its default is true. In this mode the freelist update is removed from the write path, and on a clean umount BlueStore writes the allocator map into the file ALLOCATOR_NCB_DIR/ALLOCATOR_NCB_FILE inside BlueFS. If the shutdown is not clean, the next mount scans all onodes with read_allocation_from_onodes to rebuild the used space. This makes transactions lighter, but after a crash it adds several minutes to the mount time of OSDs full of objects.

24-9 The BlueStore cache#

The caches are sharded (each OSD op shard has its own cache) to reduce lock contention. Onodes are pinned with a reference counter. An onode in use by an in-flight transaction is not evicted until the transaction ends, even if the cache is full.

ceph daemon osd.4 perf dump bluestore | jq '.bluestore | {onodes, onode_hits, onode_misses}'
ceph daemon osd.4 dump_mempools | jq '.mempool.by_pool | {o: .bluestore_cache_onode, d: .bluestore_cache_data}'

24-10 Space allocation in numbers#

The free space of BlueStore's main device is kept by the allocator. The default is bluestore_allocator = hybrid: an AVL allocator that hands part of its ranges to a bitmap allocator when needed. This section follows three of its algorithms with numbers.

24-10-1 near-fit and best-fit in AVL#

pseudocode
max_size = the largest range (the end of the size tree)
if max_size < want: want = p2align(max_size, unit) ; force best-fit   # piecewise allocation
free_pct = num_free × 100 / device_size
if force or max_size < bf_threshold (128K) or free_pct < bf_free_pct (4): best-fit
else near-fit:
    align = want & −want ; cursor = lbas[cbits(align) − 1]   # one cursor per power of two
    walk forward from lower_bound(cursor) in the offset tree until offset + want ≤ end
    (at most ff_max_search_count = 100 ranges or ff_max_search_bytes = 16M; then from the start up to cursor)
best-fit: lower_bound({0, want}) in the size tree ⇒ the smallest sufficient range; on a tie, the lower offset

Numerical example. Part of the device has four free ranges: 32K at 0x10000, 128K at 0x40000, 32K at 0x100000 and 1M at 0x200000.

• A 64K request (near-fit): align = 0x10000, so cbits = 17 and cursor = lbas[16] = 0. The first range is too small and the cursor moves to 0x20000. The second range fits: offset = 0x40000 and cursor = 0x50000. The next 64K request continues from 0x50000 with the same cursor, so same-sized allocations land next to each other.
• A 32K request (best-fit): suppose the device is large and free space has dropped below 4%. The size tree has two 32K ranges, and lower_bound with key {0, 32K} returns the one with the lower offset, that is 0x10000. The 1M range stays untouched.

The penalty of near-fit is that it fragments large ranges. best-fit is not slower, but it spreads consecutive allocations apart. That is why it is only enabled when space is low.

24-10-2 The fragmentation score in numbers#

pseudocode
scale[0] = 1 ; scale[k+1] = scale[k] × w(k)    # w = 1.2 up to 2^20, linear to 1.0 at 2^27, then 1.0
score(v): sc = floor(log2 v) ; b = 2^sc ; x = (v − b)/b
          return b·scale[sc]·(1 − x) + 2b·scale[sc+1]·x       # linear interpolation
actual = Σ score(len_i) ; ideal = score(Σ len) ; terrible = (Σ len / block_size) × score(block_size)
rating = (ideal − actual) / (ideal − terrible)

Numerical example (block_size = 4K, 1 GiB free). These numbers were computed with an independent implementation of the same formula:

• One 1G piece, and any piece larger than 128M: score 0.
• 16M pieces: 0.093.
• 1M pieces: 0.498.
• 64K pieces: 0.837.
• 16K pieces: 0.933.
• 4K pieces: 1.
• An 896-megabyte mix (two 256M pieces, 256 1M pieces and 2048 64K pieces): 0.262. Most of the space is in large pieces, so the score stays low even though there are many small pieces.

Because the factor above 128M is 1, pieces larger than 128M carry no penalty. A score above 0.8 on HDD usually means a small min_alloc_size and scattered allocations. In that state, large writes are broken into several extents.

24-10-3 Hybrid overflow to bitmap#

pseudocode
range_count_cap = bluestore_hybrid_alloc_mem_cap (64M) / sizeof(range_seg_t)
insert(start, end):
    if size_tree.size < cap: insert into the AVL
    elif end − start > the smallest AVL range: insert and move the smallest to bitmap
    else: straight to bitmap
allocate(want):
    primary = AVL, unless bitmap has free space and want < the smallest AVL range ⇒ primary = bitmap
    take from primary ; take the shortfall from the other ; nothing ⇒ ENOSPC

Numerical example. Each range_seg_t has two 64-bit numbers (start and end, 16 bytes together) and two boost::intrusive AVL tree hooks (offset_hook and size_hook). MEMPOOL_CLASS_HELPERS() only defines operator new/delete and adds no data member. Each avl_set_member_hook<> with default parameters (no optimize_size) has three pointers, parent, left and right, and a balance field, which with 8-byte alignment comes to 32 bytes. So sizeof(range_seg_t) = 16 + 32 + 32 = 80 bytes. We checked this number by compiling a small program with the same layout on x86-64 (boost.intrusive headers from the main branch, Clang 22.1 via zig c++ 0.17.1, the C++17 standard): the output was hook = 32, seg = 80, offsetof(size_hook) = 48 and alignof = 8. The 64-megabyte cap (bluestore_hybrid_alloc_mem_cap = 64 MiB = 67108864 bytes) therefore keeps ⌊67108864 / 80⌋ = 838860 ranges in the AVL. The real memory is a bit higher, because the heap allocator's overhead is not in this calculation. On 32-bit architectures or with other boost headers the number may differ.

• A sixteen-terabyte HDD with 30% free space and an average piece of 64K: there are about 4.8T / 64K, that is nearly 73 million ranges. So more than 98% of the ranges, the smallest ones, stay in the bitmap, and the AVL keeps only the largest.
• A 4K allocation: it is smaller than the smallest AVL range, so it is taken directly from the bitmap and the large ranges stay untouched.

24-11 On a real disk: the label and the free space map#

The two figures in this section were taken from the BlueStore OSDs of a test cluster with Ceph 18.2.7. Each OSD's block device was a ten-gigabyte sparse file.

24-11-1 The first 588 bytes of the label#

The bytes were read directly from the block file and compared with the output of ceph-bluestore-tool show-label. This cluster had no cephx, so meta had no osd_key. On a real cluster, remove this field before showing it to anyone.

pseudocode
b = the first 4 KiB of the device
skip the 60 text bytes: "bluestore block device\n" (23) + text uuid + "\n" (37)
struct_v = b[60] ; compat = b[61] ; len = u32le(b[62:66])        # ENCODE_START(2, 1)
osd_uuid = b[66:82] ; size = u64le(b[82:90]) ; btime = (u32 sec, u32 nsec)
description = (u32 len, bytes) ; meta = u32 count then count pairs (u32 len, key)(u32 len, value)
end = 60 + 6 + len ; crc = u32le(b[end:end+4])
valid if crc32c(seed = 0xffffffff, no final xor)(b[0:end]) == crc

Real values.

• Structure header: at offset 0x3c the value 02 01, that is struct_v = 2 and compat = 1, and 06 02 00 00, that is a length of 518. So the body continues up to offset 584.
• size: 00 00 00 80 02 00 00 00 equals 0x280000000, that is 10737418240 bytes.
• btime: sec = 1794712746 and nsec = 393184192, that is 2026-11-15 06:49:06.393 Tehran time.
• description and meta: the description value is "main", and meta has fourteen pairs, including bfm_blocks = 2621440, bfm_bytes_per_block = 4096, kv_backend = rocksdb and magic = ceph osd volume v026.
• crc: the four bytes at offset 0x248 are 0xb012c37d. We recomputed this value with an independent crc32c implementation (the Castagnoli polynomial, seed −1, no final xor). The decoder skips the same 60 bytes with p += 60u.

24-11-2 The allocator's free space map#

The tool used is ceph daemon osd.0 bluestore allocator dump block. This command gives the complete list of free extents. … allocator score block returns the fragmentation_rating. Both were taken for this version's default allocator (hybrid) with a min_alloc_size of 4 KiB. Three moments were recorded:

• A: after deleting the earlier test pools (the 4 KiB and 4 MiB benchmarks). The score was 0.0163.
• B: after writing 6000 64 KiB objects into a single-replica pool. The score was 0.0167.
• C: after randomly deleting 51% of those objects. The score was 0.0215.

What the data shows.

1. 1. 4 KiB holes: even in A, the free space was fragmented into 26235 extents, 23218 of which were only 4 KiB. We did not isolate the exact cause of these holes in this experiment. It probably comes from interleaved placement with live data and metadata.
2. 2. Amount of free space: about 8.5 GiB of free space is almost all in a few large extents of 256 MiB to 2.4 GiB.
3. 3. 64 KiB writes: these writes did not fill the 4 KiB holes, because the allocator wants a contiguous extent for a 64 KiB request. The later random deletion created about 330 new holes of 64 to 512 KiB.
4. 4. Overall score: fragmentation_rating stayed below 0.03 in all three states. This score is byte-weighted (the fragmentation score algorithm in the previous section), and when most free bytes are in large extents, tens of thousands of small holes do not raise it.

So a low score does not mean "we have no small holes". The number of extents affects the allocator's memory and search time. To see it, count the extent list itself.

24-12 Supplementary and up to date#

• Label copies (bdev_label_positions) exist in the code of Squid, Tentacle and main. Envelope mode in BlueFS is only in Tentacle and main, not in Squid. If you have a mixed cluster, do not count on these features on the older OSDs.
• hybrid_btree2 and bluestore_allocator_lookup_policy exist in Squid and later.
• The main branch also has structures for BlueStore's new write path (such as segment_size in the onode and FragMetric in bluestore_common.h), which are part of ongoing work on reducing fragmentation and the new EC. Follow the details in the release notes before the final release.

24-13 Hands-on exercise#

1. 1. On a test OSD, read the device's first 4K with dd. Look at the 60 text bytes, compare the rest with the output of ceph-bluestore-tool show-label, and recompute the crc with the Python function from chapter 23.
2. 2. Write a lowz and an lba function, reproduce the values in this chapter's table, and measure the encoded size for real offsets from the output of ceph-bluestore-tool fsck --deep or dump onode.
3. 3. Write an RBD image with random 4K fio, and count the O keys with an x suffix (shards) before and after with ceph-kvstore-tool.
4. 4. Record bluestore allocator score block daily on several OSDs and compare it with how full they are.
5. 5. Stop an OSD with kill -9, start it again, and measure the time of read_allocation_from_onodes in the log.

24-14 Review questions#

1. 1. What do the label's first 60 bytes contain, and why does the decoder skip them?
2. 2. Why is the BlueFS superblock always at offset 4096?
3. 3. How many bytes does denc_lba use for a 4K-aligned offset, and why?
4. 4. What condition starts BlueFS log compaction?
5. 5. Why is the hash in the onode key bit-reversed?
6. 6. What savings do the BLOBID flags in the extent map create?
7. 7. Why is the checksum the largest part of an encoded blob?
8. 8. How does the hybrid allocator limit memory use?
9. 9. Why does the freelist use merge with XOR?
10. 10. What problem of LRU does the 2Q algorithm solve?

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

24-15 Sources for this chapter#

• BlueStore types
  https://github.com/ceph/ceph/blob/main/src/os/bluestore/bluestore_types.h
• BlueFS types
  https://github.com/ceph/ceph/blob/main/src/os/bluestore/bluefs_types.h
• denc encoding
  https://github.com/ceph/ceph/blob/main/src/include/denc.h
• Fragmentation score
  https://github.com/ceph/ceph/blob/main/src/os/bluestore/Allocator.cc
• BitmapFreelistManager
  https://github.com/ceph/ceph/blob/main/src/os/bluestore/BitmapFreelistManager.cc
• BlueStore configuration
  https://docs.ceph.com/en/latest/rados/configuration/bluestore-config-ref/
• ceph-bluestore-tool
  https://docs.ceph.com/en/latest/man/8/ceph-bluestore-tool/
• The BlueStore paper (SOSP 2019
  https://www.pdl.cmu.edu/PDL-FTP/Storage/ceph-exp-sosp19.pdf
• 2Q (Johnson and Shasha, VLDB 1994
  https://www.vldb.org/conf/1994/P439.PDF