Engagemang beställning

Commitment ordering ( CO ) är en klass av interoperabla serialiseringstekniker för samtidig kontroll av databaser , transaktionsbearbetning och relaterade applikationer. Det tillåter optimistiska (icke-blockerande) implementeringar. Med spridningen av flerkärniga processorer har CO också använts alltmer i samtidig programmering , transaktionsminne och mjukvarutransaktionsminne (STM) för att uppnå serialiserbarhet optimistiskt . CO är också namnet på den resulterande transaktionsschemaegenskapen ( historik), definierad 1988 med namnet dynamisk atomicitet . I ett CO-kompatibelt schema är den kronologiska ordningen för åtagandehändelser för transaktioner kompatibel med prioritetsordningen för respektive transaktioner. CO är ett brett specialfall av konflikt serialiserbarhet och effektiva medel ( pålitliga , högpresterande, distribuerade och skalbara ) för att uppnå global serialiserbarhet (modulär serialiserbarhet) över alla samlingar av databassystem som eventuellt använder olika samtidighetskontrollmekanismer (CO gör också varje system serialiserbarhet kompatibel, om inte redan).

Varje icke-CO-kompatibelt databassystem utökas med en CO-komponent (samordnaren för åtagandeordern—COCO) som beställer åtagandehändelserna för CO-överensstämmelse, utan varken dataåtkomst eller någon annan transaktionsoperationsinterferens. Som sådan tillhandahåller CO en låg overhead, allmän lösning för global serialiserbarhet (och distribuerad serialiserbarhet), som är instrumentell för global samtidighetskontroll (och distribuerad samtidighetskontroll ) av multidatabassystem och andra transaktionsobjekt, möjligen högdistribuerade (t.ex. inom molnberäkningar) , grid computing och nätverk av smartphones ). Ett atomärt åtagandeprotokoll (ACP; av vilken typ som helst) är en grundläggande del av lösningen, som används för att bryta globala cykler i konfliktgrafen (företräde, serialiserbarhet). CO är den mest allmänna egenskapen (ett nödvändigt villkor ) som garanterar global serialiserbarhet, om de inblandade databassystemen inte delar samtidighetskontrollinformation utöver meddelanden i atomic commitment protocol (omodifierade) och inte har någon kunskap om huruvida transaktioner är globala eller lokala (databassystemen är autonoma ). Sålunda är CO (med dess varianter) den enda allmänna tekniken som inte kräver den typiskt kostsamma distributionen av lokal samtidighetskontrollinformation (t.ex. lokala prioritetsrelationer, lås, tidsstämplar eller biljetter). Den generaliserar den populära starka strikta tvåfaslåsningsegenskapen (SS2PL), som i kombination med tvåfasprotokollet (2PC) är den de facto-standarden för att uppnå global serialisering över (SS2PL-baserade) databassystem. Som ett resultat kan CO-kompatibla databassystem (med olika typer av samtidighetskontroll) transparent ansluta sådana SS2PL-baserade lösningar för global serialisering.

Dessutom löses låsningsbaserade globala dödlägen automatiskt i en CO-baserad multi-databasmiljö, en viktig sidofördel (inklusive specialfallet med en helt SS2PL-baserad miljö; ett tidigare obemärkt faktum för SS2PL ) .

Vidare ger strikt åtagandebeställning (SCO; Raz 1991c ), skärningspunkten mellan Strictness och CO, bättre prestanda (kortare genomsnittlig transaktionssluttid och vilket resulterar i bättre transaktionsgenomströmning) än SS2PL närhelst läs-skrivkonflikter förekommer (identiskt blockeringsbeteende för skrivning -läs och skriv-skriv-konflikter; jämförbar låsning overhead). Fördelen med SCO är särskilt under låsstrid. Strikthet tillåter både SS2PL och SCO att använda samma effektiva databasåterställningsmekanismer .

Det finns två stora generaliserande varianter av CO, utökad CO (ECO; Raz 1993a ) och multiversion CO (MVCO; Raz 1993b ). De ger också global serialisering utan lokal distribution av samtidighetskontrollinformation, kan kombineras med vilken relevant samtidighetskontroll som helst och tillåter optimistiska (icke-blockerande) implementeringar. Båda använder ytterligare information för att lindra CO-begränsningar och uppnå bättre samtidighet och prestanda. Röstordning (VO eller Generalized CO (GCO); Raz 2009 ) är en containerschemauppsättning (egenskap) och teknik för CO och alla dess varianter. Lokal VO är nödvändig för att garantera global serialiserbarhet om deltagarna i atomic commitment protocol (ACP) inte delar samtidighetskontrollinformation (har den generaliserade autonomiegenskapen ). CO och dess varianter samverkar transparent, vilket garanterar global serialiserbarhet och automatisk global dödlägesupplösning tillsammans i en blandad, heterogen miljö med olika varianter.

Översikt

Commitment ordering (CO; Raz 1990 , 1992 , 1994 , 2009 ) har också kallats Dynamic atomicity (sedan 1988), commit ordering , commit order serialiserbarhet och stark återvinningsbarhet (sedan 1991). Det senare är ett missvisande namn eftersom CO är ojämförligt med återvinningsbarhet och termen "stark" antyder ett specialfall. Detta innebär att en betydande återvinningsbarhetsegenskap inte nödvändigtvis har CO-egenskapen och vice versa.

Under 2009 har CO karakteriserats som en viktig metod för samtidighetskontroll, tillsammans med de tidigare kända (sedan 1980-talet) tre huvudmetoder: låsning , tidsstämpelbeställning och serialiseringsgraftestning , och som en möjliggörare för interoperabilitet av system som använder olika mekanismer för samtidighetskontroll.

I ett federerat databassystem eller något annat mer löst definierat multidatabassystem, som vanligtvis distribueras i ett kommunikationsnätverk, sträcker sig transaktioner över flera och möjligen distribuerade databaser . Att upprätthålla global serialisering i ett sådant system är problematiskt. Även om varje lokalt schema för en enskild databas fortfarande kan serialiseras, är det globala schemat för ett helt system inte nödvändigtvis serialiserbart. Det massiva kommunikationsutbytet av konfliktinformation som behövs mellan databaser för att nå konfliktserialiserbarhet skulle leda till oacceptabel prestanda, främst på grund av dator- och kommunikationslatens . Problemet med att uppnå global serialiserbarhet på ett effektivt sätt hade karakteriserats som öppet fram till offentliggörandet av CO 1991 av dess uppfinnare Yoav Raz ( Raz 1991a ; se även Global serialiserbarhet ).

Att upprätthålla CO är ett effektivt sätt att upprätthålla serialisering av konflikter globalt i ett distribuerat system eftersom upprätthållande av CO lokalt i varje databas (eller andra transaktionsobjekt) också upprätthåller det globalt. Varje databas kan använda vilken, möjligen annan, typ av samtidighetskontrollmekanism. Med en lokal mekanism som redan tillhandahåller konfliktserialisering, orsakar inte upprätthållande av CO lokalt några andra avbrott, eftersom upprätthållande av CO lokalt inte påverkar mekanismens schemaläggningsstrategi för dataåtkomst (denna schemaläggning bestämmer serialiseringsrelaterade avbrytningar; en sådan mekanism vanligtvis inte överväga åtagandehändelserna eller deras ordning). CO-lösningen kräver ingen kommunikationsoverhead eftersom den endast använder (omodifierade) atomic commitment protocol meddelanden, som redan behövs av varje distribuerad transaktion för att nå atomicitet. Ett atomärt åtagandeprotokoll spelar en central roll i den distribuerade CO-algoritmen, som upprätthåller CO globalt genom att bryta globala cykler (cykler som spänner över två eller flera databaser) i den globala konfliktgrafen. CO, dess specialfall och dess generaliseringar är interoperabla och uppnår global serialiserbarhet samtidigt som de på ett transparent sätt används tillsammans i en enda heterogen distribuerad miljö som består av objekt med möjligen olika samtidighetskontrollmekanismer. Som sådan ger Commitment ordering , inklusive dess specialfall, och tillsammans med dess generaliseringar (se CO-varianter nedan), en allmän, högpresterande, fullt distribuerad lösning (ingen central bearbetningskomponent eller central datastruktur behövs) för att garantera global serialiserbarhet i heterogena miljöer av multidatabassystem och andra multipla transaktionsobjekt (objekt med tillstånd som endast nås och modifieras av transaktioner; t.ex. inom ramen för transaktionsprocesser och inom molnberäkning och gridberäkning). CO-lösningen skalas upp med nätverksstorlek och antalet databaser utan någon negativ inverkan på prestanda (förutsatt att statistiken för en enstaka distribuerad transaktion, t.ex. det genomsnittliga antalet databaser involverade i en enda transaktion, är oförändrad).

Med spridningen av flerkärniga processorer har Optimistic CO (OCO) också använts i allt högre grad för att uppnå serialiserbarhet i transaktionsminne för programvara, och många STM-artiklar och patent som använder "commit order" har redan publicerats (t.ex. Zhang et al. 2006) ).

Åtagandebeställningslösningen för global serialisering

Allmän karakterisering av CO

Commitment ordering (CO) är ett specialfall av konflikt serialiserbarhet. CO kan upprätthållas med icke-blockerande mekanismer (varje transaktion kan slutföra sin uppgift utan att ha dess dataåtkomst blockerad, vilket möjliggör optimistisk samtidighetskontroll ; åtaganden kan dock blockeras). I ett CO-schema motsvarar åtagandehändelsernas ( partiella ) prioritetsordning för transaktionerna prioritetsordningen (delvis) för respektive transaktioner i den ( riktade ) konfliktgrafen (prioritetsgraf, serialiserbarhetsgraf), som induceras av deras motstridiga åtkomst operationer (vanligtvis läs- och skrivoperationer (infoga/ändra/ta bort) operationer; CO gäller även för operationer på högre nivå, där de är motstridiga om de inte är kommutativa , såväl som för konflikter mellan operationer på flerversionsdata).

Definition: åtagandebeställning

Låt $T_{1},T_{2}$ vara två åtagna transaktioner i ett schema, så att $T_{2}$ är i konflikt med $T_{1}$ ( $T_{1}$ föregår $T_{2}$ ). Schemat har Commitment ordering (CO), om för varannan sådana transaktioner $T_{1}$ commits innan $T_{2}$ commits.

Åtagandebeslutshändelserna genereras av antingen en lokal åtagandemekanism eller ett atomärt åtagandeprotokoll om olika processer behöver nå en konsensus om huruvida de ska åta sig eller avbryta. Protokollet kan vara distribuerat eller centraliserat. Transaktioner kan begås samtidigt om commit-delordern tillåter (om de inte har motstridiga operationer). Antag att olika motstridiga operationer inducerar olika delordningar av samma transaktioner. I så fall har konfliktdiagrammet cykler och schemat kommer att bryta mot serialiseringsbarheten när alla transaktioner i en cykel har genomförts. I detta fall kan ingen delordning för åtagandehändelser hittas. Således måste cykler i konfliktdiagrammet brytas genom att avbryta transaktioner. Alla konflikter som kan serialiseras kan dock göras till CO utan att avbryta någon transaktion genom att korrekt fördröja commit-händelser för att följa transaktionernas prioritetsordning.

