Append-Only Storage: The Log-Structured Trie

LST is the storage engine of the AlgoX2 streaming platform. Messages are stored in numbered append-only segment files, and the index that locates them is written into those same files. There is no write-ahead log, no manifest, no compaction, and no in-place update of any byte. Space is reclaimed by unlinking whole segment files.

This article describes what the engine does, what it costs, and the workloads it fits. It does not describe the implementation.

What that buys

• Crash recovery bounded by a single configured interval, independent of database size, with no second structure to reconcile. The same interval bounds the power-loss window on unforced commits, as described under the durability contract.
• Retention that costs a file unlink rather than a merge pass over live data.
• Per-stream message count, byte size, and end-of-file available from the index rather than maintained beside it.
• Point-in-time reads with no snapshot machinery and no coordination with the writer.
• Thousands of concurrent streams at one open write descriptor and one sequential byte stream to the device.
• Roughly eight index bytes per message for dense sequential keys.
• Arbitrary key arrival order, and key-value entries with rewrite, in the same index as the messages.

Where this came from

The predecessor was an LSM-based store. It worked. The problems that pushed us off it were concentrated in one place: what happens after a crash, and what it costs to keep that path correct.

• Recovery touches three things. A write-ahead log to replay, a manifest to reopen, and the sorted runs themselves. Each has its own durability story, and a crash catches them at different instants. Most of the engineering effort around crash safety went into the seams rather than into any one component.
• The manifest is a single point of unrecoverable failure. Lose or truncate the record of which files are current and the data files are still on disk and of no use. Nothing about that exposure scales down with careful operation.
• Restart time is not bounded by anything the operator sets. It depends on write-ahead log size, on how far compaction had progressed, and on the state of the run hierarchy. There is no one parameter that answers “how long will this take to come back.”
• Retention and compaction compete. Aging data out means tombstones and waiting for a merge to carry them away, so reclaiming disk costs write bandwidth at exactly the moment disk is short.
• The acknowledged write is hard to point at. A record acknowledged to a producer lives in a memtable and a log, and its relationship to the eventual sorted run is not a thing an operator can inspect.

The requirement we wrote down was that after a crash, the state of the database should be determined by the last complete thing written, and finding it should not require consulting anything else. The design follows from taking that literally.

The workload it is specialized for

The engine is not general-purpose, and the specialization is what pays for the properties above.

• A stream is an ordered, gap-free sequence of messages, each identified by a stream id and a sequence number running 0, 1, 2, … without holes.
• Writes are appends. A new key is almost always adjacent to the one written before it.
• Deletion is retention. Data leaves from the front of a stream, oldest first, never from the middle.
• Streams are numerous and mostly small. Per-instrument lanes, control channels, rollups, configuration. A few are firehoses; most publish a handful of messages and go quiet.
• End-of-file is queried continuously, because the publish protocol deduplicates against it.

Workloads outside this shape are described under applicability.

Approach

The index is a trie. A trie locates a key by walking its bytes rather than by comparing it against stored keys, so a lookup is a descent directed by the key itself, and no node’s position depends on insertion order or on a rebalancing decision. Two consequences shape the rest of the engine. First, every node covers a contiguous range of the keyspace, so a node’s subtree is a meaningful set of keys rather than an artifact of how the tree grew, which is what lets counts, byte sizes, and end-of-file be carried on nodes and answered by a descent. Because the stream id precedes the sequence number in a key, one stream’s messages occupy one subtree. Second, common prefixes collapse, so depth tracks how far keys must be read to tell them apart rather than how long they are, and consecutive sequence numbers land adjacent in the same node. That adjacency is what makes indexing a sequential run cost a few bytes per message and lets a range read of typical width be satisfied from a single node.

One file format. A database is a directory of numbered segment files. One is active and open for append; the rest are finalized and read-only. Data and index records share those files. Nothing else on disk participates in correctness, so there is no manifest to keep current and no log running beside a tree.

Nothing is rewritten. No byte is updated in place, and no live record is relocated to reclaim the space around it. Superseded index state accumulates as dead bytes inside a segment and leaves when the whole segment does.

Snapshots are a consequence, not a feature. The engine periodically commits a point from which the index is complete on disk. Those points are also what recovery looks for and what read-only openers attach to, so snapshotting, recovery, and history are one mechanism rather than three.

Aggregates live in the index. Message count, byte size, and end-of-file per stream are answered by a bounded descent of the index rather than by a scan or by a counter maintained alongside it. A separately maintained counter can disagree with the index; one derived from it cannot.

