~learn.
0:00 / 1:10
LLD · LRU cache

It's only a read, so it doesn't need a lock. Wrong.

transcript

A teammate removes the lock from get. It's only a read. In an LRU cache, that's wrong. Get writes.

Every get makes that key the most recent. The dict hands you A's node. That part really is a read. Then unlink A from its two neighbours. And push it to the front. About four pointer writes. Only then does the value go back.

Now two threads call get at once. On neighbouring nodes. Their pointer writes interleave. One node can end up pointing at a node that's gone. The dict still points at nodes the list has lost.

And the worst part? No crash. No error. The list just quietly loses entries.

Locking only put leaves get free to corrupt the list. So every operation that touches the order takes the lock. In CPython, one lock handles a few hundred thousand a second.

In an LRU cache, a read is a write. So even get takes the lock.

Full breakdown in the lecture.