Kodowanie erasure Reed-Solomon dla dystrybuowanej przechowywania danych

Kodowanie: od bloków danych do wielomianu

Kodowanie Reed-Solomon traktuje kawałek k symboli danych nie jako bajty, ale jako współczynniki lub punkty oceny wielomianu stopnia mniejszego niż k, działając nad polem skończonejącym, najczęściej poliem Galois GF(2 do 8 potęgi), tak że każdy symbol pasuje dokładnie do jednego bajtu. Aby uzyskać m symboli parzystości, kodownik ocenia ten wielomian na m dodatkowych, różnych punktów poza k używanymi do przedstawienia oryginalnych danych, lub równoważnie mnoży wektor danych przez macierz generatorkową specjalnie zbudowaną, której wiersze odpowiadają punktowi oceny. Kluczowe matematyczne fakty pozwalające na to, że wielomian stopnia mniejszego niż k jest całkowicie i jednoznacznie wyznaczony przez dowolne k jego punktów oceny, wynikają z podstawowego twierdzenia algebry stosowanego nad polem skończonym. W systemach przechowywania danych to zwykle oznacza podział dużego pliku na_stripy_, przyjmowanie k bloków na strip jako danych i obliczanie m bloków parzystości na strip, z wszystkimi k plus m bloków rozłożonymi po różnych domenach awarii, takich jak oddzielne dyski, serwery lub rafy, aby pojedyncza awaria sprzętu nie mogłaby usunąć więcej bloków niż kod może wytrzymać.

Model uszkodzeń w porównaniu do modelu błędów

Kody Reed-Solomon oryginalnie były zaprojektowane do poprawiania błędów, co oznacza symbole dotarłe z uszkodzeniami na nieznanych pozycjach. To jest trudniejsze niż poprawianie uszkodzeń, gdzie pozycje brakujących symboli są znane, ale ich wartości nie. Przede wszystkim dystrybuowane systemy przechowywania danych prawie zawsze działają w modelu uszkodzeń: gdy dysk zepsuje się lub węzeł wyjmuje się z sieci, system wie dokładnie, które bloki są utracone, i musi tylko odzyskać ich zawartość. Ta różnica ma ogromne znaczenie dla efektywności, ponieważ poprawianie t nieznanych błędów wymaga 2t symboli parzystości pod klasykami granicami, podczas gdy poprawianie t znanych uszkodzeń wymaga tylko t symboli parzystości, dokładnie połowy obciążenia. System skonfigurowany z k równego dziesięciu bloków danych i m równego czterech bloków parzystości, często napisany jako 10-of-14 lub schemat RS(14,10), może zatem tolerować stratę dowolnych czterech bloków w sektorze i nadal odzyskać wszystko, podczas gdy osiągnięcie tego samego stopnia odporności na niewykryte uszkodzenia w nieznanych lokalizacjach wymagałoby podwójnie większej ilości symboli parzystości.

Odtwórczność: interpolacja wielomianowa i odtwarzanie Lagrange'a

Gdy do m z k plus m bloków w stroku są brakujące, przetrwane bloki stanowią już k lub więcej znanych punktów oceny oryginalnego wielomianu stopnia mniejszego niż k, a odtwarzanie staje się tradycyjną problemem interpolacji: podaną ilość punktów pozwala na odtworzenie jednoznacznej funkcji wielomianowej przechodzącej przez te punkty, a następnie jej ocenie w oryginalnych pozycjach danych do odzyskania brakujących symboli. Interpolacja Lagrange'a dostarcza bezpośredniego wzoru, wyrażającego wielomian jako sumę ważoną podstawowych wielomianów, każdy z których jest równy dokładnie w jednym znanej punkcie i równy zero dla pozostałych, ale praktyczne implementacje częściej odwracają podmacierz macierzy generatorkowej odpowiadającej przetrwanym punktom oceny, ponieważ odwrotność macierzy nad cielejem Galois może być wcześnie obliczona i optymalizowana za pomocą tabel do odwołań dla konkretnej k i m wybranych. Cała arytmetyka odbywa się w skończonym ciele, gdzie dodawanie to XOR bitowe a mnożenie korzysta z specyficznych dla ciała tabel, więc całe proces kodowania i odtwarzania, mimo że brzmi jak ciężkiej algebra, w praktyce redukuje się do szybkiego odwoływania się do tabel i operacji XOR, które nawet na standardowym sprzęcie działają efektywnie, a coraz częściej na dedykowanych instrukcjach w współczesnych procesorach.

