LRU Cache — nedir, çıkarma algoritması ve nasıl çalışır

LRU Cache Nedir?

LRU Cache (Least Recently Used Cache), sınırlı sayıda öğeyi depolayan ve en az erişilenleri otomatik olarak kaldıran sabit boyutlu bir veri yapısıdır. Bir uygulama bir öğeyi talep ettiğinde, önbelleğin “taze” kısmına taşınırken, uzun süre kullanılmayan öğeler sona doğru kayar ve sınıra ulaşıldığında kaldırılır.

“Least Recently Used” adı çıkarma politikasını tanımlar: depolanan tüm öğeler arasında en uzun süredir kullanılmayan öğe kaldırılır. Bu, referans yerelliği (locality of reference) varsayımına dayanır — yakın zamanda talep edilen verilerin tekrar ihtiyaç duyulma olasılığı yüksektir. Bu nedenle LRU, çoğu uygulama için en etkili önbelleğe alma stratejilerinden biri olarak kabul edilir.

Klasik LRU Cache uygulaması iki veri yapısı gerektirir: anahtarla herhangi bir öğeye O(1) erişim için bir karma tablo ve kullanım sırasını izlemek için bir çift yönlü bağlantılı liste. Karma tablo, liste düğümlerine referanslar depolar ve liste, en yeni öğeden (baş) en eskiye (kuyruk) kadar sırayı korur.

Temel LRU Cache İşlemleri

get(key) işlemi, anahtarın karma tabloda var olup olmadığını kontrol eder. Öğe bulunursa, listenin başına taşınır (en yeni olur) ve değeri döndürülür. Bulunamazsa, null döndürülür veya bir istisna fırlatılır. put(key, value) işlemi yeni bir öğe ekler: anahtar zaten varsa, değer güncellenir ve öğe başa taşınır. Önbellek doluysa, eklemeden önce kuyruktaki öğe kaldırılır. Tüm işlemler sabit zamanda O(1) gerçekleştirilir.

LRU Cache Nasıl Çalışır

LRU Cache algoritması iki prensibe dayanır: zaman sıralı erişim sayma ve taşma durumunda çıkarma mekanizması. Her öğe çift yönlü bağlantılı listenin bir düğümünde depolanır ve bu düğümlere işaretçiler karma tabloda tutulur. Her erişimde, öğe mevcut konumundan ayrılır ve listenin başına eklenir.

Önbellek boyutu maksimum değerine (maxSize) ulaştığında ve yeni bir öğe ekleme talebi geldiğinde, algoritma çift yönlü bağlantılı listenin kuyruk öğesini kaldırır — bu en son en az kullanılan öğedir. Kaldırma işleminden sonra, listenin başına eklenen yeni öğe için yer açılır. Karma tablo buna göre güncellenir: eski anahtar kaldırılır, yeni anahtar eklenir.

LRU'nun bir özelliği, döngüsel tekrarlı erişim desenlerine karşı duyarlılığıdır. Uygulama periyodik olarak önbellek boyutundan daha büyük bir veri kümesine erişiyorsa, LRU thrashing'den (her yeni isteğin bir öncekini çıkardığı sık öğe değiştirme) zarar görebilir. Bu tür senaryolarda, LFU (Least Frequently Used) veya uyarlamalı algoritmalar daha etkili olabilir.

Önbellek Boyutu ve Metrikler

LRU Cache boyutunu seçmek, bellek tüketimi ile isabet oranı (başarılı erişim yüzdesi) arasında bir dengedir. Mobil uygulamalar için tipik değerler: resim önbelleği için kullanılabilir belleğin %10–20'si ve ağ yanıtı önbelleği için 50–200 giriş. %80–95 isabet oranı, önbelleğin bellek maliyetlerini haklı çıkardığı iyi bir gösterge olarak kabul edilir. İzleme için, Android'deki LruCache uygulamasında bulunan hitCount ve missCount sayaçları kullanılır.

LRU Cache Uygulaması: HashMap + Doubly Linked List

