Design a Proximity Server (Yelp / Nearby Friends)

Core Algorithm: Geospatial Indexing

Spatial indexing enables sub 100 millisecond proximity queries across hundreds of millions of coordinates. The production path uses GeoHash, while QuadTree remains an alternative for highly uneven density.

Option 1: GeoHash

Divide the world into 2 halves alternately by longitude and latitude, then encode the binary coordinates as Base32 strings. Nearby locations share a common GeoHash prefix.

GeoHash Precision:
  Length 1: ~5,000 km cell
  Length 4: ~39 km cell
  Length 5: ~4.9 km cell (optimal for nearby search)
  Length 6: ~1.2 km cell (optimal for walking distance)
  Length 7: ~150 m cell
  Length 8: ~38 m cell

Key property: Nearby locations share a common GeoHash prefix. "9q8yy" and "9q8yz" are adjacent cells.

Search algorithm:
1. Compute the GeoHash precision from the requested radius
2. Determine the covering cell set for the search circle
3. For the common 5 km search at precision 5, query the home cell plus its 8 neighbors: WHERE geohash LIKE '9q8yy%'
4. For larger radii, expand the covering set beyond 9 cells as needed
5. Filter by actual distance because GeoHash cells are rectangular approximations
6. Sort by the requested ranking mode

Option 2: QuadTree (alternative in memory structure)

Start with the entire world bounding box as the root node. Recursively divide each node into 4 quadrants (NW, NE, SW, SE) until a node contains at most K businesses (for example, K=100). Leaf nodes contain the actual business records.

Root (World)
├── NW (Americas)
│   ├── NW (Canada)
│   ├── NE (NE US) -> [biz1, biz2, ..., biz87]  (leaf: 87 businesses)
│   ├── SW (SW US)
│   │   ├── NW (Bay Area) -> [biz1, ..., biz95]  (leaf)
│   │   ├── NE (Central CA)
│   │   └── ...
│   └── SE (SE US)
├── NE (Europe/Asia)
└── ...

Search algorithm:
1. Start at the root and recursively traverse nodes whose bounding boxes intersect the search circle
2. Prune nodes whose bounding boxes are entirely outside the search radius
3. Collect business candidates from intersecting leaf nodes
4. Continue until all intersecting nodes are examined or the bounded candidate set is satisfied
5. Filter by exact distance

Building QuadTree: O(N log N), where N = number of businesses
Search: O(log N + M), where M = businesses in result
Memory: 200M businesses x 32-byte compact entries = ~6.4 GB (fits in memory on a single server)
Rebuild: Every night. Incremental updates during the day

Option 3: Google S2 Geometry

• Uses a space-filling Hilbert curve to map two-dimensional surface space to a one-dimensional sequence
• Encodes each cell into a compact 64-bit integer identifier
• Provides minimal cell covering set logic for arbitrary shapes and polygons
• Maintains more uniform cell sizes than GeoHash across varying latitudes
• Commonly used in production by Google Maps and Foursquare

Option 4: Uber H3 Index

• Hexagonal grid system rather than square or rectangular cells
• Hexagons have uniform distance to all 6 immediate neighbors, unlike squares where diagonal neighbors are farther
• Resolution 9 (~174m edge) for precise tracking, and Resolution 7 (~1.2km edge) for surge pricing zones
• Finding adjacent neighbors is an efficient O(1) mathematical operation

Proximity Search Service

Radius queries hit overlapping grid cells, then filter candidates and rank them along the critical read path.

1. Receive query: {lat, lng, radius, category, sort_by}
2. Query the production GeoHash index for businesses within the covering cells. QuadTree remains an alternative implementation for regions with highly uneven density.
3. Filter candidates by business category code and optional text query
4. Rank candidates by the requested sort mode. Distance uses exact distance, while relevance can combine distance, average rating, popularity, and optional text relevance.
5. Enrich top candidates with business details from Redis cache or fall back to MySQL
6. Return paginated results with a cursor containing the last ranking key and business_id for stable page boundaries

