रिडन्डन्सी यस्तो देखिन्छ

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

मेरो नाम Vadim हो, Yandex मा म आन्तरिक वस्तु भण्डारण MDS विकास गर्दैछु। यस लेखमा, म रिडन्डन्सी कोडहरू (रीड-सोलोमन र LRC कोडहरू) को सैद्धान्तिक आधारहरू सरल शब्दहरूमा वर्णन गर्नेछु। जटिल गणित र दुर्लभ सर्तहरू बिना, यसले कसरी काम गर्छ भनेर म तपाईंलाई बताउनेछु। अन्तमा म Yandex मा रिडन्डन्सी कोडहरू प्रयोग गर्ने उदाहरणहरू दिनेछु।

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

* अंग्रेजी-भाषा साहित्यमा, रिडन्डन्सी कोडहरूलाई प्रायः इरेजर कोडहरू भनिन्छ।

1. रिडन्डन्सी कोडहरूको सार

सबै रिडन्डन्सी कोडहरूको सार एकदम सरल छ: डाटा भण्डार गर्नुहोस् (वा ट्रान्समिट गर्नुहोस्) ताकि त्रुटिहरू देखा पर्दा यो हराउनु हुँदैन (डिस्क विफलता, डाटा ट्रान्सफर त्रुटिहरू, आदि)।

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

डाटाका सबै n ब्लकहरू रिकभर गर्न, तपाईंसँग कम्तिमा n + m ब्लकहरू हुन आवश्यक छ, किनकि तपाईंले n-1 ब्लक मात्र राखेर n ब्लकहरू प्राप्त गर्न सक्नुहुन्न (यस अवस्थामा, तपाईंले पातलोबाट 1 ब्लक लिनुपर्दछ। हावा")। के n + m ब्लकहरूको n अनियमित ब्लकहरू सबै डाटा रिकभर गर्न पर्याप्त छन्? यो रिडन्डन्सी कोडहरूको प्रकारमा निर्भर गर्दछ, उदाहरणका लागि, रिड-सोलोमन कोडहरूले तपाईंलाई मनमानी एन ब्लकहरू प्रयोग गरेर सबै डेटा पुन: प्राप्ति गर्न अनुमति दिन्छ, तर LRC रिडन्डन्सी कोडहरू सधैं हुँदैन।

डाटा भण्डारण

डाटा भण्डारण प्रणालीहरूमा, नियमको रूपमा, प्रत्येक डाटा ब्लकहरू र रिडन्डन्सी कोड ब्लकहरू छुट्टै डिस्कमा लेखिएको हुन्छ। त्यसपछि, यदि एक मनमानी डिस्क असफल भयो भने, मूल डाटा अझै पनि पुनर्स्थापित र पढ्न सकिन्छ। एकै समयमा धेरै डिस्क असफल भए पनि डाटा पुन: प्राप्त गर्न सकिन्छ।

डेटा स्थानान्तरण

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

* त्यहाँ रिडन्डन्सी कोडहरू पनि छन् जसमा डाटालाई ब्लकहरूमा विभाजन गरिएको छैन, जस्तै ह्यामिङ कोडहरू र CRC कोडहरू, जुन इथरनेट नेटवर्कहरूमा डाटा प्रसारणको लागि व्यापक रूपमा प्रयोग गरिन्छ। यी त्रुटिहरू सच्याउने कोडिङका लागि कोडहरू हुन्, तिनीहरू त्रुटिहरू पत्ता लगाउन डिजाइन गरिएका हुन्, तिनीहरूलाई सच्याउन होइन (ह्यामिङ कोडले त्रुटिहरूलाई आंशिक सुधार गर्न पनि अनुमति दिन्छ)।

2. रिड-सोलोमन कोडहरू

रीड-सोलोमन कोडहरू सबैभन्दा व्यापक रूपमा प्रयोग हुने रिडन्डन्सी कोडहरू मध्ये एक हो, जुन 1960 मा आविष्कार गरिएको थियो र पहिलो पटक कम्प्याक्ट डिस्कहरूको ठूलो उत्पादनको लागि 1980 मा व्यापक रूपमा प्रयोग गरियो।

रिड-सोलोमन कोडहरू बुझ्नको लागि दुईवटा मुख्य प्रश्नहरू छन्: 1) रिडन्डन्सी कोडहरूको ब्लकहरू कसरी सिर्जना गर्ने; 2) रिडन्डन्सी कोड ब्लकहरू प्रयोग गरेर डाटा कसरी रिकभर गर्ने। तिनीहरूको जवाफ खोजौं।
सरलताको लागि, हामी n=6 र m=4 मान्न सक्छौं। अन्य योजनाहरू समानताद्वारा विचार गरिन्छ।

रिडन्डन्सी कोड ब्लकहरू कसरी सिर्जना गर्ने

रिडन्डन्सी कोडहरूको प्रत्येक ब्लक अरूहरूबाट स्वतन्त्र रूपमा गणना गरिन्छ। सबै n डाटा ब्लकहरू प्रत्येक ब्लक गणना गर्न प्रयोग गरिन्छ। तलको रेखाचित्रमा, X1-X6 डाटा ब्लकहरू हुन्, P1-P4 रिडन्डन्सी कोड ब्लकहरू हुन्।

सबै डाटा ब्लकहरू एउटै साइज हुनुपर्छ, र शून्य बिटहरू पङ्क्तिबद्ध गर्न प्रयोग गर्न सकिन्छ। नतिजा रिडन्डन्सी कोड ब्लकहरू डाटा ब्लकहरू जस्तै आकार हुनेछ। सबै डाटा ब्लकहरू शब्दहरूमा विभाजित छन् (उदाहरणका लागि, 16 बिटहरू)। मानौं कि हामीले डेटा ब्लकहरूलाई k शब्दहरूमा विभाजित गर्छौं। त्यसपछि रिडन्डन्सी कोडका सबै ब्लकहरू पनि k शब्दहरूमा विभाजित हुनेछन्।

प्रत्येक रिडन्डन्सी ब्लकको i-th शब्द गणना गर्न, सबै डेटा ब्लकहरूको i-th शब्दहरू प्रयोग गरिनेछ। तिनीहरू निम्न सूत्र अनुसार गणना गरिनेछ:

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

ग्यालोइस क्षेत्रहरू किन आवश्यक छ?

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

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

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

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

Galois* फिल्डहरू फिल्डहरू हुन् जसको लागि प्रत्येक अपरेशनको एक अद्वितीय परिणाम (+, -, *, /) फिल्डका कुनै पनि दुई तत्वहरूको लागि हुन्छ। Galois फिल्डहरू 2: 2, 4, 8, 16, इत्यादिको शक्तिहरू भएका संख्याहरूको लागि निर्माण गर्न सकिन्छ (वास्तवमा कुनै पनि अविभाज्य संख्या p को शक्तिहरू, तर व्यवहारमा हामी 2 को शक्तिहरूमा मात्र रुचि राख्छौं)। उदाहरण को लागी, 16-बिट शब्दहरु को लागी, यो 65 तत्वहरु को एक फिल्ड हो, प्रत्येक जोडा को लागी तपाईले कुनै पनि अपरेशन (+, -, *, /) को परिणाम पाउन सक्नुहुन्छ। माथिको समीकरणबाट x, p, alpha, beta, gamma, delta को मानहरूलाई गणनाको लागि Galois क्षेत्रका तत्वहरू मानिनेछ।

यसरी, हामीसँग समीकरणहरूको प्रणाली छ जसको साथ हामी उपयुक्त कम्प्युटर प्रोग्राम लेखेर रिडन्डन्सी कोडहरूको ब्लकहरू निर्माण गर्न सक्छौं। समीकरणको एउटै प्रणाली प्रयोग गरेर, तपाईं डाटा रिकभरी प्रदर्शन गर्न सक्नुहुन्छ।

* यो एक सख्त परिभाषा होइन, बरु एक विवरण हो।

डाटा कसरी रिकभर गर्ने

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

रीड-सोलोमन कोडहरूका लागि समीकरणहरूलाई समीकरणहरूको प्रणालीको रूपमा हेर्न सकिन्छ जसमा सबै अल्फा, बीटा, गामा, डेल्टा मानहरू स्थिर हुन्छन्, उपलब्ध ब्लकहरूसँग सम्बन्धित सबै x र p ज्ञात चरहरू हुन्, र बाँकी x र p। अज्ञात छन्।

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

हामीसँग 4 अज्ञातहरूसँग 4 समीकरणहरूको प्रणाली छ, जसको मतलब हामी यसलाई समाधान गर्न र डेटा पुनर्स्थापना गर्न सक्छौं!

यस समीकरण प्रणालीबाट रीड-सोलोमन कोडहरू (n डेटा ब्लकहरू, m रिडन्डन्सी कोड ब्लकहरू) को लागि डाटा रिकभरीको बारेमा धेरै निष्कर्षहरू पछ्याउँछन्:

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

अरु के थाहा पाउनुपर्छ

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

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

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

n र m को छनोट

