Part 7 of 8 · 3 min read
Choosing between ranges and hashes
A short procedure and three worked cases.
Choosing between ranges and hashes
Think of choosing how to file customer letters. Filing by surname is good when you look up one customer. Filing by date is good when you read a month's mail. You cannot have both with one pile, so decide which question comes most often.
A procedure:
- List the main reads and writes. Single-key reads? Range scans? Which key do they use?
- Find the write pattern. Are writes sequential in the key (time, counters)? Then range partitioning on that key makes a hot spot.
- Pick range if range scans on the key matter and the writes are spread. Pick hash if reads are by key and writes need an even spread.
- Consider a compound key: hash the first part, sort by the rest.
- Plan for hot keys: which items could become very popular?
- Check the sizes. Will the largest partition fit on one node in a year?
Case 1: user profiles, read by user id. Hash on user id. Every request names one user. No range scans. Even spread.
Case 2: a log of events with queries "all events from yesterday". Pure time ranges make a hot spot for writes, so prefix the key: (source_id, time). Writes spread over sources, and queries per source over a time range are cheap. Queries over all sources in a time range touch all partitions.
Case 3: a leaderboard of scores, read as "top 100". Range partitioning by score puts the top players on one partition, which every read hits. A cache of the top 100 (Level 3) takes that load. Writes by player id hashed spread well.
A worked comparison of sizes. 1,000,000,000 records of 500 bytes is 500 GB. Nodes hold 100 GB each. With 5 partitions, each is at its limit, and a growth of 20 percent overflows. With 20 partitions of 25 GB, each is at a quarter of the limit, and there is room to grow. Many systems create more partitions than nodes at the start for this reason (module 5).
Interview angle
Answer in your head first, then open it.
What is sharding and why use it?
Splitting data across machines to scale size and writes. Different from replication, which copies. Normally both are used together.
Range or hash partitioning?
Range for range scans, with the risk of hot spots on sequential keys. Hash for an even spread, losing range queries. Mention the compound key.
What is a hot spot and how do you fix it?
A partition with far more load. Fix by changing the key, splitting a hot key into sub-keys, caching, or moving it to its own node.
How would you partition this system?
Name the key, say why it spreads the writes, and say which queries it makes cheap and which touch every partition.
Check yourself:
- You store chat messages and read the latest 50 in one conversation. Which key suits, and why?
- Why create more partitions than nodes at the start?
Words you will meet
| Word | Plain meaning |
|---|---|
| Partition, shard | One piece of a data set, held on one node (and its copies) |
| Partitioning, sharding | Splitting data into pieces across nodes |
| Shared-nothing | Each node has its own CPU, memory and disk |
| Skew | An unfair split of data or load |
| Hot spot | A partition with far more load than the rest |
| Key-range partitioning | Each partition holds a continuous range of keys |
| Hash partitioning | A hash of the key decides the partition |
| Range scan | Reading all keys between two values |
| Compound key | A key of several parts: the first hashed, the rest sorted |
| Hot key | One key with very high traffic |
| Sub-key | One of several keys a hot key is split into |
| Network partition | A fault that cuts the network between nodes (not the same thing) |