06 分而治之：从归并排序到 MapReduce 到分片

开篇提问

先看一个让你感受”分治”威力的对比：

要在 10 亿条记录里找一条特定的数据。

单台机器顺序扫描：假设每秒扫 100 万条 → 1000 秒（约 17 分钟）
100 台机器并行，每台扫 1000 万条 → 10 秒

快了 100 倍，而且这就是”分而治之”的全部直觉：把大任务拆成小任务，分头做，再合并结果。

但我想请你回答一个更尖锐的问题：

分治真的”解决”了问题吗？还是它只是把一个问题换成了另一个问题？如果你把任务拆给 100 台机器，你引入了什么新的麻烦？

这第二问才是分治的精髓所在。因为分治从来不是免费的——它用”协调的复杂度”换了”规模的扩展性”。理解这笔交易，你才知道什么时候该分、什么时候不该分。

子主题一：分治的三个步骤与它的适用条件

分治的经典结构就三步：分解（Divide）→ 解决（Conquer）→ 合并（Combine）。

但这个结构要成立，有个前提条件，非常关键：

子问题必须”足够独立”——子问题之间不能有太多依赖，否则分解和合并的成本会吃掉并行的收益。

想想归并排序：把数组切成两半，各自排序，然后合并。切开的左右两半互不干扰（排序左半边不需要知道右半边的内容），合并也只需要线性的归并操作。所以归并排序是分治的完美案例。

反例：计算斐波那契数列 fib(n) = fib(n-1) + fib(n-2)。你当然可以”分解”成两个子问题，但子问题之间高度重叠（fib(n-2) 被重复计算了无数次），所以朴素的分治反而比顺序计算慢指数倍。

这个判据极其实用：在你决定”要不要分而治之”之前，先问一句——子问题之间的耦合有多强？合并的成本有多高？

子问题独立、合并便宜 → 分治收益巨大（排序、MapReduce 的 map 阶段、分片）
子问题有依赖、合并昂贵 → 分治可能是陷阱（需要全局状态的任务、图算法）

子主题二：分治的”隐藏成本”——你换来了什么麻烦

回到开篇那个尖锐的问题。把任务分给 100 台机器，你引入了什么新麻烦？

麻烦一：协调成本。 谁负责分？谁负责收？有人失败了怎么办？这些”管理开销”在单机上根本不存在。

麻烦二：失败成为常态。 单机上，一台机器挂掉是”事故”；100 台机器里，每天有一两台挂掉是”统计必然”。你必须把失败当成正常流程处理——这是分布式系统和单机系统的根本区别。

麻烦三：数据倾斜（最阴险的一个）。 你以为把数据均分成 100 份，但实际可能 90% 的数据都集中在某几个 key 上——于是 97 台机器秒完，3 台机器累死。整体耗时由最慢的那台决定，加速比远低于 100 倍。（这就是你在上一本书里见过的”热分片”问题。）

麻烦四：合并阶段可能成为新瓶颈。 如果所有子结果都要汇总到一个节点做最终合并，那这个节点就是单点瓶颈——你并行了计算，却串行了合并。

麻烦五：跨分片操作变复杂。 单机上一个事务搞定的事，分片后要跨机器协调（分布式事务、两阶段提交），复杂度和延迟都暴涨。

看清楚了吗？分治不是”把 1 个大问题变成 100 个小问题”，而是”把 1 个计算问题变成 100 个小计算问题 + 1 个协调问题”。 那 100 个小问题确实变简单了，但那个协调问题，往往是真正难的部分。

子主题三：Amdahl 定律——加速比的天花板

分治能加速多少？有个精确的定律回答这个问题——Amdahl 定律：

如果一个任务中，有比例 P 的部分可以并行，其余 (1-P) 必须串行，那么无论用多少处理器，加速比的上限是 1/(1-P)。

举例：

90% 可并行 → 加速比上限 = 1/0.1 = 10 倍。就算你用 1000 台机器，也最多快 10 倍。
99% 可并行 → 上限 100 倍
99.9% 可并行 → 上限 1000 倍

这个定律残酷的地方在于：它是非线性收益递减的。 从 90% 提到 99%，加速上限翻 10 倍；但要把并行比例从 99% 提到 99.9%，工程难度可能增加 10 倍。

Amdahl 定律最重要的工程含义是：

优化串行部分，比增加并行度更划算。 因为并行度受天花板限制，而串行部分的每一点改善都直接提高天花板。

映射到分治场景：合并阶段、协调开销、数据倾斜——这些就是”串行部分”。优化它们（让合并也能并行、让数据更均匀、减少协调）比简单粗暴地加机器有效得多。

顺带一提，还有一个更乐观的定律叫 Gustafson 定律——它说的是”如果问题规模随处理器数量一起增长（更多机器 → 处理更多数据），加速比可以接近线性”。这解释了为什么大数据系统（数据量随集群一起涨）能获得很好的扩展性。两个定律不矛盾，它们描述的是不同场景：Amdahl 是”固定问题求更快”，Gustafson 是”固定时间求更大”。

子主题四：分治在真实系统里的三种形态

分治不是一个抽象概念，它在真实系统里有几种非常具体的落地形态：

形态一：算法层分治（单机、纯计算） 归并排序、快速排序、二分查找、FFT、Strassen 矩阵乘法。特点：子问题完全独立，合并简单，加速比接近理论值。

形态二：数据分片（Sharding / Partitioning） 数据库分库分表、Redis Cluster 的槽位、Kafka 的分区。特点：数据被永久地切分存储，每个分片独立服务一部分请求。 这是”分治”在存储系统里的形态。

关键决策是分片键（shard key）怎么选：

按范围分片（range）：范围查询高效，但容易热点
按哈希分片（hash）：分布均匀，但范围查询要扫全部分片
一致性哈希：扩容时迁移量小

形态三：计算框架层的分治（MapReduce 及其后继） MapReduce 是分治思想的工业级封装：Map 阶段把任务并行分头处理，Shuffle 阶段按 key 重新分配，Reduce 阶段并行聚合。

它的天才之处在于：它把”分解、并行、容错、合并”这些脏活全部封装了，让开发者只写 map 和 reduce 两个函数。 这是”抽象掉分布式复杂性”的一次成功尝试。

但 MapReduce 也暴露了分治的经典问题：Shuffle 阶段（数据重新分区、跨节点传输）往往是整个作业最慢的部分——这就是”合并成本”的具体体现。后来的 Spark 用内存计算、流处理引擎用增量计算，本质上都是在优化这个”合并”环节。

子主题五：分治的边界——什么时候不该分

讲了这么多好处，必须说清楚什么时候不该分而治之：

不该分的情况一：问题规模根本不大。 引入分片的运维复杂度、跨分片事务的痛苦、调试的困难——如果数据量单机就能扛住，这些代价纯粹是自找麻烦。过早分片是分布式系统里最常见的过度设计。

不该分的情况二：子问题耦合太紧。 比如图算法（需要反复访问邻居节点）、迭代式算法（下一轮依赖上一轮的全局结果）。强行分治会导致大量的跨节点通信，比单机还慢。

不该分的情况三：需要强全局一致。 跨分片事务的代价（两阶段提交、锁等待、延迟）可能远超并行带来的收益。有时候”一个稍慢但简单正确的单机方案”，比”一个快但天天出一致性问题的分布式方案”好得多。

一条经验法则：先看能不能垂直扩展（换更强的机器、优化算法、加索引），实在扛不住了再水平分治。 因为垂直扩展的复杂度和运维成本，通常比水平扩展低一个数量级。

子主题六：算法层的四个样本——“合并成本”才是盈亏表

先抛一个反直觉的问题。

归并排序和快速排序都是分治，都是 O(n log n) 量级。但它们的”贵”根本不在同一个地方。

归并排序：切两半几乎不花钱（算个 mid 就行），真正花钱的是合并——那个线性扫描，还要一份额外数组。

快速排序：合并花 0 分钱（左半边都 ≤ pivot，右半边都 ≥ pivot，拼起来天然有序，什么都不用做），真正花钱的是分解——那趟 partition 扫描，而且分解质量还带着运气成分。

这不只是一个有趣的小差异。它揭示了分治的第一性原理：

分治的总成本 = 分解成本 + 子问题成本 + 合并成本。你在哪一端付钱，决定了这个算法长成什么样。

主定理：分治的盈亏计算器

别怕公式，这个公式是你判断”分治划不划算”唯一需要的工具：

T(n) = a · T(n/b) + f(n)

a：拆出几个子问题
b：每个子问题规模缩小多少倍
f(n)：分解 + 合并的成本（这两项通常合在一起算，因为它们都是”每一层要额外付出的线性工作”）

关键在于一个基准量：n^(log_b a)，可以理解成”递归树叶子层的数据总量”。

拿 f(n) 跟它比，只有三种结局：

比较	总复杂度	直觉
f(n) 明显更小	Θ(n^(log_b a))	成本被”叶子层的子问题”主导，合并几乎白送
f(n) 同阶	Θ(n^(log_b a) · log n)	每一层都平摊一份，乘个层数
f(n) 明显更大	Θ(f(n))	合并吞掉一切，你白拆了

看清楚第三行了吗？分治划不划算，从来不取决于”子问题有多好拆”，而取决于合并成本有没有盖过 n^(log_b a)。

类比狠一点：分治就像一个公司开分部。开分部的成本是”招聘和培训”（分解），分部赚钱是”子问题”，而每个季度把所有分部的报表汇总成集团报表，是”合并”。 很多公司不是死在开不出分部，是死在每季度那个汇总会——各分部口径不一、格式不同、还要人工对齐，最后汇总部门比所有业务部门加起来还大。

样本一：归并排序——合并便宜到了极致

a=2, b=2 → n^(log_2 2) = n；f(n) = Θ(n)（线性归并）→ 同阶 → Θ(n log n)。

它的合并步骤有多便宜？两个已排序序列，两个指针各指头部，比一下取小的，指针往后挪。该做的比较一次不多，一次不少。 这是理论下界级别的最优合并。

它的唯一代价是空间：不是原地算法，需要 Θ(n) 额外数组。所以在真实世界你会看到这些东西：

外部排序（数据放不下内存）：先分块排序落盘，再做多路归并——这就是把”合并”本身又做了一次分治，k 路归并配上败者树/堆，k 越大磁盘 IO 轮次越少。
TimSort（Python/Java 对象排序的底层）：不硬拆到 1，而是识别数据里天然存在的”已排序片段（run）“，然后按规则合并这些 run。它优化的不是分解，是合并的次数和方式。

你注意到没有？归并排序的工程演进史，全是在跟”合并”较劲。因为分解那一端已经没什么可优化的了。

样本二：快速排序——把成本从合并端挪到了分解端

T(n) = T(k) + T(n-k-1) + Θ(n)，其中 k 是 pivot 左边的元素个数。

注意这里 a 不是固定的 2，它是随 pivot 质量浮动的。所以快排的死穴不是合并（合并是 0），而是：

拆得不均匀，递归树就变成一条链。

pivot 每次都取到最小元素 → k=0 → T(n) = T(n-1) + Θ(n) → Θ(n²)。你从”天下最快的排序”掉到”和冒泡排序一个德性”，只差一个坏 pivot。

于是整个快排的工程史，就是一部”怎么保证拆得均匀”的历史：随机化 pivot、三数取中、ninther（九数取中）、以及最后的兜底——introsort：一旦递归深度超过阈值，直接切换成堆排序，保证最坏情况回到 O(n log n)。

一句狠的总结：

快排把成本从合并端挪到了分解端。于是它的命运也从”我合并得起吗”变成了”我敢不敢赌这个 pivot”。

这说明什么？分解成本和合并成本是可以互相转换的。 归并排序是”分解免费、合并付费”，快排是”分解付费、合并免费”。你不可能两头都免费——除非问题本身有你说的那种结构（比如二分查找：查一次就能扔掉一半，合并根本不存在，因为它只有一个答案要返回）。

样本三：最近点对——靠一个证明，把合并从 Θ(n²) 救到 Θ(n)

二维平面 n 个点，找距离最近的一对。暴力是 O(n²)。分治怎么写？

按 x 坐标切两半，各自递归求最近距离，取 δ = min(δ_left, δ_right)。然后合并：需要考虑”一个点在左、一个点在右”的跨中线情况。

最朴素的合并：拿左边每个点去跟右边每个点比 → Θ(n²)。

如果是这样，主定理给出 T(n) = 2T(n/2) + Θ(n²) = Θ(n²) ——分治白干了，和暴力一样快。 你拆了半天，全搭在合并上。

救它的是一个观察，也是这个算法真正的灵魂：

跨中线的候选点对，两边距离都必须 < δ，否则不可能比已知的 δ 更优。所以只需要看中线左右各 δ 宽的那条竖条。
在竖条里，按 y 坐标排序后，每个点只需要和紧随其后的常数个点比较（平面情形下这个常数是 7）。为什么是常数？因为竖条里任意两个距离 < δ 的点，它们的 y 坐标差必须 < δ；而在一个 δ × 2δ 的矩形里，两两距离都 ≥ δ 的点最多只能塞下常数个（鸽巢原理：把矩形切成小格子，每格至多一个点）。

于是合并变成 Θ(n)（前提是你让每层的点集按 y 有序，这可以在递归返回时用归并的方式顺带维护）。

T(n) = 2T(n/2) + Θ(n) = Θ(n log n)。从 Θ(n²) 到 Θ(n log n)，全部来自于”证明合并时根本不需要看全部组合”。

这个教训值千金：

分治能不能成立，往往取决于你能否为合并阶段找到一个强剪枝条件。证明一个”不用看”，比多拆几层有用得多。

样本四：Strassen 矩阵乘法——省了贵运算，付了便宜运算

两个 n×n 矩阵相乘，朴素算法是 8 次 n/2 阶子矩阵乘法：T(n) = 8T(n/2) + Θ(n²) = Θ(n³)。

Strassen 的骚操作：用 7 次乘法 + 18 次加减，凑出同样结果。

a=7, b=2 → n^(log_2 7) ≈ n^2.807；f(n) = Θ(n²)（18 次 n/2 阶矩阵加减）→ f 比叶子层小 → Θ(n^2.807)。

数学上赢了。但工程上呢？为什么你日常用的 BLAS 库不默认开 Strassen？

三个真实代价：

常数大。 18 次加减 + 递归带来的额外内存分配和拷贝。指数从 3 降到 2.807，听起来很美，但只有当 n 足够大时，“指数优势”才能压过”常数劣势”。
有交叉点（crossover）。 所有实际实现都会在子矩阵小到某个尺寸时回退到朴素算法——因为小规模下常数主导。具体阈值是各库的实现细节，随 CPU 缓存层次和 SIMD 宽度变化，这里不编数字；你要记住的是这个模式：分治在小规模上几乎总是亏的，必须有”递归终止阈值”。
数值稳定性略差。 加减次数变多，浮点误差累积的方式不同，对病态矩阵更敏感。这也是为什么有些场景下它”数学正确但工程不可接受”。

最关键的一句话：

Strassen 省的是 1/8 的乘法（贵运算），付的是加法从 4 次涨到 18 次（便宜运算）。你赌的是”n 足够大时，指数的胜利终将压倒常数的失败”。

所有”复杂度更优但工程上不一定更快”的算法，本质上都是这一笔交易。

小结：合并成本决定三件事

算法	分解成本	合并成本	a / b	总复杂度	死穴
归并排序	Θ(1)	Θ(n)（线性归并）	2 / 2	Θ(n log n)	额外空间
快速排序	Θ(n)（partition）	0	2（浮动）/ —	平均 Θ(n log n)	拆不均
最近点对	Θ(n)	Θ(n)（靠剪枝）	2 / 2	Θ(n log n)	剪枝条件若丢了就退回 Θ(n²)
Strassen	Θ(n²) 加减	Θ(n²) 加减	7 / 2	Θ(n^2.807)	常数 + 数值稳定性

收敛成一句话：

合并成本决定了：总复杂度落在主定理的哪一档、算法要不要为”拆不均”兜底、以及工程上到底值不值得这么干。

现在问题来了——把这个结论搬到分布式系统：“合并”变成了什么？变成了跨机器搬数据。而搬数据，比比较指针贵多少个数量级？

下一节回答。

子主题七：MapReduce 的三阶段——Shuffle 为什么是最慢的一环

2004 年 Google 发表 MapReduce 论文，把”分布式分治”封装成了两个函数。这件事的意义不在技术多新，而在于：

它让一个普通工程师，不需要懂网络、容错、调度，就能写出跑在几千台机器上的程序。

但封装的代价是：大部分人只写 map 和 reduce，从来没想过中间发生了什么。于是当作业变慢时，他们只会加机器。

我们把中间那层扒开。

三阶段到底在干什么

Map 阶段（分解 + 解决）

输入被切成 split，每个 split 喂给一个 map task
map 输出一堆 (key, value) —— 注意，map 不聚合，它只是”贴标签”
输出先写本地磁盘，不是直接发网络。这一点极重要，后面会讲为什么

Shuffle 阶段（重新分区 + 排序 + 跨节点传输） 这是被名字掩盖的最复杂的一段，实际包含：

Partition：partition = hash(key) mod R，决定这条记录该去哪个 reducer
Spill：map 端缓冲区满了就按分区排序后溢写到磁盘，产生多个小文件
Merge：map 结束前把多个 spill 文件归并成一个按分区有序的大文件
Fetch：每个 reducer 去所有 map 节点上，把自己那个分区的数据拉过来（这就是”全连接”流量）
Sort / Merge：reducer 端把从各处拉来的数据再归并排序，得到按 key 有序的输入

Reduce 阶段（合并）

对同一个 key 的所有 value 做聚合，输出结果

Shuffle 为什么最慢：三个放大镜

放大镜一：它是”全量重分布”，不是”部分搬运”。

这句话是整个 MapReduce 性能的命门。假设 M 个 map、R 个 reduce，理论上每条数据都可能需要去任何一台 reducer。所以网络流量是 M × R 条连接，而不是 R 条。

类比：你们公司 1000 人，要按”姓氏首字母”重新分成 26 组开会。Map 阶段是每个人在自己工位上写好自己的材料（很快，并行）。Shuffle 阶段是所有人同时起身，跨越大楼去找自己的新组，而且电梯是共享的。Reduce 阶段是 26 个小组各自讨论（又快了）。

你说这三个阶段哪个最慢？是那个不动脑子的物理移动。

放大镜二：磁盘 IO 被重复付了好几遍。

一条记录在 shuffle 路上大概经历：map 输出 → 内存缓冲 → spill 落盘（可能多次）→ 合并成文件 → 网络发送 → reducer 端落盘 → 归并读取。

每一次落盘都是同一份数据被完整地写一遍又读一遍。 这就是为什么”不要造太多中间数据”在 MapReduce 里是铁律——你多写一条中间记录，代价不是一条，是好几条 × 好几次 IO × 网络。

放大镜三：排序。

Shuffle 要排序，因为 reduce 的语义是”同一个 key 的所有 value 聚在一起”。排序是 O(n log n) 的，而且是在磁盘上做的（外部排序）。

有人会问：能不能不排序？ 能，但你要放弃”按 key 有序”这个语义。后来的系统确实提供了 hash-based 的聚合（不排序，用哈希表分组），这就是在”要不要付排序的钱”上做选择。没有免费的午餐，只有你愿不愿意放弃某个语义。

Spark 的思路：不是消灭 Shuffle，是少付几次

Spark 常被宣传成”内存计算，比 MapReduce 快”。这个说法太糙了。准确的说法是：

Spark 用三件事降低了”合并成本”，但 Shuffle 本身还在。

第一件：把中间结果留在内存，砍掉重复的磁盘往返。

Spark 的核心抽象是 RDD（弹性分布式数据集），它有血缘（lineage）：记录了”我这个数据集是怎么从上一级算出来的”。

这个设计带来一个和 MapReduce 本质不同的容错方式：

MapReduce 的容错靠复制：中间结果落盘，task 挂了从磁盘重跑
Spark 的容错靠重算：数据放内存，丢了就按 lineage 从源头重新算一遍

这是一笔交易：MapReduce 把 IO 成本付在”正常路径”上（每次都落盘），Spark 把它挪到了”异常路径”上（只有挂了才重算）。大部分时候不挂，所以大部分时候更快。

第二件：DAG 调度 + 区分窄依赖/宽依赖。

Spark 把计算画成一张有向无环图，并且区分两种依赖：

窄依赖（narrow）：父分区只被子分区中的一个用到 → 不需要 shuffle，可以 pipeline 在一起（map → filter → map 一路流式算下去）
宽依赖（wide）：父分区要被多个子分区用到 → 必须 shuffle

于是优化目标就很清楚了：尽量减少宽依赖的数量，把能合并的窄依赖折叠成一个 stage。

给你一个具体的判据，这是 Spark 面试和实战里最有价值的一条：

reduceByKey vs groupByKey：两者语义常常等价，但 reduceByKey 会先在 map 端做一次局部聚合再 shuffle，groupByKey 会把所有原始记录原封不动搬过去。同样结果，数据量可能差几个数量级。

第三件：能不 shuffle 就别 shuffle。

Broadcast join：一张小表直接广播到所有节点，大表原地不动 → 完全没有 shuffle
倾斜处理（AQE skew join）：运行时检测到某个 key 特别大，就把它单独拆开处理，而不是让一个 reducer 硬扛

（具体算子名和参数在不同版本里会变，思路是不变的：把”必须全量重分布”的场景，尽量改造成”局部 + 广播”或”局部 + 拆分”。）

但必须诚实：

Spark 没有消灭 Shuffle。它减少的是 shuffle 的次数、单次的数据量、以及落盘的次数。宽依赖依然是宽依赖，跨节点重分布依然是那个最贵的操作。

这也解释了为什么 Spark 作业调优的第一步永远是”看 DAG，数宽依赖”。你的作业长什么样，由那几个宽依赖决定。

子主题八：数据分片——分片键怎么选，热点怎么治

算法层的分治是”临时拆一下”，存储层的分片是永久拆开，还得长期服务。难度完全不是一个量级。

因为一旦永久拆开，你就要面对那个灵魂拷问：

同一份数据，可以被访问的维度有很多个。但你只能按其中一个维度切。切错了，90% 的查询都会变成跨分片。

分片键选择的三个维度

选分片键不是”挑个字段”，是三个维度同时权衡：

维度一：查询模式（最重要，也最常被忽略）

先问：我最高频的查询，WHERE 条件里一定带着哪个字段？

订单系统，最常见的查询是”我的订单列表” → 按 user_id 分，这个查询落单分片
但如果还有高频的”运营后台按订单号查任意一笔” → 按 user_id 分，这个查询就得扫全部分片（scatter-gather）

这里的关键洞察是：

分片键决定了哪些查询是”本地查询”，哪些是”全局查询”。你选了一个分片键，就等于宣布”除了这个维度之外的所有查询，我接受它们变慢”。

所以选之前，把所有高频查询列出来，看它们的 WHERE 子句的交集。那个交集字段，就是候选分片键。

维度二：数据分布（决定会不会倾斜）

字段选对了，但数据分布不均，照样完蛋。三个要检查的东西：

基数（cardinality）够不够高：按 gender 分？只有两个值，你最多分 2 片。按 country 分？中国美国的数据量是冰岛的几千倍。
分布是不是均匀：按 user_id 哈希通常很均匀，但如果你的业务有超级大客户（一个企业租户占了 30% 的数据量），那就不是均匀分布。
有没有”天然热点”：按时间分？今天的数据永远是热的，三个月前的数据没人碰。 这就是典型的按时间分片导致的热点——所有写入打在最后一个分片上。

维度三：扩容需求（决定未来能不能长）

多久要加机器？
加机器时要不要停服？
迁移数据要多久？

这三个问题的答案，直接决定你要取模哈希还是一致性哈希（下一节的主题）。

三个维度会打架。 一个满足查询模式的键，可能分布不均；一个分布均匀的键，可能让高频查询变跨片。这时候的常规解法不是”选一个更好的键”，而是加一层：

冗余双写：同一份数据按两种键各存一份（一份按 user_id 服务 C 端查询，一份按 order_id 服务运营查询）。代价是存储翻倍 + 一致性延迟。
全局二级索引：分片键是 user_id，但对 order_id 建一个独立的索引表，索引表自己也可以分片。查询变成”先查索引拿到分片位置，再去目标分片点查”。代价是写入要维护索引，且索引查询多一跳。
维度表广播：小表（比如商品分类、地区字典）干脆每个分片都存一份全量，join 时本地完成。这就是分布式版的”用空间换网络”。

热点（数据倾斜）的识别

倾斜最阴险的地方在于：平均值完全正常。

100 个分片，平均 QPS 1000，看起来很健康。但实际是 97 个分片 QPS 300，3 个分片 QPS 25000。平均数是 1000，而那 3 台已经烧起来了。

所以识别倾斜，只看分布，不看均值：

看 p99 / p999 与均值的比值：如果 p99 是均值的 5 倍以上，基本可以断定有倾斜
看分片的资源水位方差：CPU、连接数、磁盘 IO、慢查询数，按分片画出来
看 hot key 排行榜：在代理层/客户端埋点统计 key 访问频次，定期输出 Top N
看长尾延迟：整体 p50 很好但 p99 很差，几乎是倾斜的指纹

一个很实用的反问：你的监控大盘上，显示的是所有分片的汇总曲线，还是每一条分片单独的曲线？如果是前者，你根本看不见倾斜。

倾斜的四种应对

应对一：加盐（Salting）——把热 key 拆成 N 份

给 key 加一个随机后缀：hot_key → hot_key_0 … hot_key_7。写入时随机选一个后缀，这样写压力被打散到 8 个分片。

代价很实在：

点查变散射：读 hot_key 时要查 8 个分片再合并结果（而且在不知道后缀的情况下你不知道数据在哪一片）
聚合逻辑要改：需要两段聚合——先按 hot_key_N 局部聚合，再按去掉后缀的 hot_key 全局聚合

所以加盐不是万能药，它是”用读复杂度和查询延迟，换写吞吐”。 它最适合的场景：写多读少、或者热 key 是少数可枚举的（比如那几个超级大客户）。

应对二：复合键——换一个分布维度

如果热点来自”按 A 分导致个别 A 值特别大”，那就把分片键换成 (A, B)，用第二个字段把大 A 值内部再打散。

好处：分布更均匀；坏处：只带 A 不带 B 的查询，从单分片变成了多分片。这又回到了”你只能按一个维度切”的根本矛盾。

选择加盐还是复合键，判据是：你的读查询里，能不能稳定地带上那个额外的维度？ 能带 → 复合键（干净）；不能带 → 加盐 + 散射读（脏但有效）。

应对三：动态分片——让系统在运行时自己切开热点

不预先固定分片数，而是让系统监控每个分片，超过阈值就自动分裂（split）成两半，并把其中一半迁移到别的节点。Bigtable/HBase 这类系统的 region 自动分裂就是这个思路。

它的好处是不需要你提前预测哪里会热。代价是：

迁移本身要占用网络和 IO（在业务高峰期迁移，等于火上浇油）
路由元数据要跟着更新，并且必须保证所有客户端一致地看到新路由（否则请求会打到旧位置）
分裂后如果键分布本身是单点突刺（一个 key 极端热），再怎么分裂也没用——因为那个 key 整体就在一片里。这时候必须回到加盐。

应对四：热 key 旁路——承认它是特例，特殊处理

有些热点是”物理上不可分”的：比如一个全局计数器、一个大促商品的库存、一条爆款微博的点赞数。这类东西，再怎么分片都是一片。

工程上的手段是：

本地缓存 + 短 TTL：读多写少的 hot key，在每个应用节点缓存，容忍秒级不一致
写合并/批量刷：把 N 次 +1 合并成一次 +N
读副本：给这个分片挂更多只读副本，分担读压力
拆计数器：把一个计数器拆成 N 个子计数器（本质还是加盐），读时求和

看到共性了吗？四种手段，本质上都是”要么把热点分掉，要么把热点绕开”。分不掉就只能绕，而绕的代价一定是一致性或延迟。

子主题九：一致性哈希——为什么取模扩容是灾难

先做一个思想实验，别急着看结论。

你有 4 台机器，用 hash(key) mod 4 决定数据放哪台。现在业务涨了，加一台变成 5 台。请问：有多少数据需要搬家？

直觉可能说”1/5 吧，新机器只占五分之一”。错了。

看几个 key（假设 hash 值就是这些数字）：

key 的 hash	mod 4	mod 5	位置变了吗
6	2	1	变了
7	3	2	变了
8	0	3	变了
9	1	4	变了
12	0	2	变了
20	0	0	没变

只有 hash 值同时是 4 和 5 的倍数（即 20 的倍数）时，位置才不变。

精确的结论是：从 N 台扩到 N+1 台，大约只有 1/(N+1) 的数据留在原地，约 N/(N+1) 的数据要重新分布。 从 4 扩到 5，80% 的数据要搬；从 99 扩到 100，99% 的数据要搬。

这几乎是灾难级的。 因为：

