LynxKV

A high-performance, concurrent, embeddable C++23 key-value storage engine featuring a custom Robin Hood hash table, polymorphic memory pool allocation, Write-Ahead Logging (WAL) with sync/async durability, deadlock-free snapshotting, and atomic diagnostic metrics.

I built this to experiment with cache-friendly open-addressing hash tables, customized polymorphic allocators (std::pmr), lock-free instrumentation, and concurrent sharded access patterns to achieve maximum throughput with predictable sub-microsecond latency.

Architecture

┌────────────────────────────────────────────────────────┐
│                      Public API                        │
│             lynxkv::Database · lynxkv::Config          │
├────────────────────────────────────────────────────────┤
│                   Concurrency Layer                    │
│      ShardedStore (N Shards, Cache-aligned 64B)        │
│          Shared RW Locks (std::shared_mutex)           │
├───────────────────────────┬────────────────────────────┤
│     In-Memory Storage     │     Memory Management      │
│    Robin Hood HashTable   │      ArenaResource (Bump)  │
│  Backward-shift compaction│      SlabResource (Pool)   │
├───────────────────────────┼────────────────────────────┤
│    Persistence Engine     │      Eviction Manager      │
│      WalWriter / WalReader│      LRU / LFU / FIFO      │
│      SnapshotManager      │      Intrusive Nodes       │
├───────────────────────────┴────────────────────────────┤
│                   Diagnostics & Metrics                │
│       Atomic Metrics Bookkeeping (Stats, hit/miss)     │
└────────────────────────────────────────────────────────┘

• Sharded Concurrency: Partitions the key space across $N$ cache-aligned shards (using alignas(64) to prevent cache-line false sharing). Concurrent lookups are non-blocking via reader-priority shared locks (std::shared_mutex).
• Custom Robin Hood HashTable: Cache-friendly open-addressing table utilizing Robin Hood hashing (stealing slots from "richer" entries with shorter probe distances) to maintain low, uniform probe sequences. Implements backward-shift deletion for compaction to completely avoid tombstone overhead.
• Polymorphic Memory Allocation: Standard-compliant polymorphic memory resources (std::pmr::memory_resource) including ArenaResource (for fast, O(1) bump-pointer allocations) and SlabResource (for object pooling).
• Write-Ahead Logging (WAL): Crash-resilient write-ahead logging featuring synchronous (fsync per write) and asynchronous (off-critical-path background ThreadPool flushes) modes. Features CRC32 checksums and tail-tolerance for crash-torn records.
• Coherent Snapshots: Fast, deadlock-free point-in-time snapshotting. Locks shards in a strict, global index order to freeze database state without deadlocks, serializes records, and truncates the WAL.
• Global Eviction Manager: Enforces global memory capacity (max_memory_bytes) with support for LRU (O(1) intrusive list splices), LFU (frequency-based tracking with O(N) list scans), and FIFO (insertion order) policies.

---

Building & Testing

Building requires a C++23 compliant compiler (e.g., GCC 13+, Clang 16+, or MSVC 19.36+) and CMake 3.24+.

# Configure & Build using CMake presets
cmake --preset default
cmake --build --preset default

# Run functional, integration, and property-based tests
ctest --preset default

Sanitizer Presets (Linux / CI)

The project includes presets to build and run tests under sanitizers to ensure safety and catch bugs:

# AddressSanitizer (detects overflows/use-after-free)
cmake --preset asan && cmake --build --preset asan && ctest --preset asan

# ThreadSanitizer (detects data races/lock-order violations)
cmake --preset tsan && cmake --build --preset tsan && ctest --preset tsan

# UndefinedBehaviorSanitizer (detects UB, signed overflow, misalignments)
cmake --preset ubsan && cmake --build --preset ubsan && ctest --preset ubsan

---

How It Works (Quick Example)

#include "lynxkv/database.hpp"
#include <iostream>

int main() {
    // Configure database
    lynxkv::Config config;
    config.shard_count = 16;
    config.max_memory_bytes = 1024 * 1024; // 1 MB cap (evicts via LRU when reached)
    config.wal_path = "data/wal.log";
    config.snapshot_path = "data/snapshot.bin";
    config.async_persistence = true; // Flushes WAL asynchronously off the critical path
    
    // Initialize Database (uses pImpl idiom to keep compile times fast and hide STL/internal types)
    lynxkv::Database db{config};

    // 1. Set key-value pairs
    auto set_status = db.set("user:session:100", "{\"name\": \"Alice\", \"role\": \"admin\"}");
    if (!set_status) {
        std::cerr << "Write failed!\n";
    }

    // 2. Retrieve values
    auto get_result = db.get("user:session:100");
    if (get_result) {
        std::cout << "Value: " << *get_result << "\n";
    } else {
        std::cerr << "Key not found!\n";
    }

    // 3. Check existence & size
    if (db.exists("user:session:100")) {
        std::cout << "Database contains " << db.size() << " entry/entries.\n";
    }

    // 4. Save point-in-time snapshot (deadlock-free, truncates WAL)
    auto save_status = db.save();
    if (save_status) {
        std::cout << "Snapshot saved successfully.\n";
    }

    // 5. Diagnostics
    lynxkv::Database::Stats stats = db.stats();
    std::cout << "Diagnostics:\n"
              << " - Hits: " << stats.hits << "\n"
              << " - Misses: " << stats.misses << "\n"
              << " - Memory Used: " << stats.memory_used_bytes << " bytes\n";
}

---

Performance & Benchmarks

Benchmarks are implemented using Google Benchmark and can be built and run by enabling the LYNXKV_BUILD_BENCHMARKS option.

# Configure, build and run benchmarks
cmake -B build -DLYNXKV_BUILD_BENCHMARKS=ON -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release
./build/benchmarks/lynxkv_bench

Performance Floors (on Reference Hardware)

The project includes a CI regression gate (benchmarks/ci_gate.sh) that verifies performance on reference hardware (x86-64, single-core clock speed $\ge$ 3.0 GHz, $\ge$ 16 GB RAM):

• Single-threaded GET Throughput: $> 10,000,000$ ops/sec
• 16-Thread Mixed Throughput (80% Read / 20% Write): $> 5,000,000$ ops/sec (aggregate)
• 64-Thread Write-Heavy Throughput (100% Write): $> 1,000,000$ ops/sec (aggregate)
• Mean GET Latency: $< 1$ microsecond (1,000 ns)