Seo an chuma atá ar iomarcaíocht

Úsáidtear cóid iomarcaíochta* go forleathan i gcórais ríomhaireachta chun iontaofacht stórála sonraí a mhéadú. I Yandex úsáidtear iad i go leor tionscadal. Mar shampla, trí úsáid a bhaint as cóid iomarcaíochta in ionad macasamhlú inár stóráil réad inmheánach, sábhálann sé na milliúin gan iontaofacht a íobairt. Ach in ainneoin a n-úsáide go forleathan, is fíor-annamh a dhéantar cur síos soiléir ar conas a oibríonn cóid iomarcaíochta. Iad siúd atá ag iarraidh tuiscint a fháil, tá thart ar an méid seo a leanas os comhair (ó Vicipéid):

Vadim is ainm dom, ag Yandex tá mé ag forbairt MDS stórála réad inmheánach. San Airteagal seo, déanfaidh mé cur síos i bhfocail shimplí ar bhunús teoiriciúil na gcód iomarcaíochta (cóid Reed-Solomon agus LRC). Inseoidh mé duit conas a oibríonn sé, gan matamaitic chasta agus téarmaí neamhchoitianta. Ag an deireadh tabharfaidh mé samplaí de na cóid iomarcaíochta a úsáid i Yandex.

Ní dhéanfaidh mé roinnt sonraí matamaitice a mheas go mion, ach cuirfidh mé naisc ar fáil dóibh siúd atá ag iarraidh tumadóireacht a dhéanamh níos doimhne. Tabharfaidh mé faoi deara freisin go bhféadfadh nach mbeadh roinnt sainmhínithe matamaitice dian, ós rud é nach bhfuil an t-alt beartaithe do na matamaiticeoirí, ach d'innealtóirí atá ag iarraidh croílár na ceiste a thuiscint.

* I litríocht an Bhéarla, is minic a dtugtar cóid scriosta ar chóid iomarcaíochta.

1. Bunús na gcód iomarcaíochta

Tá bunús na gcód iomarcaíochta go léir thar a bheith simplí: sonraí a stóráil (nó a tharchur) ionas nach gcailltear iad nuair a tharlaíonn earráidí (teipeanna diosca, earráidí aistrithe sonraí, etc.).

Sa chuid is mó de na cóid iomarcaíochta*, roinntear na sonraí ina n bloic sonraí, a ndéantar m bloic de chóid iomarcaíochta a chomhaireamh ina leith, rud a fhágann go bhfuil iomlán de bhloic n + m ann. Tógtar cóid iomarcaíochta sa chaoi is gur féidir n bloic sonraí a aisghabháil gan ach cuid de bhloc n + m a úsáid. Next, beidh muid a mheas ach amháin cóid iomarcaíochta bloc, is é sin, iad siúd ina bhfuil na sonraí roinnte i mbloic.

