Application-Level Caching

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

// Simple in-memory cache with TTL support
interface CacheEntry<T> {
  value: T;
  expiresAt: number;
}
 
class InMemoryCache<T> {
  private cache: Map<string, CacheEntry<T>> = new Map();
  private defaultTtlMs: number;
 
  constructor(defaultTtlSeconds: number = 300) {
    this.defaultTtlMs = defaultTtlSeconds * 1000;
  }
 
  set(key: string, value: T, ttlSeconds?: number): void {
    const ttl = ttlSeconds ? ttlSeconds * 1000 : this.defaultTtlMs;
    this.cache.set(key, {
      value,
      expiresAt: Date.now() + ttl,
    });
  }
 
  get(key: string): T | undefined {
    const entry = this.cache.get(key);
    
    if (!entry) {
      return undefined;
    }
    
    if (Date.now() > entry.expiresAt) {
      this.cache.delete(key);
      return undefined;
    }
    
    return entry.value;
  }
 
  delete(key: string): boolean {
    return this.cache.delete(key);
  }
 
  clear(): void {
    this.cache.clear();
  }
 
  // Periodic cleanup of expired entries
  startCleanup(intervalMs: number = 60000): NodeJS.Timeout {
    return setInterval(() => {
      const now = Date.now();
      for (const [key, entry] of this.cache) {
        if (now > entry.expiresAt) {
          this.cache.delete(key);
        }
      }
    }, intervalMs);
  }
}
 
// Usage
const userCache = new InMemoryCache<User>(300); // 5-minute default TTL
 
async function getUser(userId: string): Promise<User> {
  // Check cache first
  const cached = userCache.get(`user:${userId}`);
  if (cached) {
    return cached;
  }
  
  // Cache miss - fetch from database
  const user = await db.users.findUnique({ where: { id: userId } });
  
  if (user) {
    userCache.set(`user:${userId}`, user);
  }
  
  return user;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

// Classic LRU Cache: O(1) get and set operations
class LRUNode<K, V> {
  key: K;
  value: V;
  prev: LRUNode<K, V> | null = null;
  next: LRUNode<K, V> | null = null;
 
  constructor(key: K, value: V) {
    this.key = key;
    this.value = value;
  }
}
 
class LRUCache<K, V> {
  private capacity: number;
  private cache: Map<K, LRUNode<K, V>> = new Map();
  
  // Sentinel nodes simplify edge cases
  private head: LRUNode<K, V>;  // Most recent
  private tail: LRUNode<K, V>;  // Least recent
 
  constructor(capacity: number) {
    this.capacity = capacity;
    
    // Initialize sentinels
    this.head = new LRUNode<K, V>(null as any, null as any);
    this.tail = new LRUNode<K, V>(null as any, null as any);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
 
  get(key: K): V | undefined {
    const node = this.cache.get(key);
    
    if (!node) {
      return undefined;
    }
    
    // Move to front (most recently used)
    this.moveToHead(node);
    return node.value;
  }
 
  set(key: K, value: V): void {
    const existing = this.cache.get(key);
    
    if (existing) {
      // Update existing entry
      existing.value = value;
      this.moveToHead(existing);
      return;
    }
    
    // New entry
    const node = new LRUNode(key, value);
    this.cache.set(key, node);
    this.addToHead(node);
    
    // Evict if over capacity
    if (this.cache.size > this.capacity) {
      const evicted = this.removeTail();
      if (evicted) {
        this.cache.delete(evicted.key);
        this.onEvict?.(evicted.key, evicted.value);
      }
    }
  }
 
  delete(key: K): boolean {
    const node = this.cache.get(key);
    if (!node) return false;
    
    this.removeNode(node);
    this.cache.delete(key);
    return true;
  }
 
  // Optional callback when items are evicted
  onEvict?: (key: K, value: V) => void;
 
  // Helper methods for doubly-linked list operations
  private addToHead(node: LRUNode<K, V>): void {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next!.prev = node;
    this.head.next = node;
  }
 
  private removeNode(node: LRUNode<K, V>): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }
 
  private moveToHead(node: LRUNode<K, V>): void {
    this.removeNode(node);
    this.addToHead(node);
  }
 
  private removeTail(): LRUNode<K, V> | null {
    const node = this.tail.prev;
    if (node === this.head) return null;
    this.removeNode(node!);
    return node;
  }
 
  get size(): number {
    return this.cache.size;
  }
 
  // Iterate from most to least recent
  *entries(): IterableIterator<[K, V]> {
    let node = this.head.next;
    while (node !== this.tail) {
      yield [node!.key, node!.value];
      node = node!.next;
    }
  }
}
 
// Usage with eviction callback for metrics
const cache = new LRUCache<string, User>(1000);
cache.onEvict = (key, value) => {
  metrics.increment('cache.evictions');
  console.log(`Evicted user ${key} from cache`);
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

// Basic memoization decorator
function memoize<T extends (...args: any[]) => any>(
  fn: T,
  options: {
    maxSize?: number;
    ttlMs?: number;
    keyFn?: (...args: Parameters<T>) => string;
  } = {}
): T {
  const { 
    maxSize = 100, 
    ttlMs, 
    keyFn = (...args) => JSON.stringify(args) 
  } = options;
  
  const cache = new Map<string, { 
    value: ReturnType<T>; 
    expiresAt?: number 
  }>();
  const keyOrder: string[] = [];
 
  return ((...args: Parameters<T>): ReturnType<T> => {
    const key = keyFn(...args);
    
    const cached = cache.get(key);
    if (cached) {
      if (!ttlMs || Date.now() < cached.expiresAt!) {
        return cached.value;
      }
      // Expired - remove and continue
      cache.delete(key);
      keyOrder.splice(keyOrder.indexOf(key), 1);
    }
    
    const result = fn(...args);
    
    cache.set(key, {
      value: result,
      expiresAt: ttlMs ? Date.now() + ttlMs : undefined,
    });
    keyOrder.push(key);
    
    // LRU eviction
    while (keyOrder.length > maxSize) {
      const oldestKey = keyOrder.shift()!;
      cache.delete(oldestKey);
    }
    
    return result;
  }) as T;
}
 
// Usage: Memoizing expensive computation
const expensiveCalculation = memoize(
  (input: number): number => {
    // Simulate expensive work
    let result = 0;
    for (let i = 0; i < 10000000; i++) {
      result += Math.sin(input + i);
    }
    return result;
  },
  { maxSize: 50, ttlMs: 60000 }
);
 
// Usage: Memoizing API calls with custom key
interface ProductQuery {
  category: string;
  minPrice?: number;
  maxPrice?: number;
  sortBy?: string;
}
 
const fetchProducts = memoize(
  async (query: ProductQuery): Promise<Product[]> => {
    const response = await fetch(`/api/products?${new URLSearchParams(query as any)}`);
    return response.json();
  },
  {
    maxSize: 100,
    ttlMs: 300000, // 5 minutes
    // Custom key: normalize query to avoid cache misses for equivalent queries
    keyFn: (query) => {
      const normalized = {
        category: query.category,
        minPrice: query.minPrice ?? 0,
        maxPrice: query.maxPrice ?? Infinity,
        sortBy: query.sortBy ?? 'relevance',
      };
      return JSON.stringify(normalized);
    },
  }
);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

// Memoize that handles concurrent async calls correctly
function memoizeAsync<T extends (...args: any[]) => Promise<any>>(
  fn: T,
  options: {
    maxSize?: number;
    ttlMs?: number;
    keyFn?: (...args: Parameters<T>) => string;
  } = {}
): T {
  const { maxSize = 100, ttlMs, keyFn = (...args) => JSON.stringify(args) } = options;
  
  // Store both resolved values AND in-flight promises
  const cache = new Map<string, {
    promise?: Promise<Awaited<ReturnType<T>>>;
    value?: Awaited<ReturnType<T>>;
    expiresAt?: number;
    state: 'pending' | 'resolved' | 'rejected';
  }>();
 
  return (async (...args: Parameters<T>): Promise<Awaited<ReturnType<T>>> => {
    const key = keyFn(...args);
    
    const cached = cache.get(key);
    
    if (cached) {
      // Check expiration
      if (ttlMs && cached.expiresAt && Date.now() > cached.expiresAt) {
        cache.delete(key);
      } else if (cached.state === 'resolved') {
        return cached.value!;
      } else if (cached.state === 'pending') {
        // Wait for existing in-flight request
        return cached.promise!;
      }
      // If rejected, allow retry
    }
    
    // Create new request
    const promise = fn(...args);
    
    cache.set(key, {
      promise,
      state: 'pending',
    });
    
    try {
      const value = await promise;
      
      cache.set(key, {
        value,
        state: 'resolved',
        expiresAt: ttlMs ? Date.now() + ttlMs : undefined,
      });
      
      // LRU eviction
      if (cache.size > maxSize) {
        const oldest = cache.keys().next().value;
        cache.delete(oldest);
      }
      
      return value;
    } catch (error) {
      cache.set(key, { state: 'rejected' });
      throw error;
    }
  }) as T;
}
 
// Now concurrent calls share the same request
const getUser = memoizeAsync(
  async (userId: string) => {
    console.log(`Fetching user ${userId}`); // Only logs once per userId
    const response = await fetch(`/api/users/${userId}`);
    return response.json();
  },
  { ttlMs: 60000 }
);
 
// These three concurrent calls result in ONE fetch:
await Promise.all([
  getUser('123'),
  getUser('123'),
  getUser('123'),
]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

import { LRUCache } from 'lru-cache';
 
// Configure LRU cache with comprehensive options
const userCache = new LRUCache<string, User>({
  // Maximum number of items
  max: 500,
  
  // Maximum size in bytes (optional, requires sizeCalculation)
  maxSize: 50 * 1024 * 1024, // 50 MB
  sizeCalculation: (value, key) => {
    return JSON.stringify(value).length + key.length;
  },
  
  // TTL in milliseconds
  ttl: 1000 * 60 * 5, // 5 minutes
  
  // Update age on get? (affects TTL behavior)
  updateAgeOnGet: false,
  updateAgeOnHas: false,
  
  // Called when items are evicted
  dispose: (value, key, reason) => {
    console.log(`Cache evicted: ${key}, reason: ${reason}`);
    // 'set' - replaced by new value
    // 'delete' - explicitly deleted
    // 'evict' - removed due to size/count limit
    // 'expire' - TTL expired
  },
  
  // If true, disposed items can still be retrieved until GC
  noDisposeOnSet: false,
  
  // Allow stale items to be returned while fetching fresh
  allowStale: true,
  
  // Async fetch function for cache-aside pattern
  fetchMethod: async (key, staleValue, { options, signal }) => {
    const response = await fetch(`/api/users/${key}`, { signal });
    if (!response.ok) {
      // Return stale if fetch fails
      if (staleValue) return staleValue;
      throw new Error(`User ${key} not found`);
    }
    return response.json();
  },
  
  // Background fetch when TTL is about to expire
  ttlAutopurge: true,
});
 
// Basic operations
userCache.set('user:123', user);
const cached = userCache.get('user:123');
userCache.delete('user:123');
 
// Using fetch method (stale-while-revalidate built in)
const user = await userCache.fetch('user:123');
 
// Get stats
console.log({
  size: userCache.size,
  calculatedSize: userCache.calculatedSize,
  hits: userCache.hits,
  misses: userCache.misses,
  hitRate: userCache.hits / (userCache.hits + userCache.misses),
});

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

// BAD: Missing version - stale data after format changes
const badKey1 = `user:${userId}`;
 
// GOOD: Include version for schema changes
const goodKey1 = `v1:user:${userId}`;
 
// BAD: Object as key - different orderings produce different strings
const badKey2 = JSON.stringify({ category, sort, page });
// { category: 'A', sort: 'price' } !== { sort: 'price', category: 'A' }
 
// GOOD: Normalize key components
function normalizeKey(params: Record<string, any>): string {
  const sorted = Object.keys(params)
    .sort()
    .map(k => `${k}=${params[k]}`)
    .join('&');
  return sorted;
}
 
// BAD: Unbounded cardinality - caches for every unique search
const badKey3 = `search:${userQuery}`; // "red shoes" vs "Red shoes" vs "RED SHOES"
 
// GOOD: Normalize and limit cardinality
function searchCacheKey(query: string, page: number): string {
  const normalized = query.toLowerCase().trim().replace(/\s+/g, ' ');
  // Consider: truncate very long queries, or hash them
  if (normalized.length > 100) {
    return `search:${hash(normalized)}:page:${page}`;
  }
  return `search:${normalized}:page:${page}`;
}
 
// Key namespacing strategy for multi-tenant applications
interface CacheKeyBuilder {
  tenant: string;
  entity: string;
  id: string;
  version?: number;
}
 
function buildKey({ tenant, entity, id, version = 1 }: CacheKeyBuilder): string {
  return `v${version}:${tenant}:${entity}:${id}`;
}
 
// Examples:
buildKey({ tenant: 'acme', entity: 'user', id: '12345' });
// => "v1:acme:user:12345"
 
buildKey({ tenant: 'acme', entity: 'product', id: 'sku-789', version: 2 });
// => "v2:acme:product:sku-789"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

// Pattern 1: Cache-Aside (most common)
async function getUserCacheAside(userId: string): Promise<User> {
  const cacheKey = `user:${userId}`;
  
  // Step 1: Check cache
  const cached = await cache.get(cacheKey);
  if (cached) {
    return cached;
  }
  
  // Step 2: Fetch from source on miss
  const user = await database.users.findById(userId);
  
  // Step 3: Populate cache
  if (user) {
    await cache.set(cacheKey, user, { ttl: 300 });
  }
  
  return user;
}
 
// Pattern 2: Read-Through (via library support)
const userCache = new LRUCache<string, User>({
  max: 1000,
  ttl: 300000,
  // Library handles fetching on miss
  fetchMethod: async (userId) => {
    return database.users.findById(userId);
  },
});
 
async function getUserReadThrough(userId: string): Promise<User> {
  // Single call - cache handles miss logic
  return userCache.fetch(userId);
}
 
// Pattern 3: Cache Warming (Proactive Population)
async function warmUserCache(userIds: string[]): Promise<void> {
  console.log(`Warming cache for ${userIds.length} users`);
  
  // Batch fetch from database
  const users = await database.users.findMany({
    where: { id: { in: userIds } },
  });
  
  // Populate cache in parallel
  await Promise.all(
    users.map(user => cache.set(`user:${user.id}`, user, { ttl: 300 }))
  );
  
  console.log(`Cache warmed: ${users.length} users`);
}
 
// Warm on service startup for critical data
async function initializeService() {
  // Get IDs of recently active users
  const recentUserIds = await database.users.findMany({
    where: { lastActiveAt: { gte: new Date(Date.now() - 86400000) } },
    select: { id: true },
  });
  
  await warmUserCache(recentUserIds.map(u => u.id));
}
 
// Pattern 4: Preventing Thundering Herd with Coalescing
const inFlightRequests = new Map<string, Promise<any>>();
 
async function getUserWithCoalescing(userId: string): Promise<User> {
  const cacheKey = `user:${userId}`;
  
  const cached = await cache.get(cacheKey);
  if (cached) return cached;
  
  // Check if request already in flight
  const inFlight = inFlightRequests.get(cacheKey);
  if (inFlight) {
    return inFlight; // Wait for existing request
  }
  
  // New request - track it
  const request = (async () => {
    try {
      const user = await database.users.findById(userId);
      if (user) {
        await cache.set(cacheKey, user, { ttl: 300 });
      }
      return user;
    } finally {
      inFlightRequests.delete(cacheKey);
    }
  })();
  
  inFlightRequests.set(cacheKey, request);
  return request;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

// Event-based invalidation with domain events
class UserService {
  async updateUser(userId: string, updates: Partial<User>): Promise<User> {
    // Update database
    const user = await database.users.update({
      where: { id: userId },
      data: updates,
    });
    
    // Invalidate cache entries
    await this.invalidateUserCache(userId);
    
    // Publish event for other services
    await eventBus.publish('user.updated', { userId, changes: updates });
    
    return user;
  }
  
  private async invalidateUserCache(userId: string): Promise<void> {
    // Invalidate direct user cache
    await cache.delete(`user:${userId}`);
    
    // Invalidate derived/related caches
    await cache.delete(`user:${userId}:profile`);
    await cache.delete(`user:${userId}:permissions`);
    
    // Invalidate aggregate caches that include this user
    // This is where it gets complex...
    const userTeams = await database.teamMemberships.findMany({
      where: { userId },
      select: { teamId: true },
    });
    
    for (const { teamId } of userTeams) {
      await cache.delete(`team:${teamId}:members`);
    }
  }
}
 
// Tag-based invalidation for related data
class TaggedCache {
  private cache: Map<string, any> = new Map();
  private tagIndex: Map<string, Set<string>> = new Map();
  
  set(key: string, value: any, tags: string[]): void {
    this.cache.set(key, value);
    
    // Index by tags
    for (const tag of tags) {
      if (!this.tagIndex.has(tag)) {
        this.tagIndex.set(tag, new Set());
      }
      this.tagIndex.get(tag)!.add(key);
    }
  }
  
  invalidateByTag(tag: string): number {
    const keys = this.tagIndex.get(tag);
    if (!keys) return 0;
    
    let count = 0;
    for (const key of keys) {
      if (this.cache.delete(key)) {
        count++;
      }
    }
    
    this.tagIndex.delete(tag);
    return count;
  }
}
 
// Usage
const cache = new TaggedCache();
 
cache.set('product:123', product, ['product:123', 'category:electronics', 'featured']);
cache.set('product:456', product2, ['product:456', 'category:electronics']);
 
// When electronics category changes
cache.invalidateByTag('category:electronics'); // Clears both products