数据搬移是跨网络的，不是内存里挪指针。99% 的数据搬一遍，可能要跑几个小时甚至几天
搬移期间系统处于不一致状态，客户端路由可能指向旧位置
缓存全失效：99% 的 key 换位置，等于缓存整体冷启动，下游数据库瞬间被打穿（这就是经典的”缓存雪崩”的一个成因）

所以普通哈希取模的分片方案，本质上是”不可扩容”的。 它只适合分片数一开始就定死、且永远不会变的场景。

一致性哈希：把迁移量从 ~100% 降到 1/N

一致性哈希的做法非常优雅：

有一个固定的哈希环（比如 [0, 2^32)）
把节点也哈希到这个环上：node_position = hash(node_ip)
把 key 哈希到环上，然后顺时针找到第一个节点，就是它的归属

现在加一个新节点会发生什么？

新节点落在环上某个位置，它只”抢走”它在环上前驱节点（逆时针方向的邻居）到它自己那一段弧上的 key。其他弧完全不受影响。

节点均匀分布时，那段弧的长度约为环的 1/(N+1)。所以：

迁移比例从 N/(N+1)（接近 100%）降到了 1/(N+1)（约 1/N）。

再强调一遍，别理解错：一致性哈希不是”零迁移”，是”迁移量与节点数成反比”。 加机器就要搬数据，这是物理规律，躲不掉；一致性哈希做到的是让必须搬的量最小，而且是 O(1/N) 级别的最小。

减节点同理：节点挂了，只有它那一段弧的数据需要转移到它的顺时针后继节点上，其他节点无感。这个性质在”失败成为常态”的分布式环境里极其宝贵。

类比：环形跑道上的服务员。

想象一个圆形餐厅，服务员站在环上不同位置。顾客进来后顺时针走到最近的服务员那里点单。现在新来一个服务员站在环上某处——只有他和他逆时针方向那位服务员之间的顾客会改跟他，其他所有顾客的服务员不变。 而如果是”取模”式的排班（比如按顾客编号除以服务员人数分配），每加一个人，几乎所有顾客的分配全变。

光有环还不够：负载不均问题

一致性哈希解决了迁移量，但引入了一个新问题：节点在环上的位置是随机的，弧长不均匀。

随机撒 N 个点到一个环上，最短弧和最长弧可能差很多倍。理论上负载的不均衡度是 Θ(log N) 量级——节点数越多，最忙和最闲的差距越大（虽然增长很慢）。

后果：可能一台机器扛了别人两三倍的数据量和流量。 而你在开篇就知道了：整体性能由最慢的那台决定。

雪上加霜的是节点异构：你的集群里可能有一批老机器和一批新机器，新机器容量是老机器的两倍，但它们各自只占一段弧——容量差异完全没被利用。

虚拟节点：用”一实多虚”抹平不均

解法简单到有点粗暴：

一个物理节点，在环上占很多个位置（虚拟节点）。

比如一个物理节点对应 200 个虚拟节点（命名成 nodeA#1, nodeA#2, … nodeA#200，各自独立哈希）。环上有 N 个物理节点 × 200 个虚拟节点 = 200N 个点，每个物理节点拿到的是 200 段小弧的总和。

根据大数定律，这 200 段小弧的总长度会非常接近 200/(200N) = 1/N。虚拟节点数 k 越大，负载的标准差大约按 1/√k 的速度收敛。

虚拟节点还顺手解决了三件事：

异构容量：给大机器分配更多虚拟节点（比如 300 个），小机器少一点（100 个），天然实现加权负载均衡
扩容更平滑：新节点加入时，它的虚拟节点分散在环上各处，会从很多个老节点那里各取一小撮数据，而不是从某一个节点那里抢一大块——迁移的”冲击力”被摊薄了
宕机更平滑：一个节点挂了，它的流量被分散给多个其他节点，而不是全部压到唯一后继

代价？环上节点数变多，查找和元数据维护的成本上升（路由表从 N 项变成 N×k 项）。实际系统里通常用有序数据结构（如跳表、TreeMap）做环上查找，并用缓存降低开销。这就是典型的”用一点元数据成本，换负载均衡和迁移平滑”。

一个更实用的变体：固定槽位（预分片）

还有另一种思路，值得一提，因为它被 Redis Cluster 采用：

不把节点哈希到环上，而是固定划分 16384 个槽（slot）。

slot = hash(key) mod 16384（这个映射永远不变）
槽到节点的映射是可配置的元数据：slot 0-5460 → nodeA, slot 5461-10922 → nodeB, …

妙处在于两层解耦：

key 的归属由固定的槽决定，不随节点数变化
扩容时只需要改槽的归属，把部分槽标记为”迁移中”，逐槽搬数据，改元数据

这同样实现了”只迁移 1/N”，而且实现比哈希环简单得多（不需要虚拟节点，槽数够多天然均匀），迁移粒度也更可控（按槽为单位搬）。

所以真实系统里你常常看到的不是”纯一致性哈希”，而是”一致性哈希的思想 + 预分片的工程简化”。

概念上抓住核心就够了：把”数据 → 位置”的直接映射，拆成”数据 → 固定逻辑单元 → 节点”的两级映射。中间那一层固定的逻辑单元，就是扩容时不用动的那部分。

子主题十：分治的”合并”难题专题——让合并也能并行

回到子主题二那个”麻烦四”：你并行了计算，却串行了合并。

这是分治最顽固的瓶颈。因为计算可以无限拆——理论上你有多少机器就能拆多少份；但合并天然是把 N 份结果收敛成 1 份，它是一个收敛过程，看起来就是收敛到一个点。

那么问题来了：收敛到”一个点”这件事，是不是物理上必然串行的？

答案是：不是。收敛到”一个点”是必然的，但”一个点”上的工作量可以被压缩到极小。

有三种武器。

武器一：局部聚合（Combiner）——在数据搬家之前先瘦身

这是最有效、也最便宜的一招。

回到 word count：1000 个 map 任务，每个处理一段文本，输出 ("the", 1) 这样的对。如果直接 shuffle，"the" 这个词的每一条出现记录都要跨网络传输一次。一篇 100 万词的文档，光 “the” 就要传几万条。

Combiner 做的极其简单：在 map 端，先把本地的 ("the", 1) × 5000 合并成 ("the", 5000)，再发出去。

数据量从”词的出现次数”变成了”词的种类数”。这是从 O(语料大小) 到 O(词汇表大小) 的压缩。 对自然语言这种 Zipf 分布的语料，压缩比常常是几百上千倍。

Combiner 为什么能work？因为它依赖的是运算的结合律：

(1+1)+1 = 1+(1+1)

只要你的聚合操作满足结合律，那么”先局部聚合再全局聚合”和”直接全局聚合”结果完全一样，无论怎么分组都不影响最终结果。

这就是全部秘密：Combiner 不是什么高级优化，它是结合律的工程兑现。

但有几个必须记住的坑（这些坑都是真实踩出来的）：

不能依赖 Combiner 一定被执行。 在 MapReduce 里，Combiner 是一个”优化提示”，框架不保证调用次数，也不保证调用。所以——如果你的正确性依赖 Combiner 执行，你的程序就是错的。 Combiner 必须是”执行了更快，不执行也对”。
必须无副作用。 因为可能被调用 0 次、1 次或多次。
交换律的微妙位置。 严格说，MapReduce 的 reduce 输入是按 key 排序的，所以顺序是确定的，只靠结合律也够。但 Spark 的 reduceByKey 不保证分组内元素的顺序（它基于哈希），所以必须要求交换律 + 结合律。这就是为什么 Spark 文档会强调聚合函数要满足交换律——这不是学究气，是并行执行顺序不确定的必然要求。

顺带给出那个最有价值的工程判据：

写聚合逻辑时，先问一句：“我的 combine 函数满足结合律吗？” 如果满足，就一定要用 map 端聚合版本的算子（reduceByKey / aggregateByKey），不要用 groupByKey。这一条改动，往往比加机器有效一个数量级。

武器二：树形聚合——让合并的深度从 N 变成 log N

Combiner 解决的是”数据量”，树形聚合解决的是”单点压力”。

问题场景：1000 个节点各自算出一个部分和，现在要汇总成一个总数。

朴素做法（漏斗式）：1000 个节点全部发给一个汇总节点。

那个节点要处理 1000 次网络接收
它的网卡是 1000 个节点的汇聚点 → 单点瓶颈
而且它只有一个 CPU 在做加法

树形做法（分级式）：

第一阶段：1000 个节点分成 32 组，每组选一个”小组长”，组内 31 个节点发给小组长 → 每个小组长只收 31 份
第二阶段：32 个小组长再发给一个”班长” → 班长只收 32 份
总深度：log₃₂(1000) ≈ 2 层

关键变化：任何一个单点，接收的连接数和带宽压力从 O(N) 降到了 O(分支因子)。 而总工作量几乎没变，只是多了一次网络跳数（换来的是所有节点可以并行地做聚合，每一层都在并行）。

类比非常直白：

1000 个人交作业。漏斗式是：1000 个人排一个队，依次把本子递给班长，班长一本一本摞，收 1000 次。树形是：10 个小组长同时收，每人收 100 本打成一捆，班长只收 10 捆。

班长干的活少了 100 倍，而小组长是并行干的——总耗时由”收 100 本”决定，不是由”收 1000 本”决定。

这个模式到处都是：

Spark 的 treeReduce / treeAggregate：把 driver 端的聚合下推成树形，避免 driver 成为瓶颈
MPI 的 AllReduce：超算里几千张 GPU 同步梯度，用的是树形或环形（ring）算法
分布式深度学习的梯度聚合：参数服务器或 ring-allreduce，本质都是”别让一个点收 N 份”
多级汇总表：数据仓库里的”分区级预聚合 → 全局聚合”，也是这个思路

武器三：并行归并——让合并本身也分治

如果合并的对象是”有序序列”（归并排序、外部排序、全局排序），那合并本身也可以并行。

k 路归并：不是两两归并（深度 log₂(N)，串行轮次多），而是 k 个一组同时归并（深度 log_k(N)）。k 越大轮次越少，但每次归并需要维护 k 个游标（通常用堆/败者树）。

并行归并的真实形态：把两个长度 n 的有序序列合并，理论上可以做到 O(log n) 时间用 O(n / log n) 个处理器（用 rank 划分 + 二分查找定位），但常数巨大，实践中很少用。工程上更常见的做法是：不要合并，而是从一开始就把数据分得让合并变得便宜。

这句话值得加粗，因为它是一个更高阶的设计哲学：

最高级的合并优化，是让”合并”这件事根本不需要发生——通过预先的分区策略，让需要合并的东西一开始就在同一个地方。

MapReduce 的 TotalOrderPartitioner（全局有序输出）就是这么干的：先采样，估计数据的分布，据此划分区间边界，让每个 reducer 分到的 key 范围大致均等。 这样 reducer 内部各自排序，拼起来天然全局有序——跨 reducer 的合并变成”顺序拼接”，成本归零。

代价是什么？采样本身要跑一遍（或者用历史数据），而且分布漂移时分区会重新倾斜。 又是一笔交易。

三个武器小结

武器	降低的是什么	数学前提	代价
局部聚合（Combiner）	跨网络的数据量	结合律（+交换律）	需要重写聚合逻辑；执行次数不确定
树形聚合	单点的连接数与带宽	结合律	多一跳网络延迟
并行归并 / 预分区	合并的串行深度	有序性或可采样分布	采样成本；分布漂移

现在回头看 Amdahl 定律，是不是更清楚了？ 那个 (1-P) 的串行部分，在分治系统里具象化为：最后一次收敛、shuffle、协调、倾斜的那一台机器。 而这三件武器，全都是在削减 (1-P)。

子主题十一：业界四层对照——从二分查找到微服务

分治不是一个技巧，它是一个贯穿所有层次的思想。把不同层次摆在一起看，你会发现它们在解决同一个问题，只是”合并成本”的货币单位不同。

层一：算法层（单机、纯计算）

代表：二分查找、归并排序、FFT、Strassen

协调成本：0。 没有网络、没有失败、没有时钟
合并成本：内存里的指针操作，纳秒级
判据：主定理。 f(n) 和 n^(log_b a) 谁大
典型陷阱：递归终止阈值。 拆到太小，函数调用和 cache miss 的开销会盖过收益。所有高性能库都会在小规模时切换到非递归实现

二分查找是这一层的”理想形态”：分解 O(1)，子问题只有一个（另一半直接扔掉），合并 O(0)。 它是分治唯一一个”全赢”的案例，因为它根本不产生需要合并的结果。

层二：单机并行（共享内存的多核）

代表：Fork-Join 框架（Java ForkJoinPool / parallelStream）、Cilk、OpenMP

这一层引入了真正的调度问题，但因为共享内存，合并依然便宜。

Fork-Join 的两个核心机制，都值得单独说：

机制一：工作窃取（work-stealing）。

每个线程有自己的双端队列（deque）。线程从自己队列的头部取任务（LIFO，局部性好），空闲线程从别人的队列尾部偷任务（steal，减少竞争，而且偷到的是”最大的那块”，一次偷一把，减少窃取次数）。

为什么这个设计聪明？ 因为它把负载均衡做成了”闲的人主动找活”，而不需要一个中心调度器去分配——调度器本身就会成为 Amdahl 定律里的串行部分。 工作窃取是分布式的调度，没有单点。

机制二：递归阈值（sequential cutoff）。

Fork-Join 的递归不能拆到底。每个框架都有类似 if (size < THRESHOLD) { 直接顺序算; return; } 的逻辑。

为什么必须有？ 因为 fork 一个任务有真实成本（创建任务对象、入队、可能的线程唤醒、cache 失效）。当子问题小到几百个元素时，fork 的成本已经超过顺序计算的成本。

这就是 Amdahl 定律在微观尺度的体现：“串行部分”不只是算法里那段不能并行的代码，也包括所有”为了并行而付出的管理开销”。

这一层的实战坑（后端工程师一定会遇到）：

parallelStream 用的是全局共享的 ForkJoinPool.commonPool。 如果你在里面跑阻塞 IO，会把公共池的线程全占满，导致同一个 JVM 里其他无关的并行任务全部变慢。这是那种”线上诡异卡顿，查三天查不出来”的经典根因。
共享可变状态。 并行流里往一个普通 ArrayList 里 add，结果错乱。必须用 collect 的并发收集器——而这又回到了”合并”：并发收集器做的事正是”每个线程局部累积 + 树形合并”。
内存带宽墙。 核数上去了，但内存带宽没跟上。这时候”并行”根本不加速，因为瓶颈在搬运数据而不在计算。这和分布式系统里的网络瓶颈是一模一样的问题，只是换了个硬件层。
伪共享（false sharing）。 两个线程改两个不同的变量，但这俩变量恰好在同一个 cache line 里，导致 cache line 在两个核之间来回失效。这是”分片不彻底”在 CPU 缓存层面的翻版——你以为分开了，其实还在抢同一块资源。

层三：分布式计算（网络是主要成本）

代表：MapReduce、Spark、Flink

协调成本：高。 有调度器、有网络、有失败
合并成本：跨节点数据重分布，毫秒到秒级，比内存操作慢 5~6 个数量级
判据：宽依赖的数量 + shuffle 数据量（子主题七）
典型陷阱：以为加机器能解决一切，实际瓶颈在 shuffle 或倾斜

这一层和上一层的唯一本质区别，是”合并”这个动作的货币从纳秒变成了毫秒。于是所有在单机上”免费”的操作，到这里都要重新定价。

单机上”大家读同一块内存”是免费的；分布式里”大家读同一份数据”要广播。单机上”一个共享计数器”是免费的；分布式里它是不可分的热点。

层四：架构层（组织与服务的分治）

代表：微服务拆分、按领域拆分团队

这是分治最抽象、也最容易翻车的一层。因为它分的不是数据，是人和团队的边界。

先说它为什么是分治：微服务把一个大系统拆成若干独立服务，每个团队独立开发、独立部署、独立扩缩容。子问题是业务能力，合并是服务间的调用与集成。

它的收益来源和算法层一模一样：

独立部署 → 局部变更不需要全量回归（分解收益）
独立扩缩容 → 只有订单服务需要扩容时，不用把用户服务也扩一份（资源收益）
独立技术栈 → 搜索服务用 ES，交易服务用关系库（局部最优）

现在说陷阱：分布式单体（Distributed Monolith）。

什么叫分布式单体？你把系统拆成了 20 个服务，但它们必须一起部署、一起升级、一起挂。 你付出了分布式的一切代价，却没拿到分布式的任何收益。

四个典型症状，请对号入座：

改一个需求，要动 5 个服务，还要按顺序发布。 → 这是耦合，不是拆分
所有服务共享同一个数据库。 → 数据库 schema 一改，全部服务受影响。边界是假的。
同步调用链极深：A 调 B，B 调 C，C 调 D。任何一个抖动，全链路超时。可用性是乘法关系：10 个服务各 99.9%，端到端只有 99%。 而且没有熔断降级的话，一次抖动就是雪崩
按技术层拆，而不是按业务能力拆。 “controller 服务 / service 服务 / dao 服务”——这不是微服务，这是把单体部署成了三个进程。服务间调用量比原来单体内部函数调用量还大，还多了网络开销。

为什么会变成这样？ 因为大多数团队拆分的时候，用的是技术维度（这是前端、这是后端、这是数据库），而不是业务边界。

那正确的边界在哪？ 领域驱动设计（DDD）给的答案是限界上下文（Bounded Context）：同一个词在不同业务语境里含义不同的地方，就是边界。比如”商品”在交易上下文里关心价格和库存，在物流上下文里关心重量和体积，在推荐上下文里关心类目和标签——这三个”商品”不是同一个东西，它们应该分开建模、分开存储、分开演进。

四个可操作的健康检查（比任何架构文档都靠谱）：

独立部署：我能不能在不通知任何其他团队的情况下，独自发布这个服务？

独立扩缩：这个服务的流量翻十倍时，我能只扩它吗？

独立失败：这个服务挂了，其他服务是降级还是一起挂？

独立演进：我想换这个服务的数据库/语言/框架，需要别人同意吗？

四个里有任何一个答”不能”，你的拆分就还没完成。 你只是把一个单体切碎了，然后用网络胶水粘回去。

四层横向对照

层次	代表	分的什么	合并成本（货币）	主要陷阱
算法	二分、归并、Strassen	数据	内存指针（ns）	递归阈值、失衡
单机并行	Fork-Join、parallelStream	计算任务	内存/缓存一致性（ns~μs）	共享池污染、伪共享、带宽墙
分布式计算	MapReduce、Spark	数据 + 计算	网络 + 磁盘（ms~s）	Shuffle、数据倾斜
架构	微服务	业务能力 + 团队	服务调用 + 组织沟通（ms~天）	分布式单体、级联故障

看出那条规律了吗？

越往上走，合并成本越贵，于是”拆得对不对”就越重要，而”拆得细不细”就越不重要。

算法层你可以随便拆，因为合并几乎不要钱；架构层你必须慎之又慎，因为一次跨服务调用的成本，可能是函数内调用的百万倍。

子主题十二：实操视角——我的系统到底该不该分片

前面十一节全是”道”。这一节给”术”：一个可以照着做的检查清单。

先把丑话说前面：分片是一个不可逆性极强的决策。 算法写错了你可以改一版重新跑；分片键选错了，你要迁移全量数据、改所有查询、可能还要停服。所以下面这个清单的第一条，永远是”能不能不分”。

第一关：四个”能不能不分”

在考虑分片之前，先穷尽这些更便宜的方案。它们的成本通常比分片低一个数量级：

能不能加索引 / 改查询？ 一个慢查询可能就是缺个索引，或者写了个 SELECT * 再在应用层过滤
能不能加缓存？ 读多写少的场景，一层缓存可能扛掉 90% 的流量
能不能读写分离？ 读压力大 → 加只读副本，比分片简单得多（但要能容忍主从延迟）
能不能冷热分离 / 归档？ 如果你的数据里 80% 是三个月前没人碰的历史数据，把它们搬到归档库，主库立刻瘦下来。这可能是性价比最高的一招，却最常被忽略

只有这些都做完了还扛不住，才进入下一关。

第二关：六个信号，说明你真的该分了

不是”感觉慢了”就要分。要有可观测的证据。以下是六个相对客观的信号：

信号	观察方式	说明
数据量逼近单机上限	数据总量 / 单机可用磁盘、内存	特别关注内存与数据集的比例：如果索引已经放不进内存，随机 IO 会急剧恶化
写入打满	主库写入 QPS、磁盘 IOPS 水位持续高位	写入是最难用缓存/副本解决的压力，读写分离对它无效
单机 CPU 持续高位	CPU 使用率趋势（不是瞬时尖峰）	注意区分”CPU 在做有效计算”还是”在做锁等待/上下文切换”
连接数打满	活跃连接数 vs 最大连接数	这个信号常被忽略：连接数是单机硬约束，加应用机器反而更糟
备份/恢复/DDL 时间不可接受	一次全量备份、一次加字段要多久	这是最早出现的信号，却最少被当回事。如果你的全量备份要 8 小时，你已经活在危险里了——不是性能危险，是运维危险
垂直扩展撞墙	已经买不到更大的机型，或成本不成比例	顶级机型的价格常常是次一级的两三倍，但性能不到两倍

注意最后两个信号的分量：大多数团队是因为”慢”才想到分片，但实际上最先逼你分片的往往是运维——备份跑不完、DDL 锁表太久、故障恢复时间（RTO）超过容忍窗口。

一个实用判据：如果一次全量恢复的时间已经超过了你能接受的最长停机时间，你就必须分片了，无论性能是不是还好。 因为这时候你失去的不是性能，是出事之后能救回来的能力。

第三关：分片前必须准备的五件事

这一关比第二关更重要。 很多团队跳过了它，然后在分片上线那天出事故。

路由层：请求怎么找到分片？四种方案——客户端内嵌路由（简单但升级难）、代理层（Proxy，灵活但多一跳）、服务端路由（对应用透明）、配置中心 + 客户端缓存。无论哪种，路由规则必须是可配置、可动态下发的，否则未来改分片就是一场停服事故。
迁移工具与双写方案：从单库迁到分片，几乎必然要经历一个”双写 + 灰度读 + 校验 + 切流”的过程。你需要一个能点对账的工具（对比新旧两份数据是否一致），以及一个能随时回切的开关。
分布式 ID 生成器：自增主键在分片后不可用（会撞号）。需要雪花算法（Snowflake）类的方案，或者号段分配（segment）。这个要提前做，因为它会影响所有表结构。
跨分片查询的兜底：分页（跨片分页要在每个分片都取 N 条再归并，“深分页”代价极大）、全局排序、聚合、事务——先想好哪些查询会被牺牲，以及业务能不能接受。
监控的最小单位：分片上线后，你的监控必须能按分片下钻。汇总曲线会掩盖倾斜。每个分片独立的 QPS、延迟、连接数、磁盘、慢查询，一个都不能少。

第四关：一个诚实的反问

最后，问自己一句很难回答的话：

我们团队，有没有能力运维一个分布式系统？

不是”能不能写”，是”能不能运维”。具体地说：

半夜三点有个分片磁盘满了，谁起来处理？有 runbook 吗？
数据倾斜导致 p99 飙高，你有能力在半小时内定位和缓解吗？
要加分片了，迁移过程中出问题，能回滚吗？
跨分片的一致性出了问题（比如双写有一边失败），你有对账和修复工具吗？

如果这些问题的答案是”没有”，那么正确的选择不是”分片”，而是”先不分片 + 买更好的机器 + 做归档”，同时把运维能力建起来。

这不是保守，这是一笔很清楚的账：

分片用”运维复杂度”换”规模能力”。如果你的瓶颈是规模，这笔交易划算；如果你的瓶颈是运维能力，这笔交易会让你死得更快。

再给你一句收尾的判据，它可以印在墙上：

分片的正确时机，不是”系统扛不住了”的那一刻，而是”系统还没扛不住，但运维能力已经准备好了”的那一刻。

前者是被动救火，改架构改到一半业务在烧；后者是主动演进，从容且有退路。

子主题十三：分治的”形状”——深度与扇出，两笔你从没算过的账

先问一个几乎没人问的问题。

同样是把 1024 份子结果收敛成一份，你可以两两归并（扇出 2，深度 10），可以 32 个一组归并（扇出 32，深度 2），也可以一步到位全塞给一个节点（扇出 1024，深度 1）。三种方案的总工作量几乎一样。你选哪个？

大多数人从来没意识到这是一个选择题。他们只关心”我拆成了几份”，从来不关心”这些份是怎么被收拢的”。

但分治的形状，决定了延迟、可靠性、单点压力这三件事。我们把它算清楚。

先把递归树画出来

分治的每一层都能画成一棵树，它只有两个形状参数：

扇出（fan-out / arity） = a，每个节点拆成几个子问题
深度（depth） = log_b n，从根到叶子的层数

归并排序：a=2，b=2，深度 log₂n。每一层的总工作量都是 Θ(n)——因为每一层所有子问题加起来，还是要把 n 个元素摸一遍。于是：

总代价 = 单层代价 × 层数。 这就是递归树视角的全部价值。归并排序的 Θ(n log n) 就是这么来的：每层 n，共 log n 层。

现在把这张树搬到分布式系统里。你会发现，“层数”突然变成了三笔很贵的账。

第一笔账：深度 = 延迟的累加

在算法层，一层递归是一次函数调用，纳秒级。深度是 10 还是 2，你根本不在乎。

在分布式层，一层 = 一次网络往返 + 一次落盘 + 一次调度决策。合并树深度 d 意味着：

总延迟 ≥ d × (网络往返 + 落盘 + 调度开销)

1024 个节点：扇出 2 要 10 层，扇出 32 只要 2 层。如果瓶颈是延迟（交互式查询、流式处理），深度就是敌人——你要一棵”矮胖”的树。

第二笔账：深度 = 可靠性的指数

这一笔更阴险，而且几乎没人算。

假设每一跳（一次子任务执行 + 一次结果传递）成功的概率是 p。那么一条深度为 d 的路径全部走通的概率是 p^d。

p = 0.99，深度 2 → 约 0.98
p = 0.99，深度 10 → 约 0.90

而这还只是一条路径。你要的是所有任务都成功，不是一条路走通。深度越大，暴露在失败下的”任务-跳”总数越多。

所以：

在分布式世界里，“深”比”宽”危险。深度是可靠性的指数，扇出只是单点的线性压力。

第三笔账：扇出 = 单点的连接数与带宽

但扇出也不是白给的。扇出 k 意味着每个父节点要从 k 个子节点收数据：k 条连接，k 份带宽汇聚到一个点。

这就是 MapReduce 的真实约束：R 个 reducer 各自要从 M 个 map 拉数据，总连接数是 M × R。 当 M 和 R 都是几千时，这是几百万条连接。这不是”算力够不够”的问题，是交换机、TCP 连接表、以及 map 端同时服务太多拉取请求导致的磁盘随机 IO 问题。

所以 R 的选取是个真实的权衡：

R 太大 → 连接数爆炸、每个 reducer 分到的数据太少、小文件太多、启动开销占比上升
R 太小 → 并行度不够、单个 reducer 成为瓶颈、内存放不下、倾斜时没有回旋余地

MapReduce 论文对 M 和 R 的选取是有明确建议的：让它们显著大于 worker 机器数（文中给出的例子中 M 达到机器数的百倍量级、R 为数千）。这不是随便写的——它同时服务于负载均衡（小任务波浪式消耗）和扇出控制。

所以：矮胖还是高瘦？

瓶颈在哪	该选的形状	理由
延迟敏感（交互查询、流处理）	矮胖（大扇出、小深度）	深度 = 网络往返轮次
单点带宽 / 内存受限	高瘦（小扇出、大深度）	扇出 = 单点汇聚压力
可靠性差的环境（廉价机、Spot 实例）	矮胖	深度 = 可靠性的指数
连接数 / 路由元数据受限	高瘦	扇出 = 连接数与路由表规模

而真实系统几乎清一色选”矮胖”，而且胖到极端——MapReduce 干脆只有一层：Map → Reduce。 没有中间层。

为什么？因为一层有三个巨大的好处：

容错极简单：每个 map 的输出都落盘了。任何一个 reduce task 失败，只需重跑那一个 reduce，从磁盘重新拉数据。中间层没有任何需要维护的状态。
调度极简单：只有两波任务，没有多级依赖和中间结果的生命周期管理。
可靠性最优：深度 = 1，可靠性账的指数是 1。

那为什么超算里的 MPI AllReduce 敢用多层树/环？因为 HPC 的机器可靠得多、网络快得多、而且同构。 它付得起深度的代价，换取”每个点只跟常数个邻居通信”的带宽优势。

一句话总结这一节：

算法层分治，你只需要算”总工作量 = 单层代价 × 层数”。分布式层分治，你还要算三笔：延迟是深度的线性函数、可靠性是深度的指数函数、单点压力是扇出的线性函数。

MapReduce 所有看起来”笨”的设计（只有两层、中间全落盘），都是在为这三笔账买单。

子主题十四：完成时间 = max(子任务时间)——长尾、推测执行与幂等

这一节讲分治里最反直觉、也最容易被忽略的一条事实。

你把一个任务拆成 N 份并行跑。请问它什么时候算”完成”？

不是平均时间，不是中位数，而是——

max(所有子任务的完成时间)。