CO-upprätthållande i sig är inte tillräckligt som en samtidighetskontrollmekanism eftersom CO saknar återvinningsbarhetsegenskapen, som också bör stödjas.

Den distribuerade CO-algoritmen

en fullständigt distribuerad algoritm för verkställande av global åtagandebeställning som använder lokal CO för varje deltagande databas, och som endast behöver (omodifierade) Atomic-åtagandeprotokollmeddelanden utan vidare kommunikation. Den distribuerade algoritmen är kombinationen av lokala (till varje databas) CO-algoritmprocesser och ett atomärt åtagandeprotokoll (som kan distribueras fullt ut). Atomiskt åtagandeprotokoll är viktigt för att upprätthålla atomiciteten för varje distribuerad transaktion (för att bestämma om den ska begås eller avbrytas; denna procedur utförs alltid för distribuerade transaktioner, oberoende av samtidighetskontroll och CO). Ett vanligt exempel på ett atomärt åtagandeprotokoll är tvåfasprotokollet, som är motståndskraftigt mot många typer av systemfel. I en pålitlig miljö, eller när processer vanligtvis misslyckas tillsammans (t.ex. i samma integrerade krets ), kan ett enklare protokoll för atomärt engagemang användas (t.ex. en enkel handskakning av distribuerade transaktioners deltagande processer med någon godtycklig men känd speciell deltagare, transaktionens samordnare, dvs en typ av enfasprotokoll ). Ett atomärt åtagandeprotokoll når konsensus bland deltagarna om huruvida de ska begå eller avbryta en distribuerad (global) transaktion som sträcker sig över dessa deltagare. Ett väsentligt steg i varje sådant protokoll är JA-röst (antingen explicit eller implicit) av varje deltagare, vilket innebär en skyldighet för den röstberättigade deltagaren att lyda protokollets beslut, antingen begå eller avbryta. Annars kan en deltagare ensidigt avbryta transaktionen genom en uttrycklig NEJ-röst. Protokollet förbinder transaktionen endast om JA-röster har mottagits från alla deltagare (därmed anses en utebliven röst vanligtvis vara ett NEJ). Annars avbryter protokollet transaktionen. De olika atomic commit-protokollen skiljer sig bara åt i deras förmåga att hantera olika datormiljöfelsituationer och mängden arbete och andra datorresurser som behövs i olika situationer.

Hela CO-lösningen för global serialiserbarhet är baserad på det faktum att atomic commitment-protokollet så småningom avbryter denna transaktion i händelse av en utebliven röst för en distribuerad transaktion.

Upprätthålla global CO

I varje databassystem bestämmer en lokal CO-algoritm den nödvändiga åtagandeordningen för den databasen. Genom karakteriseringen av CO ovan beror denna ordning på den lokala prioritetsordningen för transaktioner, som är ett resultat av de lokala dataåtkomstschemaläggningsmekanismerna. Följaktligen är JA-röster i det atomära åtagandeprotokollet schemalagda för varje (oavbruten) distribuerad transaktion (i det följande betyder "en röst" en JA-röst). Antag att det finns en prioritetsrelation (konflikt) mellan två transaktioner. I så fall kommer den andra inte att röstas om innan den första har slutförts (antingen begått eller avbruten), för att förhindra eventuellt brott mot orderöverträdelser enligt protokollet om atomförpliktelse. Sådant kan hända eftersom protokollets beslutsordning inte nödvändigtvis är densamma som röstningsordningen. Om det inte finns någon företrädesrelation kan båda röstas om samtidigt. Denna röstordningsstrategi säkerställer att även det atomära åtagandeprotokollet upprätthåller åtagandeordning, och det är en nödvändig förutsättning för att garantera Global CO (och den lokala CO i en databas; utan det både Global CO och Local CO (en egenskap som betyder att varje databas är CO-kompatibel) kan överträdas).

Men eftersom databassystem schemalägger sina transaktioner oberoende, är det möjligt att transaktionernas prioritetsorder i två databaser eller fler inte är kompatibla (det finns ingen global delorder som kan bädda in respektive lokala delorder tillsammans ). Med CO är företrädesorder också åtagandeorder. När deltagande databaser i samma distribuerade transaktion inte har kompatibla lokala prioritetsorder för den transaktionen (utan att "veta" om det; vanligtvis finns ingen samordning mellan databassystem vid konflikter, eftersom den nödvändiga kommunikationen är massiv och oacceptabelt försämrar prestandan) betyder det att transaktionen ligger på en global cykel (som involverar två eller flera databaser) i den globala konfliktgrafen. I det här fallet kommer det atomära åtagandeprotokollet att misslyckas med att samla in alla röster som behövs för att genomföra den transaktionen: Genom röstordningsstrategin ovan kommer minst en databas att fördröja sin röst för den transaktionen på obestämd tid för att följa dess eget åtagande (prioritets) ordning , eftersom den kommer att vänta på att fullborda en annan, föregående transaktioner på den globala cykeln försenade på obestämd tid av en annan databas med en annan ordning. Detta innebär en dödläge för röstning som involverar databaserna i den cykeln. Som ett resultat kommer protokollet så småningom att avbryta någon låst transaktion på denna globala cykel, eftersom varje sådan transaktion saknar minst en deltagares röst. Valet av den specifika transaktionen på cykeln som ska avbrytas beror på atomic commitment-protokollets abortpolicyer (en timeout -mekanism är vanlig, men det kan resultera i mer än en nödvändig avbrytning per cykel; både förhindrande av onödiga avbrott och förkortning av avbrytningstiden kan uppnås genom en dedikerad abortmekanism för CO). Sådan avbrytning kommer att bryta den globala cykeln som involverar den distribuerade transaktionen. Både låsta transaktioner och eventuellt andra i konflikt med de låsta (och därmed blockerade) kommer att vara fria att rösta om. Det är värt att notera att varje databas som är involverad i röstlåset fortsätter att rösta regelbundet om transaktioner som inte står i konflikt med dess låsta transaktion, vanligtvis nästan alla utestående transaktioner. Sålunda, i fallet med inkompatibla lokala (partiella) åtagandeorder, behövs ingen åtgärd eftersom det atomära åtagandeprotokollet löser det automatiskt genom att avbryta en transaktion som är en orsak till inkompatibilitet. Detta innebär att ovanstående röstordningsstrategi också är ett tillräckligt villkor för att garantera Global CO.

Följande slutsats:

• Röstordningsstrategin för Global CO Enforcing Theorem

Låt $T_{1},T_{2}$ vara obestämda (varken begångna eller avbrutna) transaktioner i ett databassystem som tvingar CO för lokala transaktioner, så att $T_{2}$ är global och i konflikt med $T_{1}$ ( $T_{1}$ föregår $T_{2}$ ). Sedan, att ha $T_{1}$ avslutat (antingen begått eller avbruten) innan $T_{2}$ röstas fram för att begås ( röstordningsstrategin ) , i varje sådant databassystem i en multidatabasmiljö, är ett nödvändigt och tillräckligt villkor för att garantera Global CO (villkoret garanterar Global CO, som kan kränkas utan det).

Kommentarer:

1. Röstordningsstrategin som upprätthåller global CO hänvisas till som $CD^{3}C$ i ( Raz 1992 ) .
2. Lokal CO-egenskapen för ett globalt schema betyder att varje databas är CO-kompatibel. Av nödvändighetsdiskussionen följer direkt delen ovan att satsen även stämmer när "Global CO" ersätts med "Local CO" när globala transaktioner förekommer. Tillsammans betyder det att Global CO garanteras om och endast om Lokal CO garanteras (vilket är osant för Global konflikt serialiserbarhet och Lokal konflikt serialiserbarhet: Global innebär Lokal, men inte motsatsen).

Global CO innebär global serialiserbarhet.

Den globala CO-algoritmen innefattar att upprätthålla (lokal) CO i varje deltagande databassystem genom att beställa commits av lokala transaktioner (se Upprätthålla CO lokalt nedan) och upprätthålla röstordningsstrategin i teoremet ovan (för globala transaktioner).

Den exakta karakteriseringen av dödlägen för röstning efter globala cykler

Ovanstående globala cykelelimineringsprocess genom ett dödläge för röstning kan förklaras i detalj av följande observation:

För det första antas det, för enkelhetens skull, att varje transaktion når redo-att-begå-tillståndet och röstas fram av minst en databas (detta innebär att ingen blockering av lås sker). Definiera en "vänta på röst för att begå"-graf som en riktad graf med transaktioner som noder och en riktad kant från en första transaktion till en andra transaktion om den första transaktionen blockerar rösten för att begå för den andra transaktionen (motsats till konventionell kantriktning i en väntan-på-graf ). Sådan blockering sker endast om den andra transaktionen står i konflikt med den första transaktionen (se ovan). Således är denna "vänta på att rösta för att begå"-grafen identisk med den globala konfliktgrafen. En cykel i diagrammet "vänta på att rösten begår" innebär ett dödläge i röstningen. Därför finns det ett dödläge i röstningen om det finns en cykel i konfliktdiagrammet. De lokala serialiseringsmekanismerna eliminerar lokala cykler (begränsade till en enda databas). Följaktligen finns bara globala cykler kvar, som sedan elimineras av atomic commitment-protokollet när det avbryter låsta transaktioner med saknade (blockerade) respektive röster.

För det andra behandlas även lokala åtaganden: Observera att när man upprätthåller CO, kan även väntan på ett vanligt lokalt åtagande av en lokal transaktion blockera lokala åtaganden och röster för andra transaktioner vid konflikter, och situationen för globala transaktioner förändras inte också utan att förenkla antagandet ovan: Slutresultatet är detsamma även med ett lokalt engagemang för lokala transaktioner, utan att rösta i atomärt åtagande för dem.

Slutligen måste blockering av ett lås (som hittills har uteslutits) övervägas: Ett lås blockerar en motstridig operation och förhindrar att en konflikt förverkligas. Anta att låset släpps först efter att transaktionen är slut. I så fall kan den indirekt blockera antingen en omröstning eller en lokal commit av en annan transaktion (som nu inte kan bli klar), med samma effekt som en direkt blockering av en röst eller en lokal commit. En cykel genereras i konfliktgrafen endast om en sådan blockering av ett lås också representeras av en kant. Med sådana tillagda kanter som representerar händelser av blockering-för-ett-lås, blir konfliktgrafen en utökad konfliktgraf .

• Definition: förstärkt konfliktdiagram

En förstärkt konfliktgraf är en konfliktgraf med tillagda kanter: Förutom de ursprungliga kanterna finns en riktad kant från transaktion $T_{1}$ till transaktion $T_{2}$ om två villkor är uppfyllda:

1. $T_{2}$ blockeras av ett dataåtkomstlås som tillämpas av $T_{1}$ (blockeringen förhindrar konflikten mellan $T_{2}$ och $T_{1}$ från att materialiseras och ha en kant i den vanliga konfliktgrafen), och
2. Denna blockering kommer inte att sluta innan $T_{1}$ slutar (bekräftar eller avbryter; sant för alla låsningsbaserade CO)

