[Backend Masterclass] Các thuật toán Caching: LIFO, LRU và Tuyệt kĩ "Cơ hội thứ 2" CLOCK

Chào anh em! Sau khi chúng ta đã đi sâu vào cách Redis "đuổi khách" (Eviction) khi cạn RAM ở bài trước, hôm nay chúng ta sẽ mở rộng tầm mắt ra toàn bộ thế giới Khoa học Máy tính.

Không chỉ Redis, mà Hệ điều hành (Linux, Windows), Trình duyệt (Chrome), hay Database (PostgreSQL) đều phải đối mặt với một bài toán kinh điển: "Cái kho (Cache) thì có 3 chỗ, mà có tới 10 món đồ cần nhét vào. Nhét thằng mới vào thì phải đá thằng nào ra?"

Đó chính là lúc các thuật toán thay thế bộ nhớ đệm (Cache Replacement Algorithms) lên ngôi. Hôm nay chúng ta sẽ mổ xẻ 3 thuật toán: LIFO, LRU và CLOCK để xem tư duy của các kĩ sư hệ thống vĩ đại như thế nào nhé. Để dễ hình dung, giả sử bộ nhớ đệm (Cache) của anh em chỉ chứa được tối đa 3 phần tử. Một luồng dữ liệu (A, B, C, D...) liên tục được CPU yêu cầu. Nếu dữ liệu có trong Cache -> Cache Hit (Ngon). Nếu không có -> Cache Miss (Phải tải từ ổ cứng lên, mất thời gian) và phải tìm cách "đá" một thằng trong Cache ra để nhường chỗ.

1. LIFO (Last-In, First-Out) - Kẻ ngược đời

Anh em học cấu trúc dữ liệu chắc quen thuộc với LIFO qua cấu trúc Stack (Ngăn xếp).

• Nguyên lý: Thằng nào mới được nhét vào gần đây nhất, thằng đó sẽ bị đá ra đầu tiên khi Cache đầy.
• Cách hoạt động: Cache có [A, B, C]. C vừa được nhét vào cuối cùng. Giờ D muốn vào. Theo LIFO, nó sẽ đá thằng C ra. Cache thành [A, B, D].

Sự thật phũ phàng: Trong thế giới Caching thông thường (như Web, Database), LIFO là một thảm họa (Anti-pattern). Tại sao? Vì những dữ liệu mới được tải lên thường là những dữ liệu sắp được dùng tiếp. Đá nó ra ngay lập tức là một sự ngu ngốc. Vậy tại sao người ta vẫn đẻ ra LIFO Cache? Nó được dùng trong các trường hợp cực kì đặc thù: Khi anh em muốn Ghim (Pin) những phần tử đầu tiên vĩnh viễn trong Cache. LIFO sẽ bảo vệ những thằng cũ (A, B) không bao giờ bị đuổi, và chỉ đem thằng mới nhất ra làm "tốt thí".

2. LRU (Least Recently Used) - Tiêu chuẩn công nghiệp

Đây là thuật toán "quốc dân", được dùng ở 90% các hệ thống Caching.

• Nguyên lý: Đuổi thằng đã bị bỏ lơ (không được truy cập) lâu nhất.
• Cách hoạt động: Nó duy trì một danh sách. Mỗi khi bạn truy cập vào một phần tử (dù là thêm mới hay đọc lại), phần tử đó sẽ được đẩy lên Đầu danh sách (Vừa mới dùng). Khi Cache đầy, thằng nằm ở Cuối danh sách (Lâu rồi không ai ngó ngàng) sẽ bị trảm.

Ưu điểm: Cực kì phù hợp với hành vi của con người (Nguyên lý Locality of Reference). Bài báo nào đang hot sẽ được đọc liên tục (luôn nằm ở đầu). Bài nào hết hot sẽ tự trôi về cuối và bị xóa. Nhược điểm cực lớn: Để duy trì thứ tự Đầu - Cuối này, LRU xài cấu trúc Doubly Linked List + Hash Map. Nghĩa là MỖI LẦN bạn đọc data, nó phải thực hiện thao tác cắt/nối con trỏ để đảo phần tử lên đầu. Tốn cực nhiều CPU và Memory Overhead (như bài Redis mình đã phân tích).

3. CLOCK (Second-Chance Algorithm) - Tuyệt kĩ của Hệ điều hành

Vì LRU chuẩn quá tốn kém (thao tác đổi chỗ liên tục), các kĩ sư thiết kế Hệ điều hành (Linux Page Replacement) và Database (như PostgreSQL) không thèm dùng nó. Họ sáng tạo ra một thuật toán thông minh, nhẹ nhàng và xảo quyệt hơn rất nhiều: Thuật toán Đồng hồ (CLOCK) hay còn gọi là "Cơ hội thứ 2".

• Nguyên lý: Xếp các phần tử thành một vòng tròn (như mặt đồng hồ). Cấp cho mỗi thằng một cái bùa hộ mệnh gọi là Reference Bit (Bit tham chiếu). Ban đầu cờ này bằng 1. Có một cái Kim đồng hồ (Pointer) chỉ vào 1 phần tử.
• Khi có lệnh đọc/ghi: Thằng nào được truy cập, nó sẽ được cập nhật Reference Bit = 1 (Tức là: Tao vừa được dùng đấy nhé). Mọi thứ giữ nguyên vị trí, không tốn công dịch chuyển con trỏ nào cả! Tốc độ O(1) tuyệt đối.
• Khi Cache đầy và cần đuổi người: Cái Kim đồng hồ bắt đầu quay.
• Nó chỉ vào thằng A. Nó hỏi: "Bit của mày là 1 hay 0?"
• Nếu là 1: Kim đồng hồ nói: "Mày được tha mạng lần này (Second chance), nhưng tao sẽ hạ cờ của mày xuống 0". Rồi kim quay tiếp sang thằng B.
• Nếu nó chỉ vào một thằng có cờ là 0: Tức là từ vòng quay trước đến vòng quay này, chả có ai dùng nó cả. Đuổi nó ngay lập tức!

Sự vĩ đại của CLOCK: Nó mô phỏng lại gần như hoàn hảo sự hiệu quả của LRU (ưu tiên giữ lại data hay dùng), nhưng lại không cần phải di chuyển vị trí dữ liệu. Nó tiết kiệm được một lượng tài nguyên khổng lồ cho Server.

Lời kết

Anh em có thắc mắc gì về mấy thuật toán lõi này không? Comment bên dưới nhé! Thấy bánh cuốn thì đừng quên 1 Upvote ủng hộ tác giả! 🚀