Quorum (distribuerad datoranvändning)

Ett beslutfört är det minsta antal röster som en distribuerad transaktion måste erhålla för att få utföra en operation i ett distribuerat system . En kvorumbaserad teknik implementeras för att upprätthålla konsekvent drift i ett distribuerat system.

Kvorumbaserade tekniker i distribuerade databassystem

Kvorumsbaserad röstning kan användas som en replikkontrollmetod , såväl som en commit-metod för att säkerställa transaktionsatomicitet i närvaro av nätverkspartitionering .

Kvorumsbaserad omröstning i åtagandeprotokoll

I ett distribuerat databassystem kan en transaktion utföra sina operationer på flera platser. Eftersom atomicitet kräver att varje distribuerad transaktion är atomär, måste transaktionen ha samma öde ( begå eller avbryta ) på varje plats. Vid nätverkspartitionering partitioneras webbplatser och partitionerna kanske inte kan kommunicera med varandra. Det är här en kvorumbaserad teknik kommer in. Den grundläggande idén är att en transaktion genomförs om majoriteten av webbplatserna röstar för att utföra den.

Varje plats i systemet tilldelas en röst V _i . Låt oss anta att det totala antalet röster i systemet är V och att avbryta och begå beslutförhet är V _a respektive V _{c .} Då måste följande regler följas vid implementeringen av commit-protokollet:

V _a + V _c > V, där 0 < V _c , V _a $\leq$ V.
Innan en transaktion åtar sig måste den erhålla ett beslutsförhet V _c . Summan av minst en webbplats som är beredd att commitera och noll eller fler webbplatser som väntar $\geq$ V _c .
Innan en transaktion avbryts måste den erhålla ett avbrytande kvorum V _a Summan av noll eller fler webbplatser som är beredda att avbryta eller några platser som väntar $\geq$ V _a .

Den första regeln säkerställer att en transaktion inte kan begås och avbrytas samtidigt. De följande två reglerna anger de röster som en transaktion måste få innan den kan avslutas på ett eller annat sätt.

Kvorumsbaserad omröstning för replikkontroll

I replikerade databaser har ett dataobjekt kopior på flera platser. För att säkerställa serialiseringsbarhet bör inga två transaktioner tillåtas att läsa eller skriva ett dataobjekt samtidigt. I fallet med replikerade databaser kan ett kvorumbaserat replikkontrollprotokoll användas för att säkerställa att inga två kopior av ett dataobjekt läses eller skrivs av två transaktioner samtidigt.

Den kvorumbaserade röstningen för replikkontroll beror på [Gifford, 1979]. Varje kopia av en replikerad datapost tilldelas en röst. Varje operation måste sedan erhålla ett läskvorum (Vr ₎ eller ett skrivkvorum (Vw ) för att läsa respektive skriva _en datapost. Om en given datapost har totalt V röster, måste beslutförheterna följa följande regler:

V _r + V _w > V
V _w > V/2

Den första regeln säkerställer att en datapost inte läses och skrivs av två transaktioner samtidigt. Dessutom säkerställer det att ett läst kvorum innehåller minst en webbplats med den senaste versionen av dataobjektet. Den andra regeln säkerställer att två skrivoperationer från två transaktioner inte kan ske samtidigt på samma datapost. De två reglerna säkerställer att en kopia kan serialiseras.

Se även

^ ^a ^b Ozsu, Tamer M; Valdriez, Patrick (1991). "12". Principer för distribuerade databassystem (2:a uppl.). Upper Saddle River, NJ: Prentice-Hall, Inc. ISBN 978-0-13-691643-7 .
^ Skeen, Dale. "A Quorum-based Commit Protocol" (PDF) . Cornell University ECommons Library . Hämtad 10 februari 2013 .
^ Gifford, David K. (1979). Viktad röstning för replikerad data . SOSP '79: Handlingar från det sjunde ACM-symposiet om operativsystemsprinciper. Pacific Grove, Kalifornien, USA: ACM. s. 150–162. doi : 10.1145/800215.806583 .

[ozsu-1] Ozsu, Tamer M; Valdriez, Patrick (1991). "12". Principer för distribuerade databassystem (2:a uppl.). Upper Saddle River, NJ: Prentice-Hall, Inc. ISBN 978-0-13-691643-7 .

[2] Skeen, Dale. "A Quorum-based Commit Protocol" (PDF) . Cornell University ECommons Library . Hämtad 10 februari 2013 .

[3] Gifford, David K. (1979). Viktad röstning för replikerad data . SOSP '79: Handlingar från det sjunde ACM-symposiet om operativsystemsprinciper. Pacific Grove, Kalifornien, USA: ACM. s. 150–162. doi : 10.1145/800215.806583 .