Cache Eviction Policies: Stop Guessing, Start Predicting What Gets Kicked Out

// io.thecodeforge — System Design tutorial

// Simulating FIFO eviction in a cache
class FIFOCache<K, V>(private val maxSize: Int) {
    private val queue = ArrayDeque<K>()
    private val map = mutableMapOf<K, V>()

    fun put(key: K, value: V) {
        if (map.size >= maxSize) {
            val oldest = queue.removeFirst() // O(1) eviction
            map.remove(oldest)
        }
        queue.addLast(key)
        map[key] = value
    }

    fun get(key: K): V? = map[key] // No promotion — key stays in place
}

fun main() {
    val cache = FIFOCache<String, String>(3)
    cache.put("hot1", "data1")
    cache.put("hot2", "data2")
    cache.put("hot3", "data3")
    cache.get("hot1") // Access hot1 — but FIFO doesn't care
    cache.put("cold1", "data4") // Evicts hot1, not the oldest unused
    println(cache.get("hot1")) // null — evicted despite being recently used
}

// io.thecodeforge — System Design tutorial

// Thread-safe LRU cache using LinkedHashMap
class LRUCache<K, V>(private val maxSize: Int) {
    private val map = object : LinkedHashMap<K, V>(maxSize, 0.75f, true) {
        override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?): Boolean {
            return size > maxSize // Auto-evict on insert
        }
    }

    @Synchronized
    fun get(key: K): V? = map[key] // Access promotes entry to end

    @Synchronized
    fun put(key: K, value: V) {
        map[key] = value
    }
}

fun main() {
    val cache = LRUCache<String, String>(3)
    cache.put("A", "1")
    cache.put("B", "2")
    cache.put("C", "3")
    cache.get("A") // Promotes A to most recent
    cache.put("D", "4") // Evicts B (least recently used)
    println(cache.get("B")) // null
}

// io.thecodeforge — System Design tutorial

// Simplified LFU with min-heap for frequency tracking
class LFUCache<K, V>(private val maxSize: Int) {
    private val map = mutableMapOf<K, V>()
    private val freq = mutableMapOf<K, Int>()
    private val heap = PriorityQueue(compareBy { freq[it] }) // Min-heap by frequency

    fun put(key: K, value: V) {
        if (map.size >= maxSize && key !in map) {
            val evict = heap.poll() // Evict lowest frequency
            map.remove(evict)
            freq.remove(evict)
        }
        map[key] = value
        freq[key] = (freq[key] ?: 0) + 1
        heap.remove(key) // Reinsert to re-sort
        heap.add(key)
    }

    fun get(key: K): V? {
        val v = map[key]
        if (v != null) {
            freq[key] = freq[key]!! + 1
            heap.remove(key)
            heap.add(key)
        }
        return v
    }
}

fun main() {
    val cache = LFUCache<String, String>(3)
    cache.put("hot", "1")
    cache.get("hot")
    cache.get("hot")
    cache.put("cold", "2")
    cache.put("also_cold", "3")
    cache.put("new", "4") // Evicts 'cold' (freq=1) even though 'also_cold' is older
    println(cache.get("cold")) // null
}

// io.thecodeforge — System Design tutorial

// TTL cache with background purge thread
class TTLCache<K, V>(private val defaultTTL: Long) {
    private val map = mutableMapOf<K, V>()
    private val expiry = mutableMapOf<K, Long>() // Expiry timestamp
    private val purgeInterval = 1000L // ms

    init {
        thread(isDaemon = true) {
            while (true) {
                Thread.sleep(purgeInterval)
                val now = System.currentTimeMillis()
                val expired = expiry.filter { it.value <= now }.keys
                expired.forEach { map.remove(it); expiry.remove(it) }
            }
        }
    }

    fun put(key: K, value: V, ttl: Long = defaultTTL) {
        map[key] = value
        expiry[key] = System.currentTimeMillis() + ttl
    }

    fun get(key: K): V? {
        val exp = expiry[key] ?: return null
        if (System.currentTimeMillis() > exp) {
            map.remove(key)
            expiry.remove(key)
            return null
        }
        return map[key]
    }
}

fun main() {
    val cache = TTLCache<String, String>(2000)
    cache.put("temp", "data")
    Thread.sleep(2500)
    println(cache.get("temp")) // null — expired
}

// io.thecodeforge — System Design tutorial

// Hybrid: TTL + LRU fallback
class HybridCache<K, V>(private val maxSize: Int, private val defaultTTL: Long) {
    private val map = LinkedHashMap<K, Pair<V, Long>>(maxSize, 0.75f, true)

    @Synchronized
    fun put(key: K, value: V, ttl: Long = defaultTTL) {
        if (map.size >= maxSize && key !in map) {
            // Evict oldest (LRU order due to accessOrder=true)
            val eldest = map.keys.first()
            map.remove(eldest)
        }
        map[key] = Pair(value, System.currentTimeMillis() + ttl)
    }

    @Synchronized
    fun get(key: K): V? {
        val entry = map[key] ?: return null
        val (value, expiry) = entry
        if (System.currentTimeMillis() > expiry) {
            map.remove(key)
            return null
        }
        return value // Access promotes in LinkedHashMap
    }
}

fun main() {
    val cache = HybridCache<String, String>(3, 5000)
    cache.put("A", "1", 100) // Short TTL
    Thread.sleep(200)
    println(cache.get("A")) // null — expired
}

// io.thecodeforge — System Design tutorial

// Striped LRU: 16 stripes to reduce lock contention
class StripedLRUCache<K, V>(private val maxSize: Int, private val stripes: Int = 16) {
    private val caches = Array(stripes) { LRUCache<K, V>(maxSize / stripes) }

    private fun stripe(key: K): Int = key.hashCode().mod(stripes).let { if (it < 0) it + stripes else it }

    fun get(key: K): V? = caches[stripe(key)].get(key)
    fun put(key: K, value: V) = caches[stripe(key)].put(key, value)
}

// Note: This can evict more than maxSize if keys hash unevenly.
// Use consistent hashing or a central coordinator for strict limits.