Partitioning Strategies: Range vs Hash

How a database splits data across machines by key range or by key hash, what each does to range queries and hot spots, and how compound keys give you some of both.

Overview

Partitioning (also called sharding) splits one large dataset into pieces, called partitions, and puts different partitions on different machines. Each record belongs to exactly one partition. The point is to spread both the data and the work: with ten machines, each stores about a tenth of the data and handles about a tenth of the reads and writes.

That only works if the split is even. If one partition gets much more data or traffic than the others, it becomes a hot spot and limits the whole system. So the core question is how to map a key to a partition so that load spreads evenly, while the queries you need still touch as few partitions as possible. There are two basic answers, by key range and by key hash, plus a compound key that mixes them.

Partitioning is usually combined with replication: each partition has copies on several machines. This topic is about how keys are split; how copies are kept in step is covered in the replication topics.

Partition by key range

Sort the keys and give each partition one continuous range, like the volumes of an encyclopedia. To find a key, look up which range contains it.

Because keys stay in order, a query for all keys between two values reads only the partitions that cover that range. That is ideal for time ranges, prefixes and sorted listings. Bigtable keeps rows in key order and splits a table into row ranges called tablets; HBase calls its ranges regions and splits a region in two when its files pass a size limit (10 GiB by default).

The risk is uneven load. The boundaries must follow the actual data (far more names start with S than with X), so good systems choose them automatically by splitting large ranges. And some key patterns send all new writes to one range. The classic case is a timestamp key: every write carries the current time, so every write lands in the last partition while the others sit idle.

Partition by hash of the key

Run the key through a hash function and partition by the hash instead. A good hash spreads similar keys (user:1001, user:1002) to unrelated places, so data and traffic spread evenly even when the keys themselves are clustered.

The price is that key order is gone. A range query on the key can no longer read a few neighboring partitions; it has to be sent to all of them and the results merged (scatter/gather). Cassandra hashes the partition key with Murmur3 by default. MongoDB offers both ranged and hashed shard keys; with a hashed key, each chunk holds a range of hash values, and the docs note that range queries on the shard key then usually go to every shard.

Why not hash mod N

The obvious hash scheme, hash(key) % N for N machines, breaks when N changes. Moving from 10 to 11 machines changes the answer for almost every key, so almost all data must move. The code below measures it, and compares a hash ring where each node owns many small slices.

hash mod N — About 91% (a key stays only if both remainders match: 10 of every 110 hash values)
Hash ring with many tokens per node — About 8 to 9% in the run above; ideally 1/11, only what the new node takes
Fixed partitions, moved whole — Exactly what the new node takes; covered in Rebalancing Partitions

Consistent hashing and virtual nodes

Consistent hashing places the hash space on a ring. Each node takes one or more positions (tokens) on the ring and owns the stretch of ring before each of them. A key belongs to the first token at or after its hash. When a node joins, it takes over slices next to its tokens; every other key stays where it was.

With one token per node, the slices are uneven and a new node relieves only one neighbor. Virtual nodes fix that by giving each machine many tokens, so each machine holds many small slices spread around the ring. Amazon's Dynamo paper describes this design. Cassandra calls the setting num_tokens: the cassandra.yaml default has been 16 since Cassandra 4.0, while earlier releases used 256; since 3.0 an optional allocation algorithm can pick tokens that balance load, instead of choosing them at random (4.0 enables it by default).

Compound keys: hash first, then sort

Many stores combine the two methods. In Cassandra's primary key, the first part (the partition key) is hashed to choose the partition, and the remaining clustering columns sort rows inside that partition.

One sensor, any time range — One: rows are sorted by time inside it
All sensors, last hour — All: the time range is not part of the partition key
One sensor, one exact reading — One

The design rule follows: put in the partition key whatever your main queries always know exactly (a user, a sensor, a tenant), and put what they scan over (time, sequence) in the clustering columns. Keep each partition bounded, for example by adding a day or month to the partition key for a sensor that reports forever.

Hot spots and skewed keys

Hashing spreads different keys, but it cannot split one key. If a single key gets a huge share of traffic (a celebrity's account, a viral post, today's date), its partition is hot no matter how good the hash is.

This is called write sharding or salting. The DynamoDB guide describes two versions: a random suffix, which spreads writes best but means a single item must be looked for under every suffix, and a suffix calculated from another attribute (such as the order ID), which lets you compute where one item lives. Either way, reads of the whole key cost N queries, so apply it only to keys you know are hot, and track which ones those are.

Choosing between them

Spread of load — Even only if keys and boundaries are well chosen — Even across distinct keys — Even across partition keys
Range query on the key — Reads few partitions — Asks every partition — Cheap inside one partition key
Sequential keys (time, counters) — Hot last partition — Spread out — Spread out if the partition key is not time
Examples — Bigtable, HBase, MongoDB ranged shard keys — Cassandra, MongoDB hashed shard keys — Cassandra primary keys, DynamoDB partition and sort key

What you will be able to do

Explain the trade between range scans and even load in range and hash partitioning.
Show with numbers why hash mod N is a poor partitioning scheme.
Describe consistent hashing and why virtual nodes improve it.
Design a compound key so the main queries hit one partition.
Recognize a hot key and split it, and say what that costs readers.

Key concepts

Partition (shard): One piece of a dataset, stored on one machine (plus its replicas). Every record belongs to exactly one partition.
Range partitioning: Each partition owns a continuous range of sorted keys. Range scans are cheap; sequential keys create a hot last partition.
Hash partitioning: Partitions own ranges of hash values instead of key values. Load spreads evenly across keys, but range queries must ask every partition.
Consistent hashing: Nodes own slices of a hash ring. Adding a node moves only the keys in the slices it takes, instead of reshuffling almost everything as hash mod N does.
Virtual nodes (tokens): Many ring positions per machine, so each machine holds many small slices and a new machine takes load from many others.
Compound primary key: A hashed partition key that picks the partition plus clustering columns that sort rows inside it, as in Cassandra and DynamoDB.
Hot spot: A partition that receives far more data or traffic than the others and limits the whole cluster.
Scatter/gather: Sending a query to every partition and merging the answers. Its latency is set by the slowest partition.

When to use it

Choosing a shard key or partition key for a large table in a design interview
Explaining why a query without the partition key becomes a scatter/gather across all nodes
Designing storage for time series, where sequential keys cause write hot spots
Handling a celebrity account, viral item or other single hot key

Interview questions

How would you partition a time-series store for millions of sensors?
Why does hash mod N move so much data, and what do real systems do instead?
When would you choose range partitioning over hash partitioning?
A celebrity with 50 million followers posts, and one partition melts. What do you do?