Informatyka i programowanieSystemy rozproszone, chmura i komputery działające jak jeden system

CRDT pozwala kilku komputerom edytować dane bez uzgadniania każdej zmiany, a mimo to później dojść do tego samego stanu

Większość ludzi oczekuje, że jeśli dwie repliki jednocześnie zmieniają te same dane, muszą najpierw ustalić kolejność. CRDT pokazuje, że dla odpowiednio zaprojektowanych struktur można zrobić inaczej. Każda replika może przyjmować lokalne aktualizacje bez koordynacji. Gdy później otrzyma te same zmiany co pozostałe, deterministyczne reguły scalania doprowadzą wszystkie do identycznego stanu. Nie jest to magiczny sposób na dowolne konflikty — struktura danych musi być zaprojektowana tak, by operacje można było bezpiecznie łączyć. Dzięki temu część aplikacji może działać podczas rozłączenia i synchronizować się później.

Nie każdy konflikt wymaga wyboru zwycięzcy

Jeżeli dwie osoby niezależnie dodają element do zbioru, naturalnym rozwiązaniem może być zachowanie obu dodatków. Problem jest łatwiejszy niż równoczesna zmiana jednej liczby na dwie sprzeczne wartości. CRDT wykorzystują takie algebraiczne własności, aby zdefiniować operacje, których wynik po scaleniu jest jednoznaczny.

Repliki mogą aktualizować się lokalnie

Przegląd CRDT autorstwa Preguiçy, Baquero i Shapiro definiuje je jako typy danych przeznaczone do replikacji, w których każda replika może być modyfikowana bez koordynowania się z innymi. To szczególnie cenne przy przerwach w sieci albo w aplikacjach offline-first.

Zbieżność wynika z konstrukcji matematycznej

Warunek jest mocny: gdy dwie repliki otrzymają ten sam zestaw aktualizacji, mają deterministycznie osiągnąć ten sam stan. Osiąga się to przez specjalne reguły łączenia stanów lub właściwości operacji, np. przemienność i idempotencję w odpowiednim modelu.

Cena pojawia się w semantyce danych

CRDT nie rozwiązuje dowolnej logiki biznesowej. Dla licznika można ustalić bezpieczne reguły zwiększania. Dla zbioru można precyzyjnie określić, co znaczy jednoczesne dodanie i usunięcie. Ale jeśli dwie strony równocześnie ustalą „ostateczną cenę kontraktu” na inne wartości, system nadal potrzebuje reguły biznesowej.

To alternatywa dla koordynacji, nie jej uniwersalny zamiennik

Consensus zapewnia jedną wspólną kolejność, ale kosztuje komunikację i może blokować postęp podczas niektórych awarii. CRDT wykorzystuje inną drogę: projektuje dane tak, aby niektóre niezależne operacje mogły później bezpiecznie się spotkać. W odpowiednich zastosowaniach pozwala to uzyskać wysoką dostępność bez ciągłego uzgadniania każdej drobnej zmiany.

Różne CRDT kodują różne decyzje o konflikcie

Nie istnieje jeden uniwersalny CRDT. Są liczniki, zbiory, rejestry i inne struktury, a każda definiuje znaczenie równoległych operacji. Na przykład zbiór musi ustalić, co robić, gdy jeden węzeł dodaje element, a drugi go usuwa bez wiedzy o sobie. Reguła może preferować add albo remove, ale musi być formalnie określona, aby wszystkie repliki po otrzymaniu tych samych aktualizacji doszły do identycznego wyniku.

Dostępność offline jest naturalnym zastosowaniem

Edytor, aplikacja mobilna czy system działający na urządzeniach czasowo bez sieci może pozwolić użytkownikom pracować lokalnie i synchronizować zmiany po powrocie łączności. Jeśli model danych można wyrazić odpowiednimi CRDT, brak połączenia nie musi oznaczać blokady edycji. To pokazuje, że właściwy wybór struktury danych może zmienić wymagania infrastruktury, a nie tylko wydajność kodu.

CRDT dobrze pokazują, że część problemów koordynacji można przenieść z protokołu do modelu danych. Jeśli operacje zostały zaprojektowane tak, aby ich kolejność nie wpływała na końcowy wynik, sieć nie musi ustalać tej kolejności w czasie rzeczywistym. To potężna idea, ale wymaga myślenia o semantyce już na etapie projektowania danych. Próba „dodania CRDT” do arbitralnej istniejącej logiki po fakcie może być niemożliwa, bo biznesowy konflikt nie zawsze ma naturalne, deterministyczne scalanie.

Istnieją zarówno CRDT oparte na stanie, które okresowo scalają całe reprezentacje, jak i oparte na operacjach, gdzie repliki rozsyłają odpowiednio zaprojektowane zmiany. Każdy wariant ma inne wymagania wobec kanału komunikacji i metadanych. Wspólny cel jest jednak taki sam: convergence bez centralnej sekwencji wszystkich operacji. To pokazuje, że „brak consensusu” nie oznacza „brak reguł”; wręcz przeciwnie, reguły muszą być matematycznie bardzo precyzyjne.

#CRDT#eventual consistency#konflikty#offline-first#replikacja#zbieżność
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki