Tak wygląda nadmiarowość

Kody nadmiarowości* są szeroko stosowane w systemach komputerowych w celu zwiększenia niezawodności przechowywania danych. W Yandexie wykorzystuje się je w wielu projektach. Na przykład, zastosowanie kodów nadmiarowości zamiast replikacji w naszym wewnętrznym systemie przechowywania obiektów oszczędza miliony bez obniżania niezawodności. Mimo szerokiego zastosowania, zrozumiałe opisy działania kodów nadmiarowości są bardzo rzadkie. Osoby chcące się z tym zapoznać napotykają na mniej więcej to (z Wikipedii):

Nazywam się Wadim, w Yandexie zajmuję się opracowaniem wewnętrznego systemu przechowywania obiektów MDS. W tym artykule prosto wyjaśnię teoretyczne podstawy kodów nadmiarowości (kodów Reeda-Solomona i LRC). Opowiem, jak to działa, bez skomplikowanej matematyki i rzadkich terminów. Na końcu podam przykłady zastosowania kodów nadmiarowości w Yandexie.

Nie będę szczegółowo omawiać szeregu matematycznych detali, ale podam linki dla tych, którzy chcą zgłębić temat. Również zauważam, że niektóre definicje matematyczne mogą być niedokładne, ponieważ artykuł jest przeznaczony nie dla matematyków, lecz dla inżynierów, którzy chcą zrozumieć istotę problemu.

* W literaturze anglojęzycznej kody nadmiarowości często nazywane są erasure codes.

1. Istota kodów nadmiarowości

Istota wszystkich kodów nadmiarowości jest niezwykle prosta: przechowywać (lub przesyłać) dane w taki sposób, aby nie zniknęły w przypadku wystąpienia błędów (awarii dysków, błędów transmisji danych itp.).

W większości* kodów nadmiarowości dane dzieli się na n bloków danych, dla których liczy się m bloków kodów nadmiarowości, co daje łącznie n + m bloków. Kody nadmiarowości są konstruowane w taki sposób, aby można było odzyskać n bloków danych, używając tylko części bloków z n + m. Następnie rozważymy tylko bloki kodów nadmiarowości, czyli takie, w których dane dzielone są na bloki.

Aby przywrócić wszystkie n bloków danych, konieczne jest posiadanie przynajmniej n z n + m bloków, ponieważ nie można uzyskać n bloków mając tylko n-1 blok (w takim przypadku musiałby być wzięty 1 blok „z powietrza”). Czy wystarczą n dowolnych bloków z n + m bloków do przywrócenia wszystkich danych? Zależy to od rodzaju kodów nadmiarowych, na przykład kody Reeda-Solomona pozwalają na przywrócenie wszystkich danych za pomocą dowolnych n bloków, podczas gdy kody LRC — nie zawsze.

Przechowywanie danych

W systemach przechowywania danych zazwyczaj każdy z bloków danych i bloków kodów nadmiarowych jest zapisywany na oddzielnym dysku. W przypadku awarii dowolnego dysku, oryginalne dane wciąż można będzie przywrócić i odczytać. Dane można będzie przywrócić nawet przy jednoczesnej awarii kilku dysków.

Przesyłanie danych

Kody nadmiarowe można wykorzystać do niezawodnego przesyłania danych w zawodnej sieci. Przesyłane dane dzieli się na bloki, dla których oblicza się kody nadmiarowe. Po sieci przesyłane są zarówno bloki danych, jak i bloki kodów nadmiarowych. W przypadku wystąpienia błędów w dowolnych blokach (aż do pewnej liczby bloków), dane można nadal bezbłędnie przesłać przez sieć. Kody Reeda-Solomona, na przykład, są używane do przesyłania danych przez światłowody oraz w komunikacji satelitarnej.

* Istnieją również kody nadmiarowe, w których dane nie są dzielone na bloki, na przykład kody Hamming i kody CRC, szeroko stosowane do przesyłania danych w sieciach Ethernet. To są kody odporne na zakłócenia, przeznaczone do wykrywania błędów, a nie do ich naprawy (kod Hamming także pozwala na częściowe naprawianie błędów).

2. Kody Reeda-Solomona

