Monkey: bloom bits where they pay

“10 bits/key everywhere” was folklore; Monkey turned bloom-filter sizing into an optimization problem and won ~2× fewer wasted IOs from the same DRAM. This chapter derives the allocation rule — FPR proportional to level size, so bits/key decrease toward the bottom — and sets up the per-level-bits experiment in the mini-LSM.

The setup

An LSM with L levels, size ratio T, total filter memory budget M. Every level gets a bloom filter. Question: how should M be divided among levels?

The one picture

 uniform (state of practice):        Monkey (optimal):

 L1 (small)  10 bits/key             L1   ~14 bits/key  (FPR tiny)
 L2          10 bits/key             L2   ~12 bits/key
 L3 (huge)   10 bits/key             L3    ~8 bits/key  (FPR larger, but
                                            fewer probes land here anyway)
 total FPR cost: sum of per-level    expected wasted IOs: MINIMIZED —
 FPRs, dominated by... all equally   exponentially decreasing FPR up the tree

Key observation: expected wasted IO for a zero-result lookup = sum of the per-level FPRs (each level is one potential false probe). But bits-per-key buys FPR exponentially (fpr ≈ e^(−bits·ln²2)), while level sizes grow by T. Spending a bit at a small level buys the same FPR drop for T× fewer keys — i.e., T× cheaper. Optimum: FPRs proportional to level size ⇒ bits/key decreasing geometrically toward the bottom; the bottom level may get ~0 (its “filter” is the fact that every lookup ends there anyway).

The whole allocation, as the closed form your mini-LSM can call:

#![allow(unused)]
fn main() {
// Pick a total zero-result FPR budget; hand each level a share
// PROPORTIONAL TO ITS SIZE, then convert fpr → bits/key.
fn monkey_alloc(level_keys: &[u64], total_fpr: f64) -> Vec<f64> {
    let n: u64 = level_keys.iter().sum();
    level_keys.iter().map(|&nk| {
        let fpr = total_fpr * nk as f64 / n as f64;   // p_i ∝ level size
        -fpr.ln() / (LN_2 * LN_2)                     // bits/key: fpr ≈ e^(−bits·ln²2)
    }).collect()                                      // small levels get MORE bits/key
}
}

Reading order

§1–2 — the LSM cost model (worth it alone: R/W/M costs as formulas in T, L). Map each symbol to your mini-LSM’s knobs.
§4 — the allocation argument (above). Follow the Lagrange-multiplier sketch once; then re-derive the “FPR ∝ level size” conclusion informally yourself.
§5 — merging co-tuning (T as a continuum from leveled to tiered). Skim — Dostoevsky does this better.
§6 evaluation — look for the ~2× lookup improvement at equal memory.

Questions to answer in notes.md

In your mini-LSM (3 levels, T=10, 10M keys), compute uniform-vs-Monkey expected false probes per zero-result get at 10 bits/key average. Then measure zero-result gets both ways (the experiment supports per-level bits-per-key for exactly this).
Monkey assumes point lookups dominate. What breaks for range scans? (Filters don’t help ranges at all — prefix blooms exist for a subset.)
FalkorDB angle: an attribute store doing existence checks before edge insertion is a zero-result-heavy workload — where would Monkey’s argument apply outside an LSM?

Done when

You can state the allocation rule (“equal marginal IO saved per bit ⇒ FPR proportional to level size”) and back it with the measured table from your mini-LSM.

References

Papers

Dayan, Athanassoulis, Idreos — “Monkey: Optimal Navigable Key-Value Store” (SIGMOD 2017) — §1–2 for the LSM cost model, §4 for the allocation argument; skim §5 (Dostoevsky does the merging co-tuning better) and §6 for the ~2× lookup improvement at equal memory

Keyboard shortcuts