Sharding strategies: routing, skew and migration

Sharding partitions one logical data set across independently owned ranges or buckets. It can increase aggregate capacity and reduce per-node data size, but it introduces routing metadata, cross-shard operations, rebalancing and new failure modes. Replication is a separate concern inside each shard.

Range partitioning

A versioned map assigns ordered key intervals to shards. Point lookups route directly. Range queries are efficient when the requested interval is narrow and aligned, but a query that crosses boundaries must fan out to every overlapping shard and merge ordered results. Time-series range keys often need a second dimension or buckets to prevent the newest range from becoming one write hotspot.

Hash partitioning

A deterministic hash maps a partition key to a token or bucket. This can spread many independent keys when the hash input has enough entropy. It does not spread traffic for one hot key, and a poor partition key can still concentrate one tenant or time window.

Modulo by the current node count remaps most keys when the count changes. Consistent-hashing families or rendezvous/jump hashing reduce movement under their stated assumptions, but production placement also needs weights, failure domains, virtual partitions, replication and a durable map version. The chosen algorithm is not a substitute for measuring size and traffic skew.

Choosing a key

The partition key must serve dominant access patterns and correctness boundaries. Ask:

• Which operations need one-shard atomicity or ordering?
• Can a tenant or key grow without bound?
• Which queries fan out, and what is their worst-case shard count?
• How are secondary indexes and uniqueness enforced?
• Can a hot aggregate be decomposed and merged without losing semantics?

Cross-shard transactions and globally unique constraints require coordination. Denormalization may avoid fan-out, but every derived copy then needs an idempotent update and repair path.

Online resharding

A safe migration has an epoch and explicit states:

1. acquire one migration owner;
2. copy a snapshot and record its change position;
3. replay later changes idempotently;
4. verify counts, checksums and high-water marks;
5. atomically publish a new partition-map version;
6. keep redirects or compatible dual routing until stale clients expire;
7. retire old data only after rollback and audit windows.

Blind dual writes can diverge on partial failure. Prefer one authoritative log/change stream or versioned idempotent writes, and define which owner answers reads during every state.

Scenarios

A range crosses two explicit partitions and is merged with a continuation token.

One key is routed by a stable token and map version.

Hashing spreads keys, not traffic within one key.

Snapshot, catch-up, verification and atomic map publication.

A stale router refreshes metadata and retries with the same operation id.

Operations

Monitor bytes, rows, read/write QPS, CPU, storage latency and tail latency per shard and per partition key. Alert on skew before the largest shard is full. Keep migration bandwidth below measured headroom, throttle catch-up, and exercise abort/rollback. Backups must be restorable to a mutually consistent point across routing metadata and shard data.

Primary sources

• DeCandia et al., Dynamo, consistent hashing and preference lists: https://web.stanford.edu/class/cs244/papers/amazon-dynamo-sosp2007.pdf
• Lamping and Veach, A Fast, Minimal Memory, Consistent Hash Algorithm: https://arxiv.org/abs/1406.2294