Така изглежда излишъкът

Кодовете за излишък* се използват широко в компютърни системи за увеличаване на надеждността на съхранението на данни. В Яндекс те се използват в множество проекти. Например, прилагането на кодове за излишък вместо репликация в нашето вътрешно обектно хранилище спестява милиони без намаляване на надеждността. Въпреки това, ясното описание на начините, по които работят кодовете за излишък, е рядко. Желаящите да разберат се сблъскват с нещо такова (от Уикипедия):

Казвам се Вадим, в Яндекс се занимавам с разработка на вътрешното обектно хранилище MDS. В тази статия ще опиша на прост език теоретичните основи на кодовете за излишък (кодове на Рийд – Соломон и LRC). Ще разкажа как работи всичко, без сложна математика и редки термини. В края ще дам примери за прилагане на кодове за излишък в Яндекс.

Някои математически детайли няма да разглеждам подробно, но ще дам линкове за тези, които искат да се потопят по-дълбоко. Също така ще отбележа, че някои математически определения може да не са стриктни, тъй като статията не е предназначена за математици, а за инженери, които желаят да разберат същността на въпроса.

* В англоговорящата литература кодовете за излишък често се наричат erasure codes.

1. Същността на кодовете за излишък

Същността на всички кодове за излишък е пределно проста: да се съхраняват (или предават) данни по такъв начин, че те да не изчезват при възникване на грешки (повреди на дискове, грешки в предаване на данни и т.н.).

В повечето* кодове за излишък данните се разделят на n блока данни, за тях се изчисляват m блока кодове за излишък, и в крайна сметка се получават n + m блока. Кодове за излишък се изграждат по такъв начин, че да може да се възстановят n блока данни, използвайки само част от n + m блока. По-нататък ще разгледаме само блоковите кодове за излишък, т.е. такива, в които данните се разделят на блокове.

За да възстановите всички n блока данни, е необходимо да имате минимум n от n + m блока, тъй като не можете да получите n блока, имайки само n-1 блок (в този случай ще трябва да вземете 1 блок „от въздуха“). Достатъчни ли са n произволни блока от n + m блока за възстановяване на всички данни? Това зависи от типа на кодовете за излишък, например кодовете на Рийд – Соломон позволяват възстановяване на всички данни с произволни n блока, докато кодовете за излишък LRC – не винаги.

Съхранение на данни

В системите за съхранение на данни обикновено всеки от блоковете данни и блоковете кодове за излишък се записва на отделен диск. Тогава, при повреда на произволен диск, оригиналните данни все още могат да бъдат възстановени и прочетени. Данните могат да бъдат възстановени дори при едновременна повреда на няколко диска.

Предаване на данни

Кодовете за излишък могат да се използват за надеждно предаване на данни в ненадеждна мрежа. Предаваните данни се разделят на блокове, за тях се изчисляват кодове за излишък. По мрежата се предават както блоковете данни, така и блоковете кодове за излишък. При възникване на грешки в произволни блокове (дори и в определен брой блокове), данните все пак могат безгрешно да се предадат по мрежата. Кодове на Рийд – Соломон, например, се използват за предаване на данни по оптични линии и в спътникова връзка.

* Има също кодове за излишък, при които данните не се разделят на блокове, например кодове на Хеминг и кодове CRC, широко използвани за предаване на данни в мрежи Ethernet. Това са кодове за устойчиво на смущения кодиране, те са предназначени за откриване на грешки, а не за тяхното коригиране (кодът на Хеминг също позволява частично коригиране на грешки).

2. Кодове на Рийд – Соломон

Кодовете на Рийд – Соломон са едни от най-широко използваните кодове за излишък, изобретени още през 60-те години и за първи път получили широко приложение през 80-те за серийно производство на компактдискове.

Ключовите въпроси за разбиране на кодовете на Рийд – Соломон са два: 1) как се създават блокове кодове за излишък; 2) как да се възстановят данни с помощта на блокове кодове за излишък. Нека намерим отговори на тях.
За опростяване по-надолу ще приемем, че n=6 и m=4. Други схеми ще се разглеждат по аналогия.

Как да създадем блокове кодове за излишък

Все блокове на излишната кодировка се считат независимо един от друг. За изчисляване на всеки блок се използват всички n блока данни. На схемата по-долу X1-X6 — данни, P1–P4 — блокове с излишна кодировка.

Всички блокове данни трябва да са с еднакъв размер, за подравняване може да се използват нулеви битове. Получените блокове с излишна кодировка ще имат същия размер като блоковете данни. Всички блокове данни се разделят на думи (например, по 16 бита). Да предположим, че сме разделили блоковете данни на k думи. Тогава всички блокове с излишна кодировка също ще бъдат разделени на k думи.

