Caching is a technique used to store frequently accessed data in a temporary storage location (cache) to improve performance and speed up data retrieval. Instead of fetching data from the main source (like a database or server) repeatedly, caching keeps a copy of the data closer to where it's needed.
However, since cache storage is limited, we need strategies to decide which data to keep and which to remove when the cache is full. The following are some common cache eviction policies:
1. LRU (Least Recently Used)
Concept:
LRU removes the least recently used item from the cache when it reaches its limit.
Real-Life Example:
Imagine a small bookshelf that can hold only 5 books. You keep replacing the books based on how recently you read them. If you pick a book and read it today, it stays. But if a book hasn’t been read for weeks, it gets removed first to make space for a new one.
Use Case:
LRU is used in web browsers to manage cached pages. If you visit multiple websites, but some haven’t been accessed in a while, the browser removes the oldest ones to store new ones.
Algorithm Pseudocode
Initialize an empty cache with a fixed size.
Use a HashMap to store key-value pairs.
Use a Doubly Linked List to maintain access order (most recent at the front).
When accessing an item:
- If it exists, move it to the front (most recently used).
- If it's missing, add it to the front.
- If the cache is full, remove the least recently used item from the back.
Node.js Express Implementation
const express = require('express');
const app = express();
const PORT = 3000;
class LRUCache {
constructor(size) {
this.size = size;
this.map = new Map();
}
get(key) {
if (!this.map.has(key)) return null;
const value = this.map.get(key);
this.map.delete(key);
this.map.set(key, value);
return value;
}
put(key, value) {
if (this.map.has(key)) this.map.delete(key);
else if (this.map.size >= this.size) this.map.delete(this.map.keys().next().value);
this.map.set(key, value);
}
}
const cache = new LRUCache(3);
app.get('/users/:id', (req, res) => {
const userId = req.params.id;
let user = cache.get(userId);
if (!user) {
user = { id: userId, name: `User_${userId}` };
cache.put(userId, user);
}
res.json({ cachedUsers: Array.from(cache.map.values()) });
});
app.listen(PORT, () => console.log(`Server running on port ${PORT}`));
2. MRU (Most Recently Used)
Concept:
MRU removes the most recently used item first when the cache is full.
Real-Life Example:
Think of a music playlist with limited slots. You recently played a song, and now you want to add a new one. Instead of removing an old song, you remove the most recently played song because you assume it won’t be played again soon.
Use Case:
MRU is useful in cases where the older data is more valuable than the most recently used one, such as databases where the most recent queries are likely temporary.
Algorithm Pseudocode
Use a HashMap to store key-value pairs.
Use a Doubly Linked List to maintain access order.
When accessing an item:
- If it exists, move it to the front.
- If it’s missing, add it to the front.
- If the cache is full, remove the most recently used item (from the front).
Node.js Express Implementation
Use Case: Session management (removing the last logged-in user first)
class MRUCache {
constructor(size) {
this.size = size;
this.map = new Map();
}
get(key) {
if (!this.map.has(key)) return null;
const value = this.map.get(key);
this.map.delete(key);
this.map.set(key, value);
return value;
}
put(key, value) {
if (this.map.has(key)) this.map.delete(key);
else if (this.map.size >= this.size) {
let lastKey = Array.from(this.map.keys()).pop();
this.map.delete(lastKey);
}
this.map.set(key, value);
}
}
const sessionCache = new MRUCache(3);
app.get('/login/:user', (req, res) => {
const user = req.params.user;
sessionCache.put(user, { username: user, loggedInAt: new Date() });
res.json({ activeSessions: Array.from(sessionCache.map.values()) });
});
3. LFU (Least Frequently Used)
Concept:
LFU removes the least frequently used items first. It keeps track of how often each item is used and removes the ones that are used the least.
Real-Life Example:
Imagine a cafeteria menu where some dishes are more popular than others. If space is limited, the manager removes the least ordered dishes from the menu while keeping the bestsellers.
Use Case:
LFU is used in content delivery networks (CDNs) where the most accessed web pages and media files are cached, and less accessed ones are removed.
Algorithm Pseudocode
Use a HashMap to store key-value pairs.
Maintain a frequency counter for each item.
When adding new items:
- If the cache is full, remove the least frequently used item.
Node.js Express Implementation
Use Case: Caching most used products in an e-commerce API
class LFUCache {
constructor(size) {
this.size = size;
this.map = new Map();
this.freq = new Map();
}
get(key) {
if (!this.map.has(key)) return null;
this.freq.set(key, (this.freq.get(key) || 0) + 1);
return this.map.get(key);
}
put(key, value) {
if (this.map.size >= this.size) {
let lfuKey = [...this.freq.entries()].reduce((a, b) => (a[1] < b[1] ? a : b))[0];
this.map.delete(lfuKey);
this.freq.delete(lfuKey);
}
this.map.set(key, value);
this.freq.set(key, 1);
}
}
const productCache = new LFUCache(3);
app.get('/product/:id', (req, res) => {
const productId = req.params.id;
let product = productCache.get(productId);
if (!product) {
product = { id: productId, name: `Product_${productId}` };
productCache.put(productId, product);
}
res.json({ cachedProducts: Array.from(productCache.map.values()) });
});
4. FIFO (First In, First Out)
Concept:
FIFO removes the oldest item first, just like a queue.
Real-Life Example:
Think of a vending machine where snacks are loaded from the back. The first snack placed inside is the first one that comes out.
Use Case:
FIFO is commonly used in message queues and task scheduling where processing happens in the order requests arrive.
Algorithm Pseudocode
Use a queue to store items.
When adding a new item:
- If the cache is full, remove the oldest item (first added).
Node.js Express Implementation
Use Case: Queueing user requests in a rate limiter
class FIFOCache {
constructor(size) {
this.size = size;
this.queue = [];
}
put(value) {
if (this.queue.length >= this.size) this.queue.shift();
this.queue.push(value);
}
getAll() {
return this.queue;
}
}
const requestCache = new FIFOCache(5);
app.get('/request/:id', (req, res) => {
requestCache.put(`Request_${req.params.id}`);
res.json({ recentRequests: requestCache.getAll() });
});
5. LIFO (Last In, First Out)
Concept:
LIFO removes the most recently added item first. It works like a stack where the last item placed is the first to be removed.
Real-Life Example:
Imagine a stack of plates in a restaurant. The waiter always places clean plates on top, and the next customer takes the topmost plate.
Use Case:
LIFO is used in undo operations in text editors, where the most recent action is undone first.
Algorithm Pseudocode
Use a stack (array) to store items.
When adding a new item:
- If the cache is full, remove the last added item.
Node.js Express Implementation
Use Case: Tracking the last performed API request
class LIFOCache {
constructor(size) {
this.size = size;
this.stack = [];
}
put(value) {
if (this.stack.length >= this.size) this.stack.pop();
this.stack.push(value);
}
getLast() {
return this.stack[this.stack.length - 1];
}
}
const actionCache = new LIFOCache(3);
app.get('/action/:name', (req, res) => {
actionCache.put(req.params.name);
res.json({ lastAction: actionCache.getLast() });
});
6. RR (Round Robin)
Concept:
Round Robin cycles through items in order, giving each a fair chance before repeating.
Real-Life Example:
Imagine a queue of people waiting to ask questions in a classroom. The teacher answers one question per student before moving to the next, ensuring everyone gets a turn.
Use Case:
RR is commonly used in load balancing for servers to distribute incoming requests fairly across multiple servers.
Algorithm Pseudocode
Use a circular queue.
Each request gets assigned to the next available server in order.
Node.js Express Implementation
Use Case: Load balancing incoming requests to different servers
const servers = ['Server_1', 'Server_2', 'Server_3'];
let index = 0;
app.get('/request', (req, res) => {
const assignedServer = servers[index];
index = (index + 1) % servers.length;
res.json({ assignedServer });
});
Conclusion
Each caching technique has its advantages and is useful in different scenarios. If you need fast access to recent data, LRU is a good choice. If older data is important, MRU or LFU might be better. FIFO and LIFO are useful for queues and stacks, while RR is great for fair resource distribution.
Please ignore any typos, and let me know your thoughts on this.
Top comments (0)