I built an SSTable storage engine

Hello people!

I've been working on a project called Stryx — github, for a couple of weeks. I don't really have a motivation for as to why I built it — I read about "Sorted String Tables" somewhere, found them cool, coincidentally at the same time I'd been itching to build something involving binary formats. So I thought it would be fun, and here we are.

Contents

Part I: Background

1. What's an SSTable?
2. Designing the Stryx Table

Part II: The File Format

1. How Records are Stored
2. Index
3. Filter
4. Footer, and How open() Works

Part III: Reading and Writing

1. The Whole Flow: get(b"cherry")
2. Building a Table
3. Reading Records

Part IV: Behavior, Performance and Getting started

1. Compression, Concurrency and Caching
2. Benchmarks
3. Limitations
4. Getting Started

---

If you'd rather see the format before reading about it, I built an interactive explorer that walks through the exact byte layout described below —

→ Explore the Stryx table format

---

Part I: Background

1. What's an SSTable?

• It's essentially a file-based storage format that stores key-value pairs in sorted order. The records are arranged lexicographically by their keys, which makes looking up records and performing range queries efficient compared to scanning an entire file.

• SSTables are immutable, meaning that once the table has been written and finalized, its contents aren't modified (new data is written into a new table). This makes the format relatively straightforward to read concurrently and also avoids the complexity of managing in-place updates.

• They're commonly used as building blocks in storage engines and databases, often alongside structures such as memtables. Systems like RocksDB and LevelDB use this general approach.

For Stryx, I wanted to explore this storage model at a lower level: how records are encoded, organized into blocks, indexed, fetched, their metadata, and so on.

2. Designing the Stryx Table

A Stryx table is a single file that you write once and never touch again. Records are sorted by key, grouped into blocks, and a small amount of metadata at the end of the file describes how to find everything.

The reader starts by locating the footer at the end of the file, which tells it where the other sections are (all integers are little-endian). Both the metadata section and the optional filter section are prefixed with an 8-byte little-endian length, which lets the reader seek past one to find the next.

+------------------------------------------+
| data block 0 ... data block N-1          |  Sorted records, optionally compressed
+------------------------------------------+
| index                                    |  First key, offset, and size per block
|                                          |  Entry count + CRC32C
+------------------------------------------+
| metadata (length-prefixed)               |  Record count, block count, key range,
|                                          |  compression, file size, index location
+------------------------------------------+
| filter section (optional, len-prefixed)  |  Binary Fuse filter + CRC32C
+------------------------------------------+
| footer (29 bytes)                        |  Index offset/size, filter type, version, magic
+------------------------------------------+
 ^                                          ^
 |                                          |
file start                            file end (footer starts at len - 29)

To understand how the rest of the format works, let's start with how a single record is represented.

---

Part II: The File Format

3. How Records are Stored

For this walkthrough let's take these three records:

Key     Value
apple   red
banana  yellow
cherry  red

First record (encoded): key apple and value red.

record = [key_len: u16][value_len: u32][key][value]

Field	Value	Bytes	Why it exists
key_len	5	05 00	Keys are variable-length, so the reader needs to know where the key ends. A u16 allows keys up to 65,535 bytes.
value_len	3	03 00 00 00	Same idea for the value. A u32 allows values up to 4,294,967,295 bytes.
key	apple	61 70 70 6c 65	The raw key bytes, which are compared lexicographically.
value	red	72 65 64	The raw value bytes. Stryx doesn't interpret them.

That's 6 bytes of header plus 8 bytes of payload, so 14 bytes in total. Notice that the integers are little-endian: 5 as a u16 is 05 00, with the low byte first. Both keys and values are opaque bytes, so there is no schema and no type information in the format.

Records Inside a Block

Writing records one after another is straightforward, but there's a small problem: records are variable-length, so you can't jump straight to the second record without knowing where it starts.

That's why Stryx groups records into blocks and keeps an offset table for each block. The block also stores a record count and a checksum:

[record 0][record 1] ... [record N-1]
[offset 0: u32] ... [offset N-1: u32]
[record_count: u32][crc32c: u32]

Here is a block holding apple and banana:

Block layout

byte 0                                      byte 32
  |                                            |
  v                                            v
  +------------------+------------------------+
  | apple record     | banana record          |
  | 14 bytes         | 18 bytes               |
  +------------------+------------------------+
  | offset 0 = 0     | offset 1 = 14          |  8 bytes
  +------------------+------------------------+
  | record_count = 2                          |  4 bytes
  +-------------------------------------------+
  | CRC32C                                    |  4 bytes
  +-------------------------------------------+

  Total block size: 48 bytes

The record area is 32 bytes. The offset table takes another 8 bytes, followed by 4 bytes for the record count and 4 bytes for the CRC32C, making the entire block 48 bytes.

Each part does the following:

• Offset table: lets the reader binary-search within the block. It jumps to the middle record, reads its key, compares, and repeats. Without it, a lookup would have to scan the block.

• record_count: sits at a fixed position at the end, so the reader can read backwards from there and find the offset table.

• crc32c: computed in finish() over everything before it (records, offsets and count) and appended last. It catches accidental corruption such as bit rot or a truncated write.

How Big Is a Block?

Records are packed into blocks until the next record would exceed the configured block_size target. A record is never split across blocks, so blocks are approximately the target size rather than exactly that size. A single record bigger than the target simply gets a block of its own.

Since the records are sorted, each block can be represented in the index by its first key. That brings us to the next part of the format.

4. Index

A table with a million records might have thousands of blocks, and the reader needs to know which one to read. The index answers that. It is sparse, with one entry per block rather than per record. Each entry holds:

+-----------------------------+
| key_len                 u16 |
+-----------------------------+
| first_key             bytes |
+-----------------------------+
| offset                  u64 |
+-----------------------------+
| size                    u32 |
+-----------------------------+
| uncompressed_block_size u32 |
+-----------------------------+

                  Index
+------------------------------------------------+
| Entry 0                                        |
|                                                |
| first_key:              "apple"                |
| offset:                 0                      |
| size:                   48                     |
| uncompressed_block_size: 48                    |
|                                                |
+------------------------------------------------+
| Entry 1                                        |
|                                                |
| first_key:              "cherry"               |
| offset:                 48                     |
| size:                   27                     |
| uncompressed_block_size: 27                    |
|                                                |
+------------------------------------------------+

                    |
                    | Each entry points to a block
                    v

+----------------------+----------------------+
| Block 0              | Block 1              |
| apple ...            | cherry ...           |
+----------------------+----------------------+

For our example table, assuming no compression:

Entry	First key	Offset	Size	Uncompressed size
0	apple	0	48	48
1	cherry	48	27	27

The total encoded size of an entry is 2 + key_len + 8 + 4 + 4 bytes. The index is serialized with its entry count and a CRC32C checksum. The reader uses it to find the candidate block without having to scan all the data blocks.

How the Reader Finds the Block

Each entry identifies a candidate block based on its first key. The reader finds the last index entry whose first key is less than or equal to the requested key.

Looking up cherry

• Binary-search the index for the last first-key ≤ cherry.

• apple ≤ cherry and cherry ≤ cherry, so entry 1 wins.

• Read 27 bytes at offset 48. That's block 1.

• Binary-search its offset table, and cherry is there.

For this example, only one block is read. Two other cases follow from the same rule:

• blueberry (not in the table): the last first-key ≤ blueberry is apple, so the reader reads block 0, searches it, finds nothing, and returns None.

• aardvark, which sorts before every first key: no entry qualifies, so there is no block to read and the answer is None straight away.

5. Filter

The index can only answer "which block would hold this key?", not "is the key present?". A missing key still costs an index search and potentially a block read. The optional filter exists to skip that work.

At finalize(), Stryx hashes every key into a u64 (xxHash3 with a fixed seed), sorts and deduplicates those hashes, then builds a Binary Fuse filter (8, 16 or 32 bits per key, from the xorf crate) over the distinct hashes. Before touching the index, the reader asks it:

• "Definitely absent" → returns None immediately, without loading a data block.

• "Maybe present" → carries on to the index.

A false positive only wastes an index search and potentially a block read, because the block's binary search always has the final word. A filter can never cause a wrong value to be returned. Fuse8 is the smallest, and Fuse16 and Fuse32 spend more space for fewer false positives.

Filter Variants

Variant	Bits per key	False-positive rate (approx.)	Memory for 1M keys
BinaryFuse8	~9	~1 in 256	~1.1 MB
BinaryFuse16	~18	~1 in 65,000	~2.2 MB
BinaryFuse32	~36	~1 in 4 billion	~4.5 MB