Grafen kan också definieras som föreningen av den (vanliga) konfliktgrafen med (omvänd kant, vanlig) väntan-på-grafen

. Kommentarer:

1. Här, till skillnad från den vanliga konfliktgrafen, som endast har kanter för materialiserade konflikter, representeras alla materialiserade och icke-materialiserade konflikter av kanter.
2. Observera att alla nya kanter är alla (omvänt till de konventionella) kanterna på väntan-på-grafen . Vänta -på-grafen kan också definieras som grafen över icke-materialiserade konflikter. Enligt de vanliga konventionerna definierar kantriktning i en konfliktgraf tidsordning mellan motstridiga operationer, vilket är motsatt den tidsordning som definieras av en kant i en väntan-på-graf .
3. Observera att en sådan global graf innehåller (har inbäddad) alla (omvänd kant) vanliga lokala väntan-på- grafer och även kan inkludera låsningsbaserade globala cykler (som inte kan existera i de lokala graferna). Till exempel, om alla databaser på en global cykel är SS2PL-baserade, så orsakas alla relaterade röstblockeringssituationer av låsningar (detta är den klassiska och förmodligen den enda globala dödläget som behandlas i databasforskningslitteraturen). Detta är ett globalt dödläge där varje relaterad databas skapar en del av cykeln, men hela cykeln finns inte i någon lokal väntan-på-graf.

I närvaro av CO är den förstärkta konfliktgrafen i själva verket en (omvänd kant) graf för lokalt åtagande och väntan på röstning : Det finns en fördel från en första transaktion, antingen lokal eller global, till en andra, om den andra väntar på att den första ska sluta för att antingen röstas fram (om global) eller lokalt engagerad (om lokal). Alla globala cykler (över två eller flera databaser) i denna graf genererar dödläge för röstning. Grafens globala cykler ger fullständig karaktärisering för dödlägen i röstningen och kan inkludera vilken kombination som helst av materialiserade och icke-materialiserade konflikter. Endast cykler av (endast) materialiserade konflikter är också cykler av den vanliga konfliktgrafen och påverkar serialiserbarheten. En eller flera (låsrelaterade) icke-materialiserade konflikter på en cykel hindrar den från att vara en cykel i den vanliga konfliktgrafen och gör den till ett låsningsrelaterat dödläge. Alla globala cykler (omröstningsdödlägen) måste brytas (lösas) för att både upprätthålla global serialiseringsbarhet och lösa globala dödlägen som involverar låsning av dataåtkomst. Faktum är att de alla bryts av protokollet om atomförpliktelse på grund av att röster saknas vid ett dödläge i omröstningen.

Kommentar: Denna observation förklarar också riktigheten av Extended CO (ECO) nedan: Globala transaktioners röstordning måste följa grafordningens konfliktordning med röstblockering när orderrelation (grafväg) finns mellan två globala transaktioner. Lokala transaktioner röstas inte om, och deras (lokala) åtaganden blockeras inte vid konflikter. Detta resulterar i samma omröstningsdödläge och resulterande globala process för eliminering av kretslopp för ECO.

Situationen med röstläge och dödläge kan sammanfattas på följande sätt:

• CO Voting-Deadlock Theorem

Låt en multidatabasmiljö omfatta CO-kompatibla (vilket eliminerar lokala cykler ) databassystem som upprätthåller varje Global CO (med villkoret i satsen ovan). Ett dödläge för röstning uppstår om och endast om en global cykel (spänner över två eller flera databaser) finns i grafen för globala förstärkta konflikter (även blockering av ett dataåtkomstlås representeras av en kant). Antag att cykeln inte bryts av någon abort. I så fall är alla globala transaktioner på den inblandade i respektive röstningsdödläge. Så småningom får var och en sin röst blockerad (antingen direkt eller indirekt av ett dataåtkomstlås); om en lokal transaktion finns i cykeln, har den så småningom sin (lokala) commit blockerad.

Kommentar: En sällsynt situation med ett dödläge för röstning (genom att blockerade röster saknas) kan inträffa, utan att rösta för någon transaktion på den relaterade cykeln av något av de databassystem som är involverade i dessa transaktioner. Detta kan inträffa när lokala deltransaktioner är flertrådade . Den högsta sannolikheten för en sådan sällsynt händelse involverar två transaktioner på två samtidiga motsatta cykler. Sådana globala cykler (deadlocks) överlappar med lokala cykler som löses lokalt och vanligtvis löses av lokala mekanismer utan att involvera atomärt engagemang. Formellt är det också en global cykel, men praktiskt taget är den lokal (delar av lokala cykler genererar en global; för att se detta, dela upp varje global transaktion (nod) till lokala deltransaktioner (dess delar är begränsade till en enda databas); en riktad kant finns mellan transaktioner om det finns en kant mellan respektive lokala deltransaktioner; en cykel är lokal om alla dess kanter härrör från en cykel mellan deltransaktioner i samma databas, och global om inte; global och lokal kan överlappa: samma cykel mellan transaktioner kan härröra från flera olika cykler mellan deltransaktioner och vara både lokal och global).

Dessutom avslutas följande låsbaserade specialfall:

• Den CO-låsningsbaserade Global-Deadlock Theorem

I ett CO-kompatibelt multidatabassystem är ett låsningsbaserat globalt dödlås, som involverar minst ett dataåtkomstlås (icke-materialiserad konflikt), och två eller flera databassystem, en återspegling av en global cykel i grafen för globala förstärkta konflikter , vilket resulterar i ett dödläge för röstning. En sådan cykel är inte en cykel i den (vanliga) Globala konfliktgrafen (som endast återspeglar materialiserade konflikter, så en sådan cykel påverkar inte serialiseringsbarheten ).

Kommentarer:

1. Varje blockering (kant) i cykeln som inte är av ett dataåtkomstlås blockerar direkt antingen röstning eller lokal commit. Alla dödlägen för röstning är lösta (nästan allt genom Atomic-åtagande ; se kommentaren ovan), inklusive denna låsningsbaserade typ.
2. Låsningsbaserade globala dödlägen kan också genereras i en helt SS2PL-baserad distribuerad miljö (speciellt fall av CO-baserad). All röstblockering (och dödläge för röstning) orsakas av dataåtkomstlås. Många forskningsartiklar har i åratal handlat om att lösa sådana globala dödlägen, men ingen (förutom CO-artiklarna) är känd (från och med 2009) för att lägga märke till att atomengagemang automatiskt löser dem. Sådana automatiska upplösningar förekommer regelbundet obemärkt i alla befintliga SS2PL-baserade multidatabassystem, ofta kringgå dedikerade upplösningsmekanismer.

Omröstningsstopp är nyckeln till driften av distribuerad CO.

Global cykeleliminering (här omröstning-dödlägesupplösning genom atomärt engagemang ) och resulterande avbrutna transaktioners återverkningar är tidskrävande, oavsett vilken samtidighetskontroll som används. Om databaser schemalägger transaktioner oberoende, är globala cykler oundvikliga (i en fullständig analogi med cykler/dödlägen som genereras i lokal SS2PL; med distribution resulterar alla transaktions- eller operationsschemaläggningskoordinationer i autonomiöverträdelser och är vanligtvis i betydande prestationsstraff). Däremot kan deras sannolikhet göras mycket låg i många fall genom att implementera riktlinjer för databas- och transaktionsdesign som minskar antalet konflikter som involverar en global transaktion. ackumuleringsräknare för flera transaktioner, som vanligtvis är hot spots ) .

Atomic commitment-protokoll är avsedda och designade för att uppnå atomicitet utan att ta hänsyn till databassamtidighetskontroll. De avbryter när de upptäcker eller heuristiskt hittar (t.ex. genom en timeout; ibland av misstag, i onödan) saknade röster och vanligtvis omedvetna om globala cykler. Dessa protokoll kan förbättras speciellt för CO (inklusive CO:s varianter nedan) för att förhindra onödiga avbrott och påskynda avbrott som används för att bryta globala cykler i den globala utökade konfliktgrafen (för bättre prestanda genom tidigare utgivning vid transaktionsslut av datorresurser och vanligtvis låsta data ). Till exempel kan befintliga låsningsbaserade globala dödlägesdetekteringsmetoder, andra än timeout, generaliseras även för att överväga lokal commit och röst direkt blockering, förutom blockering av dataåtkomst. En möjlig kompromiss i sådana mekanismer är att effektivt detektera och bryta de mest frekventa och relativt enkla att hantera längd-2 globala cyklerna, och använda timeout för oupptäckta, mycket mindre frekventa, längre cykler.

Upprätthålla CO lokalt

Beställning av åtaganden kan verkställas lokalt (i en enda databas) av en dedikerad CO-algoritm, eller av någon algoritm/protokoll som tillhandahåller något speciellt fall av CO. Ett viktigt sådant protokoll, som används flitigt i databassystem, vilket genererar ett CO-schema, är det starka strikta tvåfaslåsningsprotokollet (SS2PL: "släpp transaktionens lås först efter att transaktionen antingen har begåtts eller avbrutits"; se nedan). SS2PL är en riktig delmängd av skärningspunkten mellan 2PL och strikthet.

En generisk lokal CO-algoritm

En generisk lokal CO-algoritm ( Raz 1992 ; Algorithm 4.1) är en algoritm oberoende av implementeringsdetaljer som upprätthåller exakt CO-egenskapen. Det blockerar inte dataåtkomst (icke-blockerande) och består av att avbryta en viss uppsättning transaktioner (endast om det behövs) när en transaktion utförs. Den avbryter en (unikt bestämd vid varje given tidpunkt) minimal uppsättning andra obestämda (varken begångna eller avbrutna) transaktioner som körs lokalt och kan orsaka brott mot serialiseringsbarhet i framtiden (kan senare generera cykler av begångna transaktioner i konfliktdiagrammet; detta är ABORT-uppsättningen av en begången transaktion T; efter att T har begåtts kan ingen transaktion i ABORT vid beställningstidpunkten begås, och alla är dömda att avbrytas). Denna uppsättning består av alla obestämda transaktioner med riktade kanter i konfliktgrafen till den begångna transaktionen. Storleken på denna uppsättning kan inte öka när den transaktionen väntar på att begås (i redo-tillståndet: bearbetningen har avslutats) och minskar vanligtvis med tiden när dess transaktioner beslutas. Såvida det inte realtidsbegränsningar för att slutföra den transaktionen, är det att föredra att vänta med att utföra den transaktionen och låta denna uppsättning minska i storlek. Om en annan serialiseringsmekanism finns lokalt (som eliminerar cykler i den lokala konfliktgrafen), eller om det inte finns någon cykel som involverar den transaktionen, kommer uppsättningen att vara tom så småningom, och ingen avbrytning av en uppsättningsmedlem behövs. Annars kommer uppsättningen att stabiliseras med transaktioner på lokala cykler, och avbrytande av uppsättningsmedlemmar måste ske för att bryta cyklerna. Eftersom i fallet med CO-konflikter genererar blockering vid commit, indikerar lokala cykler i augments-konfliktgrafen (se ovan) lokala commit-deadlocks, och deadlock-lösningstekniker som i SS2PL kan användas (t.ex. timeout och wait-for-graf ) . En lokal cykel i den utökade konfliktgrafen med minst en icke-materialiserad konflikt återspeglar ett låsningsbaserat dödläge. Den lokala algoritmen ovan, applicerad på den lokala förstärkta konfliktgrafen snarare än den vanliga lokala konfliktgrafen, omfattar den generiska förbättrade lokala CO-algoritmen , en enda lokal cykelelimineringsmekanism, för att både garantera lokal serialisering och hantera låsbaserade lokala dödlägen. Praktiskt taget en ytterligare kontrollmekanism för samtidighet används alltid, även enbart för att upprätthålla återvinningsbarhet. Den generiska CO-algoritmen påverkar inte den lokala dataåtkomstschemaläggningsstrategin när den körs tillsammans med någon annan lokal samtidighetskontrollmekanism. Det påverkar endast commit-ordern, och av denna anledning behöver den inte avbryta fler transaktioner än de som måste avbrytas för att förhindra serialiseringsbrott av någon kombinerad lokal samtidighetskontrollmekanism. Som mest kan nettoeffekten av CO vara en försening av commit-händelser (eller röstning i en distribuerad miljö), för att följa den nödvändiga commit-ordern (men inte mer försening än dess specialfall, till exempel SS2PL, och i genomsnitt betydligt mindre).

