Sharding & Partitioning (Hash-based, Range-based, Geo-based)

Tier 1 — Building Block

1. What Is It?

Sharding (also called horizontal partitioning) splits a large dataset across multiple database nodes, where each node owns a disjoint subset of the data. Each node is called a shard. Collectively the shards form one logical database.

The problem sharding solves: a single database node has a physical ceiling. A single PostgreSQL instance on the largest cloud VM handles ~30K writes/sec and stores up to a few TB before performance degrades. When your dataset is 100TB and your write rate is 500K/sec, no single node can handle it. Sharding distributes both storage and compute across N nodes, multiplying write throughput and storage capacity by N.

Partitioning is the same concept applied within a single database node (e.g., PostgreSQL table partitioning splits a large table into smaller physical files). Sharding is partitioning across multiple machines.

2. How It Works

The Core Mechanism

A shard key (partition key) is a column or set of columns used to determine which shard a given row belongs to. The routing function maps shard_key → shard_id.

-+ResetFullscreen

Hash-Based Sharding

Shard assignment: shard_id = hash(shard_key) % N

For a 4-shard setup, user_id=42 → hash(42) % 4 = 2 → Shard 2.

-+ResetFullscreen

• Pros: Uniform distribution (no hotspots if key is high-cardinality); simple logic
• Cons: Range queries across shards require scatter-gather (sending the query to all N shards in parallel and merging the results); resharding when adding nodes remaps many keys (use consistent hashing to mitigate)

Range-Based Sharding

Shard assignment: Predefined key ranges map to shards.

Shard 1: user_id 1 – 1,000,000
Shard 2: user_id 1,000,001 – 2,000,000
Shard 3: user_id 2,000,001 – 3,000,000

Or for time-series:

Shard 1: events with timestamp Jan–Mar 2024
Shard 2: events with timestamp Apr–Jun 2024
Shard 3: events with timestamp Jul–Sep 2024

-+ResetFullscreen

• Pros: Range queries efficient within a shard (e.g., "all users 1M–1.5M" goes to one shard); contiguous data locality
• Cons: Hotspot risk if a range is disproportionately active (e.g., all new users go to the latest shard — "write amplification" of new data); requires explicit rebalancing as ranges fill up

Geo-Based (Directory-Based) Sharding

Routes based on geographic region or an explicit lookup table.

Shard US-East: users where region = 'us-east'
Shard EU-West: users where region = 'eu-west'
Shard AP-South: users where region = 'ap-south'

• Pros: Data locality (user data stored near user); data residency compliance (GDPR)
• Cons: Uneven distribution if user population is geographically concentrated; cross-region queries are expensive

Cross-Shard Challenges

-+ResetFullscreen

• Cross-shard JOINs: Must scatter to all relevant shards and join in the application layer. Expensive. Design shard key to keep related data on the same shard (e.g., all orders for a user on the same shard as the user).
• Cross-shard transactions: Require two-phase commit (2PC) — complex and slow. Avoid by designing to keep transactional data co-located.

3. Variants & Comparisons

4. When to Use It (and When NOT To)

Use Sharding When:

• Single DB node is the bottleneck: Write QPS exceeds ~20K/sec on a single node, or data size exceeds ~1TB with performance degradation
• Storage exceeds single-node capacity: Dataset too large for any single machine
• Data has a natural partition key: user_id, order_id, tenant_id — a key that distributes data evenly and keeps related records together
• Multi-tenant SaaS: Shard by tenant_id to isolate tenant data and scale each tenant independently

Decision triggers:

• "If primary DB CPU > 80% on writes at peak → add shards to distribute write load"
• "If dataset > 2TB and growing → shard before single-node performance cliff"
• "If you have clear tenant/user isolation requirements → shard by tenant or user"

Do NOT Shard When:

• Read replicas or caching haven't been tried first: Sharding adds massive operational complexity. Cache + read replicas can handle 10–100× the traffic first.
• Your dataset fits on one node: Sharding is premature optimization for 95% of applications.
• You need frequent cross-shard transactions: Financial applications where every transfer spans two users (two shards) require 2PC everywhere. Consider a NewSQL database (Spanner, CockroachDB) that handles distributed transactions natively.
• You haven't chosen a good shard key: Sharding with a bad shard key (low cardinality, or creates hotspots) is worse than not sharding.

Anti-patterns:

• Shard by sequential auto-increment ID: All new writes go to the shard holding the highest range — creating a "hot shard." Use hash-based on a high-cardinality key instead.
• "Celebrity" hot shard: A few entities (viral posts, famous users) receive 1000× the traffic of normal entities, overloading their shard. Fix: shard by a secondary key, replicate hot entities, or use application-level routing to spread the load.
• Not co-locating related data: If users and orders are sharded separately by different keys, every order query that needs user data requires a cross-shard join. Shard both tables by user_id.
• Resharding without planning: Adding a shard to a hash % N system remaps N/(N+1) keys — nearly everything. Always use consistent hashing or range-based sharding when you anticipate adding nodes.

5. Real-World Usage

Instagram (PostgreSQL sharding by user_id): Instagram shards PostgreSQL by user_id using a hash function. All of a user's photos, follows, and activity are on the same shard — avoiding cross-shard joins for common operations. They use a custom Python library (django-sharding) to route queries. Each shard is a PostgreSQL instance with primary + replica. The shard key is embedded in all object IDs (the Snowflake variant Instagram uses encodes shard ID in the ID itself).

Cassandra (automatic hash sharding via consistent hashing): Cassandra automatically shards data across nodes using consistent hashing on the partition key. The application specifies the partition key in the data model; Cassandra's token ring handles the rest. Adding nodes rebalances automatically with minimal disruption. Cassandra also replicates each partition to R nodes (replication factor) for fault tolerance — sharding and replication are unified in one system.

Vitess (MySQL sharding for YouTube/Slack): Vitess adds a sharding layer on top of MySQL. The Vitess router intercepts SQL queries, inspects the WHERE clause for the shard key, and routes to the correct MySQL shard. Cross-shard queries are executed as scatter-gather. YouTube (800M+ videos), Slack, and GitHub use Vitess to scale MySQL horizontally beyond what a single node can handle.

6. Interview Cheat Sheet

Key sentences to demonstrate depth:

1. "Sharding distributes data across N nodes by partitioning on a shard key — my first question is always: what is the shard key, and does it give uniform distribution without creating hot shards?"
2. "Hash sharding gives uniform distribution and prevents hotspots, but destroys range query efficiency — scatter-gather to all N shards is O(N) cost. Choose based on your dominant access pattern."
3. "The cardinal rule: keep data that's queried together on the same shard. If users and orders are always queried together, shard both by user_id. Cross-shard JOINs kill performance."
4. "Resharding is the nightmare scenario — adding a shard to a hash % N system remaps almost everything. Avoid by using consistent hashing from the start, or range sharding with explicit split points."
5. "Before recommending sharding, I always ask: have you tried caching, read replicas, and query optimization? Sharding multiplies operational complexity — it's a last resort, not a first resort."

Common follow-up questions:

Connections to other building blocks:

• Consistent Hashing: The standard algorithm for hash-based sharding that minimizes remapping when adding/removing shards. Cassandra's token ring is consistent hashing applied to sharding.
• Unique ID Generator: Snowflake IDs embed a shard/worker ID — IDs are globally unique across shards without coordination. Instagram's IDs encode the shard ID directly, enabling routing from ID alone.
• Read Replicas: Each shard typically has its own read replicas. Sharding handles write scale; replicas handle read scale within each shard.
• CAP Theorem: Cross-shard transactions force a CAP tradeoff. If you need shard A and shard B both to commit atomically, you need 2PC (CP) — or you sacrifice consistency (AP, eventual consistency via saga/compensation).
• Message Queues: Kafka partitions are sharding for log streams. The partition key (message key) determines which partition (shard) a message goes to, providing ordering within a partition.