Thiết kế typeahead autocomplete (search khi gõ)

Search-as-you-type là case study nơi cấu trúc dữ liệu quan trọng: chọn sai cho latency 500 ms, chọn đúng cho 20 ms. Chương này cho hai cài đặt thực dụng - sorted set Redis và service trie tuỳ - và cấu hình .NET cộng pipeline làm mới giữ ranking gần.

Khi nào typeahead cần thiết kế riêng?

Ba tín hiệu.

Latency phải dưới 100 ms. Chậm hơn user gõ vượt gợi ý. Tầng cache bắt buộc; database một mình không đạt latency đó ở scale.

Vocabulary đổi. Tên sản phẩm mới, search trending, thành phố mới đăng - data không tĩnh. Cần pipeline update ranking, không phải build index một lần.

Nhiều term, nhiều prefix. Search xuyên triệu term với triệu prefix. Query 'WHERE name LIKE @prefix%' ngây thơ sập; cấu trúc dữ liệu chuyên biệt có giá trị.

Nếu có vài trăm term tĩnh (danh sách quốc gia, dropdown ngôn ngữ), filter phía client là đúng.

Số nào nên ngân sách?

Search / ngày               50M
Avg keystroke / search      7
Tổng query prefix           50M * 7 = 350M / ngày
Sau debounce client         350M / 7 = 50M (một mỗi pause)
Đỉnh QPS                    50M / 100K * 5 = 2,500
Budget latency              < 100 ms p99 đầu cuối
Kích thước vocabulary       1M term unique
Avg bucket prefix           top 10 completion

Không có debounce client, QPS gấp 7x; debounce là tối ưu phía server lớn nhất. 1M vocabulary vừa thoải mái Redis - sorted set với TTL giữ mới, kèm rate limit bảo vệ endpoint khỏi abuse.

Kiến trúc trông thế nào?

flowchart LR
    Client[Browser] -->|debounce 200ms| App[ASP.NET Core]
    App -->|ZRANGE prefix| Redis[(Redis<br/>sorted set)]
    App --> Result[top K completion]
    SearchLog[Click search] --> Stream[(Kafka / queue event)]
    Stream --> Agg[Aggregator]
    Agg -->|update score| Redis
    Reload[Batch đêm] -->|rebuild đầy đủ| Redis

Đường query là một call Redis. Đường tươi là aggregator streaming update score. Job batch đêm rebuild từ đầu để phục hồi mọi drift.

Cấu hình .NET 10 với sorted set Redis?

Lúc index:

public class AutocompleteIndexer(IConnectionMultiplexer redis)
{
    public async Task IndexTermAsync(string term, double popularity)
    {
        var db = redis.GetDatabase();
        var lower = term.ToLowerInvariant();
        // Mỗi prefix từ độ dài 2 đến len(term), thêm term vào sorted set.
        for (var len = 2; len <= lower.Length; len++)
        {
            var prefix = lower.Substring(0, len);
            await db.SortedSetAddAsync($"ac:{prefix}", term, popularity);
        }
    }
}

Lúc query:

app.MapGet("/autocomplete", async (string q, IConnectionMultiplexer redis) =>
{
    if (string.IsNullOrWhiteSpace(q) || q.Length < 2) return Results.Ok(Array.Empty<string>());
    var db = redis.GetDatabase();
    var key = $"ac:{q.ToLowerInvariant()}";
    var top = await db.SortedSetRangeByRankAsync(key, 0, 9, Order.Descending);
    return Results.Ok(top.Select(v => v.ToString()).ToArray());
})
.RequireRateLimiting("autocomplete");

Ba chi tiết. Fanout prefix lúc index nhân storage theo độ dài term trung bình (~10x). Cho triệu term, đó là ~10M entry sorted set - rẻ trên Redis. Query là một ZRANGE - dưới mili giây. Rate limit thiết yếu vì endpoint autocomplete dễ lạm dụng.

Pipeline tươi giữ ranking gần ra sao?

flowchart LR
    SearchEvent --> K[(Kafka)]
    K --> Counter[Worker đếm]
    Counter --> Window[(Đếm 7d sliding)]
    Window --> Updater[Updater score]
    Updater -->|ZADD hoặc ZINCRBY| Redis
    Reload[Job đêm] --> Redis

Event search stream qua Kafka. Aggregator cửa sổ tính count 7 ngày mỗi term. Updater push score mới sang Redis qua ZADD (ghi đè) hoặc ZINCRBY (tăng dần). Job đêm là phương án an toàn rebuild toàn bộ index từ log; ngay cả mọi worker streaming vỡ, autocomplete đuổi kịp trong 24 giờ.

Đường scale-out hỗ trợ?

• Redis: cluster, shard sorted set theo hash prefix; một prefix vừa một shard nên không có query xuyên shard.
• Tier app: stateless, scale ngang; mỗi query là một call Redis nên điểm nghẽn là CPU Redis, không phải app.
• Pipeline streaming: partition Kafka + Flink/Spark hoặc worker .NET tuỳ; partition theo hash term.
• Storage term lạnh: Postgres cho danh sách chính; Redis cho prefix nóng thôi.

Cho vocabulary rất lớn (>10M term), service trie tuỳ trong .NET (server giữ trie trong memory) cắt memory Redis đáng kể.

Tạo failure mode nào?

• Ranking cũ - pipeline streaming hỏng; ranking lỗi thời. Phòng: rebuild batch đêm làm phương án an toàn; alert lag aggregator.
• Prefix nóng - "a" trả 10K kết quả xuyên user; một CPU Redis quá tải. Phòng: cache prefix nóng trong IMemoryCache mỗi instance app vài giây.
• Prefix lạnh user đầu - sản phẩm mới ra, prefix không có data. Phòng: fallback query Elasticsearch nếu Redis trả rỗng; populate Redis khi miss.
• Tục tĩu trong gợi ý - query user thành gợi ý cho người khác. Phòng: blocklist lọc lúc index và lúc query.

Khi nào autocomplete quá liều?

Khi input từ tập cố định nhỏ (tên bang, mã ngôn ngữ) - load phía client và filter ở đó. Khi backend search đã trả top-10 dưới 50 ms (index nhỏ), gọi trực tiếp. Service autocomplete chuyên là cho ca search engine quá chậm hay quá đắt để gọi mỗi phím.

Đi tiếp đâu từ đây?

Case study kế tiếp: hệ thanh toán / checkout - ca idempotency, saga, và reliability đều va. Case study khó nhất trong series.