algorithm - 百分比负载平衡线程请求

Question

我有一个工作线程池，我在其中根据百分比向它们发送请求。例如，worker 1 必须处理总请求的 60%，worker 2 必须处理总请求的 31%，最后 worker 3 处理 9%。我需要从数学上知道如何按比例缩小数字并保持比率，这样我就不必向线程 1 发送 60 个请求，然后开始向工作人员 2 发送请求。这听起来像是一种“线性比例”数学方法。无论如何，感谢所有关于此问题的意见

Answer 1

考虑此问题的一种方法使其与在基于像素的显示器上绘制斜线的问题非常相似，这可以用 Bresenham's algorithm 完成。 .

首先，为简单起见，我们假设只有 2 个工作人员，他们应该从传入请求中获取分数 p(对于工作人员 1)和 (1-p)(对于工作人员 2)。想象一下，“发送给工作人员 1 的请求”是横轴，“发送给工作人员 2 的请求”是图表的纵轴:我们要做的是在该图中绘制一条(像素化)线，从 (0, 0) 并且具有斜率 (1-p)/p(即它向右前进每 p 个单位向上前进 (1-p) 个单位)。当一个新的请求进来时，一个新的像素被绘制出来。这个新像素将始终紧邻前一个像素的右侧(如果我们将工作分配给 worker 1)或紧靠其上方(如果我们将其分配给 worker 2)，因此它不太像 Bresenham 的算法，其中对角线移动是可能，但有相似之处。

随着每个新请求的到来，我们必须将该请求分配给其中一个工作人员，对应于从前一个像素向右或向上绘制下一个像素。我建议选择正确方向的一个好方法是选择最小化误差函数的方向。最简单的方法是取 (0, 0) 和2 个可能选择中的每一个都会产生的点，并将这些斜率与理想斜率 (1-p)/p 进行比较；然后选择产生最低差异的那个。这将使绘制的像素尽可能地“跟踪”理想线。

要将其推广到超过 2 个维度( worker )，我们不能直接使用斜率。如果有 W 个 worker，我们需要想出一些函数 error(X, Y)，其中 X 和 Y 都是 W 维向量，一个代表理想的方向(请求与分配，类似于前面的斜率 (1-p)/p)，另一个代表候选点，并返回一些数字来表示它们的方向有多么不同。幸运的是，这很容易:我们可以通过将 dot product 除以两个向量之间的角度来获取余弦值通过它们的大小的乘积，这很容易计算。如果他们的方向相同，这将为 1，否则小于 1，因此当新请求到达时，我们需要做的就是对每个 worker 1 <= i <= W 执行此计算并查看哪个错误(X , Y[i]) 最接近 1:这是向其发出请求的工作人员。

[编辑]

这个程序也会适应理想方向的变化。但就目前而言，它会尝试(尽其所能)使到目前为止分配的每个请求的总体比率跟踪理想方向，因此如果该过程已经运行了很长时间，那么即使目标方向的微小调整可能会导致较大的“摆动”以进行补偿。在那种情况下，当调用 error(X, Y[i]) 时，最好使用最新像素(请求分配)与某个数字 k(例如 k=100)步骤中的像素之间的差异来计算第二个参数前。 (在原始算法中，我们隐式地减去起点 (0, 0)，即 k 尽可能大。)这只需要您保留最后 k 个选择的端点。选择太大的 k 意味着你仍然可以获得较大的波动，而选择太小的 k 可能意味着“线”漂移得很好，一些 worker 根本没有选择，因为每个分配都会彻底改变方向。您可能需要进行试验才能找到合适的 k。