LLD-8 Distributed Cache (Part-1) Implementing LRU Eviction Strategy from Cach
In this article, we will discuss Distributed Cache and try to implement Consistent Hashing and LRU Cache.
Part 1 has the implementation of the LRU eviction strategy and Part 2 contains the implementation of Consistent Hashing.
Introduction:
👉 In the realm of distributed systems 🚨, the design and implementation of a distributed cache system play a pivotal role in ensuring high availability and scalability for applications. This article ✍️ delves into the intricacies of designing a distributed cache system that encompasses both functional and non-functional requirements.
👉 A Cache is a temporary storage that stores data in memory (most frequently accessed, queries, static files, and responses… depending on the use case) for a small period. Storing data in memory makes retrieval very fast, thus reducing the load on the actual database.
👉 There are many types of cache but the most widely used is Key-Value Cache.
What is Distributed Caching:
👉 Distributed caching is a fundamental concept in modern computing that involves storing data across multiple servers 🛜 or machines ⚙️ to enhance performance and scalability.
Use Cases:
- Application Acceleration: By storing frequently accessed data in a distributed cache, applications can run faster, even during high transaction volumes.
- Web Session Data Storage: Storing user session data in a cache allows for load-balancing web traffic over multiple servers and ensures session data availability.
- Network Cost Reduction: Caching data in multiple locations reduces network traffic, optimizing bandwidth for other applications
- Data Replication: Distributed caching helps reduce the impact of interruptions by allowing data requests even when the source database is unavailable.
- Extreme Scaling: Applications with high data volume demands can leverage distributed caching to handle significant data requests efficiently
Working of Distributed Cache:
👉 Distributed caching involves storing data across multiple servers to enhance performance and scalability.
👉 A distributed cache extends the traditional cache concept used in a single locale, spanning multiple servers to increase in size and transactional capacity.
Core Requirements:
👉 There are 2 main core requirements for the cache system.
- How to read and write data to the cache system. 👇
For Reading Data
- Cache-Aside Strategy:
Description: In the cache-aside pattern, the application interacts directly with the cache and database independently. The application code manages cache lookups, updates on writes, and database queries on cache misses to maintain data consistency
Process: When reading data, the application first checks the cache. If the data is available (cache hit), it is returned directly; if not (cache miss), the application retrieves data from the database, updates the cache, and then serves it to the user
- Read-Through Strategy:
Description: In read-through caching, if there is a cache hit, data is retrieved directly from the cache; otherwise, the cache fetches data from the database itself. This strategy simplifies data loading processes and reduces client-side load for complex data loading requirements
Process: When a client requests data, the system checks the cache first. If there is a cache miss, the cache retrieves data from the database, stores it, and then returns it to the client
For Writing Data
- Write-Around Strategy: Write-around caching involves updating only the primary storage when writing new data. This approach avoids caching new or infrequently accessed data to prevent unnecessary storage consumption in the cache
2. Write-Back Strategy: Write-back caching enhances write performance by updating only the cache initially and later synchronizing with the primary storage. It improves performance for read-heavy and write-heavy workloads by insulating applications from database failures.
3. Write-Through Strategy: In write-through caching, after updating the database, both the database and cache are updated simultaneously. This ensures improved read performance, reduced chances of stale data, and maintains consistency between cache and database
2. How to remove stale data from the cache system. 👇
👉 There are two scenarios when we need to remove data from the cache.
- When data is present in the system for a long time and is not getting updated, then it might have expired and should be deleted. For this, we need to assign a time to live (TTL) to keys that after a certain interval expire and are deleted from the cache.
- When the cache becomes full then we need to remove some data from the cache so that new entries can come. Different data eviction strategies can be used for this purpose.
- First In First Out (FIFO): The cache evicts the first block accessed first without any regard to how often or how many times it was accessed before.
- Last In First Out (LIFO): The cache evicts the block accessed most recently without any regard to how often or how many times it was accessed before.
- Least Recently Used (LRU): Discards the least recently used items first.
The most preferred is LRU only. 🙂 - Most Recently Used (MRU): Discards, in contrast to LRU, the most recently used items first.
- Least Frequently Used (LFU): Counts how often an item is needed. Those that are used least often are discarded first.
💁 So till now, we have discussed how we can write and read data from cache and how to remove data from the cache system if required. Now let's implement LRU Cache. You may have known LRU cache before, it is quite a common DSA problem but let’s try to do something new…😅
👉 Cache: represents the data structure to store cache data with an object of eviction policy strategy (Strategy Design Pattern👀).
👉 IReplacementPolicy (interface)
- Why I am passing the cache object here because the eviction policy needs to shuffle data accordingly to evict the data. That’s why I have the Get and Put method defined for the replacement policy too.
👉 LRU Cache Replacement Policy
Thus, we have implemented a simple cache with the LRU eviction policy. Now let’s move a step higher, to make this suitable for a distributed system.
👉 A cache can be Co-located (means in the same server) or in a dedicated cluster (means cache service is on a separate host. In both cases, we need to split the data based on the keys that we are going to enter.
But now the question is how to decide which shared to call to get or store the data…?🥸
👉 Most Naive Approach would be a Mod Hash Function. The node key will be mod with the number of available hosts which will give a number that is used as an index to the server host.
But But But……😲 What will happen when:
- New nodes are to be added to the cluster
- Nodes to be deleted from the cluster
- Some node's service goes down
In these cases, the mod function will start producing completely different results. Also, we need to shuffle/ remap all the keys to the new host. Thus mod function is a poor choice for the production environment.
A much better choice is Consistent Hashing.
We will discuss and implement this in another article, Else this will be a very long blog 😬
