Sharding and Partitioning, In Depth

A single database server has a ceiling: finite disk, finite memory, finite CPU, and a finite number of requests per second it can answer. When your data or traffic grows past that ceiling, you split the data into pieces and spread those pieces across many machines. The word for one such piece is a partition (a slice of the whole dataset), and when partitions live on different machines to share the load, each machine's slice is often called a shard. This chapter is about how to cut the data, where to put the pieces, how to move them around as you grow, and which queries get harder once the data no longer lives in one place.

Two fundamentally different cuts exist, and it helps to name them before anything else.

Vertical partitioning splits a table's columns into groups. Horizontal partitioning, also called sharding, splits a table's rows into groups. Both are covered below, starting with vertical because it is the simpler idea.

Vertical partitioning means taking a wide table and splitting its columns into separate tables (or separate services), grouped by how they are used. A users table might hold login fields, profile fields, and billing fields all together. Vertical partitioning pulls those apart so that hot, frequently-read columns are not dragged along with cold, rarely-touched ones.

The payoff is that each piece can be stored, cached, scaled, and secured on its own. Login reads stay small and fast; sensitive billing columns can sit behind stricter access controls; a rarely-read bio blob does not bloat the rows that the login path scans. Taken to its logical end, vertical partitioning by domain is how a monolith's one big database becomes a database-per-service.

The natural limit matters: vertical partitioning helps only until one of the resulting pieces is itself too big or too busy for a single machine. When the login table alone has two billion rows, splitting off billing did not help. At that point you need to split rows, not columns — which is horizontal sharding.

Horizontal partitioning splits the rows of a table across multiple machines, so that no single machine holds the whole table. Every shard has the same schema (the same columns); it just holds a different subset of the rows. A shard is one such machine (or logical group) holding one subset.

The question that decides everything about a sharded system is: given a row, which shard does it belong on? You answer it by choosing a partition key (also called a shard key) — one or more columns whose value maps each row to a shard. Get that choice right and load spreads evenly and queries stay cheap. Get it wrong and one machine melts while the others idle, and common queries turn into expensive fan-outs. The next section is entirely about that choice, because it is the single most consequential decision here.

The partition key is the column whose value decides which shard a row lands on. Because you build the whole routing scheme on top of it, a poor key is painful to undo later. Four properties make a key good.

• Even distribution. Values should spread rows roughly equally across shards, so no single machine holds a disproportionate share of the data or traffic.
• Aligned with the common query. Your most frequent lookups should include the key, so the system can go straight to one shard instead of asking all of them.
• Stable over time. The key's value for a row should not change, because changing it means physically moving the row to a different shard.
• High cardinality. Cardinality is the number of distinct values a column can take. High cardinality (many possible values, like user_id) gives the system enough distinct buckets to spread load; low cardinality (few values, like country or a boolean) cannot.

Two failure shapes deserve a name. A low-cardinality key cannot create enough buckets — sharding on a boolean gives you exactly two groups no matter how many machines you own. A monotonically increasing key, most often a timestamp or auto-increment id, is worse than it looks: every new row has a larger key than the last, so every insert lands on whichever shard owns the highest range. That newest shard takes all the writes while older shards go idle — the classic hot-latest-partition problem.

insert at 10:00  -> key 1699999001 -> shard "newest"
insert at 10:01  -> key 1699999061 -> shard "newest"
insert at 10:02  -> key 1699999121 -> shard "newest"   (every write, one shard)

A common fix when you genuinely need time ordering is a compound key — combine the timestamp with something high-cardinality and evenly spread, like (user_id, created_at). Writes then scatter across shards by user while still sorting by time within each user.

Now to strategies for turning a key into a shard assignment. Range partitioning assigns contiguous ranges of the key to shards: keys A–H on shard 1, I–P on shard 2, Q–Z on shard 3. Each shard owns a band of the key space.

shard 1: keys "A" .. "H"
shard 2: keys "I" .. "P"
shard 3: keys "Q" .. "Z"

The big win is range scans: a query like "all orders from March 1 to March 31" touches only the one or two shards that own that band, and the rows come back already sorted. Range partitioning keeps related, adjacent keys physically together, which is exactly what time-series and alphabetical browsing want.

The matching risk is a hot range: if activity clusters in one band of the key space, the shard owning that band gets hammered while others idle. Range-partitioning on a timestamp reproduces the hot-latest-partition problem — today's band is where every write goes. Range partitioning is the right call when range scans dominate and the key's activity is spread across the whole range, not piled into one corner of it.

Hash partitioning runs the key through a hash function — a function that scrambles any input into a fixed-size pseudo-random number — and uses that hashed value to pick the shard. Because a good hash spreads even similar inputs to wildly different outputs, load ends up spread evenly almost by construction.

shard = hash(key) % number_of_shards

Even distribution is the whole point: user_1000 and user_1001 land on different shards, and no single band of the key space can become a hot range, because hashing destroys the ordering that created the band. This is the safest default for point lookups — "give me the row for this exact key."

The cost is that hashing kills range scans. Since adjacent keys are scattered to unrelated shards, a query for "all keys from A to H" now has to ask every shard, because those keys could be anywhere. You have traded cheap range queries for even load. There is also a subtle rebalancing trap hiding in that innocent % number_of_shards, which the rebalancing section below dismantles.

Plain hash-mod partitioning has a nasty property: change the number of shards and almost every key moves (shown next section). Consistent hashing is a scheme designed to avoid that. Picture the range of hash values bent into a circle — a hash ring. Each shard is placed at one or more points on the ring by hashing its name. To find a key's shard, you hash the key to a point on the ring and walk clockwise to the first shard you meet.

The magic is what happens on change. Add a node and it inserts itself at its ring positions, taking over only the keys in the arcs immediately before those points — roughly 1/N of all keys, where N is the node count. Every other key stays exactly where it was. Remove a node and its arcs pass to the next nodes clockwise; again only that node's share moves. Compare that to hash-mod, where changing N reshuffles nearly everything.

One refinement makes it practical: virtual nodes (vnodes). Instead of placing each physical machine at a single ring point, you place it at many (say 100–200) points. This smooths distribution — a single random point per node produces lumpy arcs and uneven load — and it lets a departing node hand its arcs to many neighbors instead of dumping everything on one. Virtual nodes also make heterogeneous hardware easy: give a bigger machine more vnodes and it naturally owns a bigger share of the ring.

The strategies so far compute the shard from the key. Directory partitioning instead looks it up: a separate mapping service holds an explicit table of "this key (or key range) lives on this shard," and every request consults it first.

This is the most flexible option. You can place any key on any shard, move a single hot customer to a dedicated machine, split a busy range in half, or migrate keys gradually — all by editing the mapping, with no hashing math to respect. It is how you get fine-grained control that formulas cannot express.

The flexibility has two costs. First, every request pays an extra lookup hop to the directory before it can reach the data, adding latency. Second, the directory is now critical shared state: if it is slow the whole system is slow, and if it is wrong requests go to the wrong shard. In practice the directory itself must be replicated and cached (often cached right on the clients) to keep it fast and available — which means it inherits all the replication concerns of any other critical datastore.

Rebalancing is moving partitions between machines so load stays even as you add capacity, lose a node, or watch some shards grow faster than others. The goal is to move as few keys as possible while doing it, because every moved key is bytes copied over the network and a window where routing must stay correct.

Start with what not to do. The naive shard = hash(key) % N breaks catastrophically on rebalance. Growing from 4 shards to 5 changes N from 4 to 5, and since hash(key) % 4 and hash(key) % 5 disagree for almost every key, nearly the entire dataset has to move at once.

key hashes to 100
  with N=4:  100 % 4 = 0   -> shard 0
  with N=5:  100 % 5 = 0   -> shard 0   (coincidence)
key hashes to 101
  with N=4:  101 % 4 = 1   -> shard 1
  with N=5:  101 % 5 = 1   -> shard 1   (coincidence)
key hashes to 102
  with N=4:  102 % 4 = 2   -> shard 2
  with N=5:  102 % 5 = 2   -> shard 2
key hashes to 103
  with N=4:  103 % 4 = 3   -> shard 3
  with N=5:  103 % 5 = 3   -> shard 3
key hashes to 104
  with N=4:  104 % 4 = 0   -> shard 0
  with N=5:  104 % 5 = 4   -> shard 4   (moved!)

The widely used fix is to decouple the number of partitions from the number of nodes. Create a large, fixed number of partitions up front — say 1024 — far more than you will ever have machines. Each node simply owns a bunch of those partitions.

Now hash(key) % 1024 never changes — a key's partition is fixed for life. Rebalancing only reassigns whole partitions to nodes. Add a third node and it claims about a third of the partitions from the existing nodes; only the keys in those partitions move, and every other key stays put. This "fixed large partition count" approach is exactly the mechanism consistent hashing's virtual nodes give you in ring form.

Two more rebalancing moves round it out. Splitting a partition: when one partition grows too large or too hot, cut it into two and let one half migrate to another node — this is how range-partitioned systems relieve a hot range. Moving a partition on scale-out: when you add capacity, hand whole partitions from busy nodes to the new node until load evens out. A good rule of thumb: never rebalance automatically the instant a node looks slow — a brief blip can trigger a stampede of copying that makes things worse. Move partitions deliberately.

Even a perfectly chosen key can fail against one specific pattern: a single key that is enormously more popular than the rest. If one celebrity account has fifty million followers, every request touching that account hits whichever shard owns it, and that shard is on fire while its neighbors nap. No hash function saves you, because the skew is in the access, not the key distribution — one key is simply hot.

The mitigations all share one idea: stop letting a single key map to a single place.

• Split the hot key. Break the one logical key into sub-keys — celebrity#1, celebrity#2, … celebrity#16 — write across all of them, and combine on read. The load of one key now spreads over sixteen shards.
• Add a random suffix and scatter. A write-side version of the same trick: append a small random number to the key so writes fan out across shards, then gather the pieces at read time.
• Give it a dedicated shard or cache. Detect the hot key and put it on its own machine, or (for read-heavy hotness) in front of a cache so the shard barely feels the traffic. A celebrity's profile that is read a million times and written once is a perfect cache candidate.

