Zamówienie na zobowiązania

Porządkowanie zobowiązań ( CO ) to klasa interoperacyjnych technik serializacji w kontroli współbieżności baz danych , przetwarzania transakcji i powiązanych aplikacji. Pozwala na optymistyczne (nieblokujące) implementacje. Wraz z rozprzestrzenianiem się procesorów wielordzeniowych CO jest również coraz częściej wykorzystywane w programowaniu współbieżnym , pamięci transakcyjnej i pamięci transakcyjnej oprogramowania (STM), aby optymistycznie osiągnąć serializowalność . CO to także nazwa wynikowej harmonogramu transakcji (historii), zdefiniowanej w 1988 roku nazwą dynamiczna niepodzielność . W harmonogramie zgodnym z CO porządek chronologiczny zdarzeń zobowiązań transakcji jest zgodny z porządkiem pierwszeństwa odpowiednich transakcji. CO to szeroki szczególny przypadek serializacji konfliktów i skutecznych środków ( niezawodnych , wysokowydajnych, rozproszonych i skalowalnych ) w celu osiągnięcia globalnej serializowalności (serializowalności modułowej) w dowolnym zbiorze systemów baz danych, które prawdopodobnie używają różnych mechanizmów kontroli współbieżności (CO sprawia również, że każdy zgodność z serializacją systemu, jeśli jeszcze nie).

Każdy system bazy danych niezgodny z CO jest rozszerzony o komponent CO (koordynator zleceń zobowiązań — COCO), który porządkuje zdarzenia zobowiązań pod kątem zgodności z CO, bez dostępu do danych ani żadnych innych zakłóceń w operacjach transakcyjnych. Jako taki, CO zapewnia niskie narzuty, ogólne rozwiązanie dla globalnej serializacji (i rozproszonej serializacji), instrumentalne dla globalnej kontroli współbieżności (i rozproszonej kontroli współbieżności ) systemów z wieloma bazami danych i innych obiektów transakcyjnych, prawdopodobnie wysoce rozproszonych (np. w ramach przetwarzania w chmurze , grid computing i sieci smartfonów ). Atomowy protokół zobowiązań (ACP; dowolnego typu) jest podstawową częścią rozwiązania, wykorzystywaną do przerywania globalnych cykli w grafie konfliktów (pierwszeństwo, serializowalność). CO jest najbardziej ogólną właściwością ( warunkiem koniecznym ), która gwarantuje globalną serializację, jeśli zaangażowane systemy baz danych nie współdzielą informacji kontroli współbieżności poza komunikatami protokołu zobowiązań atomowych (niezmodyfikowanych) i nie mają wiedzy o tym, czy transakcje są globalne, czy lokalne (systemy baz danych są autonomiczne ). Zatem CO (wraz z jego wariantami) jest jedyną ogólną techniką, która nie wymaga typowo kosztownej dystrybucji lokalnych informacji sterowania współbieżnością (np. lokalnych relacji pierwszeństwa, blokad, znaczników czasu lub biletów). Uogólnia popularną silnego ścisłego blokowania dwufazowego (SS2PL), która w połączeniu z protokołem zatwierdzania dwufazowego (2PC) jest de facto standardem umożliwiającym osiągnięcie globalnej serializacji w systemach baz danych (opartych na SS2PL). W rezultacie systemy baz danych zgodne z CO (z dowolnymi różnymi typami kontroli współbieżności) mogą w przejrzysty sposób łączyć się z takimi rozwiązaniami opartymi na SS2PL w celu globalnej serializacji.

Ponadto globalne zakleszczenia oparte na blokowaniu są rozwiązywane automatycznie w środowisku wielu baz danych opartym na CO, co jest istotną korzyścią uboczną (w tym specjalny przypadek środowiska całkowicie opartego na SS2PL; wcześniej niezauważony fakt w przypadku SS2PL).

Co więcej, ścisłe porządkowanie zobowiązań (SCO; Raz 1991c ), skrzyżowanie Ścisłości i CO, zapewnia lepszą wydajność (krótszy średni czas realizacji transakcji i skutkujący lepszą przepustowością transakcji ) niż SS2PL, gdy występują konflikty odczytu i zapisu (identyczne zachowanie blokowania dla zapisu -konflikty odczytu i zapisu-zapisu; porównywalny narzut blokowania). Zaletą SCO jest zwłaszcza rywalizacja o blokadę. Ścisłość pozwala zarówno SS2PL, jak i SCO na korzystanie z tych samych skutecznych odzyskiwania bazy danych .

Istnieją dwa główne uogólniające warianty CO, rozszerzony CO (ECO; Raz 1993a ) i wielowersyjny CO (MVCO; Raz 1993b ). Zapewniają również globalną serializację bez lokalnej dystrybucji informacji o kontroli współbieżności, można je łączyć z dowolną odpowiednią kontrolą współbieżności i umożliwiają optymistyczne (nieblokujące) implementacje. Oba wykorzystują dodatkowe informacje w celu złagodzenia ograniczeń CO i osiągnięcia lepszej współbieżności i wydajności. Porządkowanie głosów (VO lub Generalized CO (GCO); Raz 2009 ) to zestaw harmonogramów kontenerów (właściwości) i technika dla CO i wszystkich jego wariantów. Lokalne VO jest niezbędne do zagwarantowania globalnej serializacji, jeśli uczestnicy atomowego protokołu zobowiązań (ACP) nie współdzielą informacji o kontroli współbieżności (mają właściwość uogólnionej autonomii ). CO i jego warianty współdziałają w przejrzysty sposób, gwarantując globalną serializację i automatyczne globalne rozwiązywanie impasu w mieszanym, heterogenicznym środowisku z różnymi wariantami.

Przegląd

Commitment ordering (CO; Raz 1990 , 1992 , 1994 , 2009 ) jest również określana jako dynamiczna niepodzielność (od 1988 r.), porządkowanie zatwierdzeń , serializowalność zleceń zatwierdzeń i silne odtwarzanie (od 1991 r.). Ta ostatnia nazwa jest myląca, ponieważ CO jest nieporównywalne z odzyskiem , a termin „silny” oznacza szczególny przypadek. Oznacza to, że istotna właściwość odzyskiwalności niekoniecznie ma właściwość CO i vice versa.

W 2009 roku CO została scharakteryzowana jako główna metoda kontroli współbieżności, wraz ze znanymi wcześniej ( od lat 80 . mechanizmy kontroli współbieżności.

W sfederowanym systemie baz danych lub dowolnym innym, bardziej luźno zdefiniowanym systemie z wieloma bazami danych, które są zwykle rozproszone w sieci komunikacyjnej, transakcje obejmują wiele baz danych i prawdopodobnie rozproszonych baz danych . Wymuszanie globalnej serializacji w takim systemie jest problematyczne. Nawet jeśli każdy lokalny harmonogram pojedynczej bazy danych jest nadal możliwy do serializacji, globalny harmonogram całego systemu niekoniecznie jest możliwy do serializacji. Masowa wymiana informacji o konflikcie potrzebna między bazami danych do osiągnięcia możliwości serializacji konfliktu doprowadziłaby do niedopuszczalnej wydajności, głównie z powodu opóźnień komputera i komunikacji . Problem skutecznego osiągnięcia globalnej serializacji został scharakteryzowany jako otwarty aż do publicznego ujawnienia CO w 1991 roku przez jego wynalazcę Yoav Raza ( Raz 1991a ; patrz także Globalna serializowalność ).

Wymuszanie CO jest skutecznym sposobem globalnego wymuszania serializacji konfliktów w systemie rozproszonym, ponieważ wymuszanie CO lokalnie w każdej bazie danych (lub innych obiektach transakcyjnych) wymusza to również globalnie. Każda baza danych może wykorzystywać dowolny, ewentualnie inny typ mechanizmu kontroli współbieżności. W przypadku lokalnego mechanizmu, który już zapewnia serializowalność konfliktów, lokalne wymuszanie CO nie powoduje żadnych innych przerwań, ponieważ lokalne wymuszanie CO nie wpływa na strategię planowania dostępu do danych mechanizmu (szeregowanie to określa przerwania związane z serializacją; taki mechanizm zazwyczaj nie rozważyć zdarzenia zaangażowania lub ich kolejność). Rozwiązanie CO nie wymaga narzutu komunikacyjnego, ponieważ wykorzystuje tylko (niezmodyfikowane) zobowiązań atomowych , które są już potrzebne każdej rozproszonej transakcji do osiągnięcia atomowości. Atomowy protokół zobowiązań odgrywa kluczową rolę w rozproszonym algorytmie CO, który wymusza globalne CO poprzez przerywanie globalnych cykli (cykli obejmujących dwie lub więcej baz danych) na globalnym grafie konfliktów. CO, jego szczególne przypadki i jego uogólnienia są interoperacyjne i osiągają globalną serializację, będąc w przejrzysty sposób wykorzystywane razem w jednym heterogenicznym środowisku rozproszonym obejmującym obiekty z możliwie różnymi mechanizmami kontroli współbieżności. Jako takie, Commitment ordering , w tym jego specjalne przypadki i wraz z jego uogólnieniami (patrz warianty CO poniżej), zapewnia ogólne, wysokowydajne, w pełni rozproszone rozwiązanie (nie jest potrzebny żaden centralny komponent przetwarzający ani centralna struktura danych) do zagwarantowania globalnej serializacji w heterogeniczne środowiska systemów wielobazowych i innych obiektów transakcyjnych (obiektów, których stany są dostępne i modyfikowane tylko przez transakcje; np. w ramach procesów transakcyjnych oraz w ramach Cloud computing i Grid computing). Rozwiązanie CO skaluje się wraz z rozmiarem sieci i liczbą baz danych bez negatywnego wpływu na wydajność (przy założeniu, że statystyki pojedynczej rozproszonej transakcji, np. średnia liczba baz danych zaangażowanych w pojedynczą transakcję, pozostają niezmienione).

Wraz z rozprzestrzenianiem się procesorów wielordzeniowych , Optimistic CO (OCO) był również coraz częściej wykorzystywany do osiągania serializacji w pamięci transakcyjnej oprogramowania, a liczne artykuły i patenty STM wykorzystujące „kolejność zatwierdzenia” zostały już opublikowane (np. Zhang i in. 2006 ).

Rozwiązanie do zamawiania zobowiązań dla globalnej serializacji

Ogólna charakterystyka CO

Porządkowanie zobowiązań (CO) to szczególny przypadek serializacji konfliktu. CO można wymusić za pomocą nieblokujących (każda transakcja może wykonać swoje zadanie bez blokowania dostępu do danych, co pozwala na optymistyczną kontrolę współbieżności ; jednak zobowiązanie może zostać zablokowane). W harmonogramie CO kolejność ( częściowa ) pierwszeństwa zdarzeń zobowiązań odpowiada kolejności (częściowej) kolejności odpowiednich transakcji na ( ukierunkowanym ) grafie konfliktu (wykres pierwszeństwa, wykres serializacji), zgodnie z ich sprzecznym dostępem operacje (zwykle operacje odczytu i zapisu (wstawianie/modyfikowanie/usuwanie); CO ma również zastosowanie do operacji wyższego poziomu, w których są one sprzeczne, jeśli są nieprzemienne , a także do konfliktów między operacjami na danych z wielu wersji).

Definicja: porządkowanie zobowiązań

Niech $}$ dwiema zatwierdzonymi transakcjami w harmonogramie, tak że jest w konflikcie z ${1}$${\ Displaystyle T_ {1}}$ ( ${\ Displaystyle T_ {1}}$ poprzedza ${\ Displaystyle T_ {2}}$ ). Harmonogram ma ${1}$ porządkowania zobowiązań (CO), jeśli dla każdych dwóch takich transakcji $} zatwierdza$ przed zatwierdzeniami.

Zdarzenia związane z decyzją o zaangażowaniu są generowane przez lokalny mechanizm zaangażowania lub niepodzielny protokół zaangażowania, jeśli różne procesy muszą osiągnąć konsensus co do tego, czy zatwierdzić, czy przerwać. Protokół może być rozproszony lub scentralizowany. Transakcje mogą być zatwierdzane jednocześnie, jeśli pozwala na to zlecenie częściowe zatwierdzania (jeśli nie mają sprzecznych operacji). Załóżmy, że różne sprzeczne operacje powodują różne zamówienia częściowe tych samych transakcji. W takim przypadku wykres konfliktu ma cykle , a harmonogram naruszy możliwość serializacji, gdy wszystkie transakcje w cyklu zostaną zatwierdzone. W takim przypadku nie można znaleźć częściowej kolejności zdarzeń zobowiązania. Zatem cykle na wykresie konfliktu muszą zostać przerwane przez przerwanie transakcji. Jednak każdy harmonogram, który można serializować w przypadku konfliktu, można ustawić jako CO bez przerywania jakiejkolwiek transakcji poprzez odpowiednie opóźnienie zdarzeń zatwierdzania, aby zachować zgodność z częściowym porządkiem pierwszeństwa transakcji.

Samo egzekwowanie CO nie jest wystarczające jako mechanizm kontroli współbieżności, ponieważ CO nie ma właściwości odzyskiwania, która również powinna być obsługiwana.

Algorytm rozproszonego CO

