Cache Invalidation Strategies

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

/**
 * Core TTL-based Cache Entry
 * 
 * This fundamental data structure captures the essence of
 * time-based expiration: a value paired with metadata about
 * when it was cached and when it expires.
 */
interface CacheEntry<T> {
    /** The cached value */
    value: T;
    
    /** Unix timestamp (ms) when the entry was created */
    cachedAt: number;
    
    /** Time-to-live in milliseconds */
    ttlMs: number;
    
    /** Computed expiration timestamp */
    expiresAt: number;
}
 
/**
 * Creates a cache entry with TTL
 */
function createCacheEntry<T>(value: T, ttlMs: number): CacheEntry<T> {
    const cachedAt = Date.now();
    return {
        value,
        cachedAt,
        ttlMs,
        expiresAt: cachedAt + ttlMs,
    };
}
 
/**
 * Checks if a cache entry has expired
 * 
 * Note: This uses the current system time, which means:
 * - Clock drift between servers can cause inconsistencies
 * - System time changes (NTP sync, DST) can cause unexpected behavior
 */
function isExpired<T>(entry: CacheEntry<T>): boolean {
    return Date.now() >= entry.expiresAt;
}
 
/**
 * Returns remaining TTL in milliseconds, or 0 if expired
 */
function remainingTtl<T>(entry: CacheEntry<T>): number {
    const remaining = entry.expiresAt - Date.now();
    return Math.max(0, remaining);
}
 
// Example usage
const userProfile = createCacheEntry(
    { id: "user-123", name: "Alice", email: "[email protected]" },
    5 * 60 * 1000 // 5 minute TTL
);
 
console.log(`Expires at: ${new Date(userProfile.expiresAt).toISOString()}`);
console.log(`Is expired: ${isExpired(userProfile)}`);
console.log(`Remaining TTL: ${remainingTtl(userProfile)}ms`);

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
126
127
128
129
130

/**
 * Comprehensive Cache Implementation
 * Supporting both absolute and sliding expiration strategies
 */
 
type ExpirationStrategy = 'absolute' | 'sliding';
 
interface CacheEntryExtended<T> {
    value: T;
    cachedAt: number;
    expiresAt: number;
    ttlMs: number;
    strategy: ExpirationStrategy;
    accessCount: number;
    lastAccessedAt: number;
}
 
class ExpirationAwareCache<K, V> {
    private store = new Map<K, CacheEntryExtended<V>>();
 
    /**
     * Store a value with absolute expiration
     * The entry will expire at exactly cachedAt + ttlMs, regardless of access
     */
    setWithAbsoluteExpiration(key: K, value: V, ttlMs: number): void {
        const now = Date.now();
        this.store.set(key, {
            value,
            cachedAt: now,
            expiresAt: now + ttlMs,
            ttlMs,
            strategy: 'absolute',
            accessCount: 0,
            lastAccessedAt: now,
        });
    }
 
    /**
     * Store a value with sliding expiration
     * Each access will reset the expiration timer
     */
    setWithSlidingExpiration(key: K, value: V, ttlMs: number): void {
        const now = Date.now();
        this.store.set(key, {
            value,
            cachedAt: now,
            expiresAt: now + ttlMs,  // Initial expiration
            ttlMs,
            strategy: 'sliding',
            accessCount: 0,
            lastAccessedAt: now,
        });
    }
 
    /**
     * Get a value from cache
     * For sliding expiration, this extends the expiration time
     */
    get(key: K): V | undefined {
        const entry = this.store.get(key);
        
        if (!entry) {
            return undefined;
        }
 
        const now = Date.now();
 
        // Check if expired
        if (now >= entry.expiresAt) {
            this.store.delete(key);
            return undefined;
        }
 
        // Update access metadata
        entry.accessCount++;
        entry.lastAccessedAt = now;
 
        // For sliding expiration, reset the timer
        if (entry.strategy === 'sliding') {
            entry.expiresAt = now + entry.ttlMs;
        }
 
        return entry.value;
    }
 
    /**
     * Get cache entry metadata (useful for debugging and monitoring)
     */
    getEntryInfo(key: K): Omit<CacheEntryExtended<V>, 'value'> | undefined {
        const entry = this.store.get(key);
        if (!entry) return undefined;
 
        const { value, ...metadata } = entry;
        return {
            ...metadata,
            expiresAt: entry.strategy === 'sliding' 
                ? entry.lastAccessedAt + entry.ttlMs 
                : entry.expiresAt,
        };
    }
}
 
