工作任务按主机权重循环比例分配的算法实现问题咨询

我们需要将M个工作任务以循环方式分配给N台主机，每台主机分配的工作量需与其运行速度成正比。无权重的基础分配逻辑实现代码如下：

int64_t AssignWorkToHost(const int64_t i_work) {
  return i_work % N;
}

分配比例由权重参数p[i]定义，所有p[i]的总和为1.0，第i台主机分配的工作量应大致等于p[i]*M，方案需要满足以下约束：

• M数值极大，单台主机内存无法存储全部M个任务与主机的映射关系（支持M可存储场景的解决方案也具备参考价值）
• N的取值最大可达10000
• 理想情况下单台主机存储的数值数量不超过O(M/N)
• AssignWorkToHost()函数的计算复杂度不超过O(N)
• 允许进行预处理操作
• 算法必须是确定性的，分布式集群内所有进程得到的工作-主机映射结果必须完全一致

方案一：前缀和二分查找方案（全场景适用） #

该方案无需存储全量映射关系，计算效率高，完全满足所有约束条件。

预处理步骤（所有节点执行相同逻辑，结果完全一致） #

1. 权重整数化：为避免浮点运算误差，将浮点权重放大为整数权重。选择满足精度要求的放大系数K（例如K=1e6，可根据实际精度需求调整），计算每个主机的整数权重w[i] = round(p[i] * K)，最后微调w[i]数值保证所有权重总和等于K。
2. 构造前缀和数组：生成长度为N+1的前缀和数组prefix_sum，其中prefix_sum[0] = 0，prefix_sum[i] = prefix_sum[i-1] + w[i-1]，数组仅需占用O(N)内存，远低于存储限制。

运行时代码实现 #

// 预处理生成的全局前缀和数组，所有集群节点生成的数组完全一致
std::vector<int64_t> g_prefix_sum;
// 权重总放大倍数，所有节点取值一致
int64_t g_total_weight;

int64_t AssignWorkToHost(const int64_t i_work) {
  int64_t offset = i_work % g_total_weight;
  // 二分查找第一个大于offset的前缀和位置，对应主机ID为位置减1
  auto it = std::upper_bound(g_prefix_sum.begin(), g_prefix_sum.end(), offset);
  return it - g_prefix_sum.begin() - 1;
}

方案优势 #

• 运行时计算复杂度仅为O(logN)，远低于要求的O(N)上限
• 存储消耗仅为O(N)，N最大为10000时仅需不到100KB内存，完全符合存储要求
• 算法完全确定性，相同输入下所有节点的映射结果完全一致
• 分配均匀性好，任务按循环顺序分配，不会出现单节点连续分配大量任务的情况

方案二：预生成周期映射表（适合M可存储场景） #

如果总任务量M的规模在内存可承载范围内，可以预生成完整周期的映射表，运行时直接查表获取结果。

预处理步骤 #

使用平滑加权轮询算法生成长度为g_total_weight的映射表cycle_map，其中cycle_map[k]表示偏移为k的任务对应的主机ID，所有节点生成的映射表完全一致。

运行时代码实现 #

// 预生成的周期映射表
std::vector<int64_t> g_cycle_map;
int64_t g_total_weight;

int64_t AssignWorkToHost(const int64_t i_work) {
  return g_cycle_map[i_work % g_total_weight];
}

方案优势 #

• 运行时复杂度为O(1)，性能达到最优
• 任务分配的平滑性最优，不会出现同一主机连续分配大量任务的情况

内容的提问来源于stack exchange，提问作者Serge Rogatch