Đi tới nội dung chính
System Design Lab
Case Studies

Thiết kế gợi ý tìm kiếm

Gợi ý cách hoàn thành ngay khi người dùng đang gõ — trong khoảng thời gian một phím gõ. Vì sao query database ở mỗi phím gõ thất bại, prefix index tính sẵn trả lời trong vài mili giây ra sao, và debounce cùng cache ở edge giảm tải thế nào.

Trung cấp 5 phút đọc· Cập nhật 2026-11-18

Sau bài này bạn sẽ

  • Ước lượng lưu lượng phím gõ và ngân sách độ trễ.
  • Xây prefix index với top-k gợi ý tính sẵn.
  • Cập nhật gợi ý từ log tìm kiếm mà không làm chậm lượt đọc.
  • Giảm tải bằng debounce, cache phía client và ở edge.

Nên đọc trước

Yêu cầu

  • Chức năng: khi người dùng gõ, hiển thị 5–10 gợi ý hàng đầu cho prefix hiện tại, xếp theo độ phổ biến (có thể cá nhân hoá và theo khu vực).
  • Phi chức năng: gợi ý tới trong khoảng ~100 ms từ đầu tới cuối để theo kịp tốc độ gõ; chấp nhận cũ đi vài phút hay vài giờ.
  • Quy mô: mỗi phím gõ của mỗi người dùng đều có thể là một request.

Ước lượng nhanh

Đại lượngGiả địnhKết quả
Lượt tìm kiếm50 triệu mỗi ngày, ~20 ký tự mỗi lượt~1 tỉ phím gõ/ngày ≈ 12.000/giây (cao điểm ×3)
Có debounceMỗi lần dừng gõ một request (~4 mỗi lượt tìm)~2.300/giây
Kích thước index10 triệu query phổ biến, top-10 mỗi prefixVài chục GB — vừa trong bộ nhớ của vài node

Tiến hoá thiết kế

Giai đoạn 1 / 3

Query database ở mỗi phím gõ

Kiến trúc hiện tại
Mỗi phím gõ chạy WHERE name LIKE 'pre%' ORDER BY popularity LIMIT 10.
Giới hạn
Mỗi query phải sắp xếp rất nhiều dòng khớp; lưu lượng phím gõ thì khổng lồ.
Điểm nghẽn
Connection database: một nửa request lỗi, phần còn lại tới quá muộn để còn hữu ích.
Cải tiến
Tính sẵn câu trả lời cho mọi prefix.
Tác động tới hiệu năng
~50% lỗi, p50 ≈ 430 ms.
Độ phức tạp & chi phí vận hành
Không thêm thành phần nào.
Trade-off
Luôn mới, nhưng vô dụng ở tốc độ gõ.
Đang tải mô phỏng…

Dựng index

  1. Gom log tìm kiếm (query, thời điểm, khu vực) vào một stream hoặc data warehouse.
  2. Tổng hợp số lần theo từng query trong một cửa sổ trượt (ví dụ 7 ngày gần nhất, có suy giảm) — một job batch hoặc pipes and filters.
  3. Với mọi prefix của mọi query phổ biến, giữ top-k query theo điểm.
  4. Publish một phiên bản index mới, bất biến; server gợi ý nạp nó và chuyển sang một cách atomic.
Client: debounce và huỷ request đã lỗi thời
let timer: ReturnType<typeof setTimeout> | undefined;
let inflight: AbortController | undefined;

input.addEventListener('input', () => {
  clearTimeout(timer);
  timer = setTimeout(async () => {
    inflight?.abort();                                   // người dùng gõ tiếp: bỏ câu trả lời cũ
    inflight = new AbortController();
    const prefix = input.value.trim().toLowerCase();
    if (prefix.length < 2) return;
    const res = await fetch(`/suggest?q=${encodeURIComponent(prefix)}`, { signal: inflight.signal });
    render(await res.json());
  }, 150);
});

Đánh đổi

ĐượcMất
Index tính sẵnTra cứu tính bằng mili giây bất kể dữ liệu lớn cỡ nào.Gợi ý đi sau xu hướng cho tới lần dựng tiếp theo.
Cache ở edgePrefix phổ biến được trả lời ngay cạnh người dùng.Chỉ dùng được cho response không cá nhân hoá.
DebounceGiảm request nhiều lần.Thêm một chút độ trễ trước gợi ý đầu tiên.

Checklist khi phỏng vấn

  • Ước lượng QPS của phím gõ và ngân sách độ trễ trước tiên.
  • Giải thích cấu trúc trie / prefix → top-k và cách dựng nó offline.
  • Giảm lưu lượng: debounce, độ dài prefix tối thiểu, cache ở client và CDN.
  • Nhắc tới lọc gợi ý phản cảm, bản địa hoá và query đang thịnh hành.

Đọc thêm

Bài liên quan