# DDIA Ch. 7: hashing the partition key turns a 1-shard range scan into a 16-shard fan-out

## Concept

Put 1,000,000 keys across 16 shards two ways, then run the *same* contiguous
range scan — the 1000 keys `[500000, 501000)` — against each. Under **key-range
sharding** (shard = a contiguous slice of the key space) those 1000 adjacent
keys all live in **one** shard, so the query hits **1 shard**. Under **hash
sharding** (shard = `md5(key) % 16`) the same 1000 keys are smeared across
**all 16 shards** — ~62 per shard — so the query must fan out to **every**
shard and reassemble the answer. Same query, same data: **1 shard vs 16**. That
fan-out is the price hash sharding pays for its even load. The controls pin the
boundary: a single-key **point** lookup touches exactly **1 shard under both**
schemes, and a **composite key** (`sensor#ts`, hashed by the sensor prefix
only) keeps a range over `ts` within one sensor on **1 shard** even under
hashing.

## Provenance

*Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini,
2025), Chapter 7 — *Sharding*, §"Sharding by hash range" and the chapter
Summary:

> [Hashing the key to determine its partition] destroys the ordering of keys,
> making range queries inefficient.

The book contrasts key-range sharding (good for range scans, prone to hot
spots) with hash sharding (even load, but you lose efficient range queries).
Here you measure exactly *how* inefficient: the number of shards the identical
range query has to touch under each scheme.

## Prerequisites

The surprise is entirely about *adjacency* — whether keys that are neighbors in
key order are also neighbors in shard placement. These help; each line notes
where it shows up.

1. **A hash function is designed to destroy ordering** — a good hash sends
   nearby inputs (`500000`, `500001`) to unrelated outputs, so any structure in
   the key space is gone after hashing. It shows up as the 1000 adjacent keys
   landing on all 16 shards.
2. **Range queries vs. point queries** — a point query names one key; a range
   query asks for every key in an interval (`WHERE k BETWEEN lo AND hi`, a time
   range, a scan). Only the range query cares where *neighbors* live. It shows
   up as the point control touching 1 shard under both schemes while the range
   splits 1 vs 16.
3. **Composite / concatenated keys** — a key `(partition_key, sort_key)` where
   the system hashes only the *first* component and keeps the rest sorted within
   it (Cassandra's partition key + clustering columns, DynamoDB's partition key
   + sort key). It shows up as the `sensor#ts` redemption: hashing the sensor
   keeps one sensor's readings together and sorted by `ts`.

### Where to learn the prerequisites

