Understanding Database Sharding Algorithms: Database Internals

Introduction and Core Concepts

Database sharding algorithms are the foundational strategies that enable horizontal scaling of data storage systems beyond the limits of a single machine. In an era where applications routinely manage terabytes to petabytes of data and serve millions of concurrent users, the ability to distribute data across multiple independent database nodes — called shards — has become essential for performance, availability, and cost efficiency. Unlike vertical scaling, which involves adding more CPU, RAM, or storage to a single server, sharding embraces a distributed architecture where each shard holds a distinct subset of the overall dataset and can reside on separate physical hardware, virtual machines, or containers.

At its core, a sharding algorithm is a deterministic function that maps a data record, typically identified by a shard key, to a specific shard. This mapping must be fast, balanced, and predictable so that any application server or database router can locate the correct shard for a read or write operation without scanning all nodes. The quality of the sharding algorithm directly impacts load distribution, query latency, operational complexity, and the system's ability to scale elastically. A poor algorithm can lead to hot spots where one shard receives disproportionate traffic, while a well-designed algorithm ensures uniform data and request distribution even as the dataset and cluster topology evolve.

Understanding database sharding algorithms matters because they sit at the intersection of database internals, distributed systems theory, and practical engineering trade-offs. Modern distributed databases such as MongoDB, Apache Cassandra, Amazon DynamoDB, and Vitess for MySQL all implement sophisticated sharding layers. Even when using a managed service, developers and architects must choose shard keys, understand rebalancing behavior, and anticipate failure modes. Without this knowledge, teams risk designing schemas that cannot scale, queries that require expensive scatter-gather operations across all shards, or migrations that cause prolonged downtime.

What Is a Shard?

A shard is a horizontal partition of a database — a complete, independent database instance that holds a portion of the rows or documents from a larger logical table or collection. For example, a users table with 100 million rows might be split into four shards, each holding approximately 25 million rows based on the user ID. Each shard has its own indexes, transaction log, and resources, and can be queried independently. The collection of all shards together represents the full dataset, but no single shard contains all the data.

This is distinct from vertical partitioning, where different columns or tables are split across databases, and from replication, where the same data is copied to multiple nodes for redundancy. Sharding is often combined with replication: each shard is typically replicated across two or more nodes to provide fault tolerance, creating a shard replica set. The sharding algorithm governs placement, while the replication protocol governs durability and consistency within each shard.

Why Sharding Matters at Scale

Single-node databases face hard physical limits on storage capacity, memory, write throughput, and connection handling. Sharding addresses these limits by enabling linear scalability — adding more shards increases total capacity and throughput. It also improves fault isolation: a failure or slowdown in one shard does not necessarily bring down the entire system, and maintenance can be performed on a per-shard basis. For global applications, sharding enables geographic distribution, placing data close to users to reduce latency and comply with data residency regulations.

However, sharding introduces significant complexity. Cross-shard transactions become expensive or impossible, joins across shards must be handled at the application layer, and rebalancing data when adding or removing shards can be operationally heavy. Choosing the right algorithm upfront is therefore critical, as changing the sharding strategy later often requires a full data migration and application rewrite.

How It Works

The general mechanism of database sharding follows a consistent pipeline: extract a shard key from an incoming query or write, apply the sharding algorithm to compute a target shard identifier, route the operation to that shard via a router or coordinator layer, and then execute the operation locally on that shard. The router may be a dedicated proxy such as mongos for MongoDB, Vitess VTGate, or a client-side library that embeds the sharding logic. This routing must be highly available and low-latency, as it sits on the critical path of every database operation.

The shard key is the most important design decision in this pipeline. It can be a single field such as user_id, a composite key such as (tenant_id, created_at), or a hash of one or more fields. A good shard key has high cardinality, meaning many distinct values, is uniformly distributed, and aligns with the application's most common query patterns. If the application frequently queries by user_id, sharding by user_id allows most queries to be directed to a single shard. If the shard key is rarely used in queries, the system will be forced to broadcast queries to all shards, negating many benefits of sharding.

