LRU Cache — apa itu, algoritma pengusiran dan cara kerjanya

Apa itu LRU Cache?

LRU Cache (Least Recently Used Cache) — struktur data berukuran tetap yang menyimpan jumlah elemen terbatas dan secara otomatis menghapus yang paling jarang diakses. Ketika aplikasi meminta elemen, ia dipindahkan ke bagian “segar” dari cache, dan elemen yang lama tidak digunakan bergeser ke akhir dan dihapus saat mencapai batas.

Nama “Least Recently Used” menggambarkan kebijakan pengusiran: elemen yang paling lama tidak digunakan di antara semua yang tersimpan akan dihapus. Ini didasarkan pada asumsi lokalitas referensi (locality of reference) — data yang baru saja diminta kemungkinan besar akan dibutuhkan lagi. Oleh karena itu LRU dianggap sebagai salah satu strategi caching paling efektif untuk sebagian besar aplikasi.

Implementasi klasik LRU Cache memerlukan dua struktur data: tabel hash untuk akses O(1) ke elemen mana pun berdasarkan kunci dan doubly linked list untuk melacak urutan penggunaan. Tabel hash menyimpan referensi ke node-node dalam list, dan list mempertahankan urutan dari elemen terbaru (kepala) hingga yang tertua (ekor).

Operasi Dasar LRU Cache

Operasi get(key) memeriksa keberadaan kunci di tabel hash. Jika elemen ditemukan, ia dipindahkan ke kepala list (menjadi yang terbaru) dan nilainya dikembalikan. Jika tidak ditemukan — null dikembalikan atau exception dilempar. Operasi put(key, value) menyisipkan elemen baru: jika kunci sudah ada — nilai diperbarui dan elemen dipindahkan ke kepala. Jika cache penuh, sebelum penyisipan, elemen ekor list dihapus. Semua operasi dilakukan dalam waktu konstan O(1).

Cara Kerja LRU Cache

Algoritma LRU Cache didasarkan pada dua prinsip: penghitung akses dalam urutan waktu dan mekanisme pengusiran saat meluap. Setiap elemen disimpan dalam node dari doubly linked list, dan pointer ke node-node ini — dalam tabel hash. Setiap kali elemen diakses, ia diputus dari posisi saat ini dan disisipkan ke awal list.

Ketika ukuran cache mencapai nilai maksimum (maxSize) dan ada permintaan untuk menyisipkan elemen baru, algoritma menghapus elemen ekor dari doubly linked list — ini adalah elemen yang paling lama tidak digunakan. Setelah penghapusan, ruang dibebaskan untuk elemen baru, yang disisipkan ke kepala list. Tabel hash diperbarui: kunci lama dihapus, yang baru ditambahkan.

Ciri khas LRU — ketidakpekaan terhadap pola akses dengan pengulangan siklik. Jika aplikasi secara periodik mengakses kumpulan data yang lebih besar dari ukuran cache, LRU dapat mengalami thrashing — penggantian elemen yang sering terjadi ketika setiap permintaan baru mengusir yang sebelumnya. Dalam skenario seperti itu, LFU (Least Frequently Used) atau algoritma adaptif mungkin lebih efektif.

Ukuran Cache dan Metrik

Pemilihan ukuran LRU Cache adalah kompromi antara konsumsi memori dan hit-ratio (persentase akses berhasil). Nilai tipikal untuk aplikasi mobile: 10–20% dari memori yang tersedia untuk cache gambar dan 50–200 entri untuk cache respons jaringan. Hit-ratio 80–95% dianggap sebagai indikator yang baik di mana cache membenarkan biaya memori. Untuk pemantauan digunakan penghitung hitCount dan missCount, yang tersedia dalam implementasi LruCache di Android.

Implementasi LRU Cache: HashMap + Doubly Linked List

Implementasi kanonik LRU Cache menggunakan kombinasi tabel hash dan doubly linked list. Tabel hash menyediakan akses ke node mana pun berdasarkan kunci dalam O(1), dan doubly linked list — pemindahan node ke kepala dan penghapusan dari ekor dalam O(1). Penting bahwa list tersebut benar-benar doubly linked: ini memungkinkan pemutusan node dari tengah list tanpa menelusuri semua elemen.

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

Dalam implementasi, setiap node (Node) menyimpan nilai dan referensi ke node sebelumnya dan berikutnya. Node sentinel head dan tail menyederhanakan kasus batas — tidak perlu pemeriksaan null saat penyisipan dan penghapusan. Metode get memindahkan node yang ditemukan ke kepala, dan put saat meluap menghapus elemen ekor. Metode terpisah removeKeyByValue menemukan kunci dalam tabel hash melalui referensi ke node dan menghapusnya.

Implementasi Bawaan LruCache di Android

Android SDK menyediakan kelas siap pakai LruCache dalam paket android.util, yang mengimplementasikan algoritma LRU menggunakan LinkedHashMap dalam mode access-order. Kelas ini thread-safe, mendukung penghitungan hit/miss, dan juga menyediakan callback entryRemoved untuk membebaskan sumber daya saat pengusiran elemen. Ukuran cache diatur dalam unit arbitrer (byte, jumlah elemen) — cukup override metode sizeOf.

LRU Cache vs FIFO dan LIFO

Ketiga algoritma — LRU, FIFO, dan LIFO — memecahkan satu tugas: membatasi konsumsi memori melalui pengusiran elemen saat meluap. Namun mereka menggunakan kriteria yang berbeda secara fundamental untuk memilih korban, yang menentukan efektivitas mereka dalam skenario yang berbeda.

FIFO mengusir elemen tertua berdasarkan waktu penambahan, terlepas dari seberapa sering diakses. Ini bisa tidak efisien jika elemen lama masih relevan. LRU menghindari kekurangan ini dengan mempertimbangkan pola akses. LIFO mengusir elemen yang baru ditambahkan — berguna untuk skenario undo, tetapi tidak cocok untuk caching karena data baru seringkali lebih dibutuhkan daripada yang lama. LRU dianggap sebagai keseimbangan optimal antara kompleksitas implementasi dan hit-ratio untuk sebagian besar aplikasi.

Contoh Kode LRU Cache

Mari kita lihat penggunaan kelas bawaan LruCache dari Android SDK untuk caching gambar yang dimuat. Contoh menunjukkan inisialisasi cache pada 1/8 dari memori yang tersedia aplikasi, yang merupakan rekomendasi standar Google untuk cache gambar.

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

Metode sizeOf mengembalikan ukuran elemen dalam satuan yang sama dengan cacheSize. Di sini ukuran Bitmap dalam kilobyte digunakan (rowBytes × height / 1024). Ketika jumlah sizeOf semua elemen melebihi cacheSize, LruCache secara otomatis mengusir Bitmap yang paling jarang digunakan. Callback entryRemoved dapat digunakan untuk memanggil bitmap.recycle() — membebaskan memori sebelum pengusiran.

Implementasi LRU Cache di Swift

iOS tidak memiliki kelas LRU Cache bawaan, tetapi dapat dengan mudah diimplementasikan melalui NSCache (yang menggunakan kebijakan pengusiran serupa tetapi tidak terdokumentasi) atau melalui implementasi sendiri berdasarkan Dictionary + Doubly Linked List, seperti yang ditunjukkan di bawah ini.

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

Dalam implementasi Swift ini, Node adalah kelas internal dengan bidang value, next, dan prev. Metode moveToHead memutus node dari posisi saat ini dan menyisipkannya ke awal list. Saat meluap, tail — elemen yang paling jarang digunakan — dihapus. Untuk versi produksi, disarankan untuk menambahkan keamanan thread melalui NSLock atau antrian DispatchQueue.