动机
把大计算分给多台机器,只有在结果能重新组合成预期答案时才有用。分块大小不等时,对各块均值取平均会出错;把重试算两次,即使各台机器的局部计算都正确,数据也已改变;浮点总和则可能随合并树改变。这是三个不同的问题,增加工作节点并不能同时解决它们。
我们先研究精确直方图,因为它的代数很清楚:固定的类别数给出有界摘要,合并就是逐分量相加。再用这个例子分析依赖、通信与负载不均。最后回到浮点求和:同一棵树既组织计算,也改变舍入误差。目的是给出可以核查的、与框架无关的参考计算,不指定某种产品,也不把本机演示冒充为硬件基准测试。
MapReduce 的观点,是对独立分区作映射,再归约其摘要;它本身没有指定操作系统或容错协议。以下程序在本机串行运行。依赖图指出在给定资源假设下哪些节点可以并行,但并未测量真正分布式系统的速度。这条界线让我们能把代数正确性与实际性能分开讨论。
定义
以下反复出现三类对象:被合并的摘要、规定合并哪些摘要的约定,以及度量并行时间的成本模型。
定义 5.1.1
(直方图摘要与合并)
记录的类别属于 ,。有限多重集 的直方图是 ,第 个分量是类别 的出现次数。合并为 ,单位元是零向量。
同一类别可以有多条不同的观测;重复处理同一条预期观测则是数据处理错误,除非目标本来就允许重复。
定义 5.1.2
(恰好一次的分区约定)
分区标识符标记固定输入版本中互不重叠的片段。归约约定要求每个预期标识符恰好有一份被接受的摘要,其他标识符则一份也没有。确定的合并树还固定每个内部节点配对哪些摘要。
叶节点正确与算术可复现是相互独立的性质:完全可复现的树也可以稳定地算出错误数据的结果。
定义 5.1.3
(工作量、跨度与列表调度)
工作量是所有节点的总算术量;跨度是在处理器数量不受限的模型下,计算图中最长的依赖链。调度模型中,每个作业在 个相同工作节点中的任一个上成本为正数 ;列表调度在节点空闲时派发下一个等待的作业,作业不可抢占。
有限系统上的运行时间至少是工作量除以处理器数,也至少是跨度,还可能包括输入、通信及等待。 等计数采用单位成本算术;任意大的精确整数需要更多的位运算,不能忽略字长模型。调度模型不包括网络竞争或同时运行造成的速度变化,所以所得上界不是共享链路系统的实际秒数保证。
定理 / 命题
定理 5.1.4
(精确摘要与分区独立性)
若 是互不重叠的分区,则 。任何以它们为叶节点的二叉合并树,在精确整数算术下都得到同一摘要。各节点可以用 工作量、 摘要空间逐条计数,无须保留原始记录。
定理 5.1.5
(显示负载倾斜的列表调度界)
令 、。 个相同节点上的列表调度,完成时间满足
任何调度都有下界 。上界假设作业一开始就可以派发,并且有等待作业可以运行时,空闲节点不会闲置。
命题 5.1.6
(浮点树形求和的误差界)
设每次加法满足 、,并且没有使该模型失效的上溢或下溢。对高度为 的二叉求和树,若 ,计算结果满足
个叶节点的平衡树高度为 ,串行链的高度可达 。此界是绝对误差界;精确总和近乎相消时,不保证相对误差小。
证明思路
证明
(分区独立性的证明)
对每个类别,互不重叠并集中的次数等于各块次数之和,所以逐分量证得合并恒等式。对树归纳,每个内部节点就代表其后代的并集。结合律、交换律与零单位元允许重新分组、重新排序及空分区,却不允许删去叶节点,或把重试当成额外的叶节点。局部映射对其 条记录各处理一次,并初始化 个计数器,由此得到工作量与存储界。
互不重叠是代数本身无法提供的唯一假设。
反例模式
重叠片段会重复计数
断言:只要片段合起来覆盖全部输入,把它们的直方图相加就得到整体直方图。取记录 (类别 )和 (类别 ),真正的直方图是 。一次重试产生片段 与 ,两者覆盖输入却互相重叠。其直方图为 和 ,和为 :尽管每个节点都正确计算了自己的片段,记录 仍被计了两次。修正后的说法要求分成互不重叠的片段,而这正是恰好一次约定所强制的。
证明
(列表调度界的证明)
考察最后完成、成本为 的作业。若它在时间 开始,它在 期间一直在等待;列表调度下有作业等待时不会有节点空闲,所以 个节点在整段 都忙于其他作业,故 。因此 ,再用 代替 。所有工作终须完成,最大的不可分作业也必须由一个节点完成,故两个下界都成立。把其他作业切小,不能使这个大作业凭空消失。
证明
(树形求和界的证明)
从树根向叶展开计算结果:每个 乘上其路径上的舍入因子,至多 个。其乘积偏离一不超过 ,因为 ,而 。较短的路径可以补上因子一。减去精确和,再用三角不等式就得到上界。这是求和的证明,不能当作所有非线性摘要合并的通用误差定理。
最后一个证明把关于整棵树的陈述,化为关于各个叶节点的陈述。
证明透视
树同时有代数意义与数值高度
舍入模型在每个内部节点用一次:每次计算的加法,等于两个计算输入的精确和乘以一个因子 ,其中 。关键一步是展开整棵树,使计算结果成为每个输入乘以其自身根到叶路径上各因子之积的总和。树形只通过路径长度起作用,所以控制上界的是高度而不是叶数;使树形不影响数学直方图的精确结合律,在这里不起作用。假设 使每个乘积的界有限。论证以三角不等式收尾,也正是在这里变成以绝对值之和表示的绝对界。固定树消除了一种数值变动来源,平衡树限制了路径长度,但两者都不能证明病态的相消问题有小的相对误差。
例题详解
例题 5.1.7
(可运行的映射及平衡归约)
下面的完整 Python 程序先构造小型输入,把连续分区映射为直方图,拒绝重复标识符,核查有无缺失,再按固定的二叉树合并。为了便于检查,示例保存输入列表;局部映射本身只需要计数数组,可以直接消耗流式迭代器。
def map_counts(values, q):
counts = [0] * q
for value in values:
if not isinstance(value, int) or not 0 <= value < q:
raise ValueError("invalid category")
counts[value] += 1
return counts
def merge(a, b):
return [x + y for x, y in zip(a, b)]
def reduce_once(messages, expected_ids, q):
by_id = {}
for pid, summary in messages:
if pid not in expected_ids or pid in by_id:
raise ValueError("unexpected or repeated partition")
if len(summary) != q or any(not isinstance(x, int) or x < 0
for x in summary):
raise ValueError("invalid summary")
by_id[pid] = summary
if set(by_id) != set(expected_ids):
raise ValueError("missing partition")
level = [by_id[pid] for pid in sorted(expected_ids)]
if not level:
return [0] * q
while len(level) > 1:
level = [merge(level[i], level[i + 1])
if i + 1 < len(level) else level[i]
for i in range(0, len(level), 2)]
return level[0]
values = [(7 * i + 3) % 5 for i in range(37)]
blocks = [values[i:i + 7] for i in range(0, len(values), 7)]
messages = [(pid, map_counts(block, 5))
for pid, block in enumerate(blocks)]
answer = reduce_once(messages, set(range(len(blocks))), 5)
assert answer == map_counts(values, 5)
assert sum(answer) == 37
print(answer)
结果是 [8, 7, 7, 8, 7]。这个本机归约器在演示中保存 个摘要字段。分布式树改为在各层之间传送摘要,但其架构仍须执行相同的标识符与输入版本约定。只检查形状及非负计数,不能证明工作节点确实读取了预期的数据。
例题 5.1.8
(相同工作量,不同完成时间)
三个节点处理一个成本为八的作业及九个成本为一的作业,总工作量为十七。若先派发九个小作业,它们使全部节点忙到时间三,最后的大作业要到时间十一才完成。若先派发大作业,它占用一个节点,其余两个节点在时间五之前完成九个小作业,完成时间为八,达到最大作业给出的下界。
定理的上界为 ,所以两种结果都在允许范围内,且第一种次序取等号。下面的模拟器只计算调度,不等待也不测量真实机器:
import heapq
def completion(costs, workers):
free = [(0, worker) for worker in range(workers)]
heapq.heapify(free)
for cost in costs:
start, worker = heapq.heappop(free)
heapq.heappush(free, (start + cost, worker))
return max(time for time, worker in free)
assert completion([1] * 9 + [8], 3) == 11
assert completion([8] + [1] * 9, 3) == 8
按记录数平均分区,仍可能造成成本不均,因为有些记录需要昂贵得多的处理。细分作业可以改善负载均衡,却增加调度及通信开销。没有成本模型,工作量的界不会自动选出最佳分区大小。
例题 5.1.9
(确定的浮点总和可以稳定地丢掉一)
对 binary64 数值 ,从左到右求和时第一次加法舍入为 ,最后返回零;先把两个大的相反数相加则返回一,即精确的实数和。因此固定的树可以稳定地重复一个较差的答案。在 Python 中,math.fsum([1e16, 1.0, -1e16]) 用更仔细的求和过程也返回一;但这只是观察到的计算,并不证明任何库的求和对所有数据都精确。
对 个非负输入,求和的条件数为一,因此总和为正时,树形界也给出相对误差界。对于正负混合的输入,比值 可以任意大。因此,可复现性与条件数应和工作节点数分开报告。
常见错误
合并必须与状态相符。合并标识符互相重叠的摘要,或在没有依据的情况下先作非线性后处理,都会改变问题。归约服务还需要知道其标识符描述的是哪个输入版本;同一标识符但内容不同,就不是原来的那个分区。
常见错误
(忽略记录数而平均各分区均值)
片段 与 的均值分别为 和 ,平均为 ;全部四条记录的均值却是 。均值本身不是可合并的摘要。(记录数,总和)这一对,即 和 ,用加法合并为 ,就恢复出正确的均值。
概念视角结构
可合并的摘要就是幺半群同态
第一个定理说, 把多重集的不交并变成向量加法,并把空输入变成 :它是交换幺半群之间的同态,仅凭这一点,每棵合并树都正确。平均值则根本不存在这样的合并规则,而不只是规则不同。输入 与 的平均值都是 ,但并入片段 后,平均值分别为 和 ;两个片段平均值的任何函数都不能同时给出这两个结果。(个数,总和)这对量是同态,平均值只在最后由它算出。
通信也有数学上的规模。把 条记录映射成 个稠密直方图,需要 个摘要字段;类别全集很大时,稠密摘要可能很昂贵。局部出现的类别少时,稀疏摘要有帮助;但几乎处处出现的热门键,仍可能造成负载很重的聚合路径。树的深度、总字节数、消息延迟、工作节点内存及最大分区是各自独立的瓶颈。
例如,假设在没有其他竞争的链路上,传送含 个字段的消息需要 时间,其中 是延迟, 是每个字段的传输时间。平衡树约有 个依次进行的通信轮次,而通过单一串行瓶颈接收全部消息的归约器,可能在那里花费 量级的时间。这只是明确的玩具链路模型,不是对所有网络的预测。批处理减少了支付延迟的次数,却增大了消息,并可能推迟第一个可用结果。把热门键拆成若干局部部分和可以分散映射工作,但这些部分和最终仍须在一次归约中相遇:依赖只是换了位置,并没有消失。
常见错误
(把固定树当作跨环境的逐位保证)
固定树只在算术选择受控时才支持逐位复现。改变精度、编译器变换、局部求和次序或被接受的叶节点,都可能改变结果。实数算术下的代数答案是确定的,但这一陈述弱于跨环境的逐位保证。
总结
分区正确性是关于互不重叠输入片段的恰好一次约定。精确的合并代数允许重新分组,而工作量与调度界描述的是并行执行的不同限制。浮点求和在明确的舍入模型下,额外带有依赖路径、可由树高界定的误差。可运行的本机参考计算使这些区分可以核查,而不假装测量了分布式系统。
练习
快速检查
(类别为零、一、二,映射 及 ,合并摘要,并解释空块为什么不改变结果。)
逐块数出每个类别。
解答 · 答案
两个摘要为 、,合计 ,总数为五。空直方图 是加法单位元,不改变结果。这来自每个坐标的计数含义,与合并的分组方式无关。
快速检查
(两个节点分别按 与 的次序处理作业。求两种完成时间及列表调度上界。)
模拟两种次序,再用 与 计算上界。
解答 · 答案
第一种次序中,两个成本为三的作业在时间三完成,之后成本为十的作业到时间十三才完成。第二种次序中,一个节点处理十,另一个节点在时间六完成两个成本为三的作业,所以完成时间为十。总工作量为十六、最大作业为十,上界为 ,第一种次序取等号。
快速检查
(输入 的求和条件数是多少?为什么小的绝对树形求和界不一定意味着小的相对误差?)
比较 与 。
解答 · 答案
精确和为 ,绝对值之和为 ,比值是 。把绝对估计 除以微小的精确和,就把 放大了这么多倍。较矮的树有助于控制舍入的阶段数,但不能消除相消带来的条件数问题。
快速检查
(归约器预期标识符零至三,只收到零、一、三,但报告的记录数恰好合计正确。应否接受?若改为一出现两次,又应如何处理?)
检查恰好一次约定,而不是总数。
解答 · 答案
应当拒绝,因为缺少分区二。记录数偶然吻合,不能证明预期记录都已处理。同样,按约定重复的标识符一也必须拒绝,而不能当作额外的独立叶节点接受。这些检查保护输入身份,但不能代替对每份摘要内容的数学验证。