企业官网建设流程全解析

• 文档
• 教程
• 后端

本文以 system-design-primer 仓库中 Design the data structures for a social network 为骨架，完整讲解如何从零设计一个支撑「亿级用户、十亿好友关系」的社交网络数据结构与"找朋友最短路径"系统：从需求估算、单机 BFS 算法原型，到分片存储、查询服务与用户图服务的分层实现，再到缓存与迭代扩展。读完本文，你将掌握一套可直接复用于系统设计面试与分布式图应用实战的完整方法论与配套 Python 代码。

问题定义：为社交网络设计数据结构

该题目的完整描述位于 README 的面试题清单 中。核心诉求是：用户搜索某人时，系统能返回从当前用户到目标用户之间的最短路径，同时保证服务高可用。解题时要求使用更传统的系统组件（如 Web 服务器、数据库、缓存），不要使用图数据库（如 Neo4j）或图专用查询语言（如 GraphQL），以此检验工程师对通用分布式系统原语的理解深度。

第 1 步：用例与约束的收集与估算

用例范围

• 用户搜索某人，看到与被搜人之间的最短路径；
• 服务保持高可用。

假设条件

• 流量分布不均：部分搜索非常热门，另一些可能只被搜索一次；
• 图数据无法放入单台机器；
• 图的边（好友关系）没有权重；
• 1 亿用户；
• 每个用户平均 50 个好友；
• 每月 10 亿次好友搜索。

用量估算（back-of-the-envelope）

• 50 亿条好友关系：1 亿用户 × 平均每人 50 个好友；
• 每秒约 400 次搜索请求：10 亿次/月 ÷ 250 万秒/月。

常用换算速查表（面试时可直接引用）：

面试提示：做估算前应先向面试官确认是否需要，避免在不必要的地方浪费时间。

第 2 步：高级设计方案

整体架构采用经典的分层模式：客户端 → DNS → 负载均衡 → Web 服务器（反向代理）→ 搜索/查询 API → 用户图服务 → 查询服务（Lookup Service）→ 人员服务器（Person Server），人员数据前端还可叠加内存缓存层。其中：

• 客户端向Web 服务器发起请求，Web 服务器作为反向代理；
• 搜索 API 服务器把请求转发给用户图服务（User Graph Service）；
• 用户图服务负责执行 BFS 最短路径计算，并与查询服务、人员服务器协作获取图数据。

第 3 步：核心组件设计

单机基线：基于 BFS 的无权重最短路径

在不考虑亿级规模时，无权重图上的最短路径可以直接用 BFS 求解。仓库 social_graph_snippets.py 提供了配套的Graph.bfs()实现（使用deque队列与State枚举标记访问状态）；README 则给出了返回完整路径的扩展版：

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以"节点 key → 前驱节点 key"的形式记录路径；找到目标后从dest反向回溯到source，最后把列表反转得到[source, ..., dest]。

分布式化：Person Server + Lookup Service

1 亿用户无法放入单机内存，必须把用户**分片（shard）**到多台Person Server，并通过Lookup Service定位每个用户落在哪台服务器上。README 给出了三个基础类的实现：

Lookup Service——维护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]

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

Person——用户数据模型，好友关系以friend_ids列表（邻接表）形式存储：

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

仓库佐证：social_graph_snippets.py 中Person把friend_ids初始化为空列表、PersonServer.get_people()按 id 批量取用户、LookupService.get_person()通过映射直达目标服务器，与 README 的接口设计一一对应。

用户图服务：跨分片的 BFS

User Graph Service是执行最短路径的核心服务，它把"单机 BFS"改造成"分布式 BFS"：每个节点不再通过adj_nodes直接访问邻居，而是通过person(friend_id)经 Lookup Service 从对应 Person Server 拉取好友数据：

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

与单机版的三个关键差异：

1. 用visited_ids（set）替代节点上的visit_state：因为 Person 数据散落在不同服务器，不能依赖在节点对象上打标记；
2. 每次展开邻居都要走一次 Lookup：self.person(friend_id)需要再次与 Lookup Service 通信，判断存储该好友的 Person Server（README 明确指出这是潜在的优化点）；
3. 调用链：User Graph Service 先通过 Lookup Service 找到当前用户所在的 Person Server、取得其friend_ids列表，再以当前用户为source、以好友 id 为各adjacent_node的键执行 BFS。

仓库佐证：social_graph_snippets.py 中的UserGraphService构造时接收person_ids与lookup，并维护self.visited_ids集合，注释明确说明要用visited_ids跟踪访问节点、用lookup把person_id翻译成Person——正是 README 分布式 BFS 设计的骨架预留。

对外 API：REST 与内部 RPC

对外使用公共REST API（相关原理见主 README 的 REST 章节：REST 以资源为中心、无状态、可缓存，适合横向扩展与公开 HTTP 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（参见主 README 的 RPC 章节）：RPC 聚焦"行为调用"，可手工定制原生调用以贴合场景，常用于对性能敏感的内部通信；REST 与 RPC 的典型操作对比可参考主 README 的 RPC 与 REST 调用对比表。

面试提示：动手写代码前应向面试官确认期望的代码量；为简洁起见上述实现省略了错误处理，正式实现前应确认是否需要补充。

第 4 步：扩展设计

迭代扩展方法论

