date - 如何扩展基于日期的事件系统，例如在任何给定时间处理数百万个事件的 Google 日历

Question

我正在寻找架构或算法，通过这些架构或算法可以使用有效的模式来触发基于时间的事件。前的意思。当“Sun, 06 May 2012 23:54:11 +0300” 到达时，应该立即触发 n 个事件。（其中 N 可以介于 0 和 N 之间）。

问题不在于扩展交付的系统（无论是消息队列，还是 http get 或其他任何东西……），而是关于有效检测应该在给定时间触发的事件。或者更准确地说，我想我是在询问正确的数据结构以允许有效的 O(n) ？根据日期窗口轮询 n 个事件。

参考文献很有价值，谢谢。

Answer 1

堆可以让你保留一个项目的集合，在成本 O(log n) 的情况下执行以下操作： -- 插入任意项目 -- 弹出最小项目 如果我没记错的话，你可以在 O( 1）。

因此，我认为您应该将事件保存在堆中（按时间指定的顺序），并且： - 每当堆更改时，为最小（=下一个时间）项目的时间安排操作 - 对于复杂事件，使事件再次插入自身，与下一次调用的时间一致

这并不严格基于日期窗口，但我认为它可能对你更好。