System requirements

Functional:

• User can type in a partial term and system should offer a list of suggestions (upto 5).
• When a user enters a term OR clicks on an existing term, the system should internally increment a count for that term
• Ability to mark a suggested term as not relevant
• System should take into account location of user, i.e. the suggestions should be localized. I.e. a term popular in India may not be popular in USA and vice versa

Non-Functional:

• Low latency for fetching results, under 100ms
• System should be highly available
• Term frequency count used for suggestions can be eventually consistent
• System should scale to 100m users and 1b+ terms

Capacity estimation

• System should scale to 100m users and 1b+ terms
• Each term is 10 bytes, 10GB storage needed
• Each user does 10 queries per day, so 10^9/10^5 = 1000 requests per second
• Workload seems CPU and network bound rather than memory bound

API design

GET /typeahead/{partial-term}

Returns - List of 5 top results

POST /increment-frequency/{term}

Updates frequency of term

POST /blocklist/{term}

Increments a block counter for a term, if enough users mark block a term, it will be removed from suggestions

Database design

• We need an in-memory data structure to store typeahead suggestions to enable fast lookups. Trie is an ideal data structure for this.
• The Trie only needs to store high frequency terms (seen at least 100 times). To calculate frequency efficiently, we can use a bloom filter in memory. combined with a sorted treemap to store the term to frequency map
• Bloom filter can be reset and trie can be reconstructed once a day to allow more recent terms to be favored over older popular terms
• We can flush the frequency map and bloom filter to disk periodically - either BTrees or SSTable based storage can work. SSTable is more optimized for writes wherease BTrees more optimized for faster reads.
• Trie can be reconstructed in case of node failures from disk or we can fetch the Trie from a replica

High-level design

• Load balancer - distributes load, partition by term prefix
• Typeahead server - Keeps in memory frequency map, bloom filter and constructs Trie from it. Typeahead server is partitioned by prefix range + location ID. Ex. terms starting with "a" and in USA can be stored on 1 server. Each server can have multiple read replicas, and one write replica, we can propagate changes from write replicas to read replicas every few seconds.
• Alternatively, we can have all replicas accept reads and writes and merge the frequencies across terms periodically. We can do this by having 2 sets of Tries, one to store local frequency (for writes only) and one that has frequencies merged together from other replicas. This will need an aggregator component (or Flink job) to combine the frequencies across the various replicas into one. This can support higher write throughput, so is preferable despite the more complicated architecture.
• Failure handler server - responsible for reconstructing Trie in case of failure of the Typeahead server write replicas

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

• Using bloom filter for storing frequencies can lead to potential overcounting of frequencies, but we can overcome it by using larger number of hashes to compute frequencies at the cost of larger memory footprint.
• We can sort the term to frequency map by frequency OR use a heap data structure, and only pick terms that have over 100 frequency count to reduce memory footprint of Trie
• We use multiple write replicas which requires us to merge frequencies across replicas, but this tradeoff may be worth it to avoid overloading a single write replica
• We can rate limit each user to no more than 2 requests per minute to avoid overloading our system
• We can combine the Trie lookup with an in memory cache like Redis/Memcached for typeahead for frequently queries terms.
• Trie and frequency map can be reconstructed every day so that the freshest terms can be returned to the user.

Failure scenarios/bottlenecks

• Hot partitions due to queries concentrated for a single prefix and geographic location. We can overcome with a greater degree of sharding, more replicas and caching of frequently queried terms using Memcached
• As our system is eventually consistent, updates in frequency or blocking of terms may take time to propogate. For certain terms (ex. inappropriate terms for ex. related to terrorism or pornography), we can force replication across all replicas (i.e. strong consistency) at the cost of higher latency.
• As we reconstruct frequency map and trie each day, we can lose historical terms, instead of a complete reset, an alternative may be to decay older query terms each day, for ex. a term entered that is 1 day old can be 0.8 the weight of a fresh term.

Future improvements

• Incorporate auto-correct of incorrectly typed terms, can use ML models to get a list of nearest terms to the typed in (incorrect) word.
• We can have some level of personalization of the terms based on context. For example if a user has made a lot of searches related to food or restaurants, the suggested terms should weigh food related terms more.
• The typeahead terms are localized however if there are insufficient terms to suggest in a locale (for long-tail terms), there should be a way to fetch global terms, which can be done by a global aggregator
• Monitoring/obervability using Prometheus/Grafana for latency, request success rate, hot partitions, top 100 most frequent terms, etc. Info related to hot partitions and most frequent terms can be used to tune the system, add more shards/replicas, etc.