> ## Documentation Index
> Fetch the complete documentation index at: https://notes.kodekloud.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Hashing and the Four Ways to Split

> Describes deterministic hashing for shard routing and compares four sharding strategies with routing guidance and best practices for even distribution and scalable database design.

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:

```python theme={null}
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)

1. Hash the shard key (e.g., user ID or email).
2. Convert the hash digest to a numeric value (e.g., `int(hex_digest, 16)`).
3. Compute `numeric_hash % num_shards`.
4. 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.](https://mintcdn.com/kodekloud-c4ac6d9a/U9fTv2NKZBAqmNMH/images/System-Design-Database-Sharding/Shard-Keys-and-Partitioning/Hashing-and-the-Four-Ways-to-Split/user-id-hash-modulo4-shards.jpg?fit=max\&auto=format\&n=U9fTv2NKZBAqmNMH\&q=85\&s=f9a30e862dfa759738ffafad697ddc67)

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.](https://mintcdn.com/kodekloud-c4ac6d9a/U9fTv2NKZBAqmNMH/images/System-Design-Database-Sharding/Shard-Keys-and-Partitioning/Hashing-and-the-Four-Ways-to-Split/range-sharding-transactions-quarterly-diagram.jpg?fit=max\&auto=format\&n=U9fTv2NKZBAqmNMH\&q=85\&s=662a45ad2cdb131cfca46a93604d2a49)

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).](https://mintcdn.com/kodekloud-c4ac6d9a/U9fTv2NKZBAqmNMH/images/System-Design-Database-Sharding/Shard-Keys-and-Partitioning/Hashing-and-the-Four-Ways-to-Split/directory-sharding-customer-shard-map.jpg?fit=max\&auto=format\&n=U9fTv2NKZBAqmNMH\&q=85\&s=f5961bb77d38ceea7de941458748e556)

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.](https://mintcdn.com/kodekloud-c4ac6d9a/U9fTv2NKZBAqmNMH/images/System-Design-Database-Sharding/Shard-Keys-and-Partitioning/Hashing-and-the-Four-Ways-to-Split/indexing-methods-hash-range-directory-geographic.jpg?fit=max\&auto=format\&n=U9fTv2NKZBAqmNMH\&q=85\&s=73de0f219fffd4d9901fb1cd131fe307)

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](https://docs.python.org/3/library/hashlib.html)
* Database sharding (overview): [https://en.wikipedia.org/wiki/Shard\_(database)](https://en.wikipedia.org/wiki/Shard_\(database\))
* MD5 (brief): [https://en.wikipedia.org/wiki/MD5](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.

> **[Watch Video](https://learn.kodekloud.com/user/courses/database-sharding/module/9c52f7ec-c4dc-4255-93b4-0467d4713ae6/lesson/25e727b2-4517-41f6-a3c9-2ca56451bb58)**


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.