Part 2 of 8 · 3 min read
What makes a key good
Four tests that a shard key should pass.
Think of dividing a large mail room between 10 clerks. If letters are split by street name, a clerk who gets "High Street" is swamped. If letters are split by the last digit of the house number, the work is even, but a request for "all letters for one household" means asking all clerks. The rule for splitting must suit both the workload and the questions.
The book "System Design Interview" says that the most important factor in sharding is the choice of the sharding key, also called the partition key, made of one or more columns that decide how data is distributed. A good key lets you find and change data efficiently by routing queries to the right database. One of the most important criteria is to choose a key that spreads the data evenly. In its example, user_id is the key and user_id % 4 decides the shard.
Shard key (partition key)
The shard key is the field, or set of fields, whose value decides which shard a record is stored on.
Example: in an orders table sharded by user_id, every order of user 812 lives on the shard chosen by the hash of 812.
Four tests:
- Even data. Each shard holds about the same amount of data. The key has many different values (high cardinality) with no value dominating.
- Even load. Each shard gets about the same traffic. No single key value gets much more than the rest.
- Queries stay local. The most frequent queries name the key, so each goes to one shard. Queries that do not name it become scatter/gather (module 5).
- Stable. The key's value never changes for a record. If it changes, the record must move between shards.
A worked example of the tests on country as the key of a user table. 70 percent of users are in one country; there are 200 countries.
- Even data: fails. One shard holds 70 percent.
- Even load: fails for the same reason.
- Queries stay local: "users in France" is local; "user 812" is not, unless country is known.
- Stable: usually, but users move.
user_id as the key: even data (millions of values), even load (unless some users are very popular), "user 812" is local, stable.
The trade-offs come from the book's list of difficulties that sharding brings:
- Resharding. Needed when a shard can no longer hold more data, or when some shards fill faster because of uneven distribution. It means changing the sharding function and moving data. The book says consistent hashing is a common cure (module 6).
- Celebrity problem (hot key). Excess access to one shard overloads it. The book's example is three very popular people whose data lands on one shard. One answer is a dedicated shard for each celebrity, which may itself need splitting.
- Joins and denormalisation. Joins across shards are hard. A common workaround is to denormalise [store copies of related data together] so a query reads a single table.
Check yourself:
- Why does a key that can change cause trouble?
- Which test does a timestamp key fail for a write-heavy log?