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

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 tìm kiếm một người và xem đường đi ngắn nhất tới người được tìm
• 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
  • Một số lượt tìm kiếm phổ biến hơn các lượt khác, trong khi có những lượt chỉ được thực hiện một lần
• Dữ liệu đồ thị không vừa trên một máy
• Các cạnh của đồ thị không có trọng số
• 100 triệu user
• Trung bình 50 bạn bè mỗi user
• 1 tỷ lượt tìm kiếm bạn bè mỗi tháng

Hãy luyện tập với các hệ thống truyền thống hơn: không dùng các giải pháp chuyên cho đồ thị như GraphQL hay graph database như Neo4j

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.

• 5 tỷ quan hệ bạn bè
  • 100 triệu user * trung bình 50 bạn bè mỗi user
• 400 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.

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

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

Nếu không có ràng buộc về hàng triệu user (đỉnh) và hàng tỷ quan hệ bạn bè (cạnh), ta có thể giải bài toán đường đi ngắn nhất trên đồ thị không trọng số này bằng cách tiếp cận BFS 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

Ta không thể đặt toàn bộ user trên cùng một máy, nên cần shard user ra nhiều Person Server và truy cập chúng thông qua một Lookup Service.

• 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 Search API
• Server Search API chuyển tiếp request tới User Graph Service
• User Graph Service làm các việc sau:
  • Dùng Lookup Service để tìm Person Server đang lưu thông tin của user hiện tại
  • Tìm Person Server phù hợp để lấy danh sách friend_ids của user hiện tại
  • Chạy tìm kiếm BFS, lấy user hiện tại làm source và dùng friend_ids của user hiện tại làm id cho từng adjacent_node
  • Để lấy adjacent_node từ một id cho trước:
    • User Graph Service sẽ lại phải giao tiếp với Lookup Service để xác định Person Server nào lưu adjacent_node khớp với id đó (có thể tối ưu)

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

Lưu ý: Phần xử lý lỗi được bỏ qua bên dưới cho đơn giản. Hãy hỏi xem có nên viết 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:
            # Iterate through the path_ids backwards, starting at 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]
            # Reverse the list since we iterated backwards
            return path_ids[::-1]

    def _shortest_path(self, source_key, dest_key, path):
        # Use the id to get the Person
        source = self.person(source_key)
        # Update our bfs queue
        queue = deque()
        queue.append(source)
        # prev_node_keys keeps track of each hop from
        # the source_key to the dest_key
        prev_node_keys = {source_key: None}
        # We'll use visited_ids to keep track of which nodes we've
        # visited, which can be different from a typical bfs where
        # this can be stored in the node itself
        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

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

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

Response:

{
    "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ộ, 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.

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

• DNS
• Load balancer
• Horizontal scaling
• Web server (reverse proxy)
• API server (application layer)
• Cache
• Các mẫu nhất quán
• Các mẫu sẵn sàng

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

• Lưu kết quả duyệt BFS đầy đủ hoặc một phần trong Memory Cache để tăng tốc các lần tra cứu sau
• Tính toán theo batch offline rồi lưu kết quả duyệt BFS đầy đủ hoặc một phần trong NoSQL Database để tăng tốc các lần tra cứu sau
• Giảm số lần nhảy giữa các máy bằng cách gom các lần tra cứu bạn bè nằm trên cùng một Person Server thành một batch
  • Shard Person Server theo vị trí địa lý để cải thiện thêm, vì bạn bè thường sống gần nhau
• Chạy hai lượt tìm kiếm BFS cùng lúc, một lượt xuất phát từ nguồn và một lượt từ đích, rồi ghép hai đường đi lại
• Bắt đầu tìm kiếm BFS từ những người có rất nhiều bạn bè, vì họ có nhiều khả năng làm giảm số bậc phân cách giữa user hiện tại và người được tìm
• Đặt giới hạn theo thời gian hoặc số bước nhảy trước khi hỏi user có muốn tiếp tục tìm hay không, vì trong một số trường hợp việc tìm kiếm có thể mất khá nhiều thời gian
• Dùng Graph Database như Neo4j hoặc ngôn ngữ truy vấn chuyên cho đồ thị như GraphQL (nếu không có ràng buộc cấm dùng Graph Database)

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

• Read replicas
• Federation
• Sharding
• Denormalization
• SQL Tuning

NoSQL

• Key-value store
• Document store
• Wide column store
• Graph database
• SQL so với NoSQL

Caching

• Cache ở đâu
  • Client caching
  • CDN caching
  • Web server caching
  • Database caching
  • Application caching
• Cache cái gì
  • Cache ở mức database query
  • Cache ở mức object
• Khi nào cập nhật cache
  • Cache-aside
  • Write-through
  • Write-behind (write-back)
  • Refresh-ahead

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

• Message queue
• Task queue
• Back pressure
• 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