Cache Engine Deep Dive

This post documents the Cache-Engine project, a high performance in memory cache with LRU eviction, custom memory management and thread safe sharding.

The core idea is simple. A hash map gives O(1) lookup and a doubly linked list gives O(1) recency. See also ERPlag-Compiler-Build for similar arena allocation and PR-Review-Agent for how we review cache code.

LRU in 10 lines

Map plus list. get moves node to head. put inserts at head and evicts tail when over capacity. Both O(1).

Memory

Per entry new fragments. We use slab allocation, preallocate 1MB chunks and bump allocate. Freed nodes go to a free list. 3x faster under churn, same technique used in ERPlag-Compiler-Build for AST nodes.

Sharding

16 shards, each with its own mutex and map. Shard = hash(key) % 16. Global ordering is relaxed, similar to eventual consistency discussed in BRKGA-Orienteering search distribution.

Project: In-memory Cache Engine Related: Tetris-BRKG-AI also stresses memory under load.