අතිරික්තය පෙනෙන්නේ මෙයයි

අතිරික්ත කේත* දත්ත ගබඩා කිරීමේ විශ්වසනීයත්වය වැඩි කිරීම සඳහා පරිගණක පද්ධතිවල බහුලව භාවිතා වේ. Yandex හි ඔවුන් බොහෝ ව්යාපෘති වල භාවිතා වේ. උදාහරණයක් ලෙස, අපගේ අභ්‍යන්තර වස්තු ගබඩාවේ අනුකරණය වෙනුවට අතිරික්ත කේත භාවිතා කිරීම විශ්වසනීයත්වය කැප නොකර මිලියන ගණනක් ඉතිරි කරයි. නමුත් ඒවායේ පුළුල් භාවිතය තිබියදීත්, අතිරික්ත කේතයන් ක්රියා කරන ආකාරය පිළිබඳ පැහැදිලි විස්තර ඉතා දුර්ලභ ය. තේරුම් ගැනීමට කැමති අය ආසන්න වශයෙන් පහත කරුණු වලට මුහුණ දෙති (සිට විකිපීඩියා):

මගේ නම Vadim, Yandex හි මම අභ්‍යන්තර වස්තු ගබඩා MDS සංවර්ධනය කරමින් සිටිමි. මෙම ලිපියෙන්, මම අතිරික්ත කේත (රීඩ්-සොලමන් සහ එල්ආර්සී කේත) න්‍යායාත්මක පදනම් සරල වචන වලින් විස්තර කරමි. සංකීර්ණ ගණිතය සහ දුර්ලභ පද නොමැතිව එය ක්‍රියා කරන ආකාරය මම ඔබට කියමි. අවසානයේ මම Yandex හි අතිරික්ත කේතයන් භාවිතා කිරීම සඳහා උදාහරණ දෙන්නෙමි.

මම ගණිතමය විස්තර ගණනාවක් විස්තරාත්මකව සලකා බලන්නේ නැත, නමුත් ගැඹුරට කිමිදීමට කැමති අය සඳහා මම සබැඳි ලබා දෙන්නෙමි. ලිපිය ගණිතඥයින් සඳහා නොව, ගැටලුවේ සාරය තේරුම් ගැනීමට කැමති ඉංජිනේරුවන් සඳහා වන බැවින් සමහර ගණිතමය අර්ථ දැක්වීම් දැඩි නොවිය හැකි බව මම සටහන් කරමි.

* ඉංග්‍රීසි භාෂා සාහිත්‍යයේ, අතිරික්ත කේත බොහෝ විට මකන කේත ලෙස හැඳින්වේ.

1. අතිරික්ත කේතයන්ගේ සාරය

සියලුම අතිරික්ත කේතවල සාරය අතිශයින්ම සරල ය: දෝෂ ඇති වූ විට එය නැති නොවන පරිදි දත්ත ගබඩා කිරීම (හෝ සම්ප්‍රේෂණය කිරීම) (තැටි අසමත්වීම්, දත්ත හුවමාරු දෝෂ, ආදිය).

බොහෝ* අතිරික්ත කේත වලදී, දත්ත n දත්ත කොටස් වලට බෙදා ඇත, ඒ සඳහා අතිරික්ත කේත m කුට්ටි ගණනය කරනු ලැබේ, එහි ප්‍රතිඵලයක් ලෙස මුළු n + m කුට්ටි ඇතිවේ. අතිරික්ත කේත ගොඩනගා ඇත්තේ n + m බ්ලොක් වලින් කොටසක් පමණක් භාවිතා කර n බ්ලොක් දත්ත ප්‍රතිසාධනය කළ හැකි ආකාරයටය. මීලඟට, අපි සලකා බලන්නේ වාරණ අතිරික්ත කේතයන් පමණි, එනම් දත්ත බ්ලොක් වලට බෙදා ඇත.