Once the shard key is selected, the algorithm determines placement. The simplest approach is to apply a hash function to the key and take the modulo with the number of shards. More advanced approaches use range boundaries, consistent hashing rings, or an external directory service. Each has different trade-offs in terms of data locality, rebalancing cost, and operational overhead, which we explore in detail below.

The Sharding Pipeline in Detail

When a write arrives, the application extracts the shard key, computes hash(key) % N or performs a range lookup, and forwards the write to the corresponding shard. For reads, the same computation occurs. If the query does not contain the shard key, the router must perform a scatter-gather operation: it sends the query to all shards, collects the partial results, merges and sorts them, and returns the combined result to the client. Scatter-gather queries are significantly slower and more resource-intensive, which is why shard key selection is so critical.

Metadata management is another core component. The system must maintain a mapping of shard topology — which key ranges or hash slots belong to which physical node — and propagate changes consistently to all routers. This metadata is typically stored in a highly available configuration service such as ZooKeeper, etcd, or a dedicated config server replica set. Updates to this metadata during rebalancing must be atomic to avoid routing errors.

Primary Sharding Strategies

There are four dominant families of sharding algorithms. Range-based sharding partitions data by intervals of the shard key, preserving order and enabling efficient range scans but risking hot spots if the key is monotonically increasing like a timestamp or auto-increment ID. Hash-based sharding distributes keys pseudo-randomly using a hash function, achieving excellent balance but destroying ordering and making range queries expensive.

Consistent hashing maps both shards and keys onto a circular hash ring, minimizing data movement when nodes are added or removed — only K/N keys need to move where K is total keys and N is number of shards. Directory-based sharding uses a lookup table that explicitly maps each key or key range to a shard, offering maximum flexibility for custom placement and rebalancing at the cost of an extra lookup hop and the need to manage the directory itself.

Implementation

Implementing sharding algorithms in practice requires careful attention to hash function choice, handling of cluster membership changes, and integration with the application layer. Below are four canonical implementations in Python that illustrate the core ideas. These are simplified for clarity but capture the essential logic used in production systems. Note that production implementations would add persistence, concurrency control, and failure handling.

Hash-Based Sharding

Hash-based sharding is the most common default due to its simplicity and uniform distribution. It uses a stable hash function such as MD5, SHA-1, or MurmurHash to convert any shard key into a large integer, then maps that integer to a shard via modulo arithmetic.

import hashlib

def get_shard_id(key: str, num_shards: int) -> int:
    """
    Simple hash-based sharding using MD5.
    Deterministically maps any key to a shard ID in [0, num_shards).
    Uses a stable hash so the same key always maps to the same shard.
    """
    # Create a stable hash of the key (MD5 is fast and sufficient for sharding)
    hash_hex = hashlib.md5(key.encode('utf-8')).hexdigest()
    hash_int = int(hash_hex, 16)
    # Modulo maps the large hash space to the shard count
    shard_id = hash_int % num_shards
    return shard_id

# Example usage
keys = ["user:1001", "user:1002", "user:1003", "order:5001"]
for k in keys:
    print(f"{k} -> Shard {get_shard_id(k, 4)}")

# Verifying distribution
from collections import Counter
dist = Counter(get_shard_id(f"user:{i}", 4) for i in range(10000))
print(dist)  # Should be roughly balanced: ~2500 per shard

Range-Based Sharding

Range-based sharding is ideal when ordered scans are required, such as retrieving all orders for a date range. It defines explicit boundaries for each shard and assigns keys based on where they fall in the sorted order.

def range_shard(key: int, boundaries: list) -> int:
    """
    Range-based sharding for ordered numeric keys.
    boundaries: sorted list of upper bounds for each shard.
    Returns shard_id where key belongs.
    """
    for shard_id, upper in enumerate(boundaries):
        if key < upper:
            return shard_id
    # If key is greater than all boundaries, assign to last shard
    return len(boundaries) - 1

# Shard boundaries: Shard 0: < 10000, Shard 1: < 20000, Shard 2: < 30000, Shard 3: rest
boundaries = [10000, 20000, 30000, float('inf')]
print(range_shard(5234, boundaries))   # -> 0
print(range_shard(18500, boundaries))  # -> 1
print(range_shard(45000, boundaries))  # -> 3

# Range query optimization: only shards 1 and 2 needed for 15000 <= key < 25000
def shards_for_range(low: int, high: int, boundaries: list) -> list:
    """Determine which shards to query for a range scan."""
    needed = set()
    for key in [low, high]:
        needed.add(range_shard(key, boundaries))
    # In production, iterate over all boundaries between low and high
    return sorted(needed)

Consistent Hashing with Virtual Nodes

Consistent hashing solves the major drawback of naive hash modulo sharding: when the number of shards changes, nearly all keys must be remapped. By placing nodes and keys on a ring, only a fraction of keys move during topology changes. Virtual nodes improve balance by assigning multiple points on the ring to each physical shard.

import bisect
import hashlib

class ConsistentHashRing:
    def __init__(self, nodes=None, replicas=100):
        self.replicas = replicas
        self.ring = {}  # hash -> node
        self.sorted_keys = []
        if nodes:
            for node in nodes:
                self.add_node(node)

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node: str):
        """Add a physical node with many virtual replicas for balance."""
        for i in range(self.replicas):
            virtual_key = f"{node}:{i}"
            h = self._hash(virtual_key)
            self.ring[h] = node
            bisect.insort(self.sorted_keys, h)

    def remove_node(self, node: str):
        """Remove node and its virtual replicas."""
        for i in range(self.replicas):
            virtual_key = f"{node}:{i}"
            h = self._hash(virtual_key)
            if h in self.ring:
                del self.ring[h]
                self.sorted_keys.remove(h)

    def get_node(self, key: str) -> str:
        """Get the node responsible for a given key (clockwise search)."""
        if not self.ring:
            return None
        h = self._hash(key)
        # Find first node with hash >= key hash
        idx = bisect.bisect(self.sorted_keys, h)
        if idx == len(self.sorted_keys):
            idx = 0  # Wrap around the ring
        return self.ring[self.sorted_keys[idx]]

# Usage
ring = ConsistentHashRing(["shard-0", "shard-1", "shard-2"], replicas=100)
print(ring.get_node("user:8421"))
print(ring.get_node("order:9912"))

# Adding a node only moves ~1/N keys
ring.add_node("shard-3")
print(f"After adding shard-3, user:8421 -> {ring.get_node('user:8421')}")

Directory-Based Sharding

Directory-based sharding provides explicit control by maintaining a central lookup table. This is used by systems like Vitess and some multi-tenant SaaS platforms where custom placement rules or frequent rebalancing is required.

import hashlib
from collections import defaultdict

class DirectoryShardManager:
    def __init__(self, total_slots=1024):
        self.total_slots = total_slots
        self.shard_map = {}  # slot -> shard_id
        self.shard_stats = defaultdict(lambda: {"count": 0, "size_bytes": 0})

    def add_shard_mapping(self, start: int, end: int, shard_id: str):
        """Map a contiguous range of hash slots to a shard."""
        for slot in range(start, end):
            self.shard_map[slot] = shard_id

    def get_shard(self, key: str) -> str:
        """Lookup shard via directory service (extra hop)."""
        slot = int(hashlib.md5(key.encode()).hexdigest(), 16) % self.total_slots
        return self.shard_map.get(slot, "shard-0")

    def record_write(self, key: str, size_bytes: int):
        shard = self.get_shard(key)
        self.shard_stats[shard]["count"] += 1
        self.shard_stats[shard]["size_bytes"] += size_bytes

    def rebalance_needed(self, threshold=0.25) -> bool:
        """Check if any shard exceeds threshold imbalance."""
        if not self.shard_stats:
            return False
        counts = [v["count"] for v in self.shard_stats.values()]
        avg = sum(counts) / len(counts)
        for c in counts:
            if avg > 0 and abs(c - avg) / avg > threshold:
                return True
        return False

