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