Level 1 Load each key once
A service reads table metadata from slow storage: each read takes a long time. Many threads ask for the same few tables, so you put a cache in front of the storage. A plain cache has a nasty gap. When a popular key is missing, every thread that asks for it at that moment sees the miss and starts its own slow read, all for the same value. A single-flight cache closes that gap: the first thread to miss starts the load, and every other thread that wants that key waits for that one load to finish.
Build SingleFlightCache(loader, capacity=None). loader(key) is the slow function that fetches a value. capacity is for level 2; it is None here, which means no limit.
get(key)returns the value forkey:- If a value for
keyis stored, return it without callingloader. - Otherwise, if no load of
keyis in progress, this call runs the load: callloader(key)on the calling thread, store the value, and return it. - Otherwise, a load of
keyis already running on another thread. Wait until it finishes, then return the value it produced.
- If a value for
- So
loaderruns once per key: never twice for the same key, however many threads ask at once. - Loads of different keys must be able to run at the same time, and a
getfor a stored key must return right away, even while other keys are loading. So don't hold a lock whileloaderruns. A loader may even callgetfor another key itself. - Keys are strings. Values can be anything the loader returns, including
None.
Many threads share one cache, and the tests call it from up to 16 threads at once. Waiting must not burn CPU: block on a condition variable (or something built on one) instead of looping.
calls = []
def loader(key):
calls.append(key)
time.sleep(0.5) # slow storage
return key.upper()
cache = SingleFlightCache(loader)
# 5 threads call cache.get("users") at the same moment:
# all 5 return "USERS" after about 0.5 s, and calls == ["users"].
cache.get("users") # "USERS" at once, no new call
In C++ the loader is a function<string(const string&)>, and in Java a Function<String, String>. Values are strings there. The starters show the details.