FIFO (First In First Out) — HLD: Cache Invalidation… | OneNoughtOne

0/121

System Design (HLD)Cache Invalidation Strategies

Cache Invalidation Strategies

LevelIntermediate

Duration120 mins

TopicCache Invalidation Strategies

5 / 6

FIFO (First In First Out)

The Virtue of Simplicity

LRU tracks recency. LFU tracks frequency. Both require per-access bookkeeping—updating linked lists, incrementing counters, managing data structures. This overhead is typically negligible, but there are scenarios where even this cost matters. FIFO (First-In-First-Out) takes a radically different approach: evict the oldest item by insertion time, regardless of access patterns . No recency tracking. No frequency counting. Just a queue where items enter at one end and leave from the other. This sounds naive—and in many ways it is. FIFO ignores valuable information about which items are actually being used. Yet FIFO persists in production systems because simplicity has its own value: predictable behavior, trivial implementation, zero per-access overhead, and surprisingly acceptable hit rates in certain workloads.

What You Will Learn

By the end of this page, you will understand FIFO's mechanics and trade-offs, when FIFO is surprisingly effective, its improved variants (Second-Chance, CLOCK), and practical scenarios where FIFO outperforms more complex policies. You'll learn to recognize workloads where simplicity wins.

FIFO Conceptual Model

The Core Idea: Imagine a queue at a bakery. Customers enter at the back and are served from the front. The customer who's been waiting longest gets served next. Similarly, FIFO evicts the cache entry that was inserted earliest, regardless of how recently or frequently it was accessed. Formal Definition: On insert: Add entry to the tail of the queue On access: Return value if present; do not modify position (this is the key difference from LRU) On eviction: Remove and discard the entry at the head of the queue (oldest insertion) FIFO's defining characteristic is that accessing an item does NOT affect its eviction priority . Only insertion time matters.

FIFO Cache with capacity 4
 
Insert order: A → B → C → D (oldest → newest)
 
Queue state:
┌────────────────────────────────────────────┐
│ HEAD                               TAIL    │
│ (oldest)                        (newest)   │
│                                            │
│  [A] ──→ [B] ──→ [C] ──→ [D]              │
│   ↑                        ↑               │
│ Evict                   Insert             │
│ Here                    Here               │
└────────────────────────────────────────────┘
 
Access B, C, D repeatedly (no state change):
Queue: [A] → [B] → [C] → [D]  (unchanged!)
 
Insert E (need to evict):
1. Evict A (head, oldest)
2. Insert E at tail
 
Queue: [B] → [C] → [D] → [E]
 
Key observation: A was evicted even though it might have been
accessed frequently. FIFO doesn't care about access patterns.
 
Compare to LRU:
- If we accessed B, C, D repeatedly, A would be LRU
- FIFO and LRU evict the same item (A), but for different reasons
- FIFO: "A is oldest"  
- LRU: "A is least recently used"

What FIFO Ignores: Recency: Item accessed 1 second ago vs. 1 hour ago are treated identically Frequency: Item accessed 1000 times vs. 1 time are treated identically Value/cost: Large expensive-to-compute items vs. small cheap items are treated identically By ignoring all access information, FIFO achieves maximum simplicity at the cost of responsiveness to actual usage patterns. What FIFO Preserves: Insertion order determinism: Given the same insert sequence, eviction order is completely predictable Zero per-access overhead: No bookkeeping on reads, only on writes Constant memory overhead: Just a single queue pointer per entry Implementation simplicity: A circular buffer or simple queue suffices

FIFO ≠ Always Bad

FIFO's reputation as a "naive" algorithm overlooks scenarios where it performs well. For workloads with uniform access patterns, short-lived relevance, or where item freshness correlates with insertion time, FIFO can match or exceed LRU hit rates—with less overhead.

FIFO Implementation: Circular Buffer Efficiency

FIFO's simplicity enables highly efficient implementations. The most elegant uses a circular buffer (ring buffer)—a fixed-size array where head and tail pointers wrap around. Circular Buffer Advantages: No memory allocation after initialization: The array is pre-allocated O(1) insert and evict: Just pointer increments with modulo Cache-friendly: Contiguous memory improves CPU cache utilization No pointers between nodes: Lower memory overhead than linked lists

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
from typing import TypeVar, Generic, Optional, Dict
from dataclasses import dataclass
 
K = TypeVar('K')
V = TypeVar('V')
 
@dataclass
class FIFOEntry(Generic[K, V]):
    key: K
    value: V
    valid: bool = True  # For O(1) logical deletion
 
class FIFOCache(Generic[K, V]):
    """
    FIFO cache using circular buffer for memory efficiency.
    
    No per-access overhead. O(1) insert and evict.
    """
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        
        # Circular buffer of entries
        self.buffer: list[Optional[FIFOEntry[K, V]]] = [None] * capacity
        
        # Head points to oldest entry (next to evict)
        # Tail points to next insertion slot
        self.head = 0
        self.tail = 0
        self.size = 0
        
        # Key → buffer index for O(1) lookup
        self.index_map: Dict[K, int] = {}
    
    def get(self, key: K) -> Optional[V]:
        """
        Retrieve value by key.
        
        Unlike LRU, this does NOT modify any state.
        Time complexity: O(1)
        """
        if key not in self.index_map:
            return None
        
        idx = self.index_map[key]
        entry = self.buffer[idx]
        
        if entry is None or not entry.valid:
            # Entry was logically deleted
            del self.index_map[key]
            return None
        
        return entry.value
    
    def put(self, key: K, value: V) -> Optional[K]:
        """
        Store key-value pair.
        
        Returns evicted key if eviction occurred.
        Time complexity: O(1)
        """
        evicted_key = None
        
        # If key exists, update in place
        if key in self.index_map:
            idx = self.index_map[key]
            entry = self.buffer[idx]
            if entry and entry.valid:
                entry.value = value
                return None
        
        # Need new slot, may need to evict
        if self.size >= self.capacity:
            evicted_key = self._evict()
        
        # Insert at tail
        self.buffer[self.tail] = FIFOEntry(key=key, value=value, valid=True)
        self.index_map[key] = self.tail
        
        self.tail = (self.tail + 1) % self.capacity
        self.size += 1
        
        return evicted_key
    
    def _evict(self) -> K:
        """
        Evict the oldest entry (at head).
        
        Handles logically deleted entries by skipping them.
        """
        while self.size > 0:
            entry = self.buffer[self.head]
            
            if entry and entry.valid:
                # This is a valid entry to evict
                entry.valid = False
                evicted_key = entry.key
                
                if evicted_key in self.index_map:
                    del self.index_map[evicted_key]
                
                self.head = (self.head + 1) % self.capacity
                self.size -= 1
                
                return evicted_key
            else:
                # Skip invalid entries
                self.head = (self.head + 1) % self.capacity
                if entry:
                    self.size -= 1
        
        raise RuntimeError("Cannot evict from empty cache")
    
    def delete(self, key: K) -> bool:
        """
        Logically delete key from cache.
        
        We can't remove from middle of circular buffer efficiently,
        so we mark as invalid. Space is reclaimed on eviction.
        """
        if key not in self.index_map:
            return False
        
        idx = self.index_map[key]
        entry = self.buffer[idx]
        
        if entry and entry.valid:
            entry.valid = False
            del self.index_map[key]
            return True
        
        return False
    
    def __len__(self) -> int:
        return len(self.index_map)
    
    def __contains__(self, key: K) -> bool:
        return key in self.index_map
 
 
# Usage:
cache = FIFOCache[str, bytes](capacity=1000)
 
cache.put("key1", b"value1")
cache.put("key2", b"value2")
cache.put("key3", b"value3")
 
# Access doesn't change eviction order
_ = cache.get("key1")  # key1 is still oldest, will be evicted first
 
cache.put("key4", b"value4")  # No eviction yet (capacity 1000)
 
# ... after 998 more inserts, key1 will be evicted first

Logical vs Physical Deletion

Circular buffers can't efficiently remove elements from the middle. We use logical deletion (mark as invalid) and clean up during eviction. This adds a bit of space waste but maintains O(1) operations. For high-deletion workloads, consider a doubly-linked list instead.

When FIFO Surprisingly Works Well

Despite ignoring access patterns, FIFO achieves acceptable hit rates for several workload classes: 1. Uniform Random Access When every item has equal probability of access, no eviction policy can do better than random—and FIFO effectively approximates random eviction. Since there's no predictable pattern to exploit, LRU and LFU provide no advantage. 2. Working Set Smaller Than Cache If your working set fits entirely in cache, eviction policy is irrelevant—everything stays cached. FIFO's simplicity becomes pure advantage. 3. Time-Correlated Insertion and Access When newer items are more likely to be accessed (recency correlates with insertion time), FIFO naturally retains relevant items. Examples: Log processing (recent logs more relevant) Event streams (recent events queried more) Social feeds (newer posts shown first)

4. Short-Lived Relevance When items are only relevant for a brief window after insertion, FIFO's age-based eviction matches the access pattern. After the relevance window, items aren't accessed regardless of eviction policy. 5. High-Throughput, Low-Latency Requirements When every microsecond counts and the workload is write-heavy, FIFO's zero per-access overhead can outweigh marginal hit rate differences. 6. Hardware Caches Many CPU caches use FIFO or FIFO-like policies because they're implementable in hardware with minimal transistors. The slight hit rate loss is worth the speed and power savings.

FIFO vs LRU Hit Rate Comparison by Workload
Workload Type	FIFO Hit Rate	LRU Hit Rate	Winner
Uniform random access	~65%	~65%	Tie
Strongly temporal (recent is hot)	~75%	~90%	LRU by 15%
Working set < cache size	~100%	~100%	Tie
Zipf distribution (few items dominate)	~60%	~85%	LRU by 25%
Short-lived items (10s relevance window)	~80%	~82%	Tie (±2%)
Sequential scan	~0%	~0%	Both terrible

The Key Insight: FIFO performs within 10-20% of LRU for many real workloads. That hit rate gap closes further when you factor in: Implementation cost: FIFO is simpler to implement correctly Operational cost: Fewer parameters to tune CPU cost: Zero overhead per access Memory cost: Less metadata per entry For some systems, these savings exceed the marginal hit rate benefit of LRU.

When FIFO Fails Badly

FIFO fails catastrophically when a small set of highly popular items should be retained indefinitely. Consider a cache holding 'config' and 'user:12345'. Under FIFO, config (inserted early) will be evicted even if accessed constantly. LRU/LFU would retain it. For workloads with stable hot items, avoid FIFO.

Second-Chance Algorithm: FIFO with a Safety Net

Second-Chance (also called Clock Algorithm) adds minimal recency tracking to FIFO. Each entry has a single "reference bit" that's set on access. During eviction: Look at the head entry (oldest) If reference bit is 0: evict this entry If reference bit is 1: clear the bit, move entry to tail, try next This gives recently-accessed items a "second chance" before eviction. Items accessed since their last second-chance check get pushed back in the queue. Behavior: An item accessed at least once since entering gets one reprieve An item not accessed since its last second chance gets evicted In the worst case, all items have been accessed, and we circle through everyone giving second chances until someone loses theirs

Clock Algorithm with capacity 4
 
State: (entry, reference_bit)
Clock hand points to next eviction candidate
 
        ┌────────────────────────────────┐
        │   (A,0)  (B,1)  (C,0)  (D,1)  │
        │     ↑                          │
        │   clock                        │
        │   hand                         │
        └────────────────────────────────┘
 
Need to evict for new entry E:
 
Step 1: Check A, ref=0 → EVICT A
        ┌────────────────────────────────┐
        │   (E,1)  (B,1)  (C,0)  (D,1)  │
        │           ↑                    │
        │         clock                  │
        │         hand                   │
        └────────────────────────────────┘
 
Later, need to evict for new entry F:
 
Step 1: Check B, ref=1 → Clear bit, move on
        │   (E,1)  (B,0)  (C,0)  (D,1)  │
        │                  ↑             │
 
Step 2: Check C, ref=0 → EVICT C
        ┌────────────────────────────────┐
        │   (E,1)  (B,0)  (F,1)  (D,1)  │
        │                        ↑       │
        │                      clock     │
        │                      hand      │
        └────────────────────────────────┘
 
B got a second chance and survived.
C (never accessed after second chance) was evicted.

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
from typing import TypeVar, Generic, Optional, Dict
from dataclasses import dataclass
 
K = TypeVar('K')
V = TypeVar('V')
 
@dataclass
class ClockEntry(Generic[K, V]):
    key: K
    value: V
    ref_bit: bool = True  # Set to True on insert and access
 
class SecondChanceCache(Generic[K, V]):
    """
    Second-Chance (Clock) cache eviction algorithm.
    
    Like FIFO, but recently-accessed items get a second chance
    before eviction. Uses a single reference bit per entry.
    
    Time complexity: O(1) amortized (circular scan on eviction)
    Space overhead: 1 bit per entry
    """
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        
        # Circular buffer
        self.buffer: list[Optional[ClockEntry[K, V]]] = [None] * capacity
        
        # Clock hand position
        self.hand = 0
        
        # Key → buffer index
        self.index_map: Dict[K, int] = {}
    
    def get(self, key: K) -> Optional[V]:
        """
        Retrieve value by key.
        
        On hit, sets the reference bit (gives second chance).
        """
        if key not in self.index_map:
            return None
        
        idx = self.index_map[key]
        entry = self.buffer[idx]
        
        if entry:
            entry.ref_bit = True  # Mark as recently used
            return entry.value
        
        return None
    
    def put(self, key: K, value: V) -> Optional[K]:
        """
        Store key-value pair.
        
        Returns evicted key if eviction occurred.
        """
        evicted_key = None
        
        # Update existing entry
        if key in self.index_map:
            idx = self.index_map[key]
            entry = self.buffer[idx]
            if entry:
                entry.value = value
                entry.ref_bit = True
                return None
        
        # Need eviction if at capacity
        if len(self.index_map) >= self.capacity:
            evicted_key = self._evict_clock()
        
        # Find empty slot (will exist after eviction)
        # In circular buffer, hand now points to empty slot
        insert_idx = self.hand
        
        self.buffer[insert_idx] = ClockEntry(key=key, value=value, ref_bit=True)
        self.index_map[key] = insert_idx
        
        # Advance hand past the new entry
        self.hand = (self.hand + 1) % self.capacity
        
        return evicted_key
    
    def _evict_clock(self) -> K:
        """
        Clock algorithm eviction.
        
        Scan from hand position:
        - If ref_bit=0: evict
        - If ref_bit=1: clear bit, continue
        
        Amortized O(1) because each entry is visited at most twice
        per eviction cycle.
        """
        while True:
            entry = self.buffer[self.hand]
            
            if entry is None:
                # Empty slot, move on
                self.hand = (self.hand + 1) % self.capacity
                continue
            
            if not entry.ref_bit:
                # No second chance, evict this entry
                evicted_key = entry.key
                
                self.buffer[self.hand] = None
                del self.index_map[evicted_key]
                
                # Hand stays here; this slot is now empty for insertion
                return evicted_key
            else:
                # Give second chance: clear bit, move on
                entry.ref_bit = False
                self.hand = (self.hand + 1) % self.capacity
    
    def delete(self, key: K) -> bool:
        """Explicitly delete an entry."""
        if key not in self.index_map:
            return False
        
        idx = self.index_map[key]
        self.buffer[idx] = None
        del self.index_map[key]
        
        return True
    
    def __len__(self) -> int:
        return len(self.index_map)
 
 
# Second-Chance provides LRU-like behavior with FIFO-like simplicity
# It's widely used in operating systems for page replacement

Second-Chance Approximates LRU

In practice, Second-Chance achieves 90-95% of LRU's hit rate with much simpler implementation. It's the default algorithm in many operating systems (virtual memory page replacement) because it balances effectiveness with hardware implementation simplicity.

CLOCK-Pro and Advanced Variants

Basic Second-Chance/CLOCK can be enhanced to provide scan resistance and better hit rates. CLOCK-Pro is a notable variant that rivals LRU-K in effectiveness. CLOCK-Pro Key Ideas: Three lists: Hot, Cold, and Test pages (instead of one) Tracking non-resident pages: Maintains metadata for recently evicted pages to detect re-access patterns Adaptive hot page allocation: Dynamically adjusts hot vs. cold page ratio based on workload Why Track Evicted Pages? If an item is accessed, evicted (because it seemed cold), and quickly re-accessed, it was actually hot but got unlucky. By tracking recent evictions, CLOCK-Pro can: Detect this pattern Increase hot page allocation Admit re-accessed items directly to hot status

CLOCK-Pro maintains three circular lists:
 
┌─────────────────────────────────────────────────────────────────┐
│                          CLOCK-Pro                               │
└─────────────────────────────────────────────────────────────────┘
 
1. HOT CLOCK (resident, frequently accessed)
   ┌──────────────────────────────────┐
   │ [H1] → [H2] → [H3] → [H4] → ... │
   │  ↑                               │
   │ hand_hot                         │
   └──────────────────────────────────┘
   - Items here have been accessed recently
   - Protected from eviction
   - Can be demoted to cold if ref bit clear
 
2. COLD CLOCK (resident, infrequently accessed)  
   ┌──────────────────────────────────┐
   │ [C1] → [C2] → [C3] → [C4] → ... │
   │  ↑                               │
   │ hand_cold                        │
   └──────────────────────────────────┘
   - Items here are eviction candidates
   - If accessed, promote to hot
   - If not accessed, evict
 
3. TEST CLOCK (non-resident metadata only)
   ┌──────────────────────────────────┐
   │ [T1] → [T2] → [T3] → [T4] → ... │
   │  ↑                               │
   │ hand_test                        │
   └──────────────────────────────────┘
   - Tracks recently evicted items (just their keys)
   - If re-accessed while in test, item was "hot" all along
   - Triggers increase in hot allocation
 
Eviction Flow:
1. When cold clock hand reaches item with ref=0, evict it
2. Move item's key to test clock
3. If same key is accessed while in test clock:
   - Admit directly to hot clock
   - Increase hot clock capacity (adaptive!)

Other CLOCK Variants: CAR (Clock with Adaptive Replacement): Combines CLOCK with ARC-like adaptive sizing. Maintains two CLOCK lists (one for recency, one for frequency) and adapts their sizes based on workload. LIRS (Low Inter-reference Recency Set): Focuses on inter-reference recency (IRR): time between consecutive accesses to the same item. Items with low IRR are considered hot. Often outperforms LRU on benchmark workloads. 2Q (Two Queue): Simple variant: new items enter a FIFO queue (A1). If accessed again, they graduate to LRU queue (Am). Provides scan resistance with minimal complexity. These variants share a common theme: Pure FIFO/CLOCK is too simple, pure LRU is too expensive. The sweet spot is adding minimal tracking (reference bits, ghost entries) to approximate LRU's behavior.

Implementation Complexity vs. Benefit

CLOCK-Pro and similar algorithms can match or exceed LRU hit rates while maintaining O(1) amortized operations. However, they're significantly more complex to implement correctly. For most application-level caches, LRU remains the practical choice. CLOCK variants shine in operating systems and hardware where the per-operation overhead difference matters at the microsecond level.

FIFO Queues for TTL-Based Expiration

A powerful use case for FIFO is implementing TTL-based expiration efficiently. When all items have the same TTL, they expire in insertion order—exactly what FIFO tracks. The Pattern: Item A inserted at T=0, TTL=60s \to expires at T=60 Item B inserted at T=10, TTL=60s \to expires at T=70 Item C inserted at T=20, TTL=60s \to expires at T=80 Items expire in insertion order: A, B, C FIFO naturally evicts in this order! Efficient TTL Cleanup: Rather than scanning all items to check expiration, a FIFO queue with uniform TTL only needs to check the head. If the head hasn't expired, nothing has expired.

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
import time
from typing import TypeVar, Generic, Optional, Dict
from dataclasses import dataclass
from collections import deque
 
