अतिरेक इसी तरह दिखता है

डेटा भंडारण की विश्वसनीयता बढ़ाने के लिए कंप्यूटर सिस्टम में रिडंडेंसी कोड* का व्यापक रूप से उपयोग किया जाता है। यांडेक्स में इनका उपयोग कई परियोजनाओं में किया जाता है। उदाहरण के लिए, हमारे आंतरिक ऑब्जेक्ट भंडारण में प्रतिकृति के बजाय अतिरेक कोड का उपयोग करने से विश्वसनीयता का त्याग किए बिना लाखों की बचत होती है। लेकिन उनके व्यापक उपयोग के बावजूद, अतिरेक कोड कैसे काम करते हैं इसका स्पष्ट विवरण बहुत दुर्लभ है। जो लोग समझना चाहते हैं उन्हें लगभग निम्नलिखित (से) का सामना करना पड़ता है विकिपीडिया):

मेरा नाम वादिम है, यांडेक्स में मैं आंतरिक ऑब्जेक्ट स्टोरेज एमडीएस विकसित कर रहा हूं। इस लेख में, मैं सरल शब्दों में अतिरेक कोड (रीड-सोलोमन और एलआरसी कोड) की सैद्धांतिक नींव का वर्णन करूंगा। मैं आपको बताऊंगा कि यह कैसे काम करता है, जटिल गणित और दुर्लभ शब्दों के बिना। अंत में मैं यांडेक्स में रिडंडेंसी कोड का उपयोग करने का उदाहरण दूंगा।

मैं कई गणितीय विवरणों पर विस्तार से विचार नहीं करूंगा, लेकिन मैं उन लोगों के लिए लिंक प्रदान करूंगा जो गहराई से जानना चाहते हैं। मैं यह भी नोट करूंगा कि कुछ गणितीय परिभाषाएँ सख्त नहीं हो सकती हैं, क्योंकि लेख गणितज्ञों के लिए नहीं है, बल्कि उन इंजीनियरों के लिए है जो मुद्दे का सार समझना चाहते हैं।

* अंग्रेजी भाषा के साहित्य में, अतिरेक कोड को अक्सर इरेज़र कोड कहा जाता है।

1. अतिरेक कोड का सार

सभी अतिरेक कोड का सार अत्यंत सरल है: डेटा को संग्रहीत (या संचारित) करें ताकि त्रुटियां (डिस्क विफलता, डेटा स्थानांतरण त्रुटियां, आदि) होने पर यह खो न जाए।

अधिकांश* अतिरेक कोड में, डेटा को n डेटा ब्लॉक में विभाजित किया जाता है, जिसके लिए अतिरेक कोड के m ब्लॉक की गणना की जाती है, जिसके परिणामस्वरूप कुल n + m ब्लॉक होते हैं। रिडंडेंसी कोड इस तरह से बनाए गए हैं कि डेटा के एन ब्लॉक को केवल एन + एम ब्लॉक के एक हिस्से का उपयोग करके पुनर्प्राप्त किया जा सकता है। आगे, हम केवल ब्लॉक रिडंडेंसी कोड पर विचार करेंगे, यानी वे जिनमें डेटा ब्लॉक में विभाजित है।

डेटा के सभी n ब्लॉक को पुनर्प्राप्त करने के लिए, आपके पास कम से कम n + m ब्लॉक होना चाहिए, क्योंकि आप केवल n-1 ब्लॉक होने से n ब्लॉक प्राप्त नहीं कर सकते हैं (इस मामले में, आपको पतले में से 1 ब्लॉक लेना होगा) वायु")। क्या n + m ब्लॉक के n यादृच्छिक ब्लॉक सभी डेटा को पुनर्प्राप्त करने के लिए पर्याप्त हैं? यह अतिरेक कोड के प्रकार पर निर्भर करता है, उदाहरण के लिए, रीड-सोलोमन कोड आपको मनमाने ढंग से एन ब्लॉक का उपयोग करके सभी डेटा को पुनर्प्राप्त करने की अनुमति देते हैं, लेकिन एलआरसी अतिरेक कोड हमेशा ऐसा नहीं करते हैं।

डेटा भंडारण

डेटा भंडारण प्रणालियों में, एक नियम के रूप में, प्रत्येक डेटा ब्लॉक और रिडंडेंसी कोड ब्लॉक एक अलग डिस्क पर लिखा जाता है। फिर, यदि कोई मनमानी डिस्क विफल हो जाती है, तो मूल डेटा को अभी भी पुनर्स्थापित किया जा सकता है और पढ़ा जा सकता है। एक ही समय में कई डिस्क विफल होने पर भी डेटा पुनर्प्राप्त किया जा सकता है।

डाटा ट्रांसफर

अतिरेक कोड का उपयोग अविश्वसनीय नेटवर्क पर डेटा को विश्वसनीय रूप से प्रसारित करने के लिए किया जा सकता है। प्रेषित डेटा को ब्लॉकों में विभाजित किया गया है, और उनके लिए अतिरेक कोड की गणना की जाती है। डेटा ब्लॉक और रिडंडेंसी कोड ब्लॉक दोनों नेटवर्क पर प्रसारित होते हैं। यदि मनमाने ब्लॉकों (ब्लॉकों की एक निश्चित संख्या तक) में त्रुटियां होती हैं, तो भी डेटा बिना किसी त्रुटि के नेटवर्क पर प्रसारित किया जा सकता है। उदाहरण के लिए, रीड-सोलोमन कोड का उपयोग ऑप्टिकल संचार लाइनों और उपग्रह संचार में डेटा संचारित करने के लिए किया जाता है।

* ऐसे रिडंडेंसी कोड भी होते हैं जिनमें डेटा को ब्लॉकों में विभाजित नहीं किया जाता है, जैसे हैमिंग कोड और सीआरसी कोड, जो ईथरनेट नेटवर्क में डेटा ट्रांसमिशन के लिए व्यापक रूप से उपयोग किए जाते हैं। ये त्रुटि-सुधार कोडिंग के लिए कोड हैं, इन्हें त्रुटियों का पता लगाने के लिए डिज़ाइन किया गया है, न कि उन्हें ठीक करने के लिए (हैमिंग कोड भी त्रुटियों के आंशिक सुधार की अनुमति देता है)।

2. रीड-सोलोमन कोड

रीड-सोलोमन कोड सबसे व्यापक रूप से उपयोग किए जाने वाले रिडंडेंसी कोड में से एक हैं, जिनका आविष्कार 1960 के दशक में किया गया था और पहली बार 1980 के दशक में कॉम्पैक्ट डिस्क के बड़े पैमाने पर उत्पादन के लिए व्यापक रूप से उपयोग किया गया था।

रीड-सोलोमन कोड को समझने के लिए दो प्रमुख प्रश्न हैं: 1) अतिरेक कोड के ब्लॉक कैसे बनाएं; 2) रिडंडेंसी कोड ब्लॉक का उपयोग करके डेटा कैसे पुनर्प्राप्त करें। आइए उनके उत्तर खोजें।
सरलता के लिए, हम आगे यह मानेंगे कि n=6 और m=4। अन्य योजनाओं पर सादृश्य द्वारा विचार किया जाता है।

रिडंडेंसी कोड ब्लॉक कैसे बनाएं

अतिरेक कोड के प्रत्येक ब्लॉक को दूसरों से स्वतंत्र रूप से गिना जाता है। प्रत्येक ब्लॉक को गिनने के लिए सभी n डेटा ब्लॉक का उपयोग किया जाता है। नीचे दिए गए चित्र में, X1-X6 डेटा ब्लॉक हैं, P1-P4 रिडंडेंसी कोड ब्लॉक हैं।

सभी डेटा ब्लॉक समान आकार के होने चाहिए, और संरेखण के लिए शून्य बिट्स का उपयोग किया जा सकता है। परिणामी अतिरेक कोड ब्लॉक डेटा ब्लॉक के समान आकार के होंगे। सभी डेटा ब्लॉक शब्दों में विभाजित हैं (उदाहरण के लिए, 16 बिट्स)। मान लीजिए कि हम डेटा ब्लॉक को k शब्दों में विभाजित करते हैं। फिर रिडंडेंसी कोड के सभी ब्लॉक को भी k शब्दों में विभाजित किया जाएगा।

प्रत्येक अतिरेक ब्लॉक के i-वें शब्द की गणना करने के लिए, सभी डेटा ब्लॉक के i-वें शब्द का उपयोग किया जाएगा। उनकी गणना निम्नलिखित सूत्र के अनुसार की जाएगी:

यहां x मान डेटा ब्लॉक के शब्द हैं, p रिडंडेंसी कोड ब्लॉक के शब्द हैं, सभी अल्फा, बीटा, गामा और डेल्टा विशेष रूप से चयनित संख्याएं हैं जो सभी i के लिए समान हैं। इसे तुरंत कहा जाना चाहिए कि ये सभी मान सामान्य संख्याएं नहीं हैं, बल्कि गैलोज़ फ़ील्ड के तत्व हैं; ऑपरेशन +, -, *, / हम सभी से परिचित ऑपरेशन नहीं हैं, लेकिन गैलोज़ के तत्वों पर पेश किए गए विशेष ऑपरेशन हैं मैदान।

गैलोज़ फ़ील्ड की आवश्यकता क्यों है?

ऐसा प्रतीत होता है कि सब कुछ सरल है: हम डेटा को ब्लॉक में विभाजित करते हैं, ब्लॉक को शब्दों में, डेटा ब्लॉक के शब्दों का उपयोग करके हम रिडंडेंसी कोड ब्लॉक के शब्दों को गिनते हैं - हमें रिडंडेंसी कोड ब्लॉक मिलते हैं। सामान्य तौर पर यह इसी तरह काम करता है, लेकिन शैतान विवरण में है:

1. जैसा कि ऊपर कहा गया है, शब्द का आकार निश्चित है, हमारे उदाहरण में 16 बिट्स। रीड-सोलोमन कोड के लिए उपरोक्त सूत्र ऐसे हैं कि सामान्य पूर्णांकों का उपयोग करते समय, पी की गणना का परिणाम वैध आकार के शब्द का उपयोग करके प्रस्तुत नहीं किया जा सकता है।
2. डेटा पुनर्प्राप्त करते समय, उपरोक्त सूत्रों को समीकरणों की एक प्रणाली के रूप में माना जाएगा जिसे डेटा पुनर्प्राप्त करने के लिए हल किया जाना चाहिए। समाधान प्रक्रिया के दौरान, पूर्णांकों को एक दूसरे से विभाजित करना आवश्यक हो सकता है, जिसके परिणामस्वरूप एक वास्तविक संख्या प्राप्त होगी जिसे कंप्यूटर मेमोरी में सटीक रूप से प्रस्तुत नहीं किया जा सकता है।

ये समस्याएँ रीड-सोलोमन कोड के लिए पूर्णांकों के उपयोग को रोकती हैं। समस्या का समाधान मूल है, इसे निम्नानुसार वर्णित किया जा सकता है: आइए विशेष संख्याओं के साथ आएं जिन्हें आवश्यक लंबाई (उदाहरण के लिए, 16 बिट्स) के शब्दों का उपयोग करके दर्शाया जा सकता है, और सभी परिचालनों को निष्पादित करने का परिणाम (अतिरिक्त) , घटाव, गुणा, भाग) को भी आवश्यक लंबाई के शब्दों का उपयोग करके कंप्यूटर मेमोरी में प्रस्तुत किया जाएगा।

ऐसी "विशेष" संख्याओं का गणित द्वारा लंबे समय से अध्ययन किया गया है; उन्हें फ़ील्ड कहा जाता है। फ़ील्ड तत्वों का एक समूह है जिसमें जोड़, घटाव, गुणा और भाग की संक्रियाएं परिभाषित होती हैं।

गैलोइस* फ़ील्ड वे फ़ील्ड हैं जिनके लिए फ़ील्ड के किन्हीं दो तत्वों के लिए प्रत्येक ऑपरेशन (+, -, *, /) का एक अद्वितीय परिणाम होता है। गैलोइस फ़ील्ड का निर्माण उन संख्याओं के लिए किया जा सकता है जो 2: 2, 4, 8, 16 आदि की घातें हैं (वास्तव में किसी भी अभाज्य संख्या p की घातें, लेकिन व्यवहार में हम केवल 2 की घातों में रुचि रखते हैं)। उदाहरण के लिए, 16-बिट शब्दों के लिए, यह एक फ़ील्ड है जिसमें 65 तत्व हैं, जिनमें से प्रत्येक जोड़ी के लिए आप किसी भी ऑपरेशन (+, -, *, /) का परिणाम पा सकते हैं। उपरोक्त समीकरणों से x, p, अल्फा, बीटा, गामा, डेल्टा के मानों को गणना के लिए गैलोज़ फ़ील्ड के तत्व माना जाएगा।