Följande teorem avslutas:

• The Generic Local CO Algorithm Theorem

När man kör ensam eller tillsammans med någon samtidighetskontrollmekanism i ett databassystem, då

1. Den generiska lokala CO-algoritmen garanterar (lokal) CO (ett CO-kompatibelt schema).
2. Den generiska förbättrade lokala CO-algoritmen garanterar både (lokal) CO- och (lokal) låsningsbaserad dödlägesupplösning. Och (när en timeout inte används och inga begränsningar för slutförande av transaktioner i realtid tillämpas) avbryter ingen av algoritmerna fler transaktioner än vad som krävs (vilket bestäms av transaktionernas operationsschemaläggning, utanför algoritmernas omfattning).

Exempel: Samtidig programmering och transaktionsminne

Se även Samtidig programmering och Transaktionsminne.

Med spridningen av flerkärniga processorer har varianter av den generiska lokala CO-algoritmen också använts i ökande grad i samtidig programmering, transaktionsminne och speciellt i transaktionsminne för programvara för att uppnå serialiserbarhet optimistiskt genom "commit order" (t.ex. Ramadan et al. 2009, Zhang et al. 2006, von Parun et al. 2007). Många relaterade artiklar och patent som använder CO har redan publicerats.

Implementeringsöverväganden: Commitment Order Coordinator (COCO)

Ett databassystem i en multidatabasmiljö antas. Ur en mjukvaruarkitektursynpunkt kan en CO-komponent som implementerar den generiska CO-algoritmen lokalt, Commitment Order Coordinator (COCO), enkelt utformas som en förmedlare mellan ett (enkelt) databassystem och en atomic commitment-protokollkomponent ( Raz 1991b) ). COCO är dock vanligtvis en integrerad del av databassystemet. COCO:s funktioner är att rösta för att begå klara globala transaktioner (bearbetningen har avslutats) enligt den lokala åtagandeordern, att rösta för att avbryta transaktioner för vilka databassystemet har initierat en avbrytning (databassystemet kan initiera avbrytning för alla transaktioner , av många skäl), och för att skicka beslutet om atomär åtagande till databassystemet. För lokala transaktioner (när kan identifieras) behövs ingen röstning. För att fastställa åtagandeordningen upprätthåller COCO en uppdaterad representation av den lokala konfliktgrafen (eller den lokala förstärkta konfliktgrafen för att fånga även låsande dödlägen) för de obestämda (varken begångna eller avbrutna) transaktionerna som en datastruktur (t.ex. genom att använda mekanismer liknande låsning för att fånga konflikter, men utan blockering av dataåtkomst). COCO-komponenten har ett gränssnitt med sitt databassystem för att ta emot "konflikt", "klar" (bearbetningen har avslutats, beredskap att rösta om en global transaktion eller begå en lokal) och "avbryta" meddelanden från databassystemet. Det samverkar också med atomär åtagandeprotokollet för att rösta och ta emot atomåtagandeprotokollets beslut om varje global transaktion. Besluten levereras från COCO till databassystemet via deras gränssnitt, såväl som lokala transaktioners commit notifications, i en korrekt commit order. COCO, inklusive dess gränssnitt, kan förbättras om det implementerar en annan variant av CO (se nedan) eller spelar en roll i databasens samtidighetskontrollmekanism utöver röstning i atomärt engagemang.

COCO garanterar också CO lokalt i ett enda, isolerat databassystem utan gränssnitt med ett atomärt åtagandeprotokoll.

CO är ett nödvändigt villkor för global serialiserbarhet över autonoma databassystem.

Antag att databaser som deltar i distribuerade transaktioner (dvs. transaktioner som sträcker sig över mer än en enda databas) inte använder någon delad samtidighetskontrollinformation och använder omodifierade meddelanden i atomärt åtagandeprotokoll (för att nå atomicitet). I så fall är upprätthållande av (lokal) åtagandebeställning eller en av dess generaliserande varianter (se nedan) en nödvändig förutsättning för att garantera global serialiserbarhet (en bevisteknik finns i ( Raz 1992 ), och en annan bevismetod för detta i ( Raz 1993a )); det är också ett tillräckligt villkor . Detta är ett matematiskt faktum som härrör från definitionerna av serialiserbarhet och en transaktion . Det betyder att om man inte följer CO, kan global serialiseringsbarhet inte garanteras under detta villkor (villkoret att ingen lokal samtidighetskontrollinformation delas mellan databaser utöver meddelanden om atomic commit-protokoll). Atomiskt engagemang är ett minimalt krav för en distribuerad transaktion eftersom det alltid behövs, vilket antyds av transaktionsdefinitionen.

( Raz 1992 ) definierar databasens autonomi och oberoende som att uppfylla detta krav utan att använda någon ytterligare lokal kunskap:

• Definition: (baserat på samtidighetskontroll) autonomt databassystem

Ett databassystem är Autonomt , om det inte delar någon samtidighetskontrollinformation utöver omodifierade meddelanden i atomärt åtagandeprotokoll med någon annan enhet. Dessutom använder den inte för samtidighetskontroll någon ytterligare lokal information utöver konflikter (den sista meningen förekommer inte explicit utan snarare underförstått av ytterligare diskussion i Raz 1992 ).

Med hjälp av denna definition kommer följande slutsats:

• CO och global serialiseringssats

1. CO-kompatibilitet för varje autonomt databassystem (eller transaktionsobjekt) i en multidatabasmiljö är ett nödvändigt villkor för att garantera global serialiserbarhet (utan CO kan den globala serialiseringsbarheten kränkas).
2. CO-överensstämmelse med varje databassystem är ett tillräckligt villkor för att garantera global serialiserbarhet.

Definitionen av autonomi ovan innebär dock till exempel att transaktioner schemaläggs på ett sätt så att lokala transaktioner (begränsade till en enda databas) inte kan identifieras som sådana av ett autonomt databassystem. Detta är realistiskt för vissa transaktionsobjekt men alltför restriktivt och mindre realistiskt för allmänna databassystem. Om autonomin utökas med förmågan att identifiera lokala transaktioner, gör efterlevnaden av en mer allmän egenskap, Extended commitment ordering (ECO, se nedan), ECO till det nödvändiga villkoret.

Endast i ( Raz 2009 ) fångar begreppet generaliserad autonomi det avsedda begreppet autonomi:

• Definition: generaliserad autonomi

Ett databassystem har egenskapen Generalized autonomy om det inte delar något annat databassystem någon lokal samtidighetsinformation utöver (omodifierade) atomic commit protokollmeddelanden (dock kan all lokal information användas).

Denna definition är förmodligen den bredaste sådan definition som är möjlig i samband med databassamtidighetskontroll, och den gör CO tillsammans med någon av dess (användbara: Ingen samtidighetskontrollinformationsdistribution) generaliserande varianter (röstordning (VO); se CO-varianter nedan) till nödvändig förutsättning för global serialiserbarhet (dvs föreningen av CO och dess generaliserande varianter är den nödvändiga uppsättningen VO, som också kan inkludera nya okända användbara generaliserande varianter).

Sammanfattning

Commitment ordering (CO)-lösningen (tekniken) för global serialiserbarhet kan sammanfattas enligt följande:

Om varje databas (eller något annat transaktionsobjekt ) i en multidatabasmiljö överensstämmer med CO, dvs. ordnar sina lokala transaktioners åtaganden och sina röster på (globala, distribuerade) transaktioner till atomic commitment -protokollet enligt det lokala (till databasen) partiell ordning inducerad av den lokala konfliktgrafen (serialiserbarhetsgraf) för respektive transaktioner, då garanteras Global CO och Global serialiserbarhet . En databas CO-kompatibilitet kan uppnås effektivt med vilken lokal konfliktserialiserbarhet som helst baserad på samtidig kontrollmekanism, varken påverkar någon transaktions exekveringsprocess eller schemaläggning eller avbryter den. Databasens autonomi kränks inte heller. Den enda låga omkostnaden som uppstår är att upptäcka konflikter (t.ex. med låsning, men utan blockering av dataåtkomst, om det inte redan har upptäckts för andra ändamål) och beställning av röster och lokala transaktioners åtaganden enligt konflikterna.

Schemalagd klassinneslutning: En pil från klass A till klass B indikerar att klass A strikt innehåller B; bristen på en riktad väg mellan klasserna gör att klasserna är ojämförliga. En egenskap är i sig blockerande , om den endast kan upprätthållas genom att blockera transaktionens dataåtkomstoperationer tills vissa händelser inträffar i andra transaktioner. ( Raz 1992 )

Vid inkompatibla delordrar av två eller flera databaser (ingen global delordning kan bädda in respektive lokala delordningar tillsammans), genereras en global cykel (spänner över två databaser eller fler) i den globala konfliktgrafen. Detta, tillsammans med CO, resulterar i en cykel av blockerade röster. Ett dödläge för omröstning uppstår för databaserna under den cykeln (men tillåten samtidig röstning i varje databas, vanligtvis för nästan alla utestående röster, fortsätter att utföras). I det här fallet misslyckas det atomära åtagandeprotokollet att samla in alla röster som behövs för de blockerade transaktionerna på den globala cykeln. Följaktligen avbryter protokollet vissa transaktioner med en saknad röst. Detta bryter den globala cykeln, dödläget för röstning är löst och de relaterade blockerade rösterna är fria att verkställas. Att bryta den globala cykeln i den globala konfliktgrafen säkerställer att global CO och global serialiserbarhet bibehålls. Sålunda, i fallet med inkompatibla lokala (partiella) åtagandeorder, behövs ingen åtgärd eftersom det atomära åtagandeprotokollet löser det automatiskt genom att avbryta en transaktion som är en orsak till inkompatibiliteten. Dessutom resulterar globala dödlägen på grund av låsning (globala cykler i den utökade konfliktgrafen med minst en blockering av dataåtkomst) i dödläge för röstning och löses automatiskt av samma mekanism.

