When to Use Advanced Data Structures

If range query structures are surgical instruments for slicing through data, caching structures are memory banks for avoiding work entirely. A well-designed cache doesn't just speed up individual operations—it fundamentally changes the economics of your system by trading space for time, turning expensive repeated computations into near-instantaneous retrievals.

But caching is far from a silver bullet. Every cache decision involves tradeoffs: memory consumption, staleness of data, complexity of invalidation, and the overhead of cache management itself. Knowing when to cache, what eviction policy to use, and how to design the cache interface separates thoughtful system design from naive optimization attempts.

This page exhaustively covers cache design considerations—from the fundamental question of whether you need a cache at all, through eviction policy selection, to the intricate details of cache sizing and invalidation strategies.

The first—and most important—cache design decision is whether to cache at all. Caching introduces complexity: additional code, potential consistency bugs, memory overhead, and the perpetual question of 'is my cache serving stale data?' Before adding a cache, rigorously evaluate whether it's truly necessary.

When a cache reaches capacity, an eviction policy determines which existing item to remove to make room for new entries. The choice of eviction policy dramatically affects cache performance—the difference between a well-tuned policy and a poor one can be a 2-3x difference in hit rate.

Deep Dive: LRU vs LFU

The LRU vs LFU decision is the most common policy choice engineers face. Let's analyze when each excels:

LRU (Least Recently Used):

• Assumes temporal locality: recently accessed items will be accessed again
• Excellent for user sessions, web page caching, database query results
• Vulnerable to 'scan' patterns: a one-time sequential read evicts useful cached data
• Implementation: O(1) with hash map + doubly linked list (the classic LeetCode problem)

LFU (Least Frequently Used):

• Assumes popularity: frequently accessed items should stay in cache
• Excellent for static assets, CDN edge caches, content that doesn't change often
• Slow to adapt: an item accessed 1000 times yesterday stays even if never accessed today
• Implementation: O(1) possible but more complex (multiple frequency buckets)

The Hybrid Approach: Many production systems use hybrid policies. For example:

• TTL + LRU: Items expire after a time limit, and LRU handles capacity limits
• LFU with aging: Frequency counts decay over time to adapt to changing patterns
• Window-TinyLFU (used by Caffeine cache): Admits based on recency, evicts based on frequency

Choosing the right cache size is a delicate balancing act. Too small, and hit rates suffer. Too large, and you waste memory that could be used elsewhere (or cause garbage collection issues). The optimal size depends on your access patterns, available memory, and acceptable miss rates.

The Working Set Concept:

The working set is the subset of data actively being accessed during a given time window. Ideally, your cache should be large enough to hold the entire working set:

• If cache size ≥ working set: Hit rate approaches 100% for repeated accesses
• If cache size < working set: Thrashing—items are evicted before they can be reused
• If cache size >> working set: Wasted memory, no additional benefit

Estimating Working Set:

1. Measure unique items in a time window: Count distinct keys accessed per minute/hour/day
2. Apply the 80/20 rule: Often 20% of items receive 80% of accesses
3. Simulate with different cache sizes: Run production logs through cache simulation
4. Monitor hit rates in production: Adjust based on observed behavior

Memory Budget Allocation:

Caches don't exist in isolation. Consider the memory budget across your entire system:

Multiple Caches: Most systems have multiple caches (query cache, session cache, computed result cache). Each needs its own sizing strategy:

• Prioritize caches with highest impact (most expensive underlying operations)
• Consider cache hierarchies: L1 (small, fast) → L2 (larger, slower)
• Monitor and adjust allocations based on relative hit rates

Phil Karlton famously said: "There are only two hard things in Computer Science: cache invalidation and naming things." Cache invalidation—ensuring cached data doesn't become stale—is indeed one of the most challenging aspects of cache design.

The Invalidation Dilemma:

Every invalidation strategy involves tradeoffs:

Too Aggressive (Frequent Invalidation):

• Cache hit rate drops
• Underlying resources see more load
• Latency increases

Too Conservative (Rare Invalidation):

• Stale data served to users
• Potential data consistency issues
• User experience problems

Finding the Balance:

The right approach depends on your staleness tolerance:

Beyond choosing eviction policies and invalidation strategies, the implementation pattern you select affects code maintainability, testability, and the potential for bugs.

Pattern 1: Inline Caching (Anti-Pattern for Complex Cases)

