Kiến trúc hệ thốngThiết kế cấu trúc dữ liệu cho một mạng xã hội

Thiết kế cấu trúc dữ liệu cho một mạng xã hội

Nội dung bài

Thiết kế cấu trúc dữ liệu cho một mạng xã hội

Bài tập20 phút đọcThe System Design Primer - bài giải "Design the data structures for a social network"

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

Thiết kế cấu trúc dữ liệu cho một mạng xã hội

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

Hãy luyện tập sử dụng các hệ thống truyền thống - không dùng các giải pháp chuyên cho đồ thị như GraphQL hay một cơ sở dữ liệu đồ thị (graph database) như Neo4j

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 social graph

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 tìm kiếm một người nào đó và thấy đường đi ngắn nhất tới người được tìm

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

Nếu không có ràng buộc hàng triệu người dùng (đỉnh - vertex) và hàng tỷ quan hệ bạn bè (cạnh - edge), ta có thể giải bài toán đường đi ngắn nhất không trọng số này bằng thuật toán tìm kiếm theo chiều rộng (BFS - breadth-first search) thông thường:

class Graph(Graph):

    def shortest_path(self, source, dest):
        if source is None or dest is None:
            return None
        if source is dest:
            return [source.key]
        prev_node_keys = self._shortest_path(source, dest)
        if prev_node_keys is None:
            return None
        else:
            path_ids = [dest.key]
            prev_node_key = prev_node_keys[dest.key]
            while prev_node_key is not None:
                path_ids.append(prev_node_key)
                prev_node_key = prev_node_keys[prev_node_key]
            return path_ids[::-1]

    def _shortest_path(self, source, dest):
        queue = deque()
        queue.append(source)
        prev_node_keys = {source.key: None}
        source.visit_state = State.visited
        while queue:
            node = queue.popleft()
            if node is dest:
                return prev_node_keys
            prev_node = node
            for adj_node in node.adj_nodes.values():
                if adj_node.visit_state == State.unvisited:
                    queue.append(adj_node)
                    prev_node_keys[adj_node.key] = prev_node.key
                    adj_node.visit_state = State.visited
        return None
BFS mở rộng từng vòng quen biết: bạn trực tiếp trước, bạn của bạn sau Vòng 1 Vòng 2 Bạn nguồn Đích
BFS duyệt hết bạn trực tiếp (vòng 1) trước khi sang bạn của bạn (vòng 2), nên đường đi tìm được luôn là ngắn nhất.

Ta sẽ không thể chứa toàn bộ người dùng trên cùng một máy, nên cần phân mảnh (shard) người dùng ra nhiều Person Server và truy cập chúng thông qua một Lookup Service (dịch vụ tra cứu).

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

Lưu ý: Phần xử lý lỗi được lược bỏ bên dưới cho đơn giản. Hãy hỏi xem bạn có cần viết code xử lý lỗi đầy đủ hay không.

Cài đặt Lookup Service:

class LookupService(object):

    def __init__(self):
        self.lookup = self._init_lookup()  # key: person_id, value: person_server

    def _init_lookup(self):
        ...

    def lookup_person_server(self, person_id):
        return self.lookup[person_id]

Cài đặt Person Server:

class PersonServer(object):

    def __init__(self):
        self.people = {}  # key: person_id, value: person

    def add_person(self, person):
        ...

    def people(self, ids):
        results = []
        for id in ids:
            if id in self.people:
                results.append(self.people[id])
        return results

Cài đặt Person:

class Person(object):

    def __init__(self, id, name, friend_ids):
        self.id = id
        self.name = name
        self.friend_ids = friend_ids

Cài đặt User Graph Service:

class UserGraphService(object):

    def __init__(self, lookup_service):
        self.lookup_service = lookup_service

    def person(self, person_id):
        person_server = self.lookup_service.lookup_person_server(person_id)
        return person_server.people([person_id])

    def shortest_path(self, source_key, dest_key):
        if source_key is None or dest_key is None:
            return None
        if source_key is dest_key:
            return [source_key]
        prev_node_keys = self._shortest_path(source_key, dest_key)
        if prev_node_keys is None:
            return None
        else:
            # Duyệt ngược path_ids, bắt đầu từ dest_key
            path_ids = [dest_key]
            prev_node_key = prev_node_keys[dest_key]
            while prev_node_key is not None:
                path_ids.append(prev_node_key)
                prev_node_key = prev_node_keys[prev_node_key]
            # Đảo ngược danh sách vì ta đã duyệt ngược
            return path_ids[::-1]

    def _shortest_path(self, source_key, dest_key, path):
        # Dùng id để lấy Person
        source = self.person(source_key)
        # Cập nhật hàng đợi bfs
        queue = deque()
        queue.append(source)
        # prev_node_keys ghi lại từng bước nhảy từ
        # source_key tới dest_key
        prev_node_keys = {source_key: None}
        # Dùng visited_ids để ghi lại các node đã thăm,
        # khác với bfs thông thường vốn có thể
        # lưu trạng thái này ngay trong node
        visited_ids = set()
        visited_ids.add(source.id)
        while queue:
            node = queue.popleft()
            if node.key is dest_key:
                return prev_node_keys
            prev_node = node
            for friend_id in node.friend_ids:
                if friend_id not in visited_ids:
                    friend_node = self.person(friend_id)
                    queue.append(friend_node)
                    prev_node_keys[friend_id] = prev_node.key
                    visited_ids.add(friend_id)
        return None

Ta sẽ dùng một REST API công khai:

$ curl https://social.com/api/v1/friend_search?person_id=1234

Phản hồi:

{
    "person_id": "100",
    "name": "foo",
    "link": "https://social.com/foo",
},
{
    "person_id": "53",
    "name": "bar",
    "link": "https://social.com/bar",
},
{
    "person_id": "1234",
    "name": "baz",
    "link": "https://social.com/baz",
},

Với giao tiếp nội bộ, ta có thể dùng gọi thủ tục từ xa (RPC - Remote Procedure Call).

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ế social graph 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ế:

Để đáp ứng ràng buộc 400 yêu cầu đọc mỗi giây trung bình (cao hơn vào giờ cao điểm), dữ liệu người dùng có thể được phục vụ từ một Memory Cache (bộ nhớ đệm trong RAM) như Redis hoặc Memcached để giảm thời gian phản hồi và giảm lưu lượng tới các dịch vụ phía sau. Điều này đặc biệt hữu ích với những người thực hiện nhiều lượt tìm kiếm liên tiếp và những người có nhiều kết nối. Đọ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

Dưới đây là các tối ưu thêm:

So sánh vùng phải duyệt: BFS một chiều mở rộng tới tận đích, BFS hai chiều mỗi phía chỉ sâu một nửa rồi gặp nhau ở giữa Một chiều: dò từ nguồn tới tận đích Nguồn Đích ≈ b^d node Hai chiều: mỗi phía sâu d/2, gặp nhau ở giữa ≈ 2 × b^(d/2) node
BFS một chiều phải mở rộng tới độ sâu d (khoảng b^d node, b là số bạn trung bình); BFS hai chiều dò từ cả nguồn lẫn đích, mỗi phía chỉ sâu d/2 rồi gặp nhau ở giữa (khoảng 2 × b^(d/2) node). Hình phẳng chỉ minh hoạ — chênh lệch thật là theo hàm mũ.

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 the data structures for a social network" — 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ế cache key-value lưu kết quả các truy vấn gần nhất của web server