w pełni rozproszony algorytm wymuszania zamawiania globalnych zobowiązań , który wykorzystuje lokalny CO każdej uczestniczącej bazy danych i potrzebuje tylko (niezmodyfikowanych) komunikatów protokołu zobowiązań atomowych bez dalszej komunikacji. Algorytm rozproszony jest połączeniem lokalnych (dla każdej bazy danych) procesów algorytmu CO i atomowego protokołu zobowiązań (który może być w pełni dystrybuowany). Atomowy protokół zobowiązań jest niezbędny do wymuszenia niepodzielności każdej transakcji rozproszonej (aby zdecydować, czy ją zatwierdzić, czy przerwać; ta procedura jest zawsze przeprowadzana dla transakcji rozproszonych, niezależnie od kontroli współbieżności i CO). Typowym przykładem protokołu zatwierdzania atomowego jest protokół zatwierdzania dwufazowego , który jest odporny na wiele typów awarii systemu. W niezawodnym środowisku lub gdy procesy zwykle zawodzą razem (np. w tym samym układzie scalonym ), można zastosować prostszy protokół zaangażowania atomowego (np. koordynator transakcji, czyli rodzaj protokołu zatwierdzania jednofazowego ). Atomowy protokół zobowiązań osiąga konsensus wśród uczestników co do tego, czy zatwierdzić , czy przerwać rozproszoną (globalną) transakcję, która obejmuje tych uczestników. Istotnym etapem w każdym takim protokole jest głosowanie TAK (wyraźne lub dorozumiane) przez każdego uczestnika, co oznacza zobowiązanie uczestnika głosującego do podporządkowania się decyzji protokołu, albo zatwierdzenia, albo zaniechania. W przeciwnym razie uczestnik może jednostronnie przerwać transakcję poprzez wyraźny głos NIE. wszyscy uczestnicy otrzymali głosy TAK (a zatem brakujący głos jest zwykle uważany za NIE). W przeciwnym razie protokół przerywa transakcję. Różne protokoły zatwierdzania atomowego różnią się jedynie możliwościami radzenia sobie z różnymi sytuacjami awarii środowiska komputerowego oraz ilością pracy i innymi zasobami obliczeniowymi potrzebnymi w różnych sytuacjach.

Całe rozwiązanie CO dla globalnej serializacji opiera się na fakcie, że atomowy protokół zobowiązań ostatecznie przerywa tę transakcję w przypadku braku głosu dla transakcji rozproszonej.

Egzekwowanie globalnego CO

W każdym systemie bazy danych lokalny algorytm CO określa wymaganą kolejność zobowiązań dla tej bazy danych. Zgodnie z powyższą charakterystyką CO kolejność ta zależy od lokalnego porządku pierwszeństwa transakcji, który wynika z lokalnych mechanizmów szeregowania dostępu do danych. W związku z tym głosy TAK w protokole zobowiązania atomowego są zaplanowane dla każdej (nieprzerwanej) transakcji rozproszonej (w dalszej części „głos” oznacza głos TAK). Załóżmy, że istnieje relacja pierwszeństwa (konflikt) między dwiema transakcjami. W takim przypadku druga nie zostanie poddana pod głosowanie, zanim pierwsza nie zostanie zakończona (zatwierdzona lub przerwana), aby zapobiec możliwemu naruszeniu rozkazu zatwierdzenia przez protokół zobowiązania atomowego. Może się tak zdarzyć, ponieważ kolejność zatwierdzenia w protokole niekoniecznie jest taka sama jak kolejność głosowania. Jeśli nie istnieje relacja pierwszeństwa, oba można głosować jednocześnie. Ta strategia porządkowania głosów zapewnia, że ​​również atomowy protokół zobowiązań zachowuje kolejność zobowiązań, co jest warunkiem koniecznym do zagwarantowania Globalnego CO (i lokalnego CO bazy danych; bez niego zarówno Globalny CO, jak i Lokalny CO (właściwość oznaczająca, że ​​każda baza danych jest zgodne z CO) mogą zostać naruszone).

Ponieważ jednak systemy baz danych planują swoje transakcje niezależnie, możliwe jest, że porządki pierwszeństwa transakcji w dwóch lub więcej bazach danych nie są kompatybilne (nie istnieje globalny porządek częściowy, który mógłby osadzić razem odpowiednie lokalne zamówienia częściowe). W przypadku CO zamówienia pierwszeństwa są również zamówieniami zobowiązań. Gdy bazy danych uczestniczące w tej samej transakcji rozproszonej nie mają zgodnych lokalnych porządków pierwszeństwa dla tej transakcji (bez „wiedzy” o tym; zazwyczaj nie istnieje koordynacja między systemami baz danych w przypadku konfliktów, ponieważ potrzebna komunikacja jest masowa i niedopuszczalnie obniża wydajność), oznacza to, że transakcja znajduje się w globalnym cyklu (obejmującym dwie lub więcej baz danych) na globalnym wykresie konfliktów. W takim przypadku protokół zobowiązania atomowego nie zbierze wszystkich głosów potrzebnych do zatwierdzenia tej transakcji: Zgodnie z strategią porządkowania głosów co najmniej jedna baza danych opóźni głosowanie za tą transakcją na czas nieokreślony, aby zachować zgodność z własnym porządkiem zobowiązań (pierwszeństwo) , ponieważ będzie czekał na zakończenie kolejnej, poprzedzającej transakcje w tym globalnym cyklu opóźnionej w nieskończoność przez inną bazę danych o innym zamówieniu. Oznacza to impas w głosowaniu dotyczący baz danych w tym cyklu. W rezultacie protokół ostatecznie przerwie pewną zablokowaną transakcję w tym globalnym cyklu, ponieważ w każdej takiej transakcji brakuje co najmniej jednego głosu uczestnika. Wybór konkretnej transakcji w cyklu do przerwania zależy od polityki przerywania protokołu zobowiązań atomowych (mechanizm limitu czasu jest powszechny, ale może skutkować więcej niż jednym przerwaniem na cykl; można zarówno zapobiegać niepotrzebnym przerwaniom, jak i skracać czas przerwania przez dedykowany mechanizm przerwania dla CO). Takie przerwanie przerwie globalny cykl obejmujący tę rozproszoną transakcję. Zarówno transakcje zablokowane, jak i prawdopodobnie inne będące w konflikcie z zablokowanymi (a tym samym zablokowanymi) będą mogły być przedmiotem głosowania. Warto zauważyć, że każda baza danych związana z zakleszczeniem głosowania nadal regularnie głosuje na transakcje, które nie są w konflikcie z jej zakleszczoną transakcją, zazwyczaj prawie wszystkie zaległe transakcje. Zatem w przypadku niezgodnych lokalnych (częściowych) zleceń zobowiązań nie jest potrzebne żadne działanie, ponieważ atomowy protokół zobowiązań rozwiązuje je automatycznie, przerywając transakcję, która jest przyczyną niezgodności. Oznacza to, że powyższa strategia porządkowania głosów jest również warunkiem wystarczającym do zagwarantowania Global CO.

Stwierdza się, co następuje:

• Strategia porządkowania głosów dla globalnego twierdzenia o egzekwowaniu CO niezdecydowanymi

$,$ będą przerwanymi) transakcjami w systemie bazy danych, który wymusza CO dla transakcji lokalnych, ${\ Displaystyle T_ {2}}$ jest globalny i jest w konflikcie z ${\ Displaystyle T_ {1}}$ ( ${\ Displaystyle T_ {1}}$ poprzedza ${\ Displaystyle T_ {2}}$ ). Następnie, po zakończeniu (zatwierdzeniu lub przerwaniu) przed głosowaniem nad zatwierdzeniem ( strategia porządkowania głosów ), w każdym takim systemie bazy danych w $2$$T_ {2}}$ wielobazowe środowisko, jest warunkiem koniecznym i wystarczającym do zagwarantowania Global CO (warunek gwarantuje Global CO, który bez niego może zostać naruszony).

Uwagi:

1. Strategia $,$ głosów , która wymusza globalną określana jako w ( Raz 1992 )
2. Właściwość Local CO harmonogramu globalnego oznacza, że ​​każda baza danych jest zgodna z CO. Z dyskusji o konieczności, powyższa część bezpośrednio wynika, że ​​twierdzenie jest również prawdziwe, gdy zastępuje się „Globalny CO” przez „Lokalny CO”, gdy obecne są transakcje globalne. Razem oznacza to, że Globalny CO jest gwarantowany wtedy i tylko wtedy, gdy Lokalny CO jest gwarantowany (co jest nieprawdą w przypadku serializowalności globalnego konfliktu i serializowalności lokalnego konfliktu: Globalny implikuje Lokalny, ale nie odwrotnie).

Globalny CO implikuje globalną serializowalność.

Algorytm globalnego CO obejmuje wymuszanie (lokalnego) CO w każdym uczestniczącym systemie bazy danych poprzez zamawianie zatwierdzeń transakcji lokalnych (zobacz Wymuszanie CO lokalnie poniżej) i wymuszanie strategii porządkowania głosów w powyższym twierdzeniu (dla transakcji globalnych).

Dokładna charakterystyka impasu w głosowaniu według cykli globalnych

Powyższy globalny proces eliminacji cyklu przez impas w głosowaniu można szczegółowo wyjaśnić następującą obserwacją:

Po pierwsze, dla uproszczenia zakłada się, że każda transakcja osiąga stan gotowości do zatwierdzenia i jest głosowana przez co najmniej jedną bazę danych (oznacza to, że nie występuje blokowanie przez blokady). Zdefiniuj graf „oczekiwania na zatwierdzenie głosowania” jako graf skierowany z transakcjami jako węzłami i skierowaną krawędzią od dowolnej pierwszej transakcji do drugiej transakcji, jeśli pierwsza transakcja blokuje głosowanie za zatwierdzeniem drugiej transakcji (przeciwnie do konwencjonalnego kierunku krawędzi w wykres oczekiwania ). Takie blokowanie ma miejsce tylko wtedy, gdy druga transakcja koliduje z pierwszą transakcją (patrz wyżej). Zatem ten wykres „oczekiwania na zatwierdzenie głosowania” jest identyczny z wykresem globalnego konfliktu. Cykl na wykresie „oczekiwania na zatwierdzenie głosowania” oznacza impas w głosowaniu. Dlatego w głosowaniu występuje impas, jeśli na wykresie konfliktu występuje cykl. Lokalne mechanizmy serializacji eliminują lokalne cykle (ograniczone do jednej bazy danych). W rezultacie pozostają tylko globalne cykle, które są następnie eliminowane przez atomowy protokół zobowiązań, gdy przerywa on zakleszczone transakcje z brakującymi (zablokowanymi) odpowiednimi głosami.

Po drugie, obsługiwane są również lokalne zatwierdzenia: Zauważ, że podczas wymuszania CO, również oczekiwanie na zwykłe lokalne zatwierdzenie transakcji lokalnej może blokować lokalne zatwierdzenia i głosowania innych transakcji w przypadku konfliktów, a sytuacja dla transakcji globalnych również nie zmienia się bez powyższe założenie upraszczające: Końcowy wynik jest taki sam również przy lokalnym zaangażowaniu dla lokalnych transakcji, bez głosowania w atomowym zaangażowaniu dla nich.

Na koniec należy rozważyć blokowanie za pomocą blokady (która była do tej pory wykluczona): blokada blokuje sprzeczną operację i zapobiega materializacji konfliktu. Załóżmy, że blokada zostaje zwolniona dopiero po zakończeniu transakcji. W takim przypadku może pośrednio zablokować głosowanie lub lokalne zatwierdzenie innej transakcji (która nie może teraz przejść do stanu gotowości), z takim samym skutkiem, jak bezpośrednie zablokowanie głosowania lub lokalnego zatwierdzenia. Cykl jest generowany na grafie konfliktu tylko wtedy, gdy takie blokowanie przez zamek jest również reprezentowane przez krawędź. Dzięki takim dodanym krawędziom reprezentującym zdarzenia blokowania przez zamek, wykres konfliktu staje się rozszerzonym wykresem konfliktu .

• Definicja: rozszerzony wykres konfliktu

Rozszerzony $displaystyle T_ {1} } }$ konfliktu to wykres konfliktu z dodanymi krawędziami Oprócz oryginalnych krawędzi istnieje skierowana krawędź od transakcji do transakcji $\$ jeśli spełnione są dwa warunki:

1. ${\ Displaystyle T_ {2}}$ jest blokowany przez blokadę dostępu do danych zastosowaną przez ${\ Displaystyle T_ {1}}$ (blokowanie zapobiega konfliktowi ${\ Displaystyle T_ {2}}$ z ${\ displaystyle T_ {1}}$ przed zmaterializowaniem się i posiadaniem przewagi na regularnym wykresie konfliktu) i
2. To blokowanie nie zatrzyma się przed zakończeniem (zatwierdza lub przerywa; prawda dla każdego CO opartego na blokowaniu) ${\ displaystyle T_ {1} }$

Graf można również zdefiniować jako sumę (zwykłego) grafu konfliktu z (odwróconym brzegiem, regularny) grafem oczekiwania

Komentarze:

