रिडंडंसी असे दिसते

डेटा स्टोरेजची विश्वासार्हता वाढवण्यासाठी रिडंडंसी कोड* संगणक प्रणालींमध्ये मोठ्या प्रमाणावर वापरले जातात. यांडेक्समध्ये ते अनेक प्रकल्पांमध्ये वापरले जातात. उदाहरणार्थ, आमच्या अंतर्गत ऑब्जेक्ट स्टोरेजमध्ये प्रतिकृतीऐवजी रिडंडंसी कोड वापरल्याने विश्वासार्हतेचा त्याग न करता लाखोंची बचत होते. परंतु त्यांचा व्यापक वापर असूनही, रिडंडंसी कोड कसे कार्य करतात याचे स्पष्ट वर्णन अत्यंत दुर्मिळ आहे. ज्यांना समजून घ्यायचे आहे त्यांना अंदाजे खालील गोष्टींचा सामना करावा लागतो (पासून विकिपीडिया):

माझे नाव वादिम आहे, यांडेक्स येथे मी अंतर्गत ऑब्जेक्ट स्टोरेज एमडीएस विकसित करत आहे. या लेखात, मी रिडंडंसी कोड्स (रीड-सोलोमन आणि एलआरसी कोड) च्या सैद्धांतिक पायाचे सोप्या शब्दात वर्णन करेन. जटिल गणित आणि दुर्मिळ संज्ञांशिवाय ते कसे कार्य करते ते मी तुम्हाला सांगेन. शेवटी मी यांडेक्समध्ये रिडंडंसी कोड वापरण्याची उदाहरणे देईन.

मी अनेक गणिती तपशीलांचा तपशीलवार विचार करणार नाही, परंतु ज्यांना खोलवर जायचे आहे त्यांच्यासाठी मी दुवे प्रदान करेन. मी हे देखील लक्षात घेईन की काही गणितीय व्याख्या कठोर असू शकत नाहीत, कारण लेख गणितज्ञांसाठी नाही, परंतु अभियंत्यांसाठी आहे ज्यांना समस्येचे सार समजून घ्यायचे आहे.

* इंग्रजी भाषेतील साहित्यात, रिडंडंसी कोडला अनेकदा इरेजर कोड म्हणतात.

1. रिडंडंसी कोडचे सार

सर्व रिडंडंसी कोडचे सार अत्यंत सोपे आहे: डेटा संग्रहित करा (किंवा प्रसारित करा) जेणेकरून त्रुटी उद्भवल्यास तो गमावला जाणार नाही (डिस्क अपयश, डेटा ट्रान्सफर त्रुटी इ.).

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

