{"id":87758,"date":"2020-07-10T01:41:58","date_gmt":"2020-07-09T23:41:58","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye"},"modified":"2020-07-10T01:41:58","modified_gmt":"2020-07-09T23:41:58","slug":"kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","status":"publish","type":"post","link":"https:\/\/prohoster.info\/pl\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Kody nadmiarowo\u015bci: prosto o tym, jak bezpiecznie i tanio przechowywa\u0107 dane","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Kody<\/p>\n

<\/p>\n

Tak wygl\u0105da nadmiarowo\u015b\u0107<\/em><\/p>\n

<\/p>\n

Kody nadmiarowo\u015bci* s\u0105 szeroko stosowane w systemach komputerowych w celu zwi\u0119kszenia niezawodno\u015bci przechowywania danych. W Yandexie wykorzystuje si\u0119 je w wielu projektach. Na przyk\u0142ad, zastosowanie kod\u00f3w nadmiarowo\u015bci zamiast replikacji w naszym wewn\u0119trznym systemie przechowywania obiekt\u00f3w oszcz\u0119dza miliony bez obni\u017cania niezawodno\u015bci. Mimo szerokiego zastosowania, zrozumia\u0142e opisy dzia\u0142ania kod\u00f3w nadmiarowo\u015bci s\u0105 bardzo rzadkie. Osoby chc\u0105ce si\u0119 z tym zapozna\u0107 napotykaj\u0105 na mniej wi\u0119cej to (z Wikipedii<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Kody<\/p>\n

<\/p>\n

Nazywam si\u0119 Wadim, w Yandexie zajmuj\u0119 si\u0119 opracowaniem wewn\u0119trznego systemu przechowywania obiekt\u00f3w MDS. W tym artykule prosto wyja\u015bni\u0119 teoretyczne podstawy kod\u00f3w nadmiarowo\u015bci (kod\u00f3w Reeda-Solomona i LRC). Opowiem, jak to dzia\u0142a, bez skomplikowanej matematyki i rzadkich termin\u00f3w. Na ko\u0144cu podam przyk\u0142ady zastosowania kod\u00f3w nadmiarowo\u015bci w Yandexie.<\/p>\n

<\/p>\n

Nie b\u0119d\u0119 szczeg\u00f3\u0142owo omawia\u0107 szeregu matematycznych detali, ale podam linki dla tych, kt\u00f3rzy chc\u0105 zg\u0142\u0119bi\u0107 temat. R\u00f3wnie\u017c zauwa\u017cam, \u017ce niekt\u00f3re definicje matematyczne mog\u0105 by\u0107 niedok\u0142adne, poniewa\u017c artyku\u0142 jest przeznaczony nie dla matematyk\u00f3w, lecz dla in\u017cynier\u00f3w, kt\u00f3rzy chc\u0105 zrozumie\u0107 istot\u0119 problemu.<\/p>\n

<\/p>\n

* W literaturze angloj\u0119zycznej kody nadmiarowo\u015bci cz\u0119sto nazywane s\u0105 erasure codes.<\/p>\n

<\/a><\/noindex><\/p>\n

1. Istota kod\u00f3w nadmiarowo\u015bci<\/h1>\n

<\/p>\n

Istota wszystkich kod\u00f3w nadmiarowo\u015bci jest niezwykle prosta: przechowywa\u0107 (lub przesy\u0142a\u0107) dane w taki spos\u00f3b, aby nie znikn\u0119\u0142y w przypadku wyst\u0105pienia b\u0142\u0119d\u00f3w (awarii dysk\u00f3w, b\u0142\u0119d\u00f3w transmisji danych itp.). <\/p>\n

<\/p>\n

W wi\u0119kszo\u015bci* kod\u00f3w nadmiarowo\u015bci dane dzieli si\u0119 na n blok\u00f3w danych, dla kt\u00f3rych liczy si\u0119 m blok\u00f3w kod\u00f3w nadmiarowo\u015bci, co daje \u0142\u0105cznie n + m blok\u00f3w. Kody nadmiarowo\u015bci s\u0105 konstruowane w taki spos\u00f3b, aby mo\u017cna by\u0142o odzyska\u0107 n blok\u00f3w danych, u\u017cywaj\u0105c tylko cz\u0119\u015bci blok\u00f3w z n + m. Nast\u0119pnie rozwa\u017cymy tylko bloki kod\u00f3w nadmiarowo\u015bci, czyli takie, w kt\u00f3rych dane dzielone s\u0105 na bloki.<\/p>\n

<\/p>\n

\"Kody<\/p>\n

<\/p>\n

Aby przywr\u00f3ci\u0107 wszystkie n blok\u00f3w danych, konieczne jest posiadanie przynajmniej n z n + m blok\u00f3w, poniewa\u017c nie mo\u017cna uzyska\u0107 n blok\u00f3w maj\u0105c tylko n-1 blok (w takim przypadku musia\u0142by by\u0107 wzi\u0119ty 1 blok \u201ez powietrza\u201d). Czy wystarcz\u0105 n dowolnych blok\u00f3w z n + m blok\u00f3w do przywr\u00f3cenia wszystkich danych? Zale\u017cy to od rodzaju kod\u00f3w nadmiarowych, na przyk\u0142ad kody Reeda-Solomona pozwalaj\u0105 na przywr\u00f3cenie wszystkich danych za pomoc\u0105 dowolnych n blok\u00f3w, podczas gdy kody LRC \u2014 nie zawsze.<\/p>\n

<\/p>\n

Przechowywanie danych<\/h3>\n

<\/p>\n

W systemach przechowywania danych zazwyczaj ka\u017cdy z blok\u00f3w danych i blok\u00f3w kod\u00f3w nadmiarowych jest zapisywany na oddzielnym dysku. W przypadku awarii dowolnego dysku, oryginalne dane wci\u0105\u017c mo\u017cna b\u0119dzie przywr\u00f3ci\u0107 i odczyta\u0107. Dane mo\u017cna b\u0119dzie przywr\u00f3ci\u0107 nawet przy jednoczesnej awarii kilku dysk\u00f3w.<\/p>\n

<\/p>\n

Przesy\u0142anie danych<\/h3>\n

<\/p>\n

Kody nadmiarowe mo\u017cna wykorzysta\u0107 do niezawodnego przesy\u0142ania danych w zawodnej sieci. Przesy\u0142ane dane dzieli si\u0119 na bloki, dla kt\u00f3rych oblicza si\u0119 kody nadmiarowe. Po sieci przesy\u0142ane s\u0105 zar\u00f3wno bloki danych, jak i bloki kod\u00f3w nadmiarowych. W przypadku wyst\u0105pienia b\u0142\u0119d\u00f3w w dowolnych blokach (a\u017c do pewnej liczby blok\u00f3w), dane mo\u017cna nadal bezb\u0142\u0119dnie przes\u0142a\u0107 przez sie\u0107. Kody Reeda-Solomona, na przyk\u0142ad, s\u0105 u\u017cywane do przesy\u0142ania danych przez \u015bwiat\u0142owody oraz w komunikacji satelitarnej.<\/p>\n

<\/p>\n

* Istniej\u0105 r\u00f3wnie\u017c kody nadmiarowe, w kt\u00f3rych dane nie s\u0105 dzielone na bloki, na przyk\u0142ad kody Hamming i kody CRC, szeroko stosowane do przesy\u0142ania danych w sieciach Ethernet. To s\u0105 kody odporne na zak\u0142\u00f3cenia, przeznaczone do wykrywania b\u0142\u0119d\u00f3w, a nie do ich naprawy (kod Hamming tak\u017ce pozwala na cz\u0119\u015bciowe naprawianie b\u0142\u0119d\u00f3w).<\/p>\n

<\/p>\n

2. Kody Reeda-Solomona<\/h1>\n

<\/p>\n

Kody Reeda-Solomona to jedne z najpowszechniej stosowanych kod\u00f3w nadmiarowych, wynalezione w latach 60-tych XX wieku i po raz pierwszy zyska\u0142y szerokie zastosowanie w latach 80-tych przy seryjnej produkcji p\u0142yt kompaktowych.<\/p>\n

<\/p>\n

Dwa kluczowe pytania dotycz\u0105ce kod\u00f3w Reeda-Solomona to: 1) jak tworzy\u0107 bloki kod\u00f3w nadmiarowych; 2) jak przywraca\u0107 dane za pomoc\u0105 blok\u00f3w kod\u00f3w nadmiarowych. Znajd\u017amy na nie odpowiedzi.
\nDla uproszczenia, b\u0119dziemy dalej zak\u0142ada\u0107, \u017ce n=6 i m=4. Inne schematy s\u0105 rozpatrywane w analogiczny spos\u00f3b.<\/p>\n

<\/p>\n

Jak tworzy\u0107 bloki kod\u00f3w nadmiarowych<\/h3>\n

<\/p>\n

Ka\u017cdy blok kod\u00f3w nadmiarowo\u015bci jest rozpatrywany niezale\u017cnie od pozosta\u0142ych. Do obliczenia ka\u017cdego bloku wykorzystuje si\u0119 wszystkie n blok\u00f3w danych. Na poni\u017cszym schemacie X1-X6 to bloki danych, a P1\u2013P4 to bloki kod\u00f3w nadmiarowo\u015bci.<\/p>\n

<\/p>\n

\"Kody<\/p>\n

<\/p>\n

Wszystkie bloki danych musz\u0105 mie\u0107 ten sam rozmiar; do wyr\u00f3wnania mo\u017cna u\u017cy\u0107 zerowych bit\u00f3w. Otrzymane bloki kod\u00f3w nadmiarowo\u015bci b\u0119d\u0105 mia\u0142y ten sam rozmiar co bloki danych. Wszystkie bloki danych dziel\u0105 si\u0119 na s\u0142owa (na przyk\u0142ad po 16 bit\u00f3w). Za\u0142\u00f3\u017cmy, \u017ce podzielili\u015bmy bloki danych na k s\u0142\u00f3w. W\u00f3wczas wszystkie bloki kod\u00f3w nadmiarowo\u015bci r\u00f3wnie\u017c b\u0119d\u0105 podzielone na k s\u0142\u00f3w.<\/p>\n

<\/p>\n

\"Kody<\/p>\n

<\/p>\n

Do obliczenia i-tego s\u0142owa ka\u017cdego bloku nadmiarowo\u015bci wykorzystywane b\u0119d\u0105 i-te s\u0142owa wszystkich blok\u00f3w danych. Obliczane b\u0119d\u0105 wed\u0142ug nast\u0119puj\u0105cego wzoru:<\/p>\n

<\/p>\n

\"Kody<\/p>\n

<\/p>\n

Tutaj warto\u015bci x to s\u0142owa blok\u00f3w danych, p to s\u0142owa blok\u00f3w kod\u00f3w nadmiarowo\u015bci, a alfa, beta, gamma i delta to specjalnie dobrane liczby, identyczne dla wszystkich i. Nale\u017cy od razu zaznaczy\u0107, \u017ce wszystkie te warto\u015bci to nie zwyk\u0142e liczby, a elementy pola Galois, a operacje +, -, *, \/ to nie znane nam operacje, lecz specjalne operacje wprowadzone nad elementami pola Galois.<\/p>\n

<\/p>\n

Po co s\u0105 pola Galois<\/h3>\n

<\/p>\n

\"Kody<\/p>\n

<\/p>\n

Wydawa\u0107 by si\u0119 mog\u0142o, \u017ce to proste: dzielimy dane na bloki, bloki na s\u0142owa, a za pomoc\u0105 s\u0142\u00f3w blok\u00f3w danych obliczamy s\u0142owa blok\u00f3w kod\u00f3w nadmiarowo\u015bci \u2013 otrzymujemy bloki kod\u00f3w nadmiarowo\u015bci. W zasadzie tak to dzia\u0142a, ale diabe\u0142 tkwi w szczeg\u00f3\u0142ach:<\/p>\n

