રીડન્ડન્સી જેવો દેખાય છે તે આ છે

ડેટા સ્ટોરેજની વિશ્વસનીયતા વધારવા માટે રિડન્ડન્સી કોડ*નો વ્યાપકપણે કમ્પ્યુટર સિસ્ટમમાં ઉપયોગ થાય છે. યાન્ડેક્સમાં તેઓ ઘણા પ્રોજેક્ટ્સમાં ઉપયોગમાં લેવાય છે. ઉદાહરણ તરીકે, અમારા આંતરિક ઑબ્જેક્ટ સ્ટોરેજમાં પ્રતિકૃતિને બદલે રીડન્ડન્સી કોડ્સનો ઉપયોગ વિશ્વસનીયતાને બલિદાન આપ્યા વિના લાખો બચાવે છે. પરંતુ તેમના વ્યાપક ઉપયોગ હોવા છતાં, રીડન્ડન્સી કોડ્સ કેવી રીતે કાર્ય કરે છે તેના સ્પષ્ટ વર્ણનો ખૂબ જ ઓછા છે. જેઓ સમજવા માંગે છે તેઓ લગભગ નીચેનાનો સામનો કરે છે (માંથી વિકિપીડિયા):

મારું નામ વાદિમ છે, યાન્ડેક્સ પર હું આંતરિક ઑબ્જેક્ટ સ્ટોરેજ MDS વિકસાવી રહ્યો છું. આ લેખમાં, હું સરળ શબ્દોમાં રીડન્ડન્સી કોડ્સ (રીડ-સોલોમન અને LRC કોડ્સ) ના સૈદ્ધાંતિક પાયાનું વર્ણન કરીશ. હું તમને કહીશ કે તે કેવી રીતે કાર્ય કરે છે, જટિલ ગણિત અને દુર્લભ શબ્દો વિના. અંતે હું યાન્ડેક્ષમાં રીડન્ડન્સી કોડનો ઉપયોગ કરવાના ઉદાહરણો આપીશ.

હું સંખ્યાબંધ ગાણિતિક વિગતોને વિગતવાર ધ્યાનમાં લઈશ નહીં, પરંતુ જેઓ ઊંડા ઉતરવા માંગે છે તેમના માટે હું લિંક્સ પ્રદાન કરીશ. હું એ પણ નોંધીશ કે કેટલીક ગાણિતિક વ્યાખ્યાઓ કડક ન હોઈ શકે, કારણ કે લેખ ગણિતશાસ્ત્રીઓ માટે નથી, પરંતુ ઇજનેરો માટે છે જેઓ મુદ્દાના સારને સમજવા માંગે છે.

* અંગ્રેજી ભાષાના સાહિત્યમાં, રીડન્ડન્સી કોડને ઘણીવાર ઇરેઝર કોડ કહેવામાં આવે છે.

1. રીડન્ડન્સી કોડ્સનો સાર

બધા રીડન્ડન્સી કોડ્સનો સાર અત્યંત સરળ છે: ડેટા સ્ટોર કરો (અથવા ટ્રાન્સમિટ કરો) જેથી જ્યારે ભૂલો થાય ત્યારે તે ખોવાઈ ન જાય (ડિસ્ક નિષ્ફળતાઓ, ડેટા ટ્રાન્સફર ભૂલો, વગેરે).

મોટાભાગના* રીડન્ડન્સી કોડ્સમાં, ડેટાને n ડેટા બ્લોક્સમાં વિભાજિત કરવામાં આવે છે, જેના માટે રીડન્ડન્સી કોડના m બ્લોકની ગણતરી કરવામાં આવે છે, પરિણામે કુલ n + m બ્લોક્સ બને છે. રીડન્ડન્સી કોડ્સ એવી રીતે બનાવવામાં આવે છે કે ડેટાના n બ્લોક્સ ફક્ત n + m બ્લોક્સના એક ભાગનો ઉપયોગ કરીને પુનઃપ્રાપ્ત કરી શકાય છે. આગળ, અમે ફક્ત બ્લોક રીડન્ડન્સી કોડ્સને ધ્યાનમાં લઈશું, એટલે કે, જેમાં ડેટાને બ્લોક્સમાં વિભાજિત કરવામાં આવ્યો છે.

