Овако изгледа вишак

Редундантни кодови* се широко користе у рачунарским системима за повећање поузданости складиштења података. У Иандек-у се користе у многим пројектима. На пример, коришћење редундантних кодова уместо репликације у нашем интерном складишту објеката штеди милионе без жртвовања поузданости. Али упркос њиховој широкој употреби, јасни описи како функционишу редундантни кодови су веома ретки. Они који желе да разумеју суочавају се са отприлике следећим (од Википедиа):

Зовем се Вадим, у Иандек-у развијам МДС интерно складиштење објеката. У овом чланку ћу једноставним речима описати теоријске основе редундантних кодова (Реед-Соломон и ЛРЦ кодови). Рећи ћу вам како то функционише, без сложене математике и ретких појмова. На крају ћу дати примере коришћења редундантних кодова у Иандек-у.

Нећу детаљно разматрати бројне математичке детаље, али ћу дати линкове за оне који желе да зароне дубље. Такође ћу приметити да неке математичке дефиниције можда нису строге, јер чланак није намењен математичарима, већ инжењерима који желе да разумеју суштину проблема.

* У литератури на енглеском језику, редундантни кодови се често називају кодовима за брисање.

1. Суштина редундантних кодова

Суштина свих редундантних кодова је крајње једноставна: ускладиштите (или пренесите) податке тако да се не изгубе када дође до грешака (кварови диска, грешке у преносу података итд.).

У већини* кодова редундансе, подаци су подељени на н блокова података, за које се броји м блокова редундантних кодова, што резултира укупно н + м блокова. Кодови редундантности су конструисани на такав начин да се н блокова података може повратити користећи само део од н + м блокова. Затим ћемо размотрити само блокове редундантне кодове, односно оне у којима су подаци подељени у блокове.

Да бисте повратили свих н блокова података, потребно је да имате најмање н од н + м блокова, пошто не можете добити н блокова ако имате само н-1 блок (у овом случају, морали бисте да узмете 1 блок из танког ваздух”). Да ли је н насумичних блокова од н + м блокова довољно за опоравак свих података? Ово зависи од врсте редундантних кодова, на пример, Реед-Соломон кодови вам омогућавају да опоравите све податке користећи произвољних н блокова, али ЛРЦ кодови редундансе то не чине увек.

Складиштење података

У системима за складиштење података, по правилу, сваки од блокова података и блокова редундантног кода се уписује на посебан диск. Затим, ако произвољни диск поквари, оригинални подаци се и даље могу вратити и прочитати. Подаци се могу опоравити чак и ако неколико дискова откаже у исто време.

Пренос података

Кодови редундантности се могу користити за поуздан пренос података преко непоуздане мреже. Пренесени подаци се деле на блокове, а за њих се израчунавају редундантни кодови. И блокови података и блокови редундантног кода се преносе преко мреже. Ако дође до грешке у произвољним блоковима (до одређеног броја блокова), подаци се и даље могу преносити преко мреже без грешака. Реед-Соломон кодови се, на пример, користе за пренос података преко оптичких комуникационих линија и у сателитским комуникацијама.

* Постоје и редундантни кодови у којима се подаци не деле на блокове, као што су Хамингови кодови и ЦРЦ кодови, који се широко користе за пренос података у Етернет мрежама. Ово су кодови за кодирање који исправља грешке, они су дизајнирани да открију грешке, а не да их исправљају (Хеммингов код такође омогућава делимичну исправку грешака).

2. Рид-Соломон кодови

Рид-Соломон кодови су један од најчешће коришћених редундантних кодова, измишљени још 1960-их и први пут широко коришћени 1980-их за масовну производњу компакт дискова.

Постоје два кључна питања за разумевање Рид-Соломон кодова: 1) како креирати блокове редундантних кодова; 2) како опоравити податке помоћу блокова редундантног кода. Хајде да нађемо одговоре на њих.
Ради једноставности, даље ћемо претпоставити да је н=6 и м=4. Друге шеме се разматрају по аналогији.

Како направити блокове редундантног кода

Сваки блок редундантних кодова се броји независно од осталих. Свих н блокова података се користи за бројање сваког блока. У дијаграму испод, Кс1-Кс6 су блокови података, П1-П4 су блокови редундантног кода.

