TrueTime è un orologio distribuito ad alta disponibilità fornito alle applicazioni su tutti i server Google.1 TrueTime consente alle applicazioni di generare timestamp con incrementi monotonici: un'applicazione può calcolare un timestamp T garantito essere maggiore di qualsiasi timestamp T' se la generazione di T' termina prima dell'inizio della generazione di T. Questa garanzia viene applicata a tutti i server e a tutti i timestamp.
Questa funzionalità di TrueTime viene utilizzata da Spanner per assegnare timestamp alle transazioni. In particolare, a ogni transazione viene assegnato un timestamp che riflette il momento in cui Spanner ritiene che si sia verificata. Poiché Spanner utilizza il controllo della contemporaneità multi-versione, la garanzia di ordinamento sui timestamp consente ai client di Spanner di eseguire letture coerenti in tutto il database (anche in più regioni di Cloud) senza bloccare le scritture.
Coerenza esterna
Spanner offre ai client le garanzie di controllo della contemporaneità più severi per le transazioni, una cosiddetta coerenza esterna2. In presenza di coerenza esterna, il sistema si comporta come se tutte le transazioni venissero eseguite in sequenza, anche se Spanner in realtà le esegue su più server (e possibilmente in più data center) per ottenere prestazioni e disponibilità migliori. Inoltre, se una transazione viene completata prima che ne inizi il commit di un'altra, il sistema garantisce che i clienti non possano mai vedere uno stato che include l'effetto della seconda transazione, ma non della prima. Intuitivamente, Spanner è semanticamente indistinguibile da un database di una singola macchina. Anche se offre garanzie così efficaci, Spanner consente alle applicazioni di raggiungere prestazioni paragonabili a quelle dei database che offrono garanzie più deboli (in cambio di prestazioni migliori). Ad esempio, come i database che supportano l'isolamento degli snapshot, Spanner consente alle scritture di procedere senza essere bloccate dalle transazioni di sola lettura, ma senza presentare le anomalie consentite dall'isolamento degli snapshot.
La coerenza esterna semplifica notevolmente lo sviluppo di applicazioni. Ad esempio, supponiamo di aver creato un'applicazione di banking su Spanner e che uno dei tuoi clienti inizi con 50 $nel conto corrente e 50 $nel conto di risparmio. La tua applicazione avvia quindi un flusso di lavoro in cui si impegna innanzitutto una transazione T1 per depositare $200 sul conto di risparmio e poi emette una seconda transazione T2 per addebitare 150 $dal conto corrente. Inoltre, supponiamo che, in fin dei conti, i saldi negativi di un account vengano coperti automaticamente dagli altri account e che un cliente incorra in una sanzione se il saldo totale di tutti i suoi account è negativo in qualsiasi momento della giornata. La coerenza esterna garantisce che, poiché il commit di T2 inizia al termine di T1, tutti i lettori del database osserveranno che il deposito T1 è avvenuto prima dell'addebito T2. In altre parole, la coerenza esterna garantisce che nessuno vedrà mai uno stato in cui T2 è precedente a T1; in altre parole, l'addebito non verrà mai applicato a sanzioni per insufficienza di fondi.
Un database tradizionale che utilizza l'archiviazione a una sola versione e il rigoroso blocco a due fasi fornisce coerenza esterna. Purtroppo, in un sistema di questo tipo, ogni volta che la tua applicazione vuole leggere i dati più aggiornati (che definiamo "lettura efficace"), il sistema acquisisce un blocco di lettura sui dati, che blocca le scritture sui dati letti.
Timestamp e controllo della contemporaneità tra più versioni (MVCC)
Per leggere senza bloccare le scritture, Spanner e molti altri sistemi di database mantengono più versioni immutabili dei dati (spesso chiamato controllo della contemporaneità multi-versione). Una scrittura crea una nuova versione immutabile il cui timestamp è quello della transazione della scrittura. Una "lettura snapshot" in un timestamp restituisce il valore della versione più recente prima di quel timestamp e non ha bisogno di bloccare le scritture. Pertanto, è importante che i timestamp assegnati alle versioni siano coerenti con l'ordine in cui è possibile osservare il commit delle transazioni. Questa proprietà viene chiamata "timestamp corretta". Tieni presente che l'esistenza di un timestamp corretto equivale a una coerenza esterna.
Per capire perché è importante un timestamp corretto, considera l'esempio bancario della sezione precedente. Senza il timestamp corretto, a T2 potrebbe essere assegnato un timestamp precedente a quello assegnato a T1 (ad esempio, se un sistema ipotetico utilizzava orologi locali anziché TrueTime e l'orologio del server che elabora T2 è leggermente ritardato). La lettura di uno snapshot potrebbe quindi riflettere l'addebito di T2 ma non il bonifico di T1, anche se il cliente ha visto il completamento del bonifico prima di iniziare l'addebito.
Ottenere un timestamp corretto è facile per un database di una sola macchina (ad esempio, puoi semplicemente assegnare i timestamp da un contatore globale e monotonico). Farlo in un sistema ampiamente distribuito come Spanner, in cui i server di tutto il mondo devono assegnare timestamp, è molto più difficile da fare in modo efficiente.
Spanner si basa su TrueTime per generare timestamp con aumento monotonico. Spanner utilizza questi timestamp in due modi. In primo luogo, li utilizza come timestamp appropriati per le transazioni di scrittura senza bisogno di una comunicazione globale. In secondo luogo, li utilizza come timestamp per le letture efficaci, che consentono l'esecuzione di letture efficaci in un solo ciclo di comunicazione, anche su più server.
Domande frequenti
Quali garanzie di coerenza offre Spanner?
Spanner offre coerenza esterna, ovvero la proprietà di coerenza più severa per i sistemi di elaborazione delle transazioni. Tutte le transazioni in Spanner soddisfano questa proprietà di coerenza, non solo quelle all'interno di una partizione. La coerenza esterna indica che Spanner esegue le transazioni in modo non distinguibile da un sistema in cui le transazioni vengono eseguite in serie e, inoltre, che l'ordine seriale è coerente con l'ordine in cui è possibile osservare il commit delle transazioni. Poiché i timestamp generati per le transazioni corrispondono all'ordine seriale, se un cliente vede l'avvio del commit di una transazione T2 al termine dell'altra transazione T1, il sistema assegnerà a T2 un timestamp superiore a quello di T1.
Spanner offre la linearizzabilità?
Sì, Di fatto, Spanner offre coerenza esterna, una proprietà più efficace della linearizzabilità, in quanto non indica nulla sul comportamento delle transazioni. La linearizzabilità è una proprietà di oggetti simultanei che supportano operazioni di lettura e scrittura atomiche. In un database, un "oggetto" è in genere una singola riga o anche una singola cella. La coerenza esterna è una proprietà dei sistemi di elaborazione delle transazioni, in cui i client sintetizzano dinamicamente le transazioni che contengono più operazioni di lettura e scrittura su oggetti arbitrari. La Linearizzazione può essere vista come un caso speciale di coerenza esterna, in cui una transazione può contenere solo una singola operazione di lettura o scrittura su un singolo oggetto.
Spanner fornisce la serializzabilità?
Sì, Di fatto, Spanner offre coerenza esterna, una proprietà più restrittiva rispetto alla serializzabilità. Un sistema di elaborazione delle transazioni è serializzabile se esegue le transazioni in un modo non distinguibile da un sistema in cui le transazioni vengono eseguite in modo seriale. Spanner garantisce inoltre che l'ordine seriale sia coerente con l'ordine in cui è possibile osservare il commit delle transazioni.
Consideriamo di nuovo l'esempio bancario utilizzato in precedenza. In un sistema che fornisce la serietà ma non la coerenza esterna, anche se il cliente ha eseguito T1 e poi T2 in sequenza, il sistema sarebbe autorizzato a riordinarli, il che potrebbe comportare una sanzione per l'addebito a causa di fondi insufficienti.
Spanner offre elevata coerenza?
Sì, Di fatto, Spanner offre coerenza esterna, una proprietà più elevata rispetto a un'elevata coerenza. La modalità predefinita per le letture in Spanner è "strong", che garantisce che vengano osservati gli effetti di tutte le transazioni sottoposte a commit prima dell'inizio dell'operazione, indipendentemente da quale replica riceve la lettura.
Qual è la differenza tra elevata coerenza e coerenza esterna?
Un protocollo di replica mostra un'elevata coerenza se gli oggetti replicati sono linearizzabili. Come la linearizzabilità, una "elevata coerenza" è più debole della "coerenza esterna", perché non fornisce informazioni sul comportamento delle transazioni.
Spanner fornisce coerenza finale (o lazy)?
Spanner offre coerenza esterna, una proprietà molto più efficace rispetto alla coerenza finale. La coerenza finale garantisce garanzie più deboli per prestazioni migliori. La coerenza finale è problematica perché significa che i lettori possono osservare il database in uno stato in cui non è mai stato realmente (ad esempio, una lettura potrebbe osservare uno stato in cui è stato eseguito il commit della Transazione B, ma non della Transazione A, anche se A è avvenuta prima di B). Spanner offre letture inattive, che offrono vantaggi in termini di prestazioni simili alla coerenza finale, ma con garanzie di coerenza molto più elevate. Una lettura inattiva restituisce i dati di un timestamp "precedente", che non può bloccare le scritture perché le versioni precedenti dei dati sono immutabili.