Part 6 of 6 · 4 min read
Exercises
Easy
Easy 1: Name the two operations (15 minutes)
Name the two core operations a key-value store supports.
Done when: put and get are both correctly named.
Hint
Put and get.
Easy 2: State what makes a lookup fast (15 minutes)
State what data structure typically makes a key-value lookup fast, instead of scanning every record.
Done when: an index, specifically a hash map from key to location, is correctly named.
Hint
A hash map (an index) mapping each key to the location of its value.
Easy 3: State what a plain key-value store cannot do (15 minutes)
State what kind of query a plain key-value store cannot answer directly.
Done when: searching or finding records by a field other than the exact key is correctly identified as unanswerable without a secondary index or a full scan.
Hint
Searching or finding by a field other than the exact key; this is not directly answerable without a secondary index or a full scan.
Medium
Medium 1: Decide the key for a caching scenario (25 minutes)
The bookstore wants to cache the rendered HTML of each book's product page. Propose a reasonable key design, and explain what the value would hold.
Done when: a reasonable key is proposed, such as a key combining a fixed prefix with the book's ID, for example "page:book:1", with the value holding the rendered HTML for that book's page.
Hint
A key such as "page:book:1", with the value holding that book's rendered HTML page.
Medium 2: Explain why partitioning is simple here (25 minutes)
Explain, in your own words, why a key-value model partitions more easily than a model requiring secondary indexes.
Done when: the explanation correctly notes that because every access names an exact key, the responsible machine can be determined from the key alone, with no need to coordinate across machines, unlike a secondary index, which can match records spread across many machines.
Hint
Because every access names an exact key, the responsible machine is determined from the key alone with no cross-machine coordination needed, unlike a secondary index, which can require matching records across many machines.
Medium 3: Diagnose a missing-index scenario (30 minutes)
A key-value store holding ten million carts starts taking several seconds per lookup. Propose the most likely cause and a fix.
Done when: a missing or broken index is correctly proposed as the most likely cause, since without one, each lookup must scan a growing number of records, and the proposed fix is building or restoring a hash-map index from key to location.
Hint
A missing or broken index is the likely cause, since lookups would then require scanning a growing number of records; rebuilding the hash-map index is the fix.
Hard
Hard 1: Design a workaround for a by-content query (30 minutes)
The bookstore needs to occasionally find every cart that contains a specific book, using a plain key-value store with no secondary index. Propose a workaround.
Done when: a reasonable workaround is proposed, such as maintaining a second key-value mapping from book ID to a list of cart IDs containing it, updated manually in application code whenever a cart's contents change.
Hint
Maintain a second key-value mapping from book ID to a list of cart IDs containing it, updated by application code whenever a cart changes.
Hard 2: Decide durable versus caching-only for two scenarios (35 minutes)
The bookstore wants a key-value store for session carts, which can be safely rebuilt if lost, and a separate key-value store for order confirmations, which must never be lost. Decide which should be durable and which can be caching-only, and justify it.
Done when: session carts are correctly assigned to a caching-only store, since losing one is an acceptable, recoverable inconvenience, while order confirmations are correctly assigned to a durable store, since losing one would be a genuine data-loss problem.
Hint
Session carts can be caching-only, since losing one is a recoverable inconvenience; order confirmations must be durable, since losing one is a genuine data-loss problem.
Hard 3: Trace a request through partitioning (40 minutes)
A key-value store is partitioned by hash of key across eight machines. Trace what happens, step by step, when a client requests get("cart:501").
Done when: the trace correctly includes hashing the key, determining which of the eight machines' assigned hash ranges the result falls into, and routing the request to only that one machine, without contacting any of the other seven.
Hint
Hash the key, determine which of the eight machines' hash ranges it falls into, and route the request to only that one machine, leaving the other seven uncontacted.