Implementing Database Sharding
1. Understanding Sharding Concepts
| Term | Definition |
|---|---|
| Shard | Independent partition of data on its own node |
| Shard key | Column(s) used to route rows |
| Routing layer | Maps key → shard (app, proxy, or built-in) |
| Resharding | Moving data to add/remove shards |
| Co-location | Related rows on same shard for local joins |
2. Designing Shard Keys
| Criteria | Detail |
|---|---|
| High cardinality | Many distinct values for even spread |
| Even access | Avoid hotspots |
| Used in most queries | Avoid scatter-gather |
| Immutable | Changing key requires data move |
| Examples | user_id, tenant_id, account_id |
3. Implementing Range-Based Sharding
| Pro | Con |
|---|---|
| Efficient range queries | Hotspots on recent ranges |
| Easy split/merge | Sequential keys cluster on one shard |
| Used in | HBase, MongoDB, CockroachDB (default) |
4. Implementing Hash-Based Sharding
| Pro | Con |
|---|---|
| Even distribution | No range queries on shard key |
| Random spread | Adding shards re-hashes everything (use consistent hashing) |
| Used in | Cassandra, DynamoDB, Citus |
5. Implementing Directory-Based Sharding
| Aspect | Detail |
|---|---|
| Mechanism | Lookup table maps key → shard |
| Flexible | Per-tenant placement, custom rules |
| Cost | Extra lookup per request; cache aggressively |
| SPoF risk | Replicate the directory |
6. Managing Cross-Shard Queries
| Pattern | Detail |
|---|---|
| Scatter-gather | Query all shards, merge results |
| Cost | Latency = slowest shard; CPU n× higher |
| Mitigations | Co-locate joined data, denormalize, async aggregation |
| Distributed JOIN | Hash redistribute (broadcast small tables) |
7. Handling Shard Rebalancing
| Method | Detail |
|---|---|
| Pre-split | Create many empty shards up front |
| Online move | Stream changes during data copy |
| Consistent hashing | Add/remove only moves a fraction |
| Dual-write window | Write to old + new during transition |
8. Implementing Consistent Hashing
N1
/ \
key3 key1
| |
N3 --- N2
| |
key4 key2
Adding N4 redistributes only the keys
between N3 and the new node — not all keys.
| Concept | Detail |
|---|---|
| Hash ring | Nodes + keys placed on ring; key → next clockwise node |
| Virtual nodes | Many points per physical node — even distribution |
| Used in | Cassandra, DynamoDB, Riak, Memcached clients |
9. Managing Shard Failover
| Strategy | Detail |
|---|---|
| Replicas per shard | Sync or async; promote on failure |
| Health checks | Detect node loss quickly |
| Quorum reads/writes | Tolerate node loss without ack delay |
| Backpressure | Reroute traffic away from degraded shard |
10. Designing for Shard Scalability
| Principle | Detail |
|---|---|
| Plan for 10× growth | Pre-split to avoid emergency re-shard |
| Tenant per shard (multi-tenant) | Isolate noisy neighbors |
| Idempotent writes | Resharding tolerates retries |
| Avoid cross-shard txs | Use sagas or design for local-only writes |