Distributed Cache

What is Cache?

A cache temporarily stores frequently accessed data in memory.
It serves data faster than querying the database.

How it works?

Cache Hit: Data is found in the cache and served quickly.
Cache Miss: Data is retrieved from the database and added to the cache for future requests.

Why Cache is Useful?

A cache is required to reduce latency and improve system performance by storing frequently accessed data in fast memory, minimizing the load on the database.

What is a Distributed Cache?

A distributed cache is a system where multiple servers coordinate to store frequently accessed data, ensuring scalability and high availability.

Benefits of Distributed Cache:

Faster Access & Reduced Latency: Speeds up responses by storing frequently accessed data closer to the application.
Improved Availability: Ensures data is served even if the main database is temporarily down.
Reduced Load: Offloads expensive database queries, decreasing pressure on the database and network traffic.
Stores Session Data: Temporarily stores user session data for smoother interactions.
Cuts Network Costs: Uses local resources to minimize data transfer over the network.

Caching at Different Layers of a System

System Layer	Technology in Use	Usage
Web	HTTP cache headers, web accelerators, key-value store, CDNs, etc.	Accelerate retrieval of static web content, and manage sessions
Application	Local cache and key-value data store	Accelerate application-level computations and data retrieval
Database	Database cache, buffers, and key-value data store	Reduce data retrieval latency and I/O load from database

Types of Cache Writing Policies

Write-Through:

Data is written to the cache and the backing store simultaneously.
Ensures consistency between the cache and the backing store.
Keeps the cache updated with the latest data.
Higher latency for write operations as both cache and backing store are updated.
Systems where consistency is critical (e.g., financial systems).

Write-Around:

Data is written directly to the backing store, bypassing the cache.
Cache is updated only on subsequent reads (if a cache miss occurs).
Reduces cache write operations, useful for data rarely read after writing.
Can lead to higher read latency due to cache misses.
Systems where write-heavy workloads dominate (e.g., log storage).

Write-Back:

Data is written to the cache first and asynchronously updated to the backing store later.
Faster write operations as data is written to cache only.
Reduces the load on the backing store.
Risk of data loss if the cache fails before the data is written back to the store.
Systems prioritizing write performance (e.g., real-time analytics).

Eviction Policies in Cache

Eviction policies are strategies used by caching systems to decide which data to remove when the cache reaches its storage limit.

Least recently used (LRU): Removes the data that has not been accessed for the longest time.
Most recently used (MRU): Removes the most recently accessed data.
Least frequently used (LFU): Removes the data accessed the least number of times.
Random Replacement: Randomly selects data to remove when the cache is full.
Time-to-Live (TTL): Automatically removes data after a specified time.

Cache invalidation

Some cache data may become outdated over time, making it invalid and requiring removal. To identify such stale entries, metadata like a time-to-live (TTL) value is stored with each cache item, ensuring outdated data is automatically deleted.

We can use two different approaches to deal with outdated items using TTL:

Active expiration: This method actively checks the TTL of cache entries through a daemon process or thread.
Passive expiration: This method checks the TTL of a cache entry at the time of access.

Storage Mechanism in Distributed Cache

Data Placement Across Cache Servers:

Decide which data goes to which cache server using hashing algorithms.
Use consistent hashing to handle crashes or scaling efficiently.

Locating Data Inside a Cache Server:

Use typical hash functions to find specific cache entries.
Hashing helps locate data but doesn’t manage eviction or storage strategies.

Data Structure for Cache Storage:

Use a doubly linked list for simplicity and efficiency.
Supports constant-time operations for adding/removing data.

Bloom Filters for Quick Checks:

Use bloom filters to check if data is absent in the cache.
Useful in large caching systems for quick lookups (with some probabilistic errors).

Sharding in cache clusters

To avoid SPOF and high load on a single cache instance, we introduce sharding. Sharding involves splitting up cache data among multiple cache servers. It can be performed in the following two ways.

Dedicated Cache Servers: Separate cache from application servers for flexible scaling.
Co-located Cache: Combine cache and service on the same host to reduce hardware costs.

High-level Design of a Distributed Cache

Functional Requirement:

Insert Data: Users should be able to add an entry to the cache.
Retrieve Data: Users should be able to fetch data using a specific key.

NonFunctional Requirement:

High Performance: Cache should allow quick data retrieval and fast insertions.
Scalability: The cache system must handle more requests as it grows without slowdowns.
High Availability: The cache should remain accessible even during failures or high traffic.
Consistency: Data in the cache must be accurate and up-to-date across all servers.
Affordability: The caching system should be built with cost-effective hardware.

API Design:

Insertion:

insert(key, value)

Retrieval:

retrieve(key)

Cache Client:

This is a library in the application servers that holds information about cache servers.
It uses hashing and search algorithms to select the appropriate cache server for data insertion or retrieval.
All cache clients must have the same view of cache servers and follow the same method for moving data to and from the servers.

Cache Server:

These servers store and manage the cache data.
All cache clients can access any cache server, and each server is connected to a database for data retrieval or storage.
Cache clients use protocols like TCP or UDP to communicate with the cache servers.
If a cache server goes down, clients treat it as a missed cache and handle the request accordingly.

Some challenges:

How the cache client to realize the addition or failure of a cache server.

Solution: To solve this, we can use a configuration service that constantly monitors the health of cache servers. The cache clients will be notified automatically when a new cache server is added or if there’s a failure. This way, no manual monitoring is needed, and the cache clients can always get an updated list of available cache servers from the configuration service.

How can we address the single point of failure (SPOF) issue caused by having a single cache server for each data set, and how can we improve performance when certain data (hotkeys) are frequently accessed?

Solution: A simple solution is to add replica nodes, starting with one primary and two backup nodes in each cache shard. To prevent inconsistencies, we perform synchronous writes over replicas when they are in close proximity. By dividing cache data into shards, we can avoid issues of unavailability and ensure efficient use of hardware resources.

How Internal Working of cache server

Solution: Each cache client should use three mechanisms to store and evict entries from the cache servers:

Hash map: The cache server uses a hash map to store or locate different entries inside the RAM of cache servers. The illustration below shows that the map contains pointers to each cache value.
Doubly linked list: If we have to evict data from the cache, we require a linked list so that we can order entries according to their frequency of access. The illustration below depicts how entries are connected using a doubly linked list.
Eviction policy: The eviction policy depends on the application requirements. Here, we assume the least recently used (LRU) eviction policy.

Detail Desigh

Client requests are routed through load balancers to cache clients on service hosts.
Cache clients use consistent hashing to identify and forward requests to the appropriate cache server.
Cache servers use primary and replica setups with the same mechanisms for storing and evicting entries.
A configuration service ensures clients have an updated view of cache servers.
Monitoring services track and report caching service metrics.

Memcached vs Redis

Feature	Memcached	Redis
Data Structure	Key-value store (string-based)	Supports multiple data structures (strings, lists, sets, sorted sets, hashes, etc.)
Persistence	No persistence, in-memory only	Supports persistence (RDB snapshots, AOF logs)
Eviction Policies	Least Recently Used (LRU), Least Frequently Used (LFU), etc.	LRU, LFU, volatile TTL, etc.
Memory Management	Memory allocated dynamically	Supports configurable memory limits with eviction options
Replication	No native replication support	Supports master-slave replication
Clustering	No native clustering support	Supports clustering for horizontal scalability
Data Expiration	Supports time-to-live (TTL) for cache expiry	Supports TTL, but with more advanced expiry options
Use Cases	Simple caching, session storage	Advanced caching, pub/sub, real-time analytics, queues, and more
Performance	Fast for simple key-value operations	Fast, but with more overhead for advanced data structures
Community and Ecosystem	Large community, widely adopted	Large community, highly active, many advanced tools and libraries