# The Price of Sorted State: Compaction, Amplification, and Value Separation Codex (AI) | English analytical review | Local draft v1 | 2026-10-25 ## Abstract Compaction maintains sorted state by moving work across time, memory, and storage layers. This analytical review argues that amplification ratios alone are insufficient for choosing an LSM-tree policy because they conceal finite-trace effects, deferred merge debt, filter allocation, and the lifetime distribution of separated values. Six primary sources connect the original LSM structure, WiscKey, Monkey, Dostoevsky, and official RocksDB compaction descriptions. An explicitly constructed model compares geometric rewrite budgets and value-separation accounting without presenting its numbers as measured database performance. A finite tiered simulator is checked against an independent carry-count formula. A second calculation shows how collector occupancy changes the benefit of moving values outside the sorted index. A burst example demonstrates that a sustainable average arrival rate can still leave substantial recovery debt. The review develops counterexamples to unconditional claims about separation and lower amplification, then specifies a comparative protocol with equal memory and durability budgets, workload-controlled lifetime correlation, and complete recovery accounting. The central research question is which combination of read bounds, space headroom, reclamation delay, and foreground latency an engine can actually sustain. Conclusions are conditional on transparent assumptions, and implementation measurements remain proposed rather than fabricated. ## Sorted order is a maintained service An LSM tree sells an apparently simple abstraction: keys remain searchable while updates arrive continuously. The expense is deferred ordering. An insertion can finish before every older run has been reconciled, but the system must eventually perform enough work to keep lookup fanout and occupied storage within its contract. The original LSM paper motivates batching by the disparity between random disk movement and sequential merging. Its historical hardware argument should not be converted directly into a claim about contemporary flash performance. The durable insight is that changing when work occurs changes which resource pays for it. This review argues that compaction policy should be evaluated as a budget allocation across time, not merely as a steady-state amplification ratio. A low ratio can coexist with unacceptable stalls if work is concentrated; a higher ratio can be acceptable if it buys predictable reads and short reclamation delay. The proposed analysis therefore tracks rewrite volume, deferred debt, filter allocation, and value lifetime separately. These are distinct accounting dimensions even when a single background scheduler handles them. No database engine is benchmarked here. The accompanying calculations make explicit which conclusions follow from arithmetic and which require measurements of an implementation. Sources: cs2-01-1 ## What amplification actually counts Write amplification needs a numerator and a denominator before it can support a comparison. Logical bytes may mean user payload alone, serialized key-value entries, or bytes accepted after duplicate elimination. Physical bytes may stop at the storage-engine boundary or include the filesystem and device controller. Two ratios with different boundaries cannot be ranked meaningfully. This manuscript defines its constructed ratio as engine data bytes written divided by original key-plus-value bytes, excluding logging, compression, filesystem metadata, and device-internal movement. The RocksDB compaction taxonomy distinguishes classic leveling, tiering, and hybrids. It also explains that merging only overlapping files can differ from merging entire levels, especially with ordered or skewed updates. That is evidence against treating a fanout formula as an invariant of every engine. Here the formula is deliberately a rewrite budget, suitable for sensitivity analysis. A real experiment must separately report flush writes, merge writes, value-log collection, and elapsed foreground service. Otherwise an optimization can appear successful by moving cost outside the counter being watched. Read amplification deserves the same discipline: candidate runs, actual block reads, and cache misses are different quantities with different consequences for tail latency. Sources: cs2-01-5 ## Geometry produces a staircase Consider a database-to-buffer size ratio of 4096 and a geometric size ratio T between adjacent levels. The model chooses the smallest integer L for which T raised to L can cover that ratio. This is a capacity simplification, not an exact sum of every level capacity. It makes an easily missed discontinuity visible: increasing T changes both the work paid per merge and the number of levels that exist. Treating L as a smooth logarithm can hide abrupt transitions near capacity boundaries. For T equal to 8, the model has four levels and assigns a leveled budget of 33 writes per logical entry, including the original flush. Its tiered asymptotic budget is five. Figure one displays this deliberately coarse comparison across several ratios. These quantities cannot establish that tiering is universally faster: they omit reads, space occupancy, obsolete versions, and scheduling. They do show why tuning a fanout in isolation is insufficient. A proposal that changes T should state whether memory, database size, filter budget, and terminal-level occupancy remain constant. If one changes unnoticed, an apparent policy effect may instead be a change in the geometry of the workload. Author analysis or proposed verification. ## Finite merging is not the asymptote An executable carry model provides a more precise reference for tiered merging over a finite insertion trace. Each flush creates one unit run. When T runs of a size accumulate, they merge into one run T times larger. Counting written entries directly gives a total that can also be computed by summing complete carries at each size. The supplied checks compare these two implementations across 396 combinations of insertion length and radix, rather than checking the same expression twice. For 64 inserted units with T equal to 4, direct simulation writes 256 units in total. That includes 64 original writes and three complete generations of merging. A trace ending at 63 units has a different residual arrangement, so its observed ratio need not equal the full-cycle ratio. This matters when measuring a freshly loaded database. Stopping immediately after ingestion can leave unpaid merge work, while forcing complete compaction can create a state unlike normal service. A fair comparison should report both the state at admission completion and the eventual work required to reach a declared steady or quiescent condition. The stopping rule is part of the experiment, not a plotting convenience. Author analysis or proposed verification. ## Filters allocate avoided reads Monkey addresses a different budget: memory spent to avoid unnecessary probes of runs. Its central allocation insight is that negative-lookup I/O depends on the sum of run false-positive probabilities, so equal bits per entry across differently sized runs need not minimize that sum. The result is conditional on a defined access and cost model. This review uses the insight to separate filter policy from merge policy rather than claiming that a particular allocation is universally optimal. For an independent analytical approximation, let a run with n entries receive m filter bits and use the usual exponential false-positive approximation. A small run can obtain a large reduction in its false-positive rate from a comparatively small allocation. But the correct objective changes if most queries are successful, if lower-level blocks already reside in cache, or if a tenant accesses only a narrow key interval. In those cases a weighted sum of expected probe costs is more relevant than an unweighted sum. The proposed evaluation should therefore publish positive and negative lookup proportions and the physical cost of a failed probe. Without those observations, filter improvements and compaction improvements are easily confounded. Sources: cs2-01-3 ## Upper and terminal levels do different jobs Dostoevsky questions whether every level should pay equally aggressive merge costs. Its lazy-leveling design reduces merging above the largest level while preserving specified bounds on important lookup and space quantities. The paper also introduces a broader configurable design space. The relevant contribution here is the distinction between reducing the number of candidate runs and removing a large mass of obsolete data; those objectives are related but need not have identical marginal value at every level. The article does not import the paper's performance claims into the constructed figures. Instead, it proposes recording each merge's purpose: preventing a run-count limit, reclaiming obsolete bytes, satisfying an age constraint, or making room for incoming data. This classification can reveal whether a policy is spending bandwidth on an objective that is currently unimportant. It also exposes a tension with fairness. A large tenant whose files repeatedly trigger emergency work can consume capacity needed to maintain another tenant's read bound. A useful adaptive policy therefore needs both a global resource budget and a rule for distributing debt. An aggregate throughput improvement alone does not establish that all tenants retain their service contracts. Sources: cs2-01-4 ## Separating values changes the accounting WiscKey provides primary evidence for separating the sorted key index from the value storage. Its original abstract describes an SSD-oriented design intended to reduce I/O amplification. This review does not reproduce the paper's benchmarks or infer current product performance from them. The accompanying example asks a narrower question: how large must values become before avoiding their repeated sorted-index movement compensates for pointers and collection? Assume a 16-byte key, an 8-byte pointer, and the earlier index rewrite factor of 33. Inline storage rewrites both key and value. Separated storage rewrites the key and pointer, writes the value once, and pays an idealized recycling cost determined by the live fraction of collected segments. With a 1024-byte value and live fraction 0.2, the constructed physical-to-logical ratio is 1.9923076923 rather than 33. If the collected segments are 0.8 live, it rises to 5.6846153846. Figure two exposes this sensitivity. These are accounting results under fixed assumptions, not measurements of WiscKey or BlobDB. Pointer repair, concurrent snapshots, compression, and actual collection selection can all change the comparison. Sources: cs2-01-2 ## A counterexample to inevitable separation gains The separated layout does not win simply because a value log exists. If values are tiny, the additional pointer may dominate the bytes saved. If segments remain almost entirely live, collection can repeatedly copy useful values while reclaiming little space. Algebraically, the assumed benefit requires the value size multiplied by the difference between the inline rewrite factor and the collection multiplier to exceed the pointer size multiplied by the index rewrite factor. A nonpositive difference makes that condition impossible for any positive value size. This is a counterexample to the claim that key-value separation always reduces writes. It is not an argument against separation in general. It identifies the missing workload variable: the lifetime distribution of values within the segments chosen for collection. Two workloads with identical mean value size and update rate can have different collection costs if one mixes cold and hot values while the other segregates them. A credible experiment should vary lifetime correlation independently from the marginal update frequency. It should also retain long-lived snapshots in some trials, because obsolete logical versions may remain physically necessary. Reclamation policy is therefore a consistency-sensitive storage decision, not merely a background compression pass. Author analysis or proposed verification. ## Deferred work becomes an admission constraint Average bandwidth feasibility is necessary but insufficient when arrivals are bursty. The model keeps a debt balance measured in megabytes of pending engine writes. During each one-second interval it adds incoming logical bytes multiplied by the assumed amplification and subtracts the available physical write service, clipping the balance at zero. This abstraction omits scheduling and read interference, but it makes the accumulation mechanism inspectable. With amplification 33 and service capacity 40 MB per second, ten seconds of arrivals at 3 logical MB per second create 590 MB of debt. Returning to 1 logical MB per second leaves only 7 MB per second for recovery. After thirty additional seconds the debt remains 380 MB. Thus a rate that is sustainable indefinitely from an empty queue can recover very slowly from a brief overload. A foreground benchmark that ends before recovery measures only one part of the transaction between present latency and future work. Admission control should react to debt and available storage headroom, not merely the current incoming rate. The operational question is whether the system can survive the entire recovery interval without violating read, space, or durability requirements. Author analysis or proposed verification. ## Reclamation and read bounds can conflict The official leveled-compaction documentation distinguishes overlapping L0 files from the sorted lower levels and describes extra work intended to reduce L0 read amplification or reclaim aged data. These mechanisms illustrate why background activity cannot be judged only by total write volume. Spending an extra rewrite can preserve a read bound; postponing a rewrite can keep foreground throughput high while leaving stale data resident. A proposed service contract should state at least three independent limits: how many candidate runs a read may inspect, how much space can remain tied to obsolete versions, and how long a deletion can remain unreclaimed under the stated snapshot policy. None follows automatically from the other two. A mostly read-only range can retain old physical bytes despite low write pressure, while an aggressively compacted hot range can consume the shared write budget. For evaluation, file ages and obsolete-byte estimates should be sampled over time, not only at the end. A compact final image can conceal long intermediate periods of high space usage. Conversely, a temporarily large image may be harmless when headroom is explicitly budgeted and reclamation completes before a declared deadline. Sources: cs2-01-6 ## A falsifiable comparative experiment The primary hypothesis is that a policy chosen from average amplification alone will mis-rank some workloads when burst recovery, value lifetime, and negative lookup frequency vary independently. To test it, hold the engine version, key serialization, memory limit, compression policy, and durability mode fixed. Generate reproducible traces crossing those three workload dimensions. Preload to a declared occupancy, warm the intended cache state, and then run long enough to observe multiple terminal-level merge or collection cycles. Record foreground latency distributions, bytes admitted, engine writes by category, physical-device writes where available, pending work, and free space on a common timeline. Compare policies at equal resource budgets and include recovery after the offered load falls. Report failed or stalled runs rather than omitting them. A stronger result would identify a workload region where the more expensive steady-state policy wins on a preregistered recovery or tail-latency constraint. A null result is also informative if the traces actually exercise the hypothesized pressure. Without a measured resource bottleneck, similar throughput cannot distinguish genuinely equivalent policies from a benchmark whose limiting component lies elsewhere. Author analysis or proposed verification. ## What the analytical checks establish The model checks establish a finite tiered accounting identity, a value-separation break-even condition, and monotonic collection cost under fixed live fractions. They do not establish an implementation's complexity bound, crash safety, or performance. In particular, the leveled curve is not validated by the tiered simulator: it remains an explicitly declared budget approximation. This distinction prevents a small correct program from lending undeserved authority to a larger system claim. Several extensions would be useful before applying the model to a deployment. Variable record sizes require byte-based triggers rather than entry counts. Compression makes movement cost dependent on key locality and version content. Shared storage introduces read-write interference, while multiple column families make scheduling a fairness problem. Device endurance requires a boundary beyond engine writes. Finally, retained snapshots and recovery logs couple storage policy to correctness. A study that excludes these dimensions can still answer a focused question, but it must state the excluded contract. The intended contribution is a reproducible way to reason about which costs have merely moved, which have genuinely disappeared, and which will return after the headline benchmark ends. Author analysis or proposed verification. ## Mathematical model L=\min\{\ell\in\mathbb{N}:T^\ell\ge N/M\} N and M are database and buffer bytes; T is dimensionless size ratio. This capacity proxy ignores the sum of smaller levels. W_{\mathrm{lev}}=1+TL,\qquad W_{\mathrm{tier}}=1+L Dimensionless illustrative rewrite budgets; initial flush is included. They are not exact implementation formulas. W_{\mathrm{sep}}=\frac{(k+p)A+v/(1-u)}{k+v} k, p, v are key, pointer and value bytes; A is index rewrite factor; u is the collector live fraction, 0<=u<1. No pointer-repair cost is included. v\left(A-\frac{1}{1-u}\right)>pA Necessary and sufficient separation benefit within the declared byte model, compared with inline factor A. D_{t+1}=\max\{0,D_t+\lambda_t W\Delta t-\mu\Delta t\} D is pending engine-write MB; lambda is logical MB/s; mu is physical MB/s; time steps are one second in the example. f_i\simeq\exp\left[-(\ln 2)^2m_i/n_i\right],\quad R_-\simeq\sum_i f_i Approximate optimally hashed Bloom false-positive rate for m_i bits and n_i entries; R_- counts expected candidate reads for a negative query under equal probe costs. ## Figure 1: Explicit rewrite-budget approximation Fixed database-to-buffer ratio 4096; staircase levels. Budgets are illustrative, not RocksDB predictions. Assumptions: All records equal size; No compression, WAL, or cache effects; Full capacity levels Data: figures/lsm-compaction-budgets-1.csv ## Figure 2: Value size and collector occupancy Key 16 bytes, pointer 8 bytes, index rewrite factor 33; steady recycling factor 1/(1-u). Assumptions: Collector live fraction fixed independently of key distribution; Initial value append included; No pointer repair writes Data: figures/lsm-compaction-budgets-2.csv ## Executed finite checks { "levels_T8": 4, "inline_factor": 33, "separated_1024_live_02": 1.9923076923076923, "separated_1024_live_08": 5.684615384615386, "peak_debt_MB": 590, "debt_after_40s_MB": 380, "tiered_64_T4_bytes": 256 } ## Comparison Quantity | Constructed setting | Interpretation Geometry | N/M=4096, T=8, L=4 | Capacity proxy Inline rewrite factor | 33 | Engine-data budget Separated factor, u=0.2 | 1.9923076923 | 1024-byte value Separated factor, u=0.8 | 5.6846153846 | Collection sensitivity Debt after 40 seconds | 380 MB | Burst recovery still incomplete ## Proposed validation protocol - Pin engine revision, storage hardware and complete durability settings. - Fix logical byte definition and enumerate physical-write counters. - Generate independent value-size, lifetime-correlation and lookup-mix factors. - Preload equal logical datasets to declared capacity and cache states. - Run each policy with identical memory and write-bandwidth budgets. - Include steady load, ten-second bursts and complete recovery intervals. - Collect latency, debt, run counts, free space and reclamation ages on one clock. - Separate engine, filesystem and device amplification in the report. - Repeat trace seeds and report stalls and incomplete runs. - Reject any ranking that violates the preregistered read, space or recovery contract. ## Limitations - The leveled curve is an illustrative budget, not a discrete leveled-engine simulation. - Collection assumes a stationary live fraction and omits pointer repairs. - Compression, WAL and device-internal writes are outside the numerical boundary. - Finite tiered tests cover bounded traces, not all possible implementations. - No concurrency, shared-cache or snapshot-pressure benchmark was run. - Mutable official documentation is accessed evidence, not a pinned engine build. ## Open research questions - Can debt-aware admission outperform amplification-only tuning under equal tail-latency targets? - How much does hot-cold lifetime segregation shift the value-separation break-even point? - Which filter allocations remain beneficial when negative-probe costs are strongly unequal? ## Evidence and boundaries cs2-01-1: The structure batches updates through memory and disk components while preserving lookup access. Boundary: Historical disk-arm cost motivation does not predict present SSD latency. Locator: Abstract and Section 1 cs2-01-2: WiscKey separates keys and values to reduce I/O amplification in an SSD-oriented design. Boundary: Abstract performance results are historical; this manuscript does not reproduce or generalize them. Locator: USENIX abstract and BibTeX cs2-01-3: Filter memory can be distributed across runs to minimize the sum of false-positive probabilities. Boundary: Optimality belongs to the specified analytical design space, not all workloads or filter implementations. Locator: Abstract; introduction and filter-allocation discussion cs2-01-4: Lazy leveling reduces upper-level merging while retaining particular lookup and space bounds in its model. Boundary: The manuscript does not independently audit the paper proofs or reproduce its RocksDB experiments. Locator: Abstract and Section 1 cs2-01-5: Implementation compaction taxonomy includes partial-overlap merging and workload-dependent amplification. Boundary: Mutable documentation is not a pinned implementation benchmark. Locator: Overview of Compaction algorithms; Classic Leveled; Tiered cs2-01-6: L0 differs from sorted lower levels, and additional compaction can trade writes for read or reclamation behavior. Boundary: Option defaults and current implementation must be pinned for an actual experiment. Locator: Structure of the files; Intra-L0 Compaction; TTL ## References cs2-01-1. Patrick O’Neil, Edward Cheng, Dieter Gawlick, Elizabeth O’Neil. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica (1996). https://www.cs.umb.edu/~poneil/lsmtree.pdf Access: Original author-hosted PDF, abstract and introductory description of deferred batched merging. cs2-01-2. Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. WiscKey: Separating Keys from Values in SSD-conscious Storage. USENIX FAST (2016). https://www.usenix.org/conference/fast16/technical-sessions/presentation/lu Access: USENIX original abstract and complete conference bibliography. cs2-01-3. Niv Dayan, Manos Athanassoulis, Stratos Idreos. Monkey: Optimal Navigable Key-Value Store. ACM SIGMOD (2017). https://nivdayan.github.io/monkeykeyvaluestore.pdf Access: Author-hosted original PDF abstract and introduction; indexed allocation discussion also inspected. cs2-01-4. Niv Dayan, Stratos Idreos. Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging. ACM SIGMOD (2018). https://nivdayan.github.io/dostoevsky.pdf Access: Author-hosted original PDF abstract, introduction and stated lazy-leveling trade-off. cs2-01-5. RocksDB contributors. Compaction. RocksDB Wiki (2023). https://github.com/facebook/rocksdb/wiki/Compaction Access: Official wiki taxonomy, classic leveled, tiered, hybrid and options passages; page shows 2023 edit date. cs2-01-6. RocksDB contributors. Leveled Compaction. RocksDB Wiki (2023). https://github.com/facebook/rocksdb/wiki/Leveled-Compaction Access: Official wiki structure, Intra-L0 Compaction, TTL and periodic-compaction passages; page shows 2023 edit date. ## Provenance Focused technical synthesis of six inspected primary records and selected paper or documentation passages; not an exhaustive systematic review or proof audit. Written by Codex (AI), with source-based technical synthesis and explicit author-constructed models. Reproducible analytical illustrations, not measured system benchmarks. Codex team technical checks; no independent human or journal peer review.