Range-Based Sharding vs Hash-Based Sharding

When designing a sharded distributed database, the storage engine must decide how keys are partitioned across the cluster.

There are two primary partitioning paradigms:

1. Range-Based Sharding (Used by Google Spanner, CockroachDB, TiDB, HBase).
2. Hash-Based Sharding (Used by Apache Cassandra, Amazon DynamoDB, MongoDB, Redis Cluster).

Choosing between these two approaches dictates how efficiently your cluster can execute Range Scans versus how resilient it is to Write Hotspots.

---

1. Range-Based Sharding Internals

In Range-Based Sharding, keys are sorted lexicographically, and the continuous key space is sliced into contiguous ranges (often called Ranges, Tablets, or Splits):

Dynamic Range Splitting and Merging:

• When a range grows beyond a threshold (e.g. $64\text{MB}$ in CockroachDB or $4\text{GB}$ in Spanner), the storage engine automatically splits the range in half at the median key.
• A cluster coordinator (or Raft range leader) updates the routing metadata table.

The Superpower of Range Sharding: Fast Range Scans

• Because adjacent keys reside on the same physical node, scanning a range (SELECT * FROM logs WHERE timestamp BETWEEN '2026-01-01' AND '2026-01-31') is a single-node sequential disk read!

The Fatal Flaw: The Monotonic Insert Bottleneck

If your primary key is an auto-incrementing integer (1, 2, 3, 4, ...) or a timestamp (2026-09-01T12:00:00Z):

• All new writes fall into the highest key range ($[\text{last\_key}\cdots +\infty ]$).
• 100% of all write traffic hits a single physical node, completely neutralizing the benefits of having a 100-node cluster!

---

2. Hash-Based Sharding Internals

In Hash-Based Sharding, a cryptographic or non-cryptographic hashing algorithm (such as MurmurHash3, xxHash, or MD5) is applied to the shard key before routing:

$\text{Target Shard}=\text{Murmur3}(\text{key})(\mathrm{mod}\text{Total Shards})$

The Superpower of Hash Sharding: Hotspot Immunity

• Consecutive keys (user_1, user_2, user_3) are scattered uniformly across completely different physical machines.
• Monotonically increasing IDs never overload a single node.

The Fatal Flaw: Destruction of Key Ordering

• Keys that are logically adjacent in your application domain are physically scattered across opposite ends of the datacenter.
• Range queries (WHERE id BETWEEN 1 AND 1000) cannot be localized; they must fan out as a cluster-wide scatter-gather to every single shard.

---

3. The Hybrid Approach: Compound Partition Keys

How do modern distributed databases (such as Apache Cassandra and Amazon DynamoDB) achieve both uniform write scaling AND efficient localized range scans?

They use Compound Partition Keys (Partition Key + Clustering Key):

---

4. Architectural Comparison Matrix

---

5. Production Failure Postmortem: The Auto-Increment Range Shard Collapse

Incident Overview:

In 2021, an enterprise order processing system migrated from a monolithic MySQL database to a distributed range-partitioned SQL database to handle Black Friday traffic. The cluster crashed within 10 minutes of go-live.

What Happened:

1. The engineering team retained their existing MySQL auto-incrementing BIGINT primary key schema: CREATE TABLE orders (id BIGSERIAL PRIMARY KEY, ...).
2. The database range-sharded rows across 32 nodes: Range 1 (1..100,000), Range 2 (100,001..200,000), etc.
3. During peak checkout (30,000 orders/sec), every single new write targeted the highest ID range on Node 32.
4. Node 32's CPU and disk queue hit 100% capacity, while Nodes 1 through 31 sat completely idle at 1% CPU utilization.

Remediation:

• Switched the primary key from auto-increment integers to UUIDv4 (Random Hash) to distribute write throughput across all 32 nodes uniformly.
• For time-ordered queries, created a separate secondary index or used prefix-salted keys (date_bucket:uuid).

---

6. Chapter Summary & Sharding Strategy Rules