11- Caches¶

Overview¶

Caches are mechanisms that store frequently accessed data in faster, local storage to reduce the time and cost of accessing remote or slow data sources. They are used in applications such as web browsers, file systems, and memory hierarchies.

Introducing Caches¶

Caches act as a middle layer between a fast, limited memory and a slower, larger data store.
Example: Web browsers cache images, videos, and page data to avoid repeated downloads.
Cache hit: Requested data is found in the cache.
Cache miss: Data is not in the cache and must be retrieved from slower storage.

Storage Hierarchy Analogy¶

Registers / CPU Cache: Very fast but small.
RAM: Larger but slower.
Hard Drives / SSDs: Much larger, slower still.
Network / Cloud: Virtually unlimited but slowest.
Tradeoff: Speed vs. Capacity vs. Cost

Coffee Shop Analogy¶

Barista’s counter = Cache
Coffee station = Slower storage
Each coffee flavor = Data item
Choosing which coffees to keep near the register models caching strategy and eviction.

Cache Eviction¶

When the cache is full, older data is evicted to make room for new data.
Goal: Keep the most useful data nearby.
Eviction strategies determine what data to remove.

LRU (Least Recently Used) Eviction¶

Stores the most recently used items.
When full, removes the item that has not been used for the longest time.
Based on the principle of temporal locality: recently accessed items are likely to be accessed again soon.

LRU Cache Structure¶

Combines two data structures: 1. Hash Table — for O(1) lookup by key. 2. Queue (Doubly Linked List) — to track usage order.

Core Data Structures¶

LRUCache {
    HashTable: ht
    Queue: q
    Integer: max_size
    Integer: current_size
}

CacheEntry {
    Type: key
    Type: value
    QueueListNode: node
}

Cache Lookup Operation¶

CacheLookup(cache, key):
    entry = HashTableLookup(cache.ht, key)

    IF entry == null:  # Cache miss
        IF cache is full:
            remove oldest item
        data = retrieve_from_slow_storage(key)
        enqueue key to queue
        insert (key, data) into hash table

    ELSE:  # Cache hit
        move entry to back of queue (most recent)

    return entry.value

Updating Recency with a Doubly Linked Queue¶

Allows efficient removal and reinsertion of nodes.
Each node has pointers to both its previous and next node.

QueueListNode {
    value
    next
    prev
}

Queue Operations¶

Enqueue: Adds to the back of the queue.
Dequeue: Removes from the front.
RemoveNode: Removes a specific node in O(1) using its pointers.

Other Eviction Strategies¶

MRU (Most Recently Used): - Evicts the most recently accessed item. - Useful when repeated accesses are rare (e.g., ebooks).
LFU (Least Frequently Used): - Evicts items with the fewest total accesses. - Effective for stable access patterns.
Predictive Eviction: - Uses models to predict future accesses. - Can outperform simple strategies but adds complexity.

Why Caches Matter¶

Performance Boost: Reduce access to slow data sources.
Tradeoff Awareness: Memory size vs. speed vs. cost.
Parameter Tuning: Cache size and eviction policy strongly affect performance.
Data Structure Integration: Combines hash tables and queues for efficient caching.

Key Takeaways¶

Caches accelerate data access by storing recent or frequently used data.
LRU caches balance simplicity and effectiveness.
Eviction strategies depend on the use case and data access patterns.
Understanding data storage hierarchy is crucial for efficient algorithm design.