LFU, freshness, async và khóa đồng bộ trong cache

Giới thiệu

Bài này học LFU, cách dùng cache và khóa đồng bộ. Bạn dùng nó để web chạy nhanh mà không lỗi race.

Kiến thức cần nhớ

LFU đuổi theo tần suất

• LRU đuổi kẻ lâu không dùng, LFU đuổi kẻ ít được dùng nhất.
• Mỗi lần trúng thì tăng bộ đếm của khóa đó.
• Ví dụ đời thường: giữ món bán chạy trăm lần thay vì món vừa hỏi 1 lần.
• Thắng khi độ nóng ổn định, ví dụ bảng xếp hạng.

Hai bệnh của LFU

• Bám cũ: khóa từng nóng giờ nguội vẫn bám vì đếm cao.
• Chào sân: khóa mới đếm bằng 1 nên dễ bị đuổi oan.
• Chữa bằng già hóa đếm định kỳ hoặc chỉ đếm trong N phút gần nhất.
• Ví dụ đời thường: như cựu vô địch vẫn chiếm suất dù đã giải nghệ.

Cách dùng cache

• Khóa cache: quá thô thì ít trúng, quá mịn thì tốn nhớ.
• Ghi xuyên qua thì đúng ngay mà chậm, ghi lười thì nhanh mà rủi ro mất.
• Làm ấm trước khóa nóng để tránh khởi động lạnh.
• Ví dụ đời thường: như đặt tên hộp tủ, tên chung quá thì khó tìm, tên chi tiết quá thì nhiều hộp.

Khóa đồng bộ

• Khóa thường: đoạn găng chỉ 1 luồng vào.
• Khóa tái nhập: luồng đang giữ được vào tiếp mà không tự khóa mình.
• Khóa đọc: nhiều luồng đọc song song, ghi thì độc quyền.
• Ví dụ đời thường: như nhà vệ sinh, nhiều người soi gương được nhưng chỉ 1 người dùng buồng.

Ví dụ

• Input: cache LFU đầy, mọi đếm bằng nhau. Output: đuổi kẻ cũ nhất.
• Giải thích: hòa đếm thì lấy cũ nhất cho xác định.
• Input: 2 luồng đọc cùng khóa. Output: cả 2 cùng vào.
• Giải thích: đọc song song an toàn nhờ khóa đọc.

💻 Bài tập

Ngôn ngữ: C++17. Nộp vào day-066/.

Bài 1: LFU cache $O(1)$

class LFUCache {
 public:
  explicit LFUCache(size_t capacity);
  std::optional<int> get(int key);   // tăng tần suất
  void put(int key, int value);      // đầy thì đuổi khóa tần suất thấp nhất; hòa thì đuổi khóa ít dùng gần đây nhất
};

Cấu trúc gợi ý: key -> (value, freq, iterator), freq -> danh sách khóa theo thứ tự dùng, biến minFreq.

cap=2: put(1,1), put(2,2), get(1)   -> 1 (freq 1 = 2)
put(3,3)                             -> đuổi key 2 (freq thấp nhất)
get(2) -> nullopt; get(3) -> 3
put(4,4)                             -> key 1 và 3 cùng freq 2, đuổi key 1 (dùng lâu hơn)

Bài 2: So LRU và LFU

Dùng LRU ngày 39. Sinh 3 luồng truy cập 10^6 yêu cầu trên 10^4 khóa, cache 1000:

1. Zipf ổn định (khóa nóng không đổi).
2. Zipf đổi khóa nóng mỗi 10^5 yêu cầu.
3. Quét tuần tự lặp lại (1..2000, 1..2000, ...).

In hit rate của LRU và LFU cho từng luồng. Thêm LFU có già hóa: mỗi 10^4 yêu cầu chia đôi mọi tần suất. So kết quả ở luồng 2.

Bài 3: Cache nhiều luồng (nâng cao)

1. Bọc LRU bằng std::shared_mutex. Giải thích vì sao get của LRU không dùng được khóa đọc chung (nó sửa thứ tự).
2. Cài sharded cache: 16 phân mảnh, mỗi mảnh 1 LRU + 1 mutex, chọn mảnh theo hash(key) % 16.
3. Đo thông lượng với 1, 2, 4, 8 luồng cho: 1 mutex toàn cục và 16 phân mảnh.
4. Viết 1 ví dụ deadlock với 2 mutex, rồi sửa bằng std::scoped_lock.

✅ Tiêu chí hoàn thành

• LFU pass test mẫu và test ngẫu nhiên so với bản chậm.
• Bảng hit rate 3 luồng x 3 chiến lược có số thật.
• -fsanitize=thread sạch.
• Bảng thông lượng theo số luồng có số thật.

❓ Câu hỏi ôn tập

• LFU và LRU khác nhau thế nào?
• Hai bệnh của LFU là gì?
• Vì sao cách dùng cache quan trọng như chính sách đuổi?
• Khóa đọc khác khóa thường ở điểm nào?

🌕 Bạn đã hoàn thành ngày 66. Làm hết bài tập phía trên rồi sang ngày tiếp theo.