Cache dan LRU

Database memuat halaman ke buffer pool, browser menyimpan hasil request di HTTP cache, dan sistem operasi mengelola page cache untuk file system. Semua berbagi masalah yang sama: kapasitas terbatas, keputusan evict mana yang akan diganti. Strategi paling populer adalah LRU (Least Recently Used) — evict item yang paling lama tidak diakses. Pada Chapter ini kita akan mengimplementasikan LRU cache dengan template class C++ yang menggabungkan doubly linked list untuk urutan akses dan hash map untuk lookup O(1). Kombinasi kedua struktur ini menghasilkan operasi get dan put keduanya O(1) rata-rata — sebuah karya arsitektur DSA yang elegan.

Konsep: Doubly Linked List + Hash Map #

LRU cache membutuhkan dua operasi cepat: lookup berdasarkan key (hash map) dan reorder berdasarkan recency (linked list). Hash map memberi akses O(1) ke node mana pun di linked list, sementara linked list memungkinkan pemindahan node ke depan (MRU) atau penghapusan dari belakang (LRU) dalam O(1).

LRU: Aturan dan Mekanisme #

Aturan #

LRU cache menyimpan paling banyak cap_ item. Saat item baru dimasukkan dan cache penuh, item paling lama tidak diakses (LRU) dihapus. Setiap akses get atau put memindahkan item ke depan list (menjadi MRU). Urutan list mencerminkan recency: depan = paling baru, belakang = paling lama.

Mekanisme di Balik Layar #

• get(key): lookup hash map. Bila ketemu, pindah node ke depan list via splice (operasi O(1) yang memindahkan node tanpa copy), lalu kembalikan nilai.
• put(key, value):
  • Bila key sudah ada: update nilai, pindah ke depan.
  • Bila key baru dan cache penuh: evict LRU (pilih list_.back(), hapus dari hash map dan list), lalu tambah baru di depan.
  • Bila key baru dan belum penuh: tambah baru di depan, daftarkan di hash map.

std::list::splice adalah kunci efisiensi — operasi memindahkan node dari satu posisi ke posisi lain dalam O(1) tanpa reallokasi memori. Iterator std::list tetap valid setelah splice (karena node-nya yang dipindah, bukan di-copy).

Kompleksitas #

Hash map O(1) rata-rata untuk lookup; linked list O(1) untuk splice/pop. Kombinasi menghasilkan operasi cache yang konsisten cepat.

Kode: LRU Cache Template #

#include <iostream>
#include <list>
#include <unordered_map>
#include <string>
#include <optional>
using namespace std;

template<typename K, typename V>
class LRUCache {
public:
    explicit LRUCache(size_t capacity) : cap_(capacity) {}

    // Ambil nilai jika ada; pindah ke depan (most recently used)
    optional<V> get(const K& key) {
        auto it = map_.find(key);
        if (it == map_.end()) return nullopt;

        // Pindah node ke depan list
        list_.splice(list_.begin(), list_, it->second);
        return it->second->second;
    }

    // Simpan nilai; bila penuh, evict paling belakang (LRU)
    void put(const K& key, const V& value) {
        auto it = map_.find(key);
        if (it != map_.end()) {
            // Update existing
            it->second->second = value;
            list_.splice(list_.begin(), list_, it->second);
            return;
        }
        if (list_.size() >= cap_) {
            // Evict LRU (paling belakang list)
            auto last = list_.back();
            map_.erase(last.first);
            list_.pop_back();
        }
        list_.emplace_front(key, value);
        map_[key] = list_.begin();
    }

    void dump(const string& label) const {
        cout << label << ": ";
        for (const auto& kv : list_) {
            cout << "[" << kv.first << "=" << kv.second << "] ";
        }
        cout << "(size=" << list_.size() << "/" << cap_ << ")\n";
    }

private:
    size_t cap_;
    list<pair<K,V>> list_;                              // MRU di depan
    unordered_map<K, typename list<pair<K,V>>::iterator> map_;
};

