Build a concurrent cache

Why can a thread-safe LRU cache not use a reader-writer lock for get?

Because a get is not a read. A hit moves the key to the fresh end of the recency order, so every get writes to shared state, and a reader-writer lock lets any number of readers in at once. Two gets inside together are two writers of the order with nothing between them. In a recorded run of the model, one reader takes a key out of the dict to move it and a second reader, let in beside it, misses a key the cache holds. Take one lock for get and put alike, and say why when you do.

How do I stop several threads loading the same missing key at once?

Keep a record of loads in flight, keyed by the cache key, and consult it under the same lock as the data. The first thread to miss registers a flight and runs the loader; every later thread that misses on that key finds the flight and waits on its event instead of calling the loader. When the load finishes, the loader publishes the value and removes the flight under the lock, then sets the event. The recorded run shows two misses on one key and one call to the loader.

Should the loader run while the cache lock is held?

No. The lock guards the dict, and a load can take as long as a network call. Held across the load, it makes a hit on an unrelated key wait for somebody else's miss. A recorded run of the model shows it: a thread asking for a key the cache already holds is refused the lock on every turn the load takes. Register the flight under the lock, release it, load, then take the lock again only to publish.

What happens to the waiters when a load fails?

Every thread waiting on that flight gets the same error, and nothing is cached. The loader's exception is stored on the flight, the flight is removed under the lock, and the event is set, so each waiter wakes and re-raises it. Because nothing was stored, the next caller after the failure starts a fresh load. Returning None instead would make a failure look like a miss, and a caller that retries on a miss would load again.

Is functools.lru_cache thread-safe, and why not use it?

Its documentation says the cache is threadsafe, meaning the underlying data structure stays coherent during concurrent updates. It also says the wrapped function may be called more than once if another thread calls before the first call has completed and been cached, and a recorded run shows exactly that. It has a size limit and no expiry. For a cache in front of a slow load that must run once per key and expire, you write a class like the one built here; for memoising a pure function, lru_cache is the right tool.