Sharding and Partitioning

Vertical vs horizontal partitioning

Vertical partitioning splits by columns or by domain: move the profiles tables to one database and the orders tables to another, or split rarely used blob columns into a side table. This is often the first scaling step and aligns naturally with a move toward services owning their own data. Its ceiling is obvious: the busiest single table still lives on one machine.

Horizontal partitioning (sharding) splits rows of the same table across nodes by a partition key, so users 1 to 10 million live on shard A and the next 10 million on shard B. This is how systems scale writes and storage past a single machine: each shard handles a fraction of traffic and data. A single Postgres node might comfortably serve 20,000 writes per second; sixteen shards raise that ceiling to the low hundreds of thousands.

Sharding is a last resort for relational data because it breaks things you take for granted: cross-shard joins, cross-shard transactions, unique constraints across the dataset, and autoincrement IDs. Interviewers reward candidates who exhaust vertical scaling, read replicas, and caching before reaching for shards, and who then choose the partition key deliberately.

Hash, range, and directory sharding

Hash sharding applies a hash to the partition key and assigns the result to a shard, for example hash(user_id) mod 16. It distributes load evenly and is the default for key-addressed workloads, but it destroys ordering: a range query like 'all orders from last week' must scatter to every shard and gather results. Naive modulo also reshuffles almost every key when the shard count changes, which is the problem consistent hashing solves.

Range sharding assigns contiguous key ranges to shards, as HBase and Bigtable do and as DynamoDB does within partitions. Range queries become cheap single-shard scans, but poorly chosen keys create hot spots: sharding by timestamp sends every current write to the newest shard while the others sit idle. Range-sharded systems typically auto-split hot ranges, but a monotonically increasing key defeats even that.

Directory-based sharding keeps an explicit lookup service mapping keys or tenants to shards. It offers maximum flexibility, for example pinning a huge enterprise tenant to its own dedicated shard, or moving a tenant during rebalancing by updating one row. The costs are an extra hop on every request and the directory becoming a critical dependency that must itself be cached and replicated. Slack and many B2B SaaS products use variants of this for tenant placement.

Hot spots and the celebrity problem

Even a perfect hash distributes keys evenly, not load. If one key is orders of magnitude hotter than the rest, its shard melts while others idle. The canonical example is the celebrity problem: a social network shards by user_id, and a celebrity with 100 million followers turns every post into a write fan-out storm and their profile into a read hot spot on one unlucky shard.

Standard mitigations: cache hot keys aggressively in front of the shards (a celebrity profile is highly cacheable); split a hot key by appending a random suffix, writing to celebrity_id#1 through celebrity_id#8 and aggregating on read; or handle the head of the distribution with a different code path entirely, as Twitter historically did by pulling tweets from mega-follower accounts at read time instead of fanning out on write.

Choosing the partition key is where most sharding designs succeed or fail. Good keys have high cardinality, spread load evenly over time, and appear in your most common queries so those queries hit one shard. Sharding a messaging system by channel_id keeps a conversation's history together but makes one giant channel a hot spot; Discord dealt with exactly this in its Cassandra message store, where huge servers created hot partitions.

Resharding and routing in practice

Resharding, changing the number or boundaries of shards while serving traffic, is the operational nightmare that motivates planning ahead. The classic technique is to pre-create many more logical partitions than physical nodes (for example 1,024 virtual shards mapped onto 8 machines) so that growth means remapping logical shards to new machines and copying their data, never re-hashing individual keys. Consistent hashing achieves a similar goal for dynamic membership.

A live migration typically runs in phases: dual-write to old and new shards, backfill historical data with a bulk copier, verify with checksums, cut reads over, then stop writes to the old location. Each phase must be reversible. Vitess automates much of this for MySQL with resharding workflows, and DynamoDB and Cassandra handle splits internally, which is a large part of their appeal.

Routing must also live somewhere: in a client library that knows the shard map (fast, but every client needs updates), in a proxy tier like Vitess's vtgate or a MongoDB mongos router (centralized logic, extra hop), or in the database itself for natively sharded stores. Cross-shard queries then need scatter-gather with partial failure handling, and cross-shard writes need sagas or two-phase commit, which is a big enough topic that flagging it in an interview is usually sufficient.

Tradeoffs