Tinykv Key-Value Store

A Bitcask-style engine: every write appends to a log file, an in-memory hash index maps each key to the file offset of its latest value, and a read is one index lookup plus one positioned read. The values never sit on the heap, so the dataset can be larger than RAM; only the keys must fit. It teaches durability, file formats, crash recovery and what fsync really costs.

Target behaviour

$ java -jar tinykv.jar --dir ./data --port 7379 --sync batch
tinykv listening on :7379  recovered 12,408 keys in 41ms
$ nc localhost 7379
SET user:1 alice
OK
GET user:1
alice
DEL user:1
OK
STATS
keys=1 log_bytes=412 garbage=78%
# after kill -9 mid-write and restart:
tinykv listening on :7379  recovered 12,409 keys, truncated 17 torn bytes

Architecture

 client --TCP--> Server (virtual thread per connection)
                    |
                    v
               KvStore  -- ReadWriteLock --+
                    |                      |
        write path (write lock)       read path (read lock)
        encode + CRC32C, append        index.get -> positioned read
        index.put, then sync policy    return value
                    |
                    v
          data.log  [rec][rec][rec]...   (append only, never rewritten)
                    |
          open(): scan, verify CRCs, rebuild index, truncate torn tail
          compact(): live records -> data.log.tmp, atomic rename

Why an append-only log: appends are sequential and fast, a partial write only damages the tail, and old data is never overwritten so a crash cannot corrupt committed records. The price is garbage from overwritten and deleted keys, which compaction reclaims.

The core of it

Design the record on paper first.

+--------+-----------+--------+----------+-----+-------+
| CRC32C | timestamp | keyLen | valueLen | key | value |
| 4 B    | 8 B       | 4 B    | 4 B      | var | var   |
+--------+-----------+--------+----------+-----+-------+
big-endian, 20-byte header. valueLen = -1 marks a tombstone (delete).
CRC covers everything after the first 4 bytes.

Encode into one ByteBuffer so each record goes to the file in a single write, which keeps torn writes to the tail.

static final int HEADER = 20;

static ByteBuffer encode(byte[] key, byte[] value, long ts) {
    int vlen = value == null ? -1 : value.length;
    ByteBuffer b = ByteBuffer.allocate(HEADER + key.length + Math.max(vlen, 0));
    b.position(4).putLong(ts).putInt(key.length).putInt(vlen).put(key);
    if (value != null) b.put(value);
    var crc = new CRC32C();
    crc.update(b.array(), 4, b.position() - 4);
    b.putInt(0, (int) crc.getValue());
    return b.flip();
}

The store holds the channel, the index and the lock. The index entry records where the value starts, so a read does not re-read the key.

public final class KvStore implements AutoCloseable {
    record Entry(long valueOffset, int valueLen) {}

    private final FileChannel ch;
    private final Map<String, Entry> index = new HashMap<>();
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private long end;                       // next append position
    public void put(String key, byte[] value) throws IOException {
        byte[] k = key.getBytes(UTF_8);
        ByteBuffer rec = encode(k, value, System.currentTimeMillis());
        lock.writeLock().lock();
        try {
            long start = end;
            while (rec.hasRemaining()) end += ch.write(rec, end);
            index.put(key, new Entry(start + HEADER + k.length, value.length));
            if (syncPolicy == Sync.ALWAYS) ch.force(false);
        } finally { lock.writeLock().unlock(); }
    }
}

Reads share the read lock. Positional FileChannel.read leaves the shared file pointer alone, so it is safe.

public Optional<byte[]> get(String key) throws IOException {
    lock.readLock().lock();
    try {
        Entry e = index.get(key);
        if (e == null) return Optional.empty();
        ByteBuffer buf = ByteBuffer.allocate(e.valueLen());
        while (buf.hasRemaining()) {
            if (ch.read(buf, e.valueOffset() + buf.position()) < 0) throw new EOFException();
        }
        return Optional.of(buf.array());
    } finally { lock.readLock().unlock(); }
}

Recovery is the heart of the project. Scan from the start, validate every record, and stop at the first one that is short or fails its CRC. Everything before it is trusted, everything after is a torn write and is truncated.

private void recover() throws IOException {
    long pos = 0, size = ch.size();
    ByteBuffer h = ByteBuffer.allocate(HEADER);
    while (pos + HEADER <= size) {
        h.clear(); ch.read(h, pos); h.flip();
        int crc = h.getInt(); long ts = h.getLong(); int kl = h.getInt(), vl = h.getInt();
        long len = HEADER + kl + Math.max(vl, 0);
        if (kl < 0 || pos + len > size) break;                    // short record
        ByteBuffer body = ByteBuffer.allocate((int) len);
        ch.read(body, pos);
        if (checksum(body) != crc) break;                          // corrupt record
        String key = new String(body.array(), HEADER, kl, UTF_8);
        if (vl < 0) index.remove(key); else index.put(key, new Entry(pos + HEADER + kl, vl));
        pos += len;
    }
    ch.truncate(pos); end = pos;
}

Compaction copies live records to a new file and swaps it in with an atomic rename, here under the write lock.

public void compact() throws IOException {
    lock.writeLock().lock();
    try {
        Path tmp = dir.resolve("data.log.tmp");
        Map<String, Entry> fresh = new HashMap<>();
        try (FileChannel out = FileChannel.open(tmp, CREATE, TRUNCATE_EXISTING, WRITE)) {
            long pos = 0;
            for (var e : index.entrySet()) {
                byte[] k = e.getKey().getBytes(UTF_8);
                byte[] v = readValue(e.getValue());
                ByteBuffer rec = encode(k, v, System.currentTimeMillis());
                int n = out.write(rec);
                fresh.put(e.getKey(), new Entry(pos + HEADER + k.length, v.length));
                pos += n;
            }
            out.force(true);
        }
        ch.close();
        Files.move(tmp, dir.resolve("data.log"), ATOMIC_MOVE, REPLACE_EXISTING);
        reopen(fresh);
    } finally { lock.writeLock().unlock(); }
}

The front-end is a line protocol with one virtual thread per connection. Parsing is a switch on the first token; keep it dull and well tested.

void serve(Socket s) {
    try (s; var in = new BufferedReader(new InputStreamReader(s.getInputStream(), UTF_8));
         var out = new PrintWriter(s.getOutputStream(), true, UTF_8)) {
        for (String line; (line = in.readLine()) != null; ) {
            String[] p = line.split(" ", 3);
            switch (p[0].toUpperCase()) {
                case "SET" -> { store.put(p[1], p[2].getBytes(UTF_8)); out.println("OK"); }
                case "GET" -> out.println(store.get(p[1]).map(v -> new String(v, UTF_8)).orElse("(nil)"));
                case "DEL" -> { store.delete(p[1]); out.println("OK"); }
                default -> out.println("ERR unknown command");
            }
        }
    } catch (IOException | RuntimeException e) { log.warn("conn failed", e); }
}

Testing

The most valuable test simulates a crash: write good records, append a half-written record, reopen, and assert that the good data survives and the junk is gone.

class RecoveryTest {
    @Test
    void truncatesTornTailAndKeepsCommittedWrites(@TempDir Path dir) throws Exception {
        try (var kv = KvStore.open(dir)) {
            kv.put("a", "1".getBytes());
            kv.put("b", "2".getBytes());
        }
        Path log = dir.resolve("data.log");
        long good = Files.size(log);
        ByteBuffer torn = KvStore.encode("c".getBytes(), "3333".getBytes(), 1L);
        try (var ch = FileChannel.open(log, APPEND)) { ch.write(torn.limit(torn.limit() - 2)); }

        try (var kv = KvStore.open(dir)) {
            assertThat(kv.get("a")).contains("1".getBytes());
            assertThat(kv.get("b")).contains("2".getBytes());
            assertThat(kv.get("c")).isEmpty();
        }
        assertThat(Files.size(log)).isEqualTo(good);
    }
}

Add a byte-flip loop test and a concurrency test with 8 writers and 8 readers compared against a model ConcurrentHashMap.

Bugs you will hit

• Assuming write writes everything. FileChannel.write may write fewer bytes than requested. Loop until hasRemaining() is false, as in put, or you create silently short records.
• Forgetting that force is the durability line. A successful write only reaches the OS page cache. force(false) per write is safe and slow; batching bounds the loss window.
• Reading from a shared position. Using channel.position(x) then read(buf) from two threads interleaves and returns garbage. Use the positional overloads.
• Trusting a CRC-less tail. Without checksums a torn record decodes as plausible data with a huge keyLen, which then allocates gigabytes. Validate lengths against the file size before allocating, and the CRC before indexing.
• Compaction racing readers. If you rename the file while readers hold old offsets, they read from the wrong place. Swap the file and the index together under the write lock, and bump a generation if you later allow lock-free reads.

Interview angle

• Why is a Bitcask-style store fast, and what is its limit? Writes are sequential appends and reads are one seek, so both are O(1) in I/O. The limit is that every key lives in memory, and compaction is needed to bound disk usage. An LSM tree trades that for sorted files and range scans.
• How do you know a write is durable? Only after FileChannel.force returns (or the file was opened with SYNC or DSYNC). Acknowledging before that means a crash can lose a write the client believes was saved. Group commit amortises the cost across many writers.
• ReentrantReadWriteLock or StampedLock? The read-write lock is simple and reentrant. StampedLock offers optimistic reads that avoid even the read-lock cost, but it is not reentrant and the optimistic path must validate the stamp and retry, which is easy to get wrong. Measure before switching.
• How does recovery decide where the log ends? It scans forward and stops at the first record that is incomplete or fails its checksum, then truncates there. This is safe because the log is append-only, so any damage from a crash can only be at the tail.