Сви блокови података морају бити исте величине, а нулти битови се могу користити за поравнање. Добијени блокови редундантног кода биће исте величине као блокови података. Сви блокови података су подељени у речи (на пример, 16 бита). Рецимо да смо блокове података поделили на к речи. Тада ће сви блокови редундантних кодова такође бити подељени на к речи.

За бројање и-те речи сваког блока редундансе, користиће се и-те речи свих блокова података. Они ће се израчунати према следећој формули:

Овде су вредности к речи блокова података, п су речи блокова редундантног кода, сви алфа, бета, гама и делта су посебно одабрани бројеви који су исти за све и. Одмах се мора рећи да све ове вредности нису обични бројеви, већ елементи Галоа поља +, -, *, / нису операције познате свима нама, већ специјалне операције уведене на елементима Галоа; поље.

Зашто су Галоа поља потребна?

Чини се да је све једноставно: податке делимо на блокове, блокове на речи, користећи речи блокова података бројимо речи блокова редундантног кода - добијамо блокове редундантног кода. У принципу, то функционише овако, али ђаво је у детаљима:

Као што је горе наведено, величина речи је фиксна, у нашем примеру 16 бита. Формуле изнад за Рид-Соломонове кодове су такве да када се користе обични цели бројеви, резултат израчунавања п можда неће бити представљен коришћењем речи важеће величине.
Приликом опоравка података, горње формуле ће се сматрати системом једначина које се морају решити да би се подаци опоравили. Током процеса решавања, можда ће бити потребно поделити целе бројеве једни са другима, што резултира реалним бројем који се не може тачно представити у меморији рачунара.

Ови проблеми спречавају употребу целих бројева за Рид-Соломонове кодове. Решење задатка је оригинално, може се описати на следећи начин: хајде да смислимо посебне бројеве који се могу представити речима потребне дужине (на пример, 16 бита), и резултат извођења свих операција над којима (сабирање , одузимање, множење, дељење) такође ће бити представљени у меморији рачунара помоћу речи потребне дужине.

Такве „посебне“ бројеве математика проучава већ дуго времена; Поље је скуп елемената за које су дефинисане операције сабирања, одузимања, множења и дељења.

Галоа* поља су поља за која постоји јединствени резултат сваке операције (+, -, *, /) за било која два елемента поља. Галоа поља се могу конструисати за бројеве који су степен 2: 2, 4, 8, 16 итд. (заправо степена било ког простог броја п, али у пракси нас занимају само степени 2). На пример, за 16-битне речи, ово је поље које садржи 65 елемената, за сваки пар од којих се може наћи резултат било које операције (+, -, *, /). Вредности к, п, алфа, бета, гама, делта из горњих једначина ће се сматрати елементима Галоис поља за прорачуне.

Дакле, имамо систем једначина помоћу којих можемо конструисати блокове редундантних кодова писањем одговарајућег рачунарског програма. Користећи исти систем једначина, можете извршити опоравак података.

* Ово није строга дефиниција, већ опис.

Како опоравити податке

Рестаурација је потребна када неки од н + м блокова недостају. То могу бити и блокови података и блокови редундантног кода. Одсуство блокова података и/или блокова редундантног кода ће значити да су одговарајуће к и/или п променљиве непознате у горњим једначинама.

Једначине за Реед-Соломон кодове се могу посматрати као систем једначина у којем су све алфа, бета, гама, делта вредности константе, сви к и п који одговарају доступним блоковима су познате променљиве, а преостали к и п су непознати.

На пример, нека блокови података 1, 2, 3 и блок кодова редунданције 2 буду недоступни, тада ће за и-ту групу речи постојати следећи систем једначина (непознате су означене црвеном бојом):

Имамо систем од 4 једначине са 4 непознате, што значи да можемо да га решимо и вратимо податке!

Из овог система једначина следи низ закључака о обнављању података за Реед-Соломон кодове (н блокова података, м блокова редундантних кодова):

Подаци се могу повратити ако се изгуби било који м блокова или мање. Ако се изгуби м+1 или више блокова, подаци се не могу вратити: немогуће је решити систем од м једначина са м + 1 непознатим.
Да бисте опоравили чак и један блок података, потребно је да користите било који н преосталих блокова и можете користити било који од редундантних кодова.

Шта још треба да знаш

У горњем опису избегавам низ важних питања која захтевају дубље уроњење у математику. Конкретно, не говорим ништа о следећем:

Систем једначина за Рид-Соломонове кодове мора имати (јединствено) решење за било коју комбинацију непознатих (не више од м непознатих). На основу овог захтева бирају се вредности алфа, бета, гама и делта.
Систем једначина мора бити у стању да се аутоматски конструише (у зависности од тога који блокови су недоступни) и реши.
Морамо да направимо Галоис поље: за дату величину речи, моћи да пронађемо резултат било које операције (+, -, *, /) за било која два елемента.

На крају чланка налазе се референце на литературу о овим важним питањима.

Избор н и м

Како изабрати н и м у пракси? У пракси, у системима за складиштење података, редундантни кодови се користе за уштеду простора, па се м увек бира мање од н. Њихове специфичне вредности зависе од бројних фактора, укључујући:

Поузданост складиштења података. Што је већи м, то је већи број кварова диска који се могу преживети, односно већа је поузданост.
Сувишно складиште. Што је већи однос м/н, то ће бити већа редундантност складиштења, а систем ће бити скупљи.
Време обраде захтева. Што је већи збир н + м, дуже ће бити време одговора на захтеве. Пошто читање података (током опоравка) захтева читање н блокова ускладиштених на н различитих дискова, време читања ће бити одређено најспоријим диском.

Поред тога, складиштење података у неколико ДЦ намеће додатна ограничења на избор н и м: ако је 1 ДЦ искључен, подаци и даље морају бити доступни за читање. На пример, када се подаци чувају у 3 ДЦ, мора бити испуњен следећи услов: м >= н/2, иначе може доћи до ситуације да подаци нису доступни за читање када је 1 ДЦ искључен.

3. ЛРЦ - Локални кодови за реконструкцију

Да бисте опоравили податке користећи Рид-Соломон кодове, морате да користите н произвољних блокова података. Ово је веома значајан недостатак за дистрибуиране системе за складиштење података, јер да бисте вратили податке на једном поквареном диску, мораћете да читате податке са већине осталих, стварајући велико додатно оптерећење на дисковима и мрежи.

Најчешће грешке су недоступност једног блока података због квара или преоптерећења једног диска. Да ли је могуће некако смањити вишак оптерећења за опоравак података у овом (најчешћем) случају? Испоставило се да можете: постоје ЛРЦ редундантни кодови посебно за ову сврху.

LRC (Локални реконструкцијски кодови) су редундантни кодови које је развио Мајкрософт за употребу у Windows Azure Storage. Идеја која стоји иза LRC-а је веома једноставна: поделити све блокове података у две (или више) група и израчунати део блокова редундантног кода за сваку групу посебно. Затим, неки од блокова редундантног кода ће бити израчунати коришћењем свих блокова података (у LRC-у, они се називају глобални редундантни кодови), а неки ће бити израчунати коришћењем једне од две групе блокова података (они се називају локални редундантни кодови).

ЛРЦ је означен са три броја: нрл, где је н број блокова података, р је број блокова глобалног редундантног кода, л је број блокова локалног редундантног кода. Да бисте прочитали податке када је један блок података недоступан, потребно је да прочитате само н/л блокова - ово је л пута мање него код Рид-Соломонових кодова.

На пример, размотрите шему ЛРЦ 6-2-2. Кс1–Кс6 — 6 блокова података, П1, П2 — 2 глобална редундантна блока, П3, П4 — 2 локална редундантна блока.

Блокови редундантног кода П1, П2 се броје коришћењем свих блокова података. Редундантни кодни блок П3 - коришћењем блокова података Кс1-Кс3, редундантни кодни блок П4 - коришћењем блокова података Кс4-Кс6.

Остало се ради у ЛРЦ-у по аналогији са Рид-Соломоновим кодовима. Једначине за бројање речи редундантних кодних блокова биће:

Да бисте изабрали бројеве алфа, бета, гама, делта, морају бити испуњени бројни услови који гарантују могућност опоравка података (тј. решавања система једначина). Више о њима можете прочитати у Чланак.
Такође у пракси, операција КСОР се користи за израчунавање локалних редундантних кодова П3, П4.

Из система једначина за ЛРЦ следи низ закључака:

Да бисте повратили било који 1 блок података, довољно је прочитати н/л блокова (н/2 у нашем примеру).
Ако су р + л блокови недоступни, а сви блокови су укључени у једну групу, подаци се не могу вратити. Ово је лако објаснити на примеру. Нека су блокови Кс1–Кс3 и П3 недоступни: то су р + л блокови из исте групе, у нашем случају 4. Тада имамо систем од 3 једначине са 4 непознате које се не могу решити.
У свим осталим случајевима недоступности р + л блокова (када је бар један блок доступан из сваке групе), подаци у ЛРЦ-у се могу вратити.

