SSTables - Sorted String Tables

immutable on-disk “Map” implementation

SSTables (Sorted String Tables) are an immutable data structure used in databases, especially those designed for high write throughput and large-scale data management like Apache Cassandra and LevelDB.

An SSTable contains a set of sorted key-value pairs and is written to disk in a single pass.

Key Characteristics of SSTables

Immutability: Once an SSTable is written to disk, it is never modified. This immutability simplifies concurrency control and ensures data consistency.

Sorted: Keys in an SSTable are stored in a sorted order. This property allows efficient range queries and quick lookups.

Efficient Writes: Since SSTables are written in bulk and not modified later, write operations are fast.

Efficient Reads: The sorted nature of SSTables enables binary search for key lookups, making read operations efficient.

Compaction: Over time, multiple SSTables are merged (compacted) into fewer, larger SSTables to reclaim space and reduce read amplification.

Structure of an SSTable

Data File: Contains the actual key-value pairs.

Index File: Provides an offset for each key, allowing for efficient lookups.

Bloom Filter: A probabilistic data structure that helps quickly determine if a key is not present in the SSTable.

Summary File: A reduced index that allows for quick binary search in the index file.

Writing Data:

Data is initially written to a memtable (an in-memory structure).

Once the memtable reaches a certain size, it is flushed to disk as a new SSTable. This new SSTable is immutable and will not be modified.

Reading Data:

To read a key, the database first checks the bloom filter to see if the key is likely present in the SSTable.

If the bloom filter indicates the key might be present, the index file is consulted to find the offset of the key in the data file.

The data file is then accessed at the given offset to retrieve the value.

Compaction:

Over time, multiple SSTables can accumulate, which may lead to increased read latency.

The compaction process merges these SSTables into fewer, larger SSTables, discarding deleted data and redundant entries.

This process reduces the number of SSTables that need to be checked during read operations, improving read performance.

Use Cases

NoSQL Databases: Databases like Apache Cassandra and HBase utilize SSTables for their storage engines.

Log-Structured Merge-Trees (LSM-Trees): SSTables are a key component of LSM-Trees, which are used in storage systems requiring high write throughput.

SSTables are fundamental to the performance and scalability of modern distributed databases, providing a robust solution for handling large volumes of data efficiently.