Design Typeahead Suggestion - System Design

System requirements

Functional:

Assuming a e-commerce site and a logged in Customer as the primary persona , the Customer should have following capabilities -
1. As he begins typing in the search box when the typed in string is longer than 3 characters a dropdown of possible completions are listed.
2. Multi-dimensional matching - typed in text may be matched in the title of the product , or the description or category or tags of the product
3. The matched portion in the search result are highlighted in the dropdown section of the items
4. The search results are ordered by their match relevance
5. the customer can click on any of the suggested previews from the dropdown that takes him to the particular page
6. If the customer doesn't click anything in the dropdown and types the full text and presses enter - he goes to the search page experience of paginated responses that is bit slower.

Non-Functional:

p99 latency should be <50ms for responsiveness
The system should have 99% availability for better user experience.
The system should scale to 1M DAU

with 80% of them visiting the website in peak 4 hours of the day . Each user doing 10 searches on average . This works to be about (( 800000 / (3600*4)) * 10) 550 tps of peak traffic.

There are 500k products in the inventory

Capacity estimation

Estimate the scale of the system you are going to design...

API design

Request:

GET /suggestions?prefix=

Response:

200 OK

[

{

"display_text":"chiicken soup",

"url":""

"title":"",

"category":""

"tags":[ "t1", "t2" ...]

}

]

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

High-level design

Catalog store component - stores product details . The data is partitioned in alphabetical order . The ranges are uneven based on word frequency. The catalog store are periodically updated by a data pipeline .
Search cluster - the search servers read from catalog store and create a trie in memory at startup . search cluster needs to be restarted when the store is updated. A cluster is for a certain alphabet range . All servers in the node has identical data . The cluster provides horizontal scalability and necessary redundancy for the availability SLA
Ingress Proxy -- acts a reverse proxy into the system it routes the request to appropriate cluster based on the prefix present in the url. Ingress Proxy is stateless and multiple instances of it can be running to scale and handle the incoming traffic. It fetches routing table data from the Prefix Range Master
Prefix Range Master -- This is the system master that dynamically controls allocation of prefix range to the serving cluster. It can dynamically reallocate , split or merge ranges based on usage data . It works with a resource manager
Search Service Cluster Coordinator -- This co-ordinator is responsible for membership monitoring ( heartbeat ) of the cluster , it ensures that requisite number of servers are maintained
Resource Manager -- The Prefix Range Master also works with a Resource Manager to allocate extra servers when clusters are split or needs to be scaled up
Load Balancer -- the entry point to the system it forwards request the Ingress Proxy . It uses a round-robin algo to forward the request to the ingress proxy servers

graph
  B["Ingress Proxy\nPrefix based Request Partitioner"];
  C["Search Service Cluster\n (for a  prefix range)"];
F["Prefix Range Master"];
G["Resource Manager"];
H[" Load Balancer"];
C1["Search Service \n Cluster  Coordinator"];
n1[("catalog store \n Lexicographically partititoned")];
C --> B;
n1 --> C;
F --> C;
C1 --> C;
F --> G;
H --> B;
B --> H;

Request flows

As the user types a prefix -- the js on the page triggers call to the suggestions api . The hostname is mapped through DNS entry to the Load Balancer
Load Balancer -- forwards to the ingress proxy . Ingress Proxy uses the routing table published Prefix Range Master
Ingress Proxy -- uses a library to sanitize and extract prefix from the request > the library also helps extract the relevant portion of the prefix need for the routing table lookup. Based on the routing table result the request is forwarded . THere can be a service discovery system in the infra that further helps in the routing .
Search Service -- the search service does a in memory query and prepares the result list . It also sorts the result data as per the relevancy score .

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

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Initialization of a new server is a slow process as it needs to read the allocated set of products and re-create the trie datastructure in memory , so provisioning for anticipated load has to be done before hand.
Updated Catalog store needs rolling restart , that might cause unavailability . These have to planned in advance and can't be done too frequently

Future improvements

Trie serialization should be done , so that addition of initializaiton of new servers is a fast process