progress

~/problems / Coordination / Condition variable

Cache that loads each key once

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium assessment 3 levels ~50 min DatabricksModal

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 for key:
    • If a value for key is stored, return it without calling loader.
    • Otherwise, if no load of key is in progress, this call runs the load: call loader(key) on the calling thread, store the value, and return it.
    • Otherwise, a load of key is already running on another thread. Wait until it finishes, then return the value it produced.
  • So loader runs 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 get for a stored key must return right away, even while other keys are loading. So don't hold a lock while loader runs. A loader may even call get for 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.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Condition variable. wait_for(predicate) + notify_all; always include a termination case.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc