ተደጋጋሚነት ይህን ይመስላል

የመረጃ ማከማቻ አስተማማኝነትን ለመጨመር በኮምፒዩተር ሲስተሞች ውስጥ የድግግሞሽ ኮድ * በሰፊው ጥቅም ላይ ይውላል። በ Yandex ውስጥ በብዙ ፕሮጀክቶች ውስጥ ጥቅም ላይ ይውላሉ. ለምሳሌ በውስጣችን የነገሮች ማከማቻ ውስጥ ከማባዛት ይልቅ የድግግሞሽ ኮዶችን መጠቀም ታማኝነትን ሳንቆርጥ ሚሊዮኖችን ይቆጥባል። ነገር ግን በሰፊው ጥቅም ላይ ቢውሉም, የመድገም ኮዶች እንዴት እንደሚሠሩ ግልጽ መግለጫዎች በጣም ጥቂት ናቸው. ለመረዳት የሚፈልጉት በግምት የሚከተሉትን ያጋጥሟቸዋል (ከ ዊኪፔዲያ):

ስሜ ቫዲም እባላለሁ፣ በ Yandex የውስጣዊ ነገር ማከማቻ MDS እያዘጋጀሁ ነው። በዚህ ጽሑፍ ውስጥ የድጋሚ ኮድ (ሪድ-ሰለሞን እና የኤልአርሲ ኮዶች) የንድፈ ሃሳባዊ መሠረቶችን በቀላል ቃላት እገልጻለሁ። ያለ ውስብስብ ሂሳብ እና ያልተለመዱ ቃላት እንዴት እንደሚሰራ እነግርዎታለሁ። በመጨረሻ በ Yandex ውስጥ የድጋሚ ኮዶችን የመጠቀም ምሳሌዎችን እሰጣለሁ።

በርካታ የሂሳብ ዝርዝሮችን በዝርዝር አላስብም, ነገር ግን በጥልቀት ለመጥለቅ ለሚፈልጉ አገናኞችን እሰጣለሁ. ጽሑፉ ለሒሳብ ሊቃውንት የታሰበ ሳይሆን የጉዳዩን ይዘት ለመረዳት ለሚፈልጉ መሐንዲሶች ስለሆነ አንዳንድ የሂሳብ ትርጓሜዎች ጥብቅ ላይሆኑ እንደሚችሉ አስተውያለሁ።

* በእንግሊዘኛ ቋንቋ ሥነ-ጽሑፍ፣ የመቀየሪያ ኮዶች ብዙውን ጊዜ የመደምሰስ ኮድ ይባላሉ።

1. የድግግሞሽ ኮዶች ይዘት

የሁሉም የድግግሞሽ ኮዶች ይዘት እጅግ በጣም ቀላል ነው፡ ስህተቶች ሲከሰቱ እንዳይጠፋ (የዲስክ ውድቀቶች፣ የውሂብ ማስተላለፍ ስህተቶች፣ ወዘተ) ውሂብ ያከማቹ (ወይም ያስተላልፉ)።

በአብዛኛዎቹ* የድግግሞሽ ኮዶች መረጃው በ n ዳታ ብሎኮች የተከፋፈለ ሲሆን ለዚህም m blocks of reundancy code ተቆጥሯል፣ ይህም በአጠቃላይ n + m ብሎኮችን ያስከትላል። የድግግሞሽ ኮዶች የተገነቡት የ n + m ብሎኮች የተወሰነ ክፍል ብቻ በመጠቀም መረጃን መልሶ ለማግኘት በሚያስችል መንገድ ነው። በመቀጠል ፣ የድግግሞሽ ኮዶችን ብቻ እንመረምራለን ፣ ማለትም ፣ ውሂቡ ወደ ብሎኮች የተከፋፈሉት።

ሁሉንም n የውሂብ ብሎኮችን መልሶ ለማግኘት ቢያንስ n የ n + m ብሎኮች ሊኖርዎት ይገባል ፣ ምክንያቱም n-1 ብሎክን ብቻ በመያዝ n ብሎኮችን ማግኘት ስለማይችሉ (በዚህ ሁኔታ ፣ ከቀጭኑ 1 ብሎክ መውሰድ ያስፈልግዎታል) አየር"). ሁሉንም ውሂብ መልሶ ለማግኘት የ n + m ብሎኮች n የዘፈቀደ ብሎኮች በቂ ናቸው? ይሄ እንደ የድግግሞሽ ኮዶች አይነት ይወሰናል፡ ለምሳሌ፡ ሪድ-ሰለሞን ኮዶች የዘፈቀደ 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 የድጋሚ ኮድ ብሎኮች ቃላቶች ናቸው ፣ ሁሉም አልፋ ፣ ቤታ ፣ ጋማ እና ዴልታ ለሁሉም ተመሳሳይ የሆኑ ልዩ የተመረጡ ቁጥሮች ናቸው። እነዚህ ሁሉ እሴቶች ተራ ቁጥሮች አይደሉም ፣ ግን የጋሎይስ መስክ አካላት ናቸው ፣ ክዋኔዎች + ፣ - ፣ * ፣ / ሁላችንም የምናውቃቸው ክዋኔዎች አይደሉም ፣ ግን በጋሎይስ አካላት ላይ ልዩ ክዋኔዎች አስተዋውቀዋል ። መስክ.

የጋሎይስ መስኮች ለምን ያስፈልጋሉ?

ሁሉም ነገር ቀላል ይመስላል-መረጃውን ወደ ብሎኮች እንከፍላለን ፣ ብሎኮችን ወደ ቃላት ፣ የውሂብ ብሎኮችን ቃላት በመጠቀም የድግግሞሽ ኮድ ብሎኮችን ቃላት እንቆጥራለን - እንደገና የመቀየሪያ ኮድ ብሎኮች እናገኛለን። በአጠቃላይ ይህ እንዴት እንደሚሰራ ነው, ነገር ግን ዲያቢሎስ በዝርዝሮች ውስጥ ነው.

1. ከላይ እንደተገለፀው የቃሉ መጠን ቋሚ ነው, በእኛ ምሳሌ 16 ቢት. ከላይ ያሉት የሪድ-ሰለሞን ኮዶች ቀመሮች ተራ ኢንቲጀር ሲጠቀሙ ፒን የማስላት ውጤቱ ትክክለኛ መጠን ያለው ቃል በመጠቀም ላይሆን ይችላል።
2. መረጃን በሚመልሱበት ጊዜ, ከላይ ያሉት ቀመሮች መረጃን መልሶ ለማግኘት መፍትሄ ሊያገኙ የሚገባቸው የእኩልታዎች ስርዓት ተደርገው ይወሰዳሉ. በመፍትሔው ሂደት ውስጥ ኢንቲጀሮችን እርስ በርስ መከፋፈል አስፈላጊ ሊሆን ይችላል, በዚህም ምክንያት በኮምፒተር ማህደረ ትውስታ ውስጥ በትክክል ሊወከል የማይችል እውነተኛ ቁጥር.

እነዚህ ችግሮች ለሪድ-ሰለሞን ኮዶች ኢንቲጀር መጠቀምን ይከለክላሉ። ለችግሩ መፍትሄው ኦሪጅናል ነው ፣ እንደሚከተለው ሊገለፅ ይችላል-የሚፈለገውን ርዝመት ያላቸውን ቃላት (ለምሳሌ ፣ 16 ቢት) በመጠቀም ሊወከሉ የሚችሉ ልዩ ቁጥሮችን እናውጣ እና ሁሉንም ክዋኔዎች በማከናወን ላይ (ተጨማሪ)። , መቀነስ, ማባዛት, ማካፈል) የሚፈለገውን ርዝመት ያላቸውን ቃላት በመጠቀም በኮምፒተር ማህደረ ትውስታ ውስጥም ይቀርባል.

እንደነዚህ ያሉት "ልዩ" ቁጥሮች ለረጅም ጊዜ በሂሳብ ጥናት ተደርገዋል, እነሱ መስክ ይባላሉ. መስክ የመደመር፣ የመቀነስ፣ የማባዛት እና የማካፈል ስራዎች ያሉት የንጥረ ነገሮች ስብስብ ነው።

የጋሎይስ * መስኮች ለእያንዳንዱ የሜዳው ሁለት አካላት (+, -, *, /) ልዩ ውጤት ያላቸው መስኮች ናቸው. የጋሎይስ ሜዳዎች የ 2: 2, 4, 8, 16, ወዘተ ኃይላት ለሆኑ ቁጥሮች ሊገነቡ ይችላሉ (በእውነቱ የማንኛውም ዋና ቁጥር ፒ, ነገር ግን በተግባር እኛ የምንፈልገው ለ 2 ኃይሎች ብቻ ነው). ለምሳሌ, ለ 16-ቢት ቃላት, ይህ 65 ኤለመንቶችን የያዘ መስክ ነው, ለእያንዳንዱ ጥንድ የትኛውንም ኦፕሬሽን (+, -, *, /) ውጤት ማግኘት ይችላሉ. ከላይ ካሉት እኩልታዎች የ x ፣ p ፣ alpha ፣ beta ፣ gamma ፣ delta እሴቶች ለስሌቶች የጋሎይስ መስክ አካላት ይቆጠራሉ።

ስለዚህ ተገቢውን የኮምፒዩተር ፕሮግራም በመጻፍ የድጋፍ ኮድን መገንባት የምንችልበት የእኩልታዎች ስርዓት አለን። ተመሳሳዩን የእኩልታዎች ስርዓት በመጠቀም, የውሂብ መልሶ ማግኛን ማከናወን ይችላሉ.

* ይህ ጥብቅ ፍቺ ሳይሆን መግለጫ ነው።

ውሂብን እንዴት መልሶ ማግኘት እንደሚቻል

አንዳንድ የ n + m ብሎኮች ሲጠፉ ወደነበረበት መመለስ ያስፈልጋል። እነዚህ ሁለቱም የውሂብ ብሎኮች እና የድግግሞሽ ኮድ እገዳዎች ሊሆኑ ይችላሉ። የውሂብ ብሎኮች እና/ወይም የድግግሞሽ ኮድ ብሎኮች አለመኖር ተጓዳኝ x እና/ወይም p ተለዋዋጮች ከላይ ባሉት እኩልታዎች የማይታወቁ ናቸው ማለት ነው።

የሪድ-ሰለሞን ኮዶች እኩልታዎች ሁሉም አልፋ ፣ ቤታ ፣ ጋማ ፣ ዴልታ እሴቶች ቋሚዎች ናቸው ፣ ሁሉም x እና p ካሉ ብሎኮች ጋር የሚዛመዱ የታወቁ ተለዋዋጮች እና የተቀሩት x እና p እንደ እኩልታዎች ስርዓት ሊታዩ ይችላሉ። የማይታወቁ ናቸው.

ለምሳሌ የውሂብ ብሎኮች 1 ፣ 2 ፣ 3 እና የድግግሞሽ ኮድ 2 አይገኙም ፣ ከዚያ ለ i-th የቃላት ቡድን የሚከተለው የእኩልታዎች ስርዓት ይኖራል (ያልታወቁ በቀይ ምልክት ተደርገዋል)

ከ 4 ያልታወቁ 4 እኩልታዎች ጋር የ XNUMX እኩልታዎች ስርዓት አለን ይህም ማለት መፍታት እና መረጃውን ወደነበረበት መመለስ እንችላለን ማለት ነው!

ከዚህ የእኩልታዎች ስርዓት ለሪድ-ሰለሞን ኮዶች (n data blocks፣ m redundancy code blocks) ስለ ውሂብ መልሶ ማግኛ ብዙ ድምዳሜዎች ይከተላሉ።

• ማንኛውም m ብሎኮች ወይም ያነሱ ከጠፉ ውሂብን መልሶ ማግኘት ይቻላል። m+1 ወይም ከዚያ በላይ ብሎኮች ከጠፉ ውሂቡ ወደነበረበት ሊመለስ አይችልም፡ የ m + 1 ያልታወቁትን የ m እኩልታዎች ስርዓት መፍታት አይቻልም።
• አንድ የውሂብ ብሎክ እንኳን መልሶ ለማግኘት፣ ከቀሪዎቹ ብሎኮች ውስጥ ማንኛውንም n መጠቀም ያስፈልግዎታል እና ማንኛውንም የድግግሞሽ ኮዶችን መጠቀም ይችላሉ።

ሌላ ምን ማወቅ ያስፈልግዎታል

ከላይ በተገለጸው ገለጻ፣ በሂሳብ ውስጥ በጥልቀት መግባትን የሚጠይቁትን በርካታ አስፈላጊ ጉዳዮችን አስወግጃለሁ። በተለይ ስለሚከተሉት ነገሮች ምንም አልልም።

• የሪድ-ሰለሞን ኮዶች የእኩልታዎች ስርዓት ለማንኛውም ያልታወቁ ነገሮች ጥምረት (ከኤም የማይበልጥ) መፍትሄ ሊኖረው ይገባል። በዚህ መስፈርት መሰረት የአልፋ፣ቤታ፣ጋማ እና ዴልታ እሴቶች ተመርጠዋል።
• የእኩልታዎች ስርዓት በራስ ሰር መገንባት መቻል አለበት (በየትኞቹ ብሎኮች እንደማይገኙ) እና መፍታት መቻል አለበት።
• የጋሎይስ መስክ መገንባት አለብን: ለተወሰነ የቃላት መጠን, ለማንኛውም ሁለት አካላት የማንኛውንም ኦፕሬሽን (+, -, *, /) ውጤት ማግኘት መቻል.

በአንቀጹ መጨረሻ ላይ በእነዚህ አስፈላጊ ጉዳዮች ላይ ስለ ሥነ ጽሑፍ ማጣቀሻዎች አሉ።

የ n እና m ምርጫ

በተግባር n እና m እንዴት መምረጥ ይቻላል? በተግባር, በመረጃ ማከማቻ ስርዓቶች ውስጥ, የድግግሞሽ ኮዶች ቦታን ለመቆጠብ ጥቅም ላይ ይውላሉ, ስለዚህ m ሁልጊዜ ከ n ያነሰ ይመረጣል. የእነሱ ትክክለኛ ዋጋ በብዙ ሁኔታዎች ላይ የተመሰረተ ነው, የሚከተሉትን ጨምሮ:

• የውሂብ ማከማቻ አስተማማኝነት. ትልቁ ሜትር, ሊተርፉ የሚችሉ የዲስክ ውድቀቶች ብዛት, ማለትም, አስተማማኝነት ከፍ ያለ ነው.
• ተደጋጋሚ ማከማቻ። የ m / n ጥምርታ ከፍ ባለ መጠን የማከማቻው ድግግሞሽ ከፍ ያለ ይሆናል, እና ስርዓቱ የበለጠ ውድ ይሆናል.
• የማስኬጃ ጊዜ ይጠይቁ። ድምር n + m በትልቁ፣ ለጥያቄዎች የምላሽ ጊዜ ይረዝማል። መረጃን ለማንበብ (በማገገሚያ ወቅት) በተለያዩ ዲስኮች ላይ የተከማቹ n ብሎኮችን ማንበብ ስለሚፈልግ የንባብ ጊዜ የሚወሰነው በጣም ቀርፋፋ በሆነው ዲስክ ነው።

በተጨማሪም, መረጃን በበርካታ ዲሲዎች ውስጥ ማከማቸት በ n እና m ምርጫ ላይ ተጨማሪ ገደቦችን ያስገድዳል: 1 ዲሲ ከጠፋ, ውሂቡ አሁንም ለማንበብ መገኘት አለበት. ለምሳሌ, በ 3 ዲሲዎች ውስጥ መረጃን በሚከማችበት ጊዜ, የሚከተለው ሁኔታ መሟላት አለበት: m >= n / 2, አለበለዚያ 1 ዲሲ ሲጠፋ መረጃው ለማንበብ የማይቻልበት ሁኔታ ሊኖር ይችላል.

3. LRC - የአካባቢ መልሶ ግንባታ ኮዶች

ሪድ-ሰለሞን ኮዶችን በመጠቀም መረጃን መልሶ ለማግኘት n የዘፈቀደ የውሂብ ብሎኮችን መጠቀም አለብዎት። ይህ ለተከፋፈሉ የመረጃ ማከማቻ ስርዓቶች በጣም ጉልህ ኪሳራ ነው ፣ ምክንያቱም በአንድ በተሰበረ ዲስክ ላይ መረጃን ወደነበረበት ለመመለስ ፣ የሌሎቹን አብዛኛዎቹን መረጃዎች ማንበብ አለብዎት ፣ ይህም በዲስኮች እና በአውታረ መረቡ ላይ ትልቅ ተጨማሪ ጭነት ይፈጥራል።

በጣም የተለመዱት ስህተቶች የአንድ ዲስክ ውድቀት ወይም ከመጠን በላይ በመጨመራቸው የአንድ ብሎክ ውሂብ ተደራሽ አለመሆን ናቸው። በዚህ (በጣም የተለመደ) ጉዳይ ለውሂብ መልሶ ማግኛ ትርፍ ጭነት በሆነ መንገድ መቀነስ ይቻላል? እርስዎ ማድረግ እንደሚችሉ ሆኖአል፡ በተለይ ለዚህ ዓላማ የLRC የመቀየሪያ ኮዶች አሉ።

LRC (አካባቢያዊ የመልሶ ግንባታ ኮዶች) በWindows Azure Storage ውስጥ ለመጠቀም በማይክሮሶፍት የተፈለሰፉ የድጋሚ ኮዶች ናቸው። የ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 blocks (n/2 በእኛ ምሳሌ) ማንበብ በቂ ነው.
• r + l ብሎኮች ከሌሉ እና ሁሉም ብሎኮች በአንድ ቡድን ውስጥ ከተካተቱ ውሂቡ ወደነበረበት ሊመለስ አይችልም። ይህንን በምሳሌ ለማስረዳት ቀላል ነው። ብሎኮች X1–X3 እና P3 አይገኙም፡ እነዚህ r + l ብሎኮች ከተመሳሳይ ቡድን ናቸው፣ በእኛ ሁኔታ 4። ከዚያ 3 እኩልታዎች ያሉት ከ 4 የማይታወቁ ነገሮች ጋር ሊፈታ የማይችል ስርዓት አለን.
• በሌሎች በሁሉም የ r + l ብሎኮች (ቢያንስ አንድ ብሎክ ከእያንዳንዱ ቡድን ሲገኝ) በLRC ውስጥ ያለው መረጃ ወደነበረበት ሊመለስ ይችላል።

ስለዚህ፣ LRC ከነጠላ ስህተቶች በኋላ መረጃን በማገገም የሪድ-ሰለሞን ኮዶችን ይበልጣል። በሪድ-ሰለሞን ኮዶች ውስጥ አንድ የውሂብ ብሎክ እንኳን መልሶ ለማግኘት n ብሎኮችን መጠቀም ያስፈልግዎታል ፣ እና በኤልአርሲ ውስጥ አንድ ብሎክ መረጃን ለማግኘት n / l ብሎኮችን (በእኛ ምሳሌ n / 2) መጠቀም በቂ ነው። በሌላ በኩል፣ ከፍተኛው ከሚፈቀዱ ስህተቶች ብዛት አንጻር LRC ከሪድ-ሰለሞን ኮዶች ያነሰ ነው። ከላይ ባሉት ምሳሌዎች የሪድ-ሰለሞን ኮዶች ለማንኛውም 4 ስህተቶች መረጃን መልሰው ማግኘት ይችላሉ ፣ እና ለ LRC ውሂቡ መመለስ በማይቻልበት ጊዜ 2 የ 4 ስህተቶች ጥምረት አለ።

ይበልጥ አስፈላጊ የሆነው በተወሰነው ሁኔታ ላይ የተመሰረተ ነው, ነገር ግን ብዙውን ጊዜ LRC የሚያቀርበው ከመጠን በላይ ሸክም ያለው ቁጠባ በትንሹ አስተማማኝ ከሆነው ማከማቻ ይበልጣል.

4. ሌሎች የመቀየሪያ ኮዶች

ከሪድ-ሰለሞን እና ኤልአርሲ ኮድ በተጨማሪ ሌሎች ብዙ የመቀየሪያ ኮዶች አሉ። የተለያዩ የድግግሞሽ ኮዶች የተለያዩ ሒሳቦችን ይጠቀማሉ። አንዳንድ ሌሎች የመቀየሪያ ኮዶች እነኚሁና፡

• የ XOR ኦፕሬተርን በመጠቀም የመድገም ኮድ። የXOR ክዋኔው የሚከናወነው በ n ዳታ ብሎኮች ላይ ነው፣ እና 1 የድግግሞሽ ኮዶች ተገኝቷል፣ ማለትም፣ n+1 እቅድ (n data blocks፣ 1 redundancy code)። ውስጥ ጥቅም ላይ ውሏል RAID 5, የውሂብ ብሎኮች እና የድግግሞሽ ኮድ ወደ ሁሉም የድርድር ዲስኮች በሳይክል የተፃፉበት።
• በXOR አሠራር ላይ የተመሰረተ ያልተለመደ ስልተ ቀመር። 2 ብሎኮች የድግግሞሽ ኮድ እንዲገነቡ ይፈቅድልዎታል፣ ማለትም፣ n+2 እቅድ።
• በXOR አሠራር ላይ የተመሰረተ STAR አልጎሪዝም። 3 ብሎኮች የድግግሞሽ ኮድ እንዲገነቡ ይፈቅድልዎታል፣ ማለትም፣ n+3 እቅድ።
• የፒራሚድ ኮዶች ከማይክሮሶፍት ሌላ የድጋሚ ኮዶች ናቸው።

5. በ Yandex ውስጥ ይጠቀሙ

በርካታ የ Yandex መሠረተ ልማት ፕሮጄክቶች አስተማማኝ የመረጃ ማከማቻ ኮዶችን ይጠቀማሉ። አንዳንድ ምሳሌዎች እነሆ፡-

• በአንቀጹ መጀመሪያ ላይ የጻፍኩትን MDS ውስጣዊ ነገር ማከማቻ።
• YT - የ Yandex ማፕ ቅነሳ ስርዓት።
• YDB (Yandex DataBase) - newSQL የተሰራጨ የውሂብ ጎታ.

ኤም.ዲ.ኤስ የLRC የድጋሚ ኮድ፣ 8-2-2 እቅድ ይጠቀማል። የድጋሚ ኮድ ያላቸው መረጃዎች በ 12 የተለያዩ ዲሲዎች ውስጥ በተለያዩ አገልጋዮች ውስጥ ወደ 3 የተለያዩ ዲስኮች ይፃፋሉ፡ በእያንዳንዱ ዲሲ ውስጥ 4 አገልጋዮች። ስለዚህ ጉዳይ በ ውስጥ የበለጠ ያንብቡ ጽሑፍ.

YT ሁለቱንም የሪድ-ሰለሞን ኮዶችን (መርሃግብር 6-3) ይጠቀማል፣ መጀመሪያ የተተገበሩትን እና የLRC የድጋሚ ኮድ (እቅድ 12-2-2)፣ LRC ተመራጭ የማከማቻ ዘዴ ነው።

YDB እኩል ያልሆኑ የተደጋገሙ ኮዶችን ይጠቀማል (ምስል 4-2)። አስቀድሞ በYDB ውስጥ ያሉ የመቀየሪያ ኮዶች ሃይሎድ ላይ ተነግሯል።.

የተለያዩ የድግግሞሽ ኮድ መርሃግብሮችን መጠቀም ለተለያዩ ስርዓቶች በተለያዩ መስፈርቶች ምክንያት ነው. ለምሳሌ፣ በኤምዲኤስ፣ LRCን በመጠቀም የተከማቸ መረጃ በአንድ ጊዜ በ3 ዲሲዎች ውስጥ ይቀመጣል። ከየትኛውም ዲሲዎች ውስጥ 1 ቱ ካልተሳካ መረጃው ለማንበብ መቆየቱ ለእኛ አስፈላጊ ነው፣ ስለዚህ ብሎኮች በዲሲዎች ውስጥ መሰራጨት አለባቸው ስለዚህ ማንኛውም ዲሲ የማይገኝ ከሆነ የማይደረስባቸው ብሎኮች ብዛት ከተፈቀደ በላይ አይደለም። በ 8-2-2 እቅድ ውስጥ በእያንዳንዱ ዲሲ ውስጥ 4 ብሎኮችን ማስቀመጥ ይችላሉ, ከዚያ ማንኛውም ዲሲ ሲጠፋ, 4 ብሎኮች አይገኙም እና መረጃው ሊነበብ ይችላል. በ 3 ዲሲዎች ውስጥ ስናስቀምጠው ምንም አይነት እቅድ ብንመርጥ, በማንኛውም ሁኔታ (r + l) / n>= 0,5 መሆን አለበት, ማለትም የማከማቻ ድግግሞሽ ቢያንስ 50% ይሆናል.

በ YT ውስጥ ሁኔታው ​​​​የተለየ ነው፡ እያንዳንዱ የYT ክላስተር ሙሉ በሙሉ በ1 ዲሲ ውስጥ (የተለያዩ ስብስቦች በተለያዩ ዲሲዎች) ውስጥ ይገኛሉ፣ ስለዚህ ምንም አይነት ገደብ የለም። የ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. የ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. በኤምዲኤስ ውስጥ የመቀየሪያ ኮዶች፡- 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

ምንጭ: hab.com