Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
List non-functional requirements for the system...
Estimate the scale of the system you are going to design...
Number of businesses = 200 million approx
Number of queries per second (QPS) = 10K
Define what APIs are expected from the system...
GET https://
Returns JSON array with business information - id, name, location, rating, thumbnail
GET https://
POST https://
{
text:...
rating:...
}
Returns a review id and https code 201
POST for add
PUT for update
DELETE for delete
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...
Geohash Cache
============
Key-value store in Redis cache
Geo-Hash ----> key
Business Id ----> Val
LBS is stateless and does not require persistent storage.
Business Service
============
Business Table:
Id - Key
Name
Address
Image
Rating
This can be stored in a SQL DB as it requires ACID properties and has a well-defined structure
Reviews
=======
Review Id - Primary Key
Business Id - Foreign Key
Reviews { ... }
Reviews can be in a document store like MongoDB.
Overall, this is a read-heavy system.
You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...
API Gateway - Gateway which is the entry point for all requests. Routes requests based on type - location vs business
Business Service - Responsible for business management functions like adding/removing/updating a business. Add reviews.
Location Service (LBS) - Responsible for fetching nearest businesses based on user location.
Cache - Both Business and LBS have their own cache. Redis can be used for this.
Business DB - Contains persistent data for the businesses. It is synced with read-only replicas.
Replica - Used for read-access by LBS. It is synced with primary replica periodically (nightly job).
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...
Get Nearby Businesses
===================
Example - for radius of 5 km, search using query like -
find business ids where geohash like 94xyd
Add Review, Add/Update/Delete/Get Business Info
===================================
Nightly Job
=========
A nightly job syncs LBS cache with the Replica to get updated business info. This must be done when traffic is low.
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...
Location Services use technologies like Quad Tree, Geohash, Google S2 library.
Geohash
========
Divides the earth into 4 quadrants recursively. Longer the geo-hash length, lesser the search radius.
Locations with more geohash match length are closer to each other.
Pros:
------
Easy to implement
Cons:
--------
Quad Tree
========
Equally divides the Earth into 4 quadrants recursively until the number of businesses in each quadrant is less than or equal to a pre-configured number k (say 100).
Pros:
------
Cons:
--------
In this case, we will use geo-hash for its simplicity.
Geohash Cache
==============
For our search radius, a geo-hash of length 6 is enough.
len 4 = 20 km
len 5 = 5 km
len 6 = 0.5 km
Geohash cache is created on LBS with information about business id and geo-hash.
Each entry in the cache is of - 16 bytes (business id) + geo-hash (6 bytes) = 32 bytes
For 200 million businesses, total memory required = 32 * 200 million
= 8 GB
This much data can easily fit in a standard Redis cache.
Memory-wise, a single server is enough to handle the data but may require additional servers to support more requests.
Privacy of User and Business Data
==========================
Use DNS Routing to route data to local servers
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
A single instance of Location Based Service (LBS) may not be enough for high QPS. Deploy multiple instances of it. As it is stateless, scaling out is easy. Use a Load-Balancer to distribute requests evenly.
Use distributed cache for multiple types of businesses.
If not enough businesses, asks the user to expand the search and retry.
Shard the business DB based on business id or location.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?