平滑峰值使用率的算法？

Question

我有一个环境，需要在深夜接收和发送许多设备的数据，这些设备分布在三个时区中。这些设备的分布是通过基于身份号码和简单计算使用模运算伪随机确定的。这种计算的结果会产生一个不必要的人工高峰，在夜间特定时间消耗了比我想要的更多的资源。

作为我们协议的一部分，我可以指示设备何时在随后的晚上连接到我们的系统。

我正在寻求一种算法，可以将峰值分布到更平稳的线路中（尽管大多数时间可能会更高），或者至少向正确的方向推进 - 这意味着我应该花费时间阅读哪种术语。 我可以使用设备的身份号码、当前时间和设备的时区作为计算输入。我还可以执行一些提前分析计算，以创建可供选择的插槽池，虽然我觉得这种方法可能不如我希望的那样优雅（尽管学习算法也许不是件坏事…）。

（最终并且有些不相关的是，我将使用C#实现此算法。）

- cfeduke

---

我觉得问题的解释不是很清楚。我们要分发什么？一个（或多或少）随机的分布怎么会导致一个显著的峰值？如果分布改为简单的轮流分配，会发生什么？ - djna

高峰是由于时区和模运算人为创建的。 - cfeduke

Answer 1

如果您想避免使用随机时间带来的波动，请查看用于哈希表的各种哈希函数。您可以从维基百科上有关该主题的文章开始阅读:

http://en.wikipedia.org/wiki/Hash_function

基本上，将您想要更新窗口大小的时间分成适当数量的存储桶（buckets）。一个选择可能是将3小时* 60分钟* 60秒 = 10800个存储桶作为所选哈希函数的哈希表大小。然后使用您的设备ID作为唯一输入。别忘了使用格林威治标准时间(GMT)。您选择的编程语言可能具有许多内置的哈希函数，但如果您想从头开始实现一个哈希函数，该文章应该会提供一些链接，以帮助您入门。

相比于随机函数可能会有波动，此方法优于先前的随机访问时间，因为它具有更好的均匀性，并且确保您的访问模式大致平稳。

以下是有关如何实现各种函数的更具体信息:

http://www.partow.net/programming/hashfunctions/index.html

- Paul McMillan

Answer 2

你说你可以告诉设备何时连接，所以我不明白为什么需要任何随机或模数化的东西。当每个设备连接时，选择明天当前没有分配给许多设备的时间，并将该设备分配到该时间。如果所有设备的服务资源需求大致相同，则简单的贪心算法将产生完全平滑的分布-将每个设备分配到当前拥挤程度最小的时间。如果服务器处理的不仅仅是这些设备，那么你需要从其典型的负载配置开始，然后将设备负载添加到其中。我不会真的称这为“分析计算”，只是存储未来24小时内预期负载与时间的直方图。

或者您是否面临设备可能不遵守指令的问题（例如，它可能在分配的时间内处于离线状态，然后在下一次连接时再连接）？显然，如果您的用户在特定时区的早晨同时开始工作，那将是一种有问题的策略。

- Steve Jessop

---

这个问题的困难在于它有一个反馈环节。如果在第一晚发现凌晨2点是最不忙的时间，它会将资源分配到凌晨2点。如果第一晚偶然分配流量，那么凌晨2点将成为最繁忙的时间，因此它会安排其他所有任务避开凌晨2点，导致凌晨2点周围的时间浪费和效率低下。除非能够获得稳定的偶然流量分布，否则区间内的均匀分配始终是最优的。 - groundhog

如果当前凌晨1点是最繁忙的时间（比如说，有150万次点击），而2点是最不繁忙的时间（比如说，只有50万次点击），那么我的建议是指示其中的50万个1点访问者在未来改为在2点访问。我认为这没有任何反馈循环：只需保持一个包含整数的桶数组，“明天这个时间段有多少次点击计划”，并均匀地填充这些桶。除非您使用了错误的算法“明天这个时间段有多少次点击计划，不包括我已经从其他时间移动过来的”，否则不会出现过度补偿。所以不要这样做。 - Steve Jessop

Answer 3

只需要将设备数量除以n个等分时间间隔，并将每个时间段分配给一个设备，在下次连接时告知它们何时连接。这将在所有情况下都给您一个最优的均匀分布。

将所有时间标准化为GMT，不要关心时区或夏令时或其他什么。现在是现在，无论你在哪个时区。

添加随机分布可能导致聚集（统一的随机分布仅在极限情况下是统一的，但对于任何特定样本来说不一定），而且如果没有反馈机制，真的应该使用。由于您可以在某种程度上控制它们何时连接，因此随机组件根本不必要，甚至远非最佳。

如果您担心设备之间的时钟漂移，请考虑即使添加了随机性，这也不会以任何方式降低时钟漂移的随机性，而只会导致更少的优化分配。

如果您想确保按地区稳定分配设备，则计算每个地区的设备比例，并适当分配时间段。例如，如果您按时区50/25/25分配设备，则将第一个时区分配时间段，然后将其余时区的下两个时间段分配给其余时间区，然后重复。

- groundhog