# LRU Cache

Course: [Low-Level Design](https://www.devtutorials.ai/learn/system-design/lld) · Section: LLD Case Studies
Source: https://www.devtutorials.ai/learn/system-design/lld/case-studies/lru-cache

> Build a least-recently-used cache with O(1) get and put, using a Map that remembers order, and check it against a speed test.

QuickBite’s menu service takes 200 milliseconds to load a restaurant’s menu. Because many customers view the same popular restaurants, loading those menus repeatedly wastes time.

A cache solves this problem by keeping recently used menus in memory. When a requested menu is already in the cache, the system can return it quickly instead of loading it again.

However, the cache has limited space. When it becomes full, the system must remove one menu before adding another. This case study uses an LRU cache, which removes the item that has not been used for the longest time.

**In simple words:** you will build a fast, limited-size cache that keeps recently used menus and removes the least recently used menu when it becomes full.

## What You Will Learn

In this case study, you will:

1. See why a cache needs a size limit.
2. Understand Least Recently Used (LRU) eviction.
3. Use a Map that remembers order to get O(1) get and put.
4. Measure whether a cache helps with its hit rate.
5. Build the cache in the sandbox and pass the hidden tests, including a speed test.

"Design an LRU cache" is one of the most common LLD interview questions. The key word is **O(1)**: both reading and writing must take the same short time, however big the cache is.

## Step 1: Agree on the Requirements

Before any code, write down what the system must do. In an interview, say these out loud and ask if they are right.

### What It Must Do

- `new LRUCache(capacity)`, holding at most `capacity` entries.
- `get(key)` returns the value, or `undefined`, and marks the key as just used.
- `put(key, value)` adds or updates; when full, it first removes the least recently used key.
- Updating a key does not grow the cache, and marks it as just used.
- Both `get` and `put` are O(1).

### What We Leave Out

- Expiry by time (that is a TTL cache, practised below).
- Sharing the cache between servers (that is a distributed cache, like Redis).

Leaving things out on purpose is not lazy. It keeps the design small enough to finish, and you can say how you would add them later.

## Step 2: Find the Classes

A simple trick: underline the **nouns** in the requirements. Most of them become classes. The **verbs** become methods.

| Class | Its one job |
|---|---|
| LRUCache | Stores entries and keeps them in order from least to most recently used |
| Map | Gives O(1) lookups and remembers insertion order |

## Step 3: Build the Key Parts

### Why a Limit at All?

A cache keeps answers in memory so the next request is fast. But memory is not free. A cache with no limit grows until the server runs out.

For example, a plain `Map` that stores a menu for restaurants 1 to 100,000 ends up with **100,000 entries**. Nothing ever leaves. A real cache needs a size limit.

Here is the code:

```ts runnable title="Without a limit, a cache grows forever"
const cache = new Map<string, string>();
for (let i = 1; i <= 100000; i++) cache.set("restaurant:" + i, "menu " + i);
console.log("entries:", cache.size);
```

Expected output:

```text
entries: 100000
```

### Least Recently Used

When the cache is full, something must go. **LRU** (Least Recently Used) removes the item nobody has asked for in the longest time. Things people use often stay.

### The Trick: a Map Remembers Order

The classic answer uses a hash map plus a doubly linked list. In JavaScript, a `Map` already does both jobs: lookups are O(1), and it remembers the order keys were added.

Step through three keys going into a `Map`: dosa, idli, vada. The first key is always the oldest:

Here is the same idea in code:

```ts runnable title="A Map remembers the order keys were added"
const m = new Map<string, number>();
m.set("dosa", 1);
m.set("idli", 2);
m.set("vada", 3);
console.log([...m.keys()]);
console.log("oldest:", m.keys().next().value);
```

Expected output:

```text
[
  "dosa",
  "idli",
  "vada"
]
oldest: dosa
```

### Marking a Key as Just Used

To move a key to the "most recent" end, delete it and set it again.

In the last two steps of the animation, using dosa turns the order dosa, idli, vada into **idli, vada, dosa**. Now idli is the oldest.

Here is the code:

```ts runnable title="Delete and set again: the key moves to the end"
const m = new Map<string, number>([["dosa", 1], ["idli", 2], ["vada", 3]]);

function touch(key: string): void {
  const v = m.get(key)!;
  m.delete(key);
  m.set(key, v); // now the most recently used
}

touch("dosa");
console.log([...m.keys()]);
```

Expected output:

```text
[
  "idli",
  "vada",
  "dosa"
]
```

**Easy way to remember:** think of a stack of plates. Every plate you use goes back on **top**. When the shelf is full, you take away the plate at the **bottom**: nobody has used it for the longest time.

### Removing the Oldest

Step through `put` on a cache with capacity 2. Putting a, b and then c evicts **a** and leaves **b, c**:

Here is the same idea in code:

```ts runnable title="Evict the oldest when full"
const capacity = 2;
const m = new Map<string, string>();

function put(key: string, value: string): void {
  if (m.has(key)) m.delete(key);
  else if (m.size >= capacity) {
    const oldest = m.keys().next().value as string;
    m.delete(oldest);
    console.log("evicted", oldest);
  }
  m.set(key, value);
}

put("a", "1");
put("b", "2");
put("c", "3");
console.log([...m.keys()]);
```

Expected output:

```text
evicted a
[
  "b",
  "c"
]
```

### Is the Cache Helping?

Count **hits** (found in the cache) and **misses** (had to load). A cache with a low hit rate is just using memory.

Step through six requests: r1, r2, r1, r1, r3, r2. The result is **3 hits, 3 misses, a 50% hit rate**:

Here is the same idea in code:

```ts runnable title="Count hits and misses to see if the cache helps"
class CountingCache {
  private readonly m = new Map<string, number>();
  hits = 0;
  misses = 0;
  get(key: string, load: () => number): number {
    if (this.m.has(key)) { this.hits++; return this.m.get(key)!; }
    this.misses++;
    const v = load();
    this.m.set(key, v);
    return v;
  }
}

const c = new CountingCache();
for (const id of ["r1", "r2", "r1", "r1", "r3", "r2"]) c.get(id, () => id.length * 100);
console.log(`hits ${c.hits}, misses ${c.misses}, hit rate ${Math.round((c.hits / (c.hits + c.misses)) * 100)}%`);
```

Expected output:

```text
hits 3, misses 3, hit rate 50%
```

An LRU cache is not safe on its own when many threads share it: two puts at once can both see "not full" and grow it past capacity. In JavaScript the event loop runs one thing at a time, but in Java or C# you need a lock, as in Concurrency Basics.

## Lab: Build It

Build `LRUCache`. The hidden tests check eviction order, updates, and that 400,000 operations finish quickly (so no scanning the whole cache).

1. Keep a private `Map`. In `get`, move a found key to the end.
2. In `put`, delete an existing key first; otherwise, when full, delete the first (oldest) key. Then set the key.
3. Write `size` and `keys()` from the map.

Open the lab in the sandbox. Run the tests after each step. A failing test names the situation that broke, not the test code.

## Predict the Output

<CsPredict id="lru-1" code={"var order = new List<string> { \"a\", \"b\", \"c\" };\nvoid Touch(string k) { order.Remove(k); order.Add(k); }\nTouch(\"a\");\nTouch(\"c\");\nConsole.WriteLine(order[0]);\nConsole.WriteLine(string.Join(\",\", order));"} expected={"b\nb,a,c"} why="Touching a key moves it to the end. After touching a then c, the least recently used key at the front is b." />

## Common Mistakes

| Mistake | Wrong | Correct | Why it happens |
|---|---|---|---|
| No refresh on get | get returns the value but leaves it old. | Delete and set the key on every get. | Reading feels like it should not change anything. |
| Scanning for the oldest | Looping over every entry to find the least recent. | Use the order the Map keeps. | Timestamps look like the obvious solution. |
| Update grows the cache | put on an existing key evicts another key. | Delete the existing key first, then set. | Treating every put as a new key. |
| No capacity check at 1 | capacity 0 makes a cache that holds nothing. | Refuse a capacity below 1. | Edge cases are not in the happy-path test. |
| Unsafe sharing | Two threads put at once and pass the size check. | Lock in multi-threaded languages. | JavaScript hides the problem with its single thread. |

## Practice

## What to Remember

- A cache needs a **limit**, or it grows forever.
- **LRU** removes the item unused for the longest time.
- A **Map** gives O(1) lookups and remembers order.
- **Delete and set** a key to mark it as just used.
- Check the **hit rate** to know if the cache helps.

## Further Reading

These are the sources used to check this case study:

- [MDN: Map](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map): insertion order and O(1) operations.
- [Wikipedia: Cache replacement policies](https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU): LRU and other eviction rules.
- [Redis: Key eviction](https://redis.io/docs/latest/develop/reference/eviction/): how a real cache evicts keys.

Next: **Rate Limiter**. You will build a class that stops one user from flooding the system.