algorithm - 考虑到 lastupdate，对动态集的部分进行装箱

Question

有大量对象。集合是动态的:对象可以随时添加或删除。我们称对象总数为 N。

每个对象都有两个属性:上次更新的质量 (M) 和时间 (T)。

每隔 X 分钟，应从中选择一小批进行处理，这会将它们的 T 更新为当前时间。批处理中所有对象的总 M 是有限的:不超过 L。

我希望在这里解决三个任务:

1. 找到下一批对象拾取算法；
2. 介绍对象类别:简单、优先级(至少适合每个第 n 批处理)和频繁(适合每个批处理);
3. 预测系统容量耗尽(添加下一个服务器的时间 = 增加 L)。

哪种模型最能描述这样的系统？

整个事情是关于按时间间隔处理“对象”的服务。每个对象应该每 N 小时“测量”一次。 N 可以在一定范围内变化。 X 是固定的。

对象是由人类添加/删除的。 N 呈指数增长，速度相当缓慢，其中一些峰值是由出版物引起的。当然预测不可能准确，只是一些估计。 M从0到1E7呈指数分布变化，大部分接近0。

我看到这里可以有几种策略:

A. 全力以赴 - 将每批包装尽可能接近 100%。随着 N 的增长，特定对象被击中的平均间隔也会增长。

B. 平均气质 :) - 尝试将平均间隔保持在某个值附近。批处理填充水平将从某个低水平增长。当它接近 100% 时 – 是时候获得更多服务器了。

C. - ?

Answer 1

这是针对您的问题的一个非常完整的设计。

您的问题与您对系统的描述不符。所以我假设描述是准确的。

当您安排测量时，您应该通过一个对象，第一次可以测量它，以及您希望测量发生的时间。该对象应该有一个 weight 属性和一个 measured 方法。当测量发生时，将调用 measured 方法，您的类之间的区别在于它们是否以及使用什么参数重新安排自己。

在内部，您将需要几个优先级队列。参见 http://en.wikipedia.org/wiki/Heap_(data_structure)有关如何实现的详细信息。

第一个队列是测量可以发生的时间，所有还不能测量的对象。每次安排批处理时，您都将使用它来查找可能发生的所有新测量。

第二个队列是现在准备进行的测量，并按它们应该发生的调度周期和权重进行组织。我会让他们都提升。您可以通过从队列中拉出项目来安排一批，直到您有足够的东西发送。

现在您需要知道每批要放多少。鉴于您所描述的系统，可以手动输入事件尖峰，但随着时间的推移，您希望这些尖峰逐渐消失。所以我推荐选项B，平均气质。因此，要做到这一点，当您将每个对象放入“现在就绪”队列时，您可以计算它的“平均工作重量”，即它的重量除以它应该发生之前的周期数。将其与对象一起存储，并保持您应该达到的运行速率的运行总计。每个时期我都建议您继续添加到批处理中，直到满足三个条件之一:

1. 你的对象用完了。
2. 您达到了最大批处理能力。
3. 您的总重量超过了平均工作重量的 1.1 倍。额外的 10% 是因为现在使用更多的容量比以后用完容量要好。

最后，容量规划。

为此，您需要使用一些启发式方法。这是一个合理的，可能需要对您的系统进行一些调整。维护您过去 10 次平均工作重量总计测量值的数组。保持“高水位线的指数衰减平均值”。通过根据公式每次更新来做到这一点:

average_high_water_mark = 0.95 * average_high_water_mark + 0.5 * max(最后 10 次运行的工作权重)

如果 average_high_water_mark 达到最大容量的 2 个服务器，则添加更多服务器。 (这个想法是服务器应该能够死掉而不会让你被淹死。)