advanced-cache-design

Advanced Cache Design Algorithms (LRU, LFU, ARC, TinyLFU, SLRU, CMS)

This repository contains production-quality, educational implementations of modern cache eviction and admission algorithms used in systems such as:

These implementations are written in TypeScript, focusing on clarity and correctness.

🚀 Included Algorithms

✔️ LRU (Least Recently Used)

Classical O(1) LRU using a doubly linked list + hash map.

✔️ LFU (Least Frequently Used)

Full LFU with frequency lists and O(1) updates.

✔️ ARC (Adaptive Replacement Cache)

Self-tuning hybrid of recency and frequency.

✔️ TinyLFU (Admission Policy)

Modern frequency-based admission algorithm used by Google Caffeine.

✔️ SLRU (Segmented Least Recently Used)

Two-tier LRU that protects hot entries from eviction.

✔️ CMS (Count-Min Sketch)

Probabilistic frequency estimator (used by huge-scale caches).

📦 Installation

git clone https://github.com/kavicastelo/advanced-cache-design.git
cd advanced-cache-design
npm install

▶️ Running Examples

npm run build
node dist/examples/test-lru.js

Want scripts for all algorithms? Just run:

node dist/examples/test-*.js

📁 Directory Overview

src/
  lru/          → LRU cache implementation
  lfu/          → LFU cache implementation
  arc/          → ARC hybrid cache
  cms/          → Count–Min Sketch
  tiny-lfu/     → TinyLFU admission
  slru/         → Segmented LRU eviction
examples/       → Demo scripts

🧰 Technologies Used

📝 License

MIT License – Free to use and modify.

This site is open source. Improve this page.