TrueTime è un orologio distribuito ad alta disponibilità fornito alle applicazioni su tutti i server Google.1 TrueTime consente alle applicazioni di generare timestamp con aumento monotonico: un'applicazione può calcolare un timestamp T che deve essere garantito maggiore di qualsiasi timestamp T se ha terminato la generazione prima che T abbia iniziato a essere generato. Questa garanzia è valida su tutti i server e su tutti i timestamp.
Questa funzionalità di TrueTime viene utilizzata da Spanner per assegnare timestamp alle transazioni. Nello specifico, 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à multiversione, la garanzia dell'ordine sui timestamp consente ai client di Spanner di eseguire letture coerenti in un intero database (anche in più regioni Cloud) senza bloccare le scritture.
Coerenza esterna
Spanner offre ai clienti le più rigide garanzie di controllo della contemporaneità per le transazioni, ovvero coerenza esterna2. Sotto la 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 aumentare le prestazioni e la disponibilità. Inoltre, se una transazione viene completata prima dell'inizio del commit di un'altra transazione, il sistema garantisce che i client non possano mai vedere uno stato che include l'effetto della seconda transazione, ma non della prima. Intuitivamente, Spanner non è semanticamente indistinguibile da un database Anche se offre garanzie così solide, Spanner consente alle applicazioni di raggiungere prestazioni paragonabili ai database che forniscono garanzie più deboli (in cambio prestazioni superiori). 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 delle applicazioni. Ad esempio, supponiamo che tu abbia 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 commette innanzitutto una transazione T1 per depositare 200 $sul conto di risparmio, quindi emette una seconda transazione T2 per addebitare 150 $sul conto corrente. Inoltre, supponiamo che, alla fine della giornata, i saldi negativi di un account siano coperti automaticamente da altri account e che un cliente riceva una sanzione se il saldo totale di tutti i suoi account è negativo in qualsiasi momento di quella giornata. La coerenza esterna garantisce che, poiché il T2 inizia a impegnarsi al termine del T1, tutti i lettori del database noteranno che il deposito T1 si è verificato prima dell'addebito T2. In altre parole, la coerenza esterna garantisce che nessuno vedrà mai uno stato in cui si verifica il T2 prima del T1; in altre parole, l'addebito non subirà mai una sanzione per insufficienza di fondi.
Un database tradizionale che utilizza l'archiviazione a versione singola e il rigoroso blocco a due fasi fornisce coerenza esterna. Purtroppo, in un sistema di questo tipo, ogni volta che un'applicazione desidera leggere i dati più aggiornati (che chiamiamo "lettura elevata"), il sistema acquisisce un blocco di lettura sui dati, che blocca le scritture sui dati letti.
Timestamp e controllo della contemporaneità multiversione (MVCC)
Per leggere senza bloccare le scritture, Spanner e molti altri sistemi di database mantengono più versioni immutabili dei dati (spesso chiamati controllo della contemporaneità multi-versione). Una scrittura crea una nuova versione immutabile il cui timestamp è quello della transazione di scrittura. Una "lettura snapshot" in un timestamp restituisce il valore della versione più recente precedente al timestamp e non ha bisogno di bloccare le scritture. È quindi importante che i timestamp assegnati alle versioni siano coerenti con l'ordine in cui è possibile osservare il commit delle transazioni. Chiamiamo questa proprietà "timestamping corretto"; tieni presente che l'esistenza di un timestamp corretto equivale alla coerenza esterna.
Per capire perché è importante creare un timestamp corretto, consideriamo l'esempio di banking della sezione precedente. Senza un timestamp corretto, a T2 potrebbe essere assegnato un timestamp precedente a quello assegnato a T1 (ad esempio, se un sistema ipotetico ha utilizzato orologi locali invece di TrueTime e l'orologio del server che elabora T2 ha subito un leggero ritardo). Una lettura istantanea potrebbe quindi riflettere l'addebito del T2, ma non il bonifico T1, anche se il cliente ha visto il termine del bonifico prima di iniziare l'addebito.
Ottenere un timestamp corretto è semplice per un database di una singola macchina (ad esempio, è sufficiente assegnare i timestamp da un contatore globale crescente in modo monotonico). Riuscire a farlo in un sistema ampiamente distribuito come Spanner, in cui i server di tutto il mondo devono assegnare i timestamp, è molto più difficile da fare in modo efficiente.
Spanner dipende da 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 la necessità di comunicazioni globali. In secondo luogo, li utilizza come timestamp per letture complesse, che consente l'esecuzione di letture complesse in un unico round di comunicazione, anche anche su più server.
Domande frequenti
Quali garanzie di coerenza offre Spanner?
Spanner fornisce coerenza esterna, che è la proprietà a coerenza più elevata 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 un modo non distinguibile da un sistema in cui le transazioni vengono eseguite serialmente 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 client vede l'inizio del commit di una transazione T2 dopo il termine di un'altra transazione T1, il sistema assegnerà a T2 un timestamp superiore a quello di T1.
Spanner offre la linearizzabilità?
Sì. Infatti, Spanner fornisce coerenza esterna, che è una proprietà più efficace della linearizzabilità, perché la linearizzabilità non indica nulla sul comportamento delle transazioni. La linearizzabilità è una proprietà degli oggetti simultanei che supportano le operazioni atomiche di lettura e scrittura. 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 contenenti più operazioni di lettura e scrittura su oggetti arbitrari. La linearizzabilità 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 offre la serializzabilità?
Sì. Infatti, Spanner fornisce coerenza esterna, che è una proprietà più rigorosa rispetto alla serializzabilità. Un sistema di elaborazione delle transazioni è serializzabile se esegue le transazioni in un modo che non è distinguibile da un sistema in cui le transazioni sono eseguite serialmente. Spanner garantisce inoltre che l'ordine seriale sia coerente con l'ordine in cui è possibile osservare il commit delle transazioni.
Consideriamo ancora l'esempio del settore bancario usato in precedenza. In un sistema che fornisce serializzabilità ma non coerenza esterna, anche se il cliente ha eseguito T1 e poi T2 in sequenza, il sistema sarebbe consentito riordinarli, causando così una sanzione all'addebito a causa di fondi insufficienti.
Spanner offre elevata coerenza?
Sì. Infatti, Spanner fornisce coerenza esterna, che è una proprietà più efficace rispetto a un'elevata coerenza. La modalità predefinita per le letture in Spanner è "strong", il che garantisce che osservino gli effetti di tutte le transazioni eseguite prima dell'inizio dell'operazione, indipendentemente dalla replica che riceve la lettura.
Qual è la differenza tra elevata coerenza e coerenza esterna?
Un protocollo di replica mostra "elevata coerenza" se gli oggetti replicati sono linearizzabili. Come la linearizzabilità, l'"elevata coerenza" è più debole della "coerenza esterna", perché non fornisce alcuna informazione sul comportamento delle transazioni.
Spanner fornisce coerenza finale (o lazy)?
Spanner fornisce coerenza esterna, che è una proprietà molto più efficace della coerenza finale. La coerenza finale negozia garanzie più deboli per ottenere prestazioni migliori. La coerenza finale è problematica perché i lettori possono osservare il database in uno stato in cui non è mai stato realmente in cui si trova (ad esempio, una lettura potrebbe osservare uno stato in cui la transazione B è impegnata ma la transazione A non lo è, anche se A è avvenuta prima di B). Spanner offre letture inattive, che offrono vantaggi in termini di prestazioni simili a quelli della coerenza finale, ma con garanzie di coerenza molto più elevate. Una lettura inattiva restituisce i dati da un timestamp "precedente", che non può bloccare le scritture perché le versioni precedenti dei dati sono immutabili.