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

Least Frequently Used (LFU)

Removing items with the lowest access count, useful when access patterns show clear popularity differences.

Least Frequently Used (LFU)

What You'll Learn

You'll discover how the Least Frequently Used (LFU) eviction policy removes cache items based on how often they're accessed, not how recently.

The Core Idea

While LRU (Least Recently Used) tracks when items were last used, LFU tracks how many times each item has been accessed. When the cache fills up, LFU evicts the item with the lowest access count—the one that's been requested the fewest times.

Why This Matters

LFU shines when your access patterns show clear popularity differences. Some items are naturally "hot" (frequently requested) while others are rarely needed. Think of a news website: breaking news articles get thousands of views, while archived stories from years ago might only get occasional hits. LFU keeps the popular content cached while removing the rarely-accessed items.

How LFU Works

  1. Each cached item maintains an access counter
  2. Every time an item is retrieved, its counter increments
  3. When eviction is needed, the item with the smallest count is removed
  4. Ties can be broken by recency or other secondary criteria

Analogy: The Lending Library

Imagine a small library that tracks how many times each book is borrowed. When shelf space runs out, the librarian removes the book that's been checked out the fewest times—not necessarily the one that's been sitting longest. The bestsellers stay; the obscure titles go.

When to Use LFU

  • Clear popularity hierarchies: Some items are consistently more popular
  • Long-term access patterns: Popularity doesn't change rapidly
  • Read-heavy workloads: Frequent reads benefit from keeping hot items cached

Key Takeaway: LFU evicts items with the lowest access count, making it ideal when clear, stable popularity differences exist in your data access patterns.