Sena ke kamoo redundancy e shebahalang kateng
Likhoutu tsa Redundancy * li sebelisoa haholo lits'ebetsong tsa khomphutha ho eketsa ts'epahalo ea polokelo ea data. Ho Yandex li sebelisoa mererong e mengata. Ka mohlala, ho sebelisa likhoutu tsa ho fokotsa chelete ho e-na le ho pheta-pheta sebakeng sa rona sa polokelo ea lintho tse ka hare ho boloka limilione ntle le ho tela botšepehi. Empa ho sa tsotellehe ts'ebeliso ea bona e atileng, litlhaloso tse hlakileng tsa hore na li-code tsa redundancy li sebetsa joang ha li fumanehe haholo. Ba batlang ho utloisisa ba tobane le tse ka bang tse latelang (ho tloha ho ):
Lebitso la ka ke Vadim, ho Yandex ke ntse ke hlahisa MDS ea polokelo ea lintho tse ka hare. Sehloohong sena, ke tla hlalosa ka mantsoe a bonolo metheo ea theory of redundancy codes (Reed-Solomon le LRC codes). Ke tla u bolella kamoo e sebetsang kateng, ntle le lipalo tse rarahaneng le mantsoe a sa tloaelehang. Qetellong ke tla fana ka mehlala ea ho sebelisa li-code tsa redundancy ho Yandex.
Nke ke ka nahana ka lintlha tse 'maloa tsa lipalo ka botlalo, empa ke tla fana ka likhokahano bakeng sa ba batlang ho qoela ka botebo. Ke tla boela ke hlokomele hore litlhaloso tse ling tsa lipalo li ka 'na tsa se ke tsa e-ba thata, kaha sehlooho sena ha se reretsoe litsebi tsa lipalo, empa bakeng sa baenjiniere ba batlang ho utloisisa moelelo oa taba.
* Lingoliloeng tsa puo ea Senyesemane, li-redundancy codes hangata li bitsoa erasure codes.
1. Moelelo oa likhoutu tsa ho fokotsa mosebetsi
Bohlokoa ba likhoutu tsohle tsa bofokoli bo bonolo haholo: boloka (kapa fetisetsa) data e le hore e se ke ea lahleha ha liphoso li etsahala (ho hloleha ha disk, liphoso tsa phetisetso ea data, joalo-joalo).
Likhoutung tse ngata * tsa redundancy, data e arotsoe ka li-blocks tsa data, tseo m li-blocks tsa li-code tsa redundancy li baloang, tse hlahisang kakaretso ea n + m blocks. Likhoutu tsa Redundancy li hahiloe ka tsela eo n blocks ea data e ka khutlisoang ho sebelisoa karoloana feela ea n + m blocks. Ka mor'a moo, re tla nahana feela thibela li-redundancy codes, ke hore, tseo ho tsona data e arotsoeng ka li-blocks.
Ho khutlisa li-n blocks tsohle tsa data, o hloka ho ba le bonyane n of n + m blocks, kaha o ke ke oa fumana n blocks ka ho ba le n-1 block (tabeng ena, o tla tlameha ho nka "block" e le 'ngoe feela. moea”). Na li-block tsa n + m tse sa reroang li lekane ho khutlisa data kaofela? Sena se ipapisitse le mofuta oa likhoutu tsa redundancy, mohlala, likhoutu tsa Reed-Solomon li u lumella ho khutlisa data eohle u sebelisa li-blocks tse sa reroang, empa likhoutu tsa redundancy tsa LRC ha se kamehla.
Polokelo ea data
Litsamaisong tsa polokelo ea data, joalo ka molao, e 'ngoe le e' ngoe ea li-blocks tsa data le li-blocks tsa redundancy code e ngotsoe ho disk e arohaneng. Joale, haeba disk e sa lumellaneng e hlōleha, data ea pele e ntse e ka tsosolosoa le ho baloa. Lintlha li ka fumanoa le haeba li-disk tse ngata li hlōleha ka nako e le 'ngoe.
Phetiso ya data
Likhoutu tsa Redundancy li ka sebelisoa ho fetisa data ka mokhoa o ts'eptjoang marang-rang a sa tšepahaleng. Lintlha tse fetisitsoeng li arotsoe ka li-blocks, 'me li-code tsa redundancy li balloa bakeng sa bona. Ka bobeli li-block tsa data le li-code tsa redundancy li fetisoa holim'a marang-rang. Haeba liphoso li etsahala ka li-blocks (ho fihlela palo e itseng ea li-blocks), data e ntse e ka fetisoa holim'a marang-rang ntle le liphoso. Likhoutu tsa Reed-Solomon, mohlala, li sebelisetsoa ho fetisa data ka mehala ea puisano ea optical le puisanong ea sathelaete.
* Ho boetse ho na le likhoutu tsa redundancy moo data e sa arotsoeng ka li-blocks, joalo ka likhoutu tsa Hamming le likhoutu tsa CRC, tse sebelisoang haholo bakeng sa phetiso ea data marang-rang a Ethernet. Tsena ke likhoutu tsa ho lokisa liphoso, li etselitsoe ho bona liphoso, eseng ho li lokisa (Khoutu ea Hamming e boetse e lumella ho lokisoa ka mokhoa o itseng oa liphoso).
2. Reed-Solomon codes
Likhoutu tsa Reed-Solomon ke e 'ngoe ea likhoutu tse sebelisoang ka ho fetesisa tse sebelisoang haholo, tse qapiloeng morao koana lilemong tsa bo-1960' me tsa qala ho sebelisoa haholo lilemong tsa bo-1980 bakeng sa tlhahiso e kholo ea li-compact disc.
Ho na le lipotso tse peli tsa bohlokoa bakeng sa ho utloisisa li-code tsa Reed-Solomon: 1) mokhoa oa ho etsa li-blocks tsa codes tsa redundancy; 2) mokhoa oa ho khutlisa data u sebelisa li-block tsa khoutu tsa redundancy. A re fumane likarabo tsa tsona.
Bakeng sa ho nolofatsa, re tla tsoela pele ho nahana hore n=6 le m=4. Merero e meng e nkoa ka papiso.
Mokhoa oa ho theha li-block tsa khoutu tsa redundancy
E 'ngoe le e' ngoe ea li-code tsa redundancy e baloa ntle le tse ling. Li-blocks tsohle tsa n data li sebelisoa ho bala boloko bo bong le bo bong. Setšoantšong se ka tlase, X1-X6 ke li-blocks tsa data, P1-P4 ke li-block tsa khoutu tsa redundancy.
Li-block tsa data kaofela li tlameha ho lekana ka boholo, 'me likotoana tsa zero li ka sebelisoa bakeng sa ho tsamaisana. Li-block tsa khoutu tsa redundancy tse hlahisoang li tla ba boholo bo lekanang le li-blocks tsa data. Li-block tsa data kaofela li arotsoe ka mantsoe (mohlala, li-bits tse 16). Ha re re re arola li-block tsa data ka mantsoe a k. Ebe li-blocks tsohle tsa codes tsa redundancy le tsona li tla aroloa ka mantsoe a k.
Ho bala lentsoe la i-th la thibelo e 'ngoe le e' ngoe ea redundancy, ho tla sebelisoa mantsoe a i-th a li-blocks tsohle tsa data. Li tla baloa ho latela foromo e latelang:
Mona litekanyetso tsa x ke mantsoe a li-blocks tsa data, p ke mantsoe a li-block tsa codec, alpha, beta, gamma le delta kaofela ke linomoro tse khethiloeng ka ho khetheha tse tšoanang ho bohle i. Ho tlameha ho boleloa hang-hang hore litekanyetso tsena kaofela ha se lipalo tse tloaelehileng, empa likarolo tsa tšimo ea Galois; ts'ebetso +, -, *, / ha se ts'ebetso e tloaelehileng ho rona bohle, empa ts'ebetso e khethehileng e hlahisitsoeng likarolong tsa Galois. lebala.
Ke hobane'ng ha masimo a Galois a hlokahala?
Ho ne ho tla bonahala eka ntho e 'ngoe le e' ngoe e bonolo: re arola lintlha ka li-blocks, li-blocks ka mantsoe, re sebelisa mantsoe a li-blocks tsa data re bala mantsoe a li-blocks tsa khoutu ea redundancy - re fumana li-blocks tsa khoutu ea redundancy. Ka kakaretso ena ke tsela eo e sebetsang ka eona, empa diabolosi o ka lintlha:
- Joalokaha ho boletsoe ka holimo, boholo ba lentsoe bo tsitsitse, mohlala oa rona 16 bits. Litlhaloso tse kaholimo bakeng sa likhoutu tsa Reed-Solomon li joalo hore ha u sebelisa linomoro tse tloaelehileng, sephetho sa ho bala p se kanna sa se ke sa hlahisoa ho sebelisoa lentsoe la boholo bo nepahetseng.
- Ha o khutlisa data, liforomo tse kaholimo li tla nkuoa e le sistimi ea li-equations e tlamehang ho rarolloa e le hore u fumane data hape. Nakong ea ts'ebetso ea tharollo, ho ka 'na ha hlokahala hore ho arola li-integers ka bobeli, ho fella ka palo ea sebele e ke keng ea emeloa ka nepo mohopolong oa k'homphieutha.
Mathata ana a thibela tšebeliso ea linomoro tse felletseng bakeng sa likhoutu tsa Reed-Solomon. Tharollo ea bothata ke ea mantlha, e ka hlalosoa ka tsela e latelang: a re tle le linomoro tse khethehileng tse ka emeloa ho sebelisa mantsoe a bolelele bo hlokahalang (mohlala, likotoana tse 16), le sephetho sa ho etsa lits'ebetso tsohle tseo ho tsona (ho eketsa). , ho tlosa, katiso, karohano) le tsona li tla hlahisoa mohopolong oa khomphutha ho sebelisoa mantsoe a bolelele bo hlokahalang.
Lipalo tse joalo “tse khethehileng” li ’nile tsa ithutoa ke lipalo ka nako e telele; li bitsoa masimo. Tšimo ke sehlopha sa lintho tse nang le ts'ebetso ea ho kenyelletsa, ho tlosa, ho atisa le karohano bakeng sa tsona.
Masimo a Galois * ke masimo ao ho nang le phello e ikhethang ea ts'ebetso e 'ngoe le e' ngoe (+, -, *, /) bakeng sa likarolo leha e le life tse peli tsa tšimo. Masimo a Galois a ka hahuoa bakeng sa linomoro tseo e leng matla a 2: 2, 4, 8, 16, joalo-joalo (ha e le hantle matla a nomoro leha e le efe e ka sehloohong p, empa ka ts'ebetso re thahasella feela matla a 2). Ka mohlala, bakeng sa mantsoe a 16-bit, ena ke tšimo e nang le likarolo tse 65, bakeng sa para e 'ngoe le e' ngoe eo u ka fumanang liphello tsa ts'ebetso leha e le efe (+, -, *, /). Litekanyetso tsa x, p, alpha, beta, gamma, delta ho tsoa ho li-equation tse kaholimo li tla nkuoa e le likarolo tsa lebala la Galois bakeng sa lipalo.
Ka hona, re na le tsamaiso ea li-equations eo ka eona re ka hahang li-blocks of redundancy codes ka ho ngola lenaneo le loketseng la k'homphieutha. U sebelisa mokhoa o tšoanang oa li-equations, u ka etsa ho hlaphoheloa ha data.
* Ena ha se tlhaloso e tiileng, empa ke tlhaloso.
Mokhoa oa ho khutlisa data
Ho hlokahala tsosoloso ha tse ling tsa li-blocks tsa n + m li le sieo. Tsena e ka ba li-block tsa data le li-block tsa khoutu ea redundancy. Ho ba sieo ha data blocks le / kapa redundancy code blocks ho tla bolela hore mefuta e lumellanang ea x le / kapa p ha e tsejoe ho li-equations tse ka holimo.
Li-equation tsa likhoutu tsa Reed-Solomon li ka nkuoa e le sistimi ea li-equation moo boleng bohle ba alpha, beta, gamma, delta e leng li-constants, tsohle x le p tse tsamaellanang le li-block tse fumanehang ke mefuta e tsebahalang, 'me tse setseng x le p. ha li tsejoe.
Ka mohlala, tlohela data li-block 1, 2, 3 le redundancy code block 2 li se ke tsa fumaneha, joale bakeng sa sehlopha sa i-th sa mantsoe ho tla ba le tsamaiso e latelang ea li-equations (tse sa tsejoeng li ngotsoe ka bofubelu):
Re na le tsamaiso ea 4 equations le 4 tse sa tsejoeng, ho bolelang hore re ka e rarolla le ho tsosolosa lintlha!
Ho tsoa tsamaisong ena ea lipalo ho latela liqeto tse ngata mabapi le ho hlaphoheloa ha data bakeng sa likhoutu tsa Reed-Solomon (n data blocks, m redundancy code blocks):
- Lintlha li ka fumanoa haeba li-blocks leha e le life kapa tse fokolang li lahlehile. Haeba m + 1 kapa ho feta li-blocks li lahlehile, data e ke ke ea tsosolosoa: ho ke ke ha khoneha ho rarolla tsamaiso ea m equations le m + 1 tse sa tsejoeng.
- Ho khutlisa sebaka se le seng sa data, o hloka ho sebelisa n ea li-blocks tse setseng, 'me u ka sebelisa likhoutu life kapa life tsa redundancy.
Ke eng hape eo u hlokang ho e tseba
Tlhalosong e ka holimo, ke qoba lintlha tse 'maloa tsa bohlokoa tse hlokang hore motho a iketsetse thuto ea lipalo ka botebo. Haholo-holo, ha ke bue letho ka tse latelang:
- Sistimi ea li-equations bakeng sa likhoutu tsa Reed-Solomon e tlameha ho ba le tharollo (e ikhethang) bakeng sa motsoako ofe kapa ofe oa tse sa tsejoeng (ho feta m tse sa tsejoeng). Ho ipapisitsoe le tlhoko ena, ho khethoa litekanyetso tsa alpha, beta, gamma le delta.
- Sistimi ea equations e tlameha ho etsoa ka bo eona (ho latela hore na li-block ha li fumanehe) le ho rarolloa.
- Re hloka ho aha tšimo ea Galois: bakeng sa boholo ba lentsoe le fanoeng, re khone ho fumana sephetho sa ts'ebetso efe kapa efe (+, -, *, /) bakeng sa likarolo life kapa life tse peli.
Qetellong ea sengoloa ho na le litšupiso tsa lingoliloeng mabapi le litaba tsena tsa bohlokoa.
Khetho ea n le m
Joang ho khetha n le m ka ts'ebetso? Ka ts'ebetso, lits'ebetsong tsa polokelo ea data, li-code tsa redundancy li sebelisetsoa ho boloka sebaka, kahoo m e lula e khethoa ka tlase ho n. Litekanyetso tsa bona tse ikhethileng li ipapisitse le lintlha tse 'maloa, ho kenyelletsa:
- Ho tšepahala ha polokelo ea data. E kholoanyane m, palo e kholo ea ho hlōleha ha disk e ka pholohang, ke hore, ho tšepahala ho phahameng.
- Polokelo e sa hlokahaleng. Ha karo-karolelano ea m / n e phahame, ho tla ba le khaello ea polokelo e phahameng, 'me tsamaiso e tla ba e theko e boima haholo.
- Kopa nako ea ho sebetsa. Ha kakaretso ea n + m e le kholoanyane, nako ea karabo ea likopo e tla ba telele. Kaha ho bala data (nakong ea ho hlaphoheloa) ho hloka ho bala n li-blocks tse bolokiloeng ho li-disk tse fapaneng, nako ea ho bala e tla khethoa ke disk e liehang ka ho fetisisa.
Ho phaella moo, ho boloka boitsebiso ho li-DC tse 'maloa ho beha lithibelo tse eketsehileng mabapi le khetho ea n le m: haeba 1 DC e tima, boitsebiso bo ntse bo tlameha ho ba teng bakeng sa ho bala. Ka mohlala, ha u boloka boitsebiso ho 3 DCs, boemo bo latelang bo tlameha ho finyelloa: m > = n/2, ho seng joalo ho ka 'na ha e-ba le boemo boo data e sa fumaneheng bakeng sa ho bala ha 1 DC e tima.
3. LRC - Local Reconstruction Codes
Ho khutlisa data ho sebelisa likhoutu tsa Reed-Solomon, u tlameha ho sebelisa li-block tsa data tse sa reroang. Ena ke bothata bo boholo haholo bakeng sa lits'ebetso tsa polokelo ea data, hobane ho khutlisa data ho disk e le 'ngoe e robehileng, o tla tlameha ho bala data ho tsoa ho tse ling tse ngata, ho theha mojaro o mongata ho li-disk le marang-rang.
Liphoso tse atileng haholo ke ho se fihlellehe ha "block" e le 'ngoe ea data ka lebaka la ho hloleha kapa ho imeloa ha disk e le' ngoe. Na hoa khoneha ho fokotsa moroalo o feteletseng bakeng sa ho hlaphoheloa ha data tabeng ee (e tloaelehileng haholo)? Hoa fumaneha hore u ka: ho na le likhoutu tsa khaello ea mesebetsi ea LRC ka sepheo sena.
LRC (Local Reconstruction Codes) ke likhoutu tsa bofetoheli tse qapiloeng ke Microsoft hore li sebelisoe ho Windows Azure Storage. Mohopolo oa LRC o bonolo ka hohle kamoo ho ka khonehang: arola li-block tsa data ka lihlopha tse peli (kapa ho feta) 'me u bale karolo ea li-block tsa khoutu ea redundancy bakeng sa sehlopha ka seng ka thoko. Ebe li-block tsa khoutu tsa redundancy li tla baloa ho sebelisoa li-block tsa data (ho LRC li bitsoa global redundancy codes), 'me tse ling - li sebelisa e' ngoe ea lihlopha tse peli tsa li-block tsa data (li bitsoa codes tsa redundancy tsa lehae).
LRC e hlalosoa ka linomoro tse tharo: nrl, moo n e leng palo ea li-blocks tsa data, r ke palo ea li-block tsa lefats'e tsa redundancy codes, l ke palo ea li-blocks tsa libaka tsa redundancy. E le hore u bale data ha sebaka se le seng sa data se sa fumanehe, u lokela ho bala li-blocks tsa n / l feela - sena ke makhetlo a l ka tlase ho li-code tsa Reed-Solomon.
Ka mohlala, nahana ka morero oa LRC 6-2-2. X1–X6 — 6 li-blocks tsa data, P1, P2 — 2 global redundancy blocks, P3, P4 — 2 li-blocks tsa redundancy tsa lehae.
Redundancy code blocks P1, P2 e baloa ho sebelisoa li-blocks tsohle tsa data. Redundancy code block P3 - ho sebelisa data blocks X1-X3, redundancy code block P4 - ho sebelisa li-data blocks X4-X6.
Tse ling kaofela li etsoa ho LRC ka papiso le likhoutu tsa Reed-Solomon. Li-equation tsa ho bala mantsoe a redundancy code blocks e tla ba:
Ho khetha linomoro tsa alpha, beta, gamma, delta, maemo a 'maloa a tlameha ho finyelloa ho netefatsa monyetla oa ho hlaphoheloa ha data (ke hore, ho rarolla tsamaiso ea equation). U ka bala ho eketsehileng ka bona ho .
Hape ts'ebetsong, ts'ebetso ea XOR e sebelisetsoa ho bala likhoutu tsa redundancy tsa lehae P3, P4.
Ho latela liphetho tse 'maloa ho tsoa ho sistimi ea lipalo bakeng sa LRC:
- Ho khutlisa leha e le efe thibela ea data e le 'ngoe, ho lekane ho bala li-blocks tsa n / l (n / 1 mohlaleng oa rona).
- Haeba li-blocks tsa r + l li sa fumanehe, 'me li-blocks tsohle li kenyelelitsoe sehlopheng se le seng, joale data e ke ke ea tsosolosoa. Sena se bonolo ho se hlalosa ka mohlala. Tlohela li-blocks X1–X3 le P3 li se fumanehe: tsena ke li-blocks tsa r + l tse tsoang sehlopheng se le seng, 4 molemong oa rona. Joale re na le tsamaiso ea li-equations tse 3 le tse 4 tse sa tsejoeng tse ke keng tsa rarolloa.
- Maemong a mang kaofela a ho se fumanehe ha li-blocks tsa r + l (ha bonyane boloko bo le bong bo fumaneha ho tsoa ho sehlopha ka seng), data ho LRC e ka khutlisoa.
Kahoo, LRC e feta likhoutu tsa Reed-Solomon ho khutlisa data kamora liphoso tse le 'ngoe. Likhoutung tsa Reed-Solomon, ho khutlisa esita le boloko bo le bong ba data, o hloka ho sebelisa li-n blocks, 'me ho LRC, ho khutlisa boloko bo le bong ba data, ho lekane ho sebelisa li-blocks tsa n/l (n/2 mohlaleng oa rona). Ka lehlakoreng le leng, LRC e ka tlase ho likhoutu tsa Reed-Solomon ho latela palo e kholo ea liphoso tse lumelletsoeng. Mehlaleng e kaholimo, likhoutu tsa Reed-Solomon li ka khutlisa data bakeng sa liphoso leha e le life tse 4, 'me bakeng sa LRC ho na le mefuta e 2 ea liphoso tse 4 ha data e ke ke ea fumanoa.
Ntho ea bohlokoa le ho feta e ipapisitse le boemo bo ikhethileng, empa hangata chelete eo LRC e fanang ka eona e feta polokelo e sa tšepahaleng hanyane.
4. Likhoutu tse ling tsa ho fokotsa mosebetsi
Ntle le likhoutu tsa Reed-Solomon le LRC, ho na le likhoutu tse ling tse ngata tsa redundancy. Likhoutu tse fapaneng tsa ho fokotsa mosebetsi li sebelisa lipalo tse fapaneng. Likhoutu tse ling tsa redundancy ke tsena:
- Khoutu ea ho fokotsa mosebetsi ka XOR opareitara. Ts'ebetso ea XOR e etsoa ho li-blocks tsa data, 'me 1 block of redundancy codes e fumanoa, ke hore, leano la n + 1 (n li-blocks tsa data, khoutu ea 1 ea redundancy). E sebelisoa ho , moo li-blocks tsa data le redundancy codes li ngolloang ka potoloho ho li-disk tsohle tsa sehlopha.
- Algorithm e sa tloaelehang e ipapisitse le ts'ebetso ea XOR. E u lumella ho haha li-blocks tse 2 tsa likhoutu tsa redundancy, ke hore, morero oa n+2.
- STAR algorithm e ipapisitse le ts'ebetso ea XOR. E u lumella ho haha li-blocks tse 3 tsa likhoutu tsa redundancy, ke hore, leano la n+3.
- Likhoutu tsa piramide ke likhoutu tse ling tsa ho fokotsa mosebetsi ho tsoa ho Microsoft.
5. Sebelisa ho Yandex
Merero e mengata ea lits'ebetso tsa Yandex e sebelisa likhoutu tsa redundancy bakeng sa polokelo ea data e tšepahalang. Mehlala ke ena:
- MDS polokelo ea ntho e ka hare, eo ke ngotseng ka eona qalong ea sehlooho sena.
- - 'Mapa Fokotsa sistimi ea Yandex.
- (Yandex DataBase) - database e ncha eaSQL.
MDS e sebelisa LRC redundancy codes, 8-2-2 scheme. Lintlha tse nang le likhoutu tsa redundancy li ngotsoe ho li-disk tse fapaneng tsa 12 ho li-server tse fapaneng ho li-DC tse 3 tse fapaneng: li-server tse 4 ho DC ka 'ngoe. Bala haholoanyane ka sena ho .
YT e sebelisa bobeli ba Reed-Solomon codes (Scheme 6-3), tseo e bileng tsona tsa pele tsa ho kenya tšebetsong, le LRC redundancy codes (Scheme 12-2-2), LRC e le mokhoa o ratoang oa polokelo.
YDB e sebelisa likhoutu tse sa tloaelehang tse thehiloeng ho redundancy (Setšoantšo sa 4-2). Mabapi le likhoutu tsa khaello ea mesebetsi ho YDB e se e ntse e le .
Tšebeliso ea mekhoa e fapaneng ea khoutu ea ho fokotsa mosebetsi e bakoa ke litlhoko tse fapaneng tsa litsamaiso. Mohlala, ho MDS, data e bolokiloeng ho sebelisoa LRC e behiloe ho 3 DCs hang. Ke habohlokoa ho rona hore data e lule e le teng bakeng sa ho bala haeba 1 ea DCs leha e le efe e hlōleha, kahoo li-blocks li tlameha ho ajoa ho pholletsa le DC e le hore haeba DC leha e le efe e sa fumanehe, palo ea li-blocks tse sa fumaneheng ha e felle ho lumelloa. Lenaneong la 8-2-2, o ka beha li-blocks tse 4 ho DC e 'ngoe le e' ngoe, joale ha DC leha e le efe e tima, li-blocks tse 4 li ke ke tsa fumaneha, 'me data e ka baloa. Ho sa tsotellehe hore na morero ofe oo re o khethang ha o o beha ho 3 DCs, ho sa tsotellehe boemo leha e le bofe ho lokela ho ba le (r + l) / n > = 0,5, ke hore, redundancy ea polokelo e tla ba bonyane 50%.
Ho YT boemo bo fapane: sehlopha ka seng sa YT se fumaneha ka botlalo ho 1 DC (lihlopha tse fapaneng ho li-DC tse fapaneng), kahoo ha ho na thibelo e joalo. Lenaneo la 12-2-2 le fana ka 33% redundancy, ke hore, ho boloka data ho theko e tlaase, 'me e ka boela ea phela ho fihlela ho 4 ka nako e le' ngoe ho senyeha ha disk, joalo ka morero oa MDS.
Ho na le likarolo tse ling tse ngata tsa tšebeliso ea likhoutu tsa ho fokotsa ts'ebeliso ea lits'ebetso tsa polokelo ea data le lits'ebetso tsa ts'ebetso: li-nuances tsa ho hlaphoheloa ha data, phello ea ho hlaphoheloa nakong ea ts'ebetso ea lipotso, likarolo tsa ho rekota data, joalo-joalo Ke tla bua ka thoko ka lintlha tsena le tse ling. ea ts'ebeliso ea likhoutu tsa ho fokotsa mosebetsi ka ts'ebetsong, haeba sehlooho se tla khahla.
6. Lihokelo
- Letoto la lingoliloeng mabapi le likhoutu tsa Reed-Solomon le masimo a Galois:
Ba shebisisa thuto ea lipalo ka puo e fumanehang habonolo. - Sengoloa se tsoang ho Microsoft mabapi le LRC:
Karolo ea 2 e hlalosa teori ka bokhuts'oane, 'me e ntan'o buisana ka liphihlelo le LRC ka ts'ebetso. - Morero o sa tloaelehang:
- Sekema sa STAR:
- Likhoutu tsa piramite:
- Likhoutu tsa ho hloka mosebetsi ho MDS:
- Likhoutu tsa ho hloka mosebetsi ho YT:
- Likhoutu tsa tlhokeho ho YDB:
Source: www.habr.com