Top K video xem nhiều
Hiểu đề
Yêu cầu chức năng
- Hệ thống ghi nhận mỗi lượt xem hợp lệ của một video
- Người dùng xem được top K video (K ≤ 1.000) trong cửa sổ 1 giờ, 1 ngày và mọi thời đại
- Người dùng lọc được bảng xếp hạng theo quốc gia
- Người dùng xem được tổng lượt xem của một video
Yêu cầu phi chức năng
- Bảng xếp hạng trễ tối đa 1 phút so với lượt xem thực tế
- Truy vấn top K p95 < 100 ms, sẵn sàng 99,9%
- Chịu được ≈ 174.000 lượt xem/s lúc đỉnh mà không làm chậm trình phát video
- Số đếm trong top K lệch < 0,1% so với kết quả đối soát batch cuối ngày
Ngoài phạm vi: Thuật toán xu hướng có trọng số (độ mới, tốc độ tăng, đa dạng nội dung); Cá nhân hóa bảng xếp hạng theo từng người; Mô hình phát hiện view giả chi tiết (chỉ nhắc ở mức lọc cơ bản); Cửa sổ tùy ý do người dùng chọn.
Thực thể và API
| Method | Endpoint | Ghi chú |
|---|---|---|
| POST | /v1/views | Body {videoId, sessionId, watchedSec}. Trả 202 ngay, đếm bất đồng bộ. Player có thể gửi theo lô. |
| GET | /v1/top?window=1h|1d|all&country=VN&k=100 | Đọc danh sách đã tính sẵn, cache CDN 30 s. Trả kèm generated_at. |
| GET | /v1/videos/{id}/views | Tổng lượt xem, chấp nhận trễ vài phút. |
Thiết kế tổng thể
Đi lần lượt từng yêu cầu chức năng. Mục tiêu ở đây là chạy đúng, việc tối ưu để dành cho phần đào sâu.
1) Hệ thống ghi nhận mỗi lượt xem
Lượt xem chỉ cần ghi lại, người xem không chờ kết quả. API nhận sự kiện rồi đẩy vào hàng đợi, phần đếm chạy phía sau nên có thể gộp nhiều lượt xem của cùng một video thành một lần ghi.
- 1Player gửi POST /v1/views khi người dùng xem đủ 30 s
- 2API kiểm tra cơ bản (session hợp lệ, chặn lặp cùng session trong 1 phút), trả 202
- 3API đẩy ViewEvent vào queue (Pub/Sub ở mức vừa, Kafka ở mức lớn) theo key video_id
- 4Worker hoặc Flink gộp số đếm theo video trong vài giây rồi cộng vào các ô phút và ô giờ
Nguồn: Grokking Modern System Design · ch.17 Distributed Messaging Queue ↗ · bài "Design of a Distributed Messaging Queue" (producer ghi vào queue, consumer xử lý sau) ; Grokking Modern System Design · ch.24 Sharded Counters ↗ · mục "Detailed design", "Burst of writes requests" ; Chưa có nguồn trong thư viện: thư viện không có sách về Flink/Kafka; chỉ nêu khái niệm cơ bản
2) Người dùng xem top K theo cửa sổ 1 giờ, 1 ngày, mọi thời đại
Không tính lại top K mỗi lần có người hỏi. Tầng đếm giữ số đếm theo cửa sổ trượt và định kỳ (10-60 s) xuất ra danh sách top K cho từng cửa sổ và quốc gia. API chỉ đọc danh sách có sẵn.
- 1Mỗi phút, tầng đếm cộng ô mới nhất và trừ ô vừa hết hạn cho cửa sổ 1h (ô phút) và 1d (ô giờ)
- 2Tầng đếm chọn K video lớn nhất bằng min-heap kích thước K và ghi TopKList vào Redis
- 3Client gọi GET /v1/top, CDN trả cache 30 s; hết hạn thì API đọc một key Redis và trả về
- 4Mọi thời đại: tổng lượt xem lưu ở DB, danh sách top cập nhật theo giờ
Nguồn: Grokking Modern System Design · ch.24 Sharded Counters ↗ · mục "Using sharded counters for the Top K" ; Redis in Action ↗ · ch.5 · §5.2.1 Storing counters in Redis (bộ đếm theo nhiều độ phân giải) ; Redis in Action ↗ · ch.3 · §3.5 Sorted sets
3) Người dùng lọc theo quốc gia
Quốc gia là một chiều thêm vào khóa đếm. Đếm theo (video, quốc gia) rồi cộng lên toàn cầu, nên mỗi cặp cửa sổ và quốc gia có một TopKList riêng.
- 1ViewEvent mang mã quốc gia lấy từ IP hoặc tài khoản
- 2Tầng đếm giữ số đếm theo (video_id, country) và tổng toàn cầu
- 3Xuất 3 cửa sổ × số quốc gia danh sách top K, mỗi danh sách là một key
Nguồn: Grokking Modern System Design · ch.24 Sharded Counters ↗ · mục "Using sharded counters for the Top K" (Location-based) ; Redis in Action ↗ · ch.5 · §5.2.2 Storing statistics in Redis
Hạ tầng theo quy mô
Cùng một sản phẩm, ba mức người dùng. Chọn từng mức để xem sơ đồ, phép tính và cấu hình server thay đổi thế nào.
Một nền tảng video nội bộ hoặc ngách. Postgres đếm theo ô giờ bằng UPSERT, một cron mỗi phút tính top K và lưu lại, API đọc kết quả đó.
Ước lượng
- Lượt xem: 10.000 DAU × 10 = 100.000 / 86.400 ≈ 1,2 lượt/s, đỉnh ×10 ≈ 12 lượt/s
- Đọc bảng xếp hạng: 10.000 × 5 lượt / 86.400 ≈ 0,6 req/s, đỉnh ×10 ≈ 6 req/s
- API: ceil((12 + 6) / 600) = 1 → chạy 2 instance để dự phòng
- Bảng đếm theo giờ: ≤ 2.000 video có view mỗi giờ × 24 × 365 = 17.520.000 hàng × 40 B ≈ 700 MB/năm
- Top 1 ngày: SUM trên 24 × 2.000 = 48.000 hàng, chạy mỗi phút chỉ mất vài chục ms
Nguồn con số: Grokking Modern System Design · ch.5 Back-of-the-envelope Calculations ↗ · mục "Requests estimation", "Storage requirements" ; Quy tắc ước lượng của khoá học · /hoc/chon-server (600 req/s mỗi instance, 60% CPU, Redis ×1,3, năng lực Kafka/Flink là giả định của khoá học, cần load test)
Bảng hạ tầng
| Thành phần | Chọn | Số lượng | Cấu hình | Vì sao |
|---|---|---|---|---|
| CDN | Cloudflare | 1 | Cache GET /v1/top 60 s | Gần như miễn phí, đỡ hết lượt đọc lặp lại. |
| API | Node.js (NestJS) trên Cloud Run | 2 | 2 vCPU · 4 GB RAM | 18 req/s chỉ cần 1 instance, chạy 2 cho dự phòng. |
| Database | PostgreSQL managed | 1 | 2 vCPU · 8 GB · 50 GB SSD | 12 UPSERT/s vào bảng (video_id, hour) là rất nhẹ, 700 MB/năm vừa RAM. |
| Tính top K | Cron (Cloud Scheduler) gọi API mỗi phút | 1 | Chạy trong API | Tính 1h, 1d, all rồi lưu vào bảng top_k_cache, API chỉ đọc bảng này. |
- Điểm xuất phát: một API, một Postgres, đếm đồng bộ ngay trong request
- Cửa sổ là các ô giờ, top K tính lại mỗi phút và lưu thành bảng kết quả
Khi lượt xem lên hàng nghìn mỗi giây, mỗi lượt là một UPSERT vào hàng của video hot nên khóa hàng tranh chấp, và truy vấn SUM 24 giờ quét hàng triệu hàng mỗi phút.
Cấu hình và chi phí là ước lượng để học và trình bày trong phỏng vấn. Xem cách tính ở bài Chọn server.
So sánh nhanh ba mức
| Thành phần | Mức 1 | Mức 2 | Mức 3 |
|---|---|---|---|
| Người dùng | 10.000 DAU, 100.000 lượt xem/ngày | 1 triệu DAU, 20 triệu lượt xem/ngày, 2 triệu video | 100 triệu DAU, 5 tỷ lượt xem/ngày, 200 quốc gia |
| Chi phí | ≈ 30–80 USD/tháng (ước lượng) | ≈ 800–2.000 USD/tháng (ước lượng) | ≈ 35.000–80.000 USD/tháng (ước lượng) |
| CDN | Cloudflare 1 × Cache GET /v1/top 60 s | Cloudflare / CloudFront 1 × Cache /v1/top 30 s | CloudFront / Cloudflare 1 × Cache /v1/top 30 s theo quốc gia |
| API | Node.js (NestJS) trên Cloud Run 2 × 2 vCPU · 4 GB RAM | Node.js, container autoscale 3–6 (autoscale) × 2 vCPU · 4 GB RAM | Chưa cần |
| Database | PostgreSQL managed 1 × 2 vCPU · 8 GB · 50 GB SSD | PostgreSQL managed 1 primary + 1 replica × 4 vCPU · 16 GB · 200 GB SSD | Chưa cần |
| Tính top K | Cron (Cloud Scheduler) gọi API mỗi phút 1 × Chạy trong API | Chưa cần | Chưa cần |
| Queue | Chưa cần | Google Pub/Sub / Amazon SQS 1 × Managed, có dead-letter | Chưa cần |
| Worker đếm | Chưa cần | Node.js consumer 2 × 1 vCPU · 2 GB RAM | Chưa cần |
| Redis | Chưa cần | ElastiCache / Memorystore 1 primary + 1 replica × 2 vCPU · 8 GB | Chưa cần |
| Ingest API | Chưa cần | Chưa cần | Node.js trên Kubernetes, 3 AZ 290 pod (HPA) × 2 vCPU · 4 GB mỗi pod |
| Kafka | Chưa cần | Chưa cần | MSK / Confluent 6 broker × Topic views 48 partition, RF 3, 4 TB mỗi broker |
| Flink | Chưa cần | Chưa cần | Flink trên Kubernetes, RocksDB state 8 TaskManager × 4 vCPU · 16 GB mỗi TM |
| Redis Cluster | Chưa cần | Chưa cần | ElastiCache Redis Cluster 3 shard × (1 primary + 1 replica) × 2 vCPU · 8 GB mỗi node |
| Top K API | Chưa cần | Chưa cần | Node.js trên Kubernetes 3 pod × 2 vCPU · 4 GB mỗi pod |
| Cassandra | Chưa cần | Chưa cần | Cassandra / ScyllaDB 6 node (2 mỗi AZ) × 8 vCPU · 32 GB · 1 TB SSD |
| Data lake + batch | Chưa cần | Chưa cần | S3 + Spark (EMR) hàng đêm 1 cụm theo lịch × 1 TB/ngày thô, Parquet nén |
Đào sâu
Mỗi câu hỏi đi từ cách đơn giản đến cách người phỏng vấn mong đợi ở cấp senior.
1) Đếm lượt xem thế nào khi một video viral nhận hàng chục nghìn lượt xem mỗi giây?
Mỗi lượt xem là một lần ghi vào cùng một hàng. Video viral biến hàng đó thành điểm nóng: các transaction xếp hàng chờ khóa hàng, thời gian chờ tăng nhanh hơn số request.
Đánh đổi: Đơn giản và chính xác ở vài chục lượt/s, sập đúng lúc video được quan tâm nhất.
Nguồn: Grokking Modern System Design · ch.24 Sharded Counters ↗ · mục "Problem statement" (lock contention tăng phi tuyến khi nhiều ghi trên một biến đếm)
Mỗi lượt xem cộng vào một shard chọn ngẫu nhiên, đọc thì cộng tổng các shard. Đây là cách Grokking ch.24 giải bài heavy hitters cho like và view. Số shard tăng theo độ nóng của video, ví dụ kênh nhiều người theo dõi được nhiều shard từ đầu.
Đánh đổi: Hết tranh chấp khóa nhưng vẫn là một lần ghi cho mỗi lượt xem, và đọc chậm dần khi số shard lớn.
Nguồn: Grokking Modern System Design · ch.24 Sharded Counters ↗ · mục "High-level solution sketch", "Detailed design" (số shard phụ thuộc nhiều yếu tố), "Round-robin selection", "Random selection"
Sự kiện vào Kafka theo key video_id. Mỗi instance đếm trong RAM theo video trong 5-10 s rồi phát ra một bản ghi (video_id, +N). Video có 50.000 lượt/s chỉ tạo một lần ghi mỗi 10 s. Để tránh một partition gánh hết video hot, gộp hai tầng: tầng 1 theo (video_id, salt 0..7), tầng 2 cộng 8 phần lại.
Đánh đổi: Số đếm trễ thêm 5-10 s và phải có checkpoint, nếu không instance chết sẽ mất phần đang đếm trong RAM.
Nguồn: Grokking Modern System Design · ch.24 Sharded Counters ↗ · mục "Burst of writes requests" ; Grokking Modern System Design · ch.17 Distributed Messaging Queue ↗ · mục "Strict ordering" ; Chưa có nguồn trong thư viện: gộp hai tầng với salt và checkpoint của Flink
2) Cửa sổ trượt 1 giờ, 1 ngày và mọi thời đại tính thế nào cho rẻ?
Mỗi truy vấn quét hàng triệu tới hàng tỷ dòng rồi GROUP BY video. Cửa sổ 1 ngày ở mức 5 tỷ lượt xem/ngày thì không thể trả lời trong vài giây.
Đánh đổi: Chính xác tuyệt đối, chi phí đọc tỉ lệ với số lượt xem.
Nguồn: Redis in Action ↗ · ch.5 · §5.2 Counters and statistics (so sánh với đọc trực tiếp từ log sự kiện) ; Chưa có nguồn trong thư viện: chi phí COUNT trên 5 tỷ dòng là ước lượng của khoá học
Mỗi video có số đếm theo ô phút và ô giờ, giống bộ đếm nhiều độ phân giải trong Redis in Action §5.2. Cửa sổ 1h là tổng 60 ô phút, 1d là tổng 24 ô giờ. Ô cũ tự hết hạn.
Đánh đổi: Rẻ hơn nhiều, nhưng tính top K vẫn phải cộng 24 ô cho mọi video, ví dụ ZUNIONSTORE 24 sorted set lớn sẽ khóa Redis vài giây.
Nguồn: Redis in Action ↗ · ch.5 · §5.2.1 Storing counters in Redis (đếm theo độ phân giải thời gian 1 phút/5 phút/1 giờ, tự xóa bộ đếm cũ) ; Redis in Action ↗ · ch.3 · §3.5 Sorted sets (ZUNIONSTORE)
Ngoài các ô, giữ thêm một số đếm cuộn cho mỗi cửa sổ. Lượt xem mới cộng thẳng vào cả ô hiện tại và số cuộn. Khi một ô rời khỏi cửa sổ, trừ ô đó khỏi số cuộn rồi xóa video có số 0. Ở mức lớn, Flink giữ việc này trong keyed state theo video. Mọi thời đại thì chỉ cộng dồn vào DB và tính top theo giờ, vì bảng này đổi rất chậm.
Đánh đổi: Độ mịn của cửa sổ bằng kích thước ô (1h trượt theo phút, 1d trượt theo giờ), và việc trừ ô phải làm từng lô để không khóa Redis.
Nguồn: Redis in Action ↗ · ch.5 · §5.2.1 Storing counters in Redis (cleaning out old counters) ; Chưa có nguồn trong thư viện: thư viện không có sách về Flink/Kafka; chỉ nêu khái niệm cơ bản (keyed state)
3) Tìm K video lớn nhất trong hàng trăm triệu video: đếm chính xác hay xấp xỉ?
100 triệu video hoạt động mỗi ngày với vài chục byte mỗi mục là vài GB RAM trên một máy, và sort toàn bộ mỗi phút tốn thời gian. Máy đó còn là điểm chết duy nhất.
Đánh đổi: Dễ viết, không mở rộng được và không chịu lỗi.
Nguồn: Grokking Modern System Design · ch.5 Back-of-the-envelope Calculations ↗ · mục "Storage requirements" ; Grokking Modern System Design · ch.24 Sharded Counters ↗ · mục "Using sharded counters for the Top K"
Sketch gồm d hàng × w cột, mỗi lượt xem tăng d ô, ước lượng lấy giá trị nhỏ nhất. Với ε = 0,00001 thì w = ⌈e/ε⌉ = 271.829, với δ = 0,001 thì d = ⌈ln(1/δ)⌉ = 7, tổng ≈ 1,9 triệu ô × 4 B ≈ 7,6 MB. Sai số đếm dư tối đa ε × N = 50.000 lượt trên 5 tỷ lượt/ngày. Heap giữ K video có ước lượng lớn nhất.
Đánh đổi: Bộ nhớ cố định và gộp được giữa các máy, nhưng chỉ đếm dư (không đếm thiếu) và không trừ ô hết hạn được, cửa sổ trượt phải dùng nhiều sketch.
Nguồn: Lý thuyết · Count-Min Sketch: bảng d hàng × w cột, mỗi phần tử băm vào mỗi hàng và tăng một ô; ước lượng là giá trị nhỏ nhất trong d ô, không bao giờ thấp hơn thực tế. Sai số cộng thêm không quá ε × N với xác suất ít nhất 1 − δ khi w = ⌈e/ε⌉ và d = ⌈ln(1/δ)⌉; ví dụ ε = 0,001, δ = 0,01 cho w = 2.719, d = 5, khoảng 54 KB ; Redis in Action ↗ · ch.3 · §3.5 Sorted sets (top K bằng sorted set thay thế)
Kafka chia theo video_id nên mỗi subtask Flink sở hữu một phần video và đếm chính xác trong RocksDB state. Mỗi subtask tự tìm top K của phần mình bằng min-heap, rồi một operator gộp 48 danh sách × 1.000 thành top 1.000 toàn cầu. Kết quả đúng vì video nào thuộc top toàn cầu cũng nằm trong top của partition chứa nó. Count-Min Sketch vẫn có chỗ ở rìa mạng hoặc cho thống kê phụ cần ít bộ nhớ.
Đánh đổi: Tốn state hơn sketch (vài chục GB trên đĩa RocksDB) và phải vận hành Flink, đổi lại số đếm khớp với đối soát.
Nguồn: Grokking Modern System Design · ch.24 Sharded Counters ↗ · mục "Using sharded counters for the Top K" (Top K tính từ các shard rồi gộp) ; Grokking Modern System Design · ch.17 Distributed Messaging Queue ↗ · mục "Strict ordering" ; Chưa có nguồn trong thư viện: thư viện không có sách về Flink/Kafka; chỉ nêu khái niệm cơ bản
4) Trả bảng xếp hạng cho hàng chục nghìn request mỗi giây với p95 < 100 ms?
Mỗi request chạy truy vấn gộp trên bảng đếm. Cùng một kết quả bị tính lại hàng nghìn lần mỗi giây trong khi nó chỉ đổi mỗi phút.
Đánh đổi: Không có dữ liệu cũ nhưng DB sập ngay khi trang chủ gọi API này.
Nguồn: Grokking Modern System Design · ch.24 Sharded Counters ↗ · mục "Using sharded counters for the Top K" (Top K đọc từ số đã tính sẵn) ; Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Writing policies"
Request đầu tính và ghi cache, các request sau đọc cache. Đủ cho mức vừa.
Đánh đổi: Khi cache hết hạn, nhiều request cùng tính lại (cache stampede), và thời gian trả lời lúc miss vẫn chậm.
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Writing policies", "Cache invalidation" ; Redis in Action ↗ · ch.2 · §2.3 Web page caching
Mỗi 10-30 s, job đếm ghi danh sách mới vào key có phiên bản rồi đổi con trỏ sang key đó, người đọc không bao giờ thấy danh sách viết dở. API chỉ làm một lệnh GET, CDN cache 30 s nên phần lớn request không tới origin. Chi tiết video (tiêu đề, ảnh) lấy từ cache riêng.
Đánh đổi: Dữ liệu cũ tối đa khoảng 1 phút, và số danh sách tăng theo số chiều lọc nên phải giới hạn các tổ hợp được hỗ trợ.
Nguồn: Grokking Modern System Design · ch.16 Distributed Cache ↗ · mục "Cache invalidation" ; Grokking Modern System Design · ch.11 Content Delivery Network (CDN) ↗ · mục "Time-to-live (TTL)" ; Redis in Action ↗ · ch.5 · §5.2.1 Storing counters in Redis
Trong phỏng vấn
- “Ghi và đọc tách hẳn: lượt xem đi qua Kafka và được gộp trước, bảng xếp hạng là kết quả tính sẵn mỗi 10-30 s.”
- “Cửa sổ trượt dùng ô thời gian cộng bộ đếm cuộn: cộng ô mới, trừ ô hết hạn, độ mịn bằng kích thước ô.”
- “Tôi chọn đếm chính xác chia theo video_id trong Flink, top K cục bộ rồi gộp; Count-Min Sketch là phương án khi cần bộ nhớ cố định và chấp nhận đếm dư.”
- “Video viral là hot key nên gộp hai tầng với salt, và có đối soát batch để biết số stream lệch bao nhiêu.”
- UPDATE cộng 1 vào một hàng cho mỗi lượt xem.
- Tính top K ngay khi có request thay vì tính sẵn.
- Dùng ZUNIONSTORE trên hàng chục sorted set lớn mỗi phút và khóa Redis.
- Nói dùng Count-Min Sketch mà không nêu được sai số đếm dư và việc khó trừ cửa sổ.
Đọc thêm
Sách trong thư viện của bạn. Số chương có thể lệch nhẹ so với bản PDF.