// Demonstration of the behavioral difference
function demonstrateStrategies() {
    const cache = new ExpirationAwareCache<string, object>();
    const TTL = 10_000; // 10 seconds
 
    // Set up both entries
    cache.setWithAbsoluteExpiration('user:absolute', { name: 'Alice' }, TTL);
    cache.setWithSlidingExpiration('user:sliding', { name: 'Bob' }, TTL);
 
    // Simulate access pattern: access every 3 seconds
    // After 15 seconds:
    // - Absolute entry: EXPIRED at T+10s, even with continuous access
    // - Sliding entry: STILL VALID because each access reset the timer
 
    let accessTime = 0;
    const interval = setInterval(() => {
        accessTime += 3000;
        
        const absoluteResult = cache.get('user:absolute');
        const slidingResult = cache.get('user:sliding');
        
        console.log(`T+${accessTime/1000}s: absolute=${absoluteResult ? 'HIT' : 'MISS'}, sliding=${slidingResult ? 'HIT' : 'MISS'}`);
        
        if (accessTime >= 15000) {
            clearInterval(interval);
        }
    }, 3000);
}

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

/**
 * TTL Optimization Calculator
 * 
 * Helps determine optimal TTL based on data characteristics
 * and system constraints
 */
 
interface TTLAnalysis {
    optimalTtlSeconds: number;
    expectedStalenessPercent: number;
    expectedCacheMissRate: number;
    recommendedTtl: number;
    reasoning: string;
}
 
interface DataCharacteristics {
    /** Average updates per hour to this data type */
    updatesPerHour: number;
    
    /** Current read requests per second */
    readsPerSecond: number;
    
    /** Latency (ms) to fetch from source */
    sourceFetchLatencyMs: number;
    
    /** Maximum acceptable staleness in seconds (0 = must always be fresh) */
    maxAcceptableStalenessSeconds: number;
    
    /** How critical is freshness? 1-10 scale */
    freshnessImportance: number;
}
 
function calculateOptimalTTL(data: DataCharacteristics): TTLAnalysis {
    const W = data.updatesPerHour / 3600; // Updates per second
    const R = data.readsPerSecond;
    
    // Normalize costs (these would be calibrated for your system)
    const C = data.sourceFetchLatencyMs / 100; // Cache miss cost
    const S = data.freshnessImportance / 5;    // Staleness cost
    
    // Calculate theoretical optimal TTL
    let optimalTtlSeconds: number;
    
    if (W === 0) {
        // Data never updates - use maximum TTL
        optimalTtlSeconds = data.maxAcceptableStalenessSeconds || 3600;
    } else {
        // Apply the optimization formula
        optimalTtlSeconds = Math.sqrt((2 * C) / (W * S));
    }
    
    // Apply constraints
    const constrainedTtl = Math.min(
        optimalTtlSeconds,
        data.maxAcceptableStalenessSeconds || Infinity
    );
    
    // Round to practical values
    const recommendedTtl = roundToPracticalTTL(constrainedTtl);
    
    // Calculate expected metrics
    const expectedStalenessPercent = W * recommendedTtl * 100;
    const cacheMissesPerSecond = Math.max(R / (recommendedTtl * R), 1 / recommendedTtl);
    const expectedCacheMissRate = (cacheMissesPerSecond / R) * 100;
    
    // Generate reasoning
    const reasoning = generateReasoning(data, recommendedTtl, expectedStalenessPercent);
    
    return {
        optimalTtlSeconds,
        expectedStalenessPercent: Math.min(100, expectedStalenessPercent),
        expectedCacheMissRate: Math.min(100, expectedCacheMissRate),
        recommendedTtl,
        reasoning,
    };
}
 
function roundToPracticalTTL(seconds: number): number {
    // Round to common TTL values for operational simplicity
    const practicalValues = [
        5, 10, 15, 30,              // Sub-minute
        60, 120, 180, 300, 600,     // Minutes (1, 2, 3, 5, 10)
        900, 1800, 3600,            // 15, 30, 60 minutes
        7200, 14400, 28800, 86400   // Hours and day
    ];
    
    return practicalValues.reduce((prev, curr) => 
        Math.abs(curr - seconds) < Math.abs(prev - seconds) ? curr : prev
    );
}
 
