Így néz ki a redundancia
A redundancia kódokat* széles körben használják a számítógépes rendszerekben az adattárolás megbízhatóságának növelésére. A Yandexben sok projektben használják őket. Például, ha a belső objektumtárolónkban a replikáció helyett redundanciakódokat használunk, milliókat takaríthatunk meg a megbízhatóság feláldozása nélkül. Ám széles körben elterjedt használatuk ellenére a redundanciakódok működésének egyértelmű leírása nagyon ritka. Azok, akik meg akarják érteni, körülbelül a következőkkel szembesülnek (a ):
A nevem Vadim, a Yandexnél belső objektumtároló MDS-t fejlesztek. Ebben a cikkben egyszerű szavakkal leírom a redundancia kódok (Reed-Solomon és LRC kódok) elméleti alapjait. Elmondom, hogyan működik, bonyolult matematika és ritka kifejezések nélkül. A végén példákat adok a redundanciakódok használatára a Yandexben.
Számos matematikai részletet nem foglalkozom részletesen, de linkeket adok azoknak, akik mélyebbre szeretnének merülni. Azt is megjegyzem, hogy egyes matematikai meghatározások nem feltétlenül szigorúak, mivel a cikk nem matematikusoknak szól, hanem mérnököknek, akik szeretnék megérteni a kérdés lényegét.
* Az angol nyelvű irodalomban a redundancia kódokat gyakran törlési kódoknak nevezik.
1. A redundancia kódok lényege
Az összes redundanciakód lényege rendkívül egyszerű: tárolja (vagy továbbítsa) az adatokat, hogy ne vesszenek el hibák (lemezhiba, adatátviteli hibák stb.) esetén.
A legtöbb* redundancia kódban az adatok n adatblokkra vannak felosztva, amelyekhez m blokk redundancia kódot számol, így összesen n + m blokkot kapunk. A redundancia kódok úgy vannak megszerkesztve, hogy n adatblokk állítható vissza n + m blokk egy részének felhasználásával. Ezután csak a blokk redundancia kódokat vesszük figyelembe, vagyis azokat, amelyekben az adatok blokkokra vannak osztva.
Az összes n adatblokk visszaállításához legalább n blokkkal kell rendelkeznie n + m blokkból, mivel nem kaphat n blokkot úgy, hogy csak n-1 blokkja van (ebben az esetben 1 blokkot kell kivennie levegő"). Elegendő n véletlenszerű n + m blokk az összes adat helyreállításához? Ez a redundanciakódok típusától függ, például a Reed-Solomon kódok lehetővé teszik az összes adat visszaállítását tetszőleges n blokk használatával, de az LRC redundanciakódok nem mindig.
Adattárolás
Az adattároló rendszerekben általában minden adatblokk és redundanciakód blokk külön lemezre van írva. Ezután, ha egy tetszőleges lemez meghibásodik, az eredeti adatok továbbra is visszaállíthatók és olvashatók. Az adatok akkor is visszaállíthatók, ha egyszerre több lemez is meghibásodik.
Adatátvitel
A redundanciakódok segítségével megbízhatóan továbbíthatók az adatok megbízhatatlan hálózaton. A továbbított adatokat blokkokra osztják, és redundanciakódokat számítanak ki ezekhez. Mind az adatblokkok, mind a redundanciakód blokkok továbbításra kerülnek a hálózaton. Ha hiba lép fel tetszőleges blokkokban (meghatározott számú blokkig), az adatok továbbra is hiba nélkül továbbíthatók a hálózaton. A Reed-Solomon kódokat például adatátvitelre használják optikai kommunikációs vonalakon és műholdas kommunikációban.
* Vannak olyan redundanciakódok is, amelyekben az adatok nincsenek blokkokra osztva, ilyenek például a Hamming-kódok és a CRC-kódok, amelyeket széles körben használnak adatátvitelre Ethernet-hálózatokban. Ezek a hibajavító kódolás kódjai, a hibák észlelésére szolgálnak, nem pedig javításukra (a Hamming-kód a hibák részleges javítását is lehetővé teszi).
2. Reed-Solomon kódok
A Reed-Solomon kódok az egyik legszélesebb körben használt redundanciakódok, amelyeket az 1960-as években találtak fel, és először az 1980-as években használták széles körben a CD-k tömeggyártására.
Két kulcskérdés van a Reed-Solomon kódok megértéséhez: 1) hogyan lehet redundancia kódok blokkjait létrehozni; 2) hogyan lehet visszaállítani az adatokat redundancia kódblokkokkal. Keressünk rájuk választ.
Az egyszerűség kedvéért feltételezzük továbbá, hogy n=6 és m=4. A többi sémát analógia alapján vizsgáljuk.
Hogyan készítsünk redundancia kódblokkokat
A redundanciakódok minden egyes blokkját a többitől függetlenül számolja a rendszer. Mind az n adatblokk minden blokk számlálására szolgál. Az alábbi ábrán X1-X6 adatblokkok, P1-P4 redundancia kódblokkok.
Minden adatblokknak azonos méretűnek kell lennie, és nulla bitek használhatók az igazításhoz. Az eredményül kapott redundancia kódblokkok az adatblokkok méretével azonos méretűek lesznek. Minden adatblokk szavakra van osztva (például 16 bit). Tegyük fel, hogy az adatblokkokat k szóra bontjuk. Ekkor az összes redundanciakód-blokk szintén k szóra lesz osztva.
Az egyes redundanciablokkok i-edik szavának megszámlálásához az összes adatblokk i-edik szavait kell használni. Kiszámításuk a következő képlet szerint történik:
Itt az x értékek az adatblokkok szavai, a p a redundancia kódblokkok szavai, az összes alfa, béta, gamma és delta speciálisan kiválasztott számok, amelyek minden i-re azonosak. Azonnal le kell mondani, hogy ezek az értékek nem közönséges számok, hanem a Galois mező elemei; a +, -, *, / műveletek nem mindannyiunk számára ismert műveletek, hanem a Galois elemeire bevezetett speciális műveletek. terület.
Miért van szükség Galois mezőkre?
Úgy tűnik, minden egyszerű: az adatokat blokkokra osztjuk, a blokkokat szavakra, az adatblokkok szavaival megszámoljuk a redundancia kódblokkok szavait - redundancia kódblokkokat kapunk. Általában így működik, de az ördög a részletekben rejlik:
- Mint fentebb említettük, a szó mérete rögzített, példánkban 16 bit. A fenti képletek a Reed-Solomon kódokhoz olyanok, hogy közönséges egész számok használatakor előfordulhat, hogy a p kiszámításának eredménye nem ábrázolható érvényes méretű szó használatával.
- Az adatok helyreállítása során a fenti képleteket egyenletrendszernek tekintjük, amelyet meg kell oldani az adatok helyreállításához. A megoldási folyamat során előfordulhat, hogy az egész számokat el kell osztani egymással, ami egy valós számot eredményez, amelyet nem lehet pontosan ábrázolni a számítógép memóriájában.
Ezek a problémák megakadályozzák az egész számok használatát a Reed-Solomon kódokhoz. A probléma megoldása eredeti, a következőképpen írható le: találjunk ki speciális számokat, amelyek a kívánt hosszúságú (például 16 bites) szavakkal ábrázolhatók, és minden olyan művelet eredményét, amelyen (összeadás , kivonás, szorzás, osztás) a számítógép memóriájában is megjelennek a szükséges hosszúságú szavakkal.
Az ilyen „speciális” számokat a matematika régóta tanulmányozza, ezeket mezőknek nevezik. A mező olyan elemek halmaza, amelyekhez összeadás, kivonás, szorzás és osztás műveleteket definiálunk.
A Galois* mezők olyan mezők, amelyeknél minden műveletnek egyedi eredménye (+, -, *, /) van a mező bármely két elemére. Galois-mezőket szerkeszthetünk olyan számokra, amelyek 2 hatványai: 2, 4, 8, 16 stb. (valójában bármely p prímszám hatványai, de a gyakorlatban csak a 2 hatványai érdekelnek minket). Például a 16 bites szavaknál ez egy 65 536 elemet tartalmazó mező, amelyek minden párjára bármely művelet eredményét megtalálhatja (+, -, *, /). A fenti egyenletekből származó x, p, alfa, béta, gamma, delta értékeit a számításokhoz a Galois mező elemeinek tekintjük.
Így van egy egyenletrendszerünk, amellyel redundancia kódok blokkjait állíthatjuk össze megfelelő számítógépes program megírásával. Ugyanezzel az egyenletrendszerrel adat-helyreállítást végezhet.
* Ez nem szigorú meghatározás, inkább leírás.
Hogyan lehet visszaállítani az adatokat
Helyreállításra akkor van szükség, ha néhány n + m blokk hiányzik. Ezek lehetnek adatblokkok és redundancia kódblokkok is. Az adatblokkok és/vagy redundancia kódblokkok hiánya azt jelenti, hogy a megfelelő x és/vagy p változók ismeretlenek a fenti egyenletekben.
A Reed-Solomon kódok egyenletei olyan egyenletrendszernek tekinthetők, amelyben minden alfa, béta, gamma, delta érték állandó, a rendelkezésre álló blokknak megfelelő összes x és p ismert változó, a fennmaradó x és p pedig ismeretlenek.
Például ne legyen elérhető az 1., 2., 3. adatblokk és a 2. redundanciakód blokk, akkor az i-edik szócsoporthoz a következő egyenletrendszer lesz (az ismeretlenek pirossal vannak jelölve):
Van egy 4 egyenletből álló rendszerünk 4 ismeretlennel, ami azt jelenti, hogy meg tudjuk oldani és vissza tudjuk állítani az adatokat!
Ebből az egyenletrendszerből számos következtetés levonható a Reed-Solomon kódok adat-helyreállításáról (n adatblokk, m redundancia kódblokk):
- Az adatok visszaállíthatók, ha m blokk vagy kevesebb elveszik. Ha m+1 vagy több blokk elveszik, az adatok nem állíthatók vissza: lehetetlen m egyenletrendszert megoldani m + 1 ismeretlennel.
- Egy adatblokk helyreállításához a fennmaradó n blokk bármelyikét fel kell használnia, és használhatja bármelyik redundanciakódot.
Mi mást kell tudnia
A fenti leírásban elkerülök számos olyan fontos kérdést, amelyek megfontolásához mélyebb merülést igényelnek a matematikában. Konkrétan a következőkről nem mondok semmit:
- A Reed-Solomon kódok egyenletrendszerének rendelkeznie kell (egyedi) megoldással az ismeretlenek bármilyen kombinációjára (legfeljebb m ismeretlen). E követelmény alapján az alfa, béta, gamma és delta értékei kerülnek kiválasztásra.
- Egy egyenletrendszert képesnek kell lennie automatikusan felépíteni (attól függően, hogy mely blokkok nem állnak rendelkezésre) és megoldhatók.
- Fel kell építenünk egy Galois-mezőt: adott szóméret esetén meg kell tudni találni bármely művelet eredményét (+, -, *, /) bármely két elemre.
A cikk végén hivatkozások találhatók e fontos kérdésekkel foglalkozó szakirodalomra.
n és m választása
Hogyan válasszunk n-t és m-t a gyakorlatban? A gyakorlatban az adattároló rendszerekben redundancia kódokat használnak a helytakarékosság érdekében, így m mindig kisebb, mint n. Konkrét értékeik számos tényezőtől függenek, többek között:
- Az adattárolás megbízhatósága. Minél nagyobb m, annál több lemezhibát lehet túlélni, vagyis annál nagyobb a megbízhatóság.
- Redundáns tárolás. Minél nagyobb az m/n arány, annál nagyobb lesz a tároló redundancia, és annál drágább lesz a rendszer.
- Kérjen feldolgozási időt. Minél nagyobb az n + m összeg, annál hosszabb lesz a kérésekre adott válaszidő. Mivel az adatok olvasásához (helyreállítás során) n különböző lemezen tárolt blokk beolvasása szükséges, az olvasási időt a leglassabb lemez határozza meg.
Ezenkívül az adatok több DC-ben való tárolása további korlátozásokat ró az n és m választására: ha az 1 DC ki van kapcsolva, az adatoknak továbbra is elérhetőnek kell lenniük olvasásra. Például 3 DC-ben történő adattárolásnál a következő feltételnek kell teljesülnie: m >= n/2, ellenkező esetben előfordulhat olyan helyzet, hogy 1 DC kikapcsolása esetén az adatok nem érhetők el olvasásra.
3. LRC – Helyi rekonstrukciós kódok
Az adatok Reed-Solomon kódokkal történő helyreállításához n tetszőleges adatblokkot kell használnia. Ez igen jelentős hátrány az elosztott adattároló rendszerek esetében, mert egy törött lemezen lévő adatok visszaállításához a legtöbb másikról is ki kell olvasni az adatokat, ami nagy többletterhelést jelent a lemezeken és a hálózaton.
A leggyakoribb hibák egy adatblokk elérhetetlensége egy lemez meghibásodása vagy túlterhelése miatt. Lehetséges ebben a (leggyakoribb) esetben valahogy csökkenteni az adat-helyreállítás többletterhelését? Kiderült, hogy lehet: vannak kifejezetten erre a célra szolgáló LRC redundancia kódok.
Az LRC (Local Reconstruction Codes) redundanciakódok, amelyeket a Microsoft talált ki a Windows Azure Storage-ban való használatra. Az LRC ötlete a lehető legegyszerűbb: ossza fel az összes adatblokkot két (vagy több) csoportra, és olvassa el a redundancia kódblokkok egy részét minden csoporthoz külön. Ezután néhány redundancia kód blokk az összes adatblokk használatával meg lesz számolva (az LRC-ben ezeket globális redundancia kódoknak nevezik), és néhányat - az adatblokkok két csoportjának egyikével (ezeket helyi redundancia kódoknak nevezik).
Az LRC-t három szám jelöli: nrl, ahol n az adatblokkok száma, r a globális redundancia kód blokkok száma, l a helyi redundancia kód blokkok száma. Az adatok olvasásához, amikor egy adatblokk nem elérhető, csak n/l blokkot kell olvasnia - ez l-szer kevesebb, mint a Reed-Solomon kódokban.
Vegyük például az LRC 6-2-2 sémát. X1–X6 — 6 adatblokk, P1, P2 — 2 globális redundancia blokk, P3, P4 — 2 helyi redundancia blokk.
A P1, P2 redundancia kódblokkok számlálása az összes adatblokk felhasználásával történik. P3 redundancia kód blokk - X1-X3 adatblokk használatával, P4 redundancia kód blokk - X4-X6 adatblokk használatával.
A többi az LRC-ben történik, a Reed-Solomon kóddal analóg módon. A redundancia kódblokkok szavainak megszámlálására szolgáló egyenletek a következők:
Az alfa, béta, gamma, delta számok kiválasztásához számos feltételnek kell teljesülnie, amely garantálja az adat-helyreállítás (vagyis az egyenletrendszer megoldása) lehetőségét. Bővebben róluk olvashatsz .
A gyakorlatban is az XOR műveletet használják a P3, P4 helyi redundanciakódok kiszámítására.
Az LRC egyenletrendszeréből számos következtetés következik:
- Bármely 1 adatblokk helyreállításához elegendő n/l blokkot beolvasni (példánkban n/2).
- Ha az r + l blokkok nem érhetők el, és az összes blokk egy csoportba tartozik, akkor az adatok nem állíthatók vissza. Ezt egy példával könnyű megmagyarázni. Legyen nem elérhető az X1–X3 és a P3 blokk: ezek r + l blokkok ugyanabból a csoportból, esetünkben 4. Ekkor van egy 3 egyenletrendszerünk 4 ismeretlennel, amit nem lehet megoldani.
- Az r + l blokkok elérhetetlenségének minden egyéb esetben (amikor minden csoportból legalább egy blokk elérhető), az LRC-ben lévő adatok visszaállíthatók.
Így az LRC felülmúlja a Reed-Solomon kódokat az egyes hibák utáni adatok helyreállításában. A Reed-Solomon kódokban akár egy adatblokk helyreállításához n blokkot kell használni, az LRC-ben pedig egy adatblokk helyreállításához elég n/l blokkot (példánkban n/2). Másrészt az LRC alulmúlja a Reed-Solomon kódokat a megengedett hibák maximális számát tekintve. A fenti példákban a Reed-Solomon kódok bármilyen 4 hibára képesek visszaállítani az adatokat, az LRC esetében pedig 2 hiba 4 kombinációja létezik, amikor az adatok nem állíthatók vissza.
Az, hogy mi a fontosabb, az adott helyzettől függ, de gyakran az LRC által biztosított túlterhelés megtakarítása meghaladja a valamivel kevésbé megbízható tárolást.
4. Egyéb redundancia kódok
A Reed-Solomon és az LRC kódokon kívül sok más redundanciakód is létezik. A különböző redundanciakódok eltérő matematikát használnak. Íme néhány további redundancia kód:
- Redundancia kód az XOR operátor használatával. Az XOR műveletet n adatblokkon hajtjuk végre, és 1 redundanciakód blokkot kapunk, azaz n+1 sémát (n adatblokk, 1 redundancia kód). Használt , ahol az adatblokkok és a redundanciakódok ciklikusan íródnak a tömb összes lemezére.
- Páros-páratlan algoritmus az XOR műveleten alapuló. Lehetővé teszi 2 redundanciakód blokk felépítését, azaz az n+2 sémát.
- STAR algoritmus az XOR műveleten alapuló. Lehetővé teszi 3 redundanciakód blokk felépítését, azaz az n+3 sémát.
- A piramiskódok egy másik redundanciakód a Microsofttól.
5. Használja a Yandexben
Számos Yandex infrastrukturális projekt redundanciakódokat használ a megbízható adattároláshoz. Íme néhány példa:
- MDS belső objektumtárolás, amiről a cikk elején írtam.
- — A Yandex MapReduce rendszere.
- (Yandex DataBase) - newSQL elosztott adatbázis.
Az MDS LRC redundancia kódokat használ, 8-2-2 sémát. A redundanciakódokkal rendelkező adatok 12 különböző lemezre íródnak különböző szervereken, 3 különböző DC-ben: 4 szerver minden DC-ben. Erről bővebben itt olvashat .
Az YT Reed-Solomon kódokat (6-3. séma), amelyeket elsőként alkalmaztak, és LRC redundanciakódokat (12-2-2. séma), az LRC az előnyben részesített tárolási mód.
Az YDB páros-páratlan alapú redundanciakódokat használ (4-2. ábra). A redundancia kódokról már az YDB-ben .
A különböző redundanciakód-sémák alkalmazása a rendszerekkel szemben támasztott eltérő követelményekből adódik. Például MDS-ben az LRC használatával tárolt adatok egyszerre 3 DC-be kerülnek. Számunkra fontos, hogy az adatok olvashatóak maradjanak, ha bármelyik DC meghibásodik, ezért a blokkokat el kell osztani a DC-k között, hogy ha valamelyik DC nem elérhető, a hozzáférhetetlen blokkok száma ne haladja meg a megengedettet. A 1-8-2 sémában minden DC-be 2 blokkot helyezhet el, majd ha bármelyik DC ki van kapcsolva, 4 blokk nem lesz elérhető, és az adatok olvashatók. Bármilyen sémát választunk is, amikor 4 DC-be helyezzük, minden esetben legyen (r + l) / n >= 3, azaz a tárolási redundancia legalább 0,5%.
A YT-ben a helyzet más: minden YT-klaszter teljes egészében 1 DC-ben található (különböző klaszterek a különböző DC-kben), így nincs ilyen korlátozás. A 12-2-2 séma 33%-os redundanciát biztosít, vagyis olcsóbb az adatok tárolása, és akár 4 egyidejű lemezkiesést is túlél, akárcsak az MDS séma.
A redundanciakódok adattároló és -feldolgozó rendszerekben való használatának számos további jellemzője van: az adat-helyreállítás árnyalatai, a helyreállítás hatása a lekérdezés végrehajtási idejére, az adatrögzítés jellemzői stb. Ezekről és más funkciókról külön fogok beszélni. a redundancia kódok gyakorlati használatáról, ha a téma érdekes lesz.
6. Linkek
- Cikksorozat a Reed-Solomon kódokról és a Galois-mezőkről:
Mélyebb pillantást vetnek a matematikára hozzáférhető nyelven. - A Microsoft cikke az LRC-ről:
A 2. rész röviden elmagyarázza az elméletet, majd megvitatja az LRC-vel szerzett gyakorlati tapasztalatokat. - Páros-páratlan séma:
- STAR rendszer:
- Piramis kódok:
- Redundancia kódok MDS-ben:
- Redundancia kódok a YT-ben:
- Redundancia kódok YDB-ben:
Forrás: will.com