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) зберігає значення та посилання на попередній і наступний вузли. Sentinel-вузли head і tail спрощують граничні випадки — не потрібно перевіряти на null при вставці та видаленні. Метод get переміщує знайдений вузол у голову, а put при переповненні видаляє хвостовий елемент. Окремий метод removeKeyByValue знаходить ключ у хеш-таблиці за посиланням на вузол і видаляє його.

Вбудована реалізація LruCache в Android

Android SDK надає готовий клас LruCache у пакеті android.util, який реалізує LRU алгоритм з використанням LinkedHashMap у режимі access-order. Клас thread-safe, підтримує підрахунок hit/miss, а також надає колбек 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. Колбек 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 — найменш нещодавно використаний елемент. Для production рекомендується також додавати потокобезпечність через NSLock або чергу DispatchQueue.