Thiết kế web crawler

Lưu ý: Tài liệu này liên kết trực tiếp tới các phần liên quan trong các chủ đề system design để tránh lặp lại. Xem nội dung được liên kết để biết các ý thảo luận chung, đánh đổi và phương án thay thế.

Bước 1: Xác định use case và ràng buộc

Thu thập yêu cầu và giới hạn phạm vi bài toán. Đặt câu hỏi để làm rõ use case và ràng buộc. Thảo luận các giả định.

Vì không có người phỏng vấn để giải đáp các câu hỏi làm rõ, chúng ta sẽ tự định nghĩa một số use case và ràng buộc.

Use case

Chúng ta giới hạn bài toán ở các use case sau

Service crawl một danh sách url:
- Tạo reverse index từ các từ tới những trang chứa từ khoá tìm kiếm
- Tạo tiêu đề và snippet cho các trang
  - Tiêu đề và snippet là tĩnh, không thay đổi theo câu truy vấn tìm kiếm
User nhập một từ khoá tìm kiếm và xem danh sách các trang liên quan kèm tiêu đề và snippet do crawler tạo ra
- Chỉ phác thảo các thành phần và tương tác ở mức cao cho use case này, không cần đi sâu
Service có tính sẵn sàng cao

Ngoài phạm vi

Search analytics
Kết quả tìm kiếm cá nhân hoá
Page rank

Ràng buộc và giả định

Nêu các giả định

Traffic không được phân bổ đồng đều
- Một số lượt tìm kiếm rất phổ biến, trong khi số khác chỉ được thực hiện một lần
Chỉ hỗ trợ user ẩn danh
Tạo kết quả tìm kiếm phải nhanh
Web crawler không được bị kẹt trong vòng lặp vô hạn
- Chúng ta bị kẹt trong vòng lặp vô hạn nếu đồ thị chứa chu trình
1 tỷ liên kết cần crawl
- Các trang cần được crawl định kỳ để đảm bảo dữ liệu mới
- Tần suất làm mới trung bình khoảng một lần mỗi tuần, thường xuyên hơn với các site phổ biến
  - 4 tỷ liên kết được crawl mỗi tháng
- Kích thước lưu trữ trung bình mỗi trang web: 500 KB
  - Để đơn giản, coi trang thay đổi như trang mới
100 tỷ lượt tìm kiếm mỗi tháng

Hãy luyện tập với các hệ thống truyền thống hơn, đừng dùng các hệ thống có sẵn như solr hay nutch.

Tính toán mức sử dụng

Làm rõ với người phỏng vấn xem có nên tính toán ước lượng nhanh về mức sử dụng hay không.

2 PB nội dung trang được lưu mỗi tháng
- 500 KB mỗi trang * 4 tỷ liên kết được crawl mỗi tháng
- 72 PB nội dung trang được lưu trong 3 năm
1,600 request ghi mỗi giây
40,000 request tìm kiếm mỗi giây

Bảng quy đổi tiện dụng:

2.5 triệu giây mỗi tháng
1 request mỗi giây = 2.5 triệu request mỗi tháng
40 request mỗi giây = 100 triệu request mỗi tháng
400 request mỗi giây = 1 tỷ request mỗi tháng

Bước 2: Tạo thiết kế mức cao

Phác thảo thiết kế mức cao với tất cả các thành phần quan trọng.

Imgur

Bước 3: Thiết kế các thành phần cốt lõi

Đi sâu vào chi tiết của từng thành phần cốt lõi.

Use case: Service crawl một danh sách url

Chúng ta giả định có sẵn một danh sách links_to_crawl ban đầu, được xếp hạng dựa trên mức độ phổ biến chung của site. Nếu giả định này không hợp lý, chúng ta có thể khởi tạo crawler bằng các site phổ biến có liên kết ra nội dung bên ngoài như Yahoo, DMOZ, v.v.

Chúng ta dùng bảng crawled_links để lưu các liên kết đã xử lý cùng chữ ký (signature) của trang.

