Selline näeb välja koondamine
Andmete salvestamise usaldusväärsuse tõstmiseks kasutatakse arvutisüsteemides laialdaselt koondamiskoode*. Yandexis kasutatakse neid paljudes projektides. Näiteks liiasuskoodide kasutamine meie sisemise objektimälu replikatsiooni asemel säästab miljoneid ilma usaldusväärsust ohverdamata. Kuid hoolimata nende laialdasest kasutamisest on koondamiskoodide toimimise selged kirjeldused väga haruldased. Need, kes tahavad mõista, seisavad silmitsi ligikaudu järgmisega (alates ):
Minu nimi on Vadim, Yandexis töötan välja sisemist objektide salvestamise MDS-i. Selles artiklis kirjeldan lihtsate sõnadega koondamiskoodide (Reed-Salomoni ja LRC koodid) teoreetilisi aluseid. Ma ütlen teile, kuidas see töötab, ilma keerulise matemaatika ja haruldaste terminiteta. Lõpus toon näiteid koondamiskoodide kasutamisest Yandexis.
Ma ei käsitle paljusid matemaatilisi detaile üksikasjalikult, kuid annan lingid neile, kes soovivad sukelduda sügavamale. Samuti märgin, et mõned matemaatilised määratlused ei pruugi olla ranged, kuna artikkel pole mõeldud matemaatikutele, vaid inseneridele, kes soovivad mõista probleemi olemust.
* Ingliskeelses kirjanduses nimetatakse koondamiskoode sageli kustutamiskoodideks.
1. Koonduskoodide olemus
Kõikide koondamiskoodide olemus on äärmiselt lihtne: salvestage (või edastage) andmeid, et need ei läheks kaduma, kui ilmnevad vead (kettarikked, andmeedastusvead jne).
Enamikus* liiasuskoodides jagatakse andmed n andmeplokiks, mille jaoks loendatakse m plokki koondamiskoode, mille tulemuseks on kokku n + m plokki. Liiaskoodid on konstrueeritud nii, et n andmeplokki saab taastada, kasutades ainult osa n + m plokist. Järgmisena käsitleme ainult plokkide koondamiskoode, st neid, milles andmed on jagatud plokkideks.
Kõigi n andmeploki taastamiseks peab teil olema vähemalt n plokki n + m, kuna n plokki ei saa, kui teil on ainult n-1 plokki (sel juhul peaksite võtma 1 ploki õhk”). Kas n juhuslikust plokist n + m on piisav kõigi andmete taastamiseks? See sõltub koondamiskoodide tüübist, näiteks Reed-Solomoni koodid võimaldavad taastada kõik andmed suvalise n ploki abil, kuid LRC koondamiskoodid seda alati ei võimalda.
Andmekogu
Andmesalvestussüsteemides kirjutatakse reeglina kõik andmeplokid ja koondamiskoodiplokid eraldi kettale. Kui suvaline ketas ebaõnnestub, saab algandmeid siiski taastada ja lugeda. Andmeid saab taastada isegi siis, kui mitu ketast korraga rikki lähevad.
Andmeedastus
Liiaskoode saab kasutada andmete usaldusväärseks edastamiseks ebausaldusväärse võrgu kaudu. Edastatud andmed jagatakse plokkideks ning neile arvutatakse liiasuskoodid. Üle võrgu edastatakse nii andmeplokke kui ka koondamiskoodiplokke. Kui suvalistes plokkides ilmnevad vead (kuni teatud arvu plokkideni), saab siiski andmeid üle võrgu vigadeta edastada. Reed-Solomoni koode kasutatakse näiteks andmete edastamiseks optiliste sideliinide kaudu ja satelliitsides.
* Samuti on olemas liiasuskoodid, mille puhul andmed pole plokkideks jagatud, näiteks Hammingi koodid ja CRC koodid, mida kasutatakse laialdaselt Etherneti võrkudes andmeedastuseks. Need on veaparandusliku kodeerimise koodid, mis on mõeldud vigade tuvastamiseks, mitte nende parandamiseks (Hammingi kood võimaldab ka vigu osaliselt parandada).
2. Reed-Saalomoni koodid
Reed-Solomoni koodid on üks enim kasutatavaid koondamiskoode, mis leiutati juba 1960ndatel ja mida kasutati esmakordselt laialdaselt 1980ndatel CD-plaatide masstootmiseks.
Reed-Solomoni koodide mõistmiseks on kaks võtmeküsimust: 1) kuidas luua koondamiskoodide plokke; 2) kuidas taastada andmeid liiaskoodiplokkide abil. Leiame neile vastused.
Lihtsuse huvides eeldame veel, et n = 6 ja m = 4. Teisi skeeme käsitletakse analoogia põhjal.
Kuidas luua liiaskoodiplokke
Iga koondamiskoodide plokki loendatakse teistest sõltumatult. Iga ploki loendamiseks kasutatakse kõiki n andmeplokki. Alloleval diagrammil on X1-X6 andmeplokid, P1-P4 on koondamiskoodi plokid.
Kõik andmeplokid peavad olema ühesuurused ja joondamiseks võib kasutada nullbitte. Saadud liiaskoodiplokid on sama suured kui andmeplokid. Kõik andmeplokid on jagatud sõnadeks (näiteks 16 bitti). Oletame, et jagame andmeplokid k sõnaks. Siis jagatakse ka kõik liiasuskoodide plokid k sõnaks.
Iga liiasusploki i-nda sõna loendamiseks kasutatakse kõigi andmeplokkide i-ndaid sõnu. Need arvutatakse järgmise valemi järgi:
Siin on väärtused x andmeplokkide sõnad, p on koondamiskoodiplokkide sõnad, kõik alfa, beeta, gamma ja delta on spetsiaalselt valitud numbrid, mis on kõigi i jaoks samad. Peab kohe ütlema, et kõik need väärtused ei ole tavalised numbrid, vaid Galois' välja elemendid; toimingud +, -, *, / ei ole meile kõigile tuttavad toimingud, vaid Galois' elementidele sisse viidud eritoimingud. valdkonnas.
Miks on Galois põlde vaja?
Tundub, et kõik on lihtne: jagame andmed plokkideks, plokid sõnadeks, andmeplokkide sõnade abil loendame koondamiskoodiplokkide sõnad - saame koondamiskoodi plokid. Üldiselt see toimib nii, kuid kurat peitub detailides:
- Nagu eespool öeldud, on sõna suurus fikseeritud, meie näites 16 bitti. Ülaltoodud Reed-Solomoni koodide valemid on sellised, et tavaliste täisarvude kasutamisel ei pruugi p arvutamise tulemus olla esindatav kehtiva suurusega sõnaga.
- Andmete taastamisel käsitletakse ülaltoodud valemeid võrrandite süsteemina, mis tuleb andmete taastamiseks lahendada. Lahendusprotsessi käigus võib osutuda vajalikuks täisarvude üksteisega jagamine, mille tulemuseks on reaalarv, mida ei saa arvutimälus täpselt esitada.
Need probleemid takistavad täisarvude kasutamist Reed-Solomoni koodide jaoks. Ülesande lahendus on originaalne, seda saab kirjeldada järgmiselt: mõtleme välja spetsiaalsed arvud, mida saab esitada vajaliku pikkusega sõnadega (näiteks 16 bitti) ja kõigi toimingute sooritamise tulemus, millel (lisa , lahutamine, korrutamine, jagamine) esitatakse ka arvuti mällu, kasutades selleks vajaliku pikkusega sõnu.
Selliseid “erilisi” numbreid on matemaatika uurinud pikka aega, neid nimetatakse väljadeks. Väli on elementide kogum, mille jaoks on määratletud liitmise, lahutamise, korrutamise ja jagamise toimingud.
Galois* väljad on väljad, mille iga toimingu (+, -, *, /) kahe välja elemendi jaoks on kordumatu tulemus. Galois' väljad saab konstrueerida arvude jaoks, mis on astmed 2: 2, 4, 8, 16 jne (tegelikult iga algarvu p astmed, kuid praktikas huvitavad meid ainult 2 astmed). Näiteks 16-bitiste sõnade puhul on see väli, mis sisaldab 65 536 elementi, mille iga paari kohta leiate mis tahes toimingu tulemuse (+, -, *, /). Ülaltoodud võrrandite väärtusi x, p, alfa, beeta, gamma, delta loetakse arvutustes Galois' välja elementideks.
Seega on meil võrrandisüsteem, mille abil saame sobiva arvutiprogrammi kirjutades koostada liiasuskoodide plokke. Sama võrrandisüsteemi abil saate andmeid taastada.
* See ei ole range määratlus, vaid pigem kirjeldus.
Kuidas andmeid taastada
Taastamine on vajalik, kui mõni n + m plokkidest on puudu. Need võivad olla nii andmeplokid kui ka liiaskoodiplokid. Andmeplokkide ja/või liiaskoodiplokkide puudumine tähendab, et vastavad x ja/või p muutujad on ülaltoodud võrrandites tundmatud.
Reed-Solomoni koodide võrrandeid saab vaadelda võrrandite süsteemina, milles kõik alfa-, beeta-, gamma- ja delta väärtused on konstandid, kõik saadaolevatele plokkidele vastavad x ja p on tuntud muutujad ning ülejäänud x ja p on tundmatud.
Olgu näiteks andmeplokid 1, 2, 3 ja liiaskoodiplokk 2 kättesaamatud, siis i-nda sõnarühma jaoks on järgmine võrrandisüsteem (tundmatud on märgitud punasega):
Meil on 4 võrrandi süsteem 4 tundmatuga, mis tähendab, et saame selle lahendada ja andmed taastada!
Sellest võrrandisüsteemist tuleneb rida järeldusi Reed-Solomoni koodide andmete taastamise kohta (n andmeplokki, m liiaskoodiplokki):
- Andmeid saab taastada, kui kaotsi läheb m plokki või vähem. Kui kaob m+1 või enam plokki, ei saa andmeid taastada: m + 1 tundmatuga võrrandisüsteemi on võimatu lahendada.
- Kasvõi ühe andmeploki taastamiseks peate kasutama mis tahes n ülejäänud plokkidest ja võite kasutada mis tahes liiasuskoode.
Mida veel peate teadma
Ülaltoodud kirjelduses väldin mitmeid olulisi küsimusi, mille käsitlemiseks on vaja sügavamat sukeldumist matemaatikasse. Eelkõige ei ütle ma midagi järgmise kohta:
- Reed-Solomoni koodide võrrandisüsteemil peab olema (unikaalne) lahendus mis tahes tundmatute kombinatsiooni jaoks (mitte rohkem kui m tundmatu). Selle nõude alusel valitakse alfa, beeta, gamma ja delta väärtused.
- Võrrandisüsteemi peab saama automaatselt konstrueerida (olenevalt sellest, millised plokid pole saadaval) ja lahendatavad.
- Peame ehitama Galois' välja: etteantud sõnasuuruse korral suutma leida mis tahes tehte (+, -, *, /) tulemuse mis tahes kahe elemendi jaoks.
Artikli lõpus on viited neid olulisi teemasid käsitlevale kirjandusele.
Valik n ja m
Kuidas n ja m praktikas valida? Praktikas kasutatakse andmesalvestussüsteemides ruumi kokkuhoiuks koondamiskoode, mistõttu m valitakse alati väiksemaks kui n. Nende konkreetsed väärtused sõltuvad paljudest teguritest, sealhulgas:
- Andmete salvestamise usaldusväärsus. Mida suurem m, seda suurem on kettatõrgete arv, mida saab üle elada, st seda suurem on töökindlus.
- Üleliigne salvestusruum. Mida suurem on m/n suhe, seda suurem on salvestusruumi liiasus ja seda kallim on süsteem.
- Taotle töötlemise aega. Mida suurem on summa n + m, seda pikem on päringutele vastamise aeg. Kuna andmete lugemiseks (taastamise ajal) on vaja lugeda n erinevale kettale salvestatud plokki, määrab lugemisaja kõige aeglasem ketas.
Lisaks seab andmete salvestamine mitmesse DC-sse lisapiirangud n ja m valikule: kui 1 DC on välja lülitatud, peavad andmed siiski lugemiseks kättesaadavad olema. Näiteks andmete salvestamisel 3 DC-s peab olema täidetud järgmine tingimus: m >= n/2, vastasel juhul võib tekkida olukord, kus andmed pole lugemiseks kättesaadavad, kui 1 DC on välja lülitatud.
3. LRC – kohalikud rekonstrueerimiskoodid
Andmete taastamiseks Reed-Solomoni koodide abil peate kasutama n suvalist andmeplokki. See on hajutatud andmesalvestussüsteemide jaoks väga oluline puudus, kuna ühel katkisel kettal olevate andmete taastamiseks peate lugema andmeid enamikult teistelt, tekitades ketastele ja võrgule suure lisakoormuse.
Levinumad vead on ühe andmeploki kättesaamatus ühe ketta rikke või ülekoormuse tõttu. Kas sellisel (kõige tavalisemal) juhul on võimalik andmete taastamise liigset koormust kuidagi vähendada? Selgub, et saate: selleks on spetsiaalselt LRC koondamiskoodid.
LRC (Local Reconstruction Codes) on Microsofti leiutatud liiasuskoodid kasutamiseks Windows Azure Storage'is. LRC idee on võimalikult lihtne: jagage kõik andmeplokid kaheks (või enamaks) rühmaks ja lugege osa iga rühma koondamiskoodiplokkidest eraldi. Seejärel loendatakse mõned koondamiskoodiplokid kõigi andmeplokkide abil (LRC-s nimetatakse neid globaalseteks liiasuskoodideks) ja mõnda - kasutades ühte kahest andmeplokkide rühmast (neid nimetatakse kohalikeks liiasuskoodideks).
LRC tähistatakse kolme numbriga: nrl, kus n on andmeplokkide arv, r on globaalsete koondamiskoodiplokkide arv, l on kohalike koondamiskoodiplokkide arv. Andmete lugemiseks, kui üks andmeplokk pole saadaval, peate lugema ainult n/l plokke – seda on l korda vähem kui Reed-Solomoni koodides.
Näiteks kaaluge LRC 6-2-2 skeemi. X1–X6 — 6 andmeplokki, P1, P2 — 2 globaalset koondamisplokki, P3, P4 — 2 lokaalset liiasuse plokki.
Liiaskoodiplokke P1, P2 loendatakse kõiki andmeplokke kasutades. Liiaskoodiplokk P3 - andmeplokkide X1-X3 abil, koondamiskoodiplokk P4 - andmeplokkide X4-X6 abil.
Ülejäänu tehakse LRC-s analoogselt Reed-Solomoni koodidega. Liiaskoodiplokkide sõnade loendamise võrrandid on järgmised:
Numbrite alfa, beeta, gamma, delta valimiseks peavad olema täidetud mitmed tingimused, mis tagavad andmete taastamise (st võrrandisüsteemi lahendamise) võimaluse. Täpsemalt saate nende kohta lugeda .
Ka praktikas kasutatakse XOR-operatsiooni kohalike liiasuskoodide P3, P4 arvutamiseks.
LRC võrrandisüsteemist tuleneb mitmeid järeldusi:
- Mis tahes 1 andmeploki taastamiseks piisab n/l plokkide lugemisest (meie näites n/2).
- Kui r + l plokid pole saadaval ja kõik plokid kuuluvad ühte rühma, ei saa andmeid taastada. Seda on lihtne näitega selgitada. Olgu plokid X1–X3 ja P3 kättesaamatud: need on r + l plokid samast rühmast, meie puhul 4. Siis on meil 3 võrrandi süsteem 4 tundmatuga, mida ei saa lahendada.
- Kõigil muudel r + l-plokkide kättesaamatuse juhtudel (kui igast rühmast on saadaval vähemalt üks plokk), saab LRC-s olevaid andmeid taastada.
Seega ületab LRC Reed-Solomoni koode andmete taastamisel pärast üksikuid vigu. Reed-Solomoni koodides tuleb kasvõi ühe andmeploki taastamiseks kasutada n plokki ja LRC puhul piisab ühe andmeploki taastamiseks n/l plokkidest (meie näites n/2). Teisest küljest jääb LRC Reed-Solomoni koodidele alla maksimaalse lubatud vigade arvu poolest. Ülaltoodud näidetes suudavad Reed-Solomoni koodid taastada andmeid mis tahes 4 vea korral ja LRC puhul on kaks kombinatsiooni neljast veast, kui andmeid ei saa taastada.
Mis on olulisem, sõltub konkreetsest olukorrast, kuid sageli kaalub LRC pakutav ülekoormuse kokkuhoid üles veidi vähem töökindla hoiustamise.
4. Muud koondamiskoodid
Lisaks Reed-Solomoni ja LRC koodidele on palju muid koondamiskoode. Erinevad koondamiskoodid kasutavad erinevat matemaatikat. Siin on mõned muud koondamiskoodid:
- Koonduskood operaatori XOR abil. XOR-operatsioon sooritatakse n andmeplokil ja saadakse 1 liiasuskoodide plokk ehk n+1 skeem (n andmeplokki, 1 liiasuskood). Kasutatakse , kus andmeplokid ja liiasuskoodid kirjutatakse tsükliliselt kõigile massiivi ketastele.
- Paaritu-paaritu algoritm, mis põhineb XOR-operatsioonil. Võimaldab ehitada 2 plokki koondamiskoode, see tähendab n+2 skeemi.
- STAR-algoritm, mis põhineb XOR-operatsioonil. Võimaldab ehitada 3 plokki koondamiskoode, see tähendab n+3 skeemi.
- Püramiidkoodid on veel üks Microsofti koondamiskoodid.
5. Kasutage Yandexis
Mitmed Yandexi infrastruktuuriprojektid kasutavad usaldusväärseks andmete salvestamiseks koondamiskoode. siin on mõned näidised:
- MDS-i sisemine objektisalvestus, millest kirjutasin artikli alguses.
- - Yandexi süsteem MapReduce.
- (Yandex DataBase) - uusSQL hajutatud andmebaas.
MDS kasutab LRC koondamiskoode, 8-2-2 skeemi. Andmed koondamiskoodidega kirjutatakse 12 erinevale kettale erinevates serverites 3 erinevas DC-s: igas DC-s 4 serverit. Lisateavet selle kohta leiate artiklist .
YT kasutab nii Reed-Solomoni koode (skeem 6-3), mis võeti kasutusele esimesena, kui ka LRC koondamiskoode (skeem 12-2-2), kusjuures LRC on eelistatud salvestusmeetod.
YDB kasutab paaris-paaritutel põhinevaid koondamiskoode (Joonis 4-2). Juba YDB koondamiskoodide kohta .
Erinevate koondamiskoodiskeemide kasutamine on tingitud erinevatest nõuetest süsteemidele. Näiteks MDS-is paigutatakse LRC abil salvestatud andmed korraga 3 DC-sse. Meie jaoks on oluline, et andmed jääksid lugemiseks kättesaadavaks, kui 1 DC-st ebaõnnestub, seetõttu tuleb plokid jaotada DC-de vahel nii, et kui mõni alalisvoolu pole saadaval, pole ligipääsmatute plokkide arv lubatud. Skeemis 8-2-2 saate igasse alalisvoolu paigutada 4 plokki, siis kui mis tahes DC on välja lülitatud, ei ole 4 plokki saadaval ja andmeid saab lugeda. Ükskõik millise skeemi me selle 3 DC-sse paigutades valime, peaks igal juhul olema (r + l) / n >= 0,5, see tähendab, et salvestusruumi koondamine on vähemalt 50%.
YT-s on olukord erinev: iga YT-klaster asub täielikult 1 DC-s (erinevates DC-des erinevad klastrid), seega sellist piirangut pole. Skeem 12-2-2 annab 33% liiasuse ehk andmete salvestamine on odavam ning suudab ka kuni 4 samaaegset kettakatkestust üle elada, nagu MDS-skeemgi.
Liiaskoodide kasutamisel andmesalvestus- ja töötlemissüsteemides on veel palju funktsioone: andmete taastamise nüansid, taastamise mõju päringu täitmisajale, andmete salvestamise omadused jne. Nendest ja muudest funktsioonidest räägin eraldi. liiasuskoodide kasutamisest praktikas, kui teema pakub huvi.
6. Lingid
- Artiklisari Reed-Salomoni koodide ja Galois' väljade kohta:
Nad vaatavad matemaatikat ligipääsetavas keeles sügavamalt. - Microsofti artikkel LRC kohta:
2. osas selgitatakse lühidalt teooriat ja seejärel arutatakse kogemusi LRC-ga praktikas. - Paaris-paaritu skeem:
- TÄHTE skeem:
- Püramiidi koodid:
- MDS-i koondamiskoodid:
- YT koondamiskoodid:
- YDB koondamiskoodid:
Allikas: www.habr.com