非随机加权分布

Question

我目前有一个系统,服务器告诉所有客户端应用程序何时在服务器配置的时间窗口(比如客户端时间12到6点)之间连接到服务器.

当前算法按时间窗口中的秒数执行客户端的10位数ID(相当分布)的mod,并为每个客户端连接到服务器提供相当均匀分布的可预测时间.现在的问题是,客户端在不同的时区不成比例,并且某些时区对于给定的窗口重叠,因此净效应是负载不均匀地分布在服务器上.我想要的是设计一种算法,我可以使用我们当前为每个时区拥有的一定比例的客户端进行配置,并让它在窗口之间分配客户端的下一个连接时间,从而以一种方式在服务器上产生均匀负载这是可预测的(非随机的).

这是一个简单的图形表示:

                            12AM 1AM 2AM 3AM 4AM 5AM 6AM GMT
GMT -4  40% of the clients  ||||||||||||||||||||||||||||||            
GMT -5  10% of the clients       ||||||||||||||||||||||||||||||        
GMT -6  20% of the clients           ||||||||||||||||||||||||||||||    
GMT -7  30% of the clients               ||||||||||||||||||||||||||||||

Answer 1

将问题分为两部分:(1)确定您希望每组客户拥有的分布; (2)确定性地分配适合该分布的重新连接时间.

对于问题(1),考虑二维数字数组,非常类似于您绘制的图表:每行代表一个时区,每列代表一天中相等的时间段(可能是一小时).您必须解决的问题是用数字填充网格

• 每行的总数是该时区的客户端数量;
• 对于每一行,该时区重新连接窗口之外的所有数字都为零;
• 列的总和不超过某个预定的最大值(并且尽可能均匀地平衡).

这类问题有很多解决方案.您可以通过模拟找到一个而无需进行任何硬数学计算.编写一个填充网格的程序,以便每个时区的客户端均匀分布(即,您现在分发它们的方式),然后重复地将客户端从拥挤的时间水平移动到不那么拥挤的时间.

对于问题(2),您需要一个采用十位数ID和所需分布的函数(即上面问题1中矩阵的一行),并确定性地产生重新连接时间.这可以通过线性插值轻松完成.假设所需的分布是:

12:00    1:00   2:00   3:00   4:00   5:00   6:00 ...
  +------+------+------+------+------+------+----
  |    0 |    0 |  100 |   70 |   30 |    0 |   ...
  +------+------+------+------+------+------+----

首先找到整行的总和,然后将数字缩放到ID范围.也就是说,除以总和并乘以10 ¹⁰.

12:00    1:00   2:00        3:00       4:00        5:00   6:00 ...
  +------+------+-----------+-----------+-----------+------+----
  |    0 |   0  | 500000000 | 350000000 | 150000000 |    0 |   ...
  +------+------+-----------+-----------+-----------+------+----

现在让x =十位数ID,并从左到右读取行.在每个框中,从x中减去该框中的值.继续前进,直到框中的数字大于x中的数字.退货时间

(start time for this box) + (duration of this box) * x / (number in box)

请注意,一旦计算出问题(1)的解决方案,重新连接时间将是确定性的,直到下次重新计算矩阵为止.然后每个人的重新连接时间会稍微偏移 - 但不会太多,除非矩阵发生显着变化.