LRU Cache — ano ito, algorithm ng pagpapalayas at kung paano ito gumagana

Ano ang LRU Cache?

LRU Cache (Least Recently Used Cache) — isang istruktura ng data na may takdang laki na nag-iimbak ng limitadong bilang ng mga elemento at awtomatikong nagtatanggal ng mga hindi gaanong naa-access. Kapag humiling ang aplikasyon ng isang elemento, ito ay inililipat sa “sariwang” bahagi ng cache, at ang mga elementong matagal nang hindi ginamit ay gumagalaw patungo sa dulo at tinatanggal kapag naabot ang limitasyon.

Ang pangalang “Least Recently Used” ay naglalarawan ng patakaran sa pagpapalayas: ang elementong hindi nagamit nang pinakamatagal sa lahat ng nakaimbak ay tinatanggal. Ito ay batay sa palagay ng locality of reference — ang mga datong kamakailang hiniling ay may mataas na posibilidad na kailanganin muli. Iyon ang dahilan kung bakit ang LRU ay itinuturing na isa sa mga pinakaepektibong estratehiya ng caching para sa karamihan ng mga aplikasyon.

Ang klasikong implementasyon ng LRU Cache ay nangangailangan ng dalawang istruktura ng data: isang hash table para sa O(1) na pag-access sa anumang elemento sa pamamagitan ng key at isang doubly linked list para sa pagsubaybay sa pagkakasunud-sunod ng paggamit. Ang hash table ay nag-iimbak ng mga reference sa mga node ng list, at ang list ay nagpapanatili ng pagkakasunud-sunod mula sa pinakabagong elemento (ulo) hanggang sa pinakaluma (buntot).

Mga Pangunahing Operasyon ng LRU Cache

Ang operasyong get(key) ay nagsusuri kung mayroon ang key sa hash table. Kung ang elemento ay natagpuan, ito ay inililipat sa ulo ng list (nagiging pinakabago) at ang halaga nito ay ibinabalik. Kung hindi natagpuan — ang null ay ibinabalik o isang exception ay itinataas. Ang operasyong put(key, value) ay nagpapasok ng bagong elemento: kung ang key ay mayroon na — ang halaga ay ina-update at ang elemento ay inililipat sa ulo. Kung ang cache ay puno, bago ang pagpasok, ang elemento ng buntot ng list ay tinatanggal. Lahat ng operasyon ay isinasagawa sa pare-parehong oras na O(1).

Paano Gumagana ang LRU Cache

Ang algorithm ng LRU Cache ay batay sa dalawang prinsipyo: isang counter ng pag-access sa pagkakasunud-sunod ng oras at mekanika ng pagpapalayas kapag umapaw. Ang bawat elemento ay iniimbak sa isang node ng doubly linked list, at ang mga pointer sa mga node na ito — sa hash table. Sa bawat pag-access sa isang elemento, ito ay dinidiskonekta mula sa kasalukuyang posisyon at ipinasok sa simula ng list.

Kapag ang laki ng cache ay umabot sa maximum na halaga (maxSize) at may kahilingan na magpasok ng bagong elemento, ang algorithm ay nagtatanggal ng elemento ng buntot mula sa doubly linked list — ito ang elementong hindi nagamit nang pinakamatagal. Pagkatapos ng pagtatanggal, ang espasyo ay napalaya para sa bagong elemento, na ipinasok sa ulo ng list. Ang hash table ay ina-update: ang lumang key ay tinatanggal, ang bago ay idinaragdag.

Isang katangian ng LRU — ang kawalan ng pagiging sensitibo sa mga pattern ng pag-access na may paulit-ulit na siklo. Kung ang aplikasyon ay pana-panahong nag-a-access ng mas malaking set ng data kaysa sa laki ng cache, ang LRU ay maaaring magdusa mula sa thrashing — madalas na pagpapalit ng mga elemento kung saan ang bawat bagong kahilingan ay nagpapalayas sa nauna. Sa ganitong mga senaryo, ang LFU (Least Frequently Used) o mga adaptibong algorithm ay maaaring mas epektibo.

Laki ng Cache at Mga Metro

Ang pagpili ng laki ng LRU Cache ay isang kompromiso sa pagitan ng konsumo ng memorya at hit-ratio (porsyento ng matagumpay na pag-access). Ang mga tipikal na halaga para sa mga mobile na aplikasyon: 10–20% ng magagamit na memorya para sa cache ng imahe at 50–200 entry para sa cache ng mga tugon sa network. Ang Hit-ratio na 80–95% ay itinuturing na isang magandang tagapagpahiwatig kung saan ang cache ay nagbibigay-katwiran sa gastos ng memorya. Para sa pagsubaybay, ginagamit ang mga counter na hitCount at missCount, na magagamit sa implementasyon ng LruCache sa Android.

Implementasyon ng LRU Cache: HashMap + Doubly Linked List