function getUser(userId: string): User {
    // Cache check inline with business logic
    const cached = cache.get(`user:${userId}`);
    if (cached) return cached;
    
    const user = database.fetchUser(userId);
    cache.put(`user:${userId}`, user, { ttl: 3600 });
    return user;
}

Problems:

• Cache logic mixed with business logic
• Hard to test business logic in isolation
• Cache key construction duplicated everywhere
• Easy to forget cache in new code paths

Pattern 2: Decorator/Wrapper Pattern (Recommended)

function cached<T>(
    fn: (...args: any[]) => Promise<T>,
    keyGenerator: (...args: any[]) => string,
    options: { ttl: number }
): (...args: any[]) => Promise<T> {
    return async (...args) => {
        const key = keyGenerator(...args);
        const cached = await cache.get(key);
        if (cached !== undefined) return cached;
        
        const result = await fn(...args);
        await cache.put(key, result, options);
        return result;
    };
}

// Usage
const getUserCached = cached(
    (userId: string) => database.fetchUser(userId),
    (userId) => `user:${userId}`,
    { ttl: 3600 }
);

Benefits:

• Business logic remains pure
• Cache behavior is consistent and declarative
• Easy to test both cached and uncached versions
• Cache logic is centralized

Pattern 3: Repository Pattern with Caching Layer

For complex domain models, implement caching as a repository decorator:

interface UserRepository {
    findById(id: string): Promise<User>;
    save(user: User): Promise<void>;
}

class DatabaseUserRepository implements UserRepository {
    async findById(id: string): Promise<User> {
        return this.db.query('SELECT * FROM users WHERE id = ?', [id]);
    }
    async save(user: User): Promise<void> {
        await this.db.query('UPDATE users SET ... WHERE id = ?', [user]);
    }
}

class CachedUserRepository implements UserRepository {
    constructor(
        private underlying: UserRepository,
        private cache: Cache<User>
    ) {}
    
    async findById(id: string): Promise<User> {
        const cached = await this.cache.get(id);
        if (cached) return cached;
        
        const user = await this.underlying.findById(id);
        await this.cache.put(id, user);
        return user;
    }
    
    async save(user: User): Promise<void> {
        await this.underlying.save(user);
        await this.cache.invalidate(user.id);  // Invalidation on write
    }
}

Benefits:

• Clear separation of concerns
• Caching is optional and swappable
• Invalidation logic is co-located with write operations
• Testable at each layer

In multi-server deployments, caching introduces additional complexity. Each server could maintain its own local cache, leading to inconsistencies, or you could use a shared distributed cache, introducing network latency and failure modes.

Two-Tier Caching (The Production Standard):

Most production systems use a two-tier approach:

1. L1 (Local, per-server): Small, extremely fast, short TTL
2. L2 (Distributed, shared): Larger, consistent, longer TTL

Request → Check L1 → Hit? Return
                    → Miss? Check L2 → Hit? Populate L1, Return
                                     → Miss? Fetch from DB, Populate L1+L2, Return

L1 Configuration:

• Size: 100-1000 items (depends on item size)
• TTL: 10-60 seconds (short to limit staleness)
• No cross-server invalidation needed (TTL handles it)

L2 Configuration:

• Size: Tens of thousands to millions of items
• TTL: Minutes to hours
• Technology: Redis, Memcached, etc.

Just as important as knowing when to cache is recognizing scenarios where caching would be counterproductive. Adding a cache in these situations wastes development time, increases complexity, and may even hurt performance.

The Decision Heuristic:

Before implementing a cache, answer these questions:

1. What's the expected hit rate? (Below 50% is usually not worth it)
2. How expensive is the underlying operation? (Must be >>cache overhead)
3. How frequently does data change? (High churn = low cache effectiveness)
4. What's the staleness tolerance? (Zero tolerance = don't cache or very short TTL)
5. What's the memory budget? (Cache competes with other memory needs)

If any answer is unfavorable, strongly reconsider whether caching is appropriate.

The Performance Testing Imperative:

Never assume caching helps. Implement it behind a feature flag, measure hit rates and latency with and without the cache, and only enable it if metrics prove it's beneficial:

const cacheEnabled = featureFlags.get('user-cache-enabled');

const getUser = cacheEnabled 
    ? cachedGetUser 
    : directGetUser;

We've covered the complete landscape of cache design considerations. Let's synthesize the key principles:

What's Next:

The final page of this module addresses the overarching question that underlies every decision we've discussed: how to balance the power of advanced data structures against their implementation complexity. We'll develop a framework for deciding when sophistication is warranted versus when simplicity wins.