系统设计面试题 - 为一个社交网络设计数据结构

引用：
系统设计入门

为一个社交网络设计数据结构

解答

第一步：通过讨论，明确限制及用例，确定Scope

支持的用例：

• 用户可以搜索某个人，并看到连接到这个人的最短路径
• 系统高可用 high availability

不支持的用例：

• 无

Constraints and assumptions：

• 访问不均匀
• 100 million 个用户
• 每个用户大概有50个好友
• 每个月大约有1 billion 次搜索请求，每秒 400 次请求

计算规模：

• 连接关系：100 million * 50 = 5 billion，在一台机器上无法全部存储

第二步：高层次设计

为一个社交网络设计数据结构

第三步：设计核心组件

如果不考虑连接关系的存储问题，可以通过图的广度优先搜索来查找最短路径。
参见：数据结构 图的表示及相关算法&LeetCode题目

现假设用户信息存储在不同的机器上。
User Graph Service 的主要工作：

• 传入当前用户的 user_id，调用 Lookup Service 查询该用户的信息存储在哪一个 Person Server 上。
• 去对应的 Person Server 上查找当前用户的好友列表 friend_ids。
• 执行一轮广度优先搜索，对当前的每一个用户，重复执行上述两步。

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

第四步：扩展设计

为一个社交网络设计数据结构

• 为了同时响应更多请求，对服务器水平扩展，并使用Load Balancer做负载均衡。
• 为了加快读取效率，使用Memory Cache，避免频繁访问数据库。
• User Graph Service 和 Lookup Service 计算量和吞吐量比较大，可以创建多个实例。
• 设置一个搜索时间的阈值。