Skip to content
Tutorials Center
My learning

Topics

Lesson 125 of 132 ยท Projects

Project: LRU Cache with Safe and Unsafe Variants

Build an LRU cache three ways in Rust: a simple VecDeque version, an O(1) safe version with an index-linked list, and a raw-pointer version with unsafe and Drop.

An LRU cache (least recently used) keeps at most N entries. Every time you read or write an entry it becomes the "freshest" one, and when the cache is full the entry that was touched longest ago is thrown away. Browsers, databases and web servers all use this idea to keep hot data close and cold data out of memory.

The textbook design is a hash map for lookups plus a doubly linked list that keeps entries in order of use. Both operations then take constant time: the map finds a node, and the list lets you unlink it and move it to the front without scanning. In most languages that is a pleasant afternoon. In Rust it is a famous ownership puzzle, because a doubly linked list gives every node two owners (the node before it and the node after it), and a node is also reachable from the map. Safe Rust wants exactly one owner per value.

This project solves the puzzle three ways, from simplest to most dangerous, and shows how to decide between them.

The design in one picture

flowchart LR
    Map["HashMap<br/>key to node"] -.-> B
    Head["head"] --> A["A (freshest)"]
    A <--> B["B"]
    B <--> C["C (stalest)"]
    Tail["tail"] --> C

The map finds a node in O(1). The list orders the nodes: reads move a node to the head, and eviction removes the tail.

The operations are always the same, whichever variant we build:

  • get(key): look the node up; if found, unlink it and push it to the front; return its value.
  • put(key, value): if the key exists, update it and move it to the front. Otherwise, if the cache is full, evict the tail first; then insert the new node at the front.

Variant 1: the simple version

Before reaching for pointers, build the version that is obviously correct. Keep the values in a HashMap and the order in a VecDeque of keys, freshest at the front. Touching a key means finding it in the deque (a scan, so O(n)), removing it and pushing it to the front. For caches of a few dozen entries this is perfectly fine, and it is a useful reference to compare against.

Rust Variant 1: HashMap plus VecDeque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Two details to notice. put returns the evicted pair, so a caller can write dirty data back to a database before it disappears. And K: Clone is required because a key lives twice, once in values and once in order. The next variants keep that requirement.

Variant 2: a safe O(1) cache with an index-linked list

The ownership trouble comes from using references or boxes to link nodes. The trick used by many Rust libraries is to stop linking nodes to nodes and link them to positions in a Vec instead. A "pointer" becomes a plain usize index, which is Copy, owns nothing and cannot dangle in a way the borrow checker can see. The Vec is the one owner of all nodes; the links are just numbers. A sentinel value (usize::MAX) plays the role of null.

Because the cache has a fixed capacity, the Vec never needs more than capacity slots. When the cache is full, the new entry reuses the slot of the evicted tail, so there is no free list to manage.

Rust Variant 2: safe doubly linked list on a Vec

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The output is identical to Variant 1, but every operation is O(1). The cost is bookkeeping: the code that moves nodes is full of index arithmetic, and a mistake there gives wrong behavior (a stale list, a lost node) rather than a compile error. What the compiler still guarantees is memory safety: an out-of-range index panics with a clear message instead of corrupting memory. For production code this variant, or the well-tested lru crate, is almost always the right choice.

Look at detach. It reads prev and next into local variables first, so the shared borrow of the node ends before the code writes to its neighbors. With references to nodes, that same function would need two mutable borrows of the Vec at the same time. Copying the two indices out is what makes it compile.

Variant 3: raw pointers and unsafe

Safe Rust cannot express "this node is owned by the list but also pointed to by the map and by its two neighbors". With raw pointers it can, as long as you uphold the rules the compiler can no longer check. The idea:

  1. Allocate each node on the heap with Box::new, then leak it into a raw pointer with Box::leak. From that moment nobody owns it automatically.
  2. Store pointers as NonNull<Node> (a raw pointer that is never null) in the map and in the nodes' prev/next fields.
  3. Free a node yourself, exactly once, by turning the pointer back into a Box with Box::from_raw and dropping it.
  4. Implement Drop for the cache, so that dropping it frees every remaining node.