# Initialize directory: 1024 slots across 4 shards
mgr = DirectoryShardManager(total_slots=1024)
mgr.add_shard_mapping(0, 256, "shard-0")
mgr.add_shard_mapping(256, 512, "shard-1")
mgr.add_shard_mapping(512, 768, "shard-2")
mgr.add_shard_mapping(768, 1024, "shard-3")
print(mgr.get_shard("tenant:acme:user:123"))  # -> deterministic shard

Step-by-Step Example

To make these concepts concrete, let us walk through a complete example of consistent hashing with virtual nodes, as this is the most widely used algorithm in modern distributed databases. Imagine an e-commerce platform with an orders collection that has grown to 40 million documents. The team decides to shard across four shards to handle write throughput and storage.

We will use consistent hashing with 3 physical shards initially, each with 3 virtual nodes for illustration, and trace how five sample order keys are placed, then observe what happens when a fourth shard is added.

Initial Setup: 3 Shards on the Ring

We create a hash ring with a simplified hash space of 0 to 99 for readability. Each physical shard is assigned multiple virtual positions on the ring by hashing shard_id + replica_index. Suppose the virtual node positions after hashing are: shard-0 at positions 12, 37, 68; shard-1 at positions 25, 51, 89; shard-2 at positions 5, 44, 77. Sorted, the ring order is: 5(shard-2), 12(shard-0), 25(shard-1), 37(shard-0), 44(shard-2), 51(shard-1), 68(shard-0), 77(shard-2), 89(shard-1).

Now we hash five order keys: order:1001 hashes to 14, order:1002 to 42, order:1003 to 55, order:1004 to 80, order:1005 to 2. To find the responsible shard, we move clockwise from the key's hash to the next virtual node. order:1001 at 14 finds the next node at 25 which belongs to shard-1, so it is stored on shard-1. order:1002 at 42 finds 44 on shard-2. order:1003 at 55 finds 68 on shard-0. order:1004 at 80 finds 89 on shard-1. order:1005 at 2 wraps around the ring to 5 on shard-2.

The resulting distribution is: shard-0 has 1 key, shard-1 has 2 keys, shard-2 has 2 keys. With more keys and more virtual nodes (typically 100-200 per physical node), this distribution converges to near-perfect balance. The key property is that each key is deterministically mapped, and the mapping can be computed independently by any router that holds the ring topology.

Adding a New Shard: Minimal Data Movement

Six months later, data volume doubles and the team adds shard-3. Its virtual nodes hash to positions 30, 60, and 95. Inserting these into the sorted ring gives: 5(shard-2), 12(shard-0), 25(shard-1), 30(shard-3), 37(shard-0), 44(shard-2), 51(shard-1), 60(shard-3), 68(shard-0), 77(shard-2), 89(shard-1), 95(shard-3).

We re-evaluate the five keys. order:1001 at 14 still maps to 25 on shard-1, unchanged. order:1002 at 42 still maps to 44 on shard-2, unchanged. order:1003 at 55 now finds 60 on shard-3 instead of 68 on shard-0, so it moves from shard-0 to shard-3. order:1004 at 80 still maps to 89 on shard-1. order:1005 at 2 still maps to 5 on shard-2. Only one of five keys moved, approximately 1/N where N is the new shard count of 4. In a naive hash modulo scheme, changing from 3 to 4 shards would have remapped nearly all keys, requiring a massive data migration. With consistent hashing, only the keys that fall between the new nodes and their predecessors move, enabling elastic scaling with minimal disruption.

Handling Queries

