Thiết kế key-value cache để lưu kết quả của các query gần đây nhất trên web server

Lưu ý: Tài liệu này liên kết trực tiếp tới các mục liên quan trong các chủ đề system design để tránh lặp nội dung. Xem phần đượ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 để hỏi lại, chúng ta 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

User gửi request tìm kiếm và kết quả là cache hit
User gửi request tìm kiếm và kết quả là cache miss
Service có tính sẵn sàng cao

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

Nêu các giả định

Traffic không phân bố đồng đều
- Các query phổ biến gần như luôn phải nằm trong cache
- Cần xác định cách expire/refresh
Phục vụ từ cache đòi hỏi tra cứu nhanh
Latency giữa các máy thấp
Bộ nhớ của cache có hạn
- Cần xác định giữ lại và loại bỏ cái gì
- Cần cache hàng triệu query
10 triệu user
10 tỷ query mỗi tháng

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

Hỏ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.

Cache lưu một danh sách có thứ tự gồm key: query, value: kết quả
- query - 50 byte
- title - 20 byte
- snippet - 200 byte
- Tổng: 270 byte
2.7 TB dữ liệu cache mỗi tháng nếu cả 10 tỷ query đều khác nhau và đều được lưu
- 270 byte mỗi lượt tìm kiếm * 10 tỷ lượt tìm kiếm mỗi tháng
- Giả định nêu bộ nhớ có hạn, nên cần xác định cách expire nội dung
4,000 request 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: User gửi request và kết quả là cache hit

Các query phổ biến có thể được phục vụ từ Memory Cache như Redis hoặc Memcached để giảm latency đọc và tránh làm quá tải Reverse Index Service và Document Service. Đọ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.¹

Vì cache có dung lượng hạn chế, chúng ta dùng cách tiếp cận least recently used (LRU) để expire các entry cũ.

Client gửi request tới Web Server, chạy như một reverse proxy
Web Server chuyển tiếp request tới server Query API
Server Query API làm các việc sau:
- Phân tích query
  - 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 query sang dạng dùng các phép toán boolean
- Kiểm tra Memory Cache xem có nội dung khớp với query hay không
  - Nếu Memory Cache có hit, Memory Cache làm các việc sau:
    - Chuyển entry vừa truy cập lên đầu danh sách LRU
    - Trả về nội dung đã cache
  - Nếu không, Query API làm các việc sau:
    - Dùng Reverse Index Service để tìm các tài liệu khớp với query
      - 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ề title và snippet
    - Cập nhật Memory Cache với nội dung đó, đặt entry ở đầu danh sách LRU

Cài đặt cache

Cache có thể dùng doubly-linked list: item mới được thêm vào đầu, còn item cần expire được xoá từ cuối. Chúng ta dùng hash table để tra cứu nhanh tới từng node của linked list.

Hỏi người phỏng vấn xem bạn được kỳ vọng viết bao nhiêu code.

Cài đặt Query API Server:

python

class QueryApi(object):

    def __init__(self, memory_cache, reverse_index_service):
        self.memory_cache = memory_cache
        self.reverse_index_service = reverse_index_service

    def parse_query(self, query):
        """Remove markup, break text into terms, deal with typos,
        normalize capitalization, convert to use boolean operations.
        """
        ...

    def process_query(self, query):
        query = self.parse_query(query)
        results = self.memory_cache.get(query)
        if results is None:
            results = self.reverse_index_service.process_search(query)
            self.memory_cache.set(query, results)
        return results

Cài đặt Node:

python

class Node(object):

    def __init__(self, query, results):
        self.query = query
        self.results = results

Cài đặt LinkedList:

python

class LinkedList(object):

    def __init__(self):
        self.head = None
        self.tail = None

    def move_to_front(self, node):
        ...

    def append_to_front(self, node):
        ...

    def remove_from_tail(self):
        ...

Cài đặt Cache:

python

class Cache(object):

    def __init__(self, MAX_SIZE):
        self.MAX_SIZE = MAX_SIZE
        self.size = 0
        self.lookup = {}  # key: query, value: node
        self.linked_list = LinkedList()

    def get(self, query)
        """Get the stored query result from the cache.

        Accessing a node updates its position to the front of the LRU list.
        """
        node = self.lookup[query]
        if node is None:
            return None
        self.linked_list.move_to_front(node)
        return node.results

    def set(self, results, query):
        """Set the result for the given query key in the cache.

        When updating an entry, updates its position to the front of the LRU list.
        If the entry is new and the cache is at capacity, removes the oldest entry
        before the new entry is added.
        """
        node = self.lookup[query]
        if node is not None:
            # Key exists in cache, update the value
            node.results = results
            self.linked_list.move_to_front(node)
        else:
            # Key does not exist in cache
            if self.size == self.MAX_SIZE:
                # Remove the oldest entry from the linked list and lookup
                self.lookup.pop(self.linked_list.tail.query, None)
                self.linked_list.remove_from_tail()
            else:
                self.size += 1
            # Add the new key and value
            new_node = Node(query, results)
            self.linked_list.append_to_front(new_node)
            self.lookup[query] = new_node

Khi nào cập nhật cache

Cache cần được cập nhật khi:

Nội dung trang thay đổi
Một trang bị xoá hoặc một trang mới được thêm
Thứ hạng của trang thay đổi

Cách đơn giản nhất để xử lý các trường hợp này là đặt thời gian tối đa mà một entry được nằm trong cache trước khi bị cập nhật, thường gọi là time to live (TTL).

Xem Khi nào cập nhật cache để biết các đánh đổi và phương án thay thế. Cách làm ở trên mô tả cache-aside.

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.

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êu 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, rồi 4) lặp lại. Xem Design a system that scales to millions of users on AWS như một ví dụ về cách mở rộng thiết kế ban đầu theo từng bước.

Đ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ụ, việc thêm Load Balancer cùng nhiều Web Server giải quyết những vấn đề gì? CDN? Master-Slave Replicas? Mỗi phương án có những lựa chọn thay thế và đánh đổi nào?

Chúng ta sẽ đưa thêm một số thành phần để hoàn thiện thiết kế và giải quyết các vấn đề về khả năng mở rộng. Các load balancer nội bộ không được vẽ để hình đỡ rối.

Để tránh lặp lại nội dung thảo luận, 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ở rộng Memory Cache ra nhiều máy

Để xử lý lượng request lớn và dung lượng bộ nhớ cần thiết lớn, chúng ta mở rộng theo chiều ngang. Có ba lựa chọn chính để lưu dữ liệu trên cluster Memory Cache:

Mỗi máy trong cache cluster có cache riêng - Đơn giản, nhưng nhiều khả năng cho tỷ lệ cache hit thấp.
Mỗi máy trong cache cluster giữ một bản sao của cache - Đơn giản, nhưng sử dụng bộ nhớ không hiệu quả.
Cache được shard trên tất cả các máy trong cache cluster - Phức tạp hơn, nhưng nhiều khả năng là lựa chọn tốt nhất. Ta có thể dùng hashing để xác định máy nào có thể giữ kết quả cache của một query bằng machine = hash(query). Nhiều khả năng ta sẽ muốn dùng consistent hashing.

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

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

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

NoSQL

Caching

Cache ở đâu
Cache cái gì
- Cache ở mức database query
- Cache ở 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 kiểu REST
- Giao tiếp nội bộ: RPC
Service discovery

Bảo mật

Xem phần bảo mật.

Con số latency

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 lại

Thiết kế key-value cache để lưu kết quả của các query gần đây nhất trên web server ​

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 ​

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: User gửi request và kết quả là cache hit ​

Cài đặt cache ​

Khi nào cập nhật cache ​

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

Mở rộng Memory Cache ra nhiều máy ​

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

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

NoSQL ​

Caching ​

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

Giao tiếp ​

Bảo mật ​

Con số latency ​

Liên tục ​

Thiết kế key-value cache để lưu kết quả của các query gần đây nhất trên web server

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

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: User gửi request và kết quả là cache hit

Cài đặt cache

Khi nào cập nhật cache

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

Mở rộng Memory Cache ra nhiều máy

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

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

NoSQL

Caching

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

Giao tiếp

Bảo mật

Con số latency

Liên tục