function generateReasoning(
    data: DataCharacteristics, 
    ttl: number, 
    staleness: number
): string {
    const parts: string[] = [];
    
    if (data.updatesPerHour < 1) {
        parts.push("Data updates infrequently, allowing longer TTL.");
    } else if (data.updatesPerHour > 60) {
        parts.push("High update frequency requires shorter TTL for freshness.");
    }
    
    if (data.freshnessImportance >= 8) {
        parts.push("Critical freshness requirement constrains TTL.");
    }
    
    if (staleness > 20) {
        parts.push(`Warning: ~${staleness.toFixed(1)}% stale reads expected.`);
    }
    
    parts.push(`Recommended TTL: ${formatDuration(ttl)}`);
    
    return parts.join(" ");
}
 
function formatDuration(seconds: number): string {
    if (seconds < 60) return `${seconds}s`;
    if (seconds < 3600) return `${Math.round(seconds / 60)}m`;
    return `${Math.round(seconds / 3600)}h`;
}
 
// Example analyses for different data types
const examples = [
    {
        name: "User profile",
        data: {
            updatesPerHour: 0.1,  // Users rarely update profiles
            readsPerSecond: 100,
            sourceFetchLatencyMs: 50,
            maxAcceptableStalenessSeconds: 300,
            freshnessImportance: 4,
        },
    },
    {
        name: "Stock price",
        data: {
            updatesPerHour: 3600, // Updates every second
            readsPerSecond: 1000,
            sourceFetchLatencyMs: 10,
            maxAcceptableStalenessSeconds: 1,
            freshnessImportance: 10,
        },
    },
    {
        name: "Product catalog",
        data: {
            updatesPerHour: 10,
            readsPerSecond: 500,
            sourceFetchLatencyMs: 100,
            maxAcceptableStalenessSeconds: 600,
            freshnessImportance: 6,
        },
    },
];
 
examples.forEach(({ name, data }) => {
    const analysis = calculateOptimalTTL(data);
    console.log(`
=== ${name} ===`);
    console.log(`Optimal TTL: ${analysis.optimalTtlSeconds.toFixed(1)}s`);
    console.log(`Recommended TTL: ${formatDuration(analysis.recommendedTtl)}`);
    console.log(`Expected staleness: ${analysis.expectedStalenessPercent.toFixed(1)}%`);
    console.log(`Reasoning: ${analysis.reasoning}`);
});

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191

/**
 * Production-Grade In-Memory Cache with TTL Support
 * 
 * Features:
 * - Configurable TTL per entry or default
 * - Automatic background cleanup of expired entries
 * - Size-bound with LRU eviction
 * - Thread-safe design (for Node.js: async-safe)
 * - Cache statistics for monitoring
 */
 
interface CacheConfig {
    defaultTtlMs: number;
    maxSize: number;
    cleanupIntervalMs: number;
}
 
interface CacheStats {
    hits: number;
    misses: number;
    evictions: number;
    expirations: number;
    currentSize: number;
}
 
class ProductionCache<K, V> {
    private store = new Map<K, { value: V; expiresAt: number; insertedAt: number }>();
    private accessOrder: K[] = [];
    private stats: CacheStats = { hits: 0, misses: 0, evictions: 0, expirations: 0, currentSize: 0 };
    private cleanupTimer: ReturnType<typeof setInterval> | null = null;
 
    constructor(private config: CacheConfig) {
        this.startBackgroundCleanup();
    }
 
    /**
     * Store a value with optional custom TTL
     */
    set(key: K, value: V, ttlMs?: number): void {
        const effectiveTtl = ttlMs ?? this.config.defaultTtlMs;
        const now = Date.now();
 
        // If already exists, remove from access order
        if (this.store.has(key)) {
            this.removeFromAccessOrder(key);
        }
 
        // Check size limit and evict if necessary
        while (this.store.size >= this.config.maxSize) {
            this.evictLRU();
        }
 
        this.store.set(key, {
            value,
            expiresAt: now + effectiveTtl,
            insertedAt: now,
        });
 
        this.accessOrder.push(key);
        this.stats.currentSize = this.store.size;
    }
 
