# Sharding

> **Partitioning data across multiple databases or nodes to scale writes and storage beyond a single machine.**

***

## 1. Concept Overview

**Sharding** splits a dataset into shards (e.g. by user\_id or key range), each stored on a different node. It enables horizontal scaling of storage and write throughput.

**Why it exists**: A single DB has limits on disk, memory, and write capacity. Sharding spreads data and load across many nodes.

***

## 2. Core Principles

### Shard key choice

* **Critical**: Queries that don’t include the shard key require scatter-gather (all shards) or a separate index.
* **Balance**: Key should distribute data and load evenly (avoid hot shards).
* **Growth**: Prefer keys that don’t create hotspots (e.g. avoid “last N” always in one shard).

### Strategies

| Strategy            | How                             | Pros                                  | Cons                                                      |
| ------------------- | ------------------------------- | ------------------------------------- | --------------------------------------------------------- |
| **Hash-based**      | `shard = hash(key) % N`         | Even distribution                     | Resharding moves many keys; use consistent hash to reduce |
| **Range-based**     | Shard 1: A–M, Shard 2: N–Z      | Range queries on shard key            | Hotspots (e.g. recent data in one shard)                  |
| **Directory-based** | Lookup table: key → shard       | Flexible; move individual keys        | Lookup table is bottleneck and SPOF                       |
| **Consistent hash** | Ring; key → next node clockwise | Adding/removing node moves \~1/N keys | Implementation complexity                                 |

### Architecture

```
  App ──▶ Router (shard key → shard id)
              │
              ├──▶ Shard 1 (DB instance 1)
              ├──▶ Shard 2 (DB instance 2)
              └──▶ Shard 3 (DB instance 3)
```

***

## 3. Real-World Usage

* **PostgreSQL / MySQL**: Application-level sharding (app routes by key); or Citus, Vitess.
* **MongoDB**: Sharding with shard key; config servers hold metadata.
* **DynamoDB**: Partition key (required); optional sort key; automatic sharding.
* **Kafka**: Partitions are shards; key determines partition.

***

## 4. Trade-offs

| Aspect                     | Pros                       | Cons                                                                                            |
| -------------------------- | -------------------------- | ----------------------------------------------------------------------------------------------- |
| **Hash**                   | Even distribution          | No range queries across shards; resharding is costly                                            |
| **Range**                  | Range queries on shard key | Risk of hot shards                                                                              |
| **Directory**              | Flexible placement         | Lookup table scalability and HA                                                                 |
| **Cross-shard operations** | N/A                        | Joins and transactions across shards are hard; prefer denormalization or application-level join |

**When to use**: Write or storage exceeds single-node capacity; you can design access patterns around shard key.\
**When not**: Single node suffices; or you need frequent cross-shard transactions (consider alternatives first).

***

## 5. Failure Scenarios

| Scenario          | Mitigation                                                                                |
| ----------------- | ----------------------------------------------------------------------------------------- |
| One shard down    | Replicate each shard (primary + replica); failover per shard                              |
| Hot shard         | Choose different shard key; split hot shard (range); or add more replicas for reads       |
| Resharding        | Double-write during migration; background data move; consistent hashing to minimize moves |
| Cross-shard query | Avoid or limit; use caching/denormalization; or accept scatter-gather cost                |

***

## 6. Performance Considerations

* **Latency**: Single-shard queries are fast; scatter-gather increases latency and load.
* **Throughput**: Total write throughput scales with number of shards (if balanced).
* **Resharding**: Expensive; plan for growth so resharding is rare (e.g. consistent hashing with many virtual nodes).

***

## 7. Implementation Patterns

* **Application-managed**: App has shard map; routes queries by shard key; uses connection pool per shard.
* **Proxy**: Proxy (e.g. Vitess, ProxySQL) does routing; app sends same query.
* **Managed (DynamoDB, etc.)**: Choose partition key; system shards automatically.

***

## Quick Revision

* **Purpose**: Scale writes and storage by partitioning data across nodes.
* **Shard key**: Must be in most queries; should distribute evenly; consider growth.
* **Strategies**: Hash (even), range (range queries, hotspot risk), directory (flexible, lookup cost), consistent hash (minimal resharding).
* **Cross-shard**: Avoid joins/transactions; denormalize or application join.
* **Interview**: “We shard by user\_id so each user’s data is on one shard and we can scale by adding shards; we use consistent hashing so adding a node only moves about 1/N of the data.”