The Guarantee

To make the guarantee concrete, consider looking up aardvark, which sorts before every key. The filter has never seen it, so it returns "definitely absent" and the reader returns None without touching the index at all. If the filter returns "maybe present" for a key that isn't actually there, the reader falls through to the normal index-and-block lookup and still correctly returns None. The filter can save work on misses, but it can never change an answer.

The Performance Trade-off

The performance trade-off is a little counterintuitive: hits get slower, because every successful lookup pays for a filter check first, while misses get faster because most of them are rejected before any index or block work happens. In my benchmarks, hits go from ~80 µs to ~97–99 µs per 1,024 lookups, and misses drop from ~12 µs to ~9.2–9.5 µs. That's roughly a 20% improvement on misses.

My guess is that on a warm, memory-mapped file a miss without a filter is already cheap, since it's only an index search and a block search with no real disk I/O. A filter should matter more when blocks have to come from disk, and I haven't measured that.

6. Footer, and How open() Works

The index and filter are useful only if the reader can find them. The footer is what makes that possible. It is a fixed 29 bytes at the very end of the file, at a known position:

Field	Type	Bytes
index_offset	u64	8
index_size	u64	8
filter_type	u8	1
version	u32	4
magic	bytes	8

What TableReader::open() Does

1. Read the footer. Seek to file_len - 29 and read 29 bytes.

2. Validate the magic. If it doesn't match, this isn't a Stryx file, and the reader stops here.

3. Validate the version. The format is versioned but not yet stable, so a file from an incompatible version is rejected cleanly rather than misread.

4. Locate the sections. index_offset and index_size say exactly where the index is. The metadata and filter sit after the index (the order is index, metadata, filter, footer). The metadata begins with an 8-byte little-endian length, and the optional filter section (when filter_type != None) is also length-prefixed, so both can be skipped or bounded precisely.

5. Load index, metadata and filter. These are read into memory. The index and optional filter have their CRC32C checksums verified. The metadata is validated structurally (bounds and field consistency) rather than via a checksum.

6. Prepare for lookups. The index, filter, metadata and memory-mapped file are put behind an Arc. Cloning a reader for another thread shares the table state while each reader has its own scratch buffers.

Why Opening Is Cheap

The data blocks are not eagerly read into memory during open(). The file is memory-mapped, and blocks are accessed on demand. Compressed blocks are decompressed when needed. That's why opening doesn't require reading the entire table: about 15 µs for 10,000 records, and roughly 740 µs for a million. These are from my current benchmark run.

Now that the file layout and lookup structures are established, let's follow an actual read to see how all these pieces work together.

---

Part III: Reading and Writing

7. The Whole Flow: get(b"cherry")

Requested key: cherry
        |
        v
Filter check ........ "definitely absent"? -> return None
        |  "maybe present"
        v
Index lookup ........ last first-key <= "cherry"  ->  entry 1
        |
        v
Locate data block ... offset 48, size 27
        |
        v
Load the block ...... from the block cache if present, otherwise access it through mmap
        |              decompress if needed, CRC-check on first use
        v
Binary search ....... offset table -> compare keys -> find the record
        |
        v
Decode the record ... read key_len, value_len, then the value bytes
        |
        v
Return Some(b"red")

8. Building a Table

Everything so far describes the finished file. This chapter covers how TableBuilder produces it.

let mut table = TableBuilder::create("fruit.stryx", options)?;
table.add(b"apple", b"red")?;
table.add(b"banana", b"yellow")?;
table.add(b"cherry", b"red")?;
let (metadata, stats) = table.finalize()?;

Key Ordering

The format requires sorted keys, so the builder has to get them sorted somehow. key_order picks how:

• Presorted: you promise the input is already in order. The builder checks each key against the previous one and rejects anything out of order. This is the cheap path, and records can be streamed straight into blocks without being held in memory.

• Lexicographic: you can hand over records in any order, and Stryx routes them through an external spill-sorter (64 MiB in-memory budget by default) before writing. This lets arbitrary input become sorted output without holding the entire dataset in memory.

Accumulating Records Into Blocks

Internally, a block builder holds two growing buffers: the encoded records, and a list of each record's offset. Each add() call:

• Encodes the record as [key_len][value_len][key][value].

• Notes its offset, which is the current length of the data buffer.

• Appends it to the buffer.

• Remembers the key if this is the block's first record, since that becomes the index entry.

Sealing a Block

When the block fills up, the builder seals it:

• finish() appends the offset table, then record_count, then the CRC32C of everything before it.

• The bytes are compressed if the table uses LZ4 or Zstd.

• They are written to the file.

• The block's first key, file offset and size are pushed onto the index.

• The buffers are cleared and the next block starts.

This is also why the index records each block's size. Compressed blocks have different lengths, so the reader can't work out where the next block starts from the block size alone.

What finalize() Does

The last block is usually only partly full, and the file doesn't have its index, metadata or footer yet. finalize() finishes the job. Steps 1–2 build everything in memory; steps 3–6 write the file:

1. Flush the last partial block         -> data blocks done

2. Build the filter in memory           -> Binary Fuse over the sorted, deduped key hashes, plus CRC32C
   (skipped when filter_type is None)

3. Encode and write the index           -> one entry per block, then entry count + CRC32C

4. Write the metadata                   -> 8-byte length prefix + encoded metadata

5. Write the filter section (if any)    -> 8-byte length prefix + filter data + CRC32C

6. Write the footer (29 bytes)          -> index_offset, index_size, filter_type, version, magic

The footer comes last because it needs the offsets of the sections before it. The filter is built here, not earlier, because a Binary Fuse filter is constructed from the complete set of keys in one go — it can't be extended key by key. finalize() returns the table's metadata and write statistics.

9. Reading Records

Every read operation uses the index to pick candidate blocks and the offset table to search inside them.

Point Lookups

get() follows the lookup path from earlier (filter, index, block, binary search) and returns an owned Vec<u8>.

let mut reader = TableReader::open("fruit.stryx")?;

let value = reader.get(b"apple")?;   // Some(Vec<u8>)
assert_eq!(value, Some(b"red".to_vec()));

let missing = reader.get(b"durian")?;
assert_eq!(missing, None);

Note: contains_key() follows the same path through get() and therefore materializes the value before discarding it. If you only need presence, calling get() directly is no more expensive than contains_key() — but contains_key() is not a cheaper check than get().

assert!(reader.contains_key(b"banana")?);   // true
assert!(!reader.contains_key(b"durian")?);  // false

If you only need the answer as Bytes rather than a Vec<u8>, get_in_bytes() returns the same lookup result without the extra copy.

let value: Option<Bytes> = reader.get_in_bytes(b"cherry")?;

Batch Lookups

get_many() is for looking up multiple keys together. The reader sorts the requested keys, then walks them against the index in a single pass. Keys that land in the same block can be answered from one block load, and results are returned in the caller's original order.

let keys: &[&[u8]] = &[b"cherry", b"apple", b"durian"];
let results = reader.get_many(keys)?;

assert_eq!(results[0], Some(b"red".to_vec()));     // cherry
assert_eq!(results[1], Some(b"red".to_vec()));     // apple
assert_eq!(results[2], None);                      // durian

get_many_in_bytes() does the same thing but returns Vec<Option<Bytes>>.

let results: Vec<Option<Bytes>> = reader.get_many_in_bytes(keys)?;

This can avoid repeatedly traversing the index and loading the same block, although sorting the requested keys also has a cost.

Range and Prefix Queries

Sorted storage is also what makes range queries possible. For a range, the reader uses the index to find the block that could contain the start key, searches the block's offset table for the first record at or after the start, walks records forward (moving to the next block when one runs out), and stops at the exclusive end bound. Only the blocks that overlap the range need to be read, and they sit next to each other in the file, so access is mostly sequential.

for record in reader.range(b"apple", b"cherry")? {
    let record = record?;
    println!("{:?} -> {:?}", record.key, record.value);
}
// apple  -> red
// banana -> yellow
// (cherry is excluded: the end bound is exclusive)

An inverted range is rejected rather than silently returning nothing:

assert!(reader.range(b"cherry", b"apple").is_err());  // InvalidRange

prefix() provides a dedicated prefix iterator:

for record in reader.prefix(b"ban")? {
    let record = record?;
    println!("{:?}", record.key);
}
// banana

Iteration

