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

Thuật toán LFU đặc biệt hiệu quả trong môi trường có pattern truy cập lặp lại rất nhiều, ví dụ hệ thống phục vụ hàng triệu request giống nhau mỗi ngày. Bài viết này giúp bạn hiểu rõ cách hoạt động của LFU, ví dụ minh hoạ và demo UIkit trực quan.

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

Giống FIFO và LRU, LFU giải quyết vấn đề cache đầy nhưng cách chọn phần tử bị loại khác biệt:

• Nếu key được truy cập nhiều → giữ lại.
• Nếu key ít khi được truy cập → dễ bị loại bỏ.

Nói ngắn gọn: giá trị sống của một phần tử phụ thuộc vào số lần nó được gọi.

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

Thuật toán LFU hoạt động dựa trên 3 nguyên tắc:

1. Mỗi key trong cache có một bộ đếm freq.
2. Mỗi lần truy cập key → freq++.
3. Khi cache đầy:
   • Loại bỏ key có freq thấp nhất.
   • Nếu nhiều key cùng freq thấp nhất → loại key nào cũ hơn (áp dụng LRU tie-break).

Vì vậy LFU được coi là thuật toán thông minh nhất trong nhóm cơ bản.

Ví dụ minh họa

Cache dung lượng: 3

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

Bảng tần suất:

• A → 3 lần
• B → 1 lần
• C → 1 lần

Cache đầy, truy cập D → cần loại bỏ key có freq thấp nhất.

B và C cùng freq = 1 → ai cũ hơn thì bị loại.

Nếu B cũ hơn → B bị loại → cache thành:

[C(freq=1), A(freq=3), D(freq=1)]

Demo LFU Cache bằng JavaScript (UIkit)

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

• Hiển thị freq ngay trên mỗi ô.
• Khi truy cập:
  • freq tăng
  • item được highlight
• Nếu cache đầy → loại item freq thấp nhất
• Nếu tie → loại item lâu nhất trong số chúng

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

1. Cấu trúc dữ liệu cache

var LFU_CACHE_SIZE = 4;

var lfuCache = []; 
// mỗi phần tử: { key: "A", freq: 1, time: ++counter }
var lfuTimer = 0;

time dùng để xử lý tie-break: ai cũ hơn sẽ bị loại trước.

2. Tìm phần tử cần loại bỏ

function findLFUEviction() {
    var minFreq = Math.min(...lfuCache.map(i => i.freq));
    var candidates = lfuCache.filter(i => i.freq === minFreq);
    candidates.sort((a, b) => a.time - b.time);
    return candidates[0]; 
}

LFU + LRU tie-break = chính xác như hệ thống thực tế.

3. Xử lý truy cập

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

    lfuTimer++;

    var existing = lfuCache.find(i => i.key === key);

    if (existing) {
        existing.freq++;
        existing.time = lfuTimer;
        lfuLog("Hit: tăng freq của <strong>" + key + "</strong> lên " + existing.freq);
    } else {
        if (lfuCache.length < LFU_CACHE_SIZE) {
            lfuCache.push({ key: key, freq: 1, time: lfuTimer });
            lfuLog("Miss: thêm key <strong>" + key + "</strong> (freq=1)");
        } else {
            var evict = findLFUEviction();
            lfuLog("Cache đầy → loại <strong>" + evict.key + "</strong> (freq=" + evict.freq + ")");
            lfuCache = lfuCache.filter(i => i !== evict);
            lfuCache.push({ key: key, freq: 1, time: lfuTimer });
            lfuLog("Thêm key mới <strong>" + key + "</strong> (freq=1)");
        }
    }

    lfuRender();
}

4. Render giao diện

function lfuRender() {
    lfuCacheBox.innerHTML = "";

    lfuCache
      .sort((a, b) => a.freq - b.freq || a.time - b.time)
      .forEach(function (item) {
        var div = document.createElement("div");
        div.className = "lfu-item";
        div.innerHTML = "<strong>" + item.key + "</strong>
<small>freq: " + item.freq + "</small>";
        lfuCacheBox.appendChild(div);
      });
}

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

LFU đặc biệt phù hợp khi bạn có:

• Dữ liệu “nóng” lặp đi lặp lại nhiều lần.
• Lưu lượng truy cập ổn định theo pattern cố định.
• Ứng dụng cần tối ưu tỉ lệ cache hit.

Ví dụ thực tế:

• CDN edge server ưu tiên giữ file có lượt truy cập cao.
• Redis cache với chế độ LFU.
• Cache API trả về dữ liệu phân tích thống kê.

Kết luận

LFU là thuật toán mạnh hơn FIFO và LRU khi nói về tần suất truy cập. Nó đảm bảo rằng phần tử nào “đáng được giữ lại” nhất sẽ tồn tại lâu nhất trong cache.

Với demo UIkit bên trên, bạn sẽ dễ dàng hiểu được cách LFU:

• Tăng freq khi truy cập.
• Sắp xếp cache theo freq + time.
• Loại bỏ phần tử ít dùng nhất khi cache đầy.

Bài tiếp theo trong series có thể là:

• So sánh hiệu năng FIFO – LRU – LFU
• Chạy mô phỏng 1000 requests random để so hit-rate