Bitcask Explained: A Log-Structured, Fast Key-Value Store

Introduction to Bitcask

Bitcask is an embedded key-value (KV) store, recognized as one of the fastest and most efficient solutions for storing key-value pairs directly on local disk. As an embedded database, it operates within the same process as the application, eliminating the need for network calls and ensuring extremely low latency.

Origin and Context

Bitcask originated from the needs of Riak, a popular distributed database. Riak required an efficient local storage mechanism for its nodes, and Bitcask emerged as a backend option. The core inspiration for Bitcask comes from the concept of log-structured file systems, which prioritize sequential writes over random writes to maximize disk performance. This design philosophy underpins its speed and efficiency.

It’s important to note that most databases, even SQL databases, fundamentally operate as key-value stores (e.g., row ID as key, entire row as value). Efficient on-disk key-value access is a common challenge, addressed by various structures like B+ trees, LSM trees, and Bitcask.

Bitcask Architecture

At its core, Bitcask is remarkably simple:

1. A directory containing a collection of append-only data files.
2. A single, gigantic in-memory index called keydir.

The keydir (In-Memory Index)

keydir is a dense index that stores metadata for every single key present in the database. For each key, it maps to:

• The specific data file where the key’s latest value resides.
• The offset within that file where the entry begins.
• A timestamp indicating when the entry was created.

Because keydir is a dense index, if a key is not found in memory, it definitively does not exist in the database.

Data Files: Active and Immutable

Bitcask manages its data files in two states:

• Active Data File: This is the current file to which all new writes (puts and deletes) are appended. There is only one active data file at any given time.
• Immutable Data Files: Once an active data file reaches a predefined size limit, it becomes immutable. New writes then go into a newly created active data file. Immutable files are read-only for writes but remain accessible for reads.

Data File Entry Structure

Each entry written to a Bitcask data file is carefully structured to enable efficient reading and ensure data integrity. Instead of simply storing key,value, which would make reading variable-length values difficult, Bitcask uses a fixed-width header followed by the key and value:

[CRC] [Timestamp] [Key Size] [Value Size] [Key] [Value]

Let’s break down each component:

• CRC (Checksum): A fixed-width field (e.g., 4 bytes) used to validate the integrity of the record. If a write operation fails midway (e.g., for a large value), the CRC allows detection of corruption upon read. If the checksum doesn’t match, the file can be truncated to the last valid entry.
• Timestamp: A fixed-width field (e.g., 4 bytes) indicating when the entry was created. Useful for metadata and during compaction.
• Key Size: A fixed-width field (e.g., 2 bytes) storing the length of the Key in bytes. This allows the reader to know exactly how many bytes to read for the key.
• Value Size: A fixed-width field (e.g., 2 bytes) storing the length of the Value in bytes. This allows the reader to know exactly how many bytes to read for the value.
• Key: The actual key data, with a length specified by Key Size.
• Value: The actual value data, with a length specified by Value Size.

This structure ensures that reading an entry from a specific offset is highly efficient, as the header provides all necessary length information without requiring multiple disk I/O calls or searching for delimiters.

Operations in Bitcask

Write (Put) Operation

1. Construct Record: A new record is formed with CRC, Timestamp, Key Size, Value Size, Key, and Value.
2. Append to Active File: The entire record is appended to the end of the current active data file. This is a sequential write operation, which is very fast on disk.
3. Update keydir: The keydir in-memory index is updated with the key, the file ID, the offset of the new entry, and its timestamp.
4. File Rollover: If the active data file reaches its configured size limit, it is closed and becomes immutable. A new, empty file is then created to become the new active data file for subsequent writes.

Read (Get) Operation

Bitcask’s read path is designed for minimal latency:

1. keydir Lookup: The system first checks the keydir (in-memory index) for the requested key.
2. Key Not Found: If the key is not in keydir, it means the entry does not exist, and a