इस प्रकार, हमारे पास समीकरणों की एक प्रणाली है जिसके साथ हम एक उपयुक्त कंप्यूटर प्रोग्राम लिखकर अतिरेक कोड के ब्लॉक का निर्माण कर सकते हैं। समीकरणों की समान प्रणाली का उपयोग करके, आप डेटा पुनर्प्राप्ति कर सकते हैं।

* यह कोई सख्त परिभाषा नहीं है, बल्कि एक विवरण है।

डेटा कैसे रिकवर करें

जब कुछ n + m ब्लॉक गायब हों तो पुनर्स्थापना की आवश्यकता होती है। ये डेटा ब्लॉक और रिडंडेंसी कोड ब्लॉक दोनों हो सकते हैं। डेटा ब्लॉक और/या अतिरेक कोड ब्लॉक की अनुपस्थिति का मतलब यह होगा कि उपरोक्त समीकरणों में संबंधित x और/या p चर अज्ञात हैं।

रीड-सोलोमन कोड के समीकरणों को समीकरणों की एक प्रणाली के रूप में देखा जा सकता है जिसमें सभी अल्फा, बीटा, गामा, डेल्टा मान स्थिरांक हैं, उपलब्ध ब्लॉक के अनुरूप सभी x और p ज्ञात चर हैं, और शेष x और p अज्ञात हैं.

उदाहरण के लिए, मान लें कि डेटा ब्लॉक 1, 2, 3 और रिडंडेंसी कोड ब्लॉक 2 अनुपलब्ध हैं, तो शब्दों के i-वें समूह के लिए समीकरणों की निम्नलिखित प्रणाली होगी (अज्ञात को लाल रंग में चिह्नित किया गया है):

हमारे पास 4 अज्ञातों के साथ 4 समीकरणों की एक प्रणाली है, जिसका अर्थ है कि हम इसे हल कर सकते हैं और डेटा को पुनर्स्थापित कर सकते हैं!

समीकरणों की इस प्रणाली से रीड-सोलोमन कोड (एन डेटा ब्लॉक, एम रिडंडेंसी कोड ब्लॉक) के लिए डेटा रिकवरी के बारे में कई निष्कर्ष निकलते हैं:

• यदि कोई एम ब्लॉक या उससे कम खो जाता है तो डेटा पुनर्प्राप्त किया जा सकता है। यदि m+1 या अधिक ब्लॉक खो जाते हैं, तो डेटा को पुनर्स्थापित नहीं किया जा सकता है: m+1 अज्ञात के साथ m समीकरणों की प्रणाली को हल करना असंभव है।
• एक भी डेटा ब्लॉक को पुनर्प्राप्त करने के लिए, आपको शेष ब्लॉकों में से किसी भी n का उपयोग करने की आवश्यकता है, और आप किसी भी अतिरेक कोड का उपयोग कर सकते हैं।

आपको और क्या जानने की जरूरत है

उपरोक्त विवरण में, मैं कई महत्वपूर्ण मुद्दों से बचता हूँ जिन पर विचार करने के लिए गणित में गहराई से गोता लगाने की आवश्यकता होती है। विशेष रूप से, मैं निम्नलिखित के बारे में कुछ नहीं कह रहा हूँ:

• रीड-सोलोमन कोड के समीकरणों की प्रणाली में अज्ञात के किसी भी संयोजन के लिए एक (अद्वितीय) समाधान होना चाहिए (एम अज्ञात से अधिक नहीं)। इस आवश्यकता के आधार पर अल्फा, बीटा, गामा और डेल्टा के मूल्यों का चयन किया जाता है।
• समीकरणों की एक प्रणाली स्वचालित रूप से निर्मित होने में सक्षम होनी चाहिए (यह इस पर निर्भर करता है कि कौन से ब्लॉक अनुपलब्ध हैं) और हल किया जाना चाहिए।
• हमें एक गैलोइस फ़ील्ड बनाने की आवश्यकता है: किसी दिए गए शब्द आकार के लिए, किन्हीं दो तत्वों के लिए किसी भी ऑपरेशन (+, -, *, /) का परिणाम ढूंढने में सक्षम होना।

लेख के अंत में इन महत्वपूर्ण मुद्दों पर साहित्य के संदर्भ हैं।

एन और एम का चयन

व्यवहार में n और m का चयन कैसे करें? व्यवहार में, डेटा भंडारण प्रणालियों में, स्थान बचाने के लिए अतिरेक कोड का उपयोग किया जाता है, इसलिए m को हमेशा n से कम चुना जाता है। उनके विशिष्ट मूल्य कई कारकों पर निर्भर करते हैं, जिनमें शामिल हैं:

• डेटा भंडारण की विश्वसनीयता. एम जितना बड़ा होगा, डिस्क विफलताओं की संख्या उतनी ही अधिक होगी जिससे बचा जा सकता है, यानी विश्वसनीयता उतनी ही अधिक होगी।
• निरर्थक भंडारण. एम/एन अनुपात जितना अधिक होगा, भंडारण अतिरेक उतना ही अधिक होगा और सिस्टम उतना ही महंगा होगा।
• प्रसंस्करण समय का अनुरोध करें. n + m का योग जितना बड़ा होगा, अनुरोधों का प्रतिक्रिया समय उतना ही लंबा होगा। चूँकि डेटा पढ़ने के लिए (पुनर्प्राप्ति के दौरान) n विभिन्न डिस्क पर संग्रहीत n ब्लॉक को पढ़ने की आवश्यकता होती है, पढ़ने का समय सबसे धीमी डिस्क द्वारा निर्धारित किया जाएगा।

इसके अलावा, कई डीसी में डेटा संग्रहीत करने से एन और एम की पसंद पर अतिरिक्त प्रतिबंध लग जाता है: यदि 1 डीसी बंद हो जाता है, तो डेटा अभी भी पढ़ने के लिए उपलब्ध होना चाहिए। उदाहरण के लिए, 3 डीसी में डेटा संग्रहीत करते समय, निम्नलिखित शर्त पूरी होनी चाहिए: एम >= एन/2, अन्यथा ऐसी स्थिति हो सकती है जहां 1 डीसी बंद होने पर डेटा पढ़ने के लिए उपलब्ध नहीं होगा।

3. एलआरसी - स्थानीय पुनर्निर्माण कोड

रीड-सोलोमन कोड का उपयोग करके डेटा पुनर्प्राप्त करने के लिए, आपको n मनमाने डेटा ब्लॉक का उपयोग करना होगा। वितरित डेटा भंडारण प्रणालियों के लिए यह एक बहुत ही महत्वपूर्ण नुकसान है, क्योंकि एक टूटी हुई डिस्क पर डेटा को पुनर्स्थापित करने के लिए, आपको अधिकांश अन्य से डेटा पढ़ना होगा, जिससे डिस्क और नेटवर्क पर एक बड़ा अतिरिक्त भार पैदा होगा।

सबसे आम त्रुटियाँ एक डिस्क की विफलता या अधिभार के कारण डेटा के एक ब्लॉक की दुर्गमता हैं। क्या इस (सबसे सामान्य) मामले में डेटा पुनर्प्राप्ति के लिए अतिरिक्त भार को किसी तरह कम करना संभव है? यह पता चला है कि आप यह कर सकते हैं: इस उद्देश्य के लिए विशेष रूप से एलआरसी अतिरेक कोड मौजूद हैं।

एलआरसी (स्थानीय पुनर्निर्माण कोड) विंडोज़ एज़्योर स्टोरेज में उपयोग के लिए माइक्रोसॉफ्ट द्वारा आविष्कार किए गए रिडंडेंसी कोड हैं। एलआरसी का विचार यथासंभव सरल है: सभी डेटा ब्लॉक को दो (या अधिक) समूहों में विभाजित करें और प्रत्येक समूह के लिए रिडंडेंसी कोड ब्लॉक का हिस्सा अलग से पढ़ें। फिर कुछ अतिरेक कोड ब्लॉकों की गणना सभी डेटा ब्लॉक (एलआरसी में उन्हें वैश्विक अतिरेक कोड कहा जाता है) का उपयोग करके की जाएगी, और कुछ - डेटा ब्लॉक के दो समूहों में से एक का उपयोग करके (उन्हें स्थानीय अतिरेक कोड कहा जाता है)।

एलआरसी को तीन संख्याओं द्वारा दर्शाया गया है: एनआरएल, जहां एन डेटा ब्लॉक की संख्या है, आर वैश्विक रिडंडेंसी कोड ब्लॉक की संख्या है, एल स्थानीय रिडंडेंसी कोड ब्लॉक की संख्या है। जब एक डेटा ब्लॉक अनुपलब्ध हो तो डेटा पढ़ने के लिए, आपको केवल n/l ब्लॉक पढ़ने की आवश्यकता है - यह रीड-सोलोमन कोड की तुलना में l गुना कम है।

