Partitioning, Sharding, and Consistent Hashing: Designing for Scale Without Losing Control

Why a Single Database Node Eventually Stops Working

A single relational node eventually hits three hard ceilings at once: write throughput, memory, and storage. A node may handle roughly tens of thousands of queries per second and a few terabytes of data, but neither ceiling grows when the dataset keeps expanding. More memory cannot make storage infinite, and a single writer cannot accept unlimited mutations. Once the working set no longer fits in memory, reads and indexes compete with data for capacity; once storage is full, adding more traffic is no longer a tuning exercise.

Replication changes the read-side picture, not the write or storage limits. Followers can serve additional reads, but each follower still stores the full dataset and receives the writes needed to maintain its copy. For write capacity, adding followers does not remove the primary node's write bottleneck; for storage, it multiplies the number of full copies rather than increasing the capacity of one copy.

The size wall is easy to see in a concrete case. Suppose Twitter stores 500 billion tweets, with an average size of 1 KB each. The arithmetic is 500 billion × 1 KB = 500 trillion KB = 500 PB. That is 500,000 TB, so it is hundreds of thousands of times larger than a few-terabyte single-node capacity. No single node can hold the dataset; the design must divide it. The remaining question is where each piece should live, and how the system should find it.

That division is partitioning: splitting a dataset into disjoint subsets so each node owns and serves only part of the whole. Sharding is horizontal partitioning across independent database nodes, with each shard holding a self-contained slice of the keyspace. Instead of copying every row to every node, the system makes each node authoritative for writes to its own slice. This creates horizontal storage and write capacity, but the cost appears at query boundaries: joins, transactions, and range scans that cross slices are no longer cheap local operations.

Partitioning exists to move the database past a single node's write, memory, and storage ceilings by assigning disjoint data slices to independently serving nodes.

Three Ways to Decide Where a Key Lives

Start with the access pattern

The router applies the partition key before sending the request, so a point lookup can stay on one shard instead of becoming a cluster-wide operation. The partitioning scheme therefore determines both the destination for a key and the query boundaries the system can preserve.

The choice is not “which algorithm is fastest?” It is “which queries must remain local?” A scheme that preserves order helps range queries but can concentrate writes. A scheme that spreads keys evenly protects write distribution but may force a range query to contact every shard. The four layouts below make that cost visible: follow the highlighted query path, not just the placement of the records.

Key-range partitioning

Key-range partitioning assigns contiguous intervals of the sort key to shards—for example, A–F to one shard and G–M to another. The router first finds the range containing the key, then sends the request to that shard. A range predicate can identify only the relevant shard or adjacent shards, which keeps scans local. The cost is workload skew: with timestamps or auto-incrementing IDs, new values arrive at the end of the ordering, so the shard owning the newest range receives the write stream and can become hot.

The routing paths use four different placement rules. For key ranges, find the contiguous range containing the key and send the request to its shard; a range query scans only the relevant shard or adjacent shards. For hashing, hash the key, use the resulting bucket-to-shard assignment, and scatter a range query to every shard before merging results. For a composite key, hash metric_name to select the shard and keep records ordered by timestamp within it. For directory routing, look up key in the directory and route the request to the returned shard; a range query uses directory entries to identify the shards it must scan.

The first route in the artifact captures the important invariant: the range lookup happens before the database call, and the range query scans only the relevant shard or shards. This is attractive for time windows and ordered records, but you must choose boundaries that will not funnel the active part of the keyspace into one shard.

Hash partitioning

Hash partitioning runs the partition key through a hash function, then maps the resulting bucket to a shard. Because nearby input values generally no longer remain nearby after hashing, writes tend to spread across shards instead of following the key's sort order. That distribution is the reason hash partitioning is useful for uniform point lookups and write-heavy workloads. The same property removes order: a query such as “all records in this time interval” cannot identify one contiguous shard range and may need a scatter-gather across every shard, followed by a merge.

Read the second route as the operational consequence rather than as a generic hash definition: bucket = hash(key) chooses placement, but the range-query comment requires every shard. Hashing is therefore not strictly better than ranges; it exchanges range locality for distribution.

