Design a geo-distributed Recommendation System

Question

Design a geo-distributed recommendation system that handles millions of requests. Discuss trade-offs in consistency, availability, and performance.

Codemia · Accepted Answer

### Functional Requirements:
- **Real-time Recommendations**: Generate personalized property recommendations based on user behavior, preferences, and location.
- **User Profiles**: Store and update user profiles including interactions, saved properties, and search history.
- **Geo-Location Services**: Utilize geo-coordinates to filter recommendations based on user proximity to listings.
- **Feedback Mechanism**: Allow users to provide feedback on recommendations to improve future suggestions.

### Non-Functional Requirements:
- **Scalability**: The system must handle up to 10,000 QPS during peak times, with potential growth as user base increases.
- **Availability**: Aim for 99.99% uptime to ensure recommendations are always accessible, especially during peak real estate seasons.
- **Latency**: Recommendations should be generated in under 200 milliseconds to ensure a smooth user experience.
- **Data Consistency**: Offer eventual consistency for user feedback to allow for high availability without sacrificing performance.

### Back-of-Envelope Calculations:
- **Users**: Assume 1 million active users, each sending 10 requests per day for recommendations.
- **QPS Calculation**: 1,000,000 users x 10 requests/day = 10,000,000 requests/day.
  - This translates to approximately 115 QPS (10,000,000 requests / 86,400 seconds).
  - Peak usage can be estimated at 100-200 QPS during high traffic times (weekends, holidays).
- **Storage Requirements**: Assuming each user profile with recommendations takes about 1KB, the total storage for user profiles would be:
  - 1 million users x 1 KB/user = 1 GB.
- **Data Growth**: Anticipate a growth rate of 10% annually for user base and recommendations.

### Component Diagram:
- **Load Balancer**: Distributes incoming requests to multiple application servers.
- **Application Servers**: Handle business logic for recommendation generation (using Node.js).
- **Recommendation Engine**: A microservice built with Python using machine learning models for generating recommendations based on user data.
- **Cache Layer**: Redis for fast access to frequently requested data (user profiles, recent searches).
- **Database**: MongoDB as the primary data store for user profiles and interactions, chosen for its flexibility and scalability.
- **Asynchronous Processing**: Use Apache Kafka for handling feedback and batch processing to update recommendations periodically.
- **Monitoring**: Prometheus and Grafana for real-time monitoring and alerting on system health and performance.

### Schema Design:
- **User Profile Collection** (MongoDB):
  - `userId`: String (unique identifier)
  - `location`: GeoJSON (for geo-based queries)
  - `preferences`: Array of Strings (user preferences)
  - `searchHistory`: Array of Objects (timestamp, propertyId)
  - `recommendations`: Array of Objects (propertyId, score)

- **Feedback Collection**:
  - `userId`: String
  - `propertyId`: String
  - `feedbackType`: String (like/dislike)
  - `timestamp`: Date

### Access Patterns:
- Frequent reads for user profiles and recommendations, occasional writes for feedback and updates to profiles.

### Architectural Decisions:
- **Consistency vs. Availability**: Chose eventual consistency for the feedback mechanism to ensure high availability of recommendations. This allows the system to remain responsive even if some data is stale.
- **Database Selection**: Opted for MongoDB for its scalability and schema flexibility, but it comes with trade-offs in consistency compared to traditional SQL databases.
- **Caching Strategy**: Implemented Redis for caching frequently requested data to reduce database load and improve response times, though it introduces the challenge of cache invalidation.
- **Partitioning Strategy**: User data will be partitioned based on geographic regions to ensure data locality, reducing latency for users requesting recommendations in their vicinity. This may complicate cross-region queries but enhances performance.
- **Failure Handling**: Implemented circuit breakers in the microservices architecture to handle failures gracefully and fallback mechanisms to ensure users still receive relevant recommendations even when parts of the system are down.

Design a geo-distributed Recommendation System

Zillow

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Practice a Similar Problem on Codemia

Sample Answer

Requirements

Functional Requirements:

Capacity Estimation

Back-of-Envelope Calculations:

Submit Your Answer

Zillow 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