经典案例：社交网络好友关系与共同好友 (Social Graph - 类似 Facebook 与微信)¶

在现代社交网络（如微信、Facebook、Instagram、Twitter/微博、LinkedIn）中，人与人之间的连接关系构成了整个平台最核心的资产——社交图谱（Social Graph）。

初学者最感好奇的是：全网有数十亿用户，相互之间的好友关系多达数千亿条。系统如何在几毫秒内精确算出“你和张三有 18 个共同好友”？微信的“可能认识的人”又是如何通过二度人脉推荐给你的？

1. 初学者视角：单向关注 vs 双向好友的数据模型差异¶

在设计社交图谱之前，首先必须澄清业务上的两种截然不同的关系类型：

graph LR
    subgraph "1. 单向关注模型 (Twitter / 微博 / 抖音)"
    A1[用户 Alice] -->|关注| B1[用户 Bob]
    NoteNode["Alice 是 Bob 的粉丝;<br>Bob 可以不回关 Alice (有向图 Directed Graph)"]
    end

    subgraph "2. 双向好友模型 (微信 / Facebook)"
    A2[用户 Alice] <==>|互为好友| B2[用户 Bob]
    NoteNode["必须双方确认建立连接<br>(无向图 Undirected Graph)"]
    end

双向好友在关系型数据库中的存储技巧：¶

在底层存储无向图时，工业界最通用的做法是拆分成两条对称的有向边存储（冗余存储）： - 当 Alice 和 Bob 成为好友时，在数据库中同时插入两条记录：

INSERT INTO friends (user_id, friend_id) VALUES (Alice_ID, Bob_ID);
INSERT INTO friends (user_id, friend_id) VALUES (Bob_ID, Alice_ID);

- 巨大收益：当需要查询“Alice 的所有好友”时，直接执行 SELECT friend_id FROM friends WHERE user_id = Alice_ID，单列走索引，极速返回，完全避免了昂贵的 OR 关联查询！

2. 需求分析与系统范围 (Requirements & Scope)¶

2.1 功能性需求¶

好友关系管理：添加好友、同意申请、删除好友；
好友列表查询：分页查询指定用户的好友列表；
共同好友计算 (Mutual Friends)：计算任意两个用户之间的共同好友数量及详细列表；
二度人脉推荐 (People You May Know)：根据共同好友数量推荐“可能认识的人”。

2.2 非功能性需求¶

极低读取延迟 (Low Latency)：共同好友计算必须在 \(50\text{ ms}\) 以内完成；
海量边存储 (Scalability)：支持 10 亿用户与千亿级关系边的稳定存储与水平分片。

3. 存储选型对比：图数据库 vs 关系型表 vs 缓存¶

存储方案	优势	劣势与瓶颈	适用场景
图数据库 (如 Neo4j)	天然支持图结构，多度人脉深度遍历（如 4~6 度路径查找）极快。	难以水平分片扩展；面对千亿级边的海量写入吞吐乏力，运维成本极高。	反洗钱风控、小规模复杂知识图谱。
关系型数据库 (MySQL 分库分表)	技术成熟，支持强事务，按 `user_id` 分库分表扩展性良好。	复杂图遍历性能差，计算交集需在应用层完成。	关系持久化存储的主数据库（底座）。
分布式内存缓存 (Redis Set / ZSET)	纯内存位操作，读写极快，原生支持集合交集计算（`SINTER`）。	内存成本昂贵；超大好友列表（大 Key）易阻塞 Redis 单线程。	高频在线查询、共同好友实时计算。

4. 核心算法：共同好友 (Mutual Friends) 秒级计算¶

如何计算 Alice 和 Bob 的共同好友？本质上是求两个集合的交集：\(S_{\text{Alice}} \cap S_{\text{Bob}}\)。

4.1 方案一：Redis 集合交集 (`SINTER`)¶

如果用户的好友 ID 均存储在 Redis Set 中：

# 直接调用 Redis 原生求交集命令
SINTER user:alice:friends user:bob:friends

- 适用场景：普通用户（好友数 \(< 500\) 人）时极其高效； - 潜在风险（大 Key 问题）：若两名用户各自拥有 5000 名好友，SINTER 是一个 \(O(N \times M)\) 操作，在 Redis 单线程中会阻塞长达数毫秒甚至十几毫秒，影响整个 Redis 实例的其他请求。

4.2 方案二：有序数组双指针归并求交集 (工业首选)¶

工业大厂（如 Facebook、微信）普遍采用应用层双指针归并算法：

数据库或缓存中存储的好友 ID 列表保持严格升序排列（例如保存在有序数组中）；
计算交集时，将 Alice 和 Bob 的两个有序好友数组加载到应用服务器内存中；
使用双指针（Two Pointers）同时向前遍历：

graph TD
    subgraph "Alice 的好友 (有序)"
    A["[ 2, 5, 8, 11, 14, 19 ]"]
    end

    subgraph "Bob 的好友 (有序)"
    B["[ 1, 5, 7, 8, 19, 22 ]"]
    end

    A & B --> DualPointer["双指针线性扫描:<br>1. 指针指向 2 和 1: 1 < 2, Bob 指针右移<br>2. 指针指向 2 和 5: 2 < 5, Alice 指针右移<br>3. 指针指向 5 和 5: 相等! 命中共同好友 5!<br>4. 类似归并排序继续向前..."]

    DualPointer --> Result["共同好友: [ 5, 8, 19 ] (共 3 个)"]

算法时间复杂度：严格为 \(O(M + N)\)（\(M\) 和 \(N\) 为两人的好友数）；
面对微信的 5000 好友上限，两个长度为 5000 的整型数组执行双指针扫描，在现代 CPU 上只需耗费不到 10 微秒（\(0.01\text{ ms}\)）！
完全将计算压力从 Redis 单线程卸载到无状态的 Web 服务器集群中，性能与扩展性达到极致。

5. 面试深挖：二度人脉推荐 (People You May Know)¶

当你打开社交软件，系统提示“你可能认识李四，你们有 12 个共同好友”。这个二度人脉（Friend-of-a-Friend，FOAF）是如何算出来的？

graph TD
    Alice[用户 Alice] -->|一度好友| Friend1[好友 张三]
    Alice -->|一度好友| Friend2[好友 王五]

    Friend1 -->|张三的好友| Target["李四 (Alice 的二度好友)"]
    Friend2 -->|王五的好友| Target

    Note["通过张三和王五两个路径都触达了李四<br>李四的权重得分 +2! 优先推荐给 Alice!"]

工业计算架构（离线分析与实时混合）：¶

全量计算开销巨大：若用户有 1000 个好友，每个好友又有 1000 个好友，二度人脉潜在候选人高达 \(1000 \times 1000 = 1,000,000\) 个！在线实时计算会直接超时。
离线计算方案：
每天凌晨由大数据集群（Apache Spark）运行分布式图计算任务；
统计每个用户的二度人脉出现的频次（即共同好友数）；
过滤掉已经是一度好友的人，以及在黑名单中的人；
取 Top 50 结果预先存入 Redis 推荐缓存中；
当用户打开 App 时，直接从缓存中秒级读取推荐名单。