Sharding

Range sharding preserves order, so range scans (WHERE k BETWEEN ...) read from a small contiguous set of shards. The challenge: monotonic key insertion (timestamps, auto-increment IDs) creates a hotspot at the rightmost shard.

# CockroachDB: every range is a 512 MB chunk of the sorted keyspace
# When a range exceeds 512 MB, it splits at the midpoint
# When two adjacent ranges are both small, they may merge

# Hot range mitigation:
#   - Hash a prefix into the key (loses some range-scan locality)
#   - Use UUIDs or random prefixes for high-write tables
#   - Manual SPLIT AT for known hot patterns

# CockroachDB range descriptor (simplified):
RangeDescriptor {
    StartKey: "user/A",
    EndKey:   "user/F",
    Replicas: ["node1", "node2", "node3"],   // Raft group
}

Used by: CockroachDB, TiDB/TiKV, HBase, Bigtable, Spanner.

# Simple hash sharding (the "modulo" approach)
shard_id = hash(key) % num_shards

# Problem: adding a shard reshuffles ~all keys
# (every key whose hash%new_count != hash%old_count moves)

# Solution: CONSISTENT HASHING
# Map both keys and shards onto a ring (0 to 2^32-1)
# Each key belongs to the next shard clockwise on the ring
#
# Adding a shard only moves the keys that fall between
# the new shard's position and the previous one
#
# Removing a shard reassigns its keys to the next clockwise shard

Pure consistent hashing has uneven load (some arcs are bigger than others). The fix is virtual nodes: each physical node owns 100–500 positions on the ring. Average over many positions → uniform load.

Used by: DynamoDB, Cassandra, Riak, Memcached. Excellent for KV workloads with point lookups; bad for range scans (a contiguous key range maps to random shards).

Place each shard in the region closest to its users. The key contains a region prefix (or table-level region annotation):

# CockroachDB regional-by-row: each row stamped with crdb_region
CREATE TABLE users (
  id UUID PRIMARY KEY,
  email STRING,
  crdb_region crdb_internal_region NOT VISIBLE NOT NULL
    DEFAULT default_to_database_primary_region(gateway_region())
) LOCALITY REGIONAL BY ROW;

# Now each row's leaseholder lives in its crdb_region.
# Reads from the same region are local (~5 ms).
# Cross-region reads cost a WAN round-trip (~80 ms).

Spanner pioneered this with placement directives. CockroachDB exposes it as LOCALITY REGIONAL BY ROW. The hard part: cross-region updates and consistency. Spanner uses TrueTime + 2PC across regions; CockroachDB uses bounded staleness reads to avoid the WAN cost.

Horizontal partitioning = sharding (split rows). Vertical partitioning = split columns into separate tables (or even separate databases). Vertical is sometimes useful when one column is huge or accessed differently:

# Vertical partition: separate hot and cold columns
users_main:    (id, email, name, last_login)            -- read often
users_profile: (id, bio, avatar_url, preferences_json)  -- read on profile
users_audit:   (id, login_history, action_log)          -- write-heavy

# Joins across vertical partitions cost extra. Use only when:
#   - One column dominates row size
#   - Different access patterns benefit from different physical layout
#   - Different durability requirements (hot=SSD, cold=S3)

Modern OLTP databases rarely need explicit vertical partitioning — column store engines (Parquet, ORC) and TOAST (PostgreSQL) handle the same need without breaking the schema.

A query that touches multiple shards needs scatter-gather:

SELECT count(*) FROM orders WHERE created_at > '2026-01-01';

-- If "orders" is hash-sharded by order_id:
--   1. Send query to ALL N shards (scatter)
--   2. Each shard returns its count
--   3. Coordinator sums (gather)
-- Latency = max(per-shard latency); cost = N * per-shard cost.

-- If range-sharded by created_at:
--   1. Coordinator reads only the shards in range
--   2. Latency = O(matching shards)