Retention is an unlink. Dropping the oldest segments reads no data. A small amount of index state whose size scales with the number of streams and key-value keys, and not with the number of messages, is preserved across a drop by background work that never suspends a commit. If that work falls behind, the store holds disk above its budget and reports doing so, rather than discarding anything it still needs.

Stream count does not appear in the write path. All streams share one index and one active segment, so ten thousand streams is one open write descriptor and one sequential byte stream. This is the sharpest practical difference from per-partition-file designs, where descriptor consumption grows with partition count and, more importantly, per-partition sequential appending stops being sequential at the device once there are enough partitions.

The durability contract

Three levels are stated plainly because the snapshot interval governs two different things, and it is worth separating them.

A commit that returns is acknowledged. The operating system has accepted the bytes. The engine hands out a location and indexes a key only at that point, so a key can never resolve to bytes the file refused. An acknowledged record survives process failure immediately, including a kill of the writer, because the bytes are in the page cache and the page cache outlives the process. Recovery finds them.

A commit that returns is not yet power-loss durable. Writeback to the device is not ordered by the order in which writes were issued. The engine forces the device once per snapshot, so records committed since the last snapshot are the window that a power loss can take. That window is bounded by the snapshot interval and by nothing else.

A forced commit is power-loss durable on return. A caller answerable for a specific record can force it, which makes that record and everything committed before it durable against power loss at the cost of a device sync. Callers that do not need the guarantee do not pay for it.

What the snapshot interval bounds. One parameter has two effects that move in opposite directions.

Choosing it is a straightforward operational tradeoff: how much work in steady state to buy how narrow a loss window and how fast a restart. Nothing else in the engine’s recovery behavior depends on it.

Scope. Ordering is per store. One writer owns one directory of segments, and the engine makes no claim about two stores, whether they hold two partitions of one stream or two copies of one partition. Establishing order across stores is the replicating layer’s responsibility, and a single-writer local store cannot be cited for a distributed guarantee.

Properties

Comparison

Two observations follow from the table. Kafka’s cheap retention is conditional. Dropping whole segments is an unlink only for streams with no key-value semantics; a topic with keys requires log compaction, which scans the partition to determine the surviving record per key and rewrites the segments that hold them. Key-value state and cheap deletion are alternatives there, not both. LST carries key-value entries in the same index as messages and drops segments without reading them either way.

BookKeeper addresses write dispersion the same way LST does, by interleaving all ledgers into shared files, and pays for it with three subsystems: an embedded index to locate entries again, a journal because that index is not durable at write time, and a garbage collector to reclaim partially deleted entry logs. Pravega’s attribute index is the nearest prior art to storing an append-only index in a log that is itself subject to truncation, and its published design relies on compaction to make head truncation safe.

Applicability

The engine is a good fit where data is appended and aged out from the front, streams are numerous, and restart time and retention cost are operational concerns. Outside that shape:

• Overwrite-heavy or random-delete workloads. Space is reclaimed in segment-sized units, so heavy overwriting holds dead bytes longer than a compacting engine would. Measured overhead at steady state on append-mostly workloads is under six percent; an overwrite-heavy workload needs its own measurement.
• Multi-writer transactional use. One writer per store, with unlimited lock-free readers. This is a per-stream commit intake, not an OLTP engine. Distribution and cross-store ordering belong to the replicating layer above it.
• Durability of the most recent writes. Deployments that cannot tolerate a bounded power-loss window on unforced commits should read the durability contract before sizing the snapshot interval.
• Silent device corruption. Records are not checksummed. Damage that breaks record structure is reported at recovery; damage confined to the interior of a message reads back as the caller’s data. Deployments that require end-to-end integrity should checksum at the message layer or below the file system.
• Comparative performance. The comparison above is structural. It rests on what each design must do to reclaim space and to recover, not on measurements of competing engines, which we have not run.

Measurements

Counted quantities below are exact and independent of hardware. Throughput figures are omitted pending measurement against NVMe storage.

Crash recovery in typical operation completes in well under a second, because the work is bounded by the records committed since the last snapshot rather than by the size of the database. The measured rate is on the order of a hundred thousand records per second, so recovering a full snapshot interval of traffic stays sub-second at intervals in normal use, and a store of any size recovers in the time its own tail takes to re-index.

---

Want more context on the platform? Read Everything is a Stream, learn about the product, or get in touch with us on the contact page.