Google Typehead System Design | Expertifie - sulabh84/SystemDesign GitHub Wiki

Overview

  • Search Bar -> User is typing few characters, you should be able to return top 10 suggestions to the user for the typed char.
  • Suggestion to be returned should have the maximum frequency in your table

Functional Requirements (5-7 minutes)

  • Should be able to return top 10 suggestions
  • Update frequency of the word which has been searched
  • Here we are considering only words and not the sentences (Assumption)
  • Wait for another 500ms before you return the next result
  • Spells checks are not required (Out of scope)
  • Customized suggestion (Out of scope)
  • Region Specific search (Out of scope)
  • Only digits and alphabets have to be considered
  • Multiple languages

Non-Functional Requirements

  • Latency -> low approx 10ms
  • Availability -> High Availability (5 9's)
  • Consistency -> Not required immediately but the system should be eventually consistent
  • Reliability
    • System should be reliable in the sense that it doesn't capture user specific information
    • Best suggestions are returned from the system
    • Security layers are in-place
    • Rate limiter

Estimations (5-7 Minutes)

  • Assumptions
    • Approx 100M word search per day
    • 0.001% of the words being searched are new into the system
    • Avg size of the word is 7-8 characters
    • 500M words already present in the dictionary
  • QPS
    • Read QPS
      • 3 (char user has to type to make a suggestion)*100 * 10^6 (Per day) / 24 * 60 * 60 (86400)
      • 3*10^8/10^5
      • 310^3 = 31000 read QPS * 2 (Multiplier) = 6000
    • Write QPS
      • Read to write ratio is 3:1
      • Write QPS -> 2000 - 3000 write per second
  • Capacity
    • 100M search per day
    • For an Entry
      • Word
      • Freq
    • 500M (Current Disc.)
      • 500M * (7 size on avg of each word) * (1 char is 1 byte) * 100 bytes (metadata) -> words already present
      • Every day -> 500M * 0.001 -> 50K new words everyday -> 50K * 7 * 1 * 100(metadata) -> 35K * 10^3 = 35M per day new words
      • for next 1 year
        • 500M7100 + 35M*365 bytes
        • 35M * 10^4 + ~ (1M * 10^4)
        • 35 * 10^6 * 10^4 / (102410241024)
        • 360 GB of data per year = ~400GB

Detailed design (30-35 mins)

  • Apis
    • Read API -> User is waiting for the result
      • Get request
      • getSuggestions(char[] prefix)
        • return top 10 suggestions
      • System is read heavy system and should optimize for returning the results asap. Return Top 10 suggestions
    • Update API -> user is not waiting for the result
      • Post Request
      • updateFreqForPost(char[] word)
    • write can be slower as well because user really dont care about the increase in frequency -> preferences to be given to read before the write

System Design Modelling

Tables and Indexes

  • Sql DB
  • NoSql DB
    • Table 1(Suggestion Table)
      • String prefix <- key
      • List<Pair<Freq,String>> -> top 10 Suggestions
    • Table 2(WordFreq Table)
      • String word <- key(PK)
      • Int64 Freq <- Value

Scaling

  • Horizontal
  • Vertical
    • Prefer a mix of horizontal and vertical scaling

Sharding

  • Range based sharding -> Suggestion Table
    • A,B,C...Z -> 26 Instances
      • 2nd layer A is heavily loaded
      • AA - AP, AQ - AZ
    • Date based sharding ->
      • For every day you create a separate shard
      • Word,Freq
        • 2nd layer -> Range based
          • A-G H-P Q-Z

Replication

  • (Suggestion Table) -> upto 5 replications (All server at the same level)
  • (WordFreq Table) -> (Master - Master) -> 2 replications

Load balancing

  • Helps in better distribution of load across layers
  • Round Robin strategy for balancing the load between the servers/machine

Auths

  • not required

Monitoring, alearting and backups (2-3 mins)

  • same as twitter design

caching

  • 80-20 rule
  • 80% request 20% data and 20% request 80% data
  • Cache those 20% prefixes
    • Trie -> cache Optimize on read and write
      • Invalidations
      • Strategy to remove a prefix from the cache -> LRU
    • Write Around cache

Design

image image