为社交网络设计图数据结构：从 BFS 最短路径到亿级用户架构（system-design-primer 实战）

• 文档
• 教程
• 后端

本篇以 system-design-primer 仓库中 社交网络图数据结构设计 为核心骨架，完整还原系统设计面试中"为社交网络设计数据结构"这一经典考题的四步方法论：从用例与约束界定、高层架构设计、核心组件实现，到面向 1 亿用户与每月 10 亿次搜索的扩展设计。读完本文，你将掌握如何在单机 BFS 基线之上，用「查询服务 + 人员服务器」水平拆分支撑亿级节点图数据，并理解内存缓存、双向 BFS、批量预计算等一线优化手段及其取舍。

第 1 步：用例和约束概要

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

在真实面试中，需求往往需要通过与面试官的一问一答逐步澄清。在没有面试官的情况下，本文按以下方式自行定义用例和约束条件。

用例

我们将问题限定为只处理以下两个用例：

• 用户寻找某人，并显示与被寻人之间的最短路径
• 服务具备高可用性

也就是说，本设计不覆盖好友推荐、动态流（Feed）、关注关系等衍生功能，聚焦"最短路径查询"这一个核心场景。

约束和假设

状态假设

• 流量分布不均：某些搜索比别的更热门，同时某些搜索仅执行一次——这意味着缓存对热门查询收益极大，而对冷门查询几乎无效
• 图数据不适用单一机器：整张社交关系图无法放进一台服务器，必须水平拆分
• 图的边没有权重：最短路径退化为最少跳数（跳数最少）问题，可用无权 BFS 求解
• 1 亿用户（顶点规模）
• 每个用户平均有 50 个朋友（边规模）
• 每月 10 亿次朋友搜索（查询负载）

训练使用更传统的系统——不要用图特有的解决方案，例如 GraphQL 或图数据库如 Neo4j。这是一条重要的"约束"：它强制你思考如何用通用系统（关系/键值存储 + 应用层算法）解决图问题，而不是直接套用图数据库。

计算使用

向你的面试官厘清你是否应该做粗略的使用计算。这里的计算口径如下：

• 50 亿条朋友关系：1 亿用户 × 平均每人 50 个朋友
• 每秒 400 次搜索请求：10 亿次/月 折算而来

便捷的转换指南（面试中快速换算流量必备）：

（每月约 250 万秒。）

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

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

在没有规模约束时，图就是一个简单的内存对象；但在 1 亿用户、50 亿条边的约束下，我们必须引入服务拆分。下图是本文设计的基础架构（对应仓库中的social_graph_basic.png简化版示意图）：

高层设计的关键组件与职责划分：

• 客户端：发起朋友搜索请求
• Web 服务器：充当反向代理，统一入口、屏蔽后端细节
• 搜索 API 服务器（Search API）：应用层，接收并转发搜索请求
• 用户图服务（User Graph Service）：核心算法组件，负责执行 BFS 最短路径搜索
• 查询服务（Lookup Service）：维护person_id → person_server的路由映射，回答"某个用户的数据在哪台服务器上"
• 人员服务器（Person Server）：按person_id分片存储用户及其friend_ids列表

第 3 步：设计核心组件

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

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

和你的面试官说清你期望的代码量——面试中明确编码范围，避免过度实现或实现不足。

基线方案：单机无权 BFS

在没有"百万用户（点）和十亿朋友关系（边）"的限制时，无权最短路径问题可以用通用的 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

这段代码的关键设计点：

• prev_node_keys是一个"前驱节点"字典：prev_node_keys[子节点] = 父节点，BFS 结束后从dest沿着前驱链回溯到source，再反转即得完整路径；
• 借助State.visited（unvisited/visited 枚举）标记访问状态，保证每个节点至多入队一次，时间复杂度 O(V+E)；
• 用deque保证队列入队/出队均为 O(1)。

仓库中的 social_graph_snippets.py 给出了同思路的最小可运行骨架：State(Enum)定义unvisited/visited，Graph.bfs用队列完成可达性判断；同时它还定义了Person、LookupService、PersonServer、UserGraphService四个类的字段与接口（UserGraphService.bfs留作练习，注释明确要求"用self.visited_ids追踪访问过的节点、用self.lookup把 person_id 翻译成 Person"）。你可以把这两份代码对照阅读：README 里的UserGraphService._shortest_path就是 snippet 中留白接口的完整实现。

分布式拆分：查询服务 + 人员服务器

单机 BFS 无法承载所有用户，我们需要通过人员服务器拆分用户，并通过查询服务访问。请求的完整调用链如下：

1. 客户端向服务器发送请求，服务器作为反向代理
2. 搜索 API服务器向用户图服务转发请求
3. 用户图服务依次完成：
   • 使用查询服务找到当前用户信息存储的人员服务器
   • 找到适当的人员服务器检索当前用户的friend_ids列表
   • 把当前用户作为source运行 BFS 搜索算法，同时把当前用户的friend_ids作为每个adjacent_node的 id
   • 给定 id 获取adjacent_node：用户图服务将再次与查询服务通讯，最后判断出和给定 id 相匹配的存储adjacent_node的人员服务器（这一步存在优化空间——每扩展一层邻居就要做一次路由查询）

和你的面试官说清你应该写的代码量。以下代码是"面试口述级"的骨架实现；注释：为简洁起见省略了错误处理，请询问是否需要编写适当的错误处理方法。

查询服务实现——核心是person_id → person_server的路由表：

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]

人员服务器实现——按 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

用户（Person）实现——图的最小单元：

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

用户图服务实现——把"单机 BFS"改造为"跨服务器 BFS"的核心：

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

与单机版对比，这个分布式 BFS 有两个关键差异，也是面试中的高频追问点：

• 访问标记外置：单机版把visit_state存在节点对象内部；分布式版因为节点分散在多台服务器、且每次都要通过self.person()跨服务拉取，所以用独立的visited_ids集合在内存中维护访问状态，避免反复读写远端节点对象；
• 邻居获取变为远程调用：friend_node = self.person(friend_id)每次都会经过"查询服务 → 人员服务器"两级跳转，这是系统的主要延迟来源之一，也为第 4 步的优化埋下伏笔。

对外 API：REST

对外部客户端，我们使用公共的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", },

内部通信：RPC

服务之间的内部通信使用远端过程调用（RPC）。REST 适合面向客户端的、资源语义清晰的接口；而内部服务间的高频、低延迟调用更适合 RPC，二者分工是分布式系统设计的常见范式（详见仓库 README.md 中 "Remote procedure call (RPC)" 与 "Representational state transfer (REST)" 章节的对比讨论）。

第 4 步：扩展设计

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

重要：别简化从最初设计到最终设计的过程！正确的扩展路径是循环迭代的：1)基准/负载测试，2) 瓶颈概述（剖析），3) 当评估可选和折中方案时定位瓶颈，4) 重复。可以参考 在 AWS 上设计支持百万级到千万级用户的系统 了解如何一步步迭代扩展初始设计。

扩展后的完整架构如下图所示（对应仓库中的social_graph.png，新增 DNS、负载均衡器与内存缓存等组件）：

讨论初始设计可能遇到的瓶颈并逐一给出对策非常重要，例如：什么问题可以通过添加多台Web 服务器作为负载均衡解决？CDN？主从副本？每个问题都有哪些替代和折中方案？

为避免重复讨论，以下主题的详细谈资、折中方案和替代方案，请直接延伸阅读仓库 README.md（或中文版 README-zh-Hans.md）中的对应章节：域名系统（DNS）、负载均衡、横向扩展、Web 服务器（反向代理）、API 服务器（应用层）、缓存、一致性模式、可用性模式。

缓存：应对 400 请求/秒的关键一招

要解决平均每秒 400 次读请求（峰值更高）的约束，人员数据可以存放在Redis 或 Memcached 这类内存缓存中，以降低响应时间、减少对下游服务的流量。这对"连续多次搜索的用户"和"人脉极广的用户"尤其有效。

量化的延迟对比（仓库 README 的 "Latency numbers every programmer should know" 章节给出）：从内存顺序读取 1MB 数据大约需要 250 微秒，从 SSD 读取同样大小数据慢 4 倍，从硬盘读取慢 80 倍。这意味着把热点人员数据从磁盘/SSD 提升到内存，可带来数量级上的查询加速。

进一步的优化方案

