In Spanner, TrueTime & Il teorema CAP , Eric Brewer scrive:
Una cosa sottile di Spanner è che ottiene la serializzabilità dai blocchi, ma ottiene coerenza esterna (simile a linearizzabilità ) da TrueTime [ enfasi aggiunta ].
Qual è la definizione di coerenza esterna , e in cosa differisce dalla linearizzabilità ?
Commenti
- Questa è unottima domanda, e vorrei che Eric lavesse elaborato un po qui. È linearizzabile o no? 🙂
Risposta
La coerenza esterna non ha un significato fisso. In questo contesto, ha il significato che appare nella frase immediatamente successiva del documento:
Per due transazioni qualsiasi, $ T_1 $ e $ T_2 $ (anche se sui lati opposti del globo): se $ T_2 $ inizia a eseguire il commit dopo che $ T_1 $ termina il commit, il timestamp per $ T_2 $ è maggiore del timestamp per $ T_1 $.
Commenti
- Più ci penso, questo suona molto come la linearizzabilità per me perché tutte le transazioni sono ordinate.Sfortunatamente, a volte questi termini sono sottili. .. Qualcuno non è daccordo? Voglio dire, le transazioni sono serializzabili e sono totalmente ordinate in base al tempo di commit. Forse la sottigliezza sta nel modo in cui 2PC è implementato in Spanner?
- @Bminer Linearizability è un modello di coerenza che si applica solo a singoli oggetti, dove le transazioni possono coinvolgere più o oggetti.
- @LorinHochstein – Ha! Che puzza di parole minacciose. Il punto centrale della terminologia è aiutare le persone reali a concettualizzare le garanzie che ottengono, soprattutto per quanto riguarda le transazioni. Linearizzabilità + serializzabilità è la garanzia più forte e penso che ' sia ciò a cui si riferiscono i documenti di Spanner con il termine " coerenza esterna. " Ma si pone la domanda: qualcuno sa davvero qual è la " coerenza esterna " si intende? 🙂
Risposta
Puoi pensare alla coerenza esterna dallisolamento delle transazioni (Tx) e dal punto di vista dellordine . Nellisolamento Tx, la consistenza esterna è equivalente allo stretto isolamento serializzabile, dove “rigoroso” è la parte del vincolo in tempo reale (come nella linearizzabilità).
Anche questo significa che per un client di sistema Tx osservabile gli effetti collaterali sono equivalenti a un sistema, in cui tutte le Tx avvengono in isolamento senza alcuna concorrenza e in cui viene preservato il loro ordinamento in tempo reale, come visto dal client. Ancora più importante, questo stesso ordine è visto da qualsiasi altro client non correlato.
Ulteriori informazioni sulla distinzione sono disponibili in questo blog .
Risposta
Quando si menziona " coerenza esterna " , Brewer fa riferimento a B. Liskov. Usi pratici di orologi sincronizzati in sistemi distribuiti . Principi ACM di calcolo distribuito (PODC). Montreal, Canada, agosto 1991.
Liskov, in termini, fa riferimento a Gifford D.K. Archiviazione delle informazioni in un sistema informatico decentralizzato . Rapporto tecnico CSL-81-8, Xerox Corporation, marzo 1983
Ecco come Gifford definisce la coerenza esterna:
Esterno la coerenza garantisce che una transazione riceverà sempre informazioni aggiornate. Utilizzando i concetti che abbiamo appena introdotto, possiamo fornire una definizione formale di coerenza esterna. Lordine temporale effettivo in cui le transazioni vengono completate definisce una pianificazione seriale univoca. Questa pianificazione seriale è chiamata pianificazione esterna . Si dice che un sistema fornisce coerenza esterna se garantisce che la pianificazione che utilizzerà per elaborare un insieme di transazioni è equivalente alla sua pianificazione esterna.
Come menzionato da @Oleg, suona come serializzabilità rigorosa .