尧图网站建设 
文档教程后端【免费下载链接】system-design-primerLearn how to design large-scale systems. Prep for the system design interview. Includes Anki flashcards.项目地址https://gitcode.com/GitHub_Trending/sy/system-design-primer点击查看免费下载本篇以 system-design-primer 仓库中 社交网络图数据结构设计 为核心骨架完整还原系统设计面试中为社交网络设计数据结构这一经典考题的四步方法论从用例与约束界定、高层架构设计、核心组件实现到面向 1 亿用户与每月 10 亿次搜索的扩展设计。读完本文你将掌握如何在单机 BFS 基线之上用「查询服务 人员服务器」水平拆分支撑亿级节点图数据并理解内存缓存、双向 BFS、批量预计算等一线优化手段及其取舍。第 1 步用例和约束概要收集需求并调查问题通过提问澄清用例和约束讨论假设。在真实面试中需求往往需要通过与面试官的一问一答逐步澄清。在没有面试官的情况下本文按以下方式自行定义用例和约束条件。用例我们将问题限定为只处理以下两个用例用户寻找某人并显示与被寻人之间的最短路径服务具备高可用性也就是说本设计不覆盖好友推荐、动态流Feed、关注关系等衍生功能聚焦最短路径查询这一个核心场景。约束和假设状态假设流量分布不均某些搜索比别的更热门同时某些搜索仅执行一次——这意味着缓存对热门查询收益极大而对冷门查询几乎无效图数据不适用单一机器整张社交关系图无法放进一台服务器必须水平拆分图的边没有权重最短路径退化为最少跳数跳数最少问题可用无权 BFS 求解1 亿用户顶点规模每个用户平均有 50 个朋友边规模每月 10 亿次朋友搜索查询负载训练使用更传统的系统——不要用图特有的解决方案例如 GraphQL 或图数据库如 Neo4j。这是一条重要的约束它强制你思考如何用通用系统关系/键值存储 应用层算法解决图问题而不是直接套用图数据库。计算使用向你的面试官厘清你是否应该做粗略的使用计算。这里的计算口径如下50 亿条朋友关系1 亿用户 × 平均每人 50 个朋友每秒 400 次搜索请求10 亿次/月 折算而来便捷的转换指南面试中快速换算流量必备请求速率每月请求量1 请求/秒250 万次请求40 请求/秒1 亿次请求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.visitedunvisited/visited 枚举标记访问状态保证每个节点至多入队一次时间复杂度 O(VE)用deque保证队列入队/出队均为 O(1)。仓库中的 social_graph_snippets.py 给出了同思路的最小可运行骨架State(Enum)定义unvisited/visitedGraph.bfs用队列完成可达性判断同时它还定义了Person、LookupService、PersonServer、UserGraphService四个类的字段与接口UserGraphService.bfs留作练习注释明确要求用self.visited_ids追踪访问过的节点、用self.lookup把 person_id 翻译成 Person。你可以把这两份代码对照阅读README 里的UserGraphService._shortest_path就是 snippet 中留白接口的完整实现。分布式拆分查询服务 人员服务器单机 BFS 无法承载所有用户我们需要通过人员服务器拆分用户并通过查询服务访问。请求的完整调用链如下客户端向服务器发送请求服务器作为反向代理搜索 API服务器向用户图服务转发请求用户图服务依次完成使用查询服务找到当前用户信息存储的人员服务器找到适当的人员服务器检索当前用户的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} # Well use visited_ids to keep track of which nodes weve # 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 步的优化埋下伏笔。对外 APIREST对外部客户端我们使用公共的REST API$ curl https://social.com/api/v1/friend_search?person_id1234响应最短路径上的一串用户{ 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/UserGraphServiceUserGraphService.bfs留白可作为编码练习扩展架构图完整版 与 基础架构图简化版本文两处配图的仓库原件AWS 百万级用户系统设计第 4 步迭代扩展方法的参照样例系统设计主题总览英文 与 系统设计主题总览中文负载均衡、缓存、一致性、可用性等通用主题的深入资料赞分享文档教程后端【免费下载链接】system-design-primerLearn how to design large-scale systems. Prep for the system design interview. Includes Anki flashcards.项目地址https://gitcode.com/GitHub_Trending/sy/system-design-primer点击查看免费下载相关推荐notepad-- macOS 快速上手指南一文搞定中文文本编辑器notepad macOS 快速上手指南一文搞定中文文本编辑器 notepad 是一款国产跨平台 macOS 文本编辑器自动识别 GBK、UTF 8 等二十文档教程后端如何设计高可用系统架构system-design-primer项目的完整指南如何设计高可用系统架构system design primer项目的完整指南 system design primer是一个专注于教授大型系统设计的开源项目文档教程后端如何用Mermaid Live Editor 5分钟创建专业流程图免费在线图表工具终极指南如何用Mermaid Live Editor 5分钟创建专业流程图免费在线图表工具终极指南 还在为技术文档中的图表绘制而烦恼吗想象一下你只需要写几行简单的前端开发者工具数据可视化上一篇Venus存储市场集成数据交易与存储证明机制的完整指南下一篇终极MagiskOnWSALocal双架构深度评测x64与ARM64版本性能对比实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 为社交网络设计图数据结构：从 BFS 最短路径到亿级用户架构（system-design-primer 实战）
文档教程后端【免费下载链接】system-design-primerLearn how to design large-scale systems. Prep for the system design interview. Includes Anki flashcards.项目地址https://gitcode.com/GitHub_Trending/sy/system-design-primer点击查看免费下载本篇以 system-design-primer 仓库中 社交网络图数据结构设计 为核心骨架完整还原系统设计面试中为社交网络设计数据结构这一经典考题的四步方法论从用例与约束界定、高层架构设计、核心组件实现到面向 1 亿用户与每月 10 亿次搜索的扩展设计。读完本文你将掌握如何在单机 BFS 基线之上用「查询服务 人员服务器」水平拆分支撑亿级节点图数据并理解内存缓存、双向 BFS、批量预计算等一线优化手段及其取舍。第 1 步用例和约束概要收集需求并调查问题通过提问澄清用例和约束讨论假设。在真实面试中需求往往需要通过与面试官的一问一答逐步澄清。在没有面试官的情况下本文按以下方式自行定义用例和约束条件。用例我们将问题限定为只处理以下两个用例用户寻找某人并显示与被寻人之间的最短路径服务具备高可用性也就是说本设计不覆盖好友推荐、动态流Feed、关注关系等衍生功能聚焦最短路径查询这一个核心场景。约束和假设状态假设流量分布不均某些搜索比别的更热门同时某些搜索仅执行一次——这意味着缓存对热门查询收益极大而对冷门查询几乎无效图数据不适用单一机器整张社交关系图无法放进一台服务器必须水平拆分图的边没有权重最短路径退化为最少跳数跳数最少问题可用无权 BFS 求解1 亿用户顶点规模每个用户平均有 50 个朋友边规模每月 10 亿次朋友搜索查询负载训练使用更传统的系统——不要用图特有的解决方案例如 GraphQL 或图数据库如 Neo4j。这是一条重要的约束它强制你思考如何用通用系统关系/键值存储 应用层算法解决图问题而不是直接套用图数据库。计算使用向你的面试官厘清你是否应该做粗略的使用计算。这里的计算口径如下50 亿条朋友关系1 亿用户 × 平均每人 50 个朋友每秒 400 次搜索请求10 亿次/月 折算而来便捷的转换指南面试中快速换算流量必备请求速率每月请求量1 请求/秒250 万次请求40 请求/秒1 亿次请求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.visitedunvisited/visited 枚举标记访问状态保证每个节点至多入队一次时间复杂度 O(VE)用deque保证队列入队/出队均为 O(1)。仓库中的 social_graph_snippets.py 给出了同思路的最小可运行骨架State(Enum)定义unvisited/visitedGraph.bfs用队列完成可达性判断同时它还定义了Person、LookupService、PersonServer、UserGraphService四个类的字段与接口UserGraphService.bfs留作练习注释明确要求用self.visited_ids追踪访问过的节点、用self.lookup把 person_id 翻译成 Person。你可以把这两份代码对照阅读README 里的UserGraphService._shortest_path就是 snippet 中留白接口的完整实现。分布式拆分查询服务 人员服务器单机 BFS 无法承载所有用户我们需要通过人员服务器拆分用户并通过查询服务访问。请求的完整调用链如下客户端向服务器发送请求服务器作为反向代理搜索 API服务器向用户图服务转发请求用户图服务依次完成使用查询服务找到当前用户信息存储的人员服务器找到适当的人员服务器检索当前用户的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} # Well use visited_ids to keep track of which nodes weve # 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 步的优化埋下伏笔。对外 APIREST对外部客户端我们使用公共的REST API$ curl https://social.com/api/v1/friend_search?person_id1234响应最短路径上的一串用户{ 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/UserGraphServiceUserGraphService.bfs留白可作为编码练习扩展架构图完整版 与 基础架构图简化版本文两处配图的仓库原件AWS 百万级用户系统设计第 4 步迭代扩展方法的参照样例系统设计主题总览英文 与 系统设计主题总览中文负载均衡、缓存、一致性、可用性等通用主题的深入资料赞分享文档教程后端【免费下载链接】system-design-primerLearn how to design large-scale systems. Prep for the system design interview. Includes Anki flashcards.项目地址https://gitcode.com/GitHub_Trending/sy/system-design-primer点击查看免费下载相关推荐notepad-- macOS 快速上手指南一文搞定中文文本编辑器notepad macOS 快速上手指南一文搞定中文文本编辑器 notepad 是一款国产跨平台 macOS 文本编辑器自动识别 GBK、UTF 8 等二十文档教程后端如何设计高可用系统架构system-design-primer项目的完整指南如何设计高可用系统架构system design primer项目的完整指南 system design primer是一个专注于教授大型系统设计的开源项目文档教程后端如何用Mermaid Live Editor 5分钟创建专业流程图免费在线图表工具终极指南如何用Mermaid Live Editor 5分钟创建专业流程图免费在线图表工具终极指南 还在为技术文档中的图表绘制而烦恼吗想象一下你只需要写几行简单的前端开发者工具数据可视化上一篇Venus存储市场集成数据交易与存储证明机制的完整指南下一篇终极MagiskOnWSALocal双架构深度评测x64与ARM64版本性能对比实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考