Data Partitioning: Range, Hash & Consistent Hashing Explained

When a dataset grows too large or too busy for a single machine, you split it across many machines. That splitting is called partitioning (or sharding). The hard part isn't the splitting itself — it's deciding which key goes to which node, keeping the load even, and making sure that when you add or remove a node, you don't have to shuffle the entire dataset across the network.

There are three classic strategies: range partitioning, hash partitioning, and consistent hashing. We'll work through each with the same small dataset so you can see exactly how keys get assigned — and we'll finish by proving, with real numbers, why consistent hashing moves so much less data than plain hashing.

Our Sample Dataset

We'll partition 12 user records across our cluster. To partition by anything other than raw range, we first run each key through a hash function to get a number. The actual function (MD5, MurmurHash, etc.) doesn't matter for the concept; what matters is that it spreads keys evenly. Here are our 12 keys with their (illustrative) hash values:

key       hash(key)
-------   ---------
user1        701
user2        312
user3        890
user4        145
user5        623
user6        508
user7        234
user8        977
user9        456
user10       781
user11        89
user12       350

We start with a 4-node cluster: N0, N1, N2, N3. Let's place these keys using each strategy.

1. Range Partitioning

Range partitioning assigns a contiguous range of keys to each node. You keep keys in sorted order and cut the keyspace into bands. If we partition by the user name alphabetically:

Node N0  →  keys A–F
Node N1  →  keys G–M
Node N2  →  keys N–S
Node N3  →  keys T–Z

A lookup is trivial: to find "michael", you see it falls in G–M and go straight to N1. The big win is efficient range scans — "give me all users from G to M" hits a single node, because related keys live together.

Strengths:

• Range queries and sorted scans are fast (data is ordered and co-located).
• Simple to reason about; easy to find which node owns a key.

Weaknesses:

• Hotspots. If keys aren't evenly distributed — say half your users' names start with S — node N2 is overwhelmed while others idle. Time-based ranges are the classic trap: if you partition logs by date, today's partition takes 100% of the writes while older nodes sit idle.
• You must choose the range boundaries carefully and sometimes rebalance them as data skews.

This is what databases like HBase, Google Bigtable, and partitioned/clustered tables use. It's the right choice when ordered access matters.

2. Hash Partitioning (mod N)

Hash partitioning spreads keys evenly by computing the node from the key's hash. The classic formula is:

node index = hash(key) mod N, where N = number of nodes

With N = 4 nodes, we compute hash(key) mod 4 for each key. Let's calculate (remember x mod 4 is the remainder after dividing by 4):

key       hash    hash mod 4   → node
-------   ----    ----------       ----
user1      701       1            N1
user2      312       0            N0
user3      890       2            N2
user4      145       1            N1
user5      623       3            N3
user6      508       0            N0
user7      234       2            N2
user8      977       1            N1
user9      456       0            N0
user10     781       1            N1
user11      89       1            N1
user12     350       2            N2

Result:
  N0: user2, user6, user9
  N1: user1, user4, user8, user10, user11
  N2: user3, user7, user12
  N3: user5

Notice the spread is reasonably even and order is destroyed on purpose — consecutive users land on different nodes. That kills range scans, but it prevents hotspots: no single node absorbs all the "today" writes.

Strengths: uniform load distribution; no hotspots from skewed key names; lookup is a one-line calculation.

The fatal weakness — adding or removing a node. The node count N is baked into the formula. The moment you add a 5th node, the formula becomes hash(key) mod 5, and almost every key is reassigned. Let's prove it.

The Problem: What Happens When You Add a Node

Recompute every key with mod 5 instead of mod 4 and compare:

key      hash   mod 4 (old)   mod 5 (new)   moved?
------   ----   -----------   -----------   ------
user1     701      N1            N1           —
user2     312      N0            N2           MOVED
user3     890      N2            N0           MOVED
user4     145      N1            N0           MOVED
user5     623      N3            N3           —
user6     508      N0            N3           MOVED
user7     234      N2            N4           MOVED
user8     977      N1            N2           MOVED
user9     456      N0            N1           MOVED
user10    781      N1            N1           —
user11     89      N1            N4           MOVED
user12    350      N2            N0           MOVED

Keys moved: 9 of 12  =  75%

Three quarters of the data has to physically move across the network just to add one machine. In a real cluster with terabytes of data, this is catastrophic — a storm of data transfer, cache invalidation, and degraded performance, all to grow capacity by 25%.

This isn't bad luck with our numbers. It's mathematical: when you change mod N to mod N+1, a key stays put only if it happens to land on the same node in both — roughly a 1/(N+1) chance. So on average about N/(N+1) of all keys move. Going 4→5 nodes, that's 4/5 = 80% expected (we got 75%). The bigger the cluster, the worse it gets.

Plain hash mod N gives you a beautiful, even distribution — and punishes you brutally every time the cluster size changes. This is the exact pain consistent hashing was invented to solve.

3. Consistent Hashing

The key insight of consistent hashing is to stop tying the key's location to the number of nodes. Instead, we map both keys and nodes onto the same circular space — a hash ring.

Here's the recipe:

1. Imagine a ring of hash values from 0 up to some maximum (real systems use 0 to 2³²−1; we'll use 0 to 999 to keep the math readable).
2. Place each node on the ring by hashing its name. Say they land at: N0→120, N1→370, N2→640, N3→850.
3. Place each key on the ring using its hash value.
4. Assignment rule: each key belongs to the first node you meet walking clockwise from the key's position. If you walk off the end (past 999), you wrap around to the lowest node.

Let's assign our 12 keys. For each key, find the first node position that is ≥ the key's hash (wrapping to N0 at 120 if none):

Ring positions:  N0=120   N1=370   N2=640   N3=850

key      hash   first node clockwise   → node
------   ----   --------------------       ----
user11     89   next ≥ 89  is 120         N0
user4     145   next ≥ 145 is 370         N1
user7     234   next ≥ 234 is 370         N1
user12    350   next ≥ 350 is 370         N1
user2     312   next ≥ 312 is 370         N1
user9     456   next ≥ 456 is 640         N2
user6     508   next ≥ 508 is 640         N2
user5     623   next ≥ 623 is 640         N2
user1     701   next ≥ 701 is 850         N3
user10    781   next ≥ 781 is 850         N3
user3     890   none ≥ 890 → wrap to 120  N0
user8     977   none ≥ 977 → wrap to 120  N0

Result:
  N0 (120): user11, user3, user8
  N1 (370): user4, user7, user12, user2
  N2 (640): user9, user6, user5
  N3 (850): user1, user10

The Payoff: Adding a Node to the Ring

Now add a 5th node, N4, which hashes to position 500 on the ring — it slots in between N1 (370) and N2 (640). Here's the magic: nothing else on the ring moves. The only keys affected are those that now find N4 before N2 — i.e. keys whose hash falls in the arc (370, 500], the segment N4 just took over from N2.

Which of our keys are in that arc? Let's check the keys previously owned by N2 (the only node that can lose any):

N2 previously owned: user9 (456), user6 (508), user5 (623)

  user9  hash 456  → in (370, 500]?  YES  → now owned by N4
  user6  hash 508  → in (370, 500]?  no (508 > 500) → stays on N2
  user5  hash 623  → in (370, 500]?  no             → stays on N2

Keys moved: 1 of 12  =  ~8%

New layout:
  N0: user11, user3, user8
  N1: user4, user7, user12, user2
  N4: user9                     ← newly created node
  N2: user6, user5
  N3: user1, user10

Only one key moved instead of nine. Every key not in N4's new arc stays exactly where it was, on the same node, untouched. Adding capacity no longer triggers a cluster-wide reshuffle — it just peels off a thin slice from one neighbor.

Why Consistent Hashing Moves So Little Data

Here's the intuition to lock in. With mod N, the divisor is the node count, so changing the node count changes the result for nearly every key — locations are computed relative to N. With consistent hashing, a key's position on the ring is fixed forever by its own hash; it doesn't care how many nodes exist. Adding a node only changes ownership of the arc that the new node now covers — on average just K / N keys (here, 12/5 ≈ 2 keys' worth of arc). Everything else keeps its owner.

Plain hash: locations depend on N, so changing N relocates ~N/(N+1) of all keys.
Consistent hash: locations depend only on the key, so changing N relocates only ~K/N keys — the new node's share.

The same logic applies to removing a node: its keys simply flow to the next node clockwise, and no other key is disturbed.

One Catch: Uneven Distribution & Virtual Nodes

Look back at our ring result — N1 ended up with 4 keys while N3 had only 2. With a handful of nodes placed at random points, the arcs between them are uneven, so load is lumpy. Worse, when a node dies, all of its load lands on a single neighbor instead of being shared.

The fix is virtual nodes (vnodes). Instead of placing each physical node once, you place it on the ring many times under different labels — e.g. N1-a, N1-b, N1-c, … each at its own hashed position. A physical node now owns dozens of small arcs scattered around the ring rather than one big arc.

• Smoother load: many small arcs average out, so each physical node gets a near-equal share.
• Graceful failure: when a node dies, its many small arcs are inherited by many different neighbors, spreading the extra load instead of crushing one.
• Heterogeneous hardware: give a beefier server more vnodes so it naturally takes a proportionally larger share.

This is exactly how production systems do it — Amazon DynamoDB, Apache Cassandra, Riak, and many caching layers all use consistent hashing with virtual nodes.

Choosing a Strategy

1. Need ordered scans / range queries? Use range partitioning — but watch for hotspots from skewed or time-based keys.
2. Need even load and your cluster size is fixed? Plain hash partitioning is simple and effective.
3. Need even load and the cluster will grow, shrink, or suffer failures? Use consistent hashing with virtual nodes — the default for elastic, large-scale distributed datastores and caches.

Conclusion

Partitioning is about two competing goals: spread the load evenly, and minimize the cost of change. Range partitioning preserves order but risks hotspots. Plain hash partitioning spreads load beautifully but reshuffles most of your data whenever the cluster changes size. Consistent hashing breaks that dependency on node count — a key's home is fixed by its own hash, so growing or shrinking the cluster touches only a thin slice of data. Add virtual nodes and you also get smooth, fair distribution and graceful failure handling. That combination is why it underpins the largest distributed databases and caches in the world.

At TechTrailCamp, partitioning strategy and consistent hashing — and the internals of systems like DynamoDB and Cassandra — are exactly the kind of decisions our architecture consulting helps teams get right, grounded in real production systems.