Ang kanonikong implementasyon ng LRU Cache ay gumagamit ng kombinasyon ng hash table at doubly linked list. Ang hash table ay nagbibigay ng access sa anumang node sa pamamagitan ng key sa O(1), at ang doubly linked list — paglipat ng node sa ulo at pagtatanggal mula sa buntot sa O(1). Mahalaga na ang list ay doubly linked: ito ay nagpapahintulot sa pag-disconnect ng node mula sa gitna ng list nang hindi dinaanan ang lahat ng elemento.

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)
    }
}

Sa implementasyon, ang bawat node (Node) ay nag-iimbak ng halaga at mga reference sa nauna at susunod na node. Ang mga sentinel node na head at tail ay nagpapasimple sa mga kaso sa hangganan — hindi kailangan ng pagsusuri ng null sa pagpasok at pagtatanggal. Ang pamamaraang get ay naglilipat ng natagpuang node sa ulo, at ang put kapag umapaw ay nagtatanggal ng elemento ng buntot. Ang isang hiwalay na pamamaraang removeKeyByValue ay nakakahanap ng key sa hash table sa pamamagitan ng reference sa node at tinatanggal ito.

Built-in na Implementasyon ng LruCache sa Android

Ang Android SDK ay nagbibigay ng handa nang klase na LruCache sa paketeng android.util, na nagpapatupad ng LRU algorithm gamit ang LinkedHashMap sa mode na access-order. Ang klase ay thread-safe, sumusuporta sa pagbilang ng hit/miss, at nagbibigay din ng callback na entryRemoved para sa pagpapalaya ng mga mapagkukunan kapag nagpapalayas ng elemento. Ang laki ng cache ay itinakda sa mga arbitraryong yunit (bytes, bilang ng mga elemento) — sapat na upang i-override ang pamamaraang sizeOf.

LRU Cache vs FIFO at LIFO

Lahat ng tatlong algorithm — LRU, FIFO, at LIFO — ay lumulutas ng iisang gawain: paglilimita sa konsumo ng memorya sa pamamagitan ng pagpapalayas ng mga elemento kapag umapaw. Gayunpaman, gumagamit sila ng panimulang magkakaibang pamantayan para sa pagpili ng biktima, na tumutukoy sa kanilang pagiging epektibo sa iba't ibang senaryo.

FIFO ay nagpapalayas ng pinakalumang elemento ayon sa oras ng pagdaragdag, gaano man ito kadalas na-access. Ito ay maaaring hindi mahusay kung ang lumang elemento ay may kaugnayan pa rin. Iniiwasan ng LRU ang kakulangan na ito sa pamamagitan ng pagsasaalang-alang sa pattern ng pag-access. LIFO ay nagpapalayas ng bagong idinagdag na elemento — kapaki-pakinabang para sa mga senaryo ng undo, ngunit hindi angkop para sa caching dahil ang bagong data ay madalas na mas kailangan kaysa sa luma. Ang LRU ay itinuturing na pinakamainam na balanse sa pagitan ng complexity ng implementasyon at hit-ratio para sa karamihan ng mga aplikasyon.

Mga Halimbawa ng Kodigo ng LRU Cache

Tingnan natin ang paggamit ng built-in na klase na LruCache mula sa Android SDK para sa caching ng mga na-load na imahe. Ang halimbawa ay nagpapakita ng pagsisimula ng cache sa 1/8 ng magagamit na memorya ng aplikasyon, na siyang karaniwang rekomendasyon ng Google para sa cache ng imahe.

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)
    }
}

Ang pamamaraang sizeOf ay nagbabalik ng laki ng elemento sa parehong mga yunit kung saan itinakda ang cacheSize. Dito ginagamit ang laki ng Bitmap sa kilobytes (rowBytes × height / 1024). Kapag ang kabuuan ng sizeOf ng lahat ng elemento ay lumampas sa cacheSize, awtomatikong nagpapalayas ang LruCache ng mga pinakabagong hindi ginamit na Bitmap. Ang callback na entryRemoved ay maaaring gamitin upang tawagin ang bitmap.recycle() — pagpapalaya ng memorya bago ang pagpapalayas.

Implementasyon ng LRU Cache sa Swift

Ang iOS ay walang built-in na klase ng LRU Cache, ngunit madali itong maipapatupad sa pamamagitan ng NSCache (na gumagamit ng katulad ngunit hindi dokumentadong patakaran ng pagpapalayas) o sa pamamagitan ng sariling implementasyon batay sa Dictionary + Doubly Linked List, tulad ng ipinapakita sa ibaba.

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)
    }
}

Sa implementasyong ito sa Swift, ang Node ay isang panloob na klase na may mga field na value, next at prev. Ang pamamaraang moveToHead ay dinidiskonekta ang node mula sa kasalukuyang posisyon at ipinapasok ito sa simula ng list. Kapag umapaw, ang tail — ang pinakabagong hindi ginamit na elemento — ay tinatanggal. Para sa bersyong pang-produksyon, inirerekomenda ang pagdaragdag ng kaligtasan ng thread sa pamamagitan ng NSLock o isang DispatchQueue.