Sharding Strategies

How data is sharded determines the query routing strategy, load distribution uniformity, and the volume of data migration during scaling. Range sharding is friendly to range queries but prone to hotspots; hash sharding distributes data evenly but requires fan-out for range queries—there is no silver bullet, only choices tailored to access patterns.

Range Sharding

Shards are assigned based on the alphabetical/numeric intervals of the key. Similar to encyclopedia volumes: A-D → shard 1, E-H → shard 2, ...

Advantages:

Efficient Range Scans: A query like WHERE key BETWEEN 'a' AND 'c' only needs to access a single shard.
Sequential Writes: The most recent keys are written to the same shard → sequential I/O.

Disadvantages:

Hotspots: If certain key ranges are frequently accessed (e.g., recent timestamps), that shard becomes a bottleneck.
Uneven Distribution: Data distribution may be skewed (some alphabetic ranges may contain more data).

Applications: HBase, Bigtable, MongoDB range sharding.

Hash Sharding

shard = hash(key) % N — evenly distributed across all shards.

Advantages: Load balancing, no hotspots (assuming uniform key distribution). Disadvantage: Loss of Range Scan — consecutive keys are scattered across all shards → range queries require scatter-gather to all shards.

Applications: Cassandra (Murmur3), DynamoDB (MD5). Cassandra's partition key is hash(key), but it supports clustering columns to perform range scans within the same partition.

Rebalancing

Data redistribution when the number of nodes changes:

Fixed Number of Shards: A fixed number of shards (e.g., 1000) are allocated at creation time, with each node hosting multiple shards. Adding a node → migrate some shards from existing nodes to the new node. Advantages: Simple, balances migration costs evenly. Disadvantages: Difficult to change the number of shards once set (if data volume grows far beyond 1000 shards).

Dynamic Sharding: Shards are allowed to split (when data volume exceeds a threshold) and merge (when data volume falls below a threshold). Adapts to data volume growth, but has performance impacts during splits.

Hot Spot Mitigation

A specific key is accessed at a very high frequency → the shard containing it becomes a bottleneck. Mitigation strategies:

Key Salting: key = original_key + random_salt → distributed to different shards. Reads from all salt variants and aggregate results.
Caching: Hot keys are cached at the application layer (Redis/Memcached).
Partition-aware Client: The client knows which shard holds the hot key → connects directly to that shard instead of going through a middleware layer → saves one hop.

Secondary Indexes on Sharded Data

Global secondary index (DynamoDB):
  The index is independent of the main table's sharding → can have its own partition key.
  Write: Main table write + asynchronous index update (may result in temporary inconsistency).
  Read: The index directly points to the target shard.

Local secondary index (Cassandra):
  The index resides in the same partition as the main table.
  Write: Atomic (within the same partition, no cross-partition transaction needed).
  Read: Must specify the partition key → can only scan a single partition.

References

Cassandra: cassandra.apache.org/doc/stable/cassandra/architecture/dynamo.html
DynamoDB: docs.aws.amazon.com/amazondynamodb/latest/developerguide/HowItWorks.Partitions.html

Keywords: range partitioning, hash partitioning, rebalancing, hot spot, key salting, secondary index, Cassandra, DynamoDB