1. Tutaj, w przeciwieństwie do zwykłego wykresu konfliktu, który ma krawędzie tylko dla konfliktów zmaterializowanych, wszystkie zmaterializowane i niezmaterializowane konflikty są reprezentowane przez krawędzie.
2. Zauważ, że wszystkie nowe krawędzie są wszystkimi (odwróconymi do konwencjonalnych) krawędziami grafu oczekiwania . Graf oczekiwania można również zdefiniować jako wykres niezmaterializowanych konfliktów. Zgodnie z powszechną konwencją kierunek krawędzi na grafie konfliktu określa kolejność czasową między sprzecznymi operacjami, która jest przeciwna do kolejności zdefiniowanej przez krawędź na grafie oczekiwania .
3. Zauważ, że taki globalny wykres zawiera (ma osadzony) wszystkie (odwrócone krawędzie) regularne lokalne wykresy oczekiwania , a także może zawierać globalne cykle oparte na blokowaniu (które nie mogą istnieć w lokalnych wykresach). Na przykład, jeśli wszystkie bazy danych w cyklu globalnym są oparte na SS2PL, to wszystkie powiązane sytuacje blokowania głosów są spowodowane przez blokady (jest to klasyczny i prawdopodobnie jedyny globalny impas, o którym mowa w literaturze dotyczącej baz danych). Jest to przypadek globalnego zakleszczenia, w którym każda powiązana baza danych tworzy część cyklu, ale cały cykl nie znajduje się w żadnym lokalnym grafie oczekiwania.

W obecności CO rozszerzony wykres konfliktu jest w rzeczywistości (odwróconym brzegiem) wykresem oczekiwania na lokalne zatwierdzenie i głosowanie : Przewaga istnieje od pierwszej transakcji, lokalnej lub globalnej, do drugiej, jeśli druga czeka na koniec pierwszego, aby można było głosować (jeśli globalnie) lub lokalnie (jeśli lokalnie). Wszystkie globalne cykle (w dwóch lub więcej bazach danych) na tym wykresie generują impas w głosowaniu. Globalne cykle wykresu zapewniają pełną charakterystykę impasu w głosowaniu i mogą obejmować dowolną kombinację zmaterializowanych i niezmaterializowanych konfliktów. Tylko cykle (tylko) zmaterializowanych konfliktów są również cyklami regularnego grafu konfliktów i wpływają na serializowalność. Jeden lub więcej (związanych z blokadą) niezmaterializowanych konfliktów w cyklu uniemożliwia bycie cyklem na regularnym wykresie konfliktów i powoduje, że jest to impas związany z blokowaniem. Wszystkie globalne cykle (zakleszczenia w głosowaniu) muszą zostać przerwane (rozwiązane), aby zarówno zachować globalną serializowalność, jak i rozwiązać globalne zakleszczenia związane z blokowaniem dostępu do danych. Rzeczywiście, wszystkie one są łamane przez protokół zobowiązań atomowych z powodu braku głosów w przypadku impasu w głosowaniu.

Komentarz: Ta obserwacja wyjaśnia również poprawność rozszerzonego CO (ECO) poniżej: Kolejność głosowania transakcji globalnych musi być zgodna z kolejnością grafu konfliktów z blokowaniem głosów, gdy istnieje relacja kolejności (ścieżka wykresu) między dwiema transakcjami globalnymi. Lokalne transakcje nie są głosowane, a ich (lokalne) zatwierdzenia nie są blokowane w przypadku konfliktów. Powoduje to te same sytuacje impasu w głosowaniu i wynikający z tego globalny proces eliminacji cyklu dla ECO.

Sytuacja impasu w głosowaniu można podsumować w następujący sposób:

• Twierdzenie CO Voting-Deadlock

Niech środowisko z wieloma bazami danych obejmuje zgodne z CO (co eliminuje lokalne cykle ) systemy baz danych, które wymuszają każde Globalne CO (wykorzystując warunek z powyższego twierdzenia). Zakleszczenie w głosowaniu występuje wtedy i tylko wtedy, gdy globalny cykl (obejmujący dwie lub więcej baz danych) istnieje na wykresie globalnego konfliktu rozszerzonego (również blokowanie przez blokadę dostępu do danych jest reprezentowane przez krawędź). Załóżmy, że cykl nie zostanie przerwany przez żadne przerwanie. W takim przypadku wszystkie globalne transakcje na nim objęte są odpowiednim impasem w głosowaniu. Ostatecznie każdy ma zablokowany głos (bezpośrednio lub pośrednio przez blokadę dostępu do danych); jeśli transakcja lokalna znajduje się w cyklu, ostatecznie jej (lokalne) zatwierdzenie jest zablokowane.

Komentarz: Może wystąpić rzadka sytuacja impasu głosowania (poprzez brakujące głosy zablokowane), gdy żaden z systemów baz danych zaangażowanych w te transakcje nie głosuje na żadną transakcję w powiązanym cyklu. Taka sytuacja może wystąpić, gdy lokalne transakcje podrzędne są wielowątkowe . Przypadek o najwyższym prawdopodobieństwie takiego rzadkiego zdarzenia obejmuje dwie transakcje w dwóch równoczesnych przeciwnych cyklach. Takie globalne cykle (zakleszczenia) pokrywają się z lokalnymi cyklami, które są rozwiązywane lokalnie i są zwykle rozwiązywane przez lokalne mechanizmy bez zaangażowania atomowego. Formalnie jest to również cykl globalny, ale praktycznie jest to cykl lokalny (części lokalnych cykli generują cykl globalny; aby to zobaczyć, podziel każdą globalną transakcję (węzeł) na lokalne sub-transakcje (jej części są ograniczone do jednej bazy danych); między transakcjami istnieje skierowana krawędź, jeśli istnieje krawędź między dowolnymi lokalnymi podtransakcjami; cykl jest lokalny, jeśli wszystkie jego krawędzie pochodzą z cyklu między podtransakcjami tej samej bazy danych, a globalny, jeśli nie; globalny i lokalny mogą się nakładać: ten sam cykl między transakcjami może wynikać z kilku różnych cykli między podtransakcjami i być zarówno lokalny, jak i globalny).

Ponadto zakończono następujący przypadek specjalny oparty na blokowaniu:

• Twierdzenie globalnego zakleszczenia opartego na blokowaniu CO

W systemie wielobazowym zgodnym z CO globalny zakleszczenie oparte na blokowaniu, obejmujące co najmniej jedną blokadę dostępu do danych (konflikt niezmaterializowany) i dwa lub więcej systemów baz danych, jest odzwierciedleniem globalny cykl na grafie globalnego konfliktu rozszerzonego , który prowadzi do impasu w głosowaniu. Taki cykl nie jest cyklem w (zwykłym) grafie konfliktu globalnego (który odzwierciedla tylko zmaterializowane konflikty, więc taki cykl nie wpływa na serializowalność ).

Uwagi:

1. Każde zablokowanie (krawędź) w cyklu, które nie jest spowodowane blokadą dostępu do danych, bezpośrednio blokuje głosowanie lub lokalne zatwierdzenie. Wszystkie impasy w głosowaniu są rozwiązywane (prawie wszystkie przez zaangażowanie atomowe ; patrz komentarz powyżej), w tym ten typ oparty na blokowaniu.
2. Globalne zakleszczenia oparte na blokowaniu mogą być również generowane w całkowicie rozproszonym środowisku opartym na SS2PL (specjalny przypadek oparty na CO). Wszystkie blokowania głosów (i impasy w głosowaniu) są spowodowane blokadami dostępu do danych. Wiele artykułów naukowych od lat zajmuje się rozwiązywaniem takich globalnych impasów, ale żaden (z wyjątkiem artykułów dotyczących CO) nie jest znany (od 2009 r.), Aby zauważyć, że zaangażowanie atomowe automatycznie je rozwiązuje. Takie automatyczne rozwiązania regularnie pojawiają się niezauważone we wszystkich istniejących systemach wielobazowych opartych na SS2PL, często z pominięciem dedykowanych mechanizmów rozwiązywania problemów.

Zakleszczenia w głosowaniu są kluczem do działania rozproszonego CO.

Globalna eliminacja cyklu (tutaj rozwiązywanie impasu głosowania przez atomowe zobowiązanie ) i wynikające z tego ponowne wykonanie przerwanych transakcji są czasochłonne, niezależnie od zastosowanej kontroli współbieżności. Jeśli bazy danych planują transakcje niezależnie, globalne cykle są nieuniknione (w pełnej analogii do cykli/zakleszczeń generowanych w lokalnym SS2PL; przy dystrybucji każda koordynacja planowania transakcji lub operacji skutkuje naruszeniem autonomii i zwykle znacznym spadkiem wydajności). Jednak prawdopodobieństwo ich wystąpienia można w wielu przypadkach zmniejszyć, wdrażając wytyczne dotyczące projektowania baz danych i transakcji, które zmniejszają liczbę konfliktów związanych z transakcją globalną. licznikach akumulacji wielu transakcji, które są zazwyczaj gorącymi punktami ) .

Protokoły zobowiązań atomowych są przeznaczone i zaprojektowane w celu osiągnięcia atomowości bez uwzględniania kontroli współbieżności bazy danych. Przerywają po wykryciu lub znalezieniu heurystycznym (np. przez przekroczenie limitu czasu; czasami błędnie, niepotrzebnie) brakujących głosów i zazwyczaj nieświadomych globalnych cykli. Protokoły te można szczególnie udoskonalić pod kątem CO (w tym poniższych wariantów CO), aby zapobiegać niepotrzebnym przerwaniom i przyspieszać przerwania używane do przerywania globalnych cykli na globalnym rozszerzonym wykresie konfliktów (dla lepszej wydajności dzięki wcześniejszemu zwolnieniu po zakończeniu transakcji zasobów obliczeniowych i zazwyczaj zablokowanych danych ). Na przykład istniejące globalne metody wykrywania zakleszczenia oparte na blokowaniu, inne niż limit czasu, można uogólnić tak, aby uwzględniały również lokalne zatwierdzanie i bezpośrednie blokowanie głosowania, oprócz blokowania dostępu do danych. Możliwym kompromisem w takich mechanizmach jest skuteczne wykrywanie i łamanie najczęstszych i stosunkowo prostych w obsłudze globalnych cykli o długości 2 oraz wykorzystywanie limitu czasu dla niewykrytych, znacznie rzadszych, dłuższych cykli.

Egzekwowanie CO lokalnie

Porządkowanie zobowiązań może być egzekwowane lokalnie (w pojedynczej bazie danych) przez dedykowany algorytm CO lub dowolny algorytm/protokół, który zapewnia dowolny specjalny przypadek CO. Ważny taki protokół, szeroko stosowany w systemach baz danych, który generuje harmonogram CO, to silny, ścisły protokół blokowania dwufazowego (SS2PL: „zwolnij blokady transakcji dopiero po zatwierdzeniu lub przerwaniu transakcji”; patrz poniżej). SS2PL jest właściwym podzbiorem przecięcia 2PL i ścisłości.

Ogólny lokalny algorytm CO

Ogólny lokalny algorytm CO ( Raz 1992 ; Algorithm 4.1) to algorytm niezależny od szczegółów implementacji, który dokładnie wymusza właściwość CO. Nie blokuje dostępu do danych (nonblocking) i polega na przerwaniu określonego zestawu transakcji (tylko w razie potrzeby) po zatwierdzeniu transakcji. Przerywa (jednoznacznie określony w dowolnym momencie) minimalny zestaw innych niezdecydowanych (ani zatwierdzonych, ani przerwanych) transakcji, które są uruchamiane lokalnie i mogą spowodować naruszenie serializowalności w przyszłości (może później generować cykle zatwierdzonych transakcji na grafie konfliktu; jest to zestaw ABORT zatwierdzonej transakcji T; po zatwierdzeniu T żadna transakcja w ABORT w czasie zatwierdzenia nie może zostać zatwierdzona, a wszystkie z nich są skazane na przerwanie). Zbiór ten składa się ze wszystkich transakcji niezdecydowanych, których krawędzie na grafie konfliktów są skierowane do transakcji zatwierdzonej. Rozmiar tego zestawu nie może się zwiększać, gdy transakcja oczekuje na zatwierdzenie (w stanie gotowości: przetwarzanie zostało zakończone) i zwykle zmniejsza się w czasie, gdy podejmowane są decyzje dotyczące transakcji. Tak więc, o ile nie w czasie rzeczywistym , aby zakończyć tę transakcję, preferowane jest zaczekanie z zatwierdzeniem tej transakcji i pozwolenie temu zestawowi na zmniejszenie rozmiaru. Jeśli inny mechanizm serializowalności istnieje lokalnie (co eliminuje cykle w lokalnym grafie konfliktów) lub jeśli nie istnieje żaden cykl obejmujący tę transakcję, zbiór ostatecznie będzie pusty i nie będzie potrzebne przerwanie elementu zestawu. W przeciwnym razie zestaw ustabilizuje się z transakcjami w lokalnych cyklach, a przerwanie elementów zestawu będzie musiało nastąpić, aby przerwać cykle. Ponieważ w przypadku konfliktów CO generują blokowanie przy zatwierdzaniu, lokalne cykle w grafie konfliktów rozszerzeń (patrz wyżej) wskazują lokalne zakleszczenia w zatwierdzaniu i można zastosować techniki rozwiązywania zakleszczeń, takie jak w SS2PL (np. Graf limitu czasu i oczekiwania ) . Cykl lokalny na rozszerzonym grafie konfliktu z co najmniej jednym niezmaterializowanym konfliktem odzwierciedla impas oparty na blokowaniu. Powyższy algorytm lokalny, zastosowany do lokalnego rozszerzonego wykresu konfliktów, a nie do zwykłego lokalnego wykresu konfliktów, obejmuje ogólny ulepszony lokalny algorytm CO , mechanizm eliminacji pojedynczego lokalnego cyklu, zarówno w celu zagwarantowania lokalnej serializacji, jak i obsługi lokalnych zakleszczeń opartych na blokowaniu. Praktycznie zawsze wykorzystywany jest dodatkowy mechanizm kontroli współbieżności, nawet wyłącznie w celu wymuszenia możliwości odzyskania danych. Ogólny algorytm CO nie wpływa na lokalną strategię planowania dostępu do danych, gdy działa razem z jakimkolwiek innym lokalnym mechanizmem kontroli współbieżności. Wpływa tylko na kolejność zatwierdzania iz tego powodu nie musi przerywać większej liczby transakcji niż te, które są potrzebne do przerwania naruszenia możliwości serializacji przez dowolny połączony mechanizm kontroli współbieżności lokalnej. Co najwyżej efektem netto CO może być opóźnienie zdarzeń zatwierdzenia (lub głosowania w środowisku rozproszonym), aby zastosować się do wymaganego polecenia zatwierdzenia (ale nie większe opóźnienie niż jego specjalne przypadki, na przykład SS2PL, i średnio znacznie mniej).