Kody Reeda-Solomona to jedne z najpowszechniej stosowanych kodów nadmiarowych, wynalezione w latach 60-tych XX wieku i po raz pierwszy zyskały szerokie zastosowanie w latach 80-tych przy seryjnej produkcji płyt kompaktowych.

Dwa kluczowe pytania dotyczące kodów Reeda-Solomona to: 1) jak tworzyć bloki kodów nadmiarowych; 2) jak przywracać dane za pomocą bloków kodów nadmiarowych. Znajdźmy na nie odpowiedzi.
Dla uproszczenia, będziemy dalej zakładać, że n=6 i m=4. Inne schematy są rozpatrywane w analogiczny sposób.

Jak tworzyć bloki kodów nadmiarowych

Każdy blok kodów nadmiarowości jest rozpatrywany niezależnie od pozostałych. Do obliczenia każdego bloku wykorzystuje się wszystkie n bloków danych. Na poniższym schemacie X1-X6 to bloki danych, a P1–P4 to bloki kodów nadmiarowości.

Wszystkie bloki danych muszą mieć ten sam rozmiar; do wyrównania można użyć zerowych bitów. Otrzymane bloki kodów nadmiarowości będą miały ten sam rozmiar co bloki danych. Wszystkie bloki danych dzielą się na słowa (na przykład po 16 bitów). Załóżmy, że podzieliliśmy bloki danych na k słów. Wówczas wszystkie bloki kodów nadmiarowości również będą podzielone na k słów.

Do obliczenia i-tego słowa każdego bloku nadmiarowości wykorzystywane będą i-te słowa wszystkich bloków danych. Obliczane będą według następującego wzoru:

Tutaj wartości x to słowa bloków danych, p to słowa bloków kodów nadmiarowości, a alfa, beta, gamma i delta to specjalnie dobrane liczby, identyczne dla wszystkich i. Należy od razu zaznaczyć, że wszystkie te wartości to nie zwykłe liczby, a elementy pola Galois, a operacje +, -, *, / to nie znane nam operacje, lecz specjalne operacje wprowadzone nad elementami pola Galois.

Po co są pola Galois

Wydawać by się mogło, że to proste: dzielimy dane na bloki, bloki na słowa, a za pomocą słów bloków danych obliczamy słowa bloków kodów nadmiarowości – otrzymujemy bloki kodów nadmiarowości. W zasadzie tak to działa, ale diabeł tkwi w szczegółach:

Jak wspomniano wcześniej, rozmiar słowa jest stały, w naszym przykładzie wynosi 16 bitów. Powyzsze wzory dla kodów Reed-Solomona są takie, że przy użyciu zwykłych liczb całkowitych wynik obliczenia p może nie być możliwy do przedstawienia za pomocą słowa o dopuszczalnym rozmiarze.
Przy odzyskiwaniu danych powyższe wzory będą traktowane jako układ równań, który należy rozwiązać, aby odzyskać dane. W trakcie rozwiązywania może pojawić się konieczność dzielenia liczb całkowitych przez siebie, co skutkuje liczbą rzeczywistą, której nie można dokładnie przedstawić w pamięci komputera.

Te problemy uniemożliwiają używanie liczb całkowitych dla kodów Reed-Solomona. Rozwiązanie problemu jest oryginalne i można je opisać w następujący sposób: wymyślmy specjalne liczby, które można reprezentować za pomocą słów o wymaganej długości (na przykład 16 bitów), a wynik wszystkich operacji na nich (dodawanie, odejmowanie, mnożenie, dzielenie) również będzie reprezentowany w pamięci komputera za pomocą słów o wymaganej długości.

Takie „specjalne” liczby są od dawna badane w matematyce, nazywane są polami. Pole to zbiór elementów z określonymi operacjami dodawania, odejmowania, mnożenia i dzielenia.

Pola Galua* to pola, dla których istnieje i jest jednoznaczny wynik każdej operacji (+, -, *, /) dla dowolnych dwóch elementów pola. Pola Galua można budować dla liczb będących potęgą 2: 2, 4, 8, 16 itd. (w rzeczywistości potęgą dowolnej liczby pierwszej p, ale w praktyce interesują nas tylko potęgi 2). Na przykład, dla słów o rozmiarze 16 bitów to pole zawierające 65 536 elementów, dla każdej pary których 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 Galua przy obliczeniach.

