Page 275 - 《软件学报》2025年第7期

3196 软件学报 2025 年第 36 卷第 7 期

加系统整体吞吐率.
典型流式分析应用场景中的数据分布可以由两个维度去判断, Key 分布的均匀性以及数据分布的均匀性. 对
于集群配置来说, 也可以划分为资源均衡型和资源不均型. 因此, 本文根据常见的数据分布场景和集群配置情况的
不同组合, 分别提出 Modulo、LeastKey、LeastCount、Weight 这 4 种负载分发策略, 并支持在 KeyBy 算子上自定
义负载分发策略.
(1) Modulo
当 KeyBy 所使用的 Key 为整数时, 例如常见的数字 ID, 且各 Key 的分布均匀 (下称 Key 均匀分布)、各 Key
对应的数据量相当 (下称数据均匀分布) 时, 负载分发可以通过 Key 对并行度取模, 均衡地将负载分发到后续的算
子的子任务上.
(2) LeastKey
当 KeyBy 所使用的 Key 不均匀分布, 但数据均匀分布时, Modulo 策略将难以均衡分发负载. 例如某市电压传
感器的 ID 先以区级别分配前缀, 如 A 区 100 000、B 区 200 000, 后 5 位 ID 按各区内部安装顺序递增, 此时由于
ID 的不连续性, 以传感器 ID 进行 KeyBy 时, Modulo 策略可能导致较差的负载均衡.
针对这类场景, 本文提出 Least 分配策略, Least 分配策略构造映射 f (k) = n, 其中 n ∈ N 且使得 S (n) 最小,
S : N → Z 是节点的当前负载的度量函数. 不同于批式处理中固定的输入数据集, 由于流式处理系统需要处理无界
的输入数据流, 因此负载分发中仅以当前的负载状态作为依据. 分布式集群下不同节点计算相同 Key 的目标子任
务时, 由于数据可能存在潜在乱序, 系统的负载状态持续改变, 导致计算产生的目标子任务状态发生改变, 因此
Least 策略的计算需要由特定的协调者进行计算和存储. Least 分发策略实现如算法 1 所示.
算法 1. Least 分发策略.

Function: Least(Key, S)
Input: Key: Field used in KeyBy of data, S: Load function that measures the load of nodes;
Output: Target node.
1. if Key is contained in History Assignment Map then
2. return assigned node
3. Select node N with minimize load by load function S
4. Increase load of node N in load function S
5. Assign N to Key in History Map
6. return node N

Least 策略在协调器上执行, 本地仅缓存分发结果. 在 Least 分发策略中, 如何选择具有最小负载的节点 N 是
算法的关键部分, 这取决于负载函数 S 如何存储节点的负载. 本文使用哈希表存储节点对应的负载, 使用跳表对节
点负载进行排序, 以实现常数时间复杂度的最小负载节点查找和对数时间复杂度的负载变更.
LeastKey 策略使用分配到节点上的 Key 数量作为衡量节点负载的函数 S, 在分发负载时, 选择当前负载最低
的节点, 因此适用于 Key 不均匀分布, 但数据均匀分布的场景.
(3) LeastCount
LeastCount 和 LeastKey 的区别在于度量节点负载的 S 不同, 当数据也不均匀分布时, 需要根据 Key 对应的数
据量进行负载分发, 由于无界数据流的 Key 对应的数据量比例往往在一定时间内不会剧烈变化, 可以使用历史的
比例信息反映当前的状况. LeastCount 使用分配到节点上的 Key 对应的历史数据量之和对节点负载进行度量, 并
在分发负载时选择当前的负载最低节点, 从而适用于数据不均匀分布场景, 但需要历史数据的支撑.
(4) Weight
Flink 以 Task Slot 为单位调度计算任务, 对所有的 Task Slot 一视同仁, 每个 Task Slot 往往表示一个 CPU 核