System Design: Web Crawler

Ví dụ 1 luồng: Service -> url frontier ( filter, prioirty, queue, politeness -> force sleep to extend the time between downloads ) -> html crawler robots -> (communicate with dns) -> content parser -> content store -> is exist ? -> url parser -> url store

1. Khởi nguồn của rắc rối: Khi Internet trở thành một vũ trụ vô tận

Thuở bình minh của Internet, việc tìm kiếm một trang web khá đơn giản vì số lượng website chỉ đếm trên đầu ngón tay. Nhưng khi Web bùng nổ với hàng chục tỷ trang nội dung liên kết chằng chịt với nhau, bài toán đặt ra cho các cỗ máy tìm kiếm (như Google) là: Làm sao để biết được ngoài kia đang có những trang web nào, nội dung của chúng là gì để mà lập chỉ mục (index)?

Để giải quyết bài toán này, các kỹ sư tạo ra Web Crawler (còn gọi là Robot hay Spider). Nhiệm vụ của "con nhện" này là bắt đầu từ một vài URL hạt giống (Seed URLs), tải nội dung về, tìm tất cả các đường link có trong trang đó, rồi lại tiếp tục đi theo các link đó để tải trang mới. Quá trình này lặp đi lặp lại vô tận.

Nghe có vẻ là một thuật toán vòng lặp đơn giản chỉ mất vài dòng code. Nhưng thực tế, Internet không phải là một thư viện gọn gàng. Nó là một bãi chiến trường đầy rẫy các trang web lỗi, những server phản hồi chậm chạp, những đường link chết, và cả những cạm bẫy được giăng ra để đánh sập crawler của bạn. Xây dựng một Web Crawler đồ sộ là một bài toán hệ thống phân tán vô cùng phức tạp.

2. Hành trình đi tìm giải pháp: Từ Vòng lặp Đơn giản đến Kiến trúc Phân tán

Bạn có thể coi Internet như một đồ thị có hướng khổng lồ, trong đó các trang web là các Node (đỉnh), và các đường link (URL) là các Edge (cạnh). Quá trình Crawler hoạt động chính là bài toán duyệt đồ thị. Bạn sẽ chọn duyệt theo chiều sâu (DFS) hay duyệt theo chiều rộng (BFS)?

DFS (Depth-First Search) thường bị loại bỏ ngay từ vòng gửi xe. Lý do là độ sâu của một nhánh web có thể vô tận, Crawler của bạn có thể sẽ đi vào một "hố đen" mà không bao giờ quay lại được để cào các trang web quan trọng khác.

BFS (Breadth-First Search) là giải pháp tiêu chuẩn. Crawler sẽ duy trì một hàng đợi (FIFO Queue). Lấy một URL ra, tải trang, trích xuất link mới, rồi nhét các link đó vào cuối hàng đợi.

Tuy nhiên, nếu chỉ dùng BFS thuần túy ngây ngô, Crawler của bạn sẽ trở thành một Kẻ tấn công DDoS. Tại sao? Vì phần lớn các link trong một trang web thường trỏ về chính website đó (Internal links). Nếu Crawler lấy ra liên tục 1.000 URLs của Wikipedia từ hàng đợi và tải chúng cùng lúc, server của Wikipedia sẽ sập ngay lập tức vì quá tải. Hơn nữa, BFS thuần túy coi mọi link là bình đẳng, trong khi thực tế link từ diễn đàn rác không thể quan trọng bằng link từ trang chủ Apple.

Đó là lúc chúng ta phải giải phẫu trái tim của hệ thống: URL Frontier.

3. Giải phẫu kiến trúc: URL Frontier - Bộ não của sự lịch sự và ưu tiên

URL Frontier không đơn thuần là một cái Queue. Nó là một cấu trúc dữ liệu cực kỳ phức tạp để giải quyết hai vấn đề lớn nhất của Crawler:

1. Sự lịch sự (Politeness): Nguyên tắc vàng là "Không tải nhiều hơn một trang web từ cùng một host trong một khoảng thời gian ngắn". Để làm được điều này, Frontier sử dụng một bộ định tuyến (Queue Router) để đẩy các URL của cùng một host (ví dụ: wikipedia.com) vào một queue riêng biệt (Back Queue). Mỗi Worker Thread (luồng tải) sẽ chỉ được gắn liền với một Queue cụ thể. Khi Worker tải xong 1 trang, nó sẽ bị ép "ngủ" (delay) vài giây trước khi tải trang tiếp theo từ Queue đó.

2. Độ ưu tiên (Priority): Crawler phải biết cào những trang quan trọng trước. Trước khi URL rơi vào các Back Queue, nó phải đi qua một bộ định tuyến ưu tiên (Prioritizer). Dựa trên thuật toán như PageRank, lượng traffic, mức độ cập nhật, URL sẽ được phân loại vào các Front Queue có độ ưu tiên khác nhau (Cao, Trung bình, Thấp). Một bộ Selector sẽ bốc URL từ các Front Queue này (tất nhiên là ưu tiên bốc từ Queue Cao nhiều hơn) rồi mới đẩy xuống Back Queue cho Worker xử lý.

