An approximate membership sketch replaces a member collection holding 50 million identifiers a day — what does the fixed memory budget cost you?
answer
- memory decided, not accumulated
- 50 million costs what 50 thousand costs
- one direction of the answer is certain
- nothing can be listed back
- error is a design-time budget
basics
~20 sAn approximate membership sketch takes its memory at creation and never grows, so 50 million identifiers cost what 50 thousand cost. You give up certainty in one direction, and the members themselves: nothing can be listed or read back.
solid answer
~50 sA member collection stores every identifier, so its memory is a function of the input; on a tier with a memory ceiling, 50 million members a day is a capacity plan that grows with traffic. A sketch inverts that. You declare the footprint up front, from an expected item count and a target error rate, and it holds that footprint whatever you add. The price is paid in three currencies. The answer is approximate, and on the membership structures normally used for this the uncertainty has a direction — a 'no' is certain, a 'yes' may be wrong. The members cannot be enumerated or counted exactly, because none of them are kept. And the error you planned for is a design-time budget, not something the structure enforces at run time. Choose the sketch when memory is the binding constraint and a wrong 'yes' is cheap.
go deeper
Recall the defining property: the structure is given its memory when it is created and keeps that memory however many items you add. The exact collection grows with the input; the sketch does not.
Explain what the fixed footprint costs: an approximate answer, no way to list or exactly count the members, and an error rate that is a planning input rather than something enforced at run time.
Show the judgment in the choice: name the magnitude that makes memory the binding constraint, name the branch of code that touches the uncertain answer, and say what happens when the tier loses the entry.
Frame it as a contract the platform offers: which answers may be estimates, who is told they are estimates, and what authoritative record every sketch can be rebuilt from.
## The two shapes answer the same question differently Both shapes answer *have we seen this identifier before?*, and they differ entirely in what the server keeps in order to answer it. A **member collection** — an unordered collection with no duplicates, held under one key — keeps every identifier you put into it. Its memory is a function of the input: 50 million identifiers in a day means 50 million stored members, plus whatever the store charges for each element on top of the bytes. That product is your capacity plan for the day, and it moves whenever traffic moves. In exchange the collection answers exactly in both directions, can hand back everything it holds, and can report exactly how many members there are. An **approximate membership sketch** keeps none of the identifiers. It is created once from two inputs — roughly how many items it will be asked to hold, and the error rate you are prepared to accept — and it occupies that much memory for the rest of its life. Feed it 50 thousand identifiers or 50 million and the footprint is identical. What changes is how often the answer is wrong. ## What the fixed footprint buys - The size is a **decision made at creation**, not an outcome observed later, so planning the entry stops being a function of traffic. - A surge in volume spends **accuracy**, not memory. The structure keeps accepting additions at the same size. - It is **one entry**, so it is one unit of work for the server, and a lifetime attaches to the whole entry rather than to anything inside it. - The per-element charge that a collection pays on every member disappears, because there are no elements. - The memory is knowable before a single identifier arrives, which is what makes it usable on a tier whose ceiling you are already close to. ## What each answer is worth On the membership structures normally used here, the uncertainty has a direction: a 'no' is certain — that identifier was definitely never added — while a 'yes' may be wrong, because the structure keeps compressed evidence rather than the items, and two different identifiers can leave evidence you cannot tell apart. That asymmetry is the whole reason the structure is usable: one branch of your code is standing on certainty. **Which direction is certain is a property of the structure you were handed, not a law of the class.** Fixed-memory structures that estimate how often an item has been seen tend to over-count rather than under-count. Variants that let you remove an item buy that ability with error in both directions. Read the contract of the specific structure before deciding which branch may trust it. ## Side by side | | exact member collection | approximate membership sketch | |---|---|---| | memory | grows with items added | fixed when created | | membership answer | exact in both directions | one direction certain, one may be wrong | | listing the members | a whole-collection read returns them | nothing to return | | exact size | available | not available | | removing one member | supported | not in the basic form | | planning input | how many members will you hold | how many, and what error you accept | | what a surge costs | memory | accuracy | ## Keep the exact collection when 1. **The members themselves are needed later** — for an export, an audit, a repair job. A sketch has nothing to give you. 2. **A wrong 'yes' drives something irreversible or user-visible.** The uncertain direction must not be the one that fires the expensive branch. 3. **The count has to be exact** — anything anyone can dispute, or reconcile against another system. 4. **The population is small enough that the trade buys nothing.** For thousands of members, the exact collection is cheap and simpler to reason about; the sketch pays off when the population is large and the memory ceiling is real. ## It is still an entry on a volatile tier Whichever shape you choose, it is one entry on a tier that can lose it: a restart, a failover, or pressure on the memory ceiling can take it away, and what survives a restart differs sharply between stores — some keep nothing at all, others write a point-in-time copy or a log of writes. A lost collection and a lost sketch behave the same way afterwards: every identifier reads as not seen. Whatever depends on the answer therefore needs a stated behaviour for the empty case, and a rebuild path from an authoritative record — which is also the only way to rebuild a sketch, since it cannot be read back. One more variation worth knowing before you design around it: **not every store in this class offers these structures server-side.** Where the server does not, the sketch lives in the application and the store holds it as opaque bytes, so every addition becomes a read-modify-write round trip and concurrent writers have to be handled by the caller rather than by the server.
- The memory budget is met, but once a quarter someone needs the full list of identifiers for an audit. What changes?The sketch cannot serve it at all — it holds no identifiers to return. The authoritative list has to live somewhere durable, and the sketch becomes only the fast answer on the hot path. If no such record exists, the sketch was the wrong shape to choose.
- What do you need to know before you can even create the sketch?Two numbers: roughly how many items it will hold over the period it covers, and the error rate you accept. Both come from outside the structure, because it cannot report how many items it has been given. Get the population estimate wrong and the error rate you planned for quietly stops holding.
A guest list you can search but never read out: it fits on one card no matter how many names were checked in, and it will sometimes tell you a stranger was here, but never that a real guest was not.
saying these in an interview costs you the question
- Thinks the sketch stores shortened identifiers that can be read back
- Assumes the footprint still creeps upward as items are added
- Treats a wrong answer as equally likely in both directions
- Expects a membership sketch to also report an exact member count
- Justifies the sketch by speed rather than by the capped footprint
- Believes a larger allocation eventually makes wrong answers impossible