    /**
     * Get a value, returns undefined if not found or expired
     */
    get(key: K): V | undefined {
        const entry = this.store.get(key);
 
        if (!entry) {
            this.stats.misses++;
            return undefined;
        }
 
        // Check expiration
        if (Date.now() >= entry.expiresAt) {
            this.store.delete(key);
            this.removeFromAccessOrder(key);
            this.stats.expirations++;
            this.stats.misses++;
            this.stats.currentSize = this.store.size;
            return undefined;
        }
 
        // Update access order for LRU
        this.removeFromAccessOrder(key);
        this.accessOrder.push(key);
 
        this.stats.hits++;
        return entry.value;
    }
 
    /**
     * Get-or-set pattern: returns cached value or computes and caches
     */
    async getOrSet(
        key: K, 
        factory: () => Promise<V>, 
        ttlMs?: number
    ): Promise<V> {
        const cached = this.get(key);
        if (cached !== undefined) {
            return cached;
        }
 
        const value = await factory();
        this.set(key, value, ttlMs);
        return value;
    }
 
    /**
     * Get cache statistics for monitoring
     */
    getStats(): Readonly<CacheStats> & { hitRate: number } {
        const total = this.stats.hits + this.stats.misses;
        return {
            ...this.stats,
            hitRate: total > 0 ? this.stats.hits / total : 0,
        };
    }
 
    /**
     * Clear the cache and reset statistics
     */
    clear(): void {
        this.store.clear();
        this.accessOrder = [];
        this.stats = { hits: 0, misses: 0, evictions: 0, expirations: 0, currentSize: 0 };
    }
 
    /**
     * Shutdown: stop background cleanup
     */
    shutdown(): void {
        if (this.cleanupTimer) {
            clearInterval(this.cleanupTimer);
            this.cleanupTimer = null;
        }
    }
 
    private evictLRU(): void {
        const lruKey = this.accessOrder.shift();
        if (lruKey !== undefined) {
            this.store.delete(lruKey);
            this.stats.evictions++;
        }
    }
 
    private removeFromAccessOrder(key: K): void {
        const index = this.accessOrder.indexOf(key);
        if (index !== -1) {
            this.accessOrder.splice(index, 1);
        }
    }
 
    private startBackgroundCleanup(): void {
        this.cleanupTimer = setInterval(() => {
            const now = Date.now();
            let expiredCount = 0;
 
            for (const [key, entry] of this.store) {
                if (now >= entry.expiresAt) {
                    this.store.delete(key);
                    this.removeFromAccessOrder(key);
                    expiredCount++;
                }
            }
 
            this.stats.expirations += expiredCount;
            this.stats.currentSize = this.store.size;
        }, this.config.cleanupIntervalMs);
    }
}
 
// Example usage with different TTL tiers
const cache = new ProductionCache<string, unknown>({
    defaultTtlMs: 5 * 60 * 1000, // 5 minutes default
    maxSize: 10000,
    cleanupIntervalMs: 60 * 1000, // Cleanup every minute
});
 
// Different TTLs for different data types
cache.set('user:123', { name: 'Alice' }, 10 * 60 * 1000);  // 10 min for user data
cache.set('config:app', { theme: 'dark' }, 60 * 60 * 1000); // 1 hour for config
cache.set('session:abc', { token: 'xyz' }, 30 * 60 * 1000); // 30 min for sessions
 
// Using get-or-set pattern
const userData = await cache.getOrSet(
    'user:456',
    async () => fetchUserFromDatabase(456),
    10 * 60 * 1000
);

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

/**
 * Redis TTL Patterns
 * 
 * Demonstrates proper use of Redis expiration commands
 * and common patterns for production systems
 */
import Redis from 'ioredis';
 
const redis = new Redis();
 
/**
 * Pattern 1: Basic SET with EX (seconds) or PX (milliseconds)
 */
async function setWithTTL() {
    // Set with 5 minute TTL (seconds)
    await redis.set('user:123', JSON.stringify({ name: 'Alice' }), 'EX', 300);
    
    // Set with 500ms TTL (milliseconds) - for very short-lived data
    await redis.set('rate-limit:ip:1.2.3.4', '1', 'PX', 500);
}
 
/**
 * Pattern 2: SETEX - Atomic set with seconds TTL
 * More explicit than SET ... EX
 */
async function setexPattern() {
    await redis.setex('session:abc123', 1800, JSON.stringify({
        userId: 123,
        createdAt: Date.now(),
    }));
}
 
