Skip to content

fifo.md

Latest commit

 

History

History
42 lines (31 loc) · 1.63 KB

fifo.md

File metadata and controls

42 lines (31 loc) · 1.63 KB

FIFO (First-In, First-Out)

Feature: policy-fifo

Goal

Evict the oldest inserted resident entry when the cache is full.

Core Data Structures

Typical O(1) FIFO implementation:

  • HashMap<K, V> for key lookup and storage
  • VecDeque<K> (or ring buffer) to track insertion order

In cachekit, FIFO is implemented in src/policy/fifo/ with:

  • a key/value map plus an insertion-order queue
  • lazy stale entry handling (queue entries can become stale if the key is removed/updated)

Operations

insert(key, value)

  • If key already exists: update the stored value, do not change insertion order.
  • If cache is at capacity: evict from the front of the queue until a live key is found.
  • Insert the new key/value and push the key to the back of the queue.

get(key)

  • Lookup only; FIFO does not reorder on access.

pop_oldest()

  • Pop from queue front until you find a key still present in the map; remove it from the map and return it.

Complexity & Overhead

  • Lookup: O(1)
  • Insert: O(1) amortized; eviction may skip stale queue entries
  • Memory: HashMap + queue of keys

Edge Cases / Implementation Notes

  • Stale keys: if you support remove(key) (or “update” that replaces storage), you must reconcile the queue.
    • Eager cleanup requires O(n) removal from the middle of a VecDeque.
    • Lazy cleanup keeps hot path O(1) and pays cleanup during eviction.
  • Duplicate keys in queue: if your update path pushes keys again, you must handle duplicates on eviction; the repo implementation avoids changing order on update.

References