This is why range sharding wins for time-series and log workloads, even with the hotspot risk. Hash sharding is great for "look up user by id" but kills "show me yesterday's signups."

Modern distributed databases (CockroachDB, TiDB, Vitess) push predicates down to each shard so the coordinator only assembles the final result. They also use distributed SQL planners that decide whether to broadcast a small table to all shards or pull all data to one node for a join.

If a transaction touches multiple shards, you need coordination. Two-phase commit (2PC) is the textbook answer; modern systems wrap it with timestamp-ordered concurrency control:

The cost: cross-shard transactions take 2-3× the latency of single-shard ones. Most schemas are designed to keep transactions on a single shard via colocation (e.g., putting all rows for one user on the same shard).

Adding capacity without downtime. The basic flow:

• Provision new shard(s) with empty state.
• Pick rows to move — split a range or rehash a region.
• Copy and apply ongoing changes — bulk copy + tail the change log.
• Cut over atomically — flip the routing layer in one consistent step (commit a metadata change via consensus).

CockroachDB does this transparently via range splits and rebalancing. Vitess does it via VReplication — a tail-copy of the source binlog into the destination shard, with a final cutover when caught up. TiDB uses PD (Placement Driver) to schedule region splits and rebalancing.

The most common production failure mode: one key (or one range of keys) gets disproportionate traffic. Justin Bieber tweets, the World Cup, a viral video — these create skewed access patterns that any shard map cannot handle naturally.

# Strategies for hot keys:
# 1. Caching layer in front (Redis, CDN)
#    - Reads: easy
#    - Writes: hard (cache invalidation)
#
# 2. Read replicas for the hot shard
#    - Add multiple followers, scatter reads
#    - Stale reads acceptable
#
# 3. Sub-sharding the hot key
#    - Split "celebrity_user/posts" into "celebrity_user/posts_shard_N"
#    - Application aggregates on read
#
# 4. Last-write-wins with reduced consistency
#    - Convert to AP, accept eventual consistency for the hot data

The celebrity problem is one reason Twitter/X invested heavily in fanout-on-write architectures. CockroachDB has built-in load-based splitting — a range exceeding QPS threshold gets split even if it's small.

Every sharded system needs a routing component that maps a query to its target shard(s). Three architectures:

• Smart client: client library knows the shard map, routes directly to the right shard. Saves a hop but couples clients to topology. Used by Cassandra (token-aware drivers), MongoDB (mongos optional), Redis Cluster.
• Proxy layer: a stateless proxy sits between clients and shards. Easier to deploy and version, costs an extra RTT. Used by Vitess (vtgate), Envoy, Twemproxy.
• Built into the database: the database itself is distributed. Any node can accept any query and route internally. CockroachDB and TiDB work this way.

The shard map (which shard owns which keys) is stored in metadata that itself must be highly available. CockroachDB stores it in a top-level Raft group; Vitess uses a dedicated topology service (etcd or ZooKeeper); MongoDB uses a config server replica set.

You're building a chat application. Schema: users, conversations, messages. How to shard?

# Most queries: "fetch all messages in conversation C"
# So: shard messages by conversation_id
#
# users: hash by user_id (point lookups, even load)
# conversations: hash by conversation_id
# messages: hash by conversation_id (colocated with conversation)
#
# Query "all messages from user X across all conversations":
#   Two-step: first GET conversations WHERE participant=X
#             then SCATTER GET messages WHERE conversation IN (...)
#
# Cross-shard transactions only when:
#   - User joins/leaves a conversation (rare)
#   - Conversation moved or merged (very rare)
# Otherwise: all reads/writes on a single conversation are single-shard.

The general pattern: pick a "tenant" or "aggregate root" (user, conversation, account, customer) and colocate all that aggregate's data on one shard. 90%+ of operations stay single-shard. This is what every production system does, even ones that nominally support cross-shard transactions.