Problema della sincronizzazione

Si è visto come lo stato complessivo di una rete NetGame sia mantenuto in modo distribuito su tutti i server che ne fanno parte e che si connettono tra loro con modalità peer-to-peer. In particolare vi sono due livelli diversi a cui operano i server:

• i MainServer sono tutti connessi tra loro e le informazioni che trattano riguardano sostanzialmente la presenza degli utenti. Essi gestiscono infatti il login ed il logout di un utente all'interno della rete. Ogni MainServer ha di fatto nozione di tutti i clienti connessi alla struttura in quell'istante, ma può comunicare in modo diretto e ha informazioni dettagliate solo riguardo a quelli che si sono direttamente connessi a lui.
• i RoomServer hanno invece il compito di gestire, oltre agli utenti presenti nella stanza, i messaggi che essi si scambiano e soprattutto le partite che essi creano e giocano. Ogni RoomServer è connesso solo con i RoomServer remoti analoghi (cioè coloro che ospitano lo stesso gioco all'interno della stessa rete), e con essi condivide lo stato della stanza, formato dagli utenti presenti, dalle partite in definizione con i rispettivi giocatori iscritti, ecc. Anche in questo caso le informazioni sulle partite sono condivise su tutti i server.

Un obiettivo fondamentale è dunque quello di mantenere consistenti le visioni che i vari server (sia a livello MainServer che RoomServer) hanno dei rispettivi stati. Si vuole cioè che una operazione di modifica dello stato, generalmente avviata da un utente (per esempio la creazione di una partita) sia vista da tutti i server allo stesso modo o eventualmente, se non è possibile su uno di essi, non venga eseguita su nessuno.

Il Two Phase Commit Protocol

Operazioni di questo tipo possono essere inquadrate come transazioni. Le transizioni sono operazioni che devono agire nel distribuito su più risorse, mantenendone la consistenza globale. Tipicamente le proprietà che deve rispettare una transazione si indicano con l'acronimo ACID, dove :

• Atomicity. Tutte le operazioni che compongono una transazione sono eseguite con successo, oppure nessuna deve essere eseguita.
• Consistency. L’insieme delle operazioni eseguite deve lasciare lo stato del sistema in una situazione consistente.
• Isolation. L’effetto delle operazioni che compongono una transazione non deve essere visibile a oggetti esterni alla transazione fino a che questa non sia completata.
• Durability. Gli effetti della transazione devono essere durevoli e rimanere anche dopo il termine della transazione

Già a livello locale la realizzazione di queste proprietà presenta problemi di sincronizzazione, risolvibili attraverso acquisizione e rilascio di lock di risorse, avendo cura di evitare (in modo ottimista o pessimista) eventuali situazioni di deadlock.
In ambito distribuito, cioè ove la transazione veda coinvolti più processi anche su host differenti, le problematiche si moltiplicano. In particolare bisogna considerare il caso di errori di comunicazione e di possibile caduta di un partecipante.
Comunque, ipotizzando un comportamento non "bizantino" dell'ambiente distribuito in cui si opera, si è riconosciuto un protocollo che consente di ottenere le proprietà di cui sopra. Questo protocollo è il Two Phase Commit Protocol (2PC), ed il suo obiettivo è indicare come coordinare i partecipanti ad una transazione di modo che la stessa venga eseguita atomicamente.

In termini generali, il 2PC prevede la presenza di un Transaction Manager (TM), che dovrà essere eletto dal partecipante (client) che intende effettuare la transazione. Ogni volta che vorrà fare una transazione il client dovrà effettuare le seguenti operazioni :

1. Comunicare al TM tutti i partecipanti alla transazione
2. Eseguire tutte le operazioni che compongono la transazione sui partecipanti interessati
3. Chiedere al TM di effettuare l'operazione di COMMIT

A questo punto il TM dovrà :

1. Mandare il comando PREPARE a tutti i partecipanti
2. Attendere le risposte da parte dei partecipanti. Si possono verificare due casi :
1. Le risposte sono tutte affermative (cioè tutti i partecipanti sono in grado di eseguire l'operazione).
   In questo caso il TM manda a tutti i partecipanti i comando COMMIT
2. Almeno una risposta è negativa.
   In questo caso il TM manda a tutti i partecipanti il comando di ABORT provocando l’aborto della transazione.

Dal loro lato, i partecipanti dovranno comportarsi nel seguente modo

1. Ricevere ed eseguire le operazione da parte del client
2. Una volta ricevuto il comando PREPARE da parte del TM, stabilire se le operazioni di cui sopra sono state eseguite con successo (in questa fase non è possibile accettare ulteriori operazioni da parte del client). Se questo è vero si risponde al TM positivamente, altrimenti negativamente
3. Si attende la comunicazione definitiva da parte del TM (evidentemente se un partecipante ha risposto negativamente saprà già che essa sarà un ABORT). Si possono verificare due casi :
1. il TM comunica un ABORT. In questo caso le operazioni corrispondenti a questa transazione dovranno essere "disfatte", riportando lo stato alla situazione precedente.
2. il TM comunica un COMMIT. In questo caso le modifiche apportate sono rese definitive e stabili.

Evidentemente la possibilità di fare abort implica che dalla parte dei partecipanti si abbia un supporto di rollback, che può essere ottenuto in vari modi, per esempio facendo uso di un file di log, o effettuando le modifiche non sui dati principali ma su una copia, rendendole poi effettive solamente al COMMIT.

Graficamente possiamo rappresentare graficamente le transizioni di stato possibili per i partecipanti nel seguente modo :

Operazioni in conflitto

Prima di vedere come il protocollo 2PC è stato adattato al nostro caso, vediamo quali sono le operazioni "pericolose", cioè che possono entrare in conflitto e che quindi necessitano di essere configurate come transazioni.
Le operazioni possono avere inizio su iniziativa di un client (che si connette, crea una partita, ecc) o di un server (un nuovo server entra nel sistema). Comunque sia, le transazioni vengono trattate a livello di Server. In particolare MainServer e RoomServer riconoscono tali operazioni e applicano loro il protocollo.
Analizzeremo successivamente il caso di ingresso di un nuovo server. Vediamo ora i possibili conflitti che può incontrare un'operazione attivata da un utente

MainServer

La colonna Op1 indica l'operazione che il cliente vuole compiere.
La colonna Op2 indica un'altra operazione che si sta eseguendo in quel momento all'interno del sistema.
Per valutare i motivi del conflitto si considera che l'operazione in corso vada a buon fine, cioè venga completamente eseguita prima di Op1.

RoomServer

Come si può vedere in RoomServer non c'è il problema del login, perché eventuali conflitti sono già stati risolti a livello di MainServer. In sostanza, se un utente chiede di entrare in una stanza significa che è già connesso al sistema e quindi ha un nome unico all'interno di esso. Non possono quindi verificarsi due richieste di accesso ad un RoomServer con lo steso nick.
Inoltre vi sono operazioni, come il logout di un utente o l'invio di un messaggio, che non presentano alcun problema a questo livello, e non hanno quindi bisogno di essere trattati con questo protocollo.

Naturalmente in queste tabelle si sono trattati solo i problemi sorti con la concorrenza con cui possono essere eseguite operazioni su server diversi. Per esempio non si è considerato il caso enter match - create match perché risolvibile in modo 'statico', nel senso che se si è giunti a questo punto con enter significa che la partita esiste già e quindi una create con lo stesso nome di partita fallirebbe subito. Né si sono considerati tutte le condizioni che comunque devono essere valide per ogni operazione (esempio - vincolo sul numero di giocatori per enter match e start match). Si intende che tutte queste condizioni siano verificate, altrimenti l'operazione fallirebbe ben prima di effettuare il protocollo 2PC.

Per avere un'idea di cosa potrebbe accadere si consideri la seguente figura, in cui è rappresentato un caso di possibile conflitto enter match - exit match. Si pensi al caso in cui un utente entra in una partita mentre un altro ne esce ed essendo l'ultimo giocatore iscritto, la cancella. In questo caso, senza gli accorgimenti di cui sopra, e in dipendenza dalla tempistica di ricezione dei messaggi da parte dei vari server, alcuni (quelli in cui la richiesta di ingresso è giunta prima) vedrebbero la partita ancora in essere con l'utente iscritto, mentre gli altri non vedrebbero più tale partita.

Adottando invece il protocollo 2PC ed osservando la tabella precedente si vede come al passo tre avremmo un conflitto per l'operazione eseguita dal Server1, che quindi viene abortita, cancellando il giocatore 2 dalla partita P1 su Server1 e Server2.

Ingresso di un server

L'ingresso di un server in una rete (sia a livello MainServer che RoomServer) è un evento che necessita particolare attenzione. E' necessaria in questo caso una forte sincronizzazione con le altre operazioni, perché tutte loro accedono in continuazione sulla tabella dei server remoti (avendo necessità di comunicare ad essi ogni operazione) ed una modifica di tale tabella durante un ciclo potrebbe portare ad un comportamento errato o ad una inconsistenza dello stato sui diversi servers. Inoltre potrebbe accadere che se due server tentano di connettersi lo stesso istante, facendo la richiesta a server diversi, a connessione avvenuta non siano visibili l’uno all’altro. Si consideri per esempio il seguente caso:

Si supponga che all'inizio la rete sia formata da due soli server (1 e 2). Si ricorda che la struttra remoteServers su ogni nodo contiene tutti i server remoti connessi a quel nodo. Ad un certo punto, contemporaneamente il server 3 tenta di connettersi al server 1 ed il server 4 al server 2. All'inizio quindi 3 e 4 fanno richiesta al rispettivo server a cui si stanno connettendo dello stato della rete (getServerState), e in base alla risposta ricevuta modificheranno la loro tabella remoteServers. Dopo questo provvederanno ad aggiungere loro stessi a tutti i server della rete (addServer). Ma in questo modo, come si può notare dalla quarta figura, c'è il pericolo che i server 3 e 4 non siano visibili tra di loro, cioè ci si trova in uno stato inconsistente della rete con informazioni non sincronizzate.

Con l'adozione del protocollo 2PC invece il problema può essere risolto, permettendo ad un solo server alla volta di connettersi alla rete.

Adattamento del protocollo 2PC a NetGame

Si sono viste in precedenza le proprietà ACID di una transazione. In realtà in questo progetto l'accento è posto sulla serializzabilità e sulla atomicità, piuttosto che sulla persistenza. In sostanza si vuole che se due o più transazioni sono eseguite in modo concorrente, il risultato finale sia lo stesso di quello ottenuto eseguendo le transazioni in un qualche ordine sequenziale (serializzabilità) e che una transazione possa essere considerata indivisibile ed istantanea, senza stati intermedi visibili (atomicità).
Oltre a questi problemi di sincronizzazione, introdotti dall'architettura distribuita, ve ne sono altri dovuti all'uso della tecnologia RMI. L'implementazione delle RMI prevede infatti la generazione sull'oggetto server di un thread per ogni invocazione remota (in realtà questo non è specificato dalla Sun, ma comunque si è dovuto considerare il caso peggiore). Questo ha necessariamente portato all'introduzione di opportune tecniche di sincronizzazione locale (uso di semafori ed eventualmente monitor). Particolare attenzione si è quindi dovuto porre al deadlock avoidance. Si è realizzata per ora una soluzione pessimistica (2 Phase lock), assegnando un ordine alle risorse ed imponendo che i lock su di esse vengano acquisiti secondo quell'ordine ed impedendo che un lock possa essere richiesto dopo averne abbandonato un altro (naturalmente solo per una stessa sezione critica).

Innanzitutto per permettere ai partecipanti ad una transazione di operare un rollback in seguito ad un comando di ABORT, si sono introdotte delle strutture accessorie su cui avvengono effettivamente le elaborazioni dettate dal coordinatore. Solo in seguito alla ricezione del comando COMMIT le modifiche saranno rese effettive, spostandole da tali strutture a quelle ‘permanenti’.
In particolare, tenendo conto delle tabelle di conflitto sopra esposte e del problema dell'ingresso di un nuovo server, si possono individuare facilmente tali strutture accessorie. Esse sono:

Il ruolo che nel protocollo 2PC è del Transacrion Manager, viene qui vestito direttamente dal server che riceve la richiesta originaria (da parte di un client o di un secondo server).
Per implementare tutte le fasi del protocollo si specializzano i metodi dell'interfaccia di comunicazione tra i server. In particolare, per ogni operazione tra quelle precedentemente presentate, si definiscono tre metodi :

• prepare<operazione>()
• commit<operazione>()
• abort<operazione>()

Analizziamo ora in generale le operazioni che deve compiere un server e le strutture di questi tre metodi.
Supponiamo che doAction() sia il metodo del server invocato da un client e che deve essere trattato come transazione. Esso avrà la seguente struttura :

doAction() {
        <acquisisce i lock sulle strutture da controllare>
               <verifica in base ad esse la fattibilità dell'azione. Se non è possibile fallisce>
               <acquisisce i lock sulle strutture ausiliarie coinvolte>
                       <verifica in base ad esse la fattibilità dell'azione 
                                  (cfr tabelle). Se non è possibile fallisce>
                       <effettua le modifiche necessarie sulle strutture ausiliarie>
               <rilascia i lock  sulle strutture ausiliarie coinvolte>
        <rilascia i lock sulle strutture da controllare> 
        <invoca prepareAction() su tutti i Server remoti ed attende le loro risposte>
        <se tutti i prepareAction() hanno avuto esito positivo>
               <acquisisce i lock sulle strutture coinvolte>
                       <effettua le modifiche su di esse>
               <rilascia i lock acquisiti>
               <invoca commitAction() su tutti i server remoti>
        <altrimenti>
               <acquisice i lock sulle strutture ausiliarie precedentemente modificate>
                       <rimuove le modifiche precedentemente effettuate>
               <rilascia i lock>
               <invoca abortAction() su tutti i server remoti>
}

Vediamo ora la struttura delle funzioni di prepare, commit e abort :

boolean prepareAction() {
        <acquisisce i lock sulle strutture ausiliarie coinvolte>
               <verifica se l'azione può essere effettuata. Se sì>
                       <effettua le modifiche sulle strutture ausiliarie e ritorna TRUE>
               <altrimenti>
                       <ritorna FALSE>
        <rilascia i lock>
}
 
commitAction() {
        <acquisisce i lock delle strutture coinvolte>
               <rimuove le modifiche dalle strutture accessorie e le applica alle altre>
        <rilascia i lock>
}
 
abortAction() {
        <acquisice i lock sulle strutture ausiliarie modificate in prepare>
               <rimuove le modifiche effettuate in prepare>
        <rilascia i lock>
}

Vediamo ora un esempio più concreto, per esempio quello della creazione di un match :

createMatch(nome del match, nome del giocatore) {
        <acquisisce i lock di matches e startedMatches>
               <Verifica se esiste già in tali liste una partita con quel nome. Se è così fallisce>
               <acquisisce il lock di creatingMatches>
                       <Verifica se in tale lista esiste già una partita con quel nome. Se è così fallisce>
                       <inserisce in creatingMatches il nome della partita e del giocatore>
               <rilascia il lock di creatingMatches>
        <rilascia i lock di matches e startedMatches> 
        <invoca prepareCreateMatch() su tutti i server remoti ed attende le loro risposte>
        <se tutti i prepareCreateMatch() hanno avuto esito positivo>
               <acquisisce i lock di matches e creatingMatches>
                       <toglie la coppia partita-giocatore da creatingMatches e la mette in matches>
               <rilascia i lock di matches e creatingMatches>
               <invoca commitCreateMatch() su tutti i server remoti>
        <altrimenti>
               <acquisice il lock su creatingMatches>
                       <rimuove la coppia partita-giocatore da creatingMatches>
               <rilascia il lock su creatingMatches>
               <invoca abortCreateMatch() su tutti i server remoti>
}

boolean prepareCreateMatch(nome del match, nome del giocatore) {
        <acquisisce il lock su creatingMatches>
               <verifica se creatingMatches contiene già la il nome del match. Se sì>
                       <inserisce partita e giocatore in creatingMatches e ritorna TRUE>
               <altrimenti>
                       <ritorna FALSE>
        <rilascia il lock su creatingMatches>
}
 
commitCreateMatch(nome del match, nome del giocatore) {
        <acquisisce i lock di matches e creatingMatches>
               <toglie la coppia partita-giocatore da creatingMatches e la mette in matches>
        <rilascia i lock di matches e creatingMatches>
}
 
abortCreateMatch(nome del match, nome del giocatore) {
        <acquisice il lock su creatingMatches>
               <rimuove la coppia partita-giocatore da creatingMatches>
        <rilascia il lock su creatingMatches>
}

In questo esempio è necessario comunicare anche il nome del giocatore, anche se potrebbe sembrare superfluo, perché l'abort viene invocata su tutti i server, indipendentemente dal fatto che abbiano risposto positivamente o meno. Potrebbe quindi accadere che un server abbia nella tabella creatingMatches una entry con lo stesso nome della partita in questione, ma richiesta da un diverso giocatore. Evidentemente tale entry non dovrà essere toccata.

Naturalmente negli schemi sopra si sono messe solo le macroistruzioni che riguardano il protocollo 2PC. Non si sono indicate le comunicazioni ai clients, che comunque avvengono all'interno di doAction() per i clienti locali al server TM, e in commitAction() per gli altri.

Finora non si è trattato il caso spinoso dell’ingresso di un nuovo server. Si sono già presentate le situazioni pericolose che si possono presentare se non ci si cautela in qualche modo.
Per ottenere un’esecuzione corretta si è deciso di escludere mutuamente la fase di commit dell’ingresso di un nuovo server rispetto a qualsiasi altra operazione. Il metodo addServer() presente sia nel MainServer che nel RoomServer e invocato dal nuovo server che vuole entrare nella rete è così strutturato :

stato addServer(nome del Server) {
        <acquisisce il lock di connectingServer>
               <Verifica se c’è già un server che sta tentando di connettersi. Se è così fallise>
               <pone in connectingServer il nome del Server>
        <rilascia il lock di connectingServer> 
        <invoca prepareConnectServer() su tutti i server remoti ed attende le loro risposte>
        <se tutti i prepareConnectServer() hanno avuto esito positivo>
               <acquisisce TUTTI i lock delle risorse coinvolte 
                (sostanzialmente le strutture dati che devono poi essere trasferite nello stato)>
                       <toglie da connectingServer il nome del server>
                       <prepara lo stato attuale della stanza>
                       <pone il server nella lista dei server remoti>
                       <invoca commitConnectServer() su tutti i server remoti>
                       <ritorna lo stato della stanza precedentemente preparato>
               <rilascia TUTTI i lock>
        <altrimenti>
               <acquisice il lock su connectingServer>
                       <rimuove da connectingServer il nome del server >
               <rilascia il lock su connectingServer >
               <invoca abortConnectServer() su tutti i server remoti>
}

Lo stato restituito sarà naturalmente diverso nel caso di MainServer o di RoomServer.
Per un MainServer bisognerà restituire informazioni quali

• la lista degli utenti connessi
• tutte le informazioni mantenute nelle strutture dati provvisorie precedentemente presentate

Per un RoomServer invece bisognerà restituire :

• la lista degli utenti nella stanza
• la lista delle partite in definizione
• la lista delle partite iniziate, con relativo host su cui sono ospitate
• tutte le informazioni mantenute nelle strutture dati provvisorie precedentemente presentate

Si noti come la restituzione del risultato avvenga in una porzione di codice fortemente sincronizzata, in quanto il thread, per effettuare tale operazione, deve posseder tutti i lock delle risorse coinvolte. Così si garantisce che nessun altra operazione possa modificare in qualche modo lo stato del server, ed il nuovo arrivato venga a conoscenza senza alcun dubbio dello stato attuale e non corra il rischio di perdere qualche avvenimento.
Per evitare il problema di 2 server che si connettono contemporaneamente e rischiano di non vedersi, viene consentito l’ingresso di un nuovo server alla volta; sostanzialmente connectingServer può contenere al più una entry.

Oltre alla realizzazione del metodo addServer() e dei tre metodi prepareConnectServer(), commitConnectServer() e abortConnectServer() – che non presentano del resto variazioni significative rispetto alle strutture generali già viste – occorre modificare tutte le funzioni precedentemente presentate come doAction() effettuando come primo controllo la verifica che un server non si stia connettendo. Occorre che esse acquisiscano come prima cosa il lock su connectingServer, quindi verifichino se esso contiene o no il nome di un server. Se lo contiene l’operazione fallisce, viceversa si può continuare normalmente, eseguendo le operazioni successive.