Design a Rate Limiting for Expedia

Question

Design a event-driven rate limiting system that handles millions of requests. Discuss trade-offs in consistency, availability, and performance.

Codemia · Accepted Answer

Before diving into the architecture, clarify the scope with the interviewer. For Rate Limiting for Expedia, key functional requirements include: what are the core user actions? What data needs to be stored and retrieved? What are the read vs write patterns?

Non-functional requirements to discuss: target latency (sub-100ms for reads?), availability target (99.99%?), consistency model (strong vs eventual), expected scale (DAU, QPS, storage growth rate), and geographic distribution.

Estimate the scale to drive design decisions. Assume 100M DAU with an average of 10 actions per user per day = 1B requests/day ~ 12K QPS average, ~36K QPS peak (3x). For storage, estimate the average object size and multiply by daily new objects. Factor in 3-5 years of growth.

Key numbers to derive: read QPS, write QPS, storage per year, bandwidth requirements, and cache size (following the 80/20 rule, cache 20% of daily reads).

The system consists of several key components:

1. **API Gateway / Load Balancer**: Entry point for all client requests. Handles authentication, rate limiting, and request routing.

2. **Application Servers**: Stateless service layer that processes business logic. Horizontally scalable behind the load balancer.

3. **Database Layer**: Primary data store. Choose based on access patterns - SQL (PostgreSQL) for relational data with ACID requirements, NoSQL (DynamoDB/Cassandra) for high-throughput key-value access.

4. **Cache Layer**: Redis or Memcached for frequently accessed data. Reduces database load by 80-90% for read-heavy workloads.

5. **Message Queue**: Kafka or SQS for async processing - decouples producers from consumers and handles traffic spikes gracefully.

Design the core data entities and their relationships. Consider the primary access patterns to choose between normalized (SQL) and denormalized (NoSQL) schemas.

For the primary entity, define the partition key carefully - it determines data distribution and query performance. Use composite keys for range queries. Add secondary indexes for alternative access patterns, but be mindful of write amplification.

For large objects (images, videos), store in object storage (S3) and keep only metadata in the database.

**Consistency vs Availability**: For Rate Limiting for Expedia, eventual consistency is usually acceptable for read paths (stale data for a few seconds is fine), but writes may need stronger guarantees depending on the use case.

**SQL vs NoSQL**: SQL provides ACID transactions and flexible querying. NoSQL offers better horizontal scaling and higher write throughput. Many systems use both - SQL for transactional data, NoSQL for high-scale reads.

**Push vs Pull**: For real-time features, consider WebSockets (push) for active users and polling (pull) for less active users. Hybrid approaches work well at scale.

**Sharding Strategy**: Shard by user ID or entity ID using consistent hashing. This distributes load evenly and handles node additions/removals gracefully.

**Multi-Region Deployment**: Deploy in multiple regions for lower latency and disaster recovery. Use leader-follower replication with async replication across regions. Handle conflicts with last-write-wins or CRDTs.

**Performance Optimization**: Use CDN for static content, connection pooling for database connections, batch processing for bulk operations, and circuit breakers for fault isolation.

Design a Rate Limiting for Expedia

Expedia

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 Clarification

Capacity Estimation

Submit Your Answer

Expedia Software Engineer Interview Guide

Related Questions

Design a large-scale Image Processing Platform

Design a real-time Feed Generation System

Design Analytics Infrastructure for global users

Design a URL Shortening Service

Architect a event-driven Load Balancing Engine