Takto vyzerá redundancia
Redundantné kódy* sú široko používané v počítačových systémoch na zvýšenie spoľahlivosti ukladania dát. V Yandex sa používajú v mnohých projektoch. Napríklad používanie redundantných kódov namiesto replikácie v našom internom objektovom úložisku šetrí milióny bez obetovania spoľahlivosti. Ale napriek ich širokému používaniu sú jasné popisy toho, ako fungujú redundantné kódy, veľmi zriedkavé. Tí, ktorí chcú pochopiť, čelia približne nasledovnému (od ):
Volám sa Vadim, v Yandex vyvíjam interné objektové úložisko MDS. V tomto článku jednoduchými slovami popíšem teoretické základy redundantných kódov (Reed-Solomon a LRC kódy). Poviem vám, ako to funguje, bez zložitej matematiky a vzácnych termínov. Na konci uvediem príklady použitia redundantných kódov v Yandex.
Nebudem sa podrobne zaoberať množstvom matematických detailov, ale poskytnem odkazy pre tých, ktorí sa chcú ponoriť hlbšie. Ešte podotýkam, že niektoré matematické definície nemusia byť striktné, keďže článok nie je určený pre matematikov, ale pre inžinierov, ktorí chcú pochopiť podstatu problematiky.
* V anglickojazyčnej literatúre sa redundantné kódy často nazývajú vymazávacie kódy.
1. Podstata redundantných kódov
Podstata všetkých redundantných kódov je mimoriadne jednoduchá: ukladať (alebo prenášať) dáta tak, aby sa nestratili, keď sa vyskytnú chyby (zlyhania disku, chyby prenosu dát atď.).
Vo väčšine* redundantných kódov sú dáta rozdelené do n dátových blokov, pre ktoré sa počíta m blokov redundantných kódov, výsledkom čoho je celkovo n + m blokov. Redundantné kódy sú konštruované takým spôsobom, že n blokov údajov možno obnoviť iba pomocou časti n + m blokov. Ďalej budeme brať do úvahy iba blokové redundantné kódy, to znamená tie, v ktorých sú dáta rozdelené do blokov.
Ak chcete obnoviť všetkých n blokov údajov, musíte mať aspoň n z n + m blokov, pretože nemôžete získať n blokov, ak budete mať iba n-1 blok (v tomto prípade by ste museli „zobrať“ 1 blok vzduch“). Stačí n náhodných blokov n + m blokov na obnovenie všetkých údajov? Závisí to od typu redundantných kódov, napríklad kódy Reed-Solomon vám umožňujú obnoviť všetky údaje pomocou ľubovoľných n blokov, ale redundantné kódy LRC nie vždy.
Ukladanie údajov
V systémoch na ukladanie údajov sa spravidla každý z blokov údajov a blokov redundantného kódu zapisuje na samostatný disk. Potom, ak zlyhá ľubovoľný disk, pôvodné údaje je možné stále obnoviť a prečítať. Dáta je možné obnoviť aj vtedy, ak zlyhá niekoľko diskov súčasne.
Prenos údajov
Redundantné kódy možno použiť na spoľahlivý prenos údajov cez nespoľahlivú sieť. Prenášané dáta sú rozdelené do blokov a pre ne sú vypočítané redundantné kódy. Cez sieť sa prenášajú dátové bloky aj bloky redundantného kódu. Ak sa chyby vyskytnú v ľubovoľných blokoch (do určitého počtu blokov), dáta sa môžu stále prenášať cez sieť bez chyby. Reed-Solomonove kódy sa napríklad používajú na prenos údajov cez optické komunikačné linky a pri satelitnej komunikácii.
* Existujú aj redundantné kódy, v ktorých nie sú dáta rozdelené do blokov, ako sú Hammingove kódy a CRC kódy, ktoré sú široko používané na prenos dát v sieťach Ethernet. Sú to kódy pre kódovanie na opravu chýb, sú určené na zisťovanie chýb, nie na ich opravu (Hammingov kód umožňuje aj čiastočnú opravu chýb).
2. Reed-Solomonove kódy
Reed-Solomonove kódy sú jedným z najpoužívanejších redundantných kódov, ktorý bol vynájdený už v 1960. rokoch a prvýkrát široko používaný v 1980. rokoch XNUMX. storočia na hromadnú výrobu kompaktných diskov.
Existujú dve kľúčové otázky na pochopenie Reed-Solomonových kódov: 1) ako vytvoriť bloky redundantných kódov; 2) ako obnoviť dáta pomocou blokov redundantného kódu. Hľadajme na ne odpovede.
Pre jednoduchosť budeme ďalej predpokladať, že n=6 a m=4. Ostatné schémy sa posudzujú analogicky.
Ako vytvoriť bloky redundantného kódu
Každý blok redundantných kódov sa počíta nezávisle od ostatných. Na počítanie každého bloku sa použije všetkých n dátových blokov. V nižšie uvedenom diagrame sú X1-X6 dátové bloky, P1-P4 sú bloky redundantného kódu.
Všetky dátové bloky musia mať rovnakú veľkosť a na zarovnanie je možné použiť nulové bity. Výsledné bloky redundantného kódu budú mať rovnakú veľkosť ako dátové bloky. Všetky dátové bloky sú rozdelené na slová (napríklad 16 bitov). Povedzme, že rozdelíme dátové bloky na k slov. Potom budú všetky bloky redundantných kódov tiež rozdelené na k slov.
Na počítanie i-tého slova každého redundantného bloku sa použijú i-té slová všetkých dátových blokov. Vypočítajú sa podľa nasledujúceho vzorca:
Hodnoty x sú slová dátových blokov, p sú slová redundantných kódových blokov, všetky alfa, beta, gama a delta sú špeciálne vybrané čísla, ktoré sú rovnaké pre všetky i. Okamžite treba povedať, že všetky tieto hodnoty nie sú bežné čísla, ale prvky poľa Galois; operácie +, -, *, / nie sú operácie známe všetkým, ale špeciálne operácie zavedené na prvkoch Galois. lúka.
Prečo sú potrebné polia Galois?
Zdalo by sa, že všetko je jednoduché: dáta rozdelíme na bloky, bloky na slová, pomocou slov dátových blokov spočítame slová blokov redundantného kódu – dostaneme bloky redundantného kódu. Vo všeobecnosti to funguje takto, ale diabol je v detailoch:
- Ako je uvedené vyššie, veľkosť slova je pevná, v našom príklade 16 bitov. Vyššie uvedené vzorce pre Reed-Solomonove kódy sú také, že pri použití obyčajných celých čísel nemusí byť výsledok výpočtu p reprezentovateľný pomocou slova platnej veľkosti.
- Pri obnove údajov sa vyššie uvedené vzorce budú považovať za systém rovníc, ktoré je potrebné vyriešiť, aby sa údaje obnovili. Počas procesu riešenia môže byť potrebné deliť celé čísla navzájom, výsledkom čoho je reálne číslo, ktoré nemožno presne reprezentovať v pamäti počítača.
Tieto problémy bránia použitiu celých čísel pre kódy Reed-Solomon. Riešenie problému je originálne, možno ho opísať takto: vymyslime špeciálne čísla, ktoré možno znázorniť pomocou slov požadovanej dĺžky (napríklad 16 bitov), a výsledkom vykonania všetkých operácií, na ktorých (doplnok , odčítanie, násobenie, delenie) budú prezentované aj v pamäti počítača pomocou slov požadovanej dĺžky.
Takéto „špeciálne“ čísla študuje matematika už dlho, nazývajú sa polia. Pole je množina prvkov, pre ktoré sú definované operácie sčítania, odčítania, násobenia a delenia.
Polia Galois* sú polia, pre ktoré existuje jedinečný výsledok každej operácie (+, -, *, /) pre ľubovoľné dva prvky poľa. Galoisove polia možno zostrojiť pre čísla, ktoré sú mocniny 2: 2, 4, 8, 16 atď. (v skutočnosti mocniny akéhokoľvek prvočísla p, ale v praxi nás zaujímajú len mocniny 2). Napríklad pre 16-bitové slová ide o pole obsahujúce 65 536 prvkov, pre každý pár nájdete výsledok ľubovoľnej operácie (+, -, *, /). Hodnoty x, p, alfa, beta, gama, delta z rovníc vyššie sa budú považovať za prvky poľa Galois pre výpočty.
Máme teda systém rovníc, pomocou ktorých môžeme zostaviť bloky redundantných kódov napísaním vhodného počítačového programu. Pomocou rovnakého systému rovníc môžete vykonať obnovu dát.
* Toto nie je striktná definícia, ale skôr popis.
Ako obnoviť dáta
Obnova je potrebná, keď niektoré z n + m blokov chýbajú. Môžu to byť dátové bloky aj bloky redundantného kódu. Neprítomnosť dátových blokov a/alebo redundantných kódových blokov bude znamenať, že zodpovedajúce premenné x a/alebo p sú vo vyššie uvedených rovniciach neznáme.
Rovnice pre Reed-Solomonove kódy možno považovať za systém rovníc, v ktorom sú všetky hodnoty alfa, beta, gama, delta konštanty, všetky x a p zodpovedajúce dostupným blokom sú známe premenné a zvyšné x a p sú neznáme.
Ak sú napríklad dátové bloky 1, 2, 3 a blok 2 redundantného kódu nedostupné, potom pre i-tu skupinu slov bude nasledujúci systém rovníc (neznáme sú označené červenou):
Máme systém 4 rovníc so 4 neznámymi, čo znamená, že to vieme vyriešiť a obnoviť dáta!
Z tohto systému rovníc vyplýva niekoľko záverov o obnove dát pre kódy Reed-Solomon (n dátových blokov, m redundantných kódových blokov):
- Údaje je možné obnoviť, ak sa stratí m blokov alebo menej. Ak sa stratí m+1 alebo viac blokov, dáta sa nedajú obnoviť: nie je možné vyriešiť systém m rovníc s m + 1 neznámych.
- Ak chcete obnoviť čo i len jeden dátový blok, musíte použiť ľubovoľných n zostávajúcich blokov a môžete použiť ktorýkoľvek z redundantných kódov.
Čo ešte potrebujete vedieť
Vo vyššie uvedenom popise sa vyhýbam niekoľkým dôležitým problémom, ktoré si vyžadujú hlbší ponor do matematiky. Konkrétne nehovorím nič o nasledujúcom:
- Systém rovníc pre Reed-Solomonove kódy musí mať (jedinečné) riešenie pre akúkoľvek kombináciu neznámych (nie viac ako m neznámych). Na základe tejto požiadavky sa vyberú hodnoty alfa, beta, gama a delta.
- Systém rovníc sa musí dať automaticky zostrojiť (v závislosti od toho, ktoré bloky sú nedostupné) a vyriešiť.
- Musíme vytvoriť pole Galois: pre danú veľkosť slova byť schopný nájsť výsledok akejkoľvek operácie (+, -, *, /) pre ľubovoľné dva prvky.
Na konci článku sú odkazy na literatúru o týchto dôležitých otázkach.
Voľba n a m
Ako zvoliť n a m v praxi? V praxi sa v systémoch na ukladanie údajov používajú redundantné kódy na úsporu miesta, takže m sa vždy volí menej ako n. Ich špecifické hodnoty závisia od mnohých faktorov vrátane:
- Spoľahlivosť ukladania dát. Čím väčšie m, tým väčší počet zlyhaní disku sa dá prežiť, to znamená, že tým vyššia je spoľahlivosť.
- Nadbytočné úložisko. Čím vyšší je pomer m/n, tým vyššia bude redundancia úložiska a systém bude drahší.
- Požiadajte o čas spracovania. Čím väčší je súčet n + m, tým dlhší bude čas odozvy na požiadavky. Keďže čítanie údajov (počas obnovy) vyžaduje čítanie n blokov uložených na n rôznych diskoch, čas čítania bude určený najpomalším diskom.
Okrem toho ukladanie údajov do niekoľkých DC kladie ďalšie obmedzenia na výber n a m: ak je 1 DC vypnutý, údaje musia byť stále dostupné na čítanie. Napríklad pri ukladaní dát do 3 DC musí byť splnená nasledujúca podmienka: m >= n/2, inak môže nastať situácia, že pri vypnutom 1 DC budú dáta nedostupné na čítanie.
3. LRC – Local Reconstruction Codes
Ak chcete obnoviť údaje pomocou kódov Reed-Solomon, musíte použiť n ľubovoľných blokov údajov. Toto je veľmi významná nevýhoda pre distribuované systémy na ukladanie dát, pretože na obnovenie dát na jednom rozbitom disku budete musieť čítať dáta z väčšiny ostatných, čím sa vytvorí veľké dodatočné zaťaženie diskov a siete.
Najčastejšími chybami je neprístupnosť jedného bloku dát z dôvodu poruchy alebo preťaženia jedného disku. Je možné v tomto (najčastejšom) prípade nejako znížiť nadmernú záťaž na obnovu dát? Ukazuje sa, že môžete: existujú redundantné kódy LRC špeciálne na tento účel.
LRC (Local Reconstruction Codes) sú redundantné kódy vynájdené spoločnosťou Microsoft na použitie vo Windows Azure Storage. Myšlienka LRC je čo najjednoduchšia: rozdeliť všetky dátové bloky do dvoch (alebo viacerých) skupín a prečítať časť blokov redundantného kódu pre každú skupinu samostatne. Potom sa niektoré bloky redundantného kódu spočítajú pomocou všetkých dátových blokov (v LRC sa nazývajú globálne kódy redundancie) a niektoré pomocou jednej z dvoch skupín dátových blokov (nazývajú sa lokálne kódy redundancie).
LRC sa označuje tromi číslami: nrl, kde n je počet blokov údajov, r je počet blokov globálneho kódu redundancie, l je počet blokov kódu lokálnej redundancie. Na čítanie dát, keď je jeden dátový blok nedostupný, potrebujete prečítať iba n/l blokov - to je l krát menej ako v kódoch Reed-Solomon.
Zvážte napríklad schému LRC 6-2-2. X1–X6 — 6 dátových blokov, P1, P2 — 2 bloky globálnej redundancie, P3, P4 — 2 bloky lokálnej redundancie.
Bloky redundantného kódu P1, P2 sa počítajú pomocou všetkých dátových blokov. Blok redundantného kódu P3 - pomocou dátových blokov X1-X3, blok redundantného kódu P4 - pomocou dátových blokov X4-X6.
Zvyšok sa vykonáva v LRC analogicky s kódmi Reed-Solomon. Rovnice na počítanie slov blokov redundantného kódu budú:
Pre výber čísel alfa, beta, gama, delta musí byť splnených niekoľko podmienok, aby bola zaručená možnosť obnovy dát (teda vyriešenie sústavy rovníc). Viac si o nich môžete prečítať v .
Aj v praxi sa operácia XOR používa na výpočet lokálnych redundantných kódov P3, P4.
Zo systému rovníc pre LRC vyplýva niekoľko záverov:
- Na obnovenie akéhokoľvek 1 dátového bloku stačí prečítať n/l blokov (v našom príklade n/2).
- Ak bloky r + l nie sú k dispozícii a všetky bloky sú zahrnuté v jednej skupine, údaje sa nedajú obnoviť. To sa dá ľahko vysvetliť na príklade. Nech sú bloky X1–X3 a P3 nedostupné: ide o r + l blokov z rovnakej skupiny, v našom prípade 4. Potom máme systém 3 rovníc so 4 neznámymi, ktoré sa nedajú vyriešiť.
- Vo všetkých ostatných prípadoch nedostupnosti blokov r + l (keď je k dispozícii aspoň jeden blok z každej skupiny) možno údaje v LRC obnoviť.
LRC teda prekonáva Reed-Solomonove kódy pri obnove dát po jednotlivých chybách. V kódoch Reed-Solomon je na obnovenie čo i len jedného bloku údajov potrebné použiť n blokov a v prípade LRC na obnovenie jedného bloku údajov stačí použiť n/l blokov (v našom príklade n/2). Na druhej strane je LRC horší ako kódy Reed-Solomon, pokiaľ ide o maximálny počet povolených chýb. Vo vyššie uvedených príkladoch môžu kódy Reed-Solomon obnoviť údaje pre akékoľvek 4 chyby a pre LRC existujú 2 kombinácie 4 chýb, keď sa údaje nedajú obnoviť.
Čo je dôležitejšie, závisí od konkrétnej situácie, ale často úspory nadmernej záťaže, ktoré LRC poskytuje, prevažujú nad o niečo menej spoľahlivým úložiskom.
4. Iné redundantné kódy
Okrem Reed-Solomonových a LRC kódov existuje mnoho ďalších redundantných kódov. Rôzne redundantné kódy používajú rôznu matematiku. Tu sú niektoré ďalšie redundantné kódy:
- Redundantný kód pomocou operátora XOR. Operácia XOR sa vykonáva na n dátových blokoch a získa sa 1 blok redundantných kódov, teda schéma n+1 (n dátových blokov, 1 redundantný kód). Použité v , kde sa bloky dát a redundantné kódy cyklicky zapisujú na všetky disky poľa.
- Algoritmus párne-nepárny založený na operácii XOR. Umožňuje vám zostaviť 2 bloky redundantných kódov, teda schému n+2.
- Algoritmus STAR založený na operácii XOR. Umožňuje vám zostaviť 3 bloky redundantných kódov, teda schému n+3.
- Pyramidové kódy sú ďalšie redundantné kódy od spoločnosti Microsoft.
5. Použite v Yandex
Množstvo projektov infraštruktúry Yandex používa redundantné kódy na spoľahlivé ukladanie údajov. Tu je niekoľko príkladov:
- Interné objektové úložisko MDS, o ktorom som písal na začiatku článku.
- — MapReduce systém Yandex.
- (Yandex DataBase) - nová SQL distribuovaná databáza.
MDS používa redundantné kódy LRC, schému 8-2-2. Údaje s redundantnými kódmi sa zapisujú na 12 rôznych diskov v rôznych serveroch v 3 rôznych DC: 4 servery v každom DC. Prečítajte si o tom viac v .
YT používa ako Reed-Solomonove kódy (schéma 6-3), ktoré boli implementované ako prvé, tak aj LRC redundantné kódy (schéma 12-2-2), pričom LRC je preferovanou metódou ukladania.
YDB používa redundantné kódy založené na párnom a nepárnom (obrázok 4-2). O redundantných kódoch už v YDB .
Použitie rôznych schém redundantného kódu je spôsobené rôznymi požiadavkami na systémy. Napríklad v MDS sú dáta uložené pomocou LRC umiestnené v 3 DC naraz. Pre nás je dôležité, aby dáta zostali dostupné na čítanie, ak 1 z ľubovoľného DC zlyhá, preto musia byť bloky rozdelené medzi DC tak, aby v prípade, že niektorý DC nie je dostupný, počet neprístupných blokov nebol väčší ako povolený. V schéme 8-2-2 môžete umiestniť 4 bloky do každého DC, potom keď je ktorýkoľvek DC vypnutý, 4 bloky budú nedostupné a dáta je možné čítať. Bez ohľadu na schému, ktorú si vyberieme pri umiestnení do 3 DC, v každom prípade by mala byť (r + l) / n >= 0,5, to znamená, že redundancia úložiska bude aspoň 50%.
V YT je situácia iná: každý klaster YT je celý umiestnený v 1 DC (rôzne klastre v rôznych DC), takže tam takéto obmedzenie neexistuje. Schéma 12-2-2 poskytuje 33% redundanciu, to znamená, že ukladanie dát je lacnejšie a tiež dokáže prežiť až 4 súčasné výpadky disku, rovnako ako schéma MDS.
Existuje mnoho ďalších funkcií používania redundantných kódov v systémoch na ukladanie a spracovanie údajov: nuansy obnovy údajov, vplyv obnovy na čas vykonania dotazu, funkcie zaznamenávania údajov atď. O týchto a ďalších funkciách budem hovoriť samostatne. o využití redundantných kódov v praxi, ak bude téma zaujímavá.
6. Odkazy
- Séria článkov o Reed-Solomonových kódoch a poliach Galois:
Hlbšie sa pozerajú na matematiku v prístupnom jazyku. - Článok od Microsoftu o LRC:
Časť 2 stručne vysvetľuje teóriu a potom rozoberá skúsenosti s LRC v praxi. - Schéma párna-nepárna:
- Schéma STAR:
- Pyramídové kódy:
- Redundantné kódy v MDS:
- Redundantné kódy v YT:
- Redundantné kódy v YDB:
Zdroj: hab.com