非随机加权分配

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），重新连接时间将是确定性的直到下次重新计算矩阵时间。然后每个人的重新连接时间会稍稍变化 - 但不会太大，除非矩阵变化很大。

Answer 2

这个怎么样简单的东西：

• 如果服务器上的负载是确定的，向客户端发送相同的秒数你上次发送。

• 如果服务器上的负载过高，请在时间窗口中向客户端发送一些其他随机数。

几天后，事情应该自行解决。

（这里假设你有测量你试图优化，这似乎不太合理数量的某种方式。）

Answer 3

为什么不能在服务器上生成在格林尼治标准时间的重新连接，窗口时间和转换在您将时间发送到客户端之前将客户端当地时间发送给客户

Answer 4

除了ID以外，还可以考虑用户的时区。

有24个时区：使用这将是以下

一个例子的解决方案。计算每个时区的相对负载。您可以通过从静态数据中总结每个时区的客户端总数来完成此操作。现在你有“加权时区”。每个时区将获得与其权重成比例的时间份额。

例如，如果您有以下数据（为简单起见，让我们假设只有三个时区）：

Time Zone | Clients num 
------------------------ 
    0  |  20 
    1  |  30 
    2  |  10 

那么你会分配时间间隔大小的60，并给每个其时间份额：第一个时区将得到（20/60 *＃时间），第二个将得到以下（30/60 *＃时间）等。

一旦你有较小的时间段，您可以根据您之前的功能（例如，mod）告诉每个客户其时间，根据您计算的特定时区的更小间隔。

注：

1. 很显然，你需要的时区是在交通非常低一些的最低客户NUM值，但是这很简单 - 你只需编辑原始表。
2. 这是“时间分割”的一个例子，您可以根据需要修改此示例，例如，您可以为多个时区分配相互时间范围。

编辑：

给你添加到你的问题的例子，你可以应用此方法通过以下方式：

如果我理解正确的话，你有10小时，你的服务器是活动，并且您希望每个小时的负载大致相等。含义：在每个小时中，您希望10％的客户端可以访问服务器。 使用上面解释的思想，可以非一致地划分用户，以便对于每个时区，有“更多概率”的小时数，“更少概率”的小时数。在您的示例中，在GMT-4组中，10％/ 40％的客户端将在第一个小时内访问服务器：12 AM-01AM GMT。可以计算每个时区的负载，以便每小时服务器的总负载为10％。有很多方法可以做到这一点 - 一个贪婪的人会做。 一旦你有了这个，你就知道每个时区的权重，而且应该更清楚如何使用上述的时间共享方法。

Answer 5

我将定义一个辅助类为每个你正在寻找的时区的：

class Timezone 
{ 
    DateTime start; 
    int hourlyWeights[6]; //assuming you have 6 hour long timeslot for every timezone 

    DateTime GetStartTime(long clientId) 
    { 
    long allTicks = 3600*sum(hourlyWeights); 
    long clientTicks = clientId%allTicks; 
    int i = 0; 
    while(clientTicks>hourlyWeights[i]) 
    { 
     clientTicks -= hourlyWeights[i]*3600; 
     i++; 
    } 
    long seconds = clientTicks/hourlyWeights[i]; 
    return start.AddHours(i).AddSeconds(seconds); 
    } 
} 

您现在使用的方法GetStartTime得到的开始时间从该时区的客户端。这里的想法是，我们有这个hourlyWeights表，其中包含您想要在给定时区获得的分布，例如[40，20，0，0，0，0]意味着这些客户只能在头两个小时内提供服务，而且我们希望在第一个小时内客户数量增加一倍。注意：我假设ID从给定时区的客户端均匀分布。

棘手的一点是要创建这些类。如果客户的结构相当稳定，则可以手动计算分布并将其放入配置文件中。如果它经常变化，让我知道，我会张贴一些代码动态地弄清楚。