În Spanner, TrueTime & Teorema CAP , Eric Brewer scrie:
Un lucru subtil despre Spanner este că devine serializabil din blocări, dar devine consistență externă (similar cu linearizabilitate ) din TrueTime [ accent adăugat ].
Care este definiția consistenței externe , și în ce se deosebește de liniarizabilitatea ?
Comentarii
- Aceasta este o întrebare excelentă și aș dori ca Eric să aibă a elaborat un pic aici. Este linizabil sau nu? 🙂
Răspuns
Coerența externă nu are o semnificație fixă. În acest context, are sensul care apare în propoziția următoare din document:
Pentru oricare două tranzacții, $ T_1 $ și $ T_2 $ (chiar dacă pe laturile opuse ale glob): dacă $ T_2 $ începe să se angajeze după ce $ T_1 $ termină comiterea, atunci marca de timp pentru $ T_2 $ este mai mare decât marca de timp pentru $ T_1 $.
Comentarii
- Cu cât mă gândesc mai mult la asta, acest lucru mi se pare o linie de liniaritate, deoarece toate tranzacțiile sunt ordonate. Din păcate, uneori acești termeni sunt subtili. .. Oricine nu este de acord? Adică tranzacțiile sunt serializabile și sunt ordonate în totalitate pe baza timpului de comitere. Poate că subtilitatea constă în modul în care 2PC este implementat în Spanner?
- @Bminer Linearizability este un model de coerență care se aplică numai obiectelor individuale, în care tranzacțiile pot implica o multiple obiecte.
- @LorinHochstein – Ha! Miroase a cuvinte tocate. Întregul punct al terminologiei este de a ajuta oamenii reali să conceptualizeze ce garanții primesc, în special în ceea ce privește tranzacțiile. Linearizabilitate + serializabilitate este cea mai puternică garanție și cred că ' este ceea ce se referă documentele Spanner cu termenul " consistență externă. " Dar, ne pune întrebarea: știe cineva cu adevărat ce " consistență externă " mijloace? 🙂
Răspuns
Vă puteți gândi la consistența externă din izolarea tranzacțiilor (Tx) și din punctul de vedere al ordinii . În izolarea Tx vorbim, consistența externă este echivalentă cu izolarea serializabilă strictă, unde „strictă” este partea de constrângere în timp real (ca și în liniarizabilitate).
Asta înseamnă, din nou, că pentru un client de sistem, Tx observabilă efectele secundare sunt echivalente cu un sistem, în care toate Tx-urile se desfășoară izolat fără nicio concurență și unde se păstrează ordonarea lor în timp real, așa cum a văzut clientul. Mai important, aceeași comandă este văzută de orice alt client fără legătură.
Citiți mai multe despre distincție la acest blog .
Răspuns
La menționarea " consistență externă " , Brewer se referă la B. Liskov. Utilizări practice ale ceasurilor sincronizate în sisteme distribuite . Principiile ACM de calcul distribuit (PODC). Montreal, Canada, august 1991.
Liskov, în termen, se referă la Gifford D.K. Stocarea informațiilor într-un sistem computerizat descentralizat . Raport tehnic CSL-81-8, Xerox Corporation, martie 1983
Iată cum definește Gifford consistența externă:
Extern consistența garantează că o tranzacție va primi întotdeauna informații actuale. Folosind conceptele pe care tocmai le-am introdus, putem oferi o definiție formală a consistenței externe. Ordinea de timp efectivă în care tranzacțiile se finalizează definește un program serial unic. Acest program serial se numește em> calendar extern . Se spune că un sistem oferă consistență externă dacă garantează că programul pe care îl va utiliza pentru a procesa un set de tranzacții este echivalent cu programul său extern.
După cum menționează @Oleg, sună ca serializabilitate strictă .