Key-Value Store: Trade-Offs and Wrap-Up

Trade-offs in a key-value store are the costs chosen at each earlier step, from the log on one machine to the quorum across copies. This lesson covers trade-offs and wrap-up, the last step of the interview method.

One failed copy is tolerated, two are not

The quorum from the copies lesson needs two copies up for a write or a read to count. The printout shows the point where failures stop being tolerated.

for alive in [3, 2, 1]:
    print("copies up:", alive, "write counts:", alive >= 2, "read counts:", alive >= 2)

A hot key stands out in the counts

In this run, 7 of the 10 requests ask for one key. That key's server takes most of the load while the others sit nearly idle.

requests = ["key-7", "key-7", "key-1", "key-7", "key-2", "key-7", "key-7", "key-3", "key-7", "key-7"]
counts = {}

for key in requests:
    counts[key] = counts.get(key, 0) + 1

for key in sorted(counts):
    print(key, "asked", counts[key], "times")
print("total requests:", len(requests))

More copies cost more storage for the same keys

The same keys are stored once with one copy and once with three copies. The entry count shows what the extra safety costs.

keys = ["name", "city", "job", "cart"]

for copies in [1, 3]:
    print("copies:", copies, "stored entries:", len(keys) * copies)

Example

requests = ["song-1", "song-1", "song-2", "song-1", "song-3", "song-1", "song-1", "song-1"]
counts = {}

for key in requests:
    counts[key] = counts.get(key, 0) + 1

for key in sorted(counts):
    print(key, "asked", counts[key], "times")

alive = 2
print("total requests:", len(requests))
print("copies up:", alive, "write counts:", alive >= 2, "read counts:", alive >= 2)

Key points

Failure shape: with copies on separate servers, one failed server leaves its ranges served by the copies that remain.
Hot key: a key asked for far more than the others, the hot spot from the Beginner course in a new shape.
Storage cost: more copies survive more failures and cost more storage for the same keys.
Read cost: a strong read asks more copies, and an eventual read asks fewer and answers faster.

In this example, 8 requests arrive and 6 of them ask for one hot key, while one of the three copies is down. The store still counts its writes and reads, and the hot key remains the load problem to fix.

Note

how replicas agree on a leader is covered in the Advanced course.

Try it Yourself

Edit the code, then press Run.

Running is simulated

requests = ["song-1", "song-1", "song-2", "song-1", "song-3", "song-1", "song-1", "song-1"]
counts = {}

for key in requests:
    counts[key] = counts.get(key, 0) + 1

for key in sorted(counts):
    print(key, "asked", counts[key], "times")

alive = 2
print("total requests:", len(requests))
print("copies up:", alive, "write counts:", alive >= 2, "read counts:", alive >= 2)

Key-value store trade-offs

Choice	Gain	Cost
More copies	Reads survive more failures	More storage and slower writes
Strong reads	The newest value comes back	More copies asked on each read
Eventual reads	A fast answer from one copy	An older value may come back
Compaction	A shorter log	Work spent rewriting the log

Exercise

What is a sound first move for a hot key?

Spread its reads across its copies and cache its value, so one server stops taking every request Move every other key onto the same server Raise W so each read asks more copies of the same server Delete the key so the load disappears