{"id":87758,"date":"2020-07-10T01:41:58","date_gmt":"2020-07-09T23:41:58","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye"},"modified":"2020-07-10T01:41:58","modified_gmt":"2020-07-09T23:41:58","slug":"kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","status":"publish","type":"post","link":"https:\/\/prohoster.info\/hu\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Redundancia k\u00f3dok: egyszer\u0171 szavakkal arr\u00f3l, hogyan t\u00e1rolhatunk adatokat megb\u00edzhat\u00f3an \u00e9s olcs\u00f3n","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Redundancia<\/p>\n

<\/p>\n

Ez a redundancia<\/em><\/p>\n

<\/p>\n

A redundancia k\u00f3dokat* sz\u00e9les k\u00f6rben alkalmazz\u00e1k a sz\u00e1m\u00edt\u00f3g\u00e9pes rendszerekben az adatok t\u00e1rol\u00e1s\u00e1nak megb\u00edzhat\u00f3s\u00e1g\u00e1nak n\u00f6vel\u00e9s\u00e9re. A Yandexn\u00e9l sz\u00e1mos projektben haszn\u00e1lj\u00e1k \u0151ket. P\u00e9ld\u00e1ul a redundancia k\u00f3dok alkalmaz\u00e1sa a replik\u00e1ci\u00f3 helyett a bels\u0151 objektum t\u00e1rol\u00f3nkban milli\u00f3kat takar\u00edt meg an\u00e9lk\u00fcl, hogy cs\u00f6kkenten\u00e9 a megb\u00edzhat\u00f3s\u00e1got. De a sz\u00e9lesk\u00f6r\u0171 elterjed\u00e9s ellen\u00e9re ritk\u00e1n tal\u00e1lhat\u00f3 \u00e9rthet\u0151 le\u00edr\u00e1s arr\u00f3l, hogyan m\u0171k\u00f6dnek a redundancia k\u00f3dok. Azok, akik szeretn\u00e9k meg\u00e9rteni, k\u00f6r\u00fclbel\u00fcl a k\u00f6vetkez\u0151vel tal\u00e1lkoznak (a Wikip\u00e9di\u00e1n<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Redundancia<\/p>\n

<\/p>\n

A nevem Vadim, a Yandexn\u00e9l az MDS bels\u0151 objektum t\u00e1rol\u00f3 fejleszt\u00e9s\u00e9vel foglalkozom. Ebben a cikkben egyszer\u0171 szavakkal fogom le\u00edrni a redundancia k\u00f3dok (Reed-Solomon k\u00f3dok \u00e9s LRC) elm\u00e9leti alapjait. Elmondom, hogyan m\u0171k\u00f6dik ez, bonyolult matematika \u00e9s ritka kifejez\u00e9sek n\u00e9lk\u00fcl. A v\u00e9g\u00e9n p\u00e9ld\u00e1kat hozok a redundancia k\u00f3dok Yandexbeli haszn\u00e1lat\u00e1ra.<\/p>\n

<\/p>\n

N\u00e9h\u00e1ny matematikai r\u00e9szletet nem fogok r\u00e9szletesen t\u00e1rgyalni, de linkeket fogok adni azok sz\u00e1m\u00e1ra, akik szeretn\u00e9nek m\u00e9lyebben elmer\u00fclni a t\u00e9m\u00e1ban. Megjegyzem tov\u00e1bb\u00e1, hogy egyes matematikai meghat\u00e1roz\u00e1sok nem lehetnek szigor\u00faak, mivel a cikk nem matematikusoknak k\u00e9sz\u00fclt, hanem m\u00e9rn\u00f6k\u00f6knek, akik szeretn\u00e9k meg\u00e9rteni a k\u00e9rd\u00e9s l\u00e9nyeg\u00e9t.<\/p>\n

<\/p>\n

* Az angol nyelv\u0171 szakirodalomban a redundancia k\u00f3dokat gyakran erasure code-nak nevezik.<\/p>\n

<\/a><\/noindex><\/p>\n

1. A redundancia k\u00f3dok l\u00e9nyege<\/h1>\n

<\/p>\n

A redundancia k\u00f3dok l\u00e9nyege rendk\u00edv\u00fcl egyszer\u0171: az adatok t\u00e1rol\u00e1sa (vagy tov\u00e1bb\u00edt\u00e1sa) \u00fagy, hogy azok ne vesszenek el hib\u00e1k (p\u00e9ld\u00e1ul lemezhib\u00e1k, adat\u00e1tviteli hib\u00e1k stb.) eset\u00e9n. <\/p>\n

<\/p>\n

A legt\u00f6bb* redundancia k\u00f3dban az adatokat n blokkra osztj\u00e1k, \u00e9s m redundancia blokkot sz\u00e1m\u00edtanak hozz\u00e1juk, \u00edgy \u00f6sszesen n + m blokkb\u00f3l \u00e1ll. A redundancia k\u00f3dokat \u00fagy \u00e9p\u00edtik fel, hogy n adatblokk helyre\u00e1ll\u00edthat\u00f3 legyen csak n + m blokk egy r\u00e9sz\u00e9nek felhaszn\u00e1l\u00e1s\u00e1val. Ezut\u00e1n csak a blokk k\u00f3dokkal foglalkozunk, vagyis azokkal, amelyekben az adatokat blokkokra osztj\u00e1k.<\/p>\n

<\/p>\n

\"Redundancia<\/p>\n

<\/p>\n

Ahhoz, hogy helyre\u00e1ll\u00edtsuk az \u00f6sszes n adatblokkot, minimum n az n + m blokkb\u00f3l sz\u00fcks\u00e9ges, mivel nem lehet n blokkot el\u0151\u00e1ll\u00edtani, ha csak n-1 blokkunk van (ebben az esetben 1 blokkot a \u201eleveg\u0151b\u0151l\u201d kellene szerezni). El\u00e9gs\u00e9gesek-e n tetsz\u0151leges blokk az n + m blokk k\u00f6z\u00fcl az \u00f6sszes adat helyre\u00e1ll\u00edt\u00e1s\u00e1hoz? Ez a redundancia k\u00f3djainak t\u00edpus\u00e1t\u00f3l f\u00fcgg, p\u00e9ld\u00e1ul a Reed-Solomon k\u00f3dok lehet\u0151v\u00e9 teszik, hogy tetsz\u0151leges n blokk seg\u00edts\u00e9g\u00e9vel helyre\u00e1ll\u00edtsuk az \u00f6sszes adatot, m\u00edg az LRC redundancia k\u00f3dok ezt nem mindig teszik lehet\u0151v\u00e9.<\/p>\n

<\/p>\n

Adatt\u00e1rol\u00e1s<\/h3>\n

<\/p>\n

Az adatt\u00e1rol\u00f3 rendszerekben \u00e1ltal\u00e1ban minden adatblokk \u00e9s redundancia k\u00f3d blokk k\u00fcl\u00f6n lemezen t\u00e1rol\u00f3dik. \u00cdgy, ha egy tetsz\u0151leges lemez meghib\u00e1sodik, az eredeti adatok m\u00e9g mindig helyre\u00e1ll\u00edthat\u00f3k \u00e9s olvashat\u00f3k. Az adatok ak\u00e1r t\u00f6bb lemez egyidej\u0171 meghib\u00e1sod\u00e1sa eset\u00e9n is helyre\u00e1ll\u00edthat\u00f3k.<\/p>\n

<\/p>\n

Adat\u00e1tvitel<\/h3>\n

<\/p>\n

A redundancia k\u00f3dok megb\u00edzhat\u00f3 adat\u00e1tvitelre haszn\u00e1lhat\u00f3k megb\u00edzhatatlan h\u00e1l\u00f3zatokon. Az \u00e1tvitt adatokat blokkokra bontj\u00e1k, \u00e9s ehhez k\u00f3dokat sz\u00e1m\u00edtanak. Az adatblokkok mellett a redundancia k\u00f3d blokkjait is \u00e1tviszik a h\u00e1l\u00f3zaton. Ha hib\u00e1k l\u00e9pnek fel tetsz\u0151leges blokkokban (ak\u00e1r bizonyos sz\u00e1m\u00fa blokkig), az adatokat akkor is hibamentesen \u00e1t lehet vinni a h\u00e1l\u00f3zaton. A Reed-Solomon k\u00f3dokat p\u00e9ld\u00e1ul optikai kommunik\u00e1ci\u00f3s vonalakon \u00e9s m\u0171holdas kommunik\u00e1ci\u00f3ban haszn\u00e1lj\u00e1k az adatok \u00e1tvitel\u00e9re.<\/p>\n

<\/p>\n

* Vannak olyan redundancia k\u00f3dok is, amelyek nem bontj\u00e1k blokkokra az adatokat, p\u00e9ld\u00e1ul a Hamming-k\u00f3dok \u00e9s a CRC k\u00f3dok, amelyeket sz\u00e9les k\u00f6rben haszn\u00e1lnak az Ethereum h\u00e1l\u00f3zatokban t\u00f6rt\u00e9n\u0151 adat\u00e1tvitelhez. Ezek a zajt\u0171r\u0151 k\u00f3dok hib\u00e1k \u00e9szlel\u00e9s\u00e9re szolg\u00e1lnak, nem azok jav\u00edt\u00e1s\u00e1ra (a Hamming-k\u00f3d r\u00e9szben hib\u00e1k jav\u00edt\u00e1s\u00e1ra is alkalmas).<\/p>\n

<\/p>\n

2. Reed-Solomon k\u00f3dok<\/h1>\n

<\/p>\n

A Reed-Solomon k\u00f3dok a legsz\u00e9lesebb k\u00f6rben elterjedt redundancia k\u00f3dok k\u00f6z\u00e9 tartoznak, amelyeket m\u00e9g az 1960-as \u00e9vekben tal\u00e1ltak ki, \u00e9s el\u0151sz\u00f6r az 1980-as \u00e9vekben alkalmaztak sz\u00e9les k\u00f6rben a CD-k sorozatgy\u00e1rt\u00e1s\u00e1ban.<\/p>\n

<\/p>\n

A Reed-Solomon k\u00f3dok meg\u00e9rt\u00e9s\u00e9hez k\u00e9t kulcsk\u00e9rd\u00e9s tartozik: 1) hogyan \u00e1ll\u00edtsunk el\u0151 redundancia k\u00f3d blokkokat; 2) hogyan \u00e1ll\u00edtsuk helyre az adatokat redundancia k\u00f3d blokkok seg\u00edts\u00e9g\u00e9vel. Keress\u00fck meg a v\u00e1laszokat ezekre.
\nA tov\u00e1bbi egyszer\u0171s\u00edt\u00e9s \u00e9rdek\u00e9ben tegy\u00fck fel, hogy n=6 \u00e9s m=4. M\u00e1s s\u00e9m\u00e1k hasonl\u00f3an kezelhet\u0151k.<\/p>\n

<\/p>\n

Hogyan \u00e1ll\u00edtsunk el\u0151 redundancia k\u00f3d blokkokat<\/h3>\n

<\/p>\n

Minden parit\u00e1sblokkot f\u00fcggetlen\u00fcl kell kezelni. Minden parit\u00e1sblokk kisz\u00e1m\u00edt\u00e1s\u00e1hoz az \u00f6sszes n adatblokkot haszn\u00e1ljuk. Az al\u00e1bbi \u00e1br\u00e1n az X1-X6 az adatblokkok, a P1\u2013P4 pedig a parit\u00e1sblokkok.<\/p>\n

<\/p>\n

\"Redundancia<\/p>\n

<\/p>\n

Minden adatblokk azonos m\u00e9ret\u0171 kell legyen, a kiegyenl\u00edt\u00e9st z\u00e9r\u00f3 bitek haszn\u00e1lat\u00e1val lehet el\u00e9rni. A l\u00e9trej\u00f6v\u0151 parit\u00e1sblokkok ugyanolyan m\u00e9ret\u0171ek lesznek, mint az adatblokkok. Minden adatblokkot szavakra bontunk (p\u00e9ld\u00e1ul 16 bitre). Tegy\u00fck fel, hogy az adatblokkokat k sz\u00f3val osztottuk fel. Ekkor az \u00f6sszes parit\u00e1sblokkot szint\u00e9n k sz\u00f3ra bontj\u00e1k.<\/p>\n

<\/p>\n

\"Redundancia<\/p>\n

<\/p>\n

Az i-edik parit\u00e1sblokk szav\u00e1nak kisz\u00e1m\u00edt\u00e1s\u00e1hoz az \u00f6sszes adatblokk i-edik szav\u00e1t haszn\u00e1lj\u00e1k. Ezen a k\u00e9pleten kereszt\u00fcl sz\u00e1m\u00edtj\u00e1k ki:<\/p>\n

<\/p>\n

\"Redundancia<\/p>\n

<\/p>\n

Itt az x \u00e9rt\u00e9kek az adatblokkok szavai, a p \u00e9rt\u00e9kek a parit\u00e1sblokkok szavai, minden alfa, b\u00e9ta, gamma \u00e9s delta - k\u00fcl\u00f6nlegesen megv\u00e1lasztott sz\u00e1mok, amelyek az \u00f6sszes i-ra \u00e9rv\u00e9nyesek. Azonnal meg kell eml\u00edteni, hogy ezek az \u00e9rt\u00e9kek nem szokv\u00e1nyos sz\u00e1mok, hanem Galois-mez\u0151k elemei. A +, -, *, \/ m\u0171veletek nem a megszokott m\u0171veletek, hanem a Galois-mez\u0151k elemein v\u00e9gzett speci\u00e1lis m\u0171veletek.<\/p>\n

<\/p>\n

Mi\u00e9rt sz\u00fcks\u00e9gesek a Galois-mez\u0151k<\/h3>\n

<\/p>\n

\"Redundancia<\/p>\n

<\/p>\n

Els\u0151 pillant\u00e1sra \u00fagy t\u0171nik, hogy ez egyszer\u0171: az adatokat blokkokra bontjuk, a blokkokat szavakra, majd az adatblokkok szavaival sz\u00e1m\u00edtjuk ki a parit\u00e1sblokkok szavait - \u00edgy kapjuk meg a parit\u00e1sblokkokat. \u00c1ltal\u00e1ban ez \u00edgy m\u0171k\u00f6dik, de a r\u00e9szletekben rejlik a buktat\u00f3:<\/p>\n

<\/p>\n

    \n
  1. Amint azt eml\u00edtettem, a sz\u00f3 m\u00e9rete fix, a mi p\u00e9ld\u00e1nkban 16 bit. A Reed-Solomon k\u00f3dokhoz tartoz\u00f3 k\u00e9pletek olyanok, hogy a szok\u00e1sos eg\u00e9sz sz\u00e1mok haszn\u00e1lata eset\u00e9n a p sz\u00e1m\u00edt\u00e1s\u00e1nak eredm\u00e9nye nem \u00e1br\u00e1zolhat\u00f3 a megengedett m\u00e9ret\u0171 sz\u00f3val.<\/li>\n
  2. Az adatok vissza\u00e1ll\u00edt\u00e1sakor a fenti k\u00e9pleteket egy egyenletrendszerk\u00e9nt kezelik, amelyet meg kell oldani az adatok helyre\u00e1ll\u00edt\u00e1s\u00e1hoz. A megold\u00e1si folyamat sor\u00e1n el\u0151fordulhat, hogy eg\u00e9szeket kell osztani egym\u00e1ssal, aminek eredm\u00e9nye egy val\u00f3s sz\u00e1m, amit nem lehet pontosan \u00e1br\u00e1zolni a sz\u00e1m\u00edt\u00f3g\u00e9p mem\u00f3ri\u00e1j\u00e1ban.<\/li>\n<\/ol>\n

    <\/p>\n

    Ezek a probl\u00e9m\u00e1k megakad\u00e1lyozz\u00e1k, hogy a Reed-Solomon k\u00f3dok eg\u00e9sz sz\u00e1mokat haszn\u00e1ljanak. A probl\u00e9ma megold\u00e1sa egyedi, a k\u00f6vetkez\u0151k\u00e9ppen lehet le\u00edrni: tal\u00e1ljuk ki azokat a speci\u00e1lis sz\u00e1mokat, amelyeket a megfelel\u0151 hossz\u00fas\u00e1g\u00fa szavakkal (p\u00e9ld\u00e1ul 16 bit) lehet \u00e1br\u00e1zolni, \u00e9s amelyekkel v\u00e9gzett \u00f6sszes m\u0171velet (\u00f6sszead\u00e1s, kivon\u00e1s, szorz\u00e1s, oszt\u00e1s) szint\u00e9n a sz\u00e1m\u00edt\u00f3g\u00e9p mem\u00f3ri\u00e1j\u00e1ban a megfelel\u0151 hossz\u00fas\u00e1g\u00fa szavakkal lesz \u00e1br\u00e1zolva.<\/p>\n

    <\/p>\n

    Az ilyen \u00bbspeci\u00e1lis\u00ab sz\u00e1mokat a matematika r\u00e9g\u00f3ta tanulm\u00e1nyozza, mez\u0151knek h\u00edvj\u00e1k \u0151ket. A mez\u0151 olyan elemek halmaza, amelyekre meghat\u00e1rozott \u00f6sszead\u00e1si, kivon\u00e1si, szorz\u00e1si \u00e9s oszt\u00e1si m\u0171veletek vonatkoznak.<\/p>\n

    <\/p>\n

    A Galois-mez\u0151k* olyan mez\u0151k, amelyek eset\u00e9ben minden m\u0171veletnek (+, -, *, \/) egy\u00e9rtelm\u0171 \u00e9s egyedi eredm\u00e9nye van b\u00e1rmely k\u00e9t mez\u0151elem sz\u00e1m\u00e1ra. A Galois-mez\u0151ket a 2 hatv\u00e1nyainak sz\u00e1m\u00e1hoz lehet fel\u00e9p\u00edteni: 2, 4, 8, 16 stb. (val\u00f3j\u00e1ban b\u00e1rmely pr\u00edmsz\u00e1m p hatv\u00e1nyai, de a gyakorlatban csak a 2 hatv\u00e1nyai \u00e9rdekelnek minket). P\u00e9ld\u00e1ul, 16 bit m\u00e9ret\u0171 szavak eset\u00e9n ez a mez\u0151 65 536 elemet tartalmaz, b\u00e1rmely p\u00e1r eset\u00e9ben megtal\u00e1lhat\u00f3 az \u00f6sszes m\u0171velet (+, -, *, \/) eredm\u00e9nye. Az x, p, alfa, b\u00e9ta, gamma, delta \u00e9rt\u00e9kek a fenti egyenletekben a sz\u00e1m\u00edt\u00e1sok sz\u00e1m\u00e1ra Galois-mez\u0151elemeknek tekinthet\u0151k.<\/p>\n

    <\/p>\n

    Teh\u00e1t rendelkez\u00e9s\u00fcnkre \u00e1ll egy egyenletrendszer, amely seg\u00edts\u00e9g\u00e9vel redundancia k\u00f3dblokkokat tudunk l\u00e9trehozni egy megfelel\u0151 sz\u00e1m\u00edt\u00f3g\u00e9pes program \u00edr\u00e1s\u00e1val. Ezen egyenletek seg\u00edts\u00e9g\u00e9vel az adatok helyre\u00e1ll\u00edt\u00e1s\u00e1t is v\u00e9gre lehet hajtani.<\/p>\n

    <\/p>\n

    * Ez nem szigor\u00fa defin\u00edci\u00f3, ink\u00e1bb egy le\u00edr\u00e1s.<\/p>\n

    <\/p>\n

    Hogyan lehet vissza\u00e1ll\u00edtani az adatokat<\/h3>\n

    <\/p>\n

    A helyre\u00e1ll\u00edt\u00e1sra akkor van sz\u00fcks\u00e9g, ha az n + m blokkb\u00f3l n\u00e9h\u00e1ny blokknak hi\u00e1nyzik. Ez lehet adatblokk vagy redundancia k\u00f3dblokk is. Az adatblokk \u00e9s\/vagy a redundancia k\u00f3dblokkok hi\u00e1nya azt jelenti, hogy a fenti egyenletekben az adott x \u00e9s\/vagy p v\u00e1ltoz\u00f3k ismeretlenek.<\/p>\n

    <\/p>\n

    A Reed-Solomon k\u00f3dok egyenletei egy egyenletrendszerk\u00e9nt tekinthet\u0151k, ahol minden alfa, b\u00e9ta, gamma, delta \u2014 konstans \u00e9rt\u00e9kek, minden x \u00e9s p, a rendelkez\u00e9sre \u00e1ll\u00f3 blokkoknak megfelel\u0151en \u2014 ismert v\u00e1ltoz\u00f3k, m\u00edg a t\u00f6bbi x \u00e9s p \u2014 ismeretlen.<\/p>\n

    <\/p>\n

    P\u00e9ld\u00e1ul, tegy\u00fck fel, hogy az 1., 2., 3. adatblokkok \u00e9s a 2. redundancia k\u00f3dblokk nem el\u00e9rhet\u0151, akkor az i. szavak csoportj\u00e1ra a k\u00f6vetkez\u0151 egyenletrendszer vonatkozik (az ismeretlenek pirossal megjel\u00f6lve):<\/p>\n

    <\/p>\n

    \"Redundancia<\/p>\n

    <\/p>\n

    Rendelkez\u00fcnk n\u00e9gy ismeretlent tartalmaz\u00f3, n\u00e9gy egyenletb\u0151l \u00e1ll\u00f3 rendszerrel, teh\u00e1t meg tudjuk oldani, \u00e9s vissza tudjuk \u00e1ll\u00edtani az adatokat!<\/p>\n

    <\/p>\n

    Ez a rendszer sz\u00e1mos k\u00f6vetkeztet\u00e9st von le az adatok helyre\u00e1ll\u00edt\u00e1s\u00e1r\u00f3l a Reed-Solomon k\u00f3dok eset\u00e9ben (n adatblokk, m redund\u00e1ns k\u00f3dbloock):<\/p>\n

    <\/p>\n