分治把”总工作量”除以了 N，却把”完成时间”变成了 N 个随机变量的最大值。

这件事的杀伤力，比大多数人想的大得多。

为什么 max 会随着 N 一起变坏

直觉非常简单：你从一个分布里取样，样本越多，取到的最大值越大。

单机跑一个任务：耗时是个随机变量，通常 1 秒，偶尔 GC 抖一下变成 3 秒。

拆成 1000 份：你要取 1000 个样本的最大值。那个 3 秒的抖动，现在几乎必然出现——而且你必须等它。

拆成 10000 份：你几乎必然撞上那个万分之一概率的 30 秒极端抖动。

分治度越高，你越是在跟”分布的尾巴”打交道。你优化的不再是平均情况，而是极端情况。

这正是 Jeff Dean 与 Luiz André Barroso 那篇著名的《The Tail at Scale》（CACM，2013）讲的核心问题：当一次用户请求需要 fan-out 到上百台机器时，即使单机长尾概率极低，端到端撞上长尾的概率也会被放大成常态。（文中有具体的概率推算，这里不复述数字，你只需记住那个机制：扇出把单机的长尾概率，放大成端到端的普遍问题——这和我们上一节说的”扇出账”是同一件事的两个侧面。）

注意，长尾和数据倾斜是两个不同的病：

倾斜 = 某些子任务天生活多（数据分布问题）
长尾 = 子任务活一样多，但跑得慢（执行环境问题）

倾斜你能提前看出来（看 key 分布）；长尾你看不出来，因为它来自硬件和运行时。所以两者的治法完全不同——用错药是最常见的无效优化。

长尾从哪里来

硬件：慢盘（坏道重试）、CPU 降频、内存 ECC 纠错、网卡丢包重传
共享与超卖：云上的邻居在抢你的 CPU/网络（noisy neighbor）；容器内存超限被 OOM kill
运行时：GC 停顿、JIT 编译、页缓存未命中、锁竞争
数据本身的隐藏倾斜：不是 key 倾斜，是记录大小倾斜——某个 key 只有 100 条，但每条 10MB，那 100 条比别人的 100 万条还慢
调度：task 排队、资源碎片、数据本地性没命中要跨机读
外部依赖：子任务里偷偷调了一个第三方 API，那个 API 抖了一下

看到第 6 条了吗？在并行任务里调用外部服务，等于把外部服务的长尾整个搬进你的关键路径，而且它还会被 N 倍放大。这是很多”Spark 作业偶发跑 10 倍时间、查遍资源指标都正常”的真实根因。

三件武器

武器一：把子任务切得更小、更多。

这听起来反直觉（切得越多，不是越多 max 样本吗？），但它有两个实打实的好处：

单个 straggler 的伤害变小：一个任务卡住，它只占总工作量的一小部分
负载均衡变成自适应的：调度器把任务”波浪式”地分给当前空闲的机器——快机器多干几轮，慢机器少干几轮。这本身就是一种无中心的负载均衡，和 Fork-Join 的工作窃取是同一个思想。

MapReduce 的建议正是”让 M 和 R 显著大于机器数”，道理就在这。

代价：task 启动有固定开销，切太碎调度成本盖过收益。又是”分治的最小粒度”问题——和算法层的递归终止阈值、和 Fork-Join 的 sequential cutoff 是同一个道理，只是货币换成了调度开销。

武器二：推测执行（speculative execution / backup task）。

原理极简单：发现某个 task 明显落后于同批，就在另一台机器上同时起一份一模一样的备份任务，谁先跑完用谁的。

这里有个必须知道的坑：

备份任务不能在 t=0 就发。 那等于把所有任务跑两遍，集群负载直接翻倍，反而制造更多长尾。正确做法是观察到明显落后之后才发（例如进度显著低于同批平均，且已运行一段时间）。

更精细的做法是 hedged request（对冲请求）：先发一次，若 T 毫秒内没回来，就再发一份给另一台，取先返回的。T 通常取该请求的 p95/p99 延迟。代价是流量放大约等于”超过 T 的请求比例”——用小比例额外请求，换掉整条长尾。

还有一条：如果长尾的根源是数据倾斜，推测执行无效。 备份任务要干的活一样多，一样慢，还白占一台机器。先分清”倾斜”还是”抖动”，再选武器。

武器三：隔离与淘汰。

若某台机器反复出现长尾（硬件亚健康、被 OOM 过、磁盘慢），最有效的手段不是重试，是把它从资源池里摘掉。成熟的调度系统都有”慢节点黑名单 / 节点健康度”机制。

类比：8 车道的路上有一条道上有辆抛锚车。你不是让所有车都去试一遍这条道（重试），而是直接封了这条道（隔离），让车流从剩下 7 条走。

重试的三个前提：幂等、有界、可观测

遇到长尾第一反应永远是重试。但重试是分治系统里最容易把小故障放大成大故障的操作。

前提一：幂等性（最重要）。

分治系统中，一个 task 失败时，你通常无法区分这三种情况：

它根本没开始
它跑了一半
它跑完了，但结果回传时网络断了

所以重试必然意味着”可能重复执行”。若操作不幂等，重试就是数据损坏。

这就是那条铁律：

at-least-once 投递 + 幂等消费 = 效果上的 exactly-once。

实现上就两条路：用唯一键去重（业务主键 / 请求 ID / (partition, offset)，下游加唯一约束或去重表），或把处理设计成幂等的状态机（用”设置成值 X”代替”加 1”）。

前提二：重试必须有界。

无上限重试 = 重试风暴。下游抖一下 → 上游全重试 → 流量放大 → 下游更抖 → 更多重试 → 雪崩。三个必须做的限制：

次数上限（通常 2~3 次）
指数退避 + jitter：不加 jitter 会导致所有客户端在同一刻集体重试（惊群），把抖动同步放大
熔断（circuit breaker）：下游持续失败时快速失败一段时间，别再送流量过去

前提三：重试必须可观测。

你要有能力回答：“当前系统里多少比例的流量是重试流量？“如果答案是 30%，你已经在正反馈崩溃的边缘，而你的大盘可能还显示”请求量平稳”。 所以：重试率必须是一级监控指标，与 QPS、延迟平级。

容错方式的选择：复制 vs 重算 vs 检查点

分治系统的容错，本质上只有三种：

方式	做法	付钱路径	适合
复制	中间结果落盘，挂了从磁盘重跑	正常路径（每次都付）	计算昂贵、重算更贵；MapReduce
重算（lineage）	不落盘，挂了按血缘从源头重算	异常路径（只有挂了才付）	计算便宜、血缘短；Spark RDD
检查点（checkpoint）	周期性持久化状态，挂了从最近快照恢复	分期付款（周期性付）	血缘长、重算会爆炸；流处理

Spark 选重算，因为大部分时候不出事。但有一个必须知道的陷阱：

血缘链越长，重算代价越大——而且它可能是扇出式爆炸的。 一个 RDD 依赖两个父 RDD，每个父又各依赖两个……挂一次就要重算整棵子树。所以 Spark 提供 persist 和 checkpoint，本质都是给”重算代价”设上限。

而流处理几乎强制要求 checkpoint：流是无限的，血缘链无限长，从源头重算物理上不可能。所以流的容错必然是”检查点 + 有限重放”，并且要求数据源本身可重放（Kafka 这类）。

看明白了吗：

容错方式不是技术偏好，是由”重算代价的形状”决定的。血缘短 → 重算；血缘长 → 检查点；计算贵得离谱 → 落盘复制。

子主题十五：有状态分片的专属难题——再均衡（Rebalance）

前面讲分片，大多默认”分片是静态的”。但真实系统里分片一直在动：加机器、减机器、宕机、热点分裂。

而”移动分片”这件事，在无状态系统和有状态系统里的难度，差好几个数量级。

无状态 vs 有状态

无状态分片（计算分片）：任务给谁都行，节点挂了换一台重跑。迁移成本 ≈ 0。MapReduce 的 map task、无状态 Web 服务都是这类。

有状态分片（存储 / 流式分片）：节点上存着数据或状态。要迁移，就得搬数据。而搬数据意味着四件麻烦事：

网络和磁盘 IO 占用（搬迁流量会挤压在线流量）
搬迁期间的一致性（边写边搬，怎么保证不丢不重）
路由切换的原子性（客户端什么时候开始往新位置发）
可回滚（搬一半发现问题，能退回去吗）

路由的”中间态”问题

这是有状态迁移里最精妙的一环，值得单独讲。

迁移不是瞬时的，但流量是连续的。 当你把 slot 1000 从 A 搬到 B 的过程中，客户端还在往 A 写。如果你搬完才切路由，中间这段写入就丢了。

Redis Cluster 的解法非常典型（这是真实机制，值得把这个模式记住）：

迁移中的槽：源节点标记 MIGRATING，目标节点标记 IMPORTING
客户端请求某个 key：
- 源节点上还有这个 key → 正常处理
- 源节点上已经没有这个 key（已搬走）→ 返回 ASK 重定向，客户端临时去目标节点要一次，但不更新本地路由表
客户端收到 MOVED（永久重定向）→ 这才更新本地路由缓存

看出精髓了吗？

ASK 是”临时问一次”，MOVED 是”永久改路由”。 区分这两种重定向，就让”迁移中”这个中间态能被精确表达——而不是让客户端猜。

这个思路是通用的：任何有状态迁移，都必须设计一个”过渡态协议”，让客户端能区分”还没搬 / 正在搬 / 已搬完”。缺了这一层的迁移方案，一定会在某个时刻丢数据。

消费者组的再均衡：分布式里的 stop-the-world

讲一个后端工程师一定会撞上的具体场景：Kafka 消费者组的 rebalance。

一个 topic 有 P 个分区，一个消费组有 C 个消费者，每个分区只能被组内一个消费者消费。成员数量一变（扩容、宕机、重启），就要重新分配分区归属。

经典的 eager（急切）rebalance 有个臭名昭著的性质：

再均衡期间，整个消费组停止消费。所有成员必须先撤销（revoke）自己持有的全部分区，重新加入组，协商出新方案，才能恢复消费。

后果极其具体：

你滚动重启一个 20 实例的消费组 → 每重启一个实例就触发一次全组停顿 → 20 次全组停顿，消费积压反复冲高
一次网络抖动导致心跳超时 → 成员被踢出 → 触发全组 rebalance

这就是”分治的协调成本”在实时系统里的具体形态：你为了重新分配工作，把所有工作都停了。

缓解手段（记住思路，不必记版本号）：

静态成员（static membership）：给每个消费者一个稳定的实例 ID。短暂重启（在会话超时内回来）不触发 rebalance，因为它的身份没变。这直接消灭了”滚动重启引发 rebalance”这个最高频的痛点。
协作式增量再均衡（cooperative rebalance）：不是”全撤再重分”，而是只交出需要移动的分区，其余分区继续消费。再均衡期间不停止消费。
调优心跳与会话超时：更容忍抖动，代价是故障发现变慢（又一笔交易：发现故障的速度 vs 误判的概率）

抽象出来，这是适用于所有有状态再均衡的原则：

缩小 rebalance 的爆炸半径：能不触发就不触发（稳定身份），触发了就只动必须动的部分（增量），实在要停就让它尽快结束（缩短协商）。

有状态流处理的扩缩容：最难的一档

如果说 Kafka rebalance 是中等难度，那有状态流处理（Flink 这类）的扩缩容是地狱难度。因为它不只是”分区归属”变了，而是算子内部的本地状态（窗口聚合中间结果、join 缓存、去重集合）也要一起重新分布。

大致流程：

触发一次 savepoint（全局一致的状态快照）
停止作业
按新并行度重启，重新分配状态
从 savepoint 恢复

关键在第一步：什么叫”全局一致”的快照？ 分布式里没有全局时钟，你没法让所有节点”同时”拍照。Flink 用的是 Chandy-Lamport 算法的异步屏障快照（asynchronous barrier snapshotting）变体：在数据流中注入 barrier，每个算子收到 barrier 时冻结并持久化自己的状态，barrier 流过整个拓扑后这一轮快照就完整了。

它的巧妙之处是：不需要暂停计算就能拿到全局一致快照。 代价是 barrier 对齐会带来延迟尖峰（背压严重时尤其明显）。

而”从 savepoint 恢复且改变并行度”意味着把原来 N 份状态重新切成 M 份——这要求状态本身可重新分区。这就是为什么 Flink 区分 keyed state（按 key 切好，可自由重分）和 operator state（重分规则受限）。

于是又回到那条贯穿全章的规律：

有状态系统的可迁移性，取决于”状态的切分维度”是否和”并行度的切分维度”一致。 keyed state 能自由扩缩容，是因为它的状态从一开始就是分片存储的。

这和”预分区让合并变便宜”是同一个思想：让数据的组织方式，从一开始就适配你未来要做的切分。

分片内强一致，跨分片最终一致

最后说一个有状态分片绕不开的架构妥协。

一个分片为了高可用，通常不只一份，而是一个分片 = 一个 Raft/Paxos 复制组（3 或 5 副本，容忍 1 或 2 台故障）。于是：

分片内：共识协议保证强一致（多数派提交、可选线性一致读）
跨分片：没有共识协议覆盖，只能靠 2PC / Saga / 最终一致

于是就有了分布式系统里最常见的那句架构声明：

分片内强一致，跨分片最终一致。

为什么不能全强一致？ 因为共识的代价是：多数派确认 + 落盘 + 至少一轮网络往返。跨分片事务若也走共识，你要付”两轮共识 + 跨片锁 + 协调者自身高可用”，延迟和复杂度都暴涨。

为什么这个妥协是合理的？ 因为——

分片键选得好，可以把”需要强一致的那些操作”全部约束在单个分片内。

这是分片键选择的第四个维度（子主题八给了三个，这是隐藏的第四个）：把事务边界与分片边界对齐。

举例：转账要强一致。要么按账户分并接受跨片 2PC；要么让频繁互转的账户落在同一片。现实中的常见做法是按用户分而非按账户分——因为同一用户的多个账户互转是最常见的事务；跨用户转账则接受异步与补偿。

收尾一句：

无状态分片迁移的是”任务”，几乎免费；有状态分片迁移的是”数据 + 路由 + 一致性”，你必须为中间态设计协议。而所有优雅的迁移方案（ASK/MOVED、静态成员、增量 rebalance、savepoint），核心都是同一件事：把”全量停止”改造成”局部过渡”。

子主题十六：测量你的分治——别再靠”感觉快了”

前面十五节讲了很多”应该这样设计”。但工程里最难的问题其实是：我怎么知道我的分治到底有没有效果？瓶颈在哪一段？

大部分团队的答案是”加了机器之后快了”。这不是测量，这是安慰剂。

这一节给四个能立刻用的测量方法。

方法一：先分清你在做哪个实验

加速比有两种，混用会得到完全相反的结论：

强扩展（strong scaling）：问题规模固定，加机器求更快 → Amdahl 的适用条件

S(N) = 1 / ( s + (1-s)/N )

（s = 串行比例，N = 处理器数；N→∞ 时趋向 1/s，就是本章前面说的 1/(1-P)）

弱扩展（weak scaling）：每台机器处理的数据量固定，加机器的同时加数据，求”相同时间内干更多活” → Gustafson 的适用条件

S(N) = N - (N-1) · s

注意 Gustafson 公式里 s 的定义，这是最容易搞错的地方：它测的是”在 N 个处理器上运行时串行部分占的时间比例”，不是”串行程序里的串行比例”。

推导只要一行：把 N 处理器上的总运行时间归一化为 1，其中串行 s、并行 (1-s)；这些并行工作若放在单核上要花 N×(1-s)；所以相对单核执行，加速比 = s + N(1-s) = N - (N-1)s。

所以当有人拿 Gustafson 说”我们能线性扩展”时，你要反问一句：你的问题是”固定大小求更快”，还是”固定时间求更大”？

离线跑批（每天固定处理昨天的全量日志）→ 规模固定，Amdahl 说了算
在线服务（用户涨了、QPS 涨了、数据也涨了）→ 规模随集群增长，Gustafson 更贴近

这也解释了为什么大数据系统天然容易”看起来扩展性很好”：它们的数据量确实随集群一起涨。 但同一个系统，如果突然要”把这个紧急的历史回溯任务在 10 分钟内跑完”，Amdahl 的天花板立刻压下来——因为问题规模被钉死了。

方法二：从两次实测反推你的串行比例 s

这个技巧极实用：不用读代码就能估算出你的 Amdahl 天花板。

由 Amdahl 公式反解：

s = ( 1/S - 1/N ) / ( 1 - 1/N )

用法：

用 N₁=4 个 worker 跑一遍，得加速比 S₁
用 N₂=16 个 worker 跑一遍，得 S₂
分别代入，看反推出的 s 是否一致
若 N=16 反推出的 s 明显大于 N=4 的，说明并行度提高时出现了新的串行瓶颈

第 4 条是这个方法最宝贵的地方：

如果 s 随 N 一起变大，说明你的”串行部分”不是一个常数，而是 N 的函数。这时 Amdahl 比它看起来更残酷——你的天花板在往下掉。

什么会让 s 随 N 增长？几乎就是本章讲过的所有东西：协调开销（N 越大协调越贵）、合并阶段的单点收敛、路由/元数据要同步给更多节点、连接数上升导致网络争用。

方法三：给倾斜定一个数字

子主题八讲了识别倾斜要看分布。这里再进一步：用一个数字跟踪它，这样才能告警、才能看趋势。

指标	算法	识别的是哪种病
max / avg	最大分片负载 ÷ 平均负载	单个突刺（易被极端样本带偏）
p99 / p50	分片级延迟或耗时的分位比	抗单点噪声，看整体长尾
基尼系数	按分片负载排序后算累积分布的不平等度（0 = 完全均匀，越接近 1 越不均）	整体分布不均，不只最大值

三个要分开看，因为它们诊断的是不同的病：

max/avg 高，基尼低 → 单点突刺（一个热 key）→ 用加盐
max/avg 一般，基尼高 → 整体不平（分片键基数不够、大小分片混部、容量异构）→ 换键或加权
两个都高 → 先治热点，因为单点收益最大

再加两个分治系统独有的指标：

straggler 比 = 最慢子任务耗时 ÷ 子任务耗时中位数。这个数字直接告诉你”你在为长尾付多少钱”。若它是 5，意味着八成的时间在等最后那几个。
重试率 = 重试请求数 ÷ 总请求数。前面说过，必须是一级指标。

方法四：警惕”超线性加速”的假象

有时你会测出 S > N（用 10 台快了 15 倍）。这叫超线性加速，它真的存在，但庆祝之前先怀疑三件事：

可能一（真实收益）：缓存与局部性效应。 数据被切成小块后，每块能完整放进 CPU cache / 内存；单机跑全量时放不下，频繁换入换出。这是真收益——分治改善了访存局部性。 外部排序的多路归并、数据库的分块扫描都吃这个红利。

可能二（假象）：基线不公平。 你拿”10 台并行”对比”1 台跑全量”，但那 1 台内存不够、一直在做磁盘交换。你测的不是加速比，是”内存够用 vs 不够用”。

如何排除：补一个”单机分批”的对照——单机上把数据切成 10 批顺序处理。若单机也快了很多，说明收益来自局部性而非并行。

可能三（假象）：IO 并发度变化。 10 台 = 10 块盘 = 10 倍的 IO 并发。你测的是 IO 并行，不是计算并行。

所以正确的测量协议是：

永远测三组：单机全量、单机分批、N 机并行。前两组的差 = 局部性收益；后两组的差 = 并行收益。只报第三组对比第一组，是耍流氓。

一个可复用的分治复盘模板

不管你在调优什么（Spark 作业、分片数据库、Fork-Join 任务），把这七个数字填出来，瓶颈基本现形：

扇出：拆成了几份
深度：合并要几轮网络 / 调度
并行段耗时 vs 合并段耗时（这就是 Amdahl 的 s）
straggler 比：max 子任务 ÷ 中位子任务
倾斜度：max/avg 与基尼系数
重试率
s 是否随 N 增长（用两个并行度各测一次）

填完后问一句：

这七个数字里最坏的是哪个？你的下一个优化动作，是不是针对它的？

如果不是，你多半在做无效优化——比如 straggler 比已经是 10 了，你却在加机器。

子主题十七：分治的对偶——复制（Replication）

这一节讲一个很少被人放在一起讲、但放在一起看会”顿悟”的对照。

计算机科学里有两件看起来完全相反的事：

分治（Partition / Sharding）：把一个东西拆成 N 份，每份存/算一部分
复制（Replication）：把一个东西抄成 N 份，每份都是完整的

一个在”分”，一个在”抄”。它们的目的、代价、以及带来的麻烦，恰好是对偶的。

目的的对偶

	分治（拆）	复制（抄）
主要目的	提升规模上限与吞吐	提升可用性与读吞吐
对写入	写入被分散 → 写吞吐提升	要写 N 份 → 写延迟上升 / 写成本放大
对读取	点查更快（数据少），范围读变慢（scatter-gather）	读可分摊到副本 → 读吞吐提升
对容量	容量 = 各分片之和（线性增长）	容量不变（每份都是全量）

那个漂亮的对称是：

分片用”跨片查询变难”换”容量与写吞吐”；复制用”写入放大与一致性”换”可用性与读吞吐”。

麻烦的对偶

两者都会带来一致性问题，但方向正好相反：

分治的一致性难题：一个逻辑对象只有一个副本，却被跨分片引用。

典型：跨分片事务、跨分片 join、跨分片唯一约束
本质：钱在 A 片，货在 B 片，你要原子地改两边

复制的一致性难题：一个逻辑对象有多个副本，它们可能不一样。

典型：主从延迟、脑裂、读到旧数据
本质：同一笔余额，三个副本记了三个数，哪个是真的

一个是”分”出来的问题，一个是”抄”出来的问题。

复制的两笔硬成本

成本一：写入放大。 3 副本 = 3 倍网络出流量 + 3 倍磁盘写入。所以”副本数”是要反复权衡的数字：3 副本容忍 1 台故障，5 副本容忍 2 台，但写入成本直接翻到 1.67 倍。

成本二：共识——这是”合并成本”最贵的形态。

要让多副本对外表现成”一个不会出错的单一对象”，你需要共识协议（Raft / Paxos / Zab）。代价是：多数派确认、额外网络往返、选主期间的不可用。

这里有一个极其深刻、值得反复咀嚼的观察：

共识协议做的事，是用 2f+1 台机器，去模拟 1 台”不会宕机的机器”。

复制的目的不是并行，而是消除单点；而它达成目的的方式，恰恰是让多台机器表现得就像一台——即在逻辑上，把 N 台”合并”回一台。

分治是把 1 台拆成 N 台以提升能力，复制是把 N 台合成 1 台以提升可靠。它们是同一个动作的正反两面。

而这个”合并回一台”的动作，是整个计算机科学里最贵的合并：

归并排序的合并：内存指针比较，纳秒
Shuffle 的合并：跨节点传输，毫秒
共识的合并：网络往返 + 落盘 + 多数派投票，且任何一台慢都会拖慢全体

共识之所以慢，和”完成时间 = max”是同一个道理：多数派确认要等最快的多数派集合，任何一个参与副本慢/网络抖，这次提交就慢。更狠的是：少数派故障不损害可用性，但”慢的副本”会实实在在拖高提交延迟。

组合形态：分片 × 复制

真实系统从不二选一，而是两个都做：

先按 key 分片（提升容量与写吞吐），再让每个分片拥有多个副本（提升可用性）。

Kafka：topic 分 P 个分区（分片），每分区 N 副本（1 leader + N-1 follower）
Redis Cluster：16384 槽分给主节点（分片），每个主节点可挂从节点（复制）
分布式数据库（TiDB / CockroachDB 这类）：数据切成 Region/Range（分片），每个 Region 是一个 Raft 组（复制）
GFS / HDFS：文件切 block（分片），每 block 存多份（复制）

为什么要两个都做？因为它们解决的是不同维度的问题：

分片解决”装不下 / 扛不住” —— 这是规模问题
复制解决”挂了怎么办” —— 这是可靠问题

只要你的系统既”装不下”又”会挂”，你就两个都要。（现实中所有生产系统都是这样。）

一个反直觉的推论：副本会拖累并行吗？

会，而且方式很隐蔽。

考虑 Spark 读 HDFS：一个 block 有 3 副本。理论上三处都可读，但调度器会优先选”数据本地性”最好的节点（同机 > 同机架 > 跨机架）。 于是：

副本提升了可用性与读吞吐，却可能让调度把任务集中到少数几个持有本地副本的节点上，反而制造新的倾斜。

这就是为什么生产里会看到两种相反的调优方向：优先本地性（省网络，但可能调度不均）vs 放弃本地性换均衡（多花网络，任务分布均匀）。

而在存算分离架构下（计算节点无状态，数据放对象存储），本地性这个概念直接消失了——所有读取都是远程的。这笔账是：

存算一体：读快（本地盘），但扩容要搬数据，计算和存储必须一起扩。 存算分离：读慢（走网络），但计算节点无状态 → 扩缩容秒级、不需要 rebalance、故障恢复快。

这其实是”有状态迁移难题”的终极解法之一：如果计算节点上什么都不存，迁移就不需要发生了。 你把”迁移状态的成本”，换成了”每次读都走网络的成本”。在数据持续膨胀、计算弹性要求高的场景，这笔交易越来越划算。

把它连回本章主线：

分治是”拆开以提升能力”，复制是”合并以提升可靠”。成熟系统会在不同层次交替使用这两个动作：数据分片（拆）→ 分片内多副本（合）→ 多副本用共识对外表现成一台（更深的合）→ 跨片查询用 scatter-gather（再拆）。

所以架构设计的真实动作，从来不是”分还是合”，而是”在哪一层分、在哪一层合”。

子主题十八：合并的四档定价——从拼接到共识

本章从头到尾都在讲”合并成本”。这一节把它定量化：合并不是一个动作，是四类动作，它们的价差可以达到好几个数量级。

你做分治设计时的核心动作之一，就是：把高层级的合并，尽量降级成低层级的合并。

第一档：拼接（Concat / Union）

定义：子结果之间完全独立，合并不做任何计算，只是按顺序或按片排在一起。

例子：MapReduce 的 map-only 作业；全局有序输出配合预分区（各 reducer 的 key 范围不重叠，结果直接顺序拼接）；分片库上按分片键做范围查询（每片返回自己那段，拼起来即可）。

成本：O(结果集大小)，且完全可并行（各分片各写各的）。

这是最便宜的合并。只要有可能，就把所有合并降级到这一档。 怎么降？答案你已经见过两次了：预分区——让需要合并的东西从一开始就在同一个地方，或让它们天然有序、根本不需要交叉计算。

第二档：聚合（Aggregate / Reduce）

定义：把子结果按某种运算规约成一个值（或一组 key 的值）。

例子：count、sum、max、min、top-N、直方图。

成本：

数据量层面：可**局部聚合（Combiner）**压缩，从 O(原始记录数) 降到 O(key 种类数)
结构层面：可树形聚合，深度从 N 降为 log N

关键前提：结合律（+交换律）。有了它，你可以任意分组、任意顺序、任意深度地合并。子主题十讲的三件武器，全是在这一档里做优化。

反例（会掉到更贵的档）：精确去重计数（count distinct）。 为什么？两个集合的并集大小 = a + b − |交集|，但要算交集你得知道具体元素。所以精确 count distinct 天然要求”把同一个 key 的所有值聚到一起”，无法用结合律做无损的局部压缩（除非你把整个集合传过去）。

这就是 count distinct 在大数据系统里出了名的贵的原因，也是 HyperLogLog 这类近似算法存在的理由。

记住这个模式：“精确”有时会破坏结合律，而结合律一旦没了，你就失去了所有便宜的合并手段。这就是分布式系统里充满”用近似换可合并性”交易的原因。

同类例子：近似 top-K、BloomFilter（可合并的集合成员判断）、count-min sketch（可合并的频次估计）。它们的共同点是：用一个满足结合律的固定大小结构，代表一个无界的数据集——本质上又是一次”用空间换合并成本”。

第三档：连接（Join）

定义：结果依赖不同子问题之间的元素配对。A 片的第 i 条，可能要和 B 片的第 j 条组合。

成本：必须把配对双方搬到同一个地方 → 一次全量重分布（shuffle）。

但 Join 内部还有档次之分，这个梯度非常实用：

Join 类型	是否 shuffle	做法	适用
Broadcast join	否	小表广播到所有节点，大表原地不动	一张表显著小，能放进 executor 内存
Co-located / bucket join	否（或极少）	两表预先按同一个键、同一种分区方式分好，同分区内本地 join	数据从一开始就按 join key 分桶
Shuffle hash join	是	两边按 join key shuffle，同 key 落同节点，内存建哈希表	一般情况
Sort-merge join	是	两边按 join key shuffle + 排序，再归并	大表对大表；已排序数据；内存不足

看第二行——co-located join 是这一档里最妙的：它把第三档的合并，直接降级成第一档的拼接。

如果两表从一开始就按同一个 key、同一个哈希函数、同样的分片数分片，那么”分片 i 的订单”和”分片 i 的用户”天然配对——join 退化成每个分片内部的本地操作，跨节点合并归零。

