Computed examples / not database measurements

Key-value separation: cleaning-cost sensitivity

Thirty deterministic byte-accounting cases compare inline records with separated values, including relocation-driven index writes. Invented inputs, not engine measurements.

JSON and provenance / Evaluator code / Research explanation

Method

For equal-sized records, K=16 key bytes, P=16 reference bytes, H=8 log-header bytes; V in {16,128,1024} bytes; C in {4,10} tree output/input-byte factors; selected-region live fraction u in {0,0.25,0.5,0.75,0.9}. Inline=C(K+V); separated=[C(K+P)+K+V+H]/(1-u). Every relocated record induces an index update charged at C. Each ratio uses K+V new logical bytes as denominator. Original steady-state accounting example, not a fit to a paper.

Cleaning S bytes moves uS live bytes but makes only (1-u)S net space. The append-plus-relocation multiplier is 1/(1-u). We apply it to both log records and their index updates. A separate index and value log are the modeled layout, not a claim that every implementation has this exact cost.

Interpretation

Below 1 in the final column means fewer modeled writes, not higher throughput. Above 1 means the separated layout loses this byte comparison. The break-even live fraction in JSON is specific to selected cleaning regions; it is not a drive-capacity threshold. Null, serialized as an empty CSV cell, means no crossover for nonnegative live fractions.

Reproduce

The standalone JavaScript module requires Node.js and no packages. It rejects non-finite values, byte sizes outside 1-1,000,000,000 (headers may be zero), C outside 1-1,000,000, and live fractions outside [0,1). The JSON includes full-precision rows, runtime and SHA-256 hashes of code and CSV.

node --input-type=module -e 'import { toCsv } from "./kv-cleaning.mjs"; process.stdout.write(toCsv())'

Limits

• All inputs are invented and fixed; no devices, traces or database engines were measured.
• Assumes steady-state cleaning with equal record sizes and a fixed live fraction of selected regions.
• Identical C for inline, separated and relocation-driven tree updates isolates layout; a real smaller index can have a different C.
• No WAL, reads, compression, caching, coalescing, metadata beyond H/P, alignment, latency or NAND writes.
• Charging an index update for every relocation does not represent compaction-integrated BlobDB reclamation.
• u=1 cannot reclaim net space and is rejected; u is not storage utilization or a fill-limit recommendation.
• No statistical confidence intervals apply to these deterministic cases; applicability remains uncertain.

Column definitions

keyBytes

Assumed key size, bytes.

valueBytes

Assumed value size, bytes.

pointerBytes

Assumed reference size in the separated tree, bytes.

logHeaderBytes

Assumed extra log header size, bytes.

treeWriteFactor

Tree output bytes per inserted tree-record byte, including initial table writes and rewrites; same for both layouts.

liveFraction

Live-byte fraction of the selected cleaning regions, not whole-database utilization.

logicalBytes

New logical input bytes per key-value insertion: keyBytes + valueBytes.

relocationFactor

Total append-plus-relocation multiplier: 1/(1-liveFraction).

inlineBytes

Modeled tree bytes written per new logical insertion in the inline layout.

separatedTreeBytes

Modeled tree bytes per new insertion including pointer updates for relocated records.

valueLogBytes

Modeled log bytes per new insertion including all repeated copies and headers.

separatedBytes

Separated tree plus log bytes per new insertion; excludes WAL and lower-layer writes.

inlineWriteRatio

inlineBytes / logicalBytes, modeled byte ratio.

separatedWriteRatio

separatedBytes / logicalBytes, modeled byte ratio.

separatedToInline

separatedBytes / inlineBytes; below 1 means fewer modeled writes.

breakEvenLiveFraction

Selected-region live fraction at equal cost; null/empty CSV means no nonnegative crossover (separation loses even at zero live bytes).

Sources and license

CC0-1.0 for Hesela's original code and computed rows. Source papers and documentation retain their own rights.

1. Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau and Remzi H. Arpaci-Dusseau. WiscKey: Separating Keys from Values in SSD-conscious Storage. USENIX FAST 2016, pp. 133-148, sections 3.2-3.3 and 4.
2. Helen H. W. Chan, Yongkun Li, Patrick P. C. Lee and Yinlong Xu. HashKV: Enabling Efficient Updates in KV Storage via Hashing. USENIX ATC 2018, pp. 1007-1019, sections 3-4.
3. RocksDB project. BlobDB: integrated implementation, garbage collection and configuration. Documentation reviewed 12 October 2026; page displays revision date 22 September 2022.

Related concepts: key-value separation, value log and database write amplification.