FIFO — First In, First Out — Cache Eviction

Overview

What this concept solves

FIFO — First In, First Out — is the simplest possible eviction policy. Whichever entry has been in the cache the longest is the one that gets evicted next. Accessing an entry doesn't change its eviction priority. There is no recency, no frequency — only age.

It's a single queue, a single counter, and a single pointer. The implementation is so small you can fit it in a tweet. The price for that simplicity is hit rate: on most workloads FIFO loses to LRU and LFU. But on certain workloads — streams, log replay, one-shot reads — it's actually the right tool.

Mechanics

How it works

One queue, one decision

State is a queue (or a circular buffer) of entries in insertion order, plus a hash map for O(1) lookup. The algorithm:

Get(key) — look up the value in the map and return it. The queue is not touched.
Put(key, value) — if the key is new, append it to the back of the queue and insert it in the map. If the cache is now over capacity, pop the front of the queue and remove it from the map.

Belady's anomaly

FIFO has a strange property: increasing the cache size can decrease the hit rate. This is called Belady's anomaly and was discovered in 1969. LRU does not have this anomaly (it's a 'stack algorithm'). It's mostly a curiosity, but it's a sign that FIFO doesn't track the right signal.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › FIFO — First In, First Out

About this simulation

Capacity 4 — ordered by arrival, newest on the left. Re-accessing an entry does nothing to its position (the status line will literally say 'no reorder'). Only insertion can evict, and only the oldest arrival on the right gets dropped.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Confirm that reads do nothing

Click A, B, C, D to fill. Now click A several times. Watch the row: A stays where it was, in the oldest slot. The status line confirms 'HIT (no reorder)'. Reads are pure look-ups in FIFO.

try 02

Evict the key you just hammered

After step 1, click E. A is gone — the slot you were just hammering — because A was the oldest arrival. FIFO doesn't care how many times you touched it.

try 03

Compare to LRU mentally

Run the same demo sequence A, B, C, D, A, E, B here, then in the LRU prototype. FIFO drops A; LRU keeps it. That gap — same workload, different victim — is FIFO's cost on any trace with re-use.

In practice

When to use it — and what you give up

When to reach for it

Streaming or one-shot reads — log replay, ETL pipelines, batch jobs. Re-use is rare, so spending CPU to track it is waste.
You need a hard cap on retention age — FIFO is age-bounded by construction.
Hardware caches at the lowest level — sometimes one bit of state and a circular pointer is all you can afford.
As a baseline — implement FIFO first, measure your hit rate, then decide if LRU or LFU is worth the added complexity.

Pros

The simplest possible policy — easy to implement, debug, and reason about.
Zero bookkeeping on reads. No list shuffling, no counter increments. Trivially thread-safe.
Predictable: every entry lives for exactly N evictions after insertion (where N is the cache size).

Cons

Ignores access patterns entirely — a hot key is evicted at the same age as a cold one.
Worse hit rate than LRU on virtually every realistic workload that has any reuse.
Belady's anomaly — a bigger cache can perform worse than a smaller one on adversarial traces.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

fifo.ts

// Map preserves insertion order in JS — perfect for FIFO.
// Critically, we do *not* re-insert on get.
class FIFO<K, V> {
  private store = new Map<K, V>();
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    return this.store.get(key); // age unchanged
  }

  set(key: K, value: V): void {
    if (this.store.has(key)) {
      this.store.set(key, value); // value updated, age unchanged
      return;
    }
    this.store.set(key, value);
    if (this.store.size > this.capacity) {
      const oldest = this.store.keys().next().value!;
      this.store.delete(oldest);
    }
  }
}

References & further reading

3 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

What distinguishes FIFO from LRU in one sentence?

question 02 / 03

What is Belady's anomaly?

question 03 / 03

FIFO cache, capacity 3. Trace: A, B, C, A, A, A, D. After D, which keys remain?

0/3 answered