In Spanner, TrueTime & The CAP Theorem , Eric Brewer schrijft:
Een subtiel aspect van Spanner is dat het serialiseerbaarheid krijgt van sloten, maar het krijgt externe consistentie (vergelijkbaar met lineariseerbaarheid ) van TrueTime [ nadruk toegevoegd ].
Wat is de definitie van externe consistentie , en hoe verschilt het van lineariseerbaarheid ?
Opmerkingen
- Dit is een geweldige vraag, en ik zou willen dat Eric hier een beetje uitgewerkt. Is het lineariseerbaar of niet? 🙂
Answer
Externe consistentie heeft geen vaste betekenis. In deze context heeft het de betekenis die in de volgende zin van het document verschijnt:
Voor twee transacties, $ T_1 $ en $ T_2 $ (zelfs als ze aan weerszijden van de globe): als $ T_2 $ begint met vastleggen nadat $ T_1 $ klaar is met vastleggen, dan is het tijdstempel voor $ T_2 $ groter dan het tijdstempel voor $ T_1 $.
Opmerkingen
- Hoe meer ik erover nadenk, dit klinkt voor mij heel erg als lineariseerbaarheid omdat alle transacties geordend zijn. Helaas zijn deze termen soms subtiel. .. Iedereen is het daar niet mee eens? Ik bedoel, de transacties zijn serialiseerbaar en ze zijn volledig geordend op basis van de vastlegtijd. Misschien ligt de subtiliteit in hoe 2PC wordt geïmplementeerd in Spanner?
- @Bminer Linearizeerbaarheid is een consistentiemodel dat is alleen van toepassing op enkele objecten, waarbij transacties meerdere o kunnen betreffen bjects.
- @LorinHochstein – Ha! Dat ruikt naar gehakte woorden. Het hele punt van de terminologie is om echte mensen te helpen een idee te krijgen van welke garanties ze krijgen, vooral met betrekking tot transacties. Linearizeerbaarheid + serialiseerbaarheid is de sterkste garantie, en ik denk dat ' is waarnaar de Spanner-documenten verwijzen met de term " externe consistentie. " Maar het roept de vraag op: weet iemand echt wat " externe consistentie " middelen? 🙂
Antwoord
U kunt nadenken over externe consistentie vanuit het oogpunt van isolatie van transacties (Tx) en volgorde . In Tx-isolatie spreekt de externe consistentie gelijk aan de strikte serialiseerbare isolatie, waarbij “strikt” het deel van de realtime beperking is (zoals bij lineariseerbaarheid).
Dat betekent weer dat voor een systeemclient waarneembare Tx bijwerkingen zijn gelijk aan een systeem, waar alle Tx geïsoleerd plaatsvinden zonder enige gelijktijdigheid en waar hun real-time ordening, zoals gezien door de klant, behouden blijft. Wat nog belangrijker is, is dat dezelfde volgorde wordt gezien door elke andere niet-gerelateerde klant.
Lees meer over het onderscheid op dit blog .
Answer
Bij het vermelden van " externe consistentie " Brewer verwijst naar B. Liskov. Praktisch gebruik van gesynchroniseerde klokken in gedistribueerde systemen . ACM Principles of Distributed Computing (PODC). Montreal, Canada, augustus 1991.
Liskov verwijst in term naar Gifford D.K. Informatieopslag in een gedecentraliseerd computersysteem . Technisch rapport CSL-81-8, Xerox Corporation, maart 1983
Hier is hoe Gifford externe consistentie definieert:
Extern consistentie garandeert dat een transactie altijd actuele informatie ontvangt. Met behulp van de concepten die we zojuist hebben geïntroduceerd, kunnen we een formele definitie van externe consistentie geven. De werkelijke tijdsvolgorde waarin transacties zijn voltooid, definieert een uniek serieel schema. Dit serieel schema wordt de extern schema . Van een systeem wordt gezegd dat het externe consistentie biedt als het garandeert dat het schema dat het zal gebruiken om een reeks transacties te verwerken gelijk is aan het externe schema.
Zoals @Oleg vermeldt, klinkt dit als strikte serialiseerbaarheid .