Build a concurrent key-value store

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

The single lock. It is the design whose correctness a reviewer can check by reading, and you can have it working and tested in five minutes. Say the invariant as you write it: every access to the dict happens while the lock is held, and an increment holds it from its read to its write. Then name striped locks, copy on write and an owner thread as the alternatives, and say what would make you reach for each.

Why does an increment need a lock when each line is short?

Because it is a read, an add and a write, and Python may switch threads between any two bytecode instructions. Two threads can both read 5, both compute 6, and both store 6, so one increment is lost. The Python FAQ lists D[x] = D[x] + 1 among the operations that are not atomic. Holding one lock across the read and the write makes them one step as far as other threads can see.

How do striped locks avoid a deadlock in a transfer between two keys?

Every operation that needs two stripes takes them in one global order, lowest index first. A transfer that took the source stripe and then the destination stripe would meet a transfer the other way round, each holding the lock the other wants. On this page the build forces that deadlock with two Barrier meetings and records both acquires failing. Sort a set of the two indices, so that two keys on one stripe take that lock once: a plain Lock taken twice by the same thread waits for itself for ever.

How do you take a consistent snapshot of a striped store?

Take every stripe lock in the same order a transfer uses, copy every stripe while holding them all, then release. Taking the stripes one at a time can see a transfer half done. If snapshots are frequent and writes rare, copy on write is the alternative: each write copies the dict under a write lock and swaps it in, readers take no lock, and a snapshot is a read-only view of the current dict.

Why does hash() of a string matter when testing a striped store?

Because the hash of a str is salted with a random value per process unless PYTHONHASHSEED is set, so a key can land on a different stripe from one run to the next. That is harmless for the store, since a stripe only has to be stable while the process lives. A test must not assume which stripe a string lands on. Ask the store for each key's stripe and choose keys that share one, or keys that do not.