System requirements

Functional:

• local businesses can add their locations
• users can query nearby businesses

Non-Functional:

• high scalability
• high performance: low latency, high throughput
• high reliability

Capacity estimation

Assume we have about 100M users and 1M businesses.

=> DAU 20M DAU and 200k establishments x 10 QPD

=> 2k QPS and 20QPS

=> 5k QPS and 50 QPS at peak

Storage requirement: 1M * 100 KB = 100GB

It is read heavy service

API design

• CreateBusiness
  • request: geo_info,
  • response: business_id
• UpdateBusiness
• DeleteBusiness
• GetBusiness

• GetNearbyBusinesses
  • request: {location}
  • response: a list of businesses

Database design

Busineses

• business_id(pk)
• created_at
• geohash

High-level design

• We uses geohash to track and query the geological information for businesses
• We uses relational DB to store the businesses information
• We uses redis for reading cache

Request flows

• Stateful request: invalidate the cache
• Stateles request

Detailed component design

Geohash

Intuitively, we can save the geo information by storing the latitude and longitude info but query geo distance using them is complicated. Then the idea is to compress the 2 dimension calcuation into 1 dimension and there are several algorithms to support that. Geohash is one type of them. It uniquely represents any location with a hash value and the more prefix two hash values are shared, they are closedly in geologically.

Therefore, by given with a geohash, we can query by the prefix according the granularity we want. It is log(n) as the geohash is sorted ahead of time.

Consideration:

• two locations are closed, could in different blocks on grid: we need to include the neighbors as well
• sometimes, the query could return insufficient businesses: we can re-query by shorter prefix

Relational DB

This is a read-heavy service and 100GB can be fully held by one machine so we choose relational DB.

Index

we can build index with as compound key so that it is faster to update

Redis

Since this is read-heavy service, adding in-mem kv store is a natural improvement. 2 tables

geohash -> list of locationId

business_id -> business object

Trade offs/Tech choices

Failure scenarios/bottlenecks

All the components are stateless except the redis and the DB.

Redis should down very rarely if we set up redis cluster which has back up instance

DB also have replicas which will be choosen as the write master when the orignal get down.

Future improvements

Region and Zone

This is a typical location-base service and having multiple regions and availablity zones have several pros:

• low latency as phycailly closer to users
• load balancing according to population
• privacy law

Pagination

We can do pagination on the getBusiness API for better user experience.

API Rate limiting

We can potentially add api rate limiiting feature to protect our service from throttling