Thuật toán LRU (Least Recently Used) là gì? Giải thích dễ hiểu kèm demo trực quan

Thuật toán LRU được dùng rất nhiều trong trình duyệt, hệ điều hành, Redis, CDN, API gateway… Bài viết này giải thích cách hoạt động của LRU ở mức khái niệm, minh họa bằng ví dụ đơn giản và kèm theo một demo trực quan bằng JavaScript + UIkit để bạn thấy rõ từng bước cache hit, cache miss và loại bỏ phần tử.

LRU giải bài toán gì?

Giống như các thuật toán cache khác, LRU xử lý bài toán:

• Cache có dung lượng giới hạn (ví dụ: chỉ lưu được 4 key).
• Khi cần truy cập một key:
  • Nếu có trong cache → lấy từ cache (cache hit).
  • Nếu không có → cache miss → phải nạp từ nguồn gốc (database, disk, API).
• Khi cache đầy mà cần lưu thêm key mới → bắt buộc phải loại bỏ một key cũ.

Vấn đề: loại key nào ra để tổng thể cache hiệu quả nhất?
LRU đưa ra chiến lược: loại bỏ phần tử ít được sử dụng gần đây nhất.

Ý tưởng chính của thuật toán LRU

LRU dựa trên hai quan sát:

• Dữ liệu vừa được sử dụng gần đây có khả năng sẽ được dùng lại trong tương lai gần.
• Dữ liệu lâu rồi không được đụng tới có thể ít quan trọng hơn.

Do đó, LRU giữ lại các phần tử “vừa sờ tới” và hy sinh những phần tử đã bị lãng quên lâu nhất.

Mô hình đơn giản:

1. Cache được xem như một danh sách được sắp theo thứ tự sử dụng gần nhất.
   • Đầu danh sách: phần tử ít được dùng gần đây nhất.
   • Cuối danh sách: phần tử vừa được dùng gần đây nhất.
2. Khi truy cập một key:
   • Nếu key đã có trong cache:
     • Đây là một cache hit.
     • Dời key đó về cuối danh sách (coi như “vừa được dùng”).
   • Nếu key không có trong cache:
     • Đây là một cache miss.
     • Nếu cache chưa đầy → thêm key vào cuối danh sách.
     • Nếu cache đã đầy → loại phần tử ở đầu danh sách (least recently used) rồi thêm key mới vào cuối.

Ví dụ minh họa

Giả sử cache LRU có dung lượng 4 và ta truy cập lần lượt các key:

Truy cập: A, B, C, D, B, E, A

Diễn biến:

• Truy cập A → cache: [A]
• Truy cập B → cache: [A, B]
• Truy cập C → cache: [A, B, C]
• Truy cập D → cache: [A, B, C, D]
• Truy cập B:
  • B đã có trong cache → cache hit.
  • Di chuyển B ra cuối danh sách → [A, C, D, B]
• Truy cập E:
  • E chưa có → cache miss.
  • Cache đầy → loại phần tử đầu tiên (A).
  • Thêm E vào cuối → [C, D, B, E]
• Truy cập A:
  • A hiện không còn trong cache → cache miss.
  • Cache đầy → loại C → [D, B, E, A]

Qua ví dụ trên có thể thấy: phần tử không được dùng lại sẽ dần bị đẩy ra khỏi cache, còn phần tử được dùng lại sẽ “sống lâu” hơn.

Demo LRU Cache bằng JavaScript (UIkit)

Demo dưới đây mô phỏng cache LRU dung lượng 4:

• Nhập key (A, B, C, 1, 2, 3…) rồi bấm “Truy cập”.
• Cache sẽ:
  • Hit → di chuyển key đó về cuối (mới nhất).
  • Miss → nếu đầy sẽ loại phần tử lâu nhất, sau đó thêm key mới vào cuối.
• Màu sắc:
  • Ô đang được truy cập → tô xanh nhạt.
  • Ô vừa bị loại bỏ → tô đỏ nhạt ở log (thể hiện bằng text).
• Thống kê:
  • Tổng số lần hit / miss.
  • Tỷ lệ cache hit theo phần trăm.

Phân tích code thuật toán LRU

1. Khởi tạo cache và biến trạng thái

var LRU_CACHE_SIZE = 4;
var lruCache = [];          // mảng lưu các key, trái = cũ nhất, phải = mới nhất
var lastAccessKey = null;   // key vừa truy cập
var lastEvictedKey = null;  // key vừa bị loại