For a point query such as db.orders.find({order_id: 1003}), the router hashes order:1003 to 55, finds shard-3, and routes directly to that shard. Latency is equivalent to a single-shard query. For a range query such as db.orders.find({order_id: {$gte: 1002, $lt: 1004}}), the router would need to query multiple shards because hash-based sharding destroys ordering. This is why applications that require range scans often choose range-based sharding or maintain a secondary index, trading off perfect balance for query efficiency.

Complexity Analysis

Understanding the computational and operational complexity of sharding algorithms is essential for capacity planning and performance tuning. The complexities below refer to the routing and management operations, not the underlying database operations on each shard, which retain their own complexities such as O(log N) for indexed lookups.

For point lookups where the shard key is provided, hash-based and consistent hashing both achieve O(1) average time to compute the target shard, as they involve a single hash computation and either a modulo or a binary search over a small sorted list of virtual nodes. Range-based sharding requires a binary search over the boundary array, giving O(log S) where S is the number of shards, which is effectively constant for typical cluster sizes under 1000 shards. Directory-based sharding adds a network hop to consult the directory service, making it O(1) computationally but with higher latency.

The most significant complexity difference appears during rebalancing. Naive hash modulo sharding requires O(K) data movement where K is total number of keys, as every key may need to be relocated when shard count changes. Consistent hashing reduces this to O(K/N), moving only the keys that map to the new or removed nodes. Range-based sharding can be O(K/N) if ranges are split, but may require O(K) if the key distribution is skewed and a full rebalancing is needed. Directory-based sharding can achieve O(K/N) with fine-grained slots, as only the slots reassigned to new shards need to move.

Where V is the number of virtual nodes, S is the number of shards, K is total keys, N is shard count, T is total slots, and R is the number of shards that overlap the queried range. Space overhead for consistent hashing is dominated by the virtual node table, typically a few hundred entries per physical node, which is negligible. Directory-based sharding requires storing the full slot-to-shard mapping, which for 1024 or 4096 slots is also small but must be replicated for high availability.

In practical terms, the routing computation itself is rarely the bottleneck. The dominant costs are network round trips, scatter-gather fan-out for queries lacking the shard key, and the I/O cost of moving data during rebalancing. Therefore, optimizing for minimal data movement and maximal query pruning often outweighs micro-optimizations of the hash function.

Variations and Optimizations

While the basic sharding strategies are powerful, production systems employ numerous variations and optimizations to handle skew, improve balance, and reduce operational pain. Understanding these enhancements is key to designing a robust sharding layer that adapts to real-world data distributions.

Virtual Nodes and Weighted Sharding

Virtual nodes, also called vnodes, are a critical optimization for consistent hashing. Instead of mapping each physical shard to a single point on the ring, each shard is assigned many virtual positions, often 100 to 200. This dramatically improves load balance, especially when the number of physical shards is small, and allows for heterogeneous hardware. A more powerful shard with twice the capacity can be assigned twice as many virtual nodes, receiving a proportionally larger share of keys. This weighted sharding is essential in cloud environments where shard instances may have different sizes.

Another optimization is bounded-load consistent hashing, which prevents any single shard from becoming overloaded due to hash collisions or skewed key popularity. When a key maps to an overloaded shard, the algorithm probes to the next node on the ring until it finds a shard below a load threshold. This adds a small amount of extra lookup cost but prevents catastrophic hot spots.

Composite and Hashed Shard Keys

Many systems support composite shard keys that combine multiple fields, such as (tenant_id, user_id). This allows for hierarchical locality: all data for a single tenant is co-located, enabling efficient tenant-scoped queries while still distributing tenants across shards. Hashed shard keys apply a hash function to the shard key before range partitioning, combining the balance of hashing with the ability to use range-based chunk management. MongoDB's hashed sharding is a prime example, where the hash of the shard key is range-partitioned into chunks that can be migrated independently.

Zone and Tag-Aware Sharding

Advanced deployments use zone-aware or tag-aware sharding to enforce placement constraints. For example, European user data can be constrained to shards located in EU data centers for GDPR compliance, while US data stays in US shards. This is implemented by tagging shards with zones and defining zone ranges that map key intervals to specific zones. The sharding algorithm then respects these constraints during placement and rebalancing, ensuring regulatory and latency requirements are met without application-level logic.

Dynamic Chunk Splitting and Auto-Balancing

Instead of statically partitioning the key space, many systems use dynamic chunks or tablets that split automatically when they grow too large. For instance, a chunk might be defined as a range of hash values or key values, and when its size exceeds 64 MB, it splits into two smaller chunks. A background balancer then migrates chunks between shards to equalize load. This approach, used by MongoDB and CockroachDB, decouples the logical partitioning from physical shard assignment and enables fine-grained, incremental rebalancing without manual intervention.

Real-World Applications

Database sharding algorithms are not theoretical curiosities; they power some of the largest and most demanding systems on the internet. Their application spans industries where data volume, throughput, or geographic distribution exceeds single-node capabilities.

In e-commerce and SaaS platforms, multi-tenant sharding is ubiquitous. Salesforce, Shopify, and similar platforms shard by tenant or organization ID, ensuring that each customer's data is isolated to a subset of shards. This provides performance isolation, simplifies per-tenant backups, and allows large tenants to be moved to dedicated shards. Hash-based or directory-based sharding is common here, often with a lookup service that maps tenant IDs to shards.

Social networks and messaging systems shard by user ID to handle massive write loads and fan-out queries. Twitter's Manhattan, Facebook's TAO, and Discord's Cassandra clusters all shard user data and timelines. Consistent hashing is favored for its elastic scaling, as these systems must frequently add capacity to handle growth. The ability to add shards with minimal data movement is critical for maintaining availability during scaling events.

Financial systems and time-series databases often use range-based sharding by timestamp or account ID. InfluxDB, TimescaleDB, and many trading platforms partition time-series data into time-based shards, enabling efficient retention policies where old shards can be archived or dropped, and recent shards can be kept on faster storage. This also optimizes range queries for dashboards that query recent time windows.

Content delivery and metadata services, such as Amazon DynamoDB, Apache Cassandra, and Google Spanner, use sharding internally to distribute partitions across nodes. DynamoDB's partition key is hashed to determine the storage partition, while Spanner uses range-based sharding with automatic splitting and load-based rebalancing. These managed services hide much of the complexity from users but still require thoughtful partition key design to avoid throttling and hot partitions.

Comparison with Alternatives

Sharding is one of several scaling strategies, and it is often confused with or combined with other techniques. Choosing the right approach depends on data size, consistency requirements, query patterns, and operational expertise.

Vertical scaling is the simplest alternative: upgrade the existing server with more resources. It requires no application changes and preserves ACID transactions and joins, but it has hard limits and creates a single point of failure. Read replicas provide another alternative by copying data to multiple nodes to scale read throughput, but they do not increase write capacity or storage, and replication lag can cause stale reads.

Vertical partitioning splits a table by columns, placing different attributes on different nodes. This can be useful when some columns are large or infrequently accessed, but it does not solve the problem of a single table growing too large. Caching with systems like Redis or Memcached reduces database load by serving hot data from memory, but it is not a persistence solution and requires cache invalidation logic. Sharding is the only approach that scales both storage and write throughput linearly, but it does so at the cost of increased complexity for cross-shard operations.

In practice, most large systems combine multiple strategies. A typical architecture might use sharding for the primary dataset, read replicas for each shard to scale reads and provide failover, vertical partitioning to separate blob storage from metadata, and a caching layer in front for the hottest keys. Understanding the trade-offs allows architects to apply each technique where it is most effective rather than treating sharding as a silver bullet.

Common Mistakes and Best Practices

Sharding is notoriously difficult to retrofit, so avoiding common pitfalls during initial design is crucial. One of the most frequent mistakes is choosing a poor shard key. A low-cardinality key such as status with only a few distinct values, or a monotonically increasing key such as an auto-increment ID or timestamp, will create severe hot spots. All recent writes will target the last shard, overwhelming it while other shards sit idle. Best practice is to choose a high-cardinality, uniformly distributed key that appears in most queries, and to use a hashed or composite key if the natural key is ordered.

Another common error is ignoring the impact of scatter-gather queries. Developers may shard by user_id but then frequently run queries filtered only by email or status, forcing the system to broadcast to all shards. This not only increases latency but also multiplies load. The solution is to design the schema and query patterns around the shard key, create global secondary indexes where necessary, or maintain a separate lookup table that maps alternative keys to shard locations. Some systems also denormalize data to avoid cross-shard joins, storing redundant copies of frequently joined data on the same shard.

Underestimating the cost of rebalancing and not planning for it is a third major pitfall. Teams may assume that adding shards is instantaneous, only to discover that migrating terabytes of data takes hours or days and impacts live traffic. Best practices include using consistent hashing or fine-grained chunks to minimize movement, performing rebalancing during off-peak hours with throttling, and monitoring shard balance continuously. Implementing virtual nodes and dynamic chunk splitting from the start makes future scaling far smoother.

Additional best practices include: always shard with replication, never run a shard as a single point of failure; implement a robust shard router that handles failures and retries transparently; avoid cross-shard transactions where possible by co-locating related data, and when they are unavoidable, use two-phase commit or saga patterns with careful error handling; test failure scenarios including shard loss and network partitions; and instrument everything — track per-shard CPU, disk, query latency, and data distribution to detect skew early. Finally, consider whether you truly need sharding. For many applications, read replicas, caching, and vertical scaling are sufficient until data exceeds several hundred gigabytes or write throughput exceeds single-node limits. Premature sharding adds unnecessary complexity.

Interview Questions

1. What is the difference between hash-based sharding and consistent hashing, and when would you choose one over the other?

Hash-based sharding typically refers to naive modulo sharding where shard = hash(key) % N. It provides excellent balance and O(1) lookup but requires remapping nearly all keys when N changes, making elastic scaling very expensive. Consistent hashing maps both keys and nodes onto a ring and assigns each key to the next node clockwise, so adding or removing a node only moves K/N keys. You would choose naive hashing for static clusters where shard count rarely changes and simplicity is paramount. You would choose consistent hashing for dynamic, elastic environments where nodes are frequently added or removed, such as auto-scaling cloud deployments or peer-to-peer systems. Be prepared to discuss virtual nodes as an optimization for balance and to sketch the ring and remapping process.

2. How do you choose a good shard key? What makes a bad shard key?

A good shard key has high cardinality, uniform distribution, and aligns with query patterns. High cardinality ensures many distinct values to distribute evenly. Uniform distribution prevents hot spots. Query alignment ensures most queries include the shard key and can be routed to a single shard, avoiding scatter-gather. A bad shard key is low cardinality, such as gender or status, monotonically increasing such as timestamp or auto-increment ID, or rarely used in queries. An ideal answer would give examples: user_id is often good for user-centric workloads, while timestamp alone is bad due to hot spotting on the latest shard. Mention composite keys and hashed keys as solutions when the natural key is ordered or skewed.

3. What is a scatter-gather query and why is it a problem? How would you mitigate it?

A scatter-gather query is one that does not contain the shard key, so the router cannot determine the target shard and must broadcast the query to all shards, gather partial results, and merge them. This is problematic because it increases latency to the slowest shard, multiplies resource consumption by the number of shards, and limits scalability — the cost grows with cluster size. Mitigations include redesigning queries to include the shard key, creating global secondary indexes, maintaining a lookup service for alternative keys, denormalizing data to avoid cross-shard joins, and using caching for frequent scatter-gather queries. In an interview, emphasize that minimizing scatter-gather is a primary goal of shard key design.

4. Explain how you would handle a hot spot where one shard receives disproportionate traffic.

Frequently Asked Questions