Kiến trúc hệ thốngThiết kế một web crawler

Thiết kế một web crawler

Nội dung bài

Thiết kế một web crawler

Bài tập21 phút đọcThe System Design Primer - bài giải "Design a web crawler"

Mục lục
  1. Nội dung gốc
  2. Bước 1: Phác thảo các trường hợp sử dụng và ràng buộc
  3. Bước 2: Tạo thiết kế tổng quan
  4. Bước 3: Thiết kế các thành phần cốt lõi
  5. Bước 4: Mở rộng thiết kế
  6. Các điểm thảo luận bổ sung
  7. Ghi chú của người dịch

Thiết kế một web crawler

Nội dung gốc

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. Hãy tham khảo nội dung được liên kết để nắm các điểm thảo luận chung, các đánh đổi (tradeoff) và phương án thay thế.

Bước 1: Phác thảo các trường hợp sử dụng và ràng buộc

Thu thập yêu cầu và khoanh vùng bài toán. Đặt câu hỏi để làm rõ các trường hợp sử dụng (use case) và ràng buộc (constraint). Thảo luận các giả định.

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

Các trường hợp sử dụng

Chúng ta khoanh vùng bài toán, chỉ xử lý các trường hợp sử dụng sau

Ngoài phạm vi

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

Nêu các giả định

Hãy luyện tập dùng các hệ thống truyền thống hơn - không dùng các hệ thống có sẵn như solr hoặc nutch.

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

Hãy hỏi rõ người phỏng vấn xem bạn có nên thực hiện các phép ước lượng nhanh (back-of-the-envelope) hay không.

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

Bước 2: Tạo thiết kế tổng quan

Phác thảo thiết kế tổng quan (high level design) với tất cả các thành phần quan trọng.

Thiết kế tổng quan web crawler

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

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

Trường hợp sử dụng: Dịch vụ crawl một danh sách url

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

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

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

Hãy hỏi rõ người phỏng vấn bạn cần viết bao nhiêu code.

PagesDataStore là một lớp trừu tượng bên trong Crawler Service, sử dụng cơ sở dữ liệu NoSQL:

class PagesDataStore(object):

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

    def add_link_to_crawl(self, url):
        """Thêm liên kết đã cho vào `links_to_crawl`."""
        ...

    def remove_link_to_crawl(self, url):
        """Xóa liên kết đã cho khỏi `links_to_crawl`."""
        ...

    def reduce_priority_link_to_crawl(self, url)
        """Giảm độ ưu tiên của một liên kết trong `links_to_crawl` để tránh chu trình."""
        ...

    def extract_max_priority_page(self):
        """Trả về liên kết có độ ưu tiên cao nhất trong `links_to_crawl`."""
        ...

    def insert_crawled_link(self, url, signature):
        """Thêm liên kết đã cho vào `crawled_links`."""
        ...

    def crawled_similar(self, signature):
        """Xác định xem ta đã crawl một trang khớp với chữ ký đã cho hay chưa"""
        ...

Page là một lớp trừu tượng bên trong Crawler Service, đóng gói một trang, nội dung của trang, các url con và chữ ký:

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à lớp chính bên trong Crawler Service, được cấu thành từ Page và PagesDataStore.

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):
        """Tạo chữ ký dựa trên url và nội dung."""
        ...

    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)

Mã nguồn đầy đủ của các đoạn trên: web_crawler_snippets.py.

Vòng lặp crawl: kiểm tra chữ ký tương tự trước khi crawl, nếu trùng thì giảm độ ưu tiên để tránh chu trình Lấy URL ưu tiên cao nhất Đã crawl trang tương tự? không Crawl trang, tạo chữ ký Job chỉ mục + lưu crawled_links có Giảm ưu tiên
Mỗi vòng lặp lấy URL ưu tiên cao nhất; nếu đã crawl trang có chữ ký tương tự thì giảm độ ưu tiên của link đó và lấy link tiếp theo, nếu chưa thì crawl, tạo chữ ký, đẩy job tạo chỉ mục rồi lưu vào crawled_links.

Xử lý trùng lặp

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

Hãy hỏi rõ người phỏng vấn bạn cần viết bao nhiêu code.

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

class RemoveDuplicateUrls(MRJob):

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

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

Mã nguồn đầy đủ: web_crawler_mapreduce.py.

Phát hiện nội dung trùng lặp phức tạp hơn. Ta có thể tạo chữ ký dựa trên nội dung trang rồi so sánh hai chữ ký để đo độ tương tự. Một số thuật toán có thể dùng là chỉ số Jaccard (Jaccard index) và độ tương tự cosin (cosine similarity).

So sánh vân tay nội dung để phát hiện trang gần trùng lặp Trang A Trang B khác 1 bit → vẫn tính là gần trùng
Minh hoạ kiểu SimHash (thu gọn còn 8 bit, thực tế thường 64 bit): hai trang gần giống nhau cho hai vân tay chỉ lệch vài bit (khoảng cách Hamming nhỏ, dưới ngưỡng) nên được tính là gần trùng.

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 độ tươi mới. Kết quả crawl có thể có một 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, mọi trang nên được làm mới. Các trang cập nhật thường xuyên hoặc phổ biến hơn có thể được làm mới với chu kỳ ngắn hơn.

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

Ta cũng có thể chọn hỗ trợ file Robots.txt, cho phép quản trị viên trang web (webmaster) kiểm soát tần suất crawl.

Trường hợp sử dụng: Người dùng nhập một từ khóa tìm kiếm và thấy danh sách các trang liên quan cùng tiêu đề và đoạn trích

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

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

Phản hồi:

{
    "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 lời gọi thủ tục từ xa (Remote Procedure Call - RPC).

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

Xác định và xử lý các điểm nghẽn (bottleneck), dựa trên các ràng buộc.

Thiết kế web crawler sau khi mở rộng

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ằng bạn sẽ 1) Benchmark/kiểm thử tải (Load Test), 2) Profile để tìm điểm nghẽn, 3) xử lý các điểm nghẽn trong khi đánh giá các phương án thay thế và đánh đổi, và 4) lặp lại. Xem Thiết kế một hệ thống mở rộng tới hàng triệu người dùng trên AWS để có ví dụ về cách mở rộng thiết kế ban đầu theo từng bước lặp.

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

Chúng ta sẽ đưa vào 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 bộ cân bằng tải nội bộ không được vẽ ra để hình đỡ rối.

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

Một số truy vấn 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ý lưu lượng phân bố không đều và các đợt tăng đột biến (traffic spike). Đọc tuần tự 1 MB từ bộ nhớ mất khoảng 250 micro giây, trong khi đọc từ SSD lâu hơn 4 lần và từ ổ đĩa cứng lâu hơn 80 lần.1

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

Các điểm thảo luận bổ sung

Các chủ đề bổ sung để đi sâu, tùy theo phạm vi bài toán và thời gian còn lại.

Các mẫu mở rộng SQL

NoSQL

Bộ nhớ đệm (Caching)

Bất đồng bộ và microservices

Giao tiếp

Bảo mật

Tham khảo mục bảo mật.

Các con số độ trễ

Xem Các con số độ trễ mà mọi lập trình viên nên biết (Latency numbers every programmer should know).

Liên tục

Nguồn: The System Design Primer - bài giải "Design a web crawler" — Donne Martin và cộng đồng đóng góp

Giấy phép: CC BY 4.0 (nguyên bản: Donne Martin, The System Design Primer)

Xem bản gốc

Bài tiếp theoThiết kế Mint.com