codeloopback
Guide contents

Lesson 6 of 12

Generic LRU Cache

A cache keeps the results of expensive work, such as database queries, HTTP calls, or rendered pages, so the next request for the same key is fast. Memory is limited, so the cache has a capacity, and when it's full it evicts the entry that was least recently used (LRU). Crates such as lru and moka provide one ready-made; here we build the data structure ourselves as a small library crate called lru.

Step Topics
1. a simple version HashMap, VecDeque, generics with Hash + Eq + Clone
2. O(1) operations an index-linked list in a Vec, swap_remove, Borrow for lookups
3. expiry and statistics a Clock trait with a real and a fake implementation, composition
4. a documented library /// docs with doc tests, impl Iterator returns
5. sharing between threads Arc<Mutex<...>>, memoizing a slow function
Terminal
cargo new --lib lru

Step 1: The simplest correct version

A HashMap stores the values and a VecDeque stores the keys in usage order, most recent at the front. Every access moves the key to the front; eviction pops from the back. It's correct and short, but moving a key means searching the VecDeque, which is O(n).

Rust
use std::collections::{HashMap, VecDeque};
use std::fmt::Debug;
use std::hash::Hash;

struct SimpleLru<K, V> {
    values: HashMap<K, V>,
    order: VecDeque<K>, // front = most recently used
    capacity: usize,
}

impl<K: Hash + Eq + Clone + Debug, V> SimpleLru<K, V> {
    fn new(capacity: usize) -> Self {
        SimpleLru { values: HashMap::new(), order: VecDeque::new(), capacity }
    }

    fn touch(&mut self, key: &K) {
        if let Some(position) = self.order.iter().position(|k| k == key) {
            let key = self.order.remove(position).unwrap(); // O(n)
            self.order.push_front(key);
        }
    }

    fn get(&mut self, key: &K) -> Option<&V> {
        self.touch(key);
        self.values.get(key)
    }

    fn put(&mut self, key: K, value: V) {
        if self.values.insert(key.clone(), value).is_some() {
            self.touch(&key);
            return;
        }
        self.order.push_front(key);
        if self.order.len() > self.capacity {
            let oldest = self.order.pop_back().unwrap();
            self.values.remove(&oldest);
            println!("  evicted {oldest:?}");
        }
    }

    fn keys(&self) -> Vec<&K> {
        self.order.iter().collect()
    }
}

fn main() {
    let mut cache = SimpleLru::new(3);
    cache.put("a", 1);
    cache.put("b", 2);
    cache.put("c", 3);
    println!("{:?}", cache.keys());

    println!("get a = {:?}", cache.get(&"a"));
    println!("{:?}", cache.keys());

    cache.put("d", 4); // evicts b, the least recently used
    println!("{:?}", cache.keys());
    println!("get b = {:?}", cache.get(&"b"));
}
Output
["c", "b", "a"]
get a = Some(1)
["a", "c", "b"]
  evicted "b"
["d", "a", "c"]
get b = None

Step 2: O(1) with an index-linked list

To move an entry to the front in constant time, the usage order must be a doubly linked list, and the map must point straight at list nodes. In a garbage-collected language that's done with object references. In Rust, nodes that point at each other in both directions don't fit the ownership model well, so the usual design stores all nodes in a Vec and links them by index:

Text
map:   "a" -> 2    "c" -> 0    "d" -> 1

nodes: [0] c  prev=2 next=NIL      head = 1 (d, most recent)
       [1] d  prev=NIL next=2      tail = 0 (c, least recent)
       [2] a  prev=1 next=0

Moving a node means rewriting a few indices. Removing one uses swap_remove, which moves the last node into the hole in O(1); the moved node's neighbors and map entry are then pointed at its new index.

get and remove accept any borrowed form of the key through Borrow, the same signature as HashMap::get, so a LruCache<String, _> can be queried with a &str.

Rustcargo test
use std::borrow::Borrow;
use std::collections::HashMap;
use std::hash::Hash;

const NIL: usize = usize::MAX;

struct Node<K, V> {
    key: K,
    value: V,
    prev: usize,
    next: usize,
}

pub struct LruCache<K, V> {
    map: HashMap<K, usize>,
    nodes: Vec<Node<K, V>>,
    head: usize, // most recently used
    tail: usize, // least recently used
    capacity: usize,
}

impl<K: Hash + Eq + Clone, V> LruCache<K, V> {
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "capacity must be at least 1");
        LruCache { map: HashMap::with_capacity(capacity), nodes: Vec::with_capacity(capacity), head: NIL, tail: NIL, capacity }
    }

    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    fn unlink(&mut self, i: usize) {
        let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);
        if prev != NIL { self.nodes[prev].next = next } else { self.head = next }
        if next != NIL { self.nodes[next].prev = prev } else { self.tail = prev }
    }

    fn push_front(&mut self, i: usize) {
        self.nodes[i].prev = NIL;
        self.nodes[i].next = self.head;
        if self.head != NIL {
            self.nodes[self.head].prev = i;
        }
        self.head = i;
        if self.tail == NIL {
            self.tail = i;
        }
    }

    pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        let i = *self.map.get(key)?;
        self.unlink(i);
        self.push_front(i);
        Some(&self.nodes[i].value)
    }

    /// Inserts or updates; returns the evicted entry, if one had to go.
    pub fn put(&mut self, key: K, value: V) -> Option<(K, V)> {
        if let Some(&i) = self.map.get(&key) {
            self.nodes[i].value = value;
            self.unlink(i);
            self.push_front(i);
            return None;
        }
        let evicted = if self.nodes.len() == self.capacity {
            let lru_key = self.nodes[self.tail].key.clone();
            self.remove(&lru_key).map(|value| (lru_key, value))
        } else {
            None
        };
        let i = self.nodes.len();
        self.nodes.push(Node { key: key.clone(), value, prev: NIL, next: NIL });
        self.map.insert(key, i);
        self.push_front(i);
        evicted
    }

    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        let i = self.map.remove(key)?;
        self.unlink(i);
        let removed = self.nodes.swap_remove(i);
        if i < self.nodes.len() {
            // The last node moved into slot `i`: repoint its neighbors and its map entry.
            let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);
            if prev != NIL { self.nodes[prev].next = i } else { self.head = i }
            if next != NIL { self.nodes[next].prev = i } else { self.tail = i }
            *self.map.get_mut::<K>(&self.nodes[i].key).unwrap() = i;
        }
        Some(removed.value)
    }

    /// Keys from most to least recently used.
    pub fn keys(&self) -> impl Iterator<Item = &K> {
        let first = (self.head != NIL).then_some(self.head);
        std::iter::successors(first, |&i| {
            let next = self.nodes[i].next;
            (next != NIL).then_some(next)
        })
        .map(|i| &self.nodes[i].key)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn keys(cache: &LruCache<String, i32>) -> Vec<&str> {
        cache.keys().map(String::as_str).collect()
    }

    #[test]
    fn evicts_the_least_recently_used() {
        let mut cache = LruCache::new(2);
        cache.put(String::from("a"), 1);
        cache.put(String::from("b"), 2);
        assert_eq!(cache.get("a"), Some(&1)); // lookup with &str thanks to Borrow
        let evicted = cache.put(String::from("c"), 3);
        assert_eq!(evicted, Some((String::from("b"), 2)));
        assert_eq!(keys(&cache), ["c", "a"]);
    }

    #[test]
    fn updating_a_key_refreshes_it() {
        let mut cache = LruCache::new(2);
        cache.put(String::from("a"), 1);
        cache.put(String::from("b"), 2);
        cache.put(String::from("a"), 10);
        cache.put(String::from("c"), 3);
        assert_eq!(keys(&cache), ["c", "a"]);
        assert_eq!(cache.get("a"), Some(&10));
    }

    #[test]
    fn removing_keeps_the_links_consistent() {
        let mut cache = LruCache::new(4);
        for (i, key) in ["a", "b", "c", "d"].into_iter().enumerate() {
            cache.put(key.to_string(), i as i32);
        }
        assert_eq!(cache.remove("b"), Some(1)); // "d" moves into b's slot
        assert_eq!(keys(&cache), ["d", "c", "a"]);
        assert_eq!(cache.get("d"), Some(&3));
        cache.put(String::from("e"), 4);
        cache.put(String::from("f"), 5); // evicts "a"
        assert_eq!(keys(&cache), ["f", "e", "d", "c"]);
        assert_eq!(cache.len(), 4);
    }

    #[test]
    fn many_operations_match_the_simple_model() {
        // Compare against a Vec-based model over a long pseudo-random sequence.
        let mut cache = LruCache::new(5);
        let mut model: Vec<(String, i32)> = Vec::new(); // front = most recent
        let mut seed: u32 = 7;
        for step in 0..2_000 {
            seed = seed.wrapping_mul(1_103_515_245).wrapping_add(12_345);
            let key = format!("k{}", (seed >> 16) % 9);
            if (seed >> 8) % 3 == 0 {
                let expected = model.iter().position(|(k, _)| *k == key).map(|p| model.remove(p));
                assert_eq!(cache.remove(key.as_str()), expected.map(|(_, v)| v));
            } else {
                if let Some(p) = model.iter().position(|(k, _)| *k == key) {
                    model.remove(p);
                }
                model.insert(0, (key.clone(), step));
                model.truncate(5);
                cache.put(key, step);
            }
            let expected: Vec<&str> = model.iter().map(|(k, _)| k.as_str()).collect();
            assert_eq!(keys(&cache), expected);
        }
    }
}
Output
running 4 tests
test tests::evicts_the_least_recently_used ... ok
test tests::many_operations_match_the_simple_model ... ok
test tests::removing_keeps_the_links_consistent ... ok
test tests::updating_a_key_refreshes_it ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

The last test is a small model-based test: it runs thousands of random operations against both the fast cache and an obviously correct slow model, and checks that they always agree. Index-juggling code is exactly where such tests find bugs.

Step 3: Expiry, statistics, and a clock you can control

Cached data goes stale, so entries get a time to live (TTL). Testing expiry with real time means sleeping in tests, which is slow and flaky. Instead, the cache asks a Clock for the time, and tests pass a ManualClock they can move forward instantly.

TtlCache doesn't reimplement anything: it wraps LruCache<K, (V, expires_at)> and adds the expiry check and hit counters, composition rather than inheritance.

Rust
use std::cell::Cell;
use std::collections::HashMap;
use std::hash::Hash;
use std::time::Instant;

// A compact LruCache from step 2 (get, peek, put, remove).
const NIL: usize = usize::MAX;
struct Node<K, V> { key: K, value: V, prev: usize, next: usize }
struct LruCache<K, V> { map: HashMap<K, usize>, nodes: Vec<Node<K, V>>, head: usize, tail: usize, capacity: usize }

impl<K: Hash + Eq + Clone, V> LruCache<K, V> {
    fn new(capacity: usize) -> Self {
        LruCache { map: HashMap::new(), nodes: Vec::new(), head: NIL, tail: NIL, capacity }
    }
    fn unlink(&mut self, i: usize) {
        let (p, n) = (self.nodes[i].prev, self.nodes[i].next);
        if p != NIL { self.nodes[p].next = n } else { self.head = n }
        if n != NIL { self.nodes[n].prev = p } else { self.tail = p }
    }
    fn push_front(&mut self, i: usize) {
        self.nodes[i].prev = NIL;
        self.nodes[i].next = self.head;
        if self.head != NIL { self.nodes[self.head].prev = i }
        self.head = i;
        if self.tail == NIL { self.tail = i }
    }
    fn peek(&self, key: &K) -> Option<&V> {
        self.map.get(key).map(|&i| &self.nodes[i].value)
    }
    fn get(&mut self, key: &K) -> Option<&V> {
        let i = *self.map.get(key)?;
        self.unlink(i);
        self.push_front(i);
        Some(&self.nodes[i].value)
    }
    fn put(&mut self, key: K, value: V) {
        if let Some(&i) = self.map.get(&key) {
            self.nodes[i].value = value;
            self.unlink(i);
            self.push_front(i);
            return;
        }
        if self.nodes.len() == self.capacity {
            let lru = self.nodes[self.tail].key.clone();
            self.remove(&lru);
        }
        let i = self.nodes.len();
        self.nodes.push(Node { key: key.clone(), value, prev: NIL, next: NIL });
        self.map.insert(key, i);
        self.push_front(i);
    }
    fn remove(&mut self, key: &K) -> Option<V> {
        let i = self.map.remove(key)?;
        self.unlink(i);
        let removed = self.nodes.swap_remove(i);
        if i < self.nodes.len() {
            let (p, n) = (self.nodes[i].prev, self.nodes[i].next);
            if p != NIL { self.nodes[p].next = i } else { self.head = i }
            if n != NIL { self.nodes[n].prev = i } else { self.tail = i }
            *self.map.get_mut::<K>(&self.nodes[i].key).unwrap() = i;
        }
        Some(removed.value)
    }
}

