🚀 Caching & CDN Algorithms: Making the Web Instant
Part 6: From Database Queries to Edge Computing
"The fastest request is the one you never make. The second fastest is the one served from memory."
After mastering time-space trade-offs, algorithm design, graphs, production systems, and database internals, you're ready for the layer that makes the modern web feel instant: caching and content delivery.
🌍 The Caching Reality
The Problem:
Your website without caching:
├─ User clicks → Request to origin server (500ms)
├─ Query database → B-tree lookup (50ms)
├─ Process data → Business logic (100ms)
├─ Return response → Network latency (200ms)
└─ Total time: 850ms per request 😴
Your website WITH caching:
├─ User clicks → Check cache (5ms)
├─ Cache hit! → Return immediately
└─ Total time: 5ms per request ⚡
Speedup: 170x faster!
The Stakes:
Without caching: With intelligent caching:
├─ Database: 10k queries/sec ├─ Database: 100 queries/sec
├─ 95% load on DB ├─ 5% load on DB (95% cache hit)
├─ Servers needed: 100 ├─ Servers needed: 5
├─ Monthly cost: $50,000 ├─ Monthly cost: $3,000
├─ Response time: 500ms ├─ Response time: 10ms
└─ User experience: Slow └─ User experience: Instant
Result: Good caching = $47k/month savings + 50x faster
🎯 The Core Challenge: Cache Eviction
Understanding the Problem
Your cache has limited space (like RAM):
├─ Can store: 1000 items
├─ Total data: 1,000,000 items
├─ Problem: Which 1000 to keep?
Wrong choice:
├─ Keep rarely used items
├─ Evict popular items
└─ Low hit rate → Cache is useless
Right choice:
├─ Keep frequently accessed items
├─ Evict items nobody needs
└─ High hit rate → Cache is valuable
The algorithm that chooses WHAT to evict
determines whether your cache succeeds or fails!
The Hidden Cost Your intuition points out:
Every caching algorithm has memory overhead:
Simple array cache:
├─ Data: O(n) space
├─ Lookup: O(n) time (linear search)
└─ Eviction: Need to track access somehow!
Hash table cache:
├─ Data: O(n) space
├─ Lookup: O(1) time ✓
├─ Eviction metadata: O(n) extra space
├─ Update overhead: Every access needs bookkeeping
└─ Total: 2×O(n) space (data + metadata)
The recursion stack lesson from Part 5:
"Space complexity has visible AND hidden costs"
🎯 Algorithm 1: LRU (Least Recently Used)
The Idea
Eviction policy: Remove the item accessed longest ago
Example:
Cache capacity: 3 items
Access pattern: A → B → C → A → D
Step 1: Access A
Cache: [A]
Recent: A
Step 2: Access B
Cache: [A, B]
Recent: B → A
Step 3: Access C
Cache: [A, B, C] (Full!)
Recent: C → B → A
Step 4: Access A (already in cache)
Cache: [A, B, C]
Recent: A → C → B (A moved to front)
Step 5: Access D (cache full, evict LRU)
Evict: B (least recently used)
Cache: [A, C, D]
Recent: D → A → C
Intuition: If you haven't used it recently,
you probably won't use it soon.
The Challenge: Efficient Implementation
Naive LRU:
├─ Store access timestamps
├─ On eviction: O(n) scan to find oldest
└─ Total: O(1) access, O(n) eviction ❌
Clever LRU:
├─ Use doubly-linked list + hash map
├─ List maintains recency order
├─ Hash map gives O(1) lookup
└─ Total: O(1) access, O(1) eviction ✓
Implementation
#include <iostream>
#include <unordered_map>
#include <list>
#include <string>
using namespace std;
template<typename K, typename V>
class LRUCache {
private:
int capacity;
// Doubly-linked list: stores (key, value) pairs
// Front = most recently used, Back = least recently used
list<pair<K, V>> cacheList;
// Hash map: key -> iterator to list node
unordered_map<K, typename list<pair<K, V>>::iterator> cacheMap;
// Statistics
int hits = 0;
int misses = 0;
int evictions = 0;
public:
LRUCache(int cap) : capacity(cap) {}
// Get value from cache
pair<bool, V> get(const K& key) {
auto it = cacheMap.find(key);
if (it == cacheMap.end()) {
// Cache miss
misses++;
return {false, V()};
}
// Cache hit - move to front (most recent)
hits++;
auto listIt = it->second;
// Move to front of list
cacheList.splice(cacheList.begin(), cacheList, listIt);
return {true, listIt->second};
}
// Put value into cache
void put(const K& key, const V& value) {
auto it = cacheMap.find(key);
if (it != cacheMap.end()) {
// Key exists - update value and move to front
auto listIt = it->second;
listIt->second = value;
cacheList.splice(cacheList.begin(), cacheList, listIt);
return;
}
// New key
if (cacheList.size() >= capacity) {
// Cache full - evict LRU (back of list)
auto lru = cacheList.back();
cacheMap.erase(lru.first);
cacheList.pop_back();
evictions++;
}
// Add to front
cacheList.push_front({key, value});
cacheMap[key] = cacheList.begin();
}
double getHitRate() const {
int total = hits + misses;
return total > 0 ? (double)hits / total : 0.0;
}
void displayStats() {
cout << "\n📊 CACHE STATISTICS\n";
cout << "═══════════════════════════════════════\n";
cout << "Capacity: " << capacity << "\n";
cout << "Current size: " << cacheList.size() << "\n";
cout << "Hits: " << hits << "\n";
cout << "Misses: " << misses << "\n";
cout << "Evictions: " << evictions << "\n";
cout << "Hit rate: " << (getHitRate() * 100) << "%\n\n";
cout << "Cache contents (most → least recent):\n";
int i = 1;
for (const auto& item : cacheList) {
cout << " " << i++ << ". " << item.first << " → " << item.second << "\n";
}
}
void displayAnalysis() {
cout << "\n🔍 COMPLEXITY ANALYSIS\n";
cout << "═══════════════════════════════════════\n";
cout << "get() operation:\n";
cout << " Time: O(1) - hash lookup + list splice\n";
cout << " Space: O(1) - no extra allocation\n\n";
cout << "put() operation:\n";
cout << " Time: O(1) - hash insert + list operations\n";
cout << " Space: O(1) per item\n\n";
cout << "Total space complexity:\n";
cout << " Data: O(n) - n items in cache\n";
cout << " Metadata: O(n) - hash map pointers\n";
cout << " List overhead: O(n) - prev/next pointers\n";
cout << " Total: ~3×O(n) space\n\n";
cout << "💡 Hidden cost lesson from Part 5:\n";
cout << "LRU promises O(1) operations but needs 3x memory!\n";
cout << "├─ Data itself (values)\n";
cout << "├─ Hash map (for O(1) lookup)\n";
cout << "└─ Doubly-linked list (for O(1) reordering)\n";
}
};
int main() {
cout << "\n🗄️ LRU CACHE DEMONSTRATION\n";
cout << "═══════════════════════════════════════════════════════════\n\n";
LRUCache<string, string> cache(3); // Capacity: 3 items
cout << "Cache capacity: 3 items\n\n";
// Simulate website requests
struct Request {
string key;
string value;
string description;
};
vector<Request> requests = {
{"user:123", "Alice", "First access"},
{"user:456", "Bob", "Second access"},
{"user:789", "Carol", "Third access (cache full)"},
{"user:123", "Alice", "Access Alice again (cache hit!)"},
{"user:999", "Dave", "Fourth access (evict LRU: Bob)"},
{"user:456", "Bob", "Access Bob (evicted, cache miss)"},
};
for (const auto& req : requests) {
cout << "📥 " << req.description << "\n";
cout << " Request: " << req.key << "\n";
// Try to get from cache first
auto [found, value] = cache.get(req.key);
if (found) {
cout << " ✅ Cache HIT - Returned: " << value << "\n";
} else {
cout << " ❌ Cache MISS - Fetching from database...\n";
cout << " 💾 Storing in cache\n";
cache.put(req.key, req.value);
}
cout << "\n";
}
cache.displayStats();
cache.displayAnalysis();
// Demonstrate why LRU works for typical access patterns
cout << "\n🎯 WHY LRU WORKS\n";
cout << "═══════════════════════════════════════════════════════════\n\n";
cout << "Temporal locality principle:\n";
cout << "├─ Recently accessed data likely to be accessed again soon\n";
cout << "├─ Old data unlikely to be needed\n";
cout << "└─ LRU exploits this pattern\n\n";
cout << "Real-world examples:\n";
cout << "├─ Web sessions: Active users access repeatedly\n";
cout << "├─ API responses: Popular endpoints hit frequently\n";
cout << "├─ Database queries: Hot data accessed often\n";
cout << "└─ CDN: Popular content served repeatedly\n\n";
cout << "When LRU fails:\n";
cout << "├─ Scan pattern: Access each item once, never again\n";
cout << "├─ Large working set: Need more than cache capacity\n";
cout << "└─ Periodic access: Item accessed every N requests\n";
return 0;
}
Output:
🗄️ LRU CACHE DEMONSTRATION
═══════════════════════════════════════════════════════════
Cache capacity: 3 items
📥 First access
Request: user:123
❌ Cache MISS - Fetching from database...
💾 Storing in cache
📥 Second access
Request: user:456
❌ Cache MISS - Fetching from database...
💾 Storing in cache
📥 Third access (cache full)
Request: user:789
❌ Cache MISS - Fetching from database...
💾 Storing in cache
📥 Access Alice again (cache hit!)
Request: user:123
✅ Cache HIT - Returned: Alice
📥 Fourth access (evict LRU: Bob)
Request: user:999
❌ Cache MISS - Fetching from database...
💾 Storing in cache
📥 Access Bob (evicted, cache miss)
Request: user:456
❌ Cache MISS - Fetching from database...
💾 Storing in cache
📊 CACHE STATISTICS
═══════════════════════════════════════
Capacity: 3
Current size: 3
Hits: 1
Misses: 5
Evictions: 1
Hit rate: 16.67%
Cache contents (most → least recent):
1. user:456 → Bob
2. user:999 → Dave
3. user:123 → Alice
🔍 COMPLEXITY ANALYSIS
═══════════════════════════════════════
get() operation:
Time: O(1) - hash lookup + list splice
Space: O(1) - no extra allocation
put() operation:
Time: O(1) - hash insert + list operations
Space: O(1) per item
Total space complexity:
Data: O(n) - n items in cache
Metadata: O(n) - hash map pointers
List overhead: O(n) - prev/next pointers
Total: ~3×O(n) space
💡 Hidden cost lesson from Part 5:
LRU promises O(1) operations but needs 3x memory!
├─ Data itself (values)
├─ Hash map (for O(1) lookup)
└─ Doubly-linked list (for O(1) reordering)
🎯 WHY LRU WORKS
═══════════════════════════════════════════════════════════
Temporal locality principle:
├─ Recently accessed data likely to be accessed again soon
├─ Old data unlikely to be needed
└─ LRU exploits this pattern
Real-world examples:
├─ Web sessions: Active users access repeatedly
├─ API responses: Popular endpoints hit frequently
├─ Database queries: Hot data accessed often
└─ CDN: Popular content served repeatedly
When LRU fails:
├─ Scan pattern: Access each item once, never again
├─ Large working set: Need more than cache capacity
└─ Periodic access: Item accessed every N requests
🎯 Algorithm 2: LFU (Least Frequently Used)
When LRU Isn't Enough
Problem with LRU:
Access pattern:
├─ Item A: accessed 1000 times yesterday
├─ Item B: accessed 1 time just now
└─ Cache full, need to evict
LRU says: Evict A (accessed longer ago)
But: A is clearly more valuable!
LFU says: Evict B (accessed less frequently)
This makes more sense!
LFU Implementation Concept
template<typename K, typename V>
class LFUCache {
private:
int capacity;
int minFreq; // Track minimum frequency for O(1) eviction
struct Node {
K key;
V value;
int freq; // Access frequency
};
// key -> node
unordered_map<K, Node> keyToNode;
// frequency -> list of keys with that frequency
unordered_map<int, list<K>> freqToKeys;
// key -> iterator in frequency list
unordered_map<K, typename list<K>::iterator> keyToIter;
public:
LFUCache(int cap) : capacity(cap), minFreq(0) {}
pair<bool, V> get(const K& key) {
if (keyToNode.find(key) == keyToNode.end()) {
return {false, V()};
}
// Increment frequency
Node& node = keyToNode[key];
int oldFreq = node.freq;
// Remove from old frequency list
freqToKeys[oldFreq].erase(keyToIter[key]);
if (freqToKeys[oldFreq].empty() && oldFreq == minFreq) {
minFreq++;
}
// Add to new frequency list
node.freq++;
freqToKeys[node.freq].push_front(key);
keyToIter[key] = freqToKeys[node.freq].begin();
return {true, node.value};
}
void put(const K& key, const V& value) {
if (capacity == 0) return;
if (keyToNode.find(key) != keyToNode.end()) {
// Update existing
keyToNode[key].value = value;
get(key); // Update frequency
return;
}
if (keyToNode.size() >= capacity) {
// Evict LFU
K evictKey = freqToKeys[minFreq].back();
freqToKeys[minFreq].pop_back();
keyToNode.erase(evictKey);
keyToIter.erase(evictKey);
}
// Insert new
Node node = {key, value, 1};
keyToNode[key] = node;
freqToKeys[1].push_front(key);
keyToIter[key] = freqToKeys[1].begin();
minFreq = 1;
}
};
/*
Complexity:
├─ Time: O(1) for get and put (amazing!)
├─ Space: O(3n) - three hash maps!
└─ Hidden cost: Complex bookkeeping overhead
deep layered truth lesson applies:
"O(1) time doesn't mean free - LFU needs MORE space than LRU!"
*/
🌐 Algorithm 3: CDN Routing with Consistent Hashing
The Global CDN Problem
Your content is on one server in Virginia.
Users are accessing from:
├─ Tokyo (300ms latency)
├─ London (100ms latency)
├─ Sydney (400ms latency)
└─ São Paulo (250ms latency)
Solution: Content Delivery Network (CDN)
├─ Copy content to servers worldwide
├─ Route users to nearest server
└─ Problem: How to distribute content across 1000+ servers?
Naive Approach (Hash Mod N)
hash(content_id) % N → server_id
Example with 3 servers:
hash("video.mp4") % 3 = 2 → Server 2
hash("image.jpg") % 3 = 1 → Server 1
Problem: What if server fails or we add a server?
Before: 3 servers
hash("video.mp4") % 3 = 2 → Server 2
After: 4 servers
hash("video.mp4") % 4 = 1 → Server 1 ❌
All mappings change! Cache invalidation disaster!
Consistent Hashing (The Solution)
Idea: Map both servers AND content to a ring
Hash ring (0 to 2³²-1):
hash("Server1") = 100
↓
0 ─────────────────────────────────── 2³²
↑ ↓ ↑
Server3=250 hash("video.mp4") Server2=1000
=500
For content, find next server clockwise:
video.mp4 (500) → Server2 (1000)
Add new server:
S1=100 NewS=400 S2=1000
0 ─────────────────────────────────── 2³²
↓ ↑
video.mp4 Now goes to NewS
Only items between NewS and prev server remapped!
Not everything like hash mod!
Implementation
#include <iostream>
#include <map>
#include <string>
#include <functional>
#include <vector>
using namespace std;
class ConsistentHashRing {
private:
map<size_t, string> ring; // hash → server name
int virtualNodes; // Replicas per server for better distribution
hash<string> hasher;
size_t hashKey(const string& key) {
return hasher(key);
}
public:
ConsistentHashRing(int vnodes = 150) : virtualNodes(vnodes) {}
// Add server to ring
void addServer(const string& server) {
for (int i = 0; i < virtualNodes; i++) {
string vnode = server + "#" + to_string(i);
size_t hash = hashKey(vnode);
ring[hash] = server;
}
cout << "✅ Added server: " << server
<< " (" << virtualNodes << " virtual nodes)\n";
}
// Remove server from ring
void removeServer(const string& server) {
for (int i = 0; i < virtualNodes; i++) {
string vnode = server + "#" + to_string(i);
size_t hash = hashKey(vnode);
ring.erase(hash);
}
cout << "❌ Removed server: " << server << "\n";
}
// Get server for a key
string getServer(const string& key) {
if (ring.empty()) {
return "";
}
size_t hash = hashKey(key);
// Find first server >= hash (clockwise on ring)
auto it = ring.lower_bound(hash);
// Wrap around if needed
if (it == ring.end()) {
it = ring.begin();
}
return it->second;
}
// Analyze distribution
void analyzeDistribution(const vector<string>& keys) {
map<string, int> serverCounts;
for (const auto& key : keys) {
string server = getServer(key);
serverCounts[server]++;
}
cout << "\n📊 DISTRIBUTION ANALYSIS\n";
cout << "═══════════════════════════════════════\n";
cout << "Total keys: " << keys.size() << "\n";
cout << "Total servers: " << (ring.size() / virtualNodes) << "\n\n";
cout << "Keys per server:\n";
for (const auto& [server, count] : serverCounts) {
double percentage = (count * 100.0) / keys.size();
cout << " " << server << ": " << count
<< " (" << (int)percentage << "%)\n";
}
}
};
int main() {
cout << "\n🌐 CONSISTENT HASHING FOR CDN\n";
cout << "═══════════════════════════════════════════════════════════\n\n";
ConsistentHashRing cdn(150); // 150 virtual nodes per server
// Initial servers
cdn.addServer("US-East");
cdn.addServer("EU-West");
cdn.addServer("Asia-Pacific");
// Simulate content requests
vector<string> content = {
"video1.mp4", "video2.mp4", "video3.mp4",
"image1.jpg", "image2.jpg", "image3.jpg",
"doc1.pdf", "doc2.pdf", "doc3.pdf",
"page1.html", "page2.html", "page3.html",
};
cout << "\n📍 INITIAL ROUTING\n";
cout << "═══════════════════════════════════════\n";
for (const auto& item : content) {
cout << item << " → " << cdn.getServer(item) << "\n";
}
cdn.analyzeDistribution(content);
// Add new server
cout << "\n🚀 ADDING NEW SERVER\n";
cout << "═══════════════════════════════════════\n";
cdn.addServer("US-West");
cout << "\n📍 ROUTING AFTER ADD\n";
cout << "═══════════════════════════════════════\n";
int remapped = 0;
for (const auto& item : content) {
string newServer = cdn.getServer(item);
cout << item << " → " << newServer;
// Check if mapping changed (in real impl, track previous)
cout << "\n";
}
cdn.analyzeDistribution(content);
cout << "\n💡 KEY BENEFITS\n";
cout << "═══════════════════════════════════════\n";
cout << "1. Adding server: Only ~25% of keys remapped\n";
cout << " (With hash mod: 100% would remap!)\n\n";
cout << "2. Removing server: Only affected keys remap\n";
cout << " (Others stay on same servers)\n\n";
cout << "3. Load balanced: Virtual nodes ensure even distribution\n";
cout << " (Each server gets ~33% with 3 servers)\n\n";
cout << "🔍 COMPLEXITY\n";
cout << "═══════════════════════════════════════\n";
cout << "getServer(): O(log n) where n = servers × virtual nodes\n";
cout << " Implementation: Binary search in sorted map\n";
cout << " For 1000 servers × 150 vnodes = 150k nodes\n";
cout << " log(150k) ≈ 17 operations - very fast!\n\n";
cout << "Space: O(servers × virtual nodes)\n";
cout << " For 1000 servers: ~600KB metadata\n";
cout << " This enables billions of requests!\n\n";
cout << "Hidden cost from Part 5 lesson:\n";
cout << "├─ Ring storage: O(s × v)\n";
cout << "├─ s = servers, v = virtual nodes per server\n";
cout << "└─ Trade-off: More vnodes = better distribution\n";
cout << " but more space & slightly slower lookup\n";
return 0;
}
Output:
🌐 CONSISTENT HASHING FOR CDN
═══════════════════════════════════════════════════════════
✅ Added server: US-East (150 virtual nodes)
✅ Added server: EU-West (150 virtual nodes)
✅ Added server: Asia-Pacific (150 virtual nodes)
📍 INITIAL ROUTING
═══════════════════════════════════════
video1.mp4 → Asia-Pacific
video2.mp4 → US-East
video3.mp4 → EU-West
image1.jpg → US-East
image2.jpg → Asia-Pacific
image3.jpg → EU-West
doc1.pdf → Asia-Pacific
doc2.pdf → EU-West
doc3.pdf → US-East
page1.html → EU-West
page2.html → US-East
page3.html → Asia-Pacific
📊 DISTRIBUTION ANALYSIS
═══════════════════════════════════════
Total keys: 12
Total servers: 3
Keys per server:
Asia-Pacific: 4 (33%)
EU-West: 4 (33%)
US-East: 4 (33%)
🚀 ADDING NEW SERVER
═══════════════════════════════════════
✅ Added server: US-West (150 virtual nodes)
📍 ROUTING AFTER ADD
═══════════════════════════════════════
video1.mp4 → Asia-Pacific
video2.mp4 → US-West
video3.mp4 → EU-West
image1.jpg → US-East
image2.jpg → Asia-Pacific
image3.jpg → US-West
doc1.pdf → Asia-Pacific
doc2.pdf → EU-West
doc3.pdf → US-East
page1.html → EU-West
page2.html → US-West
page3.html → Asia-Pacific
📊 DISTRIBUTION ANALYSIS
═══════════════════════════════════════
Total keys: 12
Total servers: 4
Keys per server:
Asia-Pacific: 4 (33%)
EU-West: 3 (25%)
US-East: 2 (16%)
US-West: 3 (25%)
💡 KEY BENEFITS
═══════════════════════════════════════
1. Adding server: Only ~25% of keys remapped
(With hash mod: 100% would remap!)
2. Removing server: Only affected keys remap
(Others stay on same servers)
3. Load balanced: Virtual nodes ensure even distribution
(Each server gets ~33% with 3 servers)
🔍 COMPLEXITY
═══════════════════════════════════════
getServer(): O(log n) where n = servers × virtual nodes
Implementation: Binary search in sorted map
For 1000 servers × 150 vnodes = 150k nodes
log(150k) ≈ 17 operations - very fast!
Space: O(servers × virtual nodes)
For 1000 servers: ~600KB metadata
This enables billions of requests!
Hidden cost from Part 5 lesson:
├─ Ring storage: O(s × v)
├─ s = servers, v = virtual nodes per server
└─ Trade-off: More vnodes = better distribution
but more space & slightly slower lookup
🔄 The Complete Caching Stack (2026)
User Request Flow:
1. Browser Cache (Client Side)
├─ Storage: localStorage, IndexedDB
├─ Policy: LRU with time expiry
└─ Hit: 0ms (instant!)
2. CDN Edge (Cloudflare, Fastly)
├─ Storage: RAM + SSD at 200+ locations
├─ Policy: LRU + Geographic routing
├─ Algorithm: Consistent hashing
└─ Hit: 10-50ms (global)
3. Application Cache (Redis, Memcached)
├─ Storage: RAM on application servers
├─ Policy: LRU or LFU
└─ Hit: 1-5ms (datacenter)
4. Database Cache (PostgreSQL Buffer)
├─ Storage: RAM, B-tree pages
├─ Policy: LRU/Clock
└─ Hit: 1ms (local)
5. Origin Database
└─ Miss: 10-100ms (disk I/O)
Goal: Hit at earliest layer possible!
🎓 Hidden Costs Throughout the Stack
The beautiful balance of Time and Space Applied to Caching
Every caching algorithm trades space for speed:
LRU Cache:
├─ Advertised: O(1) operations
├─ Hidden cost: 3×O(n) space
│ ├─ Data: O(n)
│ ├─ Hash map: O(n)
│ └─ Linked list: O(n)
└─ Plus: Pointer overhead per node (~16 bytes)
LFU Cache:
├─ Advertised: O(1) operations
├─ Hidden cost: 4×O(n) space
│ ├─ Data: O(n)
│ ├─ 3 hash maps: 3×O(n)
└─ More complex = More bugs possible
Consistent Hashing:
├─ Advertised: O(log n) lookup
├─ Hidden cost: O(servers × vnodes) space
│ └─ 1000 servers × 150 vnodes = 150k entries
└─ Trade-off: More vnodes = better distribution
but more memory & slower lookup
The recursion stack lesson from Part 5:
"Complexity has VISIBLE costs (Big-O) and
HIDDEN costs (memory overhead, bookkeeping)"
🚀 From These Patterns to 2026 Problems
LRU → Edge Computing Caches
What you learned: 2026 application:
LRU for single machine → Distributed LRU across edge nodes
Evolution:
1. Local LRU cache → Global LRU with cache coherence
2. One eviction decision → Coordinated evictions
3. Single machine RAM → Edge locations worldwide
4. ms latency → <10ms global latency
Real example: Cloudflare Workers KV
├─ LRU cache at 200+ edge locations
├─ Content replicated based on access patterns
├─ Automatic cache warming for popular content
└─ <50ms latency worldwide
Consistent Hashing → Distributed Databases
What you learned: 2026 application:
CDN content routing → Database sharding (Cassandra, DynamoDB)
Evolution:
1. Route HTTP requests → Route database writes/reads
2. Minimize cache misses → Minimize cross-shard queries
3. Handle server failures → Handle node failures gracefully
4. Content distribution → Data distribution + replication
Real example: Amazon DynamoDB
├─ Consistent hashing for partition keys
├─ Automatic resharding as data grows
├─ Handles millions of requests/sec
└─ Global tables across regions
💡 Practice Problems
Problem 1: Design YouTube's Video Caching
Requirements:
├─ 2 billion videos
├─ 100 million daily active users
├─ Most views on <1% of videos (viral)
├─ Video sizes: 10MB to 2GB
├─ Global audience
Your algorithm must:
1. Cache popular videos at edge
2. Predict what will go viral
3. Handle flash crowds (sudden spikes)
4. Minimize bandwidth costs
5. Maximize cache hit rate
Hints:
├─ Multi-tier cache (hot/warm/cold)
├─ Predictive pre-caching (ML-based)
├─ Adaptive TTL based on popularity
└─ Geographic popularity patterns
Problem 2: Design Discord's Message Cache
Requirements:
├─ 150 million users
├─ Millions of servers/channels
├─ Need: last N messages per channel
├─ Real-time delivery (<100ms)
├─ Minimize database queries
Your algorithm must:
1. Cache recent messages per channel
2. Handle both active and dormant channels
3. Evict intelligently (not all channels equal)
4. Support message edits/deletes
5. Minimize memory per user
Hints:
├─ Per-channel LRU with size limits
├─ Activity-based eviction
├─ Sliding window for recent messages
└─ Write-through cache for consistency
Problem 3: Design AWS Lambda's Code Cache
Requirements:
├─ Serverless functions (no persistent servers)
├─ Cold start problem (loading code is slow)
├─ Millions of different functions
├─ Unpredictable access patterns
├─ Balance: keep warm vs reclaim memory
Your algorithm must:
1. Predict which functions to keep warm
2. Decide eviction under memory pressure
3. Handle burst traffic
4. Minimize cold starts
5. Maximize resource utilization
Hints:
├─ Predictive warming (time patterns)
├─ Adaptive keep-alive timers
├─ LFU + recency for eviction
└─ Per-customer quotas
🎯 Key Takeaways
1. CACHING = TIME-SPACE TRADE-OFF (Part 1 callback!)
Pay memory cost → Get speed benefit
2. HIDDEN COSTS EVERYWHERE (Part 5 lesson!)
┌──────────────────────────────────┐
│ LRU: "O(1)" = 3×O(n) space │
│ LFU: "O(1)" = 4×O(n) space │
│ Consistent Hash: O(s×v) space │
└──────────────────────────────────┘
3. NO PERFECT CACHING ALGORITHM
├─ LRU: Good for recency, bad for frequency
├─ LFU: Good for frequency, bad for bursts
├─ Hybrid: More complex, more overhead
└─ Choose based on access patterns!
4. DISTRIBUTION IS HARD
Consistent hashing solves:
├─ Minimal remapping on changes
├─ Load balancing
├─ Fault tolerance
└─ But: O(log n) lookups, O(s×v) space
5. 2026 = MULTI-LAYER CACHING
Modern systems use ALL of these:
├─ Browser cache (client)
├─ CDN edge (global)
├─ Application cache (Redis)
├─ Database cache (buffer pool)
└─ Each layer has different algorithm!
🗺️ Your Journey Progress
Where you are now:
✓ Time/space trade-offs (Part 1)
✓ Algorithm design (Part 2)
✓ Graph algorithms (Part 3)
✓ Production systems (Part 4)
✓ Database internals (Part 5)
✓ Caching & CDN (Part 6) ← YOU ARE HERE
Your expanding toolkit:
├─ Can analyze hidden costs (recursion stack, memory overhead)
├─ Understand why systems are fast (caching layers)
├─ Can design eviction policies
├─ Know distribution algorithms
└─ See the full stack (browser → CDN → app → database)
Next steps:
□ Part 7: Real-time streaming algorithms
□ Part 8: AI/ML algorithms (recommendations, LLMs)
□ Part 9: Security & cryptography
□ Part 10: Autonomous systems
💬 Your Turn
Build these yourself:
- Implement LRU cache with size limits (bytes, not just count)
- Add TTL (time-to-live) to cache entries
- Build consistent hashing with dynamic virtual nodes
- Simulate cache hit rates with different policies
Analyze your favorite websites:
- Open DevTools → Network tab
- Which resources are cached?
- What are the cache headers?
- Can you see the CDN at work?
Share your findings! What's your cache hit rate? 📊
The fastest code is the code that never runs. The fastest data is the data already in memory. Master caching, and you master performance. 🚀✨
🎯 Coming Up Next: Part 7
Real-Time Streaming & Event Processing Algorithms
From cached data to live data streams:
├─ How Twitter processes trending topics in real-time
├─ Sliding window algorithms
├─ Stream joins and aggregations
├─ Handling millions of events/second
Same principles, infinite data!
Stay tuned! 📡
Top comments (0)