ProHoster > Blog > administracja > Blokowanie rozproszone przy użyciu Redis

Blokowanie rozproszone przy użyciu Redis

Hej Habra!

Dziś zwracamy uwagę na tłumaczenie złożonego artykułu na temat wdrażania blokowania rozproszonego przy użyciu Redis i zapraszamy do dyskusji na temat perspektyw Redis. Analiza omawianego algorytmu Redlock autorstwa Martina Kleppmanna, autora książki „Aplikacje o dużym obciążeniu", dany tutaj.

Blokowanie rozproszone to bardzo przydatna metoda stosowana w wielu środowiskach, w których różne procesy muszą działać na współdzielonych zasobach w sposób wzajemnie się wykluczający.

Istnieje wiele bibliotek i postów opisujących, jak wdrożyć DLM (Distributed Lock Manager) przy użyciu Redis, ale każda biblioteka przyjmuje inne podejście, a zapewniane przez nie gwarancje są dość słabe w porównaniu z tym, co można osiągnąć przy nieco bardziej wyrafinowanym projekcie.

W tym artykule postaramy się opisać warunkowy algorytm kanoniczny, który pokazuje, jak zaimplementować blokowanie rozproszone za pomocą Redis. Porozmawiamy o algorytmie zwanym czerwony zamek, implementuje rozproszonego menedżera blokad i naszym zdaniem algorytm ten jest bezpieczniejszy niż zwykłe podejście oparte na jednej instancji. Mamy nadzieję, że społeczność to przeanalizuje, przekaże swoje uwagi i wykorzysta jako punkt wyjścia do bardziej złożonych lub alternatywnych projektów.

Wdrożenia

Zanim przejdziemy do opisu algorytmu, podajemy kilka linków do gotowych implementacji. Można je wykorzystać w celach informacyjnych.

Gwarancje bezpieczeństwa i dostępności

Zamierzamy modelować nasz projekt za pomocą zaledwie trzech właściwości, które naszym zdaniem zapewniają minimalne gwarancje potrzebne do efektywnego wykorzystania rozproszonego blokowania.

  1. Własność bezpieczeństwa: Wzajemne wykluczenie. W danym momencie tylko jeden klient może utrzymać zamek.
  2. Dostępność Właściwość A: Brak zakleszczeń. Zawsze istnieje możliwość uzyskania blokady, nawet jeśli klient, który zablokował zasób, ulegnie awarii lub wyląduje w innym segmencie dysku.
  3. Dostępność Właściwość B: Tolerancja na błędy. Dopóki działa większość węzłów Redis, klienci mogą nabywać i zwalniać blokady.

Dlaczego wdrożenie oparte na odtwarzaniu awarii nie wystarczy w tym przypadku
Aby zrozumieć co będziemy udoskonalać przeanalizujmy obecny stan rzeczy z większością rozproszonych bibliotek blokujących bazujących na Redis.

Najprostszym sposobem zablokowania zasobu za pomocą Redis jest utworzenie klucza w instancji. Zwykle klucz jest tworzony z ograniczonym czasem życia, osiąga się to za pomocą funkcji wygasania dostępnej w Redis, więc prędzej czy później ten klucz zostanie wydany (właściwość 2 na naszej liście). Gdy klient musi zwolnić zasób, usuwa klucz.

Na pierwszy rzut oka to rozwiązanie działa całkiem nieźle, jednak jest pewien problem: nasza architektura tworzy pojedynczy punkt awarii. Co się stanie, jeśli instancja Redis hosta ulegnie awarii? Dodajmy więc niewolnika! I skorzystamy z niego, jeśli prezenter będzie niedostępny. Niestety ta opcja nie jest wykonalna. Robiąc to, nie będziemy w stanie poprawnie zaimplementować właściwości wzajemnego wykluczania, której potrzebujemy dla zapewnienia bezpieczeństwa, ponieważ replikacja w Redis jest asynchroniczna.

Oczywiście w takim modelu zachodzi sytuacja wyścigu:

  1. Klient A uzyskuje blokadę na urządzeniu głównym.
  2. Urządzenie główne ulega awarii przed przesłaniem klucza do urządzenia podrzędnego.
  3. Naśladowca zostaje awansowany na lidera.
  4. Klient B uzyskuje blokadę tego samego zasobu, który A już zablokował. NARUSZENIA BEZPIECZEŃSTWA!

