LSM Trees: Writing in Layers

in reviewThis lesson is complete and being validated before release - details may still change.

LSM tree

Loading interactive demo…

The strip at the top is the memory table, sorted and capped. The grid beneath is the disk: one row per level, newest level at the top, each group of cells one immutable sorted run with its keys, oldest run at the left. The dense strip is the stream of writes, marked as they land; the last strip is every key the workload writes plus one it never does. Tap a key there to look it up once the writes are done.Take the tour, or press and explore. Legend:

The panel beside the stage is the real LsmTree class from the published library executing in your browser, with the current line highlighted.

The key just written, the run being read by the lookup, and the key looked up.
A run just made by a flush or a merge, and a write that has landed.
Runs a merge is consuming this step.
A tombstone, the record of a delete, wherever it sits.
A run the Bloom filter let the lookup skip, and writes still to come.

writes counts the stream so far; flushes and compactions count the sequential passes they cost; runs says how many sorted files the disk holds and in how many levels; reads counts the places the lookup read and the ones its filters skipped; lookup is the verdict.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Why not overwrite. A B-tree keeps every key in its place, so an update finds the page, changes it, and writes the page back: a random write per update, and on a spinning disk a seek per write. A log is the opposite shape. Appending to the end of a file is the fastest thing a disk or a flash chip does, and the write-ahead logging lesson already relies on that. The log-structured merge tree asks what an index would look like if it were allowed only to append, and the answer is layers.

The memory table. Every write goes into a small sorted structure in memory, the memtable, and is done. An update replaces the key's entry there; a delete writes a tombstone, a marker that stands where the value would. The table is bounded by its limit $L$ , so a write costs $O(\log L)$ or, on this stage, one sorted insert. A real system logs each write to the WAL first, because memory is lost in a crash: the memtable is the WAL's buffer pool, seen from the other side.

Runs. A full table is written to disk whole, in one sequential sweep, as a run: a sorted file that is never changed again. Nothing is ever overwritten in place. The same key may appear in several runs, and the newest run is right; the older entries are shadowed, not deleted, until a merge removes them. Reads therefore have to know which run is newer, which is why runs sit in levels and are numbered.

Compaction. With fanout $F$ , a level that fills with $F$ runs is merged: one pass through all of them, as in merge sort, keeping for each key the newest entry, writing one run a level down. Each level holds about $F$ times the data of the one above, so a key is rewritten once per level it passes through: write amplification of about $\log_F N$ passes for $N$ entries, all of them sequential. On this stage the fourth level merges into itself, since there is nothing below it; a real tree adds levels as it grows.

Reading. A lookup checks the memtable, then every run from the newest to the oldest, and stops at the first that holds the key. A key that is present costs as many reads as there are newer places without it; a key that is absent costs one read of every place. That is read amplification, and it is the price the tree pays for its writes. A lower fanout merges more often and leaves fewer runs to read; a higher fanout does the reverse. Real systems also keep the key range of every run so a lookup skips runs outside it.

Bloom filters. Each run carries a filter: a row of $m$ bits set at two hashed positions per key. A key whose bits are not all set was never written to the run, with certainty, so the run is skipped without a read. A key whose bits are all set may or may not be there, and the read may be wasted. With $k$ hashes and $n$ keys the false positive rate is about $(1 - e^{-kn/m})^k$ ; the stage's sixteen-bit filters are deliberately small so that false positives occur. A real filter spends about ten bits per key for a rate near one percent, and most lookups of absent keys touch no run at all.

Tombstones. Because older runs may still hold a value for a deleted key, the tombstone must survive until no older entry can exist, which is the merge into the last level. Until then every merge carries it down, and every lookup that meets it stops. A store that deletes a great deal spends real space on tombstones, and its reads slow down until compaction catches up.

The trade. A B-tree answers a point read in one descent and pays a random write per update. An LSM tree answers a write in one memory insert and pays several reads per lookup, plus background passes. Space is the third corner: shadowed entries and tombstones waste space until they are merged away. Choose by the workload: ingest-heavy, append-mostly, and time-ordered data favour the LSM tree; read-heavy, update-in-place data favours the B-tree.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

