RAID TP

macierz

RAID TP (Triple parity)

RAID triple parity (RTP) jest nowym algorytmem ochrony przed trzema błędami. Jest to rozszerzenie korygujące podwójną korekcji błędów Row-Diagonal Parity code. Dla dowolnej liczby dysków program RTP korzysta tylko z trzech dysków parzystości. Jest to optymalne pod względem wymaganych i dostępnych ilości nadmiarowych informacji. RTP korzysta z operacji XOR i przechowuje wszystkie niezakodowane dane. Złożoność obliczeniowa algorytmu parzystości jest optymalna. Złożoność dekodowania jest również znacznie niższa niż istniejących porównywalnych kodów. Opiszemy również symetryczny wariant algorytmu, w którym obliczenie parzystości jest identyczne z potrójną rekonstrukcją.

Klienci korporacyjni oczekują bardzo wysokiej dostępności, niezawodności i gwarancji wydajności od serwerów pamięci masowej. W miarę rozwijania systemów pamięci masowych coraz ważniejsze staje się zabezpieczenie przed wieloma jednoczesnymi zdarzeniami awaryjnymi. W kontekście dysków zdarzenia mogą być klasyfikowane jako awarie dysku, częściowe awarie lub przerywane błędy. Tradycyjne schematy tolerancji błędów, takie jak RAID 4 i RAID 5, nie mogą chronić przed wieloma awariami. Zwykle używane są systemy typu mirroring, takie jak RAID 1 lub RAID 10, aby przetrwać takie awarie. Jednak znacznie wyższe potrzeby pamięci masowej sprawiają, że ​​odbicie lustrzane jest nieatrakcyjne z punktu widzenia kosztów. Różne trendy technologiczne, na przykład użycie tanich i niepewnych napędów ATA/SATA w centrach danych, dodatkowo stawiają nowe wymagania dotyczące rozwiązań opartych na oprogramowaniu, które pomagają kompensować mniej niezawodne urządzenia. Wysoki wskaźnik błędów bitu (BER) na tych napędach, w połączeniu z ich dużymi rozmiarami, implikuje znacznie wyższe prawdopodobieństwo napotkania częściowej awarii, na przykład błędu uszkodzonego sektora podczas rekonstrukcji. Chociaż systemy zapobiegania podwójnym awariom opartym na parzystości, takie jak RDP i EVENODD, mogą obecnie rozwiązać niektóre z tych problemów, potrójny schemat korekcji błędów może pomóc w dalszym zwiększaniu tolerancji zdarzeń awaryjnych, zwłaszcza gdy tablica jest już zdegradowana. Podstawową motywacją systemu potrójnej tolerancji jest zdolność do przetrwania błędów półki bez narażania grupy RAID na potencjalne zdarzenie utraty danych z powodu błędów mediów podczas rekonstrukcji. Jednakże takie awarie mogą wystąpić z powodu utraty połączenia z półą. Tendencja technologiczna na większe dyski, w połączeniu z niewłaściwą korekcją błędów bitowych, oznacza, że ​​prawdopodobieństwo wystąpienia utraty danych z powodu błędów mediów wzrośnie proporcjonalnie. Jeśli dwa dyski zostaną utracone z powodu awarii półki, nawet grupy RDP o podwójnej parzystości byłyby narażone na tę awarię podczas rekonstrukcji. Aby zapobiec takim scenariuszom, klienci musieli skonfigurować grupy RAID tylko na jednym dysku w półce. Przykładowo, w systemie 8-półkowym oznaczałoby to 6 dysków parzystości danych + 2 na grupę RAID, co doprowadziło do stosunku danych: parzystości 3: 1. Jednakże, poprzez rozłożenie dwóch dysków na półkę, potrójny program odporny na uszkodzenia może chronić przed podobnymi awariami przy użyciu 16-dyskowych grup RAID (13 danych + 3 parzystości). Powoduje to znacznie lepsze wykorzystanie pamięci masowej, ponieważ osiąga dane: współczynnik parytetu 4,3: 1. Inną motywacją dla systemu potrójnej tolerancji jest to, że zapewnia on realną alternatywę dla systemów lustrzanych, takich jak RAID 1. W miarę rozwoju systemów pamięci masowej, większość modułów sprzętowych, takich jak adaptery, pętle, zasilacze, kontrolery półek itp. mogą zostać skonfigurowane w trybie nadmiarowym, aby uniknąć pojedynczego punktu awarii. Oznacza to, że dublowanie, które pierwotnie miało przetrwać awarię tych elementów, jest teraz obniżone przede wszystkim w celu ochrony przed wieloma równymi awariami dysku. Mimo że odbicie lustrzane jest nadal niezbędne do opracowania koncepcji odzyskiwania danych po awarii, wielu klientów korzysta z nich w lokalnych centrach danych, aby chronić przed wieloma awariami. Jak stwierdzono wcześniej, błędy półkowe są najczęstszą przyczyną takiego stanu rzeczy.

Poprzez rozłożenie dysków na półkach można zastosować system potrójnej ochrony, aby przetrwać wiele awarii przy wykorzystaniu pamięci znacznie lepszym od lustrzanego odbicia. Dlatego taki schemat pomaga obniżyć koszty magazynowania przy jednoczesnym zapewnieniu wysokiego poziomu niezawodności i dostępności. W artykule opisano nowy algorytm, zwany RTP, w celu ochrony przed awariami trzech dysków. Algorytm spełnia warunek Singleton, ponieważ wymaga tylko trzech nadmiarowych dysków w celu zabezpieczenia przed trzema uszkodzeniami. Poza macierzami pamięci masowej ten algorytm może być również wykorzystany do zapewnienia potrójnej możliwości korekcji błędów w innych aplikacjach polegających na nadmiarowym strumieniu danych. Aplikacje komunikacyjne, w których przekazywane są dodatkowe dane w celu zmniejszenia uzależnienia od retransmisji, mogą również używać tego algorytmu w celu odzyskania maksymalnie trzech skasowań. RTP może być skutecznie włączony do Log-Structured File System. Podczas gdy inne układy danych zapisu na miejscu zmuszone są ponosić koszty nadrzędne dla małych losowych zapisów, Log-Structured File System ma znacznie lepszą pracę ze względu na naturę zapisu w dowolnym miejscu i tym samym zapewnia wyjątkową możliwość wdrożenia zaawansowanej parzystości systemy tolerancji błędów, które mają znacznie wyższą wydajność pamięci masowej w porównaniu z odbiciem lustrzanym. W niniejszym artykule opisujemy budowę tablicy RTP, schematu obliczeniowego parzystości i algorytmu rekonstrukcji. Przedstawiamy również wariant algorytmu, zwany symetryczny RTP, który może być używany w rozproszonej parytetowej organizacji wspierającej dodatki dyskowe. Na koniec analizujemy działanie algorytmu i porównujemy je z innymi znanymi schematami korekcji błędów.

Podstawowe algorytmy RTP

RTP może być postrzegana jako rozszerzenie schematu korekcji błędów dysku podwójnego, Row-Diagonal Parity (RDP). Przypomnijmy, że tablica RDP wymaga całkowitej ilości p + 1 dysków, gdzie p jest liczbą podstawową> 2. Tablica składa się z dysków danych p-1, parytetów rzędu i diagonalnej parzystości dysków. Tablica jest podzielona na grupy pasków p-1, z których każdy tworzy samodzielny rząd i przekątną parzystości. Każdy pas składa się z innego bloku na każdym dysku. Każdy blok na dysku parzystości wiersza przechowuje poziomą sume XOR wszystkich bloków danych w tym samym pasku. Bloki w szczelinie parzystości z drugiej strony, zapisują sumę XOR przecięć p – 1, które pokrywają tarczę pary i wszystkie dyski danych. Przekątne są skonstruowane na grupie pasków p-1. Ponieważ istnieją takie przekątne, ale przestrzeń do zapisania tylko p-1, suma XOR jednego z przekątnych nie jest obliczana. Ważną właściwością formacji przekątnej wykorzystywaną przez program RDP jest to, że każda przekątna pomija inny dysk (parzystość danych lub wierszy) w tablicy. Tablica RTP jest tworzona przez dodanie trzeciego dysku parzystości, nazywanego anty-diagonalną parzystością, do tablicy RDP. Tak więc tablica RTP składa się z dysków p + 2, gdzie p jest liczbą większą niż 2. Oprócz przekątnych używanych przez RDP, RTP definiuje zestaw p anty-diagonalnych, które mają ortogonalne nachylenie do przekątnych. Te anty-przekątne pokrywają rzędowy dysk i dyski danych. Anty-diagonale nie obejmują diagonalnej parzystości i vice versa. Anty-diagonale są skonstruowane w tej samej grupie pasków p-1 jako przekątnych. Anty-diagonalny dysk parzystości przechowuje sumę XOR p – 1 . Podobnie jak w przypadku przekątnych, istnieje całkowita liczba anty-diagonali, pokazująca wystarczającą ilość miejsca do przechowywania p-1, suma XOR jednego z anty-diagonów nie jest obliczana.

