Design a Caching for Cruise

Question

Design a multi-tenant caching system that handles millions of requests. Discuss trade-offs in consistency, availability, and performance.

Codemia · Accepted Answer

### Functional Requirements
1. **Multi-Tenancy**: The caching system should support multiple tenants, isolating their data securely.
2. **Read/Write Access**: The system should allow fast read and write operations for cached data.
3. **TTL Management**: Users should be able to configure Time-To-Live (TTL) for cached items.
4. **Eviction Policies**: Implement various eviction strategies (e.g., LRU, LFU) to manage cache size and priorities.
5. **Monitoring APIs**: Provide APIs for tenants to monitor cache hits, misses, and eviction rates.

### Non-Functional Requirements
1. **Scalability**: The system must handle millions of requests per second with low latency.
2. **Availability**: The caching service should maintain 99.99% uptime.
3. **Consistency**: The system should offer eventual consistency with the option for strong consistency for critical data.
4. **Security**: Ensure data isolation and secure access control for multi-tenant architecture.

Assuming Cruise has around 10 million active users and each user makes an average of 100 requests per day:
- **Total Requests Per Day**: 10,000,000 users * 100 requests = 1,000,000,000 requests/day.
- **Requests Per Second**: 1,000,000,000 requests/day / 86,400 seconds/day ≈ 11,574 requests/second.
- **Cache Size Estimation**: If we assume an average of 1KB of data per request and we want to cache responses for 50% of the requests:
  - **Cache Size**: 11,574 requests/second * 60 seconds * 60 minutes * 24 hours * 0.5 = ~50 TB of cached data per day.

### Component Diagram
1. **API Gateway**: Handles incoming requests and routes them to the appropriate caching service.
2. **Load Balancer**: Distributes requests across multiple caching nodes to ensure even load.
3. **Caching Layer**: 
   - **Redis**: For in-memory caching, providing fast access for frequently queried data.
   - **Memcached**: For lightweight caching of less frequently accessed data.
4. **Persistent Storage**: 
   - **Cassandra**: For storing cache metadata and eviction policies.
5. **Monitoring Service**: Utilizes Prometheus for metrics collection and Grafana for visualization.

### Schema Design
**Cache Item Table** (in Cassandra):
- **tenant_id** (Partition Key): Unique identifier for each tenant.
- **cache_key** (Clustering Key): Unique key for each cached item.
- **data** (Blob): The actual cached data.
- **ttl** (Timestamp): Time-to-live for the cached item.
- **last_accessed** (Timestamp): For tracking eviction policies.

### Access Patterns
- Frequent reads are expected on `cache_key`, while writes will be more sporadic, allowing for efficient read-heavy design.

1. **Consistency vs. Availability**: Opting for eventual consistency allows us to achieve higher availability and lower latency, but may lead to stale reads. This is acceptable for non-critical data.
2. **Performance vs. Cost**: Using Redis for all caching can provide speed but at a higher cost. A hybrid approach with Memcached for less critical data balances performance and cost.
3. **Scalability vs. Complexity**: Implementing sharding for Redis increases scalability but adds complexity in managing shards. We must ensure effective routing of requests to the correct shard.

Design a Caching for Cruise

Cruise

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

Submit Your Answer

Cruise 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