LRU Cache: Cara Cache Memutuskan Data Mana yang Harus Dibuang

Introduction

Beberapa waktu lalu saya ketemu lagi sama satu masalah yang kelihatannya simpel: aplikasi sudah pakai cache, tapi cache-nya mau diisi terus sampai kapan?

Memory terbatas. Jadi kalau cache sudah penuh dan ada data baru yang masuk, kita harus memilih data mana yang dibuang.

Nah, di situlah LRU, atau Least Recently Used, biasanya masuk.

Konsepnya cukup enak dipahami kalau dibayangkan sebagai satu baris data. Yang baru saja dipakai pindah ke depan. Yang paling lama tidak disentuh ada di belakang. Kalau cache penuh, buang yang paling belakang.

Kenapa cache perlu eviction policy?

Misalnya kita punya cache dengan kapasitas cuma 3 item.

Awalnya:

[A] [B] [C]

Lalu ada request untuk A.

Karena A baru saja dipakai, posisi A dianggap paling baru:

[A] [B] [C]

Sekarang datang D.

Cache sudah penuh. Kita harus menghapus satu item.

Pertanyaannya: A, B, atau C?

Kalau kita cuma melihat kapan data masuk, kita bisa menggunakan FIFO. Data yang masuk paling awal akan dibuang lebih dulu.

Tapi ada masalah.

A tadi baru saja dipakai. Sementara B sudah lama tidak disentuh.

LRU memilih B.

