LRU Cache — vad det är, algoritm för bortträngning och hur det fungerar

Vad är LRU Cache?

LRU Cache (Least Recently Used Cache) — en datastruktur med fast storlek som lagrar ett begränsat antal element och automatiskt tar bort de som har använts minst. När en applikation begär ett element flyttas det till den ”färska” delen av cachen och länge oanvända element flyttas mot slutet och tas bort när gränsen nås.

Namnet ”Least Recently Used” beskriver bortträngningspolicyn: elementet som inte har använts längst bland alla lagrade tas bort. Detta bygger på antagandet om lokalitet (locality of reference) — nyligen begärda data kommer med hög sannolikhet att behövas igen. Därför anses LRU vara en av de mest effektiva cachningsstrategierna för de flesta applikationer.

Den klassiska implementeringen av LRU Cache kräver två datastrukturer: en hashtabell för O(1)-åtkomst till valfritt element via nyckel och en dubbellänkad lista för att hålla reda på användningsordningen. Hashtabellen lagrar referenser till listans noder och listan upprätthåller ordningen från det nyaste elementet (huvud) till det äldsta (svans).

Grundläggande operationer för LRU Cache

Operationen get(key) kontrollerar förekomsten av nyckeln i hashtabellen. Om elementet hittas flyttas det till listans huvud (blir nyast) och dess värde returneras. Om det inte hittas — returneras null eller ett undantag kastas. Operationen put(key, value) infogar ett nytt element: om nyckeln redan finns — uppdateras värdet och elementet flyttas till huvudet. Om cachen är full raderas svanselementet före infogning. Alla operationer utförs på konstant tid O(1).

Hur LRU Cache fungerar

LRU Cache-algoritmen bygger på två principer: en åtkomsträknare i tidsordning och mekaniken för bortträngning vid överflöd. Varje element lagras i en nod i den dubbellänkade listan och pekare till dessa noder — i hashtabellen. Vid varje åtkomst till ett element kopplas det bort från sin aktuella position och infogas i början av listan.

När cachestorleken når maxvärdet (maxSize) och en begäran om att infoga ett nytt element kommer, tar algoritmen bort svanselementet från den dubbellänkade listan — detta är elementet som inte har använts längst. Efter borttagning frigörs utrymme för det nya elementet, som infogas i listans huvud. Hashtabellen uppdateras: den gamla nyckeln tas bort, den nya läggs till.

En egenskap hos LRU är okänslighet för åtkomstmönster med cyklisk upprepning. Om en applikation periodvis har åtkomst till en större datamängd än cachestorleken kan LRU drabbas av thrashing — frekvent utbyte av element där varje ny begäran tränger undan den föregående. I sådana scenarier kan LFU (Least Frequently Used) eller adaptiva algoritmer vara mer effektiva.

Cachestorlek och statistik

Valet av LRU Cache-storlek är en kompromiss mellan minnesförbrukning och hit-ratio (procentandel lyckade åtkomster). Typiska värden för mobilapplikationer: 10–20 % av tillgängligt minne för bildcache och 50–200 poster för cache av nätverkssvar. Hit-ratio på 80–95 % anses vara en bra indikator där cachen motiverar minneskostnaden. För övervakning används räknarna hitCount och missCount, tillgängliga i LruCache-implementeringen i Android.

Implementering av LRU Cache: HashMap + Doubly Linked List

Den kanoniska implementeringen av LRU Cache använder en kombination av en hashtabell och en dubbellänkad lista. Hashtabellen ger åtkomst till valfri nod via nyckel i O(1) och den dubbellänkade listan — flyttning av nod till huvudet och borttagning från svansen i O(1). Det är viktigt att listan är just dubbellänkad: detta gör det möjligt att koppla bort en nod från mitten av listan utan att gå igenom alla element.

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

I implementeringen lagrar varje nod (Node) värdet och referenser till föregående och nästa nod. Sentinel-noderna head och tail förenklar gränsfall — det behövs inga null-kontroller vid infogning och borttagning. Metoden get flyttar den hittade noden till huvudet och put tar bort svanselementet vid överflöd. En separat metod removeKeyByValue hittar nyckeln i hashtabellen via referens till noden och tar bort den.

Inbyggd LruCache-implementering i Android

Android SDK tillhandahåller den färdiga klassen LruCache i paketet android.util, som implementerar LRU-algoritmen med LinkedHashMap i access-order-läge. Klassen är trådsäker, stöder hit/miss-räkning och tillhandahåller callbacken entryRemoved för frigöring av resurser vid bortträngning av ett element. Cachestorleken ställs in i godtyckliga enheter (byte, antal element) — det räcker att åsidosätta metoden sizeOf.

LRU Cache vs FIFO och LIFO

Alla tre algoritmer — LRU, FIFO och LIFO — löser samma uppgift: att begränsa minnesförbrukning genom bortträngning av element vid överflöd. De använder dock fundamentalt olika kriterier för att välja offer, vilket avgör deras effektivitet i olika scenarier.

FIFO tränger undan det äldsta elementet baserat på tilläggstid, oavsett hur ofta det har använts. Detta kan vara ineffektivt om det gamla elementet fortfarande är relevant. LRU undviker denna nackdel genom att ta hänsyn till åtkomstmönstret. LIFO tränger undan nyligen tillagt element — användbart för undo-scenarier men olämpligt för cachning eftersom nya data ofta behövs mer än gamla. LRU anses vara den optimala balansen mellan implementeringskomplexitet och hit-ratio för de flesta applikationer.

LRU Cache-kodexempel

Låt oss titta på användningen av den inbyggda klassen LruCache från Android SDK för cachning av laddade bilder. Exemplet visar initiering av cachen på 1/8 av applikationens tillgängliga minne, vilket är Googles standardrekommendation för bildcache.

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

Metoden sizeOf returnerar elementets storlek i samma enheter som cacheSize är inställd. Här används Bitmap-storleken i kilobyte (rowBytes × height / 1024). När summan av sizeOf för alla element överstiger cacheSize tränger LruCache automatiskt undan de minst nyligen använda Bitmap. Callbacken entryRemoved kan användas för att anropa bitmap.recycle() — frigöra minne före bortträngning.

Implementering av LRU Cache i Swift

iOS har ingen inbyggd LRU Cache-klass, men den kan enkelt implementeras via NSCache (som använder en liknande men odokumenterad bortträngningspolicy) eller via egen implementering baserad på Dictionary + Doubly Linked List, som visas nedan.

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

I denna Swift-implementering är Node en intern klass med fälten value, next och prev. Metoden moveToHead kopplar bort noden från dess aktuella position och infogar den i början av listan. Vid överflöd tas tail — det minst nyligen använda elementet — bort. För produktionsversion rekommenderas att lägga till trådsäkerhet via NSLock eller en DispatchQueue.