Range, hash and directory partitioning

Gatepass sharded its bookings by city, and it worked until Mumbai grew to ten times the size of every other city. One shard sat at 90% CPU while the rest idled. Sharding by city was a decision about where rows live, and it turned out to be the wrong one. This lesson compares the three basic ways to make that decision and what each one makes easy or painful.

Partitioning, briefly

Partitioning (often called sharding) splits one big dataset into pieces, each stored on a different node. Every row lives in exactly one partition. You do it when the data no longer fits on one machine, or one machine can't keep up with the write load.

The job of a partitioning scheme is to answer two questions fast:

1. Given a key, which partition holds the row?
2. Given a query, which partitions must I ask?

A good scheme spreads data and traffic evenly, so no node is the bottleneck, and keeps related queries on few partitions, so a request doesn't have to fan out to everyone. Those two goals pull against each other, and the strategies below make different trades.

Range partitioning

Sort the keys and cut the sorted order into contiguous ranges. Partition 1 holds show ids 0 to 29, partition 2 holds 30 to 59, and so on. A shop catalogue might split by name: A to F on one node, G to M on the next.

Strengths. Range scans are cheap. "All shows between 40 and 59" is served by one partition. Order is preserved, so "next 20 results" is simple. Locating a key is a binary search over a small table of boundaries.

Weakness: skew. Ranges are even in key space, not in traffic. If keys are timestamps or auto-increment ids, every new write goes to the last partition while the old ones go cold. A time-series table partitioned by day has this problem built in: today's partition takes all the writes.

Fixes exist. Lead the key with something well spread (a prefix like city_id or a bucket number) so writes spread, at the price of scans needing to ask each prefix. Or split ranges dynamically when they grow, which is what HBase and Spanner do.

Hash partitioning

Run the key through a hash function and take the result modulo the number of partitions. Keys that look similar end up far apart, so load spreads very evenly regardless of key patterns. Sequential ids, which crush range partitioning, are no problem.

Strengths. Even distribution without effort. Point lookups ("get show 57") touch exactly one partition.

Weaknesses. You lose order. A range query like "shows 40 to 59" scatters across every partition, so it must fan out to all of them and merge. Cassandra and DynamoDB accept this: you query by partition key, and only the data within a partition is kept sorted. The second problem is that plain hash mod N reshuffles almost everything when N changes. That is the subject of the rebalancing lesson.

A useful middle: a compound key. Hash the first part to choose the partition, and sort by the second part inside it. Partition by show_id, sort by booking_time, and "all bookings for this show, newest first" is a single-partition range scan.

Directory partitioning

Keep an explicit lookup table: key (or key group) to partition. The service consults the directory, then goes to the right node.

Strengths. Total freedom. You can put a giant tenant on its own node, move one customer without moving anyone else, group data by region for legal reasons, or place related entities together. Rebalancing is just copying data and updating a table row.

Weaknesses. The directory is a new system with its own needs. It must be fast (cached at every router), highly available (every request depends on it), and consistent (two routers disagreeing about where a key lives is data corruption). It also grows with the number of entries, which is why directories usually map groups of keys rather than each one.

Gatepass's multi-tenant admin tool uses this: each organiser account maps to a partition, and a very large organiser can be moved to a dedicated one.

Try the three side by side

Switch strategies and watch the load bars. Then turn on the hot key and slide the scan window.

RangeHashDirectory

One blockbuster show (hot key)

Keys are cut into contiguous ranges. Great for range scans; newest keys pile onto the last partition.

Scan window start (20 shows)40

P1

8%

P2

19%

P3

31%

P4

42%

Hottest vs fair share

1.67x

1.00x is perfectly even

Scan touches

1 of 4

partitions for the 20-show window

Busiest partition

P4

42% of all traffic

What you should see:

• Range gives the cheapest scans (one partition) but the lopsided load, because newer shows are busier.
• Hash evens the load across partitions but a scan touches all of them.
• Directory balances load best, by placing heavy keys deliberately, but its scans land wherever the table put the keys.
• With the hot key on, all three fail the same way. One show carries most of the traffic, and a single key can only live on one partition. No placement rule fixes that. The next lesson does.

Choosing

• Range scans and ordered reads dominate: Range, with a key that spreads writes
• Point lookups by id, huge write volume: Hash
• Few big tenants, special placement rules: Directory
• Mixed: lookups by id plus "recent for this id": Hash on id, sorted within

Before picking, ask three things: What are my top three queries? Which key do they all share? Does that key spread traffic evenly today, and will it in a year? A key that is right for the query but skewed in traffic (city, in Gatepass's case) calls for either a finer key (city plus show id) or a different strategy.

Check yourself

Gatepass stores one row per booking and wants to show 'the last 50 bookings for this event' quickly, while spreading millions of bookings evenly. Which design fits best?

ARange partition by booking timeBHash partition by booking idCHash partition by event id, sorted by booking time within the partitionDA directory with one entry per booking

Key takeaways

• A partitioning scheme answers two questions: which partition holds this key, and which partitions does this query need.
• Range keeps order and makes scans cheap, but sequential keys create hot partitions.
• Hash spreads load evenly and makes point lookups cheap, but destroys order and fans out range queries.
• A directory allows any placement, at the cost of running a highly available lookup service.
• No scheme can split a single hot key. That needs a different technique.