Which one fits depends on whether the hotness is on reads (cache it) or writes (split/scatter it). The recurring lesson is that the average case and the worst case need different treatment, and the worst case is usually one specific key.

Once data is spread across shards, something has to answer "which shard holds this key?" for every request and send it there. Three common arrangements exist, and they trade simplicity against extra hops and coupling.

• Routing / proxy tier. A dedicated middle layer receives every request, looks up the shard, and forwards it. Clients stay dumb and know nothing about sharding, which makes changing the layout easy — but the proxy adds a network hop and is one more tier to run and scale.
• Client-aware routing. The client library itself holds (a cached copy of) the shard map and connects straight to the right shard, saving the extra hop. The price is that routing logic now lives in every client, so a layout change must propagate to all of them, and stale client maps can misroute.
• Coordinator node. A request lands on any node, and if that node does not own the key it forwards to (or names) the node that does. No separate tier, but nodes take on routing duty and forwarding adds internal traffic.

There is no free option: you either pay a hop (proxy), pay coupling (client-aware), or pay internal forwarding (coordinator). Which is cheapest depends on how often the layout changes and how much you can trust clients to stay current.

A secondary index is a lookup structure on a column that is not the partition key — for example, sharding users by user_id but wanting to find users by email. Because the index column does not decide the shard, indexing across shards has two designs, and they push the cost onto opposite sides.

• Local / document-partitioned index. Each shard indexes only its own rows. Writes are cheap — a row and its index entry live together on one shard, so one write touches one shard. But a query on the indexed column must ask every shard, because a matching row could be anywhere. That fan-out-and-combine pattern is scatter-gather (defined fully in the next section). Reads pay the price.
• Global / term-partitioned index. The index itself is sharded, by the indexed term rather than by the document. All email entries for a given range live on one index shard, so a lookup goes to just that one shard — fast reads. But a single row write may now have to update an index entry on a different shard than the row, so writes fan out. Writes pay the price.

The choice is a straight read-vs-write trade: local indexes make writing cheap and reading expensive; global indexes do the reverse. Pick based on which your workload does more of.

As long as a request needs data from one shard, sharding is nearly invisible. The pain begins when a request needs many shards at once. Two flavors of that pain matter.

A cross-shard query reads from several shards and combines the results — the scatter-gather pattern: fan the query out to all relevant shards (scatter), then merge their answers (gather). Its cost is that the query is only as fast as the slowest shard that answers, and it consumes work on every shard it touches. Aggregations like "count all orders" or "top 10 users globally" are inherently scatter-gather and get more expensive as you add shards.

A cross-shard transaction is harder still: it must change data on several shards and keep them consistent — all the changes commit, or none do. Two approaches dominate.

• Two-phase commit (2PC). A coordinator asks every involved shard "can you commit?" (the prepare phase); only if all say yes does it tell them "commit" (the commit phase). It gives strict atomicity, but every participant holds locks and waits for the coordinator through both phases — so it is slow, and if the coordinator dies mid-flight, participants can be left blocked holding locks.
• Saga. Instead of one atomic transaction, run a sequence of local transactions, one per shard, and for each step define a compensating action that undoes it. If step 4 fails, run the compensations for steps 3, 2, 1 to unwind. Sagas stay available and lock-free, but they are only eventually consistent — other readers can briefly see the half-finished state — and you must write and test every compensating action.

The practical lesson is to design so these are rare. The best cross-shard transaction is the one you avoided by choosing a partition key that keeps data that changes together on the same shard.

Sharding and replication solve different problems and are almost always used together. Sharding splits data so it fits and spreads load; replication keeps multiple copies of the same data so a machine can fail without losing it. A real system does both: it shards the dataset into pieces, and then each shard is itself replicated across several machines.

Read the two dimensions separately. Across shards you get scale — more shards, more total capacity. Within a shard you get durability and availability — more replicas, more tolerance to machine loss. A three-shard cluster with three replicas each is nine machines: three independent slices of data, each surviving up to two failures. Every consistency choice from replication (synchronous vs asynchronous, leader-based vs quorum) still applies — but now it applies per shard, independently. Shard 2 losing its leader does not touch shard 1.

A one-glance summary of the decisions in this chapter.

• Vertical partitioning splits columns by domain; horizontal partitioning (sharding) splits rows across machines. Reach for vertical first.
• The partition key is the load-bearing decision: even, query-aligned, stable, high-cardinality. Booleans and raw timestamps are classic bad keys.
• Range partitioning wins range scans but risks a hot range; hash partitioning spreads load evenly but kills range scans.
• Never rebalance with hash(key) % node_count — it moves almost everything. Fix a large partition count (or use consistent hashing with virtual nodes) so only ~1/N of keys move.
• One superstar key can melt a shard regardless of the key choice; split it, scatter it with a suffix, or cache/dedicate it.
• Cross-shard queries pay scatter-gather cost, and cross-shard writes force a choice between 2PC (strict, blocking) and sagas (available, eventually consistent) — so shape the partition key to keep co-changing data together.
• Real systems shard and replicate: shard for scale across the fleet, replicate each shard for survival within it.