A simple embedded key-value storage engine inspired by Bitcask.

This is a learning project that I built to sharpen my systems engineering and C language skills, NOT SUITABLE FOR PRODUCTION.

The storage engine is implemented in pure C using only the standard library. Every single line of code has been written by hand without any agents.

Design

The design of the engine has been largely based on the original Bitcask paper by Justin Sheehy and David Smith.

Overview

The keys are stored in memory and the full records with values reside on disk. Writes go into an append-only file. Deletes are just writes with a special tombstone flag. As a result, both are pretty fast.

Because the keys reside in memory, reads only require a single disk seek, so read performance is also quite reasonable.

Once an append-only file reaches a certain (configurable) threshold, it is rotated and replaced by a new one. Old files become immutable and are used only for reading. A periodic compaction process merges old files to optimize disk usage.

Data layout

A single in-memory index entry has the following layout:

Field	Size	Description
key	key_sz bytes	Key string, null-terminated
file_id	4 bytes	ID of the file containing the value
val_pos	4 bytes	Offset of the value inside the file
val_sz	4 bytes	Size of the value in bytes

The format of the encoded on-disk record:

Offset	Field	Size	Description
0	crc	4 bytes	CRC32 checksum of the record
4	timestamp_ns	8 bytes	Write timestamp in nanoseconds
12	key_sz	4 bytes	Size of the key in bytes
16	val_sz	4 bytes	Size of the value in bytes
20	flag	1 byte	0 for active records, 1 for tombstones
21	key	key_sz bytes	Record key
21 + key_sz	value	val_sz bytes	Record value

In-memory index

The hashmap (i.e. the keydir) is implemented using open addressing with linear probing. FNV1A is utilized as a hashing function.

Durability

The storage engine has a dedicated parameter which can be used to instruct the engine how often fsync should run. It supports the following values (inspired by Redis):

• FSYNC_DISABLED - no explicit fsync calls, lets the OS decide.
• FSYNC_ALWAYS - run fsync after every write - maximum durability with a corresponding write performance penalty.
• FSYNC_EVERY_SEC - run fsync every second - a reasonable balance of performance and durability.

Crash recovery

The storage maintains a strict sequential order of data files; therefore, the recovery procedure is straightforward. During startup, the engine iterates over sorted log files in the data directory and replays each record, adding it to the in-memory index. The original Bitcask paper also suggests using hint files to boost the recovery speed, but the support for them was not implemented in this project.

Compaction

The compactor runs in a separate thread alongside the main one. It scans the immutable files and merges them into compacted ones omitting any stale records (that have been either deleted or overwritten with new values).

The compaction mechanism here is very simplistic, and consequently acts as the main bottleneck. Even though the old files are immutable, they cannot be safely processed without fully locking writes in the current design (as new records can contain deletes or overwrites of existing keys). Reads also need to be locked during the swapping phase, so that the index doesn't mistakenly point to old files. The engine uses a single lock for both operations for simplicity, but that leads to the stop-the-world behavior during the entire compaction phase. Separating the two locks, and possibly sharding them based on the key, will likely mitigate a lot of the downsides of the current design.

Usage

This is an embedded database, so it needs to be built and included in your project.

The project can be built with make:

make

The library has a simple API and exposes two header files: store.h and config.h.

Example usage:

#include <bitcask/config.h>
#include <bitcask/store.h>

int main(int argc, char **argv) {
    config_t config = config_create("./data");
    store_t *store = store_create(config);

    store_put(store, "foo", "bar", 4);

    char *val;
    size_t val_sz;

    store_get(store, "foo", &val, &val_sz);

    store_destroy(store);

    return 0;
}

Benchmark

Doing a realistic benchmark is very hard and was out of scope for me. But here are some toy benchmark numbers that I got out of the engine on my M1 Pro machine.

The benchmark performs 1,000,000 writes and 1,000,000 reads (non-sequential). Key size - 32 bytes. Value size - 1024 bytes.

Writes:

Fsync policy	Write time	Write IOPS
Disabled	13.8473	72,215.89
Every second	13.7646	72,649.94
Always	39.2617	25,470.09

Reads (cold cache):

Read Time	IOPS
20.5928	48,560.69

To run the benchmark on your machine, use the benchmark make target:

make benchmark
./benchmark_runner -w -n 1000000 -f "always"
./benchmark_runner -w -n 1000000 -f "every_sec"