Bitcask: Architecting an Append-Only Log-Structured Hash Table for Fast Key-Value Storage
This article explores the core design principles of Bitcask, a log-structured hash table database often used for key-value stores. It focuses on how Bitcask achieves high read/write performance through an append-only data file structure, an in-memory KeyDir for fast lookups, and a safe compaction process to reclaim space and manage data files efficiently.
Read original on Medium #system-designIntroduction to Bitcask Architecture
Bitcask is a unique key-value database designed for high-performance read and write operations, particularly excelling in scenarios where values are frequently updated but keys remain relatively stable. Its design principles are rooted in a log-structured storage approach, which simplifies writes and avoids in-place updates common in traditional B-tree based databases. The core idea is to always append data to the end of a file, making writes sequential and very fast.
Append-Only Data Files
The fundamental aspect of Bitcask is its use of append-only data files. Every write operation—insertions, updates, or deletions—results in appending a new entry to the current active data file. This makes write operations incredibly fast as they are purely sequential I/O. Old versions of values are not overwritten; instead, new versions are simply appended. This strategy inherently creates 'dead' space over time, which needs to be managed through compaction.
In-Memory Key Directory (KeyDir)
To achieve fast lookups despite data being spread across various files, Bitcask maintains an in-memory KeyDir. This KeyDir stores a mapping from each key to the metadata needed to locate its latest value: the file ID, value size, and the offset within that file. Since the KeyDir is in memory, reads are typically a two-step process: a fast in-memory lookup to get the metadata, followed by a single disk seek to retrieve the value. This design ensures O(1) read access time, provided the KeyDir fits in memory.
Design Trade-off: KeyDir Size
The KeyDir's in-memory nature implies that the number of unique keys is limited by available RAM. While the values themselves can reside on disk, the metadata for each key must fit in memory. This makes Bitcask ideal for scenarios with many small keys but potentially large values, or a moderate number of keys overall.
Safe Compaction and Merging
Compaction is crucial for Bitcask to reclaim disk space from old, overwritten values. The process involves merging older data files into new ones, discarding obsolete entries, and updating the KeyDir. This operation must be performed safely to prevent data corruption during concurrent writes and reads. Bitcask typically handles this by creating new, compacted files, then atomically switching pointers to these new files, ensuring data consistency and availability. This background process doesn't block read or write operations significantly, although it consumes I/O resources.