Yile nto ikhangeleka ngathi i-redundancy
Iikhowudi zokuRendundancy* zisetyenziswa kakhulu kwiinkqubo zekhompyutha ukwandisa ukuthembeka kokugcinwa kwedatha. KwiYandex zisetyenziswa kwiiprojekthi ezininzi. Ngokomzekelo, ukusebenzisa iikhowudi zokuphindaphinda endaweni yokuphindaphinda kwindawo yokugcina into yangaphakathi kusindisa izigidi ngaphandle kokuncama ukuthembeka. Kodwa ngaphandle kokusetyenziswa kwazo ngokubanzi, iinkcazo ezicacileyo zendlela iikhowudi zokuphinda zisebenze zinqabile kakhulu. Abo bafuna ukuqonda bajongene noku kulandelayo (ukusuka ):
Igama lam nguVadim, eYandex ndiphuhlisa i-MDS yokugcina into yangaphakathi. Kule nqaku, ndiya kuchaza ngamagama alula iziseko zethiyori ze-redundancy codes (iReed-Solomon kunye neekhowudi ze-LRC). Ndiza kukuxelela ukuba isebenza njani, ngaphandle kwezibalo ezintsonkothileyo kunye namagama anqabileyo. Ekugqibeleni ndiya kunika imizekelo yokusebenzisa iikhowudi zokuphindaphinda kwiYandex.
Andizukuqwalasela inani leenkcukacha zemathematika ngokweenkcukacha, kodwa ndiza kubonelela ngamakhonkco abo bafuna ukuntywila nzulu. Ndiya kuphinda ndiqaphele ukuba ezinye iinkcazo zemathematika azinakuba ngqongqo, kuba inqaku alijoliswanga kwiingcali zemathematika, kodwa iinjineli ezifuna ukuqonda umongo walo mbandela.
* Kuncwadi lwesiNgesi, iikhowudi zokungafuneki zidla ngokubizwa ngokuba ziikhowudi zokucima.
1. Undoqo weekhowudi zokungafuneki
Undoqo wazo zonke iikhowudi zokungafuneki zilula kakhulu: gcina (okanye udlulise) idatha ukuze ingalahleki xa kukho iimpazamo (ukusilela kwidisk, iimpazamo zokudluliswa kwedatha, njl. njl.).
Kwiikhowudi ezininzi ze-redundancy, idatha ihlulwe kwiibhloko zedatha ye-n, apho iibhloko ze-m block of redundancy codes zibalwe, okubangela ukuba zizonke iibhloko ze-n + m. Iikhowudi zokuRedundancy zakhiwe ngendlela yokuba iibhloko ze-n data zingafunyanwa kwakhona kusetyenziswa kuphela inxalenye ye-n + m iibhloko. Okulandelayo, siya kuqwalasela kuphela iikhowudi zokurhoxiswa kwe-block, oko kukuthi, ezo apho idatha ihlukaniswe kwiibhloko.
Ukufumana kwakhona zonke iibhloko zedatha, kufuneka ube neebhloko ze-n + m ubuncinane, kuba awukwazi ukufumana iibhloko ze-n ngokuba nebhloko ye-n-1 kuphela (kule meko, kuya kufuneka uthathe ibhloko enye umoya"). Ngaba iibhloko ze-n + m ezingaqhelekanga ngokwaneleyo ukubuyisela yonke idatha? Oku kuxhomekeke kuhlobo lweekhowudi zokungafuneki, umzekelo, iikhowudi ze-Reed-Solomon zikuvumela ukuba ubuyise yonke idatha usebenzisa iibhloko ze-n ngokungenasizathu, kodwa iikhowudi ze-LRC zokuphindaphinda azisoloko.
Ukugcinwa kwedatha
Kwiinkqubo zokugcina idatha, njengomthetho, nganye yeebhloko zedatha kunye neebhloko zekhowudi ye-redundancy ibhaliwe kwidiski eyahlukileyo. Emva koko, ukuba idiski engafanelekanga ayiphumelelanga, idatha yoqobo isenokubuyiselwa kwaye ifundwe. Idatha inokufunyanwa nokuba iidiski ezininzi ziyasilela ngexesha elinye.
Ukuhanjiswa kwedatha
Iikhowudi zokuRedundancy zingasetyenziselwa ukuthumela idatha ngokuthembekileyo kwinethiwekhi engathembekanga. Idatha edlulisiweyo ihlukaniswe kwiibhloko, kwaye iikhowudi zokuphindaphinda zibalwa kubo. Zombini iibhloko zedatha kunye neebhloko zekhowudi zokuphindaphinda zihanjiswa ngenethiwekhi. Ukuba iimpazamo zenzeka kwiibhloko ezingafanelekanga (ukuya kwinani elithile leebhloko), idatha isenokudluliselwa kwinethiwekhi ngaphandle kwempazamo. Iikhowudi zeReed-Solomon, umzekelo, zisetyenziselwa ukuhambisa idatha kwimigca yonxibelelwano ye-optical kunye nonxibelelwano lwesathelayithi.
* Kukho kwakhona iikhowudi zokuphindaphinda apho idatha ingahlukaniswanga kwiibhloko, ezifana neekhowudi ze-Haming kunye neekhowudi ze-CRC, ezisetyenziselwa ngokubanzi ukuhanjiswa kwedatha kwiinethiwekhi ze-Ethernet. Ezi ziikhowudi zokulungisa iimpazamo, zenzelwe ukukhangela iimpazamo, kwaye zingazilungisi (ikhowudi ye-Haming ivumela ulungiso oluyinxenye lweempazamo).
2. Iikhowudi zeReed-Solomon
Iikhowudi zeReed-Solomon yenye yezona khowudi zokuphinda zisetyenziswe ngokubanzi, ezaqanjwa emva phayaa ngeminyaka yoo-1960 kwaye zaqala ukusetyenziswa ngokubanzi ngeminyaka yoo-1980 ukuveliswa kobunzima beediski ezixineneyo.
Kukho imibuzo emibini ephambili yokuqonda iikhowudi zeReed-Solomon: 1) indlela yokwenza iibhloko zeekhowudi zokuphindaphinda; 2) indlela yokubuyisela idatha usebenzisa iibhloko zekhowudi yokuphindaphinda. Makhe sifumane iimpendulo kubo.
Ukwenza lula, siza kuphinda sicinge ukuba n=6 kunye ne-m=4. Ezinye izikimu ziqwalaselwa ngothelekiso.
Uyenza njani iibhloko zekhowudi yokungafuneki
Ibhloko nganye yeekhowudi zokuphindaphinda ibalwa ngokuzimeleyo kwabanye. Zonke iibhloko zedatha ze-n zisetyenziselwa ukubala ibhloko nganye. Kumzobo ongezantsi, i-X1-X6 ziibhloko zedatha, i-P1-P4 ziibhloko zekhowudi yokuphindaphinda.
Zonke iibhloko zedatha kufuneka zilingane, kwaye iibhithi zero zingasetyenziselwa ukulungelelaniswa. Iibhloko zekhowudi ye-redundancy ezibangelwayo ziya kuba nobukhulu obufanayo neebhloko zedatha. Zonke iibhloko zedatha zahlulwe ngamagama (umzekelo, iibhithi ezili-16). Masithi sahlulahlula iibhloko zedatha zibe ngu-k amagama. Ke zonke iibhloko zeekhowudi zokungafuneki kwakhona ziyakwahlulwa zibe ngamagama k.
Ukubala igama le-i-th yebhloko nganye yokuphindaphinda, amagama e-i-th azo zonke iibhloko zedatha ziya kusetyenziswa. Ziya kubalwa ngokwefomula ilandelayo:
Apha amaxabiso x ngamagama eebhloko zedatha, p ngamagama eebhloko zekhowudi ye-redundancy, zonke i-alpha, i-beta, i-gamma kunye ne-delta ngamanani akhethwe ngokukodwa afana kuzo zonke i-i. Kufuneka kuthiwe kwangoko ukuba zonke ezi xabiso azikho amanani aqhelekileyo, kodwa ziyinxalenye yentsimi yeGalois; imisebenzi +, -, *, / ayiyomisebenzi eqhelekileyo kuthi sonke, kodwa imisebenzi ekhethekileyo yaziswa kwizinto zeGalois. intsimi.
Kutheni kufuneka amasimi eGalois?
Kuya kubonakala ngathi yonke into ilula: sahlula idatha kwiibhloko, iibhloko zibe ngamagama, sisebenzisa amagama eebhloko zedatha sibala amagama eebhloko zekhowudi ye-redundancy - sifumana iibhloko zekhowudi ye-redundancy. Ngokubanzi le yindlela esebenza ngayo, kodwa usathana ukwiinkcukacha:
- Njengoko kuchaziwe ngasentla, ubungakanani begama bulungisiwe, kumzekelo wethu iibhithi ezili-16. Iifomula ezingentla zeekhowudi zeReed-Solomon zezokuba xa usebenzisa amanani apheleleyo aqhelekileyo, isiphumo sokubala u-p sisenokungamelwa kusetyenziswa igama lobukhulu obusebenzayo.
- Xa kufunyanwa kwakhona idatha, iifomyula ezingentla ziya kuthathwa njengenkqubo yee-equations ekufuneka isonjululwe ukuze kufumaneke kwakhona idatha. Ngexesha lenkqubo yesisombululo, kunokuba yimfuneko ukwahlula amanani apheleleyo omnye komnye, okukhokelela kwinani lokwenyani elingenako ukumelwa ngokuchanekileyo kwimemori yekhompyuter.
Ezi ngxaki zithintela ukusetyenziswa kweekhowudi zeReed-Solomon. Isisombululo sengxaki siyintsusa, sinokuchazwa ngolu hlobo lulandelayo: makhe size namanani akhethekileyo anokumelwa ngokusebenzisa amagama obude obufunekayo (umzekelo, iibhithi ezili-16), kunye nesiphumo sokwenza yonke imisebenzi apho (ukongeza). , ukuthabatha, uphinda-phindo, ulwahlulo) ziyakunikwa kwakhona kwinkumbulo yekhompyutha kusetyenziswa amagama anobude obufunekayo.
Loo manani “akhethekileyo” aye afundwa kwimathematika ixesha elide; abizwa ngokuba ngamabala. Indawo yiseti yezinto ezinomsebenzi wokudibanisa, ukuthabatha, uphinda-phindo kunye nolwahlulo oluchaziweyo kubo.
Imimandla yeGalois* ngamasimi apho kukho isiphumo esikhethekileyo somsebenzi ngamnye (+, -, *, /) kuzo naziphi na iziqalelo ezibini zentsimi. Imimandla yeGalois inokwakhiwa ngamanani angamandla e-2: 2, 4, 8, 16, njl. Umzekelo, kumagama angama-2-bit, le yintsimi equlethe izinto ezingama-16, kwisibini ngasinye apho ungafumana isiphumo sawo nawuphi na umsebenzi (+, -, *, /). Amaxabiso ka-x, p, alpha, beta, gamma, delta ukusuka kwii-equations apha ngasentla aya kuqwalaselwa njengezinto ze-Galois field kubalo.
Ngaloo ndlela, sinenkqubo ye-equations esinokuthi senze ngayo iibhloko zeekhowudi zokuphindaphinda ngokubhala inkqubo efanelekileyo yekhompyutha. Ukusebenzisa inkqubo efanayo yokulinganisa, unokwenza ukubuyisela idatha.
* Le asiyonkcazelo engqongqo, kodwa yinkcazelo.
Indlela yokubuyisela idatha
Ukubuyisela kwakhona kuyafuneka xa ezinye iibhloko ze-n + m zingekho. Ezi zinokuba zombini iibhloko zedatha kunye neebhloko zekhowudi yokuphindaphinda. Ukungabikho kweebhloko zedatha kunye / okanye iibhloko zekhowudi zokuphindaphinda kuya kuthetha ukuba ii-variables ezihambelanayo ze-x kunye / okanye ze-p azaziwa kwii-equations apha ngasentla.
Ii-equations zeekhowudi zeReed-Solomon zinokujongwa njengenkqubo yee-equations apho zonke ialpha, i-beta, i-gamma, ixabiso le-delta zizii-constants, zonke u-x kunye no-p ezihambelana neebhloko ezikhoyo zaziwa ngokuguquguqukayo, kwaye i-x eseleyo kunye ne-p ayaziwa.
Umzekelo, vumela iibhloko zedatha 1, 2, 3 kunye nekhowudi ye-redundancy block 2 ingafumaneki, emva koko kwiqela le-i-th lamagama kuya kubakho le nkqubo ilandelayo yee-equations (ezingaziwa ziphawulwe ngombala obomvu):
Sinenkqubo ye-4 equations kunye ne-4 engaziwayo, oku kuthetha ukuba sinokuyicombulula kwaye sibuyisele idatha!
Ukusuka kule nkqubo ye-equations inani lezigqibo ezilandelayo malunga nokubuyiswa kwedatha yeekhowudi zeReed-Solomon (n iibhloko zedatha, iibhloko zekhowudi yokuphindaphinda):
- Idatha inokufunyanwa kwakhona ukuba naziphi na iibhloko m okanye ezimbalwa ezilahlekileyo. Ukuba i-m + 1 okanye iibhloko ezininzi zilahlekile, idatha ayikwazi ukubuyiselwa: akunakwenzeka ukusombulula inkqubo ye-m equations kunye ne-m + 1 engaziwayo.
- Ukufumana kwakhona ibhloko yedatha enye, kufuneka usebenzise nayiphi na i-n yeebhloko eziseleyo, kwaye ungasebenzisa naziphi na iikhowudi zokungafuneki.
Yintoni enye ekufuneka uyazi
Kule nkcazo ingentla, ndinqanda inani lemiba ebalulekileyo efuna ukuntywila nzulu kwimathematika ukuba iqwalaselwe. Ngokukodwa, andithethi nto malunga noku kulandelayo:
- Inkqubo ye-equations yeekhowudi zeReed-Solomon kufuneka ibe nesisombululo (esisodwa) sayo nayiphi na indibaniselwano yezinto ezingaziwayo (akukho ngaphezu kwe-m engaziwayo). Ngokusekwe kule mfuno, amaxabiso ealpha, beta, gamma kunye nedelta akhethiwe.
- Inkqubo yokulinganisa kufuneka ikwazi ukwakhiwa ngokuzenzekelayo (kuxhomekeke ekubeni zeziphi iibhloko ezingafumanekiyo) kwaye zisonjululwe.
- Kufuneka sakhe umhlaba weGalois: kwisayizi yegama elinikiweyo, sikwazi ukufumana isiphumo sayo nayiphi na imisebenzi (+, -, *, /) yazo naziphi na izinto ezimbini.
Ekupheleni kwenqaku kukho iimbekiselo kuncwadi ngale miba ibalulekileyo.
Ukhetho lwe-n kunye ne-m
Indlela yokukhetha u-n kunye no-m ekusebenzeni? Ngokwenza, kwiinkqubo zokugcina idatha, iikhowudi zokuphindaphinda zisetyenziselwa ukugcina indawo, ngoko ke m ihlala ikhethwa ngaphantsi kwe-n. Amaxabiso abo athile axhomekeke kwizinto ezininzi, kubandakanya:
- Ukuthembeka kokugcinwa kwedatha. I-m enkulu, inani elikhulu lokungaphumeleli kwedisk enokusinda, oko kukuthi, ukuthembeka okuphezulu.
- Ukugcinwa okungafunekiyo. Ukuphakama komlinganiselo we-m / n, ukuphakama kwe-redundancy yokugcina kuya kuba, kwaye inkqubo iya kuba yindleko ngakumbi.
- Cela ixesha lokuqhubekeka. Okukhona inkulu isamba esingu-n + m, kokukhona ixesha lokuphendula kwizicelo liya kuba lide. Ekubeni idata yokufunda (ngexesha lokubuyisela) ifuna ukufundwa kweebhloko ezigcinwe kwiidiski ezahlukeneyo zen, ixesha lokufunda liya kumiselwa yeyona diski icothayo.
Ukongezelela, ukugcinwa kwedatha kwii-DC ezininzi kubeka izithintelo ezongezelelweyo ekukhethweni kwe-n kunye ne-m: ukuba i-1 DC ivaliwe, idatha kufuneka ihlale ikhona ukuze ifundwe. Ngokomzekelo, xa ugcina idatha kwi-3 DCs, le meko ilandelayo kufuneka ihlangane: m > = n/2, ngaphandle koko kunokubakho imeko apho idatha ingafumanekiyo ekufundeni xa i-1 DC icinyiwe.
3. I-LRC - Iikhowudi zoKwakha kwakhona kwiNgingqi
Ukufumana kwakhona idata usebenzisa iikhowudi Reed-Solomon, kufuneka usebenzise n iibhloko data ngokungenasizathu. Oku kungalunganga okubaluleke kakhulu kwiinkqubo zokugcinwa kwedatha ezisasazwayo, kuba ukubuyisela idatha kwidiski enye eyaphukileyo, kuya kufuneka ufunde idatha kuninzi lwabanye, udala umthwalo owongezelelweyo omkhulu kwiidiski kunye nenethiwekhi.
Ezona mpazamo zixhaphakileyo kukungafumaneki kwebhloko enye yedatha ngenxa yokusilela okanye ukugcwala kwediski enye. Ngaba kunokwenzeka ukunciphisa umthwalo ogqithisiweyo wokubuyisela idatha kule meko (eyona ixhaphakileyo)? Kuyavela ukuba unako: kukho iikhowudi zokungafuneki kwe-LRC ngokukodwa kule njongo.
I-LRC (IiKhowudi zoKwakha kwakhona kwiNdawo) ziikhowudi zokuphinda zisetyenziswe eziveliswe nguMicrosoft ukuze zisetyenziswe kwi-Windows Azure Storage. Ingcamango ye-LRC ilula ngokusemandleni: yahlula zonke iibhloko zedatha zibe ngamaqela amabini (okanye ngaphezulu) kwaye ufunde inxalenye yeebhloko zekhowudi ye-redundancy kwiqela ngalinye ngokwahlukileyo. Emva koko ezinye iibhloko zekhowudi zokuphindaphinda ziya kubalwa kusetyenziswa zonke iibhloko zedatha (kwi-LRC zibizwa ngokuba yikhowudi ye-redundancy yehlabathi), kwaye ezinye - zisebenzisa elinye lamaqela amabini eebhloko zedatha (zibizwa ngokuba ziikhowudi ze-redundancy zendawo).
I-LRC ichazwa ngamanani amathathu: i-nrl, apho i-n inani leebhloko zedatha, r linani leebhloko zekhowudi ye-redundancy yehlabathi, l linani leebhloko zekhowudi ye-redundancy yendawo. Ukufunda idatha xa ibhloko yedatha enye ingafumaneki, kufuneka ufunde kuphela iibhloko ze-n / l - oku ngamaxesha l ngaphantsi kweekhowudi zeReed-Solomon.
Ngokomzekelo, qwalasela inkqubo ye-LRC 6-2-2. X1–X6 — 6 data blocks, P1, P2 — 2 global redundancy blocks, P3, P4 — 2 iibhloko zokungafuneki kwasekhaya.
Iibhloko zekhowudi yokuRedundancy P1, i-P2 ibalwa ngokusebenzisa zonke iibhloko zedatha. I-redundancy code block P3 - usebenzisa iibhloko zedatha X1-X3, ikhowudi ye-redundancy block P4 - usebenzisa iibhloko zedatha X4-X6.
Okunye kwenziwa kwi-LRC ngokufaniswa neekhowudi zeReed-Solomon. Ii-equations zokubala amagama eebhloko zekhowudi zokungafuneki ziya kuba:
Ukukhetha amanani alpha, i-beta, i-gamma, i-delta, inani leemeko kufuneka lihlangane ukuze kuqinisekiswe ukuba kunokwenzeka ukubuyiswa kwedatha (oko kukuthi, ukusombulula inkqubo ye-equation). Unokufunda ngakumbi malunga nabo kwi .
Kwakhona ekusebenzeni, ukusebenza kwe-XOR kusetyenziselwa ukubala iikhowudi ze-redundancy zendawo P3, P4.
Iqela lezigqibo liyalandela kwinkqubo yee-equations ye-LRC:
- Ukubuyisela nayiphi na ibhloko yedatha ye-1, kwanele ukufunda iibhloko ze-n / l (n / 2 kumzekelo wethu).
- Ukuba iibhloko ze-r + l azifumaneki, kwaye zonke iibhloko zifakwe kwiqela elinye, ngoko idatha ayikwazi ukubuyiselwa. Oku kulula ukukuchaza ngomzekelo. Vumela iibhloko ze-X1–X3 kunye ne-P3 zingafumaneki: ezi ziibhloko ze-r + l kwiqela elinye, ezi-4 kwimeko yethu. Emva koko sinenkqubo yee-equations ezi-3 kunye ne-4 engaziwayo engenakusombululeka.
- Kuzo zonke ezinye iimeko zokungafumaneki kweebhloko ze-r + l (xa ubuncinane ibhloko enye ifumaneka kwiqela ngalinye), idatha kwi-LRC inokubuyiselwa.
Ke, i-LRC igqwesa iikhowudi zeReed-Solomon ekubuyiseni idatha emva kweempazamo enye. Kwiikhowudi zeReed-Solomon, ukubuyisela ibhloko enye yedatha, kufuneka usebenzise iibhloko ze-n, kwaye kwi-LRC, ukubuyisela ibhloko enye yedatha, kwanele ukusebenzisa iibhloko ze-n / l (n / 2 kumzekelo wethu). Kwelinye icala, i-LRC ingaphantsi kwiikhowudi zeReed-Solomon ngokwenani eliphezulu leempazamo ezivumelekileyo. Kule mizekelo ingasentla, iikhowudi zeReed-Solomon ziyakwazi ukubuyisela idatha yazo naziphi na iimpazamo ezi-4, kwaye kwi-LRC kukho imidibaniso emi-2 yeempazamo ezi-4 xa idatha ingafunyanwa.
Okona kubaluleke ngakumbi kuxhomekeke kwimeko ethile, kodwa amaxesha amaninzi ukonga kumthwalo ogqithileyo obonelelwa yi-LRC ukodlula ugcino olungathembekanga kancinci.
4. Ezinye iikhowudi zokungafuneki
Ngaphandle kweekhowudi zeReed-Solomon kunye ne-LRC, zininzi ezinye iikhowudi zokungafuneki. Iikhowudi ezahlukeneyo zokungafuneki zisebenzisa imathematika ezahlukeneyo. Nazi ezinye iikhowudi zokungafuneki:
- Ikhowudi yokungafuneki kusetyenziswa umsebenzisi we-XOR. Umsebenzi we-XOR wenziwa kwiibhloko zedatha ye-n, kwaye i-1 block of redundancy codes ifunyenwe, oko kukuthi, iskimu se-n + 1 (n iibhloko zedatha, ikhowudi ye-redundancy). Isetyenziswa kwi , apho iibhloko zedatha kunye neekhowudi zokuphindaphinda zibhalwa ngebhayisikile kuzo zonke iidiski zoluhlu.
- I-algorithm ye-even-odd esekelwe kumsebenzi we-XOR. Ikuvumela ukuba wakhe iibhloko ezi-2 zeekhowudi zokuphindaphinda, oko kukuthi, i-n +2 iskimu.
- I-algorithm ye-STAR esekelwe ekusebenzeni kwe-XOR. Ikuvumela ukuba wakhe iibhloko ezi-3 zeekhowudi zokungafuneki, oko kukuthi, i-n +3 iskimu.
- Iikhowudi zePyramidi zezinye iikhowudi zokungafuneki kwaMicrosoft.
5. Sebenzisa kwiYandex
Inani leeprojekthi zeziseko zeYandex zisebenzisa iikhowudi zokuphindaphinda ukugcinwa kwedatha ethembekileyo. Nantsi eminye imizekelo:
- I-MDS yokugcina into yangaphakathi, endiyibhale ngayo ekuqaleni kwenqaku.
- - ImephuNciphisa inkqubo yeYandex.
- (Yandex DataBase) - i-newSQL yokusasazwa kwedatha.
I-MDS isebenzisa iikhowudi zokungafuneki kwe-LRC, iskimu se-8-2-2. Idatha eneekhowudi zokuphindaphinda ibhaliwe kwiidiski ezahlukeneyo ze-12 kwiiseva ezahlukeneyo kwii-DC ezi-3 ezahlukeneyo: iiseva ezi-4 kwi-DC nganye. Funda ngakumbi ngale nto kwi .
I-YT isebenzisa zombini iikhowudi zeReed-Solomon (iSkimu 6-3), eziye zaba zezokuqala ukuphumeza, kunye neekhowudi ze-LRC zokungafuneki (iSkimu 12-2-2), kunye ne-LRC eyona ndlela yokugcina ekhethwayo.
I-YDB isebenzisa iikhowudi zokuphindaphinda ezisekwe ngokungaqhelekanga (Umfanekiso 4-2). Malunga neekhowudi zokungafuneki kwi-YDB esele .
Ukusetyenziswa kweenkqubo ezahlukeneyo zekhowudi yokufuna umsebenzi ngenxa yeemfuno ezahlukeneyo zeenkqubo. Ngokomzekelo, kwi-MDS, idatha egcinwe kusetyenziswa i-LRC ifakwe kwi-3 DCs kanye. Kubalulekile kuthi ukuba idatha ihlala ikhona ukuze ifundwe ukuba i-1 yanoma yiyiphi i-DCs ayiphumelelanga, ngoko ke iibhloko kufuneka zihanjiswe kuwo wonke ama-DCs ukwenzela ukuba ukuba nayiphi na i-DC ayifumaneki, inani leebhloko ezingenakufikeleleka alikho ngaphezu kokuvunyelwa. Kwiskimu se-8-2-2, unokubeka iibhloko ezi-4 kwi-DC nganye, ngoko xa nayiphi na i-DC ivaliwe, iibhloko ezi-4 aziyi kufumaneka, kwaye idatha ingafundwa. Naluphi na iskimu esisikhethayo xa sibeka kwi-3 DCs, kuyo nayiphi na imeko kufuneka kubekho (r + l) / n > = 0,5, oko kukuthi, ukugcinwa kwe-redundancy kuya kuba ubuncinane be-50%.
Kwi-YT imeko yahlukile: iqoqo ngalinye le-YT lifumaneka ngokupheleleyo kwi-1 DC (amaqela ahlukeneyo kwii-DCs ezahlukeneyo), ngoko akukho mqobo unjalo. Iskimu se-12-2-2 sibonelela nge-33% yokuphindaphinda, oko kukuthi, ukugcinwa kwedatha kungabizi, kwaye inokusinda ukuya kuthi ga kwi-4 ngexesha elifanayo lokuphuma kwediski, njengesicwangciso se-MDS.
Kukho iimpawu ezininzi zokusetyenziswa kweekhowudi zokuphindaphinda kwiinkqubo zokugcinwa kwedatha kunye nokucubungula: i-nuances yokubuyisela idatha, impembelelo yokubuyisela ngexesha lokuqhuba umbuzo, iimpawu zokurekhodwa kwedatha, njl. Ndiza kuthetha ngokwahlukileyo ngezi kunye nezinye iimpawu. yokusetyenziswa kweekhowudi zokuphindaphinda ekusebenzeni, ukuba isihloko siya kuba nomdla.
6. Amakhonkco
- Uthotho lwamanqaku malunga neekhowudi zeReed-Solomon kunye nemimandla yeGalois:
Bajonga nzulu kwimathematika ngolwimi olufikelelekayo. - Inqaku elivela kuMicrosoft malunga neLRC:
Icandelo lesi-2 liyicacisa ngokufutshane ithiyori kwaye emva koko lixoxe ngamava kunye ne-LRC ngokusebenza. - Inkqubo engaqhelekanga:
- STAR iskimu:
- Iikhowudi zephiramidi:
- Iikhowudi zokungafuneki kwi-MDS:
- Iikhowudi zokungafuneki kwi-YT:
- Iikhowudi zokungafuneki kwi-YDB:
umthombo: www.habr.com