Durata delle letture e delle scritture di Spanner

Spanner è un database altamente coerente, distribuito e scalabile creato dagli ingegneri di Google per supportare alcune delle applicazioni più importanti di Google. Prende le idee fondamentali delle community di database e sistemi distribuiti e le espande in nuovi modi. Spanner espone questo servizio Spanner interno come servizio disponibile pubblicamente sulla Google Cloud Platform.

Poiché Spanner deve gestire gli elevati requisiti di uptime e scalabilità imposti dalle applicazioni aziendali fondamentali di Google, abbiamo creato Spanner fin dall'inizio per essere un database ampiamente distribuito, in cui il servizio può includere più macchine, più data center e regioni. Sfruttiamo questa distribuzione per gestire enormi set di dati ed enormi carichi di lavoro, pur mantenendo un'altissima disponibilità. Volevamo inoltre che Spanner fornisse le stesse rigorose garanzie di coerenza fornite da altri database di livello aziendale, perché volevamo creare un'esperienza eccellente per gli sviluppatori. È molto più facile ragionare e scrivere un 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 non ha alcuna garanzia di coerenza.

In questo documento, viene descritto in dettaglio come funzionano le scritture e le letture in Spanner e in che modo Spanner garantisce un'elevata coerenza.

Punti di partenza

Alcuni set di dati sono troppo grandi per essere inseriti in un'unica macchina. Ci sono anche scenari in cui il set di dati è piccolo, ma il carico di lavoro è troppo pesante per essere gestito da una sola macchina. Ciò significa che dobbiamo trovare un modo per suddividere i dati in parti separate che possano essere archiviate su più macchine. Il nostro approccio consiste nel partizionare le tabelle di database in intervalli di chiavi contigui chiamati suddivisioni. Una singola macchina può gestire più suddivisioni ed è disponibile un servizio di ricerca rapida per determinare le macchine che gestiscono un determinato intervallo di chiavi. I dettagli di 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 basse sia per le letture che per le scritture, anche in presenza di carichi di lavoro impegnativi, su larga scala.

Vogliamo inoltre assicurarci che i dati siano accessibili nonostante gli errori. Per garantire ciò, replichiamo ogni suddivisione su più macchine in domini in errore distinti. Una replica coerente nelle diverse copie della suddivisione è gestita dall'algoritmo Paxos. In Paxos, a condizione che la maggior parte delle repliche di voto per la suddivisione sia attiva, 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. I primi 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 garantire un'elevata coerenza e operano, per impostazione predefinita, sulla copia più recente dei tuoi dati. Inoltre, possono funzionare senza bisogno di alcun blocco interno, il che li rende più rapidi e scalabili. Le transazioni di lettura/scrittura sono utilizzate per le transazioni che inseriscono, aggiornano o eliminano dati; sono incluse le transazioni che eseguono letture seguite da una scrittura. Sono comunque altamente scalabili, ma le transazioni di lettura-scrittura introducono il blocco e devono essere orchestrate dai leader di Paxos. Tieni presente che il blocco è trasparente per i client Spanner.

