複数のプロデューサキーからのフェアデキューによるキュー

Question

私は何千ものソースからイベントを受け取っているこのシナリオを持っています。各ソースは、現在のステータスに関する情報を送信しています。すべてのイベントを処理したいのですが、各ソースの最新のイベントを最初に処理して、現在のビューが最新であることが重要です。だから私はConcurrentHashMapをキーとして各ソースの識別子と値としてLIFOキュー（スタック）を使用することを考えていました。その後、Mapのキーを繰り返して、各ソースのスタックから1つのアイテムをポップします。

私は、キーを繰り返し処理しながら各キーのキューから項目を取り除いている間に、プロデューサがキューに新しいイベントをポストして、並行処理の問題を引き起こす可能性があると懸念しています。プロデューサは、新しいキーをマップに追加することもでき、MapのentrySetを反復することは、弱く一貫しているようです。新しいアイテムは後続の反復で処理されるため、これは大きな問題ではありません。理想的には、entrySetのストリームでいくつかの並列処理を使用して処理を高速化することもできます。

これに対してよりクリーンなアプローチがあるのだろうかと思います。現実には私はLIFO BlockingDequeueを使い、最新の出来事を最初に処理することができましたが、このアプローチの問題は、あるソースが他のソースよりも多くのイベントを送る可能性があり、

この種の動作を提供する他のデータ構造はありますか？基本的に私が探しているのは、各ソースからのイベントに優先順位を付けると同時に、各ソースに消費者が処理する公平な機会を与える方法です。

Answer 1

LIFOキューのFIFOキューについて考えましたか？各ソースはLIFOキューに追加され、処理のためにFIFOキューから最初のLIFOキューを取り出し、1つのイベントを処理してFIFOキューに戻します。この方法では、LIFOキューが単にFIFOキューに追加されるため、新しいソースにも問題はありません。

イベントを正しいLIFOキューに追加するには、ソースごとにキューを認識する追加のHashMapを維持することができます。また、まだマップにない新しいソースが発生した場合は、LIFOキューをFIFOキュー。

Answer 2

これを管理する独自の構造を構築して、特にユースケースの柔軟性（速度）を高めることを推奨します。

私は循環キューを使って各LIFOキュー（スタック）を格納します。循環キューは、要素を末尾に追加し、先頭から読み取る（ただし削除しません）キューです。一度head = tailとすると、最初からやり直します。

単純な配列を使用して独自のキューを構築できます。配列にキューを追加したり、必要に応じてキューを拡張したりするなど、操作に関する同期を管理するのはそれほど難しくありません。私は配列にキューを追加することはあなたが非常に頻繁に行うことではないと思います。

これは管理が簡単で、循環キューを拡張してエントリのアクセス頻度を計算し、エントリへのアクセス頻度を抑えることができます（コンシューマスレッドを追加/削除するか、エントリによって管理されるスタックから消費する前に）。

複数のスレッドを使用して循環待ち行列から要素を読み込むときに、スタックから消費する前に「レジスタ」操作を呼び出すことでスレッドロックを回避することもできます。各スレッドはIDを持ち、指定されたキューエントリに格納されます。登録する前とスタックからポップする前に、スレッドは「登録IDの読み取り」操作を行い、返されるIDはそれ自身のIDと一致しなければなりません。つまり、指定されたキューエントリを「所有している」スレッドだけがそのスタックからポップできます。登録プロセスの登録/確認が失敗した場合は、別のスレッドがそのエントリを消費していることを意味します。したがって、現在のスレッドは次に使用可能なエントリに移動します。

私は過去にこの種の戦略を使用していましたが、それは魅力的なスケールでした。私はこれがあなたにとって理にかなっていることを望みます。