Kanonik LRU Cache uygulaması, bir karma tablo ve çift yönlü bağlantılı listenin bir kombinasyonunu kullanır. Karma tablo, anahtarla herhangi bir düğüme O(1) erişim sağlarken, çift yönlü bağlantılı liste bir düğümü başa taşımayı ve kuyruktan kaldırmayı O(1) ile mümkün kılar. Önemlisi, liste çift yönlü bağlantılıdır: bu, tüm öğeleri yinelemeden listenin ortasındaki bir düğümü ayırmaya olanak tanır.

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

Uygulamada, her düğüm (Node) bir değer ve önceki ile sonraki düğümlere referanslar depolar. Sentinel düğümler head ve tail sınır durumlarını basitleştirir — ekleme ve kaldırma sırasında null kontrolü gerekmez. get metodu bulunan düğümü başa taşır ve put, taşma durumunda kuyruk öğesini kaldırır. Ayrı bir metot olan removeKeyByValue, düğüm referansıyla karma tablodaki anahtarı bulur ve kaldırır.

Android'de Yerleşik LruCache Uygulaması

Android SDK, android.util paketinde, access-order modunda LinkedHashMap kullanarak LRU algoritmasını uygulayan hazır bir LruCache sınıfı sağlar. Sınıf thread-safe'tir, hit/miss sayımını destekler ve bir öğe çıkarılırken kaynak temizliği için entryRemoved geri çağrısını sağlar. Önbellek boyutu isteğe bağlı birimlerde (bayt, öğe sayısı) ayarlanır — sadece sizeOf metodunu geçersiz kılmak yeterlidir.

LRU Cache vs FIFO ve LIFO

Her üç algoritma — LRU, FIFO ve LIFO — aynı sorunu çözer: taşma durumunda öğeleri çıkararak bellek tüketimini sınırlamak. Ancak, kurbanı seçmek için temelde farklı kriterler kullanırlar, bu da farklı senaryolardaki etkinliklerini belirler.

FIFO, erişim sıklığından bağımsız olarak ekleme zamanına göre en eski öğeyi çıkarır. Eski bir öğe hala geçerliyse bu verimsiz olabilir. LRU, erişim desenini dikkate alarak bu dezavantajı önler. LIFO, en son eklenen öğeyi çıkarır — geri alma senaryoları için kullanışlıdır, ancak yeni veriler genellikle eskilerden daha fazla gerektiğinden önbelleğe alma için uygun değildir. LRU, çoğu uygulama için uygulama karmaşıklığı ve isabet oranı arasındaki optimal denge olarak kabul edilir.

LRU Cache Kod Örnekleri

İndirilen resimleri önbelleğe almak için Android SDK'daki yerleşik LruCache sınıfının kullanımını ele alalım. Örnek, uygulamanın kullanılabilir belleğinin 1/8'inde önbelleğin başlatılmasını gösterir; bu, Google'ın resim önbelleğe alma için standart önerisidir.

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 metodu, cacheSize'ın belirtildiği birimlerde öğe boyutunu döndürür. Burada, kilobayt cinsinden Bitmap boyutu kullanılır (rowBytes × height / 1024). Tüm öğelerin sizeOf toplamı cacheSize'ı aştığında, LruCache otomatik olarak en son en az kullanılan Bitmap'leri çıkarır. entryRemoved geri çağrısı, bitmap.recycle() çağırmak için kullanılabilir — çıkarmadan önce belleği boşaltmak için.

Swift'te LRU Cache Uygulaması

iOS'ta yerleşik bir LRU Cache sınıfı yoktur, ancak NSCache (benzer ancak belgelenmemiş bir çıkarma politikası kullanır) veya Dictionary + çift yönlü bağlantılı liste kullanan özel bir uygulama ile kolayca uygulanabilir, aşağıda gösterildiği gibi.

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

Bu Swift uygulamasında, Node value, next ve prev alanlarına sahip bir iç sınıftır. moveToHead metodu bir düğümü mevcut konumundan ayırır ve listenin başına ekler. Taşma durumunda, kuyruk — en son en az kullanılan öğe — kaldırılır. Üretim için, NSLock veya bir DispatchQueue aracılığıyla iş parçacığı güvenliği eklenmesi önerilir.