Database Sharding

Metadata

1. Overview

What problem does it solve?

Database Replication solves the problem of scaling reads by adding Read Replicas. But all writes still go to a single Master database.

When your application grows to a massive scale (e.g., millions of users uploading photos), a single Master database will hit physical hardware limits:

1. Disk Space: A 10TB hard drive fills up.
2. Write Throughput: A CPU can only handle so many INSERTs per second.
3. Memory: The index no longer fits in RAM, causing slow disk seeks.

Database Sharding (or Partitioning) solves this by splitting a single large dataset across multiple independent database servers (shards). Each server holds only a portion of the data.

What breaks without it?

• Write Bottlenecks: You cannot accept any more writes if your single master maxes out at 10,000 writes/sec.
• Storage Limits: You cannot store a 50TB table on a 10TB disk.

2. Motivation

In the mid-2000s, monolithic SQL databases were the norm. When a database got too big, companies would buy larger, millions-of-dollars servers from Oracle or IBM (Vertical Scaling).

Web 2.0 companies (Facebook, Twitter) generated data faster than hardware could improve. They realized it was much cheaper to buy 100 cheap, commodity Linux servers and split the data evenly across them (Horizontal Scaling) than to buy one massive supercomputer.

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The Sharding Architecture

Instead of the application talking directly to the database, it talks to a Sharding Router which inspects the query, looks at the Shard Key, and forwards the query to the correct physical server.

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff'}}}%%
graph TD
    classDef client fill:#f9f9f9,stroke:#333,stroke-width:2px;
    classDef router fill:#d4edda,stroke:#28a745,stroke-width:2px;
    classDef db fill:#cce5ff,stroke:#007bff,stroke-width:2px;

    C1((Client)):::client --> |"INSERT User(id=5)"| Router:::router
    
    subgraph Sharding Layer
        Router{{"Sharding Router<br/>(hash(id) % 3)"}}
    end

    subgraph Data Shards
        DB0[(Shard 0<br/>Users 0, 3, 6...)]:::db
        DB1[(Shard 1<br/>Users 1, 4, 7...)]:::db
        DB2[(Shard 2<br/>Users 2, 5, 8...)]:::db
    end

    Router -. "5 % 3 = 2" .-> DB2

6. Internal Working

6.1 The Shard Key

To split data, you must choose a column to partition by. This is the Shard Key. For a Users table, the Shard Key is usually user_id. For a Messages table, it might be chat_id.

Rules of a good Shard Key:

1. High Cardinality: You need many distinct values (e.g., user_id has millions, country only has 195).
2. Even Distribution: Prevents "Hotspots" (e.g., if you shard by timestamp, the shard holding "today" gets 100% of the writes).

6.2 Sharding Strategies

1. Hash Sharding (Algorithmic)

   • Formula: hash(shard_key) % num_shards
   • Pros: Extremely even distribution.
   • Cons: Range queries are impossible (e.g., "Get users 10 to 50" requires querying every single shard). Adding new shards requires moving massive amounts of data (unless you use Consistent Hashing).

2. Range Sharding

   • e.g., Shard 0: Users A-M, Shard 1: Users N-Z.
   • Pros: Range queries are fast.
   • Cons: Highly prone to hotspots if the data isn't perfectly uniform.

3. Directory-Based Sharding

   • A centralized lookup table (e.g., stored in Redis) maps specific keys to specific shards.
   • Pros: Maximum flexibility. You can move individual users to different shards easily.
   • Cons: The lookup table itself becomes a single point of failure and a performance bottleneck.

7. Implementation

Why Python? Python dictionaries serve as excellent mock databases. We can easily implement a Sharding Router class that intercepts queries and demonstrates Hash Sharding versus Range Sharding logic.

"""
020 - Database Sharding Simulation
Simulates a routing layer that distributes data across multiple
physical database shards using Hash Sharding.
"""
import hashlib

class DatabaseShard:
    def __init__(self, shard_id):
        self.shard_id = shard_id
        self.data = {}  # Mock table

    def insert(self, key, value):
        self.data[key] = value
        print(f"[Shard {self.shard_id}] INSERT {key} -> {value}")

    def read(self, key):
        return self.data.get(key, None)


class ShardingRouter:
    def __init__(self, num_shards):
        self.num_shards = num_shards
        # Initialize physical shards
        self.shards = [DatabaseShard(i) for i in range(num_shards)]

    def _get_shard_index(self, shard_key):
        """
        Hash Sharding strategy: hash(shard_key) % num_shards.
        Uses MD5 for a uniform distribution.
        """
        hash_val = int(hashlib.md5(str(shard_key).encode('utf-8')).hexdigest(), 16)
        return hash_val % self.num_shards

    def insert_user(self, user_id, user_data):
        """Route an insert query to the correct shard."""
        shard_idx = self._get_shard_index(user_id)
        target_shard = self.shards[shard_idx]
        target_shard.insert(user_id, user_data)

    def get_user(self, user_id):
        """Route a read query to the correct shard."""
        shard_idx = self._get_shard_index(user_id)
        target_shard = self.shards[shard_idx]
        
        data = target_shard.read(user_id)
        print(f"[Router] Searched Shard {shard_idx} for User {user_id}. Result: {data}")
        return data

    def search_all(self, query_value):
        """
        The Scatter-Gather Problem.
        If we search by something that IS NOT the shard key,
        we must query EVERY shard.
        """
        print(f"\n[Router] SCATTER-GATHER: Searching all shards for value '{query_value}'...")
        results = []
        for shard in self.shards:
            for k, v in shard.data.items():
                if v == query_value:
                    results.append(k)
                    print(f"  -> Found in Shard {shard.shard_id}")
        return results


# ── Test Harness ──

if __name__ == "__main__":
    print("--- 1. Initializing 3 Database Shards ---")
    router = ShardingRouter(num_shards=3)

    print("\n--- 2. Inserting Users (Routing by user_id) ---")
    # Notice how they are distributed randomly but uniformly due to MD5 hashing
    router.insert_user(101, "Alice")
    router.insert_user(205, "Bob")
    router.insert_user(309, "Charlie")
    router.insert_user(412, "Dave")
    router.insert_user(555, "Eve")

    print("\n--- 3. Reading a specific user (O(1) Shard lookup) ---")
    router.get_user(309)
    router.get_user(101)

    print("\n--- 4. The Scatter-Gather Problem ---")
    # We want to find Eve, but we don't know her user_id!
    # Because data is sharded by user_id, we have to check everywhere.
    router.search_all("Eve")

Sample Output

--- 1. Initializing 3 Database Shards ---

--- 2. Inserting Users (Routing by user_id) ---
[Shard 1] INSERT 101 -> Alice
[Shard 2] INSERT 205 -> Bob
[Shard 1] INSERT 309 -> Charlie
[Shard 0] INSERT 412 -> Dave
[Shard 2] INSERT 555 -> Eve

--- 3. Reading a specific user (O(1) Shard lookup) ---
[Router] Searched Shard 1 for User 309. Result: Charlie
[Router] Searched Shard 1 for User 101. Result: Alice

--- 4. The Scatter-Gather Problem ---

[Router] SCATTER-GATHER: Searching all shards for value 'Eve'...
  -> Found in Shard 2

8. Complexity

9. Trade-offs

Sharding introduces immense complexity. Do not shard until you absolutely have to.

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. What is the difference between Replication and Sharding? Hint: Replication duplicates the exact same data to scale READS. Sharding splits data into pieces to scale WRITES and STORAGE.

2. What is the "Scatter-Gather" problem? Hint: When a query does not contain the Shard Key, the router must send the query to every single shard and merge the results.

3. Why is it a bad idea to shard a multi-tenant SaaS application by company_id? Hint: Data skew (Hotspots). One massive enterprise customer will overload a single shard, while 1,000 small startups sit idle on another.

4. How do you perform a JOIN across two tables that are on different shards? Hint: You generally don't. You denormalize the data before writing, or pull the data into the application layer and join it in memory.

13. Used By (Downstream Blocks)

• 021 CAP Theorem — Sharded databases almost always experience network partitions, forcing tough choices.
• 026 Distributed Transactions — Required if you need to update Data A on Shard 1 and Data B on Shard 2 atomically.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Directory-Based Routing

Modify the ShardingRouter to use a mapping dictionary instead of a hash function. E.g., self.mapping = {101: 0, 205: 1}. Write a function to smoothly migrate user_id: 101 from Shard 0 to Shard 2 by copying the data, updating the mapping, and deleting the old data.

Exercise 2: The Celebrity Hotspot

Modify the insert_user logic to simulate a "celebrity". If user_id == "JUSTIN_BIEBER", the router should append a random number 1-10 to the user_id before hashing it, thus spreading Justin's data across multiple shards to prevent a hotspot.

Website Metadata