अभ्यासमा n र m कसरी छनौट गर्ने? अभ्यासमा, डाटा भण्डारण प्रणालीहरूमा, रिडन्डन्सी कोडहरू स्पेस बचत गर्न प्रयोग गरिन्छ, त्यसैले m सधैं n भन्दा कम छनोट गरिन्छ। तिनीहरूको विशिष्ट मानहरू धेरै कारकहरूमा निर्भर हुन्छन्, जसमा:

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

थप रूपमा, धेरै DC मा डाटा भण्डारण गर्दा n र m को छनोटमा थप प्रतिबन्धहरू लगाइन्छ: यदि 1 DC बन्द गरिएको छ भने, डाटा अझै पढ्नको लागि उपलब्ध हुनुपर्छ। उदाहरणका लागि, 3 DC मा डाटा भण्डारण गर्दा, निम्न सर्तहरू पूरा गर्नुपर्छ: m >= n/2, अन्यथा 1 DC बन्द हुँदा डाटा पढ्नको लागि उपलब्ध नहुने अवस्था हुन सक्छ।

3. LRC - स्थानीय पुनर्निर्माण संहिता

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

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

LRC (स्थानीय पुनर्निर्माण कोडहरू) Windows Azure भण्डारणमा प्रयोगको लागि Microsoft द्वारा आविष्कार गरिएका रिडन्डन्सी कोडहरू हुन्। LRC को विचार सम्भव भएसम्म सरल छ: सबै डेटा ब्लकहरूलाई दुई (वा बढी) समूहहरूमा विभाजन गर्नुहोस् र प्रत्येक समूहको लागि रिडन्डन्सी कोड ब्लकहरूको भाग छुट्टै पढ्नुहोस्। त्यसपछि सबै डेटा ब्लकहरू (LRC मा तिनीहरूलाई ग्लोबल रिडन्डन्सी कोडहरू भनिन्छ), र केही - डेटा ब्लकहरूको दुई समूहहरू मध्ये एउटा प्रयोग गरेर (तिनीहरूलाई स्थानीय रिडन्डन्सी कोडहरू भनिन्छ) प्रयोग गरेर केही रिडन्डन्सी कोड ब्लकहरू गणना गरिनेछ।

LRC लाई तीनवटा नम्बरहरूद्वारा जनाइएको छ: nrl, जहाँ n डेटा ब्लकहरूको संख्या हो, r विश्वव्यापी रिडन्डन्सी कोड ब्लकहरूको संख्या हो, l स्थानीय रिडन्डन्सी कोड ब्लकहरूको संख्या हो। एउटा डाटा ब्लक अनुपलब्ध हुँदा डाटा पढ्नको लागि, तपाईंले n/l ब्लकहरू मात्र पढ्न आवश्यक छ - यो Reed-Solomon कोडहरूमा भन्दा l गुणा कम छ।

उदाहरणका लागि, LRC 6-2-2 योजनालाई विचार गर्नुहोस्। X1–X6 — ६ डाटा ब्लकहरू, P6, P1 — २ विश्वव्यापी रिडन्डन्सी ब्लकहरू, P2, P2 — २ स्थानीय रिडन्डन्सी ब्लकहरू।

रिडन्डन्सी कोड ब्लकहरू 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 कोडहरूमा, डाटाको एक ब्लक पनि रिकभर गर्न, तपाईंले n ब्लकहरू प्रयोग गर्न आवश्यक छ, र LRC मा, डाटाको एक ब्लक रिकभर गर्न, यो n/l ब्लकहरू प्रयोग गर्न पर्याप्त छ (हाम्रो उदाहरणमा n/2)। अर्कोतर्फ, LRC अनुमतियोग्य त्रुटिहरूको अधिकतम संख्याको सन्दर्भमा रीड-सोलोमन कोडहरू भन्दा कम छ। माथिका उदाहरणहरूमा, Reed-Solomon कोडहरूले कुनै पनि 4 त्रुटिहरूको लागि डेटा पुन: प्राप्त गर्न सक्छ, र LRC को लागि त्यहाँ 2 त्रुटिहरूको 4 संयोजनहरू छन् जब डेटा पुन: प्राप्त गर्न सकिँदैन।

के बढी महत्त्वपूर्ण छ विशेष परिस्थितिमा निर्भर गर्दछ, तर अक्सर LRC ले प्रदान गर्ने अतिरिक्त लोडमा बचत अलि कम भरपर्दो भण्डारण भन्दा बढी हुन्छ।

४. अन्य रिडन्डन्सी कोडहरू

रीड-सोलोमन र LRC कोडहरू बाहेक, त्यहाँ धेरै अन्य रिडन्डन्सी कोडहरू छन्। विभिन्न रिडन्डन्सी कोडहरूले फरक गणित प्रयोग गर्दछ। यहाँ केहि अन्य रिडन्डन्सी कोडहरू छन्:

• XOR अपरेटर प्रयोग गरेर रिडन्डन्सी कोड। XOR सञ्चालन n डेटा ब्लकहरूमा गरिन्छ, र रिडन्डन्सी कोडहरूको 1 ब्लक प्राप्त हुन्छ, त्यो हो, एक n+1 योजना (n डेटा ब्लकहरू, 1 रिडन्डन्सी कोड)। मा प्रयोग गरियो RAID 5, जहाँ डेटा र रिडन्डन्सी कोडहरूको ब्लकहरू एरेका सबै डिस्कहरूमा चक्रीय रूपमा लेखिन्छन्।
• XOR सञ्चालनमा आधारित सम-विचित्र एल्गोरिथ्म। तपाईंलाई रिडन्डन्सी कोडहरूको २ ब्लकहरू निर्माण गर्न अनुमति दिन्छ, त्यो हो, n+2 योजना।
• XOR सञ्चालनमा आधारित STAR एल्गोरिथ्म। तपाईंलाई रिडन्डन्सी कोडहरूको 3 ब्लकहरू निर्माण गर्न अनुमति दिन्छ, त्यो हो, n+3 योजना।
• पिरामाइड कोडहरू Microsoft बाट अर्को रिडन्डन्सी कोडहरू हुन्।

5. Yandex मा प्रयोग गर्नुहोस्

Yandex पूर्वाधार परियोजनाहरूको संख्या विश्वसनीय डाटा भण्डारणको लागि रिडन्डन्सी कोडहरू प्रयोग गर्दछ। यहाँ केही उदाहरणहरू छन्:

• MDS आन्तरिक वस्तु भण्डारण, जुन मैले लेखको सुरुमा लेखेको थिएँ।
• YT - Yandex को MapReduce प्रणाली।
• YDB (Yandex DataBase) - newSQL वितरित डाटाबेस।

MDS ले LRC रिडन्डन्सी कोडहरू, 8-2-2 योजना प्रयोग गर्दछ। रिडन्डन्सी कोडहरू भएको डाटा 12 फरक DC मा विभिन्न सर्भरहरूमा 3 फरक डिस्कहरूमा लेखिएको छ: प्रत्येक DC मा 4 सर्भरहरू। यस बारे थप पढ्नुहोस् मा लेख.

YT ले दुबै रीड-सोलोमन कोडहरू (योजना 6-3) प्रयोग गर्दछ, जुन लागू गर्ने पहिलो थियो, र LRC रिडन्डन्सी कोडहरू (योजना 12-2-2), LRC लाई प्राथमिकतामा राखिएको भण्डारण विधि हो।

YDB ले सम-विजोड आधारित रिडन्डन्सी कोडहरू प्रयोग गर्दछ (चित्र ४-२)। YDB मा रिडन्डन्सी कोडहरूको बारेमा पहिले नै Highload मा भन्नुभयो.

विभिन्न रिडन्डन्सी कोड योजनाहरूको प्रयोग प्रणालीहरूको लागि विभिन्न आवश्यकताहरूको कारण हो। उदाहरणका लागि, MDS मा, LRC प्रयोग गरेर भण्डारण गरिएको डाटालाई एकै पटक ३ DC मा राखिन्छ। हाम्रो लागि यो महत्त्वपूर्ण छ कि यदि कुनै DCs मध्ये 3 असफल भएमा डेटा पढ्नको लागि उपलब्ध रहन्छ, त्यसैले ब्लकहरू DC हरू बीच वितरण गरिनुपर्छ ताकि यदि कुनै DC अनुपलब्ध छ भने, पहुँचयोग्य ब्लकहरूको संख्या अनुमतियोग्य भन्दा बढी हुँदैन। 1-8-2 योजनामा, तपाईंले प्रत्येक DC मा 2 ब्लकहरू राख्न सक्नुहुन्छ, त्यसपछि कुनै पनि DC बन्द हुँदा, 4 ब्लकहरू उपलब्ध हुनेछैनन्, र डाटा पढ्न सकिन्छ। हामीले यसलाई ३ DC मा राख्दा जुनसुकै योजना छनोट गर्छौँ, कुनै पनि अवस्थामा त्यहाँ (r + l) / n >= ०.५ हुनुपर्छ, अर्थात् भण्डारण रिडन्डन्सी कम्तीमा ५०% हुनेछ।

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
   खण्ड २ ले सिद्धान्तलाई संक्षिप्त रूपमा व्याख्या गर्छ र त्यसपछि व्यवहारमा 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