App: hệ thống cache LRU, LFU và locks

Giới thiệu

Bài này xây kho nhớ tạm cho app nhanh. Trúng cache trả vài ms, trượt phải chờ DB 50ms.

Kiến thức cần nhớ

LRU và LFU đuổi gì

• LRU đuổi món ít dùng gần đây nhất.
• LFU đuổi món ít dùng nhất theo tần suất có aging.
• Gu ổn định thì LFU thắng, gu trượt nhanh thì LRU thắng.
• Ví dụ đời thường: dọn tủ lạnh bỏ món lâu không ăn hoặc ít ăn.

TTL và refresh nền

• TTL là hạn tươi của mỗi entry, quá hạn thành cũ.
• Stale-while-revalidate trả cũ ngay đồng thời refresh nền.
• Async load giúp reader không bị chặn khi tải lại.
• Nhờ đó p99 không vọt mỗi lần key hot hết hạn.

Singleflight chống dogpile

• Dogpile là chục request cùng miss 1 key đổ xuống DB.
• Singleflight gom waiter, chỉ 1 request xuống DB thật.
• 9 người còn lại chờ ké kết quả rồi cùng về.
• Khóa theo key để đúng mà không khóa cả cache.

Ví dụ

• Input: 50 luồng cùng miss 1 key hết hạn. Output: DB chỉ bị gọi đúng 1 lần.
• Giải thích: singleflight gom 50 waiter thành 1 lượt tải duy nhất.
• Input: tải Zipf gu ổn định. Output: LFU hit-rate hơn LRU ít nhất 5 điểm.
• Giải thích: tần suất tích lũy bắt đúng hot set ổn định.

💻 Bài tập

Ngôn ngữ: Go hoặc C++17 hoặc Python (asyncio). Dùng code ngày 39, 66. Nộp vào day-144-cache/.

Bài 1: Thư viện cache

Cache(capacity, policy = LRU | LFU, default_ttl)
  get(key) -> (value, found)
  set(key, value, ttl)
  delete(key)
  stats() -> hits, misses, evictions, size

Bài 2: Loader, singleflight và stale-while-revalidate

get_or_load(key, loader, ttl, stale_ttl)

1. Singleflight: 100 goroutine/luồng cùng miss 1 key -> loader chỉ chạy 1 lần. Có test đếm số lần gọi.
2. Stale-while-revalidate: key hết ttl nhưng còn trong stale_ttl -> trả giá trị cũ ngay, tải lại ở nền. Có test bằng đồng hồ giả.
3. loader lỗi -> không lưu lỗi vào cache, trả lỗi cho mọi người đang chờ.

Bài 3: Benchmark trước kho chậm (nâng cao)

Kho giả lập: mỗi lần đọc 20 ms, tối đa 50 truy vấn đồng thời.

1. 10.000 request/giây theo Zipf trên 100.000 key trong 60 giây.
2. So 4 cấu hình: không cache, LRU, LFU, LRU + singleflight + SWR. In hit rate, p50, p99, số truy vấn xuống kho.
3. Kịch bản "key nóng hết hạn": 1 key nhận 30% lưu lượng, TTL 5 giây. Vẽ p99 theo thời gian có và không có SWR.

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

• Test singleflight, SWR, loader lỗi pass.
• Không data race (race detector của Go, TSan, hoặc test đồng thời).
• Bảng benchmark 4 cấu hình có số thật.
• Hình p99 theo thời gian cho kịch bản key nóng.

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

• LRU và LFU mỗi cái đuổi entry nào?
• TTL và stale-while-revalidate giúp gì cho p99?
• Dogpile giết DB lúc nào?
• Singleflight gom request trùng thế nào?

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