Đây chính là nhiệm vụ của thuật toán thay thế trang (page replacement algorithms). Chúng quyết định phần tử nào nên được giữ lại, và phần tử nào nên bị loại bỏ dựa trên hành vi truy cập thực tế.
Bài viết này đóng vai trò như một bài Hub — cung cấp góc nhìn tổng quan về các thuật toán cache phổ biến nhất (FIFO, LRU, LFU), cách chúng hoạt động, ưu – nhược điểm và khi nào nên sử dụng thuật toán nào.
Cache là gì và tại sao cần thuật toán thay thế?
Cache là một vùng nhớ nhỏ nhưng tốc độ rất nhanh, dùng để lưu trữ tạm thời những dữ liệu được truy cập nhiều.
Nhưng cache có giới hạn — ví dụ:
- Trình duyệt chỉ lưu được một lượng file nhất định.
- Redis có dung lượng bộ nhớ giới hạn.
- CDN (như Cloudflare) chỉ lưu một số lượng file nóng nhất ở edge server.
- Hệ điều hành chỉ giữ một số trang (pages) trong RAM để tối ưu tốc độ.
Khi cache đầy, hệ thống sẽ cần dùng thuật toán thay thế trang để quyết định phần tử nào bị loại bỏ (eviction) để thêm phần tử mới.
Các yếu tố quan trọng khi thiết kế thuật toán cache
Mỗi môi trường có nhu cầu riêng, nhưng đa phần thuật toán cache phải cân nhắc:
- Tính mới (recency): Dữ liệu vừa truy cập gần đây nên được giữ lại?
- Tần suất (frequency): Dữ liệu được truy cập thường xuyên có quan trọng hơn?
- Chi phí tải lại: Mất nhiều thời gian để tải lại dữ liệu đó?
- Hiệu năng thuật toán: Có chạy nhanh với lượng dữ liệu lớn không?
- Tính đơn giản vs. hiệu quả: Một thuật toán đơn giản đôi khi đủ tốt và dễ triển khai.
FIFO – First In First Out
FIFO là thuật toán thay thế trang đơn giản nhất:
- Phần tử vào cache trước → bị loại bỏ trước.
- Queue là cấu trúc dữ liệu phù hợp nhất để triển khai.
Ưu điểm:
- Cực kỳ dễ hiểu, dễ code.
- Hiệu năng ổn vì cấu trúc đơn giản.
Nhược điểm:
- Không xem xét “recently used”.
- Dễ loại bỏ phần tử vẫn đang được dùng.
Khi dùng: các hệ thống cũ, nhúng, buffer đơn giản.
LRU – Least Recently Used
LRU ưu tiên giữ lại các phần tử được truy cập gần đây nhất.
Ý tưởng: Nếu một phần tử lâu rồi không được sử dụng → khả năng cao sắp tới cũng không cần.
Cách triển khai:
- Dùng danh sách liên kết kép (Doubly Linked List) + Hash Map.
- Mỗi lần truy cập → di chuyển phần tử lên đầu danh sách.
- Khi cache đầy → loại phần tử cuối danh sách (lâu nhất).
Ưu điểm:
- Rất hiệu quả trong hầu hết các môi trường thực tế.
- Được dùng trong trình duyệt, Redis, hệ điều hành…
Nhược điểm:
- Một số workloads khiến LRU hoạt động không tối ưu (ví dụ: truy cập tuần tự khổng lồ).
- Chi phí quản lý cấu trúc dữ liệu cao hơn FIFO.
Khi dùng: hầu hết mọi ứng dụng web và backend.
LFU – Least Frequently Used
LFU chọn loại bỏ phần tử ít được truy cập nhất.
Ý tưởng:
- Mỗi phần tử đi kèm bộ đếm tần suất (
freq). - Khi truy cập →
freq++. - Khi cache đầy → loại phần tử có freq thấp nhất.
Ưu điểm:
- Giữ lại các phần tử “được dùng nhiều nhất” → tối ưu cho pattern tần suất cao.
- Rất tốt cho cache CDN và dữ liệu nóng.
Nhược điểm:
- Cần xử lý tie-break (2 phần tử cùng freq).
- Triển khai phức tạp nhất trong nhóm cơ bản.
Khi dùng: hệ thống traffic lớn, mẫu truy cập ổn định.
So sánh nhanh FIFO – LRU – LFU
- FIFO: dễ triển khai, nhưng hiệu quả thấp trong thực tế.
- LRU: cân bằng tốt giữa đơn giản và hiệu quả → được dùng phổ biến nhất.
- LFU: mạnh trong môi trường dữ liệu lặp lại nhiều, tần suất cao.
Bảng so sánh tóm tắt:
- FIFO → theo thứ tự thời gian vào cache.
- LRU → theo thời gian sử dụng gần nhất.
- LFU → theo tần suất sử dụng.
Các yếu tố thực tế khi chọn thuật toán cache
Khi áp dụng vào hệ thống thật, cần cân nhắc:
- Pattern truy cập: tuần tự hay lặp lại?
- Chi phí load dữ liệu: có tốn thời gian không?
- Memory overhead: cần đánh đổi thêm bao nhiêu RAM?
- Cấu trúc dữ liệu: ưu tiên tốc độ hay đơn giản?
Không có thuật toán nào hoàn hảo, nhưng mỗi thuật toán phù hợp với ngữ cảnh cụ thể. Đó cũng là lý do hệ sinh thái hiện nay rất đa dạng: từ FIFO trong embedded, đến LRU trong web browser, cho tới LFU trong cache của hệ thống lớn.
Bình luận