Spanner è un database a elevata coerenza, distribuito e scalabile creato da Google per supportare alcune delle applicazioni più critiche di Google. Prende le idee di base delle community di database e sistemi distribuiti e le espande in nuovi modi. Spanner espone questo servizio Spanner interno come servizio pubblico disponibile su Google Cloud Platform.
Perché Spanner deve gestire i impegnativi requisiti di uptime e scalabilità imposti dalle applicazioni aziendali critiche di Google, abbiamo creato Spanner da zero essere un database ampiamente distribuito: il servizio può estendersi su più macchine tra più data center e regioni. Sfruttiamo questa distribuzione per gestire set di dati e carichi di lavoro enormi, mantenendo al contempo una disponibilità molto elevata. Inoltre, volevamo che Spanner fornisse le stesse garanzie di coerenza rigorosa offerte da altri database di livello enterprise, perché volevamo creare un'esperienza ottimale per gli sviluppatori. È molto più facile ragionare e scrivere software per un database che supporta la coerenza forte rispetto a un database che supporta solo la coerenza a livello di riga, la coerenza a livello di entità o non offre affatto garanzie di coerenza.
In questo documento descriviamo in dettaglio il funzionamento delle scritture e delle letture in Spanner e il modo in cui Spanner garantisce un'elevata coerenza.
Punti di partenza
Alcuni set di dati sono troppo grandi per essere inseriti in un'unica macchina. Esistono anche scenari in cui il set di dati è piccolo, ma il carico di lavoro è troppo elevato per essere gestito da un'unica macchina. Ciò significa che dobbiamo trovare un modo per suddividere i dati in parti separate che possono essere archiviate su più macchine. Il nostro approccio consiste nel partizionare le tabelle di database in intervalli di chiavi contigui denominati split. Un singolo di una macchina virtuale può gestire più suddivisioni ed è disponibile un servizio di ricerca rapida determinare le macchine che gestiscono un determinato intervallo di chiavi. I dettagli su come vengono suddivisi i dati e su quali macchine si trovano sono trasparenti per gli utenti di Spanner. Il risultato è un sistema in grado di fornire latenze ridotte sia per le letture che per le scritture, anche sotto carichi di lavoro elevati, su larga scala.
Vogliamo inoltre assicurarci che i dati siano accessibili nonostante gli errori. Per garantire In questo modo, replichiamo ogni suddivisione su più macchine in domini di errore distinti. La replica coerente alle diverse copie della suddivisione è gestita dall'algoritmo Paxos. A Paxos, a condizione che la maggioranza delle repliche di voto dei divisi, una di queste repliche può essere eletta leader per elaborare le scritture e consentire ad altre repliche di gestire le letture.
Spanner fornisce sia transazioni di sola lettura sia transazioni di lettura/scrittura. Le prime sono il tipo di transazione preferito per le operazioni
(incluse le istruzioni SQL SELECT) che non modificano i dati. Le transazioni di sola lettura continuano a fornire una coerenza elevata e, per impostazione predefinita, operano sulla copia più recente dei dati. ma possono essere eseguiti senza bisogno di moduli
blocco interno, che li rende più veloci e scalabili. Lettura/scrittura
vengono utilizzate per transazioni che inseriscono, aggiornano o eliminano dati; questo
include le transazioni che eseguono letture seguite da una scrittura. Sono ancora
a scalabilità elevata, ma le transazioni di lettura/scrittura introducono un blocco e devono essere
orchestrate dai leader di Paxos. Tieni presente che il blocco è trasparente per Spanner
clienti.
Molti sistemi di database distribuiti precedenti hanno scelto di non fornire forti garanzie di coerenza a causa della costosa comunicazione tra macchine solitamente richiesta. Spanner è in grado di fornire snapshot a elevata coerenza
nell'intero database utilizzando una tecnologia sviluppata da Google
chiamato TrueTime. Come il condensatore di flusso in una macchina del tempo di circa il 1985, TrueTime è ciò che rende possibile Spanner. Si tratta di un'API che consente a qualsiasi macchina nei data center di Google di conoscere l'ora globale esatta con un elevato grado di precisione (ovvero entro pochi millisecondi). In questo modo, diverse macchine Spanner possono ragionare sull'ordine delle operazioni di transazione (e fare in modo che l'ordine corrisponda a quello osservato dal cliente), spesso senza alcuna comunicazione. Google ha dovuto dotare i suoi data center di hardware speciale
(orologi atomici!) per far funzionare TrueTime. La precisione temporale risultante
e la precisione è molto più elevata di quella ottenibile con altri protocolli (come
NTP). In particolare, Spanner assegna un timestamp a tutte le letture e scritture. R
la transazione al timestamp T1 dovrebbe riflettere i risultati di tutte le scritture
che si sono verificati prima del giorno T1. Se una macchina vuole soddisfare una lettura in T2, deve assicurarsi che la sua visualizzazione dei dati sia aggiornata almeno fino al giorno T2. Poiché
di TrueTime, questa determinazione è solitamente molto economica. I protocolli per garantire la coerenza dei dati sono complicati, ma sono trattati più nel documento originale su Spanner e in questo documento su Spanner e sulla coerenza.
Esempio pratico
Vediamo alcuni esempi pratici per capire come funziona:
CREATE TABLE ExampleTable (
Id INT64 NOT NULL,
Value STRING(MAX),
) PRIMARY KEY(Id);
In questo esempio, abbiamo una tabella con una chiave primaria di tipo intero semplice.
| Suddividi | KeyRange |
|---|---|
| 0 | [-∞,3) |
| 1 | [3224) |
| 2 | [224.712) |
| 3 | [712.717) |
| 4 | [717.1265) |
| 5 | [1265.1724) |
| 6 | [1724,1997) |
| 7 | [1997,2456) |
| 8 | [2456,∞) |
Dato lo schema di ExampleTable riportato sopra, lo spazio delle chiavi principali è suddiviso in split. Ad esempio: se è presente una riga in ExampleTable con un valore Id di
3700, sarà disponibile nella suddivisione 8. Come spiegato in precedenza, la suddivisione 8 stessa viene replicata
su più macchine.
In questo esempio di istanza Spanner, il cliente ha cinque nodi e l'istanza è replicata in tre zone. Le nove suddivisioni sono numerate da 0 a 8, con i leader di Paxos per ogni suddivisione in ombra. Le suddivisioni hanno anche repliche ciascuna zona (leggermente ombreggiata). La distribuzione delle suddivisioni tra i nodi può essere diversi in ogni zona, e i leader di Paxos non risiedono tutti nella stessa zona zona di destinazione. Questa flessibilità consente a Spanner di essere più robusto per determinati tipi di profili di carico e modalità di errore.
Scrittura con suddivisione singola
Supponiamo che il cliente voglia inserire una nuova riga (7, "Seven")
ExampleTable.
- Il livello API cerca la suddivisione proprietaria dell'intervallo di chiavi contenente
7. Risiede in Particella 1. - Il livello API invia la richiesta di scrittura al leader del gruppo 1.
- Il leader avvia una transazione.
- Il leader tenta di ottenere un blocco di scrittura sulla riga
Id=7. Si tratta di un'operazione locale. Se un'altra transazione di lettura/scrittura concorrente sta attualmente leggendo questa riga, l'altra transazione ha un blocco di lettura e la transazione corrente si blocca finché non riesce ad acquisire il blocco di scrittura.- È possibile che la transazione A sia in attesa di un blocco detenuto dalla transazione B e che la transazione B sia in attesa di un blocco detenuto dalla transazione A. Poiché nessuna transazione rilascia un blocco finché non acquisisce tutti i blocchi, questo può portare a un deadlock. Spanner usa un comando "wound-wait" standard punto morto di prevenzione per assicurare l'avanzamento delle transazioni. In particolare, una transazione "più recente" attenderà un blocco detenuto da una transazione "più vecchia", ma una transazione "più vecchia" "interromperà" (abortirà) una transazione più recente che detiene un blocco richiesto dalla transazione precedente. Pertanto, non abbiamo mai cicli di deadlock di attendenti di blocco.
- Una volta acquisito il blocco, il leader assegna un timestamp alla transazione
basata su TrueTime.
- Questo timestamp garantisce essere maggiore di quello di qualsiasi timestamp precedente una transazione di commit che ha interessato i dati. In questo modo, l'ordine delle transazioni (come percepito dal cliente) corrisponde all'ordine delle modifiche ai dati.
- Il leader comunica alle repliche di Spalla 1 la transazione e il relativo timestamp. Una volta che la maggior parte di queste repliche ha archiviato la mutazione della transazione in un ambiente archiviazione (nel file system distribuito), la transazione viene eseguita. In questo modo, la transazione è recuperabile anche se si verifica un errore in una minoranza di macchine. (Le repliche non applicano ancora le mutazioni alla loro copia del data.)
Il leader attende fino a quando non riesce ad assicurarsi che il timestamp della transazione passati in tempo reale; questa operazione richiede in genere alcuni millisecondi attenderemo incertezze nel timestamp TrueTime. Questo è ciò che garantisce coerenza: una volta che il cliente ha appreso il risultato di una transazione, garantito che tutti gli altri lettori vedano gli effetti della transazione. Questa "attesa del commit" in genere si sovrappone alla comunicazione della replica nel passaggio precedente, pertanto il costo effettivo della latenza è minimo. Ulteriori dettagli sono descritti in questo documento.
Il leader risponde al cliente dicendo che la transazione è stata eseguendo il commit, segnalando facoltativamente il timestamp di commit della transazione.
Parallelamente a rispondere al cliente, vengono applicate le mutazioni della transazione ai dati.
- Il leader applica le mutazioni alla propria copia dei dati e poi libera i blocchi delle transazioni.
- Il leader informa anche le altre repliche di Divisione 1 di applicare la mutazione alle loro copie dei dati.
- Qualsiasi transazione di lettura/scrittura o di sola lettura che dovrebbe avere gli effetti di le mutazioni attendono l'applicazione delle mutazioni prima di tentare per leggere i dati. Per le transazioni di lettura/scrittura, questo viene applicato perché la transazione deve acquisire un blocco di lettura. Per le transazioni di sola lettura, in modo forzato confrontando il timestamp della lettura con quello dell'ultima e i dati di Google Cloud.
Tutto questo avviene generalmente in una manciata di millisecondi. Questa scrittura è il tipo di scrittura più economica eseguita da Spanner, poiché è coinvolta una singola suddivisione.
Scrittura con più suddivisioni
Se sono coinvolte più suddivisioni, è necessario un livello aggiuntivo di coordinamento (utilizzando l'algoritmo di commit in due fasi standard).
Supponiamo che la tabella contenga quattromila righe:
| 1 | "uno" |
| 2 | "due" |
| … | … |
| 4000 | "quattromila" |
Supponiamo che il cliente voglia leggere il valore della riga 1000 e scrivere un valore nelle righe 2000, 3000 e 4000 all'interno di una transazione. Verrà eseguito
all'interno di una transazione di lettura/scrittura come segue:
- Il client avvia una transazione di lettura/scrittura, t.
- Il client invia una richiesta di lettura per la riga 1000 al livello API e la tagga come parte di t.
- Il livello API cerca la suddivisione che possiede la chiave
1000. Si trova in Split 4. Il livello API invia una richiesta di lettura al leader del gruppo 4 e la contrassegna come parte di t.
Il leader di Divisione 4 tenta di ottenere un blocco di lettura sulla riga
Id=1000. Questo è un'operazione locale. Se un'altra transazione in parallelo ha un blocco di scrittura su la transazione corrente si blocca finché non riesce ad acquisire il blocco. Tuttavia, questo blocco di lettura non impedisce ad altre transazioni di ottenere blocchi di lettura.- Come nel caso di una singola partizione, il deadlock viene evitato tramite "attesa con ritardo".
Il leader cerca il valore di
Id1000("Migliaia") e restituisce il valore letto il risultato al client.
Più tardi…Il client invia una richiesta di commit per la transazione t. Questa richiesta di commit contiene 3 mutazioni: (
[2000, "Dos Mil"],[3000, "Tres Mil"]e[4000, "Quatro Mil"]).- Tutte le suddivisioni coinvolte in una transazione diventano partecipanti in
la transazione. In questo caso, il split 4 (che ha eseguito la lettura per la chiave
1000), il split 7 (che gestirà la mutazione per la chiave2000) e il split 8 (che gestirà le mutazioni per le chiavi3000e4000) sono partecipanti.
- Tutte le suddivisioni coinvolte in una transazione diventano partecipanti in
la transazione. In questo caso, il split 4 (che ha eseguito la lettura per la chiave
Un partecipante diventa il coordinatore. In questo caso forse il leader La divisione 7 diventa il coordinatore. Il compito del coordinatore è assicurarsi che la transazione venga eseguita o interrotta in modo atomico su tutti i partecipanti. In altre parole, non verrà eseguito il commit per un partecipante e l'interruzione per un altro.
- Il lavoro svolto dai partecipanti e dai coordinatori viene in realtà svolto le macchine principali di queste divisioni.
I partecipanti acquisiscono delle serrature. Questa è la prima fase dell'commit a due fasi.
- La suddivisione 7 acquisisce un blocco di scrittura sulla chiave
2000. - La suddivisione 8 acquisisce un blocco di scrittura sulla chiave
3000e sulla chiave4000. - La suddivisione 4 verifica che sia ancora un blocco di lettura sulla chiave
1000(in altre parole, che la serratura non è stata persa a causa di un arresto anomalo o della ferita di attesa algorithm.) - Ogni partecipante suddivide i propri set di chiavi replicandoli su almeno la maggior parte delle repliche suddivise. In questo modo, le chiavi possono rimanere bloccate anche in caso di errori del server.
- Se tutti i partecipanti comunicano al coordinatore che i loro i blocchi vengono trattenuti, quindi può essere eseguito il commit della transazione complessiva. In questo modo, esiste un punto in cui tutte le chiavi necessarie per la transazione sono tratte e questo punto diventa il punto di commit della transazione, in modo da poter ordinare correttamente gli effetti di questa transazione rispetto alle altre transazioni che si sono verificate prima o dopo.
- È possibile che i blocchi non possano essere acquisiti (ad esempio, se scopriamo potrebbe esserci un deadlock tramite l'algoritmo wound-wait). Se un partecipante afferma di non poter eseguire il commit della transazione, l'intera transazione viene interrotta.
- La suddivisione 7 acquisisce un blocco di scrittura sulla chiave
Se tutti i partecipanti, e il coordinatore, acquisiscono correttamente i blocchi, Il coordinatore (divisione 7) decide di eseguire il commit della transazione. Assegna un timestamp alla transazione in base a TrueTime.
- Questa decisione sull'impegno, così come le mutazioni per la chiave
2000, sono replicati ai membri di Split 7. Una volta che la maggior parte delle repliche di Split 7 registra la decisione di commit nello spazio di archiviazione stabile, la transazione viene committata.
- Questa decisione sull'impegno, così come le mutazioni per la chiave
Il Coordinatore comunica l'esito della transazione a tutti i partecipanti. Questa è la seconda fase del commit in due fasi.
- Ogni leader del partecipante esegue la replica della decisione di commit alle repliche della suddivisione del partecipante.
Se la transazione è impegnata, il Coordinatore e tutti i Partecipanti e applicare le mutazioni ai dati.
- Come nel caso di una singola suddivisione, i lettori successivi dei dati presso il coordinatore oppure i partecipanti devono attendere che i dati vengano applicati.
Il responsabile del coordinatore risponde al cliente dicendo che la transazione è è stato eseguito il commit, facoltativamente restituendo il timestamp di commit della transazione
- Come nel caso di suddivisione singola, il risultato viene comunicato al cliente dopo un'attesa per il commit, per garantire un'elevata coerenza.
Tutto questo avviene in genere in pochi millisecondi, anche se in genere è poche volte in più rispetto alla suddivisione singola a causa della suddivisione incrociata extra per il coordinamento.
Lettura efficace (multi-split)
Supponiamo che il client voglia leggere tutte le righe in cui Id >= 0 e Id < 700
di una transazione di sola lettura.
- Il livello API cerca le suddivisioni che possiedono le chiavi nell'intervallo
[0, 700). Queste righe sono di proprietà di Suddivisione 0, Suddivisione 1 e Suddivisione 2. - Poiché si tratta di una lettura affidabile su più macchine, il livello API sceglie il timestamp di lettura utilizzando il TrueTime corrente. In questo modo, entrambe le letture
restituiranno i dati della stessa istantanea del database.
- Anche altri tipi di letture, ad esempio le letture inattive, scelgono un timestamp da leggere alle (ma il timestamp potrebbe essere nel passato).
- Il livello API invia la richiesta di lettura a una replica di Split 0, ad alcune repliche Split 1 e alcune repliche di Split 2. Include anche il timestamp di lettura selezionato nel passaggio precedente.
Per letture efficaci, la replica di gestione di solito invia una RPC al leader per chiedi il timestamp dell'ultima transazione da applicare e la lettura può procedere dopo l'applicazione della transazione. Se la replica è il leader o stabilisce di essere sufficientemente aggiornata per soddisfare la richiesta dal suo stato interno e da TrueTime, esegue direttamente la lettura.
I risultati delle repliche vengono combinati e restituiti al client (tramite il livello API).
Tieni presente che le letture non acquisiscono alcun blocco nelle transazioni di sola lettura. Poiché le letture possono essere potenzialmente fornite da qualsiasi replica aggiornata di una determinata suddivisione, la velocità effettiva di lettura del sistema è potenzialmente molto elevata. Se il client è in grado di tollerare letture non aggiornate da almeno dieci secondi, il throughput di lettura può essere ancora più elevato. Poiché in genere il leader aggiorna le repliche con l'ultimo timestamp sicuro ogni dieci secondi, le letture con un timestamp obsoleto possono evitare un RPC aggiuntivo al leader.
Conclusione
Tradizionalmente, i progettisti di sistemi di database distribuiti hanno scoperto che forti le garanzie transazionali sono costose, dato l'insieme la comunicazione richiesta. Con Spanner, ci siamo concentrati sulla riduzione del costo delle transazioni per renderle possibili su larga scala e nonostante la distribuzione. Un motivo principale per cui funziona è TrueTime, che riduce comunicazione per molti tipi di coordinamento. Inoltre, un'attenta progettazione e ottimizzazione delle prestazioni ha dato vita a un sistema altamente performante, offrendo al contempo solide garanzie. In Google abbiamo riscontrato che questo ha semplificato notevolmente lo sviluppo di applicazioni su Spanner rispetto ad altri sistemi di database con garanzie meno stringenti. Quando gli sviluppatori di applicazioni non devono preoccuparsi di condizioni di gara o incoerenze nei dati, possono concentrarsi su ciò che conta davvero: creare e rilasciare un'applicazione eccezionale.