Bitcask

A C++17 implementation of the Bitcask log-structured key-value storage engine, built as a shared library.

Bitcask provides low-latency reads and writes by keeping all keys in memory (via a hash index) and appending every write to an append-only log file. When a log file exceeds a configurable size threshold it is rotated into an immutable "stable" file and a new active file is created.

Features

• O(1) reads - key lookup goes through an in-memory index directly to the on-disk value offset
• Append-only writes - no in-place updates; every write is a sequential append
• Synchronous and asynchronous Put - Put blocks until committed; PutAsync returns a std::future<void>
• Automatic file rotation - active file rotates when it exceeds Setting::maxFileSize
• Crash recovery - on restart, all existing .db files are scanned and the in-memory index is rebuilt
• CRC32C integrity - every record is checksummed on write and verified on read
• Thread-safe - concurrent reads and writes via std::shared_mutex and libcuckoo::cuckoohash_map

Architecture

┌──────────────────────────────────────────────────────────┐
│  Public API  (include/bitcask/)                          │
│  Bitcask ──► BitcaskImpl  (pimpl)                        │
└────────────────────────┬─────────────────────────────────┘
                         │
           ┌─────────────▼─────────────┐
           │  In-memory index          │
           │  RecordMap  key → Hint    │
           │  ActiveMap  key → Value   │
           └─────────────┬─────────────┘
                         │
           ┌─────────────▼─────────────┐
           │  Storage layer            │
           │  ActiveFile  (write/read) │
           │  StableFile  (read-only)  │
           └───────────────────────────┘

Write path: Put enqueues a write → CommitWorker (background thread) drains the queue → appends a record to the active file → updates RecordMap and ActiveMap → rotates active file if it exceeds maxFileSize.

Read path: look up key in RecordMap to get a Hint (file id, offset, size) → if the hint points to the active file, serve from ActiveMap (in-memory) → otherwise seek into the corresponding StableFile and read the bytes at the stored offset.

On-disk record format:

| crc32c (4B) | keySize (4B) | valueSize (4B) | key (keySize B) | value (valueSize B) |

Requirements

Tool	Version
C++ compiler	C++17 or later
CMake	3.16 or later

Dependencies are fetched automatically via CMake FetchContent:

Library	Purpose
google/crc32c	CRC32C checksum
google/googletest v1.17.0	Unit testing
efficient/libcuckoo	Concurrent hash maps

Build

# Configure (fetches dependencies automatically)
cmake -B build

# Build
cmake --build build

# Or build with parallel jobs
cmake --build build -- -j$(nproc)

The output shared library is build/libbitcask_cpp.dylib (macOS) or build/libbitcask_cpp.so (Linux).

Testing

# Run all tests
cd build && ctest

# Run a specific test suite
./build/test/record
./build/test/active_map
./build/test/record_map
./build/test/init_from_existed_db
./build/test/bitcask
./build/test/bitcask_benchmark

# Run a single test case
./build/test/bitcask --gtest_filter="BitCaskTest.OverwriteKeyReturnsLatestValue"

Suite	What it covers
record	On-disk record serialisation and CRC32C verification
active_map	In-memory key-value cache including concurrent access
record_map	In-memory key→Hint index including concurrent access
init_from_existed_db	DB recovery and data persistence across restarts
bitcask	Public API (Put, PutAsync, Get, Delete) and file rotation
bitcask_benchmark	Throughput with 100 000 keys and file rotation enabled

Usage

#include <bitcask/Bitcask.hpp>
#include <bitcask/Logger.hpp>
#include <iostream>

int main() {
    // Optional: enable logging
    bitcask::logger::init(
        bitcask::logger::LOG_LEVEL_FROM_INFO,
        [](const std::string &msg) { std::cout << msg << "\n"; });

    // Open (or create) a database
    bitcask::Bitcask *db = bitcask::Bitcask::Create("/tmp/mydb/");

    // Synchronous write - blocks until committed to disk
    db->Put("hello", "world");

    // Asynchronous write - returns immediately with a future
    auto f = db->PutAsync("key2", "value2");
    f.get(); // wait for commit if needed

    // Read
    auto val = db->Get("hello");
    if (val) {
        std::cout << *val << "\n"; // "world"
    }

    delete db;
}

Custom settings

bitcask::Setting setting;
setting.dbPath = "/tmp/mydb/"; 
setting.maxFileSize = 64 * 1024 * 1024; // rotate every 64 MB (default: 1 GB)

bitcask::Bitcask *db = bitcask::Bitcask::Create(setting);

Linking (CMake consumer)

target_link_libraries(my_app PRIVATE bitcask_cpp)
target_include_directories(my_app PRIVATE path/to/bitcask-cpp/include)

Limitations

• Delete is not yet implemented - Delete() returns false (TBD).
• No compaction - stable files are never merged; disk usage grows monotonically until compaction is implemented.
• All keys must fit in memory (standard Bitcask constraint).

Benchmarks

Benchmarks are in benchmark/bitcask_benchmark.cpp and use Google Benchmark (bundled via crc32c's FetchContent, v1.9.2).

Machine: Apple M1 Pro (virtual), 6 cores, 12 MB L2 cache
Build: CMake Release mode, Apple Clang, macOS

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --target bitcask_benchmark
./build/benchmark/bitcask_benchmark

Results

Benchmark	Value size	Wall time / op	Throughput
Put (sync)	16 B	~36 µs	~110 K ops/s
Put (sync)	128 B	~39 µs	~105 K ops/s
Put (sync)	1024 B	~46 µs	~86 K ops/s
PutAsync	16 B	~12 µs	~578 K ops/s
PutAsync	128 B	~16 µs	~497 K ops/s
PutAsync	1024 B	~13 µs	~496 K ops/s
Get - active file (hot cache)	16 B	~2.2 µs	~482 K ops/s
Get - active file (hot cache)	128 B	~2.4 µs	~458 K ops/s
Get - active file (hot cache)	1024 B	~2.4 µs	~449 K ops/s
Get - stable file (disk)	16 B	~2.9 µs	~363 K ops/s
Get - stable file (disk)	128 B	~3.9 µs	~269 K ops/s
Get - stable file (disk)	1024 B	~3.9 µs	~270 K ops/s
Mixed 80 % reads / 20 % writes	64 B	~11 µs	~238 K ops/s

Key observations:

• PutAsync is 4–5× faster than synchronous Put - the background commit worker amortises fsync overhead across batches.
• Get from the active file (served from libcuckoo in-memory map) takes ~2 µs regardless of value size, demonstrating O(1) hot-cache reads.
• Stable-file reads add only ~1–2 µs over the hot-cache path, thanks to precomputed Hint offsets avoiding index scans.

License

This project is open source. See the repository for licence details.