0

次の事実を考慮して、クラスター環境でイベントの再現可能な順序付けを可能にするアルゴリズムを実装する既存のオープンソース Java API (おそらく、より優れた製品の一部として) はありますか?

1) There are N sources of events, each with a unique ID.
2) Each event produced has an ID/timestamp, which, together with
   its source ID, makes it uniquely identifiable.
3) The ids can be used to sort the events.
4) There are M application servers receiving those events.
   M is normally 3.
5) The events can arrive at any one or more of the application
   servers, in no specific order.
6) The events are processed in batches.
7) The servers have to agree for each batch on the list of events
   to process.
8) The event each have earliest and latest batch ID in which they
   must be processed.
9) They must not be processed earlier, and are "failed" if they
   cannot be processed before the deadline.
10) The batches are based on the real clock time. For example,
    one batch per second.
11) The events of a batch are processed when 2 of the 3 servers
    agree on the list of events to process for that batch (quorum).
12) The "third" server then has to wait until it possesses all the
    required events before it can process that batch too.
13) Once an event was processed or failed, the source has to be
    informed.
14) [EDIT] Events from one source must be processed (or failed) in
    the order of their ID/timestamp, but there is no causality
    between different sources.

あまり形式的ではありませんが、イベントを受信するサーバーがあります。それらは同じ初期状態から始まり、どのイベントをどの順序で処理するかについて合意することで同期を保つ必要があります。幸いなことに、イベントはできるだけ早く処理するのではなく、「少しずつ」処理する必要があるため、締め切り前にサーバーに同意してもらう時間があります。しかし、それが実際にアルゴリズムに実際の違いをもたらすかどうかはわかりません. また、すべてのサーバーがすべてのバッチに同意する場合、それらは常に同期されるため、照会時に一貫したビューが表示されます。

私は Java API に最も満足していますが、Java から呼び出すことができれば別のものを受け入れます。また、オープンソース API がなくても明確なアルゴリズムがある場合は、それを答えとして自分で実装しようとします。

4

2 に答える 2

0

これまでのところ、明確な答えは得られていませんが、興味のある人は、私が見つけたものを見るのに役立つと思います.

以下に、この主題に関連するいくつかの理論的な議論を示します。

イベントの一貫した順序付けのための動的ベクトル クロック

競合のないレプリケートされたデータ型

「バッチ」を同期するために使用できる複数の同時プロセスを互いに待機させる1つの方法は、分散バリアです。1 つの Java 実装はHazelcastの上で利用できるようで、別の Java 実装はZooKeeperを使用しています

私が見つけたより簡単な方法の 1 つは、DB を使用することです。すべてのプロセスは、受け取ったすべてのイベントを DB に挿入します。DB の設計によっては、たとえば VoltDB のように、これを完全に並行してロックフリーにすることができます。次に、1 秒間隔で、次のバッチで処理するイベントを選択してマークする「cron ジョブ」が実行されます。ジョブはすべてのサーバーで実行できます。1 つのバッチのジョブを最初に実行すると、一連のイベントが修正されるため、他のバッチは最初のバッチが定義したリストを使用できるようになります。このように、すべてのサーバーですべてのバッチに同じイベント セットが含まれていることが保証されます。また、バッチ全体で完全な順序を使用でき、cron ジョブ自体が指定できる場合は、サーバーの状態が同期されます。

于 2012-06-03T09:56:22.267 に答える