Step 01 — LRU Block Cache

Goal

Implement a bounded, O(1) LRU cache keyed on (file_id, block_offset) holding decoded block bytes, with hit/miss/eviction statistics.

Spec

API (Rust signature; the Go and C++ APIs mirror it):

#![allow(unused)]
fn main() {
pub struct BlockKey { pub file_id: u64, pub offset: u64 }
pub struct CacheStats { pub hits: u64, pub misses: u64, pub evictions: u64 }

impl BlockCache {
    pub fn new(capacity: usize) -> Self;                       // capacity > 0
    pub fn get(&mut self, k: &BlockKey) -> Option<Vec<u8>>;    // promotes to MRU on hit
    pub fn insert(&mut self, k: BlockKey, v: Vec<u8>) -> bool; // returns true on overwrite
    pub fn len(&self) -> usize;
    pub fn capacity(&self) -> usize;
    pub fn stats(&self) -> CacheStats;
    pub fn keys_mru_to_lru(&self) -> Vec<BlockKey>;            // test-only
}
}

Behavior contracts:

  • get returns Some(v.clone()) on hit and moves that entry to MRU; bumps hits counter.
  • get returns None on miss; bumps misses counter.
  • insert on an existing key overwrites the value and promotes to MRU.
  • insert on a full cache evicts the LRU entry first; bumps evictions.
  • keys_mru_to_lru() returns the live keys in order; used by tests only.

Acceptance

cd src/rust && cargo test
cd src/go   && go test
cd src/cpp  && cmake -B build && cmake --build build && ctest --test-dir build

All four LRU tests pass in each language:

  • lru_basic_hit_miss
  • lru_evicts_lru_on_capacity
  • lru_reinsert_overwrites_and_promotes
  • lru_keys_order_mru_first

Discussion prompts

  • Why does get need a &mut self and not just &self? (Because it mutates the recency order, even though it only "reads" the cached value.)
  • What changes if you bound by total bytes instead of entries? (You need to weigh each entry on insert and evict in a loop until under cap.)
  • How would you make this thread-safe with minimum contention? (Sharded by hash(key) % N, one mutex per shard.)