Loading...
Requirements
Functional Requirements:
Interception: Needs to intercept incoming requests to the server
Cache Mechanism:
- Cache hit: Return data from cache
- Cache miss: Retrieve data from Server, store it in cache and return data to client
Eviction: If Cache becomes full, come up with a mechanism to evict data (Ex: LRU)
Invalidation: Provide APIs to manually invalidate cache data.
Expiration: Implement TTL for cache entries
Concurrency: Needs to handle multiple reads and writes possibly to the same key
Non-Functional Requirements:
Low Latency: Return data to client with minimal latency
High Availability: Cache needs to be up all the time, so that it doesn't become a SPOF
Scalability: Needs to be able to scale according to the increasing traffic/volume
Consistency: Refresh data eventually to ensure data freshness
API Design
Since this is a Reverse Proxy, the main interface is HTTP along with Management APIs
Proxy Interface
Input: GET /resources?id=123
Headers: Cache-Control (public, max-age=3600), If-None-Match (return 304 no update), Accept-Encoding
Management APIs (Internal)
Used by Admin for monitoring and Purging purposes
// Remove specific Key
POST /resources/purge {url: "xyz"}
// Removes all tags associated with the Key
POST /resources/purge-tags {tag: "product-updates"}
// stats like cache hit, memory usage, eviction count
GET /resources/stats
Storage/Data-Model
We need a high performance in memory key value store
Cache Key Structure
Key needs to uniquely identify the resource
HASH (http method + scheme + host + query params)
Note: If data changes by the user (gzip, other), Accept-Encoding will also be part of the key
Cache Value Structure
we will store binary content of the data and metadata to manage the lifecyle
{
"key": "1asdas313d..",
"content_binary": "asdasd",
"content_type": "text/xml",
"headers" : {
"ETag" : "asdasd565",
"Vary": "Accept-Encoding"
},
"created_at": "134523",
"expires_at": "45656",
"access_count": 50 // for LFU eviction
}
High-Level Design
Data flow
- Incoming Request: Client sends a request to Load Balancer
- Hashing/Routing: Load Balancer applies Hashing and routes request to a Cache Node
- Local Lookup:
- Hit: Return data to client
- Miss: Checks local RAM
- Node creates "Lock" for this Key (to prevent stampedes)
- Retrieves data from Origin Server
- Saves data to RAM (optionally SSD)
- Returns data to client
Detailed Component Design
Cache Node Internals
Request Coalescing
Cache stampede - If a hot key gets evicted, and multiple requests come for same key, it will bombard the Origin Server
Solution: Use SingleFit Pattern
- request 1 requests for non existent data, cache creates that entry and requests data from origin server
- request 2 requests for same data and notices that the data exists in entry and waits for the data
- request 1 gets the data from origin and notifies all waiting requests
Eviction Policy
Implement LRU using Map and Doubly Linked List
- Map: Key -> Node Pointer
- Doubly Linked List -
- On Access: Key added to the head of the list
- On Insert (Cache full): Remove Node from Tail, delete from Map, add new data to the head
- Concurrency: To avoid locking entire cache for each read/write, we partition the data into segments.
Tiered Storage
- Tier-1: Extremely fast, store hot data in RAM (16 GB)
- Tier-2: Not as fast as RAM, but still fast, it can hold upto 1 TB.
Distributed Scaling
To distribute Keys across multiple Nodes, we can follow
Consistent Hashing
- Map Key into the Hash Ring.
- Hash request to find its position on the ring.
- Walk clockwise to find the owner of the key
Benefit: We only need to remap 1/N keys on addition or deletion of a node.
Virtual Nodes
- To prevent Hot Nodes, each physical server is hashed multiple times and scattered around the ring
Consistency
TTL (Lazy): Every Object has a max-age, Cache checks if CurrentTime > ExpiresAt before serving. Making it eventually consistent.
Efficiency
Conditional GET:
When TTL expires, Cache gets data from Origin on conditional basis to save bandwidth. Add header If-None-Match:
Bottlenecks
- Memory Limits: RAM is expensive and can get full. Mitigation: Robust LFU/LRU policies and SSD tiering
- Network Bandwidth: Node's NIC can get saturated. Mitigation: Data compression to reduce volume
- Hot Keys: A popular resource can get multiple requests. Consistent hashing will route all requests to same node. Mitigation: Split hot keys across replicas.