int main() {
    LRUCache<int,string> cache(3);

    cout << "=== LRU Cache (capacity=3) ===\n\n";

    cache.put(1, "satu");   cache.dump("put(1)");
    cache.put(2, "dua");    cache.dump("put(2)");
    cache.put(3, "tiga");   cache.dump("put(3)");

    auto v = cache.get(1);
    cout << "\nget(1) = " << v.value_or("(tidak ada)") << "\n";
    cache.dump("setelah get(1)");

    cache.put(4, "empat");  cache.dump("put(4) [evict LRU]");

    v = cache.get(2);
    cout << "\nget(2) = " << v.value_or("(tidak ada)") << "\n";

    cache.put(3, "tiga-update");
    cache.dump("put(3) [update]");

    cache.put(5, "lima");   cache.dump("put(5) [evict 4]");

    cout << "\n=== Urutan Akses LRU ===\n";
    cout << "Front (MRU): terbaru diakses\n";
    cout << "Back  (LRU): kandidat evict berikutnya\n";
    return 0;
}

Output yang Dihasilkan:

=== LRU Cache (capacity=3) ===

put(1): [1=satu] (size=1/3)
put(2): [2=dua] [1=satu] (size=2/3)
put(3): [3=tiga] [2=dua] [1=satu] (size=3/3)

get(1) = satu
setelah get(1): [1=satu] [3=tiga] [2=dua] (size=3/3)
put(4) [evict LRU]: [4=empat] [1=satu] [3=tiga] (size=3/3)

get(2) = (tidak ada)
put(3) [update]: [3=tiga-update] [4=empat] [1=satu] (size=3/3)
put(5) [evict 4]: [5=lima] [3=tiga-update] [4=empat] (size=3/3)

=== Urutan Akses LRU ===
Front (MRU): terbaru diakses
Back  (LRU): kandidat evict berikutnya

Bedah Kode Baris-per-Baris #

1. template<typename K, typename V>: class template memungkinkan LRU cache menyimpan tipe key dan value apa pun — int→string, string→vector<int>, dan lain-lain. Fleksibilitas ini krusial untuk penggunaan ulang di berbagai konteks.
2. list<pair<K,V>> list_;: doubly linked list dari std menyimpan pasangan key-value. Front adalah MRU, back adalah LRU. std::list dipilih karena menyediakan splice dan iterator stability.
3. unordered_map<K, typename list<pair<K,V>>::iterator> map_;: hash map menghubungkan key ke iterator list. typename diperlukan karena tipe iterator bergantung pada template parameter — kompilator butuh petunjuk bahwa ini adalah tipe, bukan value.
4. list_.splice(list_.begin(), list_, it->second);: pindahkan node yang ditunjuk iterator it->second ke depan list. splice adalah operasi O(1) yang memanipulasi pointer node tanpa copy data — sangat efisien.
5. if (list_.size() >= cap_) { auto last = list_.back(); map_.erase(last.first); list_.pop_back(); }: evict LRU. Ambil key dari node paling belakang, hapus dari hash map, lalu hapus dari list. Urutan penting: ambil key dulu sebelum node dihancurkan.
6. list_.emplace_front(key, value); map_[key] = list_.begin();: tambah node baru di depan. emplace_front mengkonstruksi pair in-place (lebih efisien dari push_front(make_pair(...))). Iterator begin() menunjuk ke node baru.
7. optional<V> get(const K& key): tipe kembalian optional menyatakan “mungkin tidak ada”. Lebih ekspresif daripada pointer V* dan tidak memerlukan manajemen memori manual.
8. v.value_or("(tidak ada)"): akses nilai dengan fallback bila nullopt. Lebih ringkas daripada if (v) *v else "(default)".

Variasi Strategi Cache #

LRU adalah strategi paling populer tetapi bukan satu-satunya. Pemilihan strategi bergantung pada pola akses data:

Aplikasi Praktis LRU #

Verifikasi dengan Trace #

Untuk memastikan LRU bekerja dengan benar, lakukan trace manual:

Trace ini cocok dengan output program — verifikasi visual bahwa LRU bekerja sesuai spec.

Ringkasan #

• LRU cache menggabungkan hash map (lookup O(1)) dan doubly linked list (reorder O(1)).
• Front list = MRU, back list = LRU. splice memindahkan node tanpa copy.
• Evict ambil dari list_.back(), hapus dari hash map dan list.
• Template class memungkinkan penggunaan untuk berbagai tipe key-value.
• Varian strategi: FIFO, LFU, ARC, 2Q — pilih sesuai pola akses.
• Pada skala besar, gunakan approximation (sampling) untuk efisiensi memori.