flowchart LR
    A["A
baru dipakai"] --> B["B
paling lama tidak dipakai"]
    B --> C["C"]
    C --> D["D
data baru"]

Jadi aturan sederhananya:

Data yang paling lama tidak digunakan akan menjadi kandidat pertama untuk dibuang.

LRU bergantung pada temporal locality

LRU punya satu asumsi yang cukup masuk akal: kalau sesuatu baru saja digunakan, ada kemungkinan kita akan menggunakannya lagi dalam waktu dekat.

Ini disebut temporal locality.

Contohnya gampang ditemui di aplikasi. Sebuah halaman yang baru saja dibuka bisa saja diminta lagi. Data user yang baru saja diakses mungkin akan dipakai lagi oleh request berikutnya.

LRU tidak tahu masa depan. Ia cuma memakai pola penggunaan yang sudah terjadi.

Karena itu, urutan akses menjadi penting.

Misalnya cache kita berisi:

[C] [B] [A]

Anggap posisi paling kiri adalah item yang paling baru digunakan.

Kemudian A diakses:

flowchart LR
    subgraph Before["Sebelum A diakses"]
        C1["C"] --> B1["B"] --> A1["A"]
    end

    subgraph After["Setelah A diakses"]
        A2["A"] --> C2["C"] --> B2["B"]
    end

    Before --> After

A pindah ke depan karena baru saja disentuh.

Kalau setelah itu D masuk dan cache penuh, B yang keluar.

Kenapa tidak cukup pakai array?

Kalau cuma membuat contoh sederhana, array sebenarnya bisa.

Misalnya:

const cache = ["C", "B", "A"];

Ketika A dipakai, kita bisa mencari A, menghapusnya, lalu memasukkannya ke depan.

Masalahnya ada di kompleksitas.

Untuk mencari item di array, kita bisa membutuhkan O(n). Memindahkan item juga bisa membutuhkan operasi terhadap banyak elemen.

Untuk cache kecil mungkin tidak terasa. Tapi kalau cache berisi banyak item dan operasi get terjadi sangat sering, pendekatan ini mulai kurang menarik.

Kita ingin tiga operasi ini tetap cepat:

• mencari item
• memindahkan item yang baru dipakai ke depan
• membuang item yang paling lama dipakai

Idealnya semuanya O(1).

Di sinilah struktur data yang dipakai LRU mulai menarik.

HashMap + doubly linked list

Implementasi LRU yang umum menggunakan dua struktur data:

1. HashMap untuk menemukan node dengan cepat.
2. Doubly Linked List untuk mengatur urutan penggunaan.

Gambaran sederhananya seperti ini:

flowchart LR
    subgraph Map["HashMap"]
        A["A"] --> NA["Node A"]
        B["B"] --> NB["Node B"]
        C["C"] --> NC["Node C"]
    end

    subgraph List["Doubly Linked List"]
        H["HEAD"] --> NA
        NA <--> NB
        NB <--> NC
        NC --> T["TAIL"]
    end

HashMap menyimpan pasangan key dan node.

Jadi ketika kita melakukan:

cache.get("A");

kita tidak perlu mencari A dari awal sampai akhir. HashMap bisa langsung memberikan node A.

Setelah node ditemukan, kita tinggal memindahkannya ke depan linked list.

Kenapa doubly linked list?

Karena kita perlu menghapus sebuah node dari posisi tengah dengan cepat.

Misalnya:

A <-> B <-> C

Kalau B baru saja digunakan, kita ingin mengeluarkannya dari posisi sekarang:

A <-> C

Lalu memasukkannya ke depan:

B <-> A <-> C

Dengan doubly linked list, node B punya referensi ke node sebelum dan sesudahnya.

flowchart LR
    A["A"] <--> B["B"] <--> C["C"]

    B -->|"remove"| X["A <-> C"]
    X -->|"move to front"| Y["B <-> A <-> C"]

Kalau linked list-nya hanya singly linked list, kita perlu mencari node sebelumnya untuk melakukan unlink. Itu bisa membuat operasi menjadi O(n).

Doubly linked list menyimpan prev dan next, jadi node bisa dilepas langsung.

Cara kerja get dan put

Anggap cache punya kapasitas 3.

Urutan akses:

put(A)
put(B)
put(C)
get(A)
put(D)

Kita bisa mengikuti perubahannya satu per satu.

Setelah put(A):

A

Setelah put(B):

B -> A

Setelah put(C):

C -> B -> A

Kemudian get(A):

A -> C -> B

Sekarang D masuk.

Cache sudah penuh, jadi item paling belakang, yaitu B, dibuang:

D -> A -> C

Visualisasinya:

flowchart TD
    S1["put(A)
A"] --> S2["put(B)
B -> A"]
    S2 --> S3["put(C)
C -> B -> A"]
    S3 --> S4["get(A)
A -> C -> B"]
    S4 --> S5["put(D)
D -> A -> C
B di-evict"]

Di sini kelihatan kenapa LRU berbeda dari FIFO.

FIFO hanya peduli kapan item masuk.

LRU peduli kapan item terakhir digunakan.

Implementasi sederhana dengan TypeScript

Berikut versi sederhana yang fokus ke mekanisme LRU, bukan production-ready cache.

type Node<K, V> = {
  key: K;
  value: V;
  prev: Node<K, V> | null;
  next: Node<K, V> | null;
};

class LRUCache<K, V> {
  private readonly map = new Map<K, Node<K, V>>();
  private readonly capacity: number;

  private head: Node<K, V> | null = null;
  private tail: Node<K, V> | null = null;

  constructor(capacity: number) {
    this.capacity = capacity;
  }

  get(key: K): V | undefined {
    const node = this.map.get(key);

    if (!node) {
      return undefined;
    }

    this.moveToFront(node);
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);

    if (existing) {
      existing.value = value;
      this.moveToFront(existing);
      return;
    }

    const node: Node<K, V> = {
      key,
      value,
      prev: null,
      next: null,
    };

    this.map.set(key, node);
    this.addToFront(node);

    if (this.map.size > this.capacity) {
      this.removeTail();
    }
  }

  private addToFront(node: Node<K, V>): void {
    node.next = this.head;

    if (this.head) {
      this.head.prev = node;
    }

    this.head = node;

    if (!this.tail) {
      this.tail = node;
    }
  }

  private moveToFront(node: Node<K, V>): void {
    if (node === this.head) {
      return;
    }

    if (node.prev) {
      node.prev.next = node.next;
    }

    if (node.next) {
      node.next.prev = node.prev;
    }

    if (node === this.tail) {
      this.tail = node.prev;
    }

    node.prev = null;
    node.next = this.head;

    if (this.head) {
      this.head.prev = node;
    }

    this.head = node;
  }

  private removeTail(): void {
    if (!this.tail) {
      return;
    }

    const oldTail = this.tail;

    if (oldTail.prev) {
      oldTail.prev.next = null;
      this.tail = oldTail.prev;
    } else {
      this.head = null;
      this.tail = null;
    }

    this.map.delete(oldTail.key);
  }
}

Yang perlu diperhatikan bukan banyaknya baris kode, tapi hubungan dua struktur datanya.

Map menjawab:

"Node untuk key ini ada di mana?"

Linked list menjawab:

"Node mana yang paling baru dan mana yang paling lama dipakai?"

Keduanya bekerja bareng.

Kompleksitasnya

Dengan desain tersebut:

HashMap membuat lookup cepat.

Doubly linked list membuat proses memindahkan dan menghapus node tidak perlu berjalan melewati seluruh data.

💡 Kalau ketemu pertanyaan interview "How would you implement an LRU cache with O(1) get and put?", kombinasi HashMap + Doubly Linked List adalah pola yang perlu langsung terlintas.

LRU bukan berarti selalu pilihan terbaik

LRU bekerja dengan asumsi bahwa data yang baru digunakan kemungkinan akan digunakan lagi.

Kalau pola akses aplikasinya tidak seperti itu, hasilnya bisa berbeda.

Ada juga kebijakan eviction lain seperti FIFO, yang hanya melihat urutan masuknya data.

Jadi sebelum memilih cache policy, kita tetap perlu melihat bagaimana data di aplikasi benar-benar digunakan.

Conclusion

LRU sebenarnya punya ide yang cukup sederhana.

Simpan data berdasarkan seberapa baru data itu dipakai. Saat cache penuh, buang yang paling lama tidak disentuh.

Yang membuat implementasinya menarik adalah kebutuhan untuk melakukan semuanya dengan cepat. HashMap menangani lookup, sementara doubly linked list menjaga urutan penggunaan.

Kalau sudah paham alur get, put, move to front, dan remove tail, implementasi LRU yang kelihatannya rumit mulai terasa cukup masuk akal.