put and remove are one private write, differing only in whether the value is a number or null. A delete is a write, which is the whole lesson in one method.
The memtable is an array kept sorted on insert, so a flush is a copy and nothing more. A real memtable is a skip list or a red-black tree; the sorted array keeps the file short.
flush makes a run and then loops over the levels, calling compact on any that has reached the fanout. One flush can cascade a merge down several levels, which is why a write's cost is bursty.
compact merges with a map keyed by key, visiting runs oldest first so the newest value wins by being set last. Tombstones are kept except when the target is the last level, where nothing older can lie beneath them.
Runs are never edited: a merge builds a new run and forgets the old ones. runs() hands out copies, so even the stage cannot change a run behind the class's back.
get builds the list of places newest first, the memtable and then each level's runs in reverse, and emits one probe per place from a single site, so the code panel's highlight lands on the same line for a hit, a miss, and a filter skip.
BloomFilter is sixteen bits and two multiplicative hashes, taking the top four bits of a 32-bit product so neighbouring keys land apart. It answers maybe, never yes, and that word is the honest one.

Disks and flash write a long sequential stretch far faster than they change one record in place, and a B-tree changes records in place. In 1992 Rosenblum and Ousterhout built a file system that wrote everything as a log; in 1996 O'Neil, Cheng, Gawlick, and O'Neil carried the idea into indexing, with a small tree in memory, sorted components on disk, and a rolling merge moving data down. Bigtable made it the backbone of a storage system in 2006, LevelDB put it in a library in 2011, and most write-heavy databases since rest on it.

1970Burton Bloom - Describes the space-efficient probabilistic filter that lets a lookup skip a file that cannot hold the key, at the price of an occasional needless read.source
1992Mendel Rosenblum and John Ousterhout - The log-structured file system writes every change as a sequential append to a log and cleans the log in the background, the idea the LSM tree brings to indexes.source
1996Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil - Publish the Log-Structured Merge-Tree: a memory component and a chain of disk components, data migrating down by merges, for workloads with far more inserts than lookups.source
2006Google - The Bigtable paper describes each tablet as a memtable plus a set of immutable sorted files, SSTables, merged by compactions, with Bloom filters to spare lookups the disk.source
2011Jeff Dean and Sanjay Ghemawat - Google releases LevelDB, a key-value library built on levelled compaction of sorted tables, which Chrome, Bitcoin Core, and many databases embed.source
2012Facebook - RocksDB forks LevelDB for flash storage and many cores, and becomes the storage engine beneath MySQL at Facebook, CockroachDB, TiKV, and others.source

Used today

Write-heavy stores - Cassandra, HBase, ScyllaDB, and RocksDB take writes as memtable inserts and sequential flushes, which is why they absorb ingest rates a B-tree store cannot.
Time series and logs - Keys that arrive in order flush into runs that never overlap, so merges are cheap and the newest data sits in the smallest, fastest layer.
Embedded key-value stores - LevelDB and RocksDB sit inside browsers, blockchains, and message brokers as the local store for anything that must survive a restart.

Did you know

The 1996 paper called its layers components, C0 in memory and C1 onward on disk, and moved data between them with a rolling merge that worked through the key range a stretch at a time instead of merging whole files.source
Bigtable named its immutable sorted files SSTables, for sorted string table, and the name stuck: LevelDB, RocksDB, and Cassandra all call their runs SSTables.source
Bloom's 1970 paper motivated the filter with hyphenation: most English words follow simple rules, and the filter picked out the few exceptions that needed a dictionary fetched from disk.source
A delete marker in a store that cannot overwrite is called a tombstone, a name that spread from Cassandra, where a tombstone outlives the delete for a grace period so a replica that missed it can still learn of it.source

workload

writes12

memtable

fanout

filters

seed1

writes: 12 of 12
flushes: 4
compactions: 3
runs: 1 in 1 level
reads: 2 read, 0 skipped
lookup: 5 is 50, in run 7

lsm-tree.ts

