LRU cache: thứ tự thời gian và đuổi dữ liệu cũ

Giới thiệu

Bài này học cache ghi nhớ kết quả để trả lời nhanh. Cache này giúp vượt trần 3.5 giây của bài tóm tắt.

Kiến thức cần nhớ

Vì sao cần cache

• Tính tóm tắt tốn 250ms mỗi nguồn, dễ vượt 3.5 giây.
• Mỗi công ty mỗi ngày chỉ cần một bản tóm tắt.
• Tính một lần rồi cất lại, lần sau đọc ra ngay.
• Ví dụ đời thường: photo tài liệu một lần, lần sau lấy bản photo.

Tươi mới và đang tải

• Dữ liệu có hạn dùng, qua ngày mới phải tính lại.
• Nhiều luồng cùng hỏi khóa chưa có thì dễ tính trùng.
• Cờ đang tải: một luồng tính, các luồng khác chờ.
• Ví dụ đời thường: một người xếp hàng mua, cả nhóm chờ chia nhau.

LRU đuổi kẻ cũ nhất

• Bộ nhớ đầy thì đuổi món lâu nhất không dùng.
• Cài đặt: dict tra $O(1)$ cộng danh sách đôi giữ thứ tự.
• Trúng thì nhấc lên đầu, thêm mới thì cắt đuôi.
• Ví dụ đời thường: tủ lạnh đầy thì bỏ món cũ nhất.

# Ý tưởng LRU: mới dùng thì lên đầu
from collections import OrderedDict
cache = OrderedDict()  # giữ thứ tự dùng
def lay(k):
    if k in cache:  # trúng cache
        cache.move_to_end(k, last=False)  # nhấc lên đầu
        return cache[k]
    return None  # trượt thì đi tính thật

Ví dụ

• Input: cache rỗng, hỏi khóa A -> Output: miss, đi tính thật rồi ghi lại.
• Câu này cho thấy lần đầu luôn chậm để làm ấm.
• Input: cache đầy 3 khóa, thêm khóa thứ 4 -> Output: khóa cũ nhất bị đuổi.
• Câu này cho thấy quy tắc cắt đuôi hoạt động.

💻 Bài tập

Ngôn ngữ: C++. Tự cài danh sách đôi và dùng std::unordered_map cho tra cứu. Không dùng std::list. Nộp vào day-039/.

Bài 1: LRU cache

class LRUCache {
 public:
  explicit LRUCache(size_t capacity);       // capacity = 0 thì ném invalid_argument
  std::optional<int> get(int key);          // trúng thì đưa lên đầu
  void put(int key, int value);             // có rồi thì cập nhật và đưa lên đầu; đầy thì đuổi đuôi
  size_t size() const;
  std::vector<int> keysMostRecentFirst() const;   // để test thứ tự
};

cap=2: put(1,1), put(2,2), get(1) -> 1
put(3,3)                          -> đuổi key 2
get(2)                            -> nullopt
put(4,4)                          -> đuổi key 1
get(1) -> nullopt; get(3) -> 3; get(4) -> 4
keysMostRecentFirst()             -> [4, 3]

Bài 2: Cache có hạn dùng và thống kê

1. Thêm put(key, value, ttlMs). get gặp mục hết hạn thì xóa và trả nullopt. Dùng đồng hồ giả Clock& để test không cần sleep.
2. Thêm hits(), misses(), hitRate().
3. Bọc hàm chậm long long slowSummary(int companyId) (sleep 250 ms) bằng cache. Chạy 100 truy vấn theo phân bố Zipf trên 20 công ty. In hit rate và tổng thời gian có và không có cache.

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

1. Khóa cache bằng std::mutex. 8 luồng cùng get/put 10^5 lần, không lỗi dưới -fsanitize=thread.
2. Chống tính trùng: 10 luồng cùng hỏi 1 khóa chưa có. Chỉ 1 luồng gọi slowSummary, 9 luồng còn lại chờ kết quả. Dùng std::shared_future. Kiểm tra số lần gọi slowSummary bằng 1.

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

• Test mẫu pass. Test ngẫu nhiên so với bản LRU chậm dùng vector.
• TTL test bằng đồng hồ giả, không dùng sleep.
• Bài 3 không có data race, và slowSummary chỉ chạy 1 lần.
• Giải thích được vì sao cần cả hash map lẫn danh sách đôi.

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

• Cache ghi nhớ kết quả giúp gì?
• Hạn dùng tươi mới xử lý sao?
• Cờ đang tải chống tính trùng thế nào?
• LRU chọn nạn nhân nào để đuổi?

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