Ho iniziato a esaminare gli approcci alla sincronizzazione dei dati tra un gruppo di colleghi. I peer devono essere in grado di lavorare in modalità disconnessa e quindi sincronizzare insieme per unire le loro modifiche locali.

I peer dovrebbero essere in grado di unire gli aggiornamenti locali con un "unione a tre vie" . Quindi, durante la sincronizzazione, i peer dovrebbero sapere quali fatti sono più recenti, ma dove non c'è un ordinamento rigoroso, dovrebbero essere in grado di unire i fatti in base alla radice comune.

Quando i peer indipendenti apportano modifiche, possono "stamparli" con un "orologio". Uso il termine "orologio" e "timestamp", ma non intendo un orologio da parete. Intendo una sorta di ordinamento parziale degli eventi che rende chiara la causalità. È la relazione "precedente alla" relazione tra eventi che forma un grafico aciclico diretto (DAG).

Sembra che il "solito" modo di costruire questo ordinamento parziale sia usando un orologio vettoriale . Questi possono diventare molto grandi, tuttavia. Sviluppi più recenti come intervalli di clock degli alberi offrono una maggiore compattezza dell'archiviazione dei timestamp.

Ciò di cui non sono affatto chiaro è il motivo per cui i protocolli di sincronizzazione a quanto pare non "semplicemente" memorizzano il DAG in modo esplicito. (O lo fanno?)

I peer possono creare indipendentemente un timestamp generando casualmente un UUID (o con altri mezzi, come <peer-name> + <local-monotonically-increasing-counter> ). L'ordine di questo timestamp è completamente chiaro a quel peer.

Quando 2 peer si sincronizzano tra loro, possono concordare un nuovo timestamp. Anche in questo caso, l'ordine di questo timestamp è chiaro per entrambi i peer.

Ora c'è un requisito per passare l'accaduto prima del DAG tra pari, ma i requisiti di archiviazione e larghezza di banda di questo sono piccoli. I punti temporali sono vertici del grafico. Come tali hanno 1 o 2 bordi in entrata (1 per un evento su un client e 2 per una sincronizzazione tra client). Questo è limitato e indipendente dal numero di peer nella rete.

Per utilizzare un singolo punto temporale, è necessario il grafico dei punti temporali che portano a questo. Tuttavia, per quanto posso vedere, qualsiasi peer che sia in grado di conoscere di un punto temporale (lo ha generato da solo o generato con un altro peer o è stato detto da un altro peer quando sincronizzandosi con esso) ha anche avuto l'opportunità di conoscere la storia che ha portato a quel punto temporale. Penso che ci sia probabilmente una prova induttiva per questo.

Dato che memorizzare e sincronizzare il DAG sembra esplicitamente semplice: è usato nella pratica? In caso contrario, perché sono preferiti gli orologi vettoriali?

Note

Peer to peer

Preferirei una soluzione peer-to-peer su una soluzione server client.

La probabile topologia finale saranno molti client che si connettono a un gruppo molto più piccolo di server che si replicano tra loro. Tuttavia, sarebbe bello avere una soluzione generale che supporta questa particolare topologia piuttosto che una soluzione che richiede questa topologia specifica.