High-Performance Key-Value Store (C++20)

Overview

This is a high-performance, networked Key-Value Store built from scratch in C++20. It serves as a rigorous "Hard Engineering" demonstration of systems programming fundamentals: memory management, multi-threading, custom binary protocols, and advanced file I/O using a Log-Structured Merge-tree (LSM) design approach.

System Architecture

The database operates primarily on four layers:

1. Memory Management (Arena) Frequent heap allocations (e.g., new Node) cause fragmentation and major performance hits. To fix this, the system implements a custom Arena allocator. The allocator requests large chunks of memory up-front (4KB by default) and serves pointer-aligned lock-free bumps to the MemTable. When the MemTable flushes, the entire Arena is instantly dropped—preventing per-node delete calls and eliminating fragmentation.

2. The MemTable (Thread-Safe SkipList) In-memory sorting is critical for high-performance sequential flushes to disk. It uses a custom atomic SkipList for rapid O(log N) inserts and lookups. It allocates directly out of the Arena.

3. Durability and Recovery (WAL) Before any operation modifies the MemTable, a log entry is appended to the Write-Ahead Log (WAL). Records are protected by CRC32 checksums. If the server crashes, on restart it replays the WAL sequentially to restore the exact state of the MemTable. Once the MemTable is securely flushed to an SSTable, the WAL is truncated.

4. Immutable Storage (SSTable) When the MemTable exceeds a soft-limit (e.g., 4MB), it is flushed to an SSTable (Sorted String Table) on disk. SSTables are immutable. To provide fast GET operations, an Index Block is written at the trailer of the SSTable file. Readers load this index into memory during instantiation, allowing them to binary search for a key and jump directly to the proper offset using a single seekg() call.

5. Networking (Raw TCP, No HTTP) To maximize throughput and prove systems-level understanding, HTTP and JSON have been completely sidestepped. The system listens for plain TCP connections via native Winsock2 threads.

Custom Binary Protocol

Communication happens via a fixed-length prefix + variable payload struct.

• Request Layout: [MsgSize:4][Opcode:1][KeyLen:4][Key...][ValLen:4 (if PUT)][Val...]
• Response Layout: [MsgSize:4][Status:1][Val...] This entirely eliminates the overhead of parsing text-based protocols like REST.

Build and Run

To build this project on Windows:

# 1. Generate Build Files
cmake -B build
# 2. Compile
cmake --build build --config Release
# 3. Run Server
.\build\Release\kvserver.exe ./kv_data 8080

To test functionality, run the python script:

python .\scripts\test_client.py

Engineering Decisions & Trade-Offs

• Standard Map vs SkipList: std::map/unordered_map requires strict C++ custom allocator objects which are cumbersome and carry hidden overheads. By writing a bespoke SkipList, we directly bind it to our Arena.
• Winsock vs ASIO: Relying on Asio fundamentally brings heavy template instantiations. Using raw BSD-style sockets (via WinSock2) is harder but proves deeper mastery over network byte streams.
• Compaction: Currently, the engine performs Level-0 appending. In a full production environment, this is paired with a background thread doing Sorted-Merge Compactions.