Ин аст, ки зиёдатӣ ба назар мерасад
Рамзхои зиёдатй* дар системахои хисоббарор барои баланд бардоштани эътимоднокии нигохдории маълумот васеъ истифода мешаванд. Дар Яндекс онҳо дар бисёр лоиҳаҳо истифода мешаванд. Масалан, истифодаи рамзҳои зиёдатӣ ба ҷои такрорӣ дар нигаҳдории объекти дохилии мо миллионҳо нафарро бидуни қурбонии эътимод сарфа мекунад. Аммо сарфи назар аз истифодаи васеъи онҳо, тавсифи равшани он, ки чӣ гуна рамзҳои зиёдатӣ кор мекунанд, хеле каманд. Онҳое, ки мехоҳанд дарк кунанд, тақрибан бо инҳо дучор мешаванд (аз ):
Номи ман Вадим, дар Яндекс ман MDS нигоҳдории объекти дохилиро таҳия мекунам. Дар ин мақола, ман бо суханони оддӣ асосҳои назариявии кодҳои зиёдатӣ (кодҳои Рид-Соломон ва LRC) тавсиф мекунам. Ман ба шумо мегӯям, ки он чӣ тавр кор мекунад, бе математикаи мураккаб ва истилоҳҳои нодир. Дар охир ман мисолҳои истифодаи рамзҳои зиёдатӣ дар Яндекс медиҳам.
Ман як қатор ҷузъиёти математикиро ба таври муфассал баррасӣ намекунам, аммо ман барои онҳое, ки мехоҳанд амиқтар ғарқ шаванд, истинодҳо хоҳам дод. Ман инчунин қайд мекунам, ки баъзе таърифҳои риёзӣ шояд сахт набошанд, зеро мақола на барои математикҳо, балки барои муҳандисоне пешбинӣ шудааст, ки моҳияти масъаларо фаҳмидан мехоҳанд.
* Дар адабиёти забони англисӣ, рамзҳои зиёдатӣ аксар вақт рамзҳои тозакунӣ номида мешаванд.
1. Моњияти рамзњои зиёдатї
Моҳияти ҳамаи рамзҳои зиёдатӣ ниҳоят оддӣ аст: маълумотро нигоҳ доред (ё интиқол диҳед) то он ки ҳангоми рух додани хатогиҳо (корношоямии диск, хатогиҳои интиқоли маълумот ва ғ.) гум нашавад.
Дар аксар* кодхои зиёдатй, маълумот ба n блоки додахо таксим карда мешавад, ки барои онхо m блоки кодхои зиёдатй ба хисоб гирифта мешаванд, ки дар натича n+m блокхо чамъ мешаванд. Рамзҳои зиёдатӣ тавре сохта шудаанд, ки n блоки маълумотро танҳо бо истифода аз як қисми блокҳои n + m барқарор кардан мумкин аст. Минбаъд, мо танҳо рамзҳои изофии блокро баррасӣ хоҳем кард, яъне онҳое, ки дар онҳо маълумот ба блокҳо тақсим карда шудааст.
Барои барқарор кардани ҳамаи n блокҳои додаҳо, шумо бояд ҳадди аққал n блоки n + m дошта бошед, зеро шумо наметавонед n блокро бо доштани танҳо n-1 блок ба даст оред (дар ин ҳолат, шумо бояд 1 блок "аз борик" гиред. ҳаво"). Оё n блоки тасодуфии n + m блок барои барқарор кардани ҳама маълумот кофӣ аст? Ин аз намуди рамзҳои зиёдатӣ вобаста аст, масалан, рамзҳои Reed-Solomon ба шумо имкон медиҳанд, ки ҳама маълумотро бо истифода аз блокҳои худсарона барқарор кунед, аммо рамзҳои зиёдатии 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 бит) ва натиҷаи иҷрои ҳама амалҳое, ки аз рӯи онҳо (илова кардан) ифода кардан мумкин аст. , тарњ, зарб, таќсим) низ дар хотираи компютер бо истифода аз калимањои дарозии зарурї пешкаш карда мешавад.
Чунин ракамхои «махсус»-ро риёзиёт кайхо боз омухтааст, онхоро майдонхо меноманд. Майдон маҷмӯи элементҳоест, ки барои онҳо амалҳои ҷамъ, тарҳ, зарб ва тақсим муайян карда шудаанд.
Майдонҳои Galois* майдонҳое мебошанд, ки барои онҳо натиҷаи ягонаи ҳар як амалиёт (+, -, *, /) барои ҳар ду элементи майдон мавҷуд аст. Майдонҳои Галуаро барои ададҳое сохтан мумкин аст, ки қудрати 2: 2, 4, 8, 16 ва ғайра мебошанд (воқеан қудратҳои ҳар як адади ибтидоии p, аммо дар амал мо танҳо ба қудрати 2 таваҷҷӯҳ дорем). Масалан, барои калимаҳои 16-битӣ, ин майдонест, ки 65 элементро дар бар мегирад, ки барои ҳар як ҷуфти онҳо шумо метавонед натиҷаи ҳама гуна амалиётро пайдо кунед (+, -, *, /). Қиматҳои x, p, alpha, beta, gamma, delta аз муодилаҳои дар боло овардашуда унсурҳои майдони Галуа барои ҳисобҳо ҳисобида мешаванд.
Ҳамин тариқ, мо системаи муодилаҳое дорем, ки бо он мо метавонем блокҳои кодҳои зиёдатӣ тавассути навиштани барномаи мувофиқи компютерӣ созем. Бо истифода аз ҳамон системаи муодилаҳо, шумо метавонед барқароркунии маълумотро иҷро кунед.
* Ин таърифи сахт не, балки тавсиф аст.
Чӣ тавр барқарор кардани маълумот
Вақте ки баъзе аз блокҳои 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 номаълум) ҳалли (нодир) дошта бошад. Дар асоси ин талабот, арзишҳои алфа, бета, гамма ва дельта интихоб карда мешаванд.
- Системаи муодилаҳо бояд қодир бошанд, ки ба таври худкор сохта шаванд (вобаста ба он, ки кадом блокҳо дастрас нестанд) ва ҳал карда шаванд.
- Мо бояд майдони Galois созем: барои андозаи калимаи додашуда, қодир ба пайдо кардани натиҷаи ҳама гуна амалиёт (+, -, *, /) барои ҳар ду элемент.
Дар охири мақола истинод ба адабиёт оид ба ин масъалаҳои муҳим оварда шудааст.
Интихоби n ва m
Чӣ тавр интихоб кардани n ва m дар амал? Дар амал дар системаҳои нигоҳдории маълумот кодҳои зиёдатӣ барои сарфаи ҷой истифода мешаванд, аз ин рӯ m ҳамеша камтар аз n интихоб карда мешавад. Арзиши мушаххаси онҳо аз як қатор омилҳо вобаста аст, аз ҷумла:
- Эътимоднокии нигоҳдории маълумот. Чӣ қадаре ки м калон бошад, ҳамон қадар шумораи шикасти дискҳо, ки наҷот ёфтан мумкин аст, зиёдтар аст, яъне эътимоднокӣ ҳамон қадар баландтар аст.
- Захираи зиёдатӣ. Чӣ қадаре ки таносуби м/n баланд бошад, ҳамон қадар захираи изофӣ зиёд мешавад ва система ҳамон қадар гаронтар мешавад.
- Вақти коркарди дархост. Чӣ қадаре ки маблағи n+m зиёд бошад, вақти посух ба дархостҳо ҳамон қадар зиёдтар мешавад. Азбаски хондани маълумот (ҳангоми барқарорсозӣ) хондани n блоки дар n дискҳои гуногун нигоҳ дошташударо талаб мекунад, вақти хондан аз ҷониби диски сусттарин муайян карда мешавад.
Илова бар ин, нигоҳ доштани маълумот дар якчанд DC-ҳо барои интихоби n ва m маҳдудиятҳои иловагӣ мегузорад: агар 1 DC хомӯш карда шавад, маълумот бояд барои хондан дастрас бошад. Масалан, њангоми нигоњ доштани маълумот дар 3 DC, шарти зерин бояд риоя карда шавад: m >= n/2, вагарна вазъияте ба вуљуд омада метавонад, ки маълумот њангоми хомўш кардани 1 DC барои хондан дастнорас аст.
3. LRC - Кодексҳои барқарорсозии маҳаллӣ
Барои барқарор кардани маълумот бо истифода аз рамзҳои Reed-Solomon, шумо бояд n блоки маълумотро истифода баред. Ин як нуқсони хеле муҳим барои системаҳои нигоҳдории маълумотҳои тақсимшуда мебошад, зеро барои барқарор кардани маълумот дар як диски шикаста, шумо бояд маълумотро аз аксари дигарон хонед ва дар дискҳо ва шабака бори зиёди иловагӣ эҷод кунед.
Хатогиҳои маъмултарин ин дастнорас будани як блоки додаҳо аз сабаби нокомӣ ё изофабории як диск мебошад. Оё имкон дорад, ки дар ин ҳолат (аз ҳама маъмул) сарбории зиёдатиро барои барқарорсозии маълумот кам кунад? Маълум мешавад, ки шумо метавонед: барои ин мақсад рамзҳои зиёдатии LRC вуҷуд доранд.
LRC (Рамзҳои барқарорсозии маҳаллӣ) рамзҳои зиёдатӣ мебошанд, ки аз ҷониби Microsoft барои истифода дар Windows Azure Storage ихтироъ шудааст. Идеяи LRC то ҳадди имкон содда аст: ҳамаи блокҳои маълумотро ба ду (ё бештар) гурӯҳ тақсим кунед ва як қисми блокҳои рамзи изофӣ барои ҳар як гурӯҳ алоҳида хонед. Сипас баъзе блокҳои коди зиёдатӣ бо истифода аз ҳама блокҳои додаҳо ҳисоб карда мешаванд (дар LRC онҳоро кодҳои глобалии зиёдатӣ меноманд) ва баъзеҳо - бо истифода аз яке аз ду гурӯҳи блокҳои додаҳо (онҳоро кодҳои зиёдатии маҳаллӣ меноманд).
LRC бо се рақам ишора мешавад: nrl, ки дар он n шумораи блокҳои додаҳо, r шумораи блокҳои коди изофӣ дар глобалӣ, l шумораи блокҳои коди зиёдатии маҳаллӣ мебошад. Барои хондани маълумот, вақте ки як блоки додаҳо мавҷуд нест, шумо бояд танҳо блокҳои n/l-ро хонед - ин нисбат ба рамзҳои Reed-Solomon 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 бартарӣ дорад. Дар рамзҳои 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 созед.
- Алгоритми STAR дар асоси амалиёти XOR. Ба шумо имкон медиҳад, ки 3 блоки рамзҳои зиёдатӣ, яъне схемаи n+3 созед.
- Рамзҳои пирамида дигар рамзҳои зиёдатӣ аз Microsoft мебошанд.
5. Дар Яндекс истифода баред
Як қатор лоиҳаҳои инфрасохтори Яндекс рамзҳои зиёдатӣ барои нигоҳдории боэътимоди маълумотро истифода мебаранд. Инҳоянд чанд мисол:
- Нигоҳдории объекти дохилии MDS, ки ман дар бораи он дар аввали мақола навишта будам.
- — Системаи MapReduce Yandex.
- (Yandex DataBase) - пойгоҳи додаҳои тақсимшудаи newSQL.
MDS рамзҳои зиёдатии LRC, схемаи 8-2-2 -ро истифода мебарад. Маълумот бо рамзҳои зиёдатӣ ба 12 дискҳои гуногун дар серверҳои гуногун дар 3 DC-и гуногун навишта мешаванд: 4 сервер дар ҳар як DC. Дар ин бора бештар дар .
YT ҳам кодҳои Reed-Solomon (Схемаи 6-3), ки аввалин шуда татбиқ карда шуданд ва ҳам кодҳои зиёдатии LRC (Схемаи 12-2-2) -ро истифода мебарад, ки LRC усули афзалиятноки нигоҳдорӣ мебошад.
YDB рамзҳои зиёдатӣ дар асоси ҷуфт-тоқро истифода мебарад (Расми 4-2). Дар бораи рамзҳои зиёдатӣ дар YDB аллакай .
Истифодаи схемаҳои кодҳои изофӣ аз сабаби талаботҳои гуногун барои системаҳо вобаста аст. Масалан, дар MDS, маълумоте, ки бо истифода аз LRC нигоҳ дошта мешавад, якбора дар 3 DC ҷойгир карда мешавад. Барои мо муҳим аст, ки агар 1 аз ягон DC ноком шавад, маълумот барои хондан дастрас боқӣ мемонад, бинобар ин блокҳо бояд дар байни DC-ҳо тақсим карда шаванд, то агар ягон DC дастрас набошад, шумораи блокҳои дастнорас аз иҷозатдодашуда зиёд набошад. Дар схемаи 8-2-2, шумо метавонед дар ҳар як DC 4 блок ҷойгир кунед, пас вақте ки ягон DC хомӯш карда мешавад, 4 блок дастнорас хоҳад буд ва маълумотро хондан мумкин аст. Новобаста аз он ки мо ҳангоми ҷойгир кардани он дар 3 DC-ро интихоб мекунем, дар ҳар сурат бояд (r + l) / n >= 0,5 бошад, яъне зиёдатии нигоҳдорӣ ҳадди аққал 50% хоҳад буд.
Дар YT вазъият гуногун аст: ҳар як кластери YT пурра дар 1 DC ҷойгир аст (кластерҳои гуногун дар DC-ҳои гуногун), бинобар ин чунин маҳдудият вуҷуд надорад. Нақшаи 12-2-2 33% зиёдатӣ таъмин мекунад, яъне нигоҳдории маълумот арзонтар аст ва он инчунин метавонад то 4 қатъшавии диски ҳамзамон, ба монанди схемаи MDS, наҷот ёбад.
Дар системаҳои нигоҳдорӣ ва коркарди додаҳо хусусиятҳои зиёди истифодаи рамзҳои зиёдатӣ мавҷуданд: нозукиҳои барқароркунии маълумот, таъсири барқарорсозӣ ба вақти иҷрои дархост, хусусиятҳои сабти маълумот ва ғайра. Ман дар бораи ин ва дигар хусусиятҳо алоҳида сӯҳбат мекунам. дар бораи истифодаи кодхои зиёдатй дар амал, агар мавзуъ шавковар бошад.
6. Пайвандҳо
- Силсилаи мақолаҳо дар бораи рамзҳои Рид-Соломон ва майдонҳои Галуа:
Онҳо ба математика бо забони дастрас амиқтар назар мекунанд. - Мақолаи Microsoft дар бораи LRC:
Қисми 2 назарияро ба таври мухтасар шарҳ медиҳад ва сипас таҷрибаҳоро бо LRC дар амал баррасӣ мекунад. - Схемаи ҷуфт-тоқ:
- Нақшаи STAR:
- Рамзҳои пирамида:
- Рамзҳои зиёдатӣ дар MDS:
- Рамзҳои зиёдатӣ дар YT:
- Рамзҳои зиёдатӣ дар YDB:
Манбаъ: will.com