Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 36 ยท Partitioning and Storage

Partitioning and Sharding

Learn how databases split data across nodes: range vs hash partitioning, hot spots, rebalancing, secondary indexes and consistent hashing with virtual nodes.

Replication copies the same data to several nodes. It helps with availability and read capacity, but every node still stores everything. When the data or the write rate outgrows one machine, you must split it: each node holds only a partition (also called a shard), and together the partitions hold the whole data set. Cassandra, MongoDB, DynamoDB, Kafka, Elasticsearch and Vitess all do this.

Partitioning is usually combined with replication: each shard has its own replicas. The central question of this lesson is deceptively simple: given a key, which shard owns it? Whatever answer you choose decides how evenly the load spreads, how painful it is to add a node, and which queries stay cheap.

Range partitioning

With range partitioning, each shard owns a contiguous range of keys, like volumes of an encyclopedia: Aโ€“F, Gโ€“M, Nโ€“Z. Keys stay sorted inside a shard, so a range scan ("all orders from March") touches one or two shards.

The weakness is hot spots. If the key is a timestamp, all of today's writes land on the one shard that owns "now", while the others sit idle. Ranges also need rebalancing when some turn out to hold far more data than others (names starting with "S" are more common than those with "X").

Hash partitioning

With hash partitioning, you hash the key and assign the hash value to a shard. Similar keys scatter evenly, which removes most hot spots. The price: neighbouring keys are on different shards, so range scans must ask every shard (a scatter-gather query).

A common compromise is a compound key: hash the first part to pick the shard, then keep the rest sorted inside it (for example, hash user_id, then sort by timestamp, so one user's history is a cheap range scan).

Range or hash?

Range Cheap range scans, but hot spots on sequential keys.
Hash Even spread, but range scans hit every shard.
Compound Hash one part, sort the rest.

Pick by the queries you run most.

1 / 2

Hot spots that hashing cannot fix

Hashing spreads different keys. If one key is extremely popular (a celebrity's profile, a viral product), all requests still go to the single shard that owns it. Typical remedies are to cache that key, or to split it deliberately, for example by appending a random suffix 0..9 to writes and reading all ten pieces back. The application must know which keys are hot.

Why not hash(key) % n?

Spreading by hash(key) % n_shards is easy, but when n changes almost every key moves to a new shard, so adding a node means copying nearly the whole data set. Two fixes are common:

  • Fixed number of partitions. Create many more partitions than nodes (say 1,000 partitions for 10 nodes). A key's partition never changes; only whole partitions move between nodes when a node joins. Elasticsearch and Kafka work roughly like this.
  • Consistent hashing. Nodes and keys are placed on a ring, and a key belongs to the next node clockwise. When a node joins or leaves, only its neighbours' keys move. See the DSA lesson on consistent hashing for the data-structure view; here we focus on the system view.

A shard router with virtual nodes

With only one point per node on the ring, the arcs have uneven lengths and some nodes get much more load. Giving each physical node many virtual nodes (points on the ring) evens this out, and a stronger node can simply get more virtual nodes than a weaker one. The router below hashes keys onto a ring, finds the owner with binary search, and reports the load per node.

Python Consistent hashing router with virtual nodes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With one point per node the busiest node carries well above its fair share, and even 10 points barely help in this run; with 200 it comes within about 10% of ideal. Adding a fifth node moved about 18% of the keys, close to the ideal 20%. Only keys that now belong to the new node moved. Compare that with the roughly 80% movement you would get from hash % n when going from 4 to 5 nodes.

Rebalancing in practice

Moving a shard to a new node is a live operation. Real systems copy the data in the background while still serving traffic, then switch the routing and delete the old copy. Two rules help: rebalance automatically only with human oversight (an overloaded node that is wrongly judged dead can trigger a cascade of moves that makes things worse), and throttle the copy so it does not starve normal traffic.

Clients need to know where shards live. Three common approaches are: any node forwards a request to the right node; a routing tier (proxy) knows the map; or the client keeps the map itself. A coordination service (see leader election and consensus) often stores the authoritative map, and nodes spread changes with gossip.

Secondary indexes

Partitioning by primary key makes key lookups easy. But what about "find all cars with color = red"? There are two designs:

  • Local (document-partitioned) index. Each shard indexes only its own rows. A write touches one shard, but a read must query all shards and merge the results (scatter-gather).
  • Global (term-partitioned) index. One index covers all data and is itself partitioned, by the indexed value. A read goes to one index shard, but a single write may update several index shards, usually asynchronously, so the index can lag.
Python Scatter-gather versus a global index

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The local index makes writes cheap and reads expensive; the global index does the opposite. Choose by which side your workload leans on.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main downside of hash partitioning?

    Hashing destroys key order, so neighbouring keys live on different shards and range queries must scatter-gather.
  2. 2. Why do systems use many virtual nodes per physical node?

    A single point per node leaves arcs of very different lengths. Many virtual points average out the arc sizes.
  3. 3. A single celebrity key receives most of the traffic. Why doesn't hash partitioning solve this?

    Hashing spreads different keys, not requests for the same key. You need caching or key splitting.
  4. 4. With a local (document-partitioned) secondary index, how does a query by a non-key column work?

    Each shard only indexes its own rows, so any shard may hold matches.

Summary

  • Sharding splits data so that each node stores part of it; combine it with replication for availability.
  • Range partitioning supports range scans but creates hot spots; hash partitioning spreads load but scatters ranges.
  • Avoid hash % n; use a fixed number of partitions or consistent hashing with virtual nodes so that adding a node moves only about 1/n of the data.
  • Popular single keys remain hot spots and need caching or splitting.
  • Local secondary indexes make writes cheap and reads scatter-gather; global indexes make reads cheap and writes more complex.

Next: Distributed Transactions: 2PC and Sagas, what to do when one operation touches several shards.