イベントストリームに関する分散述語計算

Question

私の質問は、実際には私の仕事を解決しようとしている問題に関する論文、記事、テキスト、書籍の要求です。

オブジェクトの属性を変更することができるイベントのストリームがある分散システム内の特定のオブジェクトに対して述語値（trueまたはfalse）を計算するプログラムに取り組んでいます。述語の値が変わると、プログラムはこの変更に関する通知を送信する必要があります。

例えば、Aという属性を持ち、オブジェクトのnameがPと等しい場合に述べるPredicate nameがあると考えるオブジェクトJhonがあると考えてください。 ストリーム内の各イベントには、タイムスタンプと属性名の値があります。そのため、次の一連のイベントを考慮してください。

e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 2 }
e3 = { name: Peter, timestamp: 3 }
e4 = { name: Doug, timestamp: 4 }
e5 = { name: Jhon, timestamp: 5 }

.

この問題の中で、イベントは合計注文関係を持っています：あなたが2つのイベントを持っているならば、あなたはいつもそれらの最も古いものであるかを常に言うことができます。

今、イベントは必ずしもそのタイムスタンプに従って正しい順序でストリームに表示されない。各イベントはそのタイムスタンプに固有のものであるため、同じオブジェクトに対して同じタイムスタンプを持つ2つ以上のイベントはありません。また、タイムスタンプは必ずしも1つずつ増加するシーケンスを形成するわけではありません。 すべてのイベントが受信されること、または受信されるときに保証はありません。それは私たちがストリームで見るイベントの存在について知っている問題の一部です。

実際のシナリオはさらに悪化しています。このイベントのストリームを並列処理する複数のコンピュータがあります。しかし、簡単にするために、私はこの例では1つのコンピュータだけを考慮してさらに行きます。

イベントが到着して上記の順序で処理された場合、送信された通知は次のようにする必要があります。

P(A) = true when e1 arrives
P(A) = false when e3 arrives
P(A) = true when e5 arrives.

.

それはタイムスタンプの順序を尊重するため、正しい通知のシーケンスです。 さて、コンピュータが次の順序でイベントを受信すると想像してください。

e1, e5, e2, e4, e3

.

イベントのタイムスタンプを考慮しないナイーブアルゴリズムは、誤った通知シーケンスを送信するでしょう：

P(A) = true when e1 arrives
P(A) = false when e4 arrives

.

通知が送信されるべきであるがそうでなかったときに作業しているアルゴリズムはタイムスタンプと害を考慮しています。そのため、e1が到着すると、1の通知e3が送信されていないことがわかります。 これは、この問題についての読み物を知らないが、ホイールを再発明するような少し感じます。 私はこの問題への言及や似たようなものへの言及をお願いします。このような問題を扱っています。

本当の問題は、コンピュータの処理の間の共有状態として機能する述語 $ \ quentes $ オブジェクト状態を格納することを含むため、非常に複雑です。ストリームと私は毎秒到着した数千のイベントについて話していますので、すべてのイベントをいくつかのデータベースに保存することはできません。

私が説明した問題についての文学はありますか？もしそうなら、あなたは私にそれへのリンクを与えてもらえますか？

この問題を解決するアルゴリズムを説明する紙やテキストを見たいと思います。そのような紙がアルゴリズム（例えば正当性）についての証明を提供する場合はさらに良くなるでしょう。

そのような紙が存在しない場合（私は実際にそれがそうであると思います）、アルゴリズムを説明し、その正当性についての引数または証明を提供する答えを受け入れます。

このアルゴリズムが正しいとなるため、イベントが到着した順序に関係なく、常に正しい通知のシーケンスを送信する必要があります。 そして、このアルゴリズムは、メモリ内で保存するため、またはDBに格納するイベントが多すぎるため、受信したイベントをすべてのメモリに保存しないでください。 いくつかのイベントをメモリに保つことは合理的であり、好ましくは一定量です。

Answer 1

不可能な結果＃1：ドロップされたイベント

一般的に解決できない。一部のイベントがドロップされている場合（すなわち、受信していない場合）という要件が満たされることを保証する方法はありません。最初にこのストリームを考慮してください：

e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 4 }

.

ここでは、両方のイベントを見る場所。次に、このストリームを検討してください。

e1' = { name: Jhon, timestamp: 1 }
e2' = { name: Pete, timestamp: 2 }
e3' = { name: Jhon, timestamp: 3 }
e4' = { name: Jhon, timestamp: 4 }

.

アルゴリズムがEvents e1'、e4'のみを見ている場合（他のイベントは失われて受信されません）。どちらの場合も見ているアルゴリズムが同じであることに気付くかもしれません。そのため、出力は両方の場合において同じになります。しかし、正しい答えはこれら2つのケースで異なりますので、常に正しい出力を生成するアルゴリズムの希望はありません。 （最初のケースでの正しい応答は通知を生成することです。2番目のケースでの正しい応答は、e2'を受信した後に述語がfalseであることを示すもので、受信後に述語がtrueであることを示すために、2つの通知を生成することです。 e3'）

この状況に対処するために要件を適用する方法は明らかではありません。私が見ることができる唯一の唯一の解決策は、送信されたイベントではなく、受信したイベントだけではないと言えることです。これは、イベントを削除できないことを指定することと同じです。

不可能な結果＃2：並べ替えイベント

すべてのイベントをメモリに保存せずに、そして任意の並べ替えを行わずに、あなたが並べ替えられたイベントを処理できるようにする必要があることを示します。しかしながら、これらの要求は互換性がない。それは達成することは不可能である。奇妙なタイムスタンプを持つイベントが到着した場合は、イベントの長い順序の終わりに、タイムスタンプの長い一連のイベントを検討します。正しく処理するのは、過去のイベント（またはオブジェクトの過去の状態）の履歴全体を保存することです。

だから、あなたは同様に並べ替えについての要件をリラックスさせる必要があります。おそらくあなたはすべてのイベントを永遠にメモリに保存しても構わないと思っています。 （もしそうなら、あなたは解決策を持っています。）あなたが並べ替えに縛られて、例えば10分以上遅れることはありません。 （もしそうなら、過去10分間の履歴を保存するだけで、年上のすべてのものは削除することができます。）おそらく他のものはあなたの特定の状況でより意味があります。

しかし、選択肢ではないものは、質問に記載されているすべての強い要件を課すことであり、常に正しいアルゴリズムを必要とすることです。

---

これに関する文学を知りません、そして私は特にそこにあることを期待する理由は特に見られません。それは非常に具体的な要件のセットです、そしてそれは結果として生じるタスクが些細なものであるか不可能なものであるように見えます。それらは通常、文献で研究される傾向があるような問題ではありません。おそらく永続データ構造に興味があるかもしれません。あなたがやりたいと言ったイベントの歴史。そして、あなたの特定の状況でそれをするために派手なデータ構造を必要としません。