Check-and-Insert for a Million User IDs: Balancing Latency, Memory and Accuracy

A service keeps a set of about 1 million user IDs. For each incoming request it must check whether the request's user ID already exists and, if it does not, add it. Design how you would store the IDs and implement this check-and-insert efficiently, and explain how you would balance latency, memory and accuracy. ### Constraints and Clarifications - The ID format, the request rate, and whether the set must survive restarts were not specified. Ask, or state your assumptions. - Check-and-insert is one logical operation: the caller wants to know whether the ID was already present, and if it was not, it must be present afterwards. ### Clarifying Questions - What do user IDs look like: 64-bit integers, UUIDs, or arbitrary strings? Are integer IDs dense within a known range? - What is the request rate, and what fraction of requests carry an ID that is new? - May the answer occasionally be wrong? If so, in which direction: wrongly "exists", or wrongly "does not exist"? - Must the set survive a restart, and is it shared by several service instances? - Will the set grow far beyond 1 million IDs, and are IDs ever deleted? ### Part 1 — A first design Start with the simplest design that works for 1 million IDs on one machine. Estimate its memory use and the latency of one check-and-insert, and make sure concurrent requests cannot corrupt the answer. ```hint Do the arithmetic before optimizing Estimate the bytes per stored ID in the structure you choose, including the structure's own overhead, and multiply by a million. Decide from that number whether anything fancier is needed yet. ``` #### What This Part Should Cover - A concrete data structure, its operation costs, and a memory estimate for the actual ID format - Making check-and-insert atomic under concurrent requests, within one process and across processes - Alternatives that suit special ID shapes or read-heavy workloads ### Part 2 — Trading memory for accuracy Now suppose memory is tight, or the set is expected to grow by orders of magnitude, so a memory-resident exact structure holding every ID is no longer an option. How do you keep most checks fast, and what accuracy do you give up? ```hint Which mistake can you afford? Decide which answer, "exists" or "does not exist", could tolerate an occasional error, and what an error in that direction would do to a check-and-insert. ``` #### What This Part Should Cover - A compact structure, the kind of error it makes, and how to size it for a target error rate - How the design keeps the final answer exact, or what the consequences are if it does not - Behavior as the set grows past its design size, and what happens if IDs must be deleted ### Part 3 — Durable storage that keeps growing The exact set must now live on disk, survive crashes, and absorb a steady stream of inserts while lookups stay fast. Design the write path and the read path. ```hint Writes and reads want different layouts Random in-place updates on disk are slow, while sequential appends are cheap. Think about what you keep in memory, what you write to disk and when, and how a lookup avoids touching most of what is on disk. ``` #### What This Part Should Cover - The write path: durability, in-memory buffering, and flushing to disk - The read path: the order in which places are searched, and how most of them are skipped - Background maintenance that keeps lookups fast, and recovery after a crash ### What a Strong Answer Covers - Starting from requirements and numbers, and not over-engineering the 1 million ID case - Atomic check-and-insert, in one process and across service instances - A precise account of the error a compact structure makes and what that error does to this particular operation - A coherent on-disk design with clear write and read paths, maintenance, and crash recovery - Scaling, observability, and explicit trade-offs among latency, memory, accuracy and durability ### Follow-up Questions - Two requests carrying the same new ID arrive at the same moment on two different servers. How do you make sure exactly one of them adds it? - IDs can now be deleted. What breaks in your design, and what would you change? - How would you shard the set when it reaches billions of IDs? - When would a sorted array, or a bitmap over the ID range, beat a hash set here?