A full scan doesn't need to search the index or the offset tables for individual keys. It decodes each block's records one after another, using key_len and value_len to move from record to record, then moves to the next block.

for record in reader.iter() {
    let record = record?;
    println!("{:?} -> {:?}", record.key, record.value);
}
// apple  -> red
// banana -> yellow
// cherry -> red

---

Part IV: Behavior and Performance

10. Compression, Concurrency and Caching

Compression

Compression is chosen once per table: None, LZ4 (fast) or Zstd (smaller). It's applied to each block separately rather than to the file as a whole. If the whole file were one compressed stream, reading one key could mean decompressing a much larger portion of the file; with per-block compression, the index points at a block and the reader decompresses that block alone. Smaller files cost CPU time on every uncached compressed block read; the block cache can avoid repeated decompression.

Concurrency

Opening a table doesn't read it all into memory. Only the small structures at the end of the file are loaded: the index, the metadata and the filter. The data blocks are accessed through the memory mapping when needed, and the OS manages which mapped pages are resident.

The shared state sits behind an Arc:

Shared across all readers (Arc)	Private to each reader
The mapped file	Scratch buffers (decompression, decoding)
Index	Read statistics (readstats)
Filter
Metadata
Block cache (if enabled)

Lookups take &mut self, so one TableReader can't be used from many threads at once. You open the table once and clone() a reader per thread. A clone only needs its own scratch buffers and an increment of the Arc reference count, so it's very cheap.

let reader = TableReader::open("data.stryx")?;

std::thread::scope(|s| {
    for _ in 0..4 {
        let mut r = reader.clone();
        s.spawn(move || { let _ = r.get(b"some-key"); });
    }
});

The Block Cache

The cache is off by default. When enabled, it keeps decoded (decompressed and verified) blocks and is shared between all clones, with a size you set in bytes. A block only enters the cache on its second load, so blocks that are read once never pay for an insert. Two threads can each decode the same cold block once before it lands in the cache, and a uniform random workload over a table much bigger than the cache gets little benefit from it.

11. Benchmarks

Single-machine microbenchmarks comparing Stryx's own configurations; I make no claims about other libraries. Point-lookup times are per 1,024 lookups.

Environment:

Intel i5-12450H, Linux 6.18.38-1-lts, Rust 1.96.0, Criterion.

Point lookups:

Operation	Config	Time	Throughput
hit	no filter	79.9 µs	12.8 Melem/s
hit	Fuse8 / 16 / 32	97.0 / 97.5 / 99.3 µs	~10.3–10.6 Melem/s
miss	no filter	12.0 µs	85.5 Melem/s
miss	Fuse8 / 16 / 32	9.5 / 9.2 / 9.4 µs	~107–111 Melem/s

Throughput, by configuration:

Workload	Config	Throughput
Sequential scan, 4 KiB blocks	None	643 MiB/s
Sequential scan, 4 KiB blocks	LZ4	461 MiB/s
Sequential scan, 4 KiB blocks	Zstd level 1	306 MiB/s
Concurrent point lookups	1 thread	11.0 Melem/s
Concurrent point lookups	2 threads	24.8 Melem/s
Concurrent point lookups	4 threads	40.0 Melem/s

Full tables — including scan times for 16 KiB blocks, opening latency at 10K/100K/1M records, and block-cache results across compression settings — are in the cargo bench harness and on the crate page.

A filter adds cost to successful lookups but helps reject missing keys — the same trade-off discussed in Filter. Four threads gave roughly 3.6× single-thread throughput on this machine and workload.

12. Limitations

• Pre-1.0 API. The format and Rust API may change between minor versions. Version is validated on open, so an incompatible file is rejected cleanly rather than misread — but expect breakage.

• Single-writer, immutable tables. There's no in-place update or delete. New records mean a new table; merging tables is left to the caller.

• No compression tuning per workload. Compression is chosen once per table and applied per block; there's no adaptive policy, and no measurement yet on cold-cache (disk-bound) reads.

13. Getting Started

cargo add stryx

Or from source:

git clone https://github.com/vamsi200/stryx
cd stryx
cargo test
cargo bench

For more details:

• docs.rs/stryx
• crates.io/crates/stryx
• github.com/vamsi200/stryx

---

And that's it — that's the whole design and inner workings of Stryx. I've omitted a few details, but this is mostly it. Thank you for reading!