Lokal CO är ett nödvändigt villkor för att garantera global serialiserbarhet om de inblandade databaserna inte delar någon samtidighetskontrollinformation utöver (omodifierade) atomic commitment protocol-meddelanden, dvs om databaserna är autonoma i samband med samtidighetskontroll. Detta innebär att varje global serialiseringslösning för autonoma databaser måste överensstämma med CO. Annars kan den globala serialiseringsbarheten kränkas (och därmed sannolikt att kränkas mycket snabbt i en högpresterande miljö).

CO-lösningen skalas upp med nätverksstorlek och antalet databaser utan prestandastraff när den använder gemensam distribuerad atomär åtagandearkitektur .

Distribuerad serialiserbarhet och CO

Distribuerad CO

En utmärkande egenskap hos CO-lösningen för distribuerad serialiserbarhet från andra tekniker är det faktum att den inte kräver någon konfliktinformation som distribueras (t.ex. lokala prioritetsrelationer, lås, tidsstämplar , biljetter), vilket gör den unikt effektiv. Den använder (omodifierade) atomic commitment protocol meddelanden (som redan används) istället.

Ett vanligt sätt att uppnå distribuerad serialiserbarhet i ett (distribuerat) system är genom en distribuerad låshanterare (DLM). DLM, som kommunicerar låsinformation (icke-materialiserad konflikt) i en distribuerad miljö, lider vanligtvis av dator- och kommunikationslatens, vilket minskar systemets prestanda. CO gör det möjligt att uppnå distribuerad serialisering under mycket allmänna förhållanden, utan en distribuerad låshanterare, vilket uppvisar de fördelar som redan utforskats ovan för multidatabasmiljöer; i synnerhet: tillförlitlighet, hög prestanda, skalbarhet, möjligheten att använda optimistisk samtidighetskontroll när så önskas, ingen konfliktinformationsrelaterad kommunikation över nätverket (som har ådragit sig overhead och förseningar) och automatisk upplösning av deadlock.

Alla distribuerade transaktionssystem förlitar sig på något atomärt åtagandeprotokoll för att koordinera atomicitet (om det ska begås eller avbrytas) bland processer i en distribuerad transaktion . Vanligtvis är också återvinningsbara data (dvs. data under transaktionskontroll, t.ex. databasdata; inte att förväxla med återställningsegenskapen för ett schema) direkt åtkomst av en enda transaktionsdatahanterarekomponent (även kallad en resurshanterare ) som hanterar lokala deltransaktioner (den distribuerade transaktionens del på en enda plats, t.ex. nätverksnod), även om dessa data nås indirekt av andra enheter i det distribuerade systemet under en transaktion (dvs. indirekt åtkomst kräver en direkt åtkomst via en lokal deltransaktion). Återvinningsbara data i ett distribuerat transaktionssystem är sålunda typiskt uppdelade mellan transaktionsdatahanterare. I ett sådant system innefattar dessa transaktionsdatahanterare typiskt deltagarna i systemets atomära åtagandeprotokoll. Om varje deltagare följer CO (t.ex. genom att använda SS2PL, eller COCOs, eller en kombination; se ovan), så tillhandahåller hela det distribuerade systemet CO (genom satserna ovan; varje deltagare kan betraktas som ett separat transaktionsobjekt), och därmed (distribuerad) serialiserbarhet. Dessutom: När CO används tillsammans med ett atomärt åtagandeprotokoll löses även distribuerade dödlägen (dvs. dödlägen som spänner över två eller flera datahanterare) som orsakas av dataåtkomstlåsning automatiskt. Sålunda är följande slutsats:

• Den CO-baserade distribuerade serialiseringssatsen

Låt ett distribuerat transaktionssystem (t.ex. ett distribuerat databassystem ) omfatta transaktionsdatahanterare (även kallade resurshanterare ) som hanterar alla systemets återställningsbara data . Datahanterarna uppfyller tre villkor:

1. Datapartition: Återställningsbar data är uppdelad mellan datahanterarna, dvs varje återställningsbar datum (dataobjekt) styrs av en enda datahanterare (t.ex. som vanligt i en Shared nothing-arkitektur ; även kopior av samma datum under olika datahanterare är fysiskt distinkt, replikerad ).
2. Deltagare i atomär åtagandeprotokoll: Dessa datahanterare är deltagare i systemets atomära åtagandeprotokoll för koordinering av distribuerade transaktioners atomicitet.
3. CO-efterlevnad: Varje sådan datahanterare är CO-kompatibel (eller någon CO-variant kompatibel; se nedan).

Sedan

1. Hela det distribuerade systemet garanterar (distribuerad CO och) serialiserbarhet , och
2. Dataåtkomstbaserade distribuerade dödlägen (dödlägen som involverar två eller flera datahanterare med minst en icke-materialiserad konflikt) löses automatiskt.

Vidare: Att datahanterarna är CO-kompatibla är ett nödvändigt villkor för (distribuerad) serialiserbarhet i ett system som uppfyller villkoren 1, 2 ovan, när datahanterarna är autonoma , dvs inte delar samtidighetskontrollinformation utöver omodifierade meddelanden från atomic commitment protocol.

Detta teorem innebär också att när SS2PL (eller någon annan CO-variant) används lokalt i varje transaktionsdatahanterare, och varje datahanterare har exklusiv kontroll över sina data, behövs ingen distribuerad låshanterare (som ofta används för att upprätthålla distribuerad SS2PL) för distribuerad SS2PL och serialiserbarhet. Det är relevant för ett brett utbud av distribuerade transaktionsapplikationer, som enkelt kan utformas för att uppfylla satsens villkor.

Distribuerad optimistisk CO (DOCO)

För att implementera Distributed Optimistic CO (DOCO) används den generiska lokala CO-algoritmen i alla deltagare i atomic commitment-protokollet i systemet utan dataåtkomstblockering och därmed utan lokala dödlägen. Den föregående satsen har följande följd:

• The Distributed optimistic CO (DOCO)-satsen

Om DOCO används, då:

1. Inga lokala låsningar uppstår, och
2. Globala (röstnings-) dödlägen löses automatiskt (och alla är serialiseringsrelaterade (med icke-blockerande konflikter) snarare än låsningsrelaterade (med blockerande och möjligen även icke-blockerande konflikter)).

Därmed behövs ingen dödlägeshantering.

Exempel

Distribuerad SS2PL

Ett distribuerat databassystem som använder SS2PL finns på två fjärrnoder, A och B. Databassystemet har två transaktionsdatahanterare ( resurshanterare ), en på varje nod, och databasdata är uppdelade mellan de två datahanterarna på ett sätt som var och en har en exklusiv kontroll över sin egen (lokal till noden) del av data: Var och en hanterar sin egen data och låser utan någon kunskap om den andra chefens. För varje distribuerad transaktion måste sådana datahanterare utföra det tillgängliga atomära åtagandeprotokollet.

Två distribuerade transaktioner, $T_{1}$ och ${\displaystyle T_{2}},$ körs samtidigt, och båda får åtkomst till data x och y. x är under exklusiv kontroll av datahanteraren på A (B:s chef kan inte komma åt x), och y under den på B.

$T_{1}$ läser x på A och skriver y på B, dvs $T_{1}=R_{\text{1A}}(x)$$W_{\text{1B}}(y)$ när du använder notation som är vanlig för samtidighetskontroll.

$T_{2}$ läser y på B och skriver x på A, dvs $T_{2}=R_{\text{2B}}(y)$$W_{\text{2A}}(x)$

De respektive lokala deltransaktionerna på A och B (delarna av $T_{1}$ och $T_{2}$ på var och en av noderna) är följande:

Lokala deltransaktioner

Nod Transaktion	A	B
$T_{1}$	$T_{\text{1A}}=R_{\text{1A}}(x)$	$T_{\text{1B}}=W_{\text{1B}}(y)$
$T_{2}$	$T_{\text{2A}}=W_{\text{2A}}(x)$	$T_{\text{2B}}=R_{\text{2B}}(y)$

Databassystemets schema vid en viss tidpunkt är följande:

$R_{\text{1A}}(x)$$R_{\text{2B}}(y)$

(även $R_{\text{2B}}(y)$$R_{\text{1A}}(x)$ är möjligt)

$T_{1}$ håller ett läslås på x och $T_{2}$ håller läslås på y. Således blockeras $W_{\text{1B}}(y)$ och ${\displaystyle W_{\text{2A}}(x)} av$ låskompatibilitetsreglerna för SS2PL och kan inte köras. Detta är en distribuerad dödlägessituation, som också är ett dödläge för röstning (se nedan) med en distribuerad (global) cykel av längd 2 (antal kanter, konflikter; 2 är den vanligaste längden). De lokala deltransaktionerna är i följande tillstånd:

$T_{\text{1A}}$ är klar (exekveringen har avslutats) och röstad (i atomärt engagemang)

$text{1B}}}$ \ körs och blockeras (en icke- materialiserad konfliktsituation; ingen omröstning om den kan inträffa)

T $T_{\text{2A}}$ körs och blockeras (en icke -materialiserad konflikt; ingen röst).

$\displaystyle T_{\text{2B}}}$ är klar och röstad

Eftersom det atomära åtagandeprotokollet inte kan ta emot röster för blockerade deltransaktioner (ett dödläge för röstning), kommer det så småningom att avbryta en transaktion med en eller flera röster som saknas genom timeout , antingen T 1 {\ displaystyle T_ $,$ eller $T_{2}$ , (eller båda, om tidsgränserna faller mycket nära). Detta kommer att lösa det globala dödläget. Den återstående transaktionen kommer att slutföras, röstas om och begås. En avbruten transaktion startas om och genomförs omedelbart.

Kommentarer

1. Datapartitionen (x på A; y på B) är viktig eftersom utan den kan till exempel x nås direkt från B. Om en transaktion $T_{3}$ körs på B samtidigt med $T_{1}$ och $T_{2}$ och direkt skriver x, utan en distribuerad låshanterare läslåset för x som hålls av $T_{1}$ på A är inte synlig på B och kan inte blockera skrivningen av $T_{3}$ (eller signalera en materialiserad konflikt för en icke-blockerande CO-variant; se nedan). Serialiseringsbarheten kan alltså kränkas.
2. På grund av datapartition kan x inte nås direkt från B. Funktionaliteten är dock inte begränsad, och en transaktion som körs på B kan fortfarande utfärda en skriv- eller läsbegäran av x (inte vanligt). Denna begäran kommuniceras till transaktionens lokala deltransaktion på A (som genereras, om den inte redan finns) som skickar denna begäran till den lokala datahanteraren på A.

Variationer

I scenariot ovan är båda konflikterna icke-materialiserade , och det globala dödläget för röstning återspeglas som en cykel i den globala väntan-på-grafen ( men inte i den globala konfliktgrafen ; se Exakt karakterisering av dödlägen för röstning efter globala cykler ovan) . Databassystemet kan dock använda vilken CO-variant som helst med exakt samma konflikter och omröstningsdödläge och samma lösning. Konflikter kan vara antingen materialiserade eller icke-materialiserade , beroende på vilken CO-variant som används. Till exempel, om SCO (nedan) används av det distribuerade databassystemet istället för SS2PL, så förverkligas de två konflikterna i exemplet , alla lokala deltransaktioner är i redo -läge och röstblockering sker i de två transaktionerna, en på varje nod, på grund av CO-röstningsregeln som tillämpas oberoende på både A och B: på grund av konflikter $T_{\text{2A}}=W_{\text{2A}}(x )$ röstas inte om innan $T_{\text{1A}}=R_{\text{1A}}(x)$ slutar, och ${\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)} röstas inte$ om innan $T_{\text{2B}}=R_ {\text{2B}}(y)$ slutar, vilket är ett dödläge för röstning. Nu konfliktgrafen den globala cykeln (alla konflikter materialiseras), och återigen löses den av atomär åtagandeprotokollet, och distribuerad serialiserbarhet bibehålls. Osannolikt för ett distribuerat databassystem, men möjligt i princip (och förekommer i en multidatabas), A kan använda SS2PL medan B använder SCO. I det här fallet är den globala cykeln varken i väntan-på-grafen eller i serialiserbarhetsgrafen, utan fortfarande i den utökade konfliktgrafen (sammanslutningen av de två). De olika kombinationerna sammanfattas i följande tabell:

Situationer med dödläge för röstning

Fall	Nod A	Nod B	Eventuellt schema	Materialiserade konflikter på cykel	Icke- materialiserade konflikter	$T_{\text{1A}}=R_{\text{1A}}(x)$	$T_{\text{1B}}=W_{\text{1B}}(y)$	$T_{\text{2A}}=W_{\text{2A}}(x)$	$T_{\text{2B}}=R_{\text{2B}}(y)$
1	SS2PL	SS2PL	$R_{\text{1A}}(x)R_{\text{2B}}(y)$	0	2	Klar röstade	Kör (blockerad)	Kör (blockerad)	Klar röstade
2	SS2PL	SCO	$R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y )$	1	1	Klar röstade	Klar omröstning blockerad	Kör (blockerad)	Klar röstade
3	SCO	SS2PL	$R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{2A}}(x )$	1	1	Klar röstade	Kör (blockerad)	Klar omröstning blockerad	Klar röstade
4	SCO	SCO	$R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{ 1B}}(y)W_{\text{2A}}(x)$	2	0	Klar röstade	Klar omröstning blockerad	Klar omröstning blockerad	Klar röstade

Kommentarer:

1. Konflikter och därmed cykler i den utökade konfliktgrafen bestäms endast av transaktionerna och deras initiala schemaläggning, oberoende av den använda samtidighetskontrollen. Med vilken variant av CO som helst, orsakar vilken global cykel som helst (dvs. som sträcker sig över två databaser eller fler) ett dödläge i röstningen . Olika CO-varianter kan skilja sig åt om en viss konflikt är materialiserad eller icke-materialiserad .
2. Vissa begränsade operationsorderändringar i scheman ovan är möjliga, begränsade av orderna inuti transaktionerna, men sådana ändringar ändrar inte resten av tabellen.
3. Som nämnts ovan beskriver endast fall 4 en cykel i den (vanliga) konfliktgrafen som påverkar serialiserbarheten. Fall 1-3 beskriver cykler av låsningsbaserade globala låsningar (minst en låsblockering finns). Alla cykeltyper löses lika av det atomära åtagandeprotokollet. Fall 1 är den vanliga distribuerade SS2PL som använts sedan 1980-talet. Men ingen forskningsartikel, förutom CO-artiklarna, är känd för att lägga märke till denna automatiska låsande globala dödlägesupplösning från och med 2009. Sådana globala låsningar har vanligtvis hanterats av dedikerade mekanismer.
4. Fall 4 ovan är också ett exempel på ett typiskt dödläge för röstning när distribuerad optimistisk CO (DOCO) används (dvs fall 4 är oförändrad när Optimistisk CO (OCO; se nedan) ersätter SCO på både A och B): Inga data- åtkomstblockering förekommer och endast materialiserade konflikter existerar.

Hypotetisk Multi Single-Threaded Core (MuSiC) miljö

Kommentar: Även om exemplen ovan beskriver verklig, rekommenderad användning av CO, är detta exempel hypotetiskt, endast för demonstration.

Vissa experimentella distribuerade minnesresidenta databaser förespråkar transaktionsmiljöer med flera entrådiga kärnor (MuSiC). "Entrådad" hänvisar endast till transaktionstrådar och till seriell exekvering av transaktioner. Syftet är möjliga storleksordningsvinster i prestanda (t.ex. H-Store och VoltDB ) jämfört med konventionell transaktionsexekvering i flera trådar på samma kärna. I det som beskrivs nedan är MuSiC oberoende av hur kärnorna är fördelade. De kan finnas i en integrerad krets (chip), eller i många chips, eventuellt fördelade geografiskt i många datorer. I en sådan miljö, om återvinningsbara (transaktionella) data är uppdelade mellan trådar (kärnor), och det implementeras på konventionellt sätt för distribuerad CO, som beskrivits i tidigare avsnitt, existerar DOCO och Strictness automatiskt. Men det finns nackdelar med denna enkla implementering av en sådan miljö, och dess praktiska funktion som en allmän lösning är tveksam. Å andra sidan kan enorma prestandavinster uppnås i applikationer som kan kringgå dessa nackdelar i de flesta situationer.

Kommentar: MuSiC enkla implementeringen som beskrivs här (som använder till exempel, som vanligt i distribuerad CO, omröstnings- (och transaktionstråd) blockering i atomärt åtagandeprotokoll när det behövs) är endast för demonstration och har ingen koppling till implementeringen i H- Butik eller något annat projekt.

I en MuSiC-miljö är lokala scheman seriella . Sålunda uppfylls automatiskt både lokal optimistisk CO (OCO; se nedan) och Global CO-upprätthållande av röstbeställningsstrategi för protokollet om atomförpliktelse. Detta resulterar i både distribuerad CO-kompatibilitet (och därmed distribuerad serialisering) och automatisk global (omröstnings) dödlägeslösning.

Dessutom följer även lokal Strictness automatiskt i ett seriellt schema. Genom sats 5.2 i ( Raz 1992 ; sid 307), när CO-röstordningsstrategin tillämpas, garanteras även Global Strictness. Observera att seriell lokalt är det enda läget som tillåter strikthet och "optimism" (ingen blockering av dataåtkomst) tillsammans.

Följande slutsats:

• MusiC Theorem

I MuSiC-miljöer, om återställningsbar (transaktions)data är uppdelad mellan kärnor (trådar), då

1. OCO (och underförstådd serialiseringsbarhet ; dvs. DOCO och distribuerad serialiseringsbarhet)
2. Strikthet (som tillåter effektiv återhämtning; 1 och 2 innebär strikt CO—se SCO nedan) och
3. (omröstning) lösning på dödläge

existerar automatiskt globalt med obegränsad skalbarhet i antal använda kärnor.

Kommentar: Det kan dock finnas två stora nackdelar, som kräver speciell hantering:

1. Lokala deltransaktioner av en global transaktion blockeras tills commit, vilket gör respektive kärnor inaktiva. Detta minskar kärnanvändningen avsevärt, även om schemaläggning av de lokala deltransaktionerna försöker utföra dem alla i tid, nästan tillsammans. Det kan övervinnas genom att ta bort exekvering från commit (med något atomärt åtagandeprotokoll) för globala transaktioner, till priset av eventuella kaskadavbrott.
2. öka antalet kärnor för en given mängd återvinningsbar data (databasstorlek) minskar den genomsnittliga mängden (partitionerad) data per kärna. Detta kan göra vissa kärnor inaktiva, medan andra är mycket upptagna, beroende på distributionen av dataanvändning. Också en lokal (till en kärna) transaktion kan bli global (multi-core) för att nå sina nödvändiga data, med ytterligare kostnader. Allteftersom antalet kärnor ökar, bör mängden och typen av data som tilldelas varje kärna balanseras efter dataanvändning, så en kärna är varken överväldigad för att bli en flaskhals, eller blir inaktiv för ofta och underutnyttjad i ett upptaget system. Ett annat övervägande är att lägga i en och samma kärnpartition all data som vanligtvis nås av samma transaktion (om möjligt), för att maximera antalet lokala transaktioner (och minimera antalet globala, distribuerade transaktioner). Detta kan uppnås genom tillfällig dataanvändning mellan kärnor baserat på lastbalansering (dataåtkomstbalansering) och mönster för dataanvändning vid transaktioner. Ett annat sätt att avsevärt mildra denna nackdel är genom korrekt fysisk datareplikering mellan vissa kärnpartitioner på ett sätt så att skrivskyddade globala transaktioner möjligen helt undviks (beroende på användningsmönster) och replikeringsändringar synkroniseras med en dedikerad commit-mekanism.

CO-varianter: specialfall och generaliseringar

Egenskapsklasser för specialfallsschema (t.ex. SS2PL och SCO nedan) ingår strikt i CO-klassen. De generaliserande klasserna (ECO och MVCO) innehåller strikt CO-klassen (dvs. inkluderar även scheman som inte är CO-kompatibla). De generaliserande varianterna garanterar också global serialiserbarhet utan att distribuera lokal samtidighetskontrollinformation (varje databas har den generaliserade autonomi- egenskapen: den använder endast lokal information), samtidigt som CO-begränsningar slappnar av och extra (lokal) information används för bättre samtidighet och prestanda: ECO använder kunskap om transaktioner är lokala (dvs. begränsade till en enda databas), och MVCO använder tillgången på dataversionsvärden. Liksom CO är båda generaliserande varianter icke-blockerande , stör inte någon transaktions schemaläggning och kan sömlöst kombineras med alla relevanta mekanismer för samtidighetskontroll.

Termen CO-variant hänvisar i allmänhet till CO, ECO, MVCO, eller en kombination av var och en av dem med någon relevant samtidighetskontrollmekanism eller -egenskap (inklusive multiversionsbaserad ECO, MVECO). Inga andra generaliserande varianter (som garanterar global serialiserbarhet utan lokal distribution av samtidighetskontrollinformation) är kända, men kan komma att upptäckas.

Stark strikt tvåfaslåsning (SS2PL)

Huvudartikel: Tvåfaslåsning

Stark strikt tvåfaslåsning (SS2PL; även kallad Rigorousness eller Rigorous scheduling ) innebär att både läs- och skrivlås för en transaktion släpps först efter att transaktionen har avslutats (antingen genomförd eller avbruten). Uppsättningen av SS2PL-scheman är en riktig delmängd av uppsättningen CO-scheman. Den här egenskapen används i stor utsträckning i databassystem, och eftersom den innebär CO, genererar databaser som använder den och deltar i globala transaktioner ett serialiserbart globalt schema (när man använder ett atomärt åtagandeprotokoll, vilket behövs för atomicitet i en multi-databasmiljö) . Ingen databasändring eller tillägg behövs i det här fallet för att delta i en CO-distribuerad lösning: Uppsättningen av obestämda transaktioner som ska avbrytas innan de utförs i den lokala generiska CO-algoritmen ovan är tom på grund av låsningarna, och därför är en sådan algoritm onödig i det här fallet. En transaktion kan röstas på av ett databassystem omedelbart efter att ha gått in i ett "färdigt" tillstånd, dvs. slutfört att köra sin uppgift lokalt. Dess lås släpps av databassystemet först efter att det har bestämts av atomic commitment-protokollet, och sålunda bibehålls villkoret i Global CO-upprätthållande teoremet ovan automatiskt. Om en lokal timeoutmekanism används av ett databassystem för att lösa (lokala) SS2PL dödlägen, bryter avbrytande av blockerade transaktioner inte bara potentiella lokala cykler i den globala konfliktgrafen (verkliga cykler i den utökade konfliktgrafen), utan också databassystemets potentiella globala cykler som en bieffekt, om protokollets avbrottsmekanism är relativt långsam. Sådana oberoende avbrott av flera enheter kan vanligtvis resultera i onödiga avbrott för mer än en transaktion per global cykel. Situationen är annorlunda för lokala väntan-på-grafbaserade mekanismer: Sådana kan inte identifiera globala cykler, och det atomära åtagandeprotokollet kommer att bryta den globala cykeln, om det resulterande dödläget i röstningen inte löses tidigare i en annan databas.

Lokal SS2PL tillsammans med atomärt engagemang som innebär global serialiserbarhet kan också härledas direkt: Alla transaktioner, inklusive distribuerade, följer 2PL (SS2PL) reglerna. Mekanismen för det atomära åtagandeprotokollet behövs inte här för konsensus om åtagande, utan snarare för slutet av fas två-synkroniseringspunkten. Förmodligen av denna anledning, utan att ta hänsyn till röstmekanismen för atomengagemang, har automatisk global dödlägeslösning inte märkts innan CO.

Strikt CO (SCO)

Läs-skrivkonflikt: SCO vs. SS2PL . Varaktigheten för transaktion T2 är längre med SS2PL än med SCO. SS2PL fördröjer skrivoperationen w2[x] för T2 tills T1 commits, på grund av en låsning på x med T1 efter läsoperationen r1[x]. Om t tidsenheter behövs för transaktion T2 efter att ha startat skrivoperation w2[x] för att nå klart tillstånd, så begår T2 t tidsenheter efter att T1 commits. SCO blockerar dock inte w2[x], och T2 kan commit direkt efter T1 commit. ( Raz 1991c )

Strict Commitment Ordering (SCO; ( Raz 1991c )) är skärningspunkten mellan strikthet (ett specialfall av återvinningsbarhet) och CO, och ger en övre gräns för ett schemas samtidighet när båda egenskaperna finns. Det kan implementeras med hjälp av blockeringsmekanismer (låsning) liknande de som används för den populära SS2PL med liknande omkostnader.

Till skillnad från SS2PL blockerar inte SCO vid en läs-skrivkonflikt utan blockerar eventuellt vid commit istället. SCO och SS2PL har identiskt blockeringsbeteende för de andra två konflikttyperna: skriv-läs och skriv-skriv. Som ett resultat har SCO kortare genomsnittliga blockeringsperioder och mer samtidighet (t.ex. prestandasimuleringar av en enda databas för den mest betydande varianten av lås med ordnad delning , som är identisk med SCO, visar tydligt detta, med ungefär 100 % vinst för vissa transaktionsbelastningar; även för identiska transaktionsbelastningar kan SCO nå högre transaktionshastigheter än SS2PL innan låsning . inträffar) Mer samtidighet innebär att med givna beräkningsresurser genomförs fler transaktioner i tidsenhet (högre transaktionshastighet, genomströmning ), och den genomsnittliga varaktigheten för en transaktion är kortare (snabbare slutförande; se diagram). Fördelen med SCO är särskilt betydande under låsstrid.

• SCO vs. SS2PL Performance Theorem

SCO ger kortare genomsnittlig transaktionssluttid än SS2PL, om läs-skrivkonflikter finns. SCO och SS2PL är identiska i övrigt (har identiskt blockeringsbeteende med skriv-läs- och skriv-skriv-konflikter).

SCO är lika praktiskt som SS2PL eftersom det som SS2PL ger förutom serialiserbarhet även strikthet, som används allmänt som en grund för effektiv återställning av databaser från fel. En SS2PL-mekanism kan konverteras till en SCO-mekanism för bättre prestanda på ett enkelt sätt utan att ändra återställningsmetoder. En beskrivning av en SCO-implementering finns i (Perrizo och Tatarinov 1998). Se även Semi-optimistisk databasschemaläggare .

SS2PL är en riktig delmängd av SCO (vilket är en annan förklaring till varför SCO är mindre begränsande och ger mer samtidighet än SS2PL).

Optimistisk CO (OCO)

För att implementera Optimistic commitment ordering (OCO) används den generiska lokala CO-algoritmen utan blockering av dataåtkomst och därmed utan lokala dödlägen. OCO utan transaktions- eller operationsschemaläggningsbegränsningar täcker hela CO-klassen och är inte ett specialfall av CO-klassen, utan snarare en användbar CO-variant och mekanismkarakterisering.

Extended CO (ECO)

Allmän karaktärisering av ECO

Extended Commitment Ordering (ECO; ( Raz 1993a )) generaliserar CO. När lokala transaktioner (transaktioner begränsade till en enda databas) kan särskiljas från globala (distribuerade) transaktioner (transaktioner som spänner över två databaser eller fler), tillämpas åtagandeorder på globala endast transaktioner. För att ett lokalt (till en databas) schema ska ha ECO-egenskapen, överensstämmer den kronologiska (delvisa) ordningen för commit-händelser för enbart globala transaktioner (oviktigt för lokala transaktioner) med deras ordning på respektive lokala konfliktgraf.

• Definition: utökad åtagandebeställning

Låt $T_{1},T_{2}$ vara två begångna globala transaktioner i ett schema, så att en riktad väg för ej avbrutna transaktioner finns i konfliktdiagrammet ( precedensdiagram ) från $T_{1}$ till $T_{2}$ ( $T_{1}$ föregår $T_{2}$ , möjligen transitivt , indirekt) . Schemat har Extended commitment ordering (ECO), om för varannan sådana transaktioner $T_{1}$ commits innan $T_{2}$ commits.

En distribuerad algoritm för att garantera global ECO existerar. När det gäller CO behöver algoritmen endast (omodifierade) atomic commitment protocol meddelanden. För att garantera global serialiserbarhet måste varje databas även garantera konfliktserialisering av sina egna transaktioner genom vilken som helst (lokal) samtidighetskontrollmekanism.

• ECO och Global Serializability Theorem

1. (Lokal, vilket innebär global) ECO tillsammans med lokal konflikt serialiserbarhet, är ett tillräckligt villkor för att garantera global konflikt serialiserbarhet.
2. När ingen samtidighetskontrollinformation utöver meddelanden om atomär åtagande delas utanför en databas (autonomi), och lokala transaktioner kan identifieras, är det också ett nödvändigt villkor.

Se ett nödvändighetsbevis i ( Raz 1993a ).

Detta tillstånd (ECO med lokal serialiserbarhet) är svagare än CO och tillåter mer samtidighet till priset av en lite mer komplicerad lokal algoritm (dock finns det ingen praktisk overheadskillnad med CO).

När alla transaktioner antas vara globala (t.ex. om ingen information finns tillgänglig om att transaktioner är lokala), minskar ECO till CO.

ECO-algoritmen

Innan en global transaktion genomförs, avbryter en generisk lokal (till en databas) ECO-algoritm en minimal uppsättning oavgjorda transaktioner (varken genomförda eller avbrutna; varken lokala transaktioner eller globala som körs lokalt), som senare kan orsaka en cykel i konfliktgraf. Denna uppsättning avbrutna transaktioner (inte unika, i motsats till CO) kan optimeras om varje transaktion tilldelas en vikt (som kan bestämmas av transaktionens betydelse och av de datorresurser som redan investerats i den löpande transaktionen; optimering kan utföras t.ex. genom en minskning från problemet med Maxflöde i nätverk ( Raz 1993a) ). Liksom för CO är en sådan uppsättning tidsberoende och blir tom så småningom. Praktiskt taget i nästan alla nödvändiga implementeringar bör en transaktion endast utföras när setet är tomt (och ingen setoptimering är tillämplig). Den lokala (till databasen) samtidighetskontrollmekanismen (separat från ECO-algoritmen) säkerställer att lokala cykler elimineras (till skillnad från med CO, vilket innebär serialiserbarhet av sig självt; men praktiskt taget även för CO används en lokal samtidighetsmekanism, åtminstone för att säkerställa återvinningsbarhet). Lokala transaktioner kan alltid utföras samtidigt (även om en prioritetsrelation existerar, till skillnad från CO). När de övergripande transaktionernas lokala partiella ordning (som bestäms av den lokala konfliktgrafen, nu endast med möjliga temporära lokala cykler, eftersom cykler elimineras av en lokal serialiseringsmekanism) tillåter, kan även globala transaktioner röstas fram för att begås samtidigt ( när alla deras transitivt (indirekta) föregående (via konflikt) globala transaktioner begås, medan transitivt föregående lokala transaktioner kan vara i vilken stat som helst. Detta i analogi med den distribuerade CO-algoritmens starkare samtidiga röstningsvillkor, där alla transitivt föregående transaktioner måste vara engagerad).

Villkoret för att garantera Global ECO kan sammanfattas på samma sätt som CO:

• The Global ECO Enforcing Vote ordering strategy Theorem

Låt $T_{1},T_{2}$ vara obestämda (varken begångna eller avbrutna) globala transaktioner i ett databassystem som säkerställer serialiserbarhet lokalt, så att en riktad sökvägen för ej avbrutna transaktioner finns i den lokala konfliktgrafen (den för själva databasen) från $T_{1}$ till $T_{2}$ . Att sedan ha $T_{1}$ avslutat (antingen committed eller aborterad) innan $T_{2}$ röstas fram för att begås, i varje sådant databassystem i en multidatabasmiljö, är en nödvändigt och tillräckligt villkor för att garantera Global ECO (villkoret garanterar Global ECO, som kan kränkas utan det).

Global ECO (alla globala cykler i den globala konfliktgrafen elimineras av atomärt engagemang) tillsammans med Lokal serialiserbarhet (dvs varje databassystem upprätthåller serialiserbarhet lokalt; alla lokala cykler elimineras) innebär Global serialiserbarhet (alla cykler är eliminerade). Detta innebär att om varje databassystem i en multidatabasmiljö tillhandahåller lokal serialiserbarhet (genom vilken mekanism som helst) och upprätthåller röstordningsstrategin i satsen ovan (en generalisering av CO:s röstordningsstrategi), så garanteras Global serialiserbarhet (ingen lokal CO behövs längre).

På samma sätt som CO kan situationen för ECO -omröstning-dödläge sammanfattas enligt följande:

• ECO Voting-Deadlock Theorem

Låt en multidatabasmiljö bestå av databassystem som var och en upprätthåller både Global ECO (med villkoret i satsen ovan) och lokal konflikt serialiserbarhet (vilket eliminerar lokala cykler i den globala konfliktgrafen). Sedan uppstår ett dödläge för röstning om och endast om en global cykel (spänner över två eller flera databaser) finns i grafen för globala förstärkta konflikter (även blockering av ett dataåtkomstlås representeras av en kant). Om cykeln inte bryter av någon avbrytning, är alla globala transaktioner på den inblandade i respektive omröstningsdödläge, och så småningom får var och en sin röst blockerad (antingen direkt eller indirekt av ett dataåtkomstlås). Om en lokal transaktion finns i cykeln, kan den vara i vilket icke-avbrutet tillstånd som helst (kör, klar eller genomförd; till skillnad från CO behövs ingen lokal commit-blockering).

