Verteilte Prädikatberechnung im Ereignisstrom

Question

Meine Frage ist eigentlich eine Anfrage nach Aufsätzen, Artikeln, Texten oder Büchern zu dem Problem, das ich mit meiner Arbeit zu lösen versuche.

Ich arbeite an einem Programm, das einen Prädikatswert (wahr oder falsch) für ein bestimmtes Objekt in einem verteilten System berechnet, in dem es einen Strom von Ereignissen gibt, die die Attribute des Objekts und folglich den Prädikatswert ändern können.Immer wenn sich der Prädikatwert ändert, muss das Programm eine Benachrichtigung über diese Änderung senden.

Stellen Sie sich zum Beispiel vor, dass es ein Objekt gibt A welches ein Attribut namens hat name und bedenken Sie, dass es ein Prädikat gibt P was wahr ist, wenn das Objekt name ist gleich Jhon.Jedes Ereignis im Stream verfügt über einen Zeitstempel und einen Wert für den Attributnamen.Betrachten Sie also die folgende Abfolge von Ereignissen:

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 }

In diesem Problem haben die Ereignisse eine totale Ordnungsbeziehung:Wenn Sie zwei Ereignisse haben, können Sie immer sagen, welches davon das älteste ist.

Nun werden die Ereignisse im Stream nicht unbedingt in der richtigen Reihenfolge entsprechend ihrem Zeitstempel angezeigt.Jedes Ereignis ist hinsichtlich seines Zeitstempels eindeutig, sodass es nicht zwei oder mehr Ereignisse mit demselben Zeitstempel für dasselbe Objekt gibt.Außerdem bilden die Zeitstempel nicht unbedingt eine Reihenfolge, die sich immer um eins erhöht:wenn wir sehen e1 mit Zeitstempel 1 Und e3 mit Zeitstempel 3, es impliziert nicht die Existenz von e2 mit Zeitstempel 2.Es gibt keine Garantie dafür, dass alle Ereignisse empfangen werden oder wann sie empfangen werden.Ein Teil des Problems besteht darin, dass wir nur über die Existenz der Ereignisse Bescheid wissen, die wir im Stream sehen.

Das reale Szenario ist noch schlimmer:Es gibt mehrere Computer, die diesen Ereignisstrom parallel verarbeiten.Der Einfachheit halber gehe ich in diesem Beispiel jedoch weiter und berücksichtige nur einen Computer.

Wenn die Ereignisse in der oben beschriebenen Reihenfolge eintreffen und verarbeitet werden, sollten die gesendeten Benachrichtigungen wie folgt lauten:

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

Das ist die richtige Reihenfolge der Benachrichtigungen, da die Zeitstempelreihenfolge berücksichtigt wird.Stellen Sie sich nun vor, dass der Computer die Ereignisse in der folgenden Reihenfolge empfängt:

e1, e5, e2, e4, e3

Ein naiver Algorithmus, der den Zeitstempel des Ereignisses nicht berücksichtigt, würde eine falsche Reihenfolge von Benachrichtigungen senden:

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

Der Algorithmus, an dem ich arbeite, berücksichtigt die Zeitstempel und leitet daraus ab, wann eine Benachrichtigung hätte gesendet werden sollen, dies aber nicht der Fall war.Also wann e3 Eintreffend wird es bemerken, dass die Benachrichtigung P(A) = true für e5 wurde nicht gesendet.Das fühlt sich ein bisschen so an, als würde man das Rad neu erfinden, obwohl mir keine Lektüre zu diesem Problem bekannt ist.Ich hätte gerne Hinweise auf dieses Problem oder auf etwas Ähnliches, etwa einige Aufsätze, die sich mit dieser Art von Problem befassen.

Das eigentliche Problem ist wesentlich komplexer, da es die Speicherung des Prädikats betrifft $ imes$ Objektstatus in einer Datenbank, die als gemeinsamer Status zwischen den Computern fungiert, die den Stream verarbeiten, und ich spreche von Tausenden von Ereignissen, die pro Sekunde eintreffen, sodass es nicht möglich ist, alle Ereignisse in einer Datenbank gespeichert zu halten.

Gibt es Literatur zu dem von mir beschriebenen Problem?Wenn ja, könnten Sie mir Links dazu geben?

Ich würde gerne einen Aufsatz oder einen Text sehen, der einen Algorithmus erklärt, der dieses Problem löst, und es wäre noch besser, wenn ein solcher Aufsatz Beweise für den Algorithmus liefern würde (z. B.Richtigkeit).

Wenn ein solches Papier nicht existiert (ich glaube tatsächlich, dass das der Fall ist), würde ich eine Antwort akzeptieren, die einen Algorithmus beschreibt und ein Argument oder einen Beweis für seine Richtigkeit liefert.

Damit dieser Algorithmus korrekt ist, sollte er immer die richtige Reihenfolge von Benachrichtigungen senden, unabhängig von der Reihenfolge, in der die Ereignisse eintreffen.Und der Algorithmus sollte nicht alle empfangenen Ereignisse im Speicher behalten, da das eigentliche Problem darin besteht, dass zu viele Ereignisse im Speicher oder in einer Datenbank gespeichert werden können.Es wäre sinnvoll, einige Ereignisse im Speicher zu behalten, vorzugsweise eine feste Menge.

Answer 1

Unmöglichkeitsergebnis Nr. 1:gelöschte Ereignisse

Das Problem lässt sich nicht pauschal lösen;Es gibt keine Garantie dafür, dass Ihre Anforderungen erfüllt werden, wenn einige Ereignisse gelöscht (d. h. nicht empfangen) werden.Betrachten Sie zunächst diesen Stream:

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

wobei der Algorithmus beide Ereignisse sieht.Betrachten Sie als Nächstes diesen Stream:

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

wobei der Algorithmus nur die Ereignisse sieht e1',e4' (Die anderen Ereignisse gehen verloren und werden nie empfangen).Möglicherweise stellen Sie fest, dass das, was der Algorithmus in beiden Fällen sieht, identisch ist, sodass seine Ausgaben in beiden Fällen identisch sind.Allerdings ist die richtige Antwort in diesen beiden Fällen unterschiedlich, sodass keine Hoffnung auf einen Algorithmus besteht, der immer eine korrekte Ausgabe liefert.(Die richtige Reaktion im ersten Fall besteht darin, keine Benachrichtigungen zu erstellen;Im zweiten Fall besteht die richtige Antwort darin, zwei Benachrichtigungen zu erzeugen, eine davon, um nach dem Empfang anzugeben, dass das Prädikat falsch ist e2', und eine, um anzuzeigen, dass das Prädikat nach dem Empfang wahr ist e3'.)

Es ist nicht klar, wie die Anforderungen an diese Situation angepasst werden sollen.Die einzig plausible Lösung, die ich sehe, besteht darin, zu sagen, dass die erzeugten Benachrichtigungen nur von den empfangenen Ereignissen abhängen sollten, nicht von den gesendeten Ereignissen.Dies entspricht der Angabe, dass Ereignisse nicht gelöscht werden können.

Unmöglichkeitsergebnis Nr. 2:neu geordnete Ereignisse

Sie geben an, dass Sie in der Lage sein müssen, neu geordnete Ereignisse zu verarbeiten, ohne alle Ereignisse im Speicher zu speichern und mit willkürlicher Neuordnung.Diese Anforderungen sind jedoch nicht kompatibel:das ist unmöglich zu erreichen.Betrachten Sie eine lange Abfolge von Ereignissen mit den Zeitstempeln 2,4,6,8,10,12,...Wenn am Ende der langen Ereignissequenz ein Ereignis mit einem ungeraden Zeitstempel eintrifft, besteht die einzige Möglichkeit, sicherzustellen, dass Sie es richtig verarbeiten können, darin, den gesamten Verlauf vergangener Ereignisse (oder früherer Zustände des Objekts) zu speichern.

Daher müssen Sie auch die Anforderungen an Nachbestellungen lockern.Vielleicht sind Sie bereit, alle Ereignisse für immer im Gedächtnis zu speichern.(Wenn ja, haben Sie eine Lösung.) Vielleicht sind Sie bereit, eine Grenze für die Nachbestellung festzulegen, z. B. dass sich kein Ereignis um mehr als 10 Minuten verzögert.(Wenn ja, müssen Sie nur den Verlauf der letzten 10 Minuten speichern und alles, was älter ist, kann gelöscht werden.) Vielleicht ist in Ihrer speziellen Situation etwas anderes sinnvoller.

Aber das einzige, was keine Option ist, ist, alle in Ihrer Frage genannten strengen Anforderungen zu stellen und einen Algorithmus zu fordern, der immer korrekt ist.

---

Mir ist keine Literatur zu diesem Thema bekannt und ich sehe auch keinen Grund zu der Annahme, dass es welche geben wird.Es handelt sich um eine Reihe sehr spezifischer Anforderungen, und für mich sieht es so aus, als ob die daraus resultierende Aufgabe entweder trivial oder unmöglich zu lösen ist.Dies sind normalerweise nicht die Art von Problemen, die in der Literatur untersucht werden.Vielleicht haben Sie Interesse persistente Datenstrukturen, aber das ist nur eine schicke Möglichkeit, den gesamten Ereignisverlauf zu speichern, was Sie Ihrer Meinung nach tun möchten.und Sie benötigen dafür in Ihrer speziellen Situation keine ausgefallene Datenstruktur.