<\/p>\n

    \n
  1. Jak wspomniano wcze\u015bniej, rozmiar s\u0142owa jest sta\u0142y, w naszym przyk\u0142adzie wynosi 16 bit\u00f3w. Powyzsze wzory dla kod\u00f3w Reed-Solomona s\u0105 takie, \u017ce przy u\u017cyciu zwyk\u0142ych liczb ca\u0142kowitych wynik obliczenia p mo\u017ce nie by\u0107 mo\u017cliwy do przedstawienia za pomoc\u0105 s\u0142owa o dopuszczalnym rozmiarze.<\/li>\n
  2. Przy odzyskiwaniu danych powy\u017csze wzory b\u0119d\u0105 traktowane jako uk\u0142ad r\u00f3wna\u0144, kt\u00f3ry nale\u017cy rozwi\u0105za\u0107, aby odzyska\u0107 dane. W trakcie rozwi\u0105zywania mo\u017ce pojawi\u0107 si\u0119 konieczno\u015b\u0107 dzielenia liczb ca\u0142kowitych przez siebie, co skutkuje liczb\u0105 rzeczywist\u0105, kt\u00f3rej nie mo\u017cna dok\u0142adnie przedstawi\u0107 w pami\u0119ci komputera.<\/li>\n<\/ol>\n

    <\/p>\n

    Te problemy uniemo\u017cliwiaj\u0105 u\u017cywanie liczb ca\u0142kowitych dla kod\u00f3w Reed-Solomona. Rozwi\u0105zanie problemu jest oryginalne i mo\u017cna je opisa\u0107 w nast\u0119puj\u0105cy spos\u00f3b: wymy\u015blmy specjalne liczby, kt\u00f3re mo\u017cna reprezentowa\u0107 za pomoc\u0105 s\u0142\u00f3w o wymaganej d\u0142ugo\u015bci (na przyk\u0142ad 16 bit\u00f3w), a wynik wszystkich operacji na nich (dodawanie, odejmowanie, mno\u017cenie, dzielenie) r\u00f3wnie\u017c b\u0119dzie reprezentowany w pami\u0119ci komputera za pomoc\u0105 s\u0142\u00f3w o wymaganej d\u0142ugo\u015bci.<\/p>\n

    <\/p>\n

    Takie \u201especjalne\u201d liczby s\u0105 od dawna badane w matematyce, nazywane s\u0105 polami. Pole to zbi\u00f3r element\u00f3w z okre\u015blonymi operacjami dodawania, odejmowania, mno\u017cenia i dzielenia.<\/p>\n

    <\/p>\n

    Pola Galua* to pola, dla kt\u00f3rych istnieje i jest jednoznaczny wynik ka\u017cdej operacji (+, -, *, \/) dla dowolnych dw\u00f3ch element\u00f3w pola. Pola Galua mo\u017cna budowa\u0107 dla liczb b\u0119d\u0105cych pot\u0119g\u0105 2: 2, 4, 8, 16 itd. (w rzeczywisto\u015bci pot\u0119g\u0105 dowolnej liczby pierwszej p, ale w praktyce interesuj\u0105 nas tylko pot\u0119gi 2). Na przyk\u0142ad, dla s\u0142\u00f3w o rozmiarze 16 bit\u00f3w to pole zawieraj\u0105ce 65 536 element\u00f3w, dla ka\u017cdej pary kt\u00f3rych mo\u017cna znale\u017a\u0107 wynik dowolnej operacji (+, -, *, \/). Warto\u015bci x, p, alfa, beta, gamma, delta z powy\u017cszych r\u00f3wna\u0144 b\u0119d\u0105 uwa\u017cane za elementy pola Galua przy obliczeniach.<\/p>\n

    <\/p>\n

    W ten spos\u00f3b mamy system r\u00f3wna\u0144, za pomoc\u0105 kt\u00f3rego mo\u017cna zbudowa\u0107 bloki kod\u00f3w nadmiarowo\u015bci, pisz\u0105c odpowiedni program komputerowy. Za pomoc\u0105 tego samego systemu r\u00f3wna\u0144 mo\u017cna r\u00f3wnie\u017c wykona\u0107 przywracanie danych.<\/p>\n

    <\/p>\n

    * To nie jest \u015bcis\u0142a definicja, raczej opis.<\/p>\n

    <\/p>\n

    Jak przywraca\u0107 dane<\/h3>\n

    <\/p>\n

    Przywracanie jest potrzebne, gdy z n + m blok\u00f3w cz\u0119\u015b\u0107 blok\u00f3w jest niedost\u0119pna. Mog\u0105 to by\u0107 zar\u00f3wno bloki danych, jak i bloki kod\u00f3w nadmiarowo\u015bci. Brak blok\u00f3w danych i\/lub blok\u00f3w kod\u00f3w nadmiarowo\u015bci oznacza, \u017ce w powy\u017cszych r\u00f3wnaniach odpowiednie zmienne x i\/lub p s\u0105 nieznane.<\/p>\n

    <\/p>\n

    R\u00f3wnania dla kod\u00f3w Reed-Solomona mo\u017cna traktowa\u0107 jako system r\u00f3wna\u0144, w kt\u00f3rym wszystkie warto\u015bci alfa, beta, gamma, delta s\u0105 sta\u0142e, wszystkie x i p, odpowiadaj\u0105ce dost\u0119pnym blokom, to znane zmienne, a pozosta\u0142e x i p to nieznane.<\/p>\n

    <\/p>\n

    Na przyk\u0142ad, je\u015bli bloki danych 1, 2, 3 oraz blok kod\u00f3w nadmiarowo\u015bci 2 s\u0105 niedost\u0119pne, w\u00f3wczas dla i-tej grupy s\u0142\u00f3w b\u0119dzie nast\u0119puj\u0105cy system r\u00f3wna\u0144 (nieznane zaznaczone na czerwono):<\/p>\n

    <\/p>\n

    \"Kody<\/p>\n

    <\/p>\n

    Mamy system r\u00f3wna\u0144 sk\u0142adaj\u0105cy si\u0119 z 4 r\u00f3wna\u0144 z 4 niewiadomymi, co oznacza, \u017ce mo\u017cemy j\u0105 rozwi\u0105za\u0107 i odzyska\u0107 dane!<\/p>\n

    <\/p>\n

    Z tego systemu r\u00f3wna\u0144 wynika szereg wniosk\u00f3w dotycz\u0105cych odzyskiwania danych dla kod\u00f3w Rida \u2014 Solomona (n blok\u00f3w danych, m blok\u00f3w kod\u00f3w nadmiarowych):<\/p>\n

    <\/p>\n