var hitCount = 0;
var missCount = 0;

2. Hàm log và render giao diện

function lruLog(msg) {
    var p = document.createElement("p");
    p.innerHTML = msg;
    lruLogBox.appendChild(p);
    lruLogBox.scrollTop = lruLogBox.scrollHeight;
}

function lruRender() {
    lruCacheBox.innerHTML = "";

    lruCache.forEach(function(key) {
        var div = document.createElement("div");
        var cls = "lru-item";

        if (key === lastAccessKey) {
            cls += " lru-item-accessed";
        }

        div.className = cls;
        div.textContent = key;
        lruCacheBox.appendChild(div);
    });

    var total = hitCount + missCount;
    var rate = total > 0 ? Math.round((hitCount / total) * 100) : 0;

    lruHitsSpan.textContent = hitCount;
    lruMissesSpan.textContent = missCount;
    lruHitRateSpan.textContent = rate + "%";
}

3. Thuật toán LRU cho mỗi lần truy cập

function lruAccess(key) {
    if (!key) return;

    lastAccessKey = key;
    lastEvictedKey = null;

    var index = lruCache.indexOf(key);

    if (index !== -1) {
        // Cache hit
        hitCount++;
        lruLog("Cache hit: key <strong>" + key + "</strong> đã có trong cache → đưa về vị trí mới nhất.");

        lruCache.splice(index, 1);
        lruCache.push(key);
    } else {
        // Cache miss
        missCount++;
        if (lruCache.length < LRU_CACHE_SIZE) {
            lruLog("Cache miss: thêm key <strong>" + key + "</strong> vào cache.");
            lruCache.push(key);
        } else {
            var evicted = lruCache.shift();
            lastEvictedKey = evicted;
            lruLog("Cache miss: cache đầy → loại key lâu nhất không dùng: <strong>" + evicted + "</strong>.");
            lruLog("Thêm key mới <strong>" + key + "</strong> vào cache.");
            lruCache.push(key);
        }
    }

    lruRender();
}

Trong triển khai thực tế (Redis, hệ điều hành…), người ta thường dùng Hash Map + Doubly Linked List để:

• Tìm kiếm key trong O(1).
• Di chuyển node trong danh sách liên kết trong O(1).

Trong demo này, để dễ hiểu, ta dùng mảng và indexOf cho đơn giản.

4. Nút random và reset

var SAMPLE_KEYS = ["A", "B", "C", "D", "E", "F", "G"];

lruRandomBtn.addEventListener("click", function () {
    var key = SAMPLE_KEYS[Math.floor(Math.random() * SAMPLE_KEYS.length)];
    lruInput.value = key;
    lruAccess(key);
});

lruResetBtn.addEventListener("click", function () {
    lruCache = [];
    lastAccessKey = null;
    lastEvictedKey = null;
    hitCount = 0;
    missCount = 0;
    lruLogBox.innerHTML = "Sẵn sàng chạy thuật toán LRU.";
    lruRender();
});

Khi nào nên dùng LRU?

LRU rất phù hợp với các hệ thống mà:

• Mẫu truy cập có tính “locality” – những dữ liệu vừa sử dụng có khả năng được dùng lại.
• Chi phí đọc lại dữ liệu từ nguồn gốc (disk, DB, remote API) cao.
• Cần cân bằng giữa độ hiệu quả và độ phức tạp thuật toán.

Ví dụ thực tế:

• Cache trang web, ảnh, file static trong browser.
• Page cache trong hệ điều hành (bộ nhớ ảo).
• Redis cache với eviction policy dạng LRU.
• API gateway / reverse proxy cache response tạm thời.

Kết luận

LRU là một trong những thuật toán cache quan trọng và thực tế nhất. Nó mô phỏng khá tốt hành vi truy cập dữ liệu của người dùng và ứng dụng trong đời sống thật.

Với demo UIkit và JavaScript ở trên, bạn có thể thấy rõ cách cache LRU:

• Di chuyển phần tử vừa truy cập về cuối danh sách.
• Loại bỏ phần tử lâu rồi không đụng tới khi cache đầy.
• Thống kê tỷ lệ hit/miss để đánh giá hiệu quả.

Trong các bài tiếp theo, chúng ta có thể đi tiếp vào thuật toán LFU (Least Frequently Used) và một bài tổng kết so sánh hiệu năng giữa FIFO, LRU và LFU.