K = TypeVar('K')
V = TypeVar('V')
 
@dataclass
class TTLEntry(Generic[K, V]):
    key: K
    value: V
    expires_at: float
 
class TTLCache(Generic[K, V]):
    """
    Cache with TTL expiration using FIFO queue for cleanup.
    
    When all items have the same TTL, FIFO order = expiration order.
    This allows O(1) cleanup of expired items by only checking the head.
    
    For variable TTL, this still works but may need to skip non-expired items.
    """
    
    def __init__(self, ttl_seconds: float = 300.0, capacity: int = 10000):
        self.ttl = ttl_seconds
        self.capacity = capacity
        
        # FIFO queue of entries (ordered by insertion = expiration time)
        self.queue: deque[TTLEntry[K, V]] = deque()
        
        # Key → latest entry (handles overwrites)
        self.store: Dict[K, TTLEntry[K, V]] = {}
    
    def get(self, key: K) -> Optional[V]:
        """Get value if present and not expired."""
        self._cleanup_expired()
        
        if key not in self.store:
            return None
        
        entry = self.store[key]
        
        if time.time() >= entry.expires_at:
            # Expired (edge case: just expired)
            del self.store[key]
            return None
        
        return entry.value
    
    def put(self, key: K, value: V, ttl: Optional[float] = None) -> None:
        """
        Store value with TTL.
        
        If key exists, creates new entry (old entry becomes orphan,
        cleaned up when reached in queue).
        """
        self._cleanup_expired()
        
        ttl = ttl or self.ttl
        expires_at = time.time() + ttl
        
        entry = TTLEntry(key=key, value=value, expires_at=expires_at)
        
        # Add to queue and store
        self.queue.append(entry)
        self.store[key] = entry
        
        # Enforce capacity (evict beyond capacity)
        while len(self.store) > self.capacity:
            self._evict_oldest()
    
    def _cleanup_expired(self) -> int:
        """
        Remove all expired entries from the head of queue.
        
        O(k) where k = number of expired items (usually small).
        Amortizes to O(1) over put/get operations.
        """
        now = time.time()
        cleaned = 0
        
        while self.queue:
            oldest = self.queue[0]
            
            if now >= oldest.expires_at:
                # Expired, remove from queue
                self.queue.popleft()
                
                # Only remove from store if this is the current entry for key
                # (handles overwritten entries)
                if oldest.key in self.store and self.store[oldest.key] is oldest:
                    del self.store[oldest.key]
                    cleaned += 1
            else:
                # Head hasn't expired; nothing has expired
                # This is the efficiency win!
                break
        
        return cleaned
    
    def _evict_oldest(self) -> None:
        """Force evict the oldest entry (for capacity management)."""
        if not self.queue:
            return
        
        oldest = self.queue.popleft()
        
        if oldest.key in self.store and self.store[oldest.key] is oldest:
            del self.store[oldest.key]
    
    def __len__(self) -> int:
        return len(self.store)
 
 
# Usage:
cache = TTLCache[str, dict](ttl_seconds=300, capacity=10000)
 
cache.put("session:abc", {"user_id": 123, "role": "admin"})
# Expires in 300 seconds
 
# Later...
session = cache.get("session:abc")  # Returns value if not expired, None otherwise
 
# Cleanup happens automatically on get/put
# No background thread needed for uniform TTL!

Variable TTL Extension: For variable TTL, the FIFO approach still provides benefits: Lazy cleanup: Most expired items cluster near the head Tombstone minimization: Items expire roughly in order Background cleanup: Sweep through queue, skip non-expired items The optimization degrades with high TTL variance but remains useful for "mostly uniform" TTL patterns (e.g., all items TTL 5-10 minutes).

Time-Based Bucketing

For highly variable TTL, use time-based buckets : separate FIFO queues for items expiring each minute. When a minute passes, evict the entire bucket atomically. This provides O(1) expiration for any TTL granularity down to your bucket size.

FIFO in Production Systems

Let's examine where FIFO and its variants are used in real production systems. Operating Systems: Virtual memory page replacement commonly uses CLOCK (Second-Chance). The reference bit is naturally set by hardware MMU on page access, making it essentially free. Linux uses an approximation of LRU-2 with active/inactive lists that function similarly to CLOCK. Database Buffer Pools: Some databases offer FIFO as a buffer pool option (alongside LRU). InnoDB (MySQL) uses a modified FIFO for certain internal caches. The rationale: for high-churn workloads, LRU's overhead exceeds its hit rate benefit. Hardware Caches: CPU L1 caches often use FIFO or pseudo-LRU (an approximation using tree-based selection). True LRU requires O(log n) comparators per access—too expensive in silicon. FIFO needs only a counter.

Eviction Policy Usage in Real Systems
System	Primary Policy	Why This Choice
CPU L1/L2 Cache	Pseudo-LRU / FIFO	Hardware simplicity; cycle time critical
Linux Page Cache	Two-list (CLOCK variant)	Balance between recency and scan resistance
Redis (default)	Approximate LRU	Good general-purpose; configurable to LFU
Memcached	Slab-based LRU	Each size class has own LRU for fairness
Caffeine (Java)	W-TinyLFU	Near-optimal hit rate; acceptable overhead
CDN edge caches	LRU / LFU (configurable)	Content type dependent; static prefers LFU
Browser HTTP cache	LRU	Prioritizes recently viewed pages
DNS caches	TTL-based (FIFO for cleanup)	RFC mandates TTL; FIFO cleanup is natural

When to Choose FIFO in Application Caches:

FIFO is Appropriate When

•Write-heavy workload: If you're inserting far more than reading, per-access overhead matters less, and FIFO's insert efficiency shines.
•Uniform access patterns: If items are accessed roughly equally, LRU/LFU provide no differentiation benefit.
•Strict TTL requirements: If data must expire after exactly N seconds, FIFO naturally supports TTL cleanup.
•Embedded/constrained systems: When memory for per-entry metadata is precious, FIFO minimizes overhead.
•Debugging/predictability needed: FIFO's deterministic eviction order simplifies reasoning about cache behavior.
•You've benchmarked and it's close enough: If FIFO hit rate is within 5-10% of LRU for your workload, the simplicity win may be worth it.

Don't Default to FIFO

FIFO should be a conscious choice, not a default. Most applications benefit from LRU's recency tracking. Choose FIFO when you've identified a specific reason (latency, simplicity, workload characteristics) and verified hit rate is acceptable for your use case.

System Design (HLD)Cache Invalidation Strategies

Cache Invalidation Strategies

LevelIntermediate

Duration120 mins

TopicCache Invalidation Strategies

5 / 6

FIFO (First In First Out)

The Virtue of Simplicity

