Spanner è un database a elevata coerenza, distribuito e scalabile creato da Google per supportare alcune delle applicazioni più critiche di Google. Richiede core di idee dalle community di database e sistemi distribuiti ed espande su di esse in modi nuovi. Spanner espone questo servizio Spanner interno come servizio pubblico sulla 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 e carichi di lavoro enormi, pur mantenendo una disponibilità molto elevata. Me ha permesso a Spanner di fornire le stesse garanzie di coerenza rigorosa forniti da altri database di livello aziendale, perché volevamo creare un'ottima esperienza per gli sviluppatori. È molto più facile ragionare e scrivere software per un database che supporta un'elevata coerenza rispetto a un database che supporta solo la coerenza a livello di riga, la coerenza a livello di entità o che non 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 una singola macchina. Esistono anche se il set di dati è ridotto, ma il carico di lavoro è troppo impegnativo da gestire. Ciò significa che dobbiamo trovare un modo per suddividere i nostri dati in parti separate che possono essere archiviate su più macchine. Il nostro approccio è le tabelle di database in intervalli di chiavi contigui denominati suddivisioni. 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 di come i dati è suddiviso e le macchine su cui risiede sono trasparenti per gli utenti di Spanner. La il risultato è un sistema in grado di fornire basse latenze sia per le letture che per le scritture, anche con carichi di lavoro gravosi, 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 nelle diverse copie della suddivisione è gestita 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 transazioni di sola lettura e lettura/scrittura
transazioni. Le prime sono il tipo di transazione preferito per le operazioni
(incluse le istruzioni SQL SELECT) che non modificano i dati. Sola lettura
continuano a garantire elevata coerenza e operano, per impostazione predefinita, sul
copia più recente dei tuoi dati. ma possono essere eseguiti senza la necessità di alcun modulo
blocco interno, il che le rende più rapide 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 precedenti sistemi di database distribuiti hanno scelto di non fornire
garantire una maggiore coerenza grazie alla costosa comunicazione tra macchine
solitamente richiesto. 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 un periodo del 1985 circa
TrueTime è ciò che rende possibile Spanner. Si tratta di un'API che consente
qualsiasi macchina nei data center Google per conoscere l'ora globale esatta con
grado di precisione (ossia entro pochi millisecondi). Ciò consente diverse
Spanner per ragionare sull'ordine delle operazioni transazionali (e
l'ordinamento corrisponda a quanto osservato dal cliente) spesso senza
la 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 alle ore T2, deve
assicurarsi che la 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 è complicata, ma ne viene parlato più diffusamente
il documento originale di Spanner e
questo articolo su Spanner e 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 per ExampleTable sopra, lo spazio della chiave primaria è partizionato
in suddivisioni. 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 viene replicato in tre zone. Le nove suddivisioni sono numerate da 0 a 8, con Paxos leader per ogni divisione con un'ombra scura. 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à aiuta Spanner a essere più robusto per determinati tipi di carico profili e modalità di errore.
Scrittura a 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. it vive in Split 1. - Il livello API invia la richiesta di scrittura al leader di suddivisione 1.
- Il leader avvia una transazione.
- Il leader tenta di ottenere un blocco di scrittura nella riga
Id=7. Si tratta di un dell'attività locale. Se al momento è in corso un'altra transazione di lettura/scrittura in contemporanea leggendo questa riga, l'altra transazione presenta un blocco di lettura e le transazioni attuali vengono bloccate fino a quando non riesce ad acquisire il blocco di scrittura.- È possibile che la transazione A sia in attesa di un blocco trattenuto da La transazione B e la transazione B sono in attesa di un blocco trattenuto dalla transazione R. Poiché nessuna transazione rilascia alcun blocco finché non viene acquisito 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. Nel particolare, un "più giovane" transazione attenderà un blocco trattenuto da un utente "meno recente" transazione, ma una data "precedente" transazione "avrà" (interrompere) un giovane transazione con un blocco richiesto dalla transazione precedente. Pertanto, non ci sono mai cicli di stallo dei camerieri della serratura.
- 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. Questo è ciò che assicura che delle transazioni (come percepito dal cliente) corrisponde all'ordine delle modifiche ai dati.
- Il leader comunica alle repliche di suddivisione 1 della transazione e del 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. Ciò garantisce che la transazione è recuperabile, anche se si verifica un errore in una minoranza di machine learning. (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. Questo "impegnati in attesa" in genere si sovrappone alla comunicazione della replica nel passaggio sopra, quindi il costo effettivo della latenza è minimo. In questa sezione verranno trattati ulteriori dettagli 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 e rilascia 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, viene applicato in modo forzato perché la transazione deve avere 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 più economico di scrittura eseguito da Spanner, poiché è coinvolta una singola suddivisione.
Scrittura su più suddivisioni
Se sono presenti più suddivisioni, è disponibile un ulteriore livello di coordinamento (utilizzando l'algoritmo di commit standard in due fasi) è necessario.
Supponiamo che la tabella contenga quattromila righe:
| 1 | "uno" |
| 2 | "due" |
| … | … |
| 4000 | "quattromila" |
Supponiamo che il client voglia leggere il valore della riga 1000 e scrivere una
alle righe 2000, 3000 e 4000 all'interno di una transazione. Questo sarà
eseguita 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 di suddivisione 4 e la tagga come parte di t.
Il leader di suddivisione 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 split singolo, il deadlock viene evitato tramite "wound-wait".
Il leader cerca il valore di
Id1000("Migliaia") e restituisce il valore letto il risultato al client.
Dopo...Il client emette una richiesta 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, Split 4 (che ha fornito la lettura per la chiave
1000), Dividi 7 (che gestirà la mutazione della chiave2000) e Dividi 8 (che gestirà le mutazioni per la chiave3000e la chiave4000) sono partecipanti.
- Tutte le suddivisioni coinvolte in una transazione diventano partecipanti in
la transazione. In questo caso, Split 4 (che ha fornito 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 è garantire che la transazione viene eseguita o si interrompe atomicamente su tutti i partecipanti. Questo non si impegna in un partecipante e si interrompe in un altro.
- Il lavoro svolto dai partecipanti e dai coordinatori viene in realtà svolto le macchine principali di queste divisioni.
I partecipanti acquisiscono blocchi. Questa è la prima fase del commit in 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 suddivisione di partecipanti registra il proprio insieme di blocchi replicandoli su almeno in base alla maggior parte delle repliche divise. In questo modo le serrature possono rimanere 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. Questo assicura è un momento in cui tutti i blocchi necessari per la transazione trattenute e questo momento diventa il punto di commit della transazione, assicurandoci di poter ordinare correttamente gli effetti di questa transazione altre transazioni precedenti o successive.
- È possibile che i blocchi non possano essere acquisiti (ad esempio, se scopriamo potrebbe esserci un deadlock tramite l'algoritmo wound-wait). Se uno o più partecipanti indica che non è possibile 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 di commit, così come le mutazioni per la chiave
2000, sono replicati ai membri di Split 7. Una volta che la maggioranza di Split 7 di repliche registrano la decisione di commit in uno spazio di archiviazione stabile, la transazione viene impegnato.
- Questa decisione di commit, così come le mutazioni per la chiave
Il coordinatore comunica il risultato della transazione a tutti i Partecipanti. Questa è la seconda fase del commit in due fasi.
- Ogni partecipante leader replica la decisione di impegno nelle repliche dalla suddivisione dei partecipanti.
Se la transazione è impegnata, il Coordinatore e tutti i Partecipanti e applicare le mutazioni ai dati.
- Come nel caso di suddivisione singola, 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 elevata (multi-diviso)
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 proprietarie di chiavi nell'intervallo
[0, 700). Queste righe sono di proprietà di Dividi 0, Dividi 1 e Dividi 2. - Poiché si tratta di una lettura efficace su più macchine, il livello API seleziona
di lettura del timestamp usando il valore TrueTime attuale. Questo assicura che entrambe le letture
restituiscono i dati dallo stesso snapshot 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 Dividi 1 e alcune repliche di Dividi 2. Include anche il read-timestamp che ha selezionata 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 è leader o determina di aver raggiunto la soglia necessaria per soddisfare la richiesta e TrueTime, quindi pubblica 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 cliente è in grado di tollera letture inattive per almeno dieci secondi, la velocità effettiva di lettura può essere in alto. Poiché il leader in genere aggiorna le repliche con gli ultimi ogni dieci secondi, legge a un timestamp inattivo può evitare 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 delle transazioni in modo da renderle realizzabili su larga scala e nonostante distribuzione dei contenuti. Un motivo principale per cui funziona è TrueTime, che riduce comunicazione per molti tipi di coordinamento. Oltre a questo, un'attenta progettazione e l'ottimizzazione delle prestazioni ha portato a un sistema ad alte prestazioni fornendo al contempo solide garanzie. In Google, abbiamo riscontrato che ce l'abbiamo fatta molto più facile sviluppare applicazioni su Spanner rispetto ad altre sistemi di database con garanzie più basse. Quando gli sviluppatori di applicazioni non devono preoccuparsi delle condizioni di gara o delle incongruenze nei dati, possono concentrarsi agli interessi principali, ovvero la creazione e la distribuzione di una fantastica applicazione.