SSTables work by storing entries in a fixed, sorted representation and adding enough indexing information to locate useful parts without reading the entire table. In an LSM storage engine, a new update normally produces a newer version elsewhere rather than editing an old SSTable entry in place.
SSTable commonly means sorted string table. The name does not define one universal binary format. LevelDB, RocksDB and other engines use related ideas with different layouts, features and visibility rules. This guide uses a block-based table as its main model and identifies product-specific details where they matter.
We will follow a fictional equipment-key lookup from a file-range check to a data block, then ask a harder question: even after the file contains the key, is that value actually visible to the reader? For the complete lifecycle, begin with How LSM Trees Work. The memory-to-file stage is explained in How Memtables Work.
Continue the LSM series: the complete storage lifecycle · the memory-to-file handoff · how compaction safely replaces sorted files.
The Direct Answer: An SSTable Is an Immutable Sorted Search Structure
The three words each do work. Sorted means a comparator orders entries. Searchable means metadata can guide reads toward likely locations. Immutable means the installed table’s logical contents do not receive ordinary in-place updates; changes are represented through other records and later replacement files.
LevelDB’s table-format specification gives one concrete structure: sorted entries divided into data blocks, index and metadata blocks, and a footer containing handles to important structures. The exact byte layout is an implementation contract, not the definition of every SSTable.
A useful comparison is a published reference volume with a contents page. You can open the relevant section without starting at page one. A correction appears in a later volume, and the catalogue tells you which volumes are authoritative. That last part matters: a searchable file is one component of the database, not the whole database.
Sorted by What?
The sort order comes from the engine’s comparator. It may compare raw bytes, numeric encodings or another defined key representation. Human-readable labels do not necessarily have the order people expect: ordinary lexical order places equipment-10 before equipment-2 unless the encoding compensates for that difference.
For versioned entries, the internal ordering can include both user key and version information. In our teaching model, entries are ordered by user key and then by descending sequence number. That brings versions of one key together and makes newer candidates easy to examine first.
Sorting must remain consistent from memtable iteration through file building to later reads. A file that is correctly sorted under one comparator can be unusable under another. Changing an application’s key encoding or comparison rules is therefore not a harmless display change when persisted tables already depend on the old ordering.
One File Can Hold Values, Deletions and Several Versions
Do not picture an SSTable as necessarily one current value per user key. A versioned representation may retain several values for the same key and deletion records that hide older values elsewhere.
Our example file contains camera-2 reserved at 47 and camera-2 available at 41. The older version may remain necessary for a snapshot at 45. Another source can contain camera-2 deleted at 52. The file’s contents are meaningful only when interpreted alongside the read sequence and other relevant sources.
LevelDB’s implementation notes explicitly describe values and deletion markers in sorted tables. The broader principle is that physical entries are evidence used to construct a logical view. Counting entries is not necessarily counting currently visible user records.
Data Blocks Make a Large File Readable in Pieces
A block-based table partitions the sorted entry sequence into data blocks. A point lookup can read a candidate block rather than the whole file. A scan can continue through blocks in order.
Block boundaries are storage decisions, not business-key boundaries. Two nearby keys can share a block. A very large value can dominate a block. Depending on the format, versions of one key or other structures may require special boundary handling.
The RocksDB block-based table format separates data blocks from metadata such as indexes and filters. This is a concrete file organisation, not a promise that every SSTable uses the same block size, compression method or arrangement. Those decisions should be checked against the deployed format version.
The Block Index Is a Map of Candidate Ranges
A sparse index can associate a boundary key with a handle to a data block. Search chooses the block whose key interval can contain the query. The handle describes where the block begins and how much data to read.
The index is not necessarily a second complete copy of every key-value entry. Its purpose is to reduce the search space. A compact separator can be sufficient if it distinguishes one block’s range from the next under the comparator.
RocksDB’s Index Block Format documents its representation choices. For reasoning, keep the contract simple: every supported query must reach a block that could contain the relevant entry, or correctly conclude that the table cannot provide one. A locally sorted index with a wrong block handle still breaks lookup.
Worked Lookup: Find Key 47 Without Scanning Every Block
For this illustrative file, block A contains keys 10 and 20, block B contains 35 and 47, and block C contains 60 and 90. Define the teaching index to store each block’s maximum key: 20 points to A, 47 points to B and 90 points to C.
To search for 47, find the first index boundary not smaller than 47. That is 47, so read B and compare its entries. The key is present. To search for 46, the same routing selects B, but exact comparison reports no matching key. To search for 91, no index boundary qualifies, so the file cannot contain it.
The first stage finds a possible location; the second proves equality or absence. The boundary numbers and block contents are invented for teaching. Real formats may use shortened separators or different index structures while preserving the same routing obligation.
A Footer Helps the Reader Discover the Index
If the data blocks have variable lengths, a reader cannot assume the index begins at one fixed offset from the start. A known trailer or footer location can provide handles to the important metadata structures.
LevelDB’s documented format uses a fixed-length footer at the end of the file to identify its index and metaindex blocks. The metaindex points to named metadata blocks. That arrangement lets a reader discover the file’s navigation structures without walking through every data block.
The explanatory lesson is recursive: the data needs an index, and the index needs a discoverable starting point. A file format must eventually provide a small, dependable anchor from which the rest of its structure can be interpreted. Corrupt or incompatible footer information is therefore a read error, not ordinary evidence that a requested key is absent.
Prefix Compression and Restart Points
Sorted neighbouring keys often share prefixes. Instead of storing equipment-camera-001 and equipment-camera-002 in full, a format can encode part of the second key relative to the first. This reduces repeated bytes.
The trade-off is dependence: decoding a key may require earlier information. Restart points periodically store enough independent information to begin decoding without replaying the entire block from its first entry. A search can locate a suitable restart region and then perform a bounded local decode.
The exact encoding belongs to the file builder and reader. The general design problem is to save space without making every random lookup a long decompression walk. Test short keys, long shared prefixes, empty suffixes and boundaries around restart points; these cases exercise assumptions that a file full of unrelated integer keys does not reveal.
Compression Trades Storage Movement for CPU Work
Block compression can reduce the bytes fetched from storage and the bytes retained on disk. Reading then requires decoding the compressed representation. The balance depends on device speed, CPU availability, key/value redundancy and caching.
RocksDB supports choices described in its Compression documentation. Do not translate support for several codecs into a universal statement that the strongest compression setting always gives the best database performance.
In a toy cost comparison, reading a smaller block can save storage time while adding decoding time. Whether that is beneficial depends on which resource is scarce. A benchmark should hold the workload, cache state and correctness guarantees constant, then report both bytes and latency. Compression ratio alone does not measure the user’s experience of the storage engine.
Bloom Filters Answer a Narrow Question
A membership filter asks whether the queried key representation could occur in its covered data. Under correct construction, compatible key semantics and intact data, a negative result permits skipping that covered source. A positive result requires further examination and can be a false positive.
The filter does not return the value, prove that the version is current or resolve a deletion in another source. It also does not make a key-to-value mapping like a hash table.
RocksDB’s filter documentation distinguishes whole-key and prefix behaviour. The practical question is what was inserted into the filter and what query is being tested. Testing a full key against a filter built for a different representation without the required transformation breaks the guarantee on which skipping depends.
A Filter Hit Is Not a Visible-Record Hit
Suppose SSTable A physically contains camera-2 available at 41. Its filter correctly says camera-2 may be present. Another table contains the deletion at 52. A latest read must return absence even if the old file’s filter is a true positive.
There are therefore several different hit rates: filter positives, actual entries found in the file, entries eligible for the snapshot, and final values returned to the application. Combining them under one metric called hits can hide where extra work occurs.
An effective diagnostic records which stage rejected the candidate. A filter false positive points toward membership-filter economics. Finding many obsolete versions points toward version retention or compaction layout. A positive physical lookup followed by a visible tombstone is correct behaviour, not a failed filter.
Ordinary Bloom Filters Are Not General Range Indexes
A request for every key between 40 and 80 is not equivalent to asking whether one particular key exists. A negative test for 40 does not prove that 47, 60 or 79 is absent.
File-range metadata and ordered indexes help position range scans. Prefix filters can help supported prefix-scanning modes when their semantics fit. Specialised range filters exist, but their guarantees are not the guarantees of an ordinary key-membership Bloom filter.
Use the earlier toy file. Key 40 is absent, but block B contains 47 and block C contains 60. An implementation that skips the whole range because 40 fails a membership test would lose real results. This counterexample is simple enough to include in a test suite and strong enough to expose a mistaken optimisation immediately.
File-Range Metadata and Block Indexes Operate at Different Scales
Before opening or searching a table, the engine may know its smallest and largest relevant keys. If a query lies outside that interval, the file can be excluded. Inside the interval, the table’s block index narrows the location further.
These are nested filters on the search space: choose candidate files, choose candidate blocks, then compare entries and resolve versions. A broad file interval does not prove the key exists. A narrow block interval does not remove the need for exact comparison.
Compaction layout affects the first stage. In a non-overlapping sorted run, a key can map to a small number of file candidates. With many overlapping runs, several files can remain possible. A brilliant block index cannot remove the cost of consulting many genuinely overlapping file ranges.
Partitioned Indexes and Filters Control Metadata Loading
A very large file can have a large index or filter. Loading the entire metadata object for one small lookup may be wasteful. Partitioning divides metadata into smaller pieces and uses another navigation layer to locate the relevant piece.
RocksDB’s Partitioned Index/Filters guide describes this design. It changes memory and I/O behaviour without changing the logical key-value contents of the table.
Again there is no free setting. More partitions can reduce the amount loaded for a small read while adding metadata lookups and bookkeeping. The right measurement is the workload’s actual metadata misses, data-block reads, cache pressure and latency. File size alone is not enough to choose the layout intelligently.
The Block Cache Changes the Meaning of a File Read
A logical request to read a table block does not necessarily perform storage I/O. The engine may already hold the block or relevant metadata in memory. The operating system can also cache file pages, depending on the I/O mode.
RocksDB’s Block Cache documentation describes a cache for table reads and distinguishes compressed and uncompressed caching choices. This is separate from the memtable that receives recent writes.
A warm-cache benchmark can therefore hide the physical costs that appear after restart or under memory pressure. Report the cache conditions. Ask how many logical block requests occurred, how many missed the engine cache and how much storage traffic resulted. Without those distinctions, a statement that an SSTable lookup reads one block can be mistaken for a claim about one physical device operation.
Checksums Detect Damage; They Do Not Explain the Correct Value
Checksums can help detect unexpected changes to stored bytes. A failed integrity check should surface as corruption or an I/O-related error according to the engine’s contract, not silently become key-not-found.
RocksDB documents full-file checksums and checksum handoff. Block-level and file-level checks serve different coverage and verification needs. Neither a checksum nor a successful parse proves that the table belongs to the correct database version.
Imagine an intact SSTable from an obsolete backup copied into the live directory. Its checksum can be correct and its entries sorted, yet using it as current state can be wrong. Integrity of bytes, identity of the file and authority of the file set are three different questions. Reliable readers and recovery tools must keep them separate.
Immutability Is Not Immunity to Corruption
Immutable describes the intended update model. Storage hardware can fail, transfer operations can truncate data, administrative actions can remove files and software bugs can write the wrong bytes. An immutable table still needs validation and a recovery strategy.
The advantage is that ordinary readers do not have to track an individual entry changing in place while they decode the same installed file. New logical state appears in other representations. That simplifies some concurrency relationships while moving complexity into version resolution and file lifecycle management.
Do not overextend the word into a backup claim. An immutable file on one failing device is still one vulnerable copy. Snapshot, replication and backup mechanisms need separate specifications describing which failures they cover and how a consistent database image is reconstructed.
Building a File and Installing a File Are Separate
A builder receives entries in the required order, writes data blocks, builds indexes and filters, finalises metadata and closes a complete output. The storage engine then needs to install that output into its recognised file set using the appropriate durability protocol.
RocksDB’s MANIFEST guide describes how file-set changes are recorded. An output left by an interrupted job is not automatically live just because its filename has the expected extension.
The safe publication model retains existing sources until a complete replacement is installed. Readers use a coherent file-set view. After installation, old files may remain temporarily because readers or recovery obligations still reference them. This overlap is intentional. A replacement protocol should prevent a visibility gap, not insist that only one physical copy exists at every instant.
File Creation Time Must Not Become Version Priority
Suppose compaction today writes camera-2 available at sequence 41 into a new file because a retained snapshot still needs it. Another file contains reserved at 47. The freshly created file does not make available the newest logical value.
The reader must use the engine’s version semantics, not the operating system’s last-modified timestamp. Copying a file, restoring it from backup or rewriting its compression also changes physical facts without creating a new business update.
This is a useful test for any explanation of immutable storage: can it distinguish the age of a container from the age of the information inside? If not, its treatment of compaction, snapshots and recovery will eventually contradict itself. Physical reorganisation must preserve the logical order that readers rely on.
Range Scanning One SSTable
Within one table, an iterator can seek near the lower bound using its index, decode the candidate block and move forward through entries and subsequent blocks. The table’s local order makes continuation possible without restarting from its beginning.
For the toy table, scanning 36 through 65 starts in block B. Key 35 is below the lower bound, 47 qualifies, then block C supplies 60. Key 90 exceeds the upper bound, so the local scan stops.
That local result is not automatically the database result. Other files can contain a newer value or a deletion for 47. A complete LSM range iterator must combine the relevant sources and apply visibility rules. This separation between a table iterator and a database iterator prevents a common conceptual shortcut.
Range Scanning Several SSTables
Consider three sorted sources. One contains keys 10, 47 and 90; another contains 20, 47 and 60; memory contains a deletion of 47 and a value for 70. A merged scan must gather the candidate versions for 47, choose the visible operation and suppress the key if that operation is the deletion.
A priority queue can help select the next entry among sorted streams. In a simplified implementation with r streams and E examined entries, stream selection can cost on the order of E log r comparisons. This is an algorithmic model, not a universal engine latency formula.
E can exceed the number of results because several physical entries may represent one logical key or no currently visible key. A performance report should distinguish entries examined, keys returned, blocks fetched and bytes transferred. Each quantity answers a different question about scan efficiency.
External SSTable Ingestion Has a Strict Contract
Some engines allow a separate tool to build sorted-table files and later ingest them. This can be useful for bulk loading, but it is not permission to manufacture arbitrary files and drop them into the database directory.
RocksDB’s Creating and Ingesting SST Files documentation specifies a supported mechanism. Comparator compatibility, key ordering, file format and ingestion visibility must match the engine’s rules.
The general principle is that an externally produced table has two acceptance stages: is the file internally valid, and can it be installed without violating the target database’s logical state? Passing the first does not imply the second. Ingestion is a database operation with semantics, not a filesystem naming convention.
SSTable Does Not Mean One Identical File Across All Engines
LevelDB and RocksDB provide one family of block-based examples. Apache Cassandra uses SSTable terminology within its own storage engine, with multiple associated components and partition-oriented semantics. A shared name does not make these formats interchangeable.
Cassandra’s compaction overview describes merging sorted partition data and choosing current column versions under its timestamp rules. That is different from treating the sequence-number catalogue model here as a complete Cassandra specification.
When using diagnostic tools or planning imports, identify the exact engine and file version. A successful explanation of the general structure is not enough to justify reading, rewriting or deleting production files with a tool intended for a different format.
Small and Large SSTables Have Different Costs
Many small files can increase metadata, file-handle and candidate-search overhead. Very large files can make metadata objects large and change the granularity of compaction, caching and transfer.
Neither observation proves a universally optimal file size. A workload concentrated in a narrow hot range differs from one scanning long cold ranges. Value size, compression, block size, partitioned metadata and storage bandwidth all affect the outcome.
Use a controlled experiment. Hold the logical dataset, workload and memory budget constant. Change one file-layout parameter, then measure candidate files, metadata loading, data-block reads, tail latency and maintenance work. A file-count reduction alone can look successful while increasing the amount of unrelated data read or rewritten.
Immutable Files Can Outlive Their Place in the Current View
After compaction installs replacements, an older reader may still reference the previous file-set version. A backup operation may also require particular files. The engine must not reclaim a file while an allowed consumer still depends on it.
This means “obsolete for new reads” and “safe to delete physically” are separate states. File-retention metrics should distinguish the reason a file remains: active membership, ongoing job output, pinned reader, backup dependency or recovery requirement.
The same distinction explains why manually deleting old-looking SSTables is unsafe. The administrator may see a timestamp; the engine tracks a dependency graph. Cleanup must follow that graph. A data file is not disposable merely because another file with overlapping keys was created later.
Corruption Must Not Be Reported as Ordinary Absence
Suppose a block cannot be decoded or fails its checksum. Returning not-found would hide a storage failure inside a legitimate query outcome. The application could then create a duplicate object or make an incorrect decision based on missing data.
Similarly, a missing file named by the live manifest is not equivalent to a healthy file whose range excludes the key. One is a violated storage dependency; the other is valid pruning information.
A clear reader interface distinguishes value, logical absence and failure. Test each independently. Remove or damage files only in a controlled disposable test environment, then verify that the engine reports the expected failure rather than silently changing the logical database. Reliability depends on errors remaining visible.
A File-Reader Test Plan
First test ordering and exact lookup on tiny files. Include an empty table where supported, one entry, duplicate user keys with different versions, keys at block boundaries, empty values and keys absent between existing entries.
Then test format boundaries: compressed and uncompressed blocks, restart points, large values, metadata partitions, truncated footers, invalid handles and damaged checksums. The expected result for malformed structure is a defined error, not arbitrary output.
Finally test integration. Install several overlapping files, keep an older snapshot, add a newer tombstone and compare reads before and after compaction. A reader can pass every single-file binary-search test and still return the wrong database view if it combines file results incorrectly. Local parsing and global visibility require separate proofs.
What to Measure Before Tuning
For point reads, count candidate tables, useful filter negatives, exact entries found, block-cache misses and storage bytes. For scans, count sources merged, physical versions examined, visible keys emitted and blocks prefetched. For memory, separate data blocks from indexes and filters.
Label warm and cold conditions. A repeated read of the same key can become a cache experiment rather than a table-format experiment. Also label successful and unsuccessful lookups, because negative queries can benefit from filters differently from queries that genuinely occur in many files.
These measurements connect tuning to mechanism. If metadata loading dominates, investigate metadata partitioning or cache policy. If many files genuinely contain older versions, investigate layout and retention. If decoding dominates, investigate block encoding and compression. Avoid changing all three at once and losing the ability to identify what helped.
Frequently Asked Questions
Is an SSTable just a sorted text file?
No. It is a sorted-table representation, commonly binary and accompanied by navigation and integrity metadata. The term does not require human-readable text or one standard layout across storage engines.
Does immutable mean it never changes physically?
It describes the intended logical update model of an installed table. Ordinary updates create newer state elsewhere. Files can still be copied, replaced, corrupted or deleted under lifecycle rules; immutability is not protection against every physical event.
Why can one key appear more than once?
The file may retain versions required by snapshot or transaction semantics. A reader chooses the eligible version according to the engine’s rules rather than assuming every physical entry is a separate current record.
Does a positive Bloom-filter result prove the value exists?
No. It can be a false positive, and a physically present entry can also be obsolete or hidden by a deletion. Exact lookup and database-level visibility checks are still necessary.
Can a sorted table answer a range without a full scan?
It can seek near the lower bound using its index and scan forward until the upper bound. A database-wide range may still need to merge several tables and memory sources, so one file’s range result is only part of the answer.
Is the newest file always the source of the newest value?
No. Compaction can put older logical versions into a newly created file. Logical sequence or timestamp rules determine priority, not filesystem creation time.
Sources, Scope and Further Reading
The LevelDB table-format document anchors the simple block-file model. RocksDB’s official format, index, filter, compression, cache, checksum, manifest and ingestion references explain concrete refinements. Cassandra is included to show that shared SSTable terminology does not imply interchangeable binary formats or identical version semantics.
The numeric block examples are intentionally small and invented. They demonstrate routing, exact comparison and range termination without making performance claims about a particular engine. Continue with the LSM master guide or the How X Works library.
Final Synthesis: The File Finds Evidence; the Database Decides Visibility
An SSTable makes immutable sorted evidence efficient to navigate. Data blocks hold entries, indexes identify candidate regions, filters avoid unnecessary checks and integrity metadata helps detect damage. These mechanisms reduce the work required to inspect a file.
The final answer still depends on the surrounding database: which files are live, which versions the reader may see and whether a newer value or deletion exists elsewhere. Keeping that boundary clear is the key to understanding SSTables. A fast file lookup is valuable, but only a correct combination of file evidence produces a trustworthy read.