Location-Based Service (Yelp)

Intermediate

Overview

A Location-Based Service (like Yelp, Google Places, or the "Nearby Friends" feature) allows users to search for places or entities within a certain geographic radius. The core technical challenge is efficiently querying a massive database of two-dimensional coordinates (latitude and longitude) at high scale.

High-level architecture for a Location-Based Service using Quadtrees

Functional Requirements

Add, update, or delete a business or point of interest (POI) with its geographic coordinates.
Given a user's latitude, longitude, and a radius, return all POIs within that area.
View detailed information about a specific POI (reviews, photos, operating hours).

Non-Functional Requirements

Low latency: The nearby search must be extremely fast (under 100ms) to support map panning in real-time.
High availability for the search read path.
Eventual consistency is acceptable for adding or updating new businesses (a new restaurant taking a few minutes to appear in search is fine).
Scalability to handle millions of POIs and high read QPS.

Capacity Estimation

Assume 100 million total businesses worldwide, and 100,000 search QPS.

Storage for POIs: 100M * ~1KB per POI = 100 GB. (Fits easily on a modern SSD).
Storage for Geospatial Index: A Quadtree node might take ~32 bytes. 100M POIs indexed = ~3 GB. (Easily fits entirely in memory on a single server).
Bandwidth: 100k QPS * ~1KB response = 100 MB/s egress.

The workload is extremely read-heavy. The primary challenge is not storage capacity, but maintaining an efficient in-memory index to serve the 100k QPS without doing a full table scan of the database.

High-Level Architecture

The system is split into two parts: a durable database for storing the actual business information, and an in-memory Geospatial Index (Quadtree) for fast querying. When a user searches for nearby places, the query hits the Quadtree index to get the IDs of the nearby businesses, and then fetches the detailed information for those IDs from a distributed cache or the database.

Data Model

Entity	Fields / Schema	Storage Choice
business	business_id (PK), name, address, latitude, longitude, category	Relational DB (PostgreSQL) or NoSQL store (DynamoDB)
quadtree_index	grid_id, list of business_ids	In-memory tree structure (replicated across multiple index servers)

Detailed Design

The Problem with SQL for Geospatial Queries

A naive approach is to use SQL: SELECT * FROM businesses WHERE lat BETWEEN x1 AND x2 AND lon BETWEEN y1 AND y2. Because this queries two independent dimensions, traditional B-tree indexes struggle. The database has to do an index scan on one dimension, yielding a massive set of rows, and then filter them by the second dimension, which is too slow for 100k QPS.

Geospatial Indexing: Geohash vs Quadtree

Geohash: Divides the world into a grid and assigns a short string to each cell. Nearby cells often share the same string prefix. It's easy to implement in standard databases (like Redis or SQL) by indexing the string, but suffers from edge-case inaccuracies (two points physically close can have completely different Geohashes if they sit across the equator or prime meridian).
Quadtree: A tree data structure where each node represents a bounding box. If a node contains more than K points, it splits into four children (quadrants). This dynamically adapts to density: Manhattan will have a very deep tree with tiny grid cells, while the Sahara Desert will have a shallow tree with massive grid cells. Quadtrees are ideal for holding in-memory for lightning-fast reads.

Quadtree Implementation and Partitioning

Since the entire Quadtree takes only a few gigabytes, we can replicate the entire tree across a fleet of 50-100 read-replica Index Servers. A load balancer distributes the 100k QPS across these servers. When a read arrives:

The Index Server finds the Quadtree node covering the user's location.
If that node doesn't contain enough businesses to satisfy the search radius, the server traverses up to the parent node and checks neighboring child nodes.
It returns a list of business_ids.

Data Updates

Updates to the Quadtree don't need to be strictly synchronous. When a new business is added to the database, a message is published to a Kafka topic. All Quadtree Index Servers consume this topic and update their local in-memory trees asynchronously. To handle server crashes, the Quadtree can be periodically serialized and saved to disk or Blob Storage (S3), allowing a restarting server to load a recent snapshot before playing the Kafka log to catch up.

Bottlenecks & Solutions

If we eventually exceed single-machine memory (e.g., tracking billions of moving people instead of static businesses), we must partition the Quadtree. We can partition by Region (e.g., Server A handles North America, Server B handles Europe). However, a user searching exactly on the border of two regions requires querying both servers and merging the results. Alternatively, we can use a Geohash to shard the data uniformly across a cluster of nodes.

Interview Follow-up Questions

Q: How would this design change for a ride-sharing app (like Uber) where locations update every few seconds?

Updating a Quadtree every 3 seconds for millions of drivers is too write-heavy; the tree would constantly be splitting and merging, causing lock contention. Instead, we'd use a Grid-based or Geohash approach stored in a highly concurrent memory store like Redis, partitioning the drivers by Geohash, and accepting slightly lower read accuracy in exchange for massive write throughput.

Q: How do you handle pagination for nearby results?

Pagination based on distance requires calculating the distance for all matches and sorting them. We can fetch an over-provisioned list of IDs from the Quadtree (e.g., top 100), sort them by true distance on the application server, and return the first 20. For the next page, we use a cursor indicating the last distance seen.