Артықшылық осылай көрінеді
Қосымша кодтар* деректерді сақтаудың сенімділігін арттыру үшін компьютерлік жүйелерде кеңінен қолданылады. Яндексте олар көптеген жобаларда қолданылады. Мысалы, ішкі нысан қоймасында репликацияның орнына артық кодтарды пайдалану сенімділікті жоғалтпай миллиондаған адамдарды үнемдейді. Бірақ олардың кең таралғанына қарамастан, артық кодтардың қалай жұмыс істейтіні туралы нақты сипаттамалар өте сирек кездеседі. Түсінгісі келетіндер шамамен келесі жағдайларға тап болады ( ):
Менің атым Вадим, Яндексте мен MDS ішкі объектілерді сақтауды әзірлеп жатырмын. Бұл мақалада мен артық кодтардың теориялық негіздерін қарапайым сөздермен сипаттаймын (Рид-Соломон және LRC кодтары). Мен сізге оның қалай жұмыс істейтінін, күрделі математикасыз және сирек кездесетін терминдерсіз айтып беремін. Соңында мен Яндекс-те артық кодтарды пайдалану мысалдарын келтіремін.
Мен бірқатар математикалық мәліметтерді егжей-тегжейлі қарастырмаймын, бірақ тереңірек сүңгуді қалайтындар үшін сілтемелер беремін. Мақала математиктерге емес, мәселенің мәнін түсінгісі келетін инженерлерге арналғандықтан, кейбір математикалық анықтамалар қатаң болмауы мүмкін екенін де атап өтейін.
* Ағылшын тіліндегі әдебиеттерде артық кодтар жиі өшіру кодтары деп аталады.
1. Артық кодтардың мәні
Барлық резервтік кодтардың мәні өте қарапайым: қателер пайда болған кезде (диск ақаулары, деректерді беру қателері және т.б.) жоғалып кетпеуі үшін деректерді сақтаңыз (немесе жіберіңіз).
Көпшілік* резервтік кодтарда деректер n деректер блогына бөлінеді, олар үшін резервтік кодтардың m блогы есептеледі, нәтижесінде барлығы n + m блок болады. Артық кодтар деректердің n блогын n + m блоктардың бір бөлігін ғана пайдаланып қалпына келтіруге болатындай етіп құрастырылған. Әрі қарай, біз тек блоктың артық кодтарын, яғни деректер блоктарға бөлінген кодтарды қарастырамыз.
Деректердің барлық n блогын қалпына келтіру үшін сізде кемінде n n + m блок болуы керек, өйткені тек n-1 блокқа ие болу арқылы n блокты ала алмайсыз (бұл жағдайда сіз жұқа блоктан 1 блокты алуыңыз керек еді) ауа»). Барлық деректерді қалпына келтіру үшін n + m блоктан тұратын n кездейсоқ блок жеткілікті ме? Бұл резервтік кодтардың түріне байланысты, мысалы, Reed-Solomon кодтары ерікті n блоктарды пайдаланып барлық деректерді қалпына келтіруге мүмкіндік береді, бірақ LRC резервтік кодтары әрқашан бола бермейді.
деректерді сақтау
Мәліметтерді сақтау жүйелерінде, әдетте, деректер блоктарының және артық код блоктарының әрқайсысы жеке дискіге жазылады. Содан кейін, егер ерікті диск сәтсіз болса, бастапқы деректерді әлі де қалпына келтіруге және оқуға болады. Бір уақытта бірнеше дискілер істен шыққан жағдайда да деректерді қалпына келтіруге болады.
Деректерді беру
Деректерді сенімсіз желі арқылы сенімді түрде жіберу үшін резервтік кодтарды пайдалануға болады. Жіберілген деректер блоктарға бөлінеді, олар үшін резервтік кодтар есептеледі. Деректер блоктары да, артық код блоктары да желі арқылы беріледі. Егер қателер ерікті блоктарда (блоктардың белгілі бір санына дейін) орын алса, деректерді желі арқылы қатесіз жіберуге болады. Рид-Соломон кодтары, мысалы, оптикалық байланыс желілері арқылы және спутниктік байланыста деректерді беру үшін қолданылады.
* Сондай-ақ Ethernet желілерінде деректерді беру үшін кеңінен қолданылатын Хамминг кодтары және CRC кодтары сияқты деректер блоктарға бөлінбейтін резервтік кодтар бар. Бұл қателерді түзететін кодтауға арналған кодтар, олар қателерді түзетуге емес, анықтауға арналған (Хэмминг коды қателерді ішінара түзетуге де мүмкіндік береді).
2. Рид-Соломон кодтары
Reed-Solomon кодтары 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 536 элементтен тұратын өріс, оның әрбір жұбы үшін кез келген операцияның нәтижесін табуға болады (+, -, *, /). Жоғарыдағы теңдеулерден x, p, альфа, бета, гамма, дельта мәндері есептеулер үшін Галуа өрісінің элементтері болып саналады.
Осылайша, бізде сәйкес компьютерлік бағдарламаны жазу арқылы артық кодтардың блоктарын құра алатын теңдеулер жүйесі бар. Бірдей теңдеулер жүйесін пайдалана отырып, деректерді қалпына келтіруді орындауға болады.
* Бұл қатаң анықтама емес, керісінше сипаттама.
Деректерді қалай қалпына келтіруге болады
Кейбір n + m блоктары жоқ болған кезде қалпына келтіру қажет. Бұл деректер блоктары да, артық код блоктары да болуы мүмкін. Деректер блоктарының және/немесе артық код блоктарының болмауы жоғарыдағы теңдеулерде сәйкес x және/немесе p айнымалыларының белгісіз екенін білдіреді.
Рид-Соломон кодтарына арналған теңдеулерді барлық альфа, бета, гамма, дельта мәндері тұрақты болып табылатын теңдеулер жүйесі ретінде қарастыруға болады, қол жетімді блоктарға сәйкес барлық x және p белгілі айнымалылар, ал қалған x және p белгісіз.
Мысалы, 1, 2, 3 деректер блоктары және резервтік код блогы 2 қолжетімсіз болсын, содан кейін i-ші сөздер тобы үшін келесі теңдеулер жүйесі болады (белгісіздер қызыл түспен белгіленген):
Бізде 4 белгісізі бар 4 теңдеу жүйесі бар, яғни біз оны шешіп, деректерді қалпына келтіре аламыз!
Осы теңдеулер жүйесінен Reed-Solomon кодтары (n деректер блогы, m артық код блоктары) үшін деректерді қалпына келтіру туралы бірқатар қорытындылар шығады:
- Кез келген m немесе одан аз блок жоғалса, деректерді қалпына келтіруге болады. Егер m+1 немесе одан да көп блоктар жоғалса, деректерді қалпына келтіру мүмкін емес: m+1 белгісіздері бар m теңдеулер жүйесін шешу мүмкін емес.
- Тіпті бір деректер блогын қалпына келтіру үшін қалған блоктардың кез келген n-ін пайдалану керек және артық кодтардың кез келгенін пайдалануға болады.
Сізге тағы не білу керек
Жоғарыдағы сипаттамада мен математикаға тереңірек енуді қажет ететін бірқатар маңызды мәселелерден аулақпын. Атап айтқанда, мен мыналар туралы ештеңе айтпаймын:
- Рид-Соломон кодтары үшін теңдеулер жүйесінде белгісіздердің кез келген комбинациясы (м белгісіз) үшін (бірегей) шешімі болуы керек. Осы талаптың негізінде альфа, бета, гамма және дельта мәндері таңдалады.
- Теңдеулер жүйесі автоматты түрде құрылуы (қай блоктардың жоқтығына байланысты) және шешілуі мүмкін болуы керек.
- Бізге Галуа өрісін құру керек: берілген сөз өлшемі үшін кез келген екі элемент үшін кез келген операцияның нәтижесін (+, -, *, /) таба білу.
Мақаланың соңында осы маңызды мәселелер бойынша әдебиеттерге сілтемелер берілген.
n және m таңдау
Практикада n және m қалай таңдауға болады? Тәжірибеде деректерді сақтау жүйелерінде кеңістікті үнемдеу үшін резервтік кодтар қолданылады, сондықтан m әрқашан n-ден аз таңдалады. Олардың нақты мәндері бірқатар факторларға байланысты, соның ішінде:
- Мәліметтерді сақтаудың сенімділігі. Неғұрлым m үлкен болса, соғұрлым сақталатын диск ақауларының саны көп болады, яғни сенімділік соғұрлым жоғары болады.
- Артық сақтау. m/n қатынасы неғұрлым жоғары болса, сақтаудың артықтығы соғұрлым жоғары болады және жүйе соғұрлым қымбатырақ болады.
- Сұраныс өңдеу уақыты. n+m сомасы неғұрлым үлкен болса, сұрауларға жауап беру уақыты соғұрлым ұзағырақ болады. Деректерді оқу (қалпына келтіру кезінде) n түрлі дискіде сақталған n блокты оқуды қажет ететіндіктен, оқу уақыты ең баяу диск арқылы анықталады.
Сонымен қатар, деректерді бірнеше тұрақты токтарда сақтау n және m таңдауына қосымша шектеулер қояды: егер 1 тұрақты ток өшірілсе, деректер әлі де оқу үшін қолжетімді болуы керек. Мысалы, деректерді 3 тұрақты токта сақтау кезінде келесі шарт орындалуы керек: m >= n/2, әйтпесе 1 тұрақты ток өшірілгенде деректер оқу үшін қолжетімсіз болатын жағдай болуы мүмкін.
3. LRC - Жергілікті қайта құру кодтары
Reed-Solomon кодтары арқылы деректерді қалпына келтіру үшін n ерікті деректер блоктарын пайдалану керек. Бұл таратылған деректерді сақтау жүйелері үшін өте маңызды кемшілік, өйткені бір бұзылған дискідегі деректерді қалпына келтіру үшін дискілер мен желіге үлкен қосымша жүктеме жасай отырып, басқалардың көпшілігінен деректерді оқуға тура келеді.
Ең жиі кездесетін қателер - бір дискінің ақаулығы немесе шамадан тыс жүктелуі салдарынан бір деректер блогына қол жетімсіздігі. Бұл (ең таралған) жағдайда деректерді қалпына келтіруге арналған артық жүктемені қандай да бір жолмен азайту мүмкін бе? Сіз жасай аласыз: осы мақсат үшін арнайы LRC резервтік кодтары бар.
LRC (Жергілікті қайта құру кодтары) — Microsoft корпорациясы Windows Azure қоймасында пайдалану үшін ойлап тапқан резервтік кодтар. 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 барлық деректер блоктары арқылы есептеледі. Р3 резервтік код блогы - X1-X3 деректер блоктарын пайдалану, Р4 резервтік код блогы - 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 рұқсат етілген қателердің максималды саны бойынша Рид-Соломон кодтарынан төмен. Жоғарыдағы мысалдарда Reed-Solomon кодтары кез келген 4 қате үшін деректерді қалпына келтіре алады, ал LRC үшін деректерді қалпына келтіру мүмкін болмаған кезде 2 қатенің 4 комбинациясы бар.
Неғұрлым маңыздысы нақты жағдайға байланысты, бірақ көбінесе LRC қамтамасыз ететін артық жүктемені үнемдеу сенімділігі аз сақтаудан асып түседі.
4. Басқа артық кодтар
Reed-Solomon және LRC кодтарынан басқа, көптеген басқа резервтік кодтар бар. Әртүрлі артық кодтар әртүрлі математиканы пайдаланады. Міне, басқа резервтік кодтар:
- XOR операторын қолданатын резервтік код. XOR операциясы n деректер блогында орындалады және резервтік кодтардың 1 блогы алынады, яғни n+1 схемасы (n деректер блогы, 1 резервтік код). Қолданылған , мұнда деректер блоктары және артық кодтар массивтің барлық дискілеріне циклдік түрде жазылады.
- XOR операциясына негізделген жұп-тақ алгоритм. Артық кодтардың 2 блогын, яғни n+2 схемасын құруға мүмкіндік береді.
- XOR операциясына негізделген STAR алгоритмі. Артық кодтардың 3 блогын, яғни n+3 схемасын құруға мүмкіндік береді.
- Пирамидтік кодтар - Microsoft корпорациясының басқа резервтік кодтары.
5. Яндексте пайдаланыңыз
Яндекстің бірқатар инфрақұрылымдық жобалары деректерді сенімді сақтау үшін резервтік кодтарды пайдаланады. Міне, кейбір мысалдар:
- Мен мақаланың басында жазған ішкі нысанды сақтау MDS.
- — Яндекстің MapReduce жүйесі.
- (Yandex DataBase) – newSQL таратылған деректер қоры.
MDS LRC резервтік кодтарын, 8-2-2 схемасын пайдаланады. Артық кодтары бар деректер 12 түрлі DC-дегі әртүрлі серверлердегі 3 түрлі дискілерге жазылады: әр DC-де 4 сервер. Бұл туралы толығырақ бөлімде оқыңыз .
YT бірінші болып енгізілген Reed-Solomon кодтарын (6-3 схемасы) және LRC артық кодтарын (12-2-2 схемасы) пайдаланады, бұл ретте LRC сақтаудың қолайлы әдісі болып табылады.
YDB жұп тақ негізіндегі артық кодтарды пайдаланады (4-2-сурет). YDB-дегі резервтік кодтар туралы .
Әртүрлі резервтік код схемаларын пайдалану жүйелерге қойылатын әртүрлі талаптарға байланысты. Мысалы, MDS-те LRC көмегімен сақталған деректер бірден 3 DC-ге орналастырылады. Кез келген тұрақты токтың біреуі істен шыққан жағдайда деректер оқу үшін қолжетімді болып қалуы біз үшін маңызды, сондықтан кез келген DC қолжетімсіз болса, қол жетімсіз блоктар саны рұқсат етілгеннен аспауы үшін блоктар тұрақты токтар бойынша таратылуы керек. 1-8-2 схемасында әрбір тұрақты токта 2 блокты орналастыруға болады, содан кейін кез келген тұрақты ток өшірілгенде 4 блок қолжетімсіз болады және деректерді оқуға болады. Оны 4 DC-ге орналастырған кезде қандай схеманы таңдасақ та, кез келген жағдайда (r + l) / n >= 3 болуы керек, яғни сақтаудың артықтығы кем дегенде 0,5% болады.
YT-де жағдай басқаша: әрбір YT кластері толығымен 1 тұрақты токта орналасқан (әртүрлі DC-дегі әртүрлі кластерлер), сондықтан мұндай шектеу жоқ. 12-2-2 схемасы 33% артықшылықты қамтамасыз етеді, яғни деректерді сақтау арзанырақ, сонымен қатар ол MDS схемасы сияқты бір уақытта дискідегі 4 рет үзілуге дейін аман қалады.
Деректерді сақтау және өңдеу жүйелерінде артық кодтарды қолданудың тағы да көптеген мүмкіндіктері бар: деректерді қалпына келтірудің нюанстары, қалпына келтірудің сұраудың орындалу уақытына әсері, деректерді жазу ерекшеліктері және т.б. Мен осы және басқа мүмкіндіктер туралы бөлек айтқым келеді. егер тақырып қызықты болатын болса, тәжірибеде артық кодтарды қолдану туралы.
6. Сілтемелер
- Рид-Соломон кодтары және Галуа өрістері туралы мақалалар сериясы:
Олар математиканы қол жетімді тілде тереңірек қарастырады. - LRC туралы Microsoft мақаласы:
2-бөлім теорияны қысқаша түсіндіреді, содан кейін тәжірибеде LRC тәжірибесін талқылайды. - Жұп-тақ схемасы:
- STAR схемасы:
- Пирамида кодтары:
- MDS-тегі артық кодтар:
- YT-дегі артық кодтар:
- YDB ішіндегі резервтік кодтар:
Ақпарат көзі: www.habr.com