System Design Interview: Proximity Service (Like Yelp) Experience

Functional Requirements * Search: Users can search for nearby places (restaurants, gyms, events) or people based on current location. * Filtering: Support for filters including distance, c

Functional Requirements * Search: Users can search for nearby places (restaurants, gyms, events) or people based on current location. * Filtering: Support for filters including distance, category, ratings, open status, and personalized recommendations. * Place Details: Users can view business information, photos, reviews, and ratings. * Management: Business owners can add, edit, or claim listings; users can add reviews. * Bookmarks: Users can save favorite locations. Non-functional Requirements * Latency: Millisecond-level search responses. * Scalability: Support for millions of users and tens of millions of locations. * Availability: High availability (99.99% uptime). * Consistency: Eventual consistency is acceptable for new locations, updates, and reviews. Capacity Estimation * Traffic: 50M MAU, 10M DAU. Average 5 searches/user/day. Peak QPS ~100,000. * Volume: 5M reviews/day, 100k new places/day. * Storage: * 100M listings (~200 GB total). * 1B historical reviews (~1 TB total). * Photos (5 per business) (~100 TB total). * 100M favorites (~5 GB total). API Design * GET /search?lat&lon&radius&category&open_now: Returns sorted list of nearby locations. * GET /place/:id: Retrieves specific place details. * POST /review/:placeId/add: Submits a new review. * POST /place/add: Business owners list a new location (name, coordinates, category, photos). * PUT /place/:id/edit: Updates listing details. * POST /place/:id/claim: Verifies ownership of an existing listing. High-Level Architecture * Client: Mobile/Web interfaces for searching and management. * API Gateway: Handles auth, routing, throttling, and monitoring. * Cache: In-memory storage for hot searches and trending zones. * Load Balancer: Distributes traffic to app servers. * App Servers: Business logic for listings, reviews, and search coordination. * Message Queue (Kafka/Redis): Asynchronous processing for search index updates. * Database: Persistent storage for user profiles and business data. * Media Storage: Blob storage/CDN for images. * Segments Producer: Ingests third-party map data (e.g., Google Maps) and divides the world into segments to narrow search scope. * QuadTree Servers: Stores spatial indexes of places; finds locations within a radius. * Aggregators: Collects results from QuadTree servers, ranks them, and returns the final list to the user. Workflows Flow-1: Business Listing 1. Owner submits details via /place/add. 2. Listing Service validates data and stores geo-indexed location. 3. Media Service links uploaded photos to the place. 4. Admin Service reviews/approves the listing. 5. Listing becomes searchable upon approval. Flow-2: Proximity Search 1. User requests /search. 2. Gateway routes to Geospatial Search Service. 3. Search Service queries QuadTree servers for places within the radius. 4. QuadTree servers return candidates to Aggregators. 5. Aggregators filter, rank (proximity + popularity), and return results with metadata. Flow-3: Review Submission 1. User posts to /review/:placeId/add. 2. Review Service validates, stores review, and updates average rating. 3. Review is displayed after moderation (if flagged). Flow-4: Media Handling 1. Uploads are stored in object storage via Media Service. 2. Read requests fetch media URLs served via CDN. Component Deep Dive: Searching Strategy SQL Solution * Stores latitude/longitude in indexed columns. * Uses range queries to find points within a coordinate box. * Limitation: Inefficient at scale (e.g., 500M places). Independent indexes on lat/lon result in large candidate sets requiring costly intersection operations. Static Grids * Map is divided into fixed-size grids; each place has a GridID. * Queries search the target grid and its 8 neighbors. * Limitation: Static grid sizes handle uneven data distribution poorly. Dense areas (e.g., NYC) overload a single grid, while sparse areas (e.g., Pacific Ocean) waste resources. Dynamic Grids (QuadTree) * A tree structure where each node represents a spatial region. * Nodes subdivide into four quadrants when the number of places exceeds a threshold (e.g., 500). * Mechanism: * Leaf Nodes: Hold specific lists of places. * Root: Covers the whole world. * Traversal: Search navigates down the tree to the leaf node covering the user's location. * Neighbors: Leaf nodes are connected via a doubly linked list, allowing expansion of the search radius to neighboring grids without re-traversing the root. * Memory Efficiency: * 500M places * 12 bytes (ID + coords) ≈ 12 GB. * 1M leaf nodes (500 places per leaf) + internal nodes ≈ negligible overhead. * The entire index fits in the RAM of a modern server (~12 GB). Ranking Search Results * Popularity Score: Aggregated from ratings (stored in DB and cached in QuadTree nodes). * Execution: QuadTree leaf nodes return the top 100 places sorted by popularity within the spatial radius. * Aggregation: The central aggregator merges lists from relevant leaf nodes to form the final result. * Updates: Popularity scores in the QuadTree are updated via batch processing (off-peak) to prevent locking and performance degradation during high-traffic reads. Replication and Fault Tolerance * Master-Slave Architecture: Writes go to the Master; Reads are distributed to Slaves. Eventual consistency applies. * Failover: If the Master fails, a Slave is promoted. * Rebuilding (Reverse Index): * If a QuadTree server fails entirely, rebuilding by scanning the whole DB is too slow. * Solution: A separate "QuadTree Index Server" maintains a reverse index (ServerID -> Set of PlaceIDs). * When a server is replaced, it queries the Index Server to know exactly which places to load from the DB. Data Partitioning * Region-Based Sharding: * Places grouped by zip code/geography. * Pros: Preserves spatial locality. * Cons: Hotspots (e.g., downtown areas) cause uneven server load. * LocationID Sharding (Hash-Based): * Places distributed uniformly based on hash of LocationID. * Pros: Even load distribution. * Cons: Every search query must be broadcast to all shard servers to find nearby places, increasing network traffic and latency. * Conclusion: Region-based sharding is generally preferred, using consistent hashing or re-partitioning to handle hotspots.