Tältä redundanssi näyttää
Redundanssikoodeja* käytetään laajalti tietokonejärjestelmissä tietojen tallennuksen luotettavuuden lisäämiseksi. Yandexissä niitä käytetään monissa projekteissa. Esimerkiksi redundanssikoodien käyttäminen replikoinnin sijaan sisäisessä objektimuistissamme säästää miljoonia luotettavuudesta tinkimättä. Mutta huolimatta niiden laajasta käytöstä, selkeät kuvaukset redundanssikoodien toiminnasta ovat erittäin harvinaisia. Ne, jotka haluavat ymmärtää, kohtaavat suunnilleen seuraavan (alkaen ):
Nimeni on Vadim, Yandexissä kehitän sisäistä objektitallennusta MDS:ää. Tässä artikkelissa kuvailen yksinkertaisin sanoin redundanssikoodien (Reed-Solomon- ja LRC-koodit) teoreettisia perusteita. Kerron sinulle, kuinka se toimii, ilman monimutkaista matematiikkaa ja harvinaisia termejä. Lopuksi annan esimerkkejä redundanssikoodien käytöstä Yandexissa.
En käsittele useita matemaattisia yksityiskohtia yksityiskohtaisesti, mutta annan linkkejä niille, jotka haluavat sukeltaa syvemmälle. Huomaan myös, että jotkin matemaattiset määritelmät eivät välttämättä ole tiukkoja, koska artikkelia ei ole tarkoitettu matemaatikoille, vaan insinööreille, jotka haluavat ymmärtää ongelman olemuksen.
* Englanninkielisessä kirjallisuudessa redundanssikoodeja kutsutaan usein poistokoodeiksi.
1. Redundanssikoodien ydin
Kaikkien redundanssikoodien olemus on äärimmäisen yksinkertainen: tallenna (tai lähetä) tiedot, jotta se ei katoa virheiden sattuessa (levyhäiriöt, tiedonsiirtovirheet jne.).
Useimmissa* redundanssikoodeissa data on jaettu n tietolohkoon, joille lasketaan m lohkoa redundanssikoodeja, jolloin saadaan yhteensä n + m lohkoa. Redundanssikoodit on rakennettu siten, että n tietolohkoa voidaan palauttaa käyttämällä vain osaa n + m lohkosta. Seuraavaksi tarkastelemme vain lohkoredundanssikoodeja, eli niitä, joissa tiedot on jaettu lohkoihin.
Jotta voit palauttaa kaikki n tietolohkoa, sinulla on oltava vähintään n lohkoa n + m, koska et voi saada n lohkoa, jos sinulla on vain n-1 lohko (tässä tapauksessa sinun pitäisi ottaa 1 lohko ilmaa”). Riittääkö n satunnaista n + m lohkoa palauttamaan kaikki tiedot? Tämä riippuu redundanssikoodien tyypistä, esimerkiksi Reed-Solomon-koodien avulla voit palauttaa kaikki tiedot mielivaltaisilla n-lohkoilla, mutta LRC-redundanssikoodit eivät aina.
Tietovarasto
Tiedontallennusjärjestelmissä jokainen tietolohko ja redundanssikoodilohko kirjoitetaan pääsääntöisesti erilliselle levylle. Sitten, jos mielivaltainen levy epäonnistuu, alkuperäiset tiedot voidaan silti palauttaa ja lukea. Tiedot voidaan palauttaa, vaikka useat levyt epäonnistuvat samanaikaisesti.
Tiedonsiirto
Redundanssikoodeja voidaan käyttää tiedon siirtämiseen luotettavasti epäluotettavan verkon yli. Lähetetyt tiedot jaetaan lohkoihin ja niille lasketaan redundanssikoodit. Sekä datalohkot että redundanssikoodilohkot lähetetään verkon yli. Jos sattuu virheitä mielivaltaisissa lohkoissa (jopa tiettyyn määrään lohkoja), dataa voidaan silti siirtää verkon yli ilman virheitä. Reed-Solomon-koodeja käytetään esimerkiksi tiedon siirtämiseen optisten viestintälinjojen kautta ja satelliittiviestinnässä.
* On myös redundanssikoodeja, joissa dataa ei ole jaettu lohkoihin, kuten Hamming-koodit ja CRC-koodit, joita käytetään laajasti tiedonsiirrossa Ethernet-verkoissa. Nämä ovat virheenkorjaavan koodauksen koodeja, ne on suunniteltu havaitsemaan virheet, ei korjaamaan niitä (Hamming-koodi sallii myös virheiden osittaisen korjaamisen).
2. Reed-Solomon koodit
Reed-Solomon-koodit ovat yksi laajimmin käytetyistä redundanssikoodeista, jotka keksittiin jo 1960-luvulla ja joita käytettiin ensimmäisen kerran laajalti 1980-luvulla CD-levyjen massatuotantoon.
Reed-Solomon-koodien ymmärtämiseen on kaksi avainkysymystä: 1) kuinka luodaan redundanssikoodien lohkoja; 2) kuinka palauttaa tiedot redundanssikoodilohkojen avulla. Etsitään vastauksia niihin.
Yksinkertaisuuden vuoksi oletetaan lisäksi, että n=6 ja m=4. Muita järjestelmiä tarkastellaan analogisesti.
Kuinka luoda redundanssikoodilohkoja
Jokainen redundanssikoodien lohko lasketaan muista riippumatta. Kaikkia n datalohkoa käytetään kunkin lohkon laskemiseen. Alla olevassa kaaviossa X1-X6 ovat datalohkoja, P1-P4 ovat redundanssikoodilohkoja.
Kaikkien tietolohkojen on oltava samankokoisia, ja nollabittejä voidaan käyttää kohdistukseen. Tuloksena olevat redundanssikoodilohkot ovat samankokoisia kuin datalohkot. Kaikki datalohkot on jaettu sanoiksi (esimerkiksi 16 bittiä). Oletetaan, että jaamme tietolohkot k sanaksi. Sitten kaikki redundanssikoodien lohkot jaetaan myös k sanaan.
Kunkin redundanssilohkon i:nnen sanan laskemiseen käytetään kaikkien tietolohkojen i:ttä sanaa. Ne lasketaan seuraavan kaavan mukaan:
Tässä arvot x ovat tietolohkojen sanoja, p ovat redundanssikoodilohkojen sanoja, kaikki alfa, beta, gamma ja delta ovat erityisesti valittuja lukuja, jotka ovat samat kaikille i:lle. On heti sanottava, että kaikki nämä arvot eivät ole tavallisia lukuja, vaan Galois-kentän elementtejä; operaatiot +, -, *, / eivät ole meille kaikille tuttuja operaatioita, vaan erikoisoperaatioita, jotka on otettu käyttöön Galois'n elementeissä ala.
Miksi Galois-peltoja tarvitaan?
Näyttää siltä, että kaikki on yksinkertaista: jaamme tiedot lohkoihin, lohkot sanoiksi, tietolohkojen sanojen avulla laskemme redundanssikoodilohkojen sanat - saamme redundanssikoodilohkot. Yleensä se toimii näin, mutta paholainen on yksityiskohdissa:
- Kuten edellä mainittiin, sanan koko on kiinteä, esimerkissämme 16 bittiä. Yllä olevat kaavat Reed-Solomon-koodeille ovat sellaisia, että tavallisia kokonaislukuja käytettäessä p:n laskentatulos ei välttämättä ole esitettävissä kelvollisen kokoisella sanalla.
- Tietoja palautettaessa yllä olevia kaavoja pidetään yhtälöjärjestelmänä, joka on ratkaistava tietojen palauttamiseksi. Ratkaisuprosessin aikana saattaa olla tarpeen jakaa kokonaisluvut keskenään, jolloin tuloksena on reaaliluku, jota ei voida esittää tarkasti tietokoneen muistissa.
Nämä ongelmat estävät kokonaislukujen käytön Reed-Solomon-koodeissa. Ongelman ratkaisu on alkuperäinen, sitä voidaan kuvata seuraavasti: keksitään erityisiä lukuja, jotka voidaan esittää vaaditun pituisilla sanoilla (esim. 16 bittiä), ja tulos kaikkien toimintojen suorittamisesta, joille (lisäys , vähennys-, kerto- ja jakolasku) esitetään myös tietokoneen muistissa vaaditun pituisin sanoin.
Matematiikka on tutkinut tällaisia "erikoislukuja" pitkään; niitä kutsutaan kentäksi. Kenttä on joukko elementtejä, joille on määritelty yhteen-, vähennys-, kerto- ja jakolaskuoperaatiot.
Galois*-kentät ovat kenttiä, joille jokaiselle operaatiolle (+, -, *, /) on yksilöllinen tulos kahdelle kentän elementille. Galois-kenttiä voidaan rakentaa luvuille, jotka ovat luvun 2 potenssit: 2, 4, 8, 16 jne. (itse asiassa minkä tahansa alkuluvun p potenssit, mutta käytännössä meitä kiinnostavat vain luvun 2 potenssit). Esimerkiksi 16-bittisille sanoille tämä on kenttä, joka sisältää 65 536 elementtiä, joista jokaiselle löytyy minkä tahansa toiminnon tulos (+, -, *, /). Arvoja x, p, alfa, beta, gamma, delta yllä olevista yhtälöistä pidetään Galois-kentän elementteinä laskelmissa.
Näin ollen meillä on yhtälöjärjestelmä, jolla voimme rakentaa redundanssikoodien lohkoja kirjoittamalla sopivan tietokoneohjelman. Käyttämällä samaa yhtälöjärjestelmää voit suorittaa tietojen palautuksen.
* Tämä ei ole tiukka määritelmä, vaan pikemminkin kuvaus.
Kuinka palauttaa tiedot
Restaurointia tarvitaan, kun osa n + m lohkosta puuttuu. Nämä voivat olla sekä datalohkoja että redundanssikoodilohkoja. Datalohkojen ja/tai redundanssikoodilohkojen puuttuminen tarkoittaa, että vastaavat x- ja/tai p-muuttujat ovat tuntemattomia yllä olevissa yhtälöissä.
Reed-Solomon-koodien yhtälöitä voidaan pitää yhtälöjärjestelmänä, jossa kaikki alfa-, beeta-, gamma- ja delta-arvot ovat vakioita, kaikki käytettävissä olevia lohkoja vastaavat x ja p ovat tunnettuja muuttujia ja loput x ja p ovat vakioita. ovat tuntemattomia.
Jos esimerkiksi tietolohkot 1, 2, 3 ja redundanssikoodilohko 2 eivät ole käytettävissä, i:nnelle sanaryhmälle tulee seuraava yhtälöjärjestelmä (tuntemattomat on merkitty punaisella):
Meillä on 4 yhtälön järjestelmä, jossa on 4 tuntematonta, mikä tarkoittaa, että voimme ratkaista sen ja palauttaa tiedot!
Tästä yhtälöjärjestelmästä seuraa useita johtopäätöksiä Reed-Solomon-koodien tietojen palauttamisesta (n tietolohkoa, m redundanssikoodilohkoa):
- Tiedot voidaan palauttaa, jos m lohkoa tai vähemmän katoaa. Jos m+1 tai useampi lohko katoaa, dataa ei voida palauttaa: on mahdotonta ratkaista m yhtälöjärjestelmää m + 1 tuntemattomilla.
- Jos haluat palauttaa edes yhden tietolohkon, sinun on käytettävä mitä tahansa n jäljellä olevista lohkoista, ja voit käyttää mitä tahansa redundanssikoodeista.
Mitä muuta sinun täytyy tietää
Yllä olevassa kuvauksessa vältän useita tärkeitä asioita, jotka edellyttävät syvempää sukellusta matematiikkaan. Erityisesti en sano mitään seuraavista:
- Reed-Solomon-koodien yhtälöjärjestelmällä on oltava (ainutlaatuinen) ratkaisu mille tahansa tuntemattomien yhdistelmälle (enintään m tuntematonta). Tämän vaatimuksen perusteella valitaan alfa-, beta-, gamma- ja delta-arvot.
- Yhtälöjärjestelmä on voitava muodostaa automaattisesti (riippuen siitä, mitkä lohkot eivät ole käytettävissä) ja ratkaistava.
- Meidän on rakennettava Galois-kenttä: annetulle sanan koolle pystyttävä löytämään minkä tahansa operaation tulos (+, -, *, /) mille tahansa kahdelle elementille.
Artikkelin lopussa on viittauksia näitä tärkeitä asioita käsittelevään kirjallisuuteen.
Valinta n ja m
Kuinka valita n ja m käytännössä? Käytännössä tiedontallennusjärjestelmissä käytetään redundanssikoodeja tilan säästämiseksi, joten m valitaan aina pienemmäksi kuin n. Niiden erityisarvot riippuvat useista tekijöistä, mukaan lukien:
- Tietojen tallennuksen luotettavuus. Mitä suurempi m, sitä suurempi määrä levyvikoja voidaan selvitä, eli sitä suurempi on luotettavuus.
- Ylimääräinen tallennustila. Mitä korkeampi m/n-suhde on, sitä suurempi on tallennustilan redundanssi ja sitä kalliimpi järjestelmä on.
- Pyydä käsittelyaikaa. Mitä suurempi summa n + m, sitä pidempi vastausaika pyyntöihin on. Koska tietojen lukeminen (palautuksen aikana) vaatii n lohkon lukemista n eri levylle, lukuaika määräytyy hitain levyn mukaan.
Lisäksi tietojen tallentaminen useisiin DC:ihin asettaa lisärajoituksia n:n ja m:n valinnalle: jos 1 DC kytketään pois päältä, datan on edelleen oltava luettavissa. Esimerkiksi tallennettaessa dataa 3 DC:hen tulee täyttyä seuraava ehto: m >= n/2, muuten voi syntyä tilanne, jossa data ei ole luettavissa, kun 1 DC on pois päältä.
3. LRC - Local Reconstruction Codes
Tietojen palauttamiseksi Reed-Solomon-koodeilla sinun on käytettävä n mielivaltaista tietolohkoa. Tämä on erittäin merkittävä haitta hajautetuille tiedontallennusjärjestelmille, koska yhden rikkinäisen levyn tietojen palauttamiseksi joudut lukemaan tietoja useimmilta muilta, mikä aiheuttaa suuren lisäkuormituksen levyille ja verkkoon.
Yleisimmät virheet ovat yhden tietolohkon saavuttamattomuus yhden levyn vian tai ylikuormituksen vuoksi. Onko mahdollista jotenkin vähentää ylimääräistä kuormitusta tietojen palauttamiseen tässä (yleisimmässä) tapauksessa? Osoittautuu, että voit: LRC:n redundanssikoodeja on erityisesti tätä tarkoitusta varten.
LRC (Local Reconstruction Codes) ovat Microsoftin keksimiä redundanssikoodeja käytettäväksi Windows Azure Storagessa. LRC:n idea on mahdollisimman yksinkertainen: jaa kaikki tietolohkot kahteen (tai useampaan) ryhmään ja lue osa redundanssikoodilohkoista jokaiselle ryhmälle erikseen. Sitten jotkin redundanssikoodilohkot lasketaan käyttämällä kaikkia datalohkoja (LRC:ssä niitä kutsutaan globaaleiksi redundanssikoodeiksi), ja jotkut - käyttämällä yhtä kahdesta tietolohkoryhmästä (niitä kutsutaan paikallisiksi redundanssikoodeiksi).
LRC on merkitty kolmella numerolla: nrl, jossa n on datalohkojen lukumäärä, r on globaalien redundanssikoodilohkojen lukumäärä, l on paikallisten redundanssikoodilohkojen lukumäärä. Jos haluat lukea tietoja, kun yksi tietolohko ei ole käytettävissä, sinun on luettava vain n/l lohkoa - tämä on l kertaa vähemmän kuin Reed-Solomon-koodeissa.
Harkitse esimerkiksi LRC 6-2-2 -mallia. X1–X6 — 6 datalohkoa, P1, P2 — 2 globaalia redundanssilohkoa, P3, P4 — 2 paikallista redundanssilohkoa.
Redundanssikoodilohkot P1, P2 lasketaan käyttäen kaikkia datalohkoja. Redundanssikoodilohko P3 - tietolohkoilla X1-X3, redundanssikoodilohko P4 - tietolohkoilla X4-X6.
Loput tehdään LRC:ssä analogisesti Reed-Solomon-koodien kanssa. Yhtälöt redundanssikoodilohkojen sanojen laskemiseksi ovat:
Jotta voit valita numerot alfa, beta, gamma, delta, useiden ehtojen on täytyttävä tietojen palauttamisen (eli yhtälöjärjestelmän ratkaisemisen) varmistamiseksi. Voit lukea niistä lisää kohdasta .
Myös käytännössä XOR-operaatiota käytetään paikallisten redundanssikoodien P3, P4 laskemiseen.
LRC:n yhtälöjärjestelmästä seuraa useita johtopäätöksiä:
- Minkä tahansa 1 tietolohkon palauttamiseksi riittää n/l lohkon lukeminen (n/2 esimerkissämme).
- Jos r + l -lohkot eivät ole käytettävissä ja kaikki lohkot sisältyvät yhteen ryhmään, tietoja ei voida palauttaa. Tämä on helppo selittää esimerkillä. Olkoon lohkot X1–X3 ja P3 poissa käytöstä: nämä ovat r + l lohkoa samasta ryhmästä, meidän tapauksessamme 4. Sitten meillä on 3 yhtälöjärjestelmä, jossa on 4 tuntematonta, joita ei voida ratkaista.
- Kaikissa muissa tapauksissa, joissa r + l lohko ei ole käytettävissä (kun vähintään yksi lohko on saatavilla kustakin ryhmästä), LRC:n tiedot voidaan palauttaa.
Näin ollen LRC ylittää Reed-Solomon-koodit tietojen palauttamisessa yksittäisten virheiden jälkeen. Reed-Solomon-koodeissa jopa yhden tietolohkon palauttamiseen tarvitaan n lohkoa, ja LRC:ssä yhden tietolohkon palauttamiseen riittää n/l lohko (esimerkissämme n/2). Toisaalta LRC on huonompi kuin Reed-Solomon -koodit sallittujen virheiden enimmäismäärän suhteen. Yllä olevissa esimerkeissä Reed-Solomon-koodit voivat palauttaa tiedot kaikista neljästä virheestä, ja LRC:ssä on kaksi neljän virheen yhdistelmää, kun tietoja ei voida palauttaa.
Tärkeämpää riippuu tilanteesta, mutta usein LRC:n tuomat säästöt ylikuormituksessa ovat suuremmat kuin hieman vähemmän luotettava varastointi.
4. Muut redundanssikoodit
Reed-Solomon- ja LRC-koodien lisäksi on olemassa monia muita redundanssikoodeja. Eri redundanssikoodit käyttävät erilaista matematiikkaa. Tässä on joitain muita redundanssikoodeja:
- Redundanssikoodi XOR-operaattorilla. XOR-toiminto suoritetaan n datalohkolle ja saadaan 1 lohko redundanssikoodeja, eli n+1 skeema (n datalohkoa, 1 redundanssikoodi). Käytetty , jossa datalohkot ja redundanssikoodit kirjoitetaan syklisesti kaikille taulukon levyille.
- Parillinen pariton algoritmi, joka perustuu XOR-operaatioon. Voit rakentaa 2 lohkoa redundanssikoodeja eli n+2-mallia.
- STAR-algoritmi, joka perustuu XOR-operaatioon. Voit rakentaa 3 lohkoa redundanssikoodeja eli n+3-mallia.
- Pyramidikoodit ovat muita Microsoftin redundanssikoodeja.
5. Käytä Yandexissa
Useat Yandexin infrastruktuuriprojektit käyttävät redundanssikoodeja luotettavaan tietojen tallentamiseen. Tässä on joitain esimerkkejä:
- MDS:n sisäinen objektimuisti, josta kirjoitin artikkelin alussa.
- - Yandexin MapReduce-järjestelmä.
- (Yandex DataBase) - uusi SQL-hajautettu tietokanta.
MDS käyttää LRC-redundanssikoodeja, 8-2-2-mallia. Redundanssikoodeilla varustetut tiedot kirjoitetaan 12 eri levylle eri palvelimissa 3 eri DC:ssä: 4 palvelinta jokaisessa DC:ssä. Lue tästä lisää kohdasta .
YT käyttää sekä Reed-Solomon-koodeja (kaavio 6-3), jotka otettiin käyttöön ensimmäisenä, että LRC-redundanssikoodeja (kaavio 12-2-2), ja LRC on suositeltu tallennustapa.
YDB käyttää parillisiin parittoihin perustuvia redundanssikoodeja (Kuva 4-2). Tietoja redundanssikoodeista jo YDB:ssä .
Erilaisten redundanssikoodimenetelmien käyttö johtuu erilaisista järjestelmille asetetuista vaatimuksista. Esimerkiksi MDS:ssä LRC:llä tallennetut tiedot sijoitetaan kolmeen DC:hen kerralla. Meille on tärkeää, että data pysyy luettavissa, jos yksi DC:istä epäonnistuu, joten lohkot on jaettava DC:iden kesken siten, että jos jokin DC ei ole käytettävissä, ei saavutettavissa olevien lohkojen määrä on suurempi kuin sallittu. Kaavassa 3-1-8 voit sijoittaa 2 lohkoa jokaiseen DC:hen, sitten kun mikä tahansa DC on kytketty pois päältä, 2 lohkoa ei ole käytettävissä ja tiedot voidaan lukea. Riippumatta siitä, minkä järjestelmän valitsemme sijoittaessaan sen 4 DC:hen, sen tulisi joka tapauksessa olla (r + l) / n >= 4, eli tallennustilan redundanssi on vähintään 3%.
YT:ssä tilanne on erilainen: jokainen YT-klusteri sijaitsee kokonaan 1 DC:ssä (eri klusterit eri DC:issä), joten tällaista rajoitusta ei ole. 12-2-2-järjestelmä tarjoaa 33 %:n redundanssin, eli tietojen tallentaminen on halvempaa, ja se voi myös kestää jopa 4 samanaikaista levykatkosta, aivan kuten MDS-järjestelmä.
Redundanssikoodien käytössä tietojen tallennus- ja käsittelyjärjestelmissä on monia muita ominaisuuksia: tietojen palauttamisen vivahteet, palautuksen vaikutus kyselyn suoritusaikaan, tiedon tallennuksen ominaisuudet jne. Aion puhua näistä ja muista ominaisuuksista erikseen. redundanssikoodien käytöstä käytännössä, jos aihe kiinnostaa.
6. Linkit
- Sarja artikkeleita Reed-Solomon-koodeista ja Galois-kentistä:
He tarkastelevat matematiikkaa syvemmällä ymmärrettävällä kielellä. - Microsoftin artikkeli LRC:stä:
Luvussa 2 selostetaan lyhyesti teoria ja sitten keskustellaan kokemuksista LRC:n kanssa käytännössä. - Parillisen pariton kaava:
- STAR-järjestelmä:
- Pyramidikoodit:
- Redundanssikoodit MDS:ssä:
- Redundanssikoodit YT:ssä:
- YDB:n redundanssikoodit:
Lähde: will.com