Dyma sut olwg sydd ar ddileu swydd
Defnyddir codau diswyddo* yn eang mewn systemau cyfrifiadurol i gynyddu dibynadwyedd storio data. Yn Yandex fe'u defnyddir mewn llawer o brosiectau. Er enghraifft, mae defnyddio codau diswyddo yn lle dyblygu yn ein storfa wrthrychau fewnol yn arbed miliynau heb aberthu dibynadwyedd. Ond er gwaethaf eu defnydd eang, prin iawn yw disgrifiadau clir o sut mae codau diswyddo yn gweithio. Mae'r rhai sydd am ddeall yn wynebu tua'r canlynol (o ):
Fy enw i yw Vadim, yn Yandex rwy'n datblygu MDS storio gwrthrychau mewnol. Yn yr erthygl hon, byddaf yn disgrifio mewn geiriau syml sylfeini damcaniaethol codau diswyddo (codau Reed-Solomon a LRC). Fe ddywedaf wrthych sut mae'n gweithio, heb fathemateg gymhleth a thermau prin. Ar y diwedd byddaf yn rhoi enghreifftiau o ddefnyddio codau diswyddo yn Yandex.
Ni fyddaf yn ystyried nifer o fanylion mathemategol yn fanwl, ond byddaf yn darparu dolenni i'r rhai sydd am blymio'n ddyfnach. Nodaf hefyd efallai na fydd rhai diffiniadau mathemategol yn llym, gan nad yw'r erthygl wedi'i bwriadu ar gyfer mathemategwyr, ond ar gyfer peirianwyr sydd am ddeall hanfod y mater.
* Mewn llenyddiaeth Saesneg, gelwir codau dileu swydd yn aml yn godau dileu.
1. Hanfod codau diswyddo
Mae hanfod yr holl godau diswyddo yn hynod o syml: storio (neu drosglwyddo) data fel nad yw'n cael ei golli pan fydd gwallau'n digwydd (methiannau disg, gwallau trosglwyddo data, ac ati).
Yn y mwyafrif o godau diswyddo*, rhennir y data yn n bloc data, y mae blociau m o godau dileu swydd yn cael eu cyfrif ar eu cyfer, gan arwain at gyfanswm o flociau n + m. Mae codau diswyddo yn cael eu llunio yn y fath fodd fel y gellir adennill n blociau o ddata gan ddefnyddio dim ond cyfran o flociau n + m. Nesaf, byddwn yn ystyried codau diswyddo bloc yn unig, hynny yw, y rhai y mae'r data wedi'i rannu'n flociau ynddynt.
I adennill yr holl flociau o ddata, mae angen i chi gael o leiaf n o flociau n + m, gan na allwch gael blociau n trwy gael bloc n-1 yn unig (yn yr achos hwn, byddai'n rhaid i chi gymryd 1 bloc "allan o denau aer”). Ydy n blociau ar hap o flociau n + m yn ddigon i adennill yr holl ddata? Mae hyn yn dibynnu ar y math o godau diswyddo, er enghraifft, mae codau Reed-Solomon yn caniatáu ichi adennill yr holl ddata gan ddefnyddio blociau n mympwyol, ond nid yw codau diswyddo'r CAD bob amser.
Storio data
Mewn systemau storio data, fel rheol, mae pob un o'r blociau data a'r blociau cod diswyddo yn cael eu hysgrifennu i ddisg ar wahân. Yna, os bydd disg mympwyol yn methu, gellir dal i adfer a darllen y data gwreiddiol. Gellir adennill data hyd yn oed os bydd sawl disg yn methu ar yr un pryd.
Trosglwyddo data
Gellir defnyddio codau diswyddo i drosglwyddo data yn ddibynadwy dros rwydwaith annibynadwy. Rhennir y data a drosglwyddir yn flociau, a chyfrifir codau diswyddo ar eu cyfer. Mae blociau data a blociau cod diswyddo yn cael eu trosglwyddo dros y rhwydwaith. Os bydd gwallau'n digwydd mewn blociau mympwyol (hyd at nifer penodol o flociau), gellir dal i drosglwyddo data dros y rhwydwaith heb gamgymeriad. Defnyddir codau Reed-Solomon, er enghraifft, i drosglwyddo data dros linellau cyfathrebu optegol ac mewn cyfathrebiadau lloeren.
* Mae yna hefyd godau diswyddo lle nad yw'r data wedi'i rannu'n flociau, megis codau Hamming a chodau CRC, a ddefnyddir yn eang ar gyfer trosglwyddo data mewn rhwydweithiau Ethernet. Mae'r rhain yn godau ar gyfer codio cywiro gwallau, maent wedi'u cynllunio i ganfod gwallau, ac nid i'w cywiro (mae'r cod Hamming hefyd yn caniatáu cywiro gwallau yn rhannol).
2. Codau Reed-Solomon
Mae codau Reed-Solomon yn un o'r codau diswyddo a ddefnyddir fwyaf, a ddyfeisiwyd yn ôl yn y 1960au ac a ddefnyddiwyd yn eang gyntaf yn yr 1980au ar gyfer cynhyrchu màs o gryno ddisgiau.
Mae dau gwestiwn allweddol ar gyfer deall codau Reed-Solomon: 1) sut i greu blociau o godau diswyddo; 2) sut i adennill data gan ddefnyddio blociau cod diswyddo. Gadewch i ni ddod o hyd i atebion iddynt.
Er mwyn symlrwydd, byddwn yn tybio ymhellach bod n=6 ac m=4. Ystyrir cynlluniau eraill trwy gyfatebiaeth.
Sut i greu blociau cod dileu swydd
Mae pob bloc o godau dileu swydd yn cael ei gyfrif yn annibynnol ar y lleill. Defnyddir pob n bloc data i gyfrif pob bloc. Yn y diagram isod, blociau data yw X1-X6, blociau cod diswyddo yw P1-P4.
Rhaid i bob bloc data fod yr un maint, a gellir defnyddio darnau sero ar gyfer aliniad. Bydd y blociau cod dileu swydd canlyniadol yr un maint â'r blociau data. Rhennir yr holl flociau data yn eiriau (er enghraifft, 16 did). Gadewch i ni ddweud ein bod yn rhannu'r blociau data yn eiriau k. Yna bydd pob bloc o godau dileu swydd hefyd yn cael eu rhannu'n eiriau k.
I gyfri gair i-th pob bloc dileu swydd, bydd geiriau i-th pob bloc data yn cael eu defnyddio. Byddant yn cael eu cyfrifo yn ôl y fformiwla ganlynol:
Yma mae'r gwerthoedd x yn eiriau blociau data, p yw geiriau blociau cod diswyddo, mae pob alffa, beta, gama a delta yn rhifau a ddewiswyd yn arbennig sydd yr un peth ar gyfer pob i. Mae'n rhaid dweud ar unwaith nad rhifau cyffredin mo'r holl werthoedd hyn, ond elfennau o faes Galois; nid yw'r gweithrediadau +, -, *, / yn weithrediadau cyfarwydd i ni i gyd, ond yn weithrediadau arbennig a gyflwynwyd ar elfennau o'r Galois maes.
Pam mae angen caeau Galois?
Mae'n ymddangos bod popeth yn syml: rydym yn rhannu'r data yn flociau, y blociau yn eiriau, gan ddefnyddio geiriau'r blociau data rydym yn cyfrif geiriau'r blociau cod diswyddo - rydym yn cael blociau cod diswyddo. Yn gyffredinol, dyma sut mae'n gweithio, ond mae'r diafol yn y manylion:
- Fel y dywedwyd uchod, mae maint y gair yn sefydlog, yn ein hesiampl 16 did. Mae'r fformiwlâu uchod ar gyfer codau Reed-Solomon yn golygu, wrth ddefnyddio cyfanrifau cyffredin, efallai na fydd canlyniad cyfrifo p yn cael ei gynrychioli gan ddefnyddio gair o faint dilys.
- Wrth adennill data, bydd y fformiwlâu uchod yn cael eu hystyried fel system o hafaliadau y mae'n rhaid eu datrys er mwyn adennill y data. Yn ystod y broses datrysiad, efallai y bydd angen rhannu cyfanrifau â'i gilydd, gan arwain at rif real na ellir ei gynrychioli'n gywir yng nghof y cyfrifiadur.
Mae'r problemau hyn yn atal y defnydd o gyfanrifau ar gyfer codau Reed-Solomon. Mae'r ateb i'r broblem yn wreiddiol, gellir ei ddisgrifio fel a ganlyn: gadewch i ni ddod o hyd i rifau arbennig y gellir eu cynrychioli gan ddefnyddio geiriau o'r hyd gofynnol (er enghraifft, 16 did), a chanlyniad perfformio'r holl weithrediadau ar ba (ychwanegiad , tynnu, lluosi, rhannu) hefyd yn cael ei gyflwyno ar gof cyfrifiadur gan ddefnyddio geiriau o'r hyd gofynnol.
Mae niferoedd “arbennig” o’r fath wedi’u hastudio gan fathemateg ers amser maith; fe’u gelwir yn feysydd. Mae maes yn set o elfennau gyda gweithrediadau adio, tynnu, lluosi a rhannu wedi'u diffinio ar eu cyfer.
Mae caeau Galois* yn feysydd lle mae canlyniad unigryw pob gweithrediad (+, -, *, /) ar gyfer unrhyw ddwy elfen o'r maes. Gellir adeiladu meysydd Galois ar gyfer rhifau sy'n bwerau o 2: 2, 4, 8, 16, ac ati (mewn gwirionedd pwerau unrhyw rif cysefin p, ond yn ymarferol dim ond pwerau 2 sydd gennym ni). Er enghraifft, ar gyfer geiriau 16-did, mae hwn yn faes sy'n cynnwys 65 o elfennau, ar gyfer pob pâr gallwch ddod o hyd i ganlyniad unrhyw weithrediad (+, -, *, /). Bydd gwerthoedd x, p, alffa, beta, gama, delta o'r hafaliadau uchod yn cael eu hystyried yn elfennau o faes Galois ar gyfer cyfrifiadau.
Felly, mae gennym system o hafaliadau y gallwn adeiladu blociau o godau dileu swydd â hi trwy ysgrifennu rhaglen gyfrifiadurol briodol. Gan ddefnyddio'r un system o hafaliadau, gallwch berfformio adfer data.
* Nid yw hwn yn ddiffiniad llym, ond yn hytrach yn ddisgrifiad.
Sut i adennill data
Mae angen adfer pan fydd rhai o'r blociau n+m ar goll. Gall y rhain fod yn flociau data ac yn flociau cod dileu swydd. Bydd absenoldeb blociau data a/neu flociau cod dileu swydd yn golygu bod y newidynnau x a/neu p cyfatebol yn anhysbys yn yr hafaliadau uchod.
Gellir gweld yr hafaliadau ar gyfer codau Reed-Solomon fel system o hafaliadau lle mae holl werthoedd alffa, beta, gama, delta yn gysonion, pob x a p sy'n cyfateb i'r blociau sydd ar gael yn newidynnau hysbys, a'r x a p sy'n weddill yn anhysbys.
Er enghraifft, gadewch i flociau data 1, 2, 3 a bloc cod dileu swydd 2 beidio â bod ar gael, yna ar gyfer y grŵp i-th o eiriau bydd y system hafaliadau ganlynol (mae anhysbys wedi'i farcio mewn coch):
Mae gennym system o 4 hafaliad gyda 4 anhysbys, sy'n golygu y gallwn ei ddatrys ac adfer y data!
O'r system hon o hafaliadau mae nifer o gasgliadau'n dilyn am adfer data ar gyfer codau Reed-Solomon (n blociau data, m blociau cod diswyddo):
- Gellir adennill data os collir unrhyw flociau m neu lai. Os collir m+1 neu fwy o flociau, ni ellir adfer y data: mae'n amhosib datrys system o hafaliadau m gyda m + 1 yn anhysbys.
- I adennill hyd yn oed un bloc data, mae angen i chi ddefnyddio unrhyw n o'r blociau sy'n weddill, a gallwch ddefnyddio unrhyw un o'r codau diswyddo.
Beth arall sydd angen i chi ei wybod
Yn y disgrifiad uchod, rwy'n osgoi nifer o faterion pwysig sy'n gofyn am blymio'n ddyfnach i fathemateg i'w hystyried. Yn benodol, nid wyf yn dweud dim am y canlynol:
- Rhaid i'r system hafaliadau ar gyfer codau Reed-Solomon gael datrysiad (unigryw) ar gyfer unrhyw gyfuniad o bethau anhysbys (dim mwy nag m anhysbys). Yn seiliedig ar y gofyniad hwn, dewisir gwerthoedd alffa, beta, gama a delta.
- Rhaid i system o hafaliadau allu cael ei llunio'n awtomatig (yn dibynnu ar ba flociau nad ydynt ar gael) a'u datrys.
- Mae angen i ni adeiladu maes Galois: ar gyfer maint gair penodol, gallu dod o hyd i ganlyniad unrhyw weithrediad (+, -, *, /) ar gyfer unrhyw ddwy elfen.
Ar ddiwedd yr erthygl ceir cyfeiriadau at lenyddiaeth ar y materion pwysig hyn.
Dewis o n ac m
Sut i ddewis n ac m yn ymarferol? Yn ymarferol, mewn systemau storio data, defnyddir codau diswyddo i arbed lle, felly mae m bob amser yn cael ei ddewis yn llai nag n. Mae eu gwerthoedd penodol yn dibynnu ar nifer o ffactorau, gan gynnwys:
- Dibynadwyedd storio data. Y mwyaf m, y mwyaf yw'r nifer o fethiannau disg y gellir eu goroesi, hynny yw, yr uchaf yw'r dibynadwyedd.
- Storfa ddiangen. Po uchaf yw'r gymhareb m/n, yr uchaf fydd y diswyddiad storio, a'r drutaf fydd y system.
- Cais am amser prosesu. Po fwyaf yw'r swm n + m, yr hiraf fydd yr amser ymateb i geisiadau. Gan fod darllen data (yn ystod adferiad) yn gofyn am ddarllen n blociau sydd wedi'u storio ar n ddisgiau gwahanol, bydd yr amser darllen yn cael ei bennu gan y ddisg arafaf.
Yn ogystal, mae storio data mewn sawl DC yn gosod cyfyngiadau ychwanegol ar y dewis o n ac m: os caiff 1 DC ei ddiffodd, rhaid i'r data fod ar gael i'w ddarllen o hyd. Er enghraifft, wrth storio data mewn 3 DC, rhaid bodloni'r amod canlynol: m >= n/2, fel arall efallai y bydd sefyllfa lle nad yw'r data ar gael i'w ddarllen pan fydd 1 DC wedi'i ddiffodd.
3. LRC - Codau Ailadeiladu Lleol
I adennill data gan ddefnyddio codau Reed-Solomon, rhaid i chi ddefnyddio n blociau data mympwyol. Mae hwn yn anfantais sylweddol iawn ar gyfer systemau storio data dosbarthedig, oherwydd i adfer data ar un ddisg wedi'i dorri, bydd yn rhaid i chi ddarllen data o'r rhan fwyaf o'r lleill, gan greu llwyth ychwanegol mawr ar y disgiau a'r rhwydwaith.
Y gwallau mwyaf cyffredin yw anhygyrchedd un bloc o ddata oherwydd methiant neu orlwytho un ddisg. A yw'n bosibl rhywsut leihau'r llwyth gormodol ar gyfer adfer data yn yr achos hwn (mwyaf cyffredin)? Mae'n troi allan y gallwch: mae codau diswyddo'r CAD yn benodol at y diben hwn.
Codau diswyddo yw LRC (Codau Ailadeiladu Lleol) a ddyfeisiwyd gan Microsoft i'w defnyddio yn Windows Azure Storage. Mae'r syniad o LRC mor syml â phosibl: rhannwch yr holl flociau data yn ddau (neu fwy) o grwpiau a darllenwch ran o'r blociau cod dileu swydd ar gyfer pob grŵp ar wahân. Yna bydd rhai blociau cod dileu swydd yn cael eu cyfrif gan ddefnyddio'r holl flociau data (yn y CAD fe'u gelwir yn godau diswyddo byd-eang), a rhai - gan ddefnyddio un o ddau grŵp o flociau data (fe'u gelwir yn godau diswyddo lleol).
Mae LRC yn cael ei ddynodi gan dri rhif: nrl, lle n yw nifer y blociau data, r yw nifer y blociau cod dileu swydd byd-eang, l yw nifer y blociau cod diswyddo lleol. I ddarllen data pan nad yw un bloc data ar gael, mae angen i chi ddarllen n/l blociau yn unig - mae hyn l gwaith yn llai nag yng nghodau Reed-Solomon.
Er enghraifft, ystyriwch gynllun LRC 6-2-2. X1–X6 – 6 bloc data, P1, P2 – 2 floc diswyddo byd-eang, P3, P4 – 2 floc diswyddo lleol.
Mae blociau cod diswyddo P1, P2 yn cael eu cyfrif gan ddefnyddio'r holl flociau data. Bloc cod diswyddo P3 - defnyddio blociau data X1-X3, bloc cod dileu swydd P4 - defnyddio blociau data X4-X6.
Gwneir y gweddill yn LRC trwy gyfatebiaeth â chodau Reed-Solomon. Yr hafaliadau ar gyfer cyfrif geiriau blociau cod dileu swydd fydd:
I ddewis y rhifau alffa, beta, gama, delta, rhaid bodloni nifer o amodau i warantu'r posibilrwydd o adfer data (hynny yw, datrys y system hafaliad). Gallwch ddarllen mwy amdanynt yn .
Hefyd yn ymarferol, defnyddir gweithrediad XOR i gyfrifo codau diswyddo lleol P3, P4.
Mae nifer o gasgliadau yn dilyn o’r system hafaliadau ar gyfer LRC:
- I adennill unrhyw 1 bloc data, mae'n ddigon darllen blociau n/l (n/2 yn ein hesiampl).
- Os nad yw blociau r + l ar gael, a bod yr holl flociau wedi'u cynnwys mewn un grŵp, yna ni ellir adfer y data. Mae hyn yn hawdd i'w esbonio gydag enghraifft. Peidiwch â gadael blociau X1–X3 a P3 ar gael: blociau r + l o'r un grŵp yw'r rhain, 4 yn ein hachos ni. Yna mae gennym system o 3 hafaliad gyda 4 anhysbys na ellir eu datrys.
- Ym mhob achos arall lle nad yw blociau r + l ar gael (pan fydd o leiaf un bloc ar gael o bob grŵp), gellir adfer y data yn y CAD.
Felly, mae LRC yn perfformio'n well na chodau Reed-Solomon wrth adfer data ar ôl gwallau sengl. Mewn codau Reed-Solomon, i adennill hyd yn oed un bloc o ddata, mae angen i chi ddefnyddio blociau n, ac yn LRC, i adennill un bloc o ddata, mae'n ddigon defnyddio blociau n / l (n/2 yn ein hesiampl). Ar y llaw arall, mae LRC yn israddol i godau Reed-Solomon o ran uchafswm nifer y gwallau a ganiateir. Yn yr enghreifftiau uchod, gall codau Reed-Solomon adennill data ar gyfer unrhyw 4 gwall, ac ar gyfer LRC mae 2 gyfuniad o 4 gwall pan na ellir adennill data.
Mae'r hyn sy'n bwysicach yn dibynnu ar y sefyllfa benodol, ond yn aml mae'r arbedion mewn llwyth gormodol y mae LRC yn eu darparu yn gorbwyso'r storfa ychydig yn llai dibynadwy.
4. Codau diswyddo eraill
Heblaw am godau Reed-Solomon a LRC, mae yna lawer o godau diswyddo eraill. Mae gwahanol godau diswyddo yn defnyddio gwahanol fathemateg. Dyma rai codau diswyddo eraill:
- Cod dileu swydd gan ddefnyddio'r gweithredwr XOR. Perfformir gweithrediad XOR ar n bloc data, a cheir 1 bloc o godau diswyddo, hynny yw, cynllun n+1 (n blociau data, 1 cod dileu swydd). Defnyddir yn , lle mae blociau o ddata a chodau dileu swydd yn cael eu hysgrifennu'n gylchol i bob disg o'r arae.
- Algorithm eilrif yn seiliedig ar y gweithrediad XOR. Yn eich galluogi i adeiladu 2 floc o godau dileu swydd, hynny yw, y cynllun n+2.
- Algorithm STAR yn seiliedig ar weithrediad XOR. Yn eich galluogi i adeiladu 3 bloc o godau diswyddo, hynny yw, cynllun n+3.
- Mae codau pyramid yn godau diswyddo arall gan Microsoft.
5. Defnyddio yn Yandex
Mae nifer o brosiectau seilwaith Yandex yn defnyddio codau diswyddo ar gyfer storio data dibynadwy. Dyma rai enghreifftiau:
- Storio gwrthrychau mewnol MDS, yr ysgrifennais amdani ar ddechrau'r erthygl.
- — System MapReduce o Yandex.
- (Cronfa DdataYandex) - cronfa ddata ddosbarthedig newSQL.
Mae ISD yn defnyddio codau diswyddo'r LRC, cynllun 8-2-2. Ysgrifennir data gyda chodau diswyddo i 12 disg gwahanol mewn gweinyddwyr gwahanol mewn 3 DC gwahanol: 4 gweinydd ym mhob DC. Darllenwch fwy am hyn yn .
Mae YT yn defnyddio codau Reed-Solomon (Cynllun 6-3), sef y rhai cyntaf i'w gweithredu, a chodau diswyddo LRC (Cynllun 12-2-2), a'r LRC oedd y dull storio a ffefrir.
Mae YDB yn defnyddio codau diswyddo sy'n seiliedig ar eilrif od (Ffigur 4-2). Ynglŷn â chodau diswyddo yn YDB eisoes .
Mae'r defnydd o wahanol gynlluniau cod diswyddo oherwydd gofynion gwahanol ar gyfer systemau. Er enghraifft, yn ISD, mae data sy'n cael ei storio gan ddefnyddio LRC yn cael ei roi mewn 3 DC ar unwaith. Mae'n bwysig i ni fod y data yn parhau i fod ar gael i'w ddarllen os bydd 1 o unrhyw DC yn methu, felly mae'n rhaid dosbarthu'r blociau ar draws y DCs fel, os nad oes unrhyw DC ar gael, nad yw nifer y blociau anhygyrch yn fwy na'r hyn a ganiateir. Yn y cynllun 8-2-2, gallwch chi osod 4 bloc ym mhob DC, yna pan fydd unrhyw DC wedi'i ddiffodd, ni fydd 4 bloc ar gael, a gellir darllen y data. Pa bynnag gynllun a ddewiswn wrth ei osod mewn 3 DC, mewn unrhyw achos dylai fod (r + l) / n>= 0,5, hynny yw, bydd diswyddo storio o leiaf 50%.
Yn YT mae'r sefyllfa'n wahanol: mae pob clwstwr YT wedi'i leoli'n gyfan gwbl mewn 1 DC (gwahanol glystyrau mewn gwahanol DCs), felly nid oes cyfyngiad o'r fath yno. Mae'r cynllun 12-2-2 yn darparu 33% o ddiswyddiadau, hynny yw, mae storio data yn rhatach, a gall hefyd oroesi hyd at 4 toriad disg ar yr un pryd, yn union fel y cynllun MDS.
Mae llawer mwy o nodweddion defnyddio codau diswyddo mewn systemau storio a phrosesu data: arlliwiau adfer data, effaith adferiad ar amser gweithredu ymholiad, nodweddion cofnodi data, ac ati. Byddaf yn siarad ar wahân am y rhain a nodweddion eraill defnyddio codau diswyddo yn ymarferol, os bydd y pwnc yn ddiddorol.
6. Cysylltiadau
- Cyfres o erthyglau am godau Reed-Solomon a meysydd Galois:
Maent yn edrych yn ddyfnach ar fathemateg mewn iaith hygyrch. - Erthygl gan Microsoft am LRC:
Mae Adran 2 yn esbonio'r ddamcaniaeth yn gryno ac yna'n trafod profiadau ymarferol gyda'r LRC. - Cynllun eilrif:
- Cynllun STAR:
- Codau pyramid:
- Codau diswyddo yn MDS:
- Codau diswyddo yn YT:
- Codau diswyddo yn YDB:
Ffynhonnell: hab.com