Range and hash partitioning

Sharding needs a rule that maps each key to a shard. There are two basic rules. Range partitioning gives each shard a block of neighboring keys. Hash partitioning runs each key through a hash function and uses the result to pick a shard. Each rule makes a different trade-off between scans and load balance.

The big idea

Range partitioning works like a phone book split into shelves: A to F on one shelf, G to M on the next. Looking up a range of names touches one shelf.

Hash partitioning works like shuffling index cards into numbered boxes. The boxes fill evenly, but a range of names is now scattered across all of them.

The phone book picture breaks when the names are not spread evenly. A shelf for "S" fills faster than a shelf for "Q".

Walking through it

Say orders have increasing IDs, and each shard owns a range.

Range partitions by order ID:
  shard 1: 1 to 1000
  shard 2: 1001 to 2000
  shard 3: 2001 to 3000

New orders: 2100, 2101, 2102 ...  → all land on shard 3
Shards 1 and 2 receive no new writes

That is a hot spot. Any monotonically increasing key, such as a timestamp or an auto-increment ID, sends all new writes to the last range.

Hash partitioning fixes that. The hash scatters consecutive IDs across shards, so writes spread evenly. The cost is that "orders 2100 to 2200" now has to ask every shard.

A middle path is a compound key. Cassandra hashes the first part of the key to choose the partition, then sorts by the rest inside it. PRIMARY KEY ((sensor_id), reading_time) makes "readings for one sensor in a time range" a single-partition scan, while writes from many sensors still spread out.

The trap of hash mod N

The simplest hash scheme is shard = hash(key) % N. It spreads keys evenly until N changes. Going from 4 to 5 nodes shows why:

A key stays put only if hash mod 4 == hash mod 5.
Over hash values 0 to 19 (the least common multiple of 4 and 5),
that holds only for 0, 1, 2 and 3.
Keys that stay: 4 / 20 = 20%
Keys that move: 80%

Moving 80% of your data to add 25% more capacity is a disaster for a database, and for a cache it causes a miss storm. The fix is consistent hashing, which moves only about one in N+1 keys when a node joins.

Common mistakes

• Range-partitioning on a timestamp or auto-increment ID. All new writes hit one shard.
• Expecting cheap range scans from hash partitioning. Hash partitioning turns every range query into a fan-out.
• Using hash mod N when the node count will change. Most keys move on every resize.

Check yourself

1. Why does a range-partitioned table keyed by auto-increment ID slow down as it grows?

Answer: All new rows fall in the last range, so one shard takes every write while the others sit idle.

2. Going from 4 to 5 nodes with hash mod N, roughly what share of keys move?

Answer: About 80%, because only 4 of every 20 hash values keep the same node.

Key takeaways

• Range partitioning keeps neighbors together and makes scans cheap, but sequential keys hot-spot.
• Hash partitioning spreads writes evenly, but it breaks range scans.
• A compound key hashes one part and sorts by the rest, combining both benefits.
• hash mod N moves most keys when N changes, so use consistent hashing.

Further learning

Next, see how a ring of nodes avoids most of that movement in consistent hashing.