{"id":87758,"date":"2020-07-10T01:41:58","date_gmt":"2020-07-09T23:41:58","guid":{"rendered":"https:\/\/prohoster.info\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye"},"modified":"2020-07-10T01:41:58","modified_gmt":"2020-07-09T23:41:58","slug":"kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","status":"publish","type":"post","link":"https:\/\/prohoster.info\/sq\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"Kodet e tepric\u00ebs: me fjal\u00eb t\u00eb thjeshta se si t\u00eb ruani t\u00eb dh\u00ebnat n\u00eb m\u00ebnyr\u00eb t\u00eb besueshme dhe me kosto t\u00eb ul\u00ebt","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"Kodet<\/p>\n

<\/p>\n

K\u00ebshtu duket redundant\u00ebsia<\/em><\/p>\n

<\/p>\n

Kodet e redundant\u00ebsis\u00eb* p\u00ebrdoren gjer\u00ebsisht n\u00eb sistemet kompjuterike p\u00ebr t\u00eb rritur besueshm\u00ebrin\u00eb e ruajtjes s\u00eb t\u00eb dh\u00ebnave. N\u00eb Yandex, ato p\u00ebrdoren n\u00eb shum\u00eb projekte. P\u00ebr shembull, p\u00ebrdorimi i kodet e redundant\u00ebsis\u00eb n\u00eb vend t\u00eb replikimit n\u00eb magazin\u00ebn ton\u00eb t\u00eb brendshme t\u00eb objekteve kursen miliona pa ulur besueshm\u00ebrin\u00eb. Por, pavar\u00ebsisht p\u00ebrhapjes s\u00eb gjer\u00eb, p\u00ebrshkrimi i qart\u00eb i m\u00ebnyr\u00ebs se si funksionojn\u00eb kodet e redundant\u00ebsis\u00eb \u00ebsht\u00eb shum\u00eb i rrall\u00eb. Ata q\u00eb duan t\u00eb kuptojn\u00eb p\u00ebrballen me di\u00e7ka t\u00eb till\u00eb (nga Wikipedia<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

Emri im \u00ebsht\u00eb Vadim, n\u00eb Yandex merrem me zhvillimin e magazin\u00ebs s\u00eb brendshme t\u00eb objekteve MDS. N\u00eb k\u00ebt\u00eb artikull, do ta p\u00ebrshkruaj me fjal\u00eb t\u00eb thjeshta teorin\u00eb e kodet e redundant\u00ebsis\u00eb (kodet e Reed-Solomon dhe LRC). Do t\u00eb flas p\u00ebr m\u00ebnyr\u00ebn se si funksionon, pa matematik\u00eb t\u00eb komplikuar dhe terminologji t\u00eb rrall\u00eb. N\u00eb fund do t\u00eb jap shembuj t\u00eb p\u00ebrdorimit t\u00eb kodet e redundant\u00ebsis\u00eb n\u00eb Yandex.<\/p>\n

<\/p>\n

Nuk do t'i shqyrtoj n\u00eb detaje disa aspekte matematikore, por do t\u00eb ofroj lidhje p\u00ebr ata q\u00eb duan t\u00eb thellohen m\u00eb shum\u00eb. Gjithashtu do t\u00eb v\u00eb n\u00eb dukje se disa p\u00ebrkufizime matematikore mund t\u00eb mos jen\u00eb t\u00eb rrepta, pasi artikulli \u00ebsht\u00eb i destinuar p\u00ebr inxhinier\u00eb q\u00eb duan t\u00eb kuptojn\u00eb thelbin e \u00e7\u00ebshtjes.<\/p>\n

<\/p>\n

* N\u00eb literatur\u00ebn anglisht fol\u00ebse, kodet e redundant\u00ebsis\u00eb shpesh quhen erasure codes.<\/p>\n

<\/a><\/noindex><\/p>\n

1. Thelbi i kodet e redundant\u00ebsis\u00eb<\/h1>\n

<\/p>\n

Thelbi i t\u00eb gjith\u00eb kodet e redundant\u00ebsis\u00eb \u00ebsht\u00eb mjaft i thjesht\u00eb: t\u00eb ruash (apo t\u00eb transmetosh) t\u00eb dh\u00ebna n\u00eb m\u00ebnyr\u00eb q\u00eb ato t\u00eb mos humbasin n\u00eb rast t\u00eb gabimeve (thyerjeve t\u00eb disqeve, gabimeve n\u00eb transmetimin e t\u00eb dh\u00ebnave etj.). <\/p>\n

<\/p>\n

N\u00eb shumic\u00ebn* e kodet e redundant\u00ebsis\u00eb, t\u00eb dh\u00ebnat ndahen n\u00eb n blloqe t\u00eb dh\u00ebnash, p\u00ebr to llogariten m blloqe kodesh redundant\u00ebsie, gjithsej ndodhin n + m blloqe. Kodet e redundant\u00ebsis\u00eb nd\u00ebrtohen n\u00eb m\u00ebnyr\u00eb q\u00eb t\u00eb jet\u00eb e mundur rikuperimi i n blloqeve t\u00eb dh\u00ebnash duke p\u00ebrdorur vet\u00ebm nj\u00eb pjes\u00eb nga n + m blloqet. M\u00eb posht\u00eb do t\u00eb shqyrtojm\u00eb vet\u00ebm kodet e bllokut t\u00eb redundant\u00ebsis\u00eb, dometh\u00ebn\u00eb ato n\u00eb t\u00eb cilat t\u00eb dh\u00ebnat ndahen n\u00eb blloqe.<\/p>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

P\u00ebr t\u00eb rikuperuar t\u00eb gjith\u00eb n blloqet e t\u00eb dh\u00ebnave, nevojitet t\u00eb pakt\u00ebn n nga n + m blloqet, pasi nuk mund t\u00eb marr\u00ebsh n blloqe duke pasur vet\u00ebm n-1 bllok (n\u00eb k\u00ebt\u00eb rast do t\u00eb duhej t\u00eb merrnim 1 bllok 'nga ajri'). A jan\u00eb t\u00eb mjaftuesh\u00ebm n blloqe t\u00eb rast\u00ebsishme nga n + m blloqet p\u00ebr rikuperimin e t\u00eb dh\u00ebnave t\u00eb gjitha? Kjo varet nga lloji i kodit t\u00eb tepric\u00ebs, p\u00ebr shembull, kodet e Reed-Solomon lejojn\u00eb rikuperimin e t\u00eb dh\u00ebnave me n blloqe t\u00eb rast\u00ebsishme, nd\u00ebrsa kodet e tepric\u00ebs LRC - jo gjithmon\u00eb.<\/p>\n

<\/p>\n

Ruajtja e t\u00eb dh\u00ebnave<\/h3>\n

<\/p>\n

N\u00eb sistemet e ruajtjes s\u00eb t\u00eb dh\u00ebnave, zakonisht secili nga blloqet e t\u00eb dh\u00ebnave dhe blloqet e kodit t\u00eb tepric\u00ebs shkruhen n\u00eb nj\u00eb disk t\u00eb ve\u00e7ant\u00eb. At\u00ebher\u00eb, n\u00eb rastin e d\u00ebshtimit t\u00eb ndonj\u00eb disku, t\u00eb dh\u00ebnat fillestare mund t\u00eb rivendosen dhe t\u00eb lexohen ende. T\u00eb dh\u00ebnat mund t\u00eb rivendosen edhe kur disa disqe d\u00ebshtojn\u00eb nj\u00ebkoh\u00ebsisht.<\/p>\n

<\/p>\n

Transmetimi i t\u00eb dh\u00ebnave<\/h3>\n

<\/p>\n

Kodat e tepric\u00ebs mund t\u00eb p\u00ebrdoren p\u00ebr transmetimin e besuesh\u00ebm t\u00eb t\u00eb dh\u00ebnave n\u00eb nj\u00eb rrjet t\u00eb pasigurt. T\u00eb dh\u00ebnat e transmetuara ndahen n\u00eb blloqe, p\u00ebr t\u00eb cilat llogariten kodet e tepric\u00ebs. T\u00eb dh\u00ebnat dhe blloqet e kodet e tepric\u00ebs transmetohen p\u00ebrmes rrjetit. N\u00eb rast t\u00eb gabimeve n\u00eb blloqe t\u00eb rast\u00ebsishme (deri n\u00eb nj\u00eb num\u00ebr t\u00eb caktuar blloqesh), t\u00eb dh\u00ebnat ende mund t\u00eb transmetohen pa gabime p\u00ebrmes rrjetit. Kodet e Reed-Solomon, p\u00ebr shembull, p\u00ebrdoren p\u00ebr transmetimin e t\u00eb dh\u00ebnave p\u00ebrmes linjave optike dhe n\u00eb komunikimin satelitor.<\/p>\n

<\/p>\n

* Ka gjithashtu kode teprice, n\u00eb t\u00eb cilat t\u00eb dh\u00ebnat nuk ndahen n\u00eb blloqe, p\u00ebr shembull, kodet Hamming dhe kodet CRC, t\u00eb cilat jan\u00eb gjer\u00ebsisht t\u00eb aplikuara p\u00ebr transmetimin e t\u00eb dh\u00ebnave n\u00eb rrjetet Ethernet. K\u00ebto jan\u00eb kode p\u00ebr kodimin e q\u00ebndruesh\u00ebm ndaj shqet\u00ebsimeve, t\u00eb destinuara p\u00ebr zbuluar gabimet, por jo p\u00ebr t'i korigjuar ato (kode Hamming gjithashtu lejon korrigjimin e pjessh\u00ebm t\u00eb gabimeve).<\/p>\n

<\/p>\n

2. Kodat e Reed-Solomon<\/h1>\n

<\/p>\n

Kodat e Reed-Solomon jan\u00eb disa nga kodet e tepric\u00ebs m\u00eb t\u00eb p\u00ebrdorura, t\u00eb shpikura q\u00eb n\u00eb vitet 1960 dhe q\u00eb filluan t\u00eb p\u00ebrdoren gjer\u00ebsisht n\u00eb vitet 1980 p\u00ebr prodhimin serik t\u00eb disqeve t\u00eb kompakt.<\/p>\n

<\/p>\n

Dy pyetje ky\u00e7e p\u00ebr t\u00eb kuptuar kodet e Reed-Solomon jan\u00eb: 1) si t\u00eb krijojm\u00eb blloqet e kodit t\u00eb tepric\u00ebs; 2) si t\u00eb rikuperojm\u00eb t\u00eb dh\u00ebnat duke p\u00ebrdorur blloqet e kodit t\u00eb tepric\u00ebs. T\u00eb gjejm\u00eb p\u00ebrgjigjet p\u00ebr to.
\nP\u00ebr thjesht\u00ebsimin e m\u00ebtejsh\u00ebm, do t\u00eb supozojm\u00eb q\u00eb n=6 dhe m=4. Skemat e tjera shqyrtohen me analogji.<\/p>\n

<\/p>\n

Si t\u00eb krijojm\u00eb blloqet e kodit t\u00eb tepric\u00ebs<\/h3>\n

<\/p>\n

\u00c7do blok kodi t\u00eb tepric\u00ebs llogaritet n\u00eb m\u00ebnyr\u00eb t\u00eb pavarur nga t\u00eb tjer\u00ebt. P\u00ebr t\u00eb llogaritur \u00e7do blok p\u00ebrdoren t\u00eb gjith\u00eb n bloket e t\u00eb dh\u00ebnave. N\u00eb diagramin m\u00eb posht\u00eb, X1-X6 jan\u00eb bloket e t\u00eb dh\u00ebnave, P1\u2013P4 jan\u00eb bloket e kodeve t\u00eb tepric\u00ebs.<\/p>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

T\u00eb gjitha bloket e t\u00eb dh\u00ebnave duhet t\u00eb ken\u00eb t\u00eb nj\u00ebjt\u00ebn madh\u00ebsi, dhe p\u00ebr rreshtimin mund t\u00eb p\u00ebrdoren bit\u00ebr 0. Bloket e marra t\u00eb kodeve t\u00eb tepric\u00ebs do t\u00eb ken\u00eb t\u00eb nj\u00ebjt\u00ebn madh\u00ebsi si bloket e t\u00eb dh\u00ebnave. T\u00eb gjitha bloket e t\u00eb dh\u00ebnave ndahen n\u00eb fjal\u00eb (p.sh., nga 16 bit). Supozoni se i kemi ndar\u00eb bloket e t\u00eb dh\u00ebnave n\u00eb k fjal\u00eb. At\u00ebher\u00eb t\u00eb gjitha bloket e kodeve t\u00eb tepric\u00ebs gjithashtu do t\u00eb ndahen n\u00eb k fjal\u00eb.<\/p>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

P\u00ebr llogaritjen e fjal\u00ebs i-t\u00eb t\u00eb secilit blok t\u00eb tepric\u00ebs do t\u00eb p\u00ebrdoren fjal\u00ebt i-ta t\u00eb t\u00eb gjith\u00eb bloket e t\u00eb dh\u00ebnave. Ato do t\u00eb llogariten sipas formul\u00ebs s\u00eb m\u00ebposhtme:<\/p>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

K\u00ebtu vlerat x jan\u00eb fjal\u00ebt e bloket e t\u00eb dh\u00ebnave, p jan\u00eb fjal\u00ebt e bloket e kodeve t\u00eb tepric\u00ebs, t\u00eb gjitha alfa, beta, gamma dhe delta jan\u00eb numra t\u00eb ve\u00e7ant\u00eb t\u00eb zgjedhur, t\u00eb nj\u00ebjt\u00eb p\u00ebr t\u00eb gjith\u00eb i. Menj\u00ebher\u00eb duhet t\u00eb thuhet se t\u00eb gjitha k\u00ebto vlera nuk jan\u00eb numra t\u00eb zakonsh\u00ebm, por elemente t\u00eb fush\u00ebs s\u00eb Galuas, operacionet +, -, *, \/ jan\u00eb jo operacionet e njohura p\u00ebr ne, por operacione speciale t\u00eb futur mbi elementet e fush\u00ebs s\u00eb Galuas.<\/p>\n

<\/p>\n

P\u00ebrse nevojiten fushat e Galuas<\/h3>\n

<\/p>\n

\"Kodet<\/p>\n

<\/p>\n

Duket se \u00ebsht\u00eb e thjesht\u00eb: ndajm\u00eb t\u00eb dh\u00ebnat n\u00eb blloqe, blloqet n\u00eb fjal\u00eb, me ndihm\u00ebn e fjal\u00ebve t\u00eb bllokut t\u00eb t\u00eb dh\u00ebnave llogarisim fjal\u00ebt e bllokut t\u00eb kodeve t\u00eb tepric\u00ebs, k\u00ebshtu marrim blloqet e kodeve t\u00eb tepric\u00ebs. N\u00eb p\u00ebrgjith\u00ebsi, k\u00ebshtu funksionon, por djalli \u00ebsht\u00eb n\u00eb detaje:<\/p>\n

<\/p>\n

    \n
  1. Si\u00e7 u tha m\u00eb sip\u00ebr, madh\u00ebsia e fjal\u00ebs \u00ebsht\u00eb e fiksuar, n\u00eb shembullin ton\u00eb 16 bit. Formulat e m\u00ebsip\u00ebrme p\u00ebr kodet e Reed-Solomon jan\u00eb t\u00eb tilla, q\u00eb duke p\u00ebrdorur numra t\u00eb zakonsh\u00ebm t\u00eb plot\u00eb rezultati i llogaritjes p mund t\u00eb mos paraqitet me nj\u00eb fjal\u00eb t\u00eb pranueshme t\u00eb madh\u00ebsis\u00eb.<\/li>\n
  2. N\u00eb procesin e rikthimit t\u00eb t\u00eb dh\u00ebnave, formulat e m\u00ebsip\u00ebrme do t\u00eb trajtohen si nj\u00eb sistem ekuacionesh q\u00eb duhet zgjidhur p\u00ebr t\u00eb rikuperuar t\u00eb dh\u00ebnat. N\u00eb procesin e zgjidhjes mund t\u00eb ndodh\u00eb q\u00eb t\u00eb nevojitet t\u00eb kryhet ndarja e numrave t\u00eb plot\u00eb nga nj\u00ebri-tjetri, rezultati i s\u00eb cil\u00ebs do t\u00eb jet\u00eb nj\u00eb num\u00ebr real, i cili nuk mund t\u00eb paraqitet sakt\u00ebsisht n\u00eb memorien e kompjuterit.<\/li>\n<\/ol>\n

    <\/p>\n

    K\u00ebto probleme nuk lejojn\u00eb p\u00ebrdorimin e numrave t\u00eb plot\u00eb p\u00ebr kodet e Reed\u2013Solomon. Zgjidhja e problemeve \u00ebsht\u00eb origjinale dhe mund t\u00eb p\u00ebrshkruhet n\u00eb k\u00ebt\u00eb m\u00ebnyr\u00eb: le t\u00eb shpikim numra t\u00eb ve\u00e7ant\u00eb, t\u00eb cil\u00ebt mund t\u00eb paraqiten me fjal\u00eb t\u00eb gjat\u00eb (p.sh., 16 bit), dhe rezultati i t\u00eb gjitha operacioneve mbi ta (shtimi, zbritja, shum\u00ebzimi, ndarja) gjithashtu do t\u00eb p\u00ebrfaq\u00ebsohet n\u00eb memorien e kompjuterit me fjal\u00eb t\u00eb nevojshme gjat\u00ebsi.<\/p>\n

    <\/p>\n

    Numrat e till\u00eb \"t\u00eb ve\u00e7ant\u00eb\" jan\u00eb studiuar prej nj\u00eb koh\u00eb t\u00eb gjat\u00eb nga matematika, dhe ata quhen fush\u00eb. Nj\u00eb fush\u00eb \u00ebsht\u00eb nj\u00eb shum\u00ebsi elementesh me operacione t\u00eb caktuara p\u00ebr to t\u00eb shtimit, zbritjes, shum\u00ebzimit dhe ndarjes.<\/p>\n

    <\/p>\n

    Fushat e Galois* jan\u00eb fusha p\u00ebr t\u00eb cilat ekziston dhe \u00ebsht\u00eb unik rezultati i \u00e7do operacioni (+, -, *, \/) p\u00ebr \u00e7do dy elemente t\u00eb fush\u00ebs. Fushat e Galois mund t\u00eb nd\u00ebrtohen p\u00ebr numra q\u00eb jan\u00eb fuqia e 2: 2, 4, 8, 16 etj. (n\u00eb t\u00eb v\u00ebrtet\u00eb fuqia e \u00e7do numri t\u00eb thjesht\u00eb p, por n\u00eb praktik\u00eb na interesojn\u00eb vet\u00ebm fuqit\u00eb e 2). P\u00ebr shembull, p\u00ebr fjal\u00eb me madh\u00ebsi 16 bit, kjo fush\u00eb p\u00ebrmban 65,536 elemente, p\u00ebr \u00e7do \u00e7ift t\u00eb cil\u00ebve mund t\u00eb gjendet rezultati i \u00e7do operacioni (+, -, *, \/). Vlerat x, p, alpha, beta, gamma, delta nga ekuacionet m\u00eb lart p\u00ebr llogaritjet do t\u00eb konsiderohen elemente t\u00eb fush\u00ebs Galois.<\/p>\n

    <\/p>\n

    K\u00ebshtu, ne kemi nj\u00eb sistem ekuacionesh, me ndihm\u00ebn e t\u00eb cilave mund t\u00eb nd\u00ebrtojm\u00eb blloqe kodesh mbivend\u00ebsimi, duke shkruar nj\u00eb program kompjuterik p\u00ebrkat\u00ebs. Me k\u00ebt\u00eb sistem ekuacionesh, gjithashtu mund t\u00eb kryhet rikuperimi i t\u00eb dh\u00ebnave.<\/p>\n

    <\/p>\n

    * K\u00ebto nuk jan\u00eb nj\u00eb p\u00ebrkufizim strik, p\u00ebrkundrazi nj\u00eb p\u00ebrshkrim.<\/p>\n

    <\/p>\n

    Si t\u00eb rikuperoni t\u00eb dh\u00ebnat<\/h3>\n

    <\/p>\n

    Rikuperimi \u00ebsht\u00eb i nevojsh\u00ebm kur nga blloqet n + m, nj\u00eb pjes\u00eb e blloqeve mungon. K\u00ebto mund t\u00eb jen\u00eb si blloqe t\u00eb dh\u00ebnash ashtu edhe blloqe kodesh mbivend\u00ebsimi. Mungesa e blloqeve t\u00eb dh\u00ebnash dhe\/ose blloqeve t\u00eb kodit mbivend\u00ebsim do t\u00eb n\u00ebnkuptoj\u00eb se n\u00eb ekuacionet m\u00eb lart, variablat p\u00ebrkat\u00ebse x dhe\/ose p jan\u00eb t\u00eb panjohura.<\/p>\n

    <\/p>\n

    Ekuacionet p\u00ebr kodet Reed\u2013Solomon mund t\u00eb merren si nj\u00eb sistem ekuacionesh, ku t\u00eb gjitha vlerat alpha, beta, gamma, delta jan\u00eb konstanta, t\u00eb gjitha x dhe p, p\u00ebrkat\u00ebsisht blloqeve t\u00eb disponueshme, jan\u00eb variabla t\u00eb njohur, dhe x dhe p t\u00eb tjer\u00ebt jan\u00eb t\u00eb panjohur.<\/p>\n

    <\/p>\n

    P\u00ebr shembull, le t\u00eb supozojm\u00eb se blloqet e dh\u00ebnash 1, 2, 3 dhe blloku i kodit mbivend\u00ebsim 2 nuk jan\u00eb t\u00eb aksesuesh\u00ebm, at\u00ebher\u00eb p\u00ebr grupin e fjal\u00ebve i do t\u00eb ket\u00eb sistemin e m\u00ebposht\u00ebm t\u00eb ekuacioneve (t\u00eb panjohurat e sh\u00ebnuara me t\u00eb kuqe):<\/p>\n

    <\/p>\n

    \"Kodet<\/p>\n

    <\/p>\n

    Ne kemi nj\u00eb sistem me 4 ekuacione dhe 4 t\u00eb panjohura, pra mund ta zgjidhim dhe t\u00eb rikuperojm\u00eb t\u00eb dh\u00ebnat!<\/p>\n

    <\/p>\n

    Nga ky sistem ekuacionesh ndodhin disa p\u00ebrfundime p\u00ebr rikuperimin e t\u00eb dh\u00ebnave p\u00ebr kodet e Reed-Solomon (n blloqe t\u00eb dh\u00ebnash, m blloqe t\u00eb kodit t\u00eb tep\u00ebrt):<\/p>\n

    <\/p>\n