Questa pagina è stata tradotta dall'API Cloud Translation.

Durata delle letture e delle scritture Spanner

Spanner è un database scalabile, distribuito e a elevata coerenza creato dai tecnici di Google per supportare alcune delle applicazioni più critiche di Google. prende le idee principali dalle community di database e sistemi distribuiti e le espande in nuovi modi. Spanner espone questo servizio Spanner interno come servizio disponibile pubblicamente su Google Cloud Platform.

Poiché Spanner deve gestire i impegnativi requisiti di uptime e scalabilità imposti dalle applicazioni aziendali critiche di Google, lo abbiamo creato da zero per essere un database a larga distribuzione. Il servizio può includere più macchine e più data center e regioni. Sfruttiamo questa distribuzione per gestire enormi set di dati e carichi di lavoro enormi, mantenendo al contempo una disponibilità molto elevata. Abbiamo puntato anche a Spanner per fornire le stesse garanzie di coerenza rigorosa fornite da altri database di livello aziendale, perché volevamo creare un'esperienza eccezionale per gli sviluppatori. È molto più facile ragionare e scrivere software per un database che supporta elevata coerenza rispetto a un database che supporta solo coerenza a livello di riga, coerenza a livello di entità o che non ha alcuna garanzia di coerenza.

In questo documento descriviamo in dettaglio il funzionamento delle scritture e delle letture in Spanner e del 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 scenari in cui il set di dati è ridotto, ma il carico di lavoro è troppo elevato 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 dei database in intervalli di chiavi contigui denominati 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 i dati vengono suddivisi e su quali macchine risiedono sono trasparenti per gli utenti di Spanner. Il risultato è un sistema in grado di fornire basse latenze sia per le letture che per le scritture, anche con carichi di lavoro intensivi, su scala molto ampia.