Diagonal Parity Sets

Ustawienia Diagonalnej parzystości

Anti-diagonal Parity Sets

Ustawienia Anty-Diagonalnej parzystości

Anty-diagonale są uformowane w taki sposób, że dzielą diagonalną właściwość braku innego dysku (pary danych lub wierszy) w tablicy. Na rysunkach 1 i 2 przedstawiono przykład układu danych i parzystości w zestawie pasków w tablicy RTP 9-dysku utworzonej przy użyciu p = 7. Tablica zawiera 6 dysków danych (D0, D1, D2, D3, D4 i D5), rzędu parzystości rzędu (R), diagonalnego dysku parzystości (Diag) i anty-diagonalnego dysku parzystości (A-Diag). Rysunki 1 i 2, reprezentujące tę samą tablicę, przedstawiają przyporządkowanie bloków do zestawów parzystości i przekątnej. Na rysunku 1 liczba w każdym bloku wskazuje przekątną parzystość, do której należy blok. Podobnie, na rysunku 2 przedstawiono przekątne zestawy parzystości, do których należy blok. Dyski/kolumny liczbowe i = 0 · · · p (gdzie indeks D0 = 0, D1 = 1 itd.), A wiersze jako j = 0 · · (p-2) (pionowo w dół) [i, j] jako blok na dysku i i wierszu j. Wartości parzystości przekątnej, do której bloku A [i, j] należy, można obliczyć jako

D(i, j) = (i + j) mod p

Anty-diagonalny zestaw parzystości odpowiadający blokowi A [i, j] będą podane przez

AD(i, j) = (i − j − 1) mod p

Zauważ, że i ma maksymalną wartość p, ponieważ obliczanie ukośnych zestawów parzystości wyklucza anty-diagonalny dysk parzystości (i vice versa). W związku z tym, dyski po nie muszą być ponumerowane, gdy zostanie obliczony zestaw parzystości innego typu. Bloki na dysku parzystości wierszy są obliczane jako pozioma parzystość równy parzystości bloku danych w tym samym pasku. Równość pary jest obliczana w taki sam sposób, jak w RDP. Anty-diagonalna parzystość jest obliczana w sposób podobny do pary dla przekątnej, wykorzystując blokady anty-diagonalne. Każdy blok Anty-diagonalny parzystości zawiera równą parzystość bloków parzystości danych i wierszy na tej samej przekątnej. Równanie 3 definiuje wartość bloku parzystości ukośnej w wierszu/indeksie x (x = 0 ··· (p-2)), obliczonego jako suma XOR bloków na dyskach i = 0 ··· (p – 1) ( tzn. D0 ··· R). Podobnie, dla powyższego rysunku, równanie 4 definiuje wartość bloku Anty-diagonalnego na rzędzie/indeks x (x = 0 · · · (p-2)). Zauważ, że blok Anty-diagonalny w wierszu 0 odpowiada przekątnej 6. Ponadto dla dowolnego i przyjmuje się, że A [i, p-1] wynosi 0.

obliczenia

Na rysunkach 1 i 2 przekątnej 6 i przekątnej 0 są wyrzucane z odpowiednich dysków parzystości, ponieważ jest wystarczająco dużo miejsca na przechowywanie 6  (=p-1) przekątnych/anty-przekątnych. Inteligentny obserwator może zauważyć, że tablica RTP może być postrzegana jako składająca się z dwóch zestawów podwójnie odpornych na uszkodzenia tablic RDP, które dzielą te same dyski parzystości danych i wierszy. Dzieje się tak dlatego, ponieważ zestaw dysków danych, parytetów wierszy i dysków równości samo formujących się to płyta RDP, która wykorzystuje przekątne o prostopadłych zboczach. Chociaż powyższe sformułowanie wymaga dysków danych typu p-1, ten sam schemat może być stosowany przy mniejszej ilości dysków danych, przyjmując fałszywe dyski zerowe, do ukończenia parzystości.