Kończy się następujące twierdzenie:

• Twierdzenie o ogólnym lokalnym algorytmie CO

Działając samodzielnie lub razem z dowolnym mechanizmem kontroli współbieżności w systemie bazy danych, wówczas

1. Ogólny algorytm lokalnego CO gwarantuje (lokalny) CO (harmonogram zgodny z CO).
2. Ulepszony lokalny algorytm CO gwarantuje zarówno (lokalne) CO, jak i (lokalne) rozwiązanie zakleszczenia oparte na blokowaniu. I (gdy nie jest używany limit czasu i nie są stosowane żadne ograniczenia dotyczące realizacji transakcji w czasie rzeczywistym ) żaden algorytm nie przerywa większej liczby transakcji niż wymagane minimum (które jest określone przez planowanie operacji transakcji poza zakresem algorytmów).

Przykład: Programowanie współbieżne i pamięć transakcyjna

Zobacz także Programowanie współbieżne i Pamięć transakcyjna.

Wraz z rozprzestrzenianiem się procesorów wielordzeniowych, warianty ogólnego lokalnego algorytmu CO były również coraz częściej wykorzystywane w programowaniu współbieżnym, pamięci transakcyjnej , a zwłaszcza w pamięci transakcyjnej oprogramowania, aby optymistycznie osiągnąć serializowalność przez „kolejność zatwierdzania” (np. Ramadan i in. 2009, Zhang i wsp. 2006, von Parun i wsp. 2007). Opublikowano już wiele powiązanych artykułów i patentów wykorzystujących CO.

Uwagi dotyczące implementacji: Koordynator zleceń zobowiązań (COCO)

Zakłada się system bazodanowy w środowisku wielobazowym. Z punktu widzenia architektury oprogramowania , komponent CO, który lokalnie implementuje ogólny algorytm CO, Commitment Order Coordinator (COCO), może być zaprojektowany bezpośrednio jako pośrednik między (pojedynczym) systemem baz danych a komponentem atomowego protokołu zobowiązań ( Raz 1991b) . ). Jednak COCO jest zazwyczaj integralną częścią systemu bazy danych. Funkcje COCO to głosowanie za zatwierdzeniem gotowych transakcji globalnych (przetwarzanie zostało zakończone) zgodnie z lokalnym poleceniem zatwierdzenia, głosowanie za przerwaniem transakcji dla których system bazy danych zainicjował przerwanie (system bazy danych może zainicjować przerwanie dla dowolnej transakcji , z wielu powodów) oraz przekazać decyzję o zobowiązaniu atomowym do systemu bazy danych. W przypadku transakcji lokalnych (kiedy można je zidentyfikować) głosowanie nie jest potrzebne. W celu określenia kolejności zobowiązań COCO utrzymuje zaktualizowaną reprezentację lokalnego wykresu konfliktów (lub lokalnego rozszerzonego wykresu konfliktów do przechwytywania również zakleszczeń blokujących) niezdecydowanych (ani zatwierdzonych, ani przerwanych) transakcji jako strukturę danych (np. wykorzystując mechanizmy podobne do blokowanie w celu przechwytywania konfliktów, ale bez blokowania dostępu do danych). Komponent COCO posiada interfejs ze swoim systemem bazodanowym do otrzymywania powiadomień „konflikt”, „gotowy” (przetwarzanie zakończone; gotowość do głosowania nad transakcją globalną lub zatwierdzenia lokalnej) oraz „przerwania” z systemu bazodanowego. Łączy się również z protokołem zobowiązań atomowych w celu głosowania i otrzymywania decyzji protokołu zobowiązań atomowych dotyczących każdej globalnej transakcji. Decyzje dostarczane są z COCO do systemu bazodanowego poprzez ich interfejs, a także lokalne powiadomienia o zatwierdzeniach transakcji, w odpowiedniej kolejności zatwierdzeń. COCO, w tym jego interfejsy, można ulepszyć, jeśli implementuje inny wariant CO (patrz poniżej) lub odgrywa rolę w mechanizmie kontroli współbieżności bazy danych poza głosowaniem w zaangażowaniu atomowym.

COCO gwarantuje również CO lokalnie w pojedynczym, odizolowanym systemie bazy danych bez interfejsu z atomowym protokołem zobowiązań.

CO jest warunkiem koniecznym globalnej serializacji w autonomicznych systemach baz danych.

Załóżmy, że bazy danych uczestniczące w transakcjach rozproszonych (tj. transakcjach obejmujących więcej niż pojedynczą bazę danych) nie używają żadnych współdzielonych informacji kontrolnych współbieżności i używają niezmodyfikowanych komunikatów protokołów zobowiązań atomowych (w celu osiągnięcia atomowości). W takim przypadku utrzymanie (lokalnego) porządku zobowiązań lub jednego z jego uogólniających wariantów (patrz poniżej) jest warunkiem koniecznym do zagwarantowania globalnej serializacji (technikę dowodową można znaleźć w ( Raz 1992 ), a inną metodę dowodową w ( Raz 1993a )); jest to również warunek wystarczający . Jest to fakt matematyczny wywodzący się z definicji serializowalności i transakcji . Oznacza to, że jeśli nie jest to zgodne z CO, nie można zagwarantować globalnej serializacji pod tym warunkiem (warunek braku współdzielenia informacji kontroli lokalnej współbieżności między bazami danych poza komunikatami protokołu zatwierdzenia atomowego). Zaangażowanie atomowe jest minimalnym wymogiem dla transakcji rozproszonej, ponieważ jest zawsze potrzebne, co wynika z definicji transakcji.

( Raz 1992 ) definiuje autonomię i niezależność bazy danych jako zgodność z tym wymogiem bez korzystania z dodatkowej wiedzy lokalnej:

• Definicja: (oparty na kontroli współbieżności) autonomiczny system bazy danych

System bazy danych jest Autonomiczny , jeśli nie udostępnia żadnych informacji dotyczących kontroli współbieżności poza niezmodyfikowanymi komunikatami protokołów zobowiązań atomowych z żadnym innym podmiotem. Ponadto, nie wykorzystuje do kontroli współbieżności żadnych dodatkowych informacji lokalnych poza konfliktami (ostatnie zdanie nie pojawia się wprost, ale jest raczej sugerowane przez dalszą dyskusję w Raz 1992 ).

Korzystając z tej definicji, stwierdza się, co następuje:

• Twierdzenie CO i globalna serializowalność

1. Zgodność CO każdego autonomicznego systemu bazodanowego (lub obiektu transakcyjnego) w środowisku wielobazowym jest warunkiem koniecznym do zagwarantowania Globalnej serializowalności (bez CO Globalna serializowalność może zostać naruszona).
2. Zgodność CO z każdym systemem bazodanowym jest warunkiem wystarczającym do zagwarantowania Globalnej serializowalności.

Jednak powyższa definicja autonomii implikuje na przykład, że transakcje są planowane w taki sposób, że transakcje lokalne (ograniczone do jednej bazy danych) nie mogą być zidentyfikowane jako takie przez autonomiczny system baz danych. Jest to realistyczne w przypadku niektórych obiektów transakcyjnych, ale zbyt restrykcyjne i mniej realistyczne w przypadku systemów baz danych ogólnego przeznaczenia. Jeśli autonomia jest powiększona o możliwość identyfikowania lokalnych transakcji, wówczas zgodność z bardziej ogólną właściwością, zamawianiem rozszerzonych zobowiązań (ECO, patrz poniżej), sprawia, że ​​ECO jest warunkiem koniecznym.

Dopiero w ( Raz 2009 ) pojęcie uogólnionej autonomii oddaje zamierzone pojęcie autonomii:

• Definicja: uogólniona autonomia

System bazy danych ma właściwość Uogólniona autonomia , jeśli nie współdzieli z żadnym innym systemem baz danych żadnych lokalnych informacji współbieżnych poza (niezmodyfikowanymi) komunikatami protokołu zatwierdzania atomowego (jednakże można wykorzystać dowolne informacje lokalne).

Ta definicja jest prawdopodobnie najszerszą możliwą definicją w kontekście kontroli współbieżności bazy danych i sprawia, że ​​CO wraz z dowolnym (przydatnym: brak dystrybucji informacji o kontroli współbieżności) uogólniającymi wariantami (porządkowanie głosów (VO); patrz warianty CO poniżej) warunek konieczny Globalnej serializowalności (tj. połączenie CO i jego uogólniających wariantów jest niezbędnym zbiorem VO, który może również zawierać nowe, nieznane, użyteczne uogólniające warianty).

Streszczenie

Rozwiązanie (technika) porządkowania zobowiązań (CO) dla globalnej serializacji można podsumować w następujący sposób:

Jeśli każda baza danych (lub jakikolwiek inny obiekt transakcyjny ) w środowisku wielobazowym jest zgodna z CO, tj. organizuje swoje lokalne zobowiązania transakcyjne i swoje głosy w transakcjach (globalnych, rozproszonych) zgodnie z atomowym protokołem zobowiązań zgodnie z lokalnymi (do bazy danych) częściowy porządek indukowany przez lokalny graf konfliktów (graf serializacji) dla odpowiednich transakcji, wówczas gwarantowana jest Globalna CO i Globalna serializowalność . Zgodność CO bazy danych można skutecznie osiągnąć za pomocą dowolnego lokalnego mechanizmu kontroli współbieżności opartego na serializacji konfliktów , nie wpływając ani na proces wykonywania transakcji, ani na planowanie, ani na jej przerwanie. Nie jest również naruszana autonomia bazy danych. Jedynym niewielkim kosztem narzutu jest wykrywanie konfliktów (np. z blokowaniem, ale bez blokowania dostępu do danych, jeśli nie zostało to już wykryte w innych celach) oraz porządkowanie głosów i zatwierdzanie lokalnych transakcji zgodnie z konfliktami.

Zaplanuj zawieranie klas: Strzałka od klasy A do klasy B wskazuje, że klasa A ściśle zawiera B; brak ukierunkowanej ścieżki między klasami oznacza, że ​​klasy są nieporównywalne. Właściwość jest z natury blokująca , jeśli można ją wymusić tylko poprzez zablokowanie operacji dostępu do danych transakcji do czasu wystąpienia określonych zdarzeń w innych transakcjach. ( Raz 1992 )

W przypadku niekompatybilnych porządków częściowych dwóch lub więcej baz danych (żaden globalny porządek częściowy nie może osadzić razem odpowiednich lokalnych rzędów częściowych), generowany jest globalny cykl (obejmujący dwie lub więcej baz danych) na globalnym grafie konfliktów. To, wraz z CO, skutkuje cyklem zablokowanych głosów. bazie impasu głosowania (jednak dozwolone jednoczesne głosowanie w każdej danych, zazwyczaj dla prawie wszystkich zaległych głosów, jest nadal wykonywane). W tym przypadku protokół zobowiązania atomowego nie zbiera wszystkich głosów potrzebnych do zablokowania transakcji w tym globalnym cyklu. W konsekwencji protokół anuluje niektóre transakcje z brakującym głosem. To przerywa globalny cykl, impas w głosowaniu zostaje rozwiązany, a związane z nim zablokowane głosy mogą zostać wykonane. Przerwanie globalnego cyklu na grafie konfliktów globalnych zapewnia utrzymanie globalnego CO i globalnej serializacji. Tak więc w przypadku niezgodnych lokalnych (częściowych) zleceń zobowiązań nie jest potrzebne żadne działanie, ponieważ atomowy protokół zobowiązań rozwiązuje je automatycznie, przerywając transakcję, która jest przyczyną niezgodności. Ponadto globalne impasy spowodowane blokowaniem (globalne cykle na rozszerzonym wykresie konfliktów z co najmniej jedną blokadą dostępu do danych) skutkują impasami w głosowaniu i są rozwiązywane automatycznie przez ten sam mechanizm.

Lokalny CO jest warunkiem koniecznym do zagwarantowania globalnej serializacji , jeśli zaangażowane bazy danych nie współdzielą żadnych informacji kontroli współbieżności poza (niezmodyfikowanymi) atomowymi komunikatami protokołu zobowiązań, tj. jeśli bazy danych są autonomiczne w kontekście kontroli współbieżności. Oznacza to, że każde rozwiązanie globalnej serializacji dla autonomicznych baz danych musi być zgodne z CO. W przeciwnym razie globalna serializowalność może zostać naruszona (a zatem prawdopodobnie zostanie naruszona bardzo szybko w środowisku o wysokiej wydajności).

Rozwiązanie CO skaluje się wraz z rozmiarem sieci i liczbą baz danych bez spadku wydajności, gdy wykorzystuje wspólną rozproszoną architekturę zobowiązań atomowych .

Rozproszona serializowalność i CO

Rozproszony CO

Cechą wyróżniającą rozwiązanie CO dla rozproszonej serializowalności spośród innych technik jest fakt, że nie wymaga ono rozpowszechniania informacji o konfliktach (np. lokalnych relacji pierwszeństwa, blokad, znaczników czasu, biletów ), co czyni je wyjątkowo skutecznym. Zamiast tego wykorzystuje (niezmodyfikowane) atomowe komunikaty protokołu zobowiązań (które są już używane).

Typowym sposobem na osiągnięcie rozproszonej serializacji w systemie (rozproszonym) jest użycie rozproszonego menedżera blokad (DLM). DLM, które przekazują informacje o blokadzie (konfliktach niezmaterializowanych) w środowisku rozproszonym, zwykle cierpią z powodu opóźnień komputera i komunikacji , co zmniejsza wydajność systemu. CO pozwala osiągnąć rozproszoną serializowalność w bardzo ogólnych warunkach, bez rozproszonego menedżera blokad, wykazując korzyści już zbadane powyżej dla środowisk z wieloma bazami danych; w szczególności: niezawodność, wysoka wydajność, skalowalność, możliwość wykorzystania optymistycznej kontroli współbieżności w razie potrzeby, brak komunikacji związanej z informacjami o konfliktach w sieci (co powodowało narzut i opóźnienia) oraz automatyczne rozwiązywanie rozproszonych zakleszczeń.

Wszystkie rozproszone systemy transakcyjne polegają na jakimś niepodzielnym protokole zobowiązań w celu koordynowania niepodzielności (zatwierdzania lub przerywania) między procesami w rozproszonej transakcji . Ponadto do typowych danych możliwych do odzyskania (tj. danych znajdujących się pod kontrolą transakcji, np. danych bazy danych; nie mylić z właściwością odtwarzania harmonogramu) można uzyskać bezpośredni dostęp za pomocą pojedynczego komponentu menedżera danych transakcyjnych (nazywanego również menedżerem zasobów ). który obsługuje lokalne subtransakcje (część transakcji rozproszonej w jednym miejscu, np. węźle sieci), nawet jeśli dostęp do tych danych jest pośredni przez inne podmioty w systemie rozproszonym podczas transakcji (tj. dostęp pośredni wymaga bezpośredniego dostępu za pośrednictwem lokalna transakcja podrzędna). W związku z tym możliwe do odzyskania dane w rozproszonym systemie transakcyjnym są zazwyczaj dzielone między menedżerów danych transakcyjnych. W takim systemie tacy menedżerowie danych transakcyjnych zazwyczaj obejmują uczestników atomowego protokołu zobowiązań systemu. Jeśli każdy uczestnik przestrzega CO (np. używając SS2PL, COCO lub ich kombinacji; patrz wyżej), to cały system rozproszony zapewnia CO (zgodnie z powyższymi twierdzeniami; każdego uczestnika można uważać za oddzielny obiekt transakcyjny), a tym samym (rozproszona) serializowalność. Co więcej: Gdy CO jest używany razem z atomowym protokołem zobowiązań, również rozproszone zakleszczenia (tj. zakleszczenia obejmujące dwóch lub więcej menedżerów danych) spowodowane przez blokowanie dostępu do danych są rozwiązywane automatycznie. W ten sposób dochodzi do następującego wniosku:

• Twierdzenie o rozproszonej serializacji opartej na CO

Niech rozproszony system transakcyjny (np. rozproszony system baz danych ) zawiera transakcyjnych menedżerów danych (zwanych także menedżerami zasobów ), którzy zarządzają wszystkimi możliwymi do odzyskania danymi systemu . Administratorzy danych spełniają trzy warunki:

1. Podział danych: Dane możliwe do odzyskania są podzielone między menedżerów danych, tj. każdy możliwy do odzyskania element danych (element danych) jest kontrolowany przez pojedynczego menedżera danych (np. tak jak w architekturze Shared Nothing ; nawet kopie tych samych danych w ramach różnych menedżerów danych są fizycznie odrębne, replikowane ).
2. Uczestnicy atomowego protokołu zobowiązań: Ci menedżerowie danych są uczestnikami atomowego protokołu zobowiązań systemu w celu koordynowania niepodzielności transakcji rozproszonych.
3. Zgodność z CO: każdy taki menedżer danych jest zgodny z CO (lub zgodny z niektórymi wariantami CO; patrz poniżej).

Następnie

1. Cały system rozproszony gwarantuje (rozproszone CO i) serializowalność , oraz
2. Rozproszone zakleszczenia związane z dostępem do danych (zakleszczenia obejmujące co najmniej dwóch menedżerów danych z co najmniej jednym niezmaterializowanym konfliktem) są rozwiązywane automatycznie.

Ponadto: Zgodność zarządców danych z CO jest warunkiem koniecznym (rozproszonej) serializacji w systemie spełniającym warunki 1, 2 powyżej, gdy zarządcy danych są autonomiczni , tj. nie współdzielą informacji kontrolnych współbieżności poza niezmodyfikowanymi komunikatami protokołu zobowiązań atomowych.

To twierdzenie oznacza również, że gdy SS2PL (lub dowolny inny wariant CO) jest używany lokalnie w każdym menedżerze danych transakcyjnych, a każdy menedżer danych ma wyłączną kontrolę nad swoimi danymi, nie jest potrzebny żaden rozproszony menedżer blokad (który jest często wykorzystywany do wymuszenia rozproszonego SS2PL). dla rozproszonego SS2PL i możliwości serializacji. Jest to istotne dla szerokiej gamy rozproszonych aplikacji transakcyjnych, które można łatwo zaprojektować tak, aby spełniały warunki twierdzenia.

Rozproszony optymistyczny CO (DOCO)

W celu wdrożenia Distributed Optimistic CO (DOCO), ogólny lokalny algorytm CO jest wykorzystywany we wszystkich uczestnikach protokołu atomowego zaangażowania w systemie bez blokowania dostępu do danych, a tym samym bez lokalnych zakleszczeń. Poprzednie twierdzenie ma następujący wniosek:

• Twierdzenie o rozłożonym optymistycznym CO (DOCO).

Jeśli stosuje się DOCO, to:

1. Nie występują lokalne zakleszczenia i
2. Globalne (głosowanie) zakleszczenia są rozwiązywane automatycznie (i wszystkie są związane z serializacją (z konfliktami nieblokującymi), a nie z blokowaniem (z konfliktami blokującymi i prawdopodobnie także nieblokującymi)).

W związku z tym nie jest wymagana obsługa zakleszczenia.

Przykłady

Rozproszony SS2PL

Rozproszony system bazy danych, który wykorzystuje SS2PL, znajduje się w dwóch zdalnych węzłach, A i B. System bazy danych ma dwóch menedżerów danych transakcyjnych ( menedżerów zasobów ), po jednym w każdym węźle, a dane bazy danych są podzielone między te dwa menedżery danych w sposób, który każdy ma wyłączną kontrolę nad własną (lokalną dla węzła) częścią danych: każdy obsługuje własne dane i blokuje bez żadnej wiedzy o drugim menedżerze. Dla każdej rozproszonej transakcji tacy menedżerowie danych muszą wykonać dostępny atomowy protokół zobowiązań.

Dwie rozproszone transakcje, ${\ displaystyle T_ {1}}$ i ${\ displaystyle T_ {2}}$ działają jednocześnie i obie uzyskują dostęp do danych x i y. x znajduje się pod wyłączną kontrolą zarządcy danych na A (menedżer B nie ma dostępu do x), a y na B.

${\ Displaystyle T_ {1}}$ czyta x na A i zapisuje y na B, tj. ${\ Displaystyle T_ {1} = R _ {\ tekst {1A}} (x)}$${\ Displaystyle W _ {\ tekst {1B}} (y)}$ przy użyciu notacji wspólnej dla kontroli współbieżności.

${\ Displaystyle T_ {2}}$ czyta y na B i zapisuje x na A, tj. ${\ Displaystyle T_ {2} = R _ {\ tekst {2B}} (y)}$${\ Displaystyle W _ {\ tekst {2A}} (x)}$

Odpowiednie lokalne transakcje podrzędne na A i B (części ${\ displaystyle T_ {1}}$ i ${\ displaystyle T_ {2}}$ na każdym z węzłów) są następujące: T 1 {\ displaystyle T_ {1}}

Lokalne transakcje podrzędne

Węzeł Transakcja	A	B
${\ Displaystyle T_ {1}}$	${\ Displaystyle T _ {\ tekst {1A}} = R _ {\ tekst {1A}} (x)}$	${\ Displaystyle T _ {\ tekst {1B}} = W _ {\ tekst {1B}} (y)}$
${\ Displaystyle T_ {2}}$	${\ Displaystyle T _ {\ tekst {2A}} = W _ {\ tekst {2A}} (x)}$	${\ Displaystyle T _ {\ tekst {2B}} = R _ {\ tekst {2B}} (y)}$

Harmonogram systemu bazy danych w określonym momencie jest następujący:

${\ Displaystyle R _ {\ tekst {1A}} (x)}$${\ Displaystyle R _ {\ tekst {2B}} (y)}$

(również ${\ Displaystyle R _ {\ tekst {2B}} (y)}$${\ Displaystyle R _ {\ tekst {1A}} (x)}$ jest możliwe)

${\ displaystyle T_ {1}}$ utrzymuje blokadę odczytu na x i ${\ displaystyle T_ {2}}$ blokuje odczyt na y. ${\ Displaystyle W _ {\ tekst {1B}} (y)}$$\ tekst {2A}} (x)}$ { { są blokowane przez reguły kompatybilności blokad SS2PL i nie można go wykonać. Jest to rozproszony impas, który jest również impasem głosowania (patrz poniżej) z rozproszonym (globalnym) cyklem o długości 2 (liczba krawędzi, konfliktów; 2 to najczęstsza długość). Lokalne transakcje podrzędne znajdują się w następujących stanach:

${\ Displaystyle T _ {\ tekst {1A}}}$ jest gotowy (wykonanie zostało zakończone) i głosowano (w zaangażowaniu atomowym)

${\ Displaystyle T _ {\ tekst {1B}}}$ działa i jest ; głosowanie w tej sprawie nie może się odbyć)

zablokowany (nie- zmaterializowana

$displaystyle T_ {\ tekst {2A}}}$ jest uruchomione i zablokowane (nie -zmaterializowany konflikt; brak głosu).

jest gotowe i głosowane ${\$

${\ displaystyle T_ {2}}$ , ostatecznie przerwie niektóre transakcje z brakującymi głosami przed przekroczeniem limitu czasu , albo T $\ displaystyle T_ {1}}$ (lub jedno i drugie, jeśli limity czasu są bardzo bliskie). To rozwiąże globalny impas. Pozostała transakcja zostanie zakończona, zostanie poddana pod głosowanie i zatwierdzona. Przerwana transakcja jest natychmiast restartowana i ponownie wykonywana.

Uwagi

1. $uruchomiona$ przykład x można uzyskać bezpośrednio z B. Jeśli transakcja jest na B jednocześnie z ${\ displaystyle T_ {1}}$$zapisuje$ bezpośrednio x, a następnie bez rozproszonego menedżera blokad blokada odczytu dla x utrzymywana przez ${\ displaystyle T_ {1}} A nie jest widoczne na$ na $zmaterializowanego$ i nie może blokować zapisu (ani sygnalizować konfliktu dla nieblokującego wariantu CO; patrz poniżej) W ten sposób serializowalność może zostać naruszona.
2. Ze względu na partycję danych do x nie można uzyskać bezpośredniego dostępu z B. Jednak funkcjonalność nie jest ograniczona, a transakcja działająca na B nadal może wysyłać żądania zapisu lub odczytu x (nieczęste). To żądanie jest przekazywane do lokalnej transakcji podrzędnej transakcji w A (która jest generowana, jeśli jeszcze nie istnieje), która wysyła to żądanie do lokalnego menedżera danych w A.

Wariacje

W powyższym scenariuszu oba konflikty są niematerialne , a globalny impas w głosowaniu jest odzwierciedlony jako cykl na globalnym wykresie oczekiwania (ale nie na globalnym wykresie konfliktu ; patrz Dokładna charakterystyka impasu w głosowaniu według globalnych cykli powyżej) . Jednak system bazy danych może wykorzystywać dowolny wariant CO z dokładnie takimi samymi konfliktami i sytuacją impasu w głosowaniu oraz z tą samą rozdzielczością. Konflikty mogą być zmaterializowane lub niezmaterializowane , w zależności od zastosowanego wariantu CO. Na przykład, jeśli SCO (poniżej) jest używany przez system rozproszonej bazy danych zamiast SS2PL, wówczas dwa konflikty w przykładzie są materializowane , wszystkie lokalne transakcje podrzędne są w stanie gotowości , a w dwóch transakcjach występuje blokowanie głosów, jedna na każdy węzeł, ze względu na regułę głosowania CO stosowaną niezależnie zarówno na A, jak i B: z powodu konfliktów ${\ Displaystyle T _ {\ tekst {2A}} = W _ {\ tekst {2A}} (x )}$ nie jest głosowane przed zakończeniem ${\ Displaystyle T _ {\ tekst {1A}} = R _ {\ tekst {1A}} (x)}$ i ${\ Displaystyle T _ {\ tekst {1B}} = W _ {\ tekst {1B}} (y)}$ nie jest głosowane przed ${\ Displaystyle T _ {\ tekst {2B}} = R_ {\text{2B}}(y)}$ kończy się, co oznacza impas w głosowaniu. Teraz wykres konfliktów ma globalny cykl (wszystkie konflikty się materializują) i ponownie jest rozwiązywany przez atomowy protokół zobowiązań, a rozproszona serializowalność jest zachowana. Jest to mało prawdopodobne w przypadku rozproszonego systemu baz danych, ale w zasadzie możliwe (i występuje w wielu bazach danych), A może wykorzystywać SS2PL, podczas gdy B stosuje SCO. W tym przypadku globalny cykl nie znajduje się ani na grafie oczekiwania, ani na grafie serializacji, ale wciąż na rozszerzonym grafie konfliktu (połączenie tych dwóch). Różne kombinacje podsumowano w poniższej tabeli:

Sytuacje impasu w głosowaniu

Sprawa	Węzeł A	Węzeł B	Możliwy harmonogram	Zmaterializowane konflikty w cyklu	Konflikty niezmaterializowane _	${\ Displaystyle T _ {\ tekst {1A}} = R _ {\ tekst {1A}} (x)}$	${\ Displaystyle T _ {\ tekst {1B}} = W _ {\ tekst {1B}} (y)}$	${\ Displaystyle T _ {\ tekst {2A}} = W _ {\ tekst {2A}} (x)}$	${\ Displaystyle T _ {\ tekst {2B}} = R _ {\ tekst {2B}} (y)}$
1	SS2PL	SS2PL	${\ Displaystyle R _ {\ tekst {1A}} (x) R _ {\ tekst {2B}} (y)}$	0	2	Gotowe Głosowanie	Bieganie (zablokowane)	Bieganie (zablokowane)	Gotowe Głosowanie
2	SS2PL	SCO	${\ Displaystyle R _ {\ tekst {1A}} (x) R _ {\ tekst {2B}} (y) W _ {\ tekst {1B}} (y )}$	1	1	Gotowe Głosowanie	Gotowy głos zablokowany	Bieganie (zablokowane)	Gotowe Głosowanie
3	SCO	SS2PL	${\ Displaystyle R _ {\ tekst {1A}} (x) R _ {\ tekst {2B}} (y) W _ {\ tekst {2A}} (x )}$	1	1	Gotowe Głosowanie	Bieganie (zablokowane)	Gotowy głos zablokowany	Gotowe Głosowanie
4	SCO	SCO	${\ Displaystyle R _ {\ tekst {1A}} (x) R _ {\ tekst {2B}} (y) W _ {\ tekst { 1B}}(y)W_{\text{2A}}(x)}$	2	0	Gotowe Głosowanie	Gotowy głos zablokowany	Gotowy głos zablokowany	Gotowe Głosowanie

Uwagi:

1. Konflikty, a tym samym cykle na rozszerzonym grafie konfliktów, są określane tylko przez transakcje i ich wstępne planowanie, niezależnie od zastosowanej kontroli współbieżności. W przypadku dowolnego wariantu CO każdy globalny cykl (tj. obejmujący dwie lub więcej baz danych) powoduje impas w głosowaniu . Różne warianty CO mogą różnić się w zależności od tego, czy dany konflikt jest zmaterializowany , czy nie .
2. Możliwe są pewne ograniczone zmiany kolejności operacji w powyższych harmonogramach, ograniczone przez zamówienia wewnątrz transakcji, ale takie zmiany nie zmieniają reszty tabeli.
3. Jak wspomniano powyżej, tylko przypadek 4 opisuje cykl w (zwykłym) grafie konfliktu, który wpływa na serializowalność. Przypadki 1-3 opisują cykle globalnych zakleszczeń opartych na blokowaniu (istnieje co najmniej jedno blokowanie). Wszystkie typy cykli są równie rozwiązywane przez atomowy protokół zobowiązań. Przypadek 1 to powszechny Distributed SS2PL, używany od lat 80-tych. Jednak żaden artykuł badawczy, z wyjątkiem artykułów CO, nie zauważył tego automatycznego blokowania rozwiązania globalnego impasu od 2009 r. Takie globalne impasy zwykle były rozwiązywane przez dedykowane mechanizmy.
4. Przypadek 4 powyżej jest również przykładem typowego impasu w głosowaniu, gdy używany jest rozproszony optymistyczny CO (DOCO) (tj. przypadek 4 pozostaje niezmieniony, gdy optymistyczny CO (OCO; patrz poniżej) zastępuje SCO zarówno na A, jak i B): Brak danych- występuje blokowanie dostępu i istnieją tylko zmaterializowane konflikty.

Hipotetyczne środowisko wielowątkowego rdzenia (MuSiC).

Komentarz: Chociaż powyższe przykłady opisują rzeczywiste, zalecane wykorzystanie CO, ten przykład jest hipotetyczny i służy wyłącznie do celów demonstracyjnych.

Niektóre eksperymentalne bazy danych rezydujące w pamięci rozproszonej opowiadają się za środowiskami transakcyjnymi z wieloma jednowątkowymi rdzeniami (MuSiC). „Jednowątkowy” odnosi się tylko do wątków transakcji i do seryjnego wykonywania transakcji. Celem jest możliwy wzrost wydajności o rzędy wielkości (np. H-Store i VoltDB ) w stosunku do konwencjonalnej realizacji transakcji w wielu wątkach na tym samym rdzeniu. W tym, co opisano poniżej, MuSiC jest niezależny od sposobu rozmieszczenia rdzeni. Mogą znajdować się w jednym układzie scalonym (układzie scalonym) lub w wielu układach scalonych, prawdopodobnie rozmieszczonych geograficznie w wielu komputerach. W takim środowisku, jeśli możliwe do odzyskania (transakcyjne) dane są podzielone na wątki (rdzenie) i są zaimplementowane w konwencjonalny sposób dla rozproszonego CO, jak opisano w poprzednich sekcjach, DOCO i Strictness istnieją automatycznie. Istnieją jednak wady tej prostej implementacji takiego środowiska, a jego praktyczność jako rozwiązania ogólnego przeznaczenia jest wątpliwa. Z drugiej strony ogromny wzrost wydajności można osiągnąć w aplikacjach, które w większości sytuacji mogą ominąć te wady.

Komentarz: Opisana tutaj prosta implementacja MuSiC (która w razie potrzeby wykorzystuje na przykład, jak zwykle w rozproszonym CO, blokowanie głosowania (i wątków transakcji) w protokole zobowiązań atomowych) służy wyłącznie do demonstracji i nie ma związku z implementacją w H- Sklep lub inny projekt.

W środowisku MuSiC lokalne harmonogramy są szeregowe . W ten sposób zarówno lokalny optymistyczny CO (OCO; patrz poniżej), jak i globalny warunek strategii porządkowania głosowania w zakresie egzekwowania CO dla protokołu zobowiązania atomowego są spełnione automatycznie. Powoduje to zarówno zgodność rozproszonego CO (a tym samym możliwość serializacji rozproszonej), jak i automatyczne globalne (głosowanie) rozwiązywanie zakleszczeń.

Ponadto, również lokalna Ścisłość następuje automatycznie w harmonogramie szeregowym. Zgodnie z Twierdzeniem 5.2 w ( Raz 1992 ; strona 307), gdy stosowana jest strategia porządkowania głosów CO, gwarantowana jest również Globalna Rygoryzm. Należy pamiętać, że tryb szeregowy jest jedynym trybem, który pozwala jednocześnie na ścisłość i „optymistyczność” (brak blokowania dostępu do danych).

Co następuje:

• Twierdzenie MuSiC

W środowiskach MuSiC, jeśli możliwe do odzyskania (transakcyjne) dane są podzielone na rdzenie (wątki), to oba

1. OCO (i dorozumiana serializowalność , tj. DOCO i rozproszona serializowalność)
2. Ścisłość (pozwalająca na skuteczne odzyskanie; 1 i 2 implikujące Ścisłe CO - patrz SCO poniżej) i
3. (głosowanie) rozwiązanie impasu

automatycznie istnieją globalnie z nieograniczoną skalowalnością liczby używanych rdzeni.

Komentarz: Mogą jednak istnieć dwie główne wady, które wymagają specjalnego traktowania:

1. Lokalne transakcje podrzędne transakcji globalnej są blokowane do czasu zatwierdzenia, co powoduje, że odpowiednie rdzenie są bezczynne. Zmniejsza to znacznie wykorzystanie rdzenia, nawet jeśli planowanie lokalnych transakcji podrzędnych ma na celu wykonanie ich wszystkich w zbliżonym czasie, prawie razem. Można temu zaradzić, odłączając wykonanie od zatwierdzenia (z pewnym atomowym protokołem zobowiązań) dla transakcji globalnych, kosztem możliwych kaskadowych przerwań.
2. zwiększenie liczby rdzeni dla danej ilości danych możliwych do odzyskania (rozmiar bazy danych) zmniejsza średnią ilość (podzielonych na partycje) danych na rdzeń. Może to spowodować, że niektóre rdzenie będą bezczynne, a inne bardzo zajęte, w zależności od rozkładu wykorzystania danych. Również lokalna (do rdzenia) transakcja może stać się globalna (wielordzeniowa), aby dotrzeć do potrzebnych danych, z dodatkowym poniesionym narzutem. Tak więc, wraz ze wzrostem liczby rdzeni, ilość i typ danych przypisanych do każdego rdzenia powinny być zrównoważone zgodnie z wykorzystaniem danych, tak aby rdzeń nie był przeciążony i nie stał się wąskim gardłem, ani nie stał się zbyt często bezczynny i nie był w pełni wykorzystywany w obciążonym systemie. Inną kwestią do rozważenia jest umieszczenie w tej samej partycji podstawowej wszystkich danych, do których zwykle uzyskuje się dostęp w ramach tej samej transakcji (jeśli to możliwe), aby zmaksymalizować liczbę transakcji lokalnych (i zminimalizować liczbę globalnych, rozproszonych transakcji). Można to osiągnąć poprzez sporadyczne ponowne partycjonowanie danych między rdzeniami w oparciu o równoważenie obciążenia (równoważenie dostępu do danych) i wzorce wykorzystania danych przez transakcje. Innym sposobem znacznego złagodzenia tej wady jest odpowiednia fizyczna replikacja danych między niektórymi partycjami rdzenia, w taki sposób, że możliwe jest całkowite uniknięcie globalnych transakcji tylko do odczytu (w zależności od wzorców użytkowania), a zmiany replikacji są synchronizowane przez dedykowany mechanizm zatwierdzania.

Warianty CO: przypadki szczególne i uogólnienia

Klasy właściwości harmonogramu przypadków specjalnych (np. SS2PL i SCO poniżej) są ściśle zawarte w klasie CO. Klasy uogólniające (ECO i MVCO) ściśle zawierają klasę CO (tj. obejmują również harmonogramy, które nie są zgodne z CO). Warianty uogólniające gwarantują również globalną serializację bez dystrybucji informacji kontroli lokalnej współbieżności (każda baza danych ma uogólnionej autonomii : wykorzystuje tylko informacje lokalne), jednocześnie rozluźniając ograniczenia CO i wykorzystując dodatkowe (lokalne) informacje dla lepszej współbieżności i wydajności: ECO wykorzystuje wiedzę o transakcje są lokalne (tj. ograniczone do jednej bazy danych), a MVCO wykorzystuje wartości dostępności wersji danych. Podobnie jak CO, oba uogólniające warianty są nieblokujące , nie zakłócają planowania operacji żadnej transakcji i można je bezproblemowo łączyć z dowolnym odpowiednim mechanizmem kontroli współbieżności.

Termin wariant CO odnosi się ogólnie do CO, ECO, MVCO lub kombinacji każdego z nich z dowolnym odpowiednim mechanizmem lub właściwością kontroli współbieżności (w tym ECO oparte na wielu wersjach, MVECO). Żadne inne uogólniające warianty (które gwarantują globalną serializację bez lokalnej dystrybucji informacji o kontroli współbieżności) nie są znane, ale mogą zostać odkryte.

Silne ścisłe blokowanie dwufazowe (SS2PL)

Główny artykuł: Blokowanie dwufazowe

Silne ścisłe blokowanie dwufazowe (SS2PL; określane również jako rygoryzm lub rygorystyczne planowanie ) oznacza, że ​​zarówno blokada odczytu, jak i zapisu transakcji jest zwalniana dopiero po jej zakończeniu (zatwierdzeniu lub przerwaniu). Zbiór harmonogramów SS2PL jest właściwym podzbiorem zbioru harmonogramów CO. Ta właściwość jest szeroko stosowana w systemach baz danych, a ponieważ implikuje CO, bazy danych, które jej używają i uczestniczą w transakcjach globalnych, generują razem możliwy do serializacji globalny harmonogram (przy użyciu dowolnego atomowego protokołu zobowiązań, który jest potrzebny do atomowości w środowisku z wieloma bazami danych) . W tym przypadku nie jest wymagana żadna modyfikacja ani dodawanie bazy danych, aby uczestniczyć w rozwiązaniu rozproszonym CO: zestaw niezdecydowanych transakcji, które należy przerwać przed zatwierdzeniem w lokalnym ogólnym algorytmie CO, jest pusty z powodu blokad, a zatem taki algorytm jest niepotrzebny w ta sprawa. Transakcja może zostać poddana pod głosowanie przez system bazodanowy natychmiast po wejściu w stan „gotowości”, czyli zakończeniu lokalnego wykonywania swojego zadania. Jego blokady są zwalniane przez system bazy danych dopiero po podjęciu decyzji przez protokół zobowiązania atomowego, a zatem warunek w twierdzeniu Global CO wymuszającym jest utrzymywany automatycznie. Jeśli lokalny mechanizm przekroczenia limitu czasu jest używany przez system bazy danych do rozwiązywania (lokalnych) zakleszczeń SS2PL, to przerwanie zablokowanych transakcji przerywa nie tylko potencjalne lokalne cykle na globalnym grafie konfliktów (rzeczywiste cykle na rozszerzonym grafie konfliktów), ale także potencjalne globalne cykle systemu bazy danych cykli jako efekt uboczny, jeśli mechanizm przerwania protokołu zobowiązań atomowych jest stosunkowo powolny. Takie niezależne przerwania przez kilka podmiotów zazwyczaj mogą skutkować niepotrzebnymi przerwaniami dla więcej niż jednej transakcji na globalny cykl. Sytuacja wygląda inaczej w przypadku lokalnych grafach oczekiwania : nie mogą one identyfikować globalnych cykli, a atomowy protokół zobowiązań przerwie globalny cykl, jeśli wynikający z tego impas głosowania nie zostanie wcześniej rozwiązany w innej bazie danych.

Lokalny SS2PL wraz z atomowym zobowiązaniem implikującym globalną serializację można również wywnioskować bezpośrednio: Wszystkie transakcje, w tym transakcje rozproszone, są zgodne z zasadami 2PL (SS2PL). Mechanizm atomowego protokołu zobowiązań nie jest tutaj potrzebny do konsensusu w sprawie zatwierdzenia, ale raczej do punktu synchronizacji końca drugiej fazy. Prawdopodobnie z tego powodu, bez uwzględnienia mechanizmu głosowania atomowego, nie zauważono automatycznego globalnego rozwiązania impasu przed CO.

Ścisłe CO (SCO)

Konflikt odczytu i zapisu: SCO vs. SS2PL . Czas trwania transakcji T2 jest dłuższy przy SS2PL niż przy SCO. SS2PL opóźnia operację zapisu w2[x] z T2 do momentu zatwierdzenia T1, z powodu zablokowania x przez T1 po operacji odczytu r1[x]. Jeżeli potrzeba t jednostek czasu dla transakcji T2 po rozpoczęciu operacji zapisu w2[x], aby osiągnąć stan gotowości, to T2 zatwierdza t jednostek czasu po zatwierdzeniu T1. Jednak SCO nie blokuje w2[x], a T2 może zatwierdzić natychmiast po zatwierdzeniu T1. ( Raz 1991c )

Strict Commitment Ordering (SCO; ( Raz 1991c )) to przecięcie ścisłości (szczególny przypadek możliwości odzyskania) i CO i zapewnia górną granicę współbieżności harmonogramu, gdy istnieją obie właściwości. Można go zaimplementować za pomocą mechanizmów blokujących (locking) podobnych do stosowanych w popularnym SS2PL przy podobnych kosztach ogólnych.

W przeciwieństwie do SS2PL, SCO nie blokuje konfliktu odczytu i zapisu, ale prawdopodobnie blokuje zamiast tego zatwierdzenie. SCO i SS2PL mają identyczne zachowanie blokujące dla pozostałych dwóch typów konfliktów: zapis-odczyt i zapis-zapis. W rezultacie SCO ma krótsze średnie okresy blokowania i większą współbieżność (np. symulacje wydajności pojedynczej bazy danych dla najbardziej znaczącego wariantu blokad z uporządkowanym udostępnianiem , który jest identyczny z SCO, wyraźnie to pokazują, z około 100% zyskiem dla niektóre blokada obciążenia transakcji; także dla identycznych obciążeń transakcji SCO może osiągnąć wyższe stawki transakcji niż SS2PL, zanim nastąpi ). Większa współbieżność oznacza, że ​​przy danych zasobach obliczeniowych więcej transakcji jest realizowanych w jednostce czasu (wyższa szybkość transakcji, przepustowość ), a średni czas trwania transakcji jest krótszy (szybsza realizacja; patrz wykres). Przewaga SCO jest szczególnie istotna podczas rywalizacji o blokadę.

• SCO vs. SS2PL Performance Theorem

SCO zapewnia krótszy średni czas realizacji transakcji niż SS2PL, jeśli występują konflikty odczytu i zapisu. SCO i SS2PL są poza tym identyczne (mają identyczne zachowanie blokujące z konfliktami zapisu-odczytu i zapisu-zapisu).

SCO jest tak samo praktyczne jak SS2PL, ponieważ jako SS2PL zapewnia oprócz serializowalności również ścisłość, która jest powszechnie wykorzystywana jako podstawa sprawnego odzyskiwania baz danych po awarii. Mechanizm SS2PL można w prosty sposób przekształcić w mechanizm SCO, aby uzyskać lepszą wydajność, bez zmiany metod odzyskiwania. Opis implementacji SCO można znaleźć w (Perrizo i Tatarinov 1998). Zobacz także Semi-optymistyczny planista bazy danych .

SS2PL jest właściwym podzbiorem SCO (co jest kolejnym wyjaśnieniem, dlaczego SCO jest mniej ograniczające i zapewnia większą współbieżność niż SS2PL).

Optymistyczny CO (OCO)

Do implementacji optymistycznego porządkowania zobowiązań (OCO) wykorzystywany jest ogólny algorytm lokalny CO bez blokowania dostępu do danych, a tym samym bez lokalnych zakleszczeń. OCO bez ograniczeń dotyczących planowania transakcji lub operacji obejmuje całą klasę CO i nie jest szczególnym przypadkiem klasy CO, ale raczej użytecznym wariantem CO i charakterystyką mechanizmu.

Rozszerzony CO (ECO)

Ogólna charakterystyka ECO

Extended Commitment Ordering (ECO; ( Raz 1993a )) uogólnia CO. Kiedy transakcje lokalne (transakcje ograniczone do jednej bazy danych) można odróżnić od transakcji globalnych (rozproszonych) (transakcje obejmujące dwie lub więcej baz danych), kolejność zobowiązań jest stosowana do globalnych tylko transakcje. Zatem, aby harmonogram lokalny (do bazy danych) miał właściwość ECO, kolejność chronologiczna (częściowa) zdarzeń zatwierdzania tylko transakcji globalnych (nieistotnych dla transakcji lokalnych) jest zgodna z ich kolejnością na odpowiednim lokalnym grafie konfliktów.

• Definicja: rozszerzone porządkowanie zobowiązań

Niech będą dwiema zatwierdzonymi transakcjami globalnymi w $skierowana$ grafie konfliktu wykres pierwszeństwa ) istnieje ścieżka nieprzerwanych transakcji od ${\ Displaystyle T_ {1}}$ do ${\ Displaystyle T_ {2}}$ ( ${\ Displaystyle T_ {1}}$ poprzedza ${\ Displaystyle T_ {2}}$ , prawdopodobnie przechodni , pośrednio) . Harmonogram ma ${1}$ zamawiania rozszerzonych zobowiązań (ECO), jeśli dla każdych dwóch takich transakcji $}$ zostaje zatwierdzona przed zatwierdzeniem.

Rozproszony algorytm gwarantujący istnienie globalnego ECO. Jeśli chodzi o CO, algorytm potrzebuje tylko (niezmodyfikowanych) komunikatów protokołu zobowiązań atomowych. Aby zagwarantować globalną serializowalność, każda baza danych musi również gwarantować serializowalność konfliktów własnych transakcji przez dowolny (lokalny) mechanizm kontroli współbieżności.

• Twierdzenie ECO i globalna serializowalność

1. (Lokalny, co implikuje globalny) ECO wraz z serializowalnością lokalnego konfliktu jest wystarczającym warunkiem do zagwarantowania serializowalności globalnego konfliktu.
2. Gdy poza bazą danych nie są udostępniane żadne informacje kontrolne współbieżności poza atomowymi komunikatami zobowiązań (autonomia), a lokalne transakcje mogą być identyfikowane, jest to również warunek konieczny.

Zobacz dowód konieczności w ( Raz 1993a ).

Ten warunek (ECO z lokalną serializowalnością) jest słabszy niż CO i pozwala na większą współbieżność kosztem nieco bardziej skomplikowanego algorytmu lokalnego (jednak nie istnieje żadna praktyczna różnica narzutu z CO).

Kiedy zakłada się, że wszystkie transakcje są globalne (np. jeśli nie ma dostępnych informacji o transakcjach lokalnych), ECO redukuje się do CO.

Algorytm ECO

Zanim transakcja globalna zostanie zatwierdzona, ogólny algorytm lokalny (do bazy danych) ECO przerywa minimalny zestaw niezdecydowanych transakcji (ani zatwierdzonych, ani przerwanych; albo transakcje lokalne, albo globalne, które działają lokalnie), co może spowodować późniejszy cykl w wykres konfliktu. Ten zestaw przerwanych transakcji (nie unikalnych, w przeciwieństwie do CO) można zoptymalizować, jeśli każdej transakcji zostanie przypisana waga (którą można określić na podstawie ważności transakcji i zasobów obliczeniowych już zainwestowanych w bieżącą transakcję; optymalizację można przeprowadzić , na przykład przez redukcję maksymalnego przepływu w sieciach ( Raz 1993a )). Podobnie jak w przypadku CO zbiór taki jest zależny od czasu iw końcu staje się pusty. Praktycznie we wszystkich potrzebnych implementacjach transakcja powinna być zatwierdzona tylko wtedy, gdy zbiór jest pusty (i nie ma zastosowania żadna optymalizacja zbioru). Lokalny (do bazy danych) mechanizm kontroli współbieżności (oddzielony od algorytmu ECO) zapewnia eliminację lokalnych cykli (w przeciwieństwie do CO, co samo w sobie implikuje serializowalność; jednak praktycznie również dla CO wykorzystywany jest lokalny mechanizm współbieżności, przynajmniej do zapewnić możliwość odzyskania). Lokalne transakcje mogą być zawsze zatwierdzane jednocześnie (nawet jeśli istnieje relacja pierwszeństwa, w przeciwieństwie do CO). Kiedy pozwala na to lokalny porządek częściowy całej transakcji (który jest określony przez lokalny wykres konfliktu, teraz tylko z możliwymi tymczasowymi cyklami lokalnymi, ponieważ cykle są eliminowane przez lokalny mechanizm serializowalności), można głosować również na transakcje globalne, aby były zatwierdzane jednocześnie ( gdy wszystkie przejściowo (pośrednio) poprzedzające (poprzez konflikt) globalne transakcje są zatwierdzone, podczas gdy przejściowo poprzedzające transakcje lokalne mogą być w dowolnym stanie. Jest to analogiczne do silniejszego współbieżnego warunku głosowania rozproszonego algorytmu CO, w którym wszystkie przejściowo poprzedzające transakcje muszą być zaangażowany).

Warunek zagwarantowania Global ECO można podsumować podobnie do CO:

${\ displaystyle T_ {1}, T_ {2}}$ Niech będą niezdecydowanymi (ani zatwierdzonymi, ani przerwanymi) globalnymi transakcjami w systemie bazy danych, który zapewnia lokalną serializację, tak że skierowany ścieżka nieprzerwanych transakcji istnieje na lokalnym grafie konfliktu (samej bazy danych) od ${\ displaystyle T_ {1}}$ do ${\ displaystyle T_ {2}}$ . Następnie zakończenie (zatwierdzone lub przerwane) przed głosowaniem za zatwierdzeniem w każdym takim systemie bazy danych w środowisku z wieloma bazami danych jest $T_ {1}}$$displaystyle$ warunek konieczny i wystarczający do zagwarantowania Global ECO (warunek gwarantuje Global ECO, który bez niego może zostać naruszony).

• Strategia zamawiania Global ECO Enforcing Vote Twierdzenie

Globalne ECO (wszystkie globalne cykle na globalnym grafie konfliktów są eliminowane przez zaangażowanie atomowe) wraz z lokalną serializowalnością (tj. każdy system bazy danych zachowuje lokalnie serializowalność; wszystkie lokalne cykle są eliminowane) implikują globalną serializowalność (wszystkie cykle są eliminowane). Oznacza to, że jeśli każdy system baz danych w środowisku wielu baz danych zapewnia lokalną serializację (za pomocą dowolnego mechanizmu) i wymusza strategię porządkowania głosów w powyższym twierdzeniu (uogólnienie strategii porządkowania głosów CO), to gwarantowana jest globalna serializacja (nie jest potrzebny lokalny CO nie więcej).

Podobnie jak w przypadku CO, sytuację impasu w głosowaniu ECO można podsumować w następujący sposób:

• Twierdzenie ECO Voting-Deadlock Niech

środowisko z wieloma bazami danych obejmuje systemy baz danych, które wymuszają zarówno globalne ECO (wykorzystując warunek z powyższego twierdzenia), jak i lokalną serializowalność konfliktów (która eliminuje lokalne cykle na globalnym grafie konfliktów). Następnie zakleszczenie głosowania występuje wtedy i tylko wtedy, gdy globalny cykl (obejmujący dwie lub więcej baz danych) istnieje na wykresie globalnego konfliktu rozszerzonego (również blokowanie przez blokadę dostępu do danych jest reprezentowane przez krawędź). Jeśli cykl nie zostanie przerwany przez żadne przerwanie, wszystkie globalne transakcje w nim zawarte są związane z odpowiednim zakleszczeniem głosowania i ostatecznie każdy ma swój głos zablokowany (bezpośrednio lub pośrednio przez blokadę dostępu do danych). Jeśli transakcja lokalna znajduje się w cyklu, może znajdować się w dowolnym stanie nieprzerwanym (uruchomiona, gotowa lub zatwierdzona; w przeciwieństwie do CO nie jest potrzebne blokowanie zatwierdzeń lokalnych).

Podobnie jak w przypadku CO oznacza to, że również globalne impasy spowodowane blokowaniem dostępu do danych (z co najmniej jedną blokadą blokady) są impasami głosowania i są automatycznie rozwiązywane przez zobowiązanie atomowe.

Wiele wersji CO (MVCO)

Multi-version Commitment Ordering (MVCO; ( Raz 1993b )) to uogólnienie CO dla baz danych z zasobami wielu wersji . Dzięki takim zasobom transakcje tylko do odczytu nie są blokowane ani blokowane w celu uzyskania lepszej wydajności. Wykorzystanie takich zasobów jest obecnie powszechnym sposobem na zwiększenie współbieżności i wydajności poprzez generowanie nowej wersji obiektu bazy danych za każdym razem, gdy obiekt jest zapisywany, oraz umożliwienie transakcjom operacji odczytu kilku ostatnich istotnych wersji (każdego obiektu). MVCO implikuje możliwość serializacji jednej kopii (1SER lub 1SR), która jest uogólnieniem możliwości serializacji dla zasobów wielowersyjnych. Podobnie jak CO, MVCO nie blokuje i można go łączyć z dowolnym odpowiednim wielowersyjnym mechanizmem kontroli współbieżności bez zakłócania go. We wprowadzonej teorii leżącej u podstaw MVCO konflikty są uogólniane dla różnych wersji tego samego zasobu (w odróżnieniu od wcześniejszych teorii wielowersyjnych). W przypadku różnych wersji kolejność chronologiczna konfliktów jest zastępowana kolejnością wersji i być może odwracana, przy jednoczesnym zachowaniu zwykłych definicji operacji będących w konflikcie. Wyniki dla regularnych i rozszerzonych wykresów konfliktów pozostają niezmienione i podobnie jak w przypadku CO istnieje rozproszony algorytm wymuszający MVCO, teraz dla środowiska mieszanego z zasobami zarówno w jednej, jak i w wielu wersjach (teraz pojedyncza wersja jest szczególnym przypadkiem wielu wersji ). Jeśli chodzi o CO, algorytm MVCO potrzebuje tylko (niezmodyfikowanych) komunikatów atomowego protokołu zobowiązań bez dodatkowych narzutów komunikacyjnych. Globalne impasy oparte na blokowaniu przekładają się na impas w głosowaniu i są rozwiązywane automatycznie. W analogii do CO zachodzi:

• Twierdzenie MVCO i Global o serializowalności jednej kopii

1. Zgodność MVCO każdego autonomicznego systemu bazodanowego (lub obiektu transakcyjnego) w mieszanym środowisku wielobazowym jedno- i wielowersyjnych baz danych jest warunkiem koniecznym do zagwarantowania globalnej serializacji jednej kopii (1SER).
2. Zgodność MVCO każdego systemu bazodanowego jest warunkiem wystarczającym do zagwarantowania Global 1SER.
3. Globalne zakleszczenia oparte na blokowaniu są rozwiązywane automatycznie.

Komentarz : Teraz zgodny z CO system bazy danych z pojedynczą wersją jest automatycznie zgodny z MVCO.

MVCO można dalej uogólnić, aby zastosować uogólnienie ECO (MVECO).

Przykład: izolacja migawek oparta na CO (COSI)

Izolacja migawki oparta na CO (COSI) to skrzyżowanie izolacji migawki (SI) z MVCO. SI to wielowersyjna metoda kontroli współbieżności szeroko stosowana ze względu na dobrą wydajność i podobieństwo do serializowalności (1SER) w kilku aspektach. Opisana powyżej teoria MVCO w (Raz 1993b) została później wykorzystana w (Fekete et al. 2005) i innych artykułach dotyczących SI, np. (Cahill et al. 2008); zobacz także Tworzenie serializacji izolacji migawek i tamtejsze odniesienia), do analizowania konfliktów w SI w celu umożliwienia serializacji. Metoda przedstawiona w (Cahill i in. 2008), Izolacja migawek serializowalnych (SerializableSI), modyfikacja SI o niskim narzucie, zapewnia dobre wyniki wydajności w porównaniu z SI, z tylko niewielką karą za wymuszanie serializowalności. Inna metoda, łącząc SI z MVCO (COSI), umożliwia również serializację SI, przy stosunkowo niskim narzucie, podobnie jak połączenie ogólnego algorytmu CO z mechanizmami pojedynczej wersji. Co więcej, wynikowa kombinacja, COSI, będąc zgodna z MVCO, umożliwia systemom baz danych zgodnym z COSI współdziałanie i przejrzysty udział w rozwiązaniu CO w celu rozproszonej/globalnej serializacji (patrz poniżej). Oprócz kosztów ogólnych należy również ilościowo porównać zachowania protokołów. Z jednej strony, wszystkie możliwe do serializacji harmonogramy SI mogą być wykonane jako MVCO przez COSI (poprzez ewentualne opóźnienia zatwierdzania w razie potrzeby) bez przerywania transakcji. Z drugiej strony wiadomo, że SerializableSI niepotrzebnie przerywa i ponownie uruchamia określone procenty transakcji, również w harmonogramach SI możliwych do serializacji.

CO i jego warianty są w przejrzysty sposób interoperacyjne dla globalnej serializacji

W przypadku CO i jego wariantów (np. SS2PL, SCO, OCO, ECO i MVCO powyżej) globalną serializowalność uzyskuje się za pomocą rozproszonych algorytmów opartych na protokole zaangażowania atomowego . W przypadku CO i wszystkich jego wariantów atomowy protokół zaangażowania jest instrumentem eliminującym globalne cykle (cykle, które obejmują dwie lub więcej baz danych) w globalnym powiększonym (a więc także regularnym) grafie konfliktów (niejawnie; nie jest wymagana implementacja globalnej struktury danych). W przypadkach niezgodnych lokalnych zamówień zobowiązań w dwóch lub więcej bazach danych (gdy żadne globalne zamówienie częściowe nie może osadzić razem odpowiednich lokalnych zamówień częściowych) lub impasu głosowania związanego z blokadą dostępu do danych, oba implikują globalny cykl na wykresie globalnego rozszerzonego konfliktu i brakujących głosów, protokół zobowiązania atomowego przerywa taki cykl, przerywając na nim niezdecydowaną transakcję (patrz Algorytm rozproszonego CO powyżej). Różnice między różnymi wariantami istnieją tylko na poziomie lokalnym (w uczestniczących systemach baz danych). Każda lokalna instancja CO dowolnego wariantu ma tę samą rolę, aby określić pozycję każdej transakcji globalnej (transakcji, która obejmuje dwie lub więcej baz danych) w ramach lokalnego zamówienia zobowiązania, tj. określić, kiedy nadejdzie kolej na głosowanie nad transakcją lokalnie w atomowym protokole zobowiązań. Zatem wszystkie warianty CO wykazują takie samo zachowanie w odniesieniu do zaangażowania atomowego. Oznacza to, że wszystkie są interoperacyjne dzięki zobowiązaniu atomowemu (wykorzystujące te same interfejsy oprogramowania, zwykle dostarczane jako usługi , niektóre już ustandaryzowane pod kątem zobowiązania atomowego, głównie dla protokołu zatwierdzania dwufazowego , np. X/Open XA ) i mogą być w przejrzysty sposób wykorzystywane razem w dowolnym środowisku rozproszonym (podczas gdy każda instancja wariantu CO jest prawdopodobnie powiązana z dowolnym odpowiednim typem lokalnego mechanizmu kontroli współbieżności).

Podsumowując, dowolna pojedyncza transakcja globalna może jednocześnie uczestniczyć w bazach danych, które mogą wykorzystywać każdy dowolny, być może inny, wariant CO (jednocześnie uruchamiając procesy w każdej takiej bazie danych i działając jednocześnie z lokalnymi i innymi globalnymi transakcjami w każdej takiej bazie danych). Protokół zaangażowania atomowego jest obojętny na CO i nie rozróżnia różnych wariantów CO. Każdy globalny cykl generowany na grafie rozszerzonego globalnego konfliktu może obejmować bazy danych różnych wariantów CO i generować (jeśli nie zostanie przerwany przez żadne lokalne przerwanie) impas głosowania, który jest rozwiązywany przez zaangażowanie atomowe dokładnie w taki sam sposób, jak w jednym środowisku wariantu CO. cykle lokalne (obecnie prawdopodobnie z mieszanymi konfliktami zmaterializowanymi i niezmaterializowanymi, związanymi zarówno z serializowalnością, jak i zakleszczeniem blokowania dostępu do danych, np. SCO) są rozwiązywane lokalnie (każdy przez własne lokalne mechanizmy odpowiedniej instancji wariantu).

Porządkowanie głosów (VO lub Generalized CO (GCO); Raz 2009 ), połączenie CO i wszystkich jego powyższych wariantów, jest użyteczną koncepcją i techniką globalnej serializacji. Aby zachować zgodność z VO, potrzebna jest lokalna serializowalność (w najbardziej ogólnej formie, oparta na przemienności i obejmująca wielowersję) oraz strategia kolejności głosowania (głosowanie według lokalnej kolejności pierwszeństwa).

Łącząc wyniki dla CO i jego wariantów, stwierdza się, co następuje:

• Twierdzenie o interoperacyjności wariantów CO

1. W środowisku wielobazowym, gdzie każdy system baz danych (obiekt transakcyjny) jest zgodny z jakąś właściwością wariantu CO (zgodny z VO), dowolna transakcja globalna może uczestniczyć jednocześnie w bazach danych o możliwie różnych wariantach CO, a globalna serializowalność jest gwarantowana (warunek wystarczający dla Globalna serializowalność i Globalna serializowalność jednej kopii (1SER) w przypadku, gdy istnieje wielowersyjna baza danych).
2. Jeśli tylko lokalna (dla systemu bazy danych) informacja kontrolna współbieżności jest wykorzystywana przez każdy system bazy danych (każdy ma uogólnioną właściwość autonomii , uogólnienie autonomii ), to zgodność każdego z (dowolną) właściwością wariantu CO (zgodność VO) jest warunek konieczny do zagwarantowania globalnej serializacji (i globalnej 1SER; w przeciwnym razie mogą zostać naruszone).
3. Co więcej, w takim środowisku globalne zakleszczenia związane z blokowaniem dostępu do danych są rozwiązywane automatycznie (każdy taki zakleszczenie jest generowane przez globalny cykl w rozszerzonym grafie konfliktów ( tj . (konflikt niezmaterializowany) i dwoma systemami baz danych; w związku z tym nie jest to cykl w regularnym grafie konfliktów i nie wpływa na serializowalność).

• Raz, Yoav (sierpień 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 XVIII International Conference on Very Large Data Bases , Vancouver, Kanada , s. 292–312 (również DEC-TR 841, Digital Equipment Corporation , listopad 1990)
• Raz , Yoav ( wrzesień 1994 ) _
• Raz, Yoav (czerwiec 2009), Theory of Commitment Ordering: Summary , dostęp 11 listopada 2011
• Raz, Yoav (listopad 1990), O znaczeniu zamawiania zobowiązań (PDF) , Digital Equipment Corporation
• Yoav Raz (1991a): patenty USA 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, grudzień 1991.
• Yoav Raz (1991c): „Locking Based Strict Commitment Ordering, czyli jak poprawić współbieżność w menedżerach zasobów opartych na blokowaniu”, DEC-TR 844, grudzień 1991.
• Yoav Raz (1993a): „Rozszerzone zamawianie zobowiązań lub gwarantowanie globalnej serializacji poprzez zastosowanie selektywności zleceń zobowiązań do transakcji globalnych”. Proceedings of the XII ACM Symposium on Principles of Database Systems (PODS), Washington, DC, s. 83-96, maj 1993. (również DEC-TR 842, listopad 1991)
• Yoav Raz (1993b): „Rozproszona kontrola współbieżności oparta na porządkowaniu zobowiązań w celu łączenia zasobów w jednej i wielu wersjach”. Proceedings of the Third IEEE International Workshop on Research Issues on Data Engineering: Interoperability in Multidatabase Systems (RIDE-IMS), Wiedeń, Austria, s. 189-198, kwiecień 1993. (również DEC-TR 853, lipiec 1992)

Linki zewnętrzne

• Strona zamawiania Yoav Raz's Commitment