c# - 非随机加权分布

Question

我目前有一个系统，其中服务器告诉所有客户端应用程序何时在服务器配置的时间窗口(比如客户端时间上午 12 点到早上 6 点)之间下次连接到服务器。

当前算法根据时间窗口中的秒数对客户端的 10 位 ID 号(公平分布)进行模数处理，并为每个客户端连接到服务器提供分布相当均匀且可预测的时间。现在的问题是，客户端不成比例地位于不同的时区，并且某些时区在给定窗口中重叠，因此最终结果是负载没有均匀分布在服务器上。我想要的是设计一种算法，我可以使用我们当前在每个时区拥有的客户端的百分比来配置它，并让它在窗口之间分配客户端的下一次连接时间，从而以某种方式在服务器上产生均匀的负载这是可预测的(非随机的)。

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

                            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) 的解决方案，重新连接时间将是确定性的直到您下次重新计算矩阵。然后每个人的重新连接时间都会稍微改变——但不会改变太多，除非矩阵发生显着变化。