Як застосування кодів надмірності в SDS допомагає Яндексу дешево і надійно зберігати дані

Яндекс, як і будь-яка інша велика інтернет-компанія, що зберігає багато, а точніше дуже багато даних. Це і користувальницькі дані з різних сервісів, і намайненные сайти, і проміжні дані для розрахунку погоди, і резервні копії баз даних. Вартість зберігання ($/ГБ) — один з важливих показників системи. У цій статті я хочу розповісти вам про один з методів, який дозволив нам серйозно здешевити сховище.


В 2015 році, як ви всі пам'ятаєте, сильно зріс курс долара. Точніше, рости-то він почав в кінці 2014-го, але нові партії заліза ми замовляли вже в 2015-м. Яндекс заробляє в рублях, і тому разом з курсом зросла і вартість заліза для нас. Це змусило нас в черговий раз подумати про те, як зробити, щоб в поточний кластер можна було покласти більше даних. Ми таке, звичайно, робимо регулярно, але в цей раз мотивація була особливо сильною. До речі, якщо після посту у вас залишаться питання, які б ви хотіли обговорити особисто, приходьте на нашу встречу.
Кожен сервер кластера надає для нас наступні ресурси: процесор, оперативну пам'ять, жорсткі диски і мережу. Мережа тут — більш складне поняття, ніж просто мережева плата. Це ще і вся інфраструктура всередині дата-центру, і зв'язність між різними дата-центрами і пунктами обміну трафіком. У кластері для забезпечення надійності застосовувалася реплікація, і сумарний обсяг кластера визначався виключно через сумарну ємність жорстких дисків. Потрібно було придумати, як обміняти ресурси, що залишилися на збільшення місця.
Оперативну пам'ять обміняти складно. Ми використовуємо дискові полки, і різниця в об'ємі оперативної пам'яті до ємності дисків — більше трьох порядків. Її можна використовувати для прискорення доступу в рамках однієї машини, але це історія для окремої статті.
Процесор обмінюється досить очевидно — через архівацію. Але потрібно звернути увагу на кілька підводних каменів. По-перше, ступінь стиснення сильно залежить від комбінації архіватора і даних, що зберігаються, тобто потрібно взяти репрезентативну вибірку даних і на ній оцінити, скільки вийде заощадити. По-друге, архіватор повинен забезпечувати можливість читати дані практично з будь-якого місця, інакше доведеться забути про Range-заголовок HTTP (а на це образяться клієнти з не дуже хорошим інтернетом, які більше не зможуть завантажувати великі файли). По-третє, важлива швидкість стиснення і розпаковування, а також супутній витрата CPU. Можна взяти архіватор, який буде стискати дані досить ефективно, але кількість процесорів у вашому кластері не вистачить, щоб забезпечити поточну швидкість запису. При розпакуванні, в свою чергу, буде страждати latency запитів. Не так давно Facebook офіційно випустив свій архіватор Zstd — ми рекомендуємо його спробувати. Він дуже швидкий і при цьому непогано стискає дані.
З усіх ресурсів залишається мережу, і з нею у нас великий простір для творчості. Про те, як обміняти мережу на ємність сховища, якраз і піде мова далі.
У Яндекса досить жорсткі вимоги до системи зберігання. Вона повинна залишатися працездатною навіть при втраті одного дата-центру. Така умова накладає досить сильні обмеження на технології, які можна застосовувати, але в обмін ми отримуємо більш високу надійність, ніж у самого дата-центру. Для нас як для розробників системи зберігання це означає, що коефіцієнт надмірності повинен бути більше одиниці при випаданні будь-якого ДЦ.
Взагалі, правильніше говорити про зони доступності. У нашому випадку це саме дата-центр цілком, але це може бути і окрема машина, стійка, машзал або навіть континент. Тобто якщо у нас є чотири зони доступності і ми рівномірно розподілили між ними дані, то ступінь надлишковості не може бути менше, ніж 1.(3), 0.(3) у кожній із зон. Отже, є N зон доступності і потрібно якось розкласти по ним дані.
Репліки
Очевидно, найпростіший спосіб — зробити повні репліки. Найчастіше роблять два або три репліки, і ми багато років жили саме за такою схемою. Недоліки очевидні: доводиться використовувати дві (або три) гігабайт місця на жорстких дисках для зберігання одного гігабайта даних. Але є і переваги: в кожній репліці зберігається повноцінний файл, його легко прочитати, і при цьому він цілком лежить на одній машині, на одному жорсткому диску. Відновити дані при втраті диска теж досить просто — звичайним копіюванням по мережі.
За зберігання контенту користувачів, даних Яндекс.Музики, різних аватарок та інших подібних даних у нас відповідає сервіс MDS — Media Storage. Він заснований на Elliptics, Eblob і HTTP proxy. Elliptics надає мережеву маршрутизацію, Eblob потрібен для зберігання даних на диску, проксі — для завершення користувацького трафіку. Всім цим кластером управляє система під назвою Mastermind. В нашому сховищі ми відійшли від концепції великих DHT-кілець, які пробували в Elliptics раніше, і розбили весь простір на невеликі шарды за 916 гігабайт. Їх ми називаємо «каплами» (від англ. couple). Цифра 916 обрана з-за того, що нам потрібно розміщувати кратну кількість реплік каплов на одному жорсткому диску (виробники дисків, в свою чергу, люблять маркетинг і вважають обсяг у десяткових терабайтах). Mastermind стежить за тим, щоб репліки одного капла завжди розташовувалися в різних ДЦ, запускає процедуру відновлення даних, дефрагментацію і взагалі автоматизує працю системних адміністраторів.


Для відновлення консистентности у нас є спеціальна процедура, яка пробігає по всіх ключів і дописує відсутні ключі в ті репліки, де їх немає. Ця процедура не дуже швидка, але ми запускаємо її тільки там, де між репліками є розбіжність у кількості живих ключів. Побічний плюс — створюється навантаження на жорсткий диск, навіть якщо дані там холодні і користувачі за ними не приходять. У результаті диск починає вмирати заздалегідь, а не в той момент, коли ми намагаємося відновити дані, виявивши, що інша репліка вже померла. Ми його спокійно міняємо, після чого автоматично запускається відновлення і дані користувачів залишаються в цілості й схоронності.
Коди надмірності
Якщо провести аналогію, подібний спосіб реплікації даних — це RAID 1, простий, надійний і не дуже ефективний з точки зору витрачання місця. Ми ж хочемо створити щось аналогічне RAID 5 або RAID 6. Знову ж, йдемо від простого до складного: беремо три зони доступності, яким-небудь чином розбиваємо на блоки наші дані, в зону доступності 1 записуємо парні блоки, у другу — непарні, а в третю — результат побайтового XOR між блоками. Для виявлення помилок вважаємо по кожному блоку контрольну суму, яка пренебрежимо мала в порівнянні з розміром блоку. Відновлення даних елементарно: якщо a^b = c, b = a^c. Коефіцієнт надмірності при такому підході — 1,5. При втраті будь-якого блоку потрібно прочитати два інших, причому з різних зон доступності. Відновлення можливе при втраті не більше ніж одного диска, що набагато гірше, ніж у випадку трьох реплік, і порівнянно з двома репліками. Ось як вважається результат XOR для рядок «Hello, habrahabr» (цифри знизу — десяткове подання байта):


Тут варто ввести поняття страйпа. Страйп — це N послідовних блоків, причому початок першого страйпа збігається з початком потоку даних, N залежить від обраної схеми кодування, і у випадку з RAID 1 N=2. Для ефективного застосування кодів надмірності потрібно об'єднати всі файли в один безперервний потік байтів, і вже розбивати на страйпы. Поруч слід зберегти розмітку, в якому стайпе і з якого байта починається кожен файл, а також його розмір. Якщо довжина потоку даних не кратна розміру страйпа, то треба частину заповнити нулями. Схематично це можна зобразити так:


При виборі розміру страйпа можна скористатися наступними міркуваннями:
  • чим більше розмір блоку, тим більше файлів поміститься в один блок і тим менше буде читань відразу з двох зон доступності,
  • чим більше розмір блоку, тим більше даних потрібно перетягнути по мережі у випадку тимчасової недоступності блоку або його втрати.
Таким чином, потрібно вважати ймовірності цих подій. У нас вийшло, що оптимальний розмір — дві медіани розміру файлу. Крім того, бажано так пересортировать файли, щоб границі блоків припадали на більш великі файли, які в один блок все одно б не помістилися. Це теж призведе до зниження навантаження на мережу. А щоб спростити код, функція зберігання блоків парності закріплюється за однією із зон доступності.
Коди Ріда-Соломона
Але що робити, якщо хочеться більшої надійності? Правильно — використовувати більш потужні коди надмірності. Зараз один з найбільш поширених кодів — це код Ріда-Соломона. Він використовується при запису DVD-дисків, цифрового ТВ (DVB-T), в QR-кодах, а також — у RAID 6. Ми тут не будемо розповідати про математику полів Галуа — вас чекає виключно інженерний підхід. Для всіх обчислень ми задіємо бібліотеку jerasure, у якій непроста доля, але яка працює дуже швидко і володіє всіма потрібними нам функціями.
Перше, що варто відзначити: для ефективного результату потрібно працювати в полях 2^8, 2^16, 2^32, тобто в машинних словах. Далі ми для простоти будемо використовувати поле 2^8 і працювати з байтами. Щоб приклад був більш конкретним, спробуємо досягти коефіцієнта реплікації 1,5, але з двома блоками парності. Для цього потрібно розділити дані на страйпы по 4 блоку кожен, і згенерувати 2 блоки парності. Якщо взяти з кожного блоку даних перший байт, то можна скласти вектор розмірності 4 і, аналогічно, вектор розмірності 2 для блоків парності. Щоб вектори розмірності 4 одержати вектор розмірності 2, його потрібно помножити на матрицю кодування розміром 2х4, причому множити треба по правилам роботи в полях Галуа, якщо дивитися з інженерної точки зору. Матриця, яка нам потрібна, називається матрицею Вандермонда. Для вибраного поля така матриця гарантує властивість, аналогічне відсутності лінійних комбінацій у звичайній алгебрі. При відновленні даних воно теж відіграє важливу роль.
Візьмемо один страйп даних «Hello, habrahabr». Він дуже вдало розбивається на 4 блоки по 4 байти у кожному, причому один байт відповідає одному слову кодування.


Отже, виходить наступна картинка:


Порахуємо блоки парності подібним чином, слово за словом (у нашому випадку — байт за байтом).
Якщо трохи змінити картинку і додати одиничну матрицю над матрицею кодування, то у вихідному векторі з'являться вихідні дані:


Припустимо, що ми втратили блок номер 2 і блок номер 4. Викреслимо відповідні рядки матриці і з правого вектора:


Потім звернемо отриману квадратну матрицю і домножим на неї обидві частини рівності:



Виходить, що для отримання вихідних даних потрібно всього лише провести таку ж операцію множення, як і при кодуванні! Якщо загубився всього один блок, то з матриці кодування, щоб вона стала квадратної, потрібно викреслити один з рядків, що відповідають блокам парності. Зверніть увагу, що перший рядок складається з одиниць і володіє особливою магією: підрахунок еквівалентний обчисленню XOR між усіма елементами і виконується в кілька разів швидше, ніж підрахунок будь-який інший рядка. Тому викидати цей рядок не варто.
Local Recovery Codes
Вийшло досить просто і, сподіваюся, зрозуміло. Але чи можна ще що-небудь поліпшити? Так, кажуть нам колеги з Microsoft Azure публікації. Цей метод називається Local Reconstruction Codes (LRC). Якщо розбити всі блоки даних на кілька груп (наприклад на дві групи), то можна кодувати блоки парності таким чином, щоб локалізувати виправлення помилок всередині груп. Для колишнього коефіцієнта реплікації 1,5 схема виглядає так: розбиваємо страйп на дві групи по чотири блоки, для кожної групи буде свій локальний блок парності плюс два глобальні блоки парності. Ця схема дозволяє виправити будь-які три помилки і близько 96% ситуацій з чотирма помилками. До рештою 4% ставляться випадки, коли всі чотири помилки припадає на одну групу, куди входять 4 блоку даних і локальний блок парності.


Знову застосувавши підхід «від простого до складного», ми взяли і розділили рядок одиниць в матриці кодування на дві наступним чином:
1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1
1 55 39 73 84 181 225 217
1 172 70 235 143 34 200 101
На жаль, на цей раз наш підхід дав збій. Спочатку все було добре, але коли ми написали тест, комбинаторно перебирающий всі варіанти теоретично відновлювальних помилок, то виявили, що частина з них наша матриця відновити не дозволяє. Довелося зануритися у вивчення публікацій. Відповідь знайшлася у тій же публікації від Microsoft, в розділі 2.2.1. Матрицю потрібно складати трохи більше хитро — на щастя, jerasure дозволяє нам з легкістю це зробити.
for row in range(4):
for column in range(8):
k = 8
index = row * k + column
is_first_half = column < k / 2
if row == 0:
matrix[index] = 1 if is_first_half else 0
elif row == 1:
matrix[index] = 0 if is_first_half else 1
elif row == 2:
shift = 1 if is_first_half else 2 ** (k / 2)
relative_column = column if is_first_half else (column - k / 2)
matrix[index] = shift * (1 + relative_column)
else:
prev = array[index - k]
matrix[index] = libjerasure.galois_single_multiply(prev, prev, 8)

З такою матрицею тест проходить успішно:
1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 1
1 2 3 4 16 32 48 64
1 4 5 16 29 116 105 205
Отже, ми сформували групи. Але не можна забувати, що система повинна залишатися працездатною при падінні цілої зони доступності. З використанням LRC цього можна домогтися, якщо розташувати блоки по зонам наступним чином:


Тут видно, що яку б рядок ми закреслили, в кожній групі локальності виявиться не більше трьох помилок, а значить, дані можна буде прочитати. Якщо ж зламається тільки один диск, на якому лежить один блок, то дані можна буде прочитати, запросивши з іншої зони доступності всього лише один додатковий блок. Міркування з приводу розміру блоку — приблизно такі ж, як і в схемі з XOR, з одним винятком: якщо вважати, що читання виявиться занадто дорогим тільки між зонами доступності, то розмір блоку можна зробити в чотири рази менше, так як вийде безперервна послідовність у межах однієї зони.
Практика
Тепер ви розумієте, що запрограмувати підрахунок кодів надмірності — досить проста задача, і можете застосовувати ці знання в своїх проектах. Варіанти, які ми розглянули в статті:
  • Репліки — дають кратну надмірність, легко реалізовані (часто — дефолтний варіант), працюють як на блочному, так і на файловому рівні.
  • XOR, надмірність — 1,5, можна реалізувати як на блочному, так і на файловому рівні, вимагає наявності трьох зон доступності.
  • Коди Ріда-Соломона — дозволяють гнучко вибирати ступінь надлишковості, але для відновлення одного блоку даних потрібно прочитати стільки ж блоків, скільки містить один страйп. Добре працюють тільки на блочному рівні.
  • LRС — схожі на коди Ріда-Соломона, але при одиночних збоях дозволяють читати менше даних, хоча і забезпечують відновлення даних в меншому відсотку випадків.
У MDS ми застосували схему LRC-8-2-2 (8 блоків даних, 2 блоку локальної парності і 2 блоки глобальної парності). У підсумку 1 капель, який мав 2 репліки і жив на 2 жорстких дисках, став розташовуватися на 12 жорстких дисках. Це суттєво ускладнило процедуру читання, так і відновлення після втрати жорсткого диска теж стало складніше. Зате ми отримали 25% економії дискового простору, що переважило всі мінуси. Щоб менше навантажувати мережа, запис даних відбувається в звичайні каплы з репліками. Конвертуємо ж ми їх, тільки коли вони повністю заповняться і читань стане трохи менше — тобто коли дані «охолонуть».
Про те, які проблеми у нас виникли при реалізації схеми, ми розповімо 15 жовтня на заході у нашому московському офісі. Приходьте, буде цікаво!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.