Chúng ta có thể lưu links_to_crawl và crawled_links trong một NoSQL Database dạng key-value. Với các liên kết đã xếp hạng trong links_to_crawl, có thể dùng Redis với sorted set để duy trì thứ hạng của các liên kết trang. Nên thảo luận về use case và đánh đổi giữa việc chọn SQL hay NoSQL.

Crawler Service xử lý từng liên kết trang bằng cách lặp lại các bước sau:
- Lấy liên kết trang có thứ hạng cao nhất để crawl
  - Kiểm tra crawled_links trong NoSQL Database xem có bản ghi nào có chữ ký trang tương tự không
    - Nếu có trang tương tự, giảm độ ưu tiên của liên kết trang
      - Điều này giúp tránh rơi vào chu trình
      - Tiếp tục
    - Nếu không, crawl liên kết
      - Thêm một job vào queue của Reverse Index Service để tạo reverse index
      - Thêm một job vào queue của Document Service để tạo tiêu đề và snippet tĩnh
      - Tạo chữ ký của trang
      - Xoá liên kết khỏi links_to_crawl trong NoSQL Database
      - Chèn liên kết trang và chữ ký vào crawled_links trong NoSQL Database

Làm rõ với người phỏng vấn xem bạn được kỳ vọng viết bao nhiêu code.

PagesDataStore là một abstraction trong Crawler Service dùng NoSQL Database:

python

class PagesDataStore(object):

    def __init__(self, db);
        self.db = db
        ...

    def add_link_to_crawl(self, url):
        """Add the given link to `links_to_crawl`."""
        ...

    def remove_link_to_crawl(self, url):
        """Remove the given link from `links_to_crawl`."""
        ...

    def reduce_priority_link_to_crawl(self, url)
        """Reduce the priority of a link in `links_to_crawl` to avoid cycles."""
        ...

    def extract_max_priority_page(self):
        """Return the highest priority link in `links_to_crawl`."""
        ...

    def insert_crawled_link(self, url, signature):
        """Add the given link to `crawled_links`."""
        ...

    def crawled_similar(self, signature):
        """Determine if we've already crawled a page matching the given signature"""
        ...

Page là một abstraction trong Crawler Service đóng gói một trang, nội dung, các url con và chữ ký của nó:

python

class Page(object):

    def __init__(self, url, contents, child_urls, signature):
        self.url = url
        self.contents = contents
        self.child_urls = child_urls
        self.signature = signature

Crawler là class chính trong Crawler Service, được ghép từ Page và PagesDataStore.

python

class Crawler(object):

    def __init__(self, data_store, reverse_index_queue, doc_index_queue):
        self.data_store = data_store
        self.reverse_index_queue = reverse_index_queue
        self.doc_index_queue = doc_index_queue

    def create_signature(self, page):
        """Create signature based on url and contents."""
        ...

    def crawl_page(self, page):
        for url in page.child_urls:
            self.data_store.add_link_to_crawl(url)
        page.signature = self.create_signature(page)
        self.data_store.remove_link_to_crawl(page.url)
        self.data_store.insert_crawled_link(page.url, page.signature)

    def crawl(self):
        while True:
            page = self.data_store.extract_max_priority_page()
            if page is None:
                break
            if self.data_store.crawled_similar(page.signature):
                self.data_store.reduce_priority_link_to_crawl(page.url)
            else:
                self.crawl_page(page)

Xử lý trùng lặp

Chúng ta cần cẩn thận để web crawler không bị kẹt trong vòng lặp vô hạn, điều xảy ra khi đồ thị chứa chu trình.

Làm rõ với người phỏng vấn xem bạn được kỳ vọng viết bao nhiêu code.

Chúng ta sẽ muốn loại bỏ các url trùng lặp:

Với danh sách nhỏ, có thể dùng thứ như sort | unique
Với 1 tỷ liên kết cần crawl, có thể dùng MapReduce để chỉ xuất ra những bản ghi có tần suất xuất hiện là 1

python

