{"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\/cs\/blog\/administrirovanie\/kody-izbytochnosti-prostymi-slovami-o-tom-kak-nadyozhno-i-dyoshevo-hranit-dannye","title":{"rendered":"K\u00f3dy redundance: zjednodu\u0161en\u011b o tom, jak spolehliv\u011b a levn\u011b uchov\u00e1vat data","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

\"K\u00f3dy<\/p>\n

<\/p>\n

Takto vypad\u00e1 redundance<\/em><\/p>\n

<\/p>\n

K\u00f3dy redundance* se \u0161iroce pou\u017e\u00edvaj\u00ed v po\u010d\u00edta\u010dov\u00fdch syst\u00e9mech pro zv\u00fd\u0161en\u00ed spolehlivosti ukl\u00e1d\u00e1n\u00ed dat. V Yandexu se pou\u017e\u00edvaj\u00ed v mnoha projektech. Nap\u0159\u00edklad pou\u017eit\u00ed k\u00f3d\u016f redundance m\u00edsto replikace v na\u0161em intern\u00edm objektov\u00e9m \u00falo\u017ei\u0161ti \u0161et\u0159\u00ed miliony bez sn\u00ed\u017een\u00ed spolehlivosti. P\u0159esto je pochopiteln\u00e9 vysv\u011btlen\u00ed toho, jak k\u00f3dy redundance funguj\u00ed, velmi vz\u00e1cn\u00e9. Z\u00e1jemci se \u010dasto pot\u00fdkaj\u00ed s n\u00e1sleduj\u00edc\u00edm (z Wikipedie<\/a><\/noindex>):<\/p>\n

<\/p>\n

\"K\u00f3dy<\/p>\n

<\/p>\n

Jmenuji se Vadim, v Yandexu se zab\u00fdv\u00e1m v\u00fdvojem intern\u00edho objektov\u00e9ho \u00falo\u017ei\u0161t\u011b MDS. V tomto \u010dl\u00e1nku jednodu\u0161e pop\u00ed\u0161u teoretick\u00e9 z\u00e1klady k\u00f3d\u016f redundance (k\u00f3d\u016f Reed-Solomon a LRC). Vysv\u011btl\u00edm, jak to funguje, bez slo\u017eit\u00e9 matematiky a vz\u00e1cn\u00e9 terminologie. Na konci uvedu p\u0159\u00edklady pou\u017eit\u00ed k\u00f3d\u016f redundance v Yandexu.<\/p>\n

<\/p>\n

N\u011bkter\u00e9 matematick\u00e9 detaily nebudu podrobn\u011b rozeb\u00edrat, ale poskytnu odkazy pro ty, kte\u0159\u00ed se cht\u011bj\u00ed pono\u0159it hloub\u011bji. R\u00e1d bych tak\u00e9 poznamenal, \u017ee n\u011bkter\u00e9 matematick\u00e9 definice nemus\u00ed b\u00fdt striktn\u00ed, proto\u017ee \u010dl\u00e1nek nen\u00ed zam\u011b\u0159en na matematiky, ale na in\u017een\u00fdry, kte\u0159\u00ed cht\u011bj\u00ed pochopit podstatu probl\u00e9mu.<\/p>\n

<\/p>\n

* V anglicky mluv\u00edc\u00ed literatu\u0159e se k\u00f3dy redundance \u010dasto naz\u00fdvaj\u00ed erasure codes.<\/p>\n

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

1. Podstata k\u00f3d\u016f redundance<\/h1>\n

<\/p>\n

Podstata v\u0161ech k\u00f3d\u016f redundance je maxim\u00e1ln\u011b jednoduch\u00e1: uchov\u00e1vat (nebo p\u0159en\u00e1\u0161et) data tak, aby nezmizela p\u0159i vzniku chyb (poruch\u00e1ch disk\u016f, chyb\u00e1ch p\u0159enosu dat atd.). <\/p>\n

<\/p>\n

Ve v\u011bt\u0161in\u011b* k\u00f3d\u016f redundance jsou data rozd\u011blena na n blok\u016f, pro kter\u00e9 se po\u010d\u00edt\u00e1 m blok\u016f k\u00f3d\u016f redundance, celkem tedy vznikne n + m blok\u016f. K\u00f3dy redundance jsou konstruov\u00e1ny tak, aby bylo mo\u017en\u00e9 obnovit n blok\u016f dat, p\u0159i\u010dem\u017e je t\u0159eba pouze \u010d\u00e1st z n + m blok\u016f. D\u00e1le se budeme zab\u00fdvat pouze blokov\u00fdmi k\u00f3dy redundance, tedy takov\u00fdmi, kde jsou data rozd\u011blena na bloky.<\/p>\n

<\/p>\n

\"K\u00f3dy<\/p>\n

<\/p>\n

Aby obnovili v\u0161echna n datov\u00e9 bloky, je t\u0159eba m\u00edt alespo\u0148 n z n + m blok\u016f, proto\u017ee nen\u00ed mo\u017en\u00e9 z\u00edskat n blok\u016f, pokud m\u00e1te pouze n-1 blok (v takov\u00e9m p\u0159\u00edpad\u011b byste museli 1 blok vz\u00edt z \u00abvzduchu\u00bb). Sta\u010d\u00ed n libovoln\u00fdch blok\u016f z n + m blok\u016f k obnoven\u00ed v\u0161ech dat? To z\u00e1vis\u00ed na typu redundatn\u00edch k\u00f3d\u016f, nap\u0159\u00edklad Reed-Solomonovy k\u00f3dy umo\u017e\u0148uj\u00ed obnovit v\u0161echna data pomoc\u00ed libovoln\u00fdch n blok\u016f, zat\u00edmco LRC redundatn\u00ed k\u00f3dy to ne v\u017edy umo\u017e\u0148uj\u00ed.<\/p>\n

<\/p>\n

Ukl\u00e1d\u00e1n\u00ed dat<\/h3>\n

<\/p>\n

V syst\u00e9mech pro ukl\u00e1d\u00e1n\u00ed dat jsou obvykle ka\u017ed\u00fd z blok\u016f dat a bloky redundatn\u00edch k\u00f3d\u016f zapisov\u00e1ny na jednotliv\u00e9 disky. Pak p\u0159i poru\u0161e libovoln\u00e9ho disku je mo\u017en\u00e9 z\u00e1kladn\u00ed data st\u00e1le obnovit a p\u0159e\u010d\u00edst. Data lze obnovit i p\u0159i soub\u011b\u017en\u00e9m selh\u00e1n\u00ed v\u00edce disk\u016f.<\/p>\n

<\/p>\n

P\u0159enos dat<\/h3>\n

<\/p>\n

Redundatn\u00ed k\u00f3dy lze pou\u017e\u00edt pro spolehliv\u00fd p\u0159enos dat v nespolehliv\u00e9 s\u00edti. P\u0159en\u00e1\u0161en\u00e1 data se d\u011bl\u00ed na bloky a pro n\u011b se po\u010d\u00edtaj\u00ed redundatn\u00ed k\u00f3dy. P\u0159es s\u00ed\u0165 se p\u0159en\u00e1\u0161ej\u00ed jak bloky dat, tak bloky redundatn\u00edch k\u00f3d\u016f. P\u0159i vzniku chyb v libovoln\u00fdch bloc\u00edch (a\u017e do ur\u010dit\u00e9ho po\u010dtu blok\u016f) lze data i tak bezchybn\u011b p\u0159en\u00e9st po s\u00edti. Reed-Solomonovy k\u00f3dy se nap\u0159\u00edklad pou\u017e\u00edvaj\u00ed pro p\u0159enos dat po optick\u00fdch link\u00e1ch a v satelitn\u00ed komunikaci.<\/p>\n

<\/p>\n

* Existuj\u00ed tak\u00e9 redundatn\u00ed k\u00f3dy, kde se data ned\u011bl\u00ed na bloky, nap\u0159\u00edklad Hammingovy k\u00f3dy a CRC k\u00f3dy, kter\u00e9 jsou \u0161iroce aplikov\u00e1ny pro p\u0159enos dat v s\u00edt\u00edch Ethernet. Jsou to k\u00f3dy pro k\u00f3dov\u00e1n\u00ed odoln\u00e9 v\u016f\u010di poruch\u00e1m, kter\u00e9 slou\u017e\u00ed k detekci chyb, nikoliv k jejich oprav\u011b (Hamming\u016fv k\u00f3d tak\u00e9 umo\u017e\u0148uje \u010d\u00e1ste\u010dnou opravu chyb).<\/p>\n

<\/p>\n

2. Reed-Solomonovy k\u00f3dy<\/h1>\n

<\/p>\n

Reed-Solomonovy k\u00f3dy jsou jedny z nejroz\u0161\u00ed\u0159en\u011bj\u0161\u00edch redundatn\u00edch k\u00f3d\u016f, kter\u00e9 byly vynalezeny u\u017e v 60. letech a poprv\u00e9 se \u0161iroce pou\u017e\u00edvaly v 80. letech p\u0159i s\u00e9riov\u00e9 v\u00fdrob\u011b kompaktn\u00edch disk\u016f.<\/p>\n

<\/p>\n

Dva kl\u00ed\u010dov\u00e9 ot\u00e1zky pro pochopen\u00ed Reed-Solomonov\u00fdch k\u00f3d\u016f jsou: 1) jak vytv\u00e1\u0159et bloky redundatn\u00edch k\u00f3d\u016f; 2) jak obnovit data pomoc\u00ed blok\u016f redundatn\u00edch k\u00f3d\u016f. Najdeme na n\u011b odpov\u011bdi.
\nAbychom to zjednodu\u0161ili, budeme d\u00e1le p\u0159edpokl\u00e1dat, \u017ee n=6 a m=4. Ostatn\u00ed sch\u00e9mata se posuzuj\u00ed analogicky.<\/p>\n

<\/p>\n

Jak vytv\u00e1\u0159et bloky redundatn\u00edch k\u00f3d\u016f<\/h3>\n

<\/p>\n

Ka\u017ed\u00fd blok k\u00f3d\u016f redundance se pova\u017euje za nez\u00e1visl\u00fd na ostatn\u00edch. Pro v\u00fdpo\u010det ka\u017ed\u00e9ho bloku se pou\u017e\u00edv\u00e1 v\u0161ech n blok\u016f dat. Na sch\u00e9matu n\u00ed\u017ee X1-X6 jsou bloky dat, P1\u2013P4 jsou bloky k\u00f3d\u016f redundance.<\/p>\n

<\/p>\n

\"K\u00f3dy<\/p>\n

<\/p>\n

V\u0161echny bloky dat mus\u00ed m\u00edt stejnou velikost, pro zarovn\u00e1n\u00ed je mo\u017en\u00e9 pou\u017e\u00edt nulov\u00e9 bity. Z\u00edskan\u00e9 bloky k\u00f3d\u016f redundance budou m\u00edt stejnou velikost jako bloky dat. V\u0161echny bloky dat se d\u011bl\u00ed na slova (nap\u0159\u00edklad po 16 bitech). P\u0159edpokl\u00e1dejme, \u017ee jsme rozd\u011blili bloky dat na k slov. Pot\u00e9 budou v\u0161echny bloky k\u00f3d\u016f redundance tak\u00e9 rozd\u011bleny na k slov.<\/p>\n

<\/p>\n

\"K\u00f3dy<\/p>\n

<\/p>\n

Pro v\u00fdpo\u010det i-t\u00e9ho slova ka\u017ed\u00e9ho bloku redundance se pou\u017eij\u00ed i-t\u00e1 slova v\u0161ech blok\u016f dat. Ta se spo\u010d\u00edtaj\u00ed podle n\u00e1sleduj\u00edc\u00edho vzorce:<\/p>\n

<\/p>\n

\"K\u00f3dy<\/p>\n

<\/p>\n

Zde hodnoty x p\u0159edstavuj\u00ed slova blok\u016f dat, p p\u0159edstavuj\u00ed slova blok\u016f k\u00f3d\u016f redundance, v\u0161echny alfa, beta, gamma a delta jsou speci\u00e1ln\u011b vybran\u00e1 \u010d\u00edsla, kter\u00e1 jsou stejn\u00e1 pro v\u0161echna i. Je nutn\u00e9 \u0159\u00edci, \u017ee v\u0161echny tyto hodnoty nejsou b\u011b\u017en\u00e1 \u010d\u00edsla, ale prvky Galoisova pole, operace +, -, *, \/ \u2013 nejsou to obvykl\u00e9 operace, jak je zn\u00e1me, ale speci\u00e1ln\u00ed operace zaveden\u00e9 nad prvky Galoisova pole.<\/p>\n

<\/p>\n

Pro\u010d jsou pot\u0159eba Galoisova pole<\/h3>\n

<\/p>\n

\"K\u00f3dy<\/p>\n

<\/p>\n

Na prvn\u00ed pohled to vypad\u00e1 jednodu\u0161e: rozd\u011bl\u00edme data na bloky, bloky na slova, a pomoc\u00ed slov blok\u016f dat spo\u010d\u00edt\u00e1me slova blok\u016f k\u00f3d\u016f redundance \u2013 z\u00edsk\u00e1me bloky k\u00f3d\u016f redundance. Celkov\u011b to tak funguje, ale \u010dert je v detailech:<\/p>\n

<\/p>\n

    \n
  1. Jak je uvedeno v\u00fd\u0161e, velikost slova je fixn\u00ed, v na\u0161em p\u0159\u00edkladu 16 bit\u016f. Vzorce v\u00fd\u0161e pro k\u00f3dy Reed-Solomon jsou takov\u00e9, \u017ee p\u0159i pou\u017eit\u00ed b\u011b\u017en\u00fdch cel\u00fdch \u010d\u00edsel m\u016f\u017ee b\u00fdt v\u00fdsledek v\u00fdpo\u010dtu p nep\u0159edstaviteln\u00fd pomoc\u00ed slova povolen\u00e9 velikosti.<\/li>\n
  2. P\u0159i obnov\u011b dat budou v\u00fd\u0161e uveden\u00e9 vzorce pova\u017eov\u00e1ny za soustavu rovnic, kterou je t\u0159eba vy\u0159e\u0161it pro obnoven\u00ed dat. P\u0159i \u0159e\u0161en\u00ed se m\u016f\u017ee objevit pot\u0159eba prov\u00e9st d\u011blen\u00ed cel\u00fdch \u010d\u00edsel mezi sebou, jeho\u017e v\u00fdsledkem bude re\u00e1ln\u00e9 \u010d\u00edslo, kter\u00e9 nelze p\u0159esn\u011b reprezentovat v po\u010d\u00edta\u010dov\u00e9 pam\u011bti.<\/li>\n<\/ol>\n

    <\/p>\n

    Tyto probl\u00e9my br\u00e1n\u00ed pou\u017eit\u00ed cel\u00fdch \u010d\u00edsel pro Reed-Solomonovy k\u00f3dy. \u0158e\u0161en\u00ed probl\u00e9mu je origin\u00e1ln\u00ed a lze ho popsat takto: vymysleme speci\u00e1ln\u00ed \u010d\u00edsla, kter\u00e1 lze reprezentovat pomoc\u00ed slov pot\u0159ebn\u00e9 d\u00e9lky (nap\u0159\u00edklad 16 bit\u016f), a v\u00fdsledek v\u0161ech operac\u00ed prov\u00e1d\u011bn\u00fdch s nimi (s\u010d\u00edt\u00e1n\u00ed, od\u010d\u00edt\u00e1n\u00ed, n\u00e1soben\u00ed, d\u011blen\u00ed) bude tak\u00e9 reprezentov\u00e1n v po\u010d\u00edta\u010dov\u00e9 pam\u011bti pomoc\u00ed slov pot\u0159ebn\u00e9 d\u00e9lky.<\/p>\n

    <\/p>\n

    Takov\u00e1 \"speci\u00e1ln\u00ed\" \u010d\u00edsla ji\u017e dlouho zkoum\u00e1 matematika a naz\u00fdvaj\u00ed se poli. Pole je mno\u017eina prvk\u016f se specifick\u00fdmi operacemi s\u010d\u00edt\u00e1n\u00ed, od\u010d\u00edt\u00e1n\u00ed, n\u00e1soben\u00ed a d\u011blen\u00ed.<\/p>\n

    <\/p>\n

    Galoisova pole* jsou pole, pro kter\u00e1 existuje a je jedine\u010dn\u00fd v\u00fdsledek ka\u017ed\u00e9 operace (+, -, *, \/) pro libovoln\u00e9 dva prvky pole. Galoisova pole lze sestavit pro \u010d\u00edsla, kter\u00e1 jsou mocninami 2: 2, 4, 8, 16 atd. (ve skute\u010dnosti mocninami jak\u00e9hokoli prvo\u010d\u00edsla p, ale v praxi n\u00e1s zaj\u00edmaj\u00ed pouze mocniny 2). Nap\u0159\u00edklad pro slova o velikosti 16 bit\u016f je toto pole, kter\u00e9 obsahuje 65 536 prvk\u016f, pro ka\u017edou dvojici kter\u00fdch lze nal\u00e9zt v\u00fdsledek libovoln\u00e9 operace (+, -, *, \/). Hodnoty x, p, alfa, beta, gama, delta v uveden\u00fdch rovnic\u00edch pro v\u00fdpo\u010dty budou pova\u017eov\u00e1ny za prvky Galoisova pole.<\/p>\n

    <\/p>\n

    T\u00edmto zp\u016fsobem m\u00e1me soustavu rovnic, pomoc\u00ed kter\u00e9 lze sestavit bloky k\u00f3d\u016f redundance naps\u00e1n\u00edm odpov\u00eddaj\u00edc\u00ed po\u010d\u00edta\u010dov\u00e9 programy. Pomoc\u00ed t\u00e9to soustavy rovnic lze tak\u00e9 prov\u00e9st obnoven\u00ed dat.<\/p>\n

    <\/p>\n

    * To nen\u00ed striktn\u00ed definice, sp\u00ed\u0161e popis.<\/p>\n

    <\/p>\n

    Jak obnovit data<\/h3>\n

    <\/p>\n

    Obnoven\u00ed je pot\u0159eba, kdy\u017e z n + m blok\u016f chyb\u00ed \u010d\u00e1st blok\u016f. M\u016f\u017ee se jednat jak o bloky dat, tak o bloky k\u00f3d\u016f redundance. Chyb\u011bj\u00edc\u00ed bloky dat a\/nebo bloky k\u00f3d\u016f redundance budou znamenat, \u017ee v uveden\u00fdch rovnic\u00edch jsou nezn\u00e1m\u00e9 p\u0159\u00edslu\u0161n\u00e9 prom\u011bnn\u00e9 x a\/nebo p.<\/p>\n

    <\/p>\n

    Rovnice pro Reed-Solomonovy k\u00f3dy lze pova\u017eovat za soustavu rovnic, v n\u00ed\u017e jsou v\u0161echny hodnoty alfa, beta, gama, delta konstanty, v\u0161echny x a p odpov\u00eddaj\u00edc\u00ed dostupn\u00fdm blok\u016fm jsou zn\u00e1m\u00e9 prom\u011bnn\u00e9, a ostatn\u00ed x a p jsou nezn\u00e1m\u00e9.<\/p>\n

    <\/p>\n

    Nap\u0159\u00edklad, pokud jsou bloky dat 1, 2, 3 a blok k\u00f3d\u016f redundance 2 nedostupn\u00e9, pak pro i-tou skupinu slov bude n\u00e1sleduj\u00edc\u00ed soustava rovnic (nezn\u00e1m\u00e9 ozna\u010deny \u010derven\u011b):<\/p>\n

    <\/p>\n

    \"K\u00f3dy<\/p>\n

    <\/p>\n

    M\u00e1me syst\u00e9m \u010dty\u0159 rovnic se \u010dty\u0159mi nezn\u00e1m\u00fdmi, co\u017e znamen\u00e1, \u017ee jej m\u016f\u017eeme vy\u0159e\u0161it a obnovit data!<\/p>\n

    <\/p>\n

    Z tohoto syst\u00e9mu rovnic vypl\u00fdv\u00e1 \u0159ada z\u00e1v\u011br\u016f o obnov\u011b dat pro k\u00f3dy Reed-Solomon (n blok\u016f dat, m blok\u016f redundance):<\/p>\n

    <\/p>\n