How do you decide what collision probability a randomly generated identifier scheme may carry across a service's lifetime?
answer
- consequence first, arithmetic second
- detected duplicates cost far less
- compare against risks already tolerated
- lifetime count, not today's rows
- scope: global or per partition
basics
~20 sSet the budget from what a duplicate would actually cost, not from taste. Compare it with failures already tolerated, apply it to lifetime volume over the scope where uniqueness must hold, then invert the collision bound to get the required width.
solid answer
~40 sThe mathematics only converts a risk budget into a width; choosing the budget is the judgment call. Start with the consequence: a duplicate rejected by a uniqueness constraint and retried is an annoyance, while a duplicate that silently merges two customers' records is an incident with no detection path, and the two deserve budgets many orders of magnitude apart. Calibrate against risks the system already accepts rather than against zero. Then apply the bound to the right quantity - the **lifetime** count of identifiers minted, not today's row count - and over the right **scope**, since uniqueness required only within a tenant is a far smaller problem than global uniqueness. Finally weigh the alternative: a coordinated allocator removes collisions outright and replaces them with an availability dependency on every mint.
go deeper
Recall that a random identifier scheme never promises zero duplicates - it promises a probability - and that the width chosen is what sets how small that probability is.
Explain the inputs the sizing needs: the total identifiers ever minted, the scope uniqueness must hold over, and the target probability. Be able to say why today's row count is the wrong number to use.
Show the assumption checks that make a derived width real: no truncation into a narrower column, a generator that cannot repeat after a restore, and identifiers of deleted rows never reused.
Own the trade explicitly. Choose between a computable, bounded risk and a coordination dependency you must operate forever, justify the budget against failures the system already tolerates, and record the inputs so the width can be re-derived rather than guessed.
## The budget comes from the consequence, not from the arithmetic Inverting a collision bound is mechanical: pick a target probability `p`, and the space must satisfy roughly `n >= k^2 / (2p)` for `k` identifiers. The interesting decision is where `p` comes from, and the honest answer is that it comes from what a duplicate would do. The distinction that matters is **detected versus silent**: | Consequence of a duplicate | Detection | Reasonable budget | |---|---|---| | Rejected by a uniqueness constraint, caller retries | Immediate, automatic | Loose - a visible, recoverable event | | Two records merged into one, no constraint in the path | None, possibly ever | Extremely tight - below other silent-corruption risks | | Cross-tenant identifier reuse in a security decision | None, and it is a breach | Tight, and probably the wrong design entirely | A scheme whose collisions are caught and retried can afford a budget many orders of magnitude looser than one whose collisions corrupt data unnoticed. Teams that skip this step usually pick a number that feels impressive and then cannot say what it protects. ## Calibrate against risks already accepted Zero is not on the menu for random identifiers, so the useful question is *how small relative to what else can go wrong*. A system already tolerates undetected storage errors, a rare mis-delivered message, an operator mistake. A collision risk far beneath those is, in engineering terms, not the thing that will hurt you, and pushing it lower buys nothing while the wider identifier costs real bytes in every index, every message and every log line. ## Apply it to lifetime volume, at the right scope Two sizing errors are common, and both are about the inputs rather than the formula: 1. **Sizing for today.** The count in the bound is every identifier the scheme will **ever** mint, including replays, test data, deleted rows whose identifiers must not be reused, and whatever a future bulk migration produces. Take the projected rate, multiply by the years the scheme will plausibly live, and add headroom. 2. **Sizing at the wrong scope.** Uniqueness is sometimes only needed **within** a partition - per tenant, per table, per day. If so, each partition draws its own, far smaller `k`, and the risk per partition falls quadratically. Splitting a fixed total across 1,000 partitions cuts each partition's pair count by about a factor of a million; summed back over the 1,000 partitions, total risk is around a thousand times smaller than the global figure. Conversely, if identifiers from separate partitions ever meet - in an export, a shared cache, a merged audit log - the scope is global whatever the schema says. ## The alternative you must price Coordinated allocation - a central sequence, a leased block per minter - removes collisions by construction, so it deserves to be on the table whenever the budget looks hard to meet. The trade is a change of failure mode, not an elimination of one: - **Random draw:** no coordination, mint offline, mint during a partition; residual risk is a statistical one you chose. - **Coordinated allocation:** zero duplicates; every mint now depends on a component that can be slow, unavailable or partitioned, and block leases reintroduce a duplicate risk of their own whenever a lease is replayed after a restore. A useful framing for a review: you are choosing between a risk you can compute and bound, and a dependency you must operate forever. Where minting must work offline or during a partition, the computable risk usually wins. ## A defensible procedure 1. Write down what a duplicate does, and whether anything detects it. 2. Pick `p` relative to the silent failures the system already tolerates. 3. Estimate lifetime `k`, generously, and state the scope uniqueness must hold over. 4. Invert the bound for the required space, then round **up** to a natural width. 5. Re-check the assumptions that the arithmetic cannot see: seeding quality, whether anything truncates the identifier, whether a restore can replay previously issued values. 6. Record the budget and the inputs, so the next person can re-derive the width instead of guessing at it. Step 5 is where real schemes fail. A width derived correctly and then truncated to fit a narrower column, or fed by a generator that repeats after a restore, is under-sized no matter how careful the original derivation was.
- Does narrowing the uniqueness requirement to one partition change the sizing?Substantially, if collisions truly only matter inside a partition. Each partition draws its own much smaller count, and risk grows with the square of that count: splitting a fixed total across 1,000 partitions cuts each partition's pair count by roughly a million, and the total summed over all partitions by roughly a thousand. The catch is whether identifiers from different partitions ever meet in an export or a shared cache.
- What makes a coordinated allocator the wrong answer even though it removes collisions?It converts a bounded statistical risk into a permanent availability dependency: every mint now needs a component that can be down, partitioned or a write bottleneck, and offline minting stops working. Leased blocks also reintroduce duplicates whenever a lease is replayed after a restore. You are trading a risk you can compute for one you must operate.
- Why is 'zero collisions' the wrong target to state for a random scheme?Because random draws cannot offer it at any width - two draws could match immediately - so the target is unachievable rather than merely expensive. The achievable statement is a bound: a probability small enough that it sits well beneath the silent failures the system already tolerates. If genuine zero is required, the answer is coordination, not more bits.
saying these in an interview costs you the question
- Sizes the identifier for today's row count, not the lifetime total
- Picks a risk target without asking what a duplicate costs
- Treats any non-zero probability as unacceptable on principle
- Assumes wider identifiers are free of storage and wire cost
- Ignores that a restore can replay previously issued values