KV Store - Thread-Safe

PracticalmediumPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

A key-value store that worked fine in one thread now sits behind a server handling many requests at once. Multiple threads call put, get, and erase on the same store concurrently, and the data must stay consistent: no lost writes, no torn reads, no two callers both winning the same conditional update. Your job is to make the store thread-safe and then make it efficient under a read-heavy load.

Level 1 - Global lock

Make every operation correct under concurrent access with a single lock.

put(key, value) stores the value.
get(key) returns the value, or None if absent.
erase(key) removes the key, returning True if it existed and False otherwise.
__len__ returns the number of stored keys.

Each operation must be safe to call from any thread at any time.

Example:

s.put("k", "v")
s.get("k")          -> "v"
s.erase("k")        -> True
s.get("k")          -> None

Level 2 - Efficient under read-heavy load

A single global lock serializes everything, including reads that don't conflict. Under a read-heavy workload that wastes throughput: two gets never interfere, yet one waits on the other.

Correctness from Level 1 must hold exactly: concurrent puts lose nothing, and concurrent gets of the same key all see a consistent value (never a half-written one). Throughput under a read-heavy workload should not be bounded by the number of readers - non-conflicting reads should proceed concurrently.

Example:

# 100 threads each write 100 distinct keys
len(s) == 10_000        # every write landed
 
# 50 threads each read the same key 100 times
all reads == "v"        # no torn reads

Level 3 - Atomic compound ops

Add two operations whose read and write must happen as one indivisible step:

def get_and_set(self, key: str, value: str) -> str | None
def compare_and_swap(self, key: str, expected: str | None, new: str) -> bool

get_and_set sets the key to value and returns the previous value (or None if it was absent).
compare_and_swap sets the key to new only if its current value equals expected, returning whether it did. expected=None means "only if the key is currently absent".

Between the read and the write inside each call, no other thread may observe or change the key. These primitives let callers build a retry loop (read, compute, swap, retry on failure) that never drops an update.

Example:

s.put("k", "old")
s.get_and_set("k", "new")            -> "old"   (k is now "new")
 
s.put("c", "1")
s.compare_and_swap("c", "1", "2")    -> True    (c is now "2")
s.compare_and_swap("c", "1", "3")    -> False   (current is "2", not "1")

Loading editor...

The live editor for this challenge unlocks with Premium.

Browse free problems

0/0 passed