I Skiftnyckel, TrueTime & CAP Theorem , skriver Eric Brewer:
En subtil sak med Spanner är att den får seriabilitet från lås, men det blir extern konsistens (liknar linjäritetsförmåga ) från TrueTime [ betoning tillagd ].
Vad är definitionen för extern konsistens , och hur skiljer det sig från linjäritetsbarhet ?
Kommentarer
- Det här är en bra fråga, och jag önskar att Eric skulle ha utarbetat lite här. Är det linjärt eller inte? 🙂
Svar
Extern konsistens har inte en fast innebörd. I detta sammanhang har den betydelse som visas i nästa mening i dokumentet:
För två transaktioner, $ T_1 $ och $ T_2 $ (även om på motsatta sidor av globe): om $ T_2 $ börjar åta sig efter att $ T_1 $ har slutfört, är tidsstämpeln för $ T_2 $ större än tidsstämpeln för $ T_1 $.
Kommentarer
- Ju mer jag tänker på det låter det här väldigt mycket som linjäritet för mig eftersom alla transaktioner är beställda. .. Någon håller inte med? Jag menar, transaktionerna kan serieiseras och de ordnas helt baserat på kommittid. Kanske subtiliteten ligger i hur 2PC implementeras i Spanner?
- @Bminer Linearizability är en konsistensmodeller som gäller endast enstaka objekt, där transaktioner kan involvera flera o bjects.
- @LorinHochstein – Ha! Det luktar som finhackningsord. Hela poängen med terminologin är att hjälpa riktiga människor att föreställa sig vilka garantier de får, särskilt när det gäller transaktioner. Linjärsbarhet + serialiserbarhet är den starkaste garantin, och jag tror att ' är vad Spanner docs hänvisar till med termen " extern konsistens. " Men det väcker frågan: vet någon verkligen vad " extern konsistens " betyder att? 🙂
Svar
Du kan tänka på extern konsistens från transaktioner (Tx) isolering och ordningssynpunkt . I Tx-isolering talar den externa konsistensen likvärdig med den strikta, seriösa isoleringen, där ”strikt” är den realtidsbegränsande delen (som i lineariserbarhet).
Det betyder återigen att för en systemklient kan observeras Tx biverkningar är likvärdiga med ett system, där alla Tx äger rum isolerat utan någon samtidighet och där deras realtidsbeställning, som klienten ser, bevaras. Ännu viktigare är att samma beställning ses av alla andra icke-relaterade klienter.
Läs mer om skillnaden på den här bloggen .
Svar
När vi nämner " extern konsistens " , Brewerreferenser B. Liskov. Praktiska användningar av synkroniserade klockor i distribuerade system . ACM-principer för distribuerad databehandling (PODC). Montreal, Kanada, augusti 1991.
Liskov, i termen, referenser Gifford D.K. Informationslagring i ett decentraliserat datorsystem . Teknisk rapport CSL-81-8, Xerox Corporation, mars 1983
Så här definierar Gifford extern konsistens:
Extern konsistens garanterar att en transaktion alltid kommer att få aktuell information. Med hjälp av de begrepp vi just har introducerat kan vi tillhandahålla en formell definition av extern konsistens. Den faktiska tidsordningen för transaktioner som definierar definierar ett unikt serieschema. em> externt schema . Ett system sägs ge extern konsistens om det garanterar att schemat som det kommer att använda för att bearbeta en uppsättning transaktioner motsvarar dess externa schema.
Som @Oleg nämner låter det här som strikt serieiserbarhet .