Hashing and the Four Ways to Split

We picked the user ID as Chirp’s shard key. That works well when the shard key is a numeric ID, but what if your shard key is not numeric — for example, an email address or username? You can’t take chris@gmail.com and divide it by 4 to get a remainder. You need a deterministic rule that converts any arbitrary value into a number so you can pick a shard and ensure even distribution. That rule is a hash function. A hash function takes an input (like chris@gmail.com) and returns a reproducible digest (a sequence of bytes or a hex string). Convert that digest to an integer and take the remainder modulo the number of shards to get a shard index. Crucially, the hash must be deterministic: applying it to the same key always yields the same value so the user always maps to the same shard. Most languages provide well-tested hashing libraries. In Python, use hashlib (MD5, SHA-1, SHA-256, etc.) for deterministic hashing. Avoid Python’s built-in hash() for sharding because it is salted per interpreter process and will produce different values across restarts — unsuitable for persistent, cross-process routing.

Use deterministic hash functions (from hashlib) for sharding. Avoid Python’s built-in hash() for persistent or cross-process sharding because it is salted per interpreter process.

Example — compute a shard index by hashing a key and taking modulo the number of shards. This Python example uses MD5 to produce a reproducible integer:

import hashlib

def shard_for_key(key: str, num_shards: int) -> int:
    """
    Deterministic: use MD5 and convert its hex digest to an integer.
    Returns an integer in range 0..num_shards-1.
    """
    digest = hashlib.md5(key.encode("utf-8")).hexdigest()
    hash_int = int(digest, 16)
    return hash_int % num_shards

# Example usage
print(shard_for_key("chris@gmail.com", 4))  # -> e.g., 3
print(shard_for_key("leo@gmail.com", 4))    # -> e.g., 0

Notes on choosing a hash:

MD5 is fast and evenly distributes keys; collision resistance is usually not required for sharding.
If you need cryptographic guarantees, use SHA variants (e.g., SHA-256).
The important properties for sharding are determinism and a uniform distribution across shards.

Sharding-by-hash process (step-by-step)

Hash the shard key (e.g., user ID or email).
Convert the hash digest to a numeric value (e.g., int(hex_digest, 16)).
Compute numeric_hash % num_shards.
Use the remainder as the shard index (0..N-1).

A diagram showing a hash function (user_id → hash ÷ 4 → remainder) that maps user IDs to four database shards labeled 0–3. Each shard has a storage icon and a sample table of ID/email entries illustrating how records are distributed.

Hashing is only one approach. There are three other common sharding strategies — range sharding, directory sharding, and geographic sharding — each suited to different access patterns. Range sharding

Do not hash. Assign each shard a contiguous range of values.
Example: split by date into quarterly shards (Jan–Mar, Apr–Jun, Jul–Sep, Oct–Dec) if most queries request date ranges.
Pros: Range queries (e.g., “all my March transactions”) hit a single shard, making them efficient.
Cons: Writes tend to concentrate on the current range, producing write hotspots.

A dark-themed diagram illustrating range-based sharding of transaction data into four quarterly shards labeled Jan–Mar, Apr–Jun, Jul–Sep, and Oct–Dec. It shows a query flow from an app and example date/amount tables under each shard.

Directory sharding

Maintain a central lookup (directory) that maps each key (customer, group, etc.) to a shard ID.
Flexible: you can route very large customers to dedicated shards by updating the directory.
Pros: Manual control over placement, easy to isolate hot customers.
Cons: Every request must consult the directory; the directory becomes critical infrastructure and must be highly available and fast.

A diagram of a directory-based sharding system where an app looks up a table mapping customers (Acme, Birch, Cobalt, Globex) to shard IDs 0–3. Arrows route each customer to one of four database shards labeled Shard 0–3, with counts shown (Acme 50, Birch 50, Cobalt 50,000).

Geographic sharding

Place data by region (Europe, Asia, US) to reduce latency and meet residency requirements.
Often implemented as two-level routing: first route by region, then within the region use hashing or range sharding to spread load.
Pros: Lower latency and easier compliance with regional regulations.
Cons: Adds complexity to routing and cross-region queries.

An infographic titled "Which one to use?" showing four lookup/indexing options — Hash, Range, Directory (highlighted), and Geographic — with simple diagrams and short notes illustrating how each method maps keys to storage. The Directory panel is emphasized and shows numbered buckets pointing to a database.

Comparison table — which method to choose

Sharding Method	Best for	Pros	Cons
Hashing	Uniform key lookups (e.g., user profiles, posts)	Even distribution, simple routing, easy to compute on any machine	Not locality-aware; poor for range queries
Range sharding	Range queries (e.g., time-series, date ranges)	Good locality for range queries	Write hotspots for the active range
Directory sharding	Few large tenants or need manual placement	Precise placement, isolates large customers	Single point of failure; added lookup overhead
Geographic sharding	Latency or legal/residency requirements	Reduced latency, compliance-friendly	Complex routing and cross-region consistency

Which method should you use?

Range sharding: choose this when most queries are range-based (dates, numeric ranges).
Hashing: ideal when most queries are single-key lookups (user profiles, item lookups).
Directory sharding: useful when a small number of tenants are huge and must be placed manually.
Geographic sharding: use when latency or legal/regulatory requirements demand regional placement; commonly implemented as region-first, then hash within the region.

For Chirp: most traffic is “open this user’s profile” or “show this user’s posts.” There are no regional legal requirements. Hashing the user ID is therefore a good fit: it yields even distribution and simple routing. Now: something has to run the hashing rule and connect to the correct shard. Who should perform that routing? Where to run the routing logic

Application server: Common choice — the app computes the shard and opens a connection to the right database. Pros: low latency, simple. Cons: changes to shard topology require app deployments or a dynamic config mechanism.
Middleware / Router / Proxy: A routing layer (API gateway, DB proxy, or service mesh) can centralize routing logic and shard configuration. Pros: simpler operational changes, single place to update topology. Cons: adds another network hop and operational component.
Directory service: For directory sharding, a fast, highly available lookup service (cached aggressively) is required before the app can connect to the target shard.

Best practices

Keep the routing logic deterministic and stateless when possible so any machine can route requests locally.
Version your shard-mapping logic and provide a migration plan when changing shard counts (see consistent hashing or resharding patterns).
Cache directory lookups with TTLs to reduce lookup overhead and protect the directory from high traffic.

Links and references

Python hashlib docs: https://docs.python.org/3/library/hashlib.html
Database sharding (overview): https://en.wikipedia.org/wiki/Shard_(database)
MD5 (brief): https://en.wikipedia.org/wiki/MD5

In short: pick a shard key that matches your read/write patterns. For Chirp’s single-user lookups, hashing the user ID with a deterministic hash (via hashlib) gives even distribution and simple, local routing.

Why One Database Isn't Enough

Sharding Fundamentals

Shard Keys and Partitioning

Routing and Hot Shards

Resharding and Cross-Shard Queries

Sharding in Practice

Hashing and the Four Ways to Split

Watch Video