System Design

Recent Searches

Design a recent searches list like the one Amazon or YouTube shows in an empty search box.

Functional requirements

• Record a user's search query the moment they run a search, so it is available the next time they open the search box.
• Return that user's most recent queries newest first when they tap into an empty search box (e.g., show the top 10 of up to 50 stored).
• Collapse repeats: searching a query the user has run before (matched case-insensitively and ignoring surrounding whitespace) moves it back to the top instead of adding a second entry.
• Let a user delete a single entry from their history (e.g., the 'x' next to 'noise cancelling headphones').
• Let a user clear their entire history from a settings screen, after which nothing they searched earlier is returned.

Non-functional requirements

• The dropdown read sits on the critical path of every search: p99 under 50ms server-side to fetch a user's list, and recording a search must not add latency to the search request itself, which returns results whether or not the history write has landed yet.
• Reads may be slightly stale across devices (a query run on a phone can take a few seconds to appear on the same user's laptop), but the device that ran the search must see it on the next focus.
• Deletes and clear-history are privacy actions, not conveniences: they must stop being served everywhere, caches included, within a few seconds.
• History is convenience data, not a system of record: the list is replicated and durable, but losing the last second or two of writes in a crash is acceptable, and if the history store is unavailable the search box must still work without its list.
• A user's history is served only to that authenticated user, and signed-out or private-mode sessions are never written to the store.

Scaling & constraints

• 200M daily active users running about 10 searches each, so roughly 2B history writes per day (about 23,000 per second average, 60,000 at peak), and a live event can push writes to about 115,000 per second (5x the daily average) for 30 minutes.
• Read:write ratio is about 4:1 because every search box focus reads the list and only some end in a search, giving about 8B reads per day (about 93,000 per second).
• Each entry is about 100 bytes (query text plus a timestamp), so a capped 50-entry list is about 5KB per user.
• 500M registered users have a history, so the full dataset is roughly 500M x 5KB = 2.5TB before replication.
• Entries older than 180 days expire, and search volume grows about 25% per year.
• No normal user is a hot key at 10 searches per day, but a few thousand shared kiosk and bot accounts run far heavier, and the hottest few dozen reach about 3,000 searches per minute each, which is 50 writes per second landing on one user's key; the whole group is under 2,500 writes per second, roughly 10% of all writes.

Out of scope

• Query autocomplete and typeahead suggestions drawn from the global corpus.
• Ranking and relevance of the actual search results.
• Personalization or recommendation models built on search history.
• Building the authentication system itself, account management, and cross-account identity merging; assume every request arrives with a trusted user id.