Ganito ang hitsura ng redundancy
Ang mga redundancy code* ay malawakang ginagamit sa mga computer system upang mapataas ang pagiging maaasahan ng pag-iimbak ng data. Sa Yandex ginagamit ang mga ito sa maraming proyekto. Halimbawa, ang paggamit ng mga redundancy code sa halip na pagtitiklop sa aming panloob na imbakan ng bagay ay nakakatipid ng milyun-milyon nang hindi sinasakripisyo ang pagiging maaasahan. Ngunit sa kabila ng kanilang malawakang paggamit, napakabihirang mga malinaw na paglalarawan kung paano gumagana ang mga redundancy code. Ang mga gustong makaunawa ay nahaharap sa humigit-kumulang sa mga sumusunod (mula sa ):
Ang pangalan ko ay Vadim, sa Yandex ako ay bumubuo ng panloob na imbakan ng bagay na MDS. Sa artikulong ito, ilalarawan ko sa mga simpleng salita ang teoretikal na pundasyon ng mga redundancy code (Reed-Solomon at LRC codes). Sasabihin ko sa iyo kung paano ito gumagana, nang walang kumplikadong matematika at mga bihirang termino. Sa dulo ay magbibigay ako ng mga halimbawa ng paggamit ng mga redundancy code sa Yandex.
Hindi ko isasaalang-alang ang isang bilang ng mga detalye ng matematika nang detalyado, ngunit magbibigay ako ng mga link para sa mga gustong sumisid nang mas malalim. Mapapansin ko rin na ang ilang mga kahulugan sa matematika ay maaaring hindi mahigpit, dahil ang artikulo ay hindi inilaan para sa mga mathematician, ngunit para sa mga inhinyero na gustong maunawaan ang kakanyahan ng isyu.
* Sa panitikan sa wikang Ingles, ang mga redundancy code ay madalas na tinatawag na erasure code.
1. Ang kakanyahan ng mga redundancy code
Ang kakanyahan ng lahat ng mga redundancy code ay napakasimple: mag-imbak (o magpadala) ng data upang hindi ito mawala kapag may mga error (disk failures, data transfer error, atbp.).
Sa karamihan* ng redundancy code, nahahati ang data sa n data block, kung saan binibilang ang m block ng redundancy code, na nagreresulta sa kabuuang n + m block. Ang mga redundancy code ay binuo sa paraang ang n bloke ng data ay maaaring mabawi gamit lamang ang isang bahagi ng n + m na bloke. Susunod, isasaalang-alang lamang namin ang mga block redundancy code, iyon ay, ang mga kung saan ang data ay nahahati sa mga bloke.
Upang mabawi ang lahat ng n bloke ng data, kailangan mong magkaroon ng hindi bababa sa n ng n + m bloke, dahil hindi ka makakakuha ng n bloke sa pamamagitan ng pagkakaroon lamang ng n-1 bloke (sa kasong ito, kailangan mong kumuha ng 1 bloke "sa manipis hanginβ). Sapat ba ang n random na bloke ng n + m block para mabawi ang lahat ng data? Depende ito sa uri ng mga redundancy code, halimbawa, ang Reed-Solomon code ay nagbibigay-daan sa iyo na mabawi ang lahat ng data gamit ang arbitrary n blocks, ngunit ang LRC redundancy code ay hindi palaging.
Imbakan ng data
Sa mga sistema ng pag-iimbak ng data, bilang panuntunan, ang bawat isa sa mga bloke ng data at mga bloke ng redundancy code ay nakasulat sa isang hiwalay na disk. Pagkatapos, kung nabigo ang isang di-makatwirang disk, maaari pa ring maibalik at mabasa ang orihinal na data. Maaaring mabawi ang data kahit na maraming mga disk ang nabigo sa parehong oras.
Paglilipat ng data
Maaaring gamitin ang mga redundancy code upang mapagkakatiwalaang magpadala ng data sa isang hindi mapagkakatiwalaang network. Ang ipinadalang data ay nahahati sa mga bloke, at ang mga redundancy code ay kinakalkula para sa kanila. Ang parehong mga bloke ng data at mga bloke ng redundancy code ay ipinapadala sa network. Kung ang mga error ay nangyari sa mga arbitrary na bloke (hanggang sa isang tiyak na bilang ng mga bloke), ang data ay maaari pa ring ipadala sa network nang walang error. Ang mga Reed-Solomon code, halimbawa, ay ginagamit upang magpadala ng data sa mga optical na linya ng komunikasyon at sa mga komunikasyong satellite.
* Mayroon ding mga redundancy code kung saan ang data ay hindi nahahati sa mga bloke, gaya ng Hamming code at CRC code, na malawakang ginagamit para sa paghahatid ng data sa mga Ethernet network. Ito ay mga code para sa error-correcting coding, ang mga ito ay idinisenyo upang makita ang mga error, at hindi para itama ang mga ito (ang Hamming code ay nagpapahintulot din sa bahagyang pagwawasto ng mga error).
2. Reed-Solomon code
Ang mga code ng Reed-Solomon ay isa sa pinakamalawak na ginagamit na redundancy code, na naimbento noong 1960s at unang malawak na ginamit noong 1980s para sa mass production ng mga compact disc.
Mayroong dalawang pangunahing katanungan para sa pag-unawa sa Reed-Solomon code: 1) kung paano gumawa ng mga bloke ng redundancy code; 2) kung paano mabawi ang data gamit ang mga bloke ng redundancy code. Hanapin natin ang mga sagot sa kanila.
Para sa pagiging simple, ipagpapalagay pa natin na n=6 at m=4. Ang iba pang mga scheme ay isinasaalang-alang sa pamamagitan ng pagkakatulad.
Paano lumikha ng mga bloke ng redundancy code
Ang bawat bloke ng redundancy code ay binibilang nang hiwalay sa iba. Ang lahat ng n bloke ng data ay ginagamit upang mabilang ang bawat bloke. Sa diagram sa ibaba, ang X1-X6 ay mga bloke ng data, ang P1-P4 ay mga bloke ng redundancy code.
Ang lahat ng mga bloke ng data ay dapat na parehong laki, at ang mga zero bit ay maaaring gamitin para sa pagkakahanay. Magiging kapareho ng laki ng mga bloke ng data ang magreresultang redundancy code blocks. Ang lahat ng mga bloke ng data ay nahahati sa mga salita (halimbawa, 16 bits). Sabihin nating hinati namin ang mga bloke ng data sa k salita. Pagkatapos ang lahat ng mga bloke ng redundancy code ay hahatiin din sa k salita.
Upang mabilang ang i-th na salita ng bawat redundancy block, ang i-th na salita ng lahat ng data block ay gagamitin. Kakalkulahin ang mga ito ayon sa sumusunod na formula:
Narito ang mga halaga x ay ang mga salita ng mga bloke ng data, ang p ay ang mga salita ng mga bloke ng redundancy code, lahat ng alpha, beta, gamma at delta ay espesyal na piniling mga numero na pareho para sa lahat ng i. Dapat sabihin kaagad na ang lahat ng mga halagang ito ay hindi ordinaryong mga numero, ngunit mga elemento ng larangan ng Galois; ang mga operasyon +, -, *, / ay hindi mga operasyon na pamilyar sa ating lahat, ngunit ang mga espesyal na operasyon na ipinakilala sa mga elemento ng Galois patlang.
Bakit kailangan ang mga patlang ng Galois?
Tila ang lahat ay simple: hinahati namin ang data sa mga bloke, ang mga bloke sa mga salita, gamit ang mga salita ng mga bloke ng data binibilang namin ang mga salita ng mga bloke ng redundancy code - nakakakuha kami ng mga bloke ng redundancy code. Sa pangkalahatan ito ay kung paano ito gumagana, ngunit ang diyablo ay nasa mga detalye:
- Tulad ng nakasaad sa itaas, ang laki ng salita ay naayos, sa aming halimbawa ay 16 bits. Ang mga formula sa itaas para sa Reed-Solomon code ay tulad na kapag gumagamit ng mga ordinaryong integer, ang resulta ng pagkalkula ng p ay maaaring hindi kinakatawan gamit ang isang salita na may wastong laki.
- Kapag nagre-recover ng data, ang mga formula sa itaas ay ituturing bilang isang sistema ng mga equation na dapat lutasin upang mabawi ang data. Sa panahon ng proseso ng solusyon, maaaring kailanganin na hatiin ang mga integer sa isa't isa, na nagreresulta sa isang tunay na numero na hindi tumpak na kinakatawan sa memorya ng computer.
Pinipigilan ng mga problemang ito ang paggamit ng mga integer para sa Reed-Solomon code. Ang solusyon sa problema ay orihinal, maaari itong ilarawan bilang mga sumusunod: makabuo tayo ng mga espesyal na numero na maaaring katawanin gamit ang mga salita ng kinakailangang haba (halimbawa, 16 bits), at ang resulta ng pagsasagawa ng lahat ng mga operasyon kung saan (dagdag , pagbabawas, pagpaparami, paghahati) ay ipapakita din sa memorya ng computer gamit ang mga salita ng kinakailangang haba.
Ang ganitong mga "espesyal" na mga numero ay pinag-aralan ng matematika sa loob ng mahabang panahon; ang mga ito ay tinatawag na mga patlang. Ang field ay isang hanay ng mga elemento na may mga operasyon ng karagdagan, pagbabawas, pagpaparami at paghahati na tinukoy para sa kanila.
Ang mga patlang ng Galois* ay mga field kung saan mayroong natatanging resulta ng bawat operasyon (+, -, *, /) para sa alinmang dalawang elemento ng field. Ang mga patlang ng Galois ay maaaring itayo para sa mga numero na may kapangyarihan na 2: 2, 4, 8, 16, atbp. (sa totoo lang, mga kapangyarihan ng anumang prime number p, ngunit sa pagsasanay ay interesado lamang kami sa mga kapangyarihan ng 2). Halimbawa, para sa 16-bit na salita, ito ay isang field na naglalaman ng 65 na elemento, para sa bawat pares kung saan mahahanap mo ang resulta ng anumang operasyon (+, -, *, /). Ang mga halaga ng x, p, alpha, beta, gamma, delta mula sa mga equation sa itaas ay ituturing na mga elemento ng Galois field para sa mga kalkulasyon.
Kaya, mayroon tayong sistema ng mga equation kung saan maaari tayong bumuo ng mga bloke ng redundancy code sa pamamagitan ng pagsulat ng naaangkop na computer program. Gamit ang parehong sistema ng mga equation, maaari kang magsagawa ng pagbawi ng data.
* Ito ay hindi isang mahigpit na kahulugan, ngunit isang paglalarawan.
Paano mabawi ang data
Kailangan ang pagpapanumbalik kapag nawawala ang ilan sa mga n + m block. Ang mga ito ay maaaring parehong mga bloke ng data at mga bloke ng redundancy code. Ang kawalan ng mga bloke ng data at/o mga bloke ng redundancy code ay nangangahulugan na ang mga katumbas na x at/o p variable ay hindi alam sa mga equation sa itaas.
Ang mga equation para sa Reed-Solomon code ay maaaring tingnan bilang isang sistema ng mga equation kung saan ang lahat ng alpha, beta, gamma, delta values ββay mga constant, lahat ng x at p na naaayon sa magagamit na mga bloke ay kilala na mga variable, at ang natitirang x at p ay hindi kilala.
Halimbawa, hayaan ang data block 1, 2, 3 at redundancy code block 2 na hindi available, pagkatapos ay para sa i-th na pangkat ng mga salita magkakaroon ng sumusunod na sistema ng mga equation (ang hindi alam ay minarkahan ng pula):
Mayroon kaming isang sistema ng 4 na equation na may 4 na hindi alam, na nangangahulugang maaari naming lutasin ito at ibalik ang data!
Mula sa sistemang ito ng mga equation ay sumusunod ang ilang konklusyon tungkol sa pagbawi ng data para sa Reed-Solomon code (n data block, m redundancy code blocks):
- Maaaring mabawi ang data kung mawawala ang anumang m bloke o mas kaunti. Kung ang m+1 o higit pang mga bloke ay nawala, ang data ay hindi maibabalik: imposibleng malutas ang isang sistema ng m equation na may m + 1 na hindi alam.
- Upang mabawi ang kahit isang bloke ng data, kailangan mong gumamit ng alinman sa mga natitirang bloke, at maaari mong gamitin ang alinman sa mga redundancy code.
Ano pa ang kailangan mong malaman
Sa paglalarawan sa itaas, iniiwasan ko ang ilang mahahalagang isyu na nangangailangan ng mas malalim na pagsisid sa matematika upang isaalang-alang. Sa partikular, wala akong sinasabi tungkol sa mga sumusunod:
- Ang sistema ng mga equation para sa Reed-Solomon code ay dapat may (natatanging) solusyon para sa anumang kumbinasyon ng mga hindi alam (hindi hihigit sa m hindi alam). Batay sa kinakailangang ito, ang mga halaga ng alpha, beta, gamma at delta ay pinili.
- Ang isang sistema ng mga equation ay dapat na awtomatikong mabuo (depende sa kung aling mga bloke ang hindi magagamit) at malutas.
- Kailangan nating bumuo ng Galois field: para sa isang ibinigay na laki ng salita, mahanap ang resulta ng anumang operasyon (+, -, *, /) para sa alinmang dalawang elemento.
Sa dulo ng artikulo ay may mga sanggunian sa panitikan sa mga mahahalagang isyung ito.
Pagpili ng n at m
Paano pumili ng n at m sa pagsasanay? Sa pagsasagawa, sa mga sistema ng pag-iimbak ng data, ang mga redundancy code ay ginagamit upang makatipid ng espasyo, kaya ang m ay palaging pinipiling mas mababa sa n. Ang kanilang mga tiyak na halaga ay nakasalalay sa isang bilang ng mga kadahilanan, kabilang ang:
- Ang pagiging maaasahan ng imbakan ng data. Ang mas malaking m, mas malaki ang bilang ng mga pagkabigo sa disk na maaaring maligtas, iyon ay, mas mataas ang pagiging maaasahan.
- Labis na imbakan. Kung mas mataas ang m/n ratio, mas mataas ang storage redundancy, at mas magiging mahal ang system.
- Humiling ng oras ng pagproseso. Kung mas malaki ang kabuuan n + m, mas mahaba ang oras ng pagtugon sa mga kahilingan. Dahil ang pagbabasa ng data (sa panahon ng pagbawi) ay nangangailangan ng pagbabasa ng n mga bloke na nakaimbak sa n magkakaibang mga disk, ang oras ng pagbasa ay matutukoy ng pinakamabagal na disk.
Bilang karagdagan, ang pag-iimbak ng data sa ilang mga DC ay nagpapataw ng mga karagdagang paghihigpit sa pagpili ng n at m: kung ang 1 DC ay naka-off, ang data ay dapat na magagamit pa rin para sa pagbabasa. Halimbawa, kapag nag-iimbak ng data sa 3 DC, dapat matugunan ang sumusunod na kundisyon: m >= n/2, kung hindi, maaaring mayroong sitwasyon kung saan hindi available ang data para sa pagbabasa kapag naka-off ang 1 DC.
3. LRC - Local Reconstruction Codes
Upang mabawi ang data gamit ang Reed-Solomon code, kailangan mong gumamit ng n arbitrary na data block. Ito ay isang napakalaking kawalan para sa mga ibinahagi na sistema ng pag-iimbak ng data, dahil upang maibalik ang data sa isang sirang disk, kakailanganin mong basahin ang data mula sa karamihan ng iba pa, na lumilikha ng isang malaking karagdagang pagkarga sa mga disk at sa network.
Ang pinakakaraniwang mga error ay ang hindi naa-access ng isang bloke ng data dahil sa pagkabigo o labis na karga ng isang disk. Posible bang bawasan ang labis na pagkarga para sa pagbawi ng data sa (pinakakaraniwang) kaso na ito? Lumalabas na kaya mo: may mga LRC redundancy code na partikular para sa layuning ito.
Ang LRC (Local Reconstruction Codes) ay mga redundancy code na inimbento ng Microsoft para gamitin sa Windows Azure Storage. Ang ideya ng LRC ay kasing simple hangga't maaari: hatiin ang lahat ng mga bloke ng data sa dalawa (o higit pa) na mga grupo at basahin ang bahagi ng mga bloke ng redundancy code para sa bawat pangkat nang hiwalay. Pagkatapos ay bibilangin ang ilang block ng redundancy code gamit ang lahat ng data blocks (sa LRC tinatawag silang mga global redundancy code), at ang ilan - gamit ang isa sa dalawang grupo ng data blocks (tinatawag silang mga local redundancy code).
Ang LRC ay tinutukoy ng tatlong numero: nrl, kung saan ang n ay ang bilang ng mga bloke ng data, ang r ay ang bilang ng mga bloke ng global na redundancy code, l ang bilang ng mga lokal na bloke ng redundancy code. Upang basahin ang data kapag ang isang bloke ng data ay hindi magagamit, kailangan mong basahin lamang ang mga n/l na bloke - ito ay l beses na mas mababa kaysa sa mga code ng Reed-Solomon.
Halimbawa, isaalang-alang ang LRC 6-2-2 scheme. X1βX6 β 6 na data block, P1, P2 β 2 global redundancy block, P3, P4 β 2 lokal na redundancy block.
Ang mga bloke ng redundancy code na P1, P2 ay binibilang gamit ang lahat ng mga bloke ng data. Redundancy code block P3 - gamit ang data blocks X1-X3, redundancy code block P4 - gamit ang data blocks X4-X6.
Ang natitira ay ginagawa sa LRC sa pamamagitan ng pagkakatulad sa Reed-Solomon code. Ang mga equation para sa pagbibilang ng mga salita ng redundancy code blocks ay:
Upang piliin ang mga numerong alpha, beta, gamma, delta, isang bilang ng mga kundisyon ang dapat matugunan upang matiyak ang posibilidad ng pagbawi ng data (iyon ay, paglutas ng sistema ng equation). Maaari mong basahin ang higit pa tungkol sa kanila sa .
Gayundin sa pagsasanay, ang operasyon ng XOR ay ginagamit upang kalkulahin ang mga lokal na redundancy code na P3, P4.
Ang ilang mga konklusyon ay sumusunod mula sa sistema ng mga equation para sa LRC:
- Upang mabawi ang anumang 1 bloke ng data, sapat na basahin ang mga n/l na bloke (n/2 sa aming halimbawa).
- Kung hindi available ang mga bloke ng r + l, at ang lahat ng mga bloke ay kasama sa isang pangkat, hindi na maibabalik ang data. Ito ay madaling ipaliwanag gamit ang isang halimbawa. Hayaang hindi available ang mga bloke X1βX3 at P3: ito ay mga bloke ng r + l mula sa parehong pangkat, 4 sa aming kaso. Pagkatapos ay mayroon kaming isang sistema ng 3 equation na may 4 na hindi alam na hindi malulutas.
- Sa lahat ng iba pang kaso ng hindi available na r + l blocks (kapag kahit isang block ay available mula sa bawat grupo), ang data sa LRC ay maaaring maibalik.
Kaya naman, nahihigitan ng LRC ang mga Reed-Solomon code sa pagbawi ng data pagkatapos ng mga solong error. Sa Reed-Solomon code, upang mabawi ang kahit isang bloke ng data, kailangan mong gumamit ng mga n bloke, at sa LRC, upang mabawi ang isang bloke ng data, sapat na gumamit ng mga n/l na bloke (n/2 sa aming halimbawa). Sa kabilang banda, ang LRC ay mas mababa sa Reed-Solomon code sa mga tuntunin ng maximum na bilang ng mga pinahihintulutang error. Sa mga halimbawa sa itaas, maaaring mabawi ng mga Reed-Solomon code ang data para sa anumang 4 na error, at para sa LRC mayroong 2 kumbinasyon ng 4 na error kapag hindi na mababawi ang data.
Ang mas mahalaga ay depende sa partikular na sitwasyon, ngunit kadalasan ang pagtitipid sa labis na load na ibinibigay ng LRC ay mas malaki kaysa sa bahagyang hindi gaanong maaasahang imbakan.
4. Iba pang mga redundancy code
Bukod sa Reed-Solomon at LRC code, marami pang ibang redundancy code. Ang iba't ibang redundancy code ay gumagamit ng iba't ibang matematika. Narito ang ilang iba pang redundancy code:
- Redundancy code gamit ang XOR operator. Isinasagawa ang operasyon ng XOR sa n mga bloke ng data, at nakuha ang 1 bloke ng mga redundancy code, iyon ay, isang scheme ng n+1 (n mga bloke ng data, 1 redundancy code). Ginamit sa , kung saan ang mga bloke ng data at redundancy code ay paikot na isinusulat sa lahat ng disk ng array.
- Kahit na kakaibang algorithm batay sa operasyon ng XOR. Binibigyang-daan kang bumuo ng 2 bloke ng redundancy code, iyon ay, ang n+2 scheme.
- STAR algorithm batay sa operasyon ng XOR. Binibigyang-daan kang bumuo ng 3 bloke ng redundancy code, iyon ay, ang n+3 scheme.
- Ang mga pyramide code ay isa pang redundancy code mula sa Microsoft.
5. Gamitin sa Yandex
Ang ilang mga proyekto sa imprastraktura ng Yandex ay gumagamit ng mga redundancy code para sa maaasahang pag-iimbak ng data. Narito ang ilang halimbawa:
- MDS internal object storage, na isinulat ko tungkol sa simula ng artikulo.
- β MapReduce system ng Yandex.
- (Yandex DataBase) - database na ipinamamahagi ng newSQL.
Gumagamit ang MDS ng mga redundancy code ng LRC, 8-2-2 scheme. Ang data na may mga redundancy code ay isinusulat sa 12 iba't ibang disk sa iba't ibang server sa 3 magkakaibang DC: 4 na server sa bawat DC. Magbasa pa tungkol dito sa .
Gumagamit ang YT ng parehong Reed-Solomon code (Scheme 6-3), na unang ipinatupad, at LRC redundancy code (Scheme 12-2-2), kung saan ang LRC ang gustong paraan ng storage.
Gumagamit ang YDB ng even-odd based redundancy code (Figure 4-2). Tungkol sa mga redundancy code sa YDB na .
Ang paggamit ng iba't ibang redundancy code scheme ay dahil sa iba't ibang mga kinakailangan para sa mga system. Halimbawa, sa MDS, ang data na nakaimbak gamit ang LRC ay inilalagay sa 3 DC nang sabay-sabay. Mahalaga para sa amin na ang data ay mananatiling magagamit para sa pagbabasa kung 1 sa anumang DC ay nabigo, samakatuwid ang mga bloke ay dapat na ipamahagi sa mga DC upang kung ang anumang DC ay hindi magagamit, ang bilang ng mga hindi naa-access na mga bloke ay hindi hihigit sa pinapayagan. Sa 8-2-2 scheme, maaari kang maglagay ng 4 na bloke sa bawat DC, at kapag naka-off ang anumang DC, 4 na bloke ang hindi magagamit, at mababasa ang data. Anuman ang scheme na pipiliin namin kapag inilalagay ito sa 3 DC, sa anumang kaso dapat mayroong (r + l) / n >= 0,5, iyon ay, ang kalabisan ng imbakan ay hindi bababa sa 50%.
Sa YT ang sitwasyon ay iba: ang bawat YT cluster ay ganap na matatagpuan sa 1 DC (iba't ibang mga cluster sa iba't ibang DC), kaya walang ganoong paghihigpit. Ang 12-2-2 scheme ay nagbibigay ng 33% redundancy, ibig sabihin, ang pag-iimbak ng data ay mas mura, at maaari din itong makaligtas ng hanggang 4 na sabay-sabay na pagkawala ng disk, tulad ng MDS scheme.
Marami pang feature ng paggamit ng redundancy code sa data storage at processing system: mga nuances ng data recovery, ang epekto ng recovery sa query execution time, features ng data recording, atbp. Hiwalay akong magsasalita tungkol sa mga ito at sa iba pang feature. ng paggamit ng redundancy code sa pagsasanay, kung magiging interesante ang paksa.
6. Mga link
- Isang serye ng mga artikulo tungkol sa Reed-Solomon code at Galois field:
Mas malalim nilang tinitingnan ang matematika sa naa-access na wika. - Artikulo mula sa Microsoft tungkol sa LRC:
Maikling ipinapaliwanag ng Seksyon 2 ang teorya at pagkatapos ay tinatalakay ang mga karanasan sa LRC sa pagsasanay. - Even-odd na scheme:
- STAR scheme:
- Pyramid code:
- Mga redundancy code sa MDS:
- Mga redundancy code sa YT:
- Mga redundancy code sa YDB:
Pinagmulan: www.habr.com