Distribué prédicat de calcul des flux d'événements

Question

Ma question est en fait une demande de documents, d'articles, de textes ou de livres sur le problème que j'essaie de résoudre sur mon travail.

Je suis en train de travailler sur un programme qui calcule une valeur de prédicat (vrai ou faux) pour un objet donné dans un système distribué, dans lequel il y a un flux d'événements qui peuvent modifier les attributs de l'objet et, par voie de conséquence, la valeur de prédicat.Chaque fois que le prédicat de changement de la valeur, le programme doit envoyer une notification au sujet de ce changement.

Par exemple, considérer qu'il y a un objet A qui a un attribut appelé name et de considérer qu'il y a un prédicat P ce qui est vrai lorsque l'objet de l' name est égal à Jhon.Chaque événement dans le flux a un horodatage et une valeur pour l'attribut nom.Ainsi, considérer la séquence d'événements suivante:

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 }

Dans ce problème, les événements ont un total de l'ordre de la relation:Si vous avez deux événements vous pouvez toujours dire ce qui est le plus ancien d'entre eux.

Maintenant, les événements ne sont pas nécessairement apparaître dans le flux de données dans le bon ordre en fonction de son timestamp.Chaque événement est unique, à son timestamp, donc il n'y a pas deux ou plusieurs événements à la même heure pour le même objet.Aussi, les horodateurs ne sont pas nécessairement la forme d'une séquence de toujours augmenter par un:si nous voyons e1 avec horodatage 1 et e3 avec horodatage 3, il n'implique pas l'existence d' e2 avec horodatage 2.Il n'y a aucune garantie que tous les événements seront reçus ou lorsqu'ils sont reçus.C'est une partie du problème que nous ne connaissons l'existence des événements que nous voyons dans le ruisseau.

Le vrai scénario est encore pire:il y a plusieurs ordinateurs en parallèle du traitement de ce flux d'évènements.Cependant, pour des raisons de simplicité, je vais aller plus loin dans cet exemple, l'examen d'un seul ordinateur.

Si les événements arrivent et sont traitées dans l'ordre décrit ci-dessus, les notifications envoyées doivent être:

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

C'est la séquence correcte des notifications car il respecte le timestamp de l'ordre.Maintenant, imaginez que l'ordinateur reçoit les événements dans l'ordre suivant:

e1, e5, e2, e4, e3

Un algorithme naïf qui ne considère pas l'horodatage de l'événement serait d'envoyer une séquence incorrecte de notifications:

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

L'algorithme que je suis en train de travailler sur l'estime de l'horodatages et en déduit si une notification doit avoir été envoyée, mais ne l'était pas.Alors, quand e3 arrivée il remarque que la notification P(A) = true pour e5 n'a pas été envoyé.Cela se sent un peu comme à réinventer la roue, même si je ne suis pas au courant de tout lire sur ce problème.Je voudrais quelques références à ce problème ou quelque chose de similaire, comme certaines études qui traitent de ce genre de problème.

Le vrai problème est bien plus complexe, car il implique de stocker le prédicat $ imes$ état de l'objet dans une base de données qui fonctionne comme un état partagé entre les ordinateurs de traitement des flux et je parle de milliers d'événements qui arrivent par seconde, de sorte qu'il n'est pas possible de garder tous les événements stockés dans une base de données.

Est-il de la littérature sur le problème que j'ai décrit?si oui, pourriez-vous me donner des liens?

Je voudrais voir un document ou un texte qui explique un algorithme qui permet de résoudre ce problème et il serait encore mieux si cette étude fournit des preuves à propos de l'algorithme (par ex.l'exactitude).

Si un tel document n'existe pas (en fait, je pense que c'est le cas), je tiens à accepter une réponse qui décrit un algorithme et fournit un argument ou une preuve de son exactitude.

Pour cet algorithme soit correct, il faut toujours envoyer la séquence correcte des notifications de n'importe quel ordre que les événements arrivent.Et l'algorithme ne devrait pas garder tous les événements reçus dans la mémoire, parce que le vrai problème de la traite avec trop d'événements à enregistrer dans la mémoire ou de la stocker dans une DB.Il serait raisonnable de garder certains événements dans la mémoire, de préférence d'un montant fixe.

Answer 1

Impossibilité de résultat n ° 1:abandonné événements

Le problème ne peut être résolu en général;il n'y a aucun moyen de garantir que vos exigences seront satisfaites si certains événements sont ignorés (c'est à dire, pas reçu).Considérons d'abord ce flux:

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

où l'algorithme voit les deux événements.Ensuite, réfléchissez à ce flux:

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

où l'algorithme ne voit que les événements e1',e4' (les autres événements sont perdus et n'ont jamais reçu).Vous remarquerez peut-être que ce que l'algorithme voit dans les deux cas est identique, de sorte que ses résultats seront identiques dans les deux cas.Cependant, la bonne réponse diffère dans ces deux cas, donc, il n'y a pas d'espoir pour un algorithme qui produit toujours un résultat correct.(La bonne réponse dans le premier cas, c'est de produire aucun des notifications;la bonne réponse dans le deuxième cas, c'est de produire deux avis, l'un pour indiquer que le prédicat est faux après la réception de e2', et un pour indiquer que le prédicat est vrai, après la réception de e3'.)

Il n'est pas clair comment adapter les exigences pour remédier à cette situation.La seule solution plausible que je peux voir, c'est-à-dire que les notifications qui sont produites doit dépendre seulement sur les événements reçus, et non pas sur les événements qui sont envoyés.Cela revient à spécifier que les événements ne peut pas être supprimé.

Impossibilité de résultat n ° 2:re-commandé événements

Vous dites que vous devez être en mesure de gérer re-commandé événements, sans stockage de tous les événements dans la mémoire, et l'arbitraire de re-commander.Toutefois, ces exigences sont incompatibles:qui est impossible à atteindre.Tenir compte d'une longue séquence d'événements avec des horodatages 2,4,6,8,10,12,...À la fin de la longue séquence des événements, si un événement avec un étrange timestamp arrive, la seule façon d'être sûr que vous pouvez gérer correctement est de stocker l'ensemble de l'historique des événements du passé (passé ou les états de l'objet).

Donc, vous allez avoir à vous détendre à l'exigence au sujet de re-commande ainsi.Peut-être que vous êtes prêt à stocker tous les événements dans la mémoire pour toujours.(Si si, vous avez une solution.) Peut-être que vous êtes prêt à imposer une limite sur la réorganisation, par exemple, aucun cas ne pourra être retardée de plus de 10 minutes.(Si oui, vous n'avez qu'à l'histoire de magasin pour les 10 dernières minutes, et tout ce que plus peuvent être supprimés.) Peut-être quelque chose d'autre a plus de sens dans votre situation particulière.

Mais la seule chose qui n'est pas une option consiste à imposer à toutes les exigences fortes indiqué dans votre question, et nécessitent un algorithme qui est toujours correct.

---

Je ne suis pas au courant de toute la littérature sur ce sujet et je n'ai pas particulièrement vois aucune raison de s'attendre à ce qu'il y a des.C'est un ensemble très spécifique de conditions, et il me semble que la tâche obtenue est soit trivial, voire impossible à résoudre.Ceux qui ne sont pas habituellement le genre de problèmes qui ont tendance à être étudiés dans la littérature.Peut-être que vous pourriez être intéressé par persistante des structures de données, mais c'est juste une façon élégante de ranger l'ensemble de l'historique des événements, qui vous dit que vous voulez faire;et vous n'avez pas besoin d'une fantaisie de structure de données pour le faire dans votre situation particulière.