Kiến trúc hệ thốngThiết kế cache key-value lưu kết quả các truy vấn gần nhất của web server

Thiết kế cache key-value lưu kết quả các truy vấn gần nhất của web server

Nội dung bài

Thiết kế cache key-value lưu kết quả các truy vấn gần nhất của web server

Bài tập19 phút đọcThe System Design Primer - bài giải "Design a key-value cache to save the results of the most recent web server queries"

Mục lục
  1. Nội dung gốc
  2. Ghi chú của người dịch

Thiết kế cache key-value lưu kết quả các truy vấn gần nhất của web server

Nội dung gốc

Lưu ý: Tài liệu này dẫn link trực tiếp tới các phần liên quan trong danh mục chủ đề system design để tránh lặp lại. Hãy tham khảo nội dung được dẫn link để nắm các ý chính cần thảo luận, các đánh đổi (tradeoff) và các 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à xác định phạm vi 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õ, ta sẽ tự định nghĩa một số use case và ràng buộc.

Các trường hợp sử dụng (use cases)

Ta giới hạn bài toán chỉ xử lý 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

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) về mức sử dụng hay không.

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

Bước 2: Tạo thiết kế tổng quan (high level design)

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

Thiết kế tổng quan query cache

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.

Use case: Người dùng gửi yêu cầu và trúng cache

Các truy vấn phổ biến có thể được phục vụ từ một Memory Cache (bộ nhớ đệm trong RAM) như Redis hoặc Memcached để giảm độ trễ đọc và tránh làm quá tải Reverse Index Service (dịch vụ chỉ mục ngược) và Document Service (dịch vụ tài liệu). Đọ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 (disk) lâu hơn 80 lần.1

Vì cache có dung lượng giới hạn, ta sẽ dùng cách loại bỏ mục ít được dùng gần đây nhất (LRU - least recently used) để làm hết hạn các mục cũ.

Cài đặt cache

Cache có thể dùng một danh sách liên kết đôi (doubly-linked list): mục mới được thêm vào đầu (head), còn mục cần loại bỏ sẽ bị xóa ở cuối (tail). Ta dùng một bảng băm (hash table) để tra cứu nhanh tới từng node của danh sách liên kết.

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

Cài đặt Query API Server:

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):
        """Loại bỏ markup, tách văn bản thành các từ, xử lý lỗi chính tả,
        chuẩn hóa chữ hoa/thường, chuyển sang dạng dùng phép toán boolean.
        """
        ...

    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:

class Node(object):

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

Cài đặt LinkedList:

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:

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)
        """Lấy kết quả truy vấn đã lưu trong cache.

        Truy cập một node sẽ đưa vị trí của nó lên đầu danh sách LRU.
        """
        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):
        """Đặt kết quả cho key truy vấn tương ứng trong cache.

        Khi cập nhật một mục, đưa vị trí của nó lên đầu danh sách LRU.
        Nếu mục là mới và cache đã đầy, xóa mục cũ nhất
        trước khi thêm mục mới.
        """
        node = self.lookup[query]
        if node is not None:
            # Key đã có trong cache, cập nhật giá trị
            node.results = results
            self.linked_list.move_to_front(node)
        else:
            # Key chưa có trong cache
            if self.size == self.MAX_SIZE:
                # Xóa mục cũ nhất khỏi danh sách liên kết và bảng tra cứu
                self.lookup.pop(self.linked_list.tail.query, None)
                self.linked_list.remove_from_tail()
            else:
                self.size += 1
            # Thêm key và value mới
            new_node = Node(query, results)
            self.linked_list.append_to_front(new_node)
            self.lookup[query] = new_node
Danh sách liên kết đôi giữ thứ tự LRU: mục trúng được đưa lên đầu, mục cuối bị loại khi đầy, bảng băm tra node trong O(1) Đầu: mới dùng Cuối: loại khi đầy trúng: đưa lên đầu Bảng băm query → node, O(1)
Mục vừa dùng được đưa lên đầu danh sách; mục lâu nhất chưa dùng ở cuối bị loại khi cache đầy. Bảng băm (query → node) tìm đúng node trong O(1), danh sách liên kết đôi cho phép gỡ node ra và đưa lên đầu cũng trong O(1).
Khi nào cập nhật cache

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

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

Tham khảo 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 chính là mẫu cache-aside.

Bước 4: Mở rộng thiết kế (scale the design)

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

Điều quan trọng là thảo luận những điểm nghẽ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 Load Balancer với nhiều Web Server giải quyết được vấn đề gì? CDN? Master-Slave Replicas (bản sao master-slave)? Các phương án thay thế và đánh đổi của từng lựa chọn là gì?

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 load balancer nội bộ không được vẽ ra để sơ đồ đỡ 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 ý chính, đánh đổi và phương án thay thế:

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

Để xử lý lượng yêu cầu lớn và lượng bộ nhớ lớn cần dùng, ta sẽ mở rộng theo chiều ngang. Có ba phương án chính để lưu dữ liệu trên cụm (cluster) Memory Cache:

Sharding cache: hash(query) xác định đúng một máy trong cụm Truy vấn hash(query) Máy 1 Máy 2 Máy 3
Mỗi truy vấn qua hàm hash(query) để xác định đúng một máy chịu trách nhiệm, thay vì phải hỏi lần lượt từng máy trong cụm. Nếu chia theo số dư của số máy, thêm hoặc bớt một máy sẽ làm gần như mọi key đổi chỗ — lý do nên dùng băm nhất quán.

Các điểm thảo luận thêm (Additional talking points)

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

Các mẫu mở rộng SQL (SQL scaling patterns)

NoSQL

Bộ nhớ đệm (caching)

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

Giao tiếp (communications)

Bảo mật (security)

Tham khảo phần bảo mật.

Các con số độ trễ (latency numbers)

Xem Các con số độ trễ mọi lập trình viên nên biết.

Liên tục

Nguồn: The System Design Primer - bài giải "Design a key-value cache to save the results of the most recent web server queries" — 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

Hoàn thành lĩnh vực — xem lại các bài