社交图谱

目的与范围

本文档详细介绍了社交网络图谱服务设计的技术实现。它重点关注高效存储和查询用户之间社交关系所需的数据结构和算法，并特别强调在大规模社交网络中查找用户间最短路径。

该设计解决了扩展社交图谱系统以处理1亿用户（平均每位用户50个朋友，共约50亿朋友关系）所面临的挑战。

来源: solutions/system_design/social_graph/README.md1-33

问题陈述

用例

我们的主要用例是允许用户搜索另一个用户，并查看与被搜索者之间的最短路径（例如，显示用户如何通过共同朋友连接起来）。

即使图数据无法在单台机器上存储，并且流量模式不均匀，该服务也必须保持高可用性。

约束与假设

1亿用户
平均每位用户50个朋友
50亿朋友关系
每月10亿次朋友搜索（平均每秒400次请求）
图边缘无权重
流量分布不均匀（有些搜索更受欢迎）
我们将使用传统系统而非Neo4j或GraphQL等专用图数据库

来源: solutions/system_design/social_graph/README.md15-47

高层架构

高级架构图

该系统包含以下关键组件

客户端：用户发起连接搜索的用户界面
Web服务器：作为内部服务的反向代理
搜索API服务器：处理用户搜索请求
用户图谱服务：查找用户之间路径的核心组件
查找服务：帮助查找哪个“人员服务器”包含用户数据
人员服务器：用于存储用户信息和朋友关系的分布式存储

来源: solutions/system_design/social_graph/README.md52-54 solutions/system_design/social_graph/README.md102-113

数据模型

人员实体

人员数据模型

Person 类是社交网络中表示用户的基本数据结构。每个用户都拥有

一个唯一标识符
一个姓名
一个朋友ID列表，表示与其他用户的连接

来源: solutions/system_design/social_graph/README.md154-161 solutions/system_design/social_graph/social_graph_snippets.py31-36

核心组件

查找服务

查找服务维护着人员ID与存储该用户数据的“人员服务器”之间的映射。该服务通过允许我们将用户数据分片到多个服务器来支持我们系统的分布式特性。

这项服务对于处理无法在单台机器上容纳的图数据至关重要。

来源: solutions/system_design/social_graph/README.md119-131 solutions/system_design/social_graph/social_graph_snippets.py39-46

人员服务器

人员服务器存储实际的用户数据。每个服务器负责一部分用户数据，这由分片策略决定。

来源: solutions/system_design/social_graph/README.md133-150 solutions/system_design/social_graph/social_graph_snippets.py49-59

用户图谱服务

用户图谱服务是实现社交图谱遍历算法的核心组件。它使用广度优先搜索（BFS）来查找两个用户之间的最短路径。

BFS算法流程

用户图谱服务的核心实现

BFS算法的工作原理是

从源用户开始
探索他们的所有朋友
然后探索朋友的朋友
持续进行直到找到目标用户或穷尽所有可能性

这种方法保证能找到两个用户之间的最短路径（最少跳数）。

来源: solutions/system_design/social_graph/README.md163-219 solutions/system_design/social_graph/social_graph_snippets.py62-72 solutions/system_design/social_graph/README.md63-100

API设计

该系统为客户端应用程序公开了一个RESTful API

GET /api/v1/friend_search?person_id=1234

响应示例

响应包含连接请求者与目标用户的路径，显示了连接链。

服务之间的内部通信使用远程过程调用（RPC）而非REST。

来源: solutions/system_design/social_graph/README.md221-247

扩展性考量

扩展架构图

为应对平均每秒400次请求（并在高峰期处理更高负载），我们实施了多种扩展策略

内存缓存：使用Redis或Memcached存储频繁访问的人员数据和预计算路径
批处理计算：离线预计算常用路径并存储在NoSQL数据库中
分片策略：按地理位置对“人员服务器”进行分片，因为朋友通常居住地相近
双向搜索：同时从源点和目标点执行BFS
优先处理高连接用户：首先从拥有众多朋友的用户开始BFS，因为他们更有可能减少分隔度数
时间/跳数限制：在询问用户是否要继续之前，设置搜索时间或跳数的限制

来源: solutions/system_design/social_graph/README.md249-286

优化技术

多项优化可以提升我们社交图谱系统的性能

优化	描述	优点
内存缓存	存储完整/部分BFS遍历结果	加速后续查找
离线计算	预计算常见搜索的路径	减少按需计算
批量朋友查找	在同一“人员服务器”上分组朋友查找	减少网络跳转
基于地理位置的分片	按位置对用户进行分片	提高数据访问的局部性
双向BFS	从源点和目标点同时搜索	可显著缩小搜索空间
高连接度节点优先级	从拥有大量连接的用户开始	通常更快地缩短路径长度
搜索限制	按时间或跳数限制搜索	防止资源过度使用

来源: solutions/system_design/social_graph/README.md273-286

额外考量

对于一个生产就绪的社交图谱系统，应考虑以下额外因素

缓存策略:
- 实施客户端、CDN、Web服务器、数据库和应用程序缓存
- 考虑旁路缓存、直写、回写和预加载模式
数据库设计:
- 对于用户配置文件，考虑NoSQL选项，如文档存储
- 对于社交连接，考虑专用图数据库
异步处理:
- 使用消息队列处理社交图谱的更新
- 为长时间运行的操作实现任务队列
安全考量:
- 实施适当的认证和授权
- 通过限制连接信息的可见性来确保隐私

来源: solutions/system_design/social_graph/README.md287-349

结论

该设计提供了一种可扩展的方法来实现社交图谱服务，能够处理1亿用户和50亿朋友关系。核心组件（用户图谱服务、查找服务和人员服务器）协同工作，以支持用户之间高效的路径查找。

通过实施上述优化技术，系统即使在高峰负载条件下也能保持高性能和高可用性。该设计遵循模块化架构，允许根据需要独立扩展不同组件。