ഇതാണ് റിഡൻഡൻസി കാണുന്നത്

റിഡൻഡൻസി കോഡുകൾ* ഡാറ്റ സംഭരണത്തിന്റെ വിശ്വാസ്യത വർദ്ധിപ്പിക്കുന്നതിന് കമ്പ്യൂട്ടർ സിസ്റ്റങ്ങളിൽ വ്യാപകമായി ഉപയോഗിക്കുന്നു. Yandex ൽ അവർ പല പദ്ധതികളിലും ഉപയോഗിക്കുന്നു. ഉദാഹരണത്തിന്, ഞങ്ങളുടെ ആന്തരിക ഒബ്ജക്റ്റ് സ്റ്റോറേജിൽ റെപ്ലിക്കേഷന് പകരം റിഡൻഡൻസി കോഡുകൾ ഉപയോഗിക്കുന്നത് വിശ്വാസ്യത നഷ്ടപ്പെടുത്താതെ ദശലക്ഷക്കണക്കിന് ലാഭിക്കുന്നു. എന്നാൽ അവയുടെ വ്യാപകമായ ഉപയോഗം ഉണ്ടായിരുന്നിട്ടും, റിഡൻഡൻസി കോഡുകൾ എങ്ങനെ പ്രവർത്തിക്കുന്നു എന്നതിന്റെ വ്യക്തമായ വിവരണങ്ങൾ വളരെ വിരളമാണ്. മനസ്സിലാക്കാൻ ആഗ്രഹിക്കുന്നവർ ഏകദേശം ഇനിപ്പറയുന്നവയെ അഭിമുഖീകരിക്കുന്നു (ഇതിൽ നിന്ന് വിക്കിപീഡിയ):

എന്റെ പേര് വാഡിം, Yandex-ൽ ഞാൻ ആന്തരിക ഒബ്ജക്റ്റ് സ്റ്റോറേജ് MDS വികസിപ്പിക്കുകയാണ്. ഈ ലേഖനത്തിൽ, റിഡൻഡൻസി കോഡുകളുടെ (റീഡ്-സോളമൻ, എൽആർസി കോഡുകൾ) സൈദ്ധാന്തിക അടിത്തറയെ ഞാൻ ലളിതമായ വാക്കുകളിൽ വിവരിക്കും. സങ്കീർണ്ണമായ ഗണിതവും അപൂർവ പദങ്ങളും ഇല്ലാതെ ഇത് എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് ഞാൻ നിങ്ങളോട് പറയും. അവസാനം Yandex-ൽ റിഡൻഡൻസി കോഡുകൾ ഉപയോഗിക്കുന്നതിനുള്ള ഉദാഹരണങ്ങൾ ഞാൻ നൽകും.

ഗണിതശാസ്ത്രപരമായ പല വിശദാംശങ്ങളും ഞാൻ വിശദമായി പരിഗണിക്കില്ല, പക്ഷേ ആഴത്തിൽ മുങ്ങാൻ ആഗ്രഹിക്കുന്നവർക്കായി ഞാൻ ലിങ്കുകൾ നൽകും. ലേഖനം ഗണിതശാസ്ത്രജ്ഞരെ ഉദ്ദേശിച്ചുള്ളതല്ല, മറിച്ച് പ്രശ്നത്തിന്റെ സാരാംശം മനസ്സിലാക്കാൻ ആഗ്രഹിക്കുന്ന എഞ്ചിനീയർമാർക്ക് വേണ്ടിയുള്ളതിനാൽ ചില ഗണിതശാസ്ത്ര നിർവചനങ്ങൾ കർശനമായിരിക്കില്ല എന്നതും ഞാൻ ശ്രദ്ധിക്കും.

* ഇംഗ്ലീഷ് ഭാഷാ സാഹിത്യത്തിൽ, റിഡൻഡൻസി കോഡുകളെ പലപ്പോഴും മായ്ക്കൽ കോഡുകൾ എന്ന് വിളിക്കുന്നു.

1. റിഡൻഡൻസി കോഡുകളുടെ സാരാംശം

എല്ലാ റിഡൻഡൻസി കോഡുകളുടെയും സാരാംശം വളരെ ലളിതമാണ്: പിശകുകൾ സംഭവിക്കുമ്പോൾ (ഡിസ്ക് പരാജയങ്ങൾ, ഡാറ്റാ ട്രാൻസ്ഫർ പിശകുകൾ മുതലായവ) നഷ്ടപ്പെടാതിരിക്കാൻ ഡാറ്റ സംഭരിക്കുക (അല്ലെങ്കിൽ ട്രാൻസ്മിറ്റ് ചെയ്യുക).