- **Hash functions destroy ordering (#1):** DDIA §"Sharding by hash range"; and
  any explanation of a good hash's *avalanche* property (Wikipedia, "Avalanche
  effect") — one-bit input change flips ~half the output bits, which is exactly
  why `500000` and `500001` land nowhere near each other.
- **Composite keys (#3):** DDIA §"Sharding by hash range" (the concatenated-index
  paragraph); Cassandra's docs on partition keys vs. clustering columns
  (datastax.com, "The partition key") for the real-world shape of the escape
  hatch.

If only one is new, make it #1 — "the hash intentionally throws away adjacency"
is the whole mechanism; everything else follows from it.

## Environment

Deterministic, so the shard counts reproduce exactly:

- macOS 26.5.2 (Darwin 25.5.0), arm64
- Python 3.15.0a8, standard library only — no Docker, no deps
- Placement decided by `md5`, never Python's per-process randomized `hash()`, so
  the numbers are byte-for-byte stable every run
- Fixed layout: 1,000,000 keys (`000000`..`999999`), 16 shards; range query is
  the 1000 keys `[500000, 501000)`

## Mental model

Same keys, same 16 shards, same range query — only the placement rule differs.

- **Key-range sharding** — `shard = key // 62500`. Shard 0 owns keys
  `0..62499`, shard 1 owns `62500..124999`, and so on: each shard is a
  *contiguous slice* of the key space. Adjacent keys share a shard, so a range
  scan is a slice of one (or, if it straddles a boundary, two) shards. The cost
  is hot spots — sequential keys (timestamps, auto-increment ids) all pile onto
  the newest shard.
- **Hash sharding** — `shard = md5(key) % 16`. The hash scatters keys uniformly,
  so load is even and there are no sequential hot spots. But adjacency is gone:
  `500000` and `500001` hash to unrelated shards, so a range of adjacent keys is
  spread across every shard and a range query must ask all of them.

Both are the same two-line function over the same key set; the exercise runs the
identical range, point, and composite queries against each. The whole thing is
one script, `code/hash_kills_range_queries.py`.

## Setup

```
cd study/ddia/ch07
python3 code/hash_kills_range_queries.py
```

Do **not** read the output yet — make each prediction first.

## Steps

### Step 1 — the range query: 1 shard or 16?

**Predict.** You scan the 1000 consecutive keys `[500000, 501000)`. Under
key-range sharding, how many of the 16 shards hold at least one matching key?
Under hash sharding, how many? (And roughly how many of the 1000 keys land on
each shard it does touch?)

**Observe.**

```
RANGE QUERY -- scan the 1,000 consecutive keys [500000, 501000):

  key-range sharding:
    shards touched : 1   -> [8]
    the whole range lives in shard 8 (keys 500000..562499); query hits 1 shard.

  hash sharding:
    shards touched : 16  -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
    the 1,000 keys spread 52-72 per shard (~62.5 each); query must fan out to ALL 16 shards.

  SAME query, SAME data: 1 shard vs 16 shards.
```

**1 vs 16.** Under key-range the 1000 keys are a slice of shard 8's contiguous
range `500000..562499`, so one shard answers the whole query. Under hashing the
same 1000 keys are scattered — 52 to 72 per shard, ~62.5 on average — so *every*
shard holds some, and the query has to fan out to all 16 and merge the results.

### Step 2 — the point query control

**Predict.** Now look up a *single* key, `500000`. How many shards does that
touch under key-range sharding? Under hash sharding? Is hashing bad here too?

**Observe.**

```
POINT QUERY -- look up the single key 500000:
    key-range sharding : shard 8   (1 shard)
    hash sharding      : shard 8   (1 shard)
    both touch exactly 1 shard -- hashing is only bad for RANGES.
```

**1 shard under both.** A single key hashes to a single shard, so a point lookup
is a direct hit either way. Hashing costs you nothing here — the penalty in
Step 1 is specific to *ranges*, which is exactly the query that depends on
neighbors sharing a shard. (That both landed on shard 8 is a coincidence of this
one key; what matters is each scheme touches exactly one.)

### Step 3 — the composite-key escape

**Predict.** Keys are now `f"{sensor}#{ts}"`, and the system hashes **only the
sensor prefix** to pick a shard (`ts` is the sort key *within* a sensor). You
range over `ts in [1000, 2000)` for one sensor, `sensor-0042` — 1000 readings.
Under hashing, how many shards does *this* range touch?

**Observe.**

```
COMPOSITE KEY -- key = f"{sensor}#{ts}", hashed by sensor prefix only:
    range over ts in [1000, 2000) for 'sensor-0042' (1,000 readings)
    shards touched : 1   -> [6]
    all readings share the sensor prefix -> one hash -> shard 6; range stays on 1 shard even under hashing.
```

**1 shard — the range came back.** Every reading shares the same `sensor-0042`
prefix, so they all hash to the *same* shard (6) and stay sorted by `ts` within
it. Hashing only the partition key buys even load *across* sensors while keeping
each sensor's time-range scan local. The catch: the range must be *within one
partition key* — a range over `ts` across *all* sensors is scattered again.

## What you should see

- The range query `[500000, 501000)` touches **1 shard** under key-range
  sharding and **all 16 shards** under hash sharding.
- Under hashing, the 1000 keys spread **52–72 per shard** (~62.5 each) — every
  shard gets some.
- The point lookup of key `500000` touches exactly **1 shard under both**
  schemes.
- The composite-key range (`ts in [1000, 2000)` for one sensor) touches **1
  shard** even under hashing.

## Why

A range query asks for keys that are *adjacent in key order* — every key in an
interval. Whether that query is cheap or expensive comes down to a single
question: are keys that are neighbors in key order also neighbors in shard
placement?

Key-range sharding answers yes by construction. `shard = key // 62500` is
monotonic: it maps a contiguous block of keys to one shard, so the keys
`500000..500999` — being inside the block `500000..562499` — are all shard 8.
The answer to a range query is a slice of one shard (two only if the interval
happens to straddle a shard boundary). Adjacency in the key space *is*
adjacency in placement.

Hashing answers no *on purpose*. A good hash function has the avalanche
property — flip one bit of the input and about half the output bits flip — so
`md5("500000")` and `md5("500001")` are unrelated 128-bit numbers, and `% 16`
sends them to independent shards. That scattering is the whole point: it spreads
sequential keys evenly and kills the hot spots key-range sharding suffers. But
it destroys adjacency, so a range of adjacent keys becomes a set of unrelated
hashes with no locality. With 1000 keys and 16 shards, each key is placed
independently and roughly uniformly, so the expected count per shard is
1000 / 16 ≈ 62.5, and the chance a given shard gets *zero* of the 1000 is about
`(15/16)^1000 ≈ e^(−1000/16) = e^(−62.5)` — astronomically small. So essentially
*every* shard holds some matching key, and the query must fan out to all 16 and
merge. The book's one line — "range queries are inefficient" — is this fan-out.

**The boundary — the penalty is specific to range scans over the hashed
column.** A point lookup names one key, which hashes to one shard, so hashing
costs nothing (Step 2). And a *composite* key escapes: hash only the partition
key and keep a sort key ordered within it, and a range over the sort key *within
one partition key* shares a single hash and stays on one shard (Step 3) — this is
exactly Cassandra's partition-key + clustering-columns and DynamoDB's
partition-key + sort-key. What you *cannot* get back is an efficient range over
the *hashed* dimension itself (a range across all sensors, or over a hashed
primary key); that scan is scattered and there is no merge-free way to run it.
Choosing hash sharding is choosing to give up cheap range scans on the shard key
in exchange for even load — and the composite key tells you which range you're
allowed to keep.

### Go deeper

1. **Shrink the range, watch the fan-out shrink.** Re-run with a 10-key range
   instead of 1000. Predict how many of the 16 shards hash sharding touches now
   (with 10 keys, expect noticeably fewer than 16 — about `16 * (1 − (15/16)^10)
   ≈ 8` distinct shards, since collisions are no longer negligible), and confirm
   key-range still touches 1.
2. **Straddle a boundary.** Move the range to `[499990, 500010)`, which crosses
   the shard-7/shard-8 line at 500000 (`437500..499999` is shard 7). Predict
   key-range now touches 2 shards — the one case it isn't 1 — while hash sharding
   is unmoved at 16.
3. **Break the composite escape.** Range over `ts in [1000, 2000)` across *all*
   100 sensors instead of one. Predict the shard count jumps back toward 16,
   because now the keys differ in their *partition* component — the escape only
   holds *within* a single partition key.