डेटाचे सर्व n ब्लॉक्स पुनर्प्राप्त करण्यासाठी, तुमच्याकडे n + m ब्लॉक्सपैकी किमान n असणे आवश्यक आहे, कारण तुम्हाला फक्त n-1 ब्लॉक घेऊन n ब्लॉक्स मिळू शकत नाहीत (या प्रकरणात, तुम्हाला पातळ मधून 1 ब्लॉक घ्यावा लागेल. हवा"). सर्व डेटा पुनर्प्राप्त करण्यासाठी n + m ब्लॉक्सचे n यादृच्छिक ब्लॉक्स पुरेसे आहेत का? हे रिडंडंसी कोडच्या प्रकारावर अवलंबून असते, उदाहरणार्थ, रीड-सोलोमन कोड तुम्हाला अनियंत्रित एन ब्लॉक्सचा वापर करून सर्व डेटा पुनर्प्राप्त करण्याची परवानगी देतात, परंतु एलआरसी रिडंडंसी कोड नेहमीच नसतात.

डेटा संचयन

डेटा स्टोरेज सिस्टममध्ये, नियमानुसार, प्रत्येक डेटा ब्लॉक्स आणि रिडंडंसी कोड ब्लॉक्स वेगळ्या डिस्कवर लिहिलेले असतात. मग, अनियंत्रित डिस्क अयशस्वी झाल्यास, मूळ डेटा अद्याप पुनर्संचयित आणि वाचला जाऊ शकतो. एकाच वेळी अनेक डिस्क अयशस्वी झाल्या तरीही डेटा पुनर्प्राप्त केला जाऊ शकतो.

डेटा ट्रान्सफर

रिडंडंसी कोडचा वापर अविश्वसनीय नेटवर्कवर डेटा विश्वसनीयरित्या प्रसारित करण्यासाठी केला जाऊ शकतो. प्रसारित केलेला डेटा ब्लॉकमध्ये विभागलेला आहे आणि त्यांच्यासाठी रिडंडंसी कोडची गणना केली जाते. दोन्ही डेटा ब्लॉक्स आणि रिडंडंसी कोड ब्लॉक्स नेटवर्कवर प्रसारित केले जातात. अनियंत्रित ब्लॉक्समध्ये त्रुटी आढळल्यास (ब्लॉकच्या ठराविक संख्येपर्यंत), डेटा अद्याप त्रुटीशिवाय नेटवर्कवर प्रसारित केला जाऊ शकतो. रीड-सोलोमन कोड, उदाहरणार्थ, ऑप्टिकल कम्युनिकेशन लाइन्स आणि उपग्रह संप्रेषणांमध्ये डेटा प्रसारित करण्यासाठी वापरले जातात.

* रिडंडंसी कोड देखील आहेत ज्यात डेटा ब्लॉकमध्ये विभागलेला नाही, जसे की हॅमिंग कोड आणि 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* फील्ड ही फील्ड आहेत ज्यासाठी फील्डच्या कोणत्याही दोन घटकांसाठी प्रत्येक ऑपरेशनचा एक अद्वितीय परिणाम (+, -, *, /) असतो. 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 समीकरणांची प्रणाली आहे, याचा अर्थ आम्ही ते सोडवू शकतो आणि डेटा पुनर्संचयित करू शकतो!

या समीकरण प्रणालीतून रीड-सोलोमन कोड्ससाठी डेटा रिकव्हरीबद्दल अनेक निष्कर्ष काढले जातात (एन डेटा ब्लॉक्स, एम रिडंडंसी कोड ब्लॉक):

• एम ब्लॉक किंवा त्यापेक्षा कमी हरवल्यास डेटा पुनर्प्राप्त केला जाऊ शकतो. जर m+1 किंवा अधिक ब्लॉक्स हरवले, तर डेटा पुनर्संचयित केला जाऊ शकत नाही: m + 1 अज्ञात असलेल्या m समीकरणांची प्रणाली सोडवणे अशक्य आहे.
• अगदी एक डेटा ब्लॉक पुनर्प्राप्त करण्यासाठी, तुम्हाला उर्वरित ब्लॉकपैकी कोणताही n वापरण्याची आवश्यकता आहे आणि तुम्ही रिडंडंसी कोडपैकी कोणताही वापरू शकता.

आपल्याला आणखी काय माहित असणे आवश्यक आहे

वरील वर्णनात, मी अनेक महत्त्वाच्या समस्या टाळतो ज्यांचा विचार करण्यासाठी गणितात खोलवर जाणे आवश्यक आहे. विशेषतः, मी खालील गोष्टींबद्दल काहीही बोलत नाही:

• रीड-सोलोमन कोड्सच्या समीकरणांच्या प्रणालीमध्ये अज्ञातांच्या कोणत्याही संयोजनासाठी (अज्ञात m पेक्षा जास्त नाही) समाधान असणे आवश्यक आहे. या आवश्यकतेवर आधारित, अल्फा, बीटा, गॅमा आणि डेल्टाची मूल्ये निवडली जातात.
• समीकरणांची प्रणाली आपोआप तयार होण्यास सक्षम असणे आवश्यक आहे (कोणते ब्लॉक अनुपलब्ध आहेत यावर अवलंबून) आणि निराकरण केले पाहिजे.
• आम्हाला गॅलोइस फील्ड तयार करणे आवश्यक आहे: दिलेल्या शब्द आकारासाठी, कोणत्याही दोन घटकांसाठी कोणत्याही ऑपरेशनचे परिणाम (+, -, *, /) शोधण्यात सक्षम व्हा.

लेखाच्या शेवटी या महत्त्वाच्या मुद्द्यांवर साहित्याचे संदर्भ दिले आहेत.

n आणि m ची निवड

सराव मध्ये n आणि m कसे निवडायचे? सराव मध्ये, डेटा स्टोरेज सिस्टममध्ये, रिडंडंसी कोड जागा वाचवण्यासाठी वापरले जातात, म्हणून m नेहमी n पेक्षा कमी निवडला जातो. त्यांची विशिष्ट मूल्ये अनेक घटकांवर अवलंबून असतात, यासह:

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

याव्यतिरिक्त, अनेक DC मध्ये डेटा संचयित केल्याने n आणि m च्या निवडीवर अतिरिक्त निर्बंध लागू होतात: 1 DC बंद असल्यास, डेटा वाचण्यासाठी अद्याप उपलब्ध असणे आवश्यक आहे. उदाहरणार्थ, 3 DC मध्ये डेटा संचयित करताना, खालील अट पूर्ण करणे आवश्यक आहे: m >= n/2, अन्यथा 1 DC बंद असताना डेटा वाचण्यासाठी अनुपलब्ध असेल अशी परिस्थिती असू शकते.

3. LRC - स्थानिक पुनर्रचना कोड

रीड-सोलोमन कोड वापरून डेटा पुनर्प्राप्त करण्यासाठी, तुम्हाला एन अनियंत्रित डेटा ब्लॉक्स वापरावे लागतील. वितरीत डेटा स्टोरेज सिस्टमसाठी हे एक अतिशय लक्षणीय नुकसान आहे, कारण एका तुटलेल्या डिस्कवर डेटा पुनर्संचयित करण्यासाठी, आपल्याला डिस्क आणि नेटवर्कवर मोठा अतिरिक्त भार तयार करून इतर बहुतेक डेटा वाचावा लागेल.

सर्वात सामान्य त्रुटी म्हणजे एका डिस्कच्या अयशस्वी किंवा ओव्हरलोडमुळे डेटाच्या एका ब्लॉकची दुर्गमता. या (सर्वात सामान्य) प्रकरणात डेटा पुनर्प्राप्तीसाठी अतिरिक्त भार कसा तरी कमी करणे शक्य आहे का? असे दिसून आले की तुम्ही हे करू शकता: विशेषत: या उद्देशासाठी LRC रिडंडंसी कोड आहेत.

LRC (स्थानिक पुनर्रचना कोड) हे Windows Azure Storage मध्ये वापरण्यासाठी Microsoft ने शोधलेले रिडंडंसी कोड आहेत. 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 सर्व डेटा ब्लॉक्स वापरून मोजले जातात. रिडंडंसी कोड ब्लॉक 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 एकल त्रुटींनंतर डेटा पुनर्प्राप्त करण्यात रीड-सोलोमन कोडपेक्षा जास्त कामगिरी करते. रीड-सोलोमन कोडमध्ये, डेटाचा एक ब्लॉक देखील पुनर्प्राप्त करण्यासाठी, आपल्याला n ब्लॉक्स वापरण्याची आवश्यकता आहे आणि LRC मध्ये, डेटाचा एक ब्लॉक पुनर्प्राप्त करण्यासाठी, n/l ब्लॉक्स वापरणे पुरेसे आहे (आमच्या उदाहरणामध्ये n/2). दुसरीकडे, एलआरसी रीड-सोलोमन कोडपेक्षा कमी दर्जाच्या अनुज्ञेय त्रुटींच्या संदर्भात आहे. वरील उदाहरणांमध्ये, रीड-सोलोमन कोड कोणत्याही 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 योजना.
• पिरामाइड कोड हे मायक्रोसॉफ्टचे आणखी एक रिडंडंसी कोड आहेत.

5. Yandex मध्ये वापरा

अनेक Yandex पायाभूत सुविधा प्रकल्प विश्वसनीय डेटा स्टोरेजसाठी रिडंडंसी कोड वापरतात. येथे काही उदाहरणे आहेत:

• एमडीएस अंतर्गत ऑब्जेक्ट स्टोरेज, ज्याबद्दल मी लेखाच्या सुरुवातीला लिहिले आहे.
• 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 सम-विषम आधारित रिडंडंसी कोड वापरतो (आकृती 4-2). आधीच YDB मध्ये रिडंडंसी कोडबद्दल हायलोड वर सांगितले.

वेगवेगळ्या रिडंडंसी कोड स्कीमचा वापर सिस्टीमसाठी वेगवेगळ्या आवश्यकतांमुळे होतो. उदाहरणार्थ, MDS मध्ये, LRC वापरून संग्रहित केलेला डेटा एकाच वेळी 3 DC मध्ये ठेवला जातो. आमच्यासाठी हे महत्त्वाचे आहे की कोणत्याही DC पैकी 1 अयशस्वी झाल्यास डेटा वाचण्यासाठी उपलब्ध राहील, म्हणून ब्लॉक्सचे वितरण 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% रिडंडंसी प्रदान करते, म्हणजेच डेटा संग्रहित करणे स्वस्त आहे आणि ते MDS योजनेप्रमाणे एकाच वेळी 4 डिस्क आउटेजपर्यंत टिकून राहू शकते.

डेटा स्टोरेज आणि प्रोसेसिंग सिस्टीममध्ये रिडंडंसी कोडच्या वापराची आणखी बरीच वैशिष्ट्ये आहेत: डेटा पुनर्प्राप्तीची बारकावे, क्वेरीच्या अंमलबजावणीच्या वेळेवर पुनर्प्राप्तीचा प्रभाव, डेटा रेकॉर्डिंगची वैशिष्ट्ये इ. मी या आणि इतर वैशिष्ट्यांबद्दल स्वतंत्रपणे बोलणार आहे. अभ्यासात रिडंडंसी कोडच्या वापराबद्दल, जर विषय मनोरंजक असेल.

6. दुवे

1. रीड-सोलोमन कोड आणि गॅलोइस फील्ड बद्दल लेखांची मालिका: https://habr.com/ru/company/yadro/blog/336286/
   https://habr.com/ru/company/yadro/blog/341506/
   ते सुलभ भाषेत गणिताचा सखोल विचार करतात.
2. LRC बद्दल मायक्रोसॉफ्टचा लेख: 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