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.