Business Service

Business listings are predominantly static, which allows indexing once and updating asynchronously on owner edits.

• Handles CRUD operations for business listings
• On create or update, write changes to MySQL. Debezium CDC then emits the asynchronous change event used to update the geospatial index.
• Review create or update writes the review row and adjusts rating_sum, review_count, and avg_rating in one transaction. The resulting business row change is captured by the same CDC pipeline used for index refresh.
• On delete, mark the business inactive and let CDC remove it from the GeoHash index and invalidate its Redis profile cache.
• Hot business profiles remain cached in Redis to minimize relational database read load

Kafka CDC: Incremental GeoHash Updates

Change data capture decouples database writes from in memory index updates and ensures consistency across search replicas.

• A full GeoHash index rebuild from MySQL executes nightly, taking roughly 5 minutes for 200M businesses. The rebuild records a consistent snapshot and CDC position, builds a replacement index from that snapshot, replays subsequent CDC events before cutover, and swaps the active index only after the new version catches up so no updates are lost during the rebuild.
• Debezium CDC on MySQL captures row-level changes and publishes them to the Kafka topic business-changes
• The GeoHash index cluster consumes changes:
  • Insert: Compute the business's GeoHash cell and add its compact index entry.
  • Update location: Remove the business from its old cell and insert it into the new cell.
  • Update metadata: Refresh compact searchable fields without changing the cell when location is unchanged.
  • Delete: Remove the business entry from its GeoHash cell.
• The CDC stream also invalidates the Redis business cache and updates Redis GeoIndex
• Typical end-to-end lag: catalog updates reflect in search results within approximately 2 seconds, with a < 30 second freshness SLO

Nearby Friends: Real Time Architecture

Nearby friends requires high throughput real time writes, with privacy enforced by limiting what location information is exposed to other users.

• Unlike static business search, moving friends produce high frequency location streams that require an in memory spatial store.
• Execution workflow:
  • Each user streams ephemeral location coordinates every 4 seconds over a WebSocket connection
  • Location writes update a city and GeoHash prefix scoped Redis Geo Set. A 15 second expiry index removes stale members, and disconnect handlers remove entries when possible
  • When a user opens Nearby Friends, the service queries nearby candidates and intersects them with the user's friend set
  • Optimization: Use the spatial index to pre-filter nearby candidates before friend-set membership checks

Reviews and Rating Denormalization

Denormalize ratings onto business records so proximity search queries never require expensive table joins.

At roughly 100K reviews per day (~1.16 writes/sec), reviews stay in the same MySQL database as businesses, so no separate review service or message queue is required. Each review insert or update runs in one transaction. A new review adds its rating to rating_sum and increments review_count. An edited review applies the difference between the old and new rating. The transaction then recomputes avg_rating = rating_sum / review_count. A UNIQUE constraint on (user_id, business_id) enforces one review per user per business. Search reads the denormalized avg_rating directly from Redis cache or the GeoHash index without joining the review table.

Event Bus Design (Kafka)

The Kafka event bus decouples relational write streams from in memory index consumers and buffers peak ingestion bursts.

Topic: business-changes (Debezium CDC from MySQL)
  Partitions: 16 (partition by business_id)
  Partition key: business_id
  Retention: 24 hours (index catch-up only)
  Replication factor: 3, min.insync.replicas: 2

Producer: Debezium connector on MySQL binlog (INSERT/UPDATE/DELETE on businesses table)
Consumer: GeoHash index updater (consumer group "proximity-index-sync")
  - Incremental cell update: remove old GeoHash cell, insert into new cell
  - Invalidate Redis cache key biz:{business_id}
  - At ~12 events/sec (1M updates/day), single consumer suffices
  - Lag alert: CDC lag > 30s indicates search index staleness

Sync path: business owner updates listing, writes to MySQL, and receives 200 OK
Async path: CDC event updates the in memory GeoHash index and invalidates the Redis cache. Typical propagation is around 2 seconds, with a <30 second freshness SLO.