Case-Design-Search-Autocomplete

Case Study: Design Search Autocomplete System — Full System Design Interview Walkthrough

“Mỗi lần bạn gõ một chữ trên Google, hệ thống phải quét hàng tỷ query trong vòng dưới 100ms để đưa ra 10 gợi ý chính xác nhất. Đó không phải magic — đó là engineering.”

Tags: system-design case-study search-autocomplete trie alex-xu interview Student: Hieu Source: Alex Xu — System Design Interview, Volume 1, Chapter 13 Prerequisite: Tuan-01-Scale-From-Zero-To-Millions · Tuan-02-Back-of-the-envelope Lien quan: Tuan-06-Cache-Strategy · Tuan-08-Message-Queue · Tuan-10-Consistent-Hashing

---

1. Context & Why — Tại sao Autocomplete quan trọng?

1.1 The Everyday Analogy

Bạn hãy mở Google Search ra. Gõ “system d” — lập tức xuất hiện một dropdown với 10 gợi ý: “system design interview”, “system design primer”, “system design alex xu”… Tất cả diễn ra trong dưới 100ms — nhanh hơn cả một cái chớp mắt (300-400ms).

Không chỉ Google. Mọi search bar bạn gặp hàng ngày đều có autocomplete:

• YouTube — gợi ý video khi gõ tìm kiếm
• Amazon — gợi ý sản phẩm khi gõ tên
• Spotify — gợi ý bài hát, nghệ sĩ
• IDE (VS Code, IntelliJ) — code completion cũng là một dạng autocomplete
• LinkedIn — gợi ý người, công ty khi search

1.2 Tại sao đây là bài toán khó?

Thách thức	Giải thích
Latency cực thấp	User kỳ vọng response < 100ms. Nếu chậm hơn, cảm giác “lag” sẽ khiến user bỏ đi
Scale khổng lồ	Google xử lý ~8.5 billion searches/day. Mỗi search có ~20 keystroke → 170 billion autocomplete requests/day
Relevance	Gợi ý phải có nghĩa — không phải random prefix match, mà phải sort theo popularity, freshness, personalization
Real-time feeling	Dù backend có thể delay, frontend phải tạo cảm giác “instant” qua debounce + caching
Multi-language	Tiếng Việt, tiếng Nhật, tiếng Trung — mỗi ngôn ngữ có cách tokenize khác nhau
Safety	Không được gợi ý nội dung offensive, bạo lực, khiêu dâm

1.3 Business Impact

Autocomplete không chỉ là tiện ích — nó là vũ khí kinh doanh:

• Giảm thời gian search — User gõ 2-3 ký tự thay vì cả câu. Google ước tính autocomplete tiết kiệm 200 năm thời gian gõ mỗi ngày (toàn cầu)
• Tăng conversion — Amazon cho thấy autocomplete tốt tăng click-through rate lên 24%
• Guided discovery — Hướng user đến các query phổ biến, gián tiếp điều khiển traffic
• Giảm lỗi chính tả — User chọn gợi ý thay vì tự gõ, giảm typo

Aha Moment: Autocomplete không chỉ “giúp user gõ nhanh hơn”. Nó là một công cụ định hướng hành vi người dùng — ai kiểm soát autocomplete, người đó ảnh hưởng đến những gì hàng triệu người tìm kiếm.

---

2. Deep Dive — Alex Xu 4-Step Framework

Overview — Bốn bước của Alex Xu

Bước	Tên gọi	Thời gian (45 phút)
1	Understand the Problem & Establish Design Scope	~5 phút
2	Propose High-Level Design	~15 phút
3	Design Deep Dive	~20 phút
4	Wrap Up	~5 phút

---

Step 1 — Understand the Problem & Establish Design Scope

1.1 Functional Requirements (Yêu cầu chức năng)

trước khi thiết kế, bạn phải hỏi interviewer để làm rõ scope. Đây là các câu hỏi và giả định:

Câu hỏi	Trả lời / Giả định
Autocomplete chỉ match từ đầu (prefix) hay bất kỳ vị trí?	Chỉ prefix match. “sys” → “system design” nhưng “stem” KHÔNG match
Trả về bao nhiêu gợi ý?	10 suggestions mỗi request
Gợi ý dựa trên tiêu chí gì?	Popularity (tần suất query) là primary signal
Có hỗ trợ multi-language không?	Có — tiếng Anh, tiếng Việt, tiếng Nhật, v.v.
Có capitalize/lowercase distinction không?	Không — tất cả query được normalize về lowercase
User phải đăng nhập mới có autocomplete?	Không — hoạt động cho cả anonymous user
Có personalization không?	Phase 1: không. Phase 2: có thể dựa vào search history cá nhân

Tóm tắt Functional Requirements:

1. Prefix matching — Khi user gõ “din”, trả về các query bắt đầu bằng “din” (ví dụ: “dinner recipes”, “dinosaur”, “dining table”)
2. Top 10 suggestions — Sort theo popularity (query frequency), trả về 10 kết quả hàng đầu
3. Multi-language — Hỗ trợ Unicode, xử lý được tiếng Việt (có dấu), tiếng Nhật (Kanji + Hiragana), tiếng Trung
4. Near real-time update — Query mới (trending) cần xuất hiện trong gợi ý sau một khoảng thời gian hợp lý (không cần instant)

1.2 Non-Functional Requirements (Yêu cầu phi chức năng)

Requirement	Target	Giải thích
Low Latency	Response < 100ms (P99)	Autocomplete phải nhanh hơn tốc độ gõ của user. Nếu user gõ 5 ký tự/giây (200ms/keystroke), response phải đến trước keystroke tiếp theo
High Availability	99.99% uptime	Autocomplete down = search bar cảm thấy “chết”, dù search vẫn hoạt động
Scalability	10M+ DAU, 20B+ requests/day	Scale ngang khi traffic tăng
Fault Tolerance	Graceful degradation	Nếu autocomplete chết, search vẫn hoạt động bình thường — chỉ mất gợi ý
Consistency	Eventual consistency OK	Không cần strong consistency — việc gợi ý cũ hơn vài phút là chấp nhận được
Relevance	Top suggestions phải có ý nghĩa	Không gợi ý random, phải sort đúng theo popularity

Pitfall: Nhiều ứng viên quên hỏi về graceful degradation. Autocomplete là non-critical feature — nếu nó chết, search PHẢI vẫn hoạt động. Đây là điều interviewer muốn nghe.

1.3 Quy mô hệ thống (Scale)

Thông số	Giá trị	Giải thích
DAU (Daily Active Users)	10 million	Quy mô trung bình (nhỏ hơn Google, lớn hơn startup)
Searches per user per day	10	Trung bình
Average words per query	4 words	”best italian restaurant nyc”
Average chars per word	5 characters	Tiếng Anh trung bình
Characters per query	20 characters	4 words x 5 chars
Autocomplete requests per query	20	Mỗi keystroke gửi 1 request (trước khi optimize)

---

Step 2 — Propose High-Level Design

2.1 Hai thành phần chính

hệ thống autocomplete có 2 phần lớn, hoạt động độc lập nhưng bổ sung cho nhau:

Thành phần	Chức năng	Tính chất
Data Gathering Service	Thu thập query từ user, aggregate frequency, xây dựng Trie	Offline / Near-realtime, write-heavy
Query Service	Nhận prefix từ user, lookup Trie, trả về top K suggestions	Online, read-heavy, latency-critical

Aha Moment: Đây là pattern CQRS (Command Query Responsibility Segregation) — tách riêng write path (data gathering) và read path (query service). Bạn đã gặp pattern này ở Tuan-11-Microservices-Pattern.

2.2 Data Gathering Service — Tổng quan

Luồng hoạt động:

1. User gõ query và nhấn Enter (hoàn thành search)
2. Query được log vào Analytics Log (raw log)
3. Định kỳ (mỗi giờ/ngày/tuần), Aggregation Pipeline đọc raw log, đếm tần suất mỗi query
4. Trie Builder lấy data aggregated, xây dựng/cập nhật Trie
5. Trie mới được push lên Trie Storage (persistent) và Trie Cache (in-memory)

2.3 Query Service — Tổng quan