• 在内存缓存中存储完整的或部分的 BFS 遍历结果，加快后续查找（空间换时间）
• 在NoSQL 数据库中批量离线计算并存储完整的或部分的 BFS 遍历，加快后续查找（对热门查询尤其划算）
• 通过把同一批朋友查找托管在同一台人员服务器上，减少机器跳转
  • 按地理位置拆分人员服务器可进一步优化——朋友通常住得都比较近，地理亲和性拆分能显著降低跨服务器查询比例
• 同时进行两个 BFS 查找：一个从 source 开始、一个从 destination 开始，然后合并两条路径（双向 BFS，能大幅缩小中间探索的顶点数量）
• 从有庞大朋友圈的人开始找起，更有可能减小当前用户和搜索目标之间的离散度数（六度分隔理论），提前收窄搜索空间
• 设置基于时间或跳数的阈值，当某些案例搜索耗时过长时，先询问用户是否继续查询（保护系统免受病态查询拖垮）
• 如果不存在"禁止使用图数据库"的限制，可以使用Neo4j 等图数据库或GraphQL 等图特定查询语法——注意本题的约束恰恰是训练使用传统系统，因此这些方案只在扩展讨论中被提及

额外的话题

根据问题的范围和剩余时间，可以继续深入以下话题。

SQL 扩展模式

• 读取副本（主从复制）：把读流量分摊到从库
• 联合（Federation）：按功能拆库，如把好友关系库与资料库分离
• 分区（Sharding）：按 person_id 或地理位置水平切分
• 反规范化：把friend_ids直接冗余存储在用户行内，避免多表 join（本设计中Person.friend_ids即反规范化思想的体现）
• SQL 调优：索引、查询缓存等

NoSQL

• 键值存储：person_id → Person天然契合本场景
• 文档存储：以 JSON 文档形式存储用户及其好友列表
• 宽表存储：适合按行聚合大量列的批量扫描
• 图数据库：如果允许，可直接表达邻接关系并内置图算法
• SQL vs NoSQL：结合一致性、扩展性、查询灵活性权衡

缓存

• 缓存到哪里：客户端缓存、CDN 缓存、Web 服务缓存、数据库缓存、应用缓存
• 缓存什么：数据库查询级别的缓存、对象级别的缓存（本设计中缓存的"对象"即 Person 及其 friend_ids）
• 何时更新缓存：预留缓存（cache-aside）、完全写入（write-through）、延迟写/写回（write-behind）、事先更新（refresh-ahead）——不同的更新策略对应不同的数据新鲜度与一致性取舍

异步性和微服务

• 消息队列：解耦好友关系变更与索引更新
• 任务队列：把离线 BFS 预计算放入后台任务
• 回退压力：当下游过载时，让上游减速而不是崩溃
• 微服务：查询服务、用户图服务、人员服务器均可以独立部署与扩缩容

沟通

关于折中方案的讨论：

• 客户端的外部通讯：遵循 REST 的 HTTP APIs
• 内部通讯：RPC
• 服务探索：在服务实例动态扩缩容时，查询服务如何发现新加入的人员服务器

安全性

参考仓库 README.md 的安全章节：认证鉴权、防 DDoS、防爬虫、私密数据脱敏等，都是社交网络系统上线前必须考虑的问题。

延迟数字指标

查阅仓库 README 中"每个程序员必懂的延迟数字"章节，用真实延迟量级指导缓存与存储选型（如本文引用的内存 250 微秒 / SSD 4x / 磁盘 80x 对比）。

正在进行

• 继续基准测试并监控你的系统，以解决不断出现的瓶颈问题
• 扩展是一个迭代的过程：设计 → 基准 → 剖析 → 优化 → 再设计，循环往复，永远不存在一劳永逸的"最终设计"

仓库源码参考

• 社交网络图数据结构设计（中文原文档）：本文主体内容的出处
• 社交网络图数据结构设计（英文原版）：术语与英文面试表述对照
• social_graph_snippets.py：最小可运行的类骨架（Graph/Person/LookupService/PersonServer/UserGraphService），UserGraphService.bfs留白可作为编码练习
• 扩展架构图（完整版） 与 基础架构图（简化版）：本文两处配图的仓库原件
• AWS 百万级用户系统设计：第 4 步迭代扩展方法的参照样例
• 系统设计主题总览（英文） 与 系统设计主题总览（中文）：负载均衡、缓存、一致性、可用性等通用主题的深入资料

• 文档
• 教程
• 后端