Так виглядає надмірність
Коди надмірності* широко застосовуються в комп'ютерних системах збільшення надійності зберігання даних. В Яндексі їх використовують у багатьох проектах. Наприклад, застосування кодів надмірності замість реплікації у нашому внутрішньому об'єктному сховищі заощаджує мільйони без зниження надійності. Але незважаючи на широке поширення, зрозуміле опис того, як працюють коди надмірності, зустрічається дуже рідко. Бажаючі розібратися стикаються приблизно з наступним (з ):
Мене звуть Вадим, в Яндексі займаюся розробкою внутрішнього об'єктного сховища 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. Коди Ріда - Соломона
Коди Ріда - Соломона - одні з найбільш поширених кодів надмірності, винайдені ще в 1960-х і вперше отримали широке застосування в 1980-х для серійного випуску компакт-дисків.
Ключових питань розуміння кодів Ріда — Соломона два: 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 елементів, для кожної пари яких можна знайти результат будь-якої операції (+, -, *, /). Значення 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 - Local Reconstruction Codes
Для відновлення даних за допомогою кодів Ріда Соломона доводиться використовувати n довільних блоків даних. Це дуже суттєвий мінус для розподілених систем зберігання даних, адже для відновлення даних на одному зламаному диску доведеться читати дані з більшості інших, створюючи велике додаткове навантаження на диски та мережу.
Найпоширеніші помилки — недоступність одного блоку даних через поломку або перевантаженість одного диска. Чи можна якось зменшити надлишкове навантаження для відновлення даних у такому (найчастішому) випадку? Виявляється, можна: спеціально для цього є коди надмірності LRC.
LRC (Local Reconstruction Codes) - коди надмірності, придумані в Microsoft для застосування в Windows Azure Storage. Ідея LRC максимально проста: розбити всі блоки даних на дві (або більше) групи і вважати частину блоків надмірності кодів для кожної групи окремо. Тоді частина блоків надмірності кодів буде підрахована за допомогою всіх блоків даних (в LRC вони називаються глобальними кодами надмірності), а частина - за допомогою однієї з двох груп блоків даних (вони називаються локальними кодами надмірності).
LRC позначається трьома числами: nrl, де n – кількість блоків даних, r – кількість глобальних блоків кодів надмірності, l – кількість локальних блоків кодів надмірності. Для читання даних при недоступності одного блоку даних потрібно прочитати тільки n/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 код надмірності). Використовується в де блоки даних і кодів надмірності циклічно записуються на всі диски масиву.
- Алгоритм even-odd, що базується на операції XOR. Дозволяє побудувати 2 блоки кодів надмірності, тобто схема n+2.
- Алгоритм STAR, що базується на операції XOR. Дозволяє побудувати 3 блоки кодів надмірності, тобто схема n+3.
- Pyramide codes - ще одні коди надмірності від Microsoft.
5. Використання в Яндексі
Ряд інфраструктурних проектів Яндекса застосовує надлишкові коди для надійного зберігання даних. Ось кілька прикладів:
- Внутрішнє об'єктне сховище MDS, про яке я писав на початку статті.
- - MapReduce-система Яндекса.
- (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 вже .
Застосування різних схем кодів надмірності обумовлено різними вимогами до систем. Наприклад, MDS дані, що зберігаються за допомогою LRC, розміщуються відразу в 3 ДЦ. Нам важливо, щоб дані залишалися доступними для читання при виході з ладу будь-якого ДЦ, тому блоки повинні бути розподілені по ДЦ так, щоб при недоступності будь-якого ДЦ кількість недоступних блоків була не більшою за допустиму. У схемі 1-8-2 можна розмістити по 2 блоки у кожному ДЦ, тоді при відключенні будь-якого ДЦ буде недоступно 4 блоки, і дані можна буде читати. Яку б схему ми не вибрали при розміщенні у 4 ДЦ, у будь-якому випадку має бути (r + l) / n >= 3, тобто надмірність зберігання буде щонайменше 0,5%.
У YT ситуація інша: кожен кластер YT повністю розташовується в 1 ДЦ (різні кластери в різних ДЦ), тому там немає такого обмеження. Схема 12-2-2 дає надмірність 33%, тобто зберігати дані виходить дешевше, причому вони також можуть переживати до 4 одночасних відключень дисків, як і схема в MDS.
Є ще багато особливостей застосування кодів надмірності в системах зберігання та обробки даних: нюанси відновлення даних, вплив відновлення на час виконання запитів, особливості запису даних і т. д. Я збираюся окремо розповісти про ці та інші особливості застосування кодів надмірності на практиці, якщо буде цікавим.
6. Посилання
- Серія статей про коди Ріда — Соломона та поля Галуа:
Вони доступною мовою глибше розглядається математика. - Стаття від Microsoft про LRC:
У розділі 2 коротко пояснюється теорія, далі розглядається досвід застосування LRC практично. - Схема even-odd:
- Схема STAR:
- Pyramid codes:
- Коди надмірності в MDS:
- Коди надмірності в YT:
- Коди надмірності в YDB:
Джерело: habr.com