Requirements

Functional Requirements:

The functional Requirements are:

1. PUT (key,value) pair. Meaning be able to add entries to the cache
2. GET (key). Be able to retrieve entries from the cache
3. TTL - Each entry to should be invalidated after a specifc time period
4. Eviction Policy - One should be able to evict entries based on policies like LRU

Non-Functional Requirements:

Here are the non-functional requirements:

1. Scalability - We should be able to support applications web scale. Meaning adding more capacity should be seamless
2. Availability - It should have an uptime by means of adequate redundancy
3. Consistency - Data rendered should not be stale
4. Latency - The system should operate with very minimal latency

API Design

PUT /v1/cache

Request Body:

{

"key": "ExampleKey",

"value": "Examplevalue",

"ttl": 3600

}

Response for success:

{

"status": "success",

"code": 200,

"message": "Entry added/updated"

}

Response for error:

{

"status": "error"

"code": 4xx/5xx

"message": "Invalid Input"

}

GET /v1/cache?key=examplekey

Response for success:

{

"status": "success"

"code": 200

"data": "Examplevalue"

}

Response for failure:

{

"status": "error"

"code": 4xx/5xx

"message": "key not found"

}

A failure is a cache miss which followed by a retrieval from the server itself. Now a corressponsind cache entry is made (lazy loading) so that future requests are served

High-Level Design

The high level Desing consists of the following components:

1. Client - It is the application/user trying to access the websever
2. API Gateway - Providing a unified entry to all the applications and APIs in the system. It also provides Authentication and Authrization services along with rate limiting
3. Cache Client - It is a component that interacts with the cache servers and the cache config manager
4. Webserver - It is the actual server that is hosting th information

Detailed Component Design

CACHING DEEP DIVE

• Information in the cache servers is loaded in the form of key-value pairs
• The best datastructure that can be used to describe this is a hash table
• The caching client has hasing funcitons that takes the keys as input and hashes it to find the location of the cach servers which are on a hash ring. The mechanism used here is consistent hasing so that we can easily add o re remove servers without having to re-disribute a lot of keys
• The cache config manager is a zookeper like service that has details of all the cache servers along with the the location of the values corresponding to keys. Addition or removal of new servers is also recorded here
• The data in the cache needs to be evicted based on alogirithms like LRU. Here the data is organised in the form of a doubly linked list. During the addition of entries in the cache it is should be moved to the head and also the recently accessed data should go to the head. In the single linked list the entire length of the list needs to be traversed which is a waste of resporces. Hence here we use a doubly linked list. Eviction is also easy for the element towards the tail
• The cache servers are geo disctributed take care of the avilablibity
• Also we have servers along with each of the cach servers thar serve as read replicas. In the event of losing the primary server , there is a leader election for the new leader
• The data in the cache servers is sharded based on the keys. This is a range-based sharding.