LRU Key-Value Store | Rutvik Mendpara

A fixed-capacity, in-memory key-value store with LRU eviction, written from scratch in C++20.

LRU key-value store design: shards, each with an open-addressed hash table and its own LRU list

Design overview, from the repository. Each shard has its own hash table, LRU list and lock.

How it works

Keys are hashed (FNV-1a) to one of several shards. Each shard holds a fixed-size, open-addressed hash table with linear probing, and an intrusive doubly linked list that tracks recency: most recently used at the head, least recently used at the tail. When a shard is full, inserting a new key evicts its tail. Eviction never needs to coordinate across shards.

Concurrency

Writers take a per-shard spinlock, so writes to different shards never contend. Reads probe the table without taking the lock and return a std::string_view to the value. The trade-off is that reads do not update recency, so the LRU order reflects writes more than reads.

Memory

All storage is allocated up front. There are no runtime heap allocations and no std::unordered_map or std::list, which keeps memory use predictable and avoids allocator contention.

Testing

Unit and concurrency tests use GoogleTest, and benchmarks use Google Benchmark, including multi-threaded read-heavy and write-heavy workloads.

Stack

C++20 · CMake · GoogleTest · Google Benchmark

Why I built it

To understand cache eviction and memory layout at a low level, and to practise writing correct concurrent data structures before reaching for a library.