W ten sposób mamy system równań, za pomocą którego można zbudować bloki kodów nadmiarowości, pisząc odpowiedni program komputerowy. Za pomocą tego samego systemu równań można również wykonać przywracanie danych.

* To nie jest ścisła definicja, raczej opis.

Jak przywracać dane

Przywracanie jest potrzebne, gdy z n + m bloków część bloków jest niedostępna. Mogą to być zarówno bloki danych, jak i bloki kodów nadmiarowości. Brak bloków danych i/lub bloków kodów nadmiarowości oznacza, że w powyższych równaniach odpowiednie zmienne x i/lub p są nieznane.

Równania dla kodów Reed-Solomona można traktować jako system równań, w którym wszystkie wartości alfa, beta, gamma, delta są stałe, wszystkie x i p, odpowiadające dostępnym blokom, to znane zmienne, a pozostałe x i p to nieznane.

Na przykład, jeśli bloki danych 1, 2, 3 oraz blok kodów nadmiarowości 2 są niedostępne, wówczas dla i-tej grupy słów będzie następujący system równań (nieznane zaznaczone na czerwono):

Mamy system równań składający się z 4 równań z 4 niewiadomymi, co oznacza, że możemy ją rozwiązać i odzyskać dane!

Z tego systemu równań wynika szereg wniosków dotyczących odzyskiwania danych dla kodów Rida — Solomona (n bloków danych, m bloków kodów nadmiarowych):

Dane można odzyskać przy utracie dowolnych m bloków lub mniej. Przy utracie m+1 i więcej bloków danych nie można odzyskać: nie można rozwiązać systemu m równań z m + 1 niewiadomymi.
Aby odzyskać nawet jeden blok danych, należy użyć dowolnych n z pozostałych bloków, przy czym można wykorzystać dowolny z kodów nadmiarowych.

Co jeszcze należy wiedzieć

W powyższym opisie omijam szereg ważnych pytań, których rozważenie wymaga głębszego zanurzenia się w matematykę. W szczególności, nic nie mówię o następujących kwestiach:

System równań dla kodów Rida — Solomona musi mieć (jedno) rozwiązanie przy dowolnych kombinacjach niewiadomych (nie więcej niż m niewiadomych). W oparciu o ten wymóg dobierane są wartości alfa, beta, gamma i delta.
System równań należy umieć automatycznie budować (w zależności od tego, które bloki są niedostępne) i rozwiązywać.
Należy zbudować pole Galois: dla danego rozmiaru słowa umieć znajdować wynik dowolnej operacji (+, -, *, /) dla dowolnych dwóch elementów.

Na końcu artykułu znajdują się odnośniki do literatury dotyczącej tych ważnych kwestii.

Wybór n i m

Jak praktycznie wybrać n i m? W praktyce w systemach przechowywania danych kody nadmiarowe stosuje się w celu oszczędności miejsca, dlatego m zawsze wybiera się mniejsze od n. Ich konkretne wartości zależą od szeregu czynników, w tym:

Niezawodność przechowywania danych. Im większe m, tym większa liczba awarii dysków, które można przetrwać, co oznacza wyższą niezawodność.
Nadwyżka przechowywania. Im wyższy stosunek m/n, tym wyższa będzie nadwyżka przechowywania, a system będzie droższy.
Czas przetwarzania zapytań. Im większa suma n + m, tym dłuższy czas odpowiedzi na zapytania. Ponieważ podczas odczytu danych (w trakcie odzyskiwania) trzeba odczytać n bloków z n różnych dysków, czas odczytu będzie określany przez najwolniejszy dysk.

Ponadto przechowywanie danych w wielu centrach danych narzuca dodatkowe ograniczenia na wybór n i m: w przypadku wyłączenia jednego centrum danych dane nadal muszą być dostępne do odczytu. Na przykład, przy przechowywaniu danych w 3 centrach danych musi być spełniony warunek: m >= n/2, w przeciwnym razie możliwa jest sytuacja, w której dane są niedostępne do odczytu po wyłączeniu jednego centrum danych.

