🔗 Trận 2: Thiết kế Web Crawler – Làm thế nào Google có thể "đọc" cả Internet?
"Hãy thiết kế một hệ thống có thể thu thập 1 tỷ trang web mỗi tháng."
Đây là một trong những câu hỏi kinh điển trong các buổi phỏng vấn System Design.
Nghe thì có vẻ đơn giản.
"Chỉ cần viết một chương trình gửi HTTP request, lấy HTML rồi lưu vào database là xong."
Nếu đó là câu trả lời đầu tiên xuất hiện trong đầu bạn thì... xin chúc mừng! Bạn vừa đi đúng con đường mà hầu như ai mới học System Design đều đi qua.
Thực tế, tải HTML chỉ chiếm một phần rất nhỏ của bài toán.
Điều khó nằm ở những câu hỏi như:
- Làm sao không làm sập website của người khác?
- Làm sao biết URL nào nên crawl trước?
- Làm sao tránh crawl cùng một trang hàng chục lần?
- Làm sao mở rộng từ 1 server lên hàng nghìn server?
- Làm sao lưu trữ hàng chục Petabyte dữ liệu trong nhiều năm?
Đó mới chính là bài toán mà Google, Bing hay Common Crawl phải giải quyết mỗi ngày.
Trong bài viết này, chúng ta sẽ cùng thiết kế một Web Crawler quy mô Internet, theo đúng phương pháp mà Alex Xu sử dụng trong System Design Interview.
- 1. Understand the problem and design scope: Hiểu rõ bài toán và thiết lập phạm vi thiết kế
- 2. Propose high-level design: Đề xuất thiết kế cấp độ tổng quan và đạt sự đồng thuận
- 3. Design deep dive: Đi sâu vào thiết kế chi tiết và phân tích các thành phần quan trọng
- 4. Wrap up: Thảo luận các trade-off và cách mở rộng
Bước 1. Hiểu yêu cầu
Đây là sai lầm phổ biến nhất của người mới. Vừa nghe đề bài xong là bắt đầu vẽ kiến trúc.
Trong một buổi phỏng vấn, đó là cách nhanh nhất để mất điểm.
Alex Xu luôn nhấn mạnh:
Đừng thiết kế ngay. Hãy hiểu bài toán trước.
Vậy nếu người phỏng vấn nói:
"Hãy thiết kế một Web Crawler."
Bạn sẽ hỏi gì?
Ví dụ:
- Hệ thống dùng để làm gì?
- Crawl bao nhiêu trang?
- Có crawl hình ảnh không?
- Có cần JavaScript Rendering không?
- Có phải cập nhật lại các trang cũ không?
- Dữ liệu sẽ được lưu trong bao lâu?
Sau khi trao đổi, chúng ta thống nhất phạm vi như sau:
- Dùng để xây dựng Search Engine.
- Crawl 1 tỷ trang web mỗi tháng.
- Chỉ crawl HTML.
- Bỏ qua ảnh, video và PDF.
- Theo dõi các trang mới và các trang vừa cập nhật.
- Lưu dữ liệu trong 5 năm.
Đến đây chúng ta mới bắt đầu thiết kế.
Bước 2. Ước lượng quy mô
Đây là bước rất nhiều người bỏ qua.
Nhưng Alex Xu luôn dành vài phút để tính nhanh quy mô hệ thống.
Hãy thử tính.
Bao nhiêu request mỗi giây?
Một tháng:
1.000.000.000 trang
Suy ra:
1.000.000.000 trang / 30 ngày / 86.400 giây ≈ 400 trang mỗi giây
Trong thực tế luôn phải tính cả giờ cao điểm.
Do đó ta thiết kế khoảng:
800 QPS
để có dư địa tăng trưởng.
Dung lượng lưu trữ
Giả sử:
500 KB / HTML
Một tháng:
1 tỷ × 500 KB ≈ 500 TB
Trong 5 năm:
≈ 30 Petabyte
Con số này rất quan trọng.
Vì nó ảnh hưởng trực tiếp đến:
- Storage
- Backup
- Chi phí
- Network
Nếu không tính từ đầu, rất dễ thiết kế sai.
Bước 3. Thiết kế kiến trúc tổng quan
Đây là lúc chúng ta bắt đầu vẽ hệ thống.
Thay vì nghĩ đến từng class hay từng API, hãy nghĩ về luồng dữ liệu.
Đây là một vòng lặp vô tận.
Crawler sẽ:
- Lấy một URL.
- Tải HTML.
- Phân tích nội dung.
- Lấy các liên kết mới.
- Đưa các liên kết đó quay trở lại hàng đợi.
Quá trình này cứ lặp đi lặp lại.
Internet giống như một đồ thị khổng lồ, còn Web Crawler chỉ đơn giản là đi từ đỉnh này sang đỉnh khác.
Thành phần quan trọng số 1 – URL Frontier
Nếu phải chọn một thành phần quan trọng nhất của Web Crawler thì đó chính là URL Frontier.
Nó giống như bộ não điều khiển toàn bộ hệ thống.
Nhiệm vụ của nó là quyết định:
URL nào sẽ được crawl tiếp theo?
Nghe có vẻ đơn giản.
Nhưng hãy tưởng tượng bạn có danh sách:
google.com/page1
google.com/page2
google.com/page3
...
Nếu crawler gửi liên tục hàng trăm request đến Google trong vài giây thì chuyện gì xảy ra?
Máy chủ của Google có thể chịu được. Maybe, nhưng đa số website thì không.
Bạn vừa vô tình tạo ra một cuộc tấn công DDoS.
Đó là lý do Web Crawler phải có một nguyên tắc gọi là Politeness.
Politeness
Ý tưởng rất đơn giản. Thay vì chỉ có một hàng đợi, ta chia thành nhiều hàng đợi.
Mỗi Queue chỉ chứa URL của một host.
Worker sẽ lấy URL xen kẽ giữa các Queue.
Ngoài ra còn có Delay Timer.
Ví dụ:
Fetch host A → delay 2s → Fetch Host A tiếp
Nhờ vậy crawler sẽ không spam một website.
Thành phần quan trọng số 2 – Priority
Không phải website nào cũng quan trọng như nhau.
Wikipedia thay đổi liên tục hay CNN cập nhật từng phút. Còn một blog cá nhân có khi cả năm không thay đổi.
Nếu tài nguyên có hạn, bạn sẽ crawl trang nào trước?
Đó là lúc Priority xuất hiện.
Ví dụ:
Wikipedia → Score 100
CNN → Score 95
BBC → Score 90
Blog cá nhân → Score 20
URL Frontier sẽ luôn ưu tiên URL có điểm cao hơn. Nhờ vậy Search Engine luôn cập nhật các trang quan trọng trước.
Thành phần quan trọng số 3 – HTML Downloader
Downloader nghe có vẻ chỉ là gửi HTTP Request. Nhưng thực tế còn nhiều việc hơn thế.
Robots.txt
Trước khi crawl một website.
Crawler phải đọc:
robots.txt
Ví dụ:
User-agent: *
Disallow:
/admin
/private
Điều này có nghĩa robot không được phép truy cập những đường dẫn đó.
Nếu bỏ qua Robots.txt.
Crawler sẽ bị xem là thiếu lịch sự. Thậm chí có thể bị chặn IP.
Thông thường Robots.txt sẽ được cache để không phải tải lại liên tục.
DNS Cache
Một bước rất tốn thời gian là DNS Lookup.
Nếu mỗi request đều phải hỏi:
google.com
↓
IP là gì?
thì mỗi lần có thể mất:
10–200ms
Nghe có vẻ ít. Nhưng nhân lên hàng tỷ request thì đó là một khoảng thời gian khổng lồ.
Giải pháp rất đơn giản. Cache kết quả DNS.
google.com
↓
142.250.xxx.xxx
Worker lấy trực tiếp từ cache.
Không cần hỏi DNS nữa.
Timeout
Không phải website nào cũng phản hồi.
Có website treo, có website chết, có website phản hồi sau 5 phút.
Nếu Worker cứ chờ mãi thì toàn bộ hệ thống sẽ bị tắc.
Do đó mỗi request đều có Timeout.
Ví dụ:
5 giây
↓
không phản hồi
↓
bỏ qua
Worker lập tức chuyển sang URL khác.
Thành phần quan trọng số 4 – Content Parser
Sau khi tải HTML.
Crawler sẽ phân tích nội dung.
Có hai việc chính.
Lưu nội dung
HTML được lưu xuống Storage.
Đây chính là dữ liệu để Search Engine lập chỉ mục sau này.
Trích xuất URL
Một trang HTML có thể chứa hàng trăm liên kết.
Ví dụ:
<a href="/news">
<a href="/about">
<a href="/contact">
Parser sẽ lấy tất cả URL này.
Sau đó gửi sang bước tiếp theo.
Thành phần quan trọng số 5 – Duplicate Detection
Một sự thật thú vị.
Khoảng 30% nội dung Internet bị trùng lặp.
Ví dụ:
Một bài báo được:
- Báo A đăng.
- Báo B copy.
- Blog C copy tiếp.
Nếu lưu cả ba.
Bạn đang lãng phí hàng Petabyte dữ liệu.
Giải pháp là Hash.
HTML
↓
Fingerprint
↓
Hash
Nếu Hash giống nhau.
Crawler sẽ bỏ qua.
Đối với các nội dung gần giống nhau (không hoàn toàn trùng khớp), hệ thống có thể dùng các kỹ thuật như MinHash hoặc Locality-Sensitive Hashing (LSH) để phát hiện các bản sao gần đúng mà không cần so sánh toàn bộ nội dung.
Thành phần quan trọng số 6 – Spider Trap
Đây là một cơn ác mộng của Web Crawler.
Ví dụ.
Một website sinh URL như sau:
/a → /a/b → /a/b/a → /a/b/a/b → ...
URL sẽ dài mãi mãi.
Crawler sẽ không bao giờ thoát.
Đây gọi là Spider Trap.
Một số cách xử lý:
- Giới hạn chiều dài URL.
- Giới hạn độ sâu crawl.
- Phân tích mẫu URL lặp.
- Bỏ qua các URL bất thường.
Bước 4. Trade-offs trong thiết kế
Đến đây, hệ thống đã hoạt động.
Nhưng System Design không chỉ là xây được.
Mà còn phải hiểu các đánh đổi.
Crawl nhanh hay lịch sự?
Nếu tăng số lượng Worker. Hệ thống crawl nhanh hơn nhưng cũng dễ làm quá tải website.
Ngược lại, nếu Delay quá lớn. Crawler sẽ rất lịch sự nhưng dữ liệu sẽ cũ.
Đó là trade-off đầu tiên.
Lưu tất cả hay loại bỏ dữ liệu trùng?
Lưu tất cả → Đơn giản → Nhưng tốn hàng chục Petabyte.
Loại bỏ dữ liệu trùng → Tiết kiệm dung lượng → Nhưng phải tốn CPU để tính Hash và so sánh.
Crawl HTML hay Render JavaScript?
Ngày nay, nhiều website dùng React. HTML ban đầu gần như rỗng.
Muốn lấy nội dung, Crawler phải chạy JavaScript bằng trình duyệt không giao diện như Puppeteer hoặc Headless Chromium.
Ưu điểm:
- Lấy được dữ liệu đầy đủ.
Nhược điểm:
- CPU và RAM tăng lên rất nhiều.
- Tốc độ crawl giảm đáng kể.
Đây là lý do nhiều Search Engine chỉ render JavaScript với các trang thực sự quan trọng.
Làm thế nào để mở rộng hệ thống?
Nếu hôm nay chúng ta crawl 1 tỷ trang. Ngày mai có thể là 10 tỷ.
Làm sao mở rộng?
Alex Xu gợi ý một số hướng.
- Consistent Hashing để phân phối URL giữa nhiều Downloader và giúp việc thêm hoặc bớt máy chủ không làm xáo trộn toàn bộ dữ liệu.
- Distributed Queue để nhiều Worker có thể lấy URL song song mà không xung đột.
- Geo-distributed Crawlers đặt máy chủ ở nhiều khu vực trên thế giới nhằm giảm độ trễ mạng.
- Plugin Architecture để dễ dàng bổ sung các module mới như Image Downloader, Video Downloader hoặc Social Media Monitor mà không cần thay đổi kiến trúc lõi.
- Spam Filter để loại bỏ các trang chất lượng thấp, nội dung rác hoặc quảng cáo trước khi lưu trữ.
Nhờ thiết kế theo các thành phần độc lập, hệ thống có thể mở rộng cả về quy mô lẫn tính năng mà không phải "đập đi xây lại".
Kết luận
Nếu nhìn bề ngoài, Web Crawler chỉ là một chương trình tải HTML.
Nhưng khi quy mô tăng lên hàng tỷ trang web, bài toán không còn là "làm sao tải được một trang", mà trở thành "làm sao quản lý hàng tỷ URL, hàng nghìn máy chủ và hàng chục Petabyte dữ liệu một cách hiệu quả".
Đó cũng chính là điều Alex Xu muốn truyền tải trong chương này.
Một Web Crawler thành công không nằm ở việc gửi HTTP request nhanh đến đâu, mà nằm ở cách nó ưu tiên đúng URL, tôn trọng website đích, tránh dữ liệu trùng lặp, chịu được lỗi và có thể mở rộng theo sự phát triển không ngừng của Internet.
Quan trọng hơn, bài học này không chỉ áp dụng cho Web Crawler. Những ý tưởng như Queue, Caching, Deduplication, Distributed Workers, Consistent Hashing và Fault Tolerance là các viên gạch nền tảng xuất hiện trong rất nhiều hệ thống lớn khác.
Vì vậy, nếu bạn hiểu được cách thiết kế một Web Crawler, bạn không chỉ học cách xây dựng "con nhện" của Internet, mà còn tiến thêm một bước trên hành trình chinh phục tư duy System Design.
All Rights Reserved