LRU tracks recency. LFU tracks frequency. Both require per-access bookkeeping—updating linked lists, incrementing counters, managing data structures. This overhead is typically negligible, but there are scenarios where even this cost matters. FIFO (First-In-First-Out) takes a radically different approach: evict the oldest item by insertion time, regardless of access patterns . No recency tracking. No frequency counting. Just a queue where items enter at one end and leave from the other. This sounds naive—and in many ways it is. FIFO ignores valuable information about which items are actually being used. Yet FIFO persists in production systems because simplicity has its own value: predictable behavior, trivial implementation, zero per-access overhead, and surprisingly acceptable hit rates in certain workloads.

What You Will Learn

By the end of this page, you will understand FIFO's mechanics and trade-offs, when FIFO is surprisingly effective, its improved variants (Second-Chance, CLOCK), and practical scenarios where FIFO outperforms more complex policies. You'll learn to recognize workloads where simplicity wins.

FIFO Conceptual Model

The Core Idea: Imagine a queue at a bakery. Customers enter at the back and are served from the front. The customer who's been waiting longest gets served next. Similarly, FIFO evicts the cache entry that was inserted earliest, regardless of how recently or frequently it was accessed. Formal Definition: On insert: Add entry to the tail of the queue On access: Return value if present; do not modify position (this is the key difference from LRU) On eviction: Remove and discard the entry at the head of the queue (oldest insertion) FIFO's defining characteristic is that accessing an item does NOT affect its eviction priority . Only insertion time matters.

FIFO Cache with capacity 4
 
Insert order: A → B → C → D (oldest → newest)
 
Queue state:
┌────────────────────────────────────────────┐
│ HEAD                               TAIL    │
│ (oldest)                        (newest)   │
│                                            │
│  [A] ──→ [B] ──→ [C] ──→ [D]              │
│   ↑                        ↑               │
│ Evict                   Insert             │
│ Here                    Here               │
└────────────────────────────────────────────┘
 
Access B, C, D repeatedly (no state change):
Queue: [A] → [B] → [C] → [D]  (unchanged!)
 
Insert E (need to evict):
1. Evict A (head, oldest)
2. Insert E at tail
 
Queue: [B] → [C] → [D] → [E]
 
Key observation: A was evicted even though it might have been
accessed frequently. FIFO doesn't care about access patterns.
 
Compare to LRU:
- If we accessed B, C, D repeatedly, A would be LRU
- FIFO and LRU evict the same item (A), but for different reasons
- FIFO: "A is oldest"  
- LRU: "A is least recently used"

What FIFO Ignores: Recency: Item accessed 1 second ago vs. 1 hour ago are treated identically Frequency: Item accessed 1000 times vs. 1 time are treated identically Value/cost: Large expensive-to-compute items vs. small cheap items are treated identically By ignoring all access information, FIFO achieves maximum simplicity at the cost of responsiveness to actual usage patterns. What FIFO Preserves: Insertion order determinism: Given the same insert sequence, eviction order is completely predictable Zero per-access overhead: No bookkeeping on reads, only on writes Constant memory overhead: Just a single queue pointer per entry Implementation simplicity: A circular buffer or simple queue suffices

FIFO ≠ Always Bad

FIFO's reputation as a "naive" algorithm overlooks scenarios where it performs well. For workloads with uniform access patterns, short-lived relevance, or where item freshness correlates with insertion time, FIFO can match or exceed LRU hit rates—with less overhead.

FIFO Implementation: Circular Buffer Efficiency

FIFO's simplicity enables highly efficient implementations. The most elegant uses a circular buffer (ring buffer)—a fixed-size array where head and tail pointers wrap around. Circular Buffer Advantages: No memory allocation after initialization: The array is pre-allocated O(1) insert and evict: Just pointer increments with modulo Cache-friendly: Contiguous memory improves CPU cache utilization No pointers between nodes: Lower memory overhead than linked lists

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
from typing import TypeVar, Generic, Optional, Dict
from dataclasses import dataclass
 
K = TypeVar('K')
V = TypeVar('V')
 
@dataclass
class FIFOEntry(Generic[K, V]):
    key: K
    value: V
    valid: bool = True  # For O(1) logical deletion
 
class FIFOCache(Generic[K, V]):
    """
    FIFO cache using circular buffer for memory efficiency.
    
    No per-access overhead. O(1) insert and evict.
    """
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        
        # Circular buffer of entries
        self.buffer: list[Optional[FIFOEntry[K, V]]] = [None] * capacity
        
        # Head points to oldest entry (next to evict)
        # Tail points to next insertion slot
        self.head = 0
        self.tail = 0
        self.size = 0
        
        # Key → buffer index for O(1) lookup
        self.index_map: Dict[K, int] = {}
    
    def get(self, key: K) -> Optional[V]:
        """
        Retrieve value by key.
        
        Unlike LRU, this does NOT modify any state.
        Time complexity: O(1)
        """
        if key not in self.index_map:
            return None
        
        idx = self.index_map[key]
        entry = self.buffer[idx]
        
        if entry is None or not entry.valid:
            # Entry was logically deleted
            del self.index_map[key]
            return None
        
        return entry.value
    
    def put(self, key: K, value: V) -> Optional[K]:
        """
        Store key-value pair.
        
        Returns evicted key if eviction occurred.
        Time complexity: O(1)
        """
        evicted_key = None
        
        # If key exists, update in place
        if key in self.index_map:
            idx = self.index_map[key]
            entry = self.buffer[idx]
            if entry and entry.valid:
                entry.value = value
                return None
        
        # Need new slot, may need to evict
        if self.size >= self.capacity:
            evicted_key = self._evict()
        
        # Insert at tail
        self.buffer[self.tail] = FIFOEntry(key=key, value=value, valid=True)
        self.index_map[key] = self.tail
        
        self.tail = (self.tail + 1) % self.capacity
        self.size += 1
        
        return evicted_key
    
    def _evict(self) -> K:
        """
        Evict the oldest entry (at head).
        
        Handles logically deleted entries by skipping them.
        """
        while self.size > 0:
            entry = self.buffer[self.head]
            
            if entry and entry.valid:
                # This is a valid entry to evict
                entry.valid = False
                evicted_key = entry.key
                
                if evicted_key in self.index_map:
                    del self.index_map[evicted_key]
                
                self.head = (self.head + 1) % self.capacity
                self.size -= 1
                
                return evicted_key
            else:
                # Skip invalid entries
                self.head = (self.head + 1) % self.capacity
                if entry:
                    self.size -= 1
        
        raise RuntimeError("Cannot evict from empty cache")
    
    def delete(self, key: K) -> bool:
        """
        Logically delete key from cache.
        
        We can't remove from middle of circular buffer efficiently,
        so we mark as invalid. Space is reclaimed on eviction.
        """
        if key not in self.index_map:
            return False
        
        idx = self.index_map[key]
        entry = self.buffer[idx]
        
        if entry and entry.valid:
            entry.valid = False
            del self.index_map[key]
            return True
        
        return False
    
    def __len__(self) -> int:
        return len(self.index_map)
    
    def __contains__(self, key: K) -> bool:
        return key in self.index_map
 
 
# Usage:
cache = FIFOCache[str, bytes](capacity=1000)
 
cache.put("key1", b"value1")
cache.put("key2", b"value2")
cache.put("key3", b"value3")
 
# Access doesn't change eviction order
_ = cache.get("key1")  # key1 is still oldest, will be evicted first
 
cache.put("key4", b"value4")  # No eviction yet (capacity 1000)
 
# ... after 998 more inserts, key1 will be evicted first

Logical vs Physical Deletion

Circular buffers can't efficiently remove elements from the middle. We use logical deletion (mark as invalid) and clean up during eviction. This adds a bit of space waste but maintains O(1) operations. For high-deletion workloads, consider a doubly-linked list instead.

When FIFO Surprisingly Works Well

Despite ignoring access patterns, FIFO achieves acceptable hit rates for several workload classes: 1. Uniform Random Access When every item has equal probability of access, no eviction policy can do better than random—and FIFO effectively approximates random eviction. Since there's no predictable pattern to exploit, LRU and LFU provide no advantage. 2. Working Set Smaller Than Cache If your working set fits entirely in cache, eviction policy is irrelevant—everything stays cached. FIFO's simplicity becomes pure advantage. 3. Time-Correlated Insertion and Access When newer items are more likely to be accessed (recency correlates with insertion time), FIFO naturally retains relevant items. Examples: Log processing (recent logs more relevant) Event streams (recent events queried more) Social feeds (newer posts shown first)

4. Short-Lived Relevance When items are only relevant for a brief window after insertion, FIFO's age-based eviction matches the access pattern. After the relevance window, items aren't accessed regardless of eviction policy. 5. High-Throughput, Low-Latency Requirements When every microsecond counts and the workload is write-heavy, FIFO's zero per-access overhead can outweigh marginal hit rate differences. 6. Hardware Caches Many CPU caches use FIFO or FIFO-like policies because they're implementable in hardware with minimal transistors. The slight hit rate loss is worth the speed and power savings.

FIFO vs LRU Hit Rate Comparison by Workload
Workload Type	FIFO Hit Rate	LRU Hit Rate	Winner
Uniform random access	~65%	~65%	Tie
Strongly temporal (recent is hot)	~75%	~90%	LRU by 15%
Working set < cache size	~100%	~100%	Tie
Zipf distribution (few items dominate)	~60%	~85%	LRU by 25%
Short-lived items (10s relevance window)	~80%	~82%	Tie (±2%)
Sequential scan	~0%	~0%	Both terrible

The Key Insight: FIFO performs within 10-20% of LRU for many real workloads. That hit rate gap closes further when you factor in: Implementation cost: FIFO is simpler to implement correctly Operational cost: Fewer parameters to tune CPU cost: Zero overhead per access Memory cost: Less metadata per entry For some systems, these savings exceed the marginal hit rate benefit of LRU.

When FIFO Fails Badly

FIFO fails catastrophically when a small set of highly popular items should be retained indefinitely. Consider a cache holding 'config' and 'user:12345'. Under FIFO, config (inserted early) will be evicted even if accessed constantly. LRU/LFU would retain it. For workloads with stable hot items, avoid FIFO.

Second-Chance Algorithm: FIFO with a Safety Net

Second-Chance (also called Clock Algorithm) adds minimal recency tracking to FIFO. Each entry has a single "reference bit" that's set on access. During eviction: Look at the head entry (oldest) If reference bit is 0: evict this entry If reference bit is 1: clear the bit, move entry to tail, try next This gives recently-accessed items a "second chance" before eviction. Items accessed since their last second-chance check get pushed back in the queue. Behavior: An item accessed at least once since entering gets one reprieve An item not accessed since its last second chance gets evicted In the worst case, all items have been accessed, and we circle through everyone giving second chances until someone loses theirs

Clock Algorithm with capacity 4
 
State: (entry, reference_bit)
Clock hand points to next eviction candidate
 
        ┌────────────────────────────────┐
        │   (A,0)  (B,1)  (C,0)  (D,1)  │
        │     ↑                          │
        │   clock                        │
        │   hand                         │
        └────────────────────────────────┘
 
Need to evict for new entry E:
 
Step 1: Check A, ref=0 → EVICT A
        ┌────────────────────────────────┐
        │   (E,1)  (B,1)  (C,0)  (D,1)  │
        │           ↑                    │
        │         clock                  │
        │         hand                   │
        └────────────────────────────────┘
 
Later, need to evict for new entry F:
 
Step 1: Check B, ref=1 → Clear bit, move on
        │   (E,1)  (B,0)  (C,0)  (D,1)  │
        │                  ↑             │
 
Step 2: Check C, ref=0 → EVICT C
        ┌────────────────────────────────┐
        │   (E,1)  (B,0)  (F,1)  (D,1)  │
        │                        ↑       │
        │                      clock     │
        │                      hand      │
        └────────────────────────────────┘
 
B got a second chance and survived.
C (never accessed after second chance) was evicted.

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
from typing import TypeVar, Generic, Optional, Dict
from dataclasses import dataclass
 
K = TypeVar('K')
V = TypeVar('V')
 
@dataclass
class ClockEntry(Generic[K, V]):
    key: K
    value: V
    ref_bit: bool = True  # Set to True on insert and access
 