import type { Tracer } from "../trace";/** Entries the sorted memory table holds before it is flushed to disk. */export const MAX_MEMTABLE = 6;/** Runs a level may hold before they merge into the level below. */export const MAX_FANOUT = 4;/** Entries one tree ever accepts, so a workload stays a stage's size. */export const MAX_LSM_KEYS = 64;/** Levels of runs; the last level merges into itself. */export const MAX_LEVELS = 4;/** Bits in a run's Bloom filter. */export const BLOOM_BITS = 16;/** One key and its value; a null value is a tombstone, the record of a delete. */export interface LsmEntry {  key: number;  value: number | null;}/** A sorted table on disk. Once written it is never changed, only read and eventually merged away. */export interface Run {  id: number;  level: number;  entries: readonly LsmEntry[];}export interface LsmOptions {  /** Entries the memory table holds before it flushes. */  memtableLimit: number;  /** Runs a level holds before they merge into one run a level down. */  fanout: number;  /** Whether each run carries a Bloom filter a lookup consults before reading it. */  bloom: boolean;}export interface LsmReport {  writes: number;  flushes: number;  compactions: number;  runs: number;  levels: number;  lookups: number;  probes: number;  found: number;  missing: number;}/** * A Bloom filter over integer keys: a row of bits, two hash functions, * and one honest answer, "no", plus one hedged answer, "maybe". A key * that was added always comes back maybe; a key that was not usually * comes back no, but two keys can share both bits, and then the filter * lets a needless read through. */export class LsmBloomFilter {  private readonly bits: boolean[] = new Array<boolean>(BLOOM_BITS).fill(false);  add(key: number): void {    this.bits[LsmBloomFilter.first(key)] = true;    this.bits[LsmBloomFilter.second(key)] = true;  }  /** False only when the key was certainly never added. */  maybe(key: number): boolean {    return (this.bits[LsmBloomFilter.first(key)] ?? false) && (this.bits[LsmBloomFilter.second(key)] ?? false);  }  /** The top four bits of a 32-bit multiplicative hash, so neighbouring keys land apart. */  private static first(key: number): number {    return LsmBloomFilter.topBits(key * 2654435761);  }  private static second(key: number): number {    return LsmBloomFilter.topBits(key * 2246822519);  }  private static topBits(product: number): number {    return Math.floor((product % 4294967296) / (4294967296 / BLOOM_BITS));  }}/** * A log-structured merge tree never overwrites a record where it lies. * Every write goes into a small sorted table in memory; when that table * is full it is written to disk whole, as an immutable sorted run, and * a fresh table starts. Runs pile up in levels: when a level holds * `fanout` runs they are merged, newest entry winning for each key, into * one run a level down. A delete is a write of a tombstone, which hides * older values until the merge that reaches the last level drops it. A * read checks the places newest first, the memory table and then each * run, and stops at the first that holds the key; a Bloom filter per * run lets most lookups skip runs that cannot hold it. Writes are * sequential appends, and reads pay for that in probes. * * Time: O(limit) per write, O(entries) per compaction, O(runs) per lookup. * Space: O(MAX_LSM_KEYS) across the table and the runs. */export class LsmTree {  private table: LsmEntry[] = [];  private readonly levels: Run[][] = Array.from({ length: MAX_LEVELS }, () => []);  private readonly filters = new Map<number, LsmBloomFilter>();  private nextRun = 1;  private writes = 0;  private flushes = 0;  private compactions = 0;  private lookups = 0;  private probes = 0;  private found = 0;  private missing = 0;  constructor(    readonly options: LsmOptions,    private readonly tracer?: Tracer,  ) {    const { memtableLimit, fanout } = options;    if (!Number.isInteger(memtableLimit) || memtableLimit < 2 || memtableLimit > MAX_MEMTABLE) throw new RangeError(`memtableLimit must be in [2, ${MAX_MEMTABLE}]`);    if (!Number.isInteger(fanout) || fanout < 2 || fanout > MAX_FANOUT) throw new RangeError(`fanout must be in [2, ${MAX_FANOUT}]`);  }  /** The memory table's entries in key order; a copy. */  memtable(): readonly LsmEntry[] {    return this.table.map((entry) => ({ ...entry }));  }  /** Every run on disk, level 0 first and within a level oldest first; copies. */  runs(): readonly Run[] {    return this.levels.flatMap((level) => level.map((run) => ({ ...run, entries: run.entries.map((entry) => ({ ...entry })) })));  }  put(key: number, value: number): void {    if (!Number.isInteger(value)) throw new RangeError(`value ${value} must be an integer`);    this.write(key, value);  }  /** A delete is a write: a tombstone that hides every older value of the key. */  remove(key: number): void {    this.write(key, null);  }  /** Reads newest first: the memory table, then every run from the top level down. */  get(key: number): number | null {    LsmTree.checkKey(key);    this.lookups++;    let probes = 0;    const places: { place: string; level: number; entries: readonly LsmEntry[]; filter: LsmBloomFilter | null }[] = [{ place: "memtable", level: -1, entries: this.table, filter: null }];    for (const [level, runs] of this.levels.entries()) {      for (const run of [...runs].reverse()) places.push({ place: `run ${run.id}`, level, entries: run.entries, filter: this.options.bloom ? (this.filters.get(run.id) ?? null) : null });    }    let answer: LsmEntry | undefined;    let where = "";    for (const { place, level, entries, filter } of places) {      const skipped = filter !== null && !filter.maybe(key);      const entry = skipped ? undefined : entries.find((candidate) => candidate.key === key);      if (!skipped) probes++;      // ▸ check one place for the key, the memory table first and then every run from the newest, unless its filter says the key is absent      this.tracer?.emit("probe", { key, place, level, hit: entry !== undefined, skipped, needless: filter !== null && !skipped && entry === undefined });      if (entry !== undefined) {        answer = entry;        where = place;        break;      }    }    this.probes += probes;    if (answer !== undefined && answer.value !== null) {      this.found++;      // ▸ the first place that holds the key answers; nothing older is consulted      this.tracer?.emit("found", { key, value: answer.value, place: where, probes });      return answer.value;    }    // Either no place holds the key, or the newest record of it is a tombstone.    this.missing++;    // ▸ no place holds a live value for the key, or the newest record of it is a tombstone    this.tracer?.emit("missing", { key, probes, tombstone: answer !== undefined });    return null;  }  report(): LsmReport {    const runs = this.levels.reduce((n, level) => n + level.length, 0);    const levels = this.levels.filter((level) => level.length > 0).length;    return { writes: this.writes, flushes: this.flushes, compactions: this.compactions, runs, levels, lookups: this.lookups, probes: this.probes, found: this.found, missing: this.missing };  }  /** Puts a key into the sorted table, replacing its older value there, and flushes a full table. */  private write(key: number, value: number | null): void {    LsmTree.checkKey(key);    if (this.writes >= MAX_LSM_KEYS) throw new RangeError(`${MAX_LSM_KEYS} writes is the most one tree accepts`);    this.writes++;    const at = this.table.findIndex((entry) => entry.key >= key);    const insertPosition = this.table.findIndex((entry) => entry.key >= key);    if (at === -1) this.table.push({ key, value });    if (insertPosition === -1) this.table.push({ key, value });    else if (this.table[at]!.key === key) this.table[at] = { key, value };    else if (this.table[insertPosition]!.key === key) this.table[insertPosition] = { key, value };    else this.table.splice(at, 0, { key, value });    else this.table.splice(insertPosition, 0, { key, value });    // ▸ put the key into the sorted table in memory, replacing an older value of the same key there    this.tracer?.emit("write", { key, value, tombstone: value === null, keys: this.table.map((entry) => entry.key), size: this.table.length, limit: this.options.memtableLimit });    if (this.table.length >= this.options.memtableLimit) this.flush();  }  /** Writes the table to disk as one sorted run at level 0 and merges any level that is now full. */  private flush(): void {    const run: Run = { id: this.nextRun++, level: 0, entries: this.table };    this.remember(run);    this.levels[0]!.push(run);    this.table = [];    this.flushes++;    // ▸ the table is full: write it to disk whole as an immutable sorted run and start an empty table    this.tracer?.emit("flush", { run: run.id, level: 0, keys: run.entries.map((entry) => entry.key), tombstones: run.entries.filter((entry) => entry.value === null).length });    for (let level = 0; level < MAX_LEVELS; level++) {      if (this.levels[level]!.length >= this.options.fanout) this.compact(level);    }  }  /** Merges every run of a level into one run a level down, the newest value of each key winning. */  private compact(level: number): void {    const runs = this.levels[level]!;    const to = Math.min(level + 1, MAX_LEVELS - 1);    const lastLevel = to === MAX_LEVELS - 1;    const newest = new Map<number, LsmEntry>();    const latestByKey = new Map<number, LsmEntry>();    let shadowed = 0;    for (const run of runs) {      for (const entry of run.entries) {        if (newest.has(entry.key)) shadowed++;        if (latestByKey.has(entry.key)) shadowed++;        newest.set(entry.key, entry);        latestByKey.set(entry.key, entry);      }    }    const entries = [...newest.values()].sort((a, b) => a.key - b.key);    const entries = [...latestByKey.values()].sort((a, b) => a.key - b.key);    const kept = lastLevel ? entries.filter((entry) => entry.value !== null) : entries;    const survivors = lastLevel ? entries.filter((entry) => entry.value !== null) : entries;    const merged: Run = { id: this.nextRun++, level: to, entries: kept };    const merged: Run = { id: this.nextRun++, level: to, entries: survivors };    this.remember(merged);    for (const run of runs) this.filters.delete(run.id);    this.levels[level] = [];    this.levels[to]!.push(merged);    this.compactions++;    // ▸ a level holds its fanout of runs: merge them into one run a level down, the newest value of each key winning    this.tracer?.emit("compact", { from: level, runs: runs.map((run) => run.id), to, run: merged.id, keys: kept.map((entry) => entry.key), shadowed, dropped: entries.length - kept.length });    this.tracer?.emit("compact", { from: level, runs: runs.map((run) => run.id), to, run: merged.id, keys: survivors.map((entry) => entry.key), shadowed, dropped: entries.length - survivors.length });  }  /** Builds the run's Bloom filter from its keys. */  private remember(run: Run): void {    const filter = new LsmBloomFilter();    for (const entry of run.entries) filter.add(entry.key);    this.filters.set(run.id, filter);  }  private static checkKey(key: number): void {    if (!Number.isInteger(key) || key < 0) throw new RangeError(`key ${key} must be a non-negative integer`);  }}

flushes =: 4
compactions =: 3
probes =: 2

12 writes took 4 flushes and 3 compactions, leaving 1 run across 1 level; the lookup of 5 found 50 in 2 reads.

import type { Tracer } from "../trace";/** Entries the sorted memory table holds before it is flushed to disk. */export const MAX_MEMTABLE = 6;/** Runs a level may hold before they merge into the level below. */export const MAX_FANOUT = 4;/** Entries one tree ever accepts, so a workload stays a stage's size. */export const MAX_LSM_KEYS = 64;/** Levels of runs; the last level merges into itself. */export const MAX_LEVELS = 4;/** Bits in a run's Bloom filter. */export const BLOOM_BITS = 16;/** One key and its value; a null value is a tombstone, the record of a delete. */export interface LsmEntry { key: number; value: number | null;}/** A sorted table on disk. Once written it is never changed, only read and eventually merged away. */export interface Run { id: number; level: number; entries: readonly LsmEntry[];}export interface LsmOptions { /** Entries the memory table holds before it flushes. */ memtableLimit: number; /** Runs a level holds before they merge into one run a level down. */ fanout: number; /** Whether each run carries a Bloom filter a lookup consults before reading it. */ bloom: boolean;}export interface LsmReport { writes: number; flushes: number; compactions: number; runs: number; levels: number; lookups: number; probes: number; found: number; missing: number;}/** * A Bloom filter over integer keys: a row of bits, two hash functions, * and one honest answer, "no", plus one hedged answer, "maybe". A key * that was added always comes back maybe; a key that was not usually * comes back no, but two keys can share both bits, and then the filter * lets a needless read through. */export class LsmBloomFilter { private readonly bits: boolean[] = new Array<boolean>(BLOOM_BITS).fill(false); add(key: number): void { this.bits[LsmBloomFilter.first(key)] = true; this.bits[LsmBloomFilter.second(key)] = true; } /** False only when the key was certainly never added. */ maybe(key: number): boolean { return (this.bits[LsmBloomFilter.first(key)] ?? false) && (this.bits[LsmBloomFilter.second(key)] ?? false); } /** The top four bits of a 32-bit multiplicative hash, so neighbouring keys land apart. */ private static first(key: number): number { return LsmBloomFilter.topBits(key * 2654435761); } private static second(key: number): number { return LsmBloomFilter.topBits(key * 2246822519); } private static topBits(product: number): number { return Math.floor((product % 4294967296) / (4294967296 / BLOOM_BITS)); }}/** * A log-structured merge tree never overwrites a record where it lies. * Every write goes into a small sorted table in memory; when that table * is full it is written to disk whole, as an immutable sorted run, and * a fresh table starts. Runs pile up in levels: when a level holds * `fanout` runs they are merged, newest entry winning for each key, into * one run a level down. A delete is a write of a tombstone, which hides * older values until the merge that reaches the last level drops it. A * read checks the places newest first, the memory table and then each * run, and stops at the first that holds the key; a Bloom filter per * run lets most lookups skip runs that cannot hold it. Writes are * sequential appends, and reads pay for that in probes. * * Time: O(limit) per write, O(entries) per compaction, O(runs) per lookup. * Space: O(MAX_LSM_KEYS) across the table and the runs. */export class LsmTree { private table: LsmEntry[] = []; private readonly levels: Run[][] = Array.from({ length: MAX_LEVELS }, () => []); private readonly filters = new Map<number, LsmBloomFilter>(); private nextRun = 1; private writes = 0; private flushes = 0; private compactions = 0; private lookups = 0; private probes = 0; private found = 0; private missing = 0; constructor( readonly options: LsmOptions, private readonly tracer?: Tracer, ) { const { memtableLimit, fanout } = options; if (!Number.isInteger(memtableLimit) || memtableLimit < 2 || memtableLimit > MAX_MEMTABLE) throw new RangeError(`memtableLimit must be in [2, ${MAX_MEMTABLE}]`); if (!Number.isInteger(fanout) || fanout < 2 || fanout > MAX_FANOUT) throw new RangeError(`fanout must be in [2, ${MAX_FANOUT}]`); } /** The memory table's entries in key order; a copy. */ memtable(): readonly LsmEntry[] { return this.table.map((entry) => ({ ...entry })); } /** Every run on disk, level 0 first and within a level oldest first; copies. */ runs(): readonly Run[] { return this.levels.flatMap((level) => level.map((run) => ({ ...run, entries: run.entries.map((entry) => ({ ...entry })) }))); } put(key: number, value: number): void { if (!Number.isInteger(value)) throw new RangeError(`value ${value} must be an integer`); this.write(key, value); } /** A delete is a write: a tombstone that hides every older value of the key. */ remove(key: number): void { this.write(key, null); } /** Reads newest first: the memory table, then every run from the top level down. */ get(key: number): number | null { LsmTree.checkKey(key); this.lookups++; let probes = 0; const places: { place: string; level: number; entries: readonly LsmEntry[]; filter: LsmBloomFilter | null }[] = [{ place: "memtable", level: -1, entries: this.table, filter: null }]; for (const [level, runs] of this.levels.entries()) { for (const run of [...runs].reverse()) places.push({ place: `run ${run.id}`, level, entries: run.entries, filter: this.options.bloom ? (this.filters.get(run.id) ?? null) : null }); } let answer: LsmEntry | undefined; let where = ""; for (const { place, level, entries, filter } of places) { const skipped = filter !== null && !filter.maybe(key); const entry = skipped ? undefined : entries.find((candidate) => candidate.key === key); if (!skipped) probes++; // ▸ check one place for the key, the memory table first and then every run from the newest, unless its filter says the key is absent this.tracer?.emit("probe", { key, place, level, hit: entry !== undefined, skipped, needless: filter !== null && !skipped && entry === undefined }); if (entry !== undefined) { answer = entry; where = place; break; } } this.probes += probes; if (answer !== undefined && answer.value !== null) { this.found++; // ▸ the first place that holds the key answers; nothing older is consulted this.tracer?.emit("found", { key, value: answer.value, place: where, probes }); return answer.value; } // Either no place holds the key, or the newest record of it is a tombstone. this.missing++; // ▸ no place holds a live value for the key, or the newest record of it is a tombstone this.tracer?.emit("missing", { key, probes, tombstone: answer !== undefined }); return null; } report(): LsmReport { const runs = this.levels.reduce((n, level) => n + level.length, 0); const levels = this.levels.filter((level) => level.length > 0).length; return { writes: this.writes, flushes: this.flushes, compactions: this.compactions, runs, levels, lookups: this.lookups, probes: this.probes, found: this.found, missing: this.missing }; } /** Puts a key into the sorted table, replacing its older value there, and flushes a full table. */ private write(key: number, value: number | null): void { LsmTree.checkKey(key); if (this.writes >= MAX_LSM_KEYS) throw new RangeError(`${MAX_LSM_KEYS} writes is the most one tree accepts`); this.writes++; const at = this.table.findIndex((entry) => entry.key >= key); const insertPosition = this.table.findIndex((entry) => entry.key >= key); if (at === -1) this.table.push({ key, value }); if (insertPosition === -1) this.table.push({ key, value }); else if (this.table[at]!.key === key) this.table[at] = { key, value }; else if (this.table[insertPosition]!.key === key) this.table[insertPosition] = { key, value }; else this.table.splice(at, 0, { key, value }); else this.table.splice(insertPosition, 0, { key, value }); // ▸ put the key into the sorted table in memory, replacing an older value of the same key there this.tracer?.emit("write", { key, value, tombstone: value === null, keys: this.table.map((entry) => entry.key), size: this.table.length, limit: this.options.memtableLimit }); if (this.table.length >= this.options.memtableLimit) this.flush(); } /** Writes the table to disk as one sorted run at level 0 and merges any level that is now full. */ private flush(): void { const run: Run = { id: this.nextRun++, level: 0, entries: this.table }; this.remember(run); this.levels[0]!.push(run); this.table = []; this.flushes++; // ▸ the table is full: write it to disk whole as an immutable sorted run and start an empty table this.tracer?.emit("flush", { run: run.id, level: 0, keys: run.entries.map((entry) => entry.key), tombstones: run.entries.filter((entry) => entry.value === null).length }); for (let level = 0; level < MAX_LEVELS; level++) { if (this.levels[level]!.length >= this.options.fanout) this.compact(level); } } /** Merges every run of a level into one run a level down, the newest value of each key winning. */ private compact(level: number): void { const runs = this.levels[level]!; const to = Math.min(level + 1, MAX_LEVELS - 1); const lastLevel = to === MAX_LEVELS - 1; const newest = new Map<number, LsmEntry>(); const latestByKey = new Map<number, LsmEntry>(); let shadowed = 0; for (const run of runs) { for (const entry of run.entries) { if (newest.has(entry.key)) shadowed++; if (latestByKey.has(entry.key)) shadowed++; newest.set(entry.key, entry); latestByKey.set(entry.key, entry); } } const entries = [...newest.values()].sort((a, b) => a.key - b.key); const entries = [...latestByKey.values()].sort((a, b) => a.key - b.key); const kept = lastLevel ? entries.filter((entry) => entry.value !== null) : entries; const survivors = lastLevel ? entries.filter((entry) => entry.value !== null) : entries; const merged: Run = { id: this.nextRun++, level: to, entries: kept }; const merged: Run = { id: this.nextRun++, level: to, entries: survivors }; this.remember(merged); for (const run of runs) this.filters.delete(run.id); this.levels[level] = []; this.levels[to]!.push(merged); this.compactions++; // ▸ a level holds its fanout of runs: merge them into one run a level down, the newest value of each key winning this.tracer?.emit("compact", { from: level, runs: runs.map((run) => run.id), to, run: merged.id, keys: kept.map((entry) => entry.key), shadowed, dropped: entries.length - kept.length }); this.tracer?.emit("compact", { from: level, runs: runs.map((run) => run.id), to, run: merged.id, keys: survivors.map((entry) => entry.key), shadowed, dropped: entries.length - survivors.length }); } /** Builds the run's Bloom filter from its keys. */ private remember(run: Run): void { const filter = new LsmBloomFilter(); for (const entry of run.entries) filter.add(entry.key); this.filters.set(run.id, filter); } private static checkKey(key: number): void { if (!Number.isInteger(key) || key < 0) throw new RangeError(`key ${key} must be a non-negative integer`); }}