class RemoveDuplicateUrls(MRJob):

    def mapper(self, _, line):
        yield line, 1

    def reducer(self, key, values):
        total = sum(values)
        if total == 1:
            yield key, total

Phát hiện nội dung trùng lặp phức tạp hơn. Chúng ta có thể tạo một chữ ký dựa trên nội dung trang và so sánh độ giống nhau giữa hai chữ ký đó. Một số thuật toán khả dĩ là Jaccard index và cosine similarity.

Xác định khi nào cập nhật kết quả crawl

Các trang cần được crawl định kỳ để đảm bảo dữ liệu mới. Kết quả crawl có thể có trường timestamp cho biết lần cuối trang được crawl. Sau một khoảng thời gian mặc định, chẳng hạn một tuần, tất cả các trang nên được làm mới. Các site cập nhật thường xuyên hoặc phổ biến hơn có thể được làm mới theo chu kỳ ngắn hơn.

Dù không đi sâu vào analytics, chúng ta có thể làm một chút data mining để xác định thời gian trung bình trước khi một trang cụ thể được cập nhật, rồi dùng số liệu đó để quyết định tần suất crawl lại trang.

Chúng ta cũng có thể chọn hỗ trợ file Robots.txt, cho phép webmaster kiểm soát tần suất crawl.

Use case: User nhập một từ khoá tìm kiếm và xem danh sách các trang liên quan kèm tiêu đề và snippet

Client gửi request tới Web Server, chạy như một reverse proxy
Web Server chuyển tiếp request tới Query API server
Query API server thực hiện các việc sau:
- Phân tích câu truy vấn
  - Loại bỏ markup
  - Tách văn bản thành các term
  - Sửa lỗi chính tả
  - Chuẩn hoá chữ hoa chữ thường
  - Chuyển truy vấn sang dạng dùng các toán tử boolean
- Dùng Reverse Index Service để tìm các tài liệu khớp với truy vấn
  - Reverse Index Service xếp hạng các kết quả khớp và trả về những kết quả đứng đầu
- Dùng Document Service để trả về tiêu đề và snippet

Chúng ta sẽ dùng một REST API công khai:

$ curl https://search.com/api/v1/search?query=hello+world

Response:

{
    "title": "foo's title",
    "snippet": "foo's snippet",
    "link": "https://foo.com",
},
{
    "title": "bar's title",
    "snippet": "bar's snippet",
    "link": "https://bar.com",
},
{
    "title": "baz's title",
    "snippet": "baz's snippet",
    "link": "https://baz.com",
},

Với giao tiếp nội bộ, chúng ta có thể dùng Remote Procedure Call.

Bước 4: Mở rộng thiết kế

Xác định và xử lý các nút thắt cổ chai, dựa trên các ràng buộc đã nêu.

Imgur

Quan trọng: Đừng nhảy thẳng từ thiết kế ban đầu sang thiết kế cuối cùng!

Hãy nói rõ bạn sẽ 1) Benchmark/Load Test, 2) Profile để tìm nút thắt cổ chai, 3) xử lý các nút thắt cổ chai trong khi cân nhắc các phương án thay thế và đánh đổi, và 4) lặp lại. Xem Design a system that scales to millions of users on AWS làm ví dụ về cách mở rộng thiết kế ban đầu theo từng vòng lặp.

Điều quan trọng là thảo luận những nút thắt cổ chai bạn có thể gặp với thiết kế ban đầu và cách xử lý từng cái. Ví dụ, thêm một Load Balancer với nhiều Web Server giải quyết được những vấn đề gì? CDN? Master-Slave Replicas? Mỗi phương án có những phương án thay thế và đánh đổi nào?

Chúng ta sẽ bổ sung một số thành phần để hoàn thiện thiết kế và xử lý các vấn đề về khả năng mở rộng. Các internal load balancer không được vẽ ra để sơ đồ đỡ rối.

Để tránh lặp lại thảo luận, hãy xem các chủ đề system design sau để biết các ý thảo luận chính, đánh đổi và phương án thay thế:

Một số lượt tìm kiếm rất phổ biến, trong khi số khác chỉ được thực hiện một lần. Các truy vấn phổ biến có thể được phục vụ từ một Memory Cache như Redis hoặc Memcached để giảm thời gian phản hồi và tránh làm quá tải Reverse Index Service và Document Service. Memory Cache cũng hữu ích để xử lý traffic phân bổ không đồng đều và các đợt tăng đột biến. Đọc tuần tự 1 MB từ bộ nhớ mất khoảng 250 microsecond, trong khi đọc từ SSD chậm hơn 4 lần và đọc từ đĩa chậm hơn 80 lần.¹

Dưới đây là một vài tối ưu khác cho Crawling Service:

Để xử lý kích thước dữ liệu và tải request, Reverse Index Service và Document Service nhiều khả năng sẽ phải dùng nhiều sharding và federation.
DNS lookup có thể là nút thắt cổ chai, Crawler Service có thể giữ DNS lookup riêng và làm mới định kỳ
Crawler Service có thể cải thiện hiệu năng và giảm mức dùng bộ nhớ bằng cách giữ nhiều kết nối mở cùng lúc, gọi là connection pooling
- Chuyển sang UDP cũng có thể tăng hiệu năng
Web crawling tốn nhiều băng thông, hãy đảm bảo có đủ băng thông để duy trì throughput cao

Các ý thảo luận thêm

Các chủ đề bổ sung có thể đào sâu, tuỳ phạm vi bài toán và thời gian còn lại.

Các pattern mở rộng SQL

NoSQL

Caching

Cache ở đâu
Cache cái gì
- Caching ở mức database query
- Caching ở mức object
Khi nào cập nhật cache

Xử lý bất đồng bộ và microservices

Giao tiếp

Thảo luận các đánh đổi:
- Giao tiếp bên ngoài với client - HTTP API theo chuẩn REST
- Giao tiếp nội bộ - RPC
Service discovery

Bảo mật

Xem phần bảo mật.

Latency numbers

Xem Latency numbers every programmer should know.

Liên tục

Tiếp tục benchmark và giám sát hệ thống để xử lý các nút thắt cổ chai khi chúng xuất hiện
Mở rộng là một quá trình lặp

Thiết kế web crawler ​

Bước 1: Xác định use case và ràng buộc ​

Use case ​

Chúng ta giới hạn bài toán ở các use case sau ​

Ngoài phạm vi ​

Ràng buộc và giả định ​

Nêu các giả định ​

Tính toán mức sử dụng ​

Bước 2: Tạo thiết kế mức cao ​

Bước 3: Thiết kế các thành phần cốt lõi ​

Use case: Service crawl một danh sách url ​

Xử lý trùng lặp ​

Xác định khi nào cập nhật kết quả crawl ​

Use case: User nhập một từ khoá tìm kiếm và xem danh sách các trang liên quan kèm tiêu đề và snippet ​

Bước 4: Mở rộng thiết kế ​

Các ý thảo luận thêm ​

Các pattern mở rộng SQL ​

NoSQL ​

Caching ​

Xử lý bất đồng bộ và microservices ​

Giao tiếp ​

Bảo mật ​

Latency numbers ​

Liên tục ​

Thiết kế web crawler

Bước 1: Xác định use case và ràng buộc

Use case

Chúng ta giới hạn bài toán ở các use case sau

Ngoài phạm vi

Ràng buộc và giả định

Nêu các giả định

Tính toán mức sử dụng

Bước 2: Tạo thiết kế mức cao

Bước 3: Thiết kế các thành phần cốt lõi

Use case: Service crawl một danh sách url

Xử lý trùng lặp

Xác định khi nào cập nhật kết quả crawl

Use case: User nhập một từ khoá tìm kiếm và xem danh sách các trang liên quan kèm tiêu đề và snippet

Bước 4: Mở rộng thiết kế

Các ý thảo luận thêm

Các pattern mở rộng SQL

NoSQL

Caching

Xử lý bất đồng bộ và microservices

Giao tiếp

Bảo mật

Latency numbers

Liên tục