සියලුම n දත්ත කොටස් ප්‍රතිසාධනය කිරීමට, ඔබට අවම වශයෙන් n + m කුට්ටි තිබිය යුතුය, මන්ද ඔබට n-1 බ්ලොක් එකක් පමණක් තිබීමෙන් n blocks ලබා ගත නොහැකි බැවින් (මෙම අවස්ථාවේදී, ඔබට "තුනී වලින් 1 block" ගැනීමට සිදුවේ. ගුවන්"). සියලුම දත්ත ප්‍රතිසාධනය කිරීමට n + m බ්ලොක් වල n සසම්භාවී බ්ලොක් ප්‍රමාණවත්ද? මෙය අතිරික්ත කේත වර්ගය මත රඳා පවතී, උදාහරණයක් ලෙස, රීඩ්-සොලමන් කේත ඔබට අත්තනෝමතික n බ්ලොක් භාවිතයෙන් සියලුම දත්ත ප්‍රතිසාධන කිරීමට ඉඩ සලසයි, නමුත් LRC අතිරික්ත කේත සෑම විටම නොවේ.

දත්ත ගබඩාව

දත්ත ගබඩා කිරීමේ පද්ධතිවල, රීතියක් ලෙස, එක් එක් දත්ත බ්ලොක් සහ අතිරික්ත කේත බ්ලොක් වෙනම තැටියකට ලියා ඇත. එවිට, අත්තනෝමතික තැටියක් අසමත් වුවහොත්, මුල් දත්ත තවමත් ප්රතිෂ්ඨාපනය කර කියවිය හැක. තැටි කිහිපයක් එකවර අසමත් වුවද දත්ත නැවත ලබා ගත හැක.

දත්ත හුවමාරුව

විශ්වාස කළ නොහැකි ජාලයක් හරහා විශ්වාසදායක ලෙස දත්ත සම්ප්‍රේෂණය කිරීමට අතිරික්ත කේත භාවිතා කළ හැක. සම්ප්රේෂණය කරන ලද දත්ත බ්ලොක් වලට බෙදී ඇති අතර, ඒවා සඳහා අතිරික්ත කේතයන් ගණනය කරනු ලැබේ. දත්ත වාරණ සහ අතිරික්ත කේත බ්ලොක් යන දෙකම ජාලය හරහා සම්ප්‍රේෂණය වේ. අත්තනෝමතික බ්ලොක් වල (නිශ්චිත වාරණ ගණනක් දක්වා) දෝෂ ඇති වුවහොත්, දත්ත තවමත් දෝෂ නොමැතිව ජාලය හරහා සම්ප්රේෂණය කළ හැක. උදාහරණයක් ලෙස, රීඩ්-සොලමන් කේත, දෘශ්‍ය සන්නිවේදන මාර්ග හරහා සහ චන්ද්‍රිකා සන්නිවේදනයන්හි දත්ත සම්ප්‍රේෂණය කිරීමට භාවිතා කරයි.

* Ethernet ජාල වල දත්ත සම්ප්‍රේෂණය සඳහා බහුලව භාවිතා වන Hamming කේත සහ CRC කේත වැනි බ්ලොක් වලට දත්ත බෙදී නොමැති අතිරික්ත කේත ද ඇත. මේවා දෝෂ නිවැරදි කිරීමේ කේතීකරණය සඳහා වන කේත වේ, ඒවා නිර්මාණය කර ඇත්තේ දෝෂ හඳුනා ගැනීමට මිස ඒවා නිවැරදි කිරීමට නොවේ (Hamming කේතය දෝෂ අර්ධ නිවැරදි කිරීමට ද ඉඩ සලසයි).

2. රීඩ්-සොලමන් කේත

රීඩ්-සොලමන් කේත යනු 1960 ගණන්වල නැවත සොයා ගන්නා ලද සහ සංයුක්ත තැටි විශාල වශයෙන් නිෂ්පාදනය කිරීම සඳහා 1980 ගණන්වල පුළුල් ලෙස භාවිතා කරන ලද බහුලව භාවිතා වන අතිරික්ත කේත වලින් එකකි.

රීඩ්-සොලමන් කේත තේරුම් ගැනීම සඳහා ප්‍රධාන ප්‍රශ්න දෙකක් තිබේ: 1) අතිරික්ත කේත කුට්ටි නිර්මාණය කරන්නේ කෙසේද; 2) අතිරික්ත කේත බ්ලොක් භාවිතයෙන් දත්ත නැවත ලබා ගන්නේ කෙසේද. අපි ඒවාට පිළිතුරු සොයා බලමු.
සරල බව සඳහා, අපි තවදුරටත් උපකල්පනය කරමු n=6 සහ m=4. අනෙකුත් යෝජනා ක්රම සාදෘශ්ය මගින් සලකනු ලැබේ.

අතිරික්ත කේත කුට්ටි නිර්මාණය කරන්නේ කෙසේද

අතිරික්ත කේත සෑම කොටසක්ම අනෙක් ඒවායින් ස්වාධීනව ගණනය කෙරේ. එක් එක් වාරණ ගණනය කිරීමට සියලුම n දත්ත කොටස් භාවිතා වේ. පහත රූප සටහනේ, X1-X6 යනු දත්ත කොටස්, P1-P4 යනු අතිරික්ත කේත කුට්ටි වේ.

සියලුම දත්ත කොටස් එකම ප්‍රමාණය විය යුතු අතර, පෙළගැස්වීම සඳහා බිටු බිටු භාවිතා කළ හැක. එහි ප්‍රතිඵලයක් ලෙස ලැබෙන අතිරික්ත කේත බ්ලොක් දත්ත වාරණවලට සමාන ප්‍රමාණයේ වනු ඇත. සියලුම දත්ත කොටස් වචන වලට බෙදා ඇත (උදාහරණයක් ලෙස, බිටු 16). අපි හිතමු අපි data blocks k වචන වලට බෙදුවා කියලා. එවිට අතිරික්ත කේත වල සියලුම කොටස් ද k වචන වලට බෙදනු ඇත.

එක් එක් අතිරික්ත වාරණවල i-th වචනය ගණන් කිරීමට, සියලු දත්ත කොටස්වල i-th වචන භාවිතා කරනු ඇත. ඒවා පහත සූත්‍රය අනුව ගණනය කරනු ලැබේ:

මෙහි අගයන් x යනු දත්ත බ්ලොක් වල වචන වේ, p යනු අතිරික්ත කේත බ්ලොක් වල වචන වේ, සියලුම ඇල්ෆා, බීටා, ගැමා සහ ඩෙල්ටා යනු සියලුම i සඳහා සමාන වන විශේෂයෙන් තෝරාගත් සංඛ්‍යා වේ. මෙම සියලු අගයන් සාමාන්‍ය සංඛ්‍යා නොව, ගැලෝයිස් ක්ෂේත්‍රයේ මූලද්‍රව්‍ය බව වහාම පැවසිය යුතුය; මෙහෙයුම් +, -, *, / යනු අප සැමට හුරුපුරුදු මෙහෙයුම් නොවේ, නමුත් ගලෝයිස් මූලද්‍රව්‍ය මත හඳුන්වා දුන් විශේෂ මෙහෙයුම් ක්ෂේත්රය.

Galois ක්ෂේත්ර අවශ්ය වන්නේ ඇයි?

සෑම දෙයක්ම සරල බව පෙනේ: අපි දත්ත බ්ලොක් වලට, බ්ලොක් වචන වලට බෙදන්න, දත්ත බ්ලොක් වල වචන භාවිතා කරමින් අපි අතිරික්ත කේත බ්ලොක් වල වචන ගණන් කරමු - අපට අතිරික්ත කේත කුට්ටි ලැබේ. පොදුවේ ගත් කල, එය ක්‍රියා කරන ආකාරය මෙයයි, නමුත් යක්ෂයා විස්තර වල ඇත:

1. ඉහත සඳහන් කළ පරිදි, වචන ප්රමාණය ස්ථාවර වේ, අපගේ උදාහරණයේ බිටු 16 කි. Reed-Solomon කේත සඳහා ඉහත සූත්‍ර සාමාන්‍ය පූර්ණ සංඛ්‍යා භාවිතා කරන විට, p ගණනය කිරීමේ ප්‍රතිඵලය වලංගු ප්‍රමාණයේ වචනයක් භාවිතයෙන් නිරූපණය කළ නොහැක.
2. දත්ත ප්‍රතිසාධනය කිරීමේදී ඉහත සූත්‍ර දත්ත ප්‍රතිසාධනය සඳහා විසඳිය යුතු සමීකරණ පද්ධතියක් ලෙස සලකනු ලැබේ. විසඳුම් ක්‍රියාවලියේදී, නිඛිල එකිනෙක බෙදීම අවශ්‍ය විය හැකි අතර, පරිගණක මතකයේ නිවැරදිව නිරූපණය කළ නොහැකි තාත්වික සංඛ්‍යාවක් ඇතිවේ.

