System Design: Local Search (Google Maps-style)

Requirements

Functional Requirements:

• Return nearby businesses, restaurants, and points of interest for a query and location
• Support radius-based search ("within 5 miles") and bounding box queries
• Rank results by relevance, distance, rating, and business hours
• Support real-time business data (open/closed status, wait time)
• Handle 200+ million business listings globally
• Support map tile rendering with POI overlays at multiple zoom levels

Non-Functional Requirements:

• P99 latency under 100ms
• Handle 200,000 local search QPS globally
• Location data updated within 5 seconds of changes
• 99.99% availability
• Support global scale with region-specific data centers

Scale Estimation

Google Maps indexes ~200 million businesses globally. At 2 KB metadata per business (name, address, categories, hours, rating, phone), the catalog is 400 GB. Geospatial indexes are compact: a 64-bit S2 cell ID per business requires just 1.6 GB for 200 million records. At 200,000 QPS, each query triggers a geospatial lookup (fast, in-memory) plus a text relevance score (Elasticsearch). Assuming 200 businesses per result set, ranking 200 businesses per query at 200,000 QPS requires scoring 40 million (query, business) pairs/sec.

High-Level Architecture

The system consists of a geospatial index for proximity filtering, a full-text index for keyword matching, and a ranking engine that combines proximity, relevance, and quality signals. A location service resolves user locations (GPS coordinates → canonical location context). A business data service maintains the authoritative business catalog and propagates updates. A map tile service renders visual map tiles with POI markers independently from search.

Geospatial search uses S2 geometry library. The Earth is recursively subdivided into a hierarchy of S2 cells (cells at level 12 ≈ 3.7 km², level 14 ≈ 0.23 km²). Each business is assigned to its S2 cell at levels 10–14. A search radius is covered by a set of S2 cells at the appropriate level (a "cell union" covering the radius polygon). A lookup retrieves all businesses in any of those cells from an in-memory cell-to-business index. This initial proximity filter returns candidates (typically 200–500 businesses within a 10km radius) that are then ranked.

Keyword matching is handled by Elasticsearch, with business name, categories, and address as text fields. For a query like "Italian restaurant", the text query matches on categories:Italian and name:restaurant. The geospatial filter is applied as a geo_distance filter in Elasticsearch, taking advantage of its built-in geospatial support with geo_point fields indexed using BKD-tree (block k-d tree) for efficient radius queries. The combined query (text + geo filter) runs in Elasticsearch, returning pre-filtered, text-relevant candidates that are then passed to the ranking engine.

Core Components

S2 Cell Geospatial Index

Google's S2 library represents Earth as the surface of a unit sphere, mapped to a Hilbert space-filling curve that assigns each point a 64-bit S2 cell ID. Spatially close points have numerically close cell IDs in the Hilbert curve, enabling efficient range scans. The in-memory cell index is a B-tree or sorted array of (S2_cell_id, business_id) pairs. A radius query computes the covering cell union (20–30 cells at the appropriate level), then does a range scan per cell. Total scan cost for a 5km radius search is ~1ms. Cells at different levels are precomputed for each business, stored as a composite key enabling multi-resolution queries.

Ranking Engine

Local search ranking balances five signals: (1) Distance — businesses closer to the user score higher, using a log-decay function (5m scores much higher than 50m; 50m vs. 500m is a smaller gap). (2) Text Relevance — BM25 score of query against business name, categories, and description. (3) Quality — composite of star rating, review count, business age, and claimed/verified status. (4) Openness — businesses currently open score a boost; businesses with "open now" filter applied are excluded if closed. (5) Personalization — user's past visit history and category preferences provide lightweight re-ranking boosts. A gradient-boosted model (LambdaMART, ~200 trees) combines these signals, trained on implicit feedback from click and navigation logs.

Real-Time Business Status

Open/closed status and wait times change frequently (hourly for business hours, minute-by-minute for real-time wait times). A dedicated Business Status Service computes open/closed status from business_hours + current_time + special_hours (holidays). Status is precomputed for the next 24 hours and cached per business. Changes to business hours trigger an async update job. Real-time signals (wait times from Google Maps reports, live busyness from opt-in device location aggregation) are written to Redis (TTL: 15 minutes) and fetched during ranking. These real-time signals are not stored in Elasticsearch due to update frequency.

Database Design

Business data is stored in Spanner (or CockroachDB for open-source) for global consistency: (business_id, name, address, lat, lng, categories, phone, website, hours, rating, review_count, verified). The geospatial index is maintained as a sorted array in memory (loaded from Spanner on startup, refreshed on writes). Elasticsearch stores business text data and geo_point coordinates for combined text + geo queries. Review data lives in a separate reviews service (Cassandra, partitioned by business_id). User location history is stored in a privacy-compliant store with 90-day retention and opt-in consent tracking.

API Design

Scaling & Bottlenecks

At 200,000 QPS globally, the geospatial computation is the lightest part (in-memory, 1ms). The Elasticsearch geo+text query takes 10–30ms per shard. With 20 shards covering the business index, each shard handles 10,000 QPS. The ranking engine (gradient-boosted model, 200 candidates per query) takes 5–10ms. Total pipeline: 50–80ms, within the 100ms budget. For global deployments, region-specific Elasticsearch clusters (US, EU, APAC) each serve their geographic subset, reducing cross-region latency. Global load balancers route requests to the nearest regional cluster.

Hot spots occur around major cities: New York, London, and Tokyo generate disproportionate query volumes. Within each regional cluster, shards covering dense urban areas receive much higher QPS than rural shards. Dynamic shard splitting (split popular geo cells into sub-shards) or assigning more replicas to urban-area shards handles geographic hot spots. An in-process result cache (LRU, keyed by geohash + query) with 30-second TTL absorbs 20–30% of repeat queries for popular areas ("coffee near Times Square" recurs thousands of times per hour).

Key Trade-offs

• S2 cell size vs. precision: Coarser cells (level 12, 3.7 km²) mean fewer cells in a radius union (faster) but return more irrelevant businesses outside the exact radius; finer cells improve precision at the cost of larger cell unions
• Real-time business data vs. index consistency: Storing live signals (wait time, open/closed) in the search index would require constant reindexing; the overlay pattern (Redis lookup during ranking) is more efficient but adds a network hop
• Regional vs. global index: Per-region indices reduce cross-region latency and simplify GDPR compliance but require separate operational overhead and complicate cross-border searches ("restaurants near the French-German border")
• Distance vs. quality ranking: Pure distance ranking returns the closest businesses regardless of quality; pure quality ranking ignores proximity entirely; learned combination with distance decay captures user intent most accurately