class SecondChanceCache(Generic[K, V]):
    """
    Second-Chance (Clock) cache eviction algorithm.
    
    Like FIFO, but recently-accessed items get a second chance
    before eviction. Uses a single reference bit per entry.
    
    Time complexity: O(1) amortized (circular scan on eviction)
    Space overhead: 1 bit per entry
    """
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        
        # Circular buffer
        self.buffer: list[Optional[ClockEntry[K, V]]] = [None] * capacity
        
        # Clock hand position
        self.hand = 0
        
        # Key → buffer index
        self.index_map: Dict[K, int] = {}
    
    def get(self, key: K) -> Optional[V]:
        """
        Retrieve value by key.
        
        On hit, sets the reference bit (gives second chance).
        """
        if key not in self.index_map:
            return None
        
        idx = self.index_map[key]
        entry = self.buffer[idx]
        
        if entry:
            entry.ref_bit = True  # Mark as recently used
            return entry.value
        
        return None
    
    def put(self, key: K, value: V) -> Optional[K]:
        """
        Store key-value pair.
        
        Returns evicted key if eviction occurred.
        """
        evicted_key = None
        
        # Update existing entry
        if key in self.index_map:
            idx = self.index_map[key]
            entry = self.buffer[idx]
            if entry:
                entry.value = value
                entry.ref_bit = True
                return None
        
        # Need eviction if at capacity
        if len(self.index_map) >= self.capacity:
            evicted_key = self._evict_clock()
        
        # Find empty slot (will exist after eviction)
        # In circular buffer, hand now points to empty slot
        insert_idx = self.hand
        
        self.buffer[insert_idx] = ClockEntry(key=key, value=value, ref_bit=True)
        self.index_map[key] = insert_idx
        
        # Advance hand past the new entry
        self.hand = (self.hand + 1) % self.capacity
        
        return evicted_key
    
    def _evict_clock(self) -> K:
        """
        Clock algorithm eviction.
        
        Scan from hand position:
        - If ref_bit=0: evict
        - If ref_bit=1: clear bit, continue
        
        Amortized O(1) because each entry is visited at most twice
        per eviction cycle.
        """
        while True:
            entry = self.buffer[self.hand]
            
            if entry is None:
                # Empty slot, move on
                self.hand = (self.hand + 1) % self.capacity
                continue
            
            if not entry.ref_bit:
                # No second chance, evict this entry
                evicted_key = entry.key
                
                self.buffer[self.hand] = None
                del self.index_map[evicted_key]
                
                # Hand stays here; this slot is now empty for insertion
                return evicted_key
            else:
                # Give second chance: clear bit, move on
                entry.ref_bit = False
                self.hand = (self.hand + 1) % self.capacity
    
    def delete(self, key: K) -> bool:
        """Explicitly delete an entry."""
        if key not in self.index_map:
            return False
        
        idx = self.index_map[key]
        self.buffer[idx] = None
        del self.index_map[key]
        
        return True
    
    def __len__(self) -> int:
        return len(self.index_map)
 
 
# Second-Chance provides LRU-like behavior with FIFO-like simplicity
# It's widely used in operating systems for page replacement

Second-Chance Approximates LRU

In practice, Second-Chance achieves 90-95% of LRU's hit rate with much simpler implementation. It's the default algorithm in many operating systems (virtual memory page replacement) because it balances effectiveness with hardware implementation simplicity.

CLOCK-Pro and Advanced Variants

Basic Second-Chance/CLOCK can be enhanced to provide scan resistance and better hit rates. CLOCK-Pro is a notable variant that rivals LRU-K in effectiveness. CLOCK-Pro Key Ideas: Three lists: Hot, Cold, and Test pages (instead of one) Tracking non-resident pages: Maintains metadata for recently evicted pages to detect re-access patterns Adaptive hot page allocation: Dynamically adjusts hot vs. cold page ratio based on workload Why Track Evicted Pages? If an item is accessed, evicted (because it seemed cold), and quickly re-accessed, it was actually hot but got unlucky. By tracking recent evictions, CLOCK-Pro can: Detect this pattern Increase hot page allocation Admit re-accessed items directly to hot status

CLOCK-Pro maintains three circular lists:
 
┌─────────────────────────────────────────────────────────────────┐
│                          CLOCK-Pro                               │
└─────────────────────────────────────────────────────────────────┘
 
1. HOT CLOCK (resident, frequently accessed)
   ┌──────────────────────────────────┐
   │ [H1] → [H2] → [H3] → [H4] → ... │
   │  ↑                               │
   │ hand_hot                         │
   └──────────────────────────────────┘
   - Items here have been accessed recently
   - Protected from eviction
   - Can be demoted to cold if ref bit clear
 
2. COLD CLOCK (resident, infrequently accessed)  
   ┌──────────────────────────────────┐
   │ [C1] → [C2] → [C3] → [C4] → ... │
   │  ↑                               │
   │ hand_cold                        │
   └──────────────────────────────────┘
   - Items here are eviction candidates
   - If accessed, promote to hot
   - If not accessed, evict
 
3. TEST CLOCK (non-resident metadata only)
   ┌──────────────────────────────────┐
   │ [T1] → [T2] → [T3] → [T4] → ... │
   │  ↑                               │
   │ hand_test                        │
   └──────────────────────────────────┘
   - Tracks recently evicted items (just their keys)
   - If re-accessed while in test, item was "hot" all along
   - Triggers increase in hot allocation
 
Eviction Flow:
1. When cold clock hand reaches item with ref=0, evict it
2. Move item's key to test clock
3. If same key is accessed while in test clock:
   - Admit directly to hot clock
   - Increase hot clock capacity (adaptive!)

Other CLOCK Variants: CAR (Clock with Adaptive Replacement): Combines CLOCK with ARC-like adaptive sizing. Maintains two CLOCK lists (one for recency, one for frequency) and adapts their sizes based on workload. LIRS (Low Inter-reference Recency Set): Focuses on inter-reference recency (IRR): time between consecutive accesses to the same item. Items with low IRR are considered hot. Often outperforms LRU on benchmark workloads. 2Q (Two Queue): Simple variant: new items enter a FIFO queue (A1). If accessed again, they graduate to LRU queue (Am). Provides scan resistance with minimal complexity. These variants share a common theme: Pure FIFO/CLOCK is too simple, pure LRU is too expensive. The sweet spot is adding minimal tracking (reference bits, ghost entries) to approximate LRU's behavior.

Implementation Complexity vs. Benefit

CLOCK-Pro and similar algorithms can match or exceed LRU hit rates while maintaining O(1) amortized operations. However, they're significantly more complex to implement correctly. For most application-level caches, LRU remains the practical choice. CLOCK variants shine in operating systems and hardware where the per-operation overhead difference matters at the microsecond level.

FIFO Queues for TTL-Based Expiration

A powerful use case for FIFO is implementing TTL-based expiration efficiently. When all items have the same TTL, they expire in insertion order—exactly what FIFO tracks. The Pattern: Item A inserted at T=0, TTL=60s \to expires at T=60 Item B inserted at T=10, TTL=60s \to expires at T=70 Item C inserted at T=20, TTL=60s \to expires at T=80 Items expire in insertion order: A, B, C FIFO naturally evicts in this order! Efficient TTL Cleanup: Rather than scanning all items to check expiration, a FIFO queue with uniform TTL only needs to check the head. If the head hasn't expired, nothing has expired.

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
import time
from typing import TypeVar, Generic, Optional, Dict
from dataclasses import dataclass
from collections import deque
 
K = TypeVar('K')
V = TypeVar('V')
 
@dataclass
class TTLEntry(Generic[K, V]):
    key: K
    value: V
    expires_at: float
 
