skip to content

Ten thousand session keys hash across 96 shards; what can you assert about the busiest shard without measuring?

level: middleimportance: should knowfreq 50%

answer

  1. the mean is a floor, not a fact
  2. something always beats the average
  3. round up, never down
  4. ceil of n over m in one box
  5. no placement escapes the ceiling

basics

~20 s

Some shard holds at least ceil(10000/96) = 105 keys. The generalized pigeonhole principle says that with n items in m boxes, one box always holds at least ceil(n/m), whatever the distribution turns out to be.

solid answer

~40 s

The generalized form of the pigeonhole principle gives a floor under the maximum: with n items in m boxes, some box holds at least `ceil(n/m)`. Here that is `ceil(10000/96) = 105`. The reasoning is a one-line contradiction — if every shard held 104 or fewer, the 96 shards together would account for at most `96 x 104 = 9,984` keys, and 10,000 were placed. It is an averaging argument in disguise: the mean load is about 104.17, and no finite set of numbers can lie entirely below its own mean, so integer counts round that up to 105. The bound holds for every assignment, so it needs no measurement, no assumption of even spread and no property of the hash function. It is a floor on the busiest shard, not an estimate of it.

go deeper

for a junior

Remember the formula and the rounding direction: n items in m boxes force some box to hold at least the ceiling of n divided by m. Compute it and say that it holds no matter how the items are placed.

for a middle

Explain the contradiction that proves it — every box at the floor value cannot account for the total — and connect it to the averaging statement that something must sit at or above the mean.

for a senior

Use it as a feasibility gate on capacity plans: compare the per-shard limit against the floor before discussing placement, and be clear that the real maximum usually sits well above it.

for a principal

Treat it as the cheapest available argument against a design assumption. It is distribution-free and needs no measurement, so it can kill an unworkable partitioning scheme at design time rather than after a load test.

## The generalized principle The basic pigeonhole statement is that n items in m boxes with n greater than m force some box to hold two. The **generalized form** sharpens it into a quantity: with n items in m boxes, - some box holds **at least `ceil(n/m)`** items, and - some box holds **at most `floor(n/m)`** items. Both halves are proved the same way, by contradiction against the total. For the shard question, n = 10,000 keys and m = 96 shards: 1. Suppose every shard holds at most 104 keys. 2. Then the 96 shards together hold at most `96 x 104 = 9,984` keys. 3. But 10,000 keys were placed, and 10,000 is greater than 9,984. 4. The supposition fails, so **some shard holds 105 or more**. And `ceil(10000/96) = 105`, since 10,000 divided by 96 is about 104.17. The downward half runs identically: if every shard held 105 or more the total would be at least `96 x 105 = 10,080`, more than were placed, so some shard holds at most 104. ## Why this is an averaging argument The mean load is `10000 / 96 = 104.17` keys per shard. A finite collection of numbers cannot all sit strictly below its own mean — if they did, their sum would be below the mean times the count, which is the total, a contradiction. So some shard is at or above the mean. Because loads are whole keys, at or above 104.17 means at least 105. **The ceiling is not a rounding convention; it is where the integrality of the counts bites.** This is why the bound survives any amount of skew. Skew moves load around, but it cannot lower the total, and the total is the only input the argument uses besides the box count. ## What the bound is, and what it is not | Statement about the busiest shard | Does it follow? | |---|---| | Some shard holds at least ceil(n/m) | Yes, for every possible assignment | | Some shard holds at most floor(n/m) | Yes, the symmetric half of the same argument | | The busiest shard is roughly ceil(n/m) | No — that is an estimate, and the real maximum is usually higher | | A better hash function lowers the floor | No — the floor uses only the two counts | | Enough shards eventually give one key per shard | Only once m reaches n; below that the floor stays above 1 | The third row is the one that misleads in practice. `ceil(n/m)` is a **guarantee about the worst case that cannot be beaten**, not a description of the typical maximum. How far above the floor the busiest shard usually sits is a question about likely behaviour under a spreading function, and it is answered by probability rather than by counting. The counting bound is deliberately weak and correspondingly unconditional. ## A few values to keep the shape in mind | Items n | Boxes m | Forced minimum for the busiest box | |---|---|---| | 10,000 | 96 | 105 | | 10,000 | 10 | 1,000 | | 1,000 | 7 | 143 | | 100 | 12 | 9 | | 1,000,000 | 1,024 | 977 | Every row is `ceil(n/m)`, and each can be checked the same way: `7 x 142 = 994 < 1,000`, so 143 is forced; `12 x 8 = 96 < 100`, so 9 is forced. ## Where it earns its place at work - **It is a capacity floor.** A per-shard budget below `ceil(n/m)` cannot be met by any placement, so a plan that sets one is already wrong before a single measurement is taken. - **It refutes even-spread assumptions cheaply.** If a design needs the maximum shard to stay under some limit, compare that limit with the floor first; if the floor already breaches it, no hashing, rebalancing or reshuffling will help. - **Adding shards has diminishing returns.** The floor falls as `1/m`, so doubling shard count halves it and nothing more. - **It needs no data.** Because the bound is distribution-free, it applies at design time to a workload nobody has run yet, which is precisely when the decision is made. - **The lower half matters too.** Some shard holds at most `floor(n/m)`, which is the argument behind claims that some partition will be under-used whenever the counts do not divide evenly. The discipline the principle enforces is small but real: when someone asserts a per-box limit, compute `ceil(n/m)` before arguing about the placement strategy, because that number settles whether the limit is reachable at all.

  • What is the symmetric statement about the least loaded shard, and how is it proved?
    Some shard holds at most floor(n/m), by the same argument run downward: if every shard held floor(n/m) + 1 or more, the total would exceed n. For 10,000 keys over 96 shards that is at most 104 in some shard, since 96 x 105 = 10,080 is more than were placed.
  • Would a better hash function or a rebalancing pass lower the ceil(n/m) floor?
    No. The floor follows from the item count and the box count alone, so no placement strategy beats it. The only ways down are fewer keys or more shards, and more shards help only as 1/m. What a good spread does is keep the real maximum close to the floor instead of far above it.
  • If the real maximum is usually higher than ceil(n/m), what is the bound good for?
    It is the one statement that needs no data and admits no exceptions, so it settles feasibility. If the per-shard limit in a design is already below ceil(n/m), the design fails for every workload and every hash function, and that verdict is available before anything is built or measured.

saying these in an interview costs you the question

  • Answers with the average rounded down, missing the forced extra item
  • Says the bound holds only if the function spreads keys evenly
  • Reads ceil(n/m) as a prediction of the busiest shard rather than a floor
  • Claims nothing can be said until the distribution is measured
  • Assumes adding shards eventually guarantees at most one key per shard
  • Forgets the symmetric half, that some shard holds at most floor(n/m)