hesela.devSSTable restart point
An SSTable restart point is an indexed entry that stores its full key so a reader can resume decoding a prefix-compressed block without reconstructing all preceding keys.
In LevelDB 1.23, ordinary entries can omit the byte prefix shared with the preceding key; a restart entry sets the shared-prefix length to zero. A block ends with four-byte restart offsets and a four-byte count. The directory enables indexed entry selection, not crash recovery. [1]
Seek uses binary search over restart keys followed by forward reconstruction. Next decodes the following entry; Prev returns to an earlier restart and decodes forward again. Reverse traversal can therefore do different reconstruction work from forward traversal. These are source-level operations, not measured latency or device reads. [2]
The data-block default is 16 entries between restarts. TableBuilder separately forces the index-block interval to 1, so that default must not be applied to every block. [4] [3]
Key-prefix encoding precedes optional compression of the finished block. Selecting kNoCompression skips that latter step but does not disable prefix encoding. A restart offset addresses the decoded block, not an independently readable region inside a compressed disk block. [3]
More frequent restarts trade extra offsets and repeated key bytes for shorter reconstruction spans. This layout mechanism is distinct from a prefix Bloom filter's membership predicate. Other SSTable implementations and versions may use different formats.
Relations
Advantages
- Indexed full-key entries let a reader begin reconstruction within a block instead of always starting at its first entry. [1, 2]
Limitations
- Restart spacing alone does not predict lookup latency: block caching, decompression, key distribution and iterator state also matter. [2, 3]
Citations
- LevelDB 1.23: BlockBuilder entry encoding and restart directory.
- LevelDB 1.23: Block::Iter Seek, Next and Prev.
- LevelDB 1.23: TableBuilder index options and block compression.
- LevelDB 1.23: Options::block_restart_interval and compression.
Further reading
Sources & caveats
- Source review of LevelDB tag 1.23, commit 99b3c03b3284f5886f9ef9a4ef703d57373e61be; builder, iterator, options and compression paths inspected on 2026-11-12. No engine benchmark or current-version claim.