Так выглядае надмернасць
Коды надмернасці* шырока прымяняюцца ў камп'ютарных сістэмах для павелічэння надзейнасці захоўвання даных. У Яндэксе іх выкарыстоўваюць у шматлікіх праектах. Напрыклад, ужыванне кодаў надмернасці замест рэплікацыі ў нашым унутраным аб'ектным сховішчы эканоміць мільёны без паніжэння надзейнасці. Але нягледзячы на шырокі распаўсюд, зразумелае апісанне таго, як працуюць коды надмернасці, сустракаецца вельмі рэдка. Жадаючыя разабрацца сутыкаюцца прыкладна з наступным (з ):
Мяне клічуць Вадзім, у Яндэксе я займаюся распрацоўкай унутранага аб'ектнага сховішча 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 слоў. Тады ўсе блокі кодаў надмернасці таксама будуць разбітыя на словы.
Для падліку 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 - Local Reconstruction Codes
Для аднаўлення дадзеных з дапамогай кодаў Рыда - Саламона даводзіцца выкарыстоўваць 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 па аналогіі з кодамі Рыда - Саламона. Ураўненні для падліку слоў блокаў кодаў надмернасці будуць наступнымі:
Для падбору лікаў альфа, бэта, гама, дэльта трэба выканаць шэраг умоў, якія гарантуюць магчымасць узнаўлення дадзеных (гэта значыць рашэнні сістэмы раўнання). Больш падрабязна пра іх можна прачытаць у .
Таксама на практыцы для падліку лакальных кодаў надмернасці 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 блокі, і дадзеныя можна будзе чытаць. Якую б схему мы ні абралі пры размяшчэнні ў 3 ДЦ, у любым выпадку павінна быць (r + l) / n> = 0,5, гэта значыць надмернасць захоўвання будзе мінімум 50%.
У YT сітуацыя іншая: кожны кластар YT цалкам размяшчаецца ў 1 ДЦ (розныя кластары ў розных ДЦ), таму тамака няма такога абмежавання. Схема 12-2-2 дае надмернасць 33%, гэта значыць захоўваць дадзеныя выходзіць танней, пры гэтым яны таксама могуць перажываць да 4 адначасовых адключэнняў дыскаў, як і схема ў MDS.
Ёсць яшчэ шмат асаблівасцяў ужывання кодаў надмернасці ў сістэмах захоўвання і апрацоўкі дадзеных: нюансы ўзнаўлення дадзеных, уплыў узнаўлення на час выканання запытаў, асаблівасці запісу дадзеных і т. д. Я збіраюся асобна распавесці аб гэтых і іншых асаблівасцях ужывання кодаў надмернасці на практыку, калі тэма будзе цікавая.
6. Спасылкі
- Серыя артыкулаў пра коды Рыда — Саламона і палі Галуа:
У іх даступнай мовай глыбей разглядаецца матэматыка. - Microsoft пра LRC:
У раздзеле 2 коратка тлумачыцца тэорыя, далей разглядаецца досвед ужывання LRC на практыцы. - Схема even-odd:
- Схема STAR:
- Pyramid codes:
- Коды надмернасці ў MDS:
- Коды надмернасці ў YT:
- Коды надмернасці ў YDB:
Крыніца: habr.com