Design a Proximity Service

Question

Design a service to find nearby places, people, or events. Cover geospatial indexing (geohash, quadtree), efficient radius queries, ranking by relevance, and handling location updates at scale.

Codemia · Accepted Answer

### Functional Requirements:
- **Nearby Places**: Users can search for nearby places based on their current location.
- **Nearby People**: Users can find other users within a specified radius.
- **Nearby Events**: Users can discover events happening nearby.
- **Real-time Location Updates**: Support for real-time updates on user locations and event changes.
- **Ranking by Relevance**: Ability to rank results based on user preferences, popularity, and recency.

### Non-Functional Requirements:
- **Scalability**: Must handle millions of users and locations, supporting dynamic scaling.
- **Low Latency**: Query responses should be under 100ms for a seamless user experience.
- **High Availability**: The system should be available 99.9% of the time to ensure users have consistent access.

Assuming Meta has around 3 billion users:
- **Active Users**: 10% (300 million) active users at peak.
- **Location Queries**: If each user makes 5 queries per day, that results in 1.5 billion queries per day, or approximately 17,000 queries per second.
- **Geospatial Data**: Assuming 10 million places, events, and users are indexed, and each user sends a location update every 5 minutes, we can expect about 3 million updates per minute. 
- **Data Storage**: Estimated storage of 1TB for geospatial data and metadata (user profiles, event details).

### Component Diagram:
- **Client App**: Mobile and web clients that interface with the service.
- **API Gateway**: Routes requests to the appropriate microservices.
- **Location Service**: Handles geospatial queries, utilizing a quadtree for efficient radius searches.
- **Geospatial Indexing**: Uses Elasticsearch for indexing and fast querying of geospatial data.
- **User Service**: Manages user profiles and preferences, using PostgreSQL for relational data.
- **Event Service**: Manages event data, utilizing a NoSQL database like MongoDB for flexible schema.
- **Cache Layer**: Redis for caching frequent queries and results, reducing latency.
- **Notification Service**: Sends updates to users for location changes and event announcements.

### Schema Design:
- **User Table**: 
  - `user_id` (UUID, PK)
  - `username` (VARCHAR)
  - `location` (GEOGRAPHY)
  - `preferences` (JSON)

- **Place Table**: 
  - `place_id` (UUID, PK)
  - `name` (VARCHAR)
  - `location` (GEOGRAPHY)
  - `category` (VARCHAR)
  - `popularity_score` (FLOAT)

- **Event Table**: 
  - `event_id` (UUID, PK)
  - `title` (VARCHAR)
  - `location` (GEOGRAPHY)
  - `start_time` (TIMESTAMP)
  - `end_time` (TIMESTAMP)
  - `tags` (ARRAY of VARCHAR)

### Access Patterns:
- Frequent geospatial queries on `location` fields.
- Updates on user location every few minutes.

1. **Choice of Storage**: Using both SQL (PostgreSQL) and NoSQL (MongoDB) allows for structured user data and flexible event data but increases complexity in data management.
2. **Real-time vs. Batch Processing**: Opting for real-time location updates increases system load but provides timely data. A balance must be struck between real-time accuracy and system performance.
3. **Caching Strategy**: Implementing Redis for caching can improve performance but may introduce stale data issues, necessitating a strategy for cache invalidation.
4. **Geospatial Indexing**: Choosing a quadtree for efficient region queries versus a geohash can impact complexity and query performance, requiring careful consideration of query patterns.

Design a Proximity Service

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Requirements

Functional Requirements:

Capacity Estimation

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search