代价是：你为了这一次 join，把两张表的分片策略绑死了。 若还有第三个查询要按别的 key join，就得再冗余一份。

这就是分治在数据层的根本矛盾的最终形态：

你只能按一个维度”预组织”数据。任何一次预组织，都是”用存储冗余和写入复杂度，换某一类查询的合并成本归零”。

第四档：共识（Consensus / 全局决策）

定义：合并的结果不是一个数据值，而是一个”全体必须同意的决定”。

例子：分布式锁（谁拿到锁）、选主（谁是 leader）、分布式事务提交（提交还是回滚）、全局唯一约束（这个用户名有没有被占用）、全局单调 ID 分配。

成本：网络往返 + 多数派投票 + 持久化，而且不可并行（它本质上就是”让 N 台机器变成 1 台”）。

这是最贵的合并，而且它有一个恐怖的性质：它是唯一一档无法用”局部聚合”或”预分区”降级的合并。

为什么？因为共识的本质是”消除分歧”，而”预先消除分歧”这个动作本身就需要一次共识。 你不能预先决定谁拿到锁——那还需要一次共识来确认这个决定。

所以这一档的优化手段不是”让它更便宜”，而是”少用它”：

手段	做法	本质
号段分配	一次共识拿一段 ID（如 1~10000），本地自增用完再要	把 N 次共识摊成 1 次
无主 / 冲突消解	不做全局锁，用 CRDT 或 last-write-wins 容忍冲突	用”允许分歧”换”不需要共识”
本地决策 + 事后对账	先本地扣减（不共识），异步对账补偿	用”短暂不一致”换”低延迟”
单写入者	让某类决定只由一个分片 / 一个服务来做	把”共识”降级成”路由”
幂等 + 重试	at-least-once + 幂等，替代 exactly-once 的协调开销	用”重复执行无害”换”不需要协调整个流程”

看最后两行——它们揭示了一个极实用的架构原则：

共识的很多使用场景，都可以通过”让某个决定只由一个地方来做”而消除。而”只由一个地方做”的实现方式，恰恰就是分片：按 key 路由到唯一的分片，那个分片就是这件事的唯一决策者。

分片和共识在这里发生了奇妙的互换：分片把”全局决策”变成”局部决策”，从而消灭了对共识的需求。

举例——库存扣减：全局锁（共识，第四档）→ 改成”按商品 ID 分片，请求路由到该商品所在分片，分片内本地锁 + Raft 保证可靠”（变为第二档的聚合 + 分片内的可靠存储）。秒杀系统的所有优化，本质上都在做这一件事。

四档定价表

档次	合并类型	可局部聚合	可树形并行	可预分区降级	相对成本
1	拼接	不需要	天然并行	—	最低（O(结果集)）
2	聚合	可以（需结合律）	可以	部分（分组键固定时）	中（可压到 O(key 数)）
3	连接	可以（半连接等技巧）	可以	可以（co-located → 拼接）	高（全量重分布）
4	共识	不可以	不可以	不可以	最高（往返 + 投票 + 落盘，且串行）

把这张表当成设计检查表。每次写分布式逻辑时问一句：我这个合并落在第几档？能不能往下压一档？

全章速查卡：分治的十二个反模式

最后给一份能直接贴在墙上的清单。每一条都是”看起来在做分治，实际在自伤”：

为了分而分：数据量单机能扛却提前分片。处方：先做冷热分离 / 归档 / 读写分离。
分片键选了时间或自增 ID：所有写入打在最后一个分片。处方：哈希，或 (时间, 哈希) 复合键。
分片键基数太低（性别、状态码、国家）：分不了几片且天然不均。处方：复合键。
拆分没有终止阈值：拆到 1 个元素还在 fork，管理开销盖过计算。处方：sequential cutoff。
在共享线程池里跑阻塞 IO（parallelStream / commonPool）：一个慢 IO 污染整个 JVM 的并行任务。处方：阻塞任务用独立线程池。
用 groupByKey 做聚合：把原始记录全量搬运。处方：reduceByKey / aggregateByKey（map 端预聚合）。
监控只有汇总曲线：倾斜被均值掩盖。处方：按分片下钻，告警看 p99 / max。
重试无上限、无退避、无熔断：小抖动 → 重试风暴 → 雪崩。处方：次数上限 + 指数退避 + jitter + 熔断。
重试的操作不幂等：重复执行导致数据损坏。处方：唯一键去重，或状态机幂等。
把不可分的热点硬分片（全局计数器、爆款库存）：再怎么分都在一片。处方：拆子计数器 + 本地缓存 + 批量合并写。
微服务按技术层拆（controller / service / dao）：分布式单体。处方：按限界上下文拆，过四条健康检查。
只报”加机器后的加速比”：测到的可能是局部性和 IO 并发，不是并行。处方：三组基线（单机全量 / 单机分批 / N 机并行）。

演进脉络

早期（单机算法）：分治是纯算法技巧（归并排序、二分查找），无协调成本。
中期（数据分片）：数据库分库分表、一致性哈希出现，分治进入存储层，开始面对”跨分片”难题。
2004 年：Google 发表 MapReduce 论文，把分布式分治封装成框架，“分解-并行-容错-合并”被标准化。
2010s：Spark 用内存计算和 DAG 优化 Shuffle；流处理引擎（Flink）把批处理的分治改造成增量流式。
2013 年：《The Tail at Scale》（Dean & Barroso）把”完成时间由 max 决定”这件事系统化，长尾治理（对冲请求、推测执行、隔离慢节点）成为分治系统的标配。
现代：存算分离、Serverless 计算——计算侧无状态化，让”分片迁移”这件事本身被回避掉；复制（Raft 组）与分片组合成标准形态。

一条主线贯穿：分治的每一次演进，都是在降低”协调成本”这个副作用——从手工分片，到框架托管，到自动化弹性。但”协调能力决定加速比”这个本质从未改变。

另一条对偶的线也在同步演进：分片解决”装不下”，复制解决”会挂掉”。两个动作在不同层次交替出现，而”在哪一层分、在哪一层合”，才是架构设计真正的决策点。

本章思考题

【思考题】

分治”换”来的新麻烦有哪些？为什么说”分治用协调复杂度换了规模扩展性”？
Amdahl 定律说明了什么？为什么”优化串行部分比增加并行度更划算”？
数据分片的三种方式（范围、哈希、一致性哈希）各有什么优劣？
什么时候不该用分治？请给出至少三条判断标准。
主定理的三档结果分别意味着什么？为什么最近点对算法的”合并”如果写成朴素的两两比较，分治就白做了？
Shuffle 阶段到底包含哪些子步骤？为什么说它是”全量重分布”而非”部分搬运”？Spark 声称用内存计算加速，它真的消灭了 Shuffle 吗？
选择分片键时要权衡哪三个维度？这三个维度冲突时，常见的”加一层”手段有哪些？
数据倾斜为什么”均值完全正常”？识别它的正确观测方式是什么？加盐、复合键、动态分片三种手段各自的代价是什么？
从 N 台机器扩到 N+1 台，普通哈希取模会有多少数据需要迁移？一致性哈希把这个数字降到了多少？虚拟节点解决的是什么问题，代价是什么？
Combiner 为什么能大幅减少 Shuffle 数据量？它的数学前提是什么？为什么说”正确性不能依赖 Combiner 被调用”？
分治在算法层、单机并行层、分布式计算层、架构层这四个层次上，各自的”合并成本”用什么货币计价？为什么越往上”拆得细不细”越不重要、“拆得对不对”越重要？
什么叫”分布式单体”？它有哪四个典型症状？判断一次微服务拆分是否真的完成了，有哪四个健康检查？
除了”数据量太大”和”QPS 太高”，还有哪些信号说明真的该分片了？分片上线前必须准备好的五件事是什么？
分治的”形状”由扇出和深度两个参数决定。深度分别以什么方式影响延迟和可靠性？扇出又决定了什么？为什么 MapReduce 选择”只有一层、中间全落盘”这种看似很笨的形状？
为什么分治系统的完成时间是 max(子任务时间) 而不是平均值？“数据倾斜”和”长尾”是两种不同的病，它们的成因和治法有何区别？推测执行为什么不能在任务启动的瞬间就发起？重试为什么必须以幂等为前提且必须有界？
有状态分片迁移和无状态分片迁移的难度差在哪？Redis Cluster 用 ASK 和 MOVED 两种重定向解决了什么问题？Kafka 消费者组的 eager rebalance 为什么被称为 stop-the-world，静态成员和协作式增量再均衡分别缓解了什么？
Amdahl 定律与 Gustafson 定律分别适用于哪两种实验设定？Gustafson 公式 S(N) = N - (N-1)·s 中的 s 是如何定义的？怎样用两次不同并行度的实测反推串行比例 s，以及”反推出的 s 随 N 变大”意味着什么？为什么测量加速比必须补上”单机分批”这一组基线？
分治与复制是一对对偶操作：它们各自的目的、代价、以及带来的一致性难题分别是什么方向？为什么说”共识是用 2f+1 台机器模拟 1 台不会宕机的机器”？为什么共识是最贵且无法用局部聚合或预分区降级的合并？
合并可以分为拼接、聚合、连接、共识四档。请分别说明它们能否局部聚合、能否树形并行、能否用预分区降级，并举例说明”把高层级的合并降级成低层级的合并”的两种具体做法（例如 co-located join、用分片替代全局锁）。

【参考答案】

