System requirements

Functional:

1. Users can search nearby businesses, like restaurants, theaters, etc.
2. Users can view the details of each business.
3. Users can submit reviews on any business.
4. Business owner can view, add, update, and delete their business.

Non-Functional:

1. Users can get search results with low latency.
2. The system should be highly available.
3. We can do eventual data consistency.
4. We must ensure privacy for sensitive data, like users' location data.
5. The system should be scalable for high peak usage.

Capacity estimation

1. Assume the DAU is 100million and there are 200million businesses.
2. Assume each user will do 5 searches on average daily, and then the search QPS is 5 * 100 * 10 ^ 6 / 10 ^ 5 = 5,000. Within the peak time, QPS can be 5 times -- 25,000.
3. Assume each user will submit 1 review on average daily, and then the review write QPS is 100 * 10 ^ 6 / 10 ^ 5 = 1,000.

API design

1. Search business
   1. url: GET /v1/search/nearby
   2. parameter:
      1. longitude
      2. latitude
      3. radius
      4. business_type
   3. return: list of businesses
2. Submit review
   1. url: POST /v1/review
   2. body:
      1. businees_id
      2. review content
3. View business details
   1. url: GET /v1/view/details
   2. parameter:
      1. businees_id
   3. return: business details
4. Add business
   1. url: POST /v1/businesses
   2. body:
      1. business details
   3. return: business_id
5. View business
   1. url: GET /v1/business/details
   2. parameter:
      1. businees_id
   3. return: business details
6. Update business
   1. url: PUT /v1/businesses
   2. body:
      1. business id
      2. business details
7. Delete business
   1. url: DELETE /v1/businesses
   2. parameter: business_id

Database design

Business

1. business_id primary key
2. owner
3. type
4. city
5. country
6. address
7. longitude
8. latitude
9. created_at
10. updated_at

Business write frequency is quite low, but the read volume is much higher for search and view requests. We can consider a relational database, like PostgreSQL. To handle high read volume, we can create replicas

Geohash

1. geohash
2. business_id
3. business_type

Geohash stores business_id and its geohash prefix. We create this table because when we query businesses within the radius based on user's longitude and latitude, no matter how we index the fields, we have to scan the whole table. Therefore, we can use geohash to convert longitude and latitude to one-dimensional data. Considering it needs to support high read volume and low write volume, we can also choose a relational database as above.

In addition, as the radius is adjustable and geohash with different lengths presents different scopes, we can store geohashes with multiple lengths for the same business.

Another thing to be noted is we don't store a list of busiess_ids for the same geohash, because it will make updating or deleting businesses complicated, but in we can do a list of busiess_ids in cache to make read faster.

Review

1. review_id
2. business_id
3. reviewed_by
4. content
5. created_at
6. updated_at

Review has both high read and write volumes, so we can consider key-value database. We can partition it by business_id, and make reviewed_by and updated_at as sort keys. Also, to retrieve user's reviews by user, we can create GSI, and make reviewed_by as partition key and business_id & updated_at as sort keys.

High-level design

1. Load balancer is responsible for distributing requests
2. Api gateway is responsible for authentication, limiting rate, and redirecting requests
3. View detail service will fetch business details and all related reviews for non-business users
4. Review service will write the review into review database
5. Business service will handle all business operations, including view, add, update, and delete
6. Location based service will calculate all business nearby
7. CDN is for the fast retrieval of business content, like images

Request flows

1. When business owner does any update on any business, the data will be directly stored in the business database. In the meantime, the data will be replicated periodically.
2. When user submits any reviews, the content will be written into database.
3. When user requests any details of a business, the service will fetch business information and related reviews
4. When user search nearby businesses, the LBS will fetch business id list from geohash cache and calculate the distance based on business data and return the exact list

Detailed component design

Even we use geohash there're still some problems:

1. Two entities don't shared geohash prefix or shared prefix length isn't long enough, but they're close
2. One geohash doesn't contain enough business

To resolve the above edge cases, we can calculate 8 neighbor geohashes and collect those businesses as well for further calculation and filtering

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?