LRU Cache — шта је то, алгоритам истискивања и како ради

Шта је LRU Cache?

LRU Cache (Least Recently Used Cache) — структура података фиксне величине која чува ограничен број елемената и аутоматски уклања оне којима се најређе приступало. Када апликација затражи елемент, он се премешта у „свеж” део кеша, а давно некоришћени елементи се померају ка крају и уклањају по достизању лимита.

Назив „Least Recently Used” описује политику истискивања: уклања се елемент који није коришћен најдуже време међу свим ускладиштеним. Ово се заснива на претпоставци о локалности референци (locality of reference) — недавно затражени подаци ће са великом вероватноћом бити потребни поново. Управо зато се LRU сматра једном од најефикаснијих стратегија кеширања за већину апликација.

Класична имплементација LRU Cache захтева две структуре података: хеш табелу за приступ O(1) било ком елементу по кључу и двоструко повезану листу за праћење редоследа коришћења. Хеш табела чува референце на чворове листе, а листа одржава редослед од најновијег елемента (глава) до најстаријег (реп).

Основне операције LRU Cache

Операција get(key) проверава присуство кључа у хеш табели. Ако је елемент пронађен, премешта се на почетак листе (постаје најновији) и враћа се његова вредност. Ако није пронађен — враћа се null или се баца изузетак. Операција put(key, value) убацује нови елемент: ако кључ већ постоји — ажурира се вредност и елемент се премешта на почетак. Ако је кеш пун, пре убацивања се уклања репни елемент листе. Све операције се извршавају у константном времену O(1).

Како ради LRU Cache

Алгоритам LRU Cache се заснива на два принципа: бројач приступа у временском редоследу и механика истискивања при прекорачењу. Сваки елемент се чува у чвору двоструко повезане листе, а показивачи на ове чворове — у хеш табели. При сваком приступу елементу он се одваја од тренутне позиције и убацује на почетак листе.

Када величина кеша достигне максималну вредност (maxSize) и стигне захтев за убацивање новог елемента, алгоритам уклања репни елемент двоструко повезане листе — то је најмање недавно коришћени елемент. Након уклањања ослобађа се место за нови елемент, који се убацује на почетак листе. Хеш табела се притом ажурира: стари кључ се уклања, нови се додаје.

Особина LRU — неосетљивост на обрасце приступа са цикличним понављањем. Ако апликација периодично приступа већем скупу података од величине кеша, LRU може патити од thrashing-а — честе замене елемената где сваки нови захтев истискује претходни. У таквим сценаријима ефикаснији могу бити LFU (Least Frequently Used) или адаптивни алгоритми.

Величина кеша и метрике

Избор величине LRU Cache је компромис између потрошње меморије и hit-ratio (процента успешних приступа). Типичне вредности за мобилне апликације: 10–20% доступне меморије за кеш слика и 50–200 уноса за кеш мрежних одговора. Hit-ratio 80–95% сматра се добрим показатељем при којем кеш оправдава трошкове меморије. За праћење се користе бројачи hitCount и missCount, доступни у имплементацији LruCache у Android-у.

Имплементација LRU Cache: HashMap + Doubly Linked List

Каноничка имплементација LRU Cache користи комбинацију хеш табеле и двоструко повезане листе. Хеш табела обезбеђује приступ било ком чвору по кључу за O(1), а двоструко повезана листа — премештање чвора на почетак и уклањање са краја за O(1). Важно је да је листа управо двоструко повезана: то омогућава одвајање чвора из средине листе без прелажења свих елемената.

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

У имплементацији сваки чвор (Node) чува вредност и референце на претходни и следећи чвор. Стражарски чворови head и tail поједностављују граничне случајеве — није потребно проверавати null при убацивању и уклањању. Метод get премешта пронађени чвор на почетак, а put при прекорачењу уклања репни елемент. Посебан метод removeKeyByValue проналази кључ у хеш табели по референци на чвор и уклања га.

Уграђена имплементација LruCache у Android-у

Android SDK пружа готову класу LruCache у пакету android.util, која имплементира LRU алгоритам коришћењем LinkedHashMap у режиму access-order. Класа је thread-safe, подржава бројање hit/miss, а такође пружа callback entryRemoved за ослобађање ресурса при истискивању елемента. Величина кеша се поставља у произвољним јединицама (бајтови, број елемената) — довољно је прегазити метод sizeOf.

LRU Cache vs FIFO и LIFO

Сва три алгоритма — LRU, FIFO и LIFO — решавају исти задатак: ограничавање потрошње меморије истискивањем елемената при прекорачењу. Међутим, они користе суштински различите критеријуме за избор жртве, што одређује њихову ефикасност у различитим сценаријима.

FIFO истискује најстарији елемент по времену додавања, без обзира на то колико често му се приступало. Ово може бити неефикасно ако је стари елемент и даље актуелан. LRU избегава овај недостатак узимајући у обзир образац приступа. LIFO истискује свеже додати елемент — корисно за сценарије undo, али неподесно за кеширање, јер су нови подаци често потребнији од старих. LRU се сматра оптималним балансом између сложености имплементације и hit-ratio за већину апликација.

Примери кода LRU Cache

Размотримо употребу уграђене класе LruCache из Android SDK-а за кеширање учитаних слика. Пример приказује иницијализацију кеша на 1/8 доступне меморије апликације, што је стандардна Google препорука за кеш слика.

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

Метод sizeOf враћа величину елемента у истим јединицама у којима је постављен cacheSize. Овде се користи величина Bitmap-а у килобајтима (rowBytes × height / 1024). Када збир sizeOf свих елемената премаши cacheSize, LruCache аутоматски истискује најмање недавно коришћене Bitmap-е. Callback entryRemoved се може користити за позив bitmap.recycle() — ослобађање меморије пре истискивања.

Имплементација LRU Cache у Swift-у

iOS нема уграђену класу LRU Cache, али се лако може имплементирати преко NSCache (који користи сличну, али недокументовану политику истискивања) или кроз сопствену имплементацију на Dictionary + Doubly Linked List, као што је приказано испод.

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

У овој Swift имплементацији Node је унутрашња класа са пољима value, next и prev. Метод moveToHead одваја чвор од тренутне позиције и убацује га на почетак листе. При прекорачењу уклања се tail — најмање недавно коришћени елемент. За продукциону верзију препоручује се додавање безбедности нити преко NSLock-а или DispatchQueue реда.