新麻烦：协调成本（谁分、谁收、失败了怎么办）、失败成为常态（100 台机器每天有机器挂是统计必然）、数据倾斜（90% 数据集中在少数 key，整体耗时由最慢那台决定）、合并阶段成为新瓶颈（并行了计算却串行了合并）、跨分片操作复杂（分布式事务）。所以分治不是把 1 个大问题变成 100 个小问题，而是变成”100 个小计算问题 + 1 个协调问题”，而那个协调问题往往才是真正的难点。
Amdahl 定律：若 P 比例可并行，加速比上限是 1/(1-P)。90% 可并行则上限仅 10 倍，即使用 1000 台机器。它是非线性收益递减的。所以优化串行部分更划算：并行度受天花板限制，而改善串行部分直接提高天花板本身。在分治场景里，“串行部分”就是合并阶段、协调开销、数据倾斜——优化它们比加机器有效得多。
范围分片：范围查询高效（连续 key 在同一片），但容易热点（某个范围访问量集中）。哈希分片：分布均匀、不易热点，但范围查询要扫全部分片。一致性哈希：扩容时只需迁移部分数据（而非全量重分布），配合虚拟节点还能打散热点，但实现更复杂。选择取决于查询模式是”范围扫”还是”点查”，以及是否需要频繁扩容。
不该分治的情况：问题规模不大（单片能扛住，分片的运维和事务成本是自找麻烦）、子问题耦合太紧（图算法、迭代算法，跨节点通信比单机还慢）、需要强全局一致（跨分片事务代价超收益）、以及还没试过垂直扩展（换更强的机器、优化算法、加索引通常成本低一个数量级）。
主定理给出 T(n) = aT(n/b) + f(n) 的三档：f(n) 明显小于 n^(log_b a) 时为 Θ(n^(log_b a))（合并几乎白送）；同阶时为 Θ(n^(log_b a)·log n)（每层平摊一份）；f(n) 明显更大时为 Θ(f(n))，即合并吞掉一切、分治白干。最近点对若用朴素合并（左半每个点对右半每个点），f(n) = Θ(n²)，T(n) = 2T(n/2) + Θ(n²) = Θ(n²)，和暴力一样。它之所以能到 Θ(n log n)，靠的是两个剪枝观察：跨中线的候选点对只可能落在中线 ±δ 的竖条里，且竖条内按 y 排序后每个点只需比较紧随的常数个（平面情形为 7 个，由鸽巢原理保证）。于是合并从 Θ(n²) 降到 Θ(n)。
Shuffle 包含：Partition（hash(key) mod R 决定去哪个 reducer）、map 端按分区排序后 spill 落盘、多个 spill 文件归并成一个按分区有序的文件、reducer 端从所有 map 节点 fetch 自己那一份、再归并排序。它慢的三个原因：一是全量重分布——M 个 map 和 R 个 reduce 之间理论上存在 M×R 条连接，每条记录都可能去任何一台机器，而不是只搬一部分；二是磁盘 IO 被重复支付（缓冲→spill→合并→发送→落盘→归并读取，同一份数据被完整读写好几遍）；三是外部排序的 O(n log n) 成本。Spark 没有消灭 Shuffle：它做的是（a）用 RDD 血缘把中间结果放内存，把容错从”落盘复制”变成”丢失重算”，把 IO 成本从正常路径挪到异常路径；（b）用 DAG 区分窄依赖（可 pipeline，无 shuffle）和宽依赖（必须 shuffle），并通过 reduceByKey 这类 map 端预聚合算子减少 shuffle 数据量；（c）用 broadcast join、AQE 倾斜处理等手段尽量绕开或拆分 shuffle。宽依赖依然是宽依赖。
三个维度：查询模式（最高频查询的 WHERE 交集字段，决定哪些查询是本地查询、哪些变 scatter-gather）、数据分布（基数够不够高、是否均匀、有无天然热点，如按时间分片会导致写入全打在最后一片）、扩容需求（加机器频率、是否停服、迁移耗时，决定取模哈希还是一致性哈希）。冲突时的”加一层”手段：冗余双写（按两种键各存一份，代价是存储翻倍和一致性延迟）、全局二级索引（索引独立分片，查询多一跳，写入要维护索引）、维度表广播（小表每片存全量，用空间换网络，join 本地完成）。
倾斜时均值正常是因为少数热分片的高负载被多数低负载分片稀释：100 个分片平均 QPS 1000，实际可能是 97 片 300、3 片 25000。所以识别只能看分布不看均值：p99/p999 与均值的比值、各分片资源水位（CPU、连接数、IO、慢查询）的方差、hot key 访问频次 Top N、以及”p50 很好但 p99 很差”这个倾斜指纹。三种手段的代价：加盐（写压力打散，但点查变散射读、聚合需改成两段聚合，适合写多读少或热 key 可枚举）；复合键（分布更均匀，但只带主维度不带次维度的查询从单分片变多分片，前提是读查询能稳定带上次维度）；动态分片（不需预测热点，但迁移本身占网络 IO、路由元数据要一致更新，且对”单个 key 极端热”的突刺无效，此时仍需加盐）。
普通哈希取模从 N 扩到 N+1，只有同时是 N 和 N+1 倍数的 hash 值留在原地，约 1/(N+1) 不动、约 N/(N+1) 需要迁移（4→5 是 80%，99→100 是 99%），且迁移是跨网络的，还会导致缓存整体失效打穿下游。一致性哈希把节点和 key 都映射到固定哈希环上，key 顺时针找第一个节点；新增节点只抢走它与逆时针前驱之间那段弧上的 key，迁移比例降到约 1/(N+1)（即 1/N 量级），减节点同理只影响相邻弧。它不是零迁移，是”迁移量与节点数成反比”。虚拟节点解决的是负载不均：节点随机落环导致弧长不均，不均衡度是 Θ(log N) 量级，且无法表达节点容量差异；一个物理节点映射为 k 个虚拟节点后，负载标准差约按 1/√k 收敛，还能用虚拟节点数量加权实现异构容量、让扩容和宕机时的流量转移被摊薄。代价是环上节点数变成 N×k，路由表变大、查找与元数据维护成本上升。
Combiner 在 map 端先做局部聚合，把”每个 key 的每条原始记录”压缩成”每个 key 一个部分结果”，数据量从 O(语料大小) 降到 O(key 种类数)，对 Zipf 分布的自然语言语料压缩比常常成百上千倍，跨网络传输量和 spill 落盘量同比例下降。数学前提是结合律：(a+b)+c = a+(b+c)，保证先局部后全局与直接全局结果一致；在 Spark 这类不保证分组内元素顺序的框架里还需要交换律。不能依赖它被调用，因为在 MapReduce 里 Combiner 只是优化提示，框架不保证调用次数甚至不保证调用，因此它必须满足”执行了更快、不执行也对”，且必须无副作用（否则被调用 0/1/多次会导致结果不同）。
四层的”合并成本”货币：算法层（二分、归并、Strassen）分的是数据，合并成本是内存指针操作，纳秒级，协调成本为零，唯一陷阱是递归终止阈值和拆不均；单机并行层（Fork-Join、parallelStream）分的是计算任务，合并成本是内存访问与缓存一致性，纳秒到微秒，陷阱是公共线程池被阻塞 IO 污染、伪共享、内存带宽墙；分布式计算层（MapReduce、Spark）分的是数据加计算，合并成本是跨节点重分布与磁盘 IO，毫秒到秒，比内存操作贵五六个数量级，陷阱是 Shuffle 和数据倾斜；架构层（微服务）分的是业务能力与团队边界，合并成本是服务间调用加组织沟通，毫秒到天，陷阱是分布式单体和级联故障。之所以越往上”拆得细”越不重要，是因为分解本身几乎总是廉价的（算个 mid、发个 RPC），而合并成本随层次呈数量级上升：算法层合并几乎免费，所以可以随便拆；架构层一次跨服务调用可能是进程内函数调用的百万倍代价，此时决定成败的是边界是否切在业务语义的正确位置（限界上下文），而不是服务数量有多少。判断方向的口诀是：往下（算法层）可以放心多拆，往上（架构层）必须谨慎少拆。
分布式单体：系统被拆成了很多服务，却必须一起部署、一起升级、一起挂——付出了分布式的全部代价，没拿到分布式的任何收益。四个典型症状：改一个需求要动多个服务且必须按序发布（是耦合不是拆分）；所有服务共享同一个数据库（schema 一改全部受影响，边界是假的）；同步调用链极深，可用性是乘法关系（10 个 99.9% 的服务端到端只有 99%），且没有熔断降级时一次抖动就是雪崩；按技术层（controller/service/dao）而非业务能力拆分，服务间调用量比原单体内部函数调用还大，还白白多了网络开销。根因是用技术维度而非业务边界拆分。四个健康检查：独立部署（能否不通知其他团队独自发布）、独立扩缩（该服务流量翻十倍能否只扩它）、独立失败（它挂了别人是降级还是一起挂）、独立演进（换数据库/语言/框架是否需要别人同意）。四项有任一答”不能”，拆分就没完成。
除数据量和 QPS 外的信号：单机 CPU 持续高位（要区分有效计算与锁等待/上下文切换）；连接数打满（单机硬约束，加应用机器反而更糟）；写入打满（写入最难用缓存和只读副本解决）；备份/恢复/DDL 时间不可接受——这是最早出现却最被忽略的信号，若全量恢复时间已超过可接受的最长停机时间，即使性能还好也必须分片，因为失去的是出事后能救回来的能力；垂直扩展撞墙（顶级机型价格二三倍但性能不到两倍）。分片前必须准备的五件事：可动态下发的路由层（客户端内嵌/代理层/服务端路由/配置中心，路由规则必须可配可动态下发）；迁移工具与双写方案（双写+灰度读+对账+可回切开关）；分布式 ID 生成器（自增主键在分片后会撞号，需 Snowflake 类或号段方案，且影响所有表结构，要提前做）；跨分片查询的兜底（跨片分页要在每片取 N 条再归并、深分页代价极大，以及全局排序/聚合/事务要提前想好牺牲哪些）；能按分片下钻的监控（每个分片独立的 QPS、延迟、连接数、磁盘、慢查询，汇总曲线会掩盖倾斜）。
递归树的形状参数是扇出 a（每个节点拆成几个子问题）和深度 log_b n（层数）。在分布式系统里深度变成两笔很贵的账：一是延迟——深度是延迟的线性函数，每层意味着一次网络往返 + 落盘 + 调度决策，所以延迟敏感的场景要”矮胖”（大扇出、小深度）；二是可靠性——深度是可靠性的指数函数，若每跳成功率 p，一条深度 d 的路径全部走通的概率是 p^d，且任务数越多暴露面越大，所以”深比宽危险”。扇出决定单点压力：扇出 k 意味着父节点要维护 k 条连接并汇聚 k 份带宽，这具象化为 MapReduce 中 R 个 reducer 各自从 M 个 map 拉取数据的 M×R 连接数问题——R 太大则连接数爆炸、小文件太多，R 太小则并行度不够、单点成瓶颈、倾斜时无回旋余地。MapReduce 之所以选”只有一层、中间全落盘”，是因为这个形状同时买到三样东西：容错极简单（map 输出已落盘，任一 reduce 失败只需重跑该 reduce 并从磁盘重拉，中间没有需要维护的状态）、调度极简单（只有两波任务，无多级依赖和中间结果生命周期）、可靠性最优（深度 = 1，可靠性账的指数为 1）。它付的代价是磁盘 IO 被重复支付，这正是后来 Spark 优化的方向。
分治把总工作量除以了 N，但完成时间等于所有子任务完成时间的最大值——因为任务要等全部子结果到齐才算完成。而取样越多最大值越大，所以并行度越高，你越是在跟分布的尾巴打交道，优化对象从平均情况变成极端情况（这正是《The Tail at Scale》的核心：fan-out 会把单机极低的长尾概率放大成端到端的常态）。倾斜与长尾是两种不同的病：倾斜是”某些子任务天生活多”（数据分布问题，可提前从 key 分布看出），治法是加盐 / 复合键 / 动态分片 / 热 key 旁路；长尾是”活一样多但跑得慢”（执行环境问题：慢盘、超卖邻居、GC、记录大小倾斜、调度排队、外部依赖抖动），治法是把任务切小切多、推测执行、隔离慢节点。关键区别：推测执行对倾斜无效（备份任务的活一样多，一样慢，还白占机器），所以必须先分辨再下药。推测执行不能在 t=0 就发起，否则等于把所有任务跑两遍、集群负载翻倍、反而制造更多长尾；正确做法是观察到明显落后之后再发备份任务，或用 hedged request（超过 p95/p99 阈值再发第二份）。重试必须以幂等为前提，因为在分治系统中无法区分”没开始 / 跑了一半 / 跑完但回传失败”，重试必然意味着可能重复执行，不幂等就是数据损坏——所以铁律是 at-least-once + 幂等消费 = 效果上的 exactly-once。重试必须有界，否则下游抖动 → 上游全重试 → 流量放大 → 下游更抖 → 雪崩；限制手段是次数上限、指数退避加 jitter（不加 jitter 会造成惊群同步重试）、以及熔断。此外重试率必须是一级监控指标。
无状态分片迁移的是”任务”，节点挂了换一台重跑，成本≈0；有状态分片迁移的是”数据 + 路由 + 一致性”，要同时处理四个问题：网络/磁盘 IO 占用挤压在线流量、边写边搬时的一致性、路由切换的原子性、以及可回滚性。难点在于迁移不是瞬时的而流量是连续的：搬完后才切路由会丢失过渡期的写入。Redis Cluster 的解法是区分两种重定向——迁移中的槽在源节点标记 MIGRATING、目标节点标记 IMPORTING；若 key 还在源节点就正常处理，若已搬走则返回 ASK（临时重定向，客户端去目标节点要一次但不更新本地路由表），而 MOVED 是永久重定向、客户端收到才更新路由缓存。ASK 是”临时问一次”，MOVED 是”永久改路由”，区分二者就让”迁移中”这个中间态能被精确表达，而不是让客户端猜。通用原则是任何有状态迁移都必须设计过渡态协议，让客户端能区分”还没搬 / 正在搬 / 已搬完”。Kafka 消费者组的 eager rebalance 之所以是 stop-the-world，是因为协议要求所有成员先撤销自己持有的全部分区、重新加入组、协商出新方案后才能恢复消费——滚动重启 20 个实例就会触发 20 次全组停顿，一次心跳超时被踢出组也会触发全组再均衡，造成消费积压反复冲高。静态成员（给消费者稳定实例 ID）让短暂重启在会话超时内返回不触发 rebalance，消灭了最高频的痛点；协作式增量再均衡则只交出需要移动的分区、其余分区继续消费，再均衡期间不停止消费。二者共同的原则是缩小 rebalance 的爆炸半径：能不触发就不触发，触发了就只动必须动的部分。
Amdahl 适用于强扩展（问题规模固定，加机器求更快，S(N)=1/(s+(1-s)/N)）；Gustafson 适用于弱扩展（每台机器处理的数据量固定，加机器的同时加数据，求相同时间干更多活，S(N)=N-(N-1)·s）。Gustafson 公式里的 s 是”在 N 个处理器上运行时串行部分所占的时间比例”，不是串行程序里的串行比例——推导：把 N 处理器上的总时间归一化为 1，串行 s、并行 (1-s)，这些并行工作放在单核上要 N×(1-s)，故相对单核的加速比 = s + N(1-s) = N-(N-1)s。反推串行比例：由 Amdahl 公式解出 s = (1/S - 1/N)/(1 - 1/N)；在两个不同并行度（如 4 和 16）下各测一次，若两者反推出的 s 一致，说明 s 是常数；若 N=16 反推出的 s 明显大于 N=4 的，说明并行度提高时出现了新的串行瓶颈（协调开销随 N 增长、合并阶段单点收敛、路由元数据要同步给更多节点、连接数上升导致网络争用），也就是说 Amdahl 的天花板在往下掉。必须补”单机分批”基线的理由是排除超线性加速的假象：可以测出 S>N 的真实原因是缓存/局部性效应（数据切小后能完整放进 cache，单机跑全量却在换页），但更多情况是基线不公平（单机内存不够一直做磁盘交换）或 IO 并发度变化（10 台 = 10 块盘）。正确协议是测三组——单机全量、单机分批、N 机并行：前两组之差是局部性收益，后两组之差才是并行收益，只报第三组对比第一组是耍流氓。
分治与复制的目的、代价、麻烦三者都对偶。目的：分治（拆成 N 份）提升规模上限与吞吐、容量线性增长；复制（抄成 N 份）提升可用性与读吞吐、容量不变。代价：分片让写入被分散从而提升写吞吐，但点查变快的同时范围读退化为 scatter-gather；复制让读可分摊到副本，但写入要写 N 份（3 副本 3 倍写成本，5 副本相对 3 副本写入成本再放大到 1.67 倍）。一致性难题方向相反：分治的问题是”一个逻辑对象只有一个副本却被跨分片引用”（跨片事务、跨片 join、跨片唯一约束，“钱在 A 片货在 B 片要原子改两边”）；复制的问题是”一个逻辑对象有多个副本且可能不一样”（主从延迟、脑裂、读到旧数据，“同一笔余额三个副本记了三个数”）。一个”分”出来的问题，一个”抄”出来的问题。说”共识是用 2f+1 台机器模拟 1 台不会宕机的机器”，是因为共识协议的目的不是并行而是消除单点，而它达成目的的方式恰恰是让多台机器对外表现得像一台——即在逻辑上把 N 台”合并”回一台，与分治”把 1 台拆成 N 台提升能力”正好互为逆操作，它们也因此是同一个动作的正反两面。共识是最贵的合并：归并排序的合并是纳秒级指针比较，shuffle 的合并是毫秒级跨节点传输，共识的合并是网络往返 + 落盘 + 多数派投票，而且任何一台参与副本慢/网络抖都会拖慢提交（与”完成时间 = max”同理）。它无法用局部聚合或预分区降级，因为共识的本质是消除分歧，而”预先消除分歧”这个动作本身就需要一次共识——你不能预先决定谁拿到锁。所以这一档的优化不是让它便宜，而是少用它：号段分配（N 次共识摊成 1 次）、无主冲突消解（用允许分歧换不需要共识）、本地决策 + 事后对账、单写入者（把共识降级成路由）、幂等 + 重试。
四档的定价维度：①拼接（如 map-only 作业、预分区后的全局有序输出）——不需要聚合、天然可并行、成本 O(结果集)，是最便宜的一档；②聚合（count/sum/max/top-N）——可局部聚合（Combiner，需结合律，把 O(记录数) 压到 O(key 数)）、可树形并行（深度从 N 降到 log N）、分组键固定时也可部分预分区降级；③连接——可局部聚合（半连接等技巧）、可树形并行，且可以用预分区显著降级；④共识——既不能局部聚合、也不能树形并行、更不能用预分区降级，成本最高且串行。两种”降级”的具体做法：其一，co-located / bucket join：让两张表从一开始就按同一个 key、同一个哈希函数、同样的分片数分片，于是”分片 i 的订单”与”分片 i 的用户”天然配对，join 退化为每个分片内部的本地操作，把第三档的全量重分布降级成第一档的拼接，跨节点合并归零；代价是为这一次 join 把两表的分片策略绑死，第三个按别的关键字 join 的查询就要再冗余一份（这体现了”你只能按一个维度预组织数据”的根本矛盾）。其二，用分片替代全局锁：库存扣减原本需要全局锁（共识，第四档），改成按商品 ID 分片、请求路由到该商品所在分片、分片内用本地锁 + Raft 保证可靠，于是”全局决策”变成”局部决策”，分片消灭了对共识的需求——秒杀系统的所有优化本质上都在做这件事。通用原则是：分片和共识会发生互换，让某个决定只由一个地方来做（按 key 路由到唯一分片，该分片即唯一决策者），就能把最贵的共识降级为廉价的路由。

徐术挺-漫思录

探索

06-分而治之