/**
 * Pattern 3: Conditional SET with TTL
 * NX = only set if not exists, XX = only set if exists
 */
async function conditionalSetWithTTL() {
    // Only cache if not already cached (prevents overwriting fresher data)
    const result = await redis.set(
        'product:456',
        JSON.stringify({ name: 'Widget', price: 9.99 }),
        'EX', 600,
        'NX'
    );
    
    // result is 'OK' if set, null if key already existed
    return result === 'OK';
}
 
/**
 * Pattern 4: Refresh TTL without changing value
 * Useful for sliding expiration
 */
async function refreshTTL(key: string, ttlSeconds: number): Promise<boolean> {
    // EXPIRE returns 1 if key exists, 0 if not
    const result = await redis.expire(key, ttlSeconds);
    return result === 1;
}
 
/**
 * Pattern 5: Check remaining TTL
 * Useful for cache-aside refresh decisions
 */
async function getRemainingTTL(key: string): Promise<number | null> {
    const ttl = await redis.ttl(key);
    
    // TTL returns:
    // -2 if key doesn't exist
    // -1 if key exists but has no TTL (never expires)
    // >= 0 for remaining seconds
    
    if (ttl === -2) return null;  // Key doesn't exist
    if (ttl === -1) return Infinity;  // No expiration
    return ttl;
}
 
/**
 * Pattern 6: GET with TTL refresh (Sliding expiration via Lua script)
 * Atomic operation to get value and refresh TTL in one round-trip
 */
async function getAndRefreshTTL(key: string, ttlSeconds: number): Promise<string | null> {
    const luaScript = `
        local value = redis.call('GET', KEYS[1])
        if value then
            redis.call('EXPIRE', KEYS[1], ARGV[1])
        end
        return value
    `;
    
    const result = await redis.eval(luaScript, 1, key, ttlSeconds);
    return result as string | null;
}
 
/**
 * Pattern 7: EXPIREAT - Set expiration to absolute Unix timestamp
 * Useful for data that should expire at a specific time (end of day, etc.)
 */
async function expireAtSpecificTime() {
    // Expire at midnight UTC
    const midnight = new Date();
    midnight.setUTCHours(24, 0, 0, 0);
    const unixTimestamp = Math.floor(midnight.getTime() / 1000);
    
    await redis.set('daily-report:2024-01-15', JSON.stringify({ views: 1000 }));
    await redis.expireat('daily-report:2024-01-15', unixTimestamp);
}
 
/**
 * Pattern 8: PERSIST - Remove TTL (make key permanent)
 * Use carefully - only for data that should never expire
 */
async function makePermanent(key: string): Promise<boolean> {
    const result = await redis.persist(key);
    return result === 1;
}
 
/**
 * Pattern 9: Monitor TTL health
 * Useful for debugging and alerting on cache behavior
 */
async function monitorCacheTTLs(keyPattern: string): Promise<{
    key: string;
    ttl: number;
    status: 'healthy' | 'expiring-soon' | 'no-ttl' | 'missing';
}[]> {
    const keys = await redis.keys(keyPattern);
    const results = [];
    
    for (const key of keys) {
        const ttl = await redis.ttl(key);
        
        let status: 'healthy' | 'expiring-soon' | 'no-ttl' | 'missing';
        if (ttl === -2) status = 'missing';
        else if (ttl === -1) status = 'no-ttl';
        else if (ttl < 60) status = 'expiring-soon';
        else status = 'healthy';
        
        results.push({ key, ttl, status });
    }
    
    return results;
}

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

/**
 * Cache Stampede Prevention Patterns
 */
 
import Redis from 'ioredis';
 
const redis = new Redis();
 
/**
 * Pattern 1: Probabilistic Early Expiration (XFetch algorithm)
 * 
 * As expiration approaches, increase probability of pre-emptive refresh.
 * Based on: https://en.wikipedia.org/wiki/Cache_stampede#Probabilistic_early_expiration
 */
interface CachedValue<T> {
    value: T;
    delta: number;  // Time taken to compute the value
    cachedAt: number;
}
 
