Cơ chế xóa Key của Redis: Bậc thầy về thiết kế hệ thống theo xác suất

Nếu bạn đã từng tự triển khai một bộ nhớ đệm (cache) có tính năng TTL (thời gian sống), chắc hẳn bạn đã đối mặt với một bài toán cân bằng khó khăn: làm thế nào để xóa các mục hết hạn một cách hiệu quả mà không làm chậm tốc độ ghi hoặc lãng phí bộ nhớ?

Redis — kho lưu trữ dữ liệu in-memory nổi tiếng với độ trễ dưới một phần nghìn giây (sub-millisecond) — có một giải pháp cực kỳ thanh lịch. Nó không dựa vào các cấu trúc dữ liệu phức tạp như heap hay danh sách liên kết để quản lý việc hết hạn. Thay vào đó, nó sử dụng một chút ngẫu nhiên và rất nhiều tư duy kỹ thuật thông minh.

Hãy cùng mổ xẻ cách nó hoạt động.

Cách tiếp cận ngây thơ (The Naïve Approach)

Hãy tưởng tượng bạn đang thiết kế cache của riêng mình. Bạn muốn mọi mục nhập (entry) đều hết hạn sau một khoảng thời gian. Giải pháp trực diện nhất là:

1. Duy trì một danh sách được sắp xếp (hoặc min-heap) các key theo thời gian hết hạn.
2. Định kỳ kiểm tra các key ở đầu danh sách và xóa những key đã quá hạn.

Cách này hoạt động được… nhưng không hề rẻ. Mỗi lần chèn vào heap tốn chi phí O(log n), và với hàng triệu key, con số này sẽ cộng dồn lại rất lớn.

Redis được thiết kế để xử lý hàng triệu lượt ghi mỗi giây; một đường dẫn ghi tốn O(log n) đơn giản là không thể chấp nhận được. Vậy Redis làm thế nào để tránh điều này?

Hai cơ chế bổ trợ của Redis

Redis sử dụng hai cơ chế song song để xử lý việc hết hạn một cách hiệu quả:

1. Xóa lười (Lazy Expiration)

Mỗi khi một key được truy cập (ví dụ, thông qua GET hoặc HGET), Redis sẽ kiểm tra xem nó đã hết hạn hay chưa.

Nếu có, nó sẽ xóa key đó ngay lập tức và giả vờ như key đó chưa từng tồn tại. Đây là việc dọn dẹp "miễn phí", với giả định rằng key đó sẽ được truy cập lại.

Nhưng còn những key đã hết hạn mà không bao giờ được đụng tới thì sao? Đó là lúc cơ chế thứ hai vào cuộc.

2. Xóa chủ động (Vòng lặp dọn dẹp ngẫu nhiên)

Bên trong, Redis giữ một từ điển (dictionary) riêng biệt gọi là expires, ánh xạ các key tới thời gian hết hạn của chúng:

expires["foo"] = 1730665000000  // Unix time in ms

Chỉ những key có TTL mới nằm trong từ điển này.

Khoảng 10 lần mỗi giây, Redis chạy một tiến trình nền (activeExpireCycle) thực hiện các bước sau:

1. Lấy mẫu ngẫu nhiên 20 key từ từ điển expires.
2. Nếu TTL của key mẫu đã qua, xóa nó.
3. Nếu hơn 25% số key mẫu đã hết hạn, chạy tiếp một vòng nữa, cho đến khi đạt giới hạn thời gian CPU.

Đây là phiên bản đơn giản hóa của logic đó:

for each db in redis:
    repeat:
        expired_count = 0
        for i in 1..20:
            key = random_key(db.expires)
            if key.is_expired():
                delete(key)
                expired_count++
        if expired_count < 5:  // <25%
            break

Chỉ có vậy. Không có heap toàn cục. Không có các thao tác O(log n). Chỉ có lấy mẫu ngẫu nhiên và dọn dẹp thích ứng.

Làm thế nào Redis chọn Key "Ngẫu nhiên"?

Đây là điểm sáng trong thiết kế. Hash table của Redis hỗ trợ lấy mẫu ngẫu nhiên với độ phức tạp O(1). Bên trong, hàm random_key chọn một bucket ngẫu nhiên trong hash table và trả về key đầu tiên nó tìm thấy ở đó. Điều này có nghĩa là Redis có thể lấy key ngẫu nhiên mà không cần quét toàn bộ từ điển hay duy trì một index riêng biệt. Làm điều này 20 lần, và bạn có 20 key ngẫu nhiên cực nhanh!

Tại sao sự ngẫu nhiên lại hiệu quả?

Thoạt nhìn, điều này nghe có vẻ quá sơ sài. Nhỡ Redis cứ chọn phải những key chưa hết hạn thì sao?

Đây là ma thuật của xác suất:

Nếu một lượng lớn key đã hết hạn (ví dụ 30–40%), xác suất chọn trúng một key hết hạn trong 20 mẫu là rất cao. Khi điều đó xảy ra, Redis ngay lập tức chạy thêm một vòng nữa. Nó tiếp tục lặp lại cho đến khi ít hơn 25% số key mẫu là hết hạn.

Về mặt thống kê, hệ thống tự điều chỉnh:

Redis tự động dọn dẹp tích cực hơn khi có lượng lớn key hết hạn tồn đọng, và thư giãn khi mọi thứ đã gọn gàng. Đó là một vòng phản hồi được vận hành bởi xác suất.

Lợi ích đạt được

Thiết kế này mang lại ba lợi ích mạnh mẽ:

Tinh chỉnh hành vi

Một vài cài đặt nội bộ kiểm soát hành vi này:

Các thông số này có thể được tinh chỉnh cho các hệ thống lớn nơi hàng triệu key hết hạn thường xuyên, nhưng các giá trị mặc định hoạt động rất tốt cho hầu hết các trường hợp.

Bài học về Thiết kế Hệ thống

Chiến lược hết hạn key của Redis là một case study điển hình về thiết kế hệ thống theo xác suất (probabilistic system design), sử dụng sự ngẫu nhiên để cân bằng giữa hiệu năng và tính chính xác.

Thay vì duy trì một hàng đợi hết hạn chính xác tuyệt đối, Redis chấp nhận việc dọn dẹp gần đúng để đổi lấy tốc độ cực nhanh. Và nhờ vào phản hồi thống kê, nó vẫn hội tụ về trạng thái đúng.

Nó là lời nhắc nhở rằng đôi khi, nước đi kỹ thuật thông minh nhất không phải là trở nên hoàn hảo, mà là trở nên đủ tốt, và nhanh.

Lời kết

Redis chứng minh rằng sự ngẫu nhiên không phải là kẻ thù của tính tất định — khi được sử dụng cẩn thận, nó là công cụ để xây dựng các hệ thống nhanh, tự sửa lỗi.

Vì vậy, lần tới khi bạn thiết kế một bộ nhớ đệm hay bộ lập lịch (scheduler), hãy tự hỏi:

Mình có thực sự cần một thứ tự toàn cục hoàn hảo không… hay một chút ngẫu nhiên là đủ để hoàn thành công việc?