# Database Sharding

Database sharding is a method of splitting and storing a single logical dataset in multiple databases. By distributing the data among multiple machines, a single database server does not have to handle all the incoming requests or store all the data.

## 1. The Core Concept

Sharding is a form of **Horizontal Scaling** (Scaling Out).
*   **Vertical Scaling:** Adding more CPU/RAM to a single server. Eventually, you hit a hardware limit.
*   **Horizontal Scaling (Sharding):** Adding more servers. You split your 1TB user table into four 250GB tables across four servers.

Each individual partition is called a **Shard** or **Database Shard**. All shards together make up the single logical dataset.

## 2. The Shard Key

The most critical decision in sharding is choosing the **Shard Key** (Partition Key). This determines how data is distributed.
*   **Example:** If you shard by `UserID`, all data for User A goes to Shard 1, and User B goes to Shard 2.
*   **Routing:** The application or a proxy (like Mongos) uses the Shard Key to know which server to query.

## 3. Sharding Strategies

### Key Based Sharding (Hash Sharding)
Uses a hash function on the Shard Key to determine the partition.
*   **Formula:** `Shard_ID = hash(Key) % Number_of_Shards`.
*   **Pros:** Even distribution of data (prevents hotspots).
*   **Cons:** Adding/removing servers is difficult (requires rebalancing everything). **Consistent Hashing** solves this.

### Range Based Sharding
Divides data based on ranges of the Shard Key.
*   **Example:** IDs 1-1000 go to Shard A, 1001-2000 go to Shard B.
*   **Pros:** Easy to implement. Good for range queries (`SELECT * WHERE ID BETWEEN 100 AND 200`).
*   **Cons:** Can lead to uneven distribution (Hotspots). If IDs are sequential (timestamps), all new writes go to the last shard.

### Directory Based Sharding
A lookup service (Directory) maintains a map of which shard holds which data.
*   **Pros:** Flexible. You can move data freely without changing the key.
*   **Cons:** The lookup service becomes a single point of failure and a performance bottleneck.

## 4. Benefits

*   **Scalability:** Theoretically infinite scaling for both storage and throughput.
*   **Availability:** If one shard goes down, only a portion of the data is unavailable. The rest of the system continues to work.
*   **Performance:** Smaller indexes and tables mean faster query speeds on individual shards.

## 5. Challenges (The Cost of Sharding)

Sharding introduces significant complexity.

*   **Joins:** You cannot perform a standard SQL `JOIN` across two different shards (machines). You must do joins in the application code.
*   **Transactions:** ACID transactions across shards (Distributed Transactions) are slow and complex (requires 2PC or Sagas).
*   **Rebalancing:** If one shard fills up, moving data to a new shard while the system is live is difficult.
*   **Operational Complexity:** Managing 100 database servers is much harder than managing 1.

## 6. Database Partitioning vs Sharding

While often used interchangeably, there is a technical distinction:

*   **Partitioning:** A general term for splitting a database table into smaller chunks.
    *   **Vertical Partitioning:** Splitting columns (e.g., moving a large `BLOB` column to a separate table).
    *   **Horizontal Partitioning:** Splitting rows (e.g., rows 1-1000 in one chunk, 1001-2000 in another).
*   **Sharding:** A specific type of **Horizontal Partitioning** where the partitions are distributed across **multiple servers** (nodes).

**Summary:** All sharding is partitioning, but not all partitioning is sharding. If the partitions sit on the same physical server, it's just partitioning. If they sit on different servers, it's sharding.

[[programming/database-basics]]
[[programming/distributed-systems]]
[[programming/consistent-hashing]]
[[programming/system-design]]