Ահա թե ինչ տեսք ունի ավելորդությունը

Ավելորդության կոդերը* լայնորեն օգտագործվում են համակարգչային համակարգերում՝ տվյալների պահպանման հուսալիությունը բարձրացնելու համար: Yandex-ում դրանք օգտագործվում են բազմաթիվ նախագծերում։ Օրինակ, մեր ներքին օբյեկտների պահեստում կրկնօրինակման փոխարեն ավելորդության կոդերի օգտագործումը խնայում է միլիոններ՝ չվնասելով հուսալիությունը: Բայց չնայած դրանց լայն տարածմանը, շատ հազվադեպ են լինում հստակ նկարագրություններ, թե ինչպես են աշխատում ավելորդության կոդերը: Նրանք, ովքեր ցանկանում են հասկանալ, բախվում են մոտավորապես հետևյալի հետ (ից Վիքիպեդիա):

Իմ անունը Վադիմ է, Yandex-ում ես մշակում եմ ներքին օբյեկտների պահպանման MDS: Այս հոդվածում ես պարզ բառերով նկարագրելու եմ ավելորդության կոդերի տեսական հիմքերը (Reed-Solomon և LRC կոդերը): Ես ձեզ կասեմ, թե ինչպես է այն աշխատում, առանց բարդ մաթեմատիկայի և հազվագյուտ տերմինների: Վերջում ես կտամ Yandex-ում ավելորդության կոդերի օգտագործման օրինակներ։

Մի շարք մաթեմատիկական մանրամասներ մանրամասն չեմ դիտարկի, բայց հղումներ կտամ նրանց համար, ովքեր ցանկանում են խորանալ։ Նշեմ նաև, որ որոշ մաթեմատիկական սահմանումներ կարող են խիստ չլինել, քանի որ հոդվածը նախատեսված է ոչ թե մաթեմատիկոսների, այլ ինժեներների համար, ովքեր ցանկանում են հասկանալ հարցի էությունը։

* Անգլալեզու գրականության մեջ ավելորդության կոդերը հաճախ կոչվում են ջնջման կոդեր:

1. Ավելորդության կոդերի էությունը

Բոլոր ավելորդության կոդերի էությունը չափազանց պարզ է. պահեք (կամ փոխանցեք) տվյալները, որպեսզի դրանք չկորչեն սխալների դեպքում (սկավառակի ձախողումներ, տվյալների փոխանցման սխալներ և այլն):

* Ավելորդության կոդերի մեծ մասում տվյալները բաժանվում են n տվյալների բլոկների, որոնց համար հաշվվում են ավելորդության կոդերի m բլոկներ, ինչը հանգեցնում է ընդհանուր n + m բլոկների: Ավելորդության կոդերը կառուցված են այնպես, որ տվյալների n բլոկները կարող են վերականգնվել՝ օգտագործելով n + m բլոկների միայն մի մասը: Հաջորդը, մենք կքննարկենք միայն բլոկի ավելորդության կոդերը, այսինքն, նրանք, որոնցում տվյալները բաժանված են բլոկների:

Տվյալների բոլոր n բլոկները վերականգնելու համար դուք պետք է ունենաք n + m բլոկներից առնվազն n, քանի որ դուք չեք կարող ստանալ n բլոկ՝ ունենալով միայն n-1 բլոկ (այս դեպքում, դուք պետք է վերցնեք 1 բլոկ «բարակից»: օդ»): Արդյո՞ք n + m բլոկների n պատահական բլոկները բավարար են բոլոր տվյալները վերականգնելու համար: Սա կախված է ավելորդության կոդերի տեսակից, օրինակ՝ Reed-Solomon կոդերը թույլ են տալիս վերականգնել բոլոր տվյալները՝ օգտագործելով կամայական n բլոկներ, սակայն LRC ավելորդության կոդերը ոչ միշտ են անում:

Տվյալների պահպանում

Տվյալների պահպանման համակարգերում, որպես կանոն, տվյալների բլոկներից և ավելորդ կոդերի բլոկներից յուրաքանչյուրը գրվում է առանձին սկավառակի վրա: Այնուհետև, եթե կամայական սկավառակը ձախողվի, սկզբնական տվյալները դեռ կարող են վերականգնվել և կարդալ: Տվյալները կարող են վերականգնվել, նույնիսկ եթե մի քանի սկավառակներ միաժամանակ ձախողվեն:

Տվյալների փոխանցում

Ավելորդության կոդերը կարող են օգտագործվել տվյալների հուսալի փոխանցման համար անվստահելի ցանցով: Փոխանցված տվյալները բաժանվում են բլոկների, և դրանց համար հաշվարկվում են ավելորդության կոդերը։ Ինչպես տվյալների բլոկները, այնպես էլ ավելորդության կոդի բլոկները փոխանցվում են ցանցով: Եթե ​​սխալներ են տեղի ունենում կամայական բլոկներում (մինչև որոշակի թվով բլոկներ), տվյալները դեռ կարող են առանց սխալի փոխանցվել ցանցով: Reed-Solomon ծածկագրերը, օրինակ, օգտագործվում են օպտիկական կապի գծերով և արբանյակային հաղորդակցություններում տվյալների փոխանցման համար:

* Կան նաև ավելորդության կոդեր, որոնցում տվյալները բաժանված չեն բլոկների, ինչպիսիք են Համինգի կոդերը և CRC կոդերը, որոնք լայնորեն օգտագործվում են Ethernet ցանցերում տվյալների փոխանցման համար: Սրանք սխալները շտկող կոդավորման կոդեր են, դրանք նախատեսված են սխալները հայտնաբերելու և ոչ թե դրանք շտկելու համար (Համինգ կոդը թույլ է տալիս նաև սխալների մասնակի ուղղում):

2. Ռիդ-Սողոմոն ծածկագրեր

Reed-Solomon ծածկագրերը ամենալայն կիրառվող ավելորդության կոդերից են, որոնք հայտնագործվել են դեռևս 1960-ականներին և առաջին անգամ լայնորեն օգտագործվել 1980-ականներին կոմպակտ սկավառակների զանգվածային արտադրության համար:

Ռիդ-Սողոմոնի ծածկագրերը հասկանալու համար երկու հիմնական հարց կա. 1) ինչպես ստեղծել ավելորդության կոդերի բլոկներ. 2) ինչպես վերականգնել տվյալները՝ օգտագործելով ավելորդ կոդերի բլոկները: Գտնենք դրանց պատասխանները։
Պարզության համար մենք այնուհետև կենթադրենք, որ n=6 և m=4: Այլ սխեմաներ դիտարկվում են անալոգիայով:

Ինչպես ստեղծել ավելորդ կոդերի բլոկներ

Ավելորդության կոդերի յուրաքանչյուր բլոկ հաշվվում է մյուսներից անկախ: Բոլոր n տվյալների բլոկները օգտագործվում են յուրաքանչյուր բլոկը հաշվելու համար: Ստորև բերված գծապատկերում X1-X6-ը տվյալների բլոկներ են, P1-P4-ը՝ ավելորդության կոդերի բլոկներ:

Բոլոր տվյալների բլոկները պետք է լինեն նույն չափի, և զրոյական բիթերը կարող են օգտագործվել հավասարեցման համար: Ստացված ավելորդության կոդի բլոկները կունենան նույն չափը, ինչ տվյալների բլոկները: Բոլոր տվյալների բլոկները բաժանված են բառերի (օրինակ, 16 բիթ): Ենթադրենք տվյալների բլոկները բաժանել ենք k բառերի: Այնուհետև ավելորդության կոդերի բոլոր բլոկները նույնպես կբաժանվեն k բառերի:

Յուրաքանչյուր ավելորդության բլոկի i-րդ բառը հաշվելու համար կօգտագործվեն տվյալների բոլոր բլոկների i-րդ բառերը: Դրանք հաշվարկվելու են հետևյալ բանաձևով.

Այստեղ x արժեքները տվյալների բլոկների բառերն են, p-ն ավելորդ կոդերի բլոկների բառերն են, բոլոր ալֆա, բետա, գամմա և դելտան հատուկ ընտրված թվեր են, որոնք նույնն են բոլոր i-ի համար: Անմիջապես պետք է ասել, որ այս բոլոր արժեքները սովորական թվեր չեն, այլ Galois դաշտի տարրեր; +, -, *, / գործողությունները բոլորիս ծանոթ գործողություններ չեն, այլ Galois-ի տարրերի վրա ներդրված հատուկ գործողություններ: դաշտ.

Ինչու են անհրաժեշտ Գալուայի դաշտերը:

Թվում է, թե ամեն ինչ պարզ է. մենք տվյալները բաժանում ենք բլոկների, բլոկները՝ բառերի, օգտագործելով տվյալների բլոկների բառերը՝ հաշվում ենք ավելորդության կոդերի բլոկների բառերը. մենք ստանում ենք ավելորդության կոդերի բլոկներ։ Ընդհանուր առմամբ դա այդպես է աշխատում, բայց սատանան մանրամասների մեջ է.

1. Ինչպես նշվեց վերևում, բառի չափը ամրագրված է, մեր օրինակում 16 բիթ: Reed-Solomon ծածկագրերի վերը նշված բանաձևերն այնպիսին են, որ սովորական ամբողջ թվեր օգտագործելիս p-ի հաշվարկի արդյունքը կարող է չներկայանալ վավեր չափի բառի միջոցով:
2. Տվյալները վերականգնելիս վերը նշված բանաձևերը կդիտարկվեն որպես հավասարումների համակարգ, որը պետք է լուծվի՝ տվյալները վերականգնելու համար: Լուծման գործընթացում կարող է անհրաժեշտ լինել ամբողջ թվերը միմյանց վրա բաժանել, ինչի արդյունքում ստացվում է իրական թիվ, որը հնարավոր չէ ճշգրիտ ներկայացնել համակարգչային հիշողության մեջ:

Այս խնդիրները կանխում են Reed-Solomon կոդերի համար ամբողջ թվերի օգտագործումը: Խնդրի լուծումը օրիգինալ է, այն կարելի է նկարագրել այսպես. եկեք գտնենք հատուկ թվեր, որոնք կարելի է ներկայացնել՝ օգտագործելով պահանջվող երկարության բառերը (օրինակ՝ 16 բիթ), և այն բոլոր գործողությունների կատարման արդյունքը, որոնց վրա (ավելացում) , հանում, բազմապատկում, բաժանում) կներկայացվի նաև համակարգչային հիշողության մեջ՝ օգտագործելով պահանջվող երկարության բառերը։

Նման «հատուկ» թվերը մաթեմատիկայում վաղուց են ուսումնասիրվել, դրանք կոչվում են դաշտեր։ Դաշտը տարրերի մի շարք է, որոնց համար սահմանված են գումարում, հանում, բազմապատկում և բաժանում:

Galois* դաշտերը դաշտեր են, որոնց համար յուրաքանչյուր գործողության եզակի արդյունք կա (+, -, *, /) դաշտի ցանկացած երկու տարրի համար։ Galois դաշտերը կարող են կառուցվել 2-ի հզորություններ ունեցող թվերի համար. Օրինակ, 2-բիթանոց բառերի համար սա 4 տարր պարունակող դաշտ է, որի յուրաքանչյուր զույգի համար կարող եք գտնել ցանկացած գործողության արդյունք (+, -, *, /): Վերը նշված հավասարումներից x, p, ալֆա, բետա, գամմա, դելտայի արժեքները հաշվարկների համար համարվելու են Galois դաշտի տարրեր:

Այսպիսով, մենք ունենք հավասարումների համակարգ, որով մենք կարող ենք կառուցել ավելորդության կոդերի բլոկներ՝ գրելով համապատասխան համակարգչային ծրագիր։ Օգտագործելով նույն հավասարումների համակարգը, կարող եք կատարել տվյալների վերականգնում:

* Սա խիստ սահմանում չէ, այլ ավելի շուտ նկարագրություն:

Ինչպես վերականգնել տվյալները

Վերականգնումն անհրաժեշտ է, երբ n + m բլոկներից մի քանիսը բացակայում են: Սրանք կարող են լինել ինչպես տվյալների բլոկներ, այնպես էլ ավելորդ կոդերի բլոկներ: Տվյալների բլոկների և/կամ ավելորդության կոդերի բլոկների բացակայությունը կնշանակի, որ համապատասխան x և/կամ p փոփոխականները վերը նշված հավասարումներում անհայտ են:

Reed-Solomon ծածկագրերի հավասարումները կարող են դիտվել որպես հավասարումների համակարգ, որտեղ բոլոր ալֆա, բետա, գամմա, դելտա արժեքները հաստատուններ են, առկա բլոկներին համապատասխանող բոլոր x և p-ը հայտնի փոփոխականներ են, իսկ մնացած x և p. անհայտ են։

Օրինակ, թող տվյալների բլոկները 1, 2, 3 և ավելորդության կոդի բլոկ 2 անհասանելի լինեն, ապա i-րդ խմբի բառերի համար կլինի հետևյալ հավասարումների համակարգը (անհայտները նշված են կարմիրով).

Մենք ունենք 4 հավասարումների համակարգ 4 անհայտներով, ինչը նշանակում է, որ մենք կարող ենք լուծել այն և վերականգնել տվյալները:

Այս հավասարումների համակարգից հետևում են մի շարք եզրակացություններ Reed-Solomon կոդերի տվյալների վերականգնման վերաբերյալ (n տվյալների բլոկներ, m ավելորդության կոդերի բլոկներ).

• Տվյալները կարող են վերականգնվել, եթե որևէ մ բլոկ կամ ավելի քիչ կորչեն: Եթե ​​m+1 կամ ավելի բլոկներ կորչեն, ապա տվյալները չեն կարող վերականգնվել՝ անհնար է լուծել m հավասարումների համակարգը m + 1 անհայտներով։
• Անգամ մեկ տվյալների բլոկ վերականգնելու համար անհրաժեշտ է օգտագործել մնացած բլոկներից ցանկացած n, և կարող եք օգտագործել ավելորդության ցանկացած կոդ:

Էլ ի՞նչ է պետք իմանալ

Վերևի նկարագրության մեջ ես խուսափում եմ մի շարք կարևոր խնդիրներից, որոնք պահանջում են ավելի խորը մաթեմատիկայի ուսումնասիրություն: Մասնավորապես, ես ոչինչ չեմ ասում հետևյալի մասին.

• Ռիդ-Սողոմոնի ծածկագրերի հավասարումների համակարգը պետք է ունենա (եզակի) լուծում անհայտների ցանկացած համակցության համար (ոչ ավելի, քան m անհայտներ): Այս պահանջի հիման վրա ընտրվում են ալֆա, բետա, գամմա և դելտայի արժեքները:
• Հավասարումների համակարգը պետք է կարողանա ինքնաբերաբար կառուցվել (կախված նրանից, թե որ բլոկներն են անհասանելի) և լուծել:
• Մենք պետք է կառուցենք Galois դաշտը. տվյալ բառի չափի համար կարողանանք գտնել ցանկացած գործողության արդյունք (+, -, *, /) ցանկացած երկու տարրի համար։

Հոդվածի վերջում կան հղումներ գրականության այս կարևոր հարցերի վերաբերյալ:

n-ի և m-ի ընտրություն

Ինչպե՞ս ընտրել n և m գործնականում: Գործնականում տվյալների պահպանման համակարգերում ավելորդության կոդերը օգտագործվում են տարածք խնայելու համար, ուստի m-ը միշտ ընտրվում է n-ից պակաս: Նրանց հատուկ արժեքները կախված են մի շարք գործոններից, ներառյալ.

• Տվյալների պահպանման հուսալիություն: Որքան մեծ է m, այնքան մեծ է սկավառակի խափանումների թիվը, որոնք կարող են պահպանվել, այսինքն, այնքան բարձր է հուսալիությունը:
• Ավելորդ պահեստավորում: Որքան բարձր լինի m/n հարաբերակցությունը, այնքան մեծ կլինի պահեստավորման ավելորդությունը, և այնքան թանկ կլինի համակարգը:
• Հայտի մշակման ժամանակը: Որքան մեծ լինի n + m գումարը, այնքան ավելի երկար կլինի հարցումներին պատասխանելու ժամանակը: Քանի որ տվյալների ընթերցման համար (վերականգնման ընթացքում) պահանջվում է կարդալ n տարբեր սկավառակների վրա պահված n բլոկ, ընթերցման ժամանակը որոշվելու է ամենադանդաղ սկավառակով:

Բացի այդ, տվյալների պահպանումը մի քանի DC-ներում լրացուցիչ սահմանափակումներ է դնում n-ի և m-ի ընտրության վրա. եթե 1 DC-ն անջատված է, տվյալները դեռ պետք է հասանելի լինեն ընթերցման համար: Օրինակ, 3 DC-ում տվյալները պահելու ժամանակ պետք է կատարվի հետևյալ պայմանը՝ m >= n/2, հակառակ դեպքում կարող է լինել իրավիճակ, երբ 1 DC-ն անջատելու դեպքում տվյալները անհասանելի են կարդալու համար:

3. LRC - Տեղական վերակառուցման ծածկագրեր

Reed-Solomon ծածկագրերի միջոցով տվյալները վերականգնելու համար դուք պետք է օգտագործեք n կամայական տվյալների բլոկներ: Սա շատ էական թերություն է բաշխված տվյալների պահպանման համակարգերի համար, քանի որ մեկ կոտրված սկավառակի վրա տվյալները վերականգնելու համար դուք ստիպված կլինեք կարդալ տվյալները մյուսներից շատերից՝ ստեղծելով մեծ լրացուցիչ բեռ սկավառակների և ցանցի վրա:

Ամենատարածված սխալներն են տվյալների մեկ բլոկի անհասանելիությունը մեկ սկավառակի ձախողման կամ գերբեռնվածության պատճառով: Հնարավո՞ր է այս (ամենատարածված) դեպքում ինչ-որ կերպ նվազեցնել տվյալների վերականգնման համար ավելորդ բեռը: Պարզվում է, որ դուք կարող եք. կան LRC ավելորդության կոդեր հատուկ այդ նպատակով:

LRC-ն (տեղական վերակառուցման կոդերը) ավելորդության կոդեր են, որոնք հորինվել են Microsoft-ի կողմից՝ Windows Azure Storage-ում օգտագործելու համար: LRC-ի գաղափարը հնարավորինս պարզ է. բոլոր տվյալների բլոկները բաժանեք երկու (կամ ավելի) խմբերի և կարդացեք ավելորդության ծածկագրի բլոկների մի մասը յուրաքանչյուր խմբի համար առանձին: Այնուհետև ավելորդության կոդերի որոշ բլոկներ կհաշվարկվեն՝ օգտագործելով տվյալների բոլոր բլոկները (LRC-ում դրանք կոչվում են գլոբալ ավելորդության կոդեր), իսկ որոշները՝ օգտագործելով տվյալների բլոկների երկու խմբերից մեկը (դրանք կոչվում են տեղական ավելորդության կոդեր):

LRC-ն նշվում է երեք թվով. nrl, որտեղ n-ը տվյալների բլոկների թիվն է, r-ը գլոբալ ավելորդության ծածկագրի բլոկների թիվն է, l-ը տեղական ավելորդության կոդերի բլոկների թիվն է։ Տվյալները կարդալու համար, երբ տվյալների մեկ բլոկն անհասանելի է, անհրաժեշտ է կարդալ միայն n/l բլոկներ. սա l անգամ ավելի քիչ է, քան Reed-Solomon ծածկագրերում:

Օրինակ, հաշվի առեք LRC 6-2-2 սխեման: X1–X6 — 6 տվյալների բլոկ, P1, P2 — 2 գլոբալ ավելորդության բլոկ, P3, P4 — 2 տեղական ավելորդության բլոկ։

Ավելորդ կոդերի P1, P2 բլոկները հաշվվում են՝ օգտագործելով բոլոր տվյալների բլոկները: Ավելորդության կոդի բլոկ P3 - օգտագործելով տվյալների բլոկներ X1-X3, ավելորդության կոդերի բլոկ P4 - օգտագործելով տվյալների բլոկներ X4-X6:

Մնացածը կատարվում է LRC-ում Reed-Solomon ծածկագրերի անալոգիայով: Ավելորդության կոդերի բլոկների բառերը հաշվելու հավասարումները կլինեն.

Ալֆա, բետա, գամմա, դելտա թվերն ընտրելու համար պետք է պահպանվեն մի շարք պայմաններ՝ երաշխավորելու տվյալների վերականգնման հնարավորությունը (այսինքն՝ լուծել հավասարումների համակարգը): Նրանց մասին ավելին կարող եք կարդալ այստեղ Հոդված.
Նաև գործնականում XOR օպերացիան օգտագործվում է P3, P4 տեղական ավելորդության կոդերը հաշվարկելու համար:

LRC-ի համար հավասարումների համակարգից բխում են մի շարք եզրակացություններ.

• Ցանկացած 1 տվյալների բլոկ վերականգնելու համար բավական է կարդալ n/l բլոկները (n/2 մեր օրինակում):
• Եթե ​​r + l բլոկները անհասանելի են, և բոլոր բլոկները ներառված են մեկ խմբի մեջ, ապա տվյալները չեն կարող վերականգնվել: Սա հեշտ է բացատրել օրինակով։ Թող X1–X3 և P3 բլոկները անհասանելի լինեն. սրանք r + l բլոկներ են նույն խմբից, մեր դեպքում՝ 4։ Այնուհետև մենք ունենք 3 անհայտ 4 հավասարումների համակարգ, որոնք հնարավոր չէ լուծել:
• R + l բլոկների անհասանելիության մյուս բոլոր դեպքերում (երբ յուրաքանչյուր խմբից հասանելի է առնվազն մեկ բլոկ), LRC-ում տվյալները կարող են վերականգնվել:

Այսպիսով, LRC-ն գերազանցում է Reed-Solomon կոդերը՝ միայնակ սխալներից հետո տվյալների վերականգնման հարցում: Reed-Solomon ծածկագրերում տվյալների թեկուզ մեկ բլոկի վերականգնման համար անհրաժեշտ է օգտագործել n բլոկ, իսկ LRC-ում տվյալների մեկ բլոկի վերականգնման համար բավական է օգտագործել n/l բլոկներ (մեր օրինակում՝ n/2): Մյուս կողմից, LRC-ն զիջում է Reed-Solomon ծածկագրերին թույլատրելի սխալների առավելագույն քանակով։ Վերոնշյալ օրինակներում Reed-Solomon ծածկագրերը կարող են վերականգնել տվյալները ցանկացած 4 սխալի դեպքում, իսկ LRC-ի համար կան 2 սխալների 4 համակցություններ, երբ տվյալները չեն կարող վերականգնվել:

Այն, ինչ ավելի կարևոր է, կախված է կոնկրետ իրավիճակից, բայց հաճախ LRC-ի կողմից տրամադրվող ավելորդ բեռի խնայողությունները գերազանցում են մի փոքր ավելի քիչ հուսալի պահեստավորմանը:

4. Ավելորդության այլ ծածկագրեր

Բացի Reed-Solomon և LRC կոդերից, կան շատ այլ ավելորդության կոդեր: Տարբեր ավելորդության կոդերը օգտագործում են տարբեր մաթեմատիկա: Ահա մի քանի այլ ավելորդության կոդեր.

• Ավելորդության կոդը՝ օգտագործելով XOR օպերատորը: XOR գործողությունը կատարվում է n տվյալների բլոկների վրա, և ստացվում է ավելորդության 1 բլոկ, այսինքն՝ n+1 սխեմա (n տվյալների բլոկ, 1 ավելորդության կոդ)։ Օգտագործված է RAID 5- ը, որտեղ տվյալների բլոկները և ավելորդության կոդերը ցիկլային կերպով գրվում են զանգվածի բոլոր սկավառակների վրա։
• Զույգ-կենտ ալգորիթմ՝ հիմնված XOR գործողության վրա: Թույլ է տալիս կառուցել ավելորդության կոդերի 2 բլոկ, այսինքն՝ n+2 սխեմա։
• STAR ալգորիթմը հիմնված է XOR գործողության վրա: Թույլ է տալիս կառուցել ավելորդության կոդերի 3 բլոկ, այսինքն՝ n+3 սխեմա։
• Բուրգային կոդերը Microsoft-ի մեկ այլ ավելորդության կոդերն են:

5. Օգտագործեք Yandex-ում

Yandex-ի մի շարք ենթակառուցվածքային նախագծեր օգտագործում են ավելորդության կոդեր՝ տվյալների հուսալի պահպանման համար: Ահա մի քանի օրինակներ.

• MDS ներքին օբյեկտների պահեստավորում, որի մասին ես գրել եմ հոդվածի սկզբում:
• YT — Yandex-ի MapReduce համակարգ:
• ԵԴԲ (Yandex DataBase) - newSQL բաշխված տվյալների բազա:

MDS-ն օգտագործում է LRC ավելորդության կոդեր, 8-2-2 սխեմա: Ավելորդության կոդերով տվյալները գրվում են 12 տարբեր սկավառակների վրա տարբեր սերվերներում 3 տարբեր DC-ներում. 4 սերվեր յուրաքանչյուր DC-ում: Կարդացեք ավելին այս մասին Հոդված.

YT-ն օգտագործում է և՛ Reed-Solomon կոդերը (Սխեմա 6-3), որոնք առաջինն են ներդրել, և՛ LRC ավելորդության կոդերը (Սխեմա 12-2-2), ընդ որում LRC-ը պահեստավորման նախընտրելի մեթոդն է:

YDB-ն օգտագործում է զույգ-կենտ հիմնված ավելորդության կոդերը (Նկար 4-2): Արդեն YDB-ում ավելորդության կոդերի մասին պատմել է Highload-ում.

Ավելորդության տարբեր կոդերի սխեմաների օգտագործումը պայմանավորված է համակարգերի տարբեր պահանջներով: Օրինակ, MDS-ում LRC-ի միջոցով պահվող տվյալները տեղադրվում են միանգամից 3 DC-ներում: Մեզ համար կարևոր է, որ տվյալները հասանելի մնան կարդալու համար, եթե որևէ DC-ից 1-ը ձախողվի, հետևաբար բլոկները պետք է բաշխվեն DC-ների միջև այնպես, որ եթե որևէ DC անհասանելի է, անհասանելի բլոկների քանակը ոչ ավելի, քան թույլատրելի է: 8-2-2 սխեմայում դուք կարող եք տեղադրել 4 բլոկ յուրաքանչյուր DC-ում, այնուհետև երբ ցանկացած DC-ն անջատված է, 4 բլոկ անհասանելի կլինի, և տվյալները կարող են կարդալ: Ինչ սխեման էլ ընտրենք այն 3 DC-ներում տեղադրելիս, ամեն դեպքում պետք է լինի (r + l) / n >= 0,5, այսինքն պահեստավորման ավելորդությունը կլինի առնվազն 50%:

YT-ում իրավիճակը տարբեր է. յուրաքանչյուր YT կլաստեր ամբողջությամբ տեղակայված է 1 DC-ում (տարբեր կլաստերներ տարբեր DC-ներում), ուստի նման սահմանափակում չկա: 12-2-2 սխեման ապահովում է 33% ավելորդություն, այսինքն՝ տվյալների պահպանումն ավելի էժան է, և այն կարող է գոյատևել մինչև 4 միաժամանակյա սկավառակի անջատում, ինչպես MDS սխեման:

Տվյալների պահպանման և մշակման համակարգերում ավելորդության կոդերի օգտագործման շատ ավելի շատ առանձնահատկություններ կան. տվյալների վերականգնման նրբերանգներ, վերականգնման ազդեցությունը հարցումների կատարման ժամանակի վրա, տվյալների ձայնագրման առանձնահատկությունները և այլն: Այս և այլ առանձնահատկությունների մասին ես պատրաստվում եմ առանձին խոսել: պրակտիկայում ավելորդության կոդերի օգտագործման մասին, եթե թեման հետաքրքիր կլինի:

6. Հղումներ

1. Reed-Solomon ծածկագրերի և Galois դաշտերի մասին հոդվածների շարք. https://habr.com/ru/company/yadro/blog/336286/
   https://habr.com/ru/company/yadro/blog/341506/
   Նրանք ավելի խորն են նայում մաթեմատիկային մատչելի լեզվով:
2. Հոդված Microsoft-ից LRC-ի մասին. https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/LRC12-cheng20webpage.pdf
   Բաժին 2-ը համառոտ բացատրում է տեսությունը և այնուհետև քննարկում LRC-ի հետ փորձը գործնականում:
3. Զույգ-կենտ սխեման. https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
4. STAR սխեման. https://www.usenix.org/legacy/event/fast05/tech/full_papers/huang/huang.pdf
5. Բուրգի կոդերը. https://www.microsoft.com/en-us/research/publication/pyramid-codes-flexible-schemes-to-trade-space-for-access-efficiency-in-reliable-data-storage-systems/
6. Ավելորդության կոդերը MDS-ում. https://habr.com/ru/company/yandex/blog/311806
7. Ավելորդության կոդերը YT-ում. https://habr.com/ru/company/yandex/blog/311104/
8. Ավելորդության կոդերը YDB-ում. https://www.youtube.com/watch?v=dCpfGJ35kK8

Source: www.habr.com