Course contentsShow
← System Design
Lesson 148 of 1,9194. Caching StrategiesFree lesson

First In First Out (FIFO)

Evicting entries in insertion order regardless of access patterns, simplest policy with minimal overhead.

First In First Out (FIFO) Cache Eviction

What you'll learn: How FIFO removes the oldest cached entries first, making it the simplest eviction policy with minimal tracking overhead.

What Is FIFO?

First In First Out (FIFO) evicts cache entries in the exact order they were added—like a queue. The oldest entry (first inserted) gets removed first when the cache reaches capacity, regardless of how often it's been accessed or when it was last used.

Think of it like a conveyor belt at a grocery store checkout: items are processed in the order they arrive. The first item placed on the belt is the first one scanned and removed, no matter how many times the cashier looks at it.

How FIFO Works

When your cache fills up:

  1. Identify the entry that was inserted earliest (oldest timestamp)
  2. Remove that entry to make room
  3. Insert the new entry at the "back of the line"

FIFO completely ignores access patterns. An entry accessed a thousand times yesterday has no advantage over one never accessed—if it's older, it goes first.

Why Use FIFO?

FIFO requires minimal bookkeeping—just track insertion order. Unlike LRU (which tracks access time) or LFU (which counts frequency), FIFO doesn't update metadata on reads. This makes it:

  • Fast: No overhead on cache reads
  • Simple: Easy to implement with a queue
  • Predictable: Deterministic eviction order

The Trade-off

FIFO often performs poorly for real workloads because it doesn't consider usage patterns. A frequently-accessed entry inserted early gets evicted before a rarely-used recent entry. It works best when access patterns are truly random or when simplicity matters more than hit ratio.

Key Takeaway: FIFO evicts cache entries in strict insertion order with minimal overhead, making it the simplest policy—but also the least intelligent about actual usage patterns.