Takto vypadá redundance
Redundantní kódy* jsou široce používány v počítačových systémech ke zvýšení spolehlivosti ukládání dat. V Yandexu se používají v mnoha projektech. Například používání redundantních kódů místo replikace v našem interním úložišti objektů ušetří miliony, aniž by to obětovalo spolehlivost. Ale navzdory jejich širokému použití jsou jasné popisy toho, jak redundantní kódy fungují, velmi vzácné. Ti, kteří chtějí porozumět, čelí přibližně následujícímu (od ):
Jmenuji se Vadim, v Yandexu vyvíjím interní objektové úložiště MDS. V tomto článku jednoduchými slovy popíšu teoretické základy redundantních kódů (Reed-Solomonovy a LRC kódy). Řeknu vám, jak to funguje, bez složité matematiky a vzácných termínů. Na konci uvedu příklady použití redundantních kódů v Yandexu.
Nebudu se podrobně zabývat řadou matematických detailů, ale poskytnu odkazy pro ty, kteří se chtějí ponořit hlouběji. Ještě podotýkám, že některé matematické definice nemusí být striktní, jelikož článek není určen pro matematiky, ale pro inženýry, kteří chtějí pochopit podstatu problematiky.
* V anglicky psané literatuře se kódy redundance často nazývají kódy výmazu.
1. Podstata redundantních kódů
Podstata všech redundantních kódů je extrémně jednoduchá: ukládat (nebo přenášet) data tak, aby se při výskytu chyb (selhání disku, chyby přenosu dat atd.) neztratila.
Ve většině* redundantních kódů jsou data rozdělena do n datových bloků, pro které se počítá m bloků redundantních kódů, což má za následek celkem n + m bloků. Redundantní kódy jsou konstruovány tak, že n bloků dat lze obnovit pouze pomocí části n + m bloků. Dále budeme uvažovat pouze blokové redundantní kódy, tedy ty, ve kterých jsou data rozdělena do bloků.
Chcete-li obnovit všech n bloků dat, musíte mít alespoň n z n + m bloků, protože nemůžete získat n bloků tím, že budete mít pouze n-1 blok (v tomto případě byste museli odebrat 1 blok vzduch"). Stačí n náhodných bloků n + m bloků k obnovení všech dat? To závisí na typu redundantních kódů, například Reed-Solomonovy kódy umožňují obnovit všechna data pomocí libovolných n bloků, ale redundantní kódy LRC ne vždy.
Ukládání dat
V systémech ukládání dat je zpravidla každý z datových bloků a bloků redundantního kódu zapsán na samostatný disk. Pokud pak selže libovolný disk, lze původní data stále obnovit a číst. Data lze obnovit, i když selže několik disků současně.
Přenos dat
Redundantní kódy lze použít ke spolehlivému přenosu dat přes nespolehlivou síť. Přenášená data jsou rozdělena do bloků a pro ně jsou vypočítány redundantní kódy. Po síti jsou přenášeny datové bloky i bloky redundantního kódu. Vyskytnou-li se chyby v libovolných blocích (do určitého počtu bloků), lze data stále přenášet po síti bez chyby. Reed-Solomonovy kódy se například používají k přenosu dat přes optické komunikační linky a v satelitní komunikaci.
* Existují také redundantní kódy, ve kterých nejsou data rozdělena do bloků, jako jsou Hammingovy kódy a CRC kódy, které jsou široce používány pro přenos dat v sítích Ethernet. Jedná se o kódy pro kódování opravující chyby, jsou určeny k detekci chyb, nikoli k jejich opravě (Hammingův kód umožňuje i částečnou opravu chyb).
2. Reed-Solomonovy kódy
Reed-Solomonovy kódy jsou jedním z nejpoužívanějších redundantních kódů, vynalezených již v 1960. letech a poprvé široce používaných v 1980. letech XNUMX. století pro hromadnou výrobu kompaktních disků.
Pro pochopení Reed-Solomonových kódů existují dvě klíčové otázky: 1) jak vytvořit bloky redundantních kódů; 2) jak obnovit data pomocí bloků redundantního kódu. Pojďme na ně najít odpovědi.
Pro jednoduchost budeme dále předpokládat, že n=6 a m=4. Další schémata jsou uvažována analogicky.
Jak vytvořit bloky redundantního kódu
Každý blok redundantních kódů se počítá nezávisle na ostatních. K počítání každého bloku se používá všech n datových bloků. V níže uvedeném diagramu jsou X1-X6 datové bloky, P1-P4 jsou bloky redundantního kódu.
Všechny datové bloky musí mít stejnou velikost a pro zarovnání lze použít nulové bity. Výsledné bloky redundantního kódu budou mít stejnou velikost jako datové bloky. Všechny datové bloky jsou rozděleny na slova (například 16 bitů). Řekněme, že rozdělíme datové bloky na k slov. Potom budou všechny bloky redundantních kódů také rozděleny na k slov.
K počítání i-tého slova každého redundantního bloku budou použita i-tá slova všech datových bloků. Budou vypočítány podle následujícího vzorce:
Zde hodnoty x jsou slova datových bloků, p jsou slova bloků redundantního kódu, všechna alfa, beta, gama a delta jsou speciálně vybraná čísla, která jsou stejná pro všechna i. Je třeba hned říci, že všechny tyto hodnoty nejsou běžná čísla, ale prvky pole Galois; operace +, -, *, / nejsou operace známé nám všem, ale speciální operace zavedené na prvcích Galois. pole.
Proč jsou pole Galois potřebná?
Zdálo by se, že vše je jednoduché: rozdělíme data na bloky, bloky na slova, pomocí slov datových bloků počítáme slova bloků redundantního kódu – dostaneme bloky redundantního kódu. Obecně to funguje takto, ale ďábel je v detailech:
- Jak je uvedeno výše, velikost slova je pevná, v našem příkladu 16 bitů. Vzorce výše pro Reed-Solomonovy kódy jsou takové, že při použití běžných celých čísel nemusí být výsledek výpočtu p reprezentovatelný pomocí slova platné velikosti.
- Při obnově dat budou výše uvedené vzorce považovány za systém rovnic, které je nutné vyřešit, aby bylo možné data obnovit. Během procesu řešení může být nutné dělit celá čísla navzájem, což má za následek reálné číslo, které nelze přesně reprezentovat v paměti počítače.
Tyto problémy brání použití celých čísel pro kódy Reed-Solomon. Řešení úlohy je originální, lze jej popsat takto: pojďme vymyslet speciální čísla, která lze znázornit pomocí slov požadované délky (například 16 bitů), a výsledek provedení všech operací, na kterých (doplnění , odčítání, násobení, dělení) budou také prezentovány v paměti počítače pomocí slov požadované délky.
Taková „zvláštní“ čísla jsou matematikou studována již dlouhou dobu, říká se jim pole. Pole je množina prvků, pro které jsou definovány operace sčítání, odčítání, násobení a dělení.
Pole Galois* jsou pole, pro která existuje jedinečný výsledek každé operace (+, -, *, /) pro libovolné dva prvky pole. Galoisova pole lze sestrojit pro čísla, která jsou mocniny 2: 2, 4, 8, 16 atd. (ve skutečnosti mocniny libovolného prvočísla p, ale v praxi nás zajímají pouze mocniny 2). Například pro 16bitová slova se jedná o pole obsahující 65 536 prvků, u každého páru najdete výsledek libovolné operace (+, -, *, /). Hodnoty x, p, alfa, beta, gama, delta z rovnic výše budou považovány za prvky pole Galois pro výpočty.
Máme tedy systém rovnic, pomocí kterých můžeme sestavit bloky redundantních kódů napsáním vhodného počítačového programu. Pomocí stejného systému rovnic můžete provádět obnovu dat.
* Toto není striktní definice, ale spíše popis.
Jak obnovit data
Obnova je nutná, když některé z n + m bloků chybí. Mohou to být jak datové bloky, tak bloky redundantního kódu. Absence datových bloků a/nebo bloků redundantního kódu bude znamenat, že odpovídající proměnné x a/nebo p jsou ve výše uvedených rovnicích neznámé.
Na rovnice pro Reed-Solomonovy kódy lze pohlížet jako na systém rovnic, ve kterém jsou všechny hodnoty alfa, beta, gama, delta konstanty, všechny x a p odpovídající dostupným blokům jsou známé proměnné a zbývající x a p jsou neznámé.
Necháme-li například datové bloky 1, 2, 3 a blok redundantního kódu 2 nedostupné, pak pro i-tou skupinu slov bude následující systém rovnic (neznámé jsou označeny červeně):
Máme systém 4 rovnic se 4 neznámými, což znamená, že to můžeme vyřešit a obnovit data!
Z tohoto systému rovnic vyplývá řada závěrů o obnově dat pro kódy Reed-Solomon (n datových bloků, m bloků redundantního kódu):
- Data lze obnovit, pokud dojde ke ztrátě m bloků nebo méně. Pokud dojde ke ztrátě m+1 nebo více bloků, data nelze obnovit: není možné vyřešit systém m rovnic s m + 1 neznámými.
- Chcete-li obnovit byť jen jeden datový blok, musíte použít libovolných n zbývajících bloků a můžete použít kterýkoli z redundantních kódů.
Co ještě potřebuji vědět?
Ve výše uvedeném popisu se vyhýbám řadě důležitých otázek, které vyžadují hlubší ponor do matematiky ke zvážení. Konkrétně neříkám nic o následujícím:
- Systém rovnic pro Reed-Solomonovy kódy musí mít (jedinečné) řešení pro jakoukoli kombinaci neznámých (ne více než m neznámých). Na základě tohoto požadavku jsou vybrány hodnoty alfa, beta, gama a delta.
- Systém rovnic musí být schopen automaticky sestavit (podle toho, které bloky jsou nedostupné) a vyřešit.
- Potřebujeme sestavit Galoisovo pole: pro danou velikost slova umět najít výsledek jakékoli operace (+, -, *, /) pro libovolné dva prvky.
Na konci článku jsou odkazy na literaturu o těchto důležitých otázkách.
Volba n a m
Jak v praxi zvolit n a m? V praxi se v systémech pro ukládání dat používají redundantní kódy pro úsporu místa, takže m je vždy zvoleno méně než n. Jejich přesné hodnoty závisí na řadě faktorů, včetně:
- Spolehlivost ukládání dat. Čím větší m, tím větší počet selhání disku lze přežít, tedy vyšší spolehlivost.
- Redundantní úložiště. Čím vyšší je poměr m/n, tím vyšší bude redundance úložiště a tím dražší systém bude.
- Požádat o dobu zpracování. Čím větší je součet n + m, tím delší bude doba odezvy na požadavky. Protože čtení dat (během obnovy) vyžaduje čtení n bloků uložených na n různých discích, bude doba čtení určena nejpomalejším diskem.
Kromě toho ukládání dat v několika DC ukládá další omezení na volbu n a m: pokud je 1 DC vypnuto, data musí být stále dostupná pro čtení. Například při ukládání dat do 3 DC musí být splněna následující podmínka: m >= n/2, jinak může nastat situace, kdy při vypnutém 1 DC nebudou data dostupná pro čtení.
3. LRC - Local Reconstruction Codes
Chcete-li obnovit data pomocí kódů Reed-Solomon, musíte použít n libovolných datových bloků. To je velmi významná nevýhoda pro distribuované systémy pro ukládání dat, protože pro obnovu dat na jednom rozbitém disku budete muset číst data z většiny ostatních, což vytváří velké dodatečné zatížení disků a sítě.
Nejčastějšími chybami je nepřístupnost jednoho bloku dat z důvodu poruchy nebo přetížení jednoho disku. Je možné v tomto (nejčastějším) případě nějak snížit nadměrnou zátěž pro obnovu dat? Ukazuje se, že je to možné: existují redundantní kódy LRC speciálně pro tento účel.
LRC (Local Reconstruction Codes) jsou redundantní kódy vynalezené společností Microsoft pro použití ve Windows Azure Storage. Myšlenka LRC je co nejjednodušší: rozdělte všechny datové bloky do dvou (nebo více) skupin a čtěte část bloků redundantního kódu pro každou skupinu zvlášť. Poté budou některé bloky redundantního kódu počítány pomocí všech datových bloků (v LRC se nazývají globální kódy redundance) a některé - pomocí jedné ze dvou skupin datových bloků (nazývají se místní kódy redundance).
LRC je označeno třemi čísly: nrl, kde n je počet bloků dat, r je počet bloků globálního kódu redundance, l je počet bloků kódu místní redundance. Chcete-li číst data, když je jeden datový blok nedostupný, musíte číst pouze n/l bloků - to je lkrát méně než v kódech Reed-Solomon.
Zvažte například schéma LRC 6-2-2. X1–X6 — 6 datových bloků, P1, P2 — 2 bloky globální redundance, P3, P4 — 2 bloky lokální redundance.
Bloky redundantního kódu P1, P2 se počítají pomocí všech datových bloků. Blok kódu redundance P3 - pomocí datových bloků X1-X3, blok kódu redundance P4 - pomocí bloků dat X4-X6.
Zbytek se provádí v LRC analogicky s kódy Reed-Solomon. Rovnice pro počítání slov bloků redundantního kódu budou:
Pro výběr čísel alfa, beta, gama, delta musí být splněna řada podmínek, které zaručí možnost obnovy dat (tedy vyřešení soustavy rovnic). Více si o nich můžete přečíst v .
Také v praxi se operace XOR používá k výpočtu lokálních redundantních kódů P3, P4.
Ze soustavy rovnic pro LRC vyplývá řada závěrů:
- K obnovení libovolného 1 bloku dat stačí přečíst n/l bloků (v našem příkladu n/2).
- Pokud jsou bloky r + l nedostupné a všechny bloky jsou zahrnuty v jedné skupině, nelze data obnovit. To lze snadno vysvětlit na příkladu. Bloky X1–X3 a P3 nechť jsou nedostupné: jedná se o r + l bloků ze stejné skupiny, v našem případě 4. Pak máme soustavu 3 rovnic se 4 neznámými, které nelze vyřešit.
- Ve všech ostatních případech nedostupnosti r + l bloků (když je dostupný alespoň jeden blok z každé skupiny) lze data v LRC obnovit.
LRC tak překonává kódy Reed-Solomon v obnově dat po jednotlivých chybách. V kódech Reed-Solomon je pro obnovu byť jednoho bloku dat potřeba použít n bloků a v LRC pro obnovu jednoho bloku dat stačí použít n/l bloků (v našem příkladu n/2). Na druhou stranu je LRC horší než kódy Reed-Solomon, pokud jde o maximální počet přípustných chyb. Ve výše uvedených příkladech mohou kódy Reed-Solomon obnovit data pro jakékoli 4 chyby a pro LRC existují 2 kombinace 4 chyb, kdy data nelze obnovit.
Co je důležitější, závisí na konkrétní situaci, ale často úspory nadměrného zatížení, které LRC poskytuje, převažují nad o něco méně spolehlivým úložištěm.
4. Jiné redundantní kódy
Kromě Reed-Solomonových a LRC kódů existuje mnoho dalších redundantních kódů. Různé redundantní kódy používají různou matematiku. Zde jsou některé další redundantní kódy:
- Redundantní kód pomocí operátoru XOR. Operace XOR se provádí na n datových blocích a získá se 1 blok redundantních kódů, to znamená schéma n+1 (n datových bloků, 1 redundantní kód). Použito v , kde se bloky dat a redundantní kódy cyklicky zapisují na všechny disky pole.
- Algoritmus sudá-lichá založený na operaci XOR. Umožňuje sestavit 2 bloky redundantních kódů, tedy schéma n+2.
- Algoritmus STAR založený na operaci XOR. Umožňuje sestavit 3 bloky redundantních kódů, tedy schéma n+3.
- Pyramidové kódy jsou další redundantní kódy od společnosti Microsoft.
5. Použijte v Yandex
Řada projektů infrastruktury Yandex používá redundantní kódy pro spolehlivé ukládání dat. Zde jsou nějaké příklady:
- Vnitřní objektové úložiště MDS, o kterém jsem psal na začátku článku.
- — MapReduce systém Yandex.
- (Yandex DataBase) - nová SQL distribuovaná databáze.
MDS používá redundantní kódy LRC, schéma 8-2-2. Data s redundantními kódy se zapisují na 12 různých disků na různých serverech ve 3 různých DC: 4 servery v každém DC. Přečtěte si o tom více v .
YT používá jak kódy Reed-Solomon (schéma 6-3), které byly implementovány jako první, tak kódy redundance LRC (schéma 12-2-2), přičemž LRC je preferovanou metodou ukládání.
YDB používá redundantní kódy založené na sudých a lichých (obrázek 4-2). O redundantních kódech již v YDB .
Použití různých schémat redundantního kódu je způsobeno různými požadavky na systémy. Například v MDS jsou data uložená pomocí LRC umístěna do 3 DC najednou. Pro nás je důležité, aby data zůstala dostupná pro čtení, pokud 1 z libovolného DC selže, proto je třeba bloky rozmístit po DC tak, aby v případě nedostupnosti některého DC nebyl počet nepřístupných bloků větší než přípustný. Ve schématu 8-2-2 můžete umístit 4 bloky do každého DC, pak když je kterýkoli DC vypnutý, 4 bloky budou nedostupné a data lze číst. Ať už zvolíme jakékoli schéma při umístění do 3 DC, v každém případě by mělo být (r + l) / n >= 0,5, to znamená, že redundance úložiště bude alespoň 50 %.
V YT je situace jiná: každý cluster YT je celý umístěn v 1 DC (různé clustery v různých DC), takže žádné takové omezení neexistuje. Schéma 12-2-2 poskytuje 33% redundanci, to znamená, že ukládání dat je levnější, a také dokáže přežít až 4 současné výpadky disku, stejně jako schéma MDS.
Existuje mnoho dalších funkcí použití redundantních kódů v systémech pro ukládání a zpracování dat: nuance obnovy dat, dopad obnovy na dobu provádění dotazu, funkce záznamu dat atd. O těchto a dalších funkcích budu mluvit samostatně. využití redundantních kódů v praxi, pokud bude téma zajímavé.
6. Odkazy
- Série článků o Reed-Solomonových kódech a Galoisových polích:
Podívají se hlouběji na matematiku v přístupném jazyce. - Článek od Microsoftu o LRC:
Část 2 stručně vysvětluje teorii a poté diskutuje zkušenosti s LRC v praxi. - Schéma sudé-liché:
- Schéma STAR:
- Kódy pyramid:
- Redundantní kódy v MDS:
- Redundantní kódy na YT:
- Redundantní kódy v YDB:
Zdroj: www.habr.com