Design Memcached

Question

Design a distributed in-memory caching system like Memcached. Cover consistent hashing, cache eviction policies, replication strategies, and handling cache stampedes. This is a common Meta E6+ infrastructure question.

Codemia · Accepted Answer

### Functional Requirements:
1. **Key-Value Storage**: The system should allow users to store and retrieve arbitrary key-value pairs.
2. **Scalability**: The system must support horizontal scaling to handle increasing load by adding more nodes.
3. **High Availability**: The system should ensure that data is accessible even if some nodes fail.
4. **Cache Eviction**: It should support various cache eviction policies such as LRU (Least Recently Used) and LFU (Least Frequently Used).
5. **Consistent Hashing**: The system should implement consistent hashing to distribute keys evenly across nodes.
6. **TTL Support**: Users should be able to set a Time To Live (TTL) for cached entries.

### Non-Functional Requirements:
1. **Performance**: The system should have a read and write latency in the sub-millisecond range.
2. **Data Consistency**: The system should maintain eventual consistency among replicas.
3. **Fault Tolerance**: The system should continue to function correctly in the event of node failures.
4. **Monitoring**: The system should provide metrics and logging for monitoring cache hit/miss rates and system health.

Assuming Meta has approximately 1 billion daily active users (DAUs) and each user generates around 1 KB of cacheable data:
- **Daily Cache Size**: 1 billion users * 1 KB = 1 TB of cacheable data per day.
- **Required Cache Size**: If we aim to cache 10% of the daily data, we would need 100 GB of cache at any given time.
- **Cache Hits**: If we assume a 90% cache hit ratio, we would expect around 900 million cache hits daily. 
- **Operational Load**: Assuming a 1:1 read/write ratio, we would have approximately 1.8 billion operations (reads + writes) per day, leading to about 20,000 operations per second (OPS). 
This allows us to assess the node requirements, estimating that each node can handle around 10,000 OPS, leading to a need for at least 2 nodes for handling peak loads.

### Component Diagram:
- **Client Layer**: Applications making cache requests.
- **Load Balancer**: Distributes incoming requests to cache nodes.
- **Cache Nodes**: 
  - Each node stores a portion of the cached data using a consistent hashing algorithm.
  - Nodes use Redis or a similar in-memory database for fast access.
- **Replica Nodes**: For high availability, each primary cache node has one or more replicas.
- **TTL Manager**: Handles expiration of cached entries.
- **Monitoring Service**: Tracks cache performance metrics.

### Technology Choices:
- **In-Memory Store**: Redis for its speed and data structures.
- **Consistent Hashing**: Implemented using a library like `hash_ring` in Python.
- **Load Balancer**: NGINX or HAProxy for request distribution.
- **Monitoring**: Prometheus or Grafana for tracking metrics and alerts.

### Schema Design:
- **Key-Value Storage**: Each entry in the cache can be represented as follows:
  - **Key**: STRING (e.g., `user:1234:session`)
  - **Value**: BLOB (binary data, can be JSON or any serialized format)
  - **TTL**: INTEGER (time-to-live in seconds)
  - **CreatedAt**: TIMESTAMP (when the entry was created)
  - **LastAccessed**: TIMESTAMP (when the entry was last accessed)

### Access Patterns:
- **Read Operation**: Retrieve the value associated with the key, check TTL, and return the value if it hasn't expired.
- **Write Operation**: Insert or update the key-value pair, setting the TTL and timestamps.

1. **Consistency vs. Availability**: Given the CAP theorem, we prioritize availability and partition tolerance over strong consistency. This means some reads may return stale data, but the system remains operational during node failures.
2. **Eviction Policy**: Choosing between LRU and LFU involves trade-offs in complexity and performance. LRU is simpler and faster to implement, but LFU might yield better cache hit ratios for frequently accessed data.
3. **Replication Strategy**: We opt for asynchronous replication for faster writes but risk temporary inconsistencies. Synchronous replication would ensure consistency but at the cost of write performance.
4. **Load Balancing**: Using a consistent hashing approach simplifies node addition/removal but can lead to uneven load distribution if not managed properly. This necessitates periodic rebalancing of keys across nodes.

Design Memcached

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