Zdalne blokady z użyciem Redis

Cześć, Habr!

Dziś przedstawiamy tłumaczenie skomplikowanego artykułu na temat wdrażania rozproszonych blokad za pomocą Redis oraz porozmawiamy o perspektywach Redis jako tematu. Analiza omawianego algorytmu Redlock autorstwa Martina Kleppmana, autora książki "Wysokowydajne aplikacje", jest przedstawiona tutaj.

Rozproszone blokady to bardzo przydatny prymityw, stosowany w wielu środowiskach, w których różne procesy muszą pracować nad współdzielonymi zasobami na zasadzie wzajemnego wykluczania.

Istnieje wiele bibliotek i artykułów opisujących, jak zaimplementować DLM (menedżer rozproszonych blokad) przy użyciu Redis, ale każda biblioteka stosuje własne podejście, a oferowane gwarancje są dość słabe w porównaniu do tego, co można osiągnąć dzięki nieco bardziej złożonemu projektowaniu.

W tym artykule spróbujemy opisać kanoniczny algorytm, który pokazuje, jak zaimplementować rozproszone blokady z wykorzystaniem Redis. Porozmawiamy o algorytmie o nazwie Redlock, który implementuje menedżera rozproszonych blokad i, naszym zdaniem, jest ten algorytm bezpieczniejszy niż zwykłe podejście z pojedynczym instansem. Mamy nadzieję, że społeczność go przeanalizuje, dostarczy informacji zwrotnej i zacznie wykorzystywać jako punkt wyjścia do realizacji bardziej złożonych lub alternatywnych projektów.

Implementacje

Zanim przejdziemy do opisu algorytmu, podamy kilka linków do już gotowych implementacji. Można z nich korzystać w celach referencyjnych.

