注释：为了避免重复，这篇文章的链接直接关联到 System Design 主题的相关章节，作为讨论要点、trade-offs 和可选方案的参考。

第 1 步：用例和约束概要

收集需求并调查问题。通过提问清晰用例和约束。讨论假设。

如果没有面试官提出明确的问题，我们将自己定义一些用例和约束条件。

用例

我们就处理以下用例审视这一问题

用户寻找某人并显示与被寻人之间的最短路径
服务 high availability

约束和假设

状态假设

流量分布不均
- 某些搜索比别的更热门，同时某些搜索仅执行一次
graph data 不适合单机
图的 edges 没有权重
1 千万用户
每个用户平均有 50 个朋友
每月 10 亿次朋友搜索

训练使用更传统的系统 - 别用图特有的解决方案例如 GraphQL 或图 database 如 Neo4j。

计算使用

向你的面试官厘清你是否应该做粗略的使用计算

50 亿朋友关系
- 1 亿用户 * 平均每人 50 个朋友
每秒 400 次搜索请求

便捷的转换指南：

每月 250 万秒
每秒 1 个请求 = 每月 250 万次请求
每秒 40 个请求 = 每月 1 亿次请求
每秒 400 个请求 = 每月 10 亿次请求

第 2 步：创建高级设计方案

用所有重要组件概述高水平设计

Imgur

第 3 步：设计核心组件

深入每个核心组件的细节。

用例：用户搜索某人并查看到被搜人的最短路径

和你的面试官说清你期望的代码量

没有百万用户（点）的和十亿朋友关系（边）的限制，我们能够用一般 BFS 方法解决无权重最短路径任务：

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

我们不能在同一台机器上满足所有用户，我们需要通过 人员服务器 拆分用户并且通过 查询服务 访问。

客户端 向 服务器 发送请求，服务器 作为 reverse proxy
搜索 API 服务器向 用户图服务 转发请求
用户图服务 有以下功能：
- 使用 查询服务 找到当前用户信息存储的 人员服务器
- 找到适当的 人员服务器 检索当前用户的 friend_ids 列表
- 把当前用户作为 source 运行 BFS 搜索算法同时当前用户的 friend_ids 作为每个 adjacent_node 的 ids
- 给定 id 获取 adjacent_node:
  - 用户图服务 将再次和 查询服务 通讯，最后判断出和给定 id 相匹配的存储 adjacent_node 的 人员服务器（有待优化）

和你的面试官说清你应该写的代码量

注释：简易版错误处理执行如下。询问你是否需要编写适当的错误处理方法。

查询服务 实现：

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]

人员服务器 实现：

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

用户实现：

class Person(object):

    def __init__(self, id, name, friend_ids):
        self.id = id
        self.name = name
        self.friend_ids = 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

我们用的是公共的 REST API：

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

响应：

{
    "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",
},

内部通信使用远端过程调用。

第 4 步：扩展设计

在给定约束条件下，定义和确认瓶颈。

Imgur

重要：别简化从最初设计到最终设计的过程！

你将要做的是：1) 基准/负载测试， 2) 瓶颈概述， 3) 当评估可选和折中方案时定位瓶颈，4) 重复。以在 AWS 上设计支持百万级到千万级用户的系统为参考迭代地扩展最初设计。

讨论最初设计可能遇到的瓶颈和处理方法十分重要。例如，什么问题可以通过添加多台 Web 服务器 作为 load balancing 解决？CDN？主从副本？每个问题都有哪些替代与 trade-offs？

我们即将介绍一些组件来完成设计并解决 scalability 问题。内部 load balancing 不显示以减少混乱。

避免重复讨论，以下网址链接到 System Design 主题相关的主流方案、折中方案和替代方案。

解决平均每秒 400 次请求的限制（峰值），人员数据可以存在例如 Redis 或 Memcached 这样的 内存 cache 中以减少响应次数和下游通信开销。这尤其在用户执行多次连续查询和查询广泛连接的人时很有用。从内存读取 1MB 数据约 250 微秒，从 SSD 读同样大小数据时间约 4 倍，从硬盘约 80 倍。^{<a href=https://github.com/donnemartin/system-design-primer#latency-numbers-every-programmer-should-know>1}