Partitioning Models

Why Partition?

Partitioning splits data across multiple nodes to distribute load. Without partitioning, all data lives on a single node, which becomes a bottleneck for both reads and writes. Partitioning enables horizontal scaling by dividing data into chunks that can be processed independently.

Hash Partitioning

Hash partitioning applies a hash function to the partition key and assigns each key to a partition based on the hash value. This provides even distribution but destroys ordering, making range queries expensive.

import hashlib
from bisect import bisect_right

class ConsistentHashRing:
    def __init__(self, nodes, virtual_nodes=150):
        self.ring = {}
        self.sorted_keys = []
        for node in nodes:
            for i in range(virtual_nodes):
                key = self._hash(f"{node}:{i}")
                self.ring[key] = node
                self.sorted_keys.append(key)
        self.sorted_keys.sort()
    
    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)
    
    def get_node(self, data_key):
        h = self._hash(data_key)
        idx = bisect_right(self.sorted_keys, h) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[idx]]

Range Partitioning

Range partitioning assigns contiguous key ranges to each partition. Keys are sorted and divided into ranges. This preserves ordering and enables efficient range queries but can create hot partitions if the key distribution is skewed.

Partition 0: user_id [0, 1000000)
Partition 1: user_id [1000000, 2000000)
Partition 2: user_id [2000000, 3000000)

Range query: WHERE user_id BETWEEN 500 AND 600
  → Hits only Partition 0 (efficient)

New users (auto-increment):
  → All go to Partition 2 (hot partition)

Composite Partitioning

Composite partitioning combines two or more partitioning strategies. For example, hash-partition by user ID, then range-partition by timestamp within each user. This provides both even distribution and efficient time-range queries within a user.

Hot Key Mitigation

Hot keys are partition keys that receive disproportionate traffic. A celebrity user's profile, a trending topic, or a viral post can overwhelm a single partition. Mitigation strategies include key salting, replication, and local caching.

• Key salting — Append a random suffix to distribute across partitions.
• Replication — Cache hot keys on every node.
• Local caching — Cache hot keys in-process to avoid network hops.
• Dedicated partitions — Assign hot keys to dedicated partitions.

Online Resharding

Online resharding changes the number of partitions while the system is running. This requires careful coordination: new partitions must be populated, routing tables updated, and old partitions cleaned up — all without downtime.

1. Add new empty partitions alongside existing ones.
2. Update the routing table to include new partitions.
3. Begin migrating data from old to new partitions.
4. Verify data integrity after migration.
5. Remove old partitions once migration is complete.