class TTLCache(Generic[K, V]):
    """
    Cache with TTL expiration using FIFO queue for cleanup.
    
    When all items have the same TTL, FIFO order = expiration order.
    This allows O(1) cleanup of expired items by only checking the head.
    
    For variable TTL, this still works but may need to skip non-expired items.
    """
    
    def __init__(self, ttl_seconds: float = 300.0, capacity: int = 10000):
        self.ttl = ttl_seconds
        self.capacity = capacity
        
        # FIFO queue of entries (ordered by insertion = expiration time)
        self.queue: deque[TTLEntry[K, V]] = deque()
        
        # Key → latest entry (handles overwrites)
        self.store: Dict[K, TTLEntry[K, V]] = {}
    
    def get(self, key: K) -> Optional[V]:
        """Get value if present and not expired."""
        self._cleanup_expired()
        
        if key not in self.store:
            return None
        
        entry = self.store[key]
        
        if time.time() >= entry.expires_at:
            # Expired (edge case: just expired)
            del self.store[key]
            return None
        
        return entry.value
    
    def put(self, key: K, value: V, ttl: Optional[float] = None) -> None:
        """
        Store value with TTL.
        
        If key exists, creates new entry (old entry becomes orphan,
        cleaned up when reached in queue).
        """
        self._cleanup_expired()
        
        ttl = ttl or self.ttl
        expires_at = time.time() + ttl
        
        entry = TTLEntry(key=key, value=value, expires_at=expires_at)
        
        # Add to queue and store
        self.queue.append(entry)
        self.store[key] = entry
        
        # Enforce capacity (evict beyond capacity)
        while len(self.store) > self.capacity:
            self._evict_oldest()
    
    def _cleanup_expired(self) -> int:
        """
        Remove all expired entries from the head of queue.
        
        O(k) where k = number of expired items (usually small).
        Amortizes to O(1) over put/get operations.
        """
        now = time.time()
        cleaned = 0
        
        while self.queue:
            oldest = self.queue[0]
            
            if now >= oldest.expires_at:
                # Expired, remove from queue
                self.queue.popleft()
                
                # Only remove from store if this is the current entry for key
                # (handles overwritten entries)
                if oldest.key in self.store and self.store[oldest.key] is oldest:
                    del self.store[oldest.key]
                    cleaned += 1
            else:
                # Head hasn't expired; nothing has expired
                # This is the efficiency win!
                break
        
        return cleaned
    
    def _evict_oldest(self) -> None:
        """Force evict the oldest entry (for capacity management)."""
        if not self.queue:
            return
        
        oldest = self.queue.popleft()
        
        if oldest.key in self.store and self.store[oldest.key] is oldest:
            del self.store[oldest.key]
    
    def __len__(self) -> int:
        return len(self.store)
 
 
# Usage:
cache = TTLCache[str, dict](ttl_seconds=300, capacity=10000)
 
cache.put("session:abc", {"user_id": 123, "role": "admin"})
# Expires in 300 seconds
 
# Later...
session = cache.get("session:abc")  # Returns value if not expired, None otherwise
 
# Cleanup happens automatically on get/put
# No background thread needed for uniform TTL!

Variable TTL Extension: For variable TTL, the FIFO approach still provides benefits: Lazy cleanup: Most expired items cluster near the head Tombstone minimization: Items expire roughly in order Background cleanup: Sweep through queue, skip non-expired items The optimization degrades with high TTL variance but remains useful for "mostly uniform" TTL patterns (e.g., all items TTL 5-10 minutes).

Time-Based Bucketing

For highly variable TTL, use time-based buckets : separate FIFO queues for items expiring each minute. When a minute passes, evict the entire bucket atomically. This provides O(1) expiration for any TTL granularity down to your bucket size.

FIFO in Production Systems

Let's examine where FIFO and its variants are used in real production systems. Operating Systems: Virtual memory page replacement commonly uses CLOCK (Second-Chance). The reference bit is naturally set by hardware MMU on page access, making it essentially free. Linux uses an approximation of LRU-2 with active/inactive lists that function similarly to CLOCK. Database Buffer Pools: Some databases offer FIFO as a buffer pool option (alongside LRU). InnoDB (MySQL) uses a modified FIFO for certain internal caches. The rationale: for high-churn workloads, LRU's overhead exceeds its hit rate benefit. Hardware Caches: CPU L1 caches often use FIFO or pseudo-LRU (an approximation using tree-based selection). True LRU requires O(log n) comparators per access—too expensive in silicon. FIFO needs only a counter.

Eviction Policy Usage in Real Systems
System	Primary Policy	Why This Choice
CPU L1/L2 Cache	Pseudo-LRU / FIFO	Hardware simplicity; cycle time critical
Linux Page Cache	Two-list (CLOCK variant)	Balance between recency and scan resistance
Redis (default)	Approximate LRU	Good general-purpose; configurable to LFU
Memcached	Slab-based LRU	Each size class has own LRU for fairness
Caffeine (Java)	W-TinyLFU	Near-optimal hit rate; acceptable overhead
CDN edge caches	LRU / LFU (configurable)	Content type dependent; static prefers LFU
Browser HTTP cache	LRU	Prioritizes recently viewed pages
DNS caches	TTL-based (FIFO for cleanup)	RFC mandates TTL; FIFO cleanup is natural

When to Choose FIFO in Application Caches:

FIFO is Appropriate When

•Write-heavy workload: If you're inserting far more than reading, per-access overhead matters less, and FIFO's insert efficiency shines.
•Uniform access patterns: If items are accessed roughly equally, LRU/LFU provide no differentiation benefit.
•Strict TTL requirements: If data must expire after exactly N seconds, FIFO naturally supports TTL cleanup.
•Embedded/constrained systems: When memory for per-entry metadata is precious, FIFO minimizes overhead.
•Debugging/predictability needed: FIFO's deterministic eviction order simplifies reasoning about cache behavior.
•You've benchmarked and it's close enough: If FIFO hit rate is within 5-10% of LRU for your workload, the simplicity win may be worth it.

Don't Default to FIFO

FIFO should be a conscious choice, not a default. Most applications benefit from LRU's recency tracking. Choose FIFO when you've identified a specific reason (latency, simplicity, workload characteristics) and verified hit rate is acceptable for your use case.

FIFO (First In First Out)

The Virtue of Simplicity

FIFO Conceptual Model

FIFO Implementation: Circular Buffer Efficiency

When FIFO Surprisingly Works Well

Second-Chance Algorithm: FIFO with a Safety Net

CLOCK-Pro and Advanced Variants

FIFO Queues for TTL-Based Expiration

FIFO in Production Systems

There’s more to understand.

FIFO (First In First Out)

The Virtue of Simplicity

FIFO Conceptual Model

FIFO Implementation: Circular Buffer Efficiency

When FIFO Surprisingly Works Well

Second-Chance Algorithm: FIFO with a Safety Net

CLOCK-Pro and Advanced Variants

FIFO Queues for TTL-Based Expiration

FIFO in Production Systems

There’s more to understand.