async function getWithProbabilisticExpiration<T>(
    key: string,
    ttlSeconds: number,
    factory: () => Promise<T>,
    beta: number = 1  // Controls aggressiveness of early expiration
): Promise<T> {
    const raw = await redis.get(key);
    
    let cached: CachedValue<T> | null = null;
    let shouldRecompute = true;
    
    if (raw) {
        cached = JSON.parse(raw);
        const now = Date.now();
        const expiresAt = cached.cachedAt + (ttlSeconds * 1000);
        const remainingMs = expiresAt - now;
        
        // XFetch formula: recompute if random() < beta * delta * log(random())
        // Probability of recompute increases as expiration approaches
        const probability = Math.max(0, 
            cached.delta * beta * Math.log(Math.random()) * -1
        );
        
        shouldRecompute = remainingMs < probability;
    }
    
    if (!shouldRecompute && cached) {
        return cached.value;
    }
    
    // Recompute value (this could be a stampede if many requests hit here)
    const startTime = Date.now();
    const value = await factory();
    const delta = Date.now() - startTime;
    
    const newEntry: CachedValue<T> = {
        value,
        delta,
        cachedAt: Date.now(),
    };
    
    await redis.setex(key, ttlSeconds, JSON.stringify(newEntry));
    return value;
}
 
/**
 * Pattern 2: Distributed Lock with Stale-While-Revalidate
 * 
 * Only one request refreshes, others get stale data or wait
 */
async function getWithLockProtection<T>(
    key: string,
    ttlSeconds: number,
    factory: () => Promise<T>,
    staleTolerance: number = 30  // Serve stale data for up to 30s during refresh
): Promise<T | null> {
    const lockKey = `lock:${key}`;
    const staleKey = `stale:${key}`;
    
    // Try to get fresh value
    let raw = await redis.get(key);
    
    if (raw) {
        return JSON.parse(raw);
    }
    
    // Fresh value expired, try to acquire lock for refresh
    const lockAcquired = await redis.set(lockKey, '1', 'EX', 10, 'NX');
    
    if (lockAcquired) {
        try {
            // We got the lock, refresh the value
            const value = await factory();
            
            // Store fresh value with TTL
            await redis.setex(key, ttlSeconds, JSON.stringify(value));
            
            // Also store as stale backup (longer TTL)
            await redis.setex(staleKey, ttlSeconds + staleTolerance, JSON.stringify(value));
            
            return value;
        } finally {
            // Release lock
            await redis.del(lockKey);
        }
    } else {
        // Another request is refreshing, try to return stale
        const staleRaw = await redis.get(staleKey);
        
        if (staleRaw) {
            // Return stale value while fresh value is being computed
            return JSON.parse(staleRaw);
        }
        
        // No stale value available, wait briefly and retry
        await new Promise(resolve => setTimeout(resolve, 100));
        raw = await redis.get(key);
        return raw ? JSON.parse(raw) : null;
    }
}
 
/**
 * Pattern 3: Background Refresh with Last-Access Tracking
 * 
 * Proactively refresh frequently-accessed entries before expiration
 */
class BackgroundRefreshCache<K extends string, V> {
    private refreshThreshold = 0.8; // Refresh when 80% of TTL elapsed
    
    constructor(private redis: Redis) {}
    
    async get(key: K, ttlSeconds: number, factory: () => Promise<V>): Promise<V> {
        // Track that this key was accessed
        const accessKey = `access:${key}`;
        await this.redis.set(accessKey, Date.now().toString(), 'EX', ttlSeconds * 2);
        
        const raw = await this.redis.get(key);
        
        if (raw) {
            const ttl = await this.redis.ttl(key);
            const elapsed = ttlSeconds - ttl;
            const elapsedRatio = elapsed / ttlSeconds;
            
            // If approaching expiration and recently accessed, trigger background refresh
            if (elapsedRatio > this.refreshThreshold) {
                this.scheduleBackgroundRefresh(key, ttlSeconds, factory);
            }
            
            return JSON.parse(raw);
        }
        
        // Cache miss, compute synchronously
        const value = await factory();
        await this.redis.setex(key, ttlSeconds, JSON.stringify(value));
        return value;
    }
    
    private async scheduleBackgroundRefresh(
        key: K, 
        ttlSeconds: number, 
        factory: () => Promise<V>
    ): Promise<void> {
        // Fire and forget - don't await
        setImmediate(async () => {
            try {
                const value = await factory();
                await this.redis.setex(key, ttlSeconds, JSON.stringify(value));
            } catch (error) {
                // Log but don't throw - current value is still valid
                console.error(`Background refresh failed for ${key}:`, error);
            }
        });
    }
}