Requirements

Functional Requirements

• Search for businesses near a location (lat, lng, radius)
• Return results sorted by distance
• Business details (name, address, hours, rating)
• Search by category (restaurants, cafes, etc.)
• Add/update/remove business locations
• Filter by open hours, rating, price range

Non-Functional Requirements

• Latency: Search results in < 200ms
• Scale: 100M businesses, 10K QPS
• Accuracy: Results must be within specified radius
• Freshness: Location updates reflected within 1 minute
• Availability: 99.99%

Back-of-the-Envelope Estimation

Geospatial Indexing

Geohashing

Query Algorithm

High-Level Architecture

Database Schema

CREATE TABLE businesses (
    id          UUID PRIMARY KEY,
    name        VARCHAR(200),
    address     TEXT,
    latitude    DECIMAL(10, 8),
    longitude   DECIMAL(11, 8),
    geohash     VARCHAR(12),
    category    VARCHAR(50),
    rating      DECIMAL(2, 1),
    open_hours  JSONB,
    created_at  TIMESTAMP
);

CREATE INDEX idx_geohash ON businesses(geohash);
CREATE INDEX idx_category ON businesses(category);

Caching Strategy

Cache popular geohash cells:

• Cache key: geo:{geohash_6}:{category}
• Cache value: List of business IDs sorted by rating
• TTL: 5 minutes (balance freshness vs. performance)
• Cache hit ratio target: > 80% for popular areas

Practice Exercises

1. Algorithm: Implement geohash encoding from latitude/longitude. What is the precision at 6 characters?

2. Scale: If 100M businesses are distributed globally, estimate the Redis memory needed for geohash indexes at 6-character precision.

3. Optimization: How would you handle a search in a sparse area (no businesses within 5 km)? Design a strategy to expand the search radius dynamically.

4. Real-time: How would you update the geohash index when a business moves to a new location? Design an atomic update strategy.

What to Learn Next