一、概述

由于 AppendOnlyMap 存放的是 Key 和 Value 的引⽤，并不是它们的实际对象⼤⼩，⽽且 Value 会不断被更新，实际⼤⼩不断变化。因此，想准确得到AppendOnlyMap 的⼤⼩⽐较困难。⼀种简单的解决⽅法是在每次插⼊ record 或对现有 record 的 Value 进⾏更新后，都扫描⼀下 AppendOnlyMap 中存放的 record，计算每个 record 的实际对象⼤⼩并相加，但这样会⾮常耗时。⽽且⼀般 AppendOnlyMap 会插⼊⼏万甚⾄⼏百万个 record，如果每个 record 进⼊ AppendOnlyMap 都计算⼀遍，开销会很⼤。

Spark 设计了⼀个增量式的⾼效估算算法，在每个 record 插⼊或更新时根据历史统计值和当前变化量直接估算当前 AppendOnlyMap 的⼤⼩，算法复杂度是 O(1)，开销很⼩: 在 record 插⼊和聚合过程中会定期对当前 AppendOnlyMap 中的 record 进⾏抽样，然后精确计算这些 record 的总⼤⼩、总个数、更新个数及平均值等，并作为历史统计值，每当有 record 插⼊或更新时，会根据历史统计值和历史平均的变化值，增量估算 AppendOnlyMap 的总⼩。

二、WritablePartitionedPairCollection 接口

WritablePartitionedPairCollection 是对由键值对构成的集合进行大小跟踪的通用接口。

三、SizeTracker 接口

Spark 在 Shuffle 阶段，给 map 任务的输出增加了缓存、聚合的数据结构。这些数据结构将使用各种执行内存，为了对这些数据结构的大小进行计算，以便于扩充大小或在没有足够内存时溢出到磁盘，特质 SizeTracker 定义了对集合进行采样和估算的规范。