Web crawler
Hiểu đề
Yêu cầu chức năng
- Hệ thống crawl bắt đầu từ danh sách seed URL và đi theo link để tìm trang mới
- Hệ thống lưu HTML và metadata của mỗi trang vào blob store cho hệ thống index
- Hệ thống crawl lại định kỳ theo tần suất thay đổi của trang (tin tức vài phút, trang thường 2 tuần)
- Hệ thống tuân thủ robots.txt và giới hạn tốc độ riêng cho từng domain
Yêu cầu phi chức năng
- Quy mô lớn: 5 tỷ trang/ngày, tức ≈ 58.000 trang/s
- Lịch sự: mặc định tối đa 1 request/s và 1 kết nối đồng thời tới mỗi host, hoặc theo Crawl-delay
- Không tải lại URL đã biết: < 1% lượt tải là URL trùng
- Worker chết không mất URL: URL đang xử lý quay lại hàng đợi sau tối đa 10 phút
- Thêm hoặc bớt máy mà không dừng hệ thống, chỉ dời khoảng 1/N số domain
Ngoài phạm vi: Index, xếp hạng (PageRank) và phục vụ kết quả tìm kiếm; Render JavaScript bằng trình duyệt headless (chỉ nhắc như một module mở rộng); Tải ảnh, video và các định dạng ngoài HTML; Crawl phần web cần đăng nhập.
Thực thể và API
| Method | Endpoint | Ghi chú |
|---|---|---|
| POST | /v1/seeds | API nội bộ cho quản trị viên: thêm danh sách seed URL kèm priority. |
| PUT | /v1/domains/{domain}/policy | Ghi đè tốc độ, số trang tối đa, chặn domain (ví dụ khi chủ site phàn nàn). |
| GET | /v1/urls/{urlHash} | Trạng thái một URL: lần tải cuối, lần tải tới, content_hash. |
| GET | /v1/domains/{domain}/stats | Số trang đã tải, tỉ lệ lỗi, TTFB trung bình để theo dõi. |
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 crawl từ seed và đi theo link
URL frontier quyết định URL nào được tải tiếp theo, vừa theo độ ưu tiên vừa theo luật lịch sự của từng domain. Fetcher chỉ nhận URL đã đến lượt, tra DNS qua cache rồi tải trang.
- 1Seed URL được chuẩn hóa, hash và ghi vào bảng Url với next_fetch_at = now
- 2Frontier xếp URL vào hàng riêng của từng domain, chỉ nhả URL của domain khi đã qua next_allowed_at
- 3Fetcher kiểm tra luật robots.txt đã cache, tra IP qua DNS cache
- 4Fetcher tải trang với timeout 10-30 s và giới hạn kích thước, rồi báo lại frontier để đặt next_allowed_at mới
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design of a Web Crawler" · mục "Components" (scheduler với URL frontier là priority queue và RDB, HTML fetcher, DNS resolver), mục "How does the crawler handle URLs with variable priorities?" (tôn trọng robots.txt, hàng đợi riêng theo độ ưu tiên) ; Chưa có nguồn trong thư viện: next_allowed_at theo domain và timeout 10-30 s là thiết kế của khoá học
2) Hệ thống lưu nội dung và trích link mới
Tách tải và phân tích: fetcher ghi HTML nén vào blob store rồi phát sự kiện, parser trích link và nội dung. Mọi link và nội dung đều qua lọc trùng trước khi đi tiếp, đúng như hai bước kiểm tra checksum URL và checksum tài liệu trong Grokking ch.35.
- 1Fetcher gom nhiều trang vào một file WARC nén trên S3, ghi Page với offset
- 2Parser đọc trang, tính content_hash; nội dung trùng thì chỉ ghi nhận URL trỏ tới bản đã có
- 3Parser trích link, chuẩn hóa (bỏ fragment, sắp tham số, bỏ tham số tracking), lọc bẫy crawler
- 4Link mới đi tới frontier của domain đó, qua Bloom filter, URL chưa thấy mới được ghi vào bảng Url
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design of a Web Crawler" · mục "Duplicate eliminator" (checksum URL và checksum tài liệu), mục "Workflow" ; Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design Improvements" (Extractor, blob store lưu nội dung) ; Chưa có nguồn trong thư viện: định dạng WARC
3) Hệ thống crawl lại định kỳ
Sau mỗi lần tải, next_fetch_at được tính lại theo mức độ thay đổi: nội dung đổi thì rút ngắn chu kỳ, không đổi thì kéo dài. Frontier định kỳ nạp các URL đã đến hạn từ bảng Url.
- 1So content_hash mới với lần trước để biết trang có đổi không
- 2Đổi thì chia đôi chu kỳ (tối thiểu vài phút cho trang tin), không đổi thì nhân đôi (tối đa vài tuần)
- 3Job nạp lại quét URL có next_fetch_at ≤ now theo từng phân vùng domain và đẩy vào frontier
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design of a Web Crawler" · mục "URLs and recrawling" (revisit mặc định hai tuần, trang tin 5 phút theo dự đoán thay đổi) ; quy tắc chia đôi/nhân đôi chu kỳ là giả định của khoá học
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.
Crawler không có đỉnh tải theo người dùng, tốc độ do ta đặt. Hai fetcher Node và một Postgres vừa làm hàng đợi vừa lọc trùng là đủ; HTML nén lên S3.
Ước lượng
- Crawl: 1.000.000 trang / 86.400 ≈ 11,6 trang/s
- Fetcher: 1 instance 2 vCPU giữ ~200 kết nối, ~2 s/trang ≈ 100 trang/s; ceil(11,6 / (100 × 0,6)) = 1 → chạy 2
- Băng thông: 11,6 × 100 KB ≈ 1,16 MB/s ≈ 9,3 Mbps
- Link: 11,6 × 50 link/trang ≈ 580 link/s, INSERT theo lô ON CONFLICT DO NOTHING
- Bảng Url: 10.000.000 URL × 300 B (hàng + index) ≈ 3 GB, vừa RAM của Postgres 8 GB
- Lưu: 1.000.000 × 20 KB (100 KB nén ~5 lần) = 20 GB/ngày, giữ 30 ngày ≈ 600 GB trên S3
Nguồn con số: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Requirements of a Web Crawler's Design" · mục "Resource estimation" (9,5 năm cho một server, storage, bandwidth, số server) ; Grokking Modern System Design · ch.5 Back-of-the-envelope Calculations ↗ · mục "Requests estimation" ; Quy tắc ước lượng của khoá học · /hoc/chon-server (60% CPU, Redis ×1,3, năng lực Kafka 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 |
|---|---|---|---|---|
| Fetcher + parser | Node.js (undici, cheerio), Docker | 2 | 2 vCPU · 4 GB RAM | 11,6 trang/s chỉ cần 1 instance, chạy 2 để dự phòng; tải và phân tích chung một tiến trình. |
| Database (frontier + Url) | PostgreSQL managed | 1 | 2 vCPU · 8 GB · 100 GB SSD | Lấy việc bằng SKIP LOCKED theo next_allowed_at của domain, 580 link/s insert theo lô là nhẹ. |
| Blob store | S3 / GCS | 1 | ≈ 600 GB, vòng đời 30 ngày | Không lưu HTML trong DB; gom 1.000 trang mỗi file để giảm số request PUT. |
| Lịch crawl lại | Cron (Cloud Scheduler) | 1 | Chạy mỗi 5 phút | Đặt lại status cho URL có next_fetch_at đã đến hạn. |
| DNS | Resolver của cloud + cache trong tiến trình | 1 | Cache theo TTL | Vài nghìn domain, cache gần như luôn trúng. |
- Điểm xuất phát: Postgres làm luôn frontier, lọc trùng và lịch crawl lại
- Lịch sự bằng cột next_allowed_at trên bảng Domain
- HTML nằm trên S3, DB chỉ giữ metadata
Ở hơn 1.000 trang/s, Postgres phải nhận hàng chục nghìn link/s, bảng Url lên hàng tỷ hàng và việc lấy URL bằng SKIP LOCKED tranh chấp trên vài domain lớn.
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 | 1 triệu trang/ngày, vài nghìn domain (crawl giá hoặc tin tức cho một startup) | 100 triệu trang/ngày, khoảng 1 triệu domain (công cụ SEO, tìm kiếm chuyên ngành) | 5 tỷ trang/ngày, hàng trăm triệu domain (máy tìm kiếm toàn cầu) |
| Chi phí | ≈ 80–200 USD/tháng (ước lượng) | ≈ 6.000–12.000 USD/tháng (ước lượng) | ≈ 150.000–300.000 USD/tháng (ước lượng) |
| Fetcher + parser | Node.js (undici, cheerio), Docker 2 × 2 vCPU · 4 GB RAM | Chưa cần | Chưa cần |
| Database (frontier + Url) | PostgreSQL managed 1 × 2 vCPU · 8 GB · 100 GB SSD | Chưa cần | Chưa cần |
| Blob store | S3 / GCS 1 × ≈ 600 GB, vòng đời 30 ngày | S3, file WARC nén 1 × ≈ 20 TB | S3 / GCS, file WARC nén 1 × 100 TB/ngày mới, giữ bản mới nhất |
| Lịch crawl lại | Cron (Cloud Scheduler) 1 × Chạy mỗi 5 phút | Chưa cần | Chưa cần |
| DNS | Resolver của cloud + cache trong tiến trình 1 × Cache theo TTL | Unbound chạy sidecar trên mỗi fetcher 20 × Cache theo TTL | Chưa cần |
| Frontier service | Chưa cần | Node.js, mỗi instance sở hữu một nhóm domain theo hash 3 × 2 vCPU · 4 GB RAM | Chưa cần |
| Redis | Chưa cần | ElastiCache Redis + RedisBloom 1 primary + 1 replica × 4 vCPU · 16 GB | Chưa cần |
| Fetcher | Chưa cần | Node.js async, autoscale 20 × 2 vCPU · 4 GB RAM | Pod async trên Kubernetes, 3 region 965 pod × 2 vCPU · 4 GB mỗi pod |
| Parser | Chưa cần | Node.js consumer 10 × 2 vCPU · 4 GB RAM | Consumer trên Kubernetes 483 pod × 2 vCPU · 4 GB mỗi pod |
| Kafka | Chưa cần | Amazon MSK 3 broker × Topic pages và links, 12 partition key theo domain, RF 3 | MSK / Confluent 12 broker × Topic links 256 partition key theo domain, RF 3 |
| Url store | Chưa cần | ScyllaDB / Cassandra 3 node × 8 vCPU · 32 GB · 1 TB NVMe | ScyllaDB 12 node (4 mỗi AZ) × 16 vCPU · 64 GB · 7,5 TB NVMe |
| Frontier shard | Chưa cần | Chưa cần | Service Go/Java hoặc Node.js trên Kubernetes, StatefulSet 64 pod × 4 vCPU · 8 GB · 200 GB SSD mỗi pod |
| DNS resolver | Chưa cần | Chưa cần | Unbound cluster mỗi region 2 mỗi region (6) × 4 vCPU · 8 GB |
| Batch | Chưa cần | Chưa cần | Spark trên EMR / Dataproc 1 cụm theo lịch × Chạy hàng đêm |
Đà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) URL frontier thế nào để vừa ưu tiên trang quan trọng vừa không dội bom một website?
Link trong một trang chủ yếu trỏ về cùng site, nên các URL liền nhau trong hàng thường cùng domain. Hàng trăm worker cùng lúc tải một site nhỏ, site đó chậm hoặc chặn IP của crawler.
Đánh đổi: Dễ làm nhưng vi phạm lịch sự và bị chặn rất nhanh.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · mục "How does the crawler handle URLs with variable priorities?" (robots.txt, giao tiếp với host server) ; Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design Improvements" · mục "Domain level log" (một domain gán cho một worker)
Worker chọn URL của domain có next_allowed_at ≤ now, khóa bằng SELECT ... FOR UPDATE SKIP LOCKED, rồi đặt next_allowed_at = now + crawl_delay. Hoặc dùng Redis: sorted set domain theo thời điểm được phép, mỗi domain một list URL.
Đánh đổi: Đúng luật lịch sự và đủ cho vài trăm trang/s; DB hoặc Redis trung tâm thành nút thắt khi tăng lên hàng chục nghìn trang/s.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design Improvements" · mục "Domain level log", "Per URL crawling" ; Redis in Action ↗ · ch.3 · §3.5 Sorted sets ; Chưa có nguồn trong thư viện: SELECT ... FOR UPDATE SKIP LOCKED của PostgreSQL
Tầng trước gồm vài hàng theo độ ưu tiên, tầng sau mỗi host một hàng, cộng một min-heap host theo thời điểm được tải tiếp. Bộ chọn lấy từ hàng ưu tiên cao thường xuyên hơn nhưng vẫn để hàng thấp có lượt. Domain được gán cho shard frontier bằng consistent hashing, nên luật lịch sự của một domain chỉ nằm ở một nơi, không cần khóa phân tán. Tốc độ tự điều chỉnh: TTFB tăng hoặc gặp 429/503 thì giãn khoảng cách, như Grokking ch.35 đề xuất dựa trên TTFB.
Đánh đổi: Shard frontier có trạng thái nên phải checkpoint và chuyển giao khi thêm bớt máy; domain cực lớn (Wikipedia) cần cấu hình tốc độ riêng.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · mục "How does the crawler handle URLs with variable priorities?" (nhiều hàng ưu tiên, dequeue theo ưu tiên), mục "Domain level log" (hash hostname gán worker) ; Grokking Modern System Design · ch.17 Distributed Messaging Queue ↗ ; Chưa có nguồn trong thư viện: consistent hashing gán domain cho shard và tự điều chỉnh theo TTFB/429 (xem bài /hoc/consistent-hashing của khoá học)
2) Lọc URL trùng và nội dung trùng thế nào khi có hàng chục tỷ URL?
Hàng triệu link mỗi giây là hàng triệu lần đọc DB. So chuỗi gốc thì http://a.com/x?b=1&a=2 và http://a.com/x?a=2&b=1 bị coi là hai URL khác nhau.
Đánh đổi: Đúng ở quy mô nhỏ, ở quy mô lớn DB chỉ còn phục vụ việc kiểm tra trùng.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design Improvements" · mục "Per URL crawling" (tính checksum của URL đã canonicalize để tránh link trùng) ; Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · mục "Duplicate eliminator"
Chuẩn hóa (chữ thường host, bỏ fragment, sắp tham số, bỏ utm_*) rồi hash 64-128 bit làm khóa chính, ghi bằng INSERT ... ON CONFLICT DO NOTHING. Nội dung tính SHA-256 trên văn bản đã làm sạch để phát hiện trang trùng, đúng mô hình hai kho checksum trong Grokking ch.35.
Đánh đổi: Gọn và chính xác, nhưng mỗi link vẫn chạm DB, và đổi 1 byte (ngày giờ, quảng cáo) là checksum khác nên bỏ sót trang gần trùng.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · mục "Duplicate eliminator" (checksum URL và checksum tài liệu; đổi 1 byte thì checksum khác) ; Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design Improvements" · mục "Per URL crawling" (canonicalized URL) ; Chưa có nguồn trong thư viện: cú pháp ON CONFLICT DO NOTHING và SHA-256 cụ thể
Bloom filter 1% dương tính giả cần ≈ 9,6 bit mỗi URL và 7 hàm hash: 50 tỷ URL ≈ 60 GB, chia 64 shard thì mỗi shard chưa tới 1 GB. Chỉ URL mà Bloom báo chưa thấy mới ghi xuống DB. 1% URL mới bị bỏ nhầm được chấp nhận, hoặc với domain ưu tiên cao thì kiểm tra lại trong DB. Nội dung dùng thêm SimHash 64 bit: hai trang lệch ≤ 3 bit coi là gần trùng.
Đánh đổi: Bloom không xóa được phần tử và phải checkpoint ra S3; SimHash cần bảng tra theo nhiều đoạn bit để tìm nhanh, tốn thêm bộ nhớ.
Nguồn: Lý thuyết · Bloom filter: mảng m bit và k hàm băm; kiểm tra thấy đủ k bit bằng 1 thì "có thể có", thiếu một bit thì "chắc chắn không" (không sai âm). Với n phần tử và tỉ lệ dương tính giả p: m = −n × ln p ÷ (ln 2)², k = (m ÷ n) × ln 2; ví dụ 1 tỉ URL ở p = 1% cần khoảng 9,6 bit mỗi URL, tức 1,2 GB, k ≈ 7. SimHash chưa có nguồn trong thư viện ; Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · mục "Duplicate eliminator" (khái niệm kho checksum thay thế)
3) Tôn trọng robots.txt, tránh bẫy crawler và chịu lỗi khi worker chết?
Số request tới site tăng gấp đôi. Worker chết là mất mọi URL đang cầm, và không có giới hạn nào cho trang lịch vô tận hay đường dẫn lặp /a/b/a/b/...
Đánh đổi: Không cần thêm thành phần, nhưng vừa bất lịch sự vừa mất việc và dễ kẹt trong bẫy.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · mục "How does the crawler handle URLs with variable priorities?" (tôn trọng robots.txt) ; Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design Improvements" · mục "Crawler traps" (hậu quả: cạn tài nguyên crawler)
Luật robots.txt được parse một lần, lưu theo domain trong Redis với TTL 24 h. URL lấy ra qua hàng đợi có visibility timeout: không ack thì quay lại. Lỗi mạng thì retry với backoff tăng dần.
Đánh đổi: Hết mất việc, nhưng URL có thể bị tải hai lần và chưa có gì chặn bẫy crawler.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · mục "How does the crawler handle URLs with variable priorities?" (robots.txt) ; Grokking Modern System Design · ch.17 Distributed Messaging Queue (ack và retry) ↗ ; Chưa có nguồn trong thư viện: TTL cache robots.txt 24 h và visibility timeout
Shard frontier sở hữu domain giữ luôn robots.txt: 404 coi là cho phép, 5xx coi là tạm cấm cả site. URL được cho thuê kèm hạn 10 phút; ghi kết quả theo (url_hash, fetched_at) nên tải lại không gây sai. Shard checkpoint hàng đợi và Bloom ra S3 định kỳ, Kafka giữ link chưa xử lý để replay. Chống bẫy theo Grokking ch.35: giới hạn độ sâu, độ dài URL, số trang mỗi domain, phát hiện đoạn đường dẫn lặp, rồi đánh dấu domain vượt ngưỡng là vùng cấm.
Đánh đổi: Phải chấp nhận at-least-once (thỉnh thoảng tải trùng), và ngưỡng chống bẫy đặt sai sẽ bỏ sót site lớn hợp lệ.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design Improvements" · mục "Crawler traps" (Classification, Identification, Prevention: phân tích URL scheme, giới hạn độ sâu, cyclic directories) ; Grokking Modern System Design · ch.23 Distributed Task Scheduler ↗ · mục "Task idempotency" ; Chưa có nguồn trong thư viện: lease 10 phút, checkpoint Bloom ra S3, luật 404/5xx của robots.txt
4) Mở rộng lên hàng tỷ trang mỗi ngày như thế nào?
Grokking ch.35 tính 5 tỷ trang × 60 ms ≈ 9,5 năm cho một luồng. Thêm thread trên một máy chỉ đẩy giới hạn sang băng thông và DNS của máy đó.
Đánh đổi: Không bao giờ đạt mục tiêu theo ngày.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · mục "Resource estimation" · "Traversal time" (5 tỷ trang × 60 ms ≈ 9,5 năm cho một server)
Thêm máy là tăng tốc độ tải. Hàng đợi trung tâm (Redis hoặc DB) giữ luật lịch sự và lọc trùng.
Đánh đổi: Hàng đợi trung tâm và kho lọc trùng thành nút thắt và điểm chết duy nhất từ khoảng vài nghìn trang/s.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design Improvements" · mục "Per URL crawling" (nhiều worker dùng chung priority queue, dequeue khi rảnh)
Kafka key theo domain, mỗi shard frontier sở hữu một phần domain với Bloom và hàng đợi riêng, fetcher kéo việc từ shard. Mỗi pod giữ hàng trăm kết nối bất đồng bộ, DNS có resolver và cache riêng. Fetcher gom ~1.000 trang thành một file WARC nén trước khi ghi S3: 100 triệu PUT/ngày xuống còn 100.000. Fetcher đặt ở nhiều region gần website để giảm độ trễ.
Đánh đổi: Domain lớn bị giới hạn bởi tốc độ lịch sự dù có thêm máy, và vận hành gần nghìn pod cần giám sát tốt.
Nguồn: Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Design Improvements" · mục "Domain level log", "Range division" ; Grokking Modern System Design · ch.35 Design a Web Crawler ↗ · bài "Evaluation of Web Crawler's Design" · mục "Scalability", "Performance" ; Chưa có nguồn trong thư viện: gom 1.000 trang vào file WARC và I/O bất đồng bộ
Trong phỏng vấn
- “Frontier là trái tim: hàng theo độ ưu tiên ở trước, mỗi host một hàng ở sau, và một heap thời điểm được tải tiếp để giữ lịch sự.”
- “Tôi chia mọi thứ theo domain bằng consistent hashing để luật lịch sự và lọc trùng của một domain chỉ nằm ở một shard.”
- “Lọc trùng hai lớp: Bloom filter cho URL đã chuẩn hóa, SHA-256 và SimHash cho nội dung.”
- “Hệ thống là at-least-once: URL được thuê có hạn, kết quả ghi idempotent, shard checkpoint ra S3 và Kafka giữ link để replay.”
- Một hàng FIFO chung khiến nhiều worker cùng đập một site.
- Quên chuẩn hóa URL nên cùng một trang bị tải nhiều lần.
- Kiểm tra trùng bằng truy vấn DB cho từng link.
- Không nói gì về bẫy crawler, robots.txt và giới hạn số trang mỗi domain.
Đọ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.