So sánh thuật toán cache FIFO, LRU và LFU: Lý thuyết và mô phỏng thực tế

Bài viết này giúp bạn:

• So sánh FIFO, LRU, LFU theo các tiêu chí quan trọng.
• Hiểu rõ khi nào nên dùng thuật toán nào.
• Xem một demo mô phỏng đơn giản bằng JavaScript + UIkit để thấy sự khác biệt về tỉ lệ cache hit.

Tổng quan nhanh về ba thuật toán

• FIFO (First In First Out)
  • Ai vào cache trước thì bị loại trước khi cache đầy.
  • Không quan tâm đến tần suất hay thời điểm truy cập gần nhất.
• LRU (Least Recently Used)
  • Loại bỏ phần tử lâu rồi không dùng tới.
  • Ưu tiên giữ lại phần tử vừa được sử dụng gần đây.
• LFU (Least Frequently Used)
  • Loại bỏ phần tử ít được truy cập nhất.
  • Có thể kết hợp tie-break kiểu LRU khi nhiều phần tử có tần suất bằng nhau.

Các tiêu chí dùng để so sánh

Để đánh giá ba thuật toán, ta có thể dựa vào các tiêu chí chính:

• Tỉ lệ cache hit: số lần lấy được dữ liệu ngay trong cache.
• Độ phức tạp triển khai: cấu trúc dữ liệu và chi phí lập trình.
• Độ ổn định với nhiều mẫu truy cập khác nhau.
• Chi phí bộ nhớ bổ sung: có cần lưu thêm metadata như tần suất, thời gian truy cập.

So sánh FIFO, LRU và LFU trên lý thuyết

FIFO

• Ưu điểm
  • Cực kỳ đơn giản, dễ triển khai.
  • Chi phí quản lý thấp.
• Nhược điểm
  • Có thể loại bỏ phần tử vẫn được dùng thường xuyên chỉ vì nó vào cache sớm.
  • Không phù hợp với pattern truy cập có locality rõ rệt.

LRU

• Ưu điểm
  • Phản ánh khá tốt hành vi thực tế của nhiều ứng dụng.
  • Hoạt động tốt khi dữ liệu có tính lặp lại theo thời gian ngắn.
• Nhược điểm
  • Có thể giảm hiệu quả khi pattern truy cập mang tính quét tuần tự khổng lồ.
  • Cần cấu trúc dữ liệu phức tạp hơn so với FIFO nếu muốn tối ưu tới O(1).

LFU

• Ưu điểm
  • Giữ lại các phần tử có tần suất truy cập cao, tối ưu cho dữ liệu nóng.
  • Hiệu quả trong môi trường có hành vi truy cập ổn định, lặp lại lâu dài.
• Nhược điểm
  • Khó triển khai hơn, cần lưu thêm tần suất và thường phải xử lý tie-break.
  • Có thể bị dính hiệu ứng dữ liệu từng nóng nhưng hiện tại không còn quan trọng (old but frequent).

Demo mô phỏng: FIFO vs LRU vs LFU với cùng tập yêu cầu

Demo dưới đây mô phỏng ba cache cùng kích thước 4, cùng xử lý một chuỗi request ngẫu nhiên trên tập key cố định:

• Khi bấm nút mô phỏng, hệ thống sẽ sinh ra một chuỗi request ngẫu nhiên, trong đó:
  • Một số key được truy cập thường xuyên hơn (dữ liệu nóng).
  • Một số key ít khi được chạm đến (dữ liệu lạnh).
• Cả ba thuật toán FIFO, LRU và LFU sẽ cùng xử lý chuỗi request đó.
• Sau khi chạy xong, UI hiển thị:
  • Tổng số hit, miss, tỉ lệ hit của từng thuật toán.
  • Trạng thái cache cuối cùng của mỗi thuật toán.
  • Log tóm tắt một vài request đầu tiên.

Phân tích code mô phỏng

1. Cấu hình và trạng thái chung

var CACHE_SIZE = 4;
var SAMPLE_KEYS_HOT = ["A", "B", "C", "D"];
var SAMPLE_KEYS_COLD = ["E", "F", "G", "H"];

Ý tưởng:

• Nhóm key nóng: A, B, C, D xuất hiện nhiều hơn.
• Nhóm key lạnh: E, F, G, H xuất hiện ít hơn.

2. Generate một chuỗi request ngẫu nhiên

