Come si elabora un grafico costantemente aggiornato, con bassa latenza?

Question

Sto lavorando a un progetto che coinvolge molti client che si connettono a un server (server se necessario) che contiene un mucchio di informazioni sul grafico (attributi e spigoli del nodo). Avranno la possibilità di introdurre un nuovo nodo o edge ogni volta che lo vorranno e quindi richiedere alcune informazioni dal grafico nel suo insieme (la distanza più breve tra due nodi, la colorazione del grafico, ecc.).

Questo ovviamente è abbastanza facile da sviluppare l'algoritmo ingenuo, ma poi sto cercando di imparare a ridimensionarlo in modo che possa gestire molti utenti che aggiornano il grafico nello stesso momento, molti utenti che richiedono informazioni dal grafico e la possibilità di gestire nodi molto grandi (500k +) e possibilmente anche un numero molto grande di bordi.

Le sfide che posso prevedere:

• con un grafico in costante aggiornamento, ho bisogno di elaborare l'intero grafico ogni volta che qualcuno richiede informazioni ... che aumenterà il tempo di calcolo e la latenza di un bel po '
• con un grafico molto grande, il tempo di calcolo e la latenza saranno ovviamente molto più alti (ho letto che questo è stato risolto da alcune aziende elaborando in batch una tonnellata di risultati e memorizzandoli con un indice per un uso successivo ... ma poi dal mio il grafico viene costantemente aggiornato e gli utenti vogliono le informazioni più aggiornate, questa non è una soluzione praticabile)
• un gran numero di utenti che richiedono informazioni che saranno piuttosto un carico sui server poiché deve elaborare il grafico molte volte

Come posso iniziare ad affrontare queste sfide? Ho guardato su hadoop e spark, ma sembrano soluzioni ad alta latenza (con elaborazione batch) o soluzioni che risolvono problemi in cui il grafico non cambia continuamente.

Mi è venuta l'idea di elaborare diverse parti del grafico e indicizzarle, quindi tenere traccia di dove il grafico viene aggiornato e rielaborare quella sezione del grafico (una sorta di approccio di programmazione dinamica distribuita), ma in non sono sicuro di quanto sia fattibile.

Grazie!

Answer 1

Come posso iniziare ad affrontare queste sfide?

ho intenzione di rispondere a questa domanda , perché è quello importante. Hai elencato una serie di dubbi validi, tutti dei quali dovrai occuparti e nessuno dei quali parlerò direttamente.

Per iniziare, è necessario completare la definizione della semantica. Potresti pensare di aver finito, ma non lo sei. Quando si dice "Gli utenti vogliono che il più aggiornate informazioni aggiornate", significa "up to date" significa

1. "tutto nel passato", che porta alla serializzazione totale di ciascuna operazione per il grafico, in modo che le risposte riflettono ogni possibile informazione?
2. Oppure "tutto transazionale più di X secondi fa", che porta alla serializzazione parziale, che più stati del database nel presente vengono progressivamente serializzati nel passato?

Se 1. è richiesto, è possibile che nel codice siano presenti punti caldi inevitabili, a seconda dell'applicazione. Hai informazioni immediate su quando eseguire il rollback di una transazione a causa di incoerenza.

Se 2. è accettabile, si ha la possibilità di prestazioni molto migliori. Ci sono dei compromessi, però. Avrai situazioni in cui devi eseguire il rollback di una transazione dopo l'accettazione iniziale.

Una volta che hai risposto a questa domanda, hai iniziato ad affrontare le tue sfide e, presumo, avremo ulteriori domande.

Answer 2

Non so molto di grafici, ma capisco un po 'di networking.

Una regola che tengo a tenere a mente è ... non lavorare sul lato server se è possibile ottenere il client per farlo.

Tutto ciò che il vostro server deve fare è mantenere i dati grezzi, servire i dati grezzi ai client e notificare i client connessi quando i dati cambiano.

I client possono avere una propria copia dei dati grezzi e quindi generare calcoli/visualizzazioni in base a ciò che sanno e agli aggiornamenti che ricevono.

I client devono solo sapere se ci sono nuovi record o se i vecchi record sono cambiati.

Se, per qualche ragione, è ASSOLUTAMENTE necessario elaborare il lato server dati e inviarlo al client (ad esempio, il client è software di terze parti, non qualcosa su cui si ha il controllo e si aspetta dati elaborati, non dati grezzi) , POI, hai un po 'di problemi, quindi prendi un server di brutto culo ... o 3 o 30. In questo caso, dovrei sapere esattamente quali sono i dati e come vengono elaborati per fare qualsiasi tipo di suggerimenti sulla configurazione in scala.