Tak wygląda redundancja
Kody redundancji* są szeroko stosowane w systemach komputerowych w celu zwiększenia niezawodności przechowywania danych. W Yandex są wykorzystywane w wielu projektach. Na przykład użycie kodów nadmiarowych zamiast replikacji w naszej wewnętrznej pamięci obiektowej pozwala zaoszczędzić miliony bez utraty niezawodności. Jednak pomimo ich powszechnego stosowania jasne opisy działania kodów nadmiarowych są bardzo rzadkie. Ci, którzy chcą zrozumieć, stają przed w przybliżeniu następującymi kwestiami (od ):
Nazywam się Vadim, w Yandex opracowuję MDS do wewnętrznej pamięci obiektowej. W tym artykule opiszę prostymi słowami teoretyczne podstawy kodów redundancyjnych (kody Reeda-Solomona i LRC). Powiem ci, jak to działa, bez skomplikowanej matematyki i rzadkich terminów. Na koniec podam przykłady wykorzystania kodów redundancyjnych w Yandex.
Nie będę szczegółowo omawiał szeregu szczegółów matematycznych, ale podam linki dla tych, którzy chcą zejść głębiej. Zwrócę też uwagę, że niektóre definicje matematyczne mogą nie być ścisłe, gdyż artykuł nie jest przeznaczony dla matematyków, ale dla inżynierów, którzy chcą zrozumieć istotę zagadnienia.
* W literaturze anglojęzycznej kody nadmiarowe są często nazywane kodami kasowania.
1. Istota kodów redundancyjnych
Istota wszystkich kodów redundancji jest niezwykle prosta: przechowuj (lub przesyłaj) dane tak, aby nie zostały utracone w przypadku wystąpienia błędów (awarii dysku, błędów przesyłania danych itp.).
W większości* kodów redundancji dane są podzielone na n bloków danych, dla których zliczanych jest m bloków kodów redundancji, co daje w sumie n + m bloków. Kody redundancji są skonstruowane w taki sposób, że n bloków danych można odzyskać przy użyciu tylko części n + m bloków. Następnie rozważymy tylko kody redundancji blokowej, czyli takie, w których dane są podzielone na bloki.
Aby odzyskać wszystkie n bloków danych, musisz mieć co najmniej n z n + m bloków, ponieważ nie możesz uzyskać n bloków, mając tylko n-1 blok (w tym przypadku musiałbyś wziąć 1 blok „z cienkiego powietrze"). Czy n losowych bloków n + m bloków wystarczy do odzyskania wszystkich danych? Zależy to od rodzaju kodów redundancji, na przykład kody Reeda-Solomona pozwalają odzyskać wszystkie dane za pomocą dowolnych n bloków, ale kody redundancji LRC nie zawsze to umożliwiają.
Przechowywanie danych
W systemach przechowywania danych z reguły każdy z bloków danych i bloków kodu redundancyjnego zapisywany jest na osobnym dysku. Następnie, jeśli dowolny dysk ulegnie awarii, oryginalne dane nadal będą mogły zostać przywrócone i odczytane. Dane można odzyskać nawet w przypadku awarii kilku dysków jednocześnie.
Transfer danych
Kody redundancji można wykorzystać do niezawodnej transmisji danych w zawodnej sieci. Przesyłane dane dzielone są na bloki i dla nich wyliczane są kody redundancji. Zarówno bloki danych, jak i bloki kodu redundancyjnego są przesyłane przez sieć. Jeżeli błędy wystąpią w dowolnych blokach (do określonej liczby bloków), dane będą nadal mogły być przesyłane w sieci bez błędów. Na przykład kody Reeda-Solomona służą do przesyłania danych optycznymi liniami komunikacyjnymi i komunikacją satelitarną.
* Istnieją również kody redundancyjne, w których dane nie są podzielone na bloki, takie jak kody Hamminga i kody CRC, które są powszechnie stosowane do transmisji danych w sieciach Ethernet. Są to kody do kodowania korygującego błędy, mają za zadanie wykrywać błędy, a nie je korygować (kod Hamminga pozwala również na częściową korektę błędów).
2. Kody Reeda-Salomona
Kody Reeda-Solomona to jeden z najczęściej używanych kodów nadmiarowych, wynaleziony w latach sześćdziesiątych XX wieku i po raz pierwszy szeroko zastosowany w latach osiemdziesiątych XX wieku do masowej produkcji płyt kompaktowych.
Istnieją dwa kluczowe pytania dotyczące zrozumienia kodów Reeda-Solomona: 1) jak tworzyć bloki kodów redundancyjnych; 2) jak odzyskać dane za pomocą bloków kodu redundancyjnego. Znajdźmy na nie odpowiedzi.
Dla uproszczenia założymy dalej, że n=6 i m=4. Inne schematy są rozpatrywane przez analogię.
Jak tworzyć bloki kodu nadmiarowego
Każdy blok kodów redundancji jest liczony niezależnie od pozostałych. Do zliczenia każdego bloku wykorzystuje się wszystkie n bloków danych. Na poniższym schemacie X1-X6 to bloki danych, P1-P4 to bloki kodu redundancji.
Wszystkie bloki danych muszą mieć ten sam rozmiar, a do wyrównania można używać bitów zerowych. Powstałe bloki kodu nadmiarowego będą miały ten sam rozmiar co bloki danych. Wszystkie bloki danych są podzielone na słowa (na przykład 16 bitów). Powiedzmy, że podzieliliśmy bloki danych na k słów. Następnie wszystkie bloki kodów redundancyjnych zostaną również podzielone na k słów.
Aby policzyć i-te słowo każdego bloku redundancji, użyte zostaną i-te słowa wszystkich bloków danych. Zostaną one obliczone według następującego wzoru:
Tutaj wartości x są słowami bloków danych, p są słowami bloków kodu redundancji, wszystkie alfa, beta, gamma i delta są specjalnie wybranymi liczbami, które są takie same dla wszystkich i. Trzeba od razu powiedzieć, że wszystkie te wartości nie są zwykłymi liczbami, ale elementami pola Galois; operacje +, -, *, / nie są operacjami znanymi nam wszystkim, ale specjalnymi operacjami wprowadzonymi na elementach Galois pole.
Dlaczego pola Galois są potrzebne?
Wydawałoby się, że wszystko jest proste: dzielimy dane na bloki, bloki na słowa, używając słów bloków danych liczymy słowa bloków kodu redundancyjnego - otrzymujemy bloki kodu redundancyjnego. Generalnie wygląda to tak, ale diabeł tkwi w szczegółach:
- Jak wspomniano powyżej, rozmiar słowa jest stały i w naszym przykładzie wynosi 16 bitów. Powyższe wzory dla kodów Reeda-Solomona są takie, że w przypadku użycia zwykłych liczb całkowitych wynik obliczenia p może nie być możliwy do przedstawienia przy użyciu słowa o prawidłowym rozmiarze.
- Podczas odzyskiwania danych powyższe wzory będą traktowane jako układ równań, które należy rozwiązać, aby odzyskać dane. Podczas rozwiązywania problemu może zaistnieć konieczność wzajemnego dzielenia liczb całkowitych, w wyniku czego otrzymana zostanie liczba rzeczywista, której nie będzie można dokładnie przedstawić w pamięci komputera.
Problemy te uniemożliwiają użycie liczb całkowitych w kodach Reeda-Solomona. Rozwiązanie problemu jest oryginalne, można je opisać w następujący sposób: wymyślmy specjalne liczby, które można przedstawić za pomocą słów o wymaganej długości (na przykład 16 bitów) oraz wynik wykonania wszystkich operacji, na których (dodanie , odejmowanie, mnożenie, dzielenie) będą również prezentowane w pamięci komputera za pomocą słów o wymaganej długości.
Takie „specjalne” liczby są od dawna badane przez matematykę i nazywane są polami. Pole to zbiór elementów, dla których zdefiniowane są operacje dodawania, odejmowania, mnożenia i dzielenia.
Pola Galois* to pola, dla których istnieje unikalny wynik każdej operacji (+, -, *, /) dla dowolnych dwóch elementów pola. Pola Galois można konstruować dla liczb będących potęgami 2: 2, 4, 8, 16 itd. (właściwie potęgi dowolnej liczby pierwszej p, ale w praktyce interesują nas tylko potęgi 2). Przykładowo dla słów 16-bitowych jest to pole zawierające 65 536 elementów, dla każdej pary można znaleźć wynik dowolnej operacji (+, -, *, /). Wartości x, p, alfa, beta, gamma, delta z powyższych równań będą uważane za elementy pola Galois do obliczeń.
Mamy zatem układ równań, za pomocą którego możemy konstruować bloki kodów redundancyjnych pisząc odpowiedni program komputerowy. Używając tego samego układu równań, możesz odzyskać dane.
* To nie jest ścisła definicja, ale raczej opis.
Jak odzyskać dane
Przywrócenie jest konieczne, gdy brakuje niektórych bloków n + m. Mogą to być zarówno bloki danych, jak i bloki kodu redundancyjnego. Brak bloków danych i/lub bloków kodu redundancji będzie oznaczać, że odpowiadające im zmienne x i/lub p są nieznane w powyższych równaniach.
Równania kodów Reeda-Solomona można postrzegać jako układ równań, w którym wszystkie wartości alfa, beta, gamma, delta są stałymi, wszystkie x i p odpowiadające dostępnym blokom są znanymi zmiennymi, a pozostałe x i p są nieznane.
Przykładowo, jeśli nie będą dostępne bloki danych 1, 2, 3 i blok kodu redundancji 2, to dla i-tej grupy słów powstanie następujący układ równań (niewiadome zaznaczono na czerwono):
Mamy układ 4 równań z 4 niewiadomymi, co oznacza, że możemy go rozwiązać i przywrócić dane!
Z tego układu równań wynika szereg wniosków dotyczących odzyskiwania danych dla kodów Reeda-Solomona (n bloków danych, m bloków kodu redundancyjnego):
- Dane można odzyskać w przypadku utraty dowolnych m bloków lub mniej. Jeśli utracone zostanie m+1 lub więcej bloków, danych nie będzie można odtworzyć: nie da się rozwiązać układu m równań z m + 1 niewiadomymi.
- Aby odzyskać chociaż jeden blok danych, należy użyć dowolnych n pozostałych bloków i można użyć dowolnego z kodów redundancji.
Co jeszcze musisz wiedzieć
W powyższym opisie omijam szereg istotnych kwestii, które wymagają głębszego zgłębienia matematyki. W szczególności nie mam na myśli następujących kwestii:
- Układ równań kodów Reeda-Solomona musi mieć (unikalne) rozwiązanie dla dowolnej kombinacji niewiadomych (nie więcej niż m niewiadomych). W oparciu o to wymaganie wybierane są wartości alfa, beta, gamma i delta.
- Układ równań musi dać się automatycznie skonstruować (w zależności od tego, które bloki są niedostępne) i rozwiązać.
- Musimy zbudować pole Galois: dla danego rozmiaru słowa, być w stanie znaleźć wynik dowolnej operacji (+, -, *, /) dla dowolnych dwóch elementów.
Na końcu artykułu znajdują się odniesienia do literatury dotyczącej tych istotnych zagadnień.
Wybór n i m
Jak wybrać n i m w praktyce? W praktyce w systemach przechowywania danych stosuje się kody redundancyjne, aby zaoszczędzić miejsce, dlatego m jest zawsze wybierane jako mniejsze niż n. Ich konkretne wartości zależą od szeregu czynników, m.in.:
- Niezawodność przechowywania danych. Im większe m, tym większa liczba awarii dysku, które można przetrwać, to znaczy wyższa niezawodność.
- Nadmiarowa pamięć masowa. Im wyższy stosunek m/n, tym większa będzie redundancja pamięci i tym droższy będzie system.
- Zapytaj o czas przetwarzania. Im większa suma n + m, tym dłuższy będzie czas odpowiedzi na żądania. Ponieważ odczyt danych (podczas odzyskiwania) wymaga odczytania n bloków przechowywanych na n różnych dyskach, o czasie odczytu będzie decydował najwolniejszy dysk.
Ponadto przechowywanie danych w kilku DC nakłada dodatkowe ograniczenia na wybór n i m: jeśli 1 DC jest wyłączony, dane muszą być nadal dostępne do odczytu. Przykładowo przy przechowywaniu danych na 3 DC musi być spełniony warunek: m >= n/2, w przeciwnym wypadku może dojść do sytuacji, że dane nie będą możliwe do odczytania przy wyłączonym 1 DC.
3. LRC – Lokalne kody rekonstrukcji
Aby odzyskać dane za pomocą kodów Reeda-Solomona, musisz użyć n dowolnych bloków danych. Jest to bardzo istotna wada w przypadku rozproszonych systemów przechowywania danych, ponieważ aby przywrócić dane na jednym uszkodzonym dysku, trzeba będzie odczytać dane z większości pozostałych, co spowoduje duże dodatkowe obciążenie dysków i sieci.
Najczęstsze błędy to niedostępność jednego bloku danych na skutek awarii lub przeciążenia jednego dysku. Czy w tym (najczęstszym) przypadku można w jakiś sposób zmniejszyć nadmierne obciążenie związane z odzyskiwaniem danych? Okazuje się, że można: istnieją specjalnie do tego celu przygotowane kody redundancji LRC.
LRC (Local Reconstruction Codes) to kody nadmiarowości opracowane przez firmę Microsoft do użytku w usłudze Windows Azure Storage. Idea LRC jest tak prosta, jak to tylko możliwe: podziel wszystkie bloki danych na dwie (lub więcej) grupy i odczytaj część bloków kodu redundancyjnego dla każdej grupy osobno. Wtedy część bloków kodu redundancji będzie zliczana przy użyciu wszystkich bloków danych (w LRC nazywane są to kodami globalnej redundancji), a część - przy użyciu jednej z dwóch grup bloków danych (nazywa się je lokalnymi kodami redundancji).
LRC jest oznaczony trzema liczbami: nrl, gdzie n jest liczbą bloków danych, r jest liczbą bloków kodu globalnej redundancji, l jest liczbą bloków kodu lokalnej redundancji. Aby odczytać dane, gdy jeden blok danych jest niedostępny, należy odczytać tylko n/l bloków - to l razy mniej niż w kodach Reeda-Solomona.
Rozważmy na przykład schemat LRC 6-2-2. X1–X6 — 6 bloków danych, P1, P2 — 2 bloki globalnej redundancji, P3, P4 — 2 bloki lokalnej redundancji.
Bloki kodu redundancyjnego P1, P2 są liczone przy użyciu wszystkich bloków danych. Blok kodu redundancyjnego P3 - z wykorzystaniem bloków danych X1-X3, blok kodu redundancyjnego P4 - z wykorzystaniem bloków danych X4-X6.
Reszta odbywa się w LRC, analogicznie do kodów Reeda-Solomona. Równania do zliczania słów bloków kodu redundancyjnego będą następujące:
Aby wybrać liczby alfa, beta, gamma, delta należy spełnić szereg warunków gwarantujących możliwość odzyskania danych (czyli rozwiązania układu równań). Więcej o nich przeczytasz w .
Również w praktyce operacja XOR służy do obliczania lokalnych kodów redundancji P3, P4.
Z układu równań dla LRC wynika szereg wniosków:
- Aby odzyskać dowolny 1 blok danych, wystarczy odczytać n/l bloków (w naszym przykładzie n/2).
- Jeśli bloki r + l są niedostępne, a wszystkie bloki znajdują się w jednej grupie, danych nie można przywrócić. Łatwo to wyjaśnić na przykładzie. Niech bloki X1–X3 i P3 będą niedostępne: są to bloki r + l z tej samej grupy, w naszym przypadku 4. Mamy wówczas układ 3 równań z 4 niewiadomymi, których nie można rozwiązać.
- We wszystkich pozostałych przypadkach niedostępności bloków r+l (gdy dostępny jest przynajmniej jeden blok z każdej grupy) dane w LRC można odtworzyć.
Tym samym LRC przewyższa kody Reeda-Solomona w odzyskiwaniu danych po pojedynczych błędach. W kodach Reeda-Solomona, aby odzyskać choćby jeden blok danych, należy użyć n bloków, natomiast w kodach LRC, aby odzyskać jeden blok danych, wystarczy użyć n/l bloków (w naszym przykładzie n/2). Z drugiej strony LRC ustępuje kodom Reeda-Solomona pod względem maksymalnej liczby dopuszczalnych błędów. W powyższych przykładach kody Reeda-Solomona mogą odzyskać dane w przypadku dowolnych 4 błędów, a w przypadku LRC istnieją 2 kombinacje 4 błędów, gdy danych nie można odzyskać.
To, co jest ważniejsze, zależy od konkretnej sytuacji, ale często oszczędności wynikające z nadmiernego obciążenia, jakie zapewnia LRC, przewyższają nieco mniej niezawodne przechowywanie.
4. Inne kody redundancji
Oprócz kodów Reeda-Solomona i LRC istnieje wiele innych kodów redundancji. Różne kody redundancji wykorzystują inną matematykę. Oto kilka innych kodów nadmiarowości:
- Kod redundancji przy użyciu operatora XOR. Operacja XOR wykonywana jest na n blokach danych i uzyskuje się 1 blok kodów redundancji, czyli schemat n+1 (n bloków danych, 1 kod redundancji). Stosuje się w , gdzie bloki danych i kody redundancji są cyklicznie zapisywane na wszystkich dyskach macierzy.
- Algorytm parzysty-nieparzysty oparty na operacji XOR. Umożliwia zbudowanie 2 bloków kodów redundancyjnych, czyli schematu n+2.
- Algorytm STAR oparty na operacji XOR. Umożliwia zbudowanie 3 bloków kodów redundancyjnych, czyli schematu n+3.
- Kody piramidowe to kolejne kody nadmiarowe firmy Microsoft.
5. Użyj w Yandex
Wiele projektów infrastrukturalnych Yandex wykorzystuje kody redundancji do niezawodnego przechowywania danych. Oto kilka przykładów:
- Wewnętrzna pamięć obiektowa MDS, o której pisałem na początku artykułu.
- — System MapReduce firmy Yandex.
- (Yandex DataBase) - rozproszona baza danych newSQL.
MDS wykorzystuje kody redundancji LRC, schemat 8-2-2. Dane z kodami nadmiarowości są zapisywane na 12 różnych dyskach w różnych serwerach w 3 różnych DC: 4 serwery w każdym DC. Więcej na ten temat przeczytasz w .
YT wykorzystuje zarówno kody Reeda-Solomona (schemat 6-3), które jako pierwsze wdrożono, jak i kody redundancyjne LRC (schemat 12-2-2), przy czym preferowaną metodą przechowywania jest LRC.
YDB używa kodów redundancji parzystych i nieparzystych (Rysunek 4-2). O kodach redundancji już w YDB .
Stosowanie różnych schematów kodów redundancji wynika z różnych wymagań stawianych systemom. Na przykład w MDS dane przechowywane przy użyciu LRC są umieszczane w 3 DC jednocześnie. Ważne jest dla nas, aby dane pozostały dostępne do odczytu w przypadku awarii jednego z dowolnych DC, dlatego bloki muszą być rozmieszczone pomiędzy DC, tak aby w przypadku braku dowolnego DC liczba niedostępnych bloków była nie większa niż dopuszczalna. W schemacie 1-8-2 możesz umieścić 2 bloki w każdym DC, wtedy gdy którykolwiek DC zostanie wyłączony, 4 bloki będą niedostępne i dane będzie można odczytać. Niezależnie od tego, jaki schemat wybierzemy, umieszczając go w 4 DC, w każdym przypadku powinno być (r + l) / n >= 3, to znaczy redundancja pamięci będzie wynosić co najmniej 0,5%.
W YT sytuacja jest inna: każdy klaster YT jest w całości zlokalizowany w 1 DC (różne klastry w różnych DC), więc nie ma takiego ograniczenia. Schemat 12-2-2 zapewnia redundancję na poziomie 33%, czyli przechowywanie danych jest tańsze, a ponadto wytrzymuje do 4 jednoczesnych awarii dysku, podobnie jak schemat MDS.
Cech wykorzystania kodów redundancji w systemach przechowywania i przetwarzania danych jest znacznie więcej: niuanse odzyskiwania danych, wpływ odzyskiwania na czas wykonania zapytania, funkcje rejestrowania danych itp. O tych i innych funkcjach będę mówić osobno wykorzystania kodów redundancyjnych w praktyce, jeśli temat będzie interesujący.
6. Linki
- Seria artykułów na temat kodów Reeda-Solomona i pól Galois:
Przyglądają się bliżej matematyce w przystępnym języku. - Artykuł firmy Microsoft na temat LRC:
Część 2 krótko wyjaśnia teorię, a następnie omawia doświadczenia z LRC w praktyce. - Schemat parzysty-nieparzysty:
- Schemat STAR:
- Kody piramidy:
- Kody redundancji w MDS:
- Kody redundancji na YT:
- Kody redundancji w YDB:
Źródło: www.habr.com