The invariants you must maintain, and that every // SAFETY: comment below refers to, are: every pointer in the map or in a link points to a live node allocated by this cache; each node appears in the list once; and a node leaves the map and the list before it is freed.

stateDiagram-v2
    [*] --> Leaked: Box::new + Box::leak
    Leaked --> Linked: push_front, map.insert
    Linked --> Linked: get / put (detach + push_front)
    Linked --> Freed: evict or Drop (Box::from_raw)
    Freed --> [*]

The life of one node. The only legal way out is exactly one Box::from_raw; two would be a double free, none would be a leak.

To prove there are no leaks and no double frees, the demo stores values of a type with a Drop implementation that counts how many are alive.

Rust Variant 3: unsafe doubly linked list with raw pointers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Check the three promises the output makes. After the eviction of b the live count is 3, not 4: the evicted value was handed back and dropped once. Updating c drops the old value in place. And after the scope ends, alive is 0: Drop for LruCache freed every remaining node exactly once. A leak would leave the count above zero, and a double free would crash or print a name twice.

Choosing between the variants

Variant Complexity Memory safety When to use it
HashMap + VecDeque O(n) touch Guaranteed by the compiler Tiny caches, prototypes, a test oracle
Index-linked Vec O(1) Guaranteed by the compiler (bugs panic or misorder, never corrupt memory) Almost everything
Raw pointers O(1) Your responsibility Learning, or a measured bottleneck

Be honest about the last row. Raw pointers do not make this cache meaningfully faster than Variant 2, since both do a hash lookup and a few pointer updates, and Variant 2 stores nodes contiguously, which is friendlier to the CPU cache. The standard advice from the unsafe Rust and unsafe data structures lessons applies: write the safe version first, measure, and reach for unsafe only when you can name the invariant you are taking over. Tools such as Miri (which interprets your program and detects use-after-free and double free) are the way to test unsafe code; they are not available in the browser runner, so run them locally with cargo +nightly miri test.

Real-world notes for taking this further: this cache is not Send or Sync (raw pointers opt out), so share it between threads behind a Mutex, as in Mutex and RwLock, and a sharded cache (several small caches chosen by hash) reduces lock contention.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is a doubly linked list awkward in safe Rust?

    Box gives single ownership, and references need lifetimes that cannot describe a cycle of neighbors. That is why the safe designs use indices or Rc/Weak, and the unsafe design uses raw pointers.
  2. 2. In Variant 2, what does usize::MAX (the NIL constant) stand for?

    Indices replace pointers, so a sentinel value plays the role of null. Option<usize> would also work but takes more space.
  3. 3. Why does Variant 3 call Box::leak when it creates a node, and Box::from_raw when it removes one?

    Leaking turns the Box into a pointer that nothing frees automatically. Box::from_raw rebuilds the Box so that the normal drop runs once. Doing it twice is a double free; never doing it is a leak.
  4. 4. What does the alive = 0 line at the end of the Variant 3 demo show?

    Each Tracked value decrements the counter when it drops. A zero total means every node, and so every value, was freed.
  5. 5. When should you prefer the raw-pointer variant over the index-linked one?

    Unsafe moves the proof obligation from the compiler to you. Without a measured benefit it only adds risk.

Summary

  • An LRU cache is a hash map for lookup plus a doubly linked list for recency; get and put both move a node to the front, and eviction removes the tail.
  • A doubly linked list fights Rust's single-ownership rule, because neighbors and the map all point at the same node.
  • The simple HashMap + VecDeque version is easy to get right but touches in O(n).
  • Replacing pointers with Vec indices gives O(1) operations in 100% safe code and is the practical default.
  • Raw pointers (NonNull, Box::leak, Box::from_raw) can express the classic design, but every unsafe block needs a stated invariant, and Drop must free each node exactly once.
  • Test equivalent variants against each other, and use a counting Drop type to catch leaks and double frees.

Next: Rust Reference: Keywords, std Types and Traits