ડેટાના તમામ n બ્લોક્સને પુનઃપ્રાપ્ત કરવા માટે, તમારી પાસે ઓછામાં ઓછા n + m બ્લોક્સ હોવા જરૂરી છે, કારણ કે તમે માત્ર n-1 બ્લોક રાખવાથી n બ્લોક્સ મેળવી શકતા નથી (આ કિસ્સામાં, તમારે પાતળામાંથી 1 બ્લોક લેવો પડશે. હવા"). શું n + m બ્લોકના n રેન્ડમ બ્લોક્સ તમામ ડેટા પુનઃપ્રાપ્ત કરવા માટે પૂરતા છે? આ રીડન્ડન્સી કોડના પ્રકાર પર આધાર રાખે છે, ઉદાહરણ તરીકે, રીડ-સોલોમન કોડ્સ તમને મનસ્વી 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 બિટ્સ), અને તેના પર તમામ કામગીરીઓ કરવાના પરિણામ (ઉપરાંત , બાદબાકી, ગુણાકાર, ભાગાકાર) પણ જરૂરી લંબાઈના શબ્દોનો ઉપયોગ કરીને કમ્પ્યુટર મેમરીમાં રજૂ કરવામાં આવશે.

આવી "વિશેષ" સંખ્યાઓનો લાંબા સમયથી ગણિત દ્વારા અભ્યાસ કરવામાં આવે છે; તેમને ક્ષેત્રો કહેવામાં આવે છે. ક્ષેત્ર એ તત્વોનો સમૂહ છે જેમાં સરવાળો, બાદબાકી, ગુણાકાર અને ભાગાકારની ક્રિયાઓ તેમના માટે નિર્ધારિત છે.

ગેલોઈસ* ફીલ્ડ્સ એ ફીલ્ડ છે કે જેના માટે ફીલ્ડના કોઈપણ બે ઘટકો માટે દરેક ઓપરેશન (+, -, *, /)નું અનન્ય પરિણામ હોય છે. 2: 2, 4, 8, 16, વગેરેની શક્તિઓ ધરાવતી સંખ્યાઓ માટે ગેલોઈસ ક્ષેત્રો બનાવી શકાય છે. ઉદાહરણ તરીકે, 2-બીટ શબ્દો માટે, આ એક ફીલ્ડ છે જેમાં 16 તત્વો છે, જેમાંથી દરેક જોડી માટે તમે કોઈપણ ઓપરેશનનું પરિણામ શોધી શકો છો (+, -, *, /). ઉપરના સમીકરણોમાંથી x, p, આલ્ફા, બીટા, ગામા, ડેલ્ટાના મૂલ્યોને ગણતરી માટે ગેલોઈસ ક્ષેત્રના ઘટકો ગણવામાં આવશે.

આમ, આપણી પાસે સમીકરણોની એક સિસ્ટમ છે જેની સાથે આપણે યોગ્ય કોમ્પ્યુટર પ્રોગ્રામ લખીને રીડન્ડન્સી કોડના બ્લોક્સ બનાવી શકીએ છીએ. સમીકરણોની સમાન સિસ્ટમનો ઉપયોગ કરીને, તમે ડેટા પુનઃપ્રાપ્તિ કરી શકો છો.

* આ કોઈ કડક વ્યાખ્યા નથી, પરંતુ તેનું વર્ણન છે.

ડેટા કેવી રીતે પુનઃપ્રાપ્ત કરવો

જ્યારે કેટલાક n + m બ્લોક્સ ખૂટે છે ત્યારે પુનઃસંગ્રહ જરૂરી છે. આ ડેટા બ્લોક્સ અને રીડન્ડન્સી કોડ બ્લોક્સ બંને હોઈ શકે છે. ડેટા બ્લોક્સ અને/અથવા રીડન્ડન્સી કોડ બ્લોક્સની ગેરહાજરીનો અર્થ એ થશે કે અનુરૂપ x અને/અથવા p ચલો ઉપરના સમીકરણોમાં અજાણ્યા છે.

રીડ-સોલોમન કોડ્સ માટેના સમીકરણોને સમીકરણોની સિસ્ટમ તરીકે જોઈ શકાય છે જેમાં તમામ આલ્ફા, બીટા, ગામા, ડેલ્ટા મૂલ્યો સ્થિરાંકો છે, ઉપલબ્ધ બ્લોક્સને અનુરૂપ તમામ x અને p જાણીતા ચલો છે, અને બાકીના x અને p અજ્ઞાત છે.

ઉદાહરણ તરીકે, ડેટા બ્લોક્સ 1, 2, 3 અને રીડન્ડન્સી કોડ બ્લોક 2 અનુપલબ્ધ રહેવા દો, પછી શબ્દોના i-th જૂથ માટે નીચેની સમીકરણોની સિસ્ટમ હશે (અજાણ્યાઓને લાલ રંગમાં ચિહ્નિત કરવામાં આવ્યા છે):

અમારી પાસે 4 અજ્ઞાત સાથે 4 સમીકરણોની સિસ્ટમ છે, જેનો અર્થ છે કે અમે તેને હલ કરી શકીએ છીએ અને ડેટા પુનઃસ્થાપિત કરી શકીએ છીએ!

આ સમીકરણોની સિસ્ટમમાંથી રીડ-સોલોમન કોડ્સ (એન ડેટા બ્લોક્સ, એમ રીડન્ડન્સી કોડ બ્લોક્સ) માટે ડેટા પુનઃપ્રાપ્તિ વિશે સંખ્યાબંધ તારણો આવે છે:

• જો કોઈ m બ્લોક અથવા ઓછા ખોવાઈ જાય તો ડેટા પુનઃપ્રાપ્ત કરી શકાય છે. જો m+1 અથવા વધુ બ્લોક્સ ખોવાઈ જાય, તો ડેટા પુનઃસ્થાપિત કરી શકાતો નથી: m + 1 અજ્ઞાત સાથે m સમીકરણોની સિસ્ટમ ઉકેલવી અશક્ય છે.
• એક પણ ડેટા બ્લોક પુનઃપ્રાપ્ત કરવા માટે, તમારે બાકીના બ્લોકમાંથી કોઈપણ n નો ઉપયોગ કરવાની જરૂર છે, અને તમે કોઈપણ રીડન્ડન્સી કોડનો ઉપયોગ કરી શકો છો.

તમારે બીજું શું જાણવાની જરૂર છે

ઉપરના વર્ણનમાં, હું સંખ્યાબંધ મહત્વપૂર્ણ મુદ્દાઓને ટાળું છું જેને ધ્યાનમાં લેવા માટે ગણિતમાં ઊંડા ઉતરવાની જરૂર છે. ખાસ કરીને, હું નીચેના વિશે કંઈપણ કહેતો નથી:

• રીડ-સોલોમન કોડ્સ માટેની સમીકરણોની સિસ્ટમમાં અજ્ઞાતના કોઈપણ સંયોજન માટે (અનન્ય) ઉકેલ હોવો જોઈએ (m અજ્ઞાત કરતાં વધુ નહીં). આ જરૂરિયાતના આધારે, આલ્ફા, બીટા, ગામા અને ડેલ્ટાના મૂલ્યો પસંદ કરવામાં આવે છે.
• સમીકરણોની સિસ્ટમ આપમેળે બાંધવામાં સક્ષમ હોવી જોઈએ (જે બ્લોક્સ અનુપલબ્ધ છે તેના આધારે) અને ઉકેલી શકાય છે.
• અમારે ગેલોઈસ ફીલ્ડ બનાવવાની જરૂર છે: આપેલ શબ્દ કદ માટે, કોઈપણ બે ઘટકો માટે કોઈપણ ઓપરેશન (+, -, *, /) નું પરિણામ શોધવા માટે સક્ષમ બનો.

લેખના અંતે આ મહત્વપૂર્ણ મુદ્દાઓ પરના સાહિત્યના સંદર્ભો છે.

n અને m ની પસંદગી

વ્યવહારમાં n અને m કેવી રીતે પસંદ કરવું? વ્યવહારમાં, ડેટા સ્ટોરેજ સિસ્ટમ્સમાં, રિડન્ડન્સી કોડ્સનો ઉપયોગ જગ્યા બચાવવા માટે થાય છે, તેથી m હંમેશા n કરતાં ઓછું પસંદ કરવામાં આવે છે. તેમના વિશિષ્ટ મૂલ્યો સંખ્યાબંધ પરિબળો પર આધાર રાખે છે, જેમાં નીચેનાનો સમાવેશ થાય છે:

• ડેટા સ્ટોરેજની વિશ્વસનીયતા. મીટર જેટલું મોટું, ડિસ્ક નિષ્ફળતાઓની સંખ્યા જેટલી વધારે છે જે બચી શકે છે, એટલે કે, વિશ્વસનીયતા વધારે છે.
• રીડન્ડન્ટ સ્ટોરેજ. m/n રેશિયો જેટલો ઊંચો હશે, તેટલી વધારે સ્ટોરેજ રિડન્ડન્સી હશે અને સિસ્ટમ વધુ ખર્ચાળ હશે.
• પ્રક્રિયા સમય માટે વિનંતી કરો. સરવાળો n + m જેટલો મોટો હશે, વિનંતીઓનો પ્રતિભાવ સમય એટલો લાંબો હશે. ડેટા વાંચવા માટે (પુનઃપ્રાપ્તિ દરમિયાન) વિવિધ ડિસ્ક પર સંગ્રહિત n બ્લોક્સ વાંચવાની જરૂર હોવાથી, વાંચવાનો સમય સૌથી ધીમી ડિસ્ક દ્વારા નક્કી કરવામાં આવશે.

વધુમાં, કેટલાક DC માં ડેટા સંગ્રહિત કરવાથી n અને m ની પસંદગી પર વધારાના નિયંત્રણો લાદવામાં આવે છે: જો 1 DC બંધ હોય, તો પણ ડેટા વાંચવા માટે ઉપલબ્ધ હોવો જોઈએ. ઉદાહરણ તરીકે, 3 DC માં ડેટા સ્ટોર કરતી વખતે, નીચેની શરત પૂરી કરવી આવશ્યક છે: m >= n/2, અન્યથા 1 DC બંધ હોય ત્યારે વાંચવા માટે ડેટા અનુપલબ્ધ હોય તેવી સ્થિતિ હોઈ શકે છે.

3. LRC - સ્થાનિક પુનર્નિર્માણ કોડ્સ

રીડ-સોલોમન કોડ્સનો ઉપયોગ કરીને ડેટા પુનઃપ્રાપ્ત કરવા માટે, તમારે n મનસ્વી ડેટા બ્લોક્સનો ઉપયોગ કરવો પડશે. વિતરિત ડેટા સ્ટોરેજ સિસ્ટમ્સ માટે આ એક ખૂબ જ નોંધપાત્ર ગેરલાભ છે, કારણ કે એક તૂટેલી ડિસ્ક પર ડેટા પુનઃસ્થાપિત કરવા માટે, તમારે ડિસ્ક અને નેટવર્ક પર મોટો વધારાનો લોડ બનાવીને, અન્યમાંથી મોટા ભાગનો ડેટા વાંચવો પડશે.

સૌથી સામાન્ય ભૂલો એક ડિસ્કની નિષ્ફળતા અથવા ઓવરલોડને કારણે ડેટાના એક બ્લોકની અગમ્યતા છે. શું આ (સૌથી સામાન્ય) કિસ્સામાં ડેટા પુનઃપ્રાપ્તિ માટેના વધારાના લોડને કોઈક રીતે ઘટાડવાનું શક્ય છે? તે તારણ આપે છે કે તમે આ કરી શકો છો: આ હેતુ માટે ખાસ કરીને LRC રીડન્ડન્સી કોડ્સ છે.

LRC (સ્થાનિક પુનઃનિર્માણ કોડ્સ) એ વિન્ડોઝ એઝ્યુર સ્ટોરેજમાં ઉપયોગ માટે માઇક્રોસોફ્ટ દ્વારા શોધાયેલ રીડન્ડન્સી કોડ છે. 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 નો ઉપયોગ કરીને.

બાકીનું એલઆરસીમાં રીડ-સોલોમન કોડ્સ સાથે સામ્યતા દ્વારા કરવામાં આવે છે. રીડન્ડન્સી કોડ બ્લોકના શબ્દોની ગણતરી માટેના સમીકરણો આ હશે:

આલ્ફા, બીટા, ગામા, ડેલ્ટા નંબરો પસંદ કરવા માટે, ડેટા પુનઃપ્રાપ્તિ (એટલે ​​​​કે, સમીકરણ સિસ્ટમ હલ કરવાની) શક્યતાની ખાતરી આપવા માટે સંખ્યાબંધ શરતો પૂરી કરવી આવશ્યક છે. તમે તેમના વિશે વધુ વાંચી શકો છો લેખ.
વ્યવહારમાં પણ, XOR ઑપરેશનનો ઉપયોગ સ્થાનિક રિડન્ડન્સી કોડ્સ P3, P4 ની ગણતરી કરવા માટે થાય છે.

LRC માટે સમીકરણોની સિસ્ટમમાંથી સંખ્યાબંધ તારણો આવે છે:

• કોઈપણ 1 ડેટા બ્લોક પુનઃપ્રાપ્ત કરવા માટે, n/l બ્લોક્સ વાંચવા માટે તે પૂરતું છે (અમારા ઉદાહરણમાં n/2).
• જો r + l બ્લોક્સ અનુપલબ્ધ છે, અને બધા બ્લોક્સ એક જૂથમાં શામેલ છે, તો ડેટા પુનઃસ્થાપિત કરી શકાશે નહીં. આ એક ઉદાહરણ સાથે સમજાવવું સરળ છે. બ્લોક્સ X1–X3 અને P3 અનુપલબ્ધ રહેવા દો: આ સમાન જૂથના r + l બ્લોક્સ છે, અમારા કિસ્સામાં 4. પછી આપણી પાસે 3 અજ્ઞાત સાથે 4 સમીકરણોની સિસ્ટમ છે જે ઉકેલી શકાતી નથી.
• r + l બ્લોકની અનુપલબ્ધતાના અન્ય તમામ કેસોમાં (જ્યારે દરેક જૂથમાંથી ઓછામાં ઓછો એક બ્લોક ઉપલબ્ધ હોય), LRCમાંનો ડેટા પુનઃસ્થાપિત કરી શકાય છે.

આમ, એલઆરસી એકલ ભૂલો પછી ડેટા પુનઃપ્રાપ્ત કરવામાં રીડ-સોલોમન કોડ્સ કરતાં આગળ છે. રીડ-સોલોમન કોડ્સમાં, ડેટાના એક બ્લોકને પણ પુનઃપ્રાપ્ત કરવા માટે, તમારે n બ્લોક્સનો ઉપયોગ કરવાની જરૂર છે, અને એલઆરસીમાં, ડેટાના એક બ્લોકને પુનઃપ્રાપ્ત કરવા માટે, તે n/l બ્લોક્સનો ઉપયોગ કરવા માટે પૂરતું છે (અમારા ઉદાહરણમાં n/2). બીજી બાજુ, એલઆરસી એ રીડ-સોલોમન કોડ્સ કરતાં નીચી છે, મહત્તમ અનુમતિપાત્ર ભૂલોની દ્રષ્ટિએ. ઉપરના ઉદાહરણોમાં, રીડ-સોલોમન કોડ કોઈપણ 4 ભૂલો માટે ડેટા પુનઃપ્રાપ્ત કરી શકે છે, અને જ્યારે ડેટા પુનઃપ્રાપ્ત કરી શકાતો નથી ત્યારે LRC માટે 2 ભૂલોના 4 સંયોજનો છે.

શું વધુ મહત્વનું છે તે ચોક્કસ પરિસ્થિતિ પર આધાર રાખે છે, પરંતુ ઘણીવાર LRC દ્વારા આપવામાં આવતા વધારાના ભારમાં બચત સહેજ ઓછા વિશ્વસનીય સ્ટોરેજ કરતાં વધી જાય છે.

4. અન્ય રીડન્ડન્સી કોડ્સ

રીડ-સોલોમન અને LRC કોડ્સ ઉપરાંત, અન્ય ઘણા રીડન્ડન્સી કોડ્સ છે. વિવિધ રીડન્ડન્સી કોડ્સ વિવિધ ગણિતનો ઉપયોગ કરે છે. અહીં કેટલાક અન્ય રીડન્ડન્સી કોડ્સ છે:

• XOR ઓપરેટરનો ઉપયોગ કરીને રીડન્ડન્સી કોડ. XOR ઑપરેશન n ડેટા બ્લોક્સ પર કરવામાં આવે છે, અને રિડન્ડન્સી કોડનો 1 બ્લોક મેળવવામાં આવે છે, એટલે કે, n+1 સ્કીમ (n ડેટા બ્લોક્સ, 1 રિડન્ડન્સી કોડ). માં વપરાય છે રેઇડ 5, જ્યાં ડેટાના બ્લોક્સ અને રીડન્ડન્સી કોડ્સ એરેની બધી ડિસ્ક પર ચક્રીય રીતે લખવામાં આવે છે.
• XOR ઑપરેશન પર આધારિત સમ-વિચિત્ર અલ્ગોરિધમ. તમને રીડન્ડન્સી કોડના 2 બ્લોક્સ, એટલે કે n+2 સ્કીમ બનાવવાની મંજૂરી આપે છે.
• XOR ઓપરેશન પર આધારિત STAR અલ્ગોરિધમ. તમને રીડન્ડન્સી કોડના 3 બ્લોક્સ, એટલે કે n+3 સ્કીમ બનાવવાની મંજૂરી આપે છે.
• પિરામાઈડ કોડ એ Microsoft ના અન્ય રીડન્ડન્સી કોડ છે.

5. યાન્ડેક્સમાં ઉપયોગ કરો

સંખ્યાબંધ યાન્ડેક્સ ઇન્ફ્રાસ્ટ્રક્ચર પ્રોજેક્ટ્સ વિશ્વસનીય ડેટા સ્ટોરેજ માટે રીડન્ડન્સી કોડનો ઉપયોગ કરે છે. અહીં કેટલાક ઉદાહરણો છે:

• MDS આંતરિક ઑબ્જેક્ટ સ્ટોરેજ, જેના વિશે મેં લેખની શરૂઆતમાં લખ્યું હતું.
• YT — યાન્ડેક્સની મેપરેડ્યુસ સિસ્ટમ.
• YDB (યાન્ડેક્ષ ડેટાબેઝ) - ન્યૂએસક્યુએલ વિતરિત ડેટાબેઝ.

MDS LRC રીડન્ડન્સી કોડ્સ, 8-2-2 સ્કીમનો ઉપયોગ કરે છે. રીડન્ડન્સી કોડ્સ સાથેનો ડેટા 12 અલગ-અલગ ડીસીમાં અલગ-અલગ સર્વરમાં 3 અલગ-અલગ ડિસ્ક પર લખવામાં આવે છે: દરેક DCમાં 4 સર્વર. આ વિશે વધુ વાંચો લેખ.

YT બંને રીડ-સોલોમન કોડ્સ (સ્કીમ 6-3) નો ઉપયોગ કરે છે, જે અમલમાં મૂકનાર પ્રથમ હતા, અને LRC રીડન્ડન્સી કોડ્સ (સ્કીમ 12-2-2), જેમાં LRC એ પસંદગીની સ્ટોરેજ પદ્ધતિ છે.

YDB સમ-વિષમ આધારિત રીડન્ડન્સી કોડનો ઉપયોગ કરે છે (આકૃતિ 4-2). YDB માં પહેલેથી જ રીડન્ડન્સી કોડ વિશે હાઇલોડ પર જણાવ્યું હતું.

વિવિધ રીડન્ડન્સી કોડ યોજનાઓનો ઉપયોગ સિસ્ટમો માટેની વિવિધ આવશ્યકતાઓને કારણે છે. ઉદાહરણ તરીકે, MDS માં, LRC નો ઉપયોગ કરીને સંગ્રહિત ડેટા એક જ સમયે 3 DC માં મૂકવામાં આવે છે. અમારા માટે તે અગત્યનું છે કે જો કોઈપણ ડીસીમાંથી 1 નિષ્ફળ જાય તો ડેટા વાંચવા માટે ઉપલબ્ધ રહે છે, તેથી બ્લોક્સને સમગ્ર ડીસીમાં વિતરિત કરવા જોઈએ જેથી કરીને જો કોઈ ડીસી અનુપલબ્ધ હોય, તો અપ્રાપ્ય બ્લોક્સની સંખ્યા અનુમતિપાત્ર કરતાં વધુ ન હોય. 8-2-2 સ્કીમમાં, તમે દરેક DCમાં 4 બ્લોક્સ મૂકી શકો છો, પછી જ્યારે કોઈપણ DC બંધ હોય, ત્યારે 4 બ્લોક્સ અનુપલબ્ધ હશે, અને ડેટા વાંચી શકાય છે. 3 ડીસીમાં મૂકતી વખતે આપણે જે પણ સ્કીમ પસંદ કરીએ છીએ, કોઈપણ સંજોગોમાં ત્યાં (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 વિશે 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