Computazione predicato distribuito sul flusso di eventi

Question

La mia domanda è in realtà una richiesta di documenti, articoli, testi o libri sul problema che sto cercando di risolvere il mio lavoro.

Sto lavorando a un programma che calcola un valore predicato (vero o falso) per un determinato oggetto in un sistema distribuito in cui esiste un flusso di eventi in grado di modificare gli attributi dell'oggetto e, conseguente, il valore predicato. Ogni volta che il valore predicato cambia, il programma deve inviare una notifica su questa modifica.

Ad esempio, considera che esiste un oggetto A oggetto che ha un attributo chiamato name e considera che esiste un predicato P che è vero quando il name dell'oggetto è uguale a Jhon. Ogni evento nel flusso ha un timestamp e un valore per il nome dell'attributo. Quindi considera la seguente sequenza di eventi:

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 questo problema gli eventi hanno una relazione totale dell'ordine: se hai due eventi, puoi sempre dire quale è il più antico di loro.

Ora, gli eventi non vengono necessariamente visualizzati nel flusso nell'ordine corretto in base al suo timestamp. Ogni evento è unico per il suo timestamp, quindi non ci sono due o più eventi con lo stesso timestamp per lo stesso oggetto. Inoltre, i timestamps non formano necessariamente una sequenza che aumenta sempre di uno: se vediamo e1 con 1 TimeStampCode e e3 con Timestamp 3, non implica l'esistenza di e2 con TimeStampoDiceTagCode. Non vi è alcuna garanzia che tutti gli eventi saranno ricevuti o quando saranno ricevuti. Fa parte del problema che sappiamo solo dell'esistenza degli eventi che vediamo nel flusso.

Lo scenario reale è ancora peggiore: ci sono più computer che elaborano in modo parallelo questo flusso di eventi. Tuttavia, per semplicità, andrò ulteriormente in questo esempio considerando solo un computer.

Se gli eventi arrivano e vengono elaborati nell'ordine sopra descritto, quindi le notifiche inviate dovrebbero essere:

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

.

Questa è la sequenza corretta delle notifiche perché rispetta l'ordine del timestamp. Ora, immagina che il computer riceva gli eventi nel seguente ordine:

e1, e5, e2, e4, e3

.

Un algoritmo ingenuo che non considera il timestamp dell'evento invierebbe una sequenza errata di notifiche:

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

.

L'algoritmo che sto lavorando a considerare i timestamp e gli inferi quando una notifica avrebbe dovuto essere inviata ma non lo era. Quindi, quando 2 arriverà notare che la notifica e3 per P(A) = true non è stata inviata. Questo è un po 'come reinventare la ruota, anche se non sono a conoscenza di alcuna lettura di questo problema. Vorrei alcuni riferimenti a questo problema o a qualcosa di simile, come alcuni documenti che si occupano di questo tipo di problema.

Il problema reale è abbastanza complesso poiché implica la memorizzazione del predicato $ \ volte $ stato oggetto in un database che funziona come uno stato condiviso tra i computer che elaborano il Stream e sto parlando di migliaia di eventi che arrivano al secondo modo, quindi non è possibile mantenere tutti gli eventi memorizzati in un database.

C'è qualche letteratura sul problema che ho descritto? Se è così, potresti darmi collegamenti ad esso?

Vorrei vedere un foglio o un testo che spiega un algoritmo che risolve questo problema e sarebbe ancora meglio se tale carta fornisce prove sull'algoritmo (E.G. correttezza).

Se tale carta non esiste (in realtà penso che sia il caso), accetterei una risposta che descrive un algoritmo e fornisca un argomento o una prova sulla sua correttezza.

Per questo algoritmo essere corretto, dovrebbe sempre inviare la sequenza corretta delle notifiche, non importa quale sia l'ordine in cui arriva gli eventi. E l'algoritmo non dovrebbe tenere tutti gli eventi ricevuti in memoria, perché il problema reale riguarda troppi eventi da salvare in memoria o per archiviare in un DB. Sarebbe ragionevole mantenere alcuni eventi in memoria, preferibilmente un importo fisso.

Answer 1

Risultato impossibilità n. 1: eventi caduti

Il problema non può essere risolto in generale; Non c'è modo di garantire che le tue esigenze saranno soddisfatte se alcuni eventi vengono rilasciati (cioè, non ricevuto). Considera il primo flusso:

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

.

Dove l'algoritmo vede entrambi gli eventi. Quindi, considera questo flusso:

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

.

Dove l'algoritmo vede solo gli eventi e1', e4' (gli altri eventi sono persi e mai ricevuti). Potresti notare che ciò che l'algoritmo vede in entrambi i casi è identico, quindi le sue uscite saranno identiche in entrambi i casi. Tuttavia, la risposta corretta differisce in questi due casi, quindi non c'è speranza per un algoritmo che produce sempre un'uscita corretta. (La risposta corretta nel primo caso è quella di produrre notifiche; la risposta corretta nel secondo caso è quella di produrre due notifiche, una per indicare che il predicato è falso dopo aver ricevuto e2', e uno per indicare che il predicato è vero dopo la ricezione e3'.)

Non è chiaro come adattare i requisiti per gestire questa situazione. L'unica soluzione plausibile che posso vedere è dire che le notifiche prodotte dovrebbero dipendere solo dagli eventi ricevuti, non sugli eventi inviati. Questo è equivalente a specificare che gli eventi non possono essere caduti.

Risultato impossibilità n. 2: Ricomincia agli eventi

Si dice che devi essere in grado di gestire gli eventi ricomuntati, senza memorizzare tutti gli eventi in memoria e con riordino arbitrario. Tuttavia, questi requisiti sono incompatibili: è impossibile da raggiungere. Considera una lunga sequenza di eventi con timestamp 2,4,6,8,10,12, ... Alla fine della lunga sequenza di eventi, se arriva un evento con uno strano timestamp, l'unico modo per essere sicuro che puoi Gestiscilo correttamente è quello di memorizzare l'intera storia degli eventi passati (o degli stati passati dell'oggetto).

Allora, dovrai rilassare anche il requisito di riordinare anche. Forse sei disposto a memorizzare tutti gli eventi in memoria per sempre. (Se è così, hai una soluzione.) Forse sei disposto a imporre un limite per il riordino, ad esempio, nessun evento sarà ritardato di oltre 10 minuti. (Se è così, devi solo memorizzare la storia negli ultimi 10 minuti, e tutto il possibile può essere cancellato.) Forse qualcos'altro ha più senso nella tua situazione particolare.

Ma l'unica cosa che non è un'opzione è quella di imporre tutti i requisiti forti indicati nella tua domanda e richiedono un algoritmo che è sempre corretto.

---

.

Non sono a conoscenza di alcuna letteratura su questo e non vedo particolarmente alcuna ragione per aspettarsi che ci sia alcuna. È una serie di requisiti molto specifici, e mi guarda come il compito risultante è banale o impossibile da risolvere. Quelli di solito non sono il tipo di problemi che tendono ad essere studiati in letteratura. Forse potresti essere interessato a strutture dati persistenti , ma è solo un modo elegante di conservare l'intero Storia degli eventi, che hai detto che vuoi fare; E non hai bisogno di una struttura di dati fantasia per farlo nella tua particolare situazione.