Doveva essere una giornata di lavoro tranquilla e senza intoppi quando hai incontrato per la prima volta il Calcolo Distribuito. Eri rilassato, un po’ come Bilbo (beh, non del tutto), ma quel giorno ti sei trovato di fronte a questa nuova tipologia di problema…
"INTENDI AUGURARMI IL BUONGIORNO, O VUOI DIRE CHE È UN BUONGIORNO CHE IO LO VOGLIA O NO?"
Il calcolo distribuito è una disciplina specializzata dell’informatica dedicata allo studio dei sistemi distribuiti. Un sistema distribuito è composto da numerosi componenti software distribuiti su più computer, che tuttavia funzionano in modo armonioso come un’unica entità. Questo paradigma offre un approccio decentralizzato per affrontare problemi complessi, permettendo di scalare orizzontalmente il nostro sistema—localmente o su più macchine—per migliorare le prestazioni complessive.
Raggiungere questo obiettivo richiede un cambiamento fondamentale nel nostro approccio alla risoluzione dei problemi. È necessario passare da una prospettiva generalizzata e da un controllo quasi totale sull’esecuzione degli algoritmi a un punto di vista localizzato. In questo contesto, ogni elemento del sistema collabora localmente, contribuendo a una soluzione complessiva e armoniosa del problema, in modo simile a un’esecuzione corale.
Il nostro viaggio nel calcolo distribuito inizierà affrontando una delle sue sfide fondamentali. Partiremo da una definizione matematica per poi passare progressivamente ad aspetti più pratici, includendo alcuni esempi di codice utilizzando uno dei framework più famosi.
Puoi provare a risolvere il problema con gli strumenti che già conosci. Ma se non vuoi lasciare La Contea e Casa Baggins, resta dove sei. Porterò io l’avventura da te.
TL;DR
Voglio darti una spiegazione iniziale di tutta la matematica che sta alla base di questo argomento. È necessario avere una base e un punto di riferimento per valutare la qualità del sistema che stiamo utilizzando. Devo almeno grattare la superficie, oppure puoi saltare direttamente alla sezione del codice.
Entità
Per dare forma alle nostre ipotesi, definiamo prima l’ambiente in cui operare: un universo con alcune restrizioni. Un universo vuoto sarebbe un po’ noioso. Abbiamo bisogno di popolarlo con alcune piccole creature: le entità. Questa collezione finita è composta da elementi computazionali che possono interagire scambiandosi messaggi.
Le capacità di un’entità x includono:
- Accesso (memorizzazione e recupero) alla memoria locale Mx: privata e non condivisa.
- Elaborazione locale: esecuzione di calcoli o azioni basate sulla memoria locale.
- Comunicazione: preparazione, trasmissione e ricezione di messaggi.
La memoria locale include un insieme di registri i cui valori devono essere sempre inizialmente definiti:
- Registro di stato
status(x) - Registro del valore di input
value(x)
Il registro status(x) assume valori da un insieme finito di stati del sistema S, precedentemente definiti, come “Idle”, “Processing”, “Waiting”, ecc. Inoltre, ogni entità dispone di una sveglia cx che può essere impostata e resettata.
Un’entità può eseguire solo quattro operazioni:
- memorizzazione ed elaborazione locale
- trasmissione di messaggi
- impostazione o reset della sveglia
- aggiornamento del registro di stato
Eventi
Ci sono tre possibili eventi:
- L’arrivo di un messaggio
- Lo squillo della sveglia
- Un impulso spontaneo
L’arrivo di un messaggio e lo squillo della sveglia sono eventi esterni all’entità ma originano all’interno del sistema: il messaggio è inviato da un’altra entità, e la sveglia viene impostata dalla stessa entità. Un impulso spontaneo, invece, è attivato da forze esterne al sistema e quindi al di fuori della percezione delle entità.
Il comportamento dell’entità x è reattivo, nel senso che risponde esclusivamente a stimoli esterni, chiamati eventi esterni (o semplicemente eventi). In assenza di stimoli, l’entità x rimane inerte e non fa nulla.
Azioni
Come reagisce l’entità x quando si verifica un evento esterno e?
L’entità x reagisce all’evento e eseguendo un’azione, ovvero una sequenza finita e indivisibile di operazioni che termina con una conclusione.
Un’azione è atomica: le operazioni che la compongono vengono eseguite senza alcuna interruzione. In altre parole, una volta iniziata, l’azione non si interrompe fino a quando non è completata entro un determinato tempo.
Ci saranno eventi che non attivano alcuna reazione nell’entità bersaglio. In questi casi specifici, l’entità reagisce con un’azione unica denominata “nil”.
Comportamento
Come si comporta un’entità quando è in azione?
La natura dell’azione che verrà eseguita è definita dalla corrispondenza tra l’evento e il valore presente in status(x). Di conseguenza, la specifica si traduce nella seguente regola:
Status × Event → Action
L’insieme delle regole a cui l’entità x obbedisce è il comportamento B(x), in cui ogni possibile evento e e valore di status(x) devono essere completi e non ambigui.
L’insieme di tutti i B(x) delle entità presenti nel sistema forma un comportamento collettivo che segue il problema da risolvere.
VADO ALL'AVVENTURA!
Comunicazioni
Messaggi. Ora che sei familiare con il calibro dei nostri cittadini modello (nessuna truffa coinvolta), come interagiscono tra loro? Una cosa da ricordare è che il nostro contesto consiste in un ambiente distribuito. Non sappiamo in anticipo come le nostre entità siano disposte nello spazio del contesto né quali entità comunichino potenzialmente tra loro. Pertanto, proprio come gli esseri umani che sanno comunicare tramite voce o testo, il metodo di comunicazione delle entità, che implica la trasmissione e la ricezione di messaggi, deve essere definito.
Topologia. Come puoi vedere, le entità che possono comunicare direttamente non rappresentano necessariamente l’insieme completo delle entità. In altre parole, un’entità può spesso comunicare direttamente solo con un sottoinsieme di altre entità. Il sottoinsieme Nout(x) rappresenta i vicini in uscita di x e denota l’insieme delle entità a cui l’entità x può trasmettere un messaggio direttamente. Allo stesso modo, Nin(x) rappresenta i vicini in entrata di x, ovvero le entità da cui x può ricevere un messaggio direttamente.
Questa relazione di vicinato definisce un grafo orientato G = (V, E) che descrive la topologia di comunicazione dell’ambiente. Questa è la definizione generale. A seconda del problema considerato, è possibile fare delle assunzioni per semplificare i due archi tra l’entità A e B (e viceversa) in una singola connessione bidirezionale.
Esempio di Broadcasting
Lascia che ti fornisca un esempio concreto del concetto sopra descritto.
Nel nostro universo, le piccole creature cercano di capire dove si trovano per organizzarsi. Quando un’entità fa una nuova scoperta importante, come può condividere queste informazioni con tutte le altre entità? Qui, l’entità si trova di fronte a un problema di broadcasting, ovvero un problema generale di diffusione delle informazioni.
Come parte della soluzione, dobbiamo semplificare il compito facendo alcune ipotesi e restrizioni (che verranno approfondite in un altro post del blog):
Assunzioni:
- I collegamenti tra le entità sono bidirezionali.
- Totale affidabilità: non ci sono né si verificano errori.
Restrizioni:
- La topologia è limitata a un grafo G connesso: non completamente connesso, ma deve esistere almeno un percorso che colleghi ogni entità appartenente all’insieme.
- Unico iniziatore: come definito nel problema, ogni esecuzione è avviata da una sola entità che fa la scoperta e avvia l’algoritmo.
Il primo passo per risolvere il problema di broadcasting è rendere esplicito l’insieme degli stati S:
- initiator
- idle
- done
Il processo può essere avviato solo dall’initiator. Sia I l’informazione da trasmettere e impulse l’arrivo di un impulso spontaneo che avvia l’algoritmo.
Ecco l’insieme delle regole B(x) (le stesse per tutte le entità):
- initiator × impulse → {send(I) to N(x); become done}
- idle × Receiving(I) → {Process(I); become done; send(I) to N(x)}
- initiator × Receiving(I) → nil
- idle × impulse → nil
- done × Receiving(I) → nil
- done × impulse → nil
Questo protocollo introduce uno stato aggiuntivo, done, senza il quale il protocollo sarebbe formalmente scorretto, non raggiungendo mai uno stato di riposo, poiché le entità continuerebbero a scambiarsi messaggi.
Mostrami il codice
THE WORLD IS NOT IN YOUR BOOKS AND MAPS. IT IS OUT THERE.
Vediamo come possiamo rendere questo esempio più pratico.
Per fare ciò, utilizzeremo il framework Akka (https://akka.io/). Ma cos’è Akka? È esattamente ciò di cui abbiamo bisogno!
Akka è un toolkit per costruire applicazioni altamente concorrenti, distribuite e resilienti basate su messaggi per Java e Scala.
Akka implementa il modello ad attori sulla Java Virtual Machine (JVM). Senza entrare troppo nei dettagli, il modello ad attori è vicino ai concetti che abbiamo discusso in precedenza.
Per il nostro esempio, utilizzeremo la classe FSM fornita dalla Classic API del framework (al momento della stesura, Akka fornisce una nuova API che permette di fare le stesse cose, ma per questo esempio usare la classe FSM offre una correlazione più esplicita con il pseudo-codice visto in precedenza).
Lasciamo da parte la modalità di definizione del grafo delle entità.
Passiamo ora a definire esplicitamente i due tipi di messaggi che le nostre entità possono ricevere:
final case class SpontaneousImpulse(info: String)
final case class Receiving(info: String)
Definiamo l’insieme S degli stati possibili:
sealed trait State
case object Initiator extends State
case object Idle extends State
case object Done extends State
E dobbiamo definire come l’entità incapsula le informazioni nel suo archivio di memoria:
sealed trait Data
case object Uninitialized extends Data
final case class Info(info: String) extends Data
E questa sarà, in generale, la struttura e la forma della nostra classe:
class Entity(name: String, initialState: State) extends FSM[State, Data] {
startWith(initialState, Uninitialized)
...
// idle × Receiving(I) → {Process(I); become done}
when(Idle) {
case Event(Receiving(ref), Uninitialized) =>
goto(Done).using(Info(ref))
}
// initiator × impulse → {become done}
when(Initiator) {
case Event(SpontaneousImpulse(ref), Uninitialized) =>
goto(Done).using(Info(ref))
}
// done × Receiving(I) → nil
when(Done) {
case Event(e, s) =>
log.warning("I'm {} already know this info {} i'm in {} state", name, e, stateName)
stay()
}
onTransition {
case Initiator -> Done =>
stateData match {
case Info(info) => sendToNeighbours(info)
case _ => // nothing to do
}
case Idle -> Done =>
stateData match {
case Info(info) => sendToNeighbours(info)
case _ => // nothing to do
}
}
...
whenUnhandled {
case Event(e, s) =>
log.warning("received unhandled request {} in state {}/{}", e, stateName, s)
stay()
}
}
Conclusione
Spero che questo primo articolo abbia suscitato la tua curiosità sul calcolo distribuito. La strada fuori dalla Contea è impegnativa, ma porterà molte soddisfazioni, accompagnate da un pizzico di spirito d’avventura.
Rimani sintonizzato per il prossimo articolo, in cui esploreremo argomenti come il costo del tempo o il numero di messaggi, oltre a fornire alcuni esempi pratici con Akka.
Hai domande sul calcolo distribuito? Lasciaci un commento. Oppure facci sapere quali argomenti ti piacerebbe approfondire.
Riferimenti
- akka.io
- Design and Analysis of distributed algorithms – Nicola Santoro – Published by John Wiley & Sons, Inc., Hoboken, New Jersey 2007
- Bing Ai
