Un sistema per la replicazione
ottimistica in una rete di pari
Progetto di
Reti di calcolatori LS
Federico Grassi
a.a. 2004/2005
Requisiti di progetto
 Il progetto ha come obiettivo quello di realizzare
un sistema che supporti la replicazione debole
fra le repliche che lo compongono.
 L’applicazione vuole che gli utenti comunichino
fra di loro per creare una base di conoscenza
comune disponibile su ogni nodo.
 Si vuole massimizzare la disponibilità dei dati
anche in un ambiente con mobilità e scarsa
connettività.
Descrizione del sistema
 Spesso valutare la qualità
di un link Internet non è
facile.
 Gli utenti
dell’applicazione si
scambiano commenti
(Annotation) sui link del
sistema peer-to-peer
Emule, differenziandole
per aree tematiche
(Channel).
Replicazione ottimistica
 Nel sistema gli utenti contribuiscono alla
creazione di una base di conoscenza comune,
scrivendo, modificando e cancellando
annotazioni.
 Ogni nodo ha diritto di effettuare modifiche in
maniera non bloccante rispetto agli altri; i nodi
perciò possono contenere, in alcuni momenti,
dati divergenti.
 Il sistema si occupa di mantenere la consistenza
finale, ovvero fa convergere le varie repliche una
volta che gli utenti hanno terminato di effettuare
modifiche.
Gestione della comunicazione
 Per comunicare alle altre repliche le operazioni
effettuate i nodi utilizzano meccanismi epidemici.
 La comunicazione avviene attraverso un
meccanismo primario ed un secondo di backup:
 Rumor mongering
 Anti-entropy
 Per le operazioni di cancellazione si utilizzano i
death-certificate.
Meccanismi epidemici: Rumor mongering
 Quando un nodo riceve una nuova operazione, questa
viene marcata come calda e comunicata ai pari.
 Dopo aver contattato un numero n di nodi che già
conoscevano l’operazione, la replica perde interesse e
non la distribuisce più.
Meccanismi epidemici: Anti-entropy
 Con rumor mongering non si ha la certezza che tutti i
nodi ricevano una informazione, per questo si utilizza
come sistema di backup il meccanismo anti-entropy.
 Un nodo sceglie ogni T secondi un pari e i due si
scambiano tutto il loro contenuto informativo secondo
una politica push-pull.
Annotation1
Log
Annotation2
Log
Annotation2
Anti-entropy session
Annotation1
Node y
Node x
Meccanismi epidemici: Death certificate
 Nel sistema non è sufficiente cancellare un oggetto da una replica
per eliminarlo definitivamente, bisogna tenere traccia
dell’operazione attraverso i death-certificate.
 Questi certificati di cancellazione vengono memorizzati in un
repository su ogni nodo e comunicati agli altri con gli stessi
meccanismi descritti in precedenza.
DeathCertificateRepository
DeathCertificate
Node x
Architettura logica
 L’architettura logica di
ogni nodo presenta
quattro elementi
fondamentali:
 EntityManager
 TimeManager
 LogManager
 NetworkManager
 Il fulcro dell’applicazione
è il LogManager che
opera tra la rete e gli
oggetti replicati.
Rete di pari e JXTA™
 I nodi fra loro formano una rete di pari.
 A livello implementativo è stato utilizzato il pacchetto
JXTA. Questo offre le primitive per creare un gruppo di
pari e farli comunicare fra loro.
 JXTA permette di offrire supporto anche a piattaforme
come telefoni cellulari e palmari.
JXTASocket
JXTASocket
JXTASocket
JXTASocket
Gestione del tempo di sistema
 Ad ogni operazione viene associato un
timestamp contente il valore dell’orologio logico
e l’identificatore della replica generatrice.
 Il tempo di sistema viene gestito attraverso la
relazione di Lamport happens-before sui clock
logici.
 L’ordine parziale introdotto diventa totale
utilizzando come ulteriore discriminante
l’identificatore dei nodi.
Gestione dei conflitti
 Essendo possibile che le repliche divergano
come contenuto occorre prevedere un
meccanismo di riconciliazione.
 Il sistema prevede un protocollo per gestire
queste situazioni basato sulla sintassi delle
operazioni e la valutazione dei timestamp.
 In questo modo si ottiene che le repliche
raggiungano la eventual consistency.
Stabilizzazione delle repliche
 Fra le repliche ne esiste una considerata
primaria. Il compito di questo nodo è quello di
stabilizzare le annotazioni.
 Rendendo definitive le annotazioni si evita che
nodi rimasti a lungo scollegati e con valori di
clock molto più bassi costringano l’intero sistema
ad un gravoso roll-back.
 Questa azione avrebbe molta importanza se il
sistema di replicazione invece di occuparsi di
annotazioni dovesse gestire, per esempio, un
sistema di prenotazioni decentralizzate.
Conclusioni e sviluppi futuri
 Il sistema implementato gestisce la replicazione
ottimistica con alcune limitazioni rispetto a quanto
progettato.
 E’ stato sviluppato un protocollo per dirimere i conflitti fra
le annotazioni utilizzando i timestamp generati dalle
repliche.
 L’applicazione è stata testata con grado di replicazione
due.
 In futuro si dovrebbero sviluppare le parti non
implementate e gestire la persistenza interfacciandosi
con un database. Inoltre l’applicazione potrebbe essere
integrata al client Emule o direttamente o attraverso l’uso
di un plug-in.