Molti precedenti sistemi di database distribuiti hanno scelto di non fornire solide garanzie di coerenza a causa della costosa comunicazione tra macchine solitamente necessaria. Spanner è in grado di fornire snapshot a elevata coerenza in tutto il database utilizzando una tecnologia sviluppata da Google chiamata TrueTime. Come il condensatore di flusso in una macchina del tempo del 1985 circa, TrueTime è ciò che rende possibile Spanner. Si tratta di un'API che consente a qualsiasi macchina nei data center 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'ordinamento delle operazioni transazionali (e fare in modo che l'ordinamento corrisponda a quello osservato dal client) spesso senza alcuna comunicazione. Google ha dovuto dotare i suoi data center di hardware speciale (orologi atomici!) per far funzionare TrueTime. La precisione e la precisione del tempo risultanti sono molto più elevate di quelle che si possono ottenere con altri protocolli (come NP). In particolare, Spanner assegna un timestamp a tutte le operazioni di lettura e scrittura. È garantito che una transazione al timestamp T1 rifletta i risultati di tutte le scritture avvenute prima del giorno T1. Se una macchina vuole soddisfare una lettura al minuto T2, deve assicurarsi che la propria visualizzazione dei dati sia aggiornata almeno fino a T2. A causa di TrueTime, questa determinazione è solitamente molto economica. I protocolli per garantire la coerenza dei dati sono complicati, ma ne vengono discussi più in dettaglio nell'articolo originale di Spanner e in questo documento su Spanner e coerenza.

A parte: file system distribuiti

Quando salvi un file sul tuo laptop, il file viene in genere scritto sul disco rigido del laptop. Ma cosa succede se si rompe il disco rigido? Perdi il file? Il tuo laptop riesce a salvare altri file (o persino essere utilizzato per qualsiasi cosa) finché il disco rigido non viene risolto? Questi sono alcuni dei problemi che i file system distribuiti provano a risolvere. Oltre dieci anni fa, Google ha creato un sistema denominato Google File System (GFS) che risolve alcuni di questi problemi. I file sono stati replicati su più macchine. Se una macchina non funzionasse, altre macchine sarebbero ancora disponibili per le operazioni di lettura e scrittura sul file. Abbiamo fatto molti progressi da GFS, ma il concetto fondamentale rimane lo stesso: l'archiviazione dei file è disaccoppiata dalle macchine che li creano, li leggono, li aggiornano ed eliminano. Ciò consente la creazione di sistemi più solidi; un singolo disco danneggiato non può causare la perdita o il danneggiamento dei dati. La combinazione della replica basata su Paxos di Spanner e della robustezza del file system distribuito sottostante, offre un'affidabilità dei dati estremamente buona.

Per garantire la durabilità delle scritture, le transazioni Spanner eseguono il commit scrivendo le mutazioni per almeno la maggior parte delle repliche degli split interessati. E le macchine che ospitano queste suddivisioni scrivono queste mutazioni in modo duraturo in un file system distribuito. Spanner è un'architettura "non condiviso" (che offre alta scalabilità), ma poiché qualsiasi server in un cluster può leggere da questo file system distribuito, possiamo recuperare rapidamente dagli errori dell'intera macchina. Poiché Google possiede l'intero stack software-hardware per Spanner, è in grado di apportare ulteriori ottimizzazioni per garantire il massimo livello di prestazioni e robustezza. Ad esempio, tutte le macchine Spanner utilizzano una RAM a batteria, che consente di sincronizzare le scritture su disco anche in caso di perdita di alimentazione del data center (improbabile). Così il file system può confermare le scritture senza attendere la latenza di scrittura su disco.

Esempio pratico

Esaminiamo alcuni esempi pratici per vedere 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 chiave primaria è partizionato in frazioni. Ad esempio, se c'è una riga in ExampleTable con Id di 3700, questa verrà pubblicata nella suddivisione 8. Come spiegato in precedenza, Split 8 è replicato su più macchine.

In questa istanza Spanner di esempio, il cliente ha cinque nodi e l'istanza viene replicata in tre zone. Le nove suddivisioni sono numerate da 0 a 8, con i leader di Paxos per ogni sezione oscurata. Le suddivisioni hanno anche repliche in ciascuna zona (leggermente ombreggiata). La distribuzione delle suddivisioni tra i nodi può essere diversa in ogni zona e i leader Paxos non risiedono tutti nella stessa zona. Questa flessibilità consente a Spanner di essere più solido per determinati tipi di profili di carico e modalità di errore.

Scrittura a suddivisione singola

Supponiamo che il client voglia inserire una nuova riga (7, "Seven") in ExampleTable.

1. Il livello API cerca la suddivisione che possiede l'intervallo di chiavi contenente 7. Si trova nella sezione Suddivisione 1.
2. Il livello API invia la richiesta di scrittura al leader della suddivisione 1.
3. Il leader avvia una transazione.
4. Il leader tenta di ottenere un blocco della scrittura nella riga Id=7. Questa è un'operazione locale. Se un'altra transazione di lettura/scrittura simultanea sta leggendo questa riga, l'altra transazione avrà un blocco di lettura e la transazione corrente si blocca finché non può acquisire il blocco della scrittura.
   1. È possibile che la transazione A sia in attesa di un blocco bloccato dalla transazione B e che la transazione B sia in attesa di un blocco bloccato dalla transazione A. Poiché nessuna delle transazioni rilascia alcun blocco finché non acquisisce tutti i blocchi, questo può comportare un deadlock. Spanner utilizza un algoritmo di prevenzione dei deadlock standard per garantire che le transazioni proseguano. In particolare, una transazione "meno recente" attende il blocco di una transazione "meno recente", mentre una transazione "meno recente" "chiude" (interrompe) una transazione più giovane che mantiene un blocco richiesto dalla transazione precedente. Pertanto, non abbiamo mai cicli di chiusura della serratura di camerieri.
5. Una volta acquisito il blocco, Leader assegna un timestamp alla transazione in base a TrueTime.
   1. Questo timestamp garantisce che sia maggiore di quello di qualsiasi transazione precedentemente impegnata che ha interessato i dati. In questo modo viene garantito che l'ordine delle transazioni (percepito dal cliente) corrisponda all'ordine delle modifiche ai dati.
6. Il leader indica alle repliche di suddivisione 1 la transazione e il relativo timestamp. Una volta che la maggior parte di queste repliche ha archiviato la mutazione della transazione nello spazio di archiviazione stabile (nel file system distribuito), la transazione viene confermata. Ciò garantisce che la transazione sia recuperabile, anche in caso di errore in una minoranza di macchine. (Le repliche non applicano ancora le mutazioni alla propria copia dei dati.)

7. Il leader attende fino a quando non è sicuro che il timestamp della transazione sia passato in tempo reale; questa operazione di solito richiede alcuni millisecondi, in modo da poter attendere qualsiasi incertezza nel timestamp TrueTime. Questo è ciò che garantisce una elevata coerenza: una volta che un cliente ha appreso il risultato di una transazione, è garantito che tutti gli altri lettori vedranno gli effetti della transazione. Questa "attesa del commit" si sovrappone in genere alla comunicazione della replica nel passaggio precedente, quindi il costo effettivo della latenza è minimo. Ulteriori dettagli sono descritti in questo documento.

8. Il leader risponde al cliente per comunicare che la transazione è stata confermata, segnalando facoltativamente il timestamp di commit della transazione.

9. Parallelamente a rispondere al client, le mutazioni delle transazioni vengono applicate ai dati.

   1. La variante principale applica le mutazioni alla propria copia dei dati e poi rilascia i blocchi delle transazioni.
   2. Il leader informa anche le altre repliche di Split 1 di applicare la mutazione alle copie dei dati.
   3. Qualsiasi transazione di lettura/scrittura o di sola lettura che dovrebbe osservare gli effetti delle mutazioni attende l'applicazione delle mutazioni prima di tentare di leggere i dati. Per le transazioni di lettura e scrittura, questo viene applicato in quanto la transazione deve richiedere un blocco in lettura. Per le transazioni di sola lettura, questo viene applicato confrontando il timestamp della lettura con quello degli ultimi dati applicati.

Tutto questo avviene generalmente in una manciata di millisecondi. Questa è la scrittura più economica eseguita da Spanner, poiché è prevista una suddivisione singola.

Scrittura multi-divisa

Se sono coinvolte più suddivisioni, è necessario un ulteriore livello di coordinazione (utilizzando l'algoritmo di commit standard a due fasi).

Supponiamo che la tabella contenga quattromila righe:

1	"uno"
2	"two"
...	...
4000	"quattromila"

Supponiamo che il client voglia leggere il valore della riga 1000 e scrivere un valore nelle righe 2000, 3000 e 4000 all'interno di una transazione. L'operazione verrà eseguita all'interno di una transazione di lettura-scrittura come segue:

1. Il client avvia una transazione di lettura-scrittura, t.
2. Il client invia una richiesta di lettura per la riga 1000 al livello API e la tagga come parte di t.
3. Il livello API cerca la suddivisione proprietaria della chiave 1000. Si trova in Split 4.

4. Il livello API invia una richiesta di lettura al leader della divisione 4 e la tagga come parte di t.

5. Il leader della divisione 4 tenta di ottenere un blocco di lettura nella riga Id=1000. Questa è un'operazione locale. Se un'altra transazione simultanea ha un blocco di scrittura su questa riga, la transazione corrente si blocca fino a quando non può acquisire il blocco. Tuttavia, questo blocco di lettura non impedisce alle altre transazioni di ricevere blocchi di lettura.

   1. Come nel caso del caso diviso singolo, il deadlock viene evitato tramite "wound-wait".

6. Il leader cerca il valore per Id 1000 ("Migliaia") e restituisce il risultato letto al client.

   
   Più tardi...
   

7. Il cliente invia una richiesta di commit per la transazione t. Questa richiesta di commit contiene tre mutazioni: ([2000, "Dos Mil"], [3000, "Tres Mil"] e [4000, "Quatro Mil"]).

   1. Tutte le suddivisioni coinvolte in una transazione diventano partecipanti alla transazione. In questo caso, la divisione 4 (che ha utilizzato la lettura per la chiave 1000), la suddivisione 7 (che gestirà la modifica per la chiave 2000) e la divisione 8 (che gestirà le mutazioni per la chiave 3000 e la chiave 4000) sono i partecipanti.

8. Un partecipante diventa il coordinatore. In questo caso, forse il leader di Split 7 diventa il coordinatore. Il compito del coordinatore è assicurarsi che la transazione si confermi o venga interrotta a livello atomico tra tutti i partecipanti. Ciò significa che non verrà eseguito il commit in un partecipante e non verrà interrotto in un altro.

   1. Il lavoro svolto dai partecipanti e dai coordinatori viene effettivamente svolto dalle macchine principali di queste suddivisioni.

9. I partecipanti acquisiscono i blocchi. Si tratta della prima fase del commit in due fasi.

   1. Split 7 acquisisce un blocco di scrittura sulla chiave 2000.
   2. Split 8 acquisisce un blocco di scrittura sulla chiave 3000 e sulla chiave 4000.
   3. La funzionalità Split 4 verifica che sia ancora in corso un blocco di lettura sulla chiave 1000 (in altre parole, che il blocco non è stato perso a causa di un arresto anomalo della macchina o dell'algoritmo di attesa.)
   4. La suddivisione di ogni partecipante registra il proprio set di blocchi replicandoli (almeno) nella maggior parte delle repliche suddivise. In questo modo, i blocchi possono rimanere tenuti anche in caso di errori del server.
   5. Se tutti i partecipanti informano correttamente il coordinatore che i blocchi sono stati bloccati, la transazione complessiva può essere confermata. In questo modo, esiste un momento specifico in cui vengono conservati tutti i blocchi richiesti dalla transazione e questo momento diventa il punto di commit della transazione, assicurandoci di poter ordinare correttamente gli effetti di questa transazione rispetto ad altre transazioni precedenti o successive.
   6. È possibile che i blocchi non possano essere acquisiti (ad esempio, se scopriamo che potrebbe esserci un deadlock tramite l'algoritmo wound-wait). Se un partecipante afferma di non poter effettuare il commit della transazione, l'intera transazione viene interrotta.

10. Se tutti i partecipanti e il coordinatore acquisiscono correttamente i blocchi, il coordinatore (gruppo 7) decide di eseguire la transazione. Assegna un timestamp alla transazione in base a TrueTime.

    1. Questa decisione sull'impegno, così come le mutazioni per la chiave 2000, vengono replicate ai membri di Split 7. Una volta che la maggior parte delle repliche Split 7 registra la decisione di commit nello spazio di archiviazione stabile, la transazione viene confermata.

11. Il Coordinatore comunica il risultato della transazione a tutti i Partecipanti. Si tratta della seconda fase del commit in due fasi.

    1. Ogni leader dei partecipanti replica la decisione sull'impegno nelle repliche della suddivisione dei partecipanti.

12. Se la transazione viene confermata, il Coordinatore e tutti i Partecipanti applicano le mutazioni ai dati.

    1. Come nel caso della singola suddivisione, i successivi lettori di dati presso il coordinatore o i partecipanti devono attendere l'applicazione dei dati.

13. Il responsabile del coordinatore risponde al cliente per dire che la transazione è stata impegnata, restituendo facoltativamente il timestamp di commit della transazione

    1. Come nel caso di una suddivisione singola, il risultato viene comunicato al client dopo un'attesa di commit, per garantire un'elevata coerenza.

Tutto questo avviene generalmente in una manciata di millisecondi, anche se in genere pochi di più rispetto al caso di suddivisione singola a causa della coordinazione cross-split extra.

Lettura forte (divisione multipla)

Supponiamo che il client voglia leggere tutte le righe in cui Id >= 0 e Id < 700 nell'ambito di una transazione di sola lettura.

1. Il livello API cerca le suddivisioni proprietarie delle chiavi nell'intervallo [0, 700). Queste righe sono di proprietà di Dividi 0, Dividi 1 e Dividi 2.
2. Poiché si tratta di una lettura efficace su più macchine, il livello API sceglie il timestamp di lettura utilizzando l'attuale TrueTime. Ciò garantisce che entrambe le letture restituiscano i dati dallo stesso snapshot del database.
   1. Anche altri tipi di letture, come quelle inattive, scelgono un timestamp per la lettura (ma il timestamp potrebbe essere nel passato).
3. Il livello API invia la richiesta di lettura a alcune repliche della suddivisione 0, alcune repliche della suddivisione 1 e alcune repliche della suddivisione 2. Include anche il timestamp di lettura selezionato nel passaggio precedente.

4. Per le letture efficaci, la replica di pubblicazione in genere invia una RPC alla versione leader per richiedere il timestamp dell'ultima transazione che deve essere applicata e la lettura può procedere dopo l'applicazione della transazione. Se la replica è l'elemento leader o stabilisce che è stata raggiunta a sufficienza per soddisfare la richiesta dal suo stato interno e da TrueTime, allora gestisce direttamente la lettura.

5. I risultati delle repliche vengono combinati e restituiti al client (tramite il livello API).

Tieni presente che le operazioni di lettura non acquisiscono alcun blocco nelle transazioni di sola lettura. Inoltre, poiché le letture possono potenzialmente essere pubblicate 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 obsolete di almeno dieci secondi, la velocità effettiva di lettura può essere ancora maggiore. Poiché il leader in genere aggiorna le repliche con l'ultimo timestamp sicuro ogni dieci secondi, le letture a un timestamp inattivo potrebbero evitare un'RPC extra per la variante leader.

A lato: blocco in Spanner

In genere, i blocchi di scrittura nei database sono esclusivi: i dati possono essere aggiornati da un solo autore alla volta. In questo modo si evita il danneggiamento dei dati, impedendo le condizioni di gara per gli stessi dati. Tuttavia, limita la velocità effettiva, dal momento che può avanzare una sola transazione alla volta. In Spanner, siamo in grado di utilizzare i timestamp assegnati alle transazioni per consentire la condivisione dei blocchi di scrittura in molti casi. In particolare, per le scritture (la scrittura di dati senza precedentemente lettura nella stessa transazione) in una singola transazione divisa, possiamo consentire a più transazioni che scrivono gli stessi dati di procedere in parallelo. Poiché i timestamp assegnati da TrueTime a ciascuna scrittura sono garantiti come diversi, evitiamo le condizioni di gara: i dati con timestamp diversi vengono applicati separatamente e in ordine di timestamp, evitando così il danneggiamento dei dati. Abbiamo scoperto che questa è una vittoria significativa in termini di velocità effettiva per le scritture cieche eseguite in Spanner dai sistemi interni di Google.

A parte: che cosa si sta catturando? Le primitive di database potenti non hanno un costo in termini di prestazioni?

Uno dei principi che cerchiamo di rispettare è "non paghi (in termini di rendimento) ciò che non usi". Un esempio di ciò sono le garanzie di contemporaneità di Spanner: mentre Spanner utilizza più meccanismi per garantire un'elevata coerenza, un'applicazione non paga per i meccanismi che non utilizza. Implementiamo il commit in due fasi (2PC) per le transazioni che comprendono le suddivisioni, ma una transazione verso una singola suddivisione ignora il 2PC e utilizza un protocollo più semplice e veloce. Le letture "forti" dei dati più recenti possono impiegare una certa latenza per verificare se una replica è sufficientemente aggiornata, ma una lettura che può essere soddisfatta con dati inattivi non paga questa latenza. Un altro esempio è il nostro layout dei dati, in cui utilizziamo lo sharding degli intervalli. Le applicazioni che eseguono scansioni dell'intervallo possono utilizzare questo layout per ottenere prestazioni elevate. Tuttavia, alcune applicazioni non hanno bisogno di scansioni di intervalli e, se queste applicazioni non vogliono preoccuparsi del costo delle prestazioni dei potenziali hotspot di intervallo di righe, possono inserire un valore hash nella loro chiave primaria, il che di fatto fa sì che Spanner utilizzi lo sharding. In generale, Spanner è stato progettato per offrire strumenti potenti agli sviluppatori di applicazioni, ma per fornire a questi sviluppatori un elevato livello di controllo su qualsiasi compromesso tra potenti funzionalità e prestazioni.

Conclusione

Tradizionalmente, i progettisti di sistemi di database distribuiti hanno riscontrato che le forti garanzie transazionali sono costose, per via di tutta la comunicazione tra macchine necessaria. Con Spanner, ci siamo concentrati sulla riduzione del costo delle transazioni per renderle attuabili su larga scala e nonostante la distribuzione. Uno dei motivi principali per cui funziona è TrueTime, che riduce la comunicazione tra macchine per molti tipi di coordinamento. A parte questo, un'attenta progettazione e l'ottimizzazione delle prestazioni ha portato a un sistema altamente performante anche con forti garanzie. All'interno di Google, abbiamo scoperto che questo ha semplificato notevolmente lo sviluppo di applicazioni su Spanner rispetto ad altri sistemi di database con garanzie più deboli. Quando gli sviluppatori di applicazioni non devono preoccuparsi delle gare o delle incoerenze nei dati, possono concentrarsi su ciò che gli interessa davvero: creare e distribuire un'ottima applicazione.