මෙම ගැටළු රීඩ්-සොලමන් කේත සඳහා පූර්ණ සංඛ්‍යා භාවිතා කිරීම වළක්වයි. ගැටලුවට විසඳුම මුල් ය, එය පහත පරිදි විස්තර කළ හැකිය: අවශ්‍ය දිග (උදාහරණයක් ලෙස, බිටු 16) වචන භාවිතයෙන් නිරූපණය කළ හැකි විශේෂ සංඛ්‍යා සහ සියලු මෙහෙයුම් සිදු කිරීමේ ප්‍රති result ලය (එකතු කිරීම) ඉදිරිපත් කරමු. , අඩු කිරීම, ගුණ කිරීම, බෙදීම) අවශ්‍ය දිග වචන භාවිතා කරමින් පරිගණක මතකයේ ද ඉදිරිපත් කෙරේ.

එවැනි "විශේෂ" සංඛ්යා දිගු කාලයක් තිස්සේ ගණිතය විසින් අධ්යයනය කර ඇත; ඒවා ක්ෂේත්ර ලෙස හැඳින්වේ. ක්ෂේත්‍රයක් යනු ඒවා සඳහා අර්ථ දක්වා ඇති එකතු කිරීම, අඩු කිරීම, ගුණ කිරීම සහ බෙදීම යන මෙහෙයුම් සහිත මූලද්‍රව්‍ය සමූහයකි.

Galois* ක්ෂේත්‍ර යනු ක්ෂේත්‍රයේ ඕනෑම මූලද්‍රව්‍ය දෙකක් සඳහා එක් එක් මෙහෙයුමේ (+, -, *, /) අනන්‍ය ප්‍රතිඵලයක් ඇති ක්ෂේත්‍ර වේ. Galois ක්ෂේත්‍ර 2: 2, 4, 8, 16 වැනි බල ඇති සංඛ්‍යා සඳහා ගොඩනගා ගත හැක (ඇත්ත වශයෙන්ම ඕනෑම ප්‍රථමක සංඛ්‍යාවක බල p, නමුත් ප්‍රායෝගිකව අප උනන්දු වන්නේ 2 හි බල ගැන පමණි). උදාහරණයක් ලෙස, 16-bit වචන සඳහා, මෙය මූලද්‍රව්‍ය 65 ක් අඩංගු ක්ෂේත්‍රයක් වන අතර, සෑම යුගලයක් සඳහාම ඔබට ඕනෑම මෙහෙයුමක ප්‍රතිඵලයක් සොයාගත හැකිය (+, -, *, /). ඉහත සමීකරණ වලින් x, p, alpha, beta, gamma, delta වල අගයන් ගණනය කිරීම් සඳහා Galois ක්ෂේත්රයේ මූලද්රව්ය ලෙස සලකනු ලැබේ.

මේ අනුව, අපට සුදුසු පරිගණක වැඩසටහනක් ලිවීමෙන් අතිරික්ත කේත කුට්ටි සෑදිය හැකි සමීකරණ පද්ධතියක් ඇත. එකම සමීකරණ පද්ධතිය භාවිතා කරමින්, ඔබට දත්ත ප්රතිසාධනය සිදු කළ හැකිය.

* මෙය දැඩි අර්ථ දැක්වීමක් නොව, විස්තරයකි.

දත්ත නැවත ලබා ගන්නේ කෙසේද

සමහර n + m කුට්ටි අස්ථානගත වූ විට ප්‍රතිසාධනය අවශ්‍ය වේ. මේවා දත්ත වාරණ සහ අතිරික්ත කේත බ්ලොක් යන දෙකම විය හැකිය. දත්ත අවහිර කිරීම් සහ/හෝ අතිරික්ත කේත අවහිර කිරීම් නොමැති වීමෙන් අදහස් වන්නේ ඉහත සමීකරණවල අදාළ x සහ/හෝ p විචල්‍යයන් නොදන්නා බවයි.

