いつでも何百万というイベントを扱うGoogleカレンダーなどの日付ベースのイベントシステムをスケールする方法

Question

時間に基づいてイベントをトリガするために効率的なスキーマを使用できるアーキテクチャまたはアルゴリズムを探しています。 exの意味。 「Sun、2012年5月6日23:54:11 +0300」が到着したとき、すぐにイベントが発射されるはずです。 （Nは0とNとの間にあり得る）。

配信されるシステム（メッセージキュー、http getなど）をスケーリングするのではなく、指定された時間にトリガーされるイベントを効率的に検出することについての質問です。または、より多くのperciseイベントになるためには、効率的なO（n）を可能にする適切なデータ構造について質問していると思いますか？日付ウィンドウに基づくn個のイベントのポーリング。

参照は、大きな価値があります。 ありがとうございました。

Answer 1

Aヒープを使用すると、コストのO（ログn）の時、次のアクションで、項目のコレクションを維持することができます： - 挿入任意の項目 - 最小限の項目 ポップそして、私は間違っていない場合は、覗き見することができますO（1）の最小項目で。

ヒープ（時間で指定された順序）でイベントを保持する必要があります： - ヒープが変更されたときに、最小（=次の時間）アイテムの時間にアクションをスケジュールする - 複雑なイベントの場合は、イベントを次回の呼び出し時に再び挿入します。

これは厳密には日付ウィンドウに基づいていませんが、それはあなたにとってさらに良いかもしれません。