Project: Building a Low-Latency LRU Cache Engine in C (Hash Table + Doubly Linked List)
Project: Building a Low-Latency LRU Cache Engine in C (Hash Table + Doubly Linked List)
Phase 3 Capstone. After mastering hash tables and doubly linked lists, you'll combine them into their most powerful combined form: an LRU (Least Recently Used) cache. This data structure achieves O(1) get, O(1) put, and O(1) eviction simultaneously — the exact engine inside Redis, Memcached, your CPU's L1/L2 cache controller, and Linux's page cache.
Table of Contents
- Why LRU? The Cache Locality Principle
- Architecture: The Hybrid Data Structure
- Node and Cache Structure Design
- Doubly Linked List Operations
- Hash Table Integration
- cache_get: O(1) Lookup + Promote
- cache_put: O(1) Insert + Auto-Evict
- Thread-Safe LRU with Mutex
- TTL Expiration: Time-Based Eviction
- Cache Statistics and Hit Ratio
- Extension Challenges
- Phase 3 Reflection
Why LRU? The Cache Locality Principle
Caches work because of temporal locality: recently accessed data is likely to be accessed again soon. LRU approximates the optimal eviction strategy:
- 80% of requests typically hit 20% of data items (Pareto principle).
- The "least recently used" item is the safest to evict — we have evidence it's not hot.
- LRU maintains a running model of "hotness" with O(1) operations.
Architecture: The Hybrid Data Structure
| Operation | Array | Linked List | Hash Table | LRU (Hash+List) |
|---|---|---|---|---|
get(key) | O(n) | O(n) | O(1) avg | O(1) |
put(key) | O(1) | O(1) | O(1) avg | O(1) |
evict LRU | O(n) | O(1) | N/A | O(1) |
| Ordered? | ❌ | ✅ | ❌ | ✅ |
The magic: the hash table stores pointers to nodes in the linked list. Finding a node by key is O(1) via the hash table. Promoting or evicting a node is O(1) via doubly linked list pointer manipulation. Neither data structure alone achieves all three in O(1).
Node and Cache Structure Design
Doubly Linked List Operations
These O(1) operations are the heart of LRU's constant-time performance:
Hash Table Integration
cache_get: O(1) Lookup + Promote
cache_put: O(1) Insert + Auto-Evict
Cache Statistics and Hit Ratio
Extension Challenges
- LFU (Least Frequently Used) Cache: Track access count per node; evict the node with the lowest count. More complex but better hit ratio for certain workloads.
- Two-Queue (2Q) Cache: Separate "hot" and "warm" queues — new items enter warm, move to hot on second access. Mimics adaptive cache behavior.
- CLOCK algorithm: Instead of a doubly linked list, use a circular buffer with access bits — lower memory overhead for very large caches.
- Sharded LRU: Partition the key space into N independent LRU caches, each with its own mutex — eliminates the single global lock as a concurrency bottleneck.
- Persistence: On
cache_destroy, serialize all entries to binary file withfwrite; reload oncache_initto restore hot data across restarts.
Phase 3 Reflection
Building an LRU cache is the systems programmer's rite of passage. You've moved from "writing C code" to "designing data structures where the choice of operations determines which algorithmic complexity class is possible."
This understanding — that data structure design constrains algorithmic performance more than algorithmic cleverness — is the defining insight that separates systems engineers from general-purpose programmers. Redis, Memcached, and every major CDN are built on variations of this exact pattern.
Read next: Phase 4: Concurrency & Networking →
Part of the C Mastery Course — 30 modules from C basics to expert systems engineering.