🔍 Trận 6: Thiết kế Search Autocomplete — Google gợi ý từ khóa như thế nào?
Hãy tưởng tượng bạn mở Google và bắt đầu gõ:
t tw twi twit twitt twitterBạn chưa kịp gõ xong, Google đã liên tục đưa ra những gợi ý như:
twitter twitch twilio twitter login twitter stock
Điều thú vị là: mỗi một ký tự bạn gõ có thể tạo ra một request đến server.
Nếu có hàng triệu người cùng sử dụng hệ thống, bài toán tưởng như đơn giản này sẽ trở thành một bài toán Distributed System thực sự.
Trong bài này, chúng ta sẽ thử thiết kế một hệ thống Search Autocomplete có khả năng phục vụ 10 triệu người dùng mỗi ngày, với mục tiêu trả kết quả trong dưới 100ms.
Thay vì bắt đầu bằng việc chọn database hay Trie ngay lập tức, chúng ta sẽ làm đúng cách tiếp cận trong một buổi System Design Interview:
1. Hiểu yêu cầu
↓
2. Ước lượng quy mô
↓
3. Vẽ kiến trúc tổng quan
↓
4. Phân tích thành phần quan trọng
↓
5. Trade-off & Scaling
🎯 1. Bước 1 — Hiểu yêu cầu
Trong System Design Interview, một trong những sai lầm phổ biến nhất là nghe đề bài xong lập tức vẽ architecture.
Ví dụ interviewer nói:
"Design a Search Autocomplete system."
Nếu ngay lập tức bạn nói:
"Em sẽ dùng Redis + Elasticsearch + Kafka + Kubernetes..."
thì bạn đang thiết kế khi chưa biết chính xác mình cần thiết kế cái gì.
Một hệ thống tốt bắt đầu bằng việc đặt câu hỏi.
Ví dụ
- Search Autocomplete cần làm gì?
- Có cần tìm substring không?
- Hiển thị bao nhiêu kết quả gợi ý?
- "Popular" được tính như thế nào?
- Latency bao nhiêu là đủ?
🎯 1. Search Autocomplete cần làm gì?
Hãy bắt đầu từ hành vi của người dùng.
Người dùng nhập:
tw
Hệ thống cần trả về:
twitch
twitter
twilio
twilight
twitter login
Nhưng không phải bất kỳ kết quả nào.
Ta muốn những query phổ biến nhất có prefix trùng với input.
Ví dụ:
Input: "tw"
twitch → 1,000,000 searches
twitter → 800,000 searches
twilio → 500,000 searches
twilight → 300,000 searches
twitter login → 200,000 searches
Hệ thống trả về Top 5.
Functional Requirement
Ta có thể chốt requirement đầu tiên:
Cho một tiền tố (prefix), hãy trả về 5 truy vấn tìm kiếm phổ biến nhất bắt đầu bằng tiền tố đó.
🎯 2. Có cần tìm substring không?
Đây là một câu hỏi quan trọng.
Nếu user nhập:
tw
ta có cần tìm:
best twitter account
how to use twitter
twitter login
hay chỉ cần:
twitter
twitch
twilio
Trong bài toán này, ta chỉ quan tâm prefix matching.
"tw" → "twitter" ✅
"tw" → "twitch" ✅
"tw" → "best twitter" ❌
Điều này đơn giản hóa hệ thống rất nhiều.
🎯 3. Bao nhiêu kết quả?
Không cần trả về hàng trăm kết quả.
UI autocomplete thường chỉ hiển thị một số lượng nhỏ:
┌─────────────────────────┐
│ tw │
├─────────────────────────┤
│ twitch │
│ twitter │
│ twilio │
│ twilight │
│ twitter login │
└─────────────────────────┘
Ta chốt:
Mỗi request trả về Top 5 suggestions.
🎯 4. "Popular" được tính như thế nào?
Đây cũng là một requirement cần làm rõ.
Có thể có rất nhiều cách tính popularity:
- Tổng số lượt search
- Số người dùng unique
- Popularity trong 24 giờ
- Popularity trong 7 ngày
- Trending score
- Kết hợp popularity + freshness
Để giữ bài toán đơn giản, ta chọn:
Popularity = tổng số lần query được tìm kiếm.
Ví dụ:
query frequency
---------------------
twitch 1,000
twitter 800
twilio 500
frequency càng lớn → query càng phổ biến.
🎯 5. Latency bao nhiêu là đủ?
Autocomplete khác với một API thông thường.
Nếu user gõ:
t
mà phải chờ:
1 giây
mới thấy kết quả thì trải nghiệm rất tệ.
User tiếp tục gõ:
tw
twi
twit
trong khi request trước còn chưa trả về.
Vì vậy chúng ta đặt mục tiêu:
P95 latency < 100ms
Tức là phần lớn request phải được xử lý trong khoảng 100ms.
Trong hệ thống thực tế, thậm chí ta có thể muốn thấp hơn nữa, nhưng 100ms là một target hợp lý cho bài System Design này.
🎯 Quy mô hệ thống
Bây giờ requirement đã rõ hơn.
Giả sử: DAU = 10 million
Tức là mỗi ngày có khoảng: 10,000,000 users
Nhưng 10 triệu DAU không đồng nghĩa với 10 triệu request/ngày.
Một user có thể tìm kiếm nhiều lần.
Giả sử trung bình:
10 searches / user / day
Ta có:
10M × 10 = 100M searches/day
Nhưng autocomplete còn đặc biệt hơn.
Mỗi search không chỉ tạo một request.
📊 2. Bước 2 — Ước lượng quy mô
Giả sử user tìm:
dinner
Họ có thể gửi request sau mỗi lần gõ:
d
di
din
dinn
dinne
dinner
Tức là khoảng 6 autocomplete requests cho một search.
Vậy 100M searches/day × 6 = 600M requests/day
Đây mới là con số chúng ta quan tâm.
📊 1. Tính QPS trung bình
Một ngày có: 86,400 seconds
Do đó: 600M / 86,400 ≈ 6,944 QPS
Làm tròn:
Average QPS ≈ 7K
Đây là mức tải trung bình.
📊 2. Peak QPS
Traffic thực tế không phân bố đều.
Ví dụ:
03:00 → ít người dùng
12:00 → nhiều người dùng
20:00 → rất nhiều người dùng
Vì vậy cần thiết kế cho peak.
Giả sử peak gấp đôi average:
7K × 2 ≈ 14K QPS
Ta có:
Peak QPS ≈ 14K
📊 3. Con số này nói cho chúng ta điều gì?
Đây chính là lý do back-of-the-envelope estimation quan trọng.
Nếu interviewer hỏi:
"Tại sao không dùng một database duy nhất?"
Ta đã có cơ sở để trả lời:
14,000 requests/second
và mỗi request yêu cầu:
prefix search + sort by popularity + return top 5
Nếu mỗi request đều phải truy vấn một database lớn thì database sẽ trở thành bottleneck rất nhanh.
Vấn đề tiếp theo là:
Làm thế nào để tìm Top 5 query với prefix trong vài chục milliseconds?
Đây mới là phần thú vị.
🌳 3. Bước 3 — Vẽ kiến trúc tổng quan
Trước khi đi vào Trie, chúng ta hãy nhìn toàn bộ hệ thống.
Một insight quan trọng xuất hiện ở đây:
Đọc và ghi có đặc điểm hoàn toàn khác nhau.
Read Path
User liên tục gõ:
t
tw
twi
twit
→ yêu cầu cực nhanh.
Write Path
Khi user tìm kiếm:
"twitter"
→ hệ thống chỉ cần ghi nhận rằng query này vừa được search.
Không nhất thiết phải cập nhật popularity vào Trie ngay lập tức.
Vì vậy ta tách thành hai luồng.
🌳 1. Kiến trúc tổng quan
| ---------------------------------------------------------------------------------------------------- |  |
---------------------------------------------------------------------------------------------------- |
Nhìn architecture này, ta có thể chia hệ thống thành hai phần lớn.
Read Path
| ---------------------------------------------------------------------------------------------------- |  |
---------------------------------------------------------------------------------------------------- |
Mục tiêu:
Nhanh nhất có thể.
Write Path
| ---------------------------------------------------------------------------------------------------- |  |
---------------------------------------------------------------------------------------------------- |
Mục tiêu:
Thu thập và xử lý dữ liệu ổn định, không ảnh hưởng Read Path.
🌳 2. Tại sao không dùng SQL
Đây là lúc interviewer có thể hỏi:
"Tại sao không đơn giản dùng database?"
Thử giải pháp đơn giản nhất trước.
Ta có bảng:
frequency_table
query frequency
---------------------
twitter 1000
twitch 800
twilio 500
...
Khi user nhập:
tw
ta chạy:
SELECT query, frequency
FROM frequency_table
WHERE query LIKE 'tw%'
ORDER BY frequency DESC
LIMIT 5;
Nhìn rất hợp lý.
Và nếu database chỉ có vài nghìn hoặc vài chục nghìn record thì có thể hoàn toàn đủ dùng.
Nhưng vấn đề xuất hiện khi dữ liệu tăng lên:
1 million
10 million
100 million
1 billion queries
Mỗi request autocomplete đều cần:
1. tìm các query bắt đầu bằng "tw"
2. lấy frequency
3. sort theo frequency
4. lấy Top 5
Với:
~14K QPS peak
thì việc bắt database thực hiện công việc này liên tục sẽ rất tốn tài nguyên.
Đặc biệt, prefix phổ biến như:
a
t
s
c
có thể match một lượng dữ liệu khổng lồ.
🌳 3. Trie — vũ khí đầu tiên
Đây là lúc chúng ta cần một cấu trúc dữ liệu phù hợp hơn.
Thay vì lưu:
twitter
twitch
twilio
như những string độc lập, ta tận dụng phần prefix chung của chúng.
Ví dụ:
root
│
t
│
w
┌──┴──┐
i e
│ │
t e
│ │
t r
│ │
e ...
│
r
Đây chính là Trie. Một cấu trúc dữ liệu dạng cây. Mỗi node đại diện cho một ký tự
root
└── c
└── a
├── t → "cat"
└── r
└── t → "cart"
Trie được thiết kế đặc biệt cho các bài toán:
"Tìm tất cả string bắt đầu bằng prefix X."
🌳 4. Nhưng Trie vẫn chưa đủ
Đây là một điểm rất quan trọng.
Nếu ta tìm được node:
tw
thì chưa có nghĩa là bài toán đã xong.
Bên dưới node đó có thể có:
twitch
twitter
twilio
twilight
...
thậm chí hàng triệu query.
Nếu mỗi request lại phải:
1. tìm node "tw"
2. duyệt toàn bộ subtree
3. lấy frequency
4. sort
5. lấy Top 5
thì chúng ta lại quay về vấn đề ban đầu.
Trie giúp chúng ta tìm prefix nhanh, nhưng chưa giải quyết triệt để bài toán:
"Trong hàng triệu query bắt đầu bằng prefix này, đâu là 5 query phổ biến nhất?"
Và đây chính là nơi phần Deep Dive trở nên thú vị.
🧠 4. Bước 4 — Phân tích thành phần quan trọng
Hãy quay lại một request đơn giản:
GET /autocomplete?q=tw
Ta muốn nhận:
twitch
twitter
twilio
twilight
twitter login
Có hai việc cần làm:
"tw"
↓
① Tìm node "tw"
↓
② Tìm Top 5 query phổ biến nhất bên dưới node đó
🧠 1. Việc ① rất nhanh
Trie cho phép tìm tw bằng cách đi qua:
root
↓
t
↓
w
Nếu prefix có độ dài p, thời gian tìm kiếm là:
O(p)
Với p rất nhỏ thì gần như không đáng kể.
Nhưng vấn đề nằm ở việc ②.
🧠 2. Vấn đề của Trie thông thường
Giả sử Trie có cấu trúc:
root
│
t
│
w
┌───────┼────────┐
↓ ↓ ↓
twitch twitter twilio
│
...
Khi user nhập:
tw
ta tìm được node w.
Nhưng làm sao biết Top 5?
Cách đơn giản nhất:
tw
↓
Duyệt toàn bộ subtree
↓
Thu thập tất cả query
↓
Sort theo frequency
↓
Lấy 5 query đầu
Giả sử có:
c = 1,000,000 queries
thì mỗi request có thể phải xử lý tới hàng triệu query.
Với hàng nghìn request mỗi giây:
14,000 QPS × 1,000,000 queries
Đây rõ ràng là một thảm họa.
🧠 3. Ý tưởng quan trọng: Đừng tính lại thứ chúng ta đã biết
Hãy thử suy nghĩ theo cách khác.
Nếu user liên tục hỏi:
tw
thì Top 5 của tw không thay đổi sau mỗi request.
Ví dụ:
tw → 1. twitch
2. twitter
3. twilio
4. twilight
5. twitter login
Tại sao mỗi request chúng ta lại phải tính lại?
Đây là một pattern rất phổ biến trong System Design:
Nếu một phép tính tốn kém nhưng kết quả thay đổi không thường xuyên, hãy tính trước (pre-compute) và lưu kết quả lại.
Và đó chính là ý tưởng chúng ta sẽ áp dụng.
🧠 4. Pre-compute Top 5 tại mỗi Trie Node
Thay vì chỉ lưu thông tin của query, mỗi node trong Trie sẽ lưu thêm:
Top 5 queries
Ví dụ:
root
│
t
│
w
│
┌──────┴──────┐
│ │
Top 5 queries children...
Node tw có thể lưu:
tw
├── twitch 1,000,000
├── twitter 800,000
├── twilio 500,000
├── twilight 300,000
└── twitter login 200,000
Khi user gửi:
tw
Query Service chỉ cần:
Find "tw"
↓
Read topQueries
↓
Return
Không cần:
❌ duyệt subtree
❌ lấy hàng triệu query
❌ sort
🧠 5. Latency thay đổi như thế nào?
Cách cũ
Find prefix
↓
Traverse subtree
↓
Collect candidates
↓
Sort
↓
Top 5
Độ phức tạp có thể xấp xỉ:
O(p + c log k)
Trong đó:
p: độ dài prefixc: số query bên dưới prefixk: số kết quả cần lấy, ở đâyk = 5
Vấn đề là c có thể rất lớn.
Cách mới
Find prefix
↓
Read pre-computed Top 5
↓
Return
Không còn phụ thuộc vào số lượng query bên dưới node.
Với prefix có độ dài giới hạn:
O(p) ≈ O(1)
Đây là một khác biệt cực kỳ lớn.
🧠 6. Tại sao có thể gọi đây là "O(1)"?
Có một điểm cần hiểu chính xác.
Nếu nói hoàn toàn về mặt lý thuyết:
O(p)
vẫn phụ thuộc vào độ dài prefix.
Nhưng trong bài toán này, ta giới hạn:
p ≤ L
Ví dụ:
L = 50
Vì 50 là một hằng số nên trong thực tế ta có thể coi:
O(p) → O(1)
Quan trọng hơn:
Chi phí query không còn phụ thuộc vào số lượng dữ liệu khổng lồ phía dưới Trie.
Đây mới là insight cần nhớ.
🧠 7. Trie Node sẽ lưu gì?
Một node có thể chứa:
TrieNode
├── children
├── isWord
├── frequency
└── topQueries[]
Ví dụ:
Node: "tw"
isWord: false
topQueries:
twitch → 1,000,000
twitter → 800,000
twilio → 500,000
twilight → 300,000
twitter login → 200,000
Nếu node là một query hoàn chỉnh:
Node: "twitter"
isWord: true
frequency: 800,000
🧠 8. Nhưng có một vấn đề mới!
Optimization này cực kỳ hiệu quả cho Read Path.
Nhưng hãy nghĩ tiếp.
Điều gì xảy ra khi popularity thay đổi?
Ví dụ hôm qua:
twitch → 1,000,000
twitter → 800,000
Nhưng hôm nay có một sự kiện lớn:
Elon Musk tuyên bố chuyển trụ sở twitter lên sao hoả
và đột nhiên:
twitter → 2,000,000
Nếu chúng ta cập nhật trực tiếp Trie:
User Search
↓
Update frequency
↓
Update twitter node
↓
Update tw
↓
Update t
↓
...
thì một search có thể phải cập nhật rất nhiều node ancestor.
Tệ hơn nữa, nếu hàng nghìn user search cùng lúc:
User 1 ─┐
User 2 ─┤
User 3 ─┤
User 4 ─┼──→ Trie
User 5 ─┤
User 6 ─┘
chúng ta có thể gặp:
Lock contention
Race condition
CPU spike
Memory write contention
Trong khi Query Service đang cần đọc Trie với tốc độ cực cao.
🧠 9. Read nhiều, Write khác kiểu
Đây là lúc một pattern System Design quan trọng xuất hiện:
Tách Read Path khỏi Write/Update Path.
Autocomplete có đặc điểm:
READ
████████████████████████████████████
WRITE / UPDATE
██
Read xảy ra liên tục.
Write popularity có thể xử lý bất đồng bộ.
Query Service không cần quan tâm quá trình aggregation đang diễn ra như thế nào.
Nó chỉ đọc:
Trie Cache
🧠 10. Analytics Logs — Đừng cập nhật Trie ngay lập tức
Mỗi khi user thực hiện search:
User
↓
Search "twitter"
thay vì:
Search
↓
Update Trie
ta ghi event:
{
"query": "twitter",
"timestamp": "..."
}
vào hệ thống log.
Có thể hình dung:
Search Event
│
├──→ Search API
│
└──→ Analytics Log
Search API phục vụ user ngay lập tức.
Analytics Log chịu trách nhiệm lưu lại dữ liệu để xử lý sau.
🧠 11. Aggregator — Gom dữ liệu
Sau một khoảng thời gian, hệ thống lấy các log:
twitter
twitter
twitch
twitter
twilio
twitch
...
và thực hiện aggregation:
twitter → 800,000
twitch → 1,000,000
twilio → 500,000
Về bản chất, đây chỉ là:
query
↓
GROUP BY query
↓
COUNT(*)
Ở quy mô rất lớn, việc này có thể được thực hiện bằng hệ thống xử lý batch/distributed như MapReduce.
Ví dụ:
Raw Logs
│
▼
┌────────────┐
│ Map │
│ query → 1 │
└─────┬──────┘
│
▼
┌────────────┐
│ Reduce │
│ query → N │
└─────┬──────┘
│
▼
Frequency Table
Kết quả cuối cùng là một tập dữ liệu popularity sạch hơn.
🧠 12. Build lại Trie
Bây giờ chúng ta đã có:
twitter → 800,000
twitch → 1,000,000
twilio → 500,000
...
Hệ thống có thể xây dựng một Trie mới.
Trong quá trình build, nó đồng thời tính Top 5 queries cho từng prefix.
Ví dụ:
Prefix "t" → Top 5: twitch
twitter
telegram
tiktok
tesla
Node "t" sẽ lưu danh sách này.
Tương tự:
Prefix "tw" → Top 5: twitch
twitter
twilio
twilight
twitter login
Node "tw" cũng lưu Top 5 riêng.
🧠 13. Làm sao thay Trie mà không làm gián đoạn hệ thống?
Ta không muốn:
Trie đang được sử dụng
↓
Xóa Trie
↓
Build Trie mới
↓
User request → ERROR ❌
Thay vào đó, có thể xây dựng một Trie mới hoàn toàn:
┌──────────────┐
│ Trie v1 │ ← đang phục vụ
└──────────────┘
+
┌──────────────┐
│ Build v2 │
└──────────────┘
Khi Trie v2 hoàn thành:
┌──────────────┐
│ Trie v1 │
└──────────────┘
↓
switch
↓
┌──────────────┐
│ Trie v2 │
└──────────────┘
Sau đó mới giải phóng Trie v1.
Đây là một pattern rất hữu ích:
Build new → Validate → Swap → Remove old
Nó giúp Read Path gần như không bị ảnh hưởng trong quá trình update.
🧠 14. Query Service lúc này đơn giản đến mức nào?
Request:
GET /autocomplete?q=tw
đi qua:
Client
↓
Query Service
↓
Trie Cache
Query Service:
1. Normalize input
2. Traverse Trie
3. Lấy topQueries
4. Filter nếu cần
5. Return
Ví dụ:
{
"query": "tw",
"suggestions": [
"twitch",
"twitter",
"twilio",
"twilight",
"twitter login"
]
}
- Không database query.
- Không SQL.
- Không sorting hàng triệu records.
- Không scan dữ liệu lớn.
🧠 15. Một insight rất quan trọng: Read Path và Write Path không cần cùng tốc độ
Đây là điều người mới học System Design rất dễ bỏ qua.
Chúng ta có thể chấp nhận popularity không hoàn toàn real-time.
Ví dụ thức tế:
10:00 twitter → 800K
10:01 twitter → 850K
10:02 twitter → 900K
Nhưng Trie chỉ được rebuild mỗi 1 hour thì người dùng có thể nhìn thấy dữ liệu cũ trong một khoảng thời gian.
➠ Điều đó có thể chấp nhận được.
Tại sao?
➠ Vì autocomplete không phải hệ thống tài chính.
Nếu twitter vẫn đứng thứ 2 trong vài phút thay vì thứ 1 thì trải nghiệm vẫn ổn.
Đổi lại, chúng ta có:
+ Read latency rất thấp
+ Architecture đơn giản hơn
+ Không lock Trie liên tục
+ Dễ scale
Đây chính là một trade-off.
🧠 16. Thêm Browser Cache
Ta vẫn có thể tối ưu thêm.
Hãy nghĩ xem:
- Một user nhập:
tw - sau đó quay lại:
tw
Tại sao phải gọi server lần nữa?
Browser có thể cache:
"tw" → [ "twitch",
"twitter",
"twilio",
...]
Lần sau:
tw
↓
Browser Cache
↓
Return ngay
Không cần request lên server.
🧠 17. CDN Cache
Không chỉ một user tìm tw.
Có thể hàng triệu user trên toàn thế giới cũng tìm: tw
CDN có thể cache response GET /autocomplete?q=tw và phục vụ trực tiếp từ edge location.
Architecture trở thành:
| ---------------------------------------------------------------------------------------------------- |  |
---------------------------------------------------------------------------------------------------- |
Điều này giúp giảm đáng kể số request thực sự đi đến backend.
🧠 18. Filter — Không phải query nào cũng nên trả về
Đến đây hệ thống đã rất nhanh.
Nhưng vẫn còn một vấn đề:
Popularity không đồng nghĩa với nội dung hợp lệ.
Một query có thể rất phổ biến nhưng chứa:
hate speech
violent content
sexual content
racist content
spam
Nếu đơn giản trả Top 5 từ Trie:
Trie
↓
Top 5
↓
Client
thì có thể vô tình trả nội dung không mong muốn.
Vì vậy thêm một lớp:
Trie Cache
↓
Filter
↓
Query Service
↓
Client
Filter có thể kiểm tra:
Blacklist
Content policy
Blocked terms
Ví dụ:
Trie:
1. good query
2. bad query
3. normal query
4. ...
Sau filter:
1. good query
2. normal query
3. ...
Một lưu ý quan trọng:
Filtering có thể khiến Top 5 trong Trie không còn đủ 5 kết quả hợp lệ.
Vì vậy hệ thống thực tế thường phải lưu nhiều hơn Top 5, chẳng hạn Top 10 hoặc Top 20, rồi filter xuống Top 5.
🧠 19. Toàn bộ kiến trúc sau khi Deep Dive
Sau các optimization, architecture đã trở thành:
🧠 20. Chúng ta đã giải quyết được gì?
Hãy quay lại requirement ban đầu.
Requirement 1 — Prefix Search
tw → twitter, twitch...
→ Trie
Requirement 2 — Top 5 Popular
Top 5
→ Pre-compute Top-K tại mỗi node
Requirement 3 — < 100ms
RAM
+
Pre-computed results
+
Browser Cache
+
CDN
→ Read Path cực nhanh.
Requirement 4 — 14K Peak QPS
Browser Cache
↓
CDN
↓
Multiple Query Servers
↓
Trie Cache
→ Giảm tải và scale horizontally.
Requirement 5 — Popularity thay đổi
Search Events
↓
Logs
↓
Aggregator
↓
Build new Trie
↓
Swap
→ Không cần update Trie trên mỗi search request.
🧠 21. Những insight cần mang vào phòng phỏng vấn
Nếu interviewer hỏi:
"What are the key design decisions?"
Bạn không cần kể lại toàn bộ architecture.
Chỉ cần nói được 4 ý:
① Trie để giải quyết Prefix Search
Prefix → Trie
② Pre-compute Top-K để giải quyết tốc độ
Prefix Node
↓
Top 5 đã tính sẵn
③ Offline/Asynchronous Aggregation để tách Read và Write
Search Event
↓
Log
↓
Aggregate
↓
Build Trie
④ Cache để giảm tải
Browser
↓
CDN
↓
Trie Cache
Đó chính là xương sống của thiết kế.
🧠 Nhưng hệ thống vẫn chưa hoàn hảo...
Hãy tưởng tượng một ngày hệ thống phát triển từ: 10M DAU thành 100M DAU
Trie không còn vừa trong RAM của một server.
Hoặc một prefix như: "t" trở nên cực kỳ hot và nhận hàng triệu request.
Hoặc popularity cần cập nhật: mỗi tuần
→ rồi : mỗi ngày
→ rồi: mỗi giờ
→ rồi: gần real-time
Lúc đó kiến trúc hiện tại bắt đầu xuất hiện những giới hạn mới.
Vậy Trie sẽ được scale như thế nào?
Làm sao đảm bảo High Availability nếu một Trie server chết?
Nên shard theo
a-z, theo prefix hay theo hash?Browser Cache, CDN và Trie Cache nên dùng trong trường hợp nào?
Đó sẽ là nội dung của Phần 3 — Scaling, High Availability và Trade-offs, nơi chúng ta hoàn thiện thiết kế để nó thực sự có thể chạy ở quy mô production.
🔥 Bước 5: Scaling, High Availability và Trade-offs
Ở Phần 1, chúng ta bắt đầu như một buổi System Design Interview:
Requirement
↓
Estimate
↓
High-Level Architecture
Ở Phần 2, chúng ta đi sâu vào vấn đề quan trọng nhất:
Prefix Search
↓
Trie
↓
Pre-compute Top-K
↓
In-memory Query
Nhờ đó, một request như:
GET /autocomplete?q=tw
không cần quét hàng triệu record.
Nhưng thiết kế hiện tại vẫn có một câu hỏi lớn:
Nếu hệ thống lớn hơn 10 triệu DAU thì sao?
Một Trie có thể không còn vừa RAM.
Một server có thể bị chết.
Một prefix có thể trở thành hot prefix với hàng triệu request.
Popularity có thể thay đổi nhanh hơn dự kiến.
Đây chính là lúc chúng ta bước vào phần cuối của System Design Interview:
Trade-offs, Scaling và Production Considerations.
🔥 1. Scale Query Service
Hiện tại ta có:
Client
↓
Query Service
↓
Trie Cache
Nếu chỉ có một Query Server:
┌──────────────┐
│ Query Server │
└──────┬───────┘
│
Trie
thì server đó sẽ trở thành Single Point of Failure.
Server chết:
User
↓
❌ Query Server
↓
Autocomplete chết
Và nếu traffic tăng từ:
14K QPS
lên:
50K QPS
một server cũng khó có thể gánh toàn bộ traffic.
Giải pháp quen thuộc:
Horizontal Scaling.
Load Balancer
│
┌─────────────┼─────────────┐
↓ ↓ ↓
Query Server 1 Query Server 2 Query Server N
│ │ │
↓ ↓ ↓
Trie 1 Trie 2 Trie N
Mỗi Query Server có thể giữ một bản copy của Trie trong RAM.
🔥 2. Tại sao mỗi server có thể giữ một Trie riêng?
Một câu hỏi hợp lý:
"Nếu mỗi server có một Trie thì dữ liệu có bị khác nhau không?"
Có thể có một chút khác biệt về thời điểm cập nhật.
Ví dụ:
Server 1 → Trie v10
Server 2 → Trie v10
Server 3 → Trie v9
Trong vài phút, một số user có thể nhận dữ liệu cũ hơn.
Nhưng với autocomplete, điều này thường không phải vấn đề nghiêm trọng.
Chúng ta không cần consistency tuyệt đối như:
Bank balance
Payment
Inventory
Nếu:
Server 1:
twitter đứng #1
Server 2:
twitter đứng #2
trong một khoảng thời gian ngắn thì trải nghiệm vẫn có thể chấp nhận được.
Đây là một trade-off rất quan trọng:
Autocomplete ưu tiên Availability + Low Latency hơn Strong Consistency.
🔥 3. High Availability
Giả sử có:
Query Server 1
Query Server 2
Query Server 3
Query Server 4
Nếu Server 2 chết:
Load Balancer
/ | \
↓ ↓ ↓
S1 ❌S2 S3
↓
failed
Load Balancer sẽ chuyển request sang server khác.
User gần như không nhận thấy sự cố.
Nhưng còn một vấn đề:
Điều gì xảy ra nếu Trie Cache bị lỗi hoặc dữ liệu Trie bị corrupt?
Ta có thể giữ nhiều version:
Trie v10 ← current
Trie v9 ← fallback
Nếu build Trie v11 thất bại:
Build v11
↓
❌ Failed
↓
Continue using v10
Không được để một lần build lỗi làm toàn bộ autocomplete ngừng hoạt động.
🔥 4. Khi Trie không còn vừa RAM
Đây là vấn đề lớn hơn.
Giả sử chúng ta có:
100 million queries
và mỗi query cần lưu:
String
Frequency
Trie nodes
Top-K suggestions
Metadata
Trie có thể chiếm một lượng RAM rất lớn.
Một server duy nhất có thể không đủ.
Lúc này ta cần:
Trie Sharding.
🔥 5. Sharding Trie theo Prefix
Cách dễ hiểu nhất là chia theo chữ cái đầu tiên.
Ví dụ:
Shard 1 → a-f
Shard 2 → g-l
Shard 3 → m-r
Shard 4 → s-z
Khi user nhập:
tw
ký tự đầu tiên là:
t
→ request được route đến:
Shard 4
Kiến trúc:
Router
│
┌────────────────┼────────────────┐
↓ ↓ ↓
Shard A Shard B Shard C
a-f g-l m-r
...
Đây là cách rất đơn giản để triển khai.
🔥 6. Nhưng Prefix Sharding có vấn đề
Không phải các chữ cái có số lượng query giống nhau.
Ví dụ:
a → 10M queries
q → 2M queries
t → 50M queries
x → 1M queries
Nếu:
Shard 1 → a-f
thì shard này có thể rất lớn.
Đặc biệt:
t
có thể trở thành một hot partition.
Ta gọi đây là:
Hotspot / Hot Shard.
Một shard có thể nhận nhiều traffic hơn rất nhiều shard khác.
🔥 7. Hash-based Sharding
Một giải pháp khác là hash prefix.
Ví dụ:
hash("tw") % N
sẽ quyết định request đi đâu.
"tw" → hash → Shard 7
"go" → hash → Shard 2
"ca" → hash → Shard 5
Điều này giúp phân phối dữ liệu đều hơn.
Nhưng lại xuất hiện một vấn đề:
Các prefix liên quan không còn nằm cùng một shard.
Ví dụ:
tw
twi
twit
twitt
có thể bị phân tán.
Vì vậy router và data placement trở nên phức tạp hơn.
🔥 8. Prefix Sharding vs Hash Sharding
| Prefix Sharding | Hash Sharding | |
|---|---|---|
| Đơn giản | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ |
| Dễ route | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐ |
| Phân phối đều | ⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| Hotspot | Có thể xảy ra | Ít hơn |
| Scale lớn | Khá tốt | Tốt |
| Complexity | Thấp | Cao hơn |
Nếu hệ thống chưa quá lớn:
Prefix sharding thường là lựa chọn đơn giản và dễ vận hành hơn.
Khi quy mô tăng mạnh, hash-based hoặc một chiến lược partitioning phức tạp hơn có thể phù hợp.
🔥 9. Hot Prefix — Một vấn đề rất thực tế
Hãy tưởng tượng một sự kiện lớn xảy ra.
Một người nổi tiếng vừa tung ra một sản phẩm mới:
"iphone"
đột nhiên trở thành query cực kỳ phổ biến.
Hoặc một sự kiện thể thao lớn:
"world cup"
Hàng triệu người cùng gõ.
Một prefix như:
i
có thể nhận traffic khổng lồ.
Ngay cả khi Query Service đã scale horizontally, một số prefix vẫn có thể trở thành hotspot.
🔥 10. CDN giúp giải quyết Hot Prefix
Đây là lý do CDN rất hữu ích.
Request:
GET /autocomplete?q=tw
có thể được cache ở edge.
User
│
▼
CDN
/ \
Cache Hit Cache Miss
│ │
│ ▼
│ Query Service
│ │
│ ▼
│ Trie Cache
│
▼
Response
Nếu:
tw → 1,000,000 requests
nhưng CDN cache được response:
tw → [twitch, twitter, twilio...]
thì phần lớn request không cần đi đến backend.
Đây là một trong những cách hiệu quả nhất để xử lý hot query.
🔥 11. Browser Cache cũng rất quan trọng
Autocomplete có một đặc điểm thú vị:
Người dùng thường gõ prefix theo chuỗi:
t
tw
twi
twit
twitt
Nếu browser đã có:
tw → [...]
thì không cần gọi API lần nữa.
Client có thể cache trong một khoảng thời gian ngắn.
Ví dụ:
Browser Cache
TTL = 1 hour
Không nhất thiết phải quá lâu vì popularity có thể thay đổi.
🔥 12. Data Freshness — Dữ liệu có cần real-time không?
Đây là một câu hỏi interviewer rất thích hỏi:
"How fresh does the data need to be?"
Không có câu trả lời duy nhất.
Option 1 — Rebuild mỗi tuần
Monday
↓
Build Trie
↓
Serve for 7 days
Đơn giản nhưng dữ liệu có thể rất cũ.
Option 2 — Rebuild mỗi ngày
Every 24 hours
↓
Aggregate
↓
Build Trie
Fresh hơn.
Option 3 — Rebuild mỗi giờ
Every hour
↓
Aggregate
↓
Build Trie
Fresh hơn nữa nhưng tốn compute.
Option 4 — Near real-time
Search Event
↓
Stream Processing
↓
Update ranking
Fresh nhất nhưng architecture phức tạp hơn rất nhiều.
🔥 13. Freshness vs Complexity
Đây là trade-off:
Freshness
↑
│ Real-time
│ ●
│
│ Hourly ●
│
│ Daily ●
│
│ Weekly ●
└────────────────────────→
Complexity
Với requirement ban đầu:
Popularity chỉ cần dựa trên tổng số search.
Chúng ta không nhất thiết cần real-time.
Một thiết kế hợp lý có thể là:
Analytics
↓
Daily aggregation
↓
Build Trie
↓
Deploy new Trie
Đơn giản hơn rất nhiều.
🔥 14. Nhưng nếu muốn Trending Search thì sao?
Đây là lúc requirement thay đổi.
Thay vì:
Popularity = total searches
ta có thể muốn:
Trending Score
=
recent searches
+
historical popularity
Ví dụ:
twitter
Total: 1,000,000
Recent: 10,000
new-event
Total: 50,000
Recent: 100,000
Mặc dù new-event có tổng search thấp hơn, nó đang trending.
Khi đó ranking không còn đơn giản là:
ORDER BY frequency DESC
mà có thể là:
score =
historical_score * α
+
recent_score * β
Đây là một bước mở rộng tự nhiên của hệ thống.
🔥 15. Filtering và Moderation
Một autocomplete production không thể chỉ quan tâm:
frequency
Nó còn phải quan tâm:
Is this query safe?
Is this query allowed?
Should this query be shown?
Architecture:
Trie
↓
Candidate Top-K
↓
Filter / Moderation
↓
Top 5 valid results
↓
Client
Và đây là lý do chúng ta có thể lưu:
Top 20
thay vì chỉ:
Top 5
Ví dụ Trie trả:
1. query A
2. query B ❌
3. query C
4. query D ❌
5. query E
6. query F
...
Sau filtering:
A
C
E
F
G
→ lấy 5 kết quả hợp lệ.
🔥 16. Điều gì xảy ra khi Trie Service chết?
Đây là một câu hỏi production rất thực tế.
Giả sử:
Query Service
↓
Trie Cache
↓
❌ unavailable
Chúng ta không muốn:
Autocomplete → toàn bộ hệ thống chết
Có thể thiết kế fallback:
Trie Cache
│
├── Hit → Return
│
└── Miss/Failure
↓
Fallback
↓
Static popular queries
Ví dụ với prefix:
"tw"
hệ thống có thể có một tập dữ liệu fallback chứa các query phổ biến nhất.
Tất nhiên fallback này không đầy đủ, nhưng:
Có kết quả cũ vẫn tốt hơn hoàn toàn không có autocomplete.
🔥 17. Một cải tiến quan trọng: Versioned Trie
Thay vì nói:
Trie Cache
ta có thể nghĩ đến:
Trie v101
Trie v102
Trie v103
Quy trình:
Raw Logs
↓
Aggregator
↓
Build Trie v104
↓
Validate
↓
Publish v104
↓
Servers load v104
↓
Switch traffic
Nếu v104 có lỗi:
❌ v104
Continue serving:
✅ v103
Điều này giúp quá trình cập nhật an toàn hơn rất nhiều.
🔥 18. Kiến trúc hoàn chỉnh
Sau tất cả các bước, ta có thể vẽ hệ thống như sau:
┌──────────────┐
│ Client │
└──────┬───────┘
│
Browser Cache
│
▼
┌────────────┐
│ CDN │
└─────┬──────┘
│
▼
┌──────────────┐
│Load Balancer │
└──────┬───────┘
│
┌────────────────┼────────────────┐
↓ ↓ ↓
Query Server 1 Query Server 2 Query Server N
│ │ │
▼ ▼ ▼
Trie Cache Trie Cache Trie Cache
│ │ │
└────────────────┼────────────────┘
│
Versioned
Trie
───────────────── WRITE PATH ─────────────────
Search Events
│
▼
┌─────────────────┐
│ Analytics Logs │
└────────┬────────┘
│
▼
┌─────────────────┐
│ Aggregator │
│ / MapReduce │
└────────┬────────┘
│
▼
┌─────────────────┐
│ Trie DB │
└────────┬────────┘
│
▼
┌─────────────────┐
│ Build Trie N+1 │
│ + Precompute │
│ Top-K │
└────────┬────────┘
│
▼
Validate
│
▼
Publish Trie
│
▼
Query Servers
🔥 19. Trade-offs — Không có kiến trúc hoàn hảo
Đây là phần cực kỳ quan trọng khi phỏng vấn.
Một ứng viên tốt không chỉ nói:
"Em sẽ dùng Trie."
Mà phải nói:
"Tại sao Trie phù hợp và chúng ta chấp nhận đánh đổi điều gì?"
SQL vs Trie
SQL
Ưu điểm:
+ Đơn giản
+ Dễ triển khai
+ Dễ update
Nhược điểm:
- Không phù hợp với cực nhiều read
- Ranking theo prefix có thể expensive
- Khó đạt latency thấp ở quy mô lớn
Trie
Ưu điểm:
+ Prefix search rất nhanh
+ In-memory
+ Pre-compute Top-K
+ Latency thấp
Nhược điểm:
- Tốn RAM
- Build phức tạp hơn
- Update khó hơn
- Cần strategy để scale
🔥 20. Real-time Update vs Batch Update
Real-time
Search
↓
Update Trie
Ưu điểm:
Popularity cực fresh
Nhược điểm:
Concurrency
Lock
Complexity
CPU
Batch
Search
↓
Log
↓
Aggregate
↓
Build Trie
Ưu điểm:
Đơn giản
Ổn định
Read Path cực nhanh
Nhược điểm:
Dữ liệu có thể stale
Với autocomplete:
Batch update thường là lựa chọn hợp lý hơn nếu requirement không yêu cầu real-time.
🔥 21. Memory vs Performance
Pre-compute Top-K ở mỗi node giúp query rất nhanh.
Nhưng đổi lại:
Performance ↑
Memory ↑
Nếu mỗi node lưu:
Top 5
thì số lượng dữ liệu bổ sung có thể rất lớn.
Đây là trade-off:
Chúng ta dùng thêm RAM để mua latency thấp hơn.
Đây là một pattern xuất hiện rất nhiều trong System Design:
More Memory
↓
Less Computation
↓
Lower Latency
🔥 22. Nếu interviewer hỏi: "Tại sao không dùng Elasticsearch?"
Một câu trả lời tốt không phải:
"Elasticsearch chậm."
Mà nên là:
"Elasticsearch có thể giải quyết prefix search và là một lựa chọn hợp lý ở nhiều quy mô. Tuy nhiên, với requirement latency rất thấp và chỉ cần Top-K prefix suggestions, một Trie được pre-compute hoàn toàn trong memory cho phép chúng ta tối ưu Read Path tốt hơn và predictable hơn."
Quan trọng nhất là:
Không có công nghệ nào luôn tốt nhất. Requirement quyết định architecture.
🔥 23. Nếu interviewer hỏi: "Tại sao không Redis?"
Redis rất phù hợp cho caching.
Ví dụ:
"tw" → ["twitch", "twitter", ...]
Ta hoàn toàn có thể lưu những kết quả phổ biến vào Redis.
Nhưng nếu có hàng triệu prefix:
t
tw
twi
twit
...
thì việc lưu toàn bộ mapping:
prefix → Top-K
cũng tiêu tốn rất nhiều memory.
Trie có lợi thế:
Các prefix dùng chung cấu trúc dữ liệu.
Ví dụ:
t
└── w
└── i
└── t
Không cần lưu mỗi prefix như một key độc lập.
🔥 24. Cách trả lời bài này trong phòng phỏng vấn
Nếu chỉ có khoảng 30 phút, bạn không cần kể tất cả mọi thứ.
Có thể trình bày theo flow:
1️⃣ Clarify Requirements
Prefix matching
Top 5
Popularity-based
< 100ms
10M DAU
2️⃣ Estimate
100M searches/day
600M autocomplete requests/day
~7K average QPS
~14K peak QPS
3️⃣ High-Level Design
Client
↓
CDN
↓
Query Service
↓
Trie Cache
và:
Search Events
↓
Logs
↓
Aggregator
↓
Trie DB
↓
Build Trie
4️⃣ Deep Dive
Giải thích:
SQL
↓
Không scale tốt
Trie
↓
Prefix search
Pre-compute Top-K
↓
Fast read
5️⃣ Scaling
Horizontal scaling
+
CDN
+
Browser cache
+
Trie sharding
+
Versioned deployment
6️⃣ Trade-offs
Freshness vs Complexity
Memory vs Performance
Consistency vs Availability
Prefix Sharding vs Hash Sharding
Đây là flow rất đẹp để interviewer thấy rằng bạn đang giải quyết vấn đề từng bước, thay vì học thuộc một architecture có sẵn.
🔥 25. Tổng kết — 5 ý tưởng cần nhớ
Nếu chỉ được nhớ 5 điều từ bài System Design này, hãy nhớ:
① Requirement quyết định architecture
Đừng bắt đầu bằng:
Redis!
Kafka!
Elasticsearch!
Kubernetes!
Hãy bắt đầu bằng:
User cần gì?
Latency bao nhiêu?
Traffic bao nhiêu?
Data thay đổi thế nào?
② Prefix Search → Trie
Khi bài toán là:
"Find strings starting with X"
hãy nghĩ đến:
Trie
③ Latency thấp → Pre-compute
Đừng để request phải tính lại một thứ mà hệ thống đã biết.
Thay:
Request
↓
Scan
↓
Sort
↓
Top 5
bằng:
Build time
↓
Pre-compute Top 5
Request
↓
Read Top 5
Đây là insight quan trọng nhất của bài.
④ Read-heavy system → Tách Read và Write
Read
↓
RAM
↓
Fast
Write
↓
Log
↓
Batch
↓
Rebuild
Không nhất thiết mọi dữ liệu phải được cập nhật real-time.
⑤ Scale bằng Cache + Replication + Sharding
Khi hệ thống lớn:
Browser Cache
↓
CDN
↓
Load Balancer
↓
Multiple Query Servers
↓
Trie Cache
↓
Sharding nếu cần
🏁 Kết luận
Search Autocomplete nhìn bên ngoài chỉ là một ô input nhỏ:
┌────────────────────────────┐
│ tw │
├────────────────────────────┤
│ twitch │
│ twitter │
│ twilio │
│ twilight │
│ twitter login │
└────────────────────────────┘
Nhưng phía sau nó là một hệ thống phải giải quyết đồng thời:
Millions of users
↓
Thousands of QPS
↓
Prefix search
↓
Ranking
↓
Low latency
↓
Large dataset
↓
Frequent updates
↓
High availability
Và cách chúng ta giải quyết không phải bằng một công nghệ thần kỳ, mà bằng việc liên tục đặt câu hỏi:
"Vấn đề lớn nhất ở bước này là gì?"
Sau đó mới chọn giải pháp.
SQL quá chậm
↓
Trie
Trie traversal quá tốn thời gian
↓
Pre-compute Top-K
Update Trie gây ảnh hưởng Read
↓
Async / Batch Processing
Một server không đủ
↓
Horizontal Scaling
Traffic quá lớn
↓
Browser Cache + CDN
Trie không vừa RAM
↓
Sharding
Update Trie gây rủi ro
↓
Versioned Trie + Atomic Swap
Đó mới chính là tư duy System Design.
Không phải:
"Tôi biết Trie, nên tôi dùng Trie."
Mà là:
"Requirement này tạo ra bottleneck X → vì vậy tôi chọn giải pháp Y → đổi lại tôi chấp nhận trade-off Z."
Và đó cũng là cách bạn nên trình bày một bài System Design trong phòng phỏng vấn.
🏁 Tóm tắt
Đến đây, chúng ta đã đi đúng 3 bước đầu tiên của một buổi System Design Interview:
① Hiểu yêu cầu
Prefix matching
Top 5
Popularity-based
P95 < 100ms
② Ước lượng
10M DAU
↓
100M searches/day
↓
600M autocomplete requests/day
↓
~7K average QPS
↓
~14K peak QPS
③ High-Level Design
Tách hệ thống thành:
READ PATH
User
↓
Cache
↓
Query Service
↓
Trie Cache
WRITE PATH
Search Event
↓
Logs
↓
Aggregator
↓
Trie DB
↓
Trie Cache
All rights reserved
