Bitcask Storage Engine (Java)

A persistent, high-performance Key-Value store based on the standard Bitcask design. It uses an append-only log format and an in-memory hash map for O(1) lookups.

How it works

1. Writes: Every put is a direct append to an active .data file. The in-memory Keydir is then updated with the pointer (file ID, offset, size).
2. Reads: The engine looks up the key in the Keydir to get the record pointer and performs exactly one disk seek to fetch the value.
3. Deletes: Appends a tombstone record to the log. The key is removed from the Keydir.
4. Compaction: A background thread periodically merges old data files, discarding obsolete versions of keys and removing tombstones to reclaim space.
5. Recovery: On startup, the engine builds the Keydir by scanning .hint files (which are faster than scanning full .data files).

Technical Highlights

• Memory Efficiency: Instead of using java.util.HashMap (which has high object overhead), I implemented a custom hash map using primitive long[] and int[] arrays. This keeps the heap clean and reduces GC pressure.
• Generic API: Fully generic K and R extends Record<K>. You can define your own serialization logic by implementing the Codec interface.
• Concurrency: Uses a ReentrantReadWriteLock to allow concurrent readers while ensuring write/compaction integrity.
• CRC Validation: Every record is checksummed on write and validated on read to detect disk corruption.

---

Quick Start

Implement a Codec for your data type (see RecordCodec.java for a JSON implementation using Jackson):

Codec<String, MyRecord> codec = new MyRecordCodec();
Bootstrap bootstrap = new Bootstrap("/tmp/bitcask-data");
StorageEngine<String, MyRecord> engine = new StorageEngine<>(codec, bootstrap);

engine.init();

// Storage
engine.put(new MyRecord("user_123", "data"));

// Retrieval
MyRecord r = engine.get("user_123");

Internal Architecture

• FileManager: Handles low-level FileChannel I/O and synchronization.
• RecordManager: Orchestrates CRC calculation, slicing byte buffers, and record layout.
• CompactionManager: Manages the lifecycle of background merges and .hint file generation.
• Keydir: The primary index. If the engine crashes, this is rebuilt from the hint files.

Performance

• Put: O(1) append.
• Get: O(1) disk seek.
• Space Efficiency: Controlled by COMPACTION_THRESHOLD and MAX_FILE_SIZE.

Current Limitations / TODO

• Compaction is currently triggered by a fixed schedule/threshold; could be more adaptive.
• File descriptor management needs a reference counter to prevent race conditions during heavy compaction.