The Value of Adaptivity in LSM Bloom-Filter Tuning: A Log-Law and a Two-Clock Frontier Madhulatha Mandarapu∗
Sandeep Kunkunuru†
arXiv:2606.18138v1 [cs.DB] 16 Jun 2026
VaidhyaMegha Private Limited, India https://samyama.ai/ June 2026
Abstract Log-structured merge (LSM) trees attach an approximate-membership filter to every run and must split a fixed memory budget across them. The static optimum is known (Monkey); a large systems literature then makes the allocation adaptive, tracking shifting hotness online. We ask a prior question: when is that adaptivity worth its machinery? We give three analytical answers and validate them on synthetic sweeps, real Twitter production cache traces, and a real RocksDB engine. First, a log-law: optimal bits-per-key is affine in the logarithm of access frequency, at a fixed slope. Second, a robustness law: because the workload enters only logarithmically, the excess read cost from a hotness misestimate is half the size-weighted variance of the log error, and a common-factor misestimate is absorbed by the budget multiplier—so coarse estimates lose little. Third, an adaptivity-value frontier: since compaction rebuilds filters for free on its own clock, the value of continuous tracking over an allocation recomputed only at compaction grows quadratically in the within-epoch drift, with a closed-form scale. This yields a three-regime policy— coarse-at-compaction suffices, then track, then at extreme drift fall back to uniform—and predicts that more skew makes fine tracking matter less. On a real cluster, reallocating only at compaction captures 96–99% of tracking’s benefit; on RocksDB the false-positive primitive holds within four percent to eight bits per key. The contribution is a characterization of when adaptive tuning pays; we add no new filter and no engine fork. Code and pre-registration are public.
1
Introduction
An LSM-tree [O’Neil et al., 1996] stores data in a sequence of immutable runs and answers a point lookup by probing runs newest-first. To avoid a disk access on every run for keys that are absent, each run carries an approximate-membership filter—classically a Bloom filter [Bloom, 1970]. A negative lookup wastes one I/O whenever a filter returns a false positive, so the expected wasted I/O is the sum of the filters’ false-positive rates (FPRs), weighted by how often each run is probed. Given a fixed memory budget, how should bits be divided among the filters? The static answer is settled. Monkey [Dayan et al., 2017, 2018] minimizes the weighted sum of FPRs and shows the optimum is non-uniform: larger runs should be allowed a higher FPR. A substantial systems literature then makes the allocation track a changing workload— ElasticBF [Li ∗ †
[email protected] [email protected]
1
et al., 2019] toggles pre-built filter segments in memory by hotness, Mnemosyne [Zhu et al., 2025] drives reallocation from accurate online statistics through flushes and compactions, Endure [Huynh et al., 2022] tunes for worst-case robustness over a workload neighborhood, and learned/activelearning tuners [Yu et al., 2024] fit the configuration to a sampled workload. These works answer how to adapt. We address a question logically upstream of all of them: how much is adaptivity worth, and when? Contributions. We show the optimal allocation has a simple analytic structure with sharp consequences for adaptivity (§2), and we validate each on synthetic sweeps, real Twitter cache traces [Yang et al., 2020], and a real RocksDB engine (§3): 1. The log-law. Optimal bits-per-key is affine in ln(access frequency) with slope 1/ ln2 2 ≈ 2.081 (a re-reading of Monkey’s formula, made explicit). 2. The robustness law. Excess read cost from a hotness misestimate is D/2, with D the sizeweighted variance of the log error; common-factor errors cost nothing. Hence coarse estimates suffice—an analytic explanation for why statistics-driven allocation works. 3. The adaptivity-value frontier. With compaction as a free-rebuild p clock, the value of continuous tracking over compaction-only reallocation is V ≈ 12 (r/r⋆ )2 , r⋆ = 2(Cunif − Corac )/Corac , giving a three-regime policy and the rule that more skew lowers the value of fine tracking. We claim no new filter or system; the novelty is the characterization, stated honestly against a crowded field (§4, §5).
2
Model and theory
Setup. A run i holds Ni keys with a Bloom filter at bi bits/key; an optimally-tuned Bloom filter has FPR fi = e−βbi with β = ln2 2 ≈ 0.4805. Let ai be the probability a negative lookup probes P run i. The expected wasted I/O per negative lookup is C(b) = i ai e−βbi , minimized subject to P i Ni bi ≤ M . Static optimum and the log-law. to [0, 1]), equivalently
The Lagrangian optimum (Monkey) is fi⋆ = λNi /ai (clipped
b⋆i =
1 ln ai − ln Ni − ln λ . β
(1)
The workload enters only through ln ai , with slope 1/β. We call (1) the log-law; it is implicit in Monkey but its consequences for estimation error are not. Robustness law. Suppose hotness is misestimated multiplicatively, âi = κi ai , and we allocate by (1) using â. The budget constraint forces the perturbation ∆bi = (ln κi − ⟨ln κ⟩N )/β, where ⟨·⟩N is the N -weighted mean. A second-order expansion at the convex optimum (Hessian ∂ 2 C/∂b2i = β 2 λNi , and C ⋆ = λN ) gives the relative excess cost ∆C ≈ 12 D, C⋆
D :=
X
Ni N
2
ln κi − ⟨ln κ⟩N .
(2)
i
Two consequences: the penalty is quadratic in the log error—a factor-2 hotness error costs O((ln 2)2 )— and a common-factor error (κi ≡ κ, D = 0) is absorbed entirely by λ. Only differential log-error matters. This is why coarse, slowly-updated hotness estimates lose almost nothing. 2
Adaptivity-value frontier. Now let hotness drift in time. Compaction rewrites runs and thus rebuilds their filters for free on its own clock. Compare two policies at equal budget: oracle reallocates from the true current hotness every step (a lower bound, and the best case for any online tracker); compaction-only recomputes the log-law allocation just at compaction events and freezes it between. Let r be the within-epoch differential log-drift (the square root of the N -weighted variance of ln ai (end) − ln ai (start) over a compaction epoch), and define the value of tracking V = (Ccomp − Corac )/(Cunif − Corac ) ∈ [0, 1], the fraction of the achievable adaptation benefit left on the table by reallocating only at compaction. Applying (2) across an epoch (drift accumulates linearly, time-averaged) gives, to leading order, V ≈
1 2
r r⋆
2
,
⋆
r =
r
2(Cunif −Corac ) . Corac
(3)
Three regimes follow. For r ≲ 0.34 r⋆ compaction-only keeps ≥ 90% of the benefit at zero extra write cost; in a middle band online tracking progressively pays; and at extreme drift (r ≳ 4r⋆ ) a stale concentrated allocation is worse than uniform (V > 1), so the robust fallback is uniform bits. Because r⋆ grows with the uniform-to-oracle gap, more workload skew raises r⋆ and lowers the value of fine tracking.
3
Experiments
All hypotheses, decision rules, and statistics were pre-registered before the real-data runs; code, seeds, and the pre-registration are public.1 Synthetic (H0–H2). On a leveled LSM (T =10) the static optimum cuts read cost by ≥ 30% vs. uniform, and a sweep of access weights recovers the log-law slope 2.081 at R2 =1.000 (Fig. 1). The robustness law (2) holds with fitted slope 0.50 and R2 =0.999, and a common-factor misestimate incurs ≈ 0 excess (Fig. 2). Over an equal-segment drift simulation the small-drift law (3) fits with c=0.44 (R2 =0.96); the coarse-suffices boundary sits at r=0.34 r⋆ and the stale-worse-than-uniform regime at r=4.2 r⋆ (Fig. 3). A stationary control gives V ≈ 0 (no harness leak), and cost is monotone in budget. Real traces (H2c). We replay three time-sorted Twitter production cache clusters [Yang et al., 2020], bucketing keys into segments and measuring the true within-epoch drift r at a range of compaction cadences (Fig. 5). The result is honestly regime-dependent. The pre-registered point test—mean absolute error of V vs. (3) within 0.15 across all cadences—fails (MAE 0.231, CI [0.13, 0.35]): the small-drift law averages poorly over the high-drift tail it does not cover. But the regime structure of §2 appears directly in production data. One cluster sits firmly in the coarse-suffices regime (Vmax =0.04): reallocating only at compaction captures 96–99% of continuous tracking’s benefit, with in-regime MAE 0.005. A second is transitional (Vmax =0.98), and a third is in the saturation regime (Vmax =2.0) where a stale concentrated allocation is worse than uniform and the fallback applies. Restricting to the law’s regime of validity (V̂ ≤ 0.3), the prediction holds with MAE 0.015 (CI [0.004, 0.033], n=9). So the central claim—coarse-at-compaction suffices under low drift—is confirmed on a real cluster, and the three-regime taxonomy is observed in real traffic, even though the single-law point test over all regimes does not pass. 1
https://github.com/samyama-ai/lsm-bloom-allocation
3
Figure 1: Log-law: optimal bits/key affine in Figure 2: Robustness law: excess cost = D/2, ln ai , slope 1/ ln2 2. linear in the log-error variance. Real engine (H3). Using db_bench on RocksDB [Facebook, 2021] we measure the empirical Bloom FPR over bits-per-key. In the operating range (≤ 8 bits) it follows the model primitive e−βb with effective βeff =0.462 vs. the theoretical 0.480 (within 4%); above 10 bits the real filter saturates above the optimal-Bloom floor (7.7× at 16 bits), exactly where Ribbon filters [Dillinger and Walzer, 2021] are indicated (Fig. 4). Enabling optimize_filters_for_hits (no filter on the largest level) confirms the Monkey direction: the largest run is the costliest to protect, so it should hold the fewest bits.
4
Figure 3: Adaptivity-value frontier V ≈ 21 (r/r⋆ )2 Figure 4: RocksDB FPR vs. bits/key: model holds to ≤ 8 bits, saturates above. and the coarse-suffices boundary.
Figure 5: H2c: the adaptivity-value law on real Twitter cache traces (normalized r/r⋆ ).
5
4
Related work
The static optimum is Monkey [Dayan et al., 2017, 2018]; the log-law (1) is a re-reading of its formula. Online and workload-aware allocation is the subject of ElasticBF [Li et al., 2019] (in-memory segment toggling) and, most closely, Mnemosyne [Zhu et al., 2025], which drives reallocation from accurate statistics through compactions and handles skew, updates, and imperfect tree shape; these are systems that do the adapting, and our frontier quantifies its value rather than competing with them. Endure [Huynh et al., 2022] achieves robustness by minimax over a workload ball—a different notion than our analytic sensitivity (2). Memory-split work [Luo and Carey, 2020] and active learning [Yu et al., 2024] are complementary. Ribbon filters [Dillinger and Walzer, 2021] change the per-filter cost curve (relevant in the saturation regime), and adaptivity has an intrinsic cost lower bound [Bender et al., 2018].
5
Limitations and honest scope
We characterize a policy frontier; we ship no new filter and no engine fork, and our RocksDB arm validates the FPR primitive and the Monkey direction rather than a per-segment dynamic controller (that is ElasticBF/Mnemosyne territory). The “continuous tracker” is idealized as a perfect oracle, which favors adaptation, so the coarse-suffices conclusion is conservative. The model FPR e−βb is the optimal-Bloom floor; real filters sit above it and saturate at high bits/key. Finally, “robustness to estimation error” is a motif shared with cardinality-estimation tuning; here the mechanism is specific—logarithmic dependence intrinsic to the bit-to-FPR curve—and the deliverable is the clock-governed value frontier. We hope the characterization is useful to the systems that implement the adapting. Reproducibility. Every number is regenerated by one command over the public code and the public traces; seeds, hardware, and pre-registration are documented in the repository.
References Michael A Bender, Martín Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, and Shikha Singh. Bloom filters, adaptivity, and the dictionary problem. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 182–193, 2018. doi: 10.1109/FOCS.2018.00026. Burton H Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422–426, 1970. doi: 10.1145/362686.362692. Niv Dayan, Manos Athanassoulis, and Stratos Idreos. Monkey: Optimal navigable key-value store. In Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD), pages 79–94, 2017. doi: 10.1145/3035918.3064054. Niv Dayan, Manos Athanassoulis, and Stratos Idreos. Optimal bloom filters and adaptive merging for LSM-trees. ACM Transactions on Database Systems (TODS), 43(4):1–48, 2018. doi: 10.1145/3276980. Peter C Dillinger and Stefan Walzer. Ribbon filter: Practically smaller than Bloom and Xor. arXiv preprint arXiv:2103.02515, 2021. Facebook. RocksDB: A persistent key-value store for fast storage environments. https://rocksdb.org, 2021.
6
Andy Huynh, Harshal A Chaudhari, Evimaria Terzi, and Manos Athanassoulis. Endure: A robust tuning paradigm for LSM trees under workload uncertainty. Proceedings of the VLDB Endowment, 15(8):1605–1618, 2022. doi: 10.14778/3529337.3529355. Yongkun Li, Chengjin Tian, Fan Guo, Cheng Li, and Yinlong Xu. ElasticBF: Elastic bloom filter with hotness awareness for boosting read performance in large key-value stores. In 2019 USENIX Annual Technical Conference (ATC), pages 739–752, 2019. Chen Luo and Michael J Carey. Breaking down memory walls: Adaptive memory management in LSM-based storage systems. Proceedings of the VLDB Endowment, 14(3):241–254, 2020. doi: 10.14778/3430915. 3430925. Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. The log-structured merge-tree (LSM-tree). Acta Informatica, 33(4):351–385, 1996. Juncheng Yang, Yao Yue, and K V Rashmi. A large-scale analysis of hundreds of in-memory cache clusters at Twitter. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 191–208, 2020. Weiping Yu, Siqiang Luo, et al. CAMAL: Optimizing LSM-trees via active learning. Proceedings of the ACM on Management of Data (PACMMOD), 2(4), 2024. arXiv:2409.15130. Zichen Zhu, Yanpeng Wei, Ju Hyoung Mun, and Manos Athanassoulis. Mnemosyne: Dynamic workloadaware BF tuning via accurate statistics in LSM trees. Proceedings of the ACM on Management of Data (PACMMOD), 3(3):1–28, 2025. doi: 10.1145/3725327.
7