Wannan shine abin da redundancy yayi kama
Lambobin sakewa * ana amfani da su sosai a cikin tsarin kwamfuta don ƙara amincin ajiyar bayanai. A cikin Yandex ana amfani da su a cikin ayyukan da yawa. Misali, yin amfani da lambobin sake maimaitawa maimakon yin kwafi a cikin ma'ajin kayan mu na ciki yana ceton miliyoyi ba tare da sadaukar da dogaro ba. Amma duk da yawan amfani da su, bayyanannun kwatancen yadda lambobin sakewa ke aiki ba kasafai ba ne. Wadanda suke son fahimta suna fuskantar kamar haka (daga ):
Sunana Vadim, a Yandex Ina haɓaka kayan ajiya na ciki MDS. A cikin wannan labarin, zan bayyana a cikin kalmomi masu sauƙi tushen tushe na ka'idojin sakewa (lambobin Reed-Solomon da LRC). Zan gaya muku yadda yake aiki, ba tare da haɗaɗɗiyar lissafi da kalmomin da ba kasafai ba. A ƙarshe zan ba da misalai na amfani da lambobin sakewa a Yandex.
Ba zan yi la'akari da adadin bayanan lissafi daki-daki ba, amma zan samar da hanyoyin haɗi ga waɗanda ke son nutsewa cikin zurfi. Zan kuma lura cewa wasu ma’anoni na lissafin ƙila ba za su kasance masu tsauri ba, tunda labarin ba a yi nufin masana lissafi ba ne, amma ga injiniyoyi waɗanda ke son fahimtar ainihin batun.
* A cikin wallafe-wallafen Turanci, yawancin lambobin sakewa ana kiran su lambobin gogewa.
1. Asalin lambobin sakewa
Ma'anar duk lambobin sakewa abu ne mai sauƙi: adana (ko watsa) bayanai don kada ya ɓace lokacin da kurakurai suka faru (rashin faifai, kurakuran canja wurin bayanai, da sauransu).
A mafi yawan * redunancy codes, an raba bayanan zuwa n data blocks, wanda m tubalan na redundancy codes ake ƙidaya, yana haifar da jimlar n + m tubalan. Ana gina lambobin sakewa ta hanyar da za a iya gano tubalan bayanai ta hanyar amfani da wani yanki na n + m tubalan kawai. Na gaba, za mu yi la'akari ne kawai toshe lambobin sakewa, wato, waɗanda aka raba bayanan zuwa tubalan.
Don dawo da duk n tubalan na bayanai, kuna buƙatar samun aƙalla n na n + m tubalan, tunda ba za ku iya samun n blocks ta hanyar samun n-1 kawai ba (a wannan yanayin, dole ne ku ɗauki 1 block “daga bakin ciki). iska"). Shin n tubalan bazuwar n + m sun isa su dawo da duk bayanan? Wannan ya dogara da nau'in lambobin sakewa, alal misali, lambobin Reed-Solomon suna ba ku damar dawo da duk bayanai ta amfani da tubalan na sabani, amma lambobin redundancy na LRC ba koyaushe ba ne.
Adana bayanai
A cikin tsarin ajiyar bayanai, a matsayin mai mulkin, kowane ɗayan bayanan toshewa da tubalan lambar sakewa ana rubuta su zuwa faifai daban. Bayan haka, idan diski na sabani ya gaza, ana iya dawo da ainihin bayanan kuma a karanta. Ana iya dawo da bayanai ko da diski da yawa sun gaza a lokaci guda.
Canja wurin bayanai
Ana iya amfani da lambobin sakewa don dogaro da kai da bayanai akan hanyar sadarwa mara inganci. An rarraba bayanan da aka watsa zuwa tubalan, kuma ana ƙididdige lambobin sakewa don su. Dukansu tubalan bayanai da tubalan lambar sakewa ana watsa su akan hanyar sadarwa. Idan kurakurai sun faru a cikin tubalan na sabani (har zuwa takamaiman adadin tubalan), ana iya watsa bayanai akan hanyar sadarwar ba tare da kuskure ba. Lambobin Reed-Solomon, alal misali, ana amfani da su don watsa bayanai akan layukan sadarwa na gani da kuma cikin sadarwar tauraron dan adam.
* Har ila yau, akwai lambobin sake maimaitawa waɗanda ba a rarraba bayanan zuwa tubalan, kamar lambobin Hamming da lambobin CRC, waɗanda ake amfani da su sosai don watsa bayanai a cikin hanyoyin sadarwar Ethernet. Waɗannan lambobi ne don gyara kurakurai, an ƙirƙira su don gano kurakurai, kuma ba don gyara su ba (lambar Hamming kuma tana ba da damar gyara kurakurai).
2. Lambobin Reed-Solomon
Lambobin Reed-Solomon ɗaya ne daga cikin lambobin sakewa da aka fi amfani da su, waɗanda aka ƙirƙira a cikin 1960s kuma an fara amfani da su sosai a cikin 1980s don yawan samar da ƙaramin fayafai.
Akwai mahimman tambayoyi guda biyu don fahimtar lambobin Reed-Solomon: 1) yadda ake ƙirƙirar tubalan lambobin sakewa; 2) yadda ake mai da bayanai ta amfani da redundancy code blocks. Bari mu nemo amsoshinsu.
Don sauƙi, za mu ƙara ɗauka cewa n=6 da m=4. Sauran tsare-tsare ana la'akari da su ta misali.
Yadda ake ƙirƙirar blocks code redundancy
Kowane tubalan lambobin sakewa ana ƙidaya su ba tare da wasu ba. Ana amfani da duk abubuwan toshewar bayanai don ƙidaya kowane toshe. A cikin zanen da ke ƙasa, X1-X6 su ne tubalan bayanai, P1-P4 sune tubalan lambar sakewa.
Duk tubalan bayanai dole ne su kasance girmansu ɗaya, kuma za a iya amfani da sifiri don daidaitawa. Sakamakon tubalan lambar sakewa zai kasance girman daidai da tubalan bayanai. An raba duk katangar bayanai zuwa kalmomi (misali, 16 ragowa). Bari mu ce mun raba bayanan tubalan zuwa kalmomin k. Sa'an nan kuma duk tubalan na redundancy code kuma za a raba zuwa k kalmomi.
Don ƙidaya kalmar i-th na kowane shingen sakewa, za a yi amfani da kalmomin i-th na duk bayanan tubalan. Za a lissafta su bisa ga tsari mai zuwa:
Anan darajar x sune kalmomin tubalan bayanai, p sune kalmomin tubalan code, duk alpha, beta, gamma da delta an zaɓa musamman lambobi waɗanda suke iri ɗaya ga duka i. Dole ne a faɗi nan da nan cewa duk waɗannan dabi'un ba lambobi ba ne, amma abubuwa na filin Galois; ayyukan +, -, *, / ba ayyukan da muka saba da su ba ne, amma ayyuka na musamman da aka gabatar akan abubuwan Galois. filin.
Me yasa ake buƙatar filayen Galois?
Zai yi kama da cewa komai yana da sauƙi: muna raba bayanan zuwa tubalan, tubalan cikin kalmomi, ta yin amfani da kalmomin tubalan bayanai muna ƙidaya kalmomin tubalan code na redundancy - muna samun tubalan lambar sakewa. Gabaɗaya wannan shine yadda yake aiki, amma shaidan yana cikin cikakkun bayanai:
- Kamar yadda aka fada a sama, girman kalmar yana daidaitawa, a cikin misalinmu 16 ragowa. Ƙididdigar da ke sama don lambobin Reed-Solomon irin waɗannan ne yayin amfani da integers na yau da kullun, sakamakon ƙididdige p ƙila ba za a iya wakilta ta amfani da kalma mai inganci ba.
- Lokacin dawo da bayanai, za a yi la'akari da hanyoyin da ke sama a matsayin tsarin daidaitawa wanda dole ne a warware don dawo da bayanan. A yayin aiwatar da mafita, yana iya zama dole a raba lambobi da juna, yana haifar da adadi na gaske wanda ba za a iya wakilta daidai a ƙwaƙwalwar kwamfuta ba.
Waɗannan matsalolin sun hana amfani da lamba don lambobin Reed-Solomon. Maganin matsalar asali ce, ana iya siffanta ta kamar haka: bari mu fito da lambobi na musamman waɗanda za a iya wakilta ta amfani da kalmomin tsayin da ake buƙata (misali, 16 bits), da sakamakon aiwatar da duk ayyukan da aka yi a kansu (ƙari. , raguwa, ninkawa, rarrabawa) kuma za a gabatar da su a cikin ƙwaƙwalwar kwamfuta ta amfani da kalmomin tsayin da ake buƙata.
Irin waɗannan lambobi "na musamman" sun yi nazarin lissafi na dogon lokaci, ana kiran su filayen. Filin saitin abubuwa ne tare da ayyukan ƙari, ragi, ninkawa da rarraba da aka ayyana musu.
Filayen Galois* filayen ne waɗanda ke da sakamako na musamman na kowane aiki (+, -, *, /) ga kowane abu biyu na filin. Ana iya gina filayen Galois don lambobi waɗanda ke da iko na 2: 2, 4, 8, 16, da sauransu. Misali, don kalmomin 2-bit, wannan fili ne mai ɗauke da abubuwa 16, ga kowane nau'in biyu wanda zaku iya samun sakamakon kowane aiki (+, -, *, /). Ƙimar x, p, alpha, beta, gamma, delta daga ma'auni na sama za a yi la'akari da abubuwa na filin Galois don lissafi.
Don haka, muna da tsarin daidaitawa wanda da shi za mu iya gina tubalan lambobi na sakewa ta hanyar rubuta shirin kwamfuta mai dacewa. Yin amfani da wannan tsarin na daidaitawa, zaku iya dawo da bayanai.
* Wannan ba ƙaƙƙarfan ma'anar ba ne, amma dai bayanin.
Yadda ake dawo da bayanai
Ana buƙatar sabuntawa lokacin da wasu tubalan n + m suka ɓace. Waɗannan na iya zama duka tubalan bayanai da tubalan lambar sakewa. Rashin tubalan bayanai da/ko tubalan lambar sakewa zai nuna cewa ba a san masu canjin x da/ko p a cikin ma'auni na sama ba.
Ana iya kallon ma'auni don lambobin Reed-Solomon a matsayin tsarin daidaitawa wanda duk alpha, beta, gamma, delta dabi'u ne akai-akai, duk x da p masu dacewa da tubalan da ake da su sanannu ne masu canji, sauran x da p. ba a sani ba.
Misali, bari bayanan blocks 1, 2, 3 da redundancy code block 2 su kasance ba su samuwa, to ga rukunin kalmomi na i-th za a sami tsarin ma'auni mai zuwa (wanda ba a sani ba ana yiwa alama ja):
Muna da tsarin 4 equations tare da 4 unknowns, wanda ke nufin za mu iya warware shi da mayar da bayanai!
Daga wannan tsarin lissafin ƙididdiga masu yawa sun biyo baya game da dawo da bayanai don lambobin Reed-Solomon (n data blocks, m redundancy code blocks):
- Ana iya dawo da bayanai idan an rasa wasu tubalan m ko kaɗan. Idan m +1 ko fiye tubalan sun ɓace, ba za a iya dawo da bayanan ba: ba shi yiwuwa a warware tsarin tsarin m tare da m + 1 wanda ba a sani ba.
- Don dawo da toshewar bayanai ko da guda ɗaya, kuna buƙatar amfani da kowane n na ragowar tubalan, kuma kuna iya amfani da kowane lambobin sakewa.
Me kuma kuke buƙatar sani
A cikin bayanin da ke sama, na guje wa wasu batutuwa masu mahimmanci waɗanda ke buƙatar zurfafa zurfafa cikin ilimin lissafi don yin la'akari. Musamman ma, ba na cewa komai game da wadannan:
- Dole ne tsarin daidaita lambobin Reed-Solomon ya sami mafita (na musamman) ga kowane haɗin abubuwan da ba a sani ba (ba fiye da m sani ba). Dangane da wannan buƙatu, an zaɓi ƙimar alpha, beta, gamma da delta.
- Dole ne a iya gina tsarin ma'auni ta atomatik (dangane da waɗanne tubalan da ba a samu ba) kuma a warware su.
- Muna buƙatar gina filin Galois: don girman kalmar da aka ba da, iya samun sakamakon kowane aiki (+, -, *, /) don kowane abubuwa biyu.
A ƙarshen labarin akwai magana game da wallafe-wallafe kan waɗannan batutuwa masu mahimmanci.
Zaɓin n da m
Yadda za a zabi n da m a aikace? A aikace, a cikin tsarin ajiyar bayanai, ana amfani da lambobin sakewa don adana sarari, don haka m ana zabar ƙasa da n. Ƙimarsu ta musamman ta dogara da abubuwa da yawa, ciki har da:
- Amincewar ajiyar bayanai. Mafi girma m, mafi girma yawan gazawar faifai da za a iya tsira, wato, mafi girma da aminci.
- Mai yawa ajiya. Mafi girma da m / n rabo, da mafi girma da ajiya redundancy zai zama, kuma mafi tsada tsarin zai zama.
- Nemi lokacin sarrafawa. Girman jimlar n + m, tsawon lokacin amsa buƙatun zai kasance. Tunda karanta bayanan (lokacin dawowa) yana buƙatar karanta n tubalan da aka adana akan diski daban-daban, lokacin karantawa za a ƙayyade shi ta faifai mafi hankali.
Bugu da ƙari, adana bayanai a cikin DCs da yawa yana ƙaddamar da ƙarin ƙuntatawa akan zaɓi na n da m: idan 1 DC aka kashe, dole ne har yanzu bayanan su kasance don karantawa. Misali, lokacin adana bayanai a cikin 3 DCs, dole ne a cika yanayin da ke gaba: m>= n/2, in ba haka ba za a iya samun yanayin da ba a samun bayanan don karantawa lokacin da aka kashe 1 DC.
3. LRC - Lambobin Gyaran Gida
Don dawo da bayanai ta amfani da lambobin Reed-Solomon, dole ne ku yi amfani da tubalan bayanan sabani. Wannan babban hasara ne ga tsarin adana bayanai da aka rarraba, domin don dawo da bayanai akan faifan diski guda ɗaya, dole ne ku karanta bayanai daga yawancin sauran, ƙirƙirar ƙarin nauyi akan diski da hanyar sadarwa.
Kurakurai da suka fi yawa sune rashin isa ga toshe ɗaya na bayanai saboda gazawa ko fiye da faifai ɗaya. Shin zai yiwu a ko ta yaya rage wuce haddi lodi ga data dawo da a cikin wannan (mafi na kowa) harka? Ya zama cewa zaku iya: akwai lambobin sakewa na LRC musamman don wannan dalili.
LRC (Lambobin Sake Gina Gida) lambobin sake ginawa ne da Microsoft ya ƙirƙira don amfani a Ma'ajiyar Windows Azure. Tunanin LRC yana da sauƙi kamar yadda zai yiwu: raba duk bayanan tubalan zuwa ƙungiyoyi biyu (ko fiye) kuma karanta wani ɓangare na tubalan lambar sakewa ga kowane rukuni daban. Sa'an nan za a ƙidaya wasu tubalan lambar sakewa ta hanyar amfani da duk bayanan bayanai (a cikin LRC ana kiran su da lambobin redundancy na duniya), wasu kuma - ta hanyar amfani da ɗayan rukuni biyu na bayanan bayanan (ana kiran su code redundancy code).
Ana nuna LRC da lambobi uku: nrl, inda n shine adadin tubalan bayanai, r shine adadin tubalan code redundancy na duniya, l shine adadin tubalan code redundancy na gida. Don karanta bayanai lokacin da babu toshe bayanai guda ɗaya, kuna buƙatar karanta n/l blocks kawai - wannan shine l sau ƙasa da na lambobin Reed-Solomon.
Misali, la'akari da tsarin LRC 6-2-2. X1–X6 — 6 bayanai tubalan, P1, P2 — 2 tubalan redundancy na duniya, P3, P4 — 2 tubalan sakewa na gida.
Ƙididdigar lambar sakewa P1, P2 ana ƙidaya ta amfani da duk tubalan bayanai. Sake lambar toshe P3 - ta amfani da toshe bayanan X1-X3, toshe lambar sakewa P4 - ta amfani da toshe bayanan X4-X6.
Ana yin sauran a cikin LRC ta kwatanci tare da lambobin Reed-Solomon. Ma'auni don kirga kalmomin tubalan lambar sakewa za su kasance:
Don zaɓar lambobin alpha, beta, gamma, delta, dole ne a cika wasu sharuɗɗa don tabbatar da yiwuwar dawo da bayanai (wato, warware tsarin daidaitawa). Kuna iya karanta ƙarin game da su a ciki .
Har ila yau, a aikace, ana amfani da aikin XOR don ƙididdige lambobin sakewa na gida P3, P4.
Ƙididdiga da yawa sun biyo baya daga tsarin daidaitawa na LRC:
- Don dawo da duk wani shingen bayanai 1, ya isa ya karanta n/l blocks (n/2 a cikin misalinmu).
- Idan babu r + l tubalan, kuma duk tubalan suna cikin rukuni ɗaya, to ba za a iya dawo da bayanan ba. Wannan yana da sauƙin bayyana tare da misali. Bari toshe X1-X3 da P3 su kasance: waɗannan tubalan r + l ne daga rukuni ɗaya, 4 a cikin yanayinmu. Sannan muna da tsarin ma'auni 3 tare da abubuwan da ba a sani ba 4 waɗanda ba za a iya warware su ba.
- A duk sauran lokuta na rashin samun tubalan r + l (lokacin da aka samu aƙalla toshe ɗaya daga kowace ƙungiya), ana iya dawo da bayanan da ke cikin LRC.
Don haka, LRC ta zarce lambobin Reed-Solomon wajen dawo da bayanai bayan kurakurai guda ɗaya. A cikin lambobin Reed-Solomon, don dawo da ko da bulogi ɗaya na bayanai, kuna buƙatar amfani da n blocks, kuma a cikin LRC, don dawo da toshe ɗaya na bayanai, ya isa a yi amfani da n/l blocks (n/2 a cikin misalinmu). A gefe guda, LRC tana ƙasa da lambobin Reed-Solomon dangane da matsakaicin adadin kurakurai da aka halatta. A cikin misalan da ke sama, lambobin Reed-Solomon na iya dawo da bayanai don kowane kurakurai 4, kuma ga LRC akwai haɗin 2 na kurakurai 4 lokacin da ba a iya dawo da bayanai ba.
Abin da ya fi mahimmanci ya dogara da takamaiman halin da ake ciki, amma sau da yawa tanadi a cikin nauyin da ya wuce kima wanda LRC ke bayarwa ya fi ƙarancin abin dogaro.
4. Sauran lambobin sakewa
Bayan lambobin Reed-Solomon da LRC, akwai wasu lambobin sakewa da yawa. Lambobin sakewa daban-daban suna amfani da lissafi daban-daban. Ga wasu wasu lambobin sakewa:
- Lambar sakewa ta amfani da ma'aikacin XOR. Ana yin aikin XOR akan n bayanan bayanai, kuma ana samun 1 block of redundancy codes, wato, tsarin n+1 (n data blocks, 1 redundancy code). Amfani a , inda aka rubuta tubalan bayanai da lambobin sakewa a cyclyally zuwa duk fayafai na tsararrun.
- Ko da-m algorithm dangane da aikin XOR. Yana ba ku damar gina tubalan 2 na lambobin sakewa, wato, tsarin n+2.
- STAR algorithm bisa aikin XOR. Yana ba ku damar gina tubalan 3 na lambobin sakewa, wato, tsarin n+3.
- Lambobin Pyramide wasu lambobi ne na sakewa daga Microsoft.
5. Yi amfani da Yandex
Yawancin ayyukan ababen more rayuwa na Yandex suna amfani da lambobin sakewa don amintaccen ajiyar bayanai. Ga wasu misalai:
- Ma'ajiyar kayan ciki na MDS, wanda na rubuta game da shi a farkon labarin.
- - MapReduce tsarin Yandex.
- (Yandex DataBase) - sabon SQL rarraba bayanai.
MDS yana amfani da lambobin sakewa na LRC, 8-2-2 makirci. An rubuta bayanai tare da lambobin sakewa zuwa faifai daban-daban 12 a cikin sabobin daban-daban a cikin 3 daban-daban DCs: sabar 4 a kowace DC. Kara karantawa game da wannan a cikin .
YT yana amfani da lambobin Reed-Solomon guda biyu (Tsarin 6-3), waɗanda sune farkon aiwatarwa, da lambobin sakewa na LRC (Tsarin 12-2-2), tare da LRC shine hanyar ajiya da aka fi so.
YDB yana amfani da ko da-m-sautan lambobi na sakewa (Hoto 4-2). Game da lambobin sakewa a cikin YDB riga .
Amfani da tsare-tsaren lambar sakewa daban-daban saboda buƙatu daban-daban na tsarin. Misali, a cikin MDS, ana sanya bayanan da aka adana ta amfani da LRC a cikin 3 DCs lokaci guda. Yana da mahimmanci a gare mu cewa bayanan sun kasance don karantawa idan 1 na kowane DCs ya kasa, don haka dole ne a rarraba tubalan a cikin DCs ta yadda idan babu wani DC, adadin tubalan da ba za a iya shiga ba ya wuce halatta. A cikin tsari na 8-2-2, zaku iya sanya tubalan 4 a kowane DC, sannan lokacin da aka kashe kowane DC, ba za a sami bulogi 4 ba, kuma ana iya karanta bayanan. Duk wani makirci da muka zaɓa lokacin sanya shi a cikin 3 DCs, a kowane hali ya kamata a sami (r + l) / n> = 0,5, wato, sakewar ajiya zai zama akalla 50%.
A cikin YT yanayin ya bambanta: kowane gungu na YT yana gaba ɗaya a cikin 1 DC (gungu daban-daban a cikin DCs daban-daban), don haka babu irin wannan ƙuntatawa. Tsarin 12-2-2 yana ba da 33% sakewa, wato, adana bayanai yana da arha, kuma yana iya tsira har zuwa 4 cirewar diski a lokaci guda, kamar tsarin MDS.
Akwai ƙarin fasalulluka da yawa na amfani da lambobin sakewa a cikin ajiyar bayanai da tsarin sarrafawa: nuances na dawo da bayanai, tasirin farfadowa akan lokacin aiwatar da tambaya, fasalulluka na rikodin bayanai, da sauransu. Zan yi magana dabam game da waɗannan da sauran fasalulluka. na yin amfani da lambobin sakewa a aikace, idan batun zai zama mai ban sha'awa.
6. Hanyoyin haɗi
- Jerin labarai game da lambobin Reed-Solomon da filayen Galois:
Suna zurfafa duban lissafi a cikin yare mai sauƙi. - Labari daga Microsoft game da LRC:
Sashi na 2 yayi bayani a taƙaice akan ka'idar sannan yayi magana akan gogewa tare da LRC a aikace. - Tsarin tsari:
- Tsarin STAR:
- Lambobin Pyramid:
- Lambobin sakewa a cikin MDS:
- Lambobin sakewa a cikin YT:
- Lambobin sakewa a cikin YDB:
source: www.habr.com