4. Câu chuyện thực chiến: Hệ thống cào 1 Tỷ trang mỗi tháng

Hãy thử thiết kế hệ thống Crawler cho một công cụ tìm kiếm cỡ vừa, tải 1 tỷ trang HTML mỗi tháng (khoảng 400 trang/giây, peak là 800 trang/giây). Nếu mỗi trang nặng 500KB, lưu trữ trong 5 năm, bạn sẽ cần một kho lưu trữ khổng lồ lên tới 30 Petabytes (PB).

Luồng xử lý thực tế của dữ liệu diễn ra như sau:

1. HTML Downloader nhận URL từ URL Frontier. Nó gọi DNS Resolver để phân giải URL thành IP. Ở quy mô này, DNS Resolver là một điểm nghẽn mạng (bottleneck) cực lớn vì độ trễ DNS mất từ 10-200ms và có tính đồng bộ (block các thread khác). Giải pháp là Crawler phải có một hệ thống Cache DNS Resolver nội bộ, chạy định kỳ (cron job) để làm mới IP thay vì gọi DNS Server bên ngoài cho mỗi request.
2. Trang tải về được chuyển cho Content Parser để phân tích HTML.
3. Kế tiếp là khâu Content Seen? (Trang này đã từng cào chưa?). Có tới 29% nội dung trên Internet là trùng lặp. Thay vì so sánh từng chữ tốn kém, ta tính mã Hash (MD5 hoặc SHA) của toàn bộ nội dung HTML. Nếu mã Hash đã nằm trong hệ thống, vứt trang đó đi.
4. Nếu là nội dung mới, đẩy vào kho lưu trữ (Disk cho số lượng lớn, Memory cho trang hot).
5. Link Extractor vào cuộc, moi tất cả thẻ <a> ra, chuyển link tương đối thành tuyệt đối.
6. Cụm URL Filter sẽ gạt bỏ các đuôi file không cần thiết (.png, .mp4) hoặc các trang bị đưa vào Blacklist.
7. Cuối cùng, cụm URL Seen? kiểm tra xem URL này đã từng nằm trong URL Frontier hay chưa. (Thường dùng Bloom Filter để check trên RAM siêu nhanh). Nếu chưa, nó được đẩy ngược lại vào URL Frontier để bắt đầu vòng đời mới.

5. Góc khuất và những sự đánh đổi (Trade-offs)

Làm Crawler là cuộc chiến không hồi kết với thế giới Internet đầy nhiễu nhương. Góc khuất đáng sợ nhất chính là Spider Traps (Bẫy nhện).

Hãy tưởng tượng một cấu trúc thư mục vô hạn được sinh ra tự động: www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/.... Crawler ngây thơ của bạn sẽ đi theo đường link này, chìm sâu vào vòng lặp vô tận và tốn sạch tài nguyên. Để đối phó, các kỹ sư thường phải thiết lập độ dài tối đa của một URL (Max URL Length), giới hạn độ sâu khi cào (Max Depth), và đôi khi là theo dõi log thủ công để Blacklist các domain giăng bẫy.

Một trade-off khác nằm ở bộ lưu trữ của URL Frontier. Với quy mô hàng trăm triệu URL nằm trong hàng đợi, việc nhét tất cả vào RAM là bất khả thi và dễ mất dữ liệu khi sập server. Nhưng nếu ném thẳng xuống Disk thì tốc độ đọc/ghi I/O sẽ kéo ghì toàn bộ hệ thống. Giải pháp dung hòa là lưu trữ phần lớn trên Disk, nhưng duy trì các cấu trúc Buffer trong Memory để phục vụ Enqueue/Dequeue liên tục, và định kỳ flush (xả) xuống Disk.

6. So sánh & Câu hỏi xoáy

Trong các cuộc phỏng vấn thiết kế Crawler, sẽ có những câu hỏi xoáy để kiểm tra độ sâu của bạn:

• "Nhiều website hiện đại dùng React, Vue, Angular. Nội dung HTML trả về ban đầu chỉ là một cái div trống rỗng, dữ liệu sinh ra sau khi chạy Javascript (AJAX). Crawler của bạn sẽ bị mù?" Lời giải: Chúng ta không thể chỉ dùng bộ tải HTML thuần túy. Phải tích hợp một bước gọi là Server-side Rendering (Dynamic Rendering) hoặc chạy một trình duyệt không giao diện (Headless Browser như Puppeteer/Playwright) tải và chạy xong JS rồi mới lấy HTML cuối cùng.

• "Làm sao bạn biết trang web nào cấm Crawler?" Lời giải: Tuân thủ tiêu chuẩn Robots Exclusion Protocol. Trước khi cào bất kỳ domain nào, phải tải và đọc file robots.txt của họ, lưu cache lại, và tuyệt đối không cào những thư mục được cấu hình Disallow. Tôn trọng "luật chơi" là nguyên tắc sinh tồn của Crawler.