Key-value store - quorums, and where the consistency knob sits

Ask these before drawing anything

• What is the access pattern - get and put by a single key, or are there range scans and secondary lookups? A store that must answer "all orders for this customer, newest first" is a different design, and bolting a secondary index onto this one is the most common way to ruin it.
• What does a stale read cost? This is the question the whole board turns on. If a stale read is merely annoying, the default can be ONE and the system is fast and cheap. If it is money or a permission, every read pays a quorum.
• Can the application resolve conflicts? Vector clocks are only useful if somebody downstream knows how to merge two versions. If the answer is no, last-write-wins is the honest choice and its cost must be written down rather than avoided.
• How large is a value, and is it ever appended to? Large values and growing values are different failure modes: one blows the row size, the other makes compaction never finish.
• What is the delete volume? Deletes are writes here, and a high-delete workload is the one that turns compaction into the bottleneck.
• Single region or multi? Cross-region quorums cost 80 ms per operation, which usually means the answer is local quorums plus asynchronous replication, which is a weaker guarantee and must be said out loud.

Functional

• get(key) and put(key, value) on an opaque value, plus delete.
• Tunable consistency per REQUEST, not per cluster: ONE, QUORUM, or ALL.
• Replication factor of 3, configurable per keyspace.
• A node may be added or removed without downtime and without moving more than its share of the token space.
• Survive the loss of any single node with no loss of availability for reads or writes at QUORUM.
• Repair divergence automatically - on read, in the background, and after an outage.

Non-functional

• p99 of 10 ms for a QUORUM read, 15 ms for a QUORUM write, measured at the coordinator.
• 99.99 percent availability for QUORUM operations, which given N=3 means surviving one replica down per partition and no more.
• Durability: a write acknowledged at QUORUM must survive the immediate loss of any one node. That is a statement about fsync of the commit log, not about replication, and the two are frequently confused.
• Linear scale-out: doubling the nodes doubles the throughput and halves the per-node data, with no rewrite of existing data beyond the moved token ranges.
• No single point of failure and no elected leader on the request path.

Out of scope, and each of these is a whole other system

• Multi-key transactions. Not supported, not partially supported, and not emulated in the client.
• Secondary indexes. A global secondary index over a partitioned store is a distributed transaction wearing a friendly name.
• Range scans across partitions. The partitioner destroys ordering by design.