Luồng hoạt động:

1. User gõ ký tự trong search box
2. Frontend gửi AJAX request với prefix hiện tại (vd: “sys”)
3. Request đến API Gateway → Query Service
4. Query Service lookup prefix trong Trie Cache (in-memory)
5. Trả về top 10 suggestions
6. Frontend hiển thị dropdown

2.4 High-Level Architecture Diagram

graph TB
    subgraph "User Layer"
        U[User Browser/App]
    end

    subgraph "Online Path — Query Service"
        AG[API Gateway<br/>Rate Limiter + Auth]
        QS[Query Service<br/>Stateless]
        TC[Trie Cache<br/>In-Memory<br/>Redis / Local Memory]
    end

    subgraph "Offline Path — Data Gathering"
        AL[Analytics Log<br/>Raw Search Queries]
        AP[Aggregation Pipeline<br/>MapReduce / Spark]
        AF[Aggregated Frequency<br/>DB / File Storage]
        TB[Trie Builder<br/>Xay dung Trie tu frequency data]
        TS[Trie Storage<br/>Persistent — S3 / HDFS]
    end

    subgraph "Filter & Safety"
        FL[Filter Layer<br/>Remove offensive content]
    end

    U -->|"AJAX: prefix='sys'"| AG
    AG --> QS
    QS --> TC
    TC -->|"Cache miss"| TS
    QS --> FL
    FL -->|"Filtered top 10"| AG
    AG -->|"JSON response"| U

    U -->|"Completed search query"| AL
    AL --> AP
    AP --> AF
    AF --> TB
    TB --> TS
    TB -->|"Push new Trie"| TC

    style TC fill:#e1f5fe
    style FL fill:#fff3e0
    style AP fill:#f3e5f5

Note: Chú ý là 2 path (online và offline) chỉ chia sẻ Trie — không có dependency trực tiếp nào khác. Điều này giúp bạn scale từng phần độc lập.

---

Step 3 — Design Deep Dive

Đây là phần quan trọng nhất của buổi phỏng vấn — nơi bạn thể hiện chiều sâu kỹ thuật.

3.1 Trie Data Structure — Cơ bản

Trie là gì?

Trie (đọc là “try”, từ chữ “reTRIEval”) là một cấu trúc dữ liệu dạng cây, được thiết kế đặc biệt cho prefix search. Mỗi node đại diện cho một ký tự, và đường đi từ root đến một node tạo thành một prefix.

Đặc điểm chính của Trie:

Đặc điểm	Giải thích
Root	Node gốc, không chứa ký tự nào
Node	Mỗi node chứa 1 ký tự và pointer đến các child node
Path	Đường từ root đến một node = một prefix
Terminal node	Node đánh dấu kết thúc một từ/query hoàn chỉnh
Branching	Mỗi node có thể có tối đa 26 child (tiếng Anh) hoặc nhiều hơn (Unicode)

Ví dụ trực quan

Giả sử bạn có 3 query: “tree”, “try”, “true” với frequency tương ứng.

graph TD
    ROOT["Root"]
    T["t"]
    R["r"]
    E1["e (tree: 35)"]
    Y["y (try: 20)"]
    U["u"]
    E2["e (true: 15)"]
    RE["r"]
    EE["e"]

    ROOT --> T
    T --> R
    R --> E1
    R --> Y
    R --> U
    E1 --> EE["e (tree: 35)"]
    U --> E2

    style E1 fill:#c8e6c9
    style Y fill:#c8e6c9
    style E2 fill:#c8e6c9

Time Complexity của Trie

Operation	Complexity	Giải thích
Insert a query	O(L)	L = độ dài query. Duyệt từng ký tự, tạo node nếu chưa có
Search exact query	O(L)	Duyệt từng ký tự từ root
Find all queries with prefix	O(L + N)	L = độ dài prefix, N = số node trong subtree. Đây là vấn đề!

Pitfall: Tìm tất cả query có prefix “a” nghĩa là duyệt toàn bộ subtree bắt đầu từ node “a”. Nếu subtree có hàng triệu node → cực chậm. Đây là lý do bạn cần optimize Trie.

3.2 Optimized Trie — Bí quyết của autocomplete nhanh

Optimization 1: Lưu top K tại mỗi node

Vấn đề: Với Trie cơ bản, để tìm top 10 suggestions cho prefix “be”:

1. Tìm node “b” → “e” (O(prefix length) = nhanh)
2. Duyệt toàn bộ subtree từ “be” → thu thập tất cả terminal node
3. Sort theo frequency → lấy top 10

Bước 2 là bottleneck — subtree có thể có hàng triệu node.

Giải pháp: Lưu sẵn top K queries tại mỗi node trong Trie.

Approach	Tìm top 10 cho prefix “be”	Time
Basic Trie	Duyệt toàn bộ subtree + sort	O(subtree size) — có thể hàng triệu
Optimized Trie	Đọc trực tiếp top 10 tại node “be”	O(1) — constant time!

Trade-off:

• Space tăng: Mỗi node lưu thêm K entries (vd: 10 strings + frequency). Nếu Trie có 1 triệu node → lưu thêm 10 triệu entries
• Update phức tạp hơn: Khi frequency thay đổi, phải cập nhật top K tại nhiều node (từ leaf lên root)
• Nhưng latency giảm cực mạnh: Từ O(millions) xuống O(1)

Aha Moment: Đây là classic space-time trade-off. Trong autocomplete, latency là vua — bạn sẵn sàng đổi space để có speed. Interviewer sẽ ấn tượng nếu bạn nói rõ trade-off này.

Optimization 2: Giới hạn độ sâu prefix (Prefix depth limit)

Vấn đề: Một query có thể dài tới 50+ ký tự. Trie sâu 50 level là lãng phí vì:

• Ít user nào gõ quá 10-15 ký tự trước khi chọn gợi ý
• Càng gõ nhiều ký tự, số lượng match càng ít → autocomplete càng ít hữu ích

Giải pháp: Giới hạn độ sâu của Trie, ví dụ chỉ lưu prefix tối đa 50 ký tự.

Prefix length	Số lượng matches	Autocomplete hữu ích?
1-3 ký tự	Hàng triệu	Rất hữu ích — user đang explore
4-7 ký tự	Hàng nghìn	Hữu ích — user đang narrow down
8-15 ký tự	Hàng trăm	Vẫn hữu ích
15+ ký tự	Vài chục hoặc ít hơn	Ít hữu ích — user đã biết muốn gì
50+ ký tự	Gần như 0	Vô nghĩa

Aha Moment: Google chỉ hiện autocomplete cho khoảng 30 ký tự đầu tiên. Sau đó, dropdown biến mất. Đây không phải bug — đây là optimization có chủ ý.

Optimization 3: Node compression (Trie nén)

Nếu một chuỗi node chỉ có 1 child (không branch), gộp chúng thành 1 node:

Trước khi nén: r → o → m → a → n → c → e (7 nodes) Sau khi nén: “romance” (1 node)

Lợi ích:

• Giảm số lượng node (thường giảm 50-70%)
• Giảm memory footprint
• Giảm số lần pointer dereference khi traverse

3.3 Trie Update Strategy — Offline Rebuild vs Incremental

Tại sao KHÔNG update Trie real-time?

Lý do	Giải thích
Write amplification	Mỗi query mới → cập nhật frequency + top K tại nhiều node (từ leaf lên root). Với 100K QPS, quá nhiều writes
Consistency phức tạp	Nhiều server đọc Trie cùng lúc. Nếu update giữa chừng → inconsistent state
Latency spike	Write lock có thể block read, gây latency spike cho autocomplete
Không cần real-time	Autocomplete suggestions không cần chính xác từng giây. Delay 15 phút - 1 giờ là chấp nhận được

Strategy 1: Offline Rebuild (Recommended cho hầu hết trường hợp)

Cách hoạt động:

1. Định kỳ (mỗi 1 giờ / mỗi ngày), Aggregation Pipeline đếm frequency của tất cả query
2. Trie Builder xây Trie mới hoàn toàn từ aggregated data
3. Trie mới được serialize và lưu vào Trie Storage
4. Query Service servers tải Trie mới (hot swap — không downtime)

Ưu điểm:

• Đơn giản, dễ implement, dễ debug
• Không có race condition
• Trie luôn ở trạng thái consistent
• Dễ rollback — chỉ cần quay về Trie version cũ

Nhược điểm:

• Trending query mất thời gian để xuất hiện (delay = rebuild interval)
• Rebuild Trie lớn tốn nhiều compute resource

Strategy 2: Incremental Update (Cho hệ thống cần nhanh hơn)

Cách hoạt động:

1. Khi có query mới, gửi event vào Message Queue (Tuan-08-Message-Queue)
2. Trie Updater consumer đọc event, cập nhật frequency tại node tương ứng
3. Recalculate top K tại các node bị ảnh hưởng (từ leaf lên root)

Ưu điểm:

• Trending query xuất hiện nhanh hơn (delay = processing time, thường vài phút)
• Không cần rebuild toàn bộ Trie

Nhược điểm:

• Phức tạp hơn nhiều: phải xử lý concurrency, locking, versioning
• Risk: cập nhật sai có thể corrupt Trie
• Cần careful engineering để không ảnh hưởng read performance

Hybrid Approach (Thực tế)

Hầu hết các hệ thống lớn dùng hybrid:

• Baseline Trie: Rebuild offline mỗi ngày từ historical data
• Delta Trie: Incremental update mỗi 15 phút từ trending data
• Merge: Khi query, merge kết quả từ cả 2 Trie

Aha Moment: YouTube dùng hybrid approach — gợi ý cơ bản từ offline Trie, nhưng trending video/topic được inject từ realtime pipeline. Đó là lý do bạn thấy trending video xuất hiện trong autocomplete chỉ vài phút sau khi viral.

3.4 Data Gathering Pipeline — Chi tiết

Toàn bộ luồng dữ liệu từ raw log đến Trie

graph LR
    subgraph "Step 1: Collection"
        SB[Search Box<br/>User go query]
        QL[Query Logger<br/>Append to log file]
        KF[Message Queue<br/>Kafka / Kinesis]
    end

    subgraph "Step 2: Storage"
        S3[Raw Log Storage<br/>S3 / HDFS]
    end

    subgraph "Step 3: Aggregation"
        SP[Aggregation Engine<br/>Spark / Flink / MapReduce]
        FT[Frequency Table<br/>query → count per time window]
    end

    subgraph "Step 4: Trie Build"
        TBU[Trie Builder<br/>Xay dung Trie tu frequency]
        SER[Trie Serializer<br/>Convert Trie → binary format]
    end

    subgraph "Step 5: Distribution"
        TST[Trie Storage<br/>S3 / GCS]
        TCA[Trie Cache<br/>Redis / In-memory]
        QSE[Query Servers<br/>Load Trie vao RAM]
    end

    SB --> QL
    QL --> KF
    KF --> S3
    S3 --> SP
    SP --> FT
    FT --> TBU
    TBU --> SER
    SER --> TST
    TST --> TCA
    TST --> QSE

    style KF fill:#e8eaf6
    style SP fill:#f3e5f5
    style TCA fill:#e1f5fe

Step-by-step giải thích

Step 1 — Collection (Thu thập):

• Mỗi khi user hoàn thành một search (nhấn Enter hoặc click gợi ý), query được log
• Quan trọng: Chỉ log query đã hoàn thành, KHÔNG log mỗi keystroke. Lý do:
  • Keystroke log quá nhiều (20x nhiều hơn completed query)
  • Keystroke là “partial query” — không đại diện cho ý định thực sự của user
  • Ví dụ: user gõ “sys” → “syst” → “system” → “system design” → Enter. Chỉ log “system design”
• Log format: timestamp | user_id_hash | query | country | language
• Dùng Message Queue (Kafka) làm buffer để tránh mất log khi traffic spike

Step 2 — Storage (Lưu trữ):

• Raw log được lưu vào distributed storage (S3, HDFS)
• Partition theo ngày và giờ để dễ truy vấn
• Retention policy: giữ raw log 30 ngày, sau đó archive hoặc xóa
• Dữ liệu này cũng được dùng cho analytics khác (search quality, trending topics)

Step 3 — Aggregation (Tổng hợp):

• Đây là bước nặng nhất về compute
• Dùng framework như Apache Spark, Flink, hoặc MapReduce
• Input: raw log files
• Output: bảng tần suất — mỗi dòng là (query, time_window, count)
• Time window thường là 1 giờ hoặc 1 ngày
• Weighted aggregation: Query gần đây hơn được trọng số cao hơn

$$weighted\_frequency(q)=\sum _{i=1}^{N}coun{t}_i\times decay\_facto{r}^{(now-t_i)}$$

Với $decay\_factor$ thường là 0.9-0.99, và $t_i$ là thời điểm của time window $i$.

Giải thích: Decay factor đảm bảo query “World Cup 2026” có weight cao trong mùa World Cup, nhưng giảm dần sau đó. Không có decay, những query cũ nhưng phổ biến (ví dụ “Facebook login”) sẽ luôn áp đảo trending query.

Step 4 — Trie Build (Xây dựng Trie):

• Đọc frequency table, xây dựng Trie từ scratch
• Tại mỗi node, tính và lưu top K queries (thường K = 10-25)
• Apply compression (gộp các node chỉ có 1 child)
• Serialize Trie thành binary format để lưu trữ và truyền tải hiệu quả

Step 5 — Distribution (Phân phối):

• Trie đã serialize được upload lên Trie Storage (S3)
• Query servers tải Trie mới từ S3 → load vào RAM
• Có thể dùng Trie Cache (Redis) làm intermediate layer cho các server chưa kịp load Trie mới
• Blue-green deployment: Giữ 2 version Trie. Server đang dùng version A. Load version B vào RAM. Switch traffic sang B. Nếu có lỗi, switch lại A

3.5 Query Service — Chi tiết

Luồng xử lý một autocomplete request

sequenceDiagram
    participant User as User Browser
    participant FE as Frontend JS
    participant CDN as CDN/Edge Cache
    participant AG as API Gateway
    participant QS as Query Service
    participant TC as Trie Cache (Memory)
    participant FL as Filter Layer

    User->>FE: Go ky tu "sys"
    Note over FE: Debounce 200ms<br/>Cho user go them
    User->>FE: Go them "t" → "syst"
    Note over FE: Debounce 200ms
    Note over FE: 200ms het — gui request
    FE->>CDN: GET /autocomplete?q=syst

    alt Cache HIT tai CDN
        CDN-->>FE: Return cached suggestions
    else Cache MISS
        CDN->>AG: Forward request
        AG->>QS: Lookup prefix "syst"
        QS->>TC: Trie.search("syst")
        TC-->>QS: Top 10 raw suggestions
        QS->>FL: Filter offensive content
        FL-->>QS: Filtered top 10
        QS-->>AG: JSON response
        AG-->>CDN: Response + Cache-Control header
        CDN-->>FE: Return suggestions
    end

    FE-->>User: Hien thi dropdown 10 goi y

Frontend Optimizations

Debounce — Kỹ thuật tiết kiệm 80% traffic:

Không có debounce, mỗi keystroke gửi 1 request:

• User gõ “system design” (13 ký tự) → 13 requests
• Nhưng user gõ liên tục — các request cho “s”, “sy”, “sys” đều vô nghĩa vì user chưa dừng lại

Với debounce 200ms:

• Chỉ gửi request khi user ngừng gõ 200ms
• User gõ “system design” liên tục → chỉ gửi 2-3 requests thay vì 13
• Tiết kiệm ~80% traffic

Không có debounce	Có debounce 200ms
”s” → request	”s” → chờ…
“sy” → request	”sy” → chờ…
“sys” → request	”sys” → chờ…
“syst” → request	”syst” → chờ…
“syste” → request	”syste” → gửi request (user ngừng 200ms)
“system” → request	”system” → chờ…
“system ” → request	”system ” → chờ…
“system d” → request	”system d” → chờ…
“system de” → request	”system de” → gửi request
… (13 requests)	… (3-4 requests)

Browser Caching:

• Response cho prefix “sys” ít thay đổi trong 1 giờ
• Set Cache-Control: max-age=3600 (cache 1 giờ tại browser)
• Lần sau user gõ “sys” → browser trả kết quả từ cache, không cần gửi request
• Hiệu quả càng lớn với các prefix ngắn (ít thay đổi hơn prefix dài)

AJAX (Asynchronous):

• Request được gửi asynchronous — không block UI
• Nếu response đến chậm (> 300ms), user đã gõ thêm ký tự → hủy request cũ, gửi request mới
• Tránh hiển thị kết quả “stale” cho prefix cũ

Backend Optimizations

In-Memory Trie:

• Toàn bộ Trie được load vào RAM của Query Server
• Lookup time = O(prefix length) — thường < 1 microsecond
• Không cần truy cập disk hay external database
• Mỗi Query Server giữ bản sao riêng của Trie — không có shared state → dễ scale horizontal

CDN / Edge Caching:

• Autocomplete responses là read-only và thay đổi chậm (mỗi giờ/ngày)
• Cache tại CDN edge server — user ở Việt Nam được serve từ CDN Singapore, không cần request về US
• Cache key: prefix string (vd: “sys”, “syst”, “syste”)
• Hit rate cao cho prefix ngắn (ít variation)

Two-tier Cache Strategy (Tham khảo: Tuan-06-Cache-Strategy):

Tier	Implementation	Latency	Hit Rate
L1: CDN/Browser cache	HTTP cache	~0ms (browser) / ~5ms (CDN)	60-80% cho short prefix
L2: Application cache	In-memory Trie tại Query Server	< 1ms	100% (Trie luôn có trong RAM)

Aha Moment: Với debounce + browser caching + CDN caching, chỉ 10-20% autocomplete requests thực sự đến backend. Đây là lý do hệ thống có thể handle hàng tỷ requests/day với ít server.

3.6 Filter Layer — An toàn nội dung

Tại sao cần filter?

Autocomplete gợi ý công khai — tất cả user đều thấy. Nếu gợi ý chứa nội dung offensive, violent, hay sexually explicit:

• PR disaster — báo chí đưa tin, social media viral (đã xảy ra với Google nhiều lần)
• Legal risk — vi phạm luật bảo vệ trẻ em, luật chống kỳ thị
• User trust — mất lòng tin người dùng

Các loại nội dung cần filter

Loại	Ví dụ	Mức độ
Hate speech	Nội dung phân biệt chủng tộc, giới tính, tôn giáo	Block hoàn toàn
Violence	Hướng dẫn bạo lực, vũ khí	Block hoàn toàn
Adult content	Nội dung khiêu dâm (trừ khi SafeSearch OFF)	Block default, cho phép với setting
Defamation	”[tên người] + từ xúc phạm”	Block dựa trên rule
Self-harm	Nội dung tự gây thương, tự tử	Block + hiển thị hotline hỗ trợ
Illegal activity	Mua bán chất cấm, hack	Block hoàn toàn

Filter implementation

Layer 1 — Blocklist (Offline):

• Danh sách các query/keyword bị cấm, được maintain bởi content moderation team
• Apply khi build Trie — loại bỏ các query trong blocklist trước khi insert vào Trie
• Ưu điểm: nhanh, không ảnh hưởng runtime
• Nhược điểm: không bắt được variation mới (vd: “h4te” thay vì “hate”)

Layer 2 — ML Classification (Near-realtime):

• Model ML phân loại query thành safe/unsafe
• Chạy khi build Trie (offline) hoặc khi filter response (online)
• Bắt được variation, tiếng lóng, encoded text
• Nhược điểm: có false positive (block query vô hại)

Layer 3 — Runtime Filter (Online):

• Trước khi trả suggestions về user, chạy qua filter cuối cùng
• Check against latest blocklist (có thể cập nhật real-time qua config service)
• Đảm bảo không có suggestion nào “lọt lưới” offline filter

3.7 Trie Serialization — Lưu trữ và truyền tải Trie

Tại sao cần serialize?

Trie trong memory là pointer-based structure — mỗi node chứa pointer đến children. Không thể:

• Lưu trực tiếp xuống disk (pointer không có nghĩa khi reload)
• Gửi qua network từ Trie Builder đến Query Server
• Version control (so sánh 2 Trie)

Các cách serialize

Cách 1 — Level-order traversal (BFS):

• Duyệt Trie theo từng level (root → level 1 → level 2 → …)
• Lưu mỗi node dưới dạng: (character, is_terminal, num_children, top_k_list)
• Dễ reconstruct — đọc tuần tự, xây lại Trie

Cách 2 — Key-value pairs:

• Lưu mỗi prefix và top K của nó dưới dạng key-value:
  • Key: “sys” → Value: [“system design:1000”, “system:800”, …]
  • Key: “syst” → Value: [“system design:1000”, “system:800”, …]
• Có thể lưu vào Redis, RocksDB, hay bất kỳ KV store nào
• Lợi ích: không cần reconstruct Trie — chỉ cần KV lookup

Cách 3 — Compact binary format (Recommended):

• Custom binary format, optimized cho size và speed
• Dùng techniques: varint encoding, dictionary compression, delta encoding
• Trie 1GB trong memory có thể giảm xuống 200-300MB khi serialize
• Nhanh nhất khi deserialize vì ít overhead

3.8 Multi-Language Support

Thách thức

Ngôn ngữ	Vấn đề	Ví dụ
Tiếng Việt	Dấu thanh, chữ cái đặc biệt (ă, â, ô, ơ, ư, đ)	“pho” vs “phở” là 2 từ khác nhau
Tiếng Nhật	3 hệ thống chữ: Hiragana, Katakana, Kanji	User có thể gõ “tokyo” bằng Romaji, Hiragana, hoặc Kanji
Tiếng Trung	Không có space giữa các từ, Pinyin input	”bei jing” (Pinyin) → “Beijing”
Tiếng Hàn	Jamo (phụ âm + nguyên âm) kết hợp thành syllable	User gõ từng Jamo, autocomplete phải xử lý từng bước
Tiếng Ả Rập	Right-to-left, ký tự thay đổi hình dạng theo vị trí	Prefix match phức tạp hơn

Giải pháp: Unicode + Separate Tries per Language

Approach 1 — Unicode Trie:

• Dùng Unicode code point làm key cho mỗi node (thay vì chỉ 26 chữ cái ASCII)
• Mỗi node có thể có hàng nghìn children (Unicode có ~150,000 ký tự)
• Dùng hash map thay vì array cho children → tiết kiệm memory
• Ưu điểm: 1 Trie cho tất cả ngôn ngữ
• Nhược điểm: Trie rất lớn, khó shard

Approach 2 — Separate Trie per Language (Recommended):

• Mỗi ngôn ngữ có Trie riêng
• Detect ngôn ngữ từ: (1) user setting, (2) keyboard input, (3) geo-location
• Route request đến Trie tương ứng
• Ưu điểm: mỗi Trie nhỏ hơn, dễ optimize cho từng ngôn ngữ
• Nhược điểm: user bilingual (vd: gõ cả tiếng Anh và tiếng Việt) cần query nhiều Trie

Normalization pipeline (áp dụng cho mỗi ngôn ngữ):

1. Convert về lowercase
2. Remove diacritics cho search (nhưng giữ lại khi hiển thị). Ví dụ: “Phở” → normalize thành “pho” để search, nhưng hiển thị “Phở”
3. Handle synonyms (vd: “tp hcm” = “thanh pho ho chi minh” = “saigon”)
4. Handle transliteration (vd: “tokyo” → Romaji match cho tiếng Nhật)

3.9 Personalization Layer

Overview

Personalization = gợi ý dựa trên lịch sử cá nhân của user, không chỉ global popularity.

Ví dụ: Khi Hieu gõ “py”:

• Global autocomplete: “python download”, “python tutorial”, “pyridoxine”
• Personalized cho Hieu (backend dev): “python asyncio”, “python system design”, “pydantic”

Architecture

Component	Chức năng
User Profile Store	Lưu search history per user (recent queries, click-through)
Personal Trie / Score Adjustment	Adjust score của suggestions dựa trên user profile
Merge Layer	Kết hợp global suggestions + personal suggestions, re-rank

Implementation đơn giản

1. Lưu 50 query gần nhất của mỗi user trong Redis (key: user_id, value: list of recent queries)
2. Khi autocomplete request đến:
   • Lấy top 10 từ global Trie (frequency-based)
   • Lấy queries từ user’s recent history match với prefix
   • Merge: ưu tiên personal match, fill còn lại từ global
3. Nếu user chưa đăng nhập → chỉ dùng global Trie

Privacy note: Personal data phải được lưu cách biệt, có thể xóa theo yêu cầu (GDPR right to erasure). Chi tiết ở Section 4 (Security).

3.10 Scaling — Trie Sharding & Replication

Tại sao cần shard Trie?

Khi hệ thống lớn:

• Trie cho tiếng Anh có thể có hàng tỷ node → không fit vào RAM của 1 server
• Traffic cho prefix “a” có thể gấp 10 lần prefix “x” → hot spot
• Cần phân tán Trie ra nhiều server

Sharding Strategy 1: By First Character

Shard	Prefixes	Những server
Shard 0	a-c	Server 1, 2, 3
Shard 1	d-f	Server 4, 5, 6
Shard 2	g-i	Server 7, 8, 9
…	…	…
Shard 8	y-z + special chars	Server 25, 26, 27

Ưu điểm: Đơn giản, dễ implement Nhược điểm: Không đều tải! Prefix “s” có nhiều query hơn prefix “x” gấp 100 lần → shard “s” bị overload

Sharding Strategy 2: By Prefix Range (Recommended)

Thay vì chia theo 1 ký tự đầu, chia theo range của prefix, đảm bảo mỗi shard có lượng traffic tương đương:

Shard	Prefix Range	Estimated Traffic
Shard 0	”a” — “be”	~12% traffic
Shard 1	”bf” — “ce”	~11% traffic
Shard 2	”cf” — “di”	~10% traffic
…	…	…
Shard 9	”t” — “z”	~13% traffic

Cách xác định range: Dựa trên historical query distribution. Điều chỉnh định kỳ khi traffic pattern thay đổi.

Shard Map & Zookeeper

Làm sao Query Service biết prefix “sys” nằm ở shard nào?

Giải pháp: Dùng Shard Map — mapping từ prefix range → shard address. Lưu shard map trong Zookeeper (hoặc etcd):

graph TD
    subgraph "Shard Map (Zookeeper)"
        ZK[Zookeeper Cluster]
        SM["Shard Map:<br/>a-be → Shard 0<br/>bf-ce → Shard 1<br/>cf-di → Shard 2<br/>...<br/>t-z → Shard 9"]
    end

    subgraph "Query Service"
        QS1[Query Server 1]
        QS2[Query Server 2]
        QS3[Query Server 3]
    end

    subgraph "Trie Shards"
        S0[Shard 0<br/>Prefix: a-be]
        S1[Shard 1<br/>Prefix: bf-ce]
        S2[Shard 2<br/>Prefix: cf-di]
        S9[Shard 9<br/>Prefix: t-z]
    end

    QS1 --> ZK
    QS2 --> ZK
    QS3 --> ZK
    ZK --> SM

    QS1 --> S0
    QS1 --> S1
    QS2 --> S2
    QS3 --> S9

    style ZK fill:#fff9c4

Luồng hoạt động:

1. Query Server khởi động → đọc shard map từ Zookeeper, cache local
2. Request đến với prefix “sys” → lookup shard map → “sys” thuộc Shard 9 (range “t-z”) — uh oh, “sys” thuộc range “s” nên cần chỉnh lại mapping
3. Route request đến Shard tương ứng
4. Khi shard map thay đổi (rebalance), Zookeeper notify tất cả Query Server → update cache

Replication

Mỗi shard có 3 replicas (tham khảo: Tuan-07-Database-Sharding-Replication):

• 1 Primary — nhận Trie update từ Trie Builder
• 2 Replicas — serve read traffic
• Nếu Primary chết → một Replica được promote lên Primary
• Read traffic được load balance giữa các replicas

Aha Moment: Sharding Trie khó hơn sharding database thông thường. Với DB, bạn hash key → shard. Với Trie, bạn phải giữ toàn bộ subtree của một prefix range trên cùng shard — không thể chia nhỏ hơn. Đây là constraint đặc biệt của Trie.

---

3. Capacity Estimation (Ước lượng chi tiết)

3.1 QPS Calculation

Given:

• DAU = 10 million
• Searches per user per day = 10
• Keystrokes per query = 20 (trung bình)
• Seconds in a day = 86,400

$$Totalsearches/day=10M\times 10=100Msearches/day$$ $$Totalkeystrokes/day=100M\times 20=2Bkeystrokes/day$$

Trước optimization (không debounce, không cache):

$$QP{S}_{raw}=\frac{2,000,000,000}{86,400}\approx 23,148requests/s\approx 23KQPS$$ $$QP{S}_{peak}=23K\times 3\approx 69KQPS$$

Sau optimization (debounce giảm 80%, browser cache giảm 60% còn lại):

$$QP{S}_{after\_debounce}=23K\times 0.2=4,600QPS$$ $$QP{S}_{after\_cache}=4,600\times 0.4=1,840QPS$$ $$QP{S}_{peak\_optimized}=1,840\times 3\approx 5,520QPS$$

Nhận xét: Từ 69K QPS peak xuống 5.5K QPS peak — giảm 92% nhờ debounce + caching. Đây là lý do frontend optimization cực kỳ quan trọng cho autocomplete.

3.2 Storage for Trie

Assumptions:

• Số lượng unique queries: 100 million (100M)
• Average query length: 20 characters = 20 bytes (ASCII) hoặc 40 bytes (UTF-8 multi-language)
• Mỗi node trong Trie: 50 bytes (character + metadata + pointers)
• Top K list per node: 10 entries x 30 bytes = 300 bytes per node
• Số lượng node trong Trie (sau compression): ~500 million (500M)

$$Triesiz{e}_{basic}=500M\times 50bytes=25GB$$ $$TopKoverhead=500M\times 300bytes=150GB$$ $$TotalTriesize=25GB+150GB=175GB$$

Với compression (binary serialization):

$$CompressedTrie\approx 175GB\times 0.3=52.5GB$$

Nhận xét: 52.5 GB có thể fit vào RAM của 1 server mạnh (64GB+ RAM). Nhưng để an toàn và scale, bạn nên shard thành 5-10 shard, mỗi shard ~5-10 GB. Rất thoải mái.

3.3 Network Bandwidth

Request size: ~50 bytes (prefix + headers) Response size: ~500 bytes (10 suggestions x 50 bytes mỗi cái)

$$Inboundbandwidth=5,520QPS\times 50bytes=276KB/s\approx 0.28MB/s$$ $$Outboundbandwidth=5,520QPS\times 500bytes=2,760KB/s\approx 2.76MB/s$$

Nhận xét: Bandwidth cực thấp. Autocomplete là tính toán nhiều, truyền tải ít (compute-heavy, IO-light). Bottleneck là CPU/RAM cho Trie lookup, không phải network.

3.4 Storage for Logs & Aggregated Data

$$Rawlogpersearch=200bytes(timestamp+user\_hash+query+metadata)$$ $$Rawlog/day=100M\times 200bytes=20GB/day$$ $$Rawlog/year=20GB\times 365=7.3TB/year$$ $$Aggregateddata(compressed)\approx 5\%ofraw=365GB/year$$

---

4. Security Considerations

4.1 Filter Offensive/Harmful Suggestions

Mối đe dọa	Ảnh hưởng	Giải pháp
Autocomplete gợi ý nội dung phân biệt chủng tộc	PR crisis, mất user trust, kiện tụng	Multi-layer filter (blocklist + ML)
Gợi ý liên quan bạo lực, vũ khí	Trách nhiệm pháp lý	Strict blocklist, zero tolerance
Gợi ý nội dung người lớn	Không phù hợp mọi đối tượng	SafeSearch toggle, default ON
Gợi ý tự tử / tự gây thương	Trách nhiệm xã hội	Block + hiển thị “Nếu bạn cần hỗ trợ, gọi 1800-…”

Best Practices:

• Maintain curated blocklist — được cập nhật hàng tuần bởi content moderation team (người thực, không chỉ ML)
• ML model phân loại query safe/unsafe — train trên data đã label
• A/B testing filter — test filter mới trên % nhỏ user trước khi rollout
• Incident response — khi phát hiện gợi ý xấu đã lọt lưới, có thể push blocklist update trong phút, không cần rebuild Trie
• Human-in-the-loop — với những query mơ hồ (có thể offensive trong 1 context nhưng không phải ở context khác), để con người review

4.2 User Privacy

Vấn đề	Chi tiết	Giải pháp
Search log chứa PII	Log query chứa tên, địa chỉ, thông tin cá nhân	Anonymize user_id trước khi log (hash + salt)
Location tracking	IP address trong log → xác định vị trí user	Aggregate theo region (quốc gia/thành phố), không lưu exact IP
Sensitive searches	User search thông tin y tế, luật sư, chính trị	KHÔNG log các query thuộc sensitive categories
Data retention	Lưu log quá lâu → tăng risk data breach	Delete raw log sau 30 ngày, aggregated data sau 2 năm

Privacy-by-design principles:

1. Data minimization — Chỉ thu thập dữ liệu cần thiết cho autocomplete, không hơn
2. Anonymization — Tách search log khỏi user identity. Dùng differential privacy khi có thể
3. Encryption at rest — Log và aggregated data được encrypt trên disk (AES-256)
4. Encryption in transit — HTTPS/TLS cho tất cả request (đã là standard)
5. Access control — Chỉ data engineering team truy cập raw log. Dùng role-based access (RBAC)

4.3 GDPR Compliance (Right to Erasure)

GDPR (General Data Protection Regulation) của EU yêu cầu:

• User có quyền yêu cầu xóa tất cả dữ liệu liên quan đến họ
• Điều này áp dụng cho: search logs, aggregated data, và cả autocomplete suggestions chứa thông tin cá nhân

Thách thức: Trie đã được build — làm sao xóa 1 query cụ thể?

Giải pháp:

Approach	Mô tả	Pros	Cons
Rebuild Trie (exclude deleted queries)	Khi nhận deletion request, đánh dấu query để exclude, áp dụng khi rebuild Trie kế tiếp	Đơn giản, clean	Delay (phải chờ rebuild cycle)
Runtime filter	Maintain “deleted queries” list. Filter tại query time	Nhanh (áp dụng ngay lập tức)	Overhead mỗi request
Hybrid	Runtime filter ngay lập tức + rebuild Trie để xóa vĩnh viễn	Nhanh và clean	Phức tạp hơn

Process xử lý GDPR deletion request:

1. User gửi request xóa dữ liệu → Identity Service xác nhận user
2. Tìm tất cả log entries liên quan đến user (bằng user_id_hash)
3. Xóa/anonymize log entries
4. Thêm các queries cần xóa vào “deletion list”
5. Apply runtime filter ngay → user không còn thấy gợi ý liên quan
6. Trie rebuild kế tiếp sẽ exclude các queries này

4.4 Preventing Manipulation (SEO Spam in Suggestions)

Mối đe dọa: Bad actors cố gắng “bom” autocomplete bằng cách:

• Dùng bot gõ lặp đi lặp lại một query để tăng frequency
• Coordinated attack — nhiều người cùng search 1 query để đẩy nó lên top
• Mục đích: quảng cáo miễn phí, bôi nhọ đối thủ, lan truyền thông tin sai

Giải pháp:

Kỹ thuật	Mô tả
Rate limiting per user/IP	Giới hạn số query/phút từ cùng 1 user hoặc IP. Tham khảo Tuan-09-Rate-Limiter
Bot detection	Phát hiện pattern bất thường: query quá nhanh, không có mouse movement, headless browser
Minimum frequency threshold	Query phải đạt số lượng tối thiểu (vd: 1000 unique users) mới xuất hiện trong autocomplete
Unique user counting	Đếm số unique users search một query, không phải tổng số searches. 1 user search 1000 lần = 1 count
Anomaly detection	Phát hiện query tăng đột ngột bất thường → flag để review trước khi đưa vào Trie
Verified source weighting	Query từ logged-in user có weight cao hơn anonymous. Query từ known-good IP range có weight cao hơn suspicious IP

---

5. DevOps & Monitoring

5.1 Trie Rebuild Pipeline Monitoring

Metric	Mô tả	Alert Threshold
Pipeline completion time	Thời gian từ raw log → Trie hoàn chỉnh	> 2x bình thường → alert
Pipeline success rate	% pipeline run thành công	< 99% → alert
Trie size delta	Thay đổi size giữa 2 version Trie	Tăng/giảm > 20% → investigate
Query count delta	Số lượng query trong Trie mới vs cũ	Giảm > 10% → có thể mất data
Aggregation lag	Thời gian từ query xảy ra → xuất hiện trong Trie	> 4 giờ → check pipeline

Pipeline health dashboard nên hiển thị:

• Thời gian hoàn thành pipeline lần gần nhất
• Số lượng raw log records processed
• Số lượng unique queries sau aggregation
• Trie size (bytes) và số lượng nodes
• Trạng thái deployment (đang serve Trie version nào)

5.2 Query Latency Monitoring

Metric	Target	Giải thích
P50 latency	< 10ms	Phân nửa request phải dưới 10ms
P95 latency	< 50ms	95% request dưới 50ms
P99 latency	< 100ms	99% request dưới 100ms — đây là hard requirement
P99.9 latency	< 200ms	Edge case — có thể chấp nhận

Nguyên nhân latency spike và cách xử lý:

Nguyên nhân	Phát hiện	Xử lý
GC pause (Java/Go)	JVM GC log, latency spike định kỳ	Tune GC, dùng low-latency GC (ZGC, Shenandoah)
Trie reload (load Trie mới vào RAM)	Latency spike tại thời điểm deploy Trie mới	Blue-green deployment: load Trie mới xong mới switch traffic
Cold start (server mới khởi động)	Latency cao ở vài nghìn request đầu	Warm-up: load Trie và xử lý dummy requests trước khi nhận traffic thật
Network issue	Latency tăng đồng đều trên nhiều server	Check network dashboard, route lại traffic
Hot prefix	Latency tăng cho 1 shard cụ thể	Scale up shard đó, hoặc rebalance prefix range

5.3 Cache Hit Ratio

Cache layer	Target hit ratio	Giải thích
Browser cache	30-50%	User thường gõ lại các prefix giống nhau
CDN cache	60-80%	Prefix ngắn (1-3 chars) được cache hiệu quả
Application cache (Trie in memory)	100%	Trie luôn có trong RAM — mọi prefix đều có kết quả

Nếu cache hit ratio thấp hơn mong đợi:

• Browser cache thấp → kiểm tra Cache-Control header có đúng không
• CDN cache thấp → kiểm tra TTL, cache key strategy, xem có vary header không cần thiết
• Nhiều cache miss → xem xét user behavior change (trending event → query mới)

5.4 A/B Testing for Ranking Algorithms

Autocomplete ranking không chỉ là frequency. Các signal khác:

Signal	Mô tả	Ví dụ
Frequency	Số lần query được search	”python tutorial” > “python asyncio”
Freshness	Query mới/trending được boost	”world cup 2026” boost trong mùa giải
Personalization	Dựa trên user history	Dev search “python” → boost “python docs”
Click-through rate	% user chọn gợi ý đó	Gợi ý được chọn nhiều → boost
Geography	Dựa trên vị trí user	User ở VN: “pho” → “pho ha noi”; User ở US: “pho” → “phone number”

A/B testing process:

1. Hypothesis: “Thêm freshness signal sẽ tăng click-through rate 5%”
2. Experiment: 5% user (random) nhận ranking mới (treatment), 95% nhận ranking cũ (control)
3. Metrics: So sánh click-through rate, search completion time, user satisfaction (bounce rate)
4. Duration: Chạy ít nhất 2 tuần để có đủ statistical significance
5. Decision: Nếu treatment tốt hơn với p-value < 0.05 → rollout 100%

Pitfall: A/B test autocomplete khó vì feedback loop — nếu bạn gợi ý “X” cho treatment group, họ sẽ click “X” nhiều hơn → tăng frequency của “X” → gợi ý “X” nhiều hơn. Cần careful experimental design để tránh bias.