// ---------- the new part ----------

trait Clock {
    fn now_ms(&self) -> u64;
}

struct SystemClock(Instant);

impl Clock for SystemClock {
    fn now_ms(&self) -> u64 {
        self.0.elapsed().as_millis() as u64
    }
}

#[derive(Default)]
struct ManualClock(Cell<u64>);

impl ManualClock {
    fn advance(&self, ms: u64) {
        self.0.set(self.0.get() + ms);
    }
}

impl Clock for &ManualClock {
    fn now_ms(&self) -> u64 {
        self.0.get()
    }
}

#[derive(Debug, Default, PartialEq)]
struct Stats {
    hits: u64,
    misses: u64,
    expired: u64,
}

struct TtlCache<K, V, C: Clock> {
    inner: LruCache<K, (V, u64)>,
    ttl_ms: u64,
    clock: C,
    stats: Stats,
}

impl<K: Hash + Eq + Clone, V, C: Clock> TtlCache<K, V, C> {
    fn new(capacity: usize, ttl_ms: u64, clock: C) -> Self {
        TtlCache { inner: LruCache::new(capacity), ttl_ms, clock, stats: Stats::default() }
    }

    fn put(&mut self, key: K, value: V) {
        let expires_at = self.clock.now_ms() + self.ttl_ms;
        self.inner.put(key, (value, expires_at));
    }

    fn get(&mut self, key: &K) -> Option<&V> {
        let now = self.clock.now_ms();
        if matches!(self.inner.peek(key), Some((_, expires_at)) if *expires_at <= now) {
            self.inner.remove(key);
            self.stats.expired += 1;
        }
        match self.inner.get(key) {
            Some((value, _)) => {
                self.stats.hits += 1;
                Some(value)
            }
            None => {
                self.stats.misses += 1;
                None
            }
        }
    }
}

fn main() {
    let clock = ManualClock::default();
    let mut cache = TtlCache::new(100, 5_000, &clock);

    cache.put("user:7", "Ana");
    println!("t=0s   {:?}", cache.get(&"user:7"));
    clock.advance(4_999);
    println!("t=4.9s {:?}", cache.get(&"user:7"));
    clock.advance(1);
    println!("t=5s   {:?}", cache.get(&"user:7"));
    println!("{:?}", cache.stats);

    // The same type with the real clock, for production code.
    let mut real = TtlCache::new(100, 60_000, SystemClock(Instant::now()));
    real.put(1, "one");
    println!("real clock: {:?}", real.get(&1));
}
Output
t=0s   Some("Ana")
t=4.9s Some("Ana")
t=5s   None
Stats { hits: 2, misses: 1, expired: 1 }
real clock: Some("one")

Clock is implemented for &ManualClock, so the test keeps its own handle to the clock while the cache holds a reference to it. The expiry test runs instantly and gives the same result every time.

Step 4: A documented library with doc tests

The finished library documents every public item with /// comments. Code in those comments is compiled and run by cargo test as doc tests, so the examples in the documentation can't go out of date. cargo doc --open renders it all as HTML, in the same format as the documentation on docs.rs.

Rustcargo test (doc tests)
//! A least-recently-used cache with O(1) operations.

use std::borrow::Borrow;
use std::collections::HashMap;
use std::hash::Hash;

const NIL: usize = usize::MAX;

struct Node<K, V> {
    key: K,
    value: V,
    prev: usize,
    next: usize,
}

/// A fixed-capacity cache that evicts the least recently used entry.
///
/// ```
/// use lru::LruCache;
///
/// let mut cache = LruCache::new(2);
/// cache.put("a", 1);
/// cache.put("b", 2);
/// cache.get("a");             // "a" is now the most recently used
/// cache.put("c", 3);          // so "b" is evicted
/// assert_eq!(cache.get("b"), None);
/// assert_eq!(cache.keys().collect::<Vec<_>>(), [&"c", &"a"]);
/// ```
pub struct LruCache<K, V> {
    map: HashMap<K, usize>,
    nodes: Vec<Node<K, V>>,
    head: usize,
    tail: usize,
    capacity: usize,
}

impl<K: Hash + Eq + Clone, V> LruCache<K, V> {
    /// Creates an empty cache that holds at most `capacity` entries.
    ///
    /// # Panics
    ///
    /// Panics if `capacity` is zero.
    ///
    /// ```should_panic
    /// let cache: lru::LruCache<u32, u32> = lru::LruCache::new(0);
    /// ```
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "capacity must be at least 1");
        LruCache { map: HashMap::with_capacity(capacity), nodes: Vec::with_capacity(capacity), head: NIL, tail: NIL, capacity }
    }

    /// The number of entries.
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    /// Returns `true` if the cache holds no entries.
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    fn unlink(&mut self, i: usize) {
        let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);
        if prev != NIL { self.nodes[prev].next = next } else { self.head = next }
        if next != NIL { self.nodes[next].prev = prev } else { self.tail = prev }
    }

    fn push_front(&mut self, i: usize) {
        self.nodes[i].prev = NIL;
        self.nodes[i].next = self.head;
        if self.head != NIL {
            self.nodes[self.head].prev = i;
        }
        self.head = i;
        if self.tail == NIL {
            self.tail = i;
        }
    }

    /// Returns the value for `key` and marks it as most recently used.
    ///
    /// The key can be any borrowed form of `K`:
    ///
    /// ```
    /// let mut cache = lru::LruCache::new(10);
    /// cache.put(String::from("config"), 42);
    /// assert_eq!(cache.get("config"), Some(&42)); // &str, no String needed
    /// ```
    pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        let i = *self.map.get(key)?;
        self.unlink(i);
        self.push_front(i);
        Some(&self.nodes[i].value)
    }

    /// Returns the value for `key` without changing the usage order.
    pub fn peek<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        self.map.get(key).map(|&i| &self.nodes[i].value)
    }

    /// Inserts or updates an entry, making it the most recently used.
    /// Returns the entry that was evicted to make room, if any.
    ///
    /// ```
    /// let mut cache = lru::LruCache::new(1);
    /// assert_eq!(cache.put("a", 1), None);
    /// assert_eq!(cache.put("b", 2), Some(("a", 1)));
    /// ```
    pub fn put(&mut self, key: K, value: V) -> Option<(K, V)> {
        if let Some(&i) = self.map.get(&key) {
            self.nodes[i].value = value;
            self.unlink(i);
            self.push_front(i);
            return None;
        }
        let evicted = if self.nodes.len() == self.capacity {
            let lru_key = self.nodes[self.tail].key.clone();
            self.remove(&lru_key).map(|value| (lru_key, value))
        } else {
            None
        };
        let i = self.nodes.len();
        self.nodes.push(Node { key: key.clone(), value, prev: NIL, next: NIL });
        self.map.insert(key, i);
        self.push_front(i);
        evicted
    }

    /// Removes an entry and returns its value.
    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        let i = self.map.remove(key)?;
        self.unlink(i);
        let removed = self.nodes.swap_remove(i);
        if i < self.nodes.len() {
            let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);
            if prev != NIL { self.nodes[prev].next = i } else { self.head = i }
            if next != NIL { self.nodes[next].prev = i } else { self.tail = i }
            *self.map.get_mut::<K>(&self.nodes[i].key).unwrap() = i;
        }
        Some(removed.value)
    }

    /// Iterates over the keys from most to least recently used.
    pub fn keys(&self) -> impl Iterator<Item = &K> {
        let first = (self.head != NIL).then_some(self.head);
        std::iter::successors(first, |&i| {
            let next = self.nodes[i].next;
            (next != NIL).then_some(next)
        })
        .map(|i| &self.nodes[i].key)
    }
}
Output
running 4 tests
test src/lib.rs - LruCache (line 18) ... ok
test src/lib.rs - LruCache<K,V>::get (line 84) ... ok
test src/lib.rs - LruCache<K,V>::new (line 44) - should panic ... ok
test src/lib.rs - LruCache<K,V>::put (line 112) ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

The should_panic doc test checks the documented panic. A crate ready for publishing would also add #![warn(missing_docs)] at the top so every public item must be documented.

Step 5: Sharing the cache between threads

get takes &mut self because it reorders the list, so even reads change the cache. Shared between threads it goes inside a Mutex, and each thread locks it briefly. Here eight workers look up exchange rates through a slow function; the cache makes repeated lookups nearly free.

Rust
use std::collections::HashMap;
use std::hash::Hash;
use std::sync::{Arc, Mutex};
use std::thread;
use std::time::{Duration, Instant};

// The LruCache from step 4, without docs.
const NIL: usize = usize::MAX;
struct Node<K, V> { key: K, value: V, prev: usize, next: usize }
struct LruCache<K, V> { map: HashMap<K, usize>, nodes: Vec<Node<K, V>>, head: usize, tail: usize, capacity: usize }

impl<K: Hash + Eq + Clone, V> LruCache<K, V> {
    fn new(capacity: usize) -> Self {
        LruCache { map: HashMap::new(), nodes: Vec::new(), head: NIL, tail: NIL, capacity }
    }
    fn unlink(&mut self, i: usize) {
        let (p, n) = (self.nodes[i].prev, self.nodes[i].next);
        if p != NIL { self.nodes[p].next = n } else { self.head = n }
        if n != NIL { self.nodes[n].prev = p } else { self.tail = p }
    }
    fn push_front(&mut self, i: usize) {
        self.nodes[i].prev = NIL;
        self.nodes[i].next = self.head;
        if self.head != NIL { self.nodes[self.head].prev = i }
        self.head = i;
        if self.tail == NIL { self.tail = i }
    }
    fn get(&mut self, key: &K) -> Option<&V> {
        let i = *self.map.get(key)?;
        self.unlink(i);
        self.push_front(i);
        Some(&self.nodes[i].value)
    }
    fn put(&mut self, key: K, value: V) {
        if let Some(&i) = self.map.get(&key) {
            self.nodes[i].value = value;
            self.unlink(i);
            self.push_front(i);
            return;
        }
        if self.nodes.len() == self.capacity {
            let lru = self.nodes[self.tail].key.clone();
            self.remove(&lru);
        }
        let i = self.nodes.len();
        self.nodes.push(Node { key: key.clone(), value, prev: NIL, next: NIL });
        self.map.insert(key, i);
        self.push_front(i);
    }
    fn remove(&mut self, key: &K) -> Option<V> {
        let i = self.map.remove(key)?;
        self.unlink(i);
        let removed = self.nodes.swap_remove(i);
        if i < self.nodes.len() {
            let (p, n) = (self.nodes[i].prev, self.nodes[i].next);
            if p != NIL { self.nodes[p].next = i } else { self.head = i }
            if n != NIL { self.nodes[n].prev = i } else { self.tail = i }
            *self.map.get_mut::<K>(&self.nodes[i].key).unwrap() = i;
        }
        Some(removed.value)
    }
}

// Pretend this calls a remote service.
fn fetch_rate(pair: &str) -> f64 {
    thread::sleep(Duration::from_millis(50));
    match pair {
        "EUR/USD" => 1.17,
        "GBP/USD" => 1.35,
        _ => 1.0,
    }
}

fn cached_rate(cache: &Mutex<LruCache<String, f64>>, pair: &str) -> f64 {
    if let Some(&rate) = cache.lock().unwrap().get(&pair.to_string()) {
        return rate;
    }
    // Not cached: fetch *without* holding the lock, so other threads aren't blocked for 50 ms.
    let rate = fetch_rate(pair);
    cache.lock().unwrap().put(pair.to_string(), rate);
    rate
}

fn main() {
    let cache = Arc::new(Mutex::new(LruCache::new(100)));
    let start = Instant::now();

    // Warm the cache, then let eight threads do 25 lookups each.
    cached_rate(&cache, "EUR/USD");
    cached_rate(&cache, "GBP/USD");
    let handles: Vec<_> = (0..8)
        .map(|worker| {
            let cache = Arc::clone(&cache);
            thread::spawn(move || {
                let pair = if worker % 2 == 0 { "EUR/USD" } else { "GBP/USD" };
                (0..25).map(|_| cached_rate(&cache, pair)).sum::<f64>()
            })
        })
        .collect();
    let total: f64 = handles.into_iter().map(|h| h.join().unwrap()).sum();

    println!("200 lookups, sum of rates {total:.2}");
    println!("finished in under 200 ms: {}", start.elapsed() < Duration::from_millis(200));
}
Output
200 lookups, sum of rates 252.00
finished in under 200 ms: true

Without the cache, 200 lookups at 50 ms each would take 10 seconds even spread over eight threads (about 1.25 s). Two things in cached_rate are typical of real caching code:

  • The lock is released before the slow call. Holding a Mutex during I/O would serialize every thread behind it.
  • Two threads missing the same key at the same moment will both fetch it. That's usually acceptable; if it isn't, the fix is a per-key "in flight" marker, which crates like moka implement.

Ideas for extending it

  • Replace the Mutex with sharding: N caches, each behind its own lock, chosen by the key's hash, so threads rarely contend.
  • Add get_or_insert_with(key, || compute()) so callers don't write the check-then-insert dance themselves.
  • Limit by total size in bytes instead of entry count, with a weigh: fn(&V) -> usize.
  • Compare with the lru and moka crates on crates.io, and benchmark with criterion.

Summary

  • An LRU cache is a hash map plus a usage-ordered list. Making both operations O(1) needs a doubly linked list whose nodes the map can reach directly.
  • In Rust, an index-linked list inside a Vec avoids Rc<RefCell<...>> and unsafe; swap_remove keeps removal O(1).
  • K: Borrow<Q> lets callers look up String keys with &str, exactly like HashMap.
  • Injecting a Clock makes time-based behavior testable without sleeping; composition (TtlCache wraps LruCache) adds features without touching the core.
  • Doc tests keep documentation examples correct, and model-based tests are a cheap way to check data structure code.
  • A cache shared across threads goes behind a Mutex; don't hold the lock while computing a missing value.

Next: Thread Pool.