Czasami jest zupełnie normalne, że w szczególnych okolicznościach, takich jak awaria, wielu klientów może jednocześnie przytrzymać zamek. W takich przypadkach można zastosować rozwiązanie oparte na replikacji. W przeciwnym wypadku polecamy rozwiązanie opisane w tym artykule.

Prawidłowa implementacja z pojedynczą instancją

Zanim spróbujemy przezwyciężyć wady opisanej powyżej konfiguracji z pojedynczą instancją, zobaczmy, jak prawidłowo obsłużyć ten prosty przypadek, ponieważ to rozwiązanie faktycznie sprawdza się w aplikacjach, w których od czasu do czasu akceptowalne są warunki wyścigu, a także dlatego, że blokowanie na pojedyncza instancja służy jako podstawa używana w opisanym tutaj algorytmie rozproszonym.

Aby zdobyć blokadę, wykonaj następujące czynności:

SET resource_name my_random_value NX PX 30000

To polecenie instaluje klucz tylko wtedy, gdy jeszcze nie istnieje (opcja NX), z okresem ważności 30000 milisekund (opcja PX). Klucz jest ustawiony na „myrandomvalue" Ta wartość musi być unikatowa dla wszystkich klientów i wszystkich żądań blokady.
Zasadniczo do bezpiecznego zwolnienia blokady używana jest losowa wartość, a skrypt mówi Redisowi: usuń klucz tylko wtedy, gdy istnieje, a przechowywana w nim wartość jest dokładnie taka, jakiej oczekiwano. Osiąga się to za pomocą następującego skryptu Lua:

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

Jest to ważne, aby zapobiec usunięciu blokady trzymanej przez innego klienta. Na przykład klient może nabyć blokadę, następnie zostać zablokowanym w jakiejś operacji, która trwa dłużej niż pierwsza blokada (aby klucz miał czas na wygaśnięcie), a później usunąć blokadę nałożoną przez innego klienta.
Używanie prostego polecenia DEL jest niebezpieczne, ponieważ klient może usunąć blokadę trzymaną przez innego klienta. Natomiast przy zastosowaniu powyższego skryptu każda blokada jest „podpisana” losowym ciągiem znaków, zatem tylko klient, który ją wcześniej umieścił, może ją usunąć.

Jaki powinien być ten losowy ciąg? Zgaduję, że powinno to być 20 bajtów z /dev/urandom, ale możesz znaleźć tańsze sposoby, aby uczynić ciąg wystarczająco unikalnym dla swoich celów. Na przykład dobrze byłoby zaszczepić RC4 za pomocą /dev/urandom, a następnie wygenerować z niego pseudolosowy strumień. Prostsze rozwiązanie polega na połączeniu czasu uniksowego w rozdzielczości mikrosekundowej oraz identyfikatora klienta; nie jest to tak bezpieczne, ale prawdopodobnie w większości kontekstów spełnia swoje zadanie.

Czas, którego używamy jako miary żywotności klucza, nazywany jest „żywotnością zamka”. Wartość ta oznacza zarówno czas, po którym blokada zostanie automatycznie zwolniona, jak i czas, jaki klient musi ukończyć, zanim inny klient będzie mógł z kolei zablokować ten zasób, bez faktycznego naruszania gwarancji wzajemnego wykluczenia. Gwarancja ta ograniczona jest jedynie pewnym oknem czasowym, które rozpoczyna się od momentu zakupu zamka.

Omówiliśmy więc dobry sposób na zdobycie i zwolnienie blokady. System (jeśli mówimy o systemie nierozproszonym składającym się z jednej i zawsze dostępnej instancji) jest bezpieczny. Rozszerzmy tę koncepcję na system rozproszony, gdzie nie mamy takich gwarancji.

Algorytm Redlocka

Rozproszona wersja algorytmu zakłada, że ​​mamy N wzorców Redis. Węzły te są od siebie całkowicie niezależne, dlatego nie stosujemy replikacji ani żadnego innego ukrytego systemu koordynacji. Omówiliśmy już, jak bezpiecznie uzyskać i zwolnić blokadę w pojedynczej instancji. Przyjmujemy za pewnik, że algorytm pracując z pojedynczą instancją będzie korzystał właśnie z tej metody. W naszych przykładach ustawiliśmy N na 5, co jest rozsądną wartością. Dlatego będziemy musieli użyć 5 wzorców Redis na różnych komputerach lub maszynach wirtualnych, aby mieć pewność, że działają one w dużej mierze niezależnie od siebie.