Composite keys

A composite key splits the trade-off across two dimensions. Hash the first component to choose a shard, then preserve sort order on the second component inside that shard. Cassandra's partition key plus clustering key is the canonical example: metric_name determines the bucket, while timestamp orders records within it. A recent-window query for one metric can therefore remain on one shard and use its local timestamp order, while different metric names distribute across the cluster.

The route_metric path makes the order explicit: select the shard from metric_name, then order by timestamp there. This only preserves locality for queries that include the first component. A query spanning many metric names still has to visit the corresponding buckets.

Directory-based partitioning

Directory-based partitioning keeps an explicit mapping from each key to its shard. The router performs a directory lookup, receives the shard identifier, and sends the request there. Because placement is data rather than an irreversible calculation, you can move one entity, repair an uneven distribution, or migrate a hotspot by changing its directory entry. The directory introduces a dependency that can become a single point of failure and a latency bottleneck.

The final route shows the extra hop: directory_lookup(key) precedes the shard request. For a range query, the directory must identify all entries whose ranges or keys could satisfy the predicate; the router then scans those shards. Directory-based routing buys control over placement, but the lookup service becomes part of the data path and must be operated like critical infrastructure.

Rebalancing When Nodes Join or Leave

A topology change always creates a migration problem: when a node joins or leaves, some keys must move. The design question is not whether movement occurs, but how much moves and whether the system can continue serving traffic while it happens. The routing function determines the blast radius.

Modulo hashing moves the keyspace

With naive modulo routing, the destination is hash(key) % N. For the five-node cluster, a key whose current result is K % 5 = 3 routes to node 3. After adding a node, N = 6; if K % 6 = 1, the same key routes to node 1 and must move. Because changing N changes the calculation for nearly every key, most data remaps at once. In a cache, those remapped entries become misses; the backing database then receives the miss storm while the cluster is supposed to be gaining capacity.

Modulo routing is simple when membership is stable, but it couples the identity of every destination to the node count. Removing a node has the same problem as adding one: the remaining nodes inherit a broadly different key assignment. The migration is therefore large, difficult to bound, and liable to overload the backends it depends on.

Fixed partitions bound the move

Fixed partitioning separates key placement from node placement. You choose a partition count, compute a stable partition ID for each key, and maintain a partition-to-node ownership map. Adding a node changes that map rather than changing every key's partition ID. For example, with 1000 partitions and five existing nodes, adding a sixth node means assigning approximately 1000 ÷ 6 ≈ 167 partitions to it. The approximation is visible in the arithmetic: 6 × 167 = 1002, so the actual assignment must round across partitions; the moved share is still about one-sixth of the set. Kafka and Elasticsearch use this fixed-partition model.

The fixed count is a design-time decision. Too few partitions leave you unable to spread future load across enough nodes without another repartitioning event. Too many partitions increase operational overhead. During a move, keep the partition readable while data is copied, verify the destination, switch ownership, and remove the old copy. Online migration may require the client to read or write in both locations until the ownership switch; an offline move is simpler but interrupts access.

Modulo routing computes a destination with hash(key) % N, so changing the node count changes the result for many keys. Fixed-partition routing instead calculates a stable partition ID and uses the partition-to-node ownership map, so a topology change updates ownership rather than every key's partition. During migration, keep the partition readable while data is copied, verify the destination, switch ownership, and remove the old copy. Online migration may require reads and writes to handle both the original and new locations until cutover.

Dynamic partitions follow growth

Dynamic partitioning avoids choosing every future boundary up front. When a partition exceeds a configured size or load threshold, the system splits it into smaller partitions and tracks the new boundaries centrally. This fits key-range schemes because the split preserves ordered ranges: one interval becomes two, and routing consults the boundary map. HBase and RethinkDB use this model. The cost is coordination around boundary ownership and split progress, especially while reads and writes continue.

Consistent Hashing: The Ring and Its Virtual Nodes

Route a key on the ring

Consistent hashing puts both keys and nodes into the same circular hash space, from 0 through 2^32-1. A request hashes its key to a position, then walks clockwise until it reaches the first node position. That node owns the key. If the walk reaches the end of the numeric range, it wraps to the beginning; the ring has no endpoint.

The routing state is a sorted collection of ring positions mapped to node IDs. A lookup therefore hashes the key, finds the first position at or after that hash, and wraps to position zero when there is no such position. The primary owner is distinct from replicas: replication is controlled by a separately configured replication factor, not by the hashing algorithm itself.

The ring uses a circular hash space from 0 through 2^32-1. Hash the key to a position and select the first node clockwise from that position, wrapping to the beginning when necessary. Replica placement is configured separately from primary ownership; consistent hashing itself determines the primary node, not the complete replica set. When a node position is inserted, only the interval up to its clockwise successor changes ownership; unrelated intervals keep their owners.

Membership changes affect only one interval. Insert a node at position P, find its clockwise successor, and move to the new node the keys in the interval from P up to that successor. Keys in every other interval keep their existing owner. With N nodes after an addition, that interval contains roughly 1/N of the keyspace, so the amount remapped is bounded by a fraction of the dataset rather than nearly all of it.

Why one position per node is not enough

A ring containing only one position for each physical node can distribute ownership unevenly. Hash positions are not guaranteed to be equally spaced: one node may own a large arc while another owns a small one. Failure makes the imbalance sharper. If node C is the only owner of its intervals, a three-node ring can send 100% of C's traffic to one clockwise neighbor after C fails.

Virtual nodes smooth both problems. Instead of placing each physical node at one position, place it at K positions; K = 150 means one physical node contributes 150 vnode positions rather than one. Those smaller intervals interleave around the ring, so ownership averages across many samples. When a physical node fails, each of its vnode intervals has its own clockwise successor; the displaced load fans out across the remaining nodes instead of piling onto one neighbor. With 150 vnodes, C's 150 positions can therefore transfer to D and A roughly equally in the three-node example.

The trade-off is state and membership work: adding or removing a physical node means adding or removing all of its vnode positions and updating the sorted ring. The payoff is more uniform ownership and a less concentrated failure response. You still need to measure actual traffic, because uniform key ownership does not make a single exceptionally hot key less hot.

Worked Example: Partitioning a Time-Series Metrics System

Start with the query, not the table

Assume a metrics system receives measurements identified by metric_name and timestamp. Its dominant read is a recent-window query such as “show the last interval for cpu.user.” You want two properties at once: writes for different metrics should spread across shards, while timestamps for one metric remain ordered so a recent-window query can read a contiguous local slice. A pure timestamp range scheme provides the second property, but every current measurement belongs to the newest range. As that range receives all new writes, the latest shard becomes the write hotspot.

For a small trace, take several metric_name values. Hash each metric_name once to select its shard, then keep that metric's records ordered by timestamp within the selected shard. The actual hash values are not important to the query shape: metric names are distributed by the hash, while each destination keeps its own timestamp order.

A recent-window read for cpu.user repeats only the routing step for that metric: hash cpu.user, send the request to its selected shard, then scan that metric's records in timestamp order and stop outside the requested window. It does not need to inspect the shards holding memory.used or requests.rate. By contrast, a timestamp-only range design sends the current writes for all three metrics into the latest range. The query may be locally ordered there, but the write path has concentrated the active workload on one partition.

This is the access-pattern trade-off in concrete form. The composite key gives up a single global timestamp order in exchange for distributing writes by metric and keeping each metric's recent records local and ordered. A query that asks for one metric can remain shard-local. A query that asks for every metric in the newest window has no such shortcut: it must contact the relevant shards and merge their results. The right design therefore follows the dominant query, rather than treating “time series” as an automatic reason to use timestamp-only ranges.

Choose the Scheme From the Access Pattern

Choose the partition key from the queries you must keep fast, then test whether it distributes the writes those queries generate. A key that makes point lookups cheap may make a leaderboard, time window, or administrative scan expensive. Conversely, a key that keeps ranges together may funnel every new write into the newest range. The right scheme is the one that makes the dominant path local without creating an unacceptable hotspot or migration burden.

The table separates two decisions that are often conflated. The partitioning strategy determines where the base records live; the secondary-index strategy determines how you find records through a different access path. Hash partitioning is a strong fit for uniform point lookups and write distribution, but it destroys global sort order, so a range query becomes a scatter-gather. Key-range partitioning makes a range query selective, but monotonically increasing keys—timestamps or sequence-like identifiers—concentrate new writes in the newest range. Composite keys split the trade-off: distribute on the partition-key component and retain local ordering on the clustering-key component.

Directory routing buys the most placement freedom. You can move one tenant, account, or hotspot without changing the routing function, but every request depends on a shard map that must be available and current. That dependency is not merely an implementation detail: stale metadata can send traffic to the wrong shard, while an unavailable directory can prevent otherwise healthy shards from being reached. Consistent hashing is a natural default for cache routing and peer-to-peer storage because topology changes remap only a fraction of keys. For a database with a known scale ceiling, fixed partitions are often simpler: capacity planning is explicit and topology changes move whole partitions. You pay up front by choosing a partition count that is neither too small to scale nor so large that partition-management overhead dominates.

Secondary indexes expose the same choice at another layer. A local index keeps each shard's write path independent, but a query without the partition key fans out to every shard and merges the results. A global index can make that read path narrower, at the cost of coordinating the base-record write with the index write; the index can also have a consistency window. MongoDB and Elasticsearch are representative local-index designs, while DynamoDB GSIs are global and eventually consistent. Treat the index as part of the partitioning design, not as a later optimization: its read fan-out, write coordination, and failure dependency all belong in the capacity and correctness review.

Document the anti-patterns before implementation: monotonically increasing keys for a range scheme, low-cardinality partition keys that create only a few large owners, and keys tied to business hotspots such as celebrity accounts or trending hashtags. A URL shortener with point lookups does not need range order: hashing short_code and assigning fixed partitions is simpler than introducing a consistent-hashing ring. In every design, estimate the data movement and migration window for a topology change, and decide whether reads remain serviceable while ownership moves.

When Queries and Transactions Cross Shard Boundaries

Partitioning makes the single-node execution model conditional: an operation is cheap only when the data it needs is colocated. A join whose inputs live on different shards becomes a client- or coordinator-side operation. A range scan can no longer walk one ordered index; it must query every shard that might contain matching rows and merge the results. Azure’s guidance describes this multi-shard pattern explicitly: a multi-shard query sends individual queries to each database and merges the results, while cross-database joins must be performed on the client side.

Secondary indexes: fan-out or coordination

A local secondary index preserves independent shards. Each shard indexes only its own rows, so a query on a non-partition key fans out to every shard, waits for the slowest response, and merges the partial results. The operator sees outbound request count rise with shard count and tail latency track the least healthy shard. This is acceptable for occasional administrative queries; it is a poor fit for a request path that performs the fan-out on every user request. Azure recommends grouping data used together in the same shard and avoiding operations that access multiple shards for this reason.

A global secondary index reverses the trade-off. The index spans the keyspace, so a lookup can route to one index rather than interrogating every local index. The write path must update the base row and the global index as a coordinated operation; if the index is maintained asynchronously, reads can be eventually consistent. DynamoDB GSIs are the canonical example of that consistency trade-off. You pay coordination and index-maintenance cost on writes to make the read path narrower.

Transactions and joins across shards

A cross-shard transaction has to coordinate independent participants. A two-phase commit can make them agree on commit or abort, but it adds coordination overhead and is slow and fragile under a network partition. The result is higher latency and more failure states than a transaction contained within one shard. Some stores do not support cross-shard transactions at all: Azure SQL Database supports transactional operations only for data in a shard, not across shards. Design the partition key so rows that must change atomically are colocated; if that is impossible, replicate slow-moving reference data or accept an explicitly eventually consistent workflow.

Hot Partitions, Failed Nodes, and Live Re-sharding

A partition scheme can be balanced by key count and still fail under real traffic. Consistent hashing spreads many keys uniformly in expectation; it does not split one hot key across nodes. A viral post or celebrity user still maps to one owner, so that node saturates while its peers remain underused. The graph typically shows one shard's QPS climbing sharply while the others stay flat—not a cluster-wide increase.

Failure fan-out also depends on whether you use virtual nodes. In a three-node ring without vnodes, Node C has one ownership position. When C fails, its successor absorbs 100% of C's traffic instead of sharing it across the two surviving nodes—twice the roughly 50% share each survivor would receive if the load were split evenly. With 150 vnodes per physical node, C contributes 150 failed positions; those positions have different clockwise successors, so the displaced load fans across Nodes D and A roughly equally rather than piling onto one node. The ring therefore improves failure distribution, but it does not remove the extra traffic caused by the failure.

A practical defense against a hot entity is key salting. Suppose user_id is the partition key for a social graph, so a user's posts, likes, and follows are colocated. A celebrity with 100 M followers can make that one shard melt. Replace the single routing key with ten salted keys—user_id_0 through user_id_9—so writes can spread across ten routing targets. The read path must then query and merge all 10 keys. If the writes distribute evenly, the average follower-associated load is 100 M ÷ 10 = 10 M per salted key, a tenfold reduction in concentration; the actual result still depends on traffic skew. Application-level fan-out is the alternative when you need to materialize the celebrity's activity into consumers' views rather than aggregate it on every read.

Re-sharding is a live migration, not a routing-table edit. First estimate how much data must move, define the migration window, and decide whether reads—and, if required, writes—remain available while copies are in flight. An online migration can leave client code reading and writing in both the original and new locations until the move is complete. During the event, monitor QPS and storage independently for every shard; aggregate cluster averages can hide one overloaded shard. Treat a shard at 80% capacity as an incident risk: its used capacity is four times its remaining 20% headroom, leaving little room for migration copies, skew, or a failed neighbor.

Use migration tooling that can copy data, verify it, switch ownership, and remove the old copy only after the new location is serving correctly. Azure's online-migration guidance describes the important distinction: the original partition stays online, but access code may need to handle data in two locations during the move. Capacity planning must include the temporary overlap. A design is incomplete until it states the amount of data moved on a topology change, the expected migration window, and the read behavior throughout that window.

Defend the Partitioning Decision

A repeatable defense

Start with the access pattern, then defend the partition key against the queries and transactions the system must support. State the dominant read explicitly, how writes distribute, which business entities must be colocated for per-shard transactional correctness, and which queries are allowed to scatter-gather. A strong answer also names the keys you rejected: monotonically increasing or low-cardinality keys, and keys that concentrate traffic around business hotspots.

For a URL shortener, choose hash(short_code) with 1024 fixed partitions assigned across nodes. Reads are point lookups by short_code, so there is no range-scan requirement to preserve. Hashing spreads writes uniformly, while fixed partitions avoid adding unnecessary consistent-hashing ring complexity. The choice follows from point-lookup access and the absence of a range-scan requirement.

• Dominant read: point lookups by short_code.
• Hash short_code for uniform write distribution.
• The specified access pattern does not require range scans.
• Use 1024 fixed partitions assigned across nodes.
• Model data movement and the migration window upfront.
• Online migration may require clients to read and write data in both locations during the move.
• Monitor QPS and storage independently for each shard.
• Include verification, cutover, and rollback in migration planning.

The checklist makes the design testable rather than rhetorical. Before approving it, quantify how much data moves when partitions are reassigned, how long the migration window lasts, and whether reads remain available throughout. Monitor QPS and storage independently for every shard; an even partition function does not guarantee even business traffic. During an online migration, application code may need to read and write data in both the original and new locations, so routing and consistency behavior belong in the design, not in an undocumented migration script.

Changing a 50 TB sharded Postgres cluster from user_id to (region, user_id) is a migration project, not a metadata toggle. You need a live data migration, verification, a controlled cutover, and a plan for routing reads and writes while data exists in both locations. Flag inconsistent writes, an extended migration window, changed cross-shard access patterns, and capacity pressure from serving production traffic while data exists in two layouts. The approval question is whether the system can keep serving reads safely during each phase, not merely whether the new key looks more descriptive.