Kvorum (distribuované výpočty) - Quorum (distributed computing)

A kvorum je minimální počet hlasů, které musí distribuovaná transakce získat, aby mohla provádět operaci v a distribuovaný systém. A kvorumJe implementována technika založená na vynucení konzistentního provozu v distribuovaném systému.

Techniky založené na kvoru v distribuovaných databázových systémech

Hlasování na základě kvora lze použít jako a replika způsob ovládání,^[1]stejně jako způsob potvrzení k zajištění transakce atomicita v přítomnosti síťové dělení.^[1]

Hlasování na základě kvora v protokolech potvrzení

V distribuovaném databázovém systému může transakce provádět své operace na více místech. Protože atomicita vyžaduje, aby každá distribuovaná transakce byla atomická, musí mít transakce stejný osud (spáchat nebo přerušit ) na každém místě. V případě síťového rozdělení jsou weby rozděleny na oddíly a oddíly nemusí být schopné vzájemně komunikovat. To je místo, kde přichází metoda založená na kvoru. Základní myšlenkou je, že transakce je provedena, pokud k jejímu provedení hlasuje většina webů.

Každému webu v systému je přidělen hlasování V_i. Předpokládejme, že celkový počet hlasů v systému je V a usnášeníschopná kvora jsou V_A a V_C, resp. Při implementaci protokolu potvrzení se musí dodržovat následující pravidla:

PROTI_A + V_C > V, kde 0 C, V_A ${displaystyle leq}$ PROTI.
Než se transakce zaváže, musí získat kvorum potvrzení V_C.
Celkem alespoň jeden web, který je připraven k potvrzení, a nula nebo více webů čeká ${displaystyle geq}$ PROTI_C.^[2]
Než se transakce přeruší, musí získat kvorum V pro zrušení_A
Celkem nula nebo více webů připravených k přerušení nebo jakékoli weby čekající ${displaystyle geq}$ PROTI_A.

První pravidlo zajišťuje, že transakce nemůže být potvrzena a zrušena současně. Další dvě pravidla označují hlasy, které musí transakce získat, než může být ukončena tak či onak.

Hlasování kvora pro kontrolu replik

V replikovaných databázích má datový objekt kopie přítomné na několika webech. Ujistit se serializovatelnost, neměly by být povoleny žádné dvě transakce ke čtení nebo zápisu datové položky současně. V případě replikovaných databází lze použít protokol kontroly replik založený na kvoru, aby bylo zajištěno, že dvě kopie kopie datové položky nebudou čteny ani zapisovány dvěma transakcemi současně.

Hlasování kvora pro kontrolu replik je způsobeno [Gifford, 1979].^[3]Každá kopie replikované datové položky má přiřazen hlas. Každá operace pak musí získat a čtení kvora (PROTI_r) nebo a napsat kvorum (PROTI_w) ke čtení nebo zápisu datové položky. Pokud má daná datová položka celkem V hlasů, musí se kvora řídit následujícími pravidly:

PROTI_r + V_w > V
PROTI_w > V / 2

První pravidlo zajišťuje, že datová položka není čtena a zapisována dvěma transakcemi současně. Kromě toho zajišťuje, že kvorum pro čtení obsahuje alespoň jeden web s nejnovější verzí datové položky. Druhé pravidlo zajišťuje, že dvě operace zápisu ze dvou transakcí nemohou na stejné datové položce nastat současně. Tato dvě pravidla zajišťují zachování serializovatelnosti jedné kopie.

Viz také

Reference

^ ^A ^b Ozsu, Tamer M; Valduriez, Patrick (1991). „12“. Principy distribuovaných databázových systémů (2. vyd.). Upper Saddle River, NJ: Prentice-Hall, Inc. ISBN 978-0-13-691643-7.
^ Skeen, Dale. „Závazkový protokol založený na kvoru“ (PDF). Cornell University ECommons Library. Citováno 10. února 2013.
^ Gifford, David K. (1979). Vážené hlasování pro replikovaná data. SOSP '79: Sborník příspěvků ze sedmého sympózia ACM o principech operačních systémů. Pacific Grove, Kalifornie, USA: ACM. 150–162. doi:10.1145/800215.806583.

[ozsu-1] A ^b Ozsu, Tamer M; Valduriez, Patrick (1991). „12“. Principy distribuovaných databázových systémů (2. vyd.). Upper Saddle River, NJ: Prentice-Hall, Inc. ISBN 978-0-13-691643-7.

[2] Skeen, Dale. „Závazkový protokol založený na kvoru“ (PDF). Cornell University ECommons Library. Citováno 10. února 2013.

[3] Gifford, David K. (1979). Vážené hlasování pro replikovaná data. SOSP '79: Sborník příspěvků ze sedmého sympózia ACM o principech operačních systémů. Pacific Grove, Kalifornie, USA: ACM. 150–162. doi:10.1145/800215.806583.

[1]

[2]

[3]