5.5 Alerting Strategy

Alert	Severity	Action
P99 latency > 100ms kéo dài 5 phút	Critical	Page on-call engineer. Kiểm tra: Trie reload? GC? Hot shard?
Pipeline fail 2 lần liên tiếp	High	Investigate pipeline. Trie cũ vẫn đang serve — không mất service
Trie size giảm > 20%	High	Có thể mất data trong aggregation. KHÔNG deploy Trie này — rollback
Cache hit ratio giảm > 30%	Medium	Kiểm tra cache config, TTL, trending event
Filter miss (offensive suggestion reported)	High	Update blocklist ngay. Root cause analysis
Error rate > 1%	Critical	Kiểm tra server health, dependency failure

---

6. Architecture Diagrams (Mermaid)

6.1 Overall System Architecture

graph TB
    subgraph "Client Layer"
        WEB[Web Browser<br/>Debounce + Local Cache]
        MOB[Mobile App<br/>Debounce + Local Cache]
    end

    subgraph "Edge Layer"
        CDN[CDN / Edge Cache<br/>Cloudflare / CloudFront]
    end

    subgraph "API Layer"
        LB[Load Balancer]
        AG1[API Gateway 1]
        AG2[API Gateway 2]
    end

    subgraph "Query Service Layer"
        QS1[Query Server 1<br/>Trie Shard 0-2 in RAM]
        QS2[Query Server 2<br/>Trie Shard 3-5 in RAM]
        QS3[Query Server 3<br/>Trie Shard 6-9 in RAM]
        FL[Filter Service<br/>Blocklist + ML]
    end

    subgraph "Coordination"
        ZK[Zookeeper<br/>Shard Map + Config]
    end

    subgraph "Storage Layer"
        TS[Trie Storage<br/>S3 / GCS]
        RC[Redis Cache<br/>Hot Prefixes]
    end

    subgraph "Data Pipeline (Offline)"
        KF[Kafka<br/>Query Event Stream]
        SP[Spark Cluster<br/>Aggregation]
        DB[Aggregated Data<br/>PostgreSQL / Hive]
        TBU[Trie Builder<br/>Build + Serialize]
    end

    subgraph "Monitoring"
        MON[Prometheus + Grafana<br/>Metrics & Dashboards]
        ALR[Alert Manager<br/>PagerDuty Integration]
    end

    WEB --> CDN
    MOB --> CDN
    CDN --> LB
    LB --> AG1
    LB --> AG2
    AG1 --> QS1
    AG1 --> QS2
    AG2 --> QS2
    AG2 --> QS3
    QS1 --> FL
    QS2 --> FL
    QS3 --> FL
    QS1 --> ZK
    QS2 --> ZK
    QS3 --> ZK
    QS1 --> RC
    QS2 --> RC
    QS3 --> RC

    WEB -->|"Completed queries"| KF
    MOB -->|"Completed queries"| KF
    KF --> SP
    SP --> DB
    DB --> TBU
    TBU --> TS
    TS -->|"Pull new Trie"| QS1
    TS -->|"Pull new Trie"| QS2
    TS -->|"Pull new Trie"| QS3

    QS1 --> MON
    QS2 --> MON
    QS3 --> MON
    SP --> MON
    MON --> ALR

    style CDN fill:#e1f5fe
    style ZK fill:#fff9c4
    style KF fill:#e8eaf6
    style SP fill:#f3e5f5
    style FL fill:#fff3e0
    style MON fill:#e8f5e9

6.2 Trie Structure Visualization

graph TD
    ROOT["ROOT<br/>Top 10: system design, software engineer, ..."]

    S["s<br/>Top 10: system design, software engineer,<br/>stack overflow, ..."]
    T["t<br/>Top 10: tutorial, twitter, ..."]

    SY["sy<br/>Top 10: system design, sync, ..."]
    SO["so<br/>Top 10: software engineer, sorting, ..."]
    ST["st<br/>Top 10: stack overflow, streaming, ..."]

    SYS["sys<br/>Top 10: system design, system design interview,<br/>system design primer, ..."]

    SYST["syst<br/>Top 10: system design, system design interview, ..."]

    SYSTE["syste<br/>Top 10: system design, system design interview,<br/>system design primer, ..."]

    SYSTEM["system<br/>Top 10: system design, system design interview,<br/>system 32, system restore, ..."]

    ROOT --> S
    ROOT --> T
    S --> SY
    S --> SO
    S --> ST
    SY --> SYS
    SYS --> SYST
    SYST --> SYSTE
    SYSTE --> SYSTEM

    style ROOT fill:#ffcdd2
    style S fill:#f8bbd0
    style SYS fill:#e1bee7
    style SYSTEM fill:#c5cae9

Key insight: Mỗi node lưu sẵn top 10. Khi user gõ “sys”, Query Service chỉ cần đọc 1 node — không cần traverse subtree. O(1) lookup!

6.3 Data Gathering Pipeline (Chi tiết)

graph LR
    subgraph "Step 1: Ingest"
        U1[User Search Event]
        U2[User Search Event]
        U3[User Search Event]
        KP[Kafka Producer<br/>Batch + Compress]
        KT[Kafka Topic<br/>search-queries<br/>Partitioned by region]
    end

    subgraph "Step 2: Raw Storage"
        KC[Kafka Consumer<br/>S3 Sink Connector]
        S3R[S3 Raw Logs<br/>Partitioned by date/hour<br/>Parquet format]
    end

    subgraph "Step 3: Aggregate"
        SCH[Scheduler<br/>Airflow / Cron]
        SPK[Spark Job<br/>GroupBy query<br/>Count distinct users<br/>Apply decay]
        S3A[S3 Aggregated<br/>query, frequency, timestamp]
    end

    subgraph "Step 4: Build"
        TB[Trie Builder<br/>Read aggregated data<br/>Build optimized Trie<br/>Compress + Serialize]
        VAL[Validator<br/>Check Trie size<br/>Spot-check queries<br/>Compare with previous]
    end

    subgraph "Step 5: Deploy"
        S3T[S3 Trie Storage<br/>Versioned: v2026-03-18-12h]
        DEP[Deployer<br/>Notify Query Servers<br/>Blue-Green switch]
        QSR[Query Servers<br/>Pull + Load Trie]
    end

    U1 --> KP
    U2 --> KP
    U3 --> KP
    KP --> KT
    KT --> KC
    KC --> S3R
    SCH -->|"Trigger hourly"| SPK
    S3R --> SPK
    SPK --> S3A
    S3A --> TB
    TB --> VAL
    VAL -->|"Pass"| S3T
    VAL -->|"Fail"| SCH
    S3T --> DEP
    DEP --> QSR

    style KT fill:#e8eaf6
    style SPK fill:#f3e5f5
    style VAL fill:#fff3e0
    style DEP fill:#e8f5e9

6.4 Query Service Flow (Chi tiết)

flowchart TD
    A[User types character] --> B{Debounce timer active?}
    B -->|Yes| C[Reset timer to 200ms]
    B -->|No| D[Start 200ms timer]
    C --> E[Wait for timer]
    D --> E
    E --> F{Timer expired?}
    F -->|No, user typed again| B
    F -->|Yes| G[Get current prefix]
    G --> H{Prefix in browser cache?}
    H -->|Yes| I[Return cached result]
    H -->|No| J[Send AJAX to CDN]
    J --> K{CDN cache hit?}
    K -->|Yes| L[Return CDN cached result]
    K -->|No| M[Forward to API Gateway]
    M --> N[Rate limit check]
    N -->|Rejected| O[Return 429 Too Many Requests]
    N -->|Passed| P[Lookup Shard Map]
    P --> Q[Route to correct Trie Shard]
    Q --> R[Trie prefix lookup — O of 1]
    R --> S[Get top 10 raw suggestions]
    S --> T[Apply Filter Layer]
    T --> U{All 10 suggestions safe?}
    U -->|Yes| V[Return JSON response]
    U -->|No| W[Remove unsafe, backfill from next candidates]
    W --> V
    V --> X[Set Cache-Control headers]
    X --> Y[Response cached at CDN]
    Y --> Z[Response cached at Browser]
    Z --> AA[Display dropdown to user]

    style I fill:#e1f5fe
    style L fill:#e1f5fe
    style R fill:#c8e6c9
    style T fill:#fff3e0

