Elezione dei leader nei sistemi distribuiti

L’elezione del leader prevede l’assegnazione di poteri speciali a una cosa (un processo, un host, un thread, un oggetto o un essere umano) in un sistema distribuito. Tali poteri speciali possono includere la capacità di assegnare lavoro, la capacità di modificare un dato o anche la responsabilità di gestire tutte le richieste nel sistema.

L’elezione dei leader è un potente strumento per migliorare l’efficienza, ridurre il coordinamento, semplificare le architetture e ridurre le operazioni. D’altra parte, l’elezione dei leader può introdurre nuove modalità di errore e colli di bottiglia nel dimensionamento. Inoltre, l'elezione dei leader può rendere più difficile valutare la correttezza di un sistema.

A causa di queste complicazioni, prima di implementare l'elezione dei leader, consideriamo attentamente altre opzioni. Per l'elaborazione dei dati e i flussi di lavoro, servizi di flussi di lavoro come AWS Step Functions possono ottenere molti degli stessi vantaggi dell’elezione del leader ed evitare molti dei relativi rischi. Per altri sistemi, spesso implementiamo gli idempotenti API, il blocco ottimistico e altri modelli che rendono superfluo un unico leader.

In questo articolo, esamino alcuni dei pro e dei contro dell’elezione dei leader in generale e dell’approccio di Amazon all’elezione dei leader nei nostri sistemi distribuiti, comprese le informazioni sugli errori del leader.

Esistono molti modi per eleggere un leader, dagli algoritmi come Paxos, al software come Apache ZooKeeper, all’hardware personalizzato ai lease. I lease sono il meccanismo di elezione dei leader più utilizzato in Amazon. Essi sono relativamente semplici da capire e da implementare e offrono una tolleranza ai guasti incorporata. I lease funzionano in base a un unico database che memorizza il leader corrente. In seguito, il lease richiede l’heartbeat del leader a intervalli regolari per dimostrare che è ancora il leader. Se il leader esistente non emette l’heartbeat dopo un certo lasso di tempo, altri candidati leader possono provare a subentrare.

Evitiamo di dipendere dal tempo nei sistemi distribuiti, anche con la grande funzione di sincronizzazione del tempo in Amazon Elastic Compute Cloud (Amazon EC2). È difficile garantire che i clock di sistema in un cluster siano sufficientemente sincronizzati per consentire di dipendere da tale sincronizzazione nell’ordinare o coordinare le operazioni distribuite. In Amazon, i sistemi distribuiti utilizzano il tempo solo per il consumo umano. I lease dipendono dal tempo. Tuttavia, essi dipendono solo dalla durata del tempo locale trascorso piuttosto che da un tempo di wall-clock che è sincronizzato e deve essere approvato da più server.

Il codice sorgente del client lock DynamoDB offre esempi e dettagli relativi all’elezione del leader. Tuttavia è emerso che, sebbene i lease e i lock siano concettualmente semplici, la corretta implementazione può essere discreta. Le implementazioni richiedono la comprensione di come un server stia misurando la durata dell’ora locale. Ad esempio, se un server o una libreria che misura il tempo ritenesse che il tempo saltasse di quando in quando all’indietro, distruggerebbe le ipotesi sulla durata del tempo incorporata nei lease. Le durate evitano i problemi di sincronizzazione globale del clock che fanno sì che i server non si accordino più sull’ora, dai secondi saltati al clock locale che si sposta nel corso del tempo a causa dell’elevato utilizzo prolungato della CPU.

Un problema più ampio per i lease, e tutti i tipi di lock distribuiti, è assicurarsi che il leader lavori solo mentre è in possesso del lock. Garantire che il leader sia in possesso del lock è in realtà abbastanza difficile. Abbiamo ritenuto importante assicurare che un leader su una rete lenta o con perdita dei dati non ritenga di poter tenere chiusi i lock più a lungo di quanto non riesca in realtà. Allo stesso modo, le pause di garbage collection tra un lock verificato e il lavoro svolto possono portare a un comportamento errato. In pratica, l’irrigidimento a fronte di questi problemi è spesso la sfida maggiore.

DynamoDB e ZooKeeper offrono semplici client di chiusura basati su lease che forniscono un’elezione del leader con tolleranza ai guasti. A meno che non vi siano esigenze particolari, preferiamo questi client perché riteniamo che forniscano il modo più semplice e collaudato per implementare l’elezione del leader. I team di Amazon preferiscono evitare di creare un’implementazione personalizzata di elezione dei leader. Privilegiamo invece i client esistenti che sono ben collaudati e resistenti sul campo.

L’elezione dei leader è un modello ampiamente diffuso in tutta Amazon. Ad esempio:

• Quasi tutti i sistemi che utilizzano sistemi di gestione tradizionali con database relazionali (RDBMS) si affidano all’elezione dei leader per scegliere un database leader che gestisca tutte le scritture e talvolta tutte le letture. In questi sistemi, l’elezione può essere automatizzata, ma spesso viene fatta manualmente da un operatore umano.
• Amazon EBS distribuisce letture e scritture per un volume su molti server di archiviazione. Per assicurare la consistenza, utilizza l'elezione dei leader per eleggere le istanze primarie in ogni area del volume che ordina le letture e le scritture. Se l'istanza primaria non va a buon fine, le copie follower agiscono utilizzando lo stesso meccanismo di elezione dei leader. In Amazon EBS, l’elezione dei leader garantisce l’uniformità, migliorando al contempo le prestazioni evitando il coordinamento sul piano dati. DynamoDB, Amazon Quantum Ledger Database (Amazon QLDB) e Amazon Kinesis (Kinesis) utilizzano approcci simili per la stessa ragione.
• La Kinesis Client Library (KCL) utilizza i lease per garantire che ogni partizione di Kinesis sia elaborata da un solo proprietario, rendendo semplice l’elaborazione di ricalibrazione dei flussi Kinesis.

Un’altra cosa a cui pensare attentamente è cosa succede al lavoro di un leader quando restituisce un errore. Se un leader restituisce un errore durante un’attività, come fa il nuovo leader a completare l’attività? Se un leader restituisce un errore prima di rendere il suo lavoro duraturo, il sistema è comunque corretto? Molti tipi di sistemi hanno fasi distinte di “rendere il lavoro duraturo” e “dire agli altri che è completo”. In Amazon, i nostri sistemi fanno sempre il primo prima del secondo (o tollerano la perdita di dati). Anche in questo caso, l’idempotenza è utile. Permette al nuovo leader di riorientare con fiducia il lavoro che il leader uscente può avere completato interamente o parzialmente ma di cui non ha parlato ad altri.

Per tollerare i guasti, i sistemi distribuiti di Amazon non hanno un unico leader. La leadership è invece una proprietà che passa da server a server, o da un processo all’altro. Nei sistemi distribuiti, non è possibile garantire che ci sia esattamente un leader nel sistema. Invece, ci può essere per lo più un leader, e ci possono essere zero leader o due leader durante i guasti.

La modalità di scelta del comportamento del sistema in caso di errore del leader dipende da ciò che accade in un sistema quando vi sono due leader. I sistemi che eseguono un lavoro idempotente possono spesso tollerare due leader con una minima perdita di efficienza. Con due leader, i sistemi possono raggiungere una maggiore disponibilità e scegliere approcci all’elezione dei leader più deboli.

I sistemi che richiedono assolutamente al massimo un leader sono più difficili da costruire rispetto ai sistemi con più leader. Il sistema di elezione dei leader deve essere sempre corretto e uniforme. Inoltre, deve garantire che il leader uscente sia deposto prima che venga eletto un nuovo leader, il che è più difficile di quanto sembri. Nei sistemi distribuiti, è spesso difficile sapere se un sistema ha subito un guasto o se sta semplicemente continuando a lavorare in qualche altra partizione di rete. In Amazon, ci assicuriamo che qualsiasi sistema scelto dal leader si occupi di questo caso limite.

In Amazon, adottiamo queste best practice per l’elezione dei leader:

• Controlla frequentemente la durata residua del lease (o lo stato di lock in generale), soprattutto prima di iniziare qualsiasi operazione che abbia effetti collaterali al di là del leader stesso.
• Rete lenta, timeout, nuovi tentativi e pause per la garbage collection possono causare la scadenza del tempo residuo del lease prima che il codice lo preveda.
• Evitare i lease con heartbeat in un thread in background. Questo può causare problemi di correttezza se il thread non può interrompere il codice alla scadenza del lease o se il thread con heartbeat si estingue. Possono verificarsi problemi di disponibilità se il thread di lavoro si estingue o si arresta mentre il thread con heartbeat si attacca al lease.
• Avere parametri affidabili che mostrano quanto lavoro un leader può fare rispetto a quanto sta facendo attualmente. Rivedere spesso questi parametri e assicurarsi che esistano piani per il dimensionamento prima che la capacità si esaurisca.
• Rendere più facile individuare quale host sia l’attuale leader e quale host è stato il leader in un dato momento. Tenere un audit trail o un log dei cambiamenti di leadership.
• Modellare e verificare formalmente la correttezza degli algoritmi distribuiti utilizzando strumenti come TLA+. In tal modo si colgono bug discreti, difficili da osservare e rari che possono insinuarsi quando un’applicazione presuppone troppo sulle garanzie fornite dal protocollo di elezione dei leader.

L’elezione dei leader è un potente strumento utilizzato nei sistemi in tutta Amazon per aiutare a rendere i nostri sistemi più facili da usare e tolleranti ai guasti. Tuttavia, quando usiamo l’elezione dei leader, stiamo attenti a considerare le garanzie che ogni protocollo di elezione dei leader fornisce e, cosa più importante, non fornisce.

I sistemi Amazon spesso utilizzano l’elezione dei leader per assicurarsi che ci sia una tolleranza ai guasti incorporata. Quando i sistemi utilizzano l’elezione dei leader per garantire che almeno un server stia elaborando un compito, utilizzano meccanismi separati per mantenere la correttezza a fronte di più leader simultanei. Per esempio, potrebbero utilizzare un database sottostante per assicurarsi che se due leader pensano di essere entrambi in possesso di un lease, non interferiscano tra loro. Anziché fare ipotesi sulle garanzie fornite dall’implementazione di un lease, ci concentriamo sulla correttezza di questi sistemi, spesso con la modellazione con tecniche come TLA+.

Nonostante le sue sfumature, l’elezione dei leader rimane uno strumento utile nel nostro kit di strumenti per sistemi distribuiti in Amazon, insieme a modelli come idempotenza e lock ottimistico.

Per ulteriori informazioni su come funzionano i lease, vedere:

• Come eseguire il lock distribuito
• Burrows, The Chubby lock service for loosely-coupled distributed systems
• Gray e Cheriton, Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency