Jakie są główne problemy badawcze w transakcjach rozproszonych?

10

Tło: Przetwarzanie transakcji jest tradycyjnym tematem badań w teorii baz danych. Obecnie transakcje rozproszone są popularyzowane przez wielkoskalowe rozproszone systemy pamięci masowej, które zazwyczaj obejmują partycjonowanie danych (zwane także shardingiem) i replikację danych .

Jakie są główne problemy badawcze w transakcjach rozproszonych?

Czy istnieją dobrze znane teorie i rozwiązania, które wymagają (teoretycznej) poprawy?

Wszelkie referencje są mile widziane.

hengxin
źródło

Odpowiedzi:

9

Istnieje wiele obszarów badawczych zarówno w teorii, jak i praktyce rozproszonych baz danych.

Jednym z głównych praktycznych wyzwań jest wdrożenie wydajnych mechanizmów kontroli współbieżności dla rozproszonych i replikowanych geograficznie baz danych. W celu wydajnego wykonywania transakcji mechanizmy takie mogą dawać słabsze gwarancje niż możliwość szeregowania, co wymaga, aby transakcje były wykonywane sekwencyjnie. Alternatywą dla szeregowania jest rozwiązanie dla Snapshot Isolation [1], ale udowodniono, że źle skaluje się do systemów replikowanych geograficznie i rozproszonych. W obecnym stanie techniki zdefiniowano dwa różne warianty izolowania migawek (SI) w celu kontrolowania współbieżności w systemach replikowanych geograficznie: równoległe izolowanie migawek (PSI) [2] i niemonotoniczne izolowanie migawek (NMSI) [ 3,4]. Jeśli chodzi o to, co dotyczy rozproszonych baz danych (tj. Gdzie dane są dzielone między różne witryny),

Mając różne pojęcia poziomów izolacji, które dają słabsze gwarancje niż szeregowalność, kolejnym ważnym pytaniem jest pisanie programów w taki sposób, aby wykonania nadal wyglądały na szeregowalne. Kryterium dźwiękowe dla izolacji migawki zostało opracowane w [1]. Niektóre osoby w mojej grupie pracują obecnie nad opracowaniem rozsądnego kryterium dla PSI.

Kolejnym istotnym pytaniem, zarówno z teoretycznego, jak i praktycznego punktu widzenia, jest wycinanie transakcji. Zasadniczo siekanie to techniki analizy statycznej, w których gruboziarniste transakcje dzielone są na mniejsze, drobnoziarniste transakcje. W przypadku szeregowalności pytanie to zostało poruszone w [6], a uzyskana teoria została zastosowana w celu praktycznego wdrożenia w [7].

Z punktu widzenia teoretycznych podstaw rozproszonych baz danych pojawiła się propozycja zastosowania technik ze społeczności słabych modeli pamięci [8] do formalnego zdefiniowania zachowania transakcji. W [9] autorzy podają formalne pojęcie zachowania dla transakcji; to samo podejście zastosowano w [10] w celu określenia zachowania replikowanych typów danych.

Niedawno ja i niektórzy z moich kolegów (Alexey Gotsman i Hongseok Yang) zbudowaliśmy, zaczynając od technik opracowanych w [8,9,10], ramy teoretyczne do określania możliwego do zaobserwowania zachowania poziomów spójności dla baz danych replikowanych geograficznie. Z powodzeniem zastosowaliśmy platformę do aksjatyzacji SI, PSI i NMSI, z których każdy okazał się poprawny w odniesieniu do prostej implementacji. Wykorzystaliśmy również powstałą teorię, aby opracować kryterium cięcia dla PSI. Mamy nadzieję, że wyniki te opublikujemy w dającej się przewidzieć przyszłości.

Nie wahaj się napisać do mnie, jeśli masz inne pytania. Mam nadzieję że to pomoże,

Andrea Cerone.

Bibliografia:

[1] Fekete i in., Making Snapshot Isolation Serializable (2005)

[2] Sovran i in., Transactional Storage for Geo-replication Systems (2011)

[3] Arkedani i in., Non-Monotonic Snapshot Isolation: skalowalna i silna spójność dla systemów transakcyjnych replikowanych geograficznie (2013)

[4] Arkedani i in., On the Scalability of Snapshot Isolation (2013)

[5] Binnig i in., Rozproszona izolacja migawek: transakcje globalne płacą globalnie, transakcje lokalne płacą lokalnie

[6] Shasha i in., Transaction chopping: algorytmy i badania wydajności (1995)

[7] Zhang i in., Łańcuchy transakcyjne: osiąganie możliwości serializacji przy niskim opóźnieniu w geograficznie rozproszonych systemach pamięci masowej (2013)

[8] Alglave, formalna hierarchia modeli słabej pamięci (2012)

[9] Buckhardt i in., Understanding Eventual Consistency (2013)

[10] Buckhardt i in., Replicated Typy danych: specyfikacja, weryfikacja, optymalność (2014)

Andrea Cerone
źródło
Dziękujemy za wyczerpującą odpowiedź. Czy w przypadku SI istnieją rozproszone protokoły bez blokady w replikowanych ustawieniach w literaturze? Czy ta próba nie ma znaczenia, ponieważ SI nie skaluje się dobrze? W przypadku PSI przeczytałem artykuł (Tim Kraska @ Eurosys'13), w którym wspomniano o jego wdrożeniu w przyszłych pracach. Czy nadaje się do tego Uogólniony Paxos ? Jakie są możliwe zalety / wady / wyzwania w porównaniu z oryginalnym w Sovran i wsp. [2]? Dzięki jeszcze raz.
hengxin
2
Rzeczywiście SI nie skaluje się dobrze do systemów replikowanych geograficznie. W [4] powyżej autorzy dowodzą, że istnieją właściwości, takie jak Oryginalna częściowa replikacja, których nie można uzyskać za pomocą DBMS replikowanych geograficznie działających na poziomie spójności SI. W [5] autorzy pokazują przykłady wykonania, które zachowują się zgodnie z SI lokalnie (w pojedynczych fragmentach), ale nie globalnie, i proponują wariant SI o nazwie DSI. Jeśli chodzi o MDCC, nie znam tego dokumentu i muszę przyznać, że nie znam szczegółów implementacji uogólnionego Paxos. Ale chętnie się obejrzę i odpowiem jak najszybciej.
Andrea Cerone,