3. LRC — Kody lokalnej rekonstrukcji

Aby przywrócić dane za pomocą kodów Reed-Solomon, należy użyć n dowolnych bloków danych. Jest to bardzo istotny minus dla rozproszonych systemów przechowywania danych, ponieważ w przypadku przywracania danych z jednego uszkodzonego dysku będziemy musieli odczytać dane z większości pozostałych, co powoduje znaczne dodatkowe obciążenie dla dysków i sieci.

Najczęściej występujące błędy to niedostępność jednego bloku danych z powodu awarii lub przeciążenia jednego dysku. Czy można jakoś zmniejszyć nadmierne obciążenie przy przywracaniu danych w takim (najczęstszym) przypadku? Okazuje się, że tak: specjalnie w tym celu istnieją kody nadmiarowości LRC.

LRC (Localized Reconstruction Codes) to kody nadmiarowości wymyślone przez Microsoft do zastosowania w Windows Azure Storage. Idea LRC jest bardzo prosta: podzielić wszystkie bloki danych na dwie (lub więcej) grupy i obliczać część bloków kodów nadmiarowości dla każdej grupy osobno. W ten sposób część bloków kodów nadmiarowości zostanie obliczona przy użyciu wszystkich bloków danych (w LRC nazywają się globalnymi kodami nadmiarowości), a część — z użyciem jednej z dwóch grup bloków danych (nazywane lokalnymi kodami nadmiarowości).

LRC oznaczane jest trzema numerami: n-r-l, gdzie n — liczba bloków danych, r — liczba globalnych bloków kodów nadmiarowości, l — liczba lokalnych bloków kodów nadmiarowości. Aby odczytać dane w przypadku niedostępności jednego bloku danych, należy odczytać tylko n/l bloków — to w l razy mniej, niż w kodach Reed-Solomon.

Na przykład, rozważmy schemat LRC 6-2-2. X1–X6 — 6 bloków danych, P1, P2 — 2 globalne bloki nadmiarowości, P3, P4 — 2 lokalne bloki nadmiarowości.

Bloki kodów nadmiarowości P1, P2 obliczane są przy użyciu wszystkich bloków danych. Blok kodu nadmiarowości P3 — przy użyciu bloków danych X1–X3, blok kodu nadmiarowości P4 — przy użyciu bloków danych X4–X6.

Pozostałe operacje wykonuje się w LRC analogicznie do kodów Reed-Solomona. Równania do obliczania liczby słów w blokach kodów nadmiarowych będą następujące:

Aby dobrać liczby alfa, beta, gamma, delta, należy spełnić szereg warunków, które zapewniają możliwość odzyskania danych (tj. rozwiązania systemu równań). Więcej informacji można znaleźć w artykuł.
W praktyce do obliczania lokalnych kodów nadmiarowych P3, P4 stosuje się operację XOR.

Z systemu równań dla LRC wynika szereg wniosków:

Aby odzyskać dowolny 1 blok danych, wystarczy odczytać n/l bloków (n/2 w naszym przykładzie).
Jeśli r + l bloków jest niedostępnych, a wszystkie bloki należą do jednej grupy, to danych nie można odzyskać. Można to łatwo wyjaśnić na przykładzie. Niech będą niedostępne bloki X1–X3 i P3: to r + l bloki z jednej grupy, w naszym przypadku 4. Wówczas mamy system z 3 równań i 4 niewiadomymi, którego nie można rozwiązać.
We wszystkich pozostałych przypadkach niedostępności r + l bloków (gdy z każdej grupy dostępny jest przynajmniej jeden blok) dane w LRC można odzyskać.

W ten sposób LRC przewyższa kody Reed-Solomona w odzyskiwaniu danych po pojedynczych błędach. W kodach Reed-Solomona, aby odzyskać nawet jeden blok danych, trzeba użyć n bloków, a w LRC do odzyskania jednego bloku danych wystarczy wykorzystać n/l bloków (n/2 w naszym przykładzie). Z drugiej strony, LRC ustępuje kodom Reed-Solomona pod względem maksymalnej liczby dozwolonych błędów. W powyższych przykładach kody Reed-Solomona mogą odzyskać dane przy dowolnych 4 błędach, a dla LRC istnieją 2 kombinacje 4 błędów, kiedy danych nie można odzyskać.