Chun na n bloic sonraí go léir a aisghabháil, ní mór duit n bloic n + m ar a laghad a bheith agat, ós rud é nach féidir leat n bloic a fháil ach n-1 bloc a bheith agat (sa chás seo, bheadh ort 1 bhloc a thógáil" as tanaí aer”). An leor n bloic randamacha n + m chun na sonraí go léir a aisghabháil? Braitheann sé seo ar an gcineál cóid iomarcaíochta, mar shampla, ceadaíonn cóid Reed-Solomon duit na sonraí go léir a aisghabháil trí úsáid a bhaint as bloic n treallach, ach ní i gcónaí a dhéantar cóid iomarcaíochta an LRC.

Stóráil sonraí

I gcórais stórála sonraí, mar riail, scríobhtar gach ceann de na bloic sonraí agus na bloic cód iomarcaíochta chuig diosca ar leith. Ansin, má theipeann ar dhiosca treallach, is féidir na sonraí bunaidh a athchóiriú agus a léamh go fóill. Is féidir sonraí a aisghabháil fiú má theipeann ar roinnt dioscaí ag an am céanna.

Aistriú sonraí

Is féidir cóid iomarcaíochta a úsáid chun sonraí a tharchur go hiontaofa thar líonra neamhiontaofa. Roinntear na sonraí tarchurtha i mbloic, agus ríomhtar cóid iomarcaíochta dóibh. Tarchuirtear bloic sonraí agus bloic cód iomarcaíochta thar an líonra. Má tharlaíonn earráidí i mbloic treallach (suas le líon áirithe bloic), is féidir sonraí a tharchur fós thar an líonra gan earráidí. Úsáidtear cóid Reed-Solomon, mar shampla, chun sonraí a tharchur thar línte cumarsáide optúla agus i gcumarsáid satailíte.

* Tá cóid iomarcaíochta ann freisin nach bhfuil na sonraí roinnte ina mbloic, mar shampla cóid Hamming agus cóid CRC, a úsáidtear go forleathan le haghaidh tarchur sonraí i líonraí Ethernet. Is cóid iad seo le haghaidh códú earráide a cheartú, tá siad deartha chun earráidí a bhrath, agus gan iad a cheartú (cheadaíonn cód Hamming freisin earráidí a cheartú go páirteach).

2. Cóid Reed-Solomon

Tá cóid Reed-Solomon ar cheann de na cóid iomarcaíochta is mó a úsáidtear, a cumadh siar sna 1960idí agus a úsáideadh go forleathan ar dtús sna 1980í chun dlúthdhioscaí a tháirgeadh le haghaidh mais.

Tá dhá phríomhcheist ann chun cóid Reed-Solomon a thuiscint: 1) conas bloic de chóid iomarcaíochta a chruthú; 2) conas sonraí a aisghabháil ag baint úsáide as bloic cód iomarcaíochta. Faighimis freagraí orthu.
Ar mhaithe le simplíocht, glacfaimid leis freisin go bhfuil n=6 agus m=4. Déantar scéimeanna eile a mheas de réir analaí.

Conas bloic cód iomarcaíochta a chruthú

Déantar gach bloc de chóid iomarcaíochta a chomhaireamh go neamhspleách ar na cinn eile. Úsáidtear gach n bloc sonraí chun gach bloc a chomhaireamh. Sa léaráid thíos, is bloic sonraí iad X1-X6, is bloic cód iomarcaíochta iad P1-P4.

Caithfidh gach bloc sonraí a bheith ar an méid céanna, agus is féidir giotán nialasach a úsáid le haghaidh ailíniú. Beidh na bloic chóid iomarcaíochta mar thoradh ar an méid céanna leis na bloic sonraí. Roinntear na bloic sonraí go léir i bhfocail (mar shampla, 16 giotán). Ligean le rá scoilt muid na bloic sonraí i k focail. Ansin roinnfear gach bloc de chóid iomarcaíochta ina fhocail k freisin.

Chun i-ú focal gach bloc iomarcaíochta a chomhaireamh, úsáidfear na focail i-ú de na bloic sonraí go léir. Déanfar iad a ríomh de réir na foirmle seo a leanas:

Anseo is iad na luachanna x focail na mbloc sonraí, is iad p na focail de bhlocanna cód iomarcaíochta, is uimhreacha roghnaithe go speisialta iad gach alfa, béite, gáma agus deilt atá mar an gcéanna do chách i. Ní mór a rá ar an bpointe boise nach gnáthuimhreacha iad na luachanna seo go léir, ach gnéithe de réimse Galois; ní oibríochtaí iad +, -, *, / a bhfuil aithne againn go léir orthu, ach oibríochtaí speisialta a tugadh isteach ar ghnéithe den Galois Gort.

Cén fáth a bhfuil gá le réimsí Galois?

Dhealródh sé go bhfuil gach rud simplí: roinnimid na sonraí i mbloic, na bloic i bhfocail, ag baint úsáide as na focail de na bloic sonraí a chomhaireamh againn na focail de na bloic cód iomarcaíochta - a fháil againn bloic cód iomarcaíochta. Go ginearálta seo mar a oibríonn sé, ach tá an diabhal sna sonraí:

Mar a dúradh thuas, tá méid na bhfocal socraithe, inár sampla 16 giotán. Tá na foirmlí thuas do chóid Reed-Solomon sa chaoi is go bhféadfadh sé nach bhféadfaí toradh ríomh p a léiriú agus focal de mhéid bailí á úsáid agat.
Agus sonraí á aisghabháil, measfar na foirmlí thuas mar chóras cothromóidí nach mór a réiteach chun na sonraí a aisghabháil. Le linn an phróisis réitigh, b'fhéidir go mbeadh sé riachtanach slánuimhreacha a roinnt ar a chéile, rud a fhágann nach féidir fíoruimhir a léiriú go cruinn i gcuimhne ríomhaire.

Cuireann na fadhbanna seo cosc ar úsáid slánuimhreacha do chóid Reed-Solomon. Is é an réiteach ar an bhfadhb bunaidh, is féidir é a chur síos mar seo a leanas: a ligean ar teacht suas le huimhreacha speisialta is féidir a léiriú ag baint úsáide as focail ar an fad riachtanach (mar shampla, 16 giotán), agus mar thoradh ar chomhlíonadh na n-oibríochtaí go léir ar a (seisiú , dealú, iolrú, roinnt) a chur i láthair freisin i gcuimhne ríomhaire ag baint úsáide as focail den fhad riachtanach.

Tá staidéar déanta ag an matamaitic ar uimhreacha “speisialta” le fada an lá; Is éard is réimse ann ná sraith eilimintí a bhfuil oibríochtaí suimithe, dealaithe, iolrúcháin agus roinnte sainithe dóibh.

Is réimsí iad réimsí Galois* a bhfuil toradh uathúil ar gach oibríocht ina leith (+, -, *, /) d’aon dá ghné den réimse. Is féidir réimsí Galois a thógáil le haghaidh uimhreacha ar cumhachtaí iad 2: 2, 4, 8, 16, etc. (i ndáiríre cumhachtaí aon phríomhuimhir p, ach i ndáiríre níl suim againn ach i gcumhachtaí 2). Mar shampla, le haghaidh focail 16-giotán, is réimse é seo ina bhfuil 65 eilimint, ar féidir leat toradh aon oibríochta a fháil do gach péire acu (+, -, *, /). Déanfar luachanna x, p, alfa, béite, gáma, deilt ó na cothromóidí thuas a mheas mar ghnéithe de réimse Galois le haghaidh ríomhaireachtaí.

Mar sin, tá córas cothromóidí againn lenar féidir linn bloic de chóid iomarcaíochta a thógáil trí ríomhchlár cuí a scríobh. Ag baint úsáide as an gcóras céanna cothromóidí, is féidir leat a dhéanamh sonraí a aisghabháil.

* Ní sainmhíniú docht é seo, ach cur síos.

Conas sonraí a aisghabháil

Tá gá le hathchóiriú nuair a bhíonn cuid de na bloic n+m in easnamh. Is féidir iad seo a bheith ina bhloic shonraí agus ina mbloic chóid iomarcaíochta araon. Mar gheall ar easpa blocanna sonraí agus/nó bloic chóid iomarcaíochta, beidh na hathróga x agus/nó p comhfhreagracha anaithnid sna cothromóidí thuas.

Is féidir breathnú ar na cothromóidí do chóid Reed-Solomon mar chóras cothromóidí inar tairisigh iad na luachanna alfa, béite, gáma, deilt ar fad, gach x agus p a chomhfhreagraíonn do na bloic atá ar fáil mar athróga aitheanta, agus na x agus p atá fágtha. anaithnid.

Mar shampla, bíodh nach bhfuil bloic sonraí 1, 2, 3 agus cód iomarcaíochta 2 ar fáil, ansin don ghrúpa i-ú focal beidh an córas cothromóidí seo a leanas (marcáiltear na neamhaitheanta i dearg):

Tá córas 4 chothromóid againn le 4 rud anaithnid, rud a chiallaíonn gur féidir linn é a réiteach agus na sonraí a athchóiriú!

Ón gcóras cothromóidí seo leanann roinnt conclúidí faoi aisghabháil sonraí do chóid Reed-Solomon (n bloic sonraí, m bloic cód iomarcaíochta):

Is féidir sonraí a aisghabháil má chailltear aon mbloic nó níos lú. Má chailltear m+1 nó níos mó bloic, ní féidir na sonraí a chur ar ais: ní féidir córas m cothromóidí a réiteach le m + 1 anaithnid.
Chun fiú bloc sonraí amháin a ghnóthú, ní mór duit aon n de na bloic atá fágtha a úsáid, agus is féidir leat aon cheann de na cóid iomarcaíochta a úsáid.

Cad eile a theastaíonn uaim a fhios?

Sa chur síos thuas, seachnaím roinnt saincheisteanna tábhachtacha nach mór breathnú níos doimhne orthu sa mhatamaitic. Go háirithe, níl mé ag rá faic faoi na nithe seo a leanas:

Caithfidh réiteach (uathúil) a bheith ag córas na gcothromóidí do chóid Reed-Solomon maidir le haon teaglaim de rudaí anaithnide (gan níos mó ná m anaithnide). Bunaithe ar an gceanglas seo, roghnaítear na luachanna alfa, béite, gáma agus deilt.
Ní mór córas cothromóidí a bheith in ann a thógáil go huathoibríoch (ag brath ar na bloic nach bhfuil ar fáil) agus a réiteach.
Ní mór dúinn réimse Galois a thógáil: le haghaidh méid focal ar leith, a bheith in ann toradh aon oibríochta (+, -, *, /) a fháil le haghaidh dhá ghné ar bith.

Ag deireadh an ailt tá tagairtí don litríocht ar na ceisteanna tábhachtacha seo.

Rogha n agus m

Conas n agus m a roghnú go praiticiúil? Go praiticiúil, i gcórais stórála sonraí, úsáidtear cóid iomarcaíochta chun spás a shábháil, mar sin roghnaítear m i gcónaí níos lú ná n. Braitheann a gcuid luachanna sonracha ar roinnt fachtóirí, lena n-áirítear:

Iontaofacht stórála sonraí. An m níos mó, is mó an líon teipeanna diosca is féidir a maireachtáil, is é sin, is airde an iontaofacht.
Stóráil iomarcach. Dá airde an cóimheas m/n, is airde a bheidh an iomarcaíocht stórála, agus is costasaí a bheidh an córas.
Iarr am próiseála. Dá mhéad an tsuim n + m, is ea is faide an t-am freagartha ar iarratais. Ós rud é go n-éilíonn léamh sonraí (le linn aisghabháil) n bloic a stóráiltear ar n dioscaí éagsúla, is é an diosca is moille a chinnfidh an t-am léite.

Ina theannta sin, cuireann stóráil sonraí i roinnt DCanna srianta breise ar an rogha n agus m: má tá 1 DC casta as, caithfidh na sonraí a bheith fós ar fáil le léamh. Mar shampla, agus sonraí á stóráil i 3 DC, ní mór an coinníoll seo a leanas a chomhlíonadh: m >= n/2, nó d’fhéadfadh go mbeadh cás ann nach bhfuil na sonraí ar fáil le léamh nuair a bhíonn 1 DC múchta.

3. LRC - Cóid Atógála Áitiúla

Chun sonraí a aisghabháil ag baint úsáide as cóid Reed-Solomon, caithfidh tú n bloic sonraí treallach a úsáid. Is míbhuntáiste an-suntasach é seo do chórais stórála sonraí dáilte, mar chun sonraí a athbhunú ar dhiosca briste amháin, beidh ort sonraí a léamh ón gcuid is mó de na cinn eile, rud a chruthaíonn ualach mór breise ar na dioscaí agus ar an líonra.

Is iad na hearráidí is coitianta ná neamh-inrochtaineacht bloc amháin sonraí mar gheall ar theip nó ró-ualach diosca amháin. An féidir an ró-ualach le haghaidh aisghabháil sonraí a laghdú ar bhealach éigin sa chás seo (is coitianta)? Tarlaíonn sé gur féidir leat: tá cóid iomarcaíochta CCO ann go sonrach chun na críche seo.

Is cóid iomarcaíochta iad LRC (Cóid Athchóirithe Áitiúla) arna bhforbairt ag Microsoft lena n-úsáid i Windows Stóráil Azure. Tá an smaoineamh atá taobh thiar de LRC an-simplí: roinn na bloic sonraí go léir ina dhá ghrúpa (nó níos mó) agus ríomh cuid de na bloic chód iomarcaíochta do gach grúpa ar leithligh. Ansin, ríomhfar cuid de na bloic chód iomarcaíochta ag baint úsáide as na bloic sonraí go léir (i LRC, tugtar cóid iomarcaíochta domhanda orthu seo), agus ríomhfar cuid eile ag baint úsáide as ceann den dá ghrúpa bloic sonraí (tugtar cóid iomarcaíochta áitiúla orthu seo).

Cuirtear trí uimhir in iúl don LRC: nrl, áit arb é n líon na mbloc sonraí, is é r líon na mbloc cód iomarcaíochta domhanda, is é l líon na mbloc cóid iomarcaíochta áitiúla. Chun sonraí a léamh nuair nach bhfuil bloc sonraí amháin ar fáil, ní mór duit ach bloic n/l a léamh - tá sé seo l uaireanta níos lú ná i gcód Reed-Solomon.

Mar shampla, smaoinigh ar scéim an LRC 6-2-2. X1–X6 – 6 bhloc sonraí, P1, P2 – 2 bhloc iomarcaíochta domhanda, P3, P4 – 2 bhloc iomarcaíochta áitiúla.

Déantar bloic cóid iomarcaíochta P1, P2 a chomhaireamh ag baint úsáide as na bloic sonraí go léir. Bloc cód iomarcaíochta P3 - ag baint úsáide as bloic sonraí X1-X3, bloc cód iomarcaíochta P4 - ag baint úsáide as bloic sonraí X4-X6.

Déantar an chuid eile sa LRC de réir analaí le cóid Reed-Solomon. Is iad seo a leanas na cothromóidí chun focail na mbloc cóid iomarcaíochta a chomhaireamh:

Chun na huimhreacha alfa, béite, gáma, deilt a roghnú, ní mór roinnt coinníollacha a chomhlíonadh chun an fhéidearthacht sonraí a aisghabháil a ráthú (is é sin, an córas cothromóide a réiteach). Is féidir leat tuilleadh a léamh mar gheall orthu i Airteagal.
Go praiticiúil freisin, úsáidtear an oibríocht XOR chun cóid iomarcaíochta áitiúla P3, P4 a ríomh.

Leanann roinnt conclúidí ón gcóras cothromóidí don LRC:

Chun aon bhloc 1 sonraí a aisghabháil, is leor bloic n/l a léamh (n/2 inár sampla).
Mura bhfuil bloic r + l ar fáil, agus go bhfuil na bloic go léir san áireamh i ngrúpa amháin, ní féidir na sonraí a chur ar ais. Is furasta é seo a mhíniú le sampla. Bíodh bloic X1–X3 agus P3 ar fáil: is iad seo bloic r + l ón ngrúpa céanna, 4 inár gcás. Ansin tá córas 3 chothromóid againn le 4 rud anaithnid nach féidir a réiteach.
I ngach cás eile nach bhfuil fáil ar bhloic r + l (nuair a bhíonn bloc amháin ar a laghad ar fáil ó gach grúpa), is féidir na sonraí sa LRC a chur ar ais.

Mar sin, sáraíonn LRC cóid Reed-Solomon maidir le sonraí a aisghabháil tar éis earráidí aonair. I gcód Reed-Solomon, chun fiú bloc amháin sonraí a aisghabháil, ní mór duit n bloic a úsáid, agus sa LRC, chun bloc amháin sonraí a aisghabháil, is leor bloic n/l a úsáid (n/2 inár sampla). Ar an láimh eile, tá LRC níos lú ná cóid Reed-Solomon i dtéarmaí uaslíon na n-earráidí incheadaithe. Sna samplaí thuas, is féidir le cóid Reed-Solomon sonraí a aisghabháil le haghaidh aon 4 earráid, agus le haghaidh LRC tá 2 theaglaim de 4 earráidí nuair nach féidir sonraí a aisghabháil.

Braitheann an rud atá níos tábhachtaí ar an staid shonrach, ach is minic a shábhálann an ró-ualach a sholáthraíonn an LRC an stóráil atá beagán níos lú iontaofa.

4. Cóid iomarcaíochta eile

Seachas cóid Reed-Solomon agus LRC, tá go leor cód iomarcaíochta eile ann. Úsáideann cóid iomarcaíochta difriúla matamaitic dhifriúla. Seo roinnt cóid iomarcaíochta eile:

Cód iomarcaíochta ag baint úsáide as an oibreoir XOR. Déantar an oibríocht XOR ar n bloic sonraí, agus faightear 1 bhloc de chóid iomarcaíochta, is é sin, scéim n+1 (n bloic sonraí, 1 cód iomarcaíochta). Úsáidtear i Raid 5, áit a scríobhtar bloic sonraí agus cóid iomarcaíochta go timthriallach ar gach diosca den eagar.
Algartam cothrom corr bunaithe ar oibríocht XOR. Ligeann sé duit 2 bhloc de chód iomarcaíochta a thógáil, is é sin, an scéim n+2.
Algartam STAR bunaithe ar oibríocht XOR. Ligeann sé duit 3 bhloc de chód iomarcaíochta a thógáil, is é sin an scéim n+3.
Is cóid iomarcaíochta eile ó Microsoft iad cóid phirimide.

5. Úsáid i Yandex

Úsáideann roinnt tionscadal bonneagair Yandex cóid iomarcaíochta chun sonraí a stóráil go hiontaofa. Seo roinnt samplaí:

Stóráil réad inmheánach MDS, a scríobh mé faoi ag tús an ailt.
YT — Córas MapReduce de Yandex.
YDB (Yandex Database) - bunachar sonraí dáilte newSQL.

Úsáideann MDS cóid iomarcaíochta an LRC, scéim 8-2-2. Scríobhtar sonraí le cóid iomarcaíochta chuig 12 dhiosca dhifriúla i bhfreastalaithe éagsúla i 3 DC éagsúla: 4 fhreastalaí i ngach DC. Léigh tuilleadh faoi seo i Airteagal.

Úsáideann YT an dá chóid Reed-Solomon (Scéim 6-3), a bhí ar na chéad cheann a cuireadh i bhfeidhm, agus cóid iomarcaíochta an LRC (Scéim 12-2-2), agus an LRC mar an modh stórála roghnaithe.

Úsáideann YDB cóid iomarcaíochta corrbhunaithe (Fíor 4-2). Maidir le cóid iomarcaíochta in YDB cheana féin a dúradh ar Highload.

Tá úsáid scéimeanna cód iomarcaíochta éagsúla mar gheall ar riachtanais éagsúla do chórais. Mar shampla, i MDS, cuirtear sonraí arna stóráil ag baint úsáide as LRC i 3 DC ag an am céanna. Tá sé tábhachtach dúinn go bhfanfadh na sonraí ar fáil le léamh má theipeann ar 1 d’aon DC, mar sin ní mór na bloic a dháileadh ar na DCanna ionas nach mbeidh líon na mbloc dorochtana níos mó ná ceadaithe mura bhfuil aon DC ar fáil. Sa scéim 8-2-2, is féidir leat 4 bhloc a chur i ngach DC, ansin nuair a bhíonn aon DC casta as, ní bheidh 4 bhloc ar fáil, agus is féidir na sonraí a léamh. Cibé scéim a roghnaíonn muid nuair a chuirtear é i 3 DC, in aon chás ba chóir go mbeadh (r + l) / n>= 0,5, is é sin, beidh iomarcaíocht stórála 50% ar a laghad.

I YT tá an scéal difriúil: tá gach braisle YT suite go hiomlán in 1 DC (braislí éagsúla i DCanna éagsúla), agus mar sin níl aon srian den sórt sin ann. Soláthraíonn an scéim 12-2-2 iomarcaíocht 33%, is é sin, tá stóráil sonraí níos saoire, agus is féidir leis maireachtáil suas le 4 bhriseadh diosca comhuaineach, díreach cosúil leis an scéim MDS.

Tá i bhfad níos mó gnéithe ag baint le húsáid na gcód iomarcaíochta i gcórais stórála agus phróiseála sonraí: nuances aisghabhála sonraí, tionchar an téarnaimh ar am forghníomhaithe fiosrúcháin, gnéithe taifeadta sonraí, etc. maidir le húsáid na gcód iomarcaíochta go praiticiúil, an mbeidh an topaic suimiúil.