ဤအရာသည် ထပ်လောင်းဖြစ်ပုံရသည်။

Redundancy codes* သည် ဒေတာသိုလှောင်မှု၏ ယုံကြည်စိတ်ချရမှုကို တိုးမြှင့်ရန်အတွက် ကွန်ပျူတာစနစ်များတွင် တွင်ကျယ်စွာ အသုံးပြုပါသည်။ Yandex တွင် ၎င်းတို့ကို ပရောဂျက်များစွာတွင် အသုံးပြုကြသည်။ ဥပမာအားဖြင့်၊ ကျွန်ုပ်တို့၏အတွင်းပိုင်းအရာဝတ္ထုသိုလှောင်မှုတွင် ပုံတူပွားခြင်းအစား ထပ်လောင်းကုဒ်များကိုအသုံးပြုခြင်းသည် ယုံကြည်စိတ်ချရမှုကို မထိခိုက်စေဘဲ သန်းပေါင်းများစွာကို သက်သာစေသည်။ ကျယ်ကျယ်ပြန့်ပြန့် အသုံးပြုနေသော်လည်း ထပ်နေသောကုဒ်များ မည်သို့အလုပ်လုပ်ကြောင်း ရှင်းလင်းပြတ်သားစွာ ဖော်ပြချက်မှာ အလွန်ရှားပါသည်။ နားလည်လိုသူများသည် အောက်ပါအကြမ်းဖျင်းနှင့် ကြုံတွေ့ရတတ်ပါသည်။ ဝီကီပီးဒီးယား):

ကျွန်ုပ်၏အမည်မှာ Vadim ဖြစ်ပြီး၊ Yandex တွင် ကျွန်ုပ်သည် အတွင်းပိုင်းအရာဝတ္ထုသိုလှောင်မှု MDS ကို တီထွင်နေပါသည်။ ဤဆောင်းပါးတွင်၊ ထပ်နေသောကုဒ်များ (Reed-Solomon နှင့် LRC ကုဒ်များ) ၏ သီအိုရီအခြေခံအုတ်မြစ်များကို ရိုးရှင်းသောစကားလုံးများဖြင့် ဖော်ပြပါမည်။ ရှုပ်ထွေးတဲ့ သင်္ချာနဲ့ ရှားပါးတဲ့ အသုံးအနှုန်းတွေမပါဘဲ ဘယ်လိုအလုပ်လုပ်တယ်ဆိုတာကို ပြောပြမယ်။ အဆုံးတွင် Yandex တွင် redundancy codes များကိုအသုံးပြုခြင်း၏နမူနာများကိုပြောပြပါမည်။

သင်္ချာအသေးစိတ်အချက်များစွာကို ကျွန်ုပ်ထည့်သွင်းစဉ်းစားမည်မဟုတ်သော်လည်း ပိုမိုနက်ရှိုင်းသောငုပ်လျှိုးလိုသူများအတွက် လင့်ခ်များကို ဖော်ပြပေးပါမည်။ ဆောင်းပါးသည် သင်္ချာပညာရှင်များအတွက် မရည်ရွယ်သော်လည်း ပြဿနာ၏ အနှစ်သာရကို နားလည်လိုသော အင်ဂျင်နီယာများအတွက် ဖြစ်သောကြောင့် အချို့သော သင်္ချာဆိုင်ရာ အဓိပ္ပါယ်ဖွင့်ဆိုချက်များသည် တင်းကျပ်မည်မဟုတ်ကြောင်းကိုလည်း ကျွန်ုပ်သတိပြုမိပါသည်။

* အင်္ဂလိပ်ဘာသာစာပေတွင်၊ ထပ်နေသောကုဒ်များကို ဖျက်ပစ်ကုဒ်များဟု မကြာခဏခေါ်သည်။

1. ထပ်နေသောကုဒ်များ၏ အနှစ်သာရ

ထပ်နေသောကုဒ်များ အားလုံး၏ အနှစ်သာရမှာ အလွန်ရိုးရှင်းပါသည်- အမှားအယွင်းများ ဖြစ်ပေါ်လာသောအခါ (ဒစ်ခ်ချို့ယွင်းမှု၊ ဒေတာလွှဲပြောင်းမှု အမှားအယွင်းများ စသည်ဖြင့်) ဒေတာကို သိမ်းဆည်း (သို့မဟုတ်) ပို့လွှတ်ခြင်း)။

* redundancy codes အများစုတွင်၊ data ကို n data blocks များအဖြစ် ပိုင်းခြားထားပြီး m blocks of redundancy codes များကို ရေတွက်ပြီး စုစုပေါင်း n + m blocks များကို ဖြစ်ပေါ်စေပါသည်။ n + m ဘလောက်တစ်စိတ်တစ်ပိုင်းကိုသာ အသုံးပြု၍ ဒေတာဘလောက်များကို ပြန်လည်ရယူနိုင်သည့် နည်းလမ်းဖြင့် ထပ်နေသောကုဒ်များကို တည်ဆောက်ထားသည်။ ထို့နောက်၊ ကျွန်ုပ်တို့သည် block redundancy codes များကိုသာ စဉ်းစားပါမည်၊ ဆိုလိုသည်မှာ ဒေတာကို blocks များအဖြစ် ပိုင်းခြားထားသော၊

ဒေတာ n blocks အားလုံးကို ပြန်လည်ရယူရန်၊ သင့်တွင် n-1 တုံးသာရှိခြင်းဖြင့် n blocks များကို မရရှိနိုင်သောကြောင့် (ဤကိစ္စတွင်၊ သင်သည် ပါးလွှာသော 1 blocks ကို ယူရမည်ဖြစ်ပါသည်။ လေ")။ n ကျပန်းလုပ်ကွက် n + m တုံးများသည် ဒေတာအားလုံးကို ပြန်လည်ရယူရန် လုံလောက်ပါသလား။ ၎င်းသည် ထပ်နေသောကုဒ်အမျိုးအစားများပေါ်တွင်မူတည်သည်၊ ဥပမာ၊ Reed-Solomon ကုဒ်များသည် သင့်အား arbitrary n blocks များအသုံးပြု၍ ဒေတာအားလုံးကို ပြန်လည်ရယူခွင့်ပြုသော်လည်း LRC ထပ်နေသောကုဒ်များသည် အမြဲတမ်းမရှိပါ။

ဒေတာသိုလှောင်မှု

ဒေတာသိုလှောင်မှုစနစ်များတွင် စည်းကမ်းအတိုင်း၊ ဒေတာပိတ်ဆို့ခြင်းနှင့် ထပ်နေသောကုဒ်တုံးတစ်ခုစီကို သီးခြားဒစ်တစ်ခုသို့ ရေးမှတ်ထားသည်။ ထို့နောက်၊ မထင်သလိုဒစ်တစ်ခု ပျက်ကွက်ပါက၊ မူရင်းဒေတာကို ပြန်လည်ရယူပြီး ဖတ်နိုင်သေးသည်။ တစ်ချိန်တည်းမှာ ဒစ်အများအပြား ပျက်သွားရင်တောင် ဒေတာကို ပြန်လည်ရယူနိုင်ပါတယ်။

ဒေတာလွှဲပြောင်းခြင်း

အားကိုးမရသော ကွန်ရက်တစ်ခုမှ ဒေတာများကို ယုံကြည်စိတ်ချစွာ ပေးပို့ရန်အတွက် ထပ်နေသောကုဒ်များကို အသုံးပြုနိုင်သည်။ ပို့လွှတ်သောဒေတာကို ဘလောက်များအဖြစ် ပိုင်းခြားထားပြီး ၎င်းတို့အတွက် ထပ်နေသောကုဒ်များကို တွက်ချက်ပါသည်။ ဒေတာဘလောက်များနှင့် ထပ်နေသောကုဒ်တုံးများ နှစ်ခုလုံးကို ကွန်ရက်ပေါ်တွင် ပို့လွှတ်ပါသည်။ မှားယွင်းသောဘလောက်များတွင် အမှားအယွင်းများဖြစ်ပေါ်ပါက (အချို့သောလုပ်ကွက်အရေအတွက်အထိ)၊ ဒေတာများကို အမှားအယွင်းမရှိဘဲ ကွန်ရက်မှတဆင့် ပေးပို့နိုင်သေးသည်။ ဥပမာအားဖြင့် Reed-Solomon ကုဒ်များကို optical ဆက်သွယ်ရေးလိုင်းများနှင့် ဂြိုလ်တုဆက်သွယ်ရေးများတွင် ဒေတာပေးပို့ရန် အသုံးပြုသည်။

* Ethernet ကွန်ရက်များတွင် ဒေတာပေးပို့ခြင်းအတွက် တွင်ကျယ်စွာအသုံးပြုသည့် Hamming ကုဒ်များနှင့် CRC ကုဒ်များကဲ့သို့သော ဒေတာများကို အတုံးများအဖြစ် ပိုင်းခြားမထားသော ထပ်နေသောကုဒ်များလည်း ရှိပါသည်။ ၎င်းတို့သည် အမှားပြင်ဆင်ခြင်းအတွက် ကုဒ်များဖြစ်သည်၊ ၎င်းတို့သည် အမှားများကို ရှာဖွေတွေ့ရှိရန် နှင့် ၎င်းတို့ကို ပြင်ရန် ဒီဇိုင်းထုတ်ထားခြင်းဖြစ်သည် ( Hamming ကုဒ်သည် အမှားအယွင်းများကို တစ်စိတ်တစ်ပိုင်းတည်းဖြတ်ခြင်းကိုလည်း ခွင့်ပြုသည်)။

2. ရိဒ်-ရှောလမုန်ကုဒ်များ

Reed-Solomon ကုဒ်များသည် 1960 ခုနှစ်များအတွင်း တီထွင်ခဲ့သော အသုံးများဆုံး redundancy codes များထဲမှ တစ်ခုဖြစ်ပြီး compact disc များ အမြောက်အမြား ထုတ်လုပ်ရန်အတွက် 1980s တွင် ပထမဆုံး အသုံးများပါသည်။

Reed-Solomon ကုဒ်များကို နားလည်ရန်အတွက် အဓိကမေးခွန်းနှစ်ခုရှိပါသည်။ 1) redundancy ကုဒ်တုံးများကို အသုံးပြု၍ ဒေတာများ ပြန်လည်ရယူနည်း။ သူတို့အတွက် အဖြေရှာကြရအောင်။
ရိုးရိုးရှင်းရှင်းပြောရရင် n=6 နဲ့ m=4 လို့ ထပ်လောင်းယူဆပါမယ်။ အခြားအစီအစဥ်များကို ယှဉ်တွဲ၍ စဉ်းစားသည်။

ထပ်နေသောကုဒ်တုံးများကို ဖန်တီးနည်း

ထပ်နေသောကုဒ်များ၏ ဘလောက်တစ်ခုစီကို အခြားအရာများနှင့် သီးခြားရေတွက်သည်။ ဘလောက်တစ်ခုစီကို ရေတွက်ရန် n data blocks အားလုံးကို အသုံးပြုပါသည်။ အောက်ဖော်ပြပါပုံတွင်၊ X1-X6 သည် ဒေတာဘလောက်များဖြစ်ပြီး P1-P4 သည် ထပ်နေသောကုဒ်တုံးများဖြစ်သည်။

ဒေတာဘလောက်များအားလုံးသည် အရွယ်အစားတူညီရမည်ဖြစ်ပြီး ချိန်ညှိမှုတွင် သုညဘစ်များကို အသုံးပြုနိုင်သည်။ ရလဒ်ထပ်နေသော ကုဒ်တုံးများသည် ဒေတာဘလောက်များကဲ့သို့ အရွယ်အစားတူညီပါမည်။ ဒေတာပိတ်ဆို့ခြင်းအားလုံးကို စကားလုံးများအဖြစ် ပိုင်းခြားထားသည် (ဥပမာ၊ 16 bits)။ ဒေတာဘလောက်များကို k စကားလုံးများဖြင့် ခွဲထားသည်ဆိုပါစို့။ ထို့နောက် ထပ်နေသောကုဒ်တုံးအားလုံးကို k စကားလုံးများအဖြစ် ပိုင်းခြားပါမည်။

redundancy block တစ်ခုစီ၏ i-th စကားလုံးကို ရေတွက်ရန်၊ data blocks အားလုံး၏ i-th စကားလုံးများကို အသုံးပြုပါမည်။ ၎င်းတို့ကို အောက်ပါပုံသေနည်းအတိုင်း တွက်ချက်မည်ဖြစ်သည်။

ဤနေရာတွင် x တန်ဖိုးများသည် ဒေတာဘလောက်များ၏ စကားလုံးများဖြစ်သည်၊ p သည် ထပ်နေသောကုဒ်တုံးများ၏ စကားလုံးများဖြစ်သည်၊ alpha၊ beta၊ gamma နှင့် delta အားလုံးသည် i အားလုံးအတွက် တူညီသော အထူးရွေးချယ်ထားသော နံပါတ်များဖြစ်သည်။ ဤတန်ဖိုးများအားလုံးသည် သာမန်နံပါတ်များမဟုတ်သော်လည်း Galois အကွက်၏ဒြပ်စင်များ ၊ လည်ပတ်မှုများ +၊ -၊ *၊ / လုပ်ဆောင်ချက်များသည် ကျွန်ုပ်တို့အားလုံးနှင့်ရင်းနှီးသည်မဟုတ်သော်လည်း Galois ၏ဒြပ်စင်များတွင် မိတ်ဆက်ထားသော အထူးလုပ်ဆောင်မှုများ၊ လယ်ကွင်း။

Galois နယ်ပယ်များသည် အဘယ်ကြောင့် လိုအပ်သနည်း။

အရာအားလုံးရိုးရှင်းပုံရသည်- ကျွန်ုပ်တို့သည် data များကို blocks များအဖြစ်ခွဲကာ၊ blocks များကိုစကားလုံးများအဖြစ်ကျွန်ုပ်တို့သည် redundancy code blocks ၏စကားလုံးများကိုရေတွက်ကြသည် - ငါတို့သည် redundancy code blocks များကိုရရှိသည်။ ယေဘူယျအားဖြင့် ၎င်းသည် မည်သို့အလုပ်လုပ်သည်၊ သို့သော် မာရ်နတ်သည် အသေးစိတ်အချက်များထဲတွင် ရှိနေသည်-

1. အထက်တွင်ဖော်ပြထားသည့်အတိုင်း၊ ကျွန်ုပ်တို့၏ဥပမာ 16 bits တွင် စကားလုံးအရွယ်အစားကို ပုံသေသတ်မှတ်ထားသည်။ Reed-Solomon ကုဒ်များအတွက် အထက်ဖော်ပြပါ ဖော်မြူလာများသည် သာမန် ကိန်းပြည့်များကို အသုံးပြုသည့်အခါ p တွက်ချက်ခြင်း၏ ရလဒ်သည် မှန်ကန်သော အရွယ်အစား စကားလုံးကို အသုံးပြု၍ ကိုယ်စားပြုနိုင်မည်မဟုတ်ပေ။
2. ဒေတာကို ပြန်လည်ရယူသည့်အခါ၊ အထက်ဖော်ပြပါ ဖော်မြူလာများသည် ဒေတာကို ပြန်လည်ရယူရန်အတွက် ဖြေရှင်းရမည့် ညီမျှခြင်းစနစ်တစ်ခုအဖြစ် သတ်မှတ်မည်ဖြစ်သည်။ ဖြေရှင်းချက်လုပ်ငန်းစဉ်အတွင်း၊ ကိန်းပြည့်များကို တစ်ခုနှင့်တစ်ခု ပိုင်းခြားရန် လိုအပ်ပြီး ကွန်ပျူတာမှတ်ဉာဏ်တွင် တိကျစွာကိုယ်စားပြုမရနိုင်သော အစစ်အမှန်အရေအတွက်ကို ဖြစ်ပေါ်စေပါသည်။

ဤပြဿနာများသည် Reed-Solomon ကုဒ်များအတွက် ကိန်းပြည့်များအသုံးပြုခြင်းကို ဟန့်တားသည်။ ပြဿနာ၏ဖြေရှင်းချက်သည် မူရင်းဖြစ်သည်၊ အောက်ပါအတိုင်း ဖော်ပြနိုင်သည်- လိုအပ်သော အရှည် (ဥပမာ၊ 16 bits) စကားလုံးများကို အသုံးပြု၍ ကိုယ်စားပြုနိုင်သည့် အထူးနံပါတ်များနှင့် လုပ်ဆောင်ချက်အားလုံးကို လုပ်ဆောင်ခြင်း၏ ရလဒ် (ထို့အပြင်၊ ၊ အနုတ် ၊ အမြှောက် ၊ ကိန်း ) ကိုလည်း လိုအပ်သော အရှည် စကားလုံးများကို အသုံးပြု၍ ကွန်ပျူတာမှတ်ဉာဏ်တွင် တင်ပြပါမည်။

ထိုကဲ့သို့သော "အထူး" ဂဏန်းများကို သင်္ချာပညာဖြင့် အချိန်အတော်ကြာ လေ့လာခဲ့ပြီး ၎င်းတို့ကို နယ်ပယ်များဟုခေါ်သည်။ အကွက်တစ်ခုသည် ၎င်းတို့အတွက် သတ်မှတ်ထားသော ပေါင်းခြင်း၊ နုတ်ခြင်း၊ မြှောက်ခြင်း နှင့် ပိုင်းခြားခြင်းဆိုင်ရာ လုပ်ဆောင်ချက်များပါရှိသော ဒြပ်စင်အစုတစ်ခုဖြစ်သည်။

Galois* အကွက်များသည် လုပ်ဆောင်ချက်တစ်ခုစီ၏ ထူးခြားသောရလဒ် (+, -, *, /) အကွက်များ၏ မည်သည့်ဒြပ်စင်နှစ်ခုအတွက်မဆို နယ်ပယ်များဖြစ်သည်။ Galois အကွက်များကို 2:2၊ 4၊ 8၊ 16 စသည်ဖြင့် ပါဝါရှိသော ဂဏန်းများအတွက် တည်ဆောက်နိုင်သည် (တကယ်တော့ မည်သည့် prime number p ၏ ပါဝါများဖြစ်သည်၊ သို့သော် လက်တွေ့တွင် ကျွန်ုပ်တို့သည် 2 ၏စွမ်းအားများကိုသာ စိတ်ဝင်စားသည်)။ ဥပမာအားဖြင့်၊ 16-bit စကားလုံးများအတွက်၊ ဤသည် 65 ဒြပ်စင်များပါ ၀ င်သောအကွက်တစ်ခုဖြစ်ပြီး၊ တစ်စုံတစ်ခုစီအတွက်မည်သည့်လုပ်ဆောင်ချက် (+၊ -၊ *၊ /) ကိုမဆိုရှာဖွေနိုင်သည်။ အထက်ပါညီမျှခြင်းများမှ x၊ p၊ alpha၊ beta၊ gamma၊ delta တန်ဖိုးများကို တွက်ချက်ရန်အတွက် Galois အကွက်၏ အစိတ်အပိုင်းများကို ထည့်သွင်းစဉ်းစားမည်ဖြစ်သည်။

ထို့ကြောင့်၊ သင့်လျော်သောကွန်ပျူတာပရိုဂရမ်တစ်ခုရေးသားခြင်းဖြင့် ကျွန်ုပ်တို့တွင် ထပ်နေသောကုဒ်တုံးများကို တည်ဆောက်နိုင်သည့် ညီမျှခြင်းစနစ်တစ်ခုရှိသည်။ ညီမျှခြင်းစနစ်တစ်ခုတည်းကို အသုံးပြု၍ သင်သည် ဒေတာပြန်လည်ရယူခြင်းကို လုပ်ဆောင်နိုင်သည်။

* ဤသည်မှာ တင်းကျပ်သော အဓိပ္ပါယ်မဟုတ်သော်လည်း ဖော်ပြချက်သာဖြစ်သည်။

ဒေတာဆယ်တင်နည်း

n + m ဘလောက်အချို့ ပျောက်ဆုံးနေချိန်တွင် ပြန်လည်ထူထောင်ရန် လိုအပ်သည်။ ၎င်းတို့သည် ဒေတာဘလောက်များနှင့် ထပ်နေသောကုဒ်တုံးများ နှစ်မျိုးလုံး ဖြစ်နိုင်သည်။ ဒေတာဘလောက်များနှင့်/သို့မဟုတ် ထပ်နေသောကုဒ်တုံးများ မရှိခြင်းသည် အထက်ဖော်ပြပါ ညီမျှခြင်းများတွင် သက်ဆိုင်ရာ x နှင့်/သို့မဟုတ် p variable များကို မသိနိုင်ဟု ဆိုလိုပါသည်။

Reed-Solomon ကုဒ်များအတွက် ညီမျှခြင်းများကို အယ်လ်ဖာ၊ ဘီတာ၊ ဂမ်မာ၊ မြစ်ဝကျွန်းပေါ်ရှိ တန်ဖိုးများသည် ကိန်းသေများ၊ ရရှိနိုင်သော ဘလောက်များနှင့် သက်ဆိုင်သော x နှင့် p အားလုံးကို ကိန်းရှင်များအဖြစ် သိရှိနိုင်ပြီး ကျန် x နှင့် p တို့ကို ညီမျှခြင်းစနစ်တစ်ခုအဖြစ် ရှုမြင်နိုင်ပါသည်။ မသိ။

ဥပမာအားဖြင့်၊ data blocks 1၊ 2၊ 3 နှင့် redundancy code block 2 ကို မရနိုင်ပါ၊ ထို့နောက် i-th စကားလုံးအုပ်စုအတွက် အောက်ပါညီမျှခြင်းစနစ်ရှိပါမည် (အမည်မသိများကို အနီရောင်ဖြင့် မှတ်သားထားသည်)။

ကျွန်ုပ်တို့တွင် အမည်မသိ 4 ခုပါသော ညီမျှခြင်း 4 ခုရှိသော စနစ်တစ်ခုရှိသည်၊ ဆိုလိုသည်မှာ ၎င်းကို ဖြေရှင်းနိုင်ပြီး ဒေတာကို ပြန်လည်ရယူနိုင်သည်။

ဤညီမျှခြင်းစနစ်မှ Reed-Solomon ကုဒ်များ (n data blocks၊ m redundancy code blocks) များအတွက် ဒေတာပြန်လည်ရယူခြင်းအကြောင်း ကောက်ချက်များစွာ ကောက်ချက်ချသည်-

• m blocks သို့မဟုတ် အနည်းငယ်သာ ဆုံးရှုံးသွားပါက ဒေတာကို ပြန်လည်ရယူနိုင်ပါသည်။ m+1 သို့မဟုတ် ထို့ထက်ပိုသော blocks များ ပျောက်ဆုံးသွားပါက ဒေတာကို ပြန်လည်ရယူနိုင်မည်မဟုတ်ပါ- m ညီမျှခြင်းစနစ်အား m+1 အမည်မသိများဖြင့် ဖြေရှင်းရန် မဖြစ်နိုင်ပါ။
• ဒေတာဘလောက်တစ်ခုပင်ကို ပြန်လည်ရယူရန်၊ သင်သည် ကျန်ရှိသော ဘလောက်များထဲမှ n ကိုအသုံးပြုရန် လိုအပ်ပြီး ထပ်နေသောကုဒ်များကိုမဆို အသုံးပြုနိုင်ပါသည်။

တခြားဘာသိဖို့ လိုသေးလဲ။

အထက်ဖော်ပြပါ ဖော်ပြချက်တွင်၊ စဉ်းစားရန် သင်္ချာတွင် ပိုမိုနက်ရှိုင်းစွာ ထိုးနှက်ရန် လိုအပ်သည့် အရေးကြီးသော ကိစ္စရပ်များကို ကျွန်ုပ် ရှောင်ကြဉ်ပါသည်။ အထူးသဖြင့်၊ ကျွန်ုပ်သည် အောက်ပါ အကြောင်းများကို ဘာမှ မပြောပါ ။

• Reed-Solomon ကုဒ်များအတွက် ညီမျှခြင်းစနစ်တွင် အမည်မသိများ ပေါင်းစပ်မှု (m ထက်မပို) အတွက် (ထူးခြားသော) အဖြေတစ်ခု ရှိရပါမည်။ ဤလိုအပ်ချက်အပေါ်အခြေခံ၍ အယ်လ်ဖာ၊ ဘီတာ၊ ဂမ်မာနှင့် မြစ်ဝကျွန်းပေါ်ဒေသတို့၏ တန်ဖိုးများကို ရွေးချယ်ထားသည်။
• ညီမျှခြင်းစနစ်တစ်ခုသည် အလိုအလျောက်တည်ဆောက်နိုင်ရမည် (မည်သည့်ဘလောက်များမရရှိနိုင်သည့်အပေါ်မူတည်၍) နှင့် ဖြေရှင်းနိုင်ရမည်။
• Galois အကွက်တစ်ခုတည်ဆောက်ရန်လိုအပ်သည်- ပေးထားသောစကားလုံးအရွယ်အစားအတွက်၊ မည်သည့်ဒြပ်စင်နှစ်ခုအတွက်မဆို (+, -, *, /) ကိုရှာဖွေနိုင်မည်ဖြစ်သည်။

ဆောင်းပါး၏အဆုံးတွင် ဤအရေးကြီးသောကိစ္စရပ်များနှင့်ပတ်သက်သော စာပေကိုးကားချက်များရှိသည်။

n နှင့် m ရွေးချယ်မှု

လက်တွေ့မှာ n နဲ့ m ကို ဘယ်လိုရွေးချယ်မလဲ။ လက်တွေ့တွင်၊ ဒေတာသိမ်းဆည်းမှုစနစ်များတွင် နေရာလွတ်များချွေတာရန်အတွက် ထပ်နေသောကုဒ်များကို အသုံးပြုထားသောကြောင့် m ကို အမြဲတမ်း n ထက်နည်းအောင် ရွေးချယ်ထားသည်။ ၎င်းတို့၏ တိကျသောတန်ဖိုးများသည် အပါအဝင်အချက်များစွာပေါ်တွင်မူတည်သည်-

• ဒေတာသိုလှောင်မှု၏ယုံကြည်စိတ်ချရ။ ပိုကြီးလေ၊ ရှင်သန်နိုင်သော disk ပျက်ကွက်အရေအတွက် ပိုများလေ၊ ဆိုလိုသည်မှာ၊ ယုံကြည်နိုင်မှု မြင့်မားလေဖြစ်သည်။
• မလိုအပ်တော့သော သိုလှောင်မှု။ m/n အချိုး ပိုမြင့်လေ၊ သိုလှောင်မှု ထပ်နေနိုင်မှု ပိုများလေလေ၊ စနစ်က ပိုစျေးကြီးလေ ဖြစ်လိမ့်မည်။
• လုပ်ဆောင်ချိန်ကို တောင်းဆိုပါ။ ပေါင်းလဒ် n + m ကြီးလေ၊ တောင်းဆိုချက်များအတွက် တုံ့ပြန်ချိန်ပိုကြာလေဖြစ်သည်။ ဒေတာကိုဖတ်ရှုခြင်း (ပြန်လည်ရယူစဉ်အတွင်း) ကွဲပြားသောဒစ်များတွင်သိမ်းဆည်းထားသည့် n ဘလောက်များကိုဖတ်ရန် လိုအပ်သောကြောင့် စာဖတ်ချိန်ကို အနှေးဆုံးဒစ်က သတ်မှတ်ပေးမည်ဖြစ်သည်။

ထို့အပြင်၊ DC အများအပြားတွင် ဒေတာသိမ်းဆည်းခြင်းသည် n နှင့် m ရွေးချယ်မှုအပေါ် ထပ်လောင်းကန့်သတ်ချက်များ ချမှတ်ထားပါသည်- 1 DC ကိုပိတ်ထားပါက၊ ဒေတာကို ဆက်လက်ဖတ်ရှုနိုင်ရပါမည်။ ဥပမာအားဖြင့်၊ 3 DC တွင် ဒေတာကို သိမ်းဆည်းသောအခါတွင်၊ အောက်ပါအခြေအနေနှင့် ကိုက်ညီရမည်- m >= n/2၊ သို့မဟုတ်ပါက 1 DC ကိုပိတ်ထားသောအခါတွင် ဒေတာဖတ်ရန် မရနိုင်သည့် အခြေအနေမျိုးရှိနိုင်သည်။

3. LRC - Local Reconstruction Codes

Reed-Solomon ကုဒ်များကို အသုံးပြု၍ ဒေတာပြန်လည်ရယူရန်၊ သင်သည် n arbitrary data blocks ကို အသုံးပြုရပါမည်။ ကျိုးပဲ့နေသောဒစ်တစ်ခုပေါ်တွင်ဒေတာကိုပြန်လည်ရယူရန်၊ ဖြန့်ဝေထားသောဒေတာသိမ်းဆည်းမှုစနစ်များအတွက်အလွန်သိသာထင်ရှားသောအားနည်းချက်တစ်ခုဖြစ်သည်၊ အကြောင်းမှာ၊ သင်သည်အခြားအများစုထံမှဒေတာများကိုဖတ်ရှုရန်၊ disks နှင့် network တွင်ကြီးမားသောအပိုဆောင်းဝန်ကိုဖန်တီးနိုင်သောကြောင့်ဖြစ်သည်။

အဖြစ်များဆုံး အမှားများသည် ဒစ်တစ်ခု၏ ချို့ယွင်းချက် သို့မဟုတ် ဒစ်တစ်ခု၏ ဝန်ပိုခြင်းကြောင့် ဒေတာဘလောက်တစ်ခု၏ လက်လှမ်းမမီနိုင်မှုဖြစ်သည်။ ဤ (အသုံးအများဆုံး) ကိစ္စတွင် ဒေတာပြန်လည်ရယူခြင်းအတွက် ပိုလျှံနေသောဝန်ကို တစ်နည်းနည်းဖြင့် လျှော့ချရန် ဖြစ်နိုင်ပါသလား။ သင်လုပ်နိုင်သည်မှာ- ဤရည်ရွယ်ချက်အတွက် အထူးသီးသန့် LRC ထပ်နေသောကုဒ်များရှိပါသည်။

LRC (Local Reconstruction Codes) များသည် Windows Azure Storage တွင် အသုံးပြုရန်အတွက် Microsoft မှ တီထွင်ခဲ့သော ထပ်လောင်းကုဒ်များဖြစ်သည်။ LRC ၏ စိတ်ကူးသည် တတ်နိုင်သမျှ ရိုးရှင်းသည်- ဒေတာပိတ်ဆို့ခြင်းအားလုံးကို အုပ်စုနှစ်စု (သို့မဟုတ် ထို့ထက်ပို၍) ခွဲကာ အုပ်စုတစ်ခုစီအတွက် ထပ်နေသောကုဒ်တုံးများ၏ တစ်စိတ်တစ်ပိုင်းကို သီးခြားစီဖတ်ပါ။ ထို့နောက် အချို့သော redundancy code blocks များကို data blocks များအားလုံးကို အသုံးပြုပြီး (LRC တွင် ၎င်းတို့ကို global redundancy codes များဟု ခေါ်သည်) နှင့် အချို့သည် - data blocks အုပ်စုနှစ်စုအနက်မှ တစ်ခုကို အသုံးပြုသည် (၎င်းတို့ကို local redundancy codes ဟုခေါ်သည်)။

LRC ကို နံပါတ်သုံးလုံးဖြင့် ရည်ညွှန်းသည်- nrl ၊ n သည် ဒေတာဘလောက်များ၏ အရေအတွက်ဖြစ်ပြီး r သည် ကမ္ဘာလုံးဆိုင်ရာ ထပ်နေသော ကုဒ်တုံးများ၏ အရေအတွက်ဖြစ်ပြီး l သည် ဒေသတွင်း ထပ်နေသော ကုဒ်တုံးများ၏ အရေအတွက်ဖြစ်သည်။ ဒေတာဘလောက်တစ်ခုမှ မရရှိနိုင်သောအခါ ဒေတာကိုဖတ်ရန်၊ သင်သည် N/l ဘလောက်များကိုသာ ဖတ်ရန် လိုအပ်သည် - ၎င်းသည် Reed-Solomon ကုဒ်များထက် အဆလျော့နည်းသည်။

ဥပမာ၊ LRC 6-2-2 အစီအစဉ်ကို စဉ်းစားပါ။ X1–X6 — ဒေတာဘလောက် 6 ခု၊ P1၊ P2 — ကမ္ဘာလုံးဆိုင်ရာ ထပ်နေသောလုပ်ကွက် 2 ခု၊ P3၊ P4 — ဒေသတွင်း ထပ်နေသောလုပ်ကွက် 2 ခု။

Redundancy code blocks P1၊ P2 သည် data blocks အားလုံးကို အသုံးပြုပြီး ရေတွက်ပါသည်။ Redundancy code block P3 - data blocks X1-X3 ကိုအသုံးပြုပြီး၊ redundancy code block P4 - data blocks X4-X6 ကိုအသုံးပြုခြင်း။

ကျန်တာတွေကို Reed-Solomon ကုဒ်တွေနဲ့ ယှဉ်ပြီး LRC မှာ လုပ်ဆောင်ပါတယ်။ ထပ်နေသောကုဒ်တုံးများ၏ စကားလုံးများကို ရေတွက်ခြင်းအတွက် ညီမျှခြင်းများသည်-

နံပါတ်များ alpha၊ beta၊ gamma၊ delta ကိုရွေးချယ်ရန်၊ data recovery ၏ဖြစ်နိုင်ခြေကိုအာမခံရန် (ဆိုလိုသည်မှာ ညီမျှခြင်းစနစ်ဖြေရှင်းခြင်း) ကိုအာမခံရန် အခြေအနေများစွာကို ပြည့်မီရပါမည်။ ၎င်းတို့အကြောင်း ပိုမိုဖတ်ရှုနိုင်ပါသည်။ ဆောင်းပါး.
လက်တွေ့တွင်၊ 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 ကုဒ်များကို စွမ်းဆောင်ရည်ထက် သာလွန်စေသည်။ Reed-Solomon ကုဒ်များတွင် ဒေတာတစ်တုံးကိုပင် ပြန်လည်ရယူရန်၊ သင်သည် n blocks များကို အသုံးပြုရန်နှင့် LRC တွင် ဒေတာတစ်တုံးကို ပြန်လည်ရယူရန် လိုအပ်သည်၊ ၎င်းသည် n/l blocks (ကျွန်ုပ်တို့၏ ဥပမာတွင် n/2) ကို အသုံးပြုရန် လုံလောက်ပါသည်။ အခြားတစ်ဖက်တွင်၊ LRC သည် ခွင့်ပြုနိုင်သော အမှားအယွင်းများ အများဆုံးအရေအတွက်အရ Reed-Solomon ကုဒ်များထက် နိမ့်သည်။ အထက်ဖော်ပြပါနမူနာများတွင် Reed-Solomon ကုဒ်များသည် မည်သည့်အမှားအယွင်း 4 ခုအတွက်မဆို ဒေတာကို ပြန်လည်ရယူနိုင်ပြီး LRC အတွက် ဒေတာပြန်လည်ရယူ၍မရသည့်အခါ အမှားပေါင်း 2 ခုရှိသည်။

ပိုအရေးကြီးတာက တိကျတဲ့အခြေအနေပေါ်မှာမူတည်ပါတယ်၊ ဒါပေမယ့် LRC ပေးဆောင်တဲ့ ပိုလျှံတဲ့ဝန်ထုပ်ဝန်ပိုးဟာ မကြာခဏဆိုသလို ယုံကြည်စိတ်ချရမှုနည်းပါးတဲ့ သိုလှောင်မှုထက် သာလွန်ပါတယ်။

4. အခြား ထပ်နေသော ကုဒ်များ

Reed-Solomon နှင့် LRC ကုဒ်များအပြင် အခြားသော ထပ်နေသော ကုဒ်များစွာလည်း ရှိသေးသည်။ မတူညီသော ထပ်နေသောကုဒ်များသည် မတူညီသောသင်္ချာကို အသုံးပြုသည်။ ဤသည်မှာ အခြားသော ထပ်နေသော ကုဒ်အချို့ ဖြစ်သည်-

• XOR အော်ပရေတာကို အသုံးပြု၍ ထပ်နေသောကုဒ်။ XOR လုပ်ဆောင်ချက်ကို n data blocks တွင်လုပ်ဆောင်ပြီး 1 block of redundancy codes ကိုရရှိပါသည်၊ ဆိုလိုသည်မှာ n+1 scheme (n data blocks၊ 1 redundancy code) ကိုရရှိသည်။ တွင်အသုံးပြုသည်။ RAID 5ဒေတာဘလောက်များနှင့် ထပ်နေသောကုဒ်များကို array ၏ဒစ်များအားလုံးတွင် စက်ဝိုင်းပုံစံဖြင့်ရေးထားသည့်နေရာတွင်၊
• XOR လုပ်ဆောင်ချက်ကို အခြေခံ၍ ထူးဆန်းသော အယ်လဂိုရီသမ်။ n+2 အစီအစဥ်၊ ဆိုလိုသည်မှာ redundancy codes တုံး 2 ခုကို တည်ဆောက်ခွင့်ပြုသည်။
• XOR လုပ်ဆောင်ချက်အပေါ် အခြေခံ၍ STAR အယ်လဂိုရီသမ်။ n+3 အစီအစဥ်၊ ဆိုလိုသည်မှာ redundancy codes 3 ခုကို တည်ဆောက်ခွင့်ပြုသည်။
• Pyramide ကုဒ်များသည် Microsoft မှ နောက်ထပ် ထပ်နေသော ကုဒ်များဖြစ်သည်။

5. Yandex တွင်အသုံးပြုပါ။

Yandex အခြေခံအဆောက်အအုံ ပရောဂျက်များစွာသည် ယုံကြည်စိတ်ချရသော ဒေတာသိုလှောင်မှုအတွက် ထပ်နေသောကုဒ်များကို အသုံးပြုပါသည်။ ဤသည်မှာ ဥပမာအချို့ဖြစ်သည်။

• ဆောင်းပါးအစမှာ ကျွန်တော်ရေးခဲ့တဲ့ MDS အတွင်းပိုင်းအရာဝတ္ထုသိုလှောင်မှု။
• YT - Yandex ၏ MapReduce စနစ်။
• YDB (Yandex DataBase) - newSQL ဖြန့်ဝေဒေတာဘေ့စ်။

MDS သည် LRC ထပ်နေသောကုဒ်များ၊ 8-2-2 အစီအစဉ်ကို အသုံးပြုသည်။ ထပ်နေသောကုဒ်များဖြင့် ဒေတာကို မတူညီသော DC 12 ခုတွင် မတူညီသော ဆာဗာများတွင် မတူညီသော ဆာဗာ 3 ခုတွင် ရေးသားထားသည်- DC တစ်ခုစီရှိ ဆာဗာ 4 ခု။ ဤအကြောင်းပိုမိုဖတ်ရှုပါ။ ဆောင်းပါး.

YT သည် ပထမဆုံး အကောင်အထည်ဖော်ခဲ့သည့် Reed-Solomon ကုဒ်များ (Scheme 6-3) နှင့် LRC ထပ်နေသောကုဒ်များ (Scheme 12-2-2) ကို အသုံးပြုပြီး LRC သည် ဦးစားပေးသိုလှောင်မှုနည်းလမ်းဖြစ်သည်။

YDB သည် ထူးထူးခြားခြား အခြေခံ ထပ်နေသော ကုဒ်များကို အသုံးပြုသည် (ပုံ 4-2)။ YDB တွင် redundancy codes များအကြောင်း ရှိပြီးသားဖြစ်သည်။ Highload မှာ ပြောထားပါတယ်။.

မတူညီသော redundancy code schemes ကိုအသုံးပြုခြင်းသည် စနစ်များအတွက် မတူညီသောလိုအပ်ချက်များကြောင့်ဖြစ်သည်။ ဥပမာအားဖြင့်၊ MDS တွင် LRC ကို အသုံးပြု၍ သိမ်းဆည်းထားသော ဒေတာကို DC 3 ခုတွင် တစ်ပြိုင်နက် ထည့်သွင်းထားသည်။ DC တစ်ခုခုမှ 1 ခု ပျက်ကွက်ပါက ဒေတာကို ဆက်လက်ဖတ်ရှုရန် အရေးကြီးပါသည်၊ ထို့ကြောင့် DC များကြားတွင် ဘလောက်များကို ဖြန့်ဝေရမည်ဖြစ်သောကြောင့် မည်သည့် DC မဆို မရရှိနိုင်ပါက၊ လက်လှမ်းမမီသော ဘလောက်အရေအတွက်သည် ခွင့်ပြုထားသည်ထက် မပိုစေရပါ။ 8-2-2 အစီအစဥ်တွင် သင်သည် DC တစ်ခုစီတွင် အကွက် 4 ခု ထားရှိနိုင်ပြီး၊ ထို့နောက် မည်သည့် DC ကိုမဆို ပိတ်လိုက်သောအခါတွင် ဘလောက် 4 ခု မရနိုင်တော့မည်ဖြစ်ပြီး ဒေတာကို ဖတ်ရှုနိုင်ပါသည်။ ၎င်းကို DC 3 ခုတွင် ထည့်သွင်းသည့်အခါ ကျွန်ုပ်တို့ရွေးချယ်သည့် မည်သည့်အစီအစဉ်တွင်မဆို (r + l) / n >= 0,5 ရှိသင့်သည်၊ ဆိုလိုသည်မှာ သိုလှောင်မှုထပ်နေမှုသည် အနည်းဆုံး 50% ရှိမည်ဖြစ်သည်။

YT တွင် အခြေအနေ ကွဲပြားသည်- YT အစုအဝေး တစ်ခုစီသည် 1 DC တွင် လုံးလုံးလျားလျား တည်ရှိသည် (ကွဲပြားခြားနားသော DCs များတွင် မတူညီသော အစုအဝေးများ) ဖြစ်သောကြောင့် ထိုကဲ့သို့ ကန့်သတ်ချက် မရှိပါ။ 12-2-2 အစီအစဥ်သည် 33% redundancy ကိုပေးသည်၊ ဆိုလိုသည်မှာ၊ ဒေတာသိမ်းဆည်းခြင်းသည် စျေးသက်သာပြီး MDS အစီအစဉ်ကဲ့သို့ပင် တပြိုင်နက်တည်း disk ပြတ်တောက်မှု 4 ခုအထိလည်း ရှင်သန်နိုင်သည်။

ဒေတာသိမ်းဆည်းခြင်းနှင့် လုပ်ဆောင်ခြင်းစနစ်များတွင် ထပ်နေသောကုဒ်များကို အသုံးပြုခြင်း၏ နောက်ထပ်အင်္ဂါရပ်များစွာပါရှိသည်- ဒေတာပြန်လည်ရယူခြင်း၏ ကွဲပြားချက်များ၊ မေးမြန်းမှုလုပ်ဆောင်ချိန်အပေါ် ပြန်လည်ရယူခြင်း၏ အကျိုးသက်ရောက်မှု၊ ဒေတာမှတ်တမ်းတင်ခြင်းဆိုင်ရာ အင်္ဂါရပ်များ စသည်တို့ကို ကျွန်ုပ် သီးခြားပြောဆိုသွားပါမည်။ အကယ်၍ redundancy codes များကို လက်တွေ့တွင် အသုံးပြုခြင်း၏ အကြောင်းအရာသည် စိတ်ဝင်စားစရာ ဖြစ်လိမ့်မည်။

6. လင့်များ

1. Reed-Solomon ကုဒ်များနှင့် Galois အကွက်များအကြောင်း ဆောင်းပါးတိုများ 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

source: www.habr.com