System Design - Walk Through

# Systems

# Proximity Service

Functional requirements

return all businesses based on a user’s location (latitude, longitude pair) and radius
business owners can add, delete or update a business, but this information doesn’t need to be reflected in real-time
customers can view detailed information about a business

Non-functional requirements

low latency
data privacy
5000 search QPS
high availibility and scalability requirements

API design

1
2
3
4
5
6
7


# this endpoint returns businesses based on certain search criteria
/v1/search/nearby

# api for business
CRUD /v1/businesses

# pagination

Data Model

read/write ratio
data schema

Algorithms to fetch nearby business

Geohash in redis
Postgresql with PostGIS extension
old school SQL query

several options

two-dimensional search
evenly divided grid
geohash
- Geohash algorithms work by recursively dividing the world into smaller and smaller grids with each additional bit.
- boundary issues
  - geohashing guarantees that the longer a shared prefix is between two geohashes, the closer they are. However, the reverse is not true.
  - two positions can have a long shared prefix, but they belong to different geohashes
quadtree
- a quadtree is a data structure that is commonly used to partition a two-dimensional space by recursively subdividing it into four quadrants until the contents of the grids meet certain criteria.
Google S2

1
2
3
4
5
6
7
8
9


-- two dimensional search
SELECT business_id, * FROM tb_business
WHERE
(latitude BETWEEN ${my_lat} - radius AND ${my_lat} + radius)
AND
(longitude BETWEEN ${my_long} - radius AND ${my_long} + radius);

-- geohash
SELECT * FROM geohash_index WHERE geohash LIKE '9q8zn%'

# Nearby Friends

# Google Maps

# Distributed Message Queue

# Metrics Monitoring and alerting system

# Ad click event aggregation

# Hotel reservation system

# Distributed Email Service

# S3-like object storage

# Real-time gaming leaderboard

# payment system

# Digital wallet

# Stock Exchange

# References

alex xu