Дакле, ЛРЦ надмашује Реед-Соломон кодове у опоравку података након појединачних грешака. У Рид-Соломон кодовима, да бисте повратили чак и један блок података, потребно је да користите н блокова, а у ЛРЦ-у, да бисте повратили један блок података, довољно је користити н/л блокова (н/2 у нашем примеру). С друге стране, ЛРЦ је инфериоран у односу на Рид-Соломон код у погледу максималног броја дозвољених грешака. У горњим примерима, Реед-Соломон кодови могу да поврате податке за било које 4 грешке, а за ЛРЦ постоје 2 комбинације од 4 грешке када подаци не могу да се поврате.

Оно што је још важније зависи од конкретне ситуације, али често уштеде у вишку оптерећења које ЛРЦ обезбеђује превазилазе нешто мање поуздано складиштење.

4. Други кодови редундантности

Поред кодова Реед-Соломон и ЛРЦ, постоје многи други кодови редундансе. Различити кодови редунданције користе различиту математику. Ево неких других кодова редундантности:

Код редундантности користећи КСОР оператор. Операција КСОР се изводи на н блокова података и добија се 1 блок редундантних кодова, односно н+1 шема (н блокова података, 1 редундантни код). Се користи у РАИД КСНУМКС, где се блокови података и редундантни кодови циклично уписују на све дискове низа.
Парно-непарни алгоритам заснован на операцији КСОР. Омогућава вам да направите 2 блока редундантних кодова, односно шему н+2.
СТАР алгоритам заснован на операцији КСОР. Омогућава вам да направите 3 блока редундантних кодова, односно шему н+3.
Пирамидни кодови су још један Мицрософтов редундантни код.

5. Користите у Иандек

Бројни Иандек инфраструктурни пројекти користе редундантне кодове за поуздано складиштење података. Ево неколико примера:

МДС интерно складиштење објеката, о чему сам писао на почетку чланка.
YT — МапРедуце систем Иандек.
ИДБ (Иандек ДатаБасе) - новаСКЛ дистрибуирана база података.

МДС користи ЛРЦ редундантне кодове, шему 8-2-2. Подаци са редундантним кодовима се уписују на 12 различитих дискова у различитим серверима у 3 различита ДЦ-а: 4 сервера у сваком ДЦ-у. Прочитајте више о овоме у Чланак.

ИТ користи и Рид-Соломон кодове (шема 6-3), који су први имплементирани, и ЛРЦ редундантне кодове (шема 12-2-2), при чему је ЛРЦ преферирани метод складиштења.

ИДБ користи редундантне кодове засноване на пар-непар (слика 4-2). О редундантним кодовима у ИДБ-у већ речено на Хигхлоад-у.

Коришћење различитих шема редундантних кодова је због различитих захтева за системе. На пример, у МДС-у, подаци који се чувају помоћу ЛРЦ-а се смештају у 3 ДЦ-а одједном. За нас је важно да подаци остану доступни за читање ако 1 од било ког ДЦ-а откаже, стога блокови морају бити распоређени између ДЦ-ова тако да ако је било који ДЦ недоступан, број недоступних блокова није већи од дозвољеног. У шеми 8-2-2 можете поставити 4 блока у сваки ДЦ, а онда када је било који ДЦ искључен, 4 блока ће бити недоступна и подаци се могу читати. Коју год шему да изаберемо када је постављамо у 3 ДЦ, у сваком случају треба да буде (р + л) / н >= 0,5, односно, редундантност складиштења ће бити најмање 50%.

У ИТ ситуација је другачија: сваки ИТ кластер је у потпуности лоциран у 1 ДЦ (различити кластери у различитим ДЦ-овима), тако да нема таквог ограничења. Шема 12-2-2 обезбеђује 33% редунданције, односно складиштење података је јефтиније, а може да преживи и до 4 истовремена прекида рада диска, баш као и МДС шема.

Постоји много више карактеристика употребе редундантних кодова у системима за складиштење и обраду података: нијансе опоравка података, утицај опоравка на време извршења упита, карактеристике снимања података, итд. О овим и другим карактеристикама ћу говорити одвојено. употребе редундантних кодова у пракси, ако ће тема бити интересантна.