function generateRequests(count) {
    var reqs = [];
    for (var i = 0; i < count; i++) {
        var useHot = Math.random() < 0.7; // 70% request vào nhóm hot
        var arr = useHot ? SAMPLE_KEYS_HOT : SAMPLE_KEYS_COLD;
        var key = arr[Math.floor(Math.random() * arr.length)];
        reqs.push(key);
    }
    return reqs;
}

3. Thuật toán FIFO trong mô phỏng

function fifoAccessSim(state, key) {
    var cache = state.cache;
    if (cache.indexOf(key) !== -1) {
        state.hits++;
    } else {
        state.misses++;
        if (cache.length < CACHE_SIZE) {
            cache.push(key);
        } else {
            cache.shift();
            cache.push(key);
        }
    }
}

4. Thuật toán LRU trong mô phỏng

function lruAccessSim(state, key) {
    var cache = state.cache;
    var idx = cache.indexOf(key);
    if (idx !== -1) {
        state.hits++;
        cache.splice(idx, 1);
        cache.push(key);
    } else {
        state.misses++;
        if (cache.length < CACHE_SIZE) {
            cache.push(key);
        } else {
            cache.shift();
            cache.push(key);
        }
    }
}

5. Thuật toán LFU trong mô phỏng

function lfuAccessSim(state, key) {
    var cache = state.cache; // mỗi phần tử: { key, freq, time }
    state.time++;

    var existing = cache.find(function (item) { return item.key === key; });
    if (existing) {
        state.hits++;
        existing.freq++;
        existing.time = state.time;
    } else {
        state.misses++;
        if (cache.length < CACHE_SIZE) {
            cache.push({ key: key, freq: 1, time: state.time });
        } else {
            var minFreq = Math.min.apply(null, cache.map(function (i) { return i.freq; }));
            var candidates = cache.filter(function (i) { return i.freq === minFreq; });
            candidates.sort(function (a, b) { return a.time - b.time; });
            var evict = candidates[0];
            cache.splice(cache.indexOf(evict), 1);
            cache.push({ key: key, freq: 1, time: state.time });
        }
    }
}

6. Chạy mô phỏng và cập nhật UI

function runSimulation(count) {
    resetSimulation(true);

    simLogBox.innerHTML = "";
    simLog("Bắt đầu mô phỏng với " + count + " request.");

    var requests = generateRequests(count);

    requests.forEach(function (key, index) {
        fifoAccessSim(fifoState, key);
        lruAccessSim(lruState, key);
        lfuAccessSim(lfuState, key);

        if (index < 20) {
            simLog(
                "Request " +
                    (index + 1) +
                    ": key <strong>" +
                    key +
                    "</strong>"
            );
        }
    });

    renderAll();
    simLog("Hoàn thành " + count + " request.");
}

Kết luận: chọn thuật toán nào trong thực tế

Không có thuật toán cache nào tốt nhất trong mọi trường hợp. Tùy theo bối cảnh, bạn có thể chọn:

• FIFO: khi cần một chiến lược cực đơn giản, dễ dự đoán, chi phí triển khai thấp.
• LRU: lựa chọn mặc định tốt cho đa số ứng dụng web và backend, nơi dữ liệu có xu hướng được lặp lại trong khoảng thời gian ngắn.
• LFU: phù hợp với hệ thống lớn, pattern truy cập ổn định và có sự phân tách rõ ràng giữa dữ liệu nóng và lạnh.

Thông qua mô phỏng, bạn có thể thấy trong nhiều kịch bản có dữ liệu nóng, LRU và LFU thường cho tỉ lệ hit cao hơn FIFO. LFU có thể nhỉnh hơn LRU nếu tần suất truy cập ổn định theo thời gian, trong khi LRU thích hợp hơn khi hành vi truy cập thay đổi liên tục theo từng giai đoạn.

Khi thiết kế hệ thống thực, việc lựa chọn thuật toán cache nên dựa trên:

• Mẫu truy cập dữ liệu thực tế.
• Tài nguyên bộ nhớ và CPU.
• Độ phức tạp chấp nhận được trong code base.

Bộ bốn bài về FIFO, LRU, LFU và bài so sánh, cùng với demo trực quan, giúp bạn có một nền tảng vững chắc để hiểu và lựa chọn chiến lược cache phù hợp cho sản phẩm của mình.