Kworum (przetwarzanie rozproszone)

Kworum to minimalna liczba głosów, jaką musi uzyskać transakcja rozproszona , aby móc wykonać operację w systemie rozproszonym . Wdrożono technikę opartą na kworum, aby wymusić spójne działanie w systemie rozproszonym .

Techniki oparte na kworum w rozproszonych systemach baz danych

Głosowanie oparte na kworum może być stosowane jako metoda kontroli replik , a także jako metoda zatwierdzania w celu zapewnienia niepodzielności transakcji w przypadku podziału sieci .

Głosowanie na podstawie kworum w protokołach zatwierdzeń

W rozproszonym systemie baz danych transakcja może wykonywać swoje operacje w wielu lokalizacjach. Ponieważ atomowość wymaga, aby każda rozproszona transakcja była niepodzielna, transakcja musi mieć ten sam los ( zatwierdzenie lub przerwanie ) w każdym miejscu. W przypadku podziału sieci witryny są podzielone i partycje mogą nie być w stanie komunikować się ze sobą. W tym miejscu pojawia się technika oparta na kworum. Podstawową ideą jest to, że transakcja zostaje zrealizowana, jeśli większość witryn zagłosuje za jej wykonaniem.

Każdej witrynie w systemie przypisany jest głos V _i . Załóżmy, że całkowita liczba głosów w systemie wynosi V, a kwora dotyczące przerwania i zatwierdzenia wynoszą odpowiednio V _a i _Vc . Następnie podczas realizacji protokołu zatwierdzenia należy przestrzegać następujących zasad:

V _za + V _do > V, gdzie 0 < V _do , V _za ${\ displaystyle \ równoważnik}$ V.
Zanim transakcja zostanie zatwierdzona, musi uzyskać kworum zatwierdzenia _Vc . Łącznie co najmniej jedna witryna gotowa do zatwierdzenia i zero lub więcej witryn oczekujących ${\ displaystyle \ geq}$ V _do .
Zanim transakcja zostanie przerwana, musi uzyskać kworum do przerwania. V _a Łączna liczba zero lub więcej witryn przygotowanych do przerwania lub jakichkolwiek $oczekujących$ V _a .

Pierwsza zasada gwarantuje, że transakcja nie może zostać zatwierdzona i przerwana w tym samym czasie. Kolejne dwie reguły wskazują liczbę głosów, jakie musi uzyskać transakcja, zanim będzie mogła zostać zakończona w ten czy inny sposób.

Głosowanie na podstawie kworum w sprawie kontroli repliki

W zreplikowanych bazach danych kopie obiektu znajdują się w kilku lokalizacjach. Aby zapewnić możliwość serializacji , żadne dwie transakcje nie powinny mieć możliwości równoczesnego odczytu lub zapisu elementu danych. W przypadku zreplikowanych baz danych można zastosować protokół kontroli repliki oparty na kworum, aby zapewnić, że dwie transakcje jednocześnie nie będą odczytywane ani zapisywane żadne dwie kopie elementu danych.

Głosowanie oparte na kworum w przypadku kontroli replik wynika z [Gifford, 1979]. Każdej kopii zreplikowanego elementu danych przypisany jest głos. Każda operacja musi następnie uzyskać kworum odczytu (Vr ₎ lub kworum zapisu (Vw ₎ , aby odpowiednio odczytać lub zapisać element danych. Jeżeli na dany element danych przypada łącznie V głosów, kwora muszą spełniać następujące zasady:

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

Pierwsza reguła gwarantuje, że element danych nie będzie odczytywany i zapisywany przez dwie transakcje jednocześnie. Ponadto zapewnia, że kworum odczytu zawiera co najmniej jedną witrynę z najnowszą wersją elementu danych. Druga reguła zapewnia, że dwie operacje zapisu z dwóch transakcji nie mogą wystąpić jednocześnie na tym samym elemencie danych. Te dwie reguły zapewniają zachowanie możliwości serializacji przy jednej kopii.

Zobacz też

^ ^ab ^Ozsu , Tamer M; Valduriez, Patrick (1991). „12”. Zasady rozproszonych systemów baz danych (wyd. 2). Upper Saddle River, New Jersey: Prentice-Hall, Inc. ISBN 978-0-13-691643-7 .
^ Skeen, Dale. „Protokół zatwierdzania oparty na kworum” (PDF) . Biblioteka ECommons Uniwersytetu Cornell . Źródło 10 lutego 2013 r .
^ Gifford, David K. (1979). Głosowanie ważone dla zreplikowanych danych . SOSP '79: Materiały z siódmego sympozjum ACM na temat zasad systemów operacyjnych. Pacific Grove, Kalifornia, Stany Zjednoczone: ACM. s. 150–162. doi : 10.1145/800215.806583 .

[ozsu-1] Ozsu , Tamer M; Valduriez, Patrick (1991). „12”. Zasady rozproszonych systemów baz danych (wyd. 2). Upper Saddle River, New Jersey: Prentice-Hall, Inc. ISBN 978-0-13-691643-7 .

[2] Skeen, Dale. „Protokół zatwierdzania oparty na kworum” (PDF) . Biblioteka ECommons Uniwersytetu Cornell . Źródło 10 lutego 2013 r .

[3] Gifford, David K. (1979). Głosowanie ważone dla zreplikowanych danych . SOSP '79: Materiały z siódmego sympozjum ACM na temat zasad systemów operacyjnych. Pacific Grove, Kalifornia, Stany Zjednoczone: ACM. s. 150–162. doi : 10.1145/800215.806583 .