Data Blocks: The Unit of I/O

Inside an SSTable, keys aren't stored one-by-one — they're packed into blocks of a few KiB each. A block is the unit of compression, the unit of caching, and the unit of disk I/O.

Block Boundary Decisions

LevelDB and RocksDB target ~4 KiB per block by default. When the writer is appending sorted entries, it tracks bytes written into the current block. Once the running size exceeds the target, the next entry starts a new block.

A block always contains at least one entry, even if that entry is bigger than block_size. Such over-sized blocks are rare but unavoidable for very large values.

Inside a Block

A simple block format:

| 4B count | (klen|key|vlen|value)* | 4B crc |

LevelDB uses prefix compression within a block: every entry stores its key as a (shared_bytes, unshared_bytes, value_len, unshared_key_bytes, value_bytes) tuple, where shared_bytes is the count of bytes shared with the previous key. For sorted data this saves a lot — consecutive keys like user:00001, user:00002 share 6 bytes.

To allow binary search within the block, LevelDB inserts a "restart" full key every N entries (default 16). The block trailer holds an array of restart offsets. Binary search jumps to a restart point, then linear-walks forward.

Per-Block Checksum

Every block ends with a CRC32 (or xxHash64 in modern systems) of the compressed bytes. On read:

1. Read the block bytes from disk.
2. Verify the CRC. If bad — bit rot. Fail the read or fall back to another replica.
3. Decompress.
4. Search.

This is how RocksDB and LevelDB detect silent disk corruption.

Compression

Each block is independently compressed (snappy, zstd, lz4, zlib). Independent compression matters because we want random block access; if blocks were chained, reading block N would require decompressing blocks 0 through N.

Snappy was LevelDB's default — fast, modest ratio (~2x). RocksDB defaults to LZ4 for L0/L1 and Zstd for deeper levels (better ratio for cold data, where decompression cost matters less).

Block Cache

The OS page cache holds raw file bytes. A higher-level block cache holds decompressed blocks. RocksDB's block cache is typically 1-8 GiB on production. A hit returns parsed entries with no decompression cost.

LRU is the canonical eviction policy. RocksDB has more sophisticated policies (Clock, LRU+LFU hybrid).