За изчисляване на i-та дума на всеки блок с излишна кодировка ще се използват i-те думи от всички блокове данни. Те ще се изчисляват по следната формула:

Тук стойностите x — думи на блоковете данни, p — думи на блоковете с излишна кодировка, всичките алфа, бета, гама и делта — специално подбрани числа, еднакви за всички i. Важно е да се спомене, че всички тези стойности не са обикновени числа, а елементи на полето на Галоа, операцийте +, -, *, / не са типичните операции, а специални операции, въведени над елементите на полето на Галоа.

Защо са нужни полета на Галоа

На пръв поглед всичко изглежда просто: разделяме данните на блокове, блоковете — на думи, с помощта на думите на блоковете данни изчисляваме думи на блоковете с излишна кодировка — получаваме блокове с излишна кодировка. В общи линии това работи така, но дяволът е в детайлите:

Както бе казано по-горе, размерът на думата е фиксиран, в нашия пример 16 бита. Формулите по-горе за кодовете на Рийд — Соломон са такива, че при използване на обикновени цели числа резултатът от изчислението p може да не бъде представен с помощта на дума с допустим размер.
При възстановяване на данните формулите по-горе ще се разглеждат като система от уравнения, която трябва да бъде решена, за да се възстановят данните. В процеса на решаването може да възникне необходимост от делене на цели числа, като резултатът ще бъде действително число, което не може точно да се представи в паметта на компютъра.

Тези проблеми не позволяват да се използват цели числа за кодовете на Рийд — Соломон. Решението на проблема е оригинално и може да се опише по следния начин: да измислим специални числа, които могат да бъдат представени чрез думи с необходима дължина (например 16 бита), и резултатът от всички операции над тях (събиране, изваждане, умножение, деление) също ще бъде представен в паметта на компютъра чрез думи с необходима дължина.

Такива „специални“ числа отдавна се изследват в математиката и се наричат полета. Полето е множество елементи с определени за тях операции на събиране, изваждане, умножение и деление.

Полята на Галуа* са поля, за които съществува и е единствен резултат за всяка операция (+, -, *, \/) за всяка двойка елементи от полето. Полята на Галуа могат да бъдат изградени за числа, които са степен на 2: 2, 4, 8, 16 и т.н. (в действителност, степен на всяко просто число p, но на практика ни интересуват само степените на 2). Например, за думи с размер 16 бита, това поле съдържа 65 536 елемента, за всяка двойка от които може да се намери резултат за всяка операция (+, -, *, \/). Стойностите x, p, алфа, бета, гама, делта от горните уравнения за изчисления ще се считат за елементи на полето на Галуа.

Така, имаме система от уравнения, с които можем да изградим блокове на кодовете на излишък, като напишем съответна компютърна програма. С помощта на тази система от уравнения можем да извършим и възстановяване на данни.

* Това не е строго определение, а по-скоро описание.

Как да възстановим данни

Възстановяването е необходимо, когато от n + m блока част от блоковете липсват. Това могат да бъдат както блокове от данни, така и блокове на кодове на излишък. Липсата на блокове от данни и/или блокове на кодове на излишък ще означава, че в горните уравнения са неизвестни съответните променливи x и/или p.

Уравненията за кодовете на Рийд — Соломон могат да се разглеждат като система от уравнения, в която всички стойности алфа, бета, гама, делта са константи, всички x и p, съответстващи на достъпните блокове, са известни променливи, а останалите x и p са неизвестни.

Например, нека блоковете на данни 1, 2, 3 и блокът с кодове на излишък 2 да не са достъпни, тогава за i-тата група думи ще има следната система от уравнения (неизвестните са отбелязани с червено):

Имаме система от 4 уравнения с 4 неизвестни, следователно можем да я решим и да възстановим данните!

От тази система уравнения следват редица изводи за възстановяване на данни за кодовете на Рийд – Соломон (n блока данни, m блока кодове на излишък):

Данните могат да бъдат възстановени при загуба на всякакви m блока или по-малко. При загуба на m+1 блока или повече данните не могат да бъдат възстановени: не може да се реши система от m уравнения с m + 1 неизвестни.
За възстановяване дори на един блок данни е необходимо да се използват всякакви n от останалите блокове, като може да се използва всеки от кодовете на излишък.

Какво още трябва да знаете

В по-горното описание подминавам редица важни въпроси, за разглеждането на които трябва да се задълбочим в математиката. По-специално, не споменавам следното:

Системата от уравнения за кодовете на Рийд – Соломон трябва да има (единствено) решение при всякакви комбинации на неизвестните (не повече от m неизвестни). На базата на това изискване се подбират стойности на алфа, бета, гама и делта.
Системата от уравнения трябва да може автоматично да се строи (в зависимост от това, кои блокове не са налични) и да се решава.
Трябва да се построи поле на Галоа: за зададена дължина на словото да се знае резултатът от всяка операция (+, -, *, /) за всякакви две елементи.

В края на статията има линкове към литература по тези важни въпроси.

Избор на n и m

Как на практика да изберем n и m? На практика в системите за съхранение на данни кодовете на излишък се използват за икономия на място, затова m винаги се избира по-малко от n. Конкретните им стойности зависят от редица фактори, включително:

Надеждност на съхранение на данни. Колкото по-голямо е m, толкова повече откази на дисковете могат да бъдат преживяни, т.е. по-висока надеждност.
Излишък на съхранение. Колкото по-високо е съотношението m / n, толкова по-голям ще бъде излишъкът на съхранение, и толкова по-скъпа ще бъде системата.
Време за обработка на заявки. Колкото по-голяма е сумата n + m, толкова по-дълго ще бъде времето за отговор на запитванията. Тъй като за четене на данни (по време на възстановяването) трябва да се прочетат n блока, съхранявани на n различни диска, времето за четене ще се определи от най-бавния диск.

Освен това, съхранението на данни в няколко дата центъра налага допълнителни ограничения при избора на n и m: при изключване на 1 дата център данните трябва все още да бъдат достъпни за четене. Например, при съхранение на данни в 3 дата центъра трябва да се изпълнява условието: m >= n/2, в противен случай е възможна ситуация, при която данните не са достъпни за четене при изключване на 1 дата център.

3. LRC — Кодове за локално възстановяване

За възстановяване на данни с помощта на кодовете на Рийд — Соломон е нужно да се използват n произволни блока данни. Това е много съществен недостатък за разпределените системи за съхранение на данни, защото за възстановяване на данни на един счупен диск ще се наложи да се четат данни от повечето останали, създавайки голямо допълнително натоварване на дисковете и мрежата.

Най-често срещаните грешки са недостъпността на един блок данни поради повреда или претоварване на един диск. Има ли начин да се намали излишното натоварване за възстановяване на данни в такъв (най-често срещан) случай? У оказывается, да: специално за това съществуват кодове за излишък LRC.

LRC (Local Reconstruction Codes) — кодове за излишък, създадени в Microsoft за приложение в Windows Azure Storage. Идеята на LRC е максимално проста: да се разделят всички блокове данни на две (или повече) групи и да се изчисли част от кодовете за излишък за всяка група поотделно. Тогава част от кодовете за излишък ще бъдат изчислени с помощта на всички блокове данни (в LRC те се наричат глобални кодове за излишък), а част — с помощта на една от двете групи блокове данни (те се наричат локални кодове за излишък).

LRC се обозначава с три числа: n-r-l, където n — брой на блоковете данни, r — брой на глобалните блокове кодове за излишък, l — брой на локалните блокове кодове за излишък. За четене на данни при недостъпност на един блок данни е нужно да се прочетат само n/l блока — това е l пъти по-малко, отколкото при кодовете на Рийд — Соломон.

За пример ще разгледаме схемата LRC 6-2-2. X1–X6 — 6 блока данни, P1, P2 — 2 глобални блока за излишък, P3, P4 — 2 локални блока за излишък.

Блоковете кодове за излишък P1, P2 се изчисляват с помощта на всички блокове данни. Блокът код за излишък P3 — с помощта на блоковете данни X1–X3, блокът код за излишък P4 — с помощта на блоковете данни X4–X6.

Останалото се прави в LRC аналогично на кодовете на Рийд – Соломон. Уравненията за броене на думите на блоковете на кодовете на излишъците ще бъдат следните:

За подбора на числата алфа, бета, гама, делта е необходимо да се изпълнят редица условия, които гарантират възможността за възстановяване на данните (тоест решаване на системата от уравнения). Повече информация относно тях можете да прочетете в статии.
Също така на практика за броене на локалните кодове за излишък P3, P4 се прилага операцията XOR.

От системата от уравнения за LRC следват редица изводи:

За възстановяване на всеки 1 блок данни е достатъчно да се прочетат n/l блока (n/2 в нашия пример).
Ако недостъпни са r + l блока и в същото време всички блокове са в една група, то данните не могат да бъдат възстановени. Това лесно се обяснява чрез пример. Нека са недостъпни блоковете X1–X3 и P3: това е r + l блока от една група, 4 в нашия случай. Тогава имаме система от 3 уравнения с 4 неизвестни, която не може да бъде решена.
В всички останали случаи на недостъпност на r + l блока (когато от всяка група е достъпен поне един блок) данните в LRC могат да бъдат възстановени.

Така LRC печели от кодовете на Рийд – Соломон при възстановяване на данни след единични грешки. В кодовете на Рийд – Соломон за възстановяване на дори един блок данни е необходимо да се използват n блока, а в LRC за възстановяване на един блок данни е достатъчно да се използват n/l блока (n/2 в нашия пример). От друга страна, LRC губи спрямо кодовете на Рийд – Соломон по максималния брой допустими грешки. В горепосочените примери кодовете на Рийд – Соломон могат да възстановят данните при всякакви 4 грешки, а за LRC съществуват 2 комбинации от 4 грешки, при които данните не могат да бъдат възстановени.

Какво е по-важно – зависи от конкретната ситуация, но често спестяването на излишно натоварване, което дава LRC, надвишава малко по-малката надеждност на съхранение.

4. Други кодове за излишъци

Освен кодовете на Рийд – Соломон и LRC, съществуват много други кодове за излишъци. Различните кодове за излишъци използват различна математика. Ето някои други кодове за излишъци:

Код за излишък с помощта на оператора XOR. Операцията XOR се извършва над n блока данни и получаваме 1 блок кодове за излишъци, т.е. схема n+1 (n блока данни, 1 код за излишък). Използва се в RAID 5, където блоковете данни и кодовете за излишъци циклично се записват на всички дискове на масива.
Алгоритъм even-odd, базиран на операцията XOR. Позволява изграждането на 2 блока кодове за излишък, т.е. схема n+2.
Алгоритъм STAR, базиран на операцията XOR. Позволява изграждането на 3 блока кодове за излишък, т.е. схема n+3.
Pyramide кодове — още едни кодове за излишък от Microsoft.

5. Използване в Яндекс

Редица инфраструктурни проекти на Яндекс прилагат кодове за излишък за надеждно съхранение на данни. Ето няколко примера:

Вътрешно обектно хранилище MDS, за което писах в началото на статията.
YT — MapReduce система на Яндекс.
YDB (Yandex DataBase) — разпределена база данни newSQL.

В MDS се използват кодове за излишък LRC, схема 8-2-2. Данните с кодове за излишък се записват на 12 различни диска в различни сървъри в 3 различни ДЦ: по 4 сървъра в всеки ДЦ. Повече за това четете в статии.

В YT се използват както кодове на Рийд — Соломон (схема 6-3), които бяха реализирани първи, така и кодове за излишък LRC (схема 12-2-2), като LRC е предпочитаният начин за съхранение.

В YDB се използват кодове за излишък, базирани на even-odd (схема 4-2). За кодовете за излишък в YDB вече разказваха на Highload.

Приложението на различни схеми на кодове за излишък се дължи на различните изисквания, поставяни пред системите. Например, в MDS данните, съхранявани с помощта на LRC, се разполагат веднага в 3 ДЦ. Важно е данните да остават достъпни за четене при повреда на 1 от всяко ДЦ, затова блоковете трябва да са разпределени по ДЦ така, че при недостъпност на всяко ДЦ броят на недостъпните блокове да не е повече от допустимото. В схемата 8-2-2 могат да се разположат по 4 блока в всяко ДЦ, така че при изключване на всяко ДЦ ще станат недостъпни 4 блока, и данните ще могат да се четат. Без значение коя схема изберем при разполагане в 3 ДЦ, във всеки случай трябва да бъде (r + l) / n >= 0,5, т.е. излишъкът на съхранение ще бъде минимум 50%.

В YT ситуацията е различна: всеки клъстер YT се разполага изцяло в 1 ДЦ (различни клъстери в различни ДЦ), затова там няма такова ограничение. Схемата 12-2-2 дава излишък 33%, т.е. съхраняването на данни излиза по-евтино, като в същото време те също могат да издържат на до 4 едновременни изключвания на дискове, както и схемата в MDS.

Има още много особености при прилагането на кодове за излишък в системите за съхранение и обработка на данни: нюанси на възстановяване на данни, влияние на възстановяването върху времето за изпълнение на запитвания, особености на записване на данни и др. Ще разкажа по-задълбочено за тези и други особености на прилагане на кодове за излишък на практика, ако темата е интересна.