ProHoster > Blogs > Administrācija > AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

Šādi izskatās atlaiŔana

AtlaiÅ”anas kodi* tiek plaÅ”i izmantoti datorsistēmās, lai palielinātu datu uzglabāŔanas uzticamÄ«bu. Yandex tie tiek izmantoti daudzos projektos. Piemēram, izmantojot dublÄ“Å”anas kodus, nevis replikāciju mÅ«su iekŔējā objektu krātuvē, tiek ietaupÄ«ti miljoni, nezaudējot uzticamÄ«bu. Bet, neskatoties uz to plaÅ”o izmantoÅ”anu, skaidri apraksti par to, kā darbojas atlaiÅ”anas kodi, ir ļoti reti. Tie, kas vēlas saprast, saskaras ar aptuveni sekojoÅ”o (no Wikipedia):

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

Mani sauc Vadims, Yandex es izstrādāju iekŔējo objektu krātuves MDS. Å ajā rakstā vienkārÅ”os vārdos aprakstÄ«Å”u atlaiÅ”anas kodu (Reed-Solomon un LRC kodu) teorētiskos pamatus. Es jums pastāstÄ«Å”u, kā tas darbojas, bez sarežģītas matemātikas un retiem terminiem. Beigās es sniegÅ”u piemērus par atlaiÅ”anas kodu izmantoÅ”anu Yandex.

Vairākas matemātiskas detaļas es sÄ«kāk neapskatÄ«Å”u, bet sniegÅ”u saites tiem, kas vēlas ienirt dziļāk. AtzÄ«mÄ“Å”u arÄ« to, ka dažas matemātiskās definÄ«cijas var nebÅ«t stingras, jo raksts nav paredzēts matemātiÄ·iem, bet gan inženieriem, kuri vēlas izprast jautājuma bÅ«tÄ«bu.

* Angļu valodas literatÅ«rā redundances kodus bieži sauc par dzÄ“Å”anas kodiem.

1. AtlaiŔanas kodu būtība

Visu atlaiÅ”anas kodu bÅ«tÄ«ba ir ārkārtÄ«gi vienkārÅ”a: saglabājiet (vai pārsÅ«tiet) datus tā, lai tie netiktu zaudēti kļūdu gadÄ«jumā (diska kļūmes, datu pārsÅ«tÄ«Å”anas kļūdas utt.).

Lielākajā daļā* redundances kodu dati tiek sadalÄ«ti n datu blokos, kuriem tiek saskaitÄ«ti m atlaiÅ”anas kodu bloki, kā rezultātā kopā tiek iegÅ«ti n + m bloki. Redundances kodi ir izveidoti tā, lai n datu blokus varētu atgÅ«t, izmantojot tikai daļu no n + m blokiem. Tālāk mēs apsvērsim tikai bloku dublÄ“Å”anas kodus, tas ir, tos, kuros dati ir sadalÄ«ti blokos.

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

Lai atgÅ«tu visus n datu blokus, jums ir jābÅ«t vismaz n blokiem no n + m, jo ā€‹ā€‹jÅ«s nevarat iegÅ«t n blokus, ja ir tikai n-1 bloks (Å”ajā gadÄ«jumā jums vajadzētu izņemt 1 bloku no plāna gaiss"). Vai ar n nejauÅ”iem n + m blokiem pietiek, lai atgÅ«tu visus datus? Tas ir atkarÄ«gs no atlaiÅ”anas kodu veida, piemēram, RÄ«da-Solamona kodi ļauj atgÅ«t visus datus, izmantojot patvaļīgus n blokus, bet LRC redundances kodi ne vienmēr.

Datu glabāŔana

Datu uzglabāŔanas sistēmās, kā likums, katrs datu bloks un dublÄ“Å”anas koda bloks tiek ierakstÄ«ts atseviŔķā diskā. Pēc tam, ja patvaļīgs disks neizdodas, sākotnējos datus joprojām var atjaunot un nolasÄ«t. Datus var atgÅ«t pat tad, ja vienlaikus neizdodas vairāki diski.

Datu pārsūtīŔana

Redundances kodus var izmantot, lai droÅ”i pārsÅ«tÄ«tu datus neuzticamā tÄ«klā. PārsÅ«tÄ«tie dati tiek sadalÄ«ti blokos, un tiem tiek aprēķināti atlaiÅ”anas kodi. TÄ«klā tiek pārsÅ«tÄ«ti gan datu bloki, gan dublÄ“Å”anas kodu bloki. Ja kļūdas rodas patvaļīgos blokos (lÄ«dz noteiktam bloku skaitam), datus joprojām var pārsÅ«tÄ«t tÄ«klā bez kļūdām. Piemēram, RÄ«da-Zālamana kodus izmanto, lai pārraidÄ«tu datus pa optiskām sakaru lÄ«nijām un satelÄ«tu sakaros.

* Ir arÄ« tādi atlaiÅ”anas kodi, kuros dati nav sadalÄ«ti blokos, piemēram, Haminga kodi un CRC kodi, kurus plaÅ”i izmanto datu pārraidei Ethernet tÄ«klos. Tie ir kodi kļūdu laboÅ”anai, tie ir paredzēti kļūdu noteikÅ”anai, nevis to laboÅ”anai (Haminga kods pieļauj arÄ« daļēju kļūdu laboÅ”anu).

2. Rīda-Zālamana kodi

Reed-Solomon kodi ir viens no visplaŔāk izmantotajiem atlaiŔanas kodiem, kas tika izgudrots tālajā 1960. gados un pirmo reizi plaŔi izmantoti 1980. gados kompaktdisku masveida ražoŔanā.

Ir divi galvenie jautājumi, lai izprastu RÄ«da-Zālamana kodus: 1) kā izveidot atlaiÅ”anas kodu blokus; 2) kā atgÅ«t datus, izmantojot dublÄ“Å”anas kodu blokus. Meklēsim atbildes uz tiem.
VienkārŔības labad mēs turpmāk pieņemsim, ka n = 6 un m = 4. Citas shēmas tiek aplÅ«kotas pēc analoÄ£ijas.

Kā izveidot dublÄ“Å”anas kodu blokus

Katrs atlaiÅ”anas kodu bloks tiek skaitÄ«ts neatkarÄ«gi no pārējiem. Katra bloka skaitÄ«Å”anai tiek izmantoti visi n datu bloki. Zemāk redzamajā diagrammā X1-X6 ir datu bloki, P1-P4 ir redundances koda bloki.

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

Visiem datu blokiem jābÅ«t vienāda izmēra, un lÄ«dzināŔanai var izmantot nulles bitus. IegÅ«tie redundances koda bloki bÅ«s tāda paÅ”a izmēra kā datu bloki. Visi datu bloki ir sadalÄ«ti vārdos (piemēram, 16 biti). Pieņemsim, ka mēs sadalām datu blokus k vārdos. Tad arÄ« visi atlaiÅ”anas kodu bloki tiks sadalÄ«ti k vārdos.

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

Lai saskaitÄ«tu katra liekuma bloka i-to vārdu, tiks izmantoti visu datu bloku i-tie vārdi. Tos aprēķina pēc Ŕādas formulas:

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

Å eit vērtÄ«bas x ir datu bloku vārdi, p ir atlaiÅ”anas kodu bloku vārdi, visi alfa, beta, gamma un delta ir Ä«paÅ”i atlasÄ«ti skaitļi, kas ir vienādi visiem i. Uzreiz jāsaka, ka visas Ŕīs vērtÄ«bas nav parastie skaitļi, bet gan Galois lauka elementi; darbÄ«bas +, -, *, / nav mums visiem pazÄ«stamas darbÄ«bas, bet gan Ä«paÅ”as darbÄ«bas, kas ieviestas ar Galois elementiem. lauks.

Kāpēc ir vajadzīgi Galois lauki?

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

Å Ä·iet, ka viss ir vienkārÅ”i: mēs sadalām datus blokos, blokus vārdos, izmantojot datu bloku vārdus, mēs saskaitām atlaiÅ”anas kodu bloku vārdus - mēs iegÅ«stam dublÄ“Å”anas kodu blokus. Kopumā tas darbojas Ŕādi, bet velns slēpjas detaļās:

  1. Kā minēts iepriekÅ”, vārda lielums ir fiksēts, mÅ«su piemērā 16 biti. IepriekÅ” minētās formulas RÄ«da-Zālamana kodiem ir tādas, ka, izmantojot parastus veselus skaitļus, p aprēķina rezultāts var nebÅ«t attēlojams, izmantojot derÄ«ga lieluma vārdu.
  2. Atkopjot datus, iepriekÅ” minētās formulas tiks uzskatÄ«tas par vienādojumu sistēmu, kas jāatrisina, lai datus atgÅ«tu. Risinājuma procesā var bÅ«t nepiecieÅ”ams dalÄ«t veselus skaitļus savā starpā, kā rezultātā tiek iegÅ«ts reāls skaitlis, ko nevar precÄ«zi attēlot datora atmiņā.

Å Ä«s problēmas neļauj izmantot veselus skaitļus RÄ«da-Zālamana kodiem. Problēmas risinājums ir oriÄ£ināls, to var raksturot Ŕādi: izdomāsim Ä«paÅ”us skaitļus, kurus var attēlot, izmantojot vajadzÄ«gā garuma vārdus (piemēram, 16 biti), un visu darbÄ«bu veikÅ”anas rezultātu, uz kuriem (papildinājums , atņemÅ”ana, reizināŔana, dalÄ«Å”ana) tiks parādÄ«ti arÄ« datora atmiņā, izmantojot vajadzÄ«gā garuma vārdus.

Šādus ā€œÄ«paÅ”usā€ skaitļus matemātika ir pētÄ«jusi jau ilgu laiku, tos sauc par laukiem. Lauks ir elementu kopa ar tiem definētām saskaitÄ«Å”anas, atņemÅ”anas, reizināŔanas un dalÄ«Å”anas operācijām.

Galois* lauki ir lauki, kuriem ir unikāls katras darbÄ«bas rezultāts (+, -, *, /) jebkuriem diviem lauka elementiem. Galois laukus var konstruēt skaitļiem, kas ir pakāpju 2: 2, 4, 8, 16 utt. (faktiski jebkura pirmskaitļa p pakāpes, bet praksē mÅ«s interesē tikai 2 pakāpes). Piemēram, 16 bitu vārdiem Å”is ir lauks, kurā ir 65 536 elementi, no kuriem katram pārim var atrast jebkuras darbÄ«bas rezultātu (+, -, *, /). IepriekÅ” minēto vienādojumu vērtÄ«bas x, p, alfa, beta, gamma, delta tiks uzskatÄ«tas par Galois lauka elementiem aprēķinos.

Tādējādi mums ir vienādojumu sistēma, ar kuru mēs varam konstruēt atlaiÅ”anas kodu blokus, uzrakstot atbilstoÅ”u datorprogrammu. Izmantojot to paÅ”u vienādojumu sistēmu, varat veikt datu atkopÅ”anu.

* Šī nav stingra definīcija, bet drīzāk apraksts.

Kā atgūt datus

Restaurācija ir nepiecieÅ”ama, ja trÅ«kst dažu n + m bloku. Tie var bÅ«t gan datu bloki, gan atlaiÅ”anas kodu bloki. Datu bloku un/vai atlaiÅ”anas koda bloku neesamÄ«ba nozÄ«mēs, ka iepriekÅ” minētajos vienādojumos atbilstoÅ”ie x un/vai p mainÄ«gie nav zināmi.

RÄ«da-Zālamana kodu vienādojumus var aplÅ«kot kā vienādojumu sistēmu, kurā visas alfa, beta, gamma, delta vērtÄ«bas ir konstantes, visi x un p, kas atbilst pieejamajiem blokiem, ir zināmi mainÄ«gie, bet atlikuÅ”ie x un p nav zināmi.

Piemēram, lai datu bloki 1, 2, 3 un redundances koda bloks 2 nebÅ«tu pieejami, tad i-ajai vārdu grupai bÅ«s Ŕāda vienādojumu sistēma (nezināmie ir atzÄ«mēti ar sarkanu):

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

Mums ir 4 vienādojumu sistēma ar 4 nezināmajiem, kas nozīmē, ka mēs varam to atrisināt un atjaunot datus!

No Ŕīs vienādojumu sistēmas izriet vairāki secinājumi par datu atkopÅ”anu RÄ«da-Zālamana kodiem (n datu bloki, m redundances kodu bloki):

  • Datus var atgÅ«t, ja tiek zaudēti m bloki vai mazāk. Ja tiek zaudēti m+1 vai vairāk bloki, datus nevar atjaunot: nav iespējams atrisināt m vienādojumu sistēmu ar m + 1 nezināmajiem.
  • Lai atgÅ«tu kaut vienu datu bloku, jums ir jāizmanto jebkurÅ” n no atlikuÅ”ajiem blokiem, un jÅ«s varat izmantot jebkuru no atlaiÅ”anas kodiem.

Kas vēl jums jāzina

IepriekÅ” minētajā aprakstā es izvairos no vairākiem svarÄ«giem jautājumiem, kuru izskatÄ«Å”anai ir nepiecieÅ”ams dziļāks ienirt matemātikā. Jo Ä«paÅ”i es neko nesaku par sekojoÅ”o:

  • RÄ«da-Zālamana kodu vienādojumu sistēmai ir jābÅ«t (unikālam) risinājumam jebkurai nezināmo kombinācijai (ne vairāk kā m nezināmo). Pamatojoties uz Å”o prasÄ«bu, tiek atlasÄ«tas alfa, beta, gamma un delta vērtÄ«bas.
  • Vienādojumu sistēmu jāspēj automātiski izveidot (atkarÄ«bā no tā, kuri bloki nav pieejami) un atrisināt.
  • Mums ir jāizveido Galois lauks: konkrētam vārda izmēram jāspēj atrast jebkuras darbÄ«bas rezultātu (+, -, *, /) jebkuriem diviem elementiem.

Raksta beigās ir atsauces uz literatūru par Ŕiem svarīgajiem jautājumiem.

n un m izvēle

Kā praksē izvēlēties n un m? Praksē datu uzglabāŔanas sistēmās, lai ietaupÄ«tu vietu, tiek izmantoti atlaiÅ”anas kodi, tāpēc m vienmēr izvēlas mazāku par n. To Ä«paŔās vērtÄ«bas ir atkarÄ«gas no vairākiem faktoriem, tostarp:

  • Datu uzglabāŔanas uzticamÄ«ba. Jo lielāks m, jo ā€‹ā€‹lielāks ir diska bojājumu skaits, ko var pārdzÄ«vot, tas ir, jo lielāka ir uzticamÄ«ba.
  • Lieka krātuve. Jo augstāka ir m/n attiecÄ«ba, jo lielāka bÅ«s krātuves dublÄ“Å”ana, un sistēma bÅ«s dārgāka.
  • PieprasÄ«t apstrādes laiku. Jo lielāka summa n + m, jo ā€‹ā€‹ilgāks bÅ«s atbildes laiks uz pieprasÄ«jumiem. Tā kā datu lasÄ«Å”anai (atkopÅ”anas laikā) ir jānolasa n bloki, kas saglabāti n dažādos diskos, lasÄ«Å”anas laiku noteiks lēnākais disks.

Turklāt datu glabāŔana vairākos DC uzliek papildu ierobežojumus n un m izvēlei: ja ir izslēgts 1 DC, datiem joprojām jābÅ«t pieejamiem nolasÄ«Å”anai. Piemēram, saglabājot datus 3 DC, ir jāievēro Ŕāds nosacÄ«jums: m >= n/2, pretējā gadÄ«jumā var rasties situācija, ka dati nav pieejami nolasÄ«Å”anai, kad ir izslēgts 1 DC.

3. LRC - Vietējie rekonstrukcijas kodeksi

Lai atgÅ«tu datus, izmantojot Reed-Solomon kodus, jums ir jāizmanto n patvaļīgi datu bloki. Tas ir ļoti bÅ«tisks trÅ«kums sadalÄ«tajām datu glabāŔanas sistēmām, jo, lai atjaunotu datus vienā bojātā diskā, jums bÅ«s jālasa dati no lielākās daļas pārējo, radot lielu papildu slodzi diskiem un tÄ«klam.

Visbiežāk sastopamās kļūdas ir viena datu bloka nepieejamÄ«ba viena diska kļūmes vai pārslodzes dēļ. Vai Å”ajā (visbiežāk) gadÄ«jumā ir iespējams kaut kā samazināt lieko slodzi datu atkopÅ”anai? Izrādās, ka var: ir speciāli Å”im nolÅ«kam paredzēti LRC atlaiÅ”anas kodi.

LRC (vietējie rekonstrukcijas kodi) ir atlaiÅ”anas kodi, ko Microsoft izgudroja izmantoÅ”anai Windows Azure krātuvē. LRC ideja ir pēc iespējas vienkārŔāka: sadaliet visus datu blokus divās (vai vairākās) grupās un nolasiet daļu no atlaiÅ”anas koda blokiem katrai grupai atseviŔķi. Pēc tam daži atlaiÅ”anas koda bloki tiks skaitÄ«ti, izmantojot visus datu blokus (LRC tos sauc par globālajiem redundances kodiem), bet daži - izmantojot vienu no divām datu bloku grupām (tos sauc par vietējiem atlaiÅ”anas kodiem).

LRC apzÄ«mē ar trim cipariem: nrl, kur n ir datu bloku skaits, r ir globālās atlaiÅ”anas koda bloku skaits, l ir lokālo redundances kodu bloku skaits. Lai nolasÄ«tu datus, kad viens datu bloks nav pieejams, jālasa tikai n/l bloki ā€“ tas ir l reizes mazāk nekā RÄ«da-Zālamana kodos.

Piemēram, apsveriet LRC 6-2-2 shēmu. X1ā€“X6 ā€” 6 datu bloki, P1, P2 ā€” 2 globālās dublÄ“Å”anas bloki, P3, P4 ā€” 2 lokālās dublÄ“Å”anas bloki.

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

Redundances koda bloki P1, P2 tiek skaitīti, izmantojot visus datu blokus. Redundances koda bloks P3 - izmantojot datu blokus X1-X3, atlaiŔanas koda bloks P4 - izmantojot datu blokus X4-X6.

Pārējais tiek darÄ«ts LRC pēc analoÄ£ijas ar Reed-Solomon kodiem. AtlaiÅ”anas kodu bloku vārdu skaitÄ«Å”anas vienādojumi bÅ«s Ŕādi:

AtlaiÅ”anas kodi: vienkārÅ”iem vārdiem sakot, kā droÅ”i un lēti uzglabāt datus

Lai atlasÄ«tu skaitļus alfa, beta, gamma, delta, ir jāizpilda vairāki nosacÄ«jumi, kas garantē datu atkopÅ”anas iespēju (tas ir, vienādojumu sistēmas atrisināŔanu). Vairāk par tiem varat lasÄ«t sadaļā raksts.
ArÄ« praksē XOR operācija tiek izmantota, lai aprēķinātu lokālos atlaiÅ”anas kodus P3, P4.

No LRC vienādojumu sistēmas izriet vairāki secinājumi:

  • Lai atgÅ«tu jebkuru 1 datu bloku, pietiek nolasÄ«t n/l blokus (mÅ«su piemērā n/2).
  • Ja r + l bloki nav pieejami un visi bloki ir iekļauti vienā grupā, datus nevar atjaunot. To ir viegli izskaidrot ar piemēru. Ä»aujiet, lai bloki X1ā€“X3 un P3 nebÅ«tu pieejami: tie ir r + l bloki no vienas grupas, mÅ«su gadÄ«jumā ā€” 4. Tad mums ir 3 vienādojumu sistēma ar 4 nezināmajiem, kurus nevar atrisināt.
  • Visos citos r + l bloku nepieejamÄ«bas gadÄ«jumos (kad ir pieejams vismaz viens bloks no katras grupas), datus LRC var atjaunot.

Tādējādi LRC pārspēj Reed-Solomon kodus datu atgÅ«Å”anā pēc atseviŔķām kļūdām. Reed-Solomon kodos, lai atgÅ«tu kaut vienu datu bloku, ir jāizmanto n bloki, savukārt LRC, lai atgÅ«tu vienu datu bloku, pietiek ar n/l blokiem (mÅ«su piemērā n/2). No otras puses, LRC ir zemāks par Reed-Solomon kodiem maksimālā pieļaujamo kļūdu skaita ziņā. IepriekÅ” minētajos piemēros RÄ«da-Solamona kodi var atgÅ«t datus par jebkurām 4 kļūdām, savukārt LRC gadÄ«jumā ir 2 4 kļūdu kombinācijas, kad datus nevar atgÅ«t.

SvarÄ«gākais ir atkarÄ«gs no konkrētās situācijas, taču nereti ietaupÄ«jumi pārslodzē, ko nodroÅ”ina LRC, atsver nedaudz mazāk uzticamu uzglabāŔanu.

4. Citi atlaiŔanas kodi

Bez Reed-Solomon un LRC kodiem ir arī daudzi citi atlaiŔanas kodi. Dažādi atlaiŔanas kodi izmanto dažādu matemātiku. Šeit ir daži citi atlaiŔanas kodi:

  • Redundances kods, izmantojot operatoru XOR. XOR operācija tiek veikta uz n datu blokiem, un tiek iegÅ«ts 1 dublÄ“Å”anas kodu bloks, tas ir, n+1 shēma (n datu bloki, 1 redundances kods). Lietots in RAID 5, kur datu bloki un dublÄ“Å”anas kodi tiek cikliski ierakstÄ«ti visos masÄ«va diskos.
  • Pāra nepāra algoritms, kas balstÄ«ts uz XOR darbÄ«bu. Ä»auj izveidot 2 atlaiÅ”anas kodu blokus, tas ir, n+2 shēmu.
  • STAR algoritms, kas balstÄ«ts uz XOR darbÄ«bu. Ä»auj izveidot 3 atlaiÅ”anas kodu blokus, tas ir, n+3 shēmu.
  • PiramÄ«du kodi ir vēl viens Microsoft atlaiÅ”anas kods.

5. Izmantojiet Yandex

Vairāki Yandex infrastruktÅ«ras projekti izmanto atlaiÅ”anas kodus uzticamai datu glabāŔanai. Å eit ir daži piemēri:

  • MDS iekŔējā objektu krātuve, par kuru rakstÄ«ju raksta sākumā.
  • YT ā€” Yandex sistēma MapReduce.
  • YDB (Yandex DataBase) - newSQL izplatÄ«ta datu bāze.

MDS izmanto LRC atlaiÅ”anas kodus, 8-2-2 shēmu. Dati ar dublÄ“Å”anas kodiem tiek ierakstÄ«ti 12 dažādos diskos dažādos serveros 3 dažādos DC: 4 serveri katrā DC. Vairāk par to lasiet sadaļā raksts.

YT izmanto gan Reed-Solomon kodus (shēma 6-3), kas tika ieviesti pirmie, un LRC atlaiÅ”anas kodus (shēma 12-2-2), un LRC ir vēlamā uzglabāŔanas metode.

YDB izmanto pāra un nepāra atlaiÅ”anas kodus (4-2. attēls). Par atlaiÅ”anas kodiem jau YDB stāstÄ«ja Highload.

Dažādu atlaiÅ”anas kodu shēmu izmantoÅ”ana ir saistÄ«ta ar dažādām prasÄ«bām sistēmām. Piemēram, MDS dati, kas tiek glabāti, izmantojot LRC, tiek ievietoti 3 lÄ«dzstrāvas blokos vienlaikus. Mums ir svarÄ«gi, lai dati paliktu pieejami lasÄ«Å”anai, ja 1 no DC neizdodas, tāpēc bloki ir jāsadala starp DC tā, lai gadÄ«jumā, ja kāds lÄ«dzstrāvas bloks nav pieejams, nepieejamo bloku skaits bÅ«tu ne vairāk kā pieļaujams. Shēmā 8-2-2 jÅ«s varat ievietot 4 blokus katrā DC, tad, kad jebkurÅ” DC ir izslēgts, 4 bloki nebÅ«s pieejami, un datus varēs nolasÄ«t. NeatkarÄ«gi no tā, kādu shēmu mēs izvēlamies, ievietojot to 3 DC, jebkurā gadÄ«jumā jābÅ«t (r + l) / n >= 0,5, tas ir, krātuves dublÄ“Å”ana bÅ«s vismaz 50%.

YT situācija ir atŔķirÄ«ga: katrs YT klasteris pilnÄ«bā atrodas 1 DC (dažādas kopas dažādos DC), tāpēc Ŕādu ierobežojumu nav. Shēma 12-2-2 nodroÅ”ina 33% dublÄ“Å”anu, tas ir, datu glabāŔana ir lētāka, un tā var arÄ« izturēt lÄ«dz pat 4 vienlaicÄ«giem diska pārtraukumiem, tāpat kā MDS shēma.

AtlaiÅ”anas kodu izmantoÅ”anai datu uzglabāŔanas un apstrādes sistēmās ir daudz vairāk iespēju: datu atkopÅ”anas nianses, atkopÅ”anas ietekme uz vaicājuma izpildes laiku, datu ierakstÄ«Å”anas iespējas utt. Par Ŕīm un citām funkcijām es runāŔu atseviŔķi. par atlaiÅ”anas kodu izmantoÅ”anu praksē, ja tēma bÅ«s interesanta.

6. Saites

  1. Rakstu sērija par Rīda-Zālamana kodiem un Galois laukiem: https://habr.com/ru/company/yadro/blog/336286/
    https://habr.com/ru/company/yadro/blog/341506/
    Viņi dziļāk aplūko matemātiku pieejamā valodā.
  2. Microsoft raksts par LRC: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/LRC12-cheng20webpage.pdf
    2. sadaļā īsi izskaidrota teorija un pēc tam apspriesta pieredze ar LRC praksē.
  3. Pāra un nepāra shēma: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
  4. ZVAIGŽŅU shēma: https://www.usenix.org/legacy/event/fast05/tech/full_papers/huang/huang.pdf
  5. Piramīdas kodi: https://www.microsoft.com/en-us/research/publication/pyramid-codes-flexible-schemes-to-trade-space-for-access-efficiency-in-reliable-data-storage-systems/
  6. AtlaiŔanas kodi MDS: https://habr.com/ru/company/yandex/blog/311806
  7. AtlaiŔanas kodi pakalpojumā YT: https://habr.com/ru/company/yandex/blog/311104/
  8. AtlaiŔanas kodi YDB: https://www.youtube.com/watch?v=dCpfGJ35kK8

Avots: www.habr.com

Pievieno komentāru