Co jest ważniejsze — zależy od konkretnej sytuacji, ale często oszczędność nadmiarowego obciążenia, jaką daje LRC, przeważa nad nieco mniejszą niezawodnością przechowywania.

4. Inne kody nadmiarowe

Oprócz kodów Reed-Solomona i LRC istnieje wiele innych kodów nadmiarowych. Różne kody nadmiarowe korzystają z różnej matematyki. Oto kilka innych kodów nadmiarowych:

Kod nadmiarowy z użyciem operatora XOR. Operacja XOR wykonywana jest nad n blokami danych, co daje 1 blok kodów nadmiarowych, czyli schemat n+1 (n bloków danych, 1 kod nadmiarowy). Stosowany w RAID 5, gdzie bloki danych i kody nadmiarowe są cyklicznie zapisywane na wszystkie dyski macierzy.
Algorytm even-odd oparty na operacji XOR. Pozwala zbudować 2 bloki kodów nadmiarowości, czyli schemat n+2.
Algorytm STAR oparty na operacji XOR. Pozwala zbudować 3 bloki kodów nadmiarowości, czyli schemat n+3.
Kody pyramidalne — kolejne kody nadmiarowości od Microsoftu.

5. Zastosowanie w Yandexie

Szereg projektów infrastrukturalnych Yandexu wykorzystuje kody nadmiarowości do niezawodnego przechowywania danych. Oto kilka przykładów:

Wewnętrzne magazyn obiektowy MDS, o którym wspominałem na początku artykułu.
YT — system MapReduce Yandexu.
YDB (Yandex DataBase) — rozproszona baza danych newSQL.

W MDS używane są kody nadmiarowości LRC, schemat 8-2-2. Dane z kodami nadmiarowości zapisywane są na 12 różnych dyskach w różnych serwerach w 3 różnych DC: po 4 serwery w każdym DC. Więcej na ten temat przeczytacie w artykuł.

W YT używane są zarówno kody Reed-Solomn (schemat 6-3), które były zaimplementowane jako pierwsze, jak i kody nadmiarowości LRC (schemat 12-2-2), przy czym LRC jest preferowanym sposobem przechowywania.

W YDB używane są kody nadmiarowości oparte na even-odd (schemat 4-2). O kodach nadmiarowości w YDB już mówiono na Highload.

Zastosowanie różnych schematów kodów nadmiarowości wynika z różnych wymagań, jakie stawiane są systemom. Na przykład w MDS dane przechowywane za pomocą LRC są rozkładane od razu w 3 DC. Ważne jest, aby dane pozostały dostępne do odczytu w przypadku awarii jednego DC, dlatego bloki muszą być rozlokowane w DC w taki sposób, aby w przypadku niedostępności jakiegokolwiek DC liczba niedostępnych bloków nie przekraczała dopuszczalnej. W schemacie 8-2-2 można umieścić po 4 bloki w każdym DC, wtedy przy wyłączaniu jakiegokolwiek DC 4 bloki będą niedostępne, a dane można będzie odczytać. Niezależnie od tego, jaki schemat wybierzemy przy rozmieszczaniu w 3 DC, w każdym razie musi być (r + l) / n >= 0,5, co oznacza, że nadmiarowość przechowywania będzie wynosić co najmniej 50%.

W YT sytuacja jest inna: każdy klaster YT znajduje się w jednym DC (różne klastry w różnych DC), dlatego nie ma takiego ograniczenia. Schemat 12-2-2 daje nadmiarowość 33%, co oznacza, że przechowywanie danych jest tańsze, a przy tym mogą one przetrwać do 4 jednoczesnych awarii dysków, jak w schemacie MDS.

Istnieje jeszcze wiele szczegółów dotyczących stosowania kodów nadmiarowości w systemach przechowywania i przetwarzania danych: niuanse przywracania danych, wpływ przywracania na czas realizacji zapytań, specyfika zapisywania danych itd. Planuję osobno omówić te oraz inne aspekty zastosowania kodów nadmiarowości w praktyce, jeśli temat będzie interesujący.