उदाहरण के लिए, एलआरसी 6-2-2 योजना पर विचार करें। X1–X6 - 6 डेटा ब्लॉक, P1, P2 - 2 वैश्विक अतिरेक ब्लॉक, P3, P4 - 2 स्थानीय अतिरेक ब्लॉक।

रिडंडेंसी कोड ब्लॉक P1, P2 की गणना सभी डेटा ब्लॉक का उपयोग करके की जाती है। रिडंडेंसी कोड ब्लॉक P3 - डेटा ब्लॉक X1-X3 का उपयोग करके, रिडंडेंसी कोड ब्लॉक P4 - डेटा ब्लॉक X4-X6 का उपयोग करके।

बाकी काम एलआरसी में रीड-सोलोमन कोड के अनुरूप किया जाता है। अतिरेक कोड ब्लॉक के शब्दों की गिनती के लिए समीकरण होंगे:

अल्फा, बीटा, गामा, डेल्टा संख्याओं का चयन करने के लिए, डेटा रिकवरी की संभावना की गारंटी के लिए कई शर्तों को पूरा करना होगा (अर्थात, समीकरण प्रणाली को हल करना)। आप उनके बारे में और अधिक पढ़ सकते हैं लेख.
व्यवहार में भी, XOR ऑपरेशन का उपयोग स्थानीय अतिरेक कोड P3, P4 की गणना के लिए किया जाता है।

एलआरसी के लिए समीकरणों की प्रणाली से कई निष्कर्ष निकलते हैं:

• किसी भी 1 डेटा ब्लॉक को पुनर्प्राप्त करने के लिए, n/l ब्लॉक (हमारे उदाहरण में n/2) को पढ़ना पर्याप्त है।
• यदि r + l ब्लॉक अनुपलब्ध हैं, और सभी ब्लॉक एक समूह में शामिल हैं, तो डेटा को पुनर्स्थापित नहीं किया जा सकता है। इसे एक उदाहरण से समझाना आसान है. मान लें कि ब्लॉक X1-X3 और P3 अनुपलब्ध हैं: ये एक ही समूह से r + l ब्लॉक हैं, हमारे मामले में 4। फिर हमारे पास 3 अज्ञात के साथ 4 समीकरणों की एक प्रणाली है जिसे हल नहीं किया जा सकता है।
• आर + एल ब्लॉक की अनुपलब्धता के अन्य सभी मामलों में (जब प्रत्येक समूह से कम से कम एक ब्लॉक उपलब्ध हो), एलआरसी में डेटा को बहाल किया जा सकता है।

इस प्रकार, एलआरसी एकल त्रुटियों के बाद डेटा पुनर्प्राप्त करने में रीड-सोलोमन कोड से बेहतर प्रदर्शन करता है। रीड-सोलोमन कोड में, डेटा के एक ब्लॉक को पुनर्प्राप्त करने के लिए, आपको n ब्लॉक का उपयोग करने की आवश्यकता होती है, और LRC में, डेटा के एक ब्लॉक को पुनर्प्राप्त करने के लिए, n/l ब्लॉक (हमारे उदाहरण में n/2) का उपयोग करने के लिए पर्याप्त है। दूसरी ओर, अनुमेय त्रुटियों की अधिकतम संख्या के मामले में एलआरसी रीड-सोलोमन कोड से कमतर है। उपरोक्त उदाहरणों में, रीड-सोलोमन कोड किसी भी 4 त्रुटियों के लिए डेटा पुनर्प्राप्त कर सकते हैं, और एलआरसी के लिए 2 त्रुटियों के 4 संयोजन हैं जब डेटा पुनर्प्राप्त नहीं किया जा सकता है।

क्या अधिक महत्वपूर्ण है यह विशिष्ट स्थिति पर निर्भर करता है, लेकिन अक्सर एलआरसी द्वारा प्रदान किए जाने वाले अतिरिक्त भार में बचत थोड़े कम विश्वसनीय भंडारण से अधिक होती है।

4. अन्य अतिरेक कोड

रीड-सोलोमन और एलआरसी कोड के अलावा, कई अन्य अतिरेक कोड हैं। अलग-अलग अतिरेक कोड अलग-अलग गणित का उपयोग करते हैं। यहां कुछ अन्य अतिरेक कोड हैं:

• XOR ऑपरेटर का उपयोग करके रिडंडेंसी कोड। XOR ऑपरेशन n डेटा ब्लॉक पर किया जाता है, और रिडंडेंसी कोड का 1 ब्लॉक प्राप्त होता है, यानी, एक n+1 योजना (n डेटा ब्लॉक, 1 रिडंडेंसी कोड)। में इस्तेमाल किया RAID 5, जहां डेटा के ब्लॉक और अतिरेक कोड चक्रीय रूप से सरणी के सभी डिस्क पर लिखे जाते हैं।
• XOR ऑपरेशन पर आधारित सम-विषम एल्गोरिदम। आपको अतिरेक कोड के 2 ब्लॉक, यानी एन+2 योजना बनाने की अनुमति देता है।
• XOR ऑपरेशन पर आधारित STAR एल्गोरिदम। आपको अतिरेक कोड के 3 ब्लॉक, यानी n+3 योजना बनाने की अनुमति देता है।
• पिरामिड कोड माइक्रोसॉफ्ट का एक और अतिरेक कोड है।

5. यांडेक्स में उपयोग करें

कई यांडेक्स इंफ्रास्ट्रक्चर परियोजनाएं विश्वसनीय डेटा भंडारण के लिए रिडंडेंसी कोड का उपयोग करती हैं। यहां कुछ उदाहरण दिए गए हैं:

• एमडीएस आंतरिक ऑब्जेक्ट भंडारण, जिसके बारे में मैंने लेख की शुरुआत में लिखा था।
• YT — Yandex का MapReduce सिस्टम।
• YDB (यांडेक्स डेटाबेस) - न्यूएसक्यूएल वितरित डेटाबेस।

एमडीएस एलआरसी रिडंडेंसी कोड, 8-2-2 योजना का उपयोग करता है। रिडंडेंसी कोड वाला डेटा 12 अलग-अलग डीसी में अलग-अलग सर्वरों में 3 अलग-अलग डिस्क पर लिखा जाता है: प्रत्येक डीसी में 4 सर्वर। इसके बारे में और पढ़ें लेख.

YT रीड-सोलोमन कोड (स्कीम 6-3) दोनों का उपयोग करता है, जो लागू करने वाले पहले थे, और एलआरसी रिडंडेंसी कोड (स्कीम 12-2-2), जिसमें एलआरसी पसंदीदा भंडारण विधि है।

YDB सम-विषम आधारित अतिरेक कोड का उपयोग करता है (चित्र 4-2)। YDB में अतिरेक कोड के बारे में पहले से ही हाईलोड पर बताया गया.

विभिन्न अतिरेक कोड योजनाओं का उपयोग सिस्टम के लिए अलग-अलग आवश्यकताओं के कारण होता है। उदाहरण के लिए, एमडीएस में, एलआरसी का उपयोग करके संग्रहीत डेटा को एक बार में 3 डीसी में रखा जाता है। हमारे लिए यह महत्वपूर्ण है कि यदि किसी डीसी में से 1 विफल हो जाए तो डेटा पढ़ने के लिए उपलब्ध रहे, इसलिए ब्लॉकों को डीसी में वितरित किया जाना चाहिए ताकि यदि कोई डीसी अनुपलब्ध हो, तो पहुंच योग्य ब्लॉकों की संख्या अनुमेय से अधिक न हो। 8-2-2 योजना में, आप प्रत्येक डीसी में 4 ब्लॉक रख सकते हैं, फिर जब कोई डीसी बंद हो जाता है, तो 4 ब्लॉक अनुपलब्ध होंगे, और डेटा पढ़ा जा सकता है। 3 डीसी में रखते समय हम जो भी योजना चुनें, किसी भी स्थिति में वहां (आर + एल) / एन >= 0,5 होना चाहिए, यानी भंडारण अतिरेक कम से कम 50% होगा।

YT में स्थिति अलग है: प्रत्येक YT क्लस्टर पूरी तरह से 1 DC (अलग-अलग DC में अलग-अलग क्लस्टर) में स्थित है, इसलिए ऐसा कोई प्रतिबंध नहीं है। 12-2-2 योजना 33% अतिरेक प्रदान करती है, अर्थात, डेटा संग्रहीत करना सस्ता है, और यह एमडीएस योजना की तरह, एक साथ 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 संक्षेप में सिद्धांत की व्याख्या करता है और फिर व्यवहार में एलआरसी के साथ अनुभवों पर चर्चा करता है।
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. एमडीएस में अतिरेक कोड: 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