• Redlock-rb (implementacja dla Ruby). Istnieje również forka Redlock-rb, dodający pakiet (gem) dla wygody uruchamiania, i nie tylko dla tego.
• Redlock-py (implementacja dla Pythona).
• Aioredlock (implementacja dla Asyncio Pythona).
• Redlock-php (implementacja dla PHP).
• PHPRedisMutex (kolejna implementacja dla PHP)
• cheprasov/php-redis-lock (biblioteka PHP do blokad)
• Redsync (implementacja dla Go).
• Redisson (implementacja dla Javy).
• Redis::DistLock (implementacja dla Perla).
• Redlock-cpp (implementacja dla C++).
• Redlock-cs (implementacja dla C#/.NET).
• RedLock.net (implementacja dla C#/.NET). Z obsługą rozszerzeń async i lock.
• ScarletLock (implementacja dla C# .NET z konfigurowalnym magazynem danych)
• Redlock4Net (implementacja dla C# .NET)
• node-redlock (implementacja dla NodeJS). Obejmuje wsparcie dla przedłużania blokad.

Gwarancje bezpieczeństwa i dostępności

Zamierzamy zmodelować nasz projekt, mając tylko trzy właściwości, które naszym zdaniem zapewniają minimalne gwarancje niezbędne do efektywnego wykorzystania rozproszonych blokad.

1. Właściwość bezpieczeństwa: Wzajemne wykluczenie. W danym momencie tylko jeden klient może posiadać blokadę.
2. Właściwość dostępności A: Brak wątków blokujących. Ostatecznie zawsze można uzyskać blokadę, nawet jeśli klient, który zablokował zasób, przestanie działać lub trafi do innego segmentu dysku.
3. Właściwość dostępności B: Odporność na awarie. Dopóki większość węzłów Redis działa, klienci mogą nabywać i zwalniać blokady.

Dlaczego realizacja oparta na odzyskiwaniu po awarii jest w tym przypadku niewystarczająca
Aby zrozumieć, co zamierzamy poprawić, przeanalizujmy bieżącą sytuację z większością bibliotek do rozproszonych blokad opartych na Redis.

Najprostszym sposobem blokowania zasobu za pomocą Redis jest stworzenie klucza w instancji. Zwykle klucz jest tworzony z ograniczonym czasem życia, co osiąga się przez funkcję expires w Redis, więc prędzej czy później ten klucz zostaje zwolniony (właściwość 2 na naszej liście). Kiedy klient musi zwolnić zasób, usuwa klucz.

Na pierwszy rzut oka to rozwiązanie działa, ale istnieje problem: w naszej architekturze pojawia się pojedynczy punkt awarii. Co się stanie, jeśli liderująca instancja Redis zawiedzie? Dodajmy więc instancję zapasową! I będziemy jej używać, gdy lider będzie niedostępny. Niestety, takie rozwiązanie jest nieżywotne. W ten sposób nie będziemy mogli prawidłowo zrealizować właściwości wzajemnego wykluczenia, niezbędnej do zapewnienia bezpieczeństwa, ponieważ replikacja w Redis jest asynchroniczna.

Oczywiście w takim modelu pojawia się stan wyścigu:

1. Klient A nabywa blokadę na liderze.
2. Lider zawodzi, zanim zapis klucza zostanie przekazany do instancji zapasowej.
3. Instancja zapasowa staje się liderem.
4. Klient B nabywa blokadę tego samego zasobu, który już jest zablokowany przez A. NARUSZENIE BEZPIECZEŃSTWA!

Czasami jest zupełnie normalne, że w szczególnych okolicznościach, takich jak awarie, wielu klientów może jednocześnie mieć blokadę. W takich sytuacjach można zastosować rozwiązanie oparte na replikacji. W innych przypadkach zalecamy rozwiązanie opisane w tym artykule.

Prawidłowa realizacja z jednym instancją

Zanim spróbujemy przezwyciężyć wady konfiguracji z jedną instancją, opisaną powyżej, przyjrzyjmy się, jak prawidłowo działać w tym prostym przypadku, ponieważ takie rozwiązanie jest naprawdę dopuszczalne w aplikacjach, gdzie wyścig o stan jest czasami akceptowalny, a także dlatego, że blokada w jednej instancji stanowi podstawę, która jest wykorzystywana w opisanym tutaj algorytmie rozproszonym.

Aby uzyskać blokadę, postępujemy tak:

SET resource_name my_random_value NX PX 30000

Ta komenda ustawia klucz, tylko jeśli jeszcze nie istnieje (opcję NX), z czasem wygaśnięcia 30000 milisekund (opcję PX). Dla klucza zostaje ustawiona wartość “myrandomvalue”. Wartość ta musi być unikalna wśród wszystkich klientów i wszystkich żądań blokady.
W zasadzie losowa wartość jest używana do bezpiecznego zwalniania blokady, przy pomocy skryptu, który informuje Redis: usuń klucz, tylko jeśli istnieje, a wartość, która została w nim zapisana, to dokładnie to, czego się oczekiwało. Osiąga się to za pomocą następującego skryptu w Lua:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

To ważne, aby zapobiec usunięciu blokady utworzonej przez innego klienta. Na przykład klient może uzyskać blokadę, a następnie zablokować się w trakcie jakiejś operacji, która trwa dłużej niż czas trwania pierwszej blokady (tak, że czas trwania klucza zdąży wygasnąć), a później usunąć blokadę, którą nałożył inny klient.
Używanie prostego DEL jest niebezpieczne, ponieważ klient może usunąć blokadę nałożoną przez innego klienta. Przeciwnie, przy użyciu powyższego skryptu, każda blokada jest „podpisana” losowym ciągiem, więc może ją usunąć tylko ten klient, który ją wcześniej nałożył.

Jaka powinna być ta losowa linia? Uważam, że powinno to być 20 bajtów z /dev/urandom, ale można znaleźć mniej kosztowne sposoby, aby uzyskać wystarczająco unikalny ciąg do celów, które przed tobą stoją. Na przykład, można wykorzystać RC4 z /dev/urandom, a następnie wygenerować na jego podstawie pseudolosowy strumień. Prostsze rozwiązanie polega na połączeniu czasu unix w rozdzielczości mikrosekundowej plus ID klienta; nie jest to tak bezpieczne, ale chyba odpowiada poziomowi zadań w większości kontekstów.

Czas, który wykorzystujemy jako wskaźnik czasu życia klucza, nazywany jest „czasem działania blokady”. Jest to wartość, która jednocześnie stanowi czas, po upływie którego blokada zostanie automatycznie zwolniona, oraz czas, który klient ma na wykonanie operacji, zanim inny klient będzie mógł zablokować ten zasób, bez faktycznego naruszania gwarancji wzajemnego wykluczania. Taka gwarancja ograniczona jest jedynie określonym oknem czasowym, które zaczyna się od momentu uzyskania blokady.

Tak więc omówiliśmy dobry sposób na uzyskanie i zwolnienie blokady. System (jeśli mówimy o niezdolnym systemie, składającym się z jednego zawsze dostępnego instancji) jest bezpieczny. Rozwińmy tę koncepcję do systemu rozproszonego, w którym nie mamy takich gwarancji.

Algorytm Redlock

W rozproszonej wersji algorytmu zakłada się, że mamy N głównych Redisów. Te węzły są całkowicie niezależne od siebie, dlatego nie wykorzystujemy replikacji ani żadnego innego niejawnego systemu koordynacji. Już opowiedzieliśmy, jak bezpiecznie uzyskać i zwolnić blokadę na pojedynczej instancji. Zakładamy, że algorytm w pracy z pojedynczą instancją wykorzysta właśnie tę metodę. W naszych przykładach ustalamy N na 5, co jest całkiem rozsądną wartością. W ten sposób będziemy potrzebować używać 5 głównych Redisów na różnych komputerach lub maszynach wirtualnych, aby zapewnić, że będą działały w zasadzie niezależnie od siebie.

Aby uzyskać blokadę, klient wykonuje następujące operacje:

1. Uzyskuje bieżący czas w milisekundach.
2. Stara się uzyskać blokadę na wszystkie N instancje, używając w każdym przypadku tej samej nazwy klucza i losowych wartości. Na etapie 2, ustanawiając blokadę dla każdej instancji, klient wykorzystuje opóźnienie, które jest wystarczająco krótkie w porównaniu do czasu, po którym blokada jest automatycznie usuwana. Na przykład, jeśli czas trwania blokady wynosi 10 sekund, opóźnienie może wynosić około 5-50 milisekund. W ten sposób wyklucza się sytuację, w której klient mógłby długo pozostawać zablokowany, próbując połączyć się z niedziałającym węzłem Redis: jeśli instancja jest niedostępna, jak najszybciej próbujemy połączyć się z inną instancją.
3. Aby uzyskać blokadę, klient oblicza, ile czasu już minęło; w tym celu odejmuje od aktualnej wartości czasu znacznik czasu, który został uzyskany w kroku 1. Tylko wtedy, gdy klient zdołał uzyskać blokadę na większości instancji (co najmniej 3), a całkowity czas potrzebny do uzyskania blokady jest mniejszy niż czas trwania blokady, uważa się, że blokada została uzyskana.
4. Jeśli blokada została przyznana, czas jej trwania określa się jako początkowa wartość długości blokady minus czas, który upłynął, obliczony w kroku 3.
5. Jeśli klient z jakiegoś powodu nie zdołał uzyskać blokady (czy to nie udało mu się zablokować N/2+1 instancji, czy też czas trwania blokady okazał się ujemny), to spróbuje odblokować wszystkie instancje (nawet te, które, jak sądzono, nie mogły być zablokowane).

Czy algorytm jest asynchroniczny?

Algorytm ten opiera się na założeniu, że chociaż nie ma zsynchronizowanych zegarów, które byłyby używane przez wszystkie procesy, lokalny czas w każdym procesie płynie mniej więcej w tym samym tempie, a błąd jest niewielki w porównaniu do całkowitego czasu, po którym blokada jest automatycznie usuwana. To założenie przypomina sytuację typową dla zwykłych komputerów: każdy komputer ma swoje lokalne zegary i zwykle możemy zakładać, że rozbieżności czasowe między różnymi komputerami są niewielkie.

Na tym etapie musimy dokładniej sformułować naszą zasadę wzajemnego wykluczenia: wzajemne wykluczenie jest gwarantowane tylko pod warunkiem, że klient, który utrzymuje blokadę, zakończy pracę w czasie, w którym blokada jest ważna (ta wartość została uzyskana w kroku 3), minus jeszcze pewien czas (zaledwie kilka milisekund, aby skompensować różnice czasowe między procesami).

Więcej na temat takich systemów, które wymagają uzgodnienia różnic czasowych, opowiada następujący interesujący artykuł: Leases: efektywny mechanizm odporny na błędy dla spójności rozproszonej pamięci podręcznej plików.

Ponowna próba w przypadku błędu

Gdy klientowi nie uda się uzyskać blokady, powinien spróbować ponownie to zrobić, stosując losowe opóźnienie; ma to na celu rozrzucenie wielu klientów, którzy jednocześnie próbują zdobyć blokadę tego samego zasobu (co może prowadzić do sytuacji „podzielonego mózgu”, w której nie ma zwycięzców). Ponadto, im szybciej klient próbuje zdobyć blokadę większości instancji Redis, tym węższe jest okno, w którym może wystąpić sytuacja podzielonego mózgu (i tym mniej potrzeba ponownych prób). Dlatego w idealnym przypadku klient powinien spróbować jednocześnie wysłać polecenia SET do N instancji za pomocą multipleksacji.

Tu warto podkreślić, jak ważne jest, aby klienci, którzy nie mogli zdobyć większości blokad, zwolnili (częściowo) zdobyte blokady, aby nie trzeba było czekać na wygaśnięcie klucza, zanim blokada nad zasobem będzie mogła zostać ponownie zdobyta (prawda, że ​​jeśli wystąpi fragmentacja sieci i klient straci kontakt z instancjami Redis, będzie musiał zapłacić karę za naruszenie dostępności, czekając na wygaśnięcie klucza).

Zwalnianie blokady

Zwalnianie blokady to prosta operacja, polegająca na odblokowaniu wszystkich instancji, niezależnie od tego, czy klientowi wydaje się, że udało mu się pomyślnie zablokować konkretną instancję.

Uwagi na temat bezpieczeństwa

Czy algorytm jest bezpieczny? Spróbujmy wyobrazić sobie, co się dzieje w różnych scenariuszach.

Na początku załóżmy, że klient zdołał zablokować większość instancji. Każda z instancji będzie zawierać klucz o tym samym czasie życia. Jednak każdy z tych kluczy został ustawiony w swoim momencie, więc okres ich ważności wygasł w różnym czasie. Jeżeli jednak pierwszy klucz został ustawiony nie później niż w T1 (czas, który wybieramy przed kontaktem z pierwszym serwerem), a ostatni klucz nie później niż w T2 (czas, w którym otrzymaliśmy odpowiedź z ostatniego serwera), to możemy być pewni, że pierwszy klucz w zbiorze, który wygaśnie, będzie ważny przynajmniej MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Wszystkie inne klucze wygasną później, więc możemy być pewni, że wszystkie klucze będą jednocześnie ważne przez co najmniej ten czas.

W okresie, gdy większość kluczy pozostaje ważna, inny klient nie będzie w stanie zakupić blokady, ponieważ operacje N/2+1 SET NX nie mogą zakończyć się sukcesem, jeśli już istnieje N/2+1 kluczy. Dlatego, jeśli blokada została nabyta, nie można jej ponownie uzyskać w tym samym czasie (łamałoby to zasadę wzajemnego wykluczania).
Prawda jest, że chcemy upewnić się, że wiele klientów próbujących jednocześnie zdobyć blokadę nie będzie mogło jednocześnie odnieść sukcesu.

Jeżeli klient zablokował większość instancji, poświęcając na to czas równy lub większy niż maksymalny czas trwania blokady, uzna blokadę za nieważną i odblokuje instancje. Dlatego musimy uwzględnić tylko przypadek, w którym klientowi udało się zablokować większość instancji w czasie krótszym niż czas ważności. W tym przypadku, jeśli chodzi o podany wcześniej argument, w czasie MIN_VALIDITY żaden klient nie powinien być w stanie ponownie zdobyć blokady. Dlatego wiele klientów będzie mogło zablokować N/2+1 instancji w tym samym czasie (które kończy się w momencie zakończenia etapu 2), tylko kiedy czas dla blokowania większości był dłuższy niż czas TTL, co czyni blokadę nieważną.

Czy możesz przedstawić formalny dowód bezpieczeństwa, wskazać istniejące podobne algorytmy, czy znaleźć błąd w opisie?

Uwagi dotyczące dostępności

Dostępność systemu zależy od trzech głównych cech:

1. Automatyczne znoszenie blokady (ponieważ klucze wygasają): ostatecznie klucze będą ponownie dostępne, aby używać ich do blokad.
2. Fakt, że klienci zazwyczaj pomagają sobie nawzajem w usuwaniu blokad, gdy potrzebna blokada nie została nabyta, lub została nabyta, a praca została zakończona; dlatego bardzo prawdopodobne jest, że nie będziemy musieli czekać na wygaśnięcie kluczy, aby ponownie nabyć blokadę.
3. Fakt, że gdy klient musi ponownie spróbować uzyskać blokadę, czeka stosunkowo dłużej niż czas potrzebny do nabycia większości blokad. To zmniejsza prawdopodobieństwo wystąpienia sytuacji rozdzielonego mózgu podczas rywalizacji o zasoby.

Jednak trzeba zapłacić karę za zmniejszenie dostępności, równą czasowi TTL w segmentach sieci, dlatego jeśli są ciągłe segmenty, kara ta może nabrać nieokreślonego rozmiaru. Dzieje się tak za każdym razem, gdy klient nabywa blokadę, a następnie zostaje odcięty w innym segmencie, zanim zdąży ją zwolnić.

W zasadzie, mając nieskończone ciągłe segmenty sieci, system może pozostawać niedostępny przez nieskończony czas.

Wydajność, odzyskiwanie po awarii i fsync

Wielu korzysta z Redis, ponieważ wymagana jest wysoka wydajność serwera blokad, na poziomie opóźnień potrzebnych do nabywania i zwalniania blokad, oraz liczby operacji takiego nabywania/zwalniania, które można wykonać na sekundę. Aby spełnić ten wymóg, istnieje strategia komunikacji z N serwerami Redis, aby zmniejszyć opóźnienie. To strategia multipleksowania (lub „multipleksowanie dla ubogich”, w której gniazdo jest ustawiane w tryb nieblokujący, wysyła wszystkie polecenia, a następnie odczytuje polecenia później, zakładając, że czas obrotu między klientem a każdym z instancji jest podobny).

Należy jednak również wziąć pod uwagę kwestę długoterminowego przechowywania danych, jeśli chcemy stworzyć model z pewnym odzyskiwaniem po awariach.

W zasadzie, aby wyjaśnić problem, załóżmy, że konfigurujemy Redis bez długoterminowego przechowywania danych. Klient zdołał zablokować 3 z 5 instancji. Jedna z instancji, którą klient zablokował, uruchamia się ponownie, i w tym momencie pojawiają się ponownie 3 instancje dla tego samego zasobu, który możemy zablokować, a inny klient może z kolei zablokować uruchomioną ponownie instancję, naruszając właściwość bezpieczeństwa, która zakłada wyłączność blokad.

Jeśli włączymy proaktywne zapisywanie danych (AOF), sytuacja nieco się poprawi. Na przykład, można uruchomić serwer, wysyłając polecenie SHUTDOWN i uruchamiając go ponownie. Ponieważ operacje wygaszenia w Redis są semantycznie realizowane w taki sposób, że czas płynie również, kiedy serwer jest wyłączony, z wszystkimi naszymi wymaganiami jest w porządku. Jest w porządku, dopóki zapewnione jest prawidłowe wyłączenie. A co w sytuacji awarii zasilania? Jeśli Redis jest skonfigurowany domyślnie, z synchronizacją fsync na dysku co sekundę, to możliwe, że po ponownym uruchomieniu stracimy nasz klucz. Teoretycznie, jeśli chcemy zagwarantować bezpieczeństwo blokad przy każdym ponownym uruchomieniu instancji, musimy włączyć fsync=always w ustawieniach długoterminowego przechowywania danych. To całkowicie zablokuje wydajność, do poziomu takich systemów CP, które są tradycyjnie stosowane do bezpiecznej realizacji rozproszonych blokad.

Jednak sytuacja jest lepsza, niż się wydaje na pierwszy rzut oka. W zasadzie bezpieczeństwo algorytmu jest zachowane, ponieważ, kiedy instancja uruchamia się ponownie po awarii, nie uczestniczy już w żadnej blokadzie aktywnej w danym momencie.

Aby to zapewnić, wystarczy upewnić się, że po awarii instancja pozostaje niedostępna przez czas nieco przekraczający maksymalny TTL, który używamy. W ten sposób poczekamy na wygaśnięcie i automatyczne zwolnienie wszystkich kluczy, które były aktywne w momencie awarii.

Dzięki użyciu opóźnionych restartów, możliwe jest osiągnięcie bezpieczeństwa nawet bez jakiejkolwiek długoterminowej trwałości w Redis. Należy jednak zauważyć, że może to prowadzić do kary za naruszenie dostępności. Na przykład, w przypadku awarii większości instancji, system stanie się globalnie niedostępny na czas TTL (i w tym czasie nie będzie można zablokować żadnego zasobu).

Zwiększamy dostępność algorytmu: przedłużamy blokadę

Jeśli prace wykonywane przez klientów składają się z drobnych etapów, możliwe jest skrócenie domyślnego czasu działania blokady i wdrożenie mechanizmu przedłużania blokad. W zasadzie, jeśli klient jest zajęty obliczeniami, a wartość czasu działania blokady niebezpiecznie się zmniejsza, można wysłać do wszystkich instancji skrypt Lua przedłużający TTL klucza, jeśli klucz nadal istnieje, a jego wartość pozostaje losowa, uzyskana w momencie przejęcia blokady.

Klient powinien uważać blokadę za ponownie nabytą tylko wtedy, gdy uda mu się zablokować większość instancji w czasie działania.

Rzeczywiście, technicznie algorytm się nie zmienia, dlatego maksymalna liczba ponownych prób nabycia blokad powinna być ograniczona, w przeciwnym razie właściwości dostępności będą naruszane.

Źródło: habr.com