മിക്ക റിഡൻഡൻസി കോഡുകളിലും, ഡാറ്റയെ n ഡാറ്റ ബ്ലോക്കുകളായി തിരിച്ചിരിക്കുന്നു, അതിനായി ആവർത്തന കോഡുകളുടെ m ബ്ലോക്കുകൾ കണക്കാക്കുന്നു, അതിന്റെ ഫലമായി ആകെ n + m ബ്ലോക്കുകൾ ലഭിക്കും. n + m ബ്ലോക്കുകളുടെ ഒരു ഭാഗം മാത്രം ഉപയോഗിച്ച് ഡാറ്റയുടെ n ബ്ലോക്കുകൾ വീണ്ടെടുക്കാൻ കഴിയുന്ന തരത്തിലാണ് റിഡൻഡൻസി കോഡുകൾ നിർമ്മിച്ചിരിക്കുന്നത്. അടുത്തതായി, ബ്ലോക്ക് റിഡൻഡൻസി കോഡുകൾ മാത്രമേ ഞങ്ങൾ പരിഗണിക്കൂ, അതായത് ഡാറ്റ ബ്ലോക്കുകളായി വിഭജിച്ചിരിക്കുന്നവ.

എല്ലാ n ബ്ലോക്കുകളുടെയും ഡാറ്റ വീണ്ടെടുക്കുന്നതിന്, നിങ്ങൾക്ക് n + m ബ്ലോക്കുകളെങ്കിലും ഉണ്ടായിരിക്കണം, കാരണം n-1 ബ്ലോക്ക് മാത്രം ഉള്ളതിനാൽ നിങ്ങൾക്ക് n ബ്ലോക്കുകൾ ലഭിക്കില്ല (ഈ സാഹചര്യത്തിൽ, നിങ്ങൾ 1 ബ്ലോക്ക് "നേർത്തതിൽ നിന്ന്" എടുക്കേണ്ടതുണ്ട്. വായു"). എല്ലാ ഡാറ്റയും വീണ്ടെടുക്കാൻ n + m ബ്ലോക്കുകളുടെ n റാൻഡം ബ്ലോക്കുകൾ മതിയോ? ഇത് റിഡൻഡൻസി കോഡുകളുടെ തരത്തെ ആശ്രയിച്ചിരിക്കുന്നു, ഉദാഹരണത്തിന്, അനിയന്ത്രിതമായ n ബ്ലോക്കുകൾ ഉപയോഗിച്ച് എല്ലാ ഡാറ്റയും വീണ്ടെടുക്കാൻ Reed-Solomon കോഡുകൾ നിങ്ങളെ അനുവദിക്കുന്നു, എന്നാൽ 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 ബിറ്റുകൾ), കൂടാതെ എല്ലാ പ്രവർത്തനങ്ങളും നടത്തുന്നതിന്റെ ഫലം (കൂടാതെ , കുറയ്ക്കൽ, ഗുണനം, ഹരിക്കൽ) എന്നിവയും ആവശ്യമായ ദൈർഘ്യമുള്ള വാക്കുകൾ ഉപയോഗിച്ച് കമ്പ്യൂട്ടർ മെമ്മറിയിൽ അവതരിപ്പിക്കും.

അത്തരം "പ്രത്യേക" സംഖ്യകൾ ഗണിതശാസ്ത്രം വളരെക്കാലമായി പഠിച്ചു; അവയെ ഫീൽഡുകൾ എന്ന് വിളിക്കുന്നു. സങ്കലനം, വ്യവകലനം, ഗുണനം, വിഭജനം എന്നിവയുടെ പ്രവർത്തനങ്ങളുള്ള മൂലകങ്ങളുടെ ഒരു കൂട്ടമാണ് ഫീൽഡ്.

ഫീൽഡിലെ ഏതെങ്കിലും രണ്ട് ഘടകങ്ങൾക്ക് ഓരോ പ്രവർത്തനത്തിനും (+, -, *, /) തനതായ ഫലം ലഭിക്കുന്ന ഫീൽഡുകളാണ് ഗലോയിസ്* ഫീൽഡുകൾ. 2: 2, 4, 8, 16, മുതലായവയുടെ ശക്തികളായ സംഖ്യകൾക്കായി ഗലോയിസ് ഫീൽഡുകൾ നിർമ്മിക്കാൻ കഴിയും (യഥാർത്ഥത്തിൽ ഏതെങ്കിലും പ്രൈം സംഖ്യ p യുടെ ശക്തികൾ, എന്നാൽ പ്രായോഗികമായി നമുക്ക് 2 ന്റെ ശക്തികളിൽ മാത്രമേ താൽപ്പര്യമുള്ളൂ). ഉദാഹരണത്തിന്, 16-ബിറ്റ് വാക്കുകൾക്ക്, ഇത് 65 ഘടകങ്ങൾ അടങ്ങിയ ഒരു ഫീൽഡാണ്, ഓരോ ജോഡിക്കും ഏത് പ്രവർത്തനത്തിന്റെയും ഫലം നിങ്ങൾക്ക് കണ്ടെത്താനാകും (+, -, *, /). മുകളിലുള്ള സമവാക്യങ്ങളിൽ നിന്നുള്ള x, p, ആൽഫ, ബീറ്റ, ഗാമ, ഡെൽറ്റ എന്നിവയുടെ മൂല്യങ്ങൾ കണക്കുകൂട്ടലുകൾക്കായി ഗലോയിസ് ഫീൽഡിന്റെ ഘടകങ്ങളായി കണക്കാക്കും.

അതിനാൽ, ഉചിതമായ ഒരു കമ്പ്യൂട്ടർ പ്രോഗ്രാം എഴുതി റിഡൻഡൻസി കോഡുകളുടെ ബ്ലോക്കുകൾ നിർമ്മിക്കാൻ കഴിയുന്ന സമവാക്യങ്ങളുടെ ഒരു സിസ്റ്റം നമുക്കുണ്ട്. സമവാക്യങ്ങളുടെ അതേ സിസ്റ്റം ഉപയോഗിച്ച്, നിങ്ങൾക്ക് ഡാറ്റ വീണ്ടെടുക്കൽ നടത്താൻ കഴിയും.

* ഇതൊരു കർശനമായ നിർവചനമല്ല, മറിച്ച് ഒരു വിവരണമാണ്.

ഡാറ്റ എങ്ങനെ വീണ്ടെടുക്കാം

ചില n + m ബ്ലോക്കുകൾ നഷ്‌ടപ്പെടുമ്പോൾ പുനഃസ്ഥാപിക്കൽ ആവശ്യമാണ്. ഇവ രണ്ടും ഡാറ്റ ബ്ലോക്കുകളും റിഡൻഡൻസി കോഡ് ബ്ലോക്കുകളും ആകാം. ഡാറ്റ ബ്ലോക്കുകൾ കൂടാതെ/അല്ലെങ്കിൽ റിഡൻഡൻസി കോഡ് ബ്ലോക്കുകളുടെ അഭാവം അർത്ഥമാക്കുന്നത്, മുകളിലുള്ള സമവാക്യങ്ങളിൽ അനുബന്ധ x കൂടാതെ/അല്ലെങ്കിൽ p വേരിയബിളുകൾ അജ്ഞാതമാണ് എന്നാണ്.

റീഡ്-സോളമൻ കോഡുകൾക്കുള്ള സമവാക്യങ്ങളെ സമവാക്യങ്ങളുടെ ഒരു സിസ്റ്റമായി കാണാൻ കഴിയും, അതിൽ എല്ലാ ആൽഫ, ബീറ്റ, ഗാമ, ഡെൽറ്റ മൂല്യങ്ങളും സ്ഥിരതയുള്ളതാണ്, ലഭ്യമായ ബ്ലോക്കുകളുമായി ബന്ധപ്പെട്ട എല്ലാ x, p എന്നിവയും അറിയപ്പെടുന്ന വേരിയബിളുകളും ശേഷിക്കുന്ന x, p എന്നിവയും അജ്ഞാതമാണ്.

ഉദാഹരണത്തിന്, ഡാറ്റ ബ്ലോക്കുകൾ 1, 2, 3, റിഡൻഡൻസി കോഡ് ബ്ലോക്ക് 2 എന്നിവ ലഭ്യമല്ലാതിരിക്കട്ടെ, തുടർന്ന് i-th ഗ്രൂപ്പിന്റെ വാക്കുകൾക്ക് ഇനിപ്പറയുന്ന സമവാക്യങ്ങൾ ഉണ്ടാകും (അജ്ഞാതമായവ ചുവപ്പ് നിറത്തിൽ അടയാളപ്പെടുത്തിയിരിക്കുന്നു):

ഞങ്ങൾക്ക് 4 അജ്ഞാതങ്ങളുള്ള 4 സമവാക്യങ്ങളുടെ ഒരു സിസ്റ്റം ഉണ്ട്, അതായത് നമുക്ക് അത് പരിഹരിക്കാനും ഡാറ്റ പുനഃസ്ഥാപിക്കാനും കഴിയും!

ഈ സമവാക്യ സംവിധാനത്തിൽ നിന്ന് റീഡ്-സോളമൻ കോഡുകൾക്കായുള്ള ഡാറ്റ വീണ്ടെടുക്കൽ സംബന്ധിച്ച് നിരവധി നിഗമനങ്ങൾ പിന്തുടരുന്നു (n ഡാറ്റ ബ്ലോക്കുകൾ, m റിഡൻഡൻസി കോഡ് ബ്ലോക്കുകൾ):

• 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 - പ്രാദേശിക പുനർനിർമ്മാണ കോഡുകൾ

Reed-Solomon കോഡുകൾ ഉപയോഗിച്ച് ഡാറ്റ വീണ്ടെടുക്കാൻ, നിങ്ങൾ n അനിയന്ത്രിതമായ ഡാറ്റ ബ്ലോക്കുകൾ ഉപയോഗിക്കേണ്ടതുണ്ട്. വിതരണം ചെയ്ത ഡാറ്റ സ്റ്റോറേജ് സിസ്റ്റങ്ങൾക്ക് ഇത് വളരെ പ്രധാനപ്പെട്ട ഒരു പോരായ്മയാണ്, കാരണം ഒരു തകർന്ന ഡിസ്കിൽ ഡാറ്റ പുനഃസ്ഥാപിക്കുന്നതിന്, നിങ്ങൾ മറ്റ് മിക്കതിൽ നിന്നും ഡാറ്റ വായിക്കേണ്ടിവരും, ഇത് ഡിസ്കുകളിലും നെറ്റ്വർക്കിലും ഒരു വലിയ അധിക ലോഡ് സൃഷ്ടിക്കുന്നു.

ഒരു ഡിസ്കിന്റെ പരാജയം അല്ലെങ്കിൽ ഓവർലോഡ് കാരണം ഡാറ്റയുടെ ഒരു ബ്ലോക്ക് ആക്സസ് ചെയ്യാൻ കഴിയാത്തതാണ് ഏറ്റവും സാധാരണമായ പിശകുകൾ. ഈ (ഏറ്റവും സാധാരണമായ) കേസിൽ ഡാറ്റ വീണ്ടെടുക്കുന്നതിനുള്ള അധിക ലോഡ് എങ്ങനെയെങ്കിലും കുറയ്ക്കാൻ കഴിയുമോ? ഇത് സാധ്യമാണെന്ന് ഇത് മാറുന്നു: ഈ ആവശ്യത്തിനായി പ്രത്യേകമായി 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-ൽ റീഡ്-സോളമൻ കോഡുകളുമായി സാമ്യമുള്ളതാണ്. റിഡൻഡൻസി കോഡ് ബ്ലോക്കുകളുടെ വാക്കുകൾ എണ്ണുന്നതിനുള്ള സമവാക്യങ്ങൾ ഇതായിരിക്കും:

ആൽഫ, ബീറ്റ, ഗാമ, ഡെൽറ്റ എന്നീ സംഖ്യകൾ തിരഞ്ഞെടുക്കുന്നതിന്, ഡാറ്റ വീണ്ടെടുക്കുന്നതിനുള്ള സാധ്യത ഉറപ്പുനൽകുന്നതിന് നിരവധി വ്യവസ്ഥകൾ പാലിക്കേണ്ടതുണ്ട് (അതായത്, സമവാക്യ സംവിധാനം പരിഹരിക്കുന്നു). നിങ്ങൾക്ക് അവയെക്കുറിച്ച് കൂടുതൽ വായിക്കാം ലേഖനം.
പ്രായോഗികമായി, പ്രാദേശിക റിഡൻഡൻസി കോഡുകൾ P3, P4 കണക്കാക്കാൻ XOR പ്രവർത്തനം ഉപയോഗിക്കുന്നു.

എൽആർസിയുടെ സമവാക്യങ്ങളുടെ സിസ്റ്റത്തിൽ നിന്ന് നിരവധി നിഗമനങ്ങൾ പിന്തുടരുന്നു:

• ഏതെങ്കിലും 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) ഉപയോഗിച്ചാൽ മതിയാകും. മറുവശത്ത്, അനുവദനീയമായ പരമാവധി പിശകുകളുടെ കാര്യത്തിൽ LRC റീഡ്-സോളമൻ കോഡുകളേക്കാൾ താഴ്ന്നതാണ്. മുകളിലുള്ള ഉദാഹരണങ്ങളിൽ, റീഡ്-സോളമൻ കോഡുകൾക്ക് ഏത് 4 പിശകുകൾക്കും ഡാറ്റ വീണ്ടെടുക്കാൻ കഴിയും, കൂടാതെ ഡാറ്റ വീണ്ടെടുക്കാൻ കഴിയാത്തപ്പോൾ എൽആർസിക്ക് 2 പിശകുകളുടെ 4 കോമ്പിനേഷനുകളുണ്ട്.

കൂടുതൽ പ്രധാനപ്പെട്ടത് നിർദ്ദിഷ്ട സാഹചര്യത്തെ ആശ്രയിച്ചിരിക്കുന്നു, എന്നാൽ പലപ്പോഴും എൽആർസി നൽകുന്ന അധിക ലോഡിലെ ലാഭം അൽപ്പം കുറഞ്ഞ വിശ്വാസ്യതയുള്ള സംഭരണത്തെക്കാൾ കൂടുതലാണ്.

4. മറ്റ് ആവർത്തന കോഡുകൾ

റീഡ്-സോളമൻ, എൽആർസി കോഡുകൾ കൂടാതെ, മറ്റ് പല റിഡൻഡൻസി കോഡുകളും ഉണ്ട്. വ്യത്യസ്ത റിഡൻഡൻസി കോഡുകൾ വ്യത്യസ്ത ഗണിതശാസ്ത്രം ഉപയോഗിക്കുന്നു. മറ്റ് ചില റിഡൻഡൻസി കോഡുകൾ ഇതാ:

• XOR ഓപ്പറേറ്റർ ഉപയോഗിക്കുന്ന റിഡൻഡൻസി കോഡ്. XOR പ്രവർത്തനം n ഡാറ്റ ബ്ലോക്കുകളിൽ നടത്തുന്നു, കൂടാതെ 1 ബ്ലോക്ക് റിഡൻഡൻസി കോഡുകൾ ലഭിക്കും, അതായത്, ഒരു n+1 സ്കീം (n ഡാറ്റ ബ്ലോക്കുകൾ, 1 റിഡൻഡൻസി കോഡ്). ൽ ഉപയോഗിച്ചു റെയ്ഡ് 5, ഇവിടെ ഡാറ്റയുടെ ബ്ലോക്കുകളും റിഡൻഡൻസി കോഡുകളും അറേയുടെ എല്ലാ ഡിസ്കുകളിലേക്കും ചാക്രികമായി എഴുതപ്പെടുന്നു.
• XOR പ്രവർത്തനത്തെ അടിസ്ഥാനമാക്കിയുള്ള ഇരട്ട-ഒറ്റ അൽഗോരിതം. റിഡൻഡൻസി കോഡുകളുടെ 2 ബ്ലോക്കുകൾ നിർമ്മിക്കാൻ നിങ്ങളെ അനുവദിക്കുന്നു, അതായത് n+2 സ്കീം.
• XOR പ്രവർത്തനത്തെ അടിസ്ഥാനമാക്കിയുള്ള STAR അൽഗോരിതം. റിഡൻഡൻസി കോഡുകളുടെ 3 ബ്ലോക്കുകൾ നിർമ്മിക്കാൻ നിങ്ങളെ അനുവദിക്കുന്നു, അതായത് n+3 സ്കീം.
• മൈക്രോസോഫ്റ്റിൽ നിന്നുള്ള മറ്റൊരു റിഡൻഡൻസി കോഡുകളാണ് പിരമിഡ് കോഡുകൾ.

5. Yandex-ൽ ഉപയോഗിക്കുക

Yandex ഇൻഫ്രാസ്ട്രക്ചർ പ്രോജക്ടുകൾ വിശ്വസനീയമായ ഡാറ്റ സംഭരണത്തിനായി റിഡൻഡൻസി കോഡുകൾ ഉപയോഗിക്കുന്നു. ചില ഉദാഹരണങ്ങൾ ഇതാ:

• MDS ഇന്റേണൽ ഒബ്ജക്റ്റ് സ്റ്റോറേജ്, ലേഖനത്തിന്റെ തുടക്കത്തിൽ ഞാൻ എഴുതിയത്.
• YT - Yandex-ന്റെ MapReduce സിസ്റ്റം.
• YDB (Yandex DataBase) - newSQL വിതരണം ചെയ്ത ഡാറ്റാബേസ്.

എംഡിഎസ് എൽആർസി റിഡൻഡൻസി കോഡുകൾ ഉപയോഗിക്കുന്നു, 8-2-2 സ്കീം. റിഡൻഡൻസി കോഡുകളുള്ള ഡാറ്റ വ്യത്യസ്ത സെർവറുകളിലെ 12 വ്യത്യസ്ത ഡിസ്കുകളിലേക്ക് 3 വ്യത്യസ്ത ഡിസികളിൽ എഴുതുന്നു: ഓരോ ഡിസിയിലും 4 സെർവറുകൾ. ഇതിനെക്കുറിച്ച് കൂടുതൽ വായിക്കുക ലേഖനം.

YT, ആദ്യം നടപ്പിലാക്കിയ റീഡ്-സോളമൻ കോഡുകളും (സ്കീം 6-3) LRC റിഡൻഡൻസി കോഡുകളും (സ്കീം 12-2-2) ഉപയോഗിക്കുന്നു, LRC എന്നത് ഇഷ്ടപ്പെട്ട സംഭരണ ​​രീതിയാണ്.

YDB ഇരട്ട-അടിസ്ഥാനത്തിലുള്ള റിഡൻഡൻസി കോഡുകൾ ഉപയോഗിക്കുന്നു (ചിത്രം 4-2). ഇതിനകം തന്നെ YDB-യിലെ റിഡൻഡൻസി കോഡുകളെക്കുറിച്ച് ഹൈലോഡിൽ പറഞ്ഞു.

വ്യത്യസ്ത റിഡൻഡൻസി കോഡ് സ്കീമുകളുടെ ഉപയോഗം സിസ്റ്റങ്ങൾക്കുള്ള വ്യത്യസ്ത ആവശ്യകതകൾ മൂലമാണ്. ഉദാഹരണത്തിന്, MDS-ൽ, LRC ഉപയോഗിച്ച് സംഭരിച്ച ഡാറ്റ ഒരേസമയം 3 DC-കളിൽ സ്ഥാപിക്കുന്നു. ഏതെങ്കിലും DC-കളിൽ ഒന്ന് പരാജയപ്പെടുകയാണെങ്കിൽ, ഡാറ്റ റീഡിംഗിനായി ലഭ്യമാണെന്നത് ഞങ്ങൾക്ക് പ്രധാനമാണ്, അതിനാൽ ബ്ലോക്കുകൾ DC-കളിൽ ഉടനീളം വിതരണം ചെയ്യണം, അങ്ങനെ ഏതെങ്കിലും DC ലഭ്യമല്ലെങ്കിൽ, ആക്സസ് ചെയ്യാൻ കഴിയാത്ത ബ്ലോക്കുകളുടെ എണ്ണം അനുവദനീയമായതിലും കൂടുതലായിരിക്കില്ല. 1-8-2 സ്കീമിൽ, നിങ്ങൾക്ക് ഓരോ ഡിസിയിലും 2 ബ്ലോക്കുകൾ സ്ഥാപിക്കാൻ കഴിയും, തുടർന്ന് ഏതെങ്കിലും ഡിസി ഓഫ് ചെയ്യുമ്പോൾ, 4 ബ്ലോക്കുകൾ ലഭ്യമല്ല, കൂടാതെ ഡാറ്റ വായിക്കാനും കഴിയും. 4 DC-കളിൽ സ്ഥാപിക്കുമ്പോൾ ഞങ്ങൾ തിരഞ്ഞെടുക്കുന്ന ഏത് സ്കീമായാലും, ഏത് സാഹചര്യത്തിലും (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 സിദ്ധാന്തം സംക്ഷിപ്തമായി വിശദീകരിക്കുകയും പ്രായോഗികമായി എൽആർസിയിലെ അനുഭവങ്ങൾ ചർച്ച ചെയ്യുകയും ചെയ്യുന്നു.
3. ഇരട്ട-ഒറ്റ സ്കീം: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
4. STAR സ്കീം: 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