Data Sharding Strategies: Hash and Range Partitioning

1. What is Data Partitioning?

Before we dive into the specific strategies, let's establish what partitioning is and what we're trying to achieve. In essence, partitioning is the process of taking a large database table and breaking it into smaller, more manageable pieces called partitions or shards, which are then spread across multiple database nodes.

As the video highlights, the ideal partitioning scheme avoids hotspots—nodes that receive a disproportionate amount of data or queries. This process of splitting a table's rows into subsets across different machines is more formally known as horizontal partitioning.

Now, let's get into the implementation details of the two most common strategies.

2. Strategy 1: Range-based Partitioning

This is the most straightforward approach to partitioning. We choose a partitioning key (e.g., user ID, product SKU, creation timestamp) and divide its possible values into contiguous ranges. Each range is then assigned to a specific partition.

How it Works

Imagine an orders table with an order_date column as the partitioning key. We could decide:

• Shard 1: Orders from 2022
• Shard 2: Orders from 2023
• Shard 3: Orders from 2024

To route a query, the system needs to know which shard holds the data. This is typically done using a simple metadata lookup table.

// Metadata mapping ranges to shard IDs
RangeShardMap = {
  (-∞, '2023-01-01'): Shard1,
  ['2023-01-01', '2024-01-01'): Shard2,
  ['2024-01-01', +∞): Shard3
}

Implementation Logic

From an implementation standpoint, finding the correct shard for a given key is a simple lookup. Given your background in data structures, you can think of this lookup table as being implemented with a sorted list or a balanced binary search tree for efficient searching.

// Pseudocode for finding a shard for a given key
class RangePartitioner {
    // Stores range boundaries and corresponding shard IDs.
    // E.g., a sorted list of pairs: (upper_bound, shard_id)
    private SortedMap<Key, ShardID> rangeMap;

    public ShardID findShardForKey(Key k) {
        // Find the first range boundary that is greater than the key.
        // The shard associated with that boundary is our target.
        for (Entry<Key, ShardID> entry : rangeMap.entrySet()) {
            if (k.compareTo(entry.getKey()) < 0) {
                return entry.getValue();
            }
        }
        // Should not happen if ranges are configured correctly
        return null; 
    }
}

Trade-offs

As summarized in the video:

• Pro: Very efficient for range queries. If you want to fetch all orders from January 2024, the router knows to query only Shard 3. This is a huge performance win.
• Con: Highly susceptible to hotspots. If our partitioning key is a timestamp or an auto-incrementing ID, all new data will be written to the same shard. This last shard becomes a write bottleneck, while the others are mostly idle for writes.

3. Strategy 2: Hash-based Partitioning

To overcome the hotspot problem of range partitioning, we can use a hash function to distribute keys more uniformly across shards.

Part A: Simple Hash Partitioning

The most basic form is to hash the partitioning key and then apply a modulo operator with the number of shards.

Partition ID = hash(partitioning_key) % N

Where N is the number of shards.

A good hash function will map seemingly random keys, spreading the load evenly. For example, user_id_12345 and user_id_12346 are likely to end up on completely different shards, eliminating the sequential write hotspot we saw with range partitioning.

Trade-offs

• Pro: Excellent for uniform data and load distribution, assuming a good hash function. This makes it ideal for workloads with many point lookups (e.g., fetching a user profile by user_id).
• Con: Destroys the natural ordering of keys. Running a range query (e.g., "find all users with IDs between 1000 and 2000") is now disastrously inefficient, as it would require querying every single shard.
• The Big Engineering Problem: What happens when you need to add or remove a shard? If you change N (the number of shards), the result of hash(key) % N changes for almost every key! This would require a massive, system-wide reshuffling of data, which is operationally infeasible for large systems.

Part B: Consistent Hashing — The Solution

To solve this massive re-shuffling problem, distributed systems use a more sophisticated technique called Consistent Hashing. This is a critical algorithm for any engineer working on scalable systems.

The core idea is to map both the nodes (shards) and the data keys onto the same abstract circle (a "hash ring"). To find the shard for a key, you hash the key to find its position on the ring and then travel clockwise until you find a node. That node is responsible for the key.

Now, let's see how this works visually.

Implementation Logic and "Virtual Nodes"

To implement consistent hashing, you need a data structure that can efficiently find the next node on the ring. A balanced binary search tree or a sorted array (with binary search) containing the hash values of the nodes would work well.

// Pseudocode for Consistent Hashing
class ConsistentHasher {
    // A map of node hash values to node IDs, kept sorted by hash value.
    private SortedMap<Integer, NodeID> ring; 

    // Add a node to the ring
    public void addNode(NodeID nodeId) {
        ring.put(hash(nodeId), nodeId);
    }

    // Get the node responsible for a key
    public NodeID getNodeForKey(Key k) {
        int keyHash = hash(k);
        // Find all nodes with hashes greater than the key's hash
        SortedMap<Integer, NodeID> tailMap = ring.tailMap(keyHash);
        
        int nodeHash;
        if (tailMap.isEmpty()) {
            // Wrap around: key is after the last node, so it belongs to the first node
            nodeHash = ring.firstKey();
        } else {
            // The first node found clockwise is the correct one
            nodeHash = tailMap.firstKey();
        }
        return ring.get(nodeHash);
    }
}

One final problem remains: if nodes are placed randomly on the ring, some might get a much larger share of the keys than others. The solution is to use virtual nodes. Instead of placing one point on the ring for each physical node, we place many (e.g., 100) virtual points for each node. This smooths out the distribution, making it statistically much more likely that each physical node gets a similar amount of data.

Consistent hashing, with virtual nodes, is the de-facto standard for hash partitioning in many popular NoSQL databases like Amazon DynamoDB and Apache Cassandra.

Conclusion

In this lesson, we explored the two primary strategies for data partitioning in a shared-nothing system. The choice between them is a classic engineering trade-off driven by your application's query patterns.

Key Takeaways:

• Partitioning (Sharding) is the process of splitting table data horizontally across multiple nodes.
• Range Partitioning is simple and highly efficient for range queries but is vulnerable to creating hotspots with sequential keys.
• Hash Partitioning provides excellent load balancing for point lookups but makes range queries inefficient.
• Simple "modulo N" hashing is not viable in dynamic systems due to the massive data reshuffling required when nodes are added or removed.
• Consistent Hashing is a critical algorithm that solves this rebalancing problem, enabling hash-partitioned systems to scale elastically with minimal data movement.

Preview of the Next Lesson

Now that we understand how to distribute data across multiple nodes, the next question is: how do we execute a query that needs this distributed data? In our next lesson, we will explore techniques for parallel query execution, starting with how to explain inter-operator and intra-operator parallelism in a shared-nothing system.