RAID6, HDFS i kompromis nadmiaru przechowywania

RAID6 jest najbardziej znanej w praktyce instancją tego pojęcia, używając dokładnie dwóch bloków paradyzacyjnych, często obliczonych przy użyciu uproszczonego schematu podobnego do Reed-Solomon, aby przetrwać jednoczesne zniszczenie dowolnych dwóch dysków w zestawie. To poprawiło się w porównaniu do jednoparadyzacyjnej tolerancji RAID5, która stała się konieczna ze wzrostem rozmiarów dysków i czasu rekonstrukcji, podczas którego drugie zniszczenie jest najbardziej zagrożone. Systemy plików dystrybuowane i magazyny obiektów przekształcają to pojęcie dalej, używając większych wartości k i m dostosowanych do ich cech zanurzenia; na przykład tryb kodowania erasure w HDFS często używa schematów takich jak 6-z 9 lub 10-z 14, trading większą szansę jednoczesnej niedostępności bloków podczas rekonstrukcji za nadmiar przechowywania o minimalnym procentach czterdziestu procent powyżej rozmiaru oryginalnych danych w porównaniu do dwustu procent nadmiaru przy trójwym replikacji. Język główny kompromisu polega na regulowaniu między efektywnością przechowywania a wytrzymałością: zwiększenie m podnosi liczbę jednoczesnych zniszczeń, które paski mogą przetrwać, ale dodaje proporcjonalnie więcej kosztów przechowywania i obliczeniowych. Z drugiej strony zwiększanie k w stosunku do m sprowadza nadmiar do minimum, co podnosi liczbę węzłów, które muszą być odczytane, aby przeprowadzić rekonstrukcję nawet jednego brakującego bloku, co jest ważnym rozważeniem zarówno dla matematyki wytrzymałości, jak i rzeczywistych bandów przerobek.

koszt naprawy i dlaczego to ważne na skalę

Efektywność przechowywania Reed-Solomon przynosi rzeczywisty koszt operacyjny podczas odtwarzania: przywracanie nawet jednego utraconego bloku w prostym schemacie wymaga czytania k przeżywających bloków połączonych przez sieć, aby wykonać interpolację, co dla dużych k może znacząco zwiększać zużycie przepustowości między węzłami i operacji we/wy tylko do naprawienia jednego awarii. To sprawia, że cała podprzemia coding theory skupiona jest na zmniejszeniu bandwiendu naprawczego, w tym regenerujące kody, które zyskują mało miejsca przechowywania za znacznie tańsze naprawy poprzez wysyłanie małych kombinacji liniowych zamiast całego bloku, oraz kody naprawialne lokalnie, które dodają dodatkowe, mniejsze grupy paradygmatyczne, tak że większość awarii jednego węzła może być naprawiona czytając tylko kilka bliskich bloków zamiast pełnej ilości k potrzebnej przez klasyczną konstrukcję Reed-Solomon. Zrozumienie prostego odtwarzania Reed-Solomon nadal stanowi podstawę dla wszystkich tych ulepszeń, ponieważ one wszystkie nadal opierają się na tym samym zasadzie, że wielomian, lub ogólniej kod liniowy, może być odzyskany na podstawie wystarczającej liczby niezależnych dowodów jego wartości.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Reed-Solomon Erasure Coding for Distributed Storage i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.