Data Partitioning and Sharding

Partitioning is the decomposition of a logical dataset into disjoint physical fragments, each small enough to be stored and processed efficiently by a single node. Two orthogonal axes describe how a fragment is carved out. Horizontal partitioning splits a table by rows: each fragment (called a partition or, when placed on an independent server, a shard) contains a subset of the rows but all the columns, and the union of all fragments reconstructs the full table. Vertical partitioning splits a table by columns: each fragment contains a subset of columns (with the primary key typically replicated in every fragment so rows can be rejoined), useful when some columns are accessed far more frequently than others, or when different columns have very different sizes (a `profile_photo` blob versus a `username` string). A partitioning scheme is a function `P: KeySpace → {1, ..., n}` that assigns every row's partitioning key to exactly one of `n` partitions. The three classical schemes differ in how this function is defined. A range partition divides the ordered key space into contiguous intervals (`[a, b)`, `[b, c)`, …), so `P` is essentially a binary search over boundary values. A hash partition applies a hash function `h` to the key and reduces it modulo the partition count (or maps it onto a hash ring), so `P(k) = h(k) mod n`. A directory-based partition stores an explicit table mapping each key (or each range/bucket of keys) to a partition, consulted via a lookup service; `P` is not a formula but a stored mapping that can encode arbitrary, even irregular, assignments. Sitting on top of any partitioning scheme is a routing layer: the component (client library, proxy, or coordinator node) responsible for evaluating `P(k)` and forwarding a request to the correct shard. Routing strategies vary in how much topology knowledge a client must hold locally versus how much it must ask a coordinator, which is precisely the tradeoff explored in this article's central design question.

Choosing what to split: horizontal vs. vertical

Vertical partitioning is decided largely by access pattern analysis: profile columns queried on every login (`user_id`, `username`, `last_login`) are grouped separately from rarely-touched large columns (`bio_text`, `avatar_blob`). The mechanism is a straightforward schema-level split with a shared key for rejoining; no runtime routing decision is required beyond "read from table A, and table B if those columns are needed." Horizontal partitioning (sharding) is the more algorithmically rich problem, since the partitioning key's distribution and query pattern determine which of the three strategies is appropriate. The rest of this section develops each strategy's mechanism in depth.

Range partitioning

Choose a partitioning key (e.g., `user_id`, or a compound key like `(country, timestamp)`). Sort the key space conceptually and divide it into contiguous ranges, each assigned to one partition. A small ordered array of boundary values (or a B-tree of them, for very large partition counts) is enough to route any key. ``` function RANGE_ROUTE(key, boundaries[1..n-1]): // boundaries is sorted ascending; boundaries[i] is the // upper exclusive bound of partition i lo = 0 hi = n - 1 // n partitions, n-1 boundaries while lo < hi: mid = (lo + hi) / 2 if key < boundaries[mid]: hi = mid else: lo = mid + 1 return lo // index of owning partition ``` This is a binary search, `O(log n)` time per lookup, `O(n)` space for the boundary array. Range partitioning's chief strength is that a range query (`WHERE key BETWEEN a AND c`) touches only the partitions whose interval overlaps `[a, c]` — often just one or two — instead of every partition. Its chief weakness is skew: if the key is monotonically increasing (an auto-incrementing ID, or a timestamp), all new writes land on the last partition, creating a hotspot while older partitions sit idle.

Hash partitioning

Apply a hash function to the key and use the result to select a partition. The naive version is direct modulo: ``` function HASH_ROUTE_NAIVE(key, n): return hash(key) mod n ``` This distributes load near-uniformly (by the hash function's pseudorandomness) but has a catastrophic operational flaw: changing `n` (adding or removing a shard) changes `hash(key) mod n` for almost every key, forcing a near-total data reshuffle. The standard remedy is consistent hashing: map both partitions and keys onto a single hash ring (values `0` to `2^m - 1`), and assign each key to the next partition clockwise from its hash position. ``` function BUILD_RING(partitions[1..n], virtualNodesPerPartition = V): ring = empty sorted map // maps hash-position -> partition id for p in partitions: for v in 1..V: pos = hash(p.id + ":" + v) ring.insert(pos, p.id) return ring function CONSISTENT_HASH_ROUTE(key, ring): pos = hash(key) // find the first ring entry with hash-position >= pos, // wrapping around to the smallest position if none exists entry = ring.ceilingEntry(pos) if entry == null: entry = ring.firstEntry() return entry.partitionId ``` Adding a partition inserts `V` new points into the ring; only the keys that fall between the new points and their previous neighbors move — in expectation, roughly a `1/n` fraction of all keys, not all of them. Virtual nodes (the `V` replicas per physical partition) smooth out load imbalance that would otherwise arise from a small number of random ring positions clustering unevenly.

Directory-based partitioning

Instead of computing `P(k)` from a formula, store the mapping explicitly in a metadata service (often itself a small, replicated, strongly-consistent database, e.g. built on a consensus protocol). ``` function DIRECTORY_ROUTE(key, directoryService): bucket = BUCKET_OF(key) // e.g., hash(key) mod B, B >> n partitionId = directoryService.lookup(bucket) return partitionId function REBALANCE(directoryService, bucket, fromPartition, toPartition): migrateData(bucket, fromPartition, toPartition) directoryService.update(bucket, toPartition) // atomic pointer swap ``` Keys are typically first hashed into a large, fixed number of logical buckets (far more buckets than partitions, e.g. thousands of buckets over tens of partitions), and the directory maps buckets to partitions rather than mapping every individual key — keeping the directory small. Rebalancing becomes a simple metadata update (move bucket 4821 from shard 3 to shard 7) after the underlying data is copied, with no client-visible formula change. The cost is an extra network hop (or a cached copy of the directory) on every request, and the directory service itself becomes a critical piece of infrastructure that must be highly available and consistent.

Routing layer patterns

Whichever scheme is used, some component must actually execute `P(k)` and forward the request. Two broad patterns recur across real systems:

• Client-side routing: the client library embeds the partitioning function (and a cached copy of shard boundaries or the hash ring) and talks directly to the correct shard. Lowest latency, but every client must be updated when topology changes, and stale caches can misroute requests until refreshed.
• Proxy/coordinator routing: a stateless (or lightly stateful) proxy layer sits between clients and shards, holding the authoritative routing table and forwarding requests. Clients stay simple; the proxy becomes an extra network hop and a potential bottleneck, but topology changes are transparent to clients.

Directory-based schemes almost always use a coordinator pattern (the directory is the coordinator's state); range and hash schemes can use either pattern depending on how tightly clients are coupled to the deployment.

Routing cost. Range partitioning routes in `O(log n)` time via binary search over `n − 1` boundaries, using `O(n)` space. Hash partitioning with direct modulo routes in `O(1)` time (one hash computation) and `O(1)` space beyond the partition count. Consistent hashing routes in `O(log(nV))` time (a search over `nV` ring points, `V` virtual nodes per partition) and `O(nV)` space for the ring — still effectively constant for fixed `V`, since `V` is a small constant (typically 100–200) independent of data size. Directory-based routing costs `O(1)` amortized for a cached local lookup, or one network round-trip (`O(1)` messages, but real wall-clock latency) for an uncached lookup against the directory service; the directory itself needs `O(B)` space for `B` buckets, with `B` chosen independent of the number of rows.

Load balance. For a hash function drawn from a suitably random-looking family (i.e., behaving like a random oracle) applied to `n` partitions, the expected number of keys per partition is `N/n` for `N` total keys, and standard concentration arguments (Chernoff bounds on sums of independent indicator variables) show the maximum partition load is `N/n + O(√((N/n) log n))` with high probability — i.e., balance improves as data grows relative to partition count. Range partitioning has no such automatic guarantee: balance depends entirely on whether the boundaries are chosen to match the actual key distribution, which requires either a priori knowledge of the distribution or adaptive splitting (splitting a partition when it grows too large, a technique used by systems that maintain B-tree-like range maps).

Rebalancing cost — the central tradeoff. This is where the three schemes differ most sharply, and it is the crux of why one is chosen over another:

• Range: adding a partition means splitting one existing range into two; only the rows in the split range move — `O(size of one partition)`, not `O(N)`. This is cheap and is why range-partitioned systems can split "hot" ranges on demand.
• Naive hash (`mod n`): changing `n` changes `h(k) mod n` for a fraction `(n-1)/n` of all keys (a classical fact: two moduli `n` and `n+1` agree on `h(k) mod n = h(k) mod (n+1)` only when `h(k) < n` and no wraparound occurs, which holds for roughly a `1/n` fraction of keys). This is effectively `O(N)` data movement — a full reshuffle — making naive modulo hashing operationally unacceptable for elastic clusters.
• Consistent hashing: adding one partition (with its `V` virtual points) only affects keys that fall in the arcs immediately preceding those new points; in expectation this is an `O(N/n)` fraction of the data — a factor of `n` improvement over naive hashing, which is the precise reason consistent hashing was invented (originally for web cache load balancing, and now standard in distributed hash tables and NoSQL stores).
• Directory: rebalancing cost is exactly the cost of moving the reassigned buckets' data (bounded by bucket size, which is a tunable, small granularity) plus a metadata update; the mapping itself needs no recomputation, only an edit. This gives directory-based schemes the finest-grained control over rebalancing, at the price of maintaining and consulting the directory.

Correctness invariant. Regardless of scheme, a partitioning function is correct if and only if it satisfies two properties: totality (every key in the domain maps to some partition — no key is "lost") and disjointness (a key maps to exactly one partition — no key is duplicated across partitions, unless replication is explicitly layered on top). Range partitioning satisfies these by construction if boundaries are sorted and cover the full key space including `−∞` and `+∞` sentinels. Hash partitioning satisfies these because `mod n` (or ring lookup with wraparound) is a total function into `{0, ..., n-1}` and every input maps to exactly one output. Directory-based schemes satisfy these only if the directory is maintained as a consistent, complete mapping — which is precisely why the directory service typically requires a consensus protocol (e.g., Raft or Paxos-based) to avoid two coordinators disagreeing about a bucket's owner during a concurrent rebalance, a scenario that would otherwise violate disjointness.

Query cost implication. A query specifying an exact partitioning key value touches exactly one partition under all three schemes — `O(1)` shards contacted. A range query over the partitioning key touches `O(k)` contiguous partitions under range partitioning (where `k` is the number of partitions the range spans, typically small), but touches all `n` partitions under hash partitioning, because consecutive keys are scattered pseudorandomly across the ring. This is the fundamental locality-versus-balance tradeoff: range partitioning preserves the order needed for efficient range scans; hash partitioning sacrifices that order to guarantee balance.

Consider an e-commerce `orders` table with primary/partitioning key `order_id`, an auto-incrementing integer, and suppose the system is scaling from `n = 3` to `n = 4` shards. We trace all three schemes on the same six sample order IDs: `101, 102, 205, 340, 341, 999`.

Setup — range partitioning, initial boundaries `[200, 400)` splitting into three ranges `[0,200), [200,400), [400,∞)` → shards `R1, R2, R3`.

Only rows in `[200, 400)` — i.e., 205, 340, 341 — were ever candidates for movement, and only 340, 341 actually moved (to the freshly created R4); 101, 102, 999 never moved. This matches the `O(one partition's worth of data)` rebalancing claim.

Setup — naive hash partitioning, `h(id) = id`, routing via `id mod n`.

Five of six keys visibly change bucket index, and all six change their meaning (since "shard 1 under `n=3`" and "shard 1 under `n=4`" are different partitions of different total data), confirming the near-total reshuffle predicted by the `(n-1)/n` fraction argument (here `(3-1)/3 = 2/3` expected to move, consistent with the observed disruption).

Setup — consistent hashing, four physical shards each with virtual points on a ring of size 1000, only shard `S4`'s points added when scaling from 3 to 4 shards.

Only key `205` — the one whose ring position happened to fall just before a newly inserted S4 point — moves; the other five stay put. This is the expected `O(N/n)` disruption (here 1-in-6 ≈ the expected `1/4` fraction for a small sample), far less than the naive hash scheme's near-total reshuffle on the identical dataset. The same six rows, the same scaling event, produce three very different amounts of data movement — 2 rows for range, 6 for naive hash, 1 for consistent hashing — a concrete illustration of why naive modulo hashing is avoided in production systems that expect to grow.

Sharding as an engineering discipline was not invented by a single person, but its two key mathematical ingredients — hashing for load distribution and consistent hashing for elastic rebalancing — were consolidated by academic and industrial researchers responding to the exact reshuffling problem this article analyzes.

Sharding is the load-bearing wall of nearly every large-scale data system in production. Relational scale-out systems such as Vitess (used to shard MySQL at YouTube-scale) and CockroachDB use range partitioning with automatic range-splitting to keep query planning simple while avoiding manual rebalancing. Wide-column and key-value stores such as Apache Cassandra and Amazon DynamoDB use consistent-hash-based partitioning explicitly to guarantee load balance across commodity nodes and to support online cluster resizing without downtime. MongoDB offers both range- and hash-based sharding keys as a schema-time choice, directly exposing the tradeoff this article describes to application developers. Distributed hash tables underlying peer-to-peer systems (BitTorrent's Mainline DHT, Chord) are, essentially, pure consistent-hashing routing layers. Content delivery networks route billions of cache lookups per second through consistent-hash rings so that a single origin server's cached objects survive edge-node churn. Finally, partitioning is the structural prerequisite for MapReduce Programming Model-style computation, since the "shuffle" phase of MapReduce is itself a hash-partitioning step that routes intermediate key-value pairs to reducers, and it interacts closely with Replication Strategies (each partition is typically also replicated for fault tolerance) and with The CAP Theorem (partition tolerance in CAP refers to network partitions, a related but distinct concept from the data partitioning discussed here, and the two interact when a routing layer must decide how to behave during a network split).

Ask the tutor: How would you design a partitioning key for a multi-tenant SaaS database that avoids both hotspots and expensive cross-tenant transactions?