It started with a LeetCode problem: implement an LRU (Least Recently Used) cache. Like many algorithm problems, it felt academic - but that question “where would I actually use this?” led me on a journey through modern caching strategies, from single servers to distributed microservices. Here’s what I learned.
What is Caching?
Caching is simple: store data somewhere fast so you don’t have to fetch it from somewhere slow.
The speed hierarchy looks like this:
- L1/L2 CPU Cache: ~1 nanosecond
- RAM: ~100 nanoseconds
- SSD: ~100 microseconds (1,000x slower than RAM)
- Network call: ~10 milliseconds (100,000x slower than RAM)
- Database query: ~50-100 milliseconds
- External API: ~200-500 milliseconds
If you’re reading the same data repeatedly, caching can turn a 100ms database query into a 1ms RAM lookup. That’s a 100x speed improvement.
LRU Cache: The Algorithm
The LRU cache evicts the least recently used item when the cache fills up. The thought is, if you haven’t used something in a while, you probably won’t need it soon.
A simple implementation uses:
- HashMap for O(1) lookups
- Doubly-linked list to track access order
When you access an item, move it to the front of the list. When the cache fills, remove the item at the back (least recently used).
This matters because most caching systems use LRU or LRU-like eviction policies. Understanding the algorithm helps you understand the behavior of tools like Redis.
Browser Caching: The First Layer
Before we get to backend caching, let’s talk about browser caching - it’s the first cache most users encounter.
How it works:
When a browser requests a resource, the server responds with cache headers:
HTTP/1.1 200 OK
Cache-Control: max-age=3600, public
ETag: "abc123"
Last-Modified: Mon, 01 Jan 2024 00:00:00 GMTmax-age=3600: Cache for 1 hourpublic: Can be cached by CDNsETag: Fingerprint for the resourceLast-Modified: When resource last changed
Next time the browser needs this resource, it checks:
- Is it in cache and not expired? → Use cached version
- Is it expired? → Send conditional request with
If-None-Match: "abc123" - Server responds with
304 Not Modifiedif unchanged → Use cached version - Otherwise, server sends new version with new ETag
Cache invalidation strategy:
For static assets (JavaScript, CSS, images), use cache-busting with versioned URLs:
/assets/app.js?v=abc123
/assets/app.js?v=def456 // New version = new URL = no cache hit
This gives you instant “invalidation” because it’s actually a new URL that bypasses the cache.
For HTML pages and API responses, use shorter TTLs or no caching.
Backend Caching: Single Server
Now let’s talk about caching on the backend. We’ll start simple: one server.
In-Memory Caching
The simplest approach: store data in the server’s memory.
// Simple in-memory cache
const cache = new Map<string, any>();
async function getUser(userId: string) {
// Check cache first
const cached = cache.get(`user:${userId}`);
if (cached) {
return cached;
}
// Cache miss - fetch from database
const user = await db.query('SELECT * FROM users WHERE id = $1', [userId]);
// Store in cache
cache.set(`user:${userId}`, user);
return user;
}This is the cache-aside pattern (also called lazy loading):
- Check cache
- If miss, fetch from database
- Store in cache
- Return data
Cache invalidation:
When data changes, you have two options:
Option 1: Delete from cache
async function updateUser(userId: string, data: UserData) {
await db.query('UPDATE users SET ... WHERE id = $1', [userId, ...]);
cache.delete(`user:${userId}`); // Remove from cache
}Next read will be a cache miss and fetch fresh data from the database.
Option 2: Update the cache
async function updateUser(userId: string, data: UserData) {
await db.query('UPDATE users SET ... WHERE id = $1', [userId, ...]);
cache.set(`user:${userId}`, data); // Update cache with new data
}This keeps the cache warm but adds complexity if the update fails.
TTL (Time-To-Live):
You can also set an expiration time:
const cache = new Map<string, { value: any, expiresAt: number }>();
function set(key: string, value: any, ttlSeconds: number) {
cache.set(key, {
value,
expiresAt: Date.now() + (ttlSeconds * 1000)
});
}
function get(key: string) {
const item = cache.get(key);
if (!item) return null;
if (Date.now() > item.expiresAt) {
cache.delete(key); // Expired
return null;
}
return item.value;
}TTL is a safety net: even if you forget to invalidate, stale data eventually expires.
When Single-Server Caching Works
This approach works great when:
- You have one server (or very few)
- All requests go to the same server
- Cache misses are acceptable
- You don’t need cross-server consistency
Small applications, internal tools, and monoliths often fit this profile.
The Problem: Horizontal Scaling
Now your application is growing. One server can’t handle the load. You add more servers behind a load balancer:
┌──────────┐
│ Load │
Users ────────>│ Balancer │
└──────────┘
╱ | ╲
╱ | ╲
┌─────────┐ ┌─────────┐ ┌─────────┐
│ Server │ │ Server │ │ Server │
│ #1 │ │ #2 │ │ #3 │
│ [Cache] │ │ [Cache] │ │ [Cache] │
└─────────┘ └─────────┘ └─────────┘
│ │ │
└───────────┴───────────┘
│
┌──────────┐
│ Database │
└──────────┘
Each server has its own in-memory cache. The problem:
User Request 1 → Server #1
- Cache miss, fetches user data from database
- Stores in Server #1’s cache
User Request 2 → Server #2 (load balancer routes to different server)
- Cache miss! Server #2 doesn’t have this user cached
- Fetches from database again
- Stores in Server #2’s cache
User updates data → Server #3
- Updates database
- Invalidates cache on Server #3
- But Server #1 and #2 still have stale data!
Your cache hit rate plummets because requests are spread across servers. Worse, you have inconsistent data across servers.
Enter: Distributed Caching with Redis
The solution: a shared cache that all servers access.
┌──────────┐
│ Load │
Users ────────>│ Balancer │
└──────────┘
╱ | ╲
╱ | ╲
┌─────────┐ ┌─────────┐ ┌─────────┐
│ Server │ │ Server │ │ Server │
│ #1 │ │ #2 │ │ #3 │
└─────────┘ └─────────┘ └─────────┘
│ │ │
└───────────┴───────────┘
│
┌──────────┐
│ Redis │ ← Shared cache
│ Cache │
└──────────┘
│
┌──────────┐
│ Database │
└──────────┘
Redis is an in-memory data store that acts as a shared cache:
import { createClient } from 'redis';
const redis = createClient({ url: 'redis://localhost:6379' });
await redis.connect();
async function getUser(userId: string) {
// Check Redis cache
const cached = await redis.get(`user:${userId}`);
if (cached) {
return JSON.parse(cached);
}
// Cache miss - fetch from database
const user = await db.query('SELECT * FROM users WHERE id = $1', [userId]);
// Store in Redis with 1 hour TTL
await redis.setEx(`user:${userId}`, 3600, JSON.stringify(user));
return user;
}
async function updateUser(userId: string, data: UserData) {
await db.query('UPDATE users SET ... WHERE id = $1', [userId, ...]);
// Invalidate cache (all servers see this)
await redis.del(`user:${userId}`);
}Now all servers share the same cache:
- Server #1 caches data → stored in Redis
- Server #2 request → cache hit in Redis!
- Server #3 invalidates → all servers see the invalidation
Redis Configuration
Redis uses LRU-based eviction when memory fills up:
maxmemory 2gb
maxmemory-policy allkeys-lru
When Redis reaches 2GB:
allkeys-lru: Evicts least recently used keysvolatile-lru: Evicts only keys with TTL setnoeviction: Reject writes (return errors)
This is where understanding the LRU algorithm matters - Redis behaves exactly as you’d expect from the algorithm.
Microservices: A New Challenge
Now let’s say you break your monolith into microservices:
- User Service: Manages users
- Order Service: Handles orders
- Inventory Service: Tracks inventory
- Email Service: Sends notifications
Each service has its own database and caches its own data in Redis.
The new problem:
When User Service updates a user’s email:
- User Service updates its database
- User Service invalidates its cache:
redis.del('user:123') - Order Service has cached this user’s data too - its cache is now stale!
How do you invalidate caches across services?
Cache Invalidation in Microservices
Approach 1: Direct Service Calls (Don’t Do This)
// User Service
async function updateUser(userId: string, email: string) {
await db.updateUser(userId, email);
await redis.del(`user:${userId}`);
// Tell other services to invalidate
await http.post('http://order-service/invalidate', { userId });
await http.post('http://email-service/invalidate', { userId });
}Problems:
- Tight coupling: User Service knows about all other services
- Synchronous: Update is slow (waits for all invalidations)
- Failure handling: What if Email Service is down? Do you fail the update?
- Doesn’t scale: Adding new services means updating User Service
Approach 2: Event-Driven Invalidation (Better)
Use a message queue (like AWS SQS, RabbitMQ, or Kafka) to broadcast changes:
// User Service: Publish event
async function updateUser(userId: string, email: string) {
await db.updateUser(userId, email);
await redis.del(`user:${userId}`);
// Publish event (fire and forget)
await messageQueue.publish('user.updated', {
userId,
timestamp: Date.now()
});
}
// Order Service: Subscribe to events
messageQueue.subscribe('user.updated', async (event) => {
await redis.del(`user:${event.userId}`);
await redis.del(`user_orders:${event.userId}`); // Invalidate related caches
});
// Email Service: Subscribe to events
messageQueue.subscribe('user.updated', async (event) => {
await redis.del(`user:${event.userId}`);
});Advantages:
- Decoupled: Services don’t know about each other
- Asynchronous: User Service doesn’t wait for invalidations
- Scalable: New services just subscribe to events
- Resilient: Message queue handles retries
The catch:
- Eventual consistency: There’s a delay between update and invalidation across services
- Reliability: What if the event fails to publish?
The Dual Write Problem
Here’s the subtle but critical issue with event-driven invalidation:
async function updateUser(userId: string, email: string) {
// Write #1: Database
await db.updateUser(userId, email);
// Write #2: Message queue
await messageQueue.publish('user.updated', { userId });
}You’re writing to two different systems (database and message queue). What could go wrong?
Scenario 1: Database succeeds, message queue fails
db.updateUser() → ✅ SUCCESS
messageQueue.publish() → ❌ FAIL (network issue)
Database has new data, but no event was published. Other services never invalidate their caches. Stale data everywhere.
Scenario 2: Message queue succeeds, database fails
db.updateUser() → ❌ FAIL (constraint violation)
messageQueue.publish() → ✅ SUCCESS
Event was published but database didn’t change. Other services invalidate caches for no reason. Next read fetches “new” data that doesn’t exist.
Scenario 3: Service crashes between writes
db.updateUser() → ✅ SUCCESS
*service crashes*
messageQueue.publish() → ❌ NEVER HAPPENS
Same as Scenario 1 - database updated but no event published.
You can’t wrap both operations in a database transaction because the message queue isn’t part of your database.
This is called the dual write problem.
The Solution: Transactional Outbox Pattern
The key insight: instead of publishing directly to the message queue, write the event to a database table in the same transaction as your data update.
How It Works
Step 1: Add an “outbox” table
CREATE TABLE outbox (
id SERIAL PRIMARY KEY,
event_id VARCHAR(255) UNIQUE NOT NULL,
aggregate_id VARCHAR(255) NOT NULL,
event_type VARCHAR(255) NOT NULL,
payload JSONB NOT NULL,
created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
processed_at TIMESTAMP
);Step 2: Write to both tables in a single transaction
async function updateUser(userId: string, email: string) {
const client = await db.connect();
try {
await client.query('BEGIN');
// Update user table
await client.query(
'UPDATE users SET email = $1 WHERE id = $2',
[email, userId]
);
// Insert event into outbox table (same transaction!)
await client.query(
'INSERT INTO outbox (event_id, aggregate_id, event_type, payload) VALUES ($1, $2, $3, $4)',
[uuidv4(), userId, 'user.updated', JSON.stringify({ userId, email })]
);
await client.query('COMMIT');
} catch (error) {
await client.query('ROLLBACK');
throw error;
} finally {
client.release();
}
}Both writes succeed or both fail together. Atomic guarantee.
Step 3: Background process publishes events
A separate service (the “event processor”) polls the outbox table and publishes events:
// Runs every 1 second
async function processOutbox() {
const events = await db.query(
'SELECT * FROM outbox WHERE processed_at IS NULL ORDER BY created_at LIMIT 10'
);
for (const event of events) {
try {
// Publish to message queue
await messageQueue.publish(event.event_type, JSON.parse(event.payload));
// Mark as processed
await db.query(
'UPDATE outbox SET processed_at = NOW() WHERE id = $1',
[event.id]
);
} catch (error) {
// Log error, will retry on next poll
console.error('Failed to publish event', event.id, error);
}
}
}Why This Works
The beauty is in the separation:
- Your application logic only cares about the database transaction (simple, fast, atomic)
- The event processor handles the messy details of reliable message delivery (retries, failures, ordering)
If the user update fails, nothing gets written - not even to the outbox.
If the user update succeeds, the event is guaranteed to be in the outbox.
The event processor keeps trying to publish until it succeeds. If it crashes, it resumes polling when it restarts.
Tradeoffs
Pros:
- ✅ Guaranteed event delivery (no lost events)
- ✅ Atomic writes (both succeed or both fail)
- ✅ Simple application logic (just write to database)
- ✅ Automatic retries (event processor handles this)
- ✅ Event ordering (via sequence numbers or timestamps)
Cons:
- ❌ Added latency (polling interval, typically 100-1000ms)
- ❌ More infrastructure (need event processor service)
- ❌ Outbox table grows (need cleanup strategy)
- ❌ Eventual consistency (not instant across services)
Cleanup Strategy
The outbox table will grow over time. You need a cleanup strategy:
Option 1: Delete after processing
await db.query('DELETE FROM outbox WHERE id = $1', [event.id]);Simple but you lose event history.
Option 2: Archive old events
// Move to archive table after 30 days
await db.query(`
INSERT INTO outbox_archive SELECT * FROM outbox
WHERE processed_at < NOW() - INTERVAL '30 days'
`);
await db.query(`
DELETE FROM outbox
WHERE processed_at < NOW() - INTERVAL '30 days'
`);Keeps history for debugging/audit but archives it to keep the outbox table small.
Option 3: TTL with processed_at index
CREATE INDEX idx_outbox_processed ON outbox(processed_at);
-- Delete old processed events
DELETE FROM outbox WHERE processed_at < NOW() - INTERVAL '7 days';Alternative: Change Data Capture (CDC)
Instead of an explicit outbox table, some databases let you stream changes directly from the transaction log.
AWS DynamoDB Streams:
// Enable streams on your table
const table = new dynamodb.Table(this, 'users', {
stream: StreamViewType.NEW_AND_OLD_IMAGES
});
// Lambda function processes stream
exports.handler = async (event) => {
for (const record of event.Records) {
if (record.eventName === 'MODIFY') {
const userId = record.dynamodb.Keys.id.S;
await messageQueue.publish('user.updated', { userId });
}
}
};Pros:
- No explicit outbox table
- Lower latency (near real-time)
- Guaranteed ordering (follows transaction log)
Cons:
- Requires CDC-capable database
- More complex infrastructure
- Harder to debug (events aren’t explicitly stored)
- Need to filter what becomes an event
Idempotency: The Other Half of the Puzzle
There’s one more problem: the transactional outbox pattern guarantees events are delivered at least once, not exactly once.
What if the event processor publishes an event successfully, but crashes before it can mark it as processed? On restart, it will publish the same event again.
Or what if the message queue delivers a message twice? (Many queuing systems guarantee “at least once delivery”.)
Your Order Service might receive the same user.updated event twice and invalidate the same cache twice. That’s fine for invalidation, but what if the event triggers a payment?
// Payment Service receives event twice
messageQueue.subscribe('order.completed', async (event) => {
await processPayment(event.orderId, event.amount);
});
// Customer gets charged twice! 💸💸The solution: idempotency. Make your event handlers safe to process multiple times.
Idempotent Event Processing
Track which events you’ve already processed:
CREATE TABLE processed_events (
event_id VARCHAR(255) PRIMARY KEY,
processed_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);Check before processing:
async function handleOrderCompleted(event) {
const client = await db.connect();
try {
await client.query('BEGIN');
// Check if already processed (within transaction)
const result = await client.query(
'SELECT 1 FROM processed_events WHERE event_id = $1',
[event.eventId]
);
if (result.rows.length > 0) {
console.log('Event already processed, skipping');
await client.query('ROLLBACK');
return;
}
// Process the payment
await client.query(
'INSERT INTO payments (order_id, amount) VALUES ($1, $2)',
[event.orderId, event.amount]
);
// Mark as processed (same transaction!)
await client.query(
'INSERT INTO processed_events (event_id) VALUES ($1)',
[event.eventId]
);
await client.query('COMMIT');
} catch (error) {
await client.query('ROLLBACK');
throw error;
} finally {
client.release();
}
}The key: checking and marking as processed happens in the same transaction as your business logic.
Now if the same event arrives twice, the second attempt sees it’s already processed and skips it. No duplicate payments.
Putting It All Together
Let’s trace a complete flow:
1. User Service updates user email:
async function updateUser(userId, email) {
await db.transaction(async (client) => {
await client.query('UPDATE users SET email = $1 WHERE id = $2', [email, userId]);
await client.query('INSERT INTO outbox (event_id, event_type, payload) VALUES ($1, $2, $3)',
[uuidv4(), 'user.updated', JSON.stringify({ userId, email })]);
});
// Both writes succeed or both fail
}2. Event processor publishes event:
const event = await db.query('SELECT * FROM outbox WHERE processed_at IS NULL LIMIT 1');
await messageQueue.publish('user.updated', event.payload);
await db.query('UPDATE outbox SET processed_at = NOW() WHERE id = $1', [event.id]);3. Order Service receives event and invalidates cache:
messageQueue.subscribe('user.updated', async (event) => {
// Idempotency check
if (await isEventProcessed(event.eventId)) return;
// Invalidate cache
await redis.del(`user:${event.userId}`);
await redis.del(`user_orders:${event.userId}`);
// Mark as processed
await markEventProcessed(event.eventId);
});Flow:
- Database update + outbox write: atomic ✅
- Event publishing: reliable (retries until success) ✅
- Event processing: idempotent (safe to process twice) ✅
- Cache invalidation: eventually consistent across all services ✅
When to Use These Patterns
Use in-memory caching (single server) when:
- Small application with one server
- All requests go to same server
- Cache misses are acceptable
Use Redis (shared cache) when:
- Multiple servers behind load balancer
- Need consistent cache across servers
- Stateless services
Use event-driven invalidation when:
- Microservices architecture
- Multiple services cache the same data
- Can tolerate eventual consistency (100ms-1s delay)
Use transactional outbox when:
- Data consistency is critical
- Can’t afford lost events
- Building event-driven architecture
- Need reliable event delivery with retries
Skip the complexity when:
- Simple CRUD app with low traffic
- Can use short TTLs (30-60 seconds) everywhere
- Cache invalidation failures are acceptable
What I Learned
The progression from LRU cache to distributed systems taught me:
-
Caching is everywhere - Browser, CDN, backend, database. Each layer has different invalidation strategies.
-
Shared state is hard - Moving from single server to multiple servers fundamentally changes caching.
-
Events solve decoupling - But introduce new problems (reliability, ordering, duplicates).
-
Transactions are your friend - The transactional outbox pattern trades complexity for reliability.
-
Idempotency is non-negotiable - In distributed systems, everything can (and will) happen twice.
-
Trade-offs are everywhere - Consistency vs. availability. Latency vs. reliability. Simplicity vs. correctness.
The “simple” LeetCode problem opened the door to understanding how modern distributed systems actually work. Cache invalidation isn’t just a hard problem - it’s the lens through which you understand distributed systems design.
Resources
- Redis Documentation
- Pattern: Transactional Outbox
- AWS: Transactional Outbox Pattern
- Martin Fowler: Two Hard Things
- My Implementation: Flight Booking System