Key-value separation: the cleaning bill moves elsewhere

Sort references, clean values

WiscKey keeps keys and value addresses in the tree, with records in an appended value log. Its collector reads the tail, checks record liveness against the index, moves survivors and updates their addresses. The log also carries keys and length fields: it is not pure value payload. Range scans fetch separated values with parallel prefetching. [1, sections 3.2-3.3]

That is a different optimization from avoiding unnecessary lookup probes. It changes the bytes moved when maintaining the index. Logical deletion remains separate from physical reclamation.

The benchmark qualification worth reading

HashKV groups values by hashing their keys so cleaning can operate within a group without per-record LSM validity lookups. It also studies hot/cold separation and keeping small values inline. [2, section 3]

Its comparison uses the authors' own WiscKey-inspired vLog implementation. The default testbed uses six SSDs in RAID 0, asynchronous writes and a 64 MiB write cache; crash consistency, hotness awareness and selective separation are disabled unless under evaluation. Experiment 8 separately examines crash-consistency overhead. [2, sections 4.1 and 4.2]

Our interpretation: a throughput ranking from that default setup is not a ranking of equally durable services. Match acknowledgement rules and recovery guarantees before transferring the result. This does not invalidate the paper; it identifies what the experiment measures.

An explicit cleaning budget

The following is our deliberately simplified model, not a measured WiscKey, HashKV or RocksDB configuration. All records have a key of K bytes and a value of V bytes. A tree reference uses P bytes, and a log record adds H header bytes. Let C be total tree bytes written per byte inserted into that tree, including its initial sorted-table write and later rewrites.

A selected cleaning region of S bytes contains a live fractionu. Copying its survivors costs uS bytes and frees only (1-u)S net space. Per new log byte, relocation therefore costs u/(1-u) bytes. Including the original append gives1/(1-u). This is a steady-state flow assumption with a fixed survivor fraction, not a model of how a real collector selects regions.

We additionally charge the same tree-write factor for every relocated record's new pointer. Leaving that out would hide some of the cost of moving live values. The two counterfactual layouts use the same C to isolate record size.

Both numerators count modeled engine writes per new logical key-value insertion. Divide by K+V for a byte-write ratio. No WAL, filesystem metadata, reads, compression, cache effects, alignment or NAND program operations are included. This is therefore neither end-to-end write amplification nor a speed prediction.

The saving can change sign

With a 1024-byte value, separation stops saving modeled writes when the selected region's live fraction reaches 86.85%. This threshold follows algebraically from the displayed equations. It is not a recommended disk-fill limit. With a 16-byte value, separation is already more expensive at u=0 under these inputs.

The critical denominator is reclaimed space, not scanned space. Whole-database occupancy cannot be substituted for u: two equally full databases may offer very different cleaning victims. The same warning applies when reasoning about SSD over-provisioning, but the two collectors operate at different layers.

All 30 cases, CSV, provenance JSON and executable model. No benchmark was run and no statistical confidence interval applies to these deterministic examples.

Do not treat every separated layout as WiscKey

RocksDB's integrated BlobDB writes immutable, key-sorted blob files during flush or compaction. Its min_blob_size threshold leaves smaller values inline; garbage collection is integrated with compaction. References can then be updated as entries are encountered, without extra LSM operations. Our per-relocation pointer-update charge does not describe that mechanism. The documentation distinguishes this implementation from legacy BlobDB.[3]

For an implementation comparison, report foreground and cleaning writes separately, value-size distribution, selected-victim liveness, free-space budget, scan mix, latency tails and recovery settings. Include a sustained update phase: a load-only run may never incur the cleaning bill being investigated.

WiscKey's collector persists copied records and the new index/tail state before reclaiming old space. That ordering matters independently of byte counts. Our evaluator contains no crash recovery or persistence protocol.[1, section 3.3.2]

Corpus: key-value separation, value log, database write amplification.

Primary sources and limits

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.

Reviewed 12 October 2026. Original model and computed rows: CC0. Papers retain their own rights. No paper performance result was reproduced.