负载平衡线程请求百分比 [英] Percentage load balance thread requests

问题描述

我有一个工作线程池，我根据百分比在其中发送请求.例如，工作人员1必须处理总请求的60％，工作人员2必须处理总请求的31％，最后工作人员3必须处理9％.我需要数学上知道如何缩小数字并保持比例，因此我不必向线程1发送60个请求，然后再开始向工作者2发送请求.这听起来像是线性比例"数学方法.无论如何，我们都会感谢您对此问题的所有投入

I have a pool of worker threads in which I send request to them based on percentage. For example, worker 1 must process 60% of total requests, worker 2 must process 31% of total requests and lastly worker 3 processes 9%. I need to know mathematically how to scale down the numbers and maintain ratio so I don't have to send 60 requests to thread 1 and then start sending requests to worker 2. It sounds like a "Linear Scale" math approach. In any case, all inputs on this issue are appreciated

推荐答案

考虑此问题的一种方法使其与在基于像素的显示器上绘制倾斜线的问题非常相似，可以使用布雷森纳姆算法.

One way to think about this problem makes it quite similar to the problem of drawing a sloped line on a pixel-based display, which can be done with Bresenham's algorithm.

为简单起见，首先让我们假设只有2个工作程序，并且它们应该占传入请求的小数p(对于工作程序1)和(1-p)(对于工作程序2).想象一下，发送给工作人员1的请求"是图的水平轴，发送给工作人员2的请求"是图的垂直轴:我们要做的是在该图中绘制一条从(0， 0)并且具有斜率(1-p)/p(即，向右前进的每p单位，向上推动(1-p)个单位).当有新请求出现时，将绘制一个新像素.这个新像素将始终位于前一个像素的右侧(如果我们将作业分配给工人1)或紧邻它的上方(如果我们将其分配给工人2)，因此它与Bresenham的算法不同(对角线移动是可能，但是有相似之处.

First let's assume for simplicity that there are only 2 workers, and that they should take a fraction p (for worker 1) and (1-p) (for worker 2) of the incoming requests. Imagine that "Requests sent to worker 1" is the horizontal axis and "Requests sent to worker 2" is the vertical axis of a graph: what we want to do is draw a (pixelated) line in this graph that starts at (0, 0) and has slope (1-p)/p (i.e. it advances (1-p) units upwards for every p units it advances rightwards). When a new request comes in, a new pixel gets drawn. This new pixel will always be either immediately to the right of the previous pixel (if we assign the job to worker 1) or immediately above it (if we assign it to worker 2), so it's not quite like Bresenham's algorithm where diagonal movements are possible, but there are similarities.

随着每个新请求的到来，我们必须将该请求分配给其中一个工作程序，这与从上一个像素向右或向上绘制下一个像素相对应.我建议，选择正确方向的一种好方法是选择一个使误差函数最小的方法.最简单的方法是采用(0，0)与(0，0)之间的直线的斜率.由这两种可能的选择中的每一种得出的点，并将这些斜率与理想斜率(1-p)/p进行比较；然后选择差异最小的那个.这将导致绘制的像素尽可能接近跟踪"理想线.

With each new request that comes in, we have to assign that request to one of the workers, corresponding to drawing the next pixel rightwards or upwards from the previous one. I propose that a good way to pick the right direction is to pick the one that minimises an error function. The easiest thing to do is to take the slope of the line between (0, 0) and the point that would result from each of the 2 possible choices, and compare these slopes to the ideal slope (1-p)/p; then pick whichever one produces the lowest difference. This will cause the drawn pixels to "track" the ideal line as closely as possible.

要将其推广到2个以上的维度(工作人员)，我们不能直接使用斜率.如果有W工人，我们需要提出一些函数错误(X，Y)，其中X和Y都是W维向量，一个代表理想的方向(请求与类似于前面的斜率(1-p)/p分配)，另一个代表候选点，并返回代表其方向有多不同的一些数字.幸运的是，这很容易:我们可以通过除以两个矢量之间的角度的余弦来将它们的

To generalise this to more than 2 dimensions (workers), we can't use slope directly. If there are W workers, we need to come up with some function error(X, Y), where X and Y are both W-dimensional vectors, one representing the ideal direction (the ratios of requests to assign, analogous to the slope (1-p)/p earlier), the other representing the candidate point, and returning some number representing how different their directions are. Fortunately this is easy: we can take the cosine of the angle between two vectors by dividing their dot product by the product of their magnitudes, which is easy to calculate. This will be 1 if their directions are identical, and less than 1 otherwise, so when a new request arrives, all we need to do is perform this calculation for each of worker 1 <= i <= W and see which one's error(X, Y[i]) is closest to 1: that's the worker to give the request to.

此过程还将适应理想方向的变化.但实际上，它试图(尽力)使到目前为止分配的每个请求的总比率跟踪理想方向，因此，如果该过程已经运行了很长时间，那么即使在目标方向上进行小的调整可能会导致较大的摆动"以进行补偿.在这种情况下，调用error(X，Y [i])时，最好使用最新像素(请求分配)和某个像素k(例如k = 100)步的像素之间的差来计算第二个参数.前. (在原始算法中，我们隐式减去起点(0，0)，即k尽可能大.)这仅要求您保留最后选择的k个端点.将k选得太大将意味着您仍然可以得到较大的摆动，而将k选得太小则可能意味着直线"偏离了正常路线，有些工人根本没有选，因为每个作业都极大地改变了方向.您可能需要尝试找到一个合适的k.

This procedure will also adapt to changes in the ideal direction. But as it stands, it tries (as hard as it can) to make the overall ratios of every request assigned so far track the ideal direction, so if the procedure has been running a long time, then even a small adjustment in the target direction could result in large "swings" to compensate. In that case, when calling error(X, Y[i]), it might be better to compute the second argument using the difference between the latest pixel (request assignment) and the pixel from some number k (e.g. k=100) steps ago. (In the original algorithm, we are implicitly subtracting the starting point (0, 0), i.e. k is as large as possible.) This only requires you to keep the last k chosen endpoints. Picking k too large will mean you can still get large swings, while picking k too small might mean that the "line" drifts well off-course, with some workers never picked at all, because each assignment alters the direction so drastically. You might need to experiment to find a good k.

这篇关于负载平衡线程请求百分比的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！