W celu uzyskania blokady Klient wykonuje następujące operacje:

  1. Pobiera bieżący czas w milisekundach.
  2. Próbuje sekwencyjnie uzyskać blokadę na wszystkich N instancjach, używając we wszystkich przypadkach tej samej nazwy klucza i losowych wartości. Na etapie 2, gdy klient konfiguruje blokadę dla poszczególnych instancji, wykorzystuje do jej uzyskania opóźnienie wystarczająco krótkie w porównaniu z czasem, po którym blokada zostaje automatycznie zwolniona. Na przykład, jeśli czas trwania blokady wynosi 10 sekund, opóźnienie może mieścić się w zakresie ~5-50 milisekund. Eliminuje to sytuację, w której klient mógłby przez długi czas pozostawać zablokowany próbując dotrzeć do uszkodzonego węzła Redis: w przypadku niedostępności instancji staramy się jak najszybciej połączyć z inną instancją.
  3. Aby wziąć blokadę, klient oblicza, ile czasu upłynęło; W tym celu odejmuje od rzeczywistej wartości czasu znacznik czasu uzyskany w kroku 1. Wtedy i tylko wtedy, gdy klientowi udało się uzyskać blokadę w większości przypadków (co najmniej 3) oraz całkowity czas potrzebny na uzyskania blokady, krócej niż czas trwania blokady, uznaje się, że blokada została uzyskana.
  4. Jeżeli blokada została uzyskana, za czas trwania blokady przyjmuje się pierwotny czas trwania blokady pomniejszony o czas, który upłynął obliczony w kroku 3.
  5. Jeśli z jakiegoś powodu klientowi nie uda się uzyskać blokady (albo nie był w stanie zablokować instancji N/2+1, albo czas trwania blokady był ujemny), wówczas spróbuje odblokować wszystkie instancje (nawet te, o których myślał, że nie może zablokować) ).

Czy algorytm jest asynchroniczny?

Algorytm ten opiera się na założeniu, że choć nie ma zsynchronizowanego zegara, na którym pracowałyby wszystkie procesy, to czas lokalny w każdym procesie wciąż płynie w przybliżeniu w tym samym tempie, a błąd jest niewielki w porównaniu do całkowitego czasu, po którym następuje zamknięcie zamka. automatycznie zwolniony. Założenie to jest bardzo podobne do sytuacji typowej dla zwykłych komputerów: każdy komputer ma zegar lokalny i zazwyczaj możemy liczyć na to, że różnica czasu pomiędzy różnymi komputerami jest niewielka.

W tym miejscu musimy dokładniej sformułować naszą zasadę wzajemnego wykluczania: wzajemne wykluczenie jest gwarantowane tylko wtedy, gdy klient posiadający zamek wyjdzie w czasie ważności zamka (ta wartość uzyskana w kroku 3), minus trochę więcej czasu (w sumie kilka milisekundy, aby skompensować różnicę czasu między procesami).

Poniższy ciekawy artykuł mówi więcej o takich systemach, które wymagają koordynacji przedziałów czasowych: Dzierżawy: wydajny, odporny na awarie mechanizm zapewniający spójność rozproszonej pamięci podręcznej plików.

Ponów próbę w przypadku niepowodzenia

Jeśli klientowi nie uda się uzyskać blokady, musi spróbować ponownie po losowym opóźnieniu; ma to na celu desynchronizację wielu klientów próbujących uzyskać blokadę tego samego zasobu w tym samym czasie (co może prowadzić do sytuacji „rozdzielenia mózgu”, w której nie ma zwycięzców). Ponadto im szybciej klient próbuje uzyskać blokadę w większości instancji Redis, tym węższe jest okno, w którym może wystąpić sytuacja podziału mózgu (i tym mniejsza jest potrzeba ponawiania prób). Dlatego w idealnym przypadku klient powinien próbować wysłać polecenia SET do N instancji jednocześnie, korzystając z multipleksowania.

Warto w tym miejscu podkreślić, jak ważne jest, aby klienci, którym nie udało się zdobyć większości blokad, zwolnili (częściowo) zdobyte blokady, aby nie musieli czekać na wygaśnięcie klucza, zanim będzie można ponownie zdobyć blokadę na zasobie (chociaż jeśli nastąpi fragmentacja sieci i klient straci kontakt z instancjami Redis, wówczas będziesz musiał zapłacić karę za dostępność w oczekiwaniu na wygaśnięcie klucza).

