Ето как изглежда съкращенията

Кодовете за излишък* се използват широко в компютърните системи за повишаване на надеждността на съхранението на данни. В Yandex те се използват в много проекти. Например, използването на резервни кодове вместо репликация в нашето вътрешно съхранение на обекти спестява милиони, без да жертва надеждността. Но въпреки широкото им използване, ясните описания на това как работят резервните кодове са много редки. Тези, които искат да разберат, са изправени пред приблизително следното (от Wikipedia):

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

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

* В англоезичната литература излишните кодове често се наричат ​​кодове за изтриване.

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

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

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

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

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

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

Трансфер на данни

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

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

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

Кодовете на Рийд-Соломон са един от най-широко използваните резервни кодове, изобретен още през 1960-те години на миналия век и за първи път широко използван през 1980-те години на миналия век за масово производство на компактдискове.

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

Как да създадете резервни кодови блокове

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

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

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

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

Защо са необходими полетата на Галоа?

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

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

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

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

Полетата Galois* са полета, за които има уникален резултат от всяка операция (+, -, *, /) за всеки два елемента от полето. Полетата на Галоа могат да бъдат конструирани за числа, които са степени на 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 различни диска, времето за четене ще се определя от най-бавния диск.

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

3. LRC - Местни кодове за реконструкция

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

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

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

LRC се обозначава с три числа: nrl, където 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 по аналогия с кодовете на Рийд-Соломон. Уравненията за преброяване на думите на кодовите блокове с излишък ще бъдат:

За да изберете числата алфа, бета, гама, делта, трябва да бъдат изпълнени редица условия, за да се гарантира възможността за възстановяване на данни (т.е. решаване на системата от уравнения). Можете да прочетете повече за тях в Статия.
Също така на практика операцията 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 при възстановяване на данни след единични грешки. В кодовете на Рийд-Соломон, за да възстановите дори един блок от данни, трябва да използвате n блока, а в LRC, за да възстановите един блок от данни, е достатъчно да използвате n/l блока (n/2 в нашия пример). От друга страна, LRC е по-нисък от кодовете на Рийд-Соломон по отношение на максималния брой допустими грешки. В примерите по-горе кодовете на Рийд-Соломон могат да възстановят данни за всякакви 4 грешки, а за LRC има 2 комбинации от 4 грешки, когато данните не могат да бъдат възстановени.

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

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

Освен кодовете на Рийд-Соломон и 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 — Системата MapReduce на Yandex.
• YDB (Yandex DataBase) - newSQL разпределена база данни.

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

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

YDB използва базирани на четно-нечетни резервни кодове (Фигура 4-2). Относно излишните кодове в YDB вече каза на Highload.

Използването на различни схеми на код за излишък се дължи на различни изисквания към системите. Например в MDS данните, съхранени с помощта на LRC, се поставят в 3 DC наведнъж. За нас е важно данните да останат достъпни за четене, ако 1 от всеки DC се повреди, следователно блоковете трябва да бъдат разпределени между 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. Поредица от статии за кодовете на Рийд-Соломон и полетата на Галоа: 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

Източник: www.habr.com