Precis som med CO betyder detta att även globala dödlägen på grund av dataåtkomstlåsning (med minst en låsning) är röstlås och automatiskt löses av atomärt engagemang.

Multiversion CO (MVCO)

Multi-version Commitment Ordering (MVCO; ( Raz 1993b )) är en generalisering av CO för databaser med flerversionsresurser . Med sådana resurser skrivskyddade transaktioner eller blockeras för bättre prestanda. Att använda sådana resurser är ett vanligt sätt numera att öka samtidighet och prestanda genom att generera en ny version av ett databasobjekt varje gång objektet skrivs, och tillåta transaktioners läsoperationer av flera senaste relevanta versioner (av varje objekt). MVCO innebär One-copy-serializability (1SER eller 1SR) som är generaliseringen av serialiserbarhet för flerversionsresurser. Liksom CO är MVCO icke-blockerande och kan kombineras med vilken som helst relevant multi-version samtidighetskontrollmekanism utan att störa den. I den introducerade underliggande teorin för MVCO är konflikter generaliserade för olika versioner av samma resurs (till skillnad från tidigare multiversionsteorier). För olika versioner ersätts konflikt kronologisk ordning med versionsordning, och eventuellt omvänd, samtidigt som de vanliga definitionerna för motstridiga operationer behålls. Resultaten för de vanliga och utökade konfliktgraferna förblir oförändrade, och på samma sätt som CO finns det en distribuerad MVCO-upprätthållande algoritm, nu för en blandad miljö med både enversions- och multiversionsresurser (nu är enkelversion ett specialfall av multiversion ). När det gäller CO behöver MVCO-algoritmen endast (omodifierade) meddelanden om atomärt åtagandeprotokoll utan ytterligare kommunikationskostnader. Låsningsbaserade globala dödlägen översätts till dödlägen för röstning och löses automatiskt. I analogi med CO gäller följande:

• MVCO och Global one-copy-serializability theorem

1. MVCO-kompatibilitet för varje autonomt databassystem (eller transaktionsobjekt) i en blandad multidatabasmiljö av enversions- och multiversionsdatabaser är ett nödvändigt villkor för att garantera Global en-kopia-serialiserbarhet (1SER).
2. MVCO-överensstämmelse för varje databassystem är ett tillräckligt villkor för att garantera Global 1SER.
3. Låsningsbaserade globala låsningar löses automatiskt.

Kommentar : Nu är ett CO-kompatibelt databassystem i en version automatiskt också MVCO-kompatibelt.

MVCO kan generaliseras ytterligare för att använda generaliseringen av ECO (MVECO).

Exempel: COSI-baserad ögonblicksbildsisolering

CO-baserad ögonblicksbildsisolering (COSI) är skärningspunkten mellan Snapshot-isolering (SI) och MVCO. SI är en för multiversion samtidighetskontroll som används allmänt på grund av god prestanda och likhet med serialiserbarhet (1SER) i flera aspekter. Teorin i (Raz 1993b) för MVCO som beskrivs ovan används senare i (Fekete et al. 2005) och andra artiklar om SI, t.ex. (Cahill et al. 2008); se även Göra snapshot isolation serialiserbar och referenserna där), för att analysera konflikter i SI för att göra det serialiserbart. Metoden som presenteras i (Cahill et al. 2008), Serializable snapshot isolation (SerializableSI), en modifiering av SI med låg overhead, ger goda prestandaresultat jämfört med SI, med endast små straff för att serialiserbarhet ska upprätthållas. En annan metod, genom att kombinera SI med MVCO (COSI), gör att SI också kan serialiseras, med en relativt låg overhead, på samma sätt som att kombinera den generiska CO-algoritmen med enversionsmekanismer. Dessutom, den resulterande kombinationen, COSI, som är MVCO-kompatibel, tillåter COSI-kompatibla databassystem att samverka och transparent delta i en CO-lösning för distribuerad/global serialiserbarhet (se nedan). Förutom omkostnader måste även protokolls beteenden jämföras kvantitativt. Å ena sidan kan alla serialiserbara SI-scheman göras MVCO av COSI (genom möjliga commit-fördröjningar vid behov) utan att avbryta transaktioner. Å andra sidan är SerializableSI känt för att i onödan avbryta och starta om vissa procentandelar av transaktioner även i serialiserbara SI-scheman.

CO och dess varianter är transparenta interoperabla för global serialisering

Med CO och dess varianter (t.ex. SS2PL, SCO, OCO, ECO och MVCO ovan) uppnås global serialisering via distribuerade algoritmer baserade på atomic commitment protocol. För CO och alla dess varianter är atomic commitment protocol instrumentet för att eliminera globala cykler (cykler som spänner över två eller flera databaser) i den globala utökade (och därmed också vanliga) konfliktgrafen (implicit; ingen global datastrukturimplementering behövs). I fall av antingen inkompatibla lokala åtagandeorder i två eller flera databaser (när ingen global delorder kan bädda in respektive lokala delorder tillsammans), eller en dataåtkomstlåsningsrelaterat omröstningsdödläge, vilket båda innebär en global cykel i den globala utökade konfliktgrafen och om röster saknas bryter protokollet för atomförpliktelse en sådan cykel genom att avbryta en obestämd transaktion på den (se Den distribuerade CO-algoritmen ovan). Skillnader mellan de olika varianterna finns endast på lokal nivå (inom de deltagande databassystemen). Varje lokal CO-instans av valfri variant har samma roll, att bestämma positionen för varje global transaktion (en transaktion som sträcker sig över två eller flera databaser) inom den lokala åtagandeordern, dvs att bestämma när det är transaktionens tur att röstas på lokalt i atomåtagandeprotokollet. Således uppvisar alla CO-varianter samma beteende när det gäller atomärt engagemang. Detta innebär att de alla är interoperabla via atomärt engagemang (med samma mjukvarugränssnitt, vanligtvis tillhandahållna som tjänster , vissa redan standardiserade för atomärt engagemang, främst för tvåfasprotokollet , t.ex. X/Open XA ) och transparent kan användas tillsammans i vilken distribuerad miljö som helst (medan varje CO-variantinstans möjligen är associerad med någon relevant lokal typ av samtidighetskontrollmekanism).

Sammanfattningsvis kan vilken enskild global transaktion som helst delta samtidigt i databaser som kan använda var och en av vilken som helst, möjligen olika, CO-variant (samtidigt som processer körs i varje sådan databas och körs samtidigt med lokala och andra globala transaktioner i varje sådan databas). Atomåtagandeprotokollet är likgiltigt för CO och skiljer inte mellan de olika CO-varianterna. Varje global cykel som genereras i den utökade globala konfliktgrafen kan sträcka sig över databaser med olika CO-varianter och generera (om den inte bryts av någon lokal avbrytning) ett dödläge för röstning som löses genom atomärt engagemang på exakt samma sätt som i en miljö med en enda CO-variant. lokala cykler (nu möjligen med blandade materialiserade och icke-materialiserade konflikter, både serialiserbarhet och låsning av dataåtkomst, t.ex. SCO) löses lokalt (var och en av sina respektive variantinstansers egna lokala mekanismer).

Röstordning (VO eller Generalized CO (GCO); Raz 2009 ), föreningen av CO och alla dess ovanstående varianter, är ett användbart koncept och global serialiseringsteknik. För att följa VO krävs lokal serialiseringsbarhet (i den mest allmänna formen, kommutativitetsbaserad, och inklusive multiversioner) och röstordningsstrategin ( röstning enligt lokal prioritetsordning).

Genom att kombinera resultaten för CO och dess varianter kommer följande slutsats:

• CO-varianters interoperabilitetssats

1. I en multi-databasmiljö, där varje databassystem (transaktionsobjekt) är kompatibelt med någon CO-variantegenskap (VO-kompatibel), kan vilken global transaktion som helst delta samtidigt i databaser med möjligen olika CO-varianter, och Global serialiserbarhet är garanterad (tillräckligt villkor för Global serialiserbarhet och Global one-copy-serializability (1SER), för ett fall då en databas med flera versioner finns).
2. Om endast lokal (till ett databassystem) samtidighetskontrollinformation används av varje databassystem (vart och ett har den generaliserade autonomi- egenskapen, en generalisering av autonomi ), så är överensstämmelse för var och en med någon (valfri) CO-variantegenskap (VO-kompatibilitet) en nödvändig förutsättning för att garantera Global serialiserbarhet (och Global 1SER; annars kan de kränkas).
3. Vidare, i en sådan miljö löses dataåtkomstlåsningsrelaterade globala dödlägen automatiskt (varje sådant dödläge genereras av en global cykel i den utökade konfliktgrafen (dvs. ett dödläge för röstning ; se ovan), som involverar minst ett dataåtkomstlås (icke-materialiserad konflikt) och två databassystem; alltså inte en cykel i den vanliga konfliktgrafen och påverkar inte serialiserbarheten).

• Raz, Yoav (augusti 1992), "The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment" ( PDF) , Proceedings of the Artonth International Conference on Very Large Data Bases , Vancouver, Kanada , s. 292–312 (även DEC-TR 841, Digital Equipment Corporation , november 1990)
• Raz, Yoav (september 1994), "Serializability by Commitment Ordering", Information Processing Letters , 51 (5): 257–264, doi : 10.1016/0020-0190(94)90005-1
• Raz, Yoav (juni 2009), Theory of Commitment Ordering: Summary , hämtad 11 november 2011
• Raz, Yoav (november 1990), On the Significance of Commitment Ordering (PDF) , Digital Equipment Corporation
• Yoav Raz (1991a): USA-patent 5 504 899 (ECO) 5 504 900 (CO) 5 701 480 (MVCO)
• Yoav Raz (1991b): "The Commitment Order Coordinator (COCO) of a Resource Manager, or Architecture for Distributed Commitment Ordering Based Concurrency Control", DEC-TR 843, Digital Equipment Corporation, december 1991.
• Yoav Raz (1991c): "Locking Based Strict Commitment Ordering, or How to improve Concurrency in Locking Based Resource Managers", DEC-TR 844, december 1991.
• Yoav Raz (1993a): "Utökad beställning av åtaganden eller garanterar global serialisering genom att tillämpa selektivitet för åtagandeorder på globala transaktioner." Proceedings of the Twelfth ACM Symposium on Principles of Database Systems (PODS), Washington, DC, s. 83-96, maj 1993. (även DEC-TR 842, november 1991)
• Yoav Raz (1993b): "Commitment Ordering Based Distributed Concurrency Control for Bridging Single and Multi Version Resources." Proceedings of the Third IEEE International Workshop on Research Issues on Data Engineering: Interoperability in Multidatabase Systems (RIDE-IMS), Wien, Österrike, s. 189-198, april 1993. (även DEC-TR 853, juli 1992)

externa länkar

• Yoav Raz's Commitment beställningssida