Zwolnij blokadę

Zwolnienie blokady to prosta operacja, która wymaga po prostu odblokowania wszystkich instancji, niezależnie od tego, czy klient pomyślnie zablokował konkretną instancję.

Względy bezpieczeństwa

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

Na początek załóżmy, że klientowi udało się uzyskać blokadę w większości przypadków. Każda instancja będzie zawierać klucz o tym samym czasie życia dla wszystkich. Jednak każdy z tych kluczy został zainstalowany w innym czasie, więc wygasną w różnym czasie. Jeżeli jednak pierwszy klucz został zainstalowany w czasie nie gorszym niż T1 (czas, który wybieramy przed skontaktowaniem się z pierwszym serwerem), a ostatni klucz został zainstalowany w czasie nie gorszym niż T2 (czas, w którym otrzymano odpowiedź z ostatniego serwera), wówczas mamy pewność, że przynajmniej pierwszy klucz z zestawu, który wygasa, przetrwa przynajmniej MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Wszystkie pozostałe klucze wygasną później, więc możemy być pewni, że wszystkie klucze będą jednocześnie ważne przynajmniej przez ten czas.

W czasie, gdy większość kluczy pozostaje ważna, inny klient nie będzie mógł uzyskać blokady, ponieważ operacje N/2+1 SET NX nie mogą się powieść, jeśli istnieją już klucze N/2+1. Zatem raz nabyty zamek nie jest już możliwy do ponownego nabycia w tym samym momencie (naruszałoby to zasadę wzajemnego wykluczania).
Chcemy jednak mieć pewność, że wielu klientów próbujących uzyskać blokadę w tym samym czasie nie zakończy się sukcesem w tym samym czasie.

Jeśli klient zablokował większość instancji na mniej więcej lub dłużej niż maksymalny czas trwania blokady, uzna blokadę za nieważną i odblokuje instancje. Zatem pod uwagę należy wziąć jedynie przypadek, w którym klientowi udało się zablokować większość instancji w czasie krótszym niż termin ważności. W tym przypadku, jeśli chodzi o powyższą argumentację, w czasie MIN_VALIDITY żaden klient nie powinien mieć możliwości ponownego zdobycia zamka. Dlatego wielu klientów będzie mogło blokować instancje N/2+1 w tym samym czasie (który kończy się na końcu etapu 2) tylko wtedy, gdy czas zablokowania większości będzie większy niż czas TTL, co powoduje, że blokada jest nieważna.

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

Rozważania dotyczące dostępności

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

  1. Automatycznie zwalniaj blokady (po wygaśnięciu kluczy): klucze będą w końcu ponownie dostępne i można ich używać do blokad.
  2. Fakt, że klienci zazwyczaj pomagają sobie nawzajem, usuwając zamki, gdy żądany zamek nie został zdobyty lub został zdobyty, a praca została zakończona; więc prawdopodobnie nie będziemy musieli czekać na wygaśnięcie ważności kluczy, aby ponownie kupić zamek.
  3. Fakt, że gdy klient musi ponowić próbę uzyskania blokady, czeka stosunkowo dłużej niż okres wymagany do uzyskania większości blokad. Zmniejsza to prawdopodobieństwo wystąpienia sytuacji rozszczepienia mózgu podczas rywalizacji o zasoby.

Jednakże istnieje kara za dostępność równa TTL segmentów sieci, więc jeśli istnieją sąsiadujące segmenty, kara może być nieokreślona. Dzieje się tak za każdym razem, gdy klient uzyskuje blokadę, a następnie przechodzi do innego segmentu, zanim będzie mógł ją zwolnić.

W zasadzie, biorąc pod uwagę nieskończoną liczbę sąsiadujących segmentów sieci, system może pozostać niedostępny przez nieskończony okres czasu.

Wydajność, przełączanie awaryjne i fsync

