Capstone: autocomplete cache LRU và Trie nâng cao

Giới thiệu

Bạn nâng gợi ý từ khóa nhanh hơn. Cache giúp câu hỏi lặp trả lời ngay.

Kiến thức cần nhớ

Trie và radix trie

• Trie là cây tiền tố, tìm gợi ý theo từng ký tự.
• Radix trie nén chuỗi chung, tiết kiệm bộ nhớ hơn.
• Ví dụ đời thường: giống mục lục từ điển theo vần.
• Tìm kiếm mỗi từ tốn theo độ dài từ.

LRU và LFU

• LRU đuổi mục lâu chưa dùng nhất.
• LFU đuổi mục ít dùng nhất.
• Ví dụ đời thường: LRU như dọn đồ lâu không đụng, LFU như bỏ đồ ít dùng.
• Chọn LRU khi thói quen mới, LFU khi thói quen ổn định.

Cache và SLO p95

• Cache lưu kết quả cũ để trả lời nhanh.
• Định nghĩa p95: 95% request nhanh hơn ngưỡng này.
• Ví dụ đời thường: p95 như cam kết 95 đơn giao đúng giờ.
• Đo p95 thay vì chỉ đo trung bình.

# cache đơn giản bằng dict
cache = {}  # nơi lưu kết quả cũ
def goi_y(tu):
    if tu in cache:  # đã hỏi rồi
        return cache[tu]  # trả ngay
    kq = ["gợi ý 1"]  # tính mới ở đây
    cache[tu] = kq  # lưu lại
    return kq

Ví dụ

• Input "app" -> output ["apple", "app"] vì cùng tiền tố.
• Hỏi "app" lần hai trả ngay từ cache.

💻 Bài tập

Ngôn ngữ: C++17 (hoặc ngôn ngữ app ngày 126). Gom code ngày 35, 36, 39, 66, 126. Nộp vào day-152-capstone/.

Bài 1: So Trie và Radix trie

Cùng từ điển 300.000 từ có tần suất:

cấu_trúc     số_nút    bộ_nhớ(MB)   nạp(ms)   suggest_p50(µs)   suggest_p95(µs)
Trie         ...
RadixTrie    ...
sorted vector + lower_bound ...

Autocomplete dùng được với cả 3 qua 1 interface PrefixIndex.

Bài 2: So LRU và LFU trước autocomplete

Sinh 3 luồng truy vấn 10^6 tiền tố: Zipf ổn định, Zipf đổi chủ đề mỗi 10^5, và luồng thật (log gõ phím nếu có, hoặc tách từ bài báo thành các tiền tố gõ dần).

1. Cache 1024 mục. In hit rate và p95 cho LRU, LFU có aging, và không cache.
2. Chọn chính sách mặc định và ghi lý do.

Bài 3: Dịch vụ hoàn chỉnh (nâng cao)

1. HTTP server GET /suggest?q=...&k=... trả JSON. POST /select ghi nhận lựa chọn.
2. Test tải bằng wrk hoặc hey: 2000 request/giây, 60 giây. In p50, p95, p99, lỗi.
3. Mục tiêu p95 dưới 2 ms. Nếu chưa đạt, profile bằng perf (hoặc py-spy) và sửa điểm nóng nhất. Ghi lại trước và sau.
4. REPORT.md: bảng Bài 1, 2, 3, ảnh flame graph, quyết định thiết kế.

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

• Bảng Trie vs Radix vs vector có số thật.
• Bảng cache 3 luồng x 3 cấu hình.
• Test tải có p95, có flame graph.
• Mỗi quyết định thiết kế gắn với số liệu.

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

1. Trie tìm theo đơn vị nào?
2. LRU khác LFU ở điểm nào?
3. p95 nghĩa là gì?
4. Khi nào cache gây sai?

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