Reed-Solomon කේත සඳහා වන සමීකරණ සියලු ඇල්ෆා, බීටා, ගැමා, ඩෙල්ටා අගයන් නියත වන සමීකරණ පද්ධතියක් ලෙස දැකිය හැකිය, පවතින කුට්ටි වලට අනුරූප වන සියලුම x සහ p දන්නා විචල්‍යයන් වන අතර ඉතිරි x සහ p නොදනිති.

උදාහරණයක් ලෙස, දත්ත වාරණ 1, 2, 3 සහ අතිරික්ත කේත වාරණ 2 නොතිබීමට ඉඩ දෙන්න, එවිට i-th වචන සමූහය සඳහා පහත සමීකරණ පද්ධතියක් ඇත (නොදන්නා ඒවා රතු පැහැයෙන් සලකුණු කර ඇත):

අප සතුව නොදන්නා 4 ක් සහිත සමීකරණ 4 ක පද්ධතියක් ඇත, එනම් අපට එය විසඳා දත්ත යථා තත්වයට පත් කළ හැකිය!

මෙම සමීකරණ පද්ධතියෙන් Reed-Solomon කේත (n දත්ත වාරණ, m අතිරික්ත කේත කුට්ටි) සඳහා දත්ත ප්‍රතිසාධනය පිළිබඳ නිගමන ගණනාවක් අනුගමනය කරයි:

• යම් m blocks හෝ ඊට අඩු ගණනක් නැති වුවහොත් දත්ත නැවත ලබාගත හැක. m+1 හෝ ඊට වැඩි වාරණ නැති වුවහොත්, දත්ත ප්‍රතිසාධනය කළ නොහැක: m + 1 නොදන්නා අය සමඟ m සමීකරණ පද්ධතියක් විසඳිය නොහැක.
• එක් දත්ත වාරණයක් ප්‍රතිසාධනය කිරීමට, ඔබට ඉතිරිව ඇති ඕනෑම n එකක් භාවිතා කළ යුතු අතර, ඔබට ඕනෑම අතිරික්ත කේතයක් භාවිතා කළ හැක.

තව මොනවද දැනගන්න ඕන

ඉහත විස්තරයේ දී, සලකා බැලීම සඳහා ගණිතයට ගැඹුරින් කිමිදීමක් අවශ්‍ය වන වැදගත් කරුණු ගණනාවක් මම මග හරිමි. විශේෂයෙන්, මම පහත සඳහන් දේ ගැන කිසිවක් නොකියමි:

• රීඩ්-සොලමන් කේත සඳහා සමීකරණ පද්ධතියට නොදන්නා (m නොදන්නා ඒවාට වඩා වැඩි) ඕනෑම සංයෝජනයක් සඳහා (අද්විතීය) විසඳුමක් තිබිය යුතුය. මෙම අවශ්‍යතාවය මත පදනම්ව, ඇල්ෆා, බීටා, ගැමා සහ ඩෙල්ටා අගයන් තෝරා ගනු ලැබේ.
• සමීකරණ පද්ධතියක් ස්වයංක්‍රීයව ගොඩනගා ගත හැකි විය යුතුය (පවතින කුට්ටි මොනවාද යන්න මත පදනම්ව) සහ විසඳිය යුතුය.
• අපි Galois ක්ෂේත්‍රයක් ගොඩනගා ගත යුතුයි: දී ඇති වචන ප්‍රමාණය සඳහා, ඕනෑම මූලද්‍රව්‍ය දෙකක් සඳහා ඕනෑම මෙහෙයුමක ප්‍රතිඵලයක් (+, -, *, /) සොයා ගැනීමට හැකි වීම.

ලිපියේ අවසානයේ මෙම වැදගත් කරුණු පිළිබඳ සාහිත්‍ය පිළිබඳ සඳහනක් ඇත.

n සහ m තේරීම

ප්රායෝගිකව n සහ m තෝරා ගන්නේ කෙසේද? ප්රායෝගිකව, දත්ත ගබඩා කිරීමේ පද්ධති තුළ, ඉඩ ඉතිරි කිරීම සඳහා අතිරික්ත කේතයන් භාවිතා කරනු ලැබේ, එබැවින් m සෑම විටම n ට වඩා අඩුවෙන් තෝරා ගනු ලැබේ. ඒවායේ නිශ්චිත අගයන් ඇතුළුව සාධක ගණනාවක් මත රඳා පවතී:

• දත්ත ගබඩා කිරීමේ විශ්වසනීයත්වය. විශාල m, නොනැසී පැවතිය හැකි තැටි අසමත්වීම් ගණන වැඩි වේ, එනම්, විශ්වසනීයත්වය වැඩි වේ.
• අතිරික්ත ගබඩා කිරීම. m/n අනුපාතය වැඩි වන තරමට ගබඩා අතිරික්තය වැඩි වන අතර පද්ධතිය මිල අධික වනු ඇත.
• සැකසුම් කාලය ඉල්ලන්න. n + m එකතුව විශාල වන තරමට, ඉල්ලීම් සඳහා ප්‍රතිචාර දැක්වීමේ කාලය දිගු වේ. දත්ත කියවීම (ප්‍රතිසාධනය අතරතුර) n විවිධ තැටිවල ගබඩා කර ඇති n බ්ලොක් කියවීම අවශ්‍ය වන බැවින්, කියවීමේ කාලය මන්දගාමීම තැටිය මගින් තීරණය වේ.

මීට අමතරව, DC කිහිපයක දත්ත ගබඩා කිරීම n සහ m තේරීමට අමතර සීමාවන් පනවයි: 1 DC ක්‍රියා විරහිත කර ඇත්නම්, දත්ත කියවීම සඳහා තවමත් තිබිය යුතුය. උදාහරණයක් ලෙස, DC 3ක දත්ත ගබඩා කිරීමේදී පහත කොන්දේසිය සපුරාලිය යුතුය: m >= n/2, එසේ නොමැතිනම් 1 DC ක්‍රියාවිරහිත කළ විට දත්ත කියවීමට නොහැකි තත්වයක් ඇති විය හැක.

3. LRC - දේශීය ප්‍රතිසංස්කරණ කේත

Reed-Solomon කේත භාවිතයෙන් දත්ත ප්‍රතිසාධනය කිරීමට, ඔබට n අත්තනෝමතික දත්ත වාරණ භාවිතා කිරීමට සිදුවේ. බෙදා හරින ලද දත්ත ගබඩා කිරීමේ පද්ධති සඳහා මෙය ඉතා වැදගත් අවාසියකි, මන්ද එක් කැඩුණු තැටියක දත්ත යථා තත්වයට පත් කිරීම සඳහා, ඔබට අනෙක් බොහෝ දත්ත කියවීමට සිදුවනු ඇත, තැටි සහ ජාලයේ විශාල අමතර බරක් නිර්මාණය කරයි.

වඩාත්ම පොදු දෝෂ වන්නේ එක් තැටියක අසමත් වීම හෝ අධි බර පැටවීම හේතුවෙන් එක් දත්ත කොටසකට ප්රවේශ විය නොහැකි වීමයි. මෙම (වඩාත් පොදු) නඩුවේ දත්ත ප්රතිසාධනය සඳහා අතිරික්ත බර කෙසේ හෝ අඩු කළ හැකිද? ඔබට කළ හැකි බව පෙනේ: මේ සඳහා විශේෂයෙන් LRC අතිරික්ත කේත තිබේ.

LRC (Local Reconstruction Codes) යනු Windows Azure Storage හි භාවිතය සඳහා Microsoft විසින් සොයා ගන්නා ලද අතිරික්ත කේත වේ. 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 භාවිතා කිරීම.

ඉතිරිය Reed-Solomon කේත සමඟ සාදෘශ්‍යයෙන් LRC හි සිදු කෙරේ. අතිරික්ත කේත කුට්ටි වල වචන ගණනය කිරීමේ සමීකරණ වනුයේ:

ඇල්ෆා, බීටා, ගැමා, ඩෙල්ටා අංක තෝරා ගැනීම සඳහා, දත්ත ප්‍රතිසාධනය කිරීමේ හැකියාව සහතික කිරීම සඳහා කොන්දේසි ගණනාවක් සපුරාලිය යුතුය (එනම්, සමීකරණ පද්ධතිය විසඳීම). ඔබට ඔවුන් ගැන වැඩිදුර කියවිය හැකිය ලිපියයි.
එසේම ප්රායෝගිකව, XOR මෙහෙයුම දේශීය අතිරික්ත කේත P3, P4 ගණනය කිරීමට භාවිතා කරයි.

LRC සඳහා සමීකරණ පද්ධතියෙන් නිගමන ගණනාවක් අනුගමනය කරයි:

• ඕනෑම දත්ත වාරණ 1ක් ප්‍රතිසාධනය කිරීමට, n/l blocks (අපගේ උදාහරණයේ 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. වෙනත් අතිරික්ත කේත

රීඩ්-සොලමන් සහ එල්ආර්සී කේත හැර, තවත් බොහෝ අතිරික්ත කේත තිබේ. විවිධ අතිරික්ත කේත විවිධ ගණිත භාවිතා කරයි. මෙන්න තවත් අතිරික්ත කේත කිහිපයක්:

• XOR ක්රියාකරු භාවිතා කරන අතිරික්ත කේතය. XOR මෙහෙයුම n දත්ත කොටස් මත සිදු කරනු ලබන අතර, අතිරික්ත කේත 1 ක් ලබා ගනී, එනම් n+1 යෝජනා ක්‍රමයක් (n දත්ත වාරණ, 1 අතිරික්ත කේතය). භාවිතා කර ඇත RAID 5, දත්ත කුට්ටි සහ අතිරික්ත කේත අරාවේ සියලුම තැටි වලට චක්‍රීයව ලියා ඇත.
• XOR මෙහෙයුම මත පදනම් වූ ඉරට්ටේ-ඔත්තේ ඇල්ගොරිතම. ඔබට අතිරික්ත කේත 2 ක් තැනීමට ඉඩ සලසයි, එනම් n+2 යෝජනා ක්‍රමය.
• XOR මෙහෙයුම මත පදනම් වූ STAR ඇල්ගොරිතම. ඔබට අතිරික්ත කේත 3 ක් තැනීමට ඉඩ සලසයි, එනම් n+3 යෝජනා ක්‍රමය.
• පිරමිඩ කේත Microsoft වෙතින් තවත් අතිරික්ත කේතයකි.

5. Yandex හි භාවිතා කරන්න

Yandex යටිතල පහසුකම් ව්යාපෘති ගණනාවක් විශ්වසනීය දත්ත ගබඩා කිරීම සඳහා අතිරික්ත කේතයන් භාවිතා කරයි. මෙන්න උදාහරණ කිහිපයක්:

• MDS අභ්‍යන්තර වස්තු ගබඩාව, මම ලිපියේ ආරම්භයේදී ලියා ඇත.
• YT - Yandex හි MapReduce පද්ධතිය.
• YDB (Yandex DataBase) - newSQL බෙදා හරින ලද දත්ත සමුදාය.

MDS LRC අතිරික්ත කේත, 8-2-2 යෝජනා ක්‍රමය භාවිතා කරයි. අතිරික්ත කේත සහිත දත්ත විවිධ DCs 12 ක් තුළ විවිධ සේවාදායකයන් තුළ විවිධ තැටි 3 කට ලියා ඇත: එක් එක් DC හි සේවාදායක 4 ක්. මේ ගැන වැඩිදුර කියවන්න ලිපියයි.

YT ප්‍රථමයෙන් ක්‍රියාත්මක කළ රීඩ්-සොලමන් කේත (6-3 යෝජනා ක්‍රමය) සහ LRC අතිරික්ත කිරීමේ කේත (යෝජනා ක්‍රමය 12-2-2) භාවිතා කරයි, LRC වඩාත් කැමති ගබඩා ක්‍රමය වේ.

YDB ඉරට්ටේ-ඔත්තේ පදනම් වූ අතිරික්ත කේත භාවිතා කරයි (රූපය 4-2). දැනටමත් YDB හි අතිරික්ත කේත ගැන Highload එකේ කිව්වා.

විවිධ අතිරික්ත කේත යෝජනා ක්‍රම භාවිතා කිරීම පද්ධති සඳහා විවිධ අවශ්‍යතා නිසාය. උදාහරණයක් ලෙස, MDS හි, LRC භාවිතයෙන් ගබඩා කර ඇති දත්ත එකවර DC 3ක් තුළ තැන්පත් කෙරේ. කිසියම් DC එකක් අසමත් වුවහොත් කියවීම සඳහා දත්ත ඉතිරිව තිබීම අපට වැදගත් වේ, එබැවින් කිසියම් DC නොමැති නම්, ප්‍රවේශ විය නොහැකි බ්ලොක් ගණන අවසර ලත් ප්‍රමාණයට වඩා වැඩි නොවන පරිදි කුට්ටි DC හරහා බෙදා හැරිය යුතුය. 1-8-2 යෝජනා ක්‍රමයේදී, ඔබට සෑම DC එකකම බ්ලොක් 2 ක් තැබිය හැකිය, එවිට ඕනෑම DC ක්‍රියා විරහිත කළ විට, බ්ලොක් 4 ක් නොතිබෙනු ඇත, සහ දත්ත කියවිය හැක. DC 4 ක් තුළ තැබීමේදී අප තෝරා ගන්නා යෝජනා ක්රමය කුමක් වුවත්, ඕනෑම අවස්ථාවක (r + l) / n >= 3 තිබිය යුතුය, එනම් ගබඩා අතිරික්තය අවම වශයෙන් 0,5% කි.

YT හි තත්වය වෙනස් වේ: සෑම YT පොකුරක්ම සම්පූර්ණයෙන්ම 1 DC (විවිධ DC වල විවිධ පොකුරු) පිහිටා ඇත, එබැවින් එවැනි සීමාවක් නොමැත. 12-2-2 යෝජනා ක්‍රමය 33% අතිරික්තයක් සපයයි, එනම් දත්ත ගබඩා කිරීම ලාභදායී වන අතර MDS යෝජනා ක්‍රමය මෙන් එය එකවර තැටි ඇනහිටීම් 4 ක් දක්වා පැවතිය හැකිය.

දත්ත ගබඩා කිරීමේ සහ සැකසුම් පද්ධතිවල අතිරික්ත කේත භාවිතයේ තවත් බොහෝ විශේෂාංග තිබේ: දත්ත ප්‍රතිසාධනයේ සූක්ෂ්මතා, විමසුම් ක්‍රියාත්මක කිරීමේ වේලාවට ප්‍රතිසාධනයේ බලපෑම, දත්ත පටිගත කිරීමේ විශේෂාංග යනාදිය. මම මේවා සහ වෙනත් විශේෂාංග ගැන වෙන වෙනම කතා කරන්නෙමි. ප්‍රායෝගිකව අතිරික්ත කේත භාවිතා කිරීම, මාතෘකාව සිත්ගන්නාසුළු නම්.

6. සබැඳි

1. රීඩ්-සොලමන් කේත සහ ගලෝයිස් ක්ෂේත්‍ර පිළිබඳ ලිපි මාලාවක්: https://habr.com/ru/company/yadro/blog/336286/
   https://habr.com/ru/company/yadro/blog/341506/
   ඔවුන් ප්‍රවේශ විය හැකි භාෂාවෙන් ගණිතය දෙස ගැඹුරින් බලයි.
2. LRC ගැන Microsoft වෙතින් ලිපිය: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/LRC12-cheng20webpage.pdf
   2 වන කොටස න්‍යාය කෙටියෙන් පැහැදිලි කරන අතර පසුව ප්‍රායෝගිකව LRC සමඟ අත්දැකීම් සාකච්ඡා කරයි.
3. ඉරට්ටේ-ඔත්තේ යෝජනා ක්රමය: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
4. ස්ටාර් යෝජනා ක්රමය: https://www.usenix.org/legacy/event/fast05/tech/full_papers/huang/huang.pdf
5. පිරමිඩ කේත: https://www.microsoft.com/en-us/research/publication/pyramid-codes-flexible-schemes-to-trade-space-for-access-efficiency-in-reliable-data-storage-systems/
6. MDS හි අතිරික්ත කේත: https://habr.com/ru/company/yandex/blog/311806
7. YT හි අතිරික්ත කේත: https://habr.com/ru/company/yandex/blog/311104/
8. YDB හි අතිරික්ත කේත: https://www.youtube.com/watch?v=dCpfGJ35kK8

මූලාශ්රය: www.habr.com