Wiele osób korzysta z Redis, ponieważ potrzebują dużej wydajności serwera blokad pod względem opóźnień wymaganych do uzyskania i zwolnienia blokad oraz liczby przejęć/zwolnień, które można wykonać na sekundę. Aby spełnić to wymaganie, istnieje strategia komunikacji z serwerami N Redis w celu zmniejszenia opóźnień. Jest to strategia multipleksowania (lub „multipleksowania biedaka”, w której gniazdo jest przełączane w tryb nieblokujący, wysyła wszystkie polecenia, a następnie je odczytuje, zakładając, że czas podróży w obie strony między klientem a każdą instancją jest podobny) .

Musimy jednak wziąć pod uwagę także względy związane z długotrwałym przechowywaniem danych, jeśli chcemy stworzyć model zapewniający niezawodne odtwarzanie po awariach.

W zasadzie, żeby rozjaśnić kwestię, załóżmy, że konfigurujemy Redisa bez długoterminowego przechowywania danych. Klientowi udaje się zablokować 3 z 5 instancji. Jedna z instancji, którą klient zdołał zablokować, zostaje zrestartowana i w tym momencie są ponownie 3 instancje dla tego samego zasobu, które możemy zablokować, a inny klient może z kolei zablokować zrestartowaną instancję, naruszając właściwość bezpieczeństwa, która zakłada wyłączność zamków.

Jeśli włączysz transmisję danych z wyprzedzeniem (AOF), sytuacja nieznacznie się poprawi. Na przykład możesz wypromować serwer, wysyłając polecenie SHUTDOWN i uruchamiając go ponownie. Ponieważ operacje wygaśnięcia w Redis są semantycznie zaimplementowane w taki sposób, że czas płynie nawet wtedy, gdy serwer jest wyłączony, wszystkie nasze wymagania są w porządku. Jest to normalne, o ile zapewnione jest normalne wyłączenie. Co zrobić w przypadku przerw w dostawie prądu? Jeśli domyślnie skonfigurowany jest Redis, z synchronizacją fsync na dysku co sekundę, to możliwe, że po ponownym uruchomieniu nie będziemy mieli naszego klucza. Teoretycznie, jeśli chcemy zagwarantować bezpieczeństwo blokady podczas dowolnego restartu instancji, powinniśmy ją włączyć fsync=always w ustawieniach długoterminowego przechowywania danych. To całkowicie zabije wydajność, aż do poziomu systemów CP, które są tradycyjnie używane do bezpiecznego wdrażania rozproszonych blokad.

Ale sytuacja jest lepsza, niż się wydaje na pierwszy rzut oka. W zasadzie bezpieczeństwo algorytmu zostaje zachowane, ponieważ po ponownym uruchomieniu instancji po awarii nie uczestniczy ona już w żadnej aktualnie aktywnej blokadzie.

Aby to zapewnić wystarczy zadbać o to, aby po awarii instancja pozostała niedostępna przez okres czasu nieco przekraczający maksymalny TTL jaki stosujemy. W ten sposób poczekamy do daty wygaśnięcia i automatycznego zwolnienia wszystkich kluczy, które były aktywne w momencie awarii.

Stosując opóźnione ponowne uruchomienie, w zasadzie możliwe jest osiągnięcie bezpieczeństwa nawet w przypadku braku długoterminowej trwałości w Redis. Należy jednak pamiętać, że może to skutkować karą pieniężną za naruszenie dostępności. Na przykład, jeśli większość instancji ulegnie awarii, system stanie się globalnie niedostępny dla TTL (i w tym czasie nie będzie można blokować żadnych zasobów).

Zwiększamy dostępność algorytmu: rozszerzamy blokowanie

Jeśli praca wykonywana przez klientów składa się z małych kroków, istnieje możliwość skrócenia domyślnego czasu trwania blokady i wdrożenia mechanizmu przedłużania blokad. W zasadzie, jeśli klient jest zajęty obliczeniami, a wartość wygaśnięcia blokady jest niebezpiecznie niska, możesz wysłać do wszystkich instancji skrypt Lua, który przedłuży TTL klucza, jeśli klucz nadal istnieje, a jego wartość jest nadal wartością losową uzyskaną podczas zamek został zakupiony.

Klient powinien rozważyć ponowne nabycie blokady tylko wtedy, gdy udało mu się zablokować większość instancji w okresie ważności.

To prawda, że ​​​​technicznie algorytm się nie zmienia, więc maksymalna liczba powtarzających się prób uzyskania blokad musi być ograniczona, w przeciwnym razie naruszone zostaną właściwości dostępności.

Źródło: www.habr.com

Dodaj komentarz