---

7. Aha Moments & Pitfalls

7.1 Aha Moments — Những điều interviewer muốn nghe

#	Aha Moment	Giải thích
1	Trie vs Database lookup	Nhiều người nghĩ “chỉ cần SELECT * FROM queries WHERE query LIKE ‘sys%’ ORDER BY frequency LIMIT 10”. Nhưng với 100M+ queries, LIKE query + sort là O(n log n) — cực chậm. Trie cho O(1) lookup vì top K đã được precomputed
2	Offline update, không phải realtime	Autocomplete không cần real-time. Delay 15 phút - 1 giờ là chấp nhận được. Điều này đơn giản hóa thiết kế rất nhiều — không cần distributed lock, không cần consensus
3	Debounce saves 80% traffic	Một optimization ở frontend giảm 80% load cho backend. Interviewer ấn tượng khi bạn nghĩ tới full-stack optimization, không chỉ backend
4	Space-time trade-off tại mỗi Trie node	Lưu top K tại mỗi node = tăng space 10x nhưng giảm lookup time từ O(millions) xuống O(1). Đây là quintessential engineering trade-off
5	Graceful degradation	Autocomplete là nice-to-have, không phải critical. Nếu chết, search vẫn hoạt động. Nói điều này cho thấy bạn hiểu system resilience
6	Two separate systems	Data Gathering và Query Service là hoàn toàn độc lập. Chỉ share Trie artifact. Đây là clean architecture — mỗi phần có thể scale/fail độc lập
7	Cache at every layer	Browser → CDN → Application RAM. Mỗi layer filter traffic, chỉ 10-20% requests đến backend. Đây là multi-tier caching strategy

7.2 Pitfalls — Những lỗi thường gặp

#	Pitfall	Tại sao sai	Nên làm gì
1	Dùng RDBMS cho autocomplete	LIKE query + ORDER BY trên 100M rows = seconds, không phải milliseconds. Index giúp nhưng vẫn chậm hơn Trie	Dùng Trie — data structure được thiết kế riêng cho prefix search
2	Update Trie mỗi keystroke	23K QPS writes vào Trie = race condition, lock contention, write amplification	Tách read path (online) và write path (offline). Update Trie định kỳ
3	Không nghĩ về frontend	Chỉ thiết kế backend → bỏ qua debounce, caching → traffic gấp 5-10x	Autocomplete là bài toán full-stack. Frontend optimization quan trọng như backend
4	Shard Trie theo hash	Hash(“sys”) có thể map đến shard khác với hash(“syst”) → không thể traverse từ prefix này sang prefix kia	Shard theo prefix range, không phải hash. Giữ subtree trên cùng shard
5	Quên filter layer	Deploy autocomplete không có content filter → gợi ý offensive → PR disaster	Luôn có filter layer. Blocklist + ML + human review
6	Quên tính capacity	Không ước lượng QPS, storage → thiết kế không phù hợp scale	Back-of-envelope estimation trước khi dive vào design. Tham khảo Tuan-02-Back-of-the-envelope
7	Không nói về failure mode	Chỉ trình bày happy path → interviewer hỏi “nếu Trie Builder fail thì sao?” → lúng túng	Luôn chuẩn bị: Trie Builder fail → keep serving Trie cũ. Query Server crash → LB route sang server khác. Filter Service down → serve unfiltered (hoặc block autocomplete tạm thời)

7.3 Interview Tips — Cách trình bày

Giai đoạn	Bạn nên làm	Bạn KHÔNG nên làm
Mở đầu (2 phút)	Hỏi requirements, clarify scope, nêu giả định	Nhảy thẳng vào vẽ diagram
High-level (5 phút)	Vẽ 2 thành phần chính (Data Gathering + Query Service), giải thích flow	Vẽ quá nhiều detail, liệt kê công nghệ cụ thể
Deep dive (15 phút)	Giải thích Trie, optimization, trade-offs. Hỏi interviewer muốn dive vào phần nào	Tự chọn phần dễ nhất để trình bày
Wrap up (3 phút)	Nói về scaling (sharding, replication), monitoring, security	Bỏ qua hoàn toàn, hoặc nói “em nghĩ vậy là đủ”

---

8. Internal Links & Cross-References

Các bài học liên quan trực tiếp

Topic	Link	Áp dụng trong Autocomplete
Cache Strategy	Tuan-06-Cache-Strategy	Multi-tier caching: Browser → CDN → In-memory Trie. Cache invalidation khi Trie mới deploy
Message Queue	Tuan-08-Message-Queue	Kafka làm buffer cho search query log. Decouple Data Gathering pipeline
Consistent Hashing	Tuan-10-Consistent-Hashing	Có thể dùng cho Trie sharding (dù prefix-range sharding phổ biến hơn)

Các bài học bổ trợ

Topic	Link	Liên hệ
Scale from Zero	Tuan-01-Scale-From-Zero-To-Millions	Autocomplete bắt đầu từ 1 server với Trie in-memory, scale dần lên
Back-of-envelope	Tuan-02-Back-of-the-envelope	Phương pháp tính QPS, storage, bandwidth ở Section 3
Database Sharding	Tuan-07-Database-Sharding-Replication	Trie sharding tương tự DB sharding nhưng có constraint riêng (phải giữ subtree)
Rate Limiter	Tuan-09-Rate-Limiter	Bảo vệ autocomplete API khỏi bot/spam
Monitoring	Tuan-13-Monitoring-Observability	Cách monitor pipeline, latency, cache hit ratio
Security	Tuan-14-AuthN-AuthZ-Security	API Gateway authentication, rate limiting

So sánh với các Case Study khác

Case Study	Điểm tương đồng	Điểm khác biệt
Tuan-16-Design-URL-Shortener	Read-heavy, caching quan trọng, estimation approach giống nhau	URL Shortener dùng hash, Autocomplete dùng Trie. URL Shortener cần strong consistency, Autocomplete chấp nhận eventual
Tuan-18-Design-News-Feed	Cả hai cần ranking algorithm, personalization, offline pipeline	News Feed phức tạp hơn về social graph. Autocomplete đơn giản hơn về data model nhưng khó hơn về latency requirement
Tuan-19-Design-Notification-System	Cả hai có offline pipeline (data gathering vs notification scheduling)	Notification là push, Autocomplete là pull. Notification chấp nhận delay, Autocomplete phải < 100ms

---

9. Summary — Tóm tắt 1 trang

Hệ thống Autocomplete gồm 2 phần chính:

1. Data Gathering Service (Offline):

• Thu thập search queries từ user → Kafka → S3
• Aggregate frequency bằng Spark/MapReduce
• Build optimized Trie (lưu top K tại mỗi node)
• Serialize và deploy Trie định kỳ (mỗi giờ/ngày)

2. Query Service (Online):

• Nhận prefix từ user (sau debounce)
• Lookup Trie in-memory → O(1) vì top K đã precomputed
• Filter offensive content
• Trả về 10 suggestions trong < 100ms

5 điều quan trọng nhất cần nhớ:

1. Trie là data structure cốt lõi — thiết kế riêng cho prefix search, vượt trội hơn database LIKE query
2. Precompute top K tại mỗi node — trade space cho speed, O(1) lookup
3. Tách read path và write path — CQRS pattern, scale độc lập
4. Frontend optimization (debounce + cache) giảm 90%+ traffic — đây là full-stack problem
5. Shard Trie theo prefix range, KHÔNG phải hash — phải giữ subtree trên cùng shard

“Autocomplete là bài toán tưởng đơn giản nhưng ẩn chứa mọi khía cạnh của system design: data structure, distributed systems, caching, pipeline, security, và full-stack thinking. Master bài này, bạn sẽ sẵn sàng cho bất kỳ system design interview nào.”

---

Next Step: Thực hành vẽ lại toàn bộ architecture diagram từ đầu, không nhìn tài liệu. Nếu bạn vẽ được 80% chính xác, bạn đã nắm vững bài này.