不要直接从初始设计跳到最终设计。正确流程是：1)基准测试/负载测试；2) **剖析（Profile）**定位瓶颈；3) 评估替代方案与折中后解决瓶颈；4) 重复以上步骤。仓库中 在 AWS 上设计可扩展到百万级用户的系统 提供了逐步迭代扩展的完整范例。

要主动思考：加入负载均衡与多台Web 服务器能解决什么问题？CDN？主从副本？各自有哪些替代方案与折中？这些话题的讨论要点见主 README 对应章节：

• DNS：域名解析与基于权重的轮询、地理路由；
• 负载均衡：分发请求、隔离故障节点、消除单点；L4/L7 两种工作层次；
• 横向扩展：用廉价通用硬件扩展而非垂直升级单机；
• Web 服务器（反向代理）：集中内部服务、SSL 终止、压缩、缓存与静态内容服务；
• API 服务器（应用层）：Web 层与应用层分离，可独立伸缩，微服务化；
• 缓存：客户端/Web/数据库/应用多级缓存，cache-aside、write-through、write-behind、refresh-ahead 四种更新策略；
• 一致性模式：弱一致、最终一致、强一致；
• 可用性模式：主备/双活故障切换与复制。

用内存缓存吸收热点读

为满足平均 400 req/s（峰值更高）的读请求，可将人员数据放入Redis 或 Memcached之类的内存缓存，缩短响应时间并减轻下游服务压力。这对连续多次搜索的用户、以及社交关系非常广的用户尤其有效。延迟数字依据（详见主 README 的 延迟数字速查）：

• 内存中顺序读 1 MB ≈ 250 微秒；
• SSD 顺序读 1 MB ≈ 1 毫秒（约为内存的 4 倍）；
• 磁盘（HDD）顺序读 1 MB ≈ 30 毫秒（约为内存的 120 倍）。

进一步优化清单

• 内存中缓存完整或部分的 BFS 遍历结果，加速后续相同/相近查询；
• 在 NoSQL 数据库中离线批量预计算，存储完整或部分 BFS 遍历结果供在线查询（结合主 README 的 NoSQL 概述：NoSQL 数据反规范化、join 一般在应用层完成，多数缺乏强 ACID、倾向于最终一致）；
• 批量合并同一台 Person Server 上的好友查询，减少跨机器跳转；
• 按地理位置分片 Person Server：朋友通常住得较近，地理分片可进一步减少跨服务器访问（分片的具体折中见主 README 的 Sharding 章节：数据分布可能倾斜、跨分片 join 复杂、需用一致性哈希缓解再平衡成本）；
• 双向 BFS：同时从source和destination出发，各自搜索后合并两条路径；
• 从好友数量多的人开始搜索：这些节点更可能缩小当前用户与目标之间的分离度数；
• 设置时间或跳数上限：某些搜索耗时过长时，先询问用户是否继续；
• 若没有"禁止使用图数据库"的约束，可选用 Neo4j 等图数据库或 GraphQL 等图专用查询语言（图数据库特点见主 README 的 Graph database 章节：针对复杂多对多关系优化，但相对较新、工具链与资源较少）。

延伸讨论话题

根据问题范围与剩余时间，可继续深入以下主题（均可在主 README 中找到对应章节）：

• SQL 扩展模式：主从复制、联邦（按功能分区）、分片、反规范化、SQL 调优（基准测试与慢查询日志剖析、收紧 schema、合理索引、避免昂贵 join、分区表、查询缓存调优）；
• NoSQL 选型：键值存储（哈希表抽象，O(1) 读写）、文档存储、宽列存储、图数据库、SQL 与 NoSQL 对比；
• 缓存：缓存位置（客户端/Web/数据库/应用层）、缓存内容（查询级/对象级，建议缓存用户会话、整页、活动流、用户图数据）、更新策略（cache-aside、write-through、write-behind、refresh-ahead）的适用场景与缺陷，详见主 README 的 缓存章节；
• 异步与微服务：消息队列（发布作业、后台处理）、任务队列（计算密集任务）、背压（限制队列长度，队列满时返回 HTTP 503 让客户端退避重试）、微服务；
• 通信：对外用遵循 REST 的 HTTP API，对内用 RPC（含 服务发现，如 Consul、Etcd、Zookeeper 维护服务注册与健康检查）；
• 安全性：参考主 README 的 安全章节（传输与存储加密、输入消毒防 XSS 与 SQL 注入、参数化查询）；
• 延迟数字：见 Latency numbers every programmer should know。

总结与面试要点

• 方法论：先定义用例与约束并做粗略估算，再画高级架构，然后逐个设计核心组件，最后按"基准测试 → 剖析 → 针对性优化 → 重复"的节奏迭代扩展；
• 数据结构：用Person（邻接表friend_ids）+PersonServer（分片存储）+LookupService（id → 服务器映射）承载亿级图数据，用UserGraphService做跨分片 BFS；
• 工程取舍：分布式 BFS 的代价是每次取邻居都要查一次 Lookup，换取的是把图数据水平拆散到多机的能力；随后用内存缓存、离线预计算、双向 BFS、地理分片等手段逐步逼近 400 req/s 的目标；
• 持续迭代：扩展不是一次性的，要持续基准测试与监控，按需引入负载均衡、CDN、复制与缓存等组件，并为每个组件准备好"替代方案与折中"的讨论话术。

相关代码与资料：social_graph 完整解答、配套 Python 片段、系统设计主题索引、scaling_aws 迭代扩展范例、中文版解答。

• 文档
• 教程
• 后端