ScyllaDB's trie-based SSTable index

ScyllaDB 2026.2 makes a trie-based SSTable index the default, replacing the flat Summary.db + Index.db pair that the me/md formats used. The format shipped in 2025.4 and is on-disk compatible with Apache Cassandra's BTI (Big Trie Index), reimplemented on Seastar. Across four read workloads the authors report 30% to 230% more throughput and 31% to 63% lower latency, with the write path essentially unaffected.

What the legacy path did

A lookup in me/md walks three structures. Summary.db is held entirely in RAM, sampled at roughly one entry per 2000 bytes of Data.db, and a binary search over it narrows the key to a window in Index.db. That window gets read off disk and scanned — on the order of 800 entries per megabyte — to find the partition key and its Data.db offset. Then one seek plus a sequential read into Data.db.

Partitions with many clustering rows add a fourth structure: a promoted index stored inside the Index.db entry, a flat list of clustering-key blocks with start/end keys and offsets, binary-searched.

Two costs stand out. Summary.db is always resident and never evicted, so it consumes memory whether or not the workload needs it. And every Index.db entry stores its key in full, so identical prefixes are paid for once per key.

What replaced it

The ms/mt formats drop both files and add two:

Partitions.db holds one trie mapping partition key to a Data.db offset (small partitions) or a Rows.db offset (large ones), followed by a footer carrying first_key, last_key, partition_count, and trie_root_pos. Rows.db holds per-partition clustering-key sub-tries concatenated together, each mapping a clustering key to a byte offset within its partition — this is what replaces the promoted index. Data.db, Filter.db, Statistics.db, and Scylla.db are byte-for-byte unchanged.

Keys go through bti_key_translation.cc first, which converts them into a comparable byte sequence whose lexicographic order matches CQL semantic order. That's what lets a byte-at-a-time structure serve range queries correctly for typed columns.

The page-packing trick

The interesting engineering isn't the trie, it's the write-time layout. The trie_writer keeps the rightmost root-to-current path on a stack, branches off it for each new key, accumulates nodes until a finished subtree would exceed a page, and then flushes child subtrees with padding so that each subtree fits inside a single 4 KB page. A node and its children land on the same page, so an entire trie neighborhood arrives in one I/O even on a cold read. Parents are written after their children, because a parent has to know where its children ended up. Fan-out is up to 256.

A typical partition lookup costs two to six page fetches, and since the top pages stay in the OS page cache it is often zero or one actual disk I/O.

ScyllaDB also diverges from the Cassandra reference implementation on node granularity. Cassandra stores one character per node; ScyllaDB groups characters into chains of up to 300 bytes. Same read-side page structure, dramatically faster writes for long keys.

The memory story inverts. Legacy had a summary that was always loaded and never evictable. The trie has no dedicated in-memory component at all — its top nodes live in the OS page cache like anything else, and can be evicted under pressure.

Benchmarks

Three i8g.2xlarge nodes on AWS, RF=3, three racks, measuring maximum throughput at which client-side P99 stays under 10 ms.

Test 2 was designed to favor the trie: partition key only, no clustering columns, ~8 bytes of effective payload per row, 650M rows. Prefix compression makes the index dense enough that the same page cache budget covers roughly 3x more trie top-nodes than the equivalent Index.db window. Test 4 was designed against it — 2048-byte clustering keys with a long common prefix so only the trailing bytes differ, which maximizes depth and erodes prefix sharing — and the trie still won by 73%.

The appendix numbers are slightly more conservative than the headline table in two cases (Test 2 is stated as >280k ops/s and >+211%; Test 3 as ~30k ops/s and +50%), which is worth knowing if you're quoting them.

Even at equal load the latency picture changes: in Test 1, at the same 130k ops/s, trie P99 is 3.19 ms against legacy's 6.28 ms.

Why it wins, and when it doesn't

Avi Kivity's summary is three effects. The index is denser, so more of it fits in cache and more lookups need no index I/O at all. When it does miss, the structure is more compact and shallower, so fewer I/Os are needed — most pronounced for large partitions, which show up constantly in materialized view workloads. And less CPU is spent processing the index on the read path.

The monitoring evidence for the first point: at identical throughput, legacy indexes drove ~240 MB/s of disk reads, trie indexes ~33 MB/s. About one seventh of the storage bandwidth.

The cost is CPU during memtable flush and compaction, since building a trie is more work than writing a sorted list. The authors judge this more than repaid on the read side.

The honest boundary condition: at a 100% cache hit rate or a 0% cache hit rate the index format barely matters, because in the first case nothing touches the index and in the second everything misses regardless. The gains live in the middle, which is where production workloads actually sit.

Related

lsm-tree for what SSTables are and why an immutable sorted file needs an index at all — the skip-list MemTable is the write-side half of the same design. levenshtein-trie uses the same prefix-sharing property for a different purpose, fuzzy dictionary lookup, and is a good companion for the shape of the structure itself.