Vogliamo inoltre assicurarci che i dati siano accessibili nonostante gli errori. Per garantire questo, replicaamo ogni suddivisione su più macchine in domini in errore distinti. La replica coerente nelle diverse copie della suddivisione è gestita dall'algoritmo Paxos. In Paxos, purché 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 transazioni di sola lettura e transazioni di lettura e scrittura. Le prime sono il tipo di transazione preferito per le operazioni (incluse le istruzioni SELECT SQL) che non modificano i dati. Le transazioni di sola lettura forniscono comunque elevata coerenza e, per impostazione predefinita, utilizzano la copia più recente dei dati. Tuttavia, possono essere eseguiti senza la necessità di alcun tipo di blocco interno, il che li rende più veloci e più scalabili. Le transazioni di lettura/scrittura vengono utilizzate per le transazioni che inseriscono, aggiornano o eliminano dati; includono le transazioni che eseguono letture seguite da una scrittura. Sono comunque altamente scalabili, ma le transazioni di lettura/scrittura introducono blocchi 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 per via della costosa comunicazione tra le macchine solitamente richiesta. Spanner è in grado di fornire snapshot a elevata coerenza in tutto il database utilizzando una tecnologia sviluppata da Google denominata TrueTime. Come il Flux Capacitor in una macchina del tempo del 1985 circa, TrueTime è ciò che rende possibile Spanner. È un'API che consente a qualsiasi macchina nei data center Google di conoscere l'ora globale esatta con un elevato grado di accuratezza (entro pochi millisecondi). Ciò consente a diverse macchine Spanner di ragionare sull'ordine delle operazioni transazionali (e far sì che l'ordinamento corrisponda a quanto 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 l'accuratezza in termini di tempo risultanti sono molto più elevate di quelle che possono essere ottenute da altri protocolli (come NTP). In particolare, Spanner assegna un timestamp a tutte le letture e scritture. È garantito che una transazione nel timestamp T1 rispecchierà i risultati di tutte le scritture avvenute 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. Grazie a TrueTime, questa determinazione è solitamente molto economica. I protocolli per garantire la coerenza dei dati sono complicati, ma ne vengono discussi più nell'articolo originale di Spanner e in questo articolo su Spanner e coerenza.

A parte: file system distribuiti

Quando salvi un file sul tuo laptop, in genere il file viene scritto sul disco rigido di quel laptop. Ma cosa succede se il disco rigido si rompe? Perdi il file? Il tuo laptop può salvare altri file (o persino utilizzarli per qualsiasi cosa) finché il disco rigido non viene sistemato? Questi sono alcuni dei problemi che i file system distribuiti cercano di risolvere. Più di 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. In caso di guasto di una macchina, le altre sarebbero disponibili per le operazioni di lettura e scrittura sul file. Da GFS abbiamo fatto molti progressi, ma il concetto fondamentale rimane lo stesso: l'archiviazione di file è disaccoppiata dalle macchine che li creano, li leggono, aggiornano ed eliminano. Ciò consente la creazione di sistemi più robusti; un singolo disco non valido 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 si impegnano scrivendo le mutazioni ad almeno la maggior parte delle repliche dei segmenti 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 scalabilità elevata), ma poiché qualsiasi server in un cluster può leggere da questo file system distribuito, possiamo ripristinare rapidamente da errori dell'intera macchina. Poiché Google è proprietaria dell'intero stack software-hardware per Spanner, possiamo effettuare ulteriori ottimizzazioni per garantire il massimo delle prestazioni e della robustezza. Ad esempio, tutte le macchine Spanner utilizzano una RAM supportata da batteria, quindi le scritture possono essere sincronizzate su disco anche nel caso (improbabile) di assenza di alimentazione del data center. Ciò consente inoltre al file system di confermare le scritture senza attendere la latenza della scrittura su disco.

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 riportato sopra, lo spazio della chiave primaria è partizionato in suddivisioni. Ad esempio, se è presente una riga in ExampleTable con Id di 3700, questa sarà presente nella suddivisione 8. Come spiegato in precedenza, Split 8 viene replicato su più macchine.

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

Scrittura a suddivisione singola

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

Il livello API cerca la suddivisione proprietaria dell'intervallo di chiavi contenente 7. È disponibile nella fase 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. Questa è un'operazione locale. Se in questa riga è in corso un'altra transazione di lettura-scrittura in parallelo, l'altra transazione ha un blocco di lettura e la transazione corrente si blocca finché non riesce ad acquisire il blocco di scrittura.
1. È possibile che la transazione A sia in attesa di un blocco della transazione B e che la transazione B sia in attesa di un blocco della transazione A. Poiché nessuna transazione rilascia alcun blocco finché non acquisisce tutti i blocchi, questo può causare un deadlock. Spanner usa un algoritmo di prevenzione del deadlock "wound-wait" per garantire che le transazioni vengano prodotte. In particolare, una transazione "meno recente" attenderà un blocco detenuto da una transazione "meno recente", mentre una transazione "meno recente" "interrompe" una transazione "più giovane" con un blocco richiesto dalla transazione precedente. Per questo non abbiamo mai cicli di stallo dei camerieri.
Una volta acquisito il blocco, Leader assegna un timestamp alla transazione in base a TrueTime.
1. Questo timestamp garantisce essere superiore a quello di qualsiasi transazione impegnata in precedenza che ha interessato i dati. Questo garantisce che l'ordine delle transazioni (come percepito dal cliente) corrisponda 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 nello spazio di archiviazione stabile (nel file system distribuito), la transazione viene eseguita. 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 loro copia dei dati.
Il leader attende fino a quando non riesce ad assicurarsi che il timestamp della transazione sia trascorso in tempo reale. Ciò di solito richiede alcuni millisecondi per poter attendere eventuali incertezze nel timestamp TrueTime. Questo è ciò che garantisce una forte 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 per il commit" in genere si sovrappone alla comunicazione della replica nel passaggio precedente, pertanto il costo effettivo della latenza è minimo. Ulteriori dettagli sono discussi in questo articolo.
Il leader risponde al client dicendo che la transazione è stata impegnata, segnalando facoltativamente il timestamp di commit della transazione.
Parallelamente a rispondere al cliente, le mutazioni della transazione vengono applicate ai dati.
1. Il leader applica le mutazioni alla propria copia dei dati, quindi rilascia i blocchi delle transazioni.
2. Il leader informa anche le altre repliche di suddivisione 1 di applicare la mutazione alle loro copie dei dati.
3. Qualsiasi transazione di lettura-scrittura o di sola lettura che dovrebbe vedere gli effetti delle mutazioni attende l'applicazione delle mutazioni prima di tentare di leggere i dati. Per le transazioni di lettura/scrittura, questo viene applicato in modo forzato perché la transazione deve avere un blocco di lettura. Per le transazioni di sola lettura, ciò viene applicato confrontando il timestamp della lettura con quello degli ultimi dati applicati.

Tutto questo avviene generalmente in una manciata di millisecondi. È il tipo di scrittura più economico eseguito da Spanner, poiché è coinvolta una singola suddivisione.

Scrittura su più suddivisioni

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

Supponiamo che la tabella contenga quattromila righe:

1	"uno"
2	"two"
...	...
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. Questa operazione verrà 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. Questa è un'operazione locale. Se un'altra transazione in parallelo ha un blocco di scrittura in questa riga, 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.
1. Come nel caso di split singolo, il deadlock viene evitato tramite "wound-wait".
Il leader cerca il valore di Id 1000 ("Migliaia") e restituisce il risultato letto al cliente.

Dopo...
Il client emette una richiesta Commit per la transazione t. Questa richiesta di commit contiene tre modifiche: ([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, Dividi 4 (che ha fornito la lettura per la chiave 1000), Dividi 7 (che gestirà la mutazione per la chiave 2000) e Dividi 8 (che gestirà le mutazioni per la chiave 3000 e la chiave 4000) sono partecipanti.
Un partecipante diventa il coordinatore. In questo caso, forse il leader di Dividi 7 diventa il coordinatore. Il compito del coordinatore è assicurarsi che la transazione venga eseguita o venga interrotta a livello atomico tra tutti i partecipanti. In altre parole, non eseguirà il commit in un partecipante e si interromperà in un altro.
1. Il lavoro svolto dai partecipanti e dai coordinatori viene in realtà svolto dalle macchine leader di questi segmenti.
I partecipanti acquisiscono blocchi. Questa è la prima fase del commit in due fasi.
1. La suddivisione 7 acquisisce un blocco di scrittura sulla chiave 2000.
2. La suddivisione 8 acquisisce un blocco di scrittura sulla chiave 3000 e sulla chiave 4000.
3. Split 4 verifica che sia ancora 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 della ferita).
4. Ogni suddivisione di partecipanti registra il proprio insieme di blocchi replicandoli nella maggior parte delle repliche divise. In questo modo i blocchi possono rimanere trattenuti anche tra gli errori del server.
5. Se tutti i partecipanti comunicano al coordinatore che i loro blocchi sono bloccati, la transazione complessiva può essere confermata. Ciò garantisce che ci sia un momento in cui vengono applicati tutti i blocchi necessari per la transazione, che 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 ci rendiamo conto che potrebbe esserci un deadlock tramite l'algoritmo wound-wait. Se un partecipante dichiara di non poter eseguire il commit della transazione, l'intera transazione viene interrotta.
Se tutti i partecipanti, e il coordinatore, acquisiscono correttamente i blocchi, Coordinator (Split 7) decide di eseguire il commit della transazione. Assegna un timestamp alla transazione basato su TrueTime.
1. Questa decisione di commit e le mutazioni per la chiave 2000 vengono replicate ai membri di Split 7. Quando la maggior parte delle repliche di Split 7 registra la decisione di impegno nello spazio di archiviazione stabile, la transazione viene impegnata.
Il Coordinatore comunica l'esito della transazione a tutti i Partecipanti. Questa è la seconda fase del commit in due fasi.
1. Ogni partecipante leader replica la decisione sull'impegno nelle repliche della suddivisione dei partecipanti.
Se la transazione viene impegnata, il coordinatore e tutti i partecipanti applicano le mutazioni ai dati.
1. Come nel caso di suddivisione singola, i lettori successivi dei dati presso il coordinatore o i partecipanti devono attendere fino all'applicazione dei dati.
Il responsabile del coordinatore risponde al client per dire che la transazione è stata confermata, restituendo il timestamp di commit della transazione
1. Come nel caso di 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 sono pochi in più rispetto al caso di suddivisione singola a causa della coordinazione della suddivisione incrociata extra.

Lettura elevata (multi-diviso)

Supponiamo che il client voglia leggere tutte le righe in cui Id >= 0 e Id < 700 nell'ambito 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 il timestamp di lettura utilizzando il valore TrueTime attuale. In questo modo entrambe le letture restituiscono i dati dallo stesso snapshot del database.
1. Anche altri tipi di letture, come le letture inattive, scelgono un timestamp da leggere (ma il timestamp potrebbe essere nel passato).
Il livello API invia la richiesta di lettura ad alcune repliche di suddivisione 0, ad alcune repliche di split 1 e ad alcune repliche di split 2. Include anche il read-timestamp che ha selezionato nel passaggio precedente.
Per letture efficaci, la replica di gestione in genere invia una RPC al 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 è leader o determina di essere raggiunta a sufficienza per soddisfare la richiesta dal suo stato interno e da TrueTime, 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. Inoltre, poiché le letture possono essere potenzialmente gestite 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 inattive per almeno dieci secondi, la velocità effettiva di lettura può essere anche superiore. Poiché il leader generalmente aggiorna le repliche con l'ultimo timestamp sicuro ogni dieci secondi, le letture a un timestamp inattivo possono evitare una RPC aggiuntiva per la leader.

A lato: il blocco di Spanner

Di solito, i blocchi di scrittura nei database sono esclusivi: è consentito aggiornare i dati a un solo writer alla volta. In questo modo si previene il danneggiamento dei dati impedendo le race condizioni sugli stessi dati. Tuttavia, limita la velocità effettiva, poiché è possibile far progredire una sola transazione alla volta. In Spanner, siamo in grado di sfruttare i timestamp assegnati alle transazioni per consentire in molti casi la condivisione dei blocchi di scrittura. In particolare, per le scritture cieche (ovvero la scrittura di dati senza leggerli prima nella stessa transazione) in un'unica transazione di suddivisione, possiamo consentire a più transazioni che scrivono gli stessi dati di procedere in parallelo. Poiché i timestamp assegnati da TrueTime a ogni scrittura sono garantiti essere diversi, evitiamo le condizioni di gara: i dati con timestamp diversi vengono applicati separatamente e in ordine di timestamp, evitando il danneggiamento dei dati. Abbiamo riscontrato che la velocità effettiva è significativa per le scritture in cieco eseguite su Spanner dai sistemi interni di Google.

A parte: Qual è il punto? Le potenti primitive dei database hanno un costo in termini di prestazioni?

Un principio che cerchiamo di rispettare è "non paghi (in termini di prestazioni) per ciò che non utilizzi". Un esempio sono le garanzie di contemporaneità di Spanner: sebbene Spanner utilizzi più meccanismi per garantire un'elevata coerenza, un'applicazione non paga per i meccanismi che non utilizza. Implementiamo un commit in due fasi (2PC) per le transazioni che comprendono le suddivisioni, ma una transazione su una singola suddivisione aggira il 2PC e utilizza un protocollo più semplice e veloce. Le letture "efficaci" dei dati più recenti potrebbero comportare 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 layout dei dati, in cui utilizziamo lo sharding per intervalli. Le applicazioni che eseguono scansioni degli intervalli possono utilizzare questo layout per ottenere prestazioni elevate. Tuttavia, alcune applicazioni non necessitano di analisi degli intervalli e, se queste applicazioni non vogliono preoccuparsi del costo delle prestazioni dei potenziali hotspot a intervalli di righe, possono inserire un valore hash nella chiave primaria, facendo in modo che Spanner utilizzi lo sharding. In generale, Spanner è stato progettato per offrire strumenti efficaci ai generatori di applicazioni, ma per offrire a questi ultimi un elevato livello di controllo su eventuali compromessi tra potenti funzionalità e prestazioni.

Conclusione

Tradizionalmente, i progettisti di sistemi di database distribuiti hanno scoperto che le forti garanzie transazionali sono costose, a causa di tutta la comunicazione tra le macchine necessaria. Con Spanner, ci siamo concentrati sulla riduzione del costo delle transazioni per renderle realizzabili su larga scala e nonostante la distribuzione. Un motivo fondamentale per questo approccio è TrueTime, che riduce la comunicazione tra macchine per molti tipi di coordinamento. Inoltre, un'attenta progettazione e messa a punto delle prestazioni ha permesso di realizzare un sistema dalle prestazioni elevate, pur fornendo solide garanzie. In Google, abbiamo riscontrato che ciò ha reso notevolmente più semplice 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 condizioni di gara o delle incoerenze nei dati, possono concentrarsi sugli aspetti di loro interesse: creare e distribuire un'applicazione efficace.