Build a concurrent key-value store

Single lock, sharded locks, or an owner thread: which should I present first?

The single lock, every time. It is the design whose correctness a reviewer can check by reading it, and it is the one you can have working in five minutes. Say the invariant out loud as you write it: every access to the map happens while the one lock is held. Then name the other two as alternatives you know and could reach for, and say what would make you reach. That order is what "answering at levels" means in a coding round, and it scores better than opening with the clever design and spending the rest of the time defending it.

Why does sharding make a two-key operation hard?

Because the operation now needs two locks rather than one, and two locks can be taken in two orders. A thread moving from a to b takes a shard lock then b shard lock; a thread moving from b to a takes them the other way round, and if each gets its first lock before the other gets its second, both wait for ever. The fix is to sort: decide a global order over the locks, shard index for example, and have every thread take them in that order. Also handle the case where both keys land in the same shard, because taking a plain lock twice from one thread deadlocks it against itself.

How many shards should I use?

More shards means fewer threads waiting on the same lock, and it costs one lock object and one dict per shard, plus a harder whole-store operation: a consistent snapshot or a size has to take every lock, in order. A fixed power of two, sixteen or thirty-two, is a reasonable answer to state and defend. What matters more than the number is saying that sharding buys you nothing when the traffic is concentrated on one hot key, because that key lives in exactly one shard and its lock is the single lock again.

Does the global interpreter lock make locking unnecessary in Python?

No. The GIL means one thread runs Python bytecode at a time; it does not mean a line of Python is one instruction. A read-modify-write such as reading a value, adding one, and storing it back is several bytecodes, and a thread can be switched out between any two of them. Check-then-act has the same shape. What the GIL does change is the payoff: for pure-Python work on a dict, sharded locks buy correctness-preserving structure rather than real parallelism, because the threads cannot run Python at the same time anyway. The comparison between the three designs still carries to any language, and to the free-threaded builds of Python that ship without the GIL.

When is the message-passing owner thread the right answer?

When operations that span several keys are common, when the state is awkward to lock finely, or when you want one place that decides everything so that ordering is obvious. The owner makes every multi-key operation atomic with no extra code and leaves no shared mutable state to race on. The price is a latency floor and a throughput ceiling: every operation pays a hand-off out and a hand-off back, and only one of them is in flight at a time. If your traffic is single-key and read-heavy, the owner is the wrong shape and a lock is better.