Database Sharding

# Package: io.thecodeforge.python.system_design

# Simple shard router based on user_id
class ShardRouter:
    def __init__(self, shards):
        self.shards = shards  # list of database connections
        self.n = len(shards)

    def get_shard(self, user_id: int):
        """Hash sharding: user_id % number_of_shards."""
        return self.shards[user_id % self.n]

    def query_user(self, user_id: int, sql: str):
        shard = self.get_shard(user_id)
        return shard.execute(sql, user_id)

# Example: 4 shards
# user_id 1001 → shard 1001 % 4 = 1
# user_id 1002 → shard 1002 % 4 = 2
# user_id 1000 → shard 1000 % 4 = 0

# Cross-shard query — must broadcast to all shards (expensive)
# SELECT * FROM orders WHERE order_date = '2025-01-01'
# This hits ALL 4 shards and merges results in application layer

# Hash sharding: even distribution, no hot shards
# Weakness: range queries require broadcast
def hash_shard(user_id, n_shards):
    return user_id % n_shards

# Range sharding: range queries efficient, but hot shard risk
# Shard 0: user_ids 1 to 1,000,000
# Shard 1: user_ids 1,000,001 to 2,000,000
# etc.
RANGE_BOUNDARIES = [0, 1_000_000, 2_000_000, 3_000_000]

def range_shard(user_id, boundaries):
    for i, boundary in enumerate(boundaries[1:], 1):
        if user_id < boundary:
            return i - 1
    return len(boundaries) - 1

# Hot shard problem with range sharding:
# If all new users have sequential IDs, new users always go to the LAST shard
# That shard gets all the write load — called a hot shard

# Consistent hashing: used by Cassandra, DynamoDB
# Solves resharding without reassigning all data
# When adding a shard, only the adjacent shard's data needs to move