We Replaced LevelDB: Why AlgoX2 Built Its Own Append-Only Storage Engine
The storage engine is where a streaming platform’s promises become physical. How messages land on disk decides the write throughput, the story after a crash, and what retention costs.
The obvious move is to reuse an engine someone else has hardened. AlgoX2 tried that, and before it, tried something simpler still. Neither held up, and what the team learned from both is the engine AlgoX2 runs on today: LST, the log-structured trie. Append-Only Storage: The Log-Structured Trie describes what it does and what it costs. This is the story of why it exists.
Attempt one: a file per stream
The first idea was the plainest one. A stream is just messages, so write each stream to a file and index it somehow.
Disk performance collapsed as soon as many files were open. NVMe drives and spinning disks are alike in one way: they write into slow-moving blocks, and they do not like being written in hundreds or thousands of places at once. Many open files is exactly that.
The crash story was worse. After a crash, some recent writes never reached the disk, and there are 10,000 files open. Each has to be opened, its tail checked for garbage, and the whole set declared consistent. Consistent with what? A node in a large cluster has no reference to compare against.
Attempt two: a log-structured merge tree
A log-structured merge tree looked like a better fit. AlgoX2 has many streams, and not all are active at once. It also needs key-value storage, both to implement the Kafka interface and for its own bookkeeping, so it wanted something more general than a flat index of messages.
RocksDB, at something like half a million lines, was too much. LevelDB, written by Jeff Dean, was about 16,000, and that was a good sign. The team learned it inside out and put it to work.
The same problem came back. An LSM tree is built for keys that are rewritten many times with new values. That is where it shines. A streaming platform is the opposite: the key is a message’s address, written once and almost never again. The keys are also dense, in fact contiguous, and nothing in the engine took advantage of that.
A trie for contiguous keys
Trial and error had drawn the outline of the right answer. AlgoX2 needed its own engine, built on a Patricia trie.
In a trie, keys that share long prefixes form corridors with no branches. A Patricia trie collapses each corridor into one node with a longer prefix. Patricia is not a name; it is an acronym, from the 1960s. Tries suit AlgoX2 because every key has nearly the same structure, and tries are very good at contiguous keys.
The trie has a fan-out of 256, eight bits per level. A key is the stream ID and sequence number together, 128 bits. With one stream in use, the first level has one slot taken out of 256, and below it is a field of zeros, since nothing has arrived yet. Patricia folds those zeros into a single layer. At the bottom, messages 0 through 255 fill one node, and message 256 starts the next. One small node per 256 messages.
The log is the storage
The entire store is a single append-only file. There is no separate index file and no write-ahead log, because the index is folded into the data. The write-ahead log is the log, and the log is the storage.
Trie nodes are serialized column-packed and appended to the same log as the messages, as messages in their own right. Because the keys are contiguous, column-packing their differences mostly encodes zeros. The overhead is under eight bytes per message.
If you want an append-only system, your indexing should be append-only as well.
Anatomy of a write
A message arrives and is appended to the current segment. Data is divided into segments, say a gigabyte each. The segment number and the offset together make a location, and the location is what goes into the trie. The trie stores nothing but locations.
The updated trie node is now dirty. At some point it is written to the log, but only once it has no dirty children. Writing it yields a location, which goes into its parent, and now the parent is dirty. The process climbs until the root is written.
The root has no parent, so its location is kept in hand. From it, the whole index is reachable. Each root on disk also stores the location of the previous root, so the log holds a chain of roots. Each is a complete, self-consistent picture of the trie at that moment, which gives point-in-time recovery for free.
Recovery after a crash is short. Open the file and find the last root written. Discard the index entries above it, find the messages there, and re-index them into the in-memory trie. Nothing else on the disk needs checking.
The same structure is also a key-value store. Keys are not limited to 128 bits and can be arbitrary strings.
Convexity and retention
There is one more property, and it follows from the order of writes. Anything that holds a location was written after the thing it points to. Every pointer points back into the past.
So when retention drops the oldest segment, no index entry breaks. Only the messages in that segment are gone, which is the point of dropping it. A lookup that lands on a removed segment simply reports that the message has aged out, or that it now lives in S3. It is not on disk.
AlgoX2 calls this property of the pointers convexity: everything reachable lies within one convex region of the log. It makes retention O(1). Drop a segment, and nothing else has to change.
An LSM tree pretends data is mutable and pays for it in compaction and recovery. LST takes the stream as it is, written once and in order, and storage gets simpler at every step.
Watch the video
Want more context on the platform? Read about the product, or get in touch with us on the contact page.