هي اهو آهي جيڪو فالتو نظر اچي ٿو
ريڊنڊنسي ڪوڊ* وڏي پيماني تي ڪمپيوٽر سسٽم ۾ استعمال ڪيا ويندا آهن ڊيٽا اسٽوريج جي اعتبار کي وڌائڻ لاءِ. Yandex ۾ اهي ڪيترن ئي منصوبن ۾ استعمال ٿيندا آهن. مثال طور، اسان جي اندروني آبجیکٹ اسٽوريج ۾ نقل ڪرڻ جي بدران فالتو ڪوڊ استعمال ڪرڻ، اعتبار کي قربان ڪرڻ کان سواءِ لکين بچائي ٿو. پر انهن جي وسيع استعمال جي باوجود، واضح وضاحتون ته ڪيئن فالتو ڪوڊ ڪم ڪن ٿا تمام نادر آهن. جيڪي سمجھڻ چاھين ٿا انھن کي لڳ ڀڳ ھيٺين سان منهن ڏيڻو پوي ٿو (مان ):
منهنجو نالو Vadim آهي، Yandex تي مان ترقي ڪري رهيو آهيان اندروني اعتراض اسٽوريج MDS. هن آرٽيڪل ۾، مان سادي لفظن ۾ بيان ڪندس نظرياتي بنيادن جي بيڪار ڪوڊس (ريڊ-سليمان ۽ ايل آر سي ڪوڊ). مان توهان کي ٻڌايان ٿو ته اهو ڪيئن ڪم ڪري ٿو، پيچيده رياضي ۽ نادر اصطلاحن کان سواء. آخر ۾ آئون مثال ڏيندس redundancy ڪوڊ استعمال ڪرڻ جا Yandex ۾.
مان ڪيترن ئي رياضياتي تفصيلن تي تفصيل سان غور نه ڪندس، پر آئون انهن لاء لنڪس مهيا ڪندس جيڪي وڌيڪ اونهي کيڏڻ چاهيندا آهن. مان اهو به نوٽ ڪندس ته ڪجهه رياضياتي وصفون شايد سخت نه هجن، ڇاڪاڻ ته مضمون رياضي دانن لاءِ نه آهي، پر انجنيئرن لاءِ جيڪي هن مسئلي جي جوهر کي سمجهڻ چاهين ٿا.
* انگريزي ٻوليءَ جي ادب ۾، redundancy codes کي اڪثر erasure codes چئبو آهي.
1. redundancy ڪوڊ جو خلاصو
تمام بيڪار ڪوڊس جو جوهر انتهائي سادو آهي: ڊيٽا کي ذخيرو ڪريو (يا منتقلي) ته جيئن اهو گم نه ٿئي جڏهن غلطيون ٿينديون آهن (ڊسڪ ناڪامي، ڊيٽا جي منتقلي جي غلطي، وغيره).
اڪثر * بيڪار ڪوڊس ۾، ڊيٽا کي ورهايو ويندو آهي n ڊيٽا بلاڪ، جنهن جي لاءِ فالتو ڪوڊ جا m بلاڪ ڳڻيا ويندا آهن، نتيجي ۾ مجموعي طور تي n + m بلاڪ هوندا آهن. ريڊنڊنسي ڪوڊس اهڙي طرح ٺاهيا ويا آهن ته ڊيٽا جا n بلاڪ حاصل ڪري سگھجن ٿا صرف n + m بلاڪ جو هڪ حصو استعمال ڪندي. اڳيون، اسان تي غور ڪنداسين صرف بلاڪ ريٽرنسي ڪوڊ، اهو آهي، جن ۾ ڊيٽا کي بلاڪ ۾ ورهايو ويو آهي.
ڊيٽا جي سڀني n بلاڪ کي بحال ڪرڻ لاء، توهان کي گهٽ ۾ گهٽ n + m بلاڪ هجڻ جي ضرورت آهي، ڇو ته توهان صرف n-1 بلاڪ حاصل ڪرڻ سان n بلاڪ حاصل نٿا ڪري سگهو (هن صورت ۾، توهان کي 1 بلاڪ وٺڻو پوندو. هوا"). ڇا n + m بلاڪ جي بي ترتيب واري بلاڪ تمام ڊيٽا کي بحال ڪرڻ لاء ڪافي آهن؟ اهو انحصار ڪري ٿو بيڪار ڪوڊ جي قسم تي، مثال طور، ريڊ-سليمن ڪوڊس توهان کي اجازت ڏين ٿا سڀني ڊيٽا کي حاصل ڪرڻ لاءِ صوابديدي n بلاڪ استعمال ڪندي، پر LRC ريڊنڊنسي ڪوڊ هميشه نه ڪندا آهن.
ڊيٽا اسٽوريج
ڊيٽا اسٽوريج سسٽم ۾، ضابطي جي طور تي، هر هڪ ڊيٽا بلاڪ ۽ بيڪار ڪوڊ بلاڪ هڪ الڳ ڊسڪ ڏانهن لکيل آهي. پوء، جيڪڏهن هڪ خودمختيار ڊسڪ ناڪام ٿئي ٿي، اصل ڊيٽا اڃا تائين بحال ۽ پڙهي سگهجي ٿو. ڊيٽا واپس ٿي سگھي ٿو جيتوڻيڪ ڪيترائي ڊسڪ هڪ ئي وقت ۾ ناڪام ٿين ٿيون.
ڊيٽا جي منتقلي
ريڊنڊنسي ڪوڊس استعمال ڪري سگھجن ٿا معتبر طور تي ڊيٽا کي غير معتبر نيٽ ورڪ تي منتقل ڪرڻ لاءِ. منتقل ٿيل ڊيٽا کي بلاڪ ۾ ورهايو ويو آهي، ۽ ريٽرنسي ڪوڊ انهن لاء حساب ڪيو ويو آهي. ٻئي ڊيٽا بلاڪ ۽ بيڪار ڪوڊ بلاڪ نيٽ ورڪ تي منتقل ڪيا ويا آهن. جيڪڏهن غلطيون صوابديدي بلاڪ ۾ ٿينديون آهن (بلاڪ جي هڪ خاص تعداد تائين)، ڊيٽا اڃا تائين نيٽ ورڪ تي بغير ڪنهن غلطي جي منتقل ڪري سگهجي ٿو. ريڊ-سليمن ڪوڊس، مثال طور، آپٽيڪل ڪميونيڪيشن لائينز ۽ سيٽلائيٽ ڪميونيڪيشن ۾ ڊيٽا کي منتقل ڪرڻ لاءِ استعمال ٿيندا آهن.
* اهڙا redundancy ڪوڊ پڻ آهن جن ۾ ڊيٽا کي بلاڪن ۾ ورهايو نه ويو آهي، جهڙوڪ هيمنگ ڪوڊ ۽ CRC ڪوڊ، جيڪي ايٿرنيٽ نيٽ ورڪن ۾ ڊيٽا جي منتقلي لاءِ وڏي پيماني تي استعمال ٿيندا آهن. اھي ڪوڊ آھن نقص کي درست ڪرڻ واري ڪوڊنگ لاءِ، اھي ٺاھيا ويا آھن نقصن کي ڳولڻ لاءِ، ۽ نه انھن کي درست ڪرڻ لاءِ (Haming ڪوڊ پڻ غلطين جي جزوي اصلاح جي اجازت ڏئي ٿو).
2. ريڊ-سليمن ڪوڊس
ريڊ-سليمن ڪوڊس سڀ کان وڏي پيماني تي استعمال ٿيندڙ ريڊنڊنسي ڪوڊز مان هڪ آهن، جيڪي 1960ع ۾ ايجاد ڪيا ويا ۽ پهريون ڀيرو 1980ع واري ڏهاڪي ۾ ڪمپيڪٽ ڊسڪ جي وڏي پيداوار لاءِ استعمال ڪيا ويا.
Reed-Solomon codes کي سمجھڻ لاءِ ٻه اھم سوال آھن: 1) redundancy codes جا بلاڪ ڪيئن ٺاھيا وڃن؛ 2) بيڪار ڪوڊ بلاڪ استعمال ڪندي ڊيٽا کي ڪيئن بحال ڪجي. اچو ته انهن جا جواب ڳوليون.
سادگي لاءِ، اسان وڌيڪ فرض ڪنداسين ته n=6 ۽ m=4. ٻين اسڪيمن کي قياس جي لحاظ کان سمجهيو ويندو آهي.
بيڪار ڪوڊ بلاڪ ڪيئن ٺاھيو
هر بلاڪ جي بيڪار ڪوڊ جي ڳڻپ ڪئي ويندي آهي آزاديءَ سان ٻين کان. سڀ n ڊيٽا بلاڪ هر بلاڪ کي ڳڻڻ لاء استعمال ڪيا ويا آهن. هيٺ ڏنل شڪل ۾، X1-X6 ڊيٽا بلاڪ آهن، P1-P4 بيڪار ڪوڊ بلاڪ آهن.
سڀئي ڊيٽا بلاڪ هڪ ئي سائيز هجڻ گهرجن، ۽ صفر بٽ ترتيب ڏيڻ لاءِ استعمال ڪري سگھجن ٿا. نتيجي ۾ بيڪار ڪوڊ بلاڪ ساڳيا سائيز هوندا جيئن ڊيٽا بلاڪ. سڀ ڊيٽا بلاڪ لفظن ۾ ورهايل آهن (مثال طور، 16 بٽ). اچو ته اسان ڊيٽا بلاڪ کي k لفظن ۾ ورهايو. پوءِ redundancy codes جا سڀ بلاڪ به k لفظن ۾ ورهايا ويندا.
هر ريڊنڊنسي بلاڪ جي i-th لفظ کي ڳڻڻ لاء، سڀني ڊيٽا بلاڪ جي i-th لفظ استعمال ڪيا ويندا. انهن جو حساب هيٺ ڏنل فارمولا مطابق ڪيو ويندو:
هتي ويل ويلز x ڊيٽا بلاڪ جا لفظ آهن، p لفظ آهن redundancy code blocks جا، سڀ الفا، بيٽا، گاما ۽ ڊيلٽا خاص طور تي چونڊيل نمبر آهن جيڪي سڀني i لاءِ ساڳيا آهن. اهو فوري طور تي چوڻ گهرجي ته اهي سڀئي قيمتون عام انگ نه آهن، پر گيلوس فيلڊ جا عنصر؛ آپريشن +، -، *، / آپريشن نه آهن جيڪي اسان سڀني کي واقف آهن، پر خاص عملن جو تعارف Galois جي عناصرن تي ڪيو ويو آهي. ميدان.
ڇو Galois شعبن جي ضرورت آهي؟
اهو لڳي ٿو ته سڀ ڪجهه سادو آهي: اسان ڊيٽا کي بلاڪن ۾ ورهايو ٿا، بلاڪ کي لفظن ۾، ڊيٽا بلاڪ جي لفظن کي استعمال ڪندي اسين ڳڻپ ڪريون ٿا فالتو ڪوڊ بلاڪ جا لفظ - اسان حاصل ڪندا آهيون redundancy code blocks. عام طور تي اهو ڪيئن ڪم ڪري ٿو، پر شيطان تفصيل ۾ آهي:
- جيئن مٿي بيان ڪيو ويو آهي، لفظ سائيز مقرر ٿيل آهي، اسان جي مثال ۾ 16 بٽ. Reed-Solomon ڪوڊس لاءِ مٿي ڏنل فارمولا اهڙا آهن ته جڏهن عام انٽيجرز استعمال ڪندا، p جي ڳڻپ جو نتيجو صحيح سائيز جو لفظ استعمال ڪندي نمايان نه ٿي سگھي.
- ڊيٽا کي بحال ڪرڻ وقت، مٿين فارمولن کي مساوات جي سسٽم طور سمجهيو ويندو جيڪو ڊيٽا کي بحال ڪرڻ لاء حل ڪيو وڃي. حل جي عمل دوران، اهو ضروري ٿي سگھي ٿو ته عددن کي هڪ ٻئي سان ورهايو وڃي، نتيجي ۾ هڪ حقيقي انگ جيڪو ڪمپيوٽر جي ياداشت ۾ صحيح طور تي نمائندگي نٿو ڪري سگهجي.
اهي مسئلا ريڊ-سليمن ڪوڊس لاءِ انٽيجرز جي استعمال کي روڪيندا آهن. مسئلي جو حل اصل آهي، ان کي هن ريت بيان ڪري سگهجي ٿو: اچو ته خاص نمبرن سان گڏ اچون جيڪي گهربل لمبائي جي لفظن (مثال طور، 16 بٽ) استعمال ڪندي نمائندگي ڪري سگھجن ٿيون، ۽ سڀني عملن کي انجام ڏيڻ جو نتيجو جنهن تي (اضافي. , subtraction, multiplication, division) پڻ ڪمپيوٽر جي ميموري ۾ پيش ڪيو ويندو گهربل لمبائي جا لفظ استعمال ڪندي.
اهڙيون "خاص" انگن اکرن لاء رياضي جي ذريعي اڀياس ڪئي وئي آهي؛ انهن کي فيلڊ سڏيو ويندو آهي. فيلڊ عناصر جو ھڪڙو سيٽ آھي جنھن ۾ اضافو، گھٽائڻ، ضرب ۽ تقسيم جي عملن جي وضاحت ڪئي وئي آھي.
Galois* فيلڊز اهي فيلڊ آهن جن لاءِ فيلڊ جي ڪنهن به ٻن عنصرن لاءِ هر آپريشن (+, -, *, /) جو هڪ منفرد نتيجو هوندو آهي. گيلوس فيلڊس انهن انگن لاءِ ٺاهي سگھجن ٿيون جيڪي 2: 2، 4، 8، 16 وغيره جون طاقتون آهن (اصل ۾ ڪنهن به پرائم نمبر p جون طاقتون آهن، پر عملي طور تي اسان کي صرف 2 جي طاقتن ۾ دلچسپي آهي). مثال طور، 16-bit لفظن لاءِ، هي هڪ فيلڊ آهي جنهن ۾ 65 عناصر شامل آهن، هر هڪ جوڙي لاءِ جنهن ۾ توهان ڪنهن به آپريشن جو نتيجو ڳولي سگهو ٿا (+, -, *, /). مٿين مساواتن مان x، p، الفا، بيٽا، گاما، ڊيلٽا جي قدرن کي حساب لاءِ گيلوس فيلڊ جا عنصر سمجھيا ويندا.
اهڙيءَ طرح، اسان وٽ مساواتن جو هڪ نظام آهي جنهن سان اسان هڪ مناسب ڪمپيوٽر پروگرام لکڻ ذريعي بيڪار ڪوڊ جا بلاڪ ٺاهي سگهون ٿا. مساوات جي ساڳئي نظام کي استعمال ڪندي، توهان ڊيٽا جي وصولي کي انجام ڏئي سگهو ٿا.
* هي هڪ سخت تعريف نه آهي، بلڪه هڪ وضاحت.
ڊيٽا کي ڪيئن بحال ڪجي
بحالي جي ضرورت آهي جڏهن ڪجهه n + m بلاڪ غائب آهن. اهي ٻئي ڊيٽا بلاڪ ۽ بيڪار ڪوڊ بلاڪ ٿي سگهن ٿا. ڊيٽا بلاڪ ۽/يا بيڪار ڪوڊ بلاڪ جي غير موجودگي جو مطلب اهو ٿيندو ته لاڳاپيل x ۽/يا p متغير مٿي ڏنل مساواتن ۾ اڻڄاتل آهن.
Reed-Solomon ڪوڊز جي مساواتن کي مساواتن جي هڪ سرشتي جي طور تي ڏسي سگهجي ٿو جنهن ۾ سڀئي الفا، بيٽا، گاما، ڊيلٽا ويلز مستقل آهن، موجود بلاڪن سان لاڳاپيل سڀئي x ۽ p ڄاڻايل متغير آهن، ۽ باقي x ۽ p. نامعلوم آهن.
مثال طور، ڊيٽا بلاڪ 1، 2، 3 ۽ ريڊنڊنسي ڪوڊ بلاڪ 2 کي دستياب نه هئڻ ڏيو، پوءِ لفظن جي i-th گروپ لاءِ هيٺ ڏنل نظام جي مساوات هوندي (اڻڄاتل ڳاڙهي ۾ نشان لڳل آهن):
اسان وٽ 4 مساواتن جو هڪ سسٽم آهي 4 نامعلومن سان، جنهن جو مطلب آهي ته اسان ان کي حل ڪري سگهون ٿا ۽ ڊيٽا کي بحال ڪري سگهون ٿا!
مساوات جي هن سرشتي مان ڪيترن ئي نتيجن تي عمل ڪيو ويو آهي ڊيٽا جي بحالي بابت ريڊ-سليمن ڪوڊس (اين ڊيٽا بلاڪ، ايم ريڊنڊنسي ڪوڊ بلاڪ):
- ڊيٽا واپس ٿي سگھي ٿي جيڪڏھن ڪو م بلاڪ يا گھٽ گم ٿي ويا آھن. جيڪڏهن m+1 يا وڌيڪ بلاڪ گم ٿي ويا آهن، ڊيٽا کي بحال نه ٿو ڪري سگهجي: m + 1 نامعلومن سان m مساوات جي سسٽم کي حل ڪرڻ ناممڪن آهي.
- هڪ به ڊيٽا بلاڪ کي بحال ڪرڻ لاء، توهان کي استعمال ڪرڻ جي ضرورت آهي n باقي بلاڪ مان، ۽ توهان استعمال ڪري سگهو ٿا ڪنهن به فالتو ڪوڊ.
ٻيو ڇا توهان کي ڄاڻڻ جي ضرورت آهي
مٿي بيان ڪيل بيان ۾، مان ڪيترن ئي اهم مسئلن کان پاسو ڪريان ٿو جن تي غور ڪرڻ لاءِ رياضي ۾ وڌيڪ اونهائي جي ضرورت آهي. خاص طور تي، مان هيٺين بابت ڪجهه به نه چئي رهيو آهيان:
- Reed-Solomon رموز جي مساواتن جي سسٽم ۾ اڻڄاڻن جي ڪنهن به ميلاپ لاءِ (منفرد) حل هجڻ ضروري آهي (m unknowns کان وڌيڪ نه). هن ضرورت جي بنياد تي، الفا، بيٽا، گاما ۽ ڊيلٽا جا قدر چونڊيا ويا آهن.
- مساوات جو هڪ نظام لازمي طور تي خودڪار طور تي تعمير ڪرڻ جي قابل هوندو (ان تي منحصر آهي ته بلاڪ موجود نه آهن) ۽ حل ڪيو وڃي.
- اسان کي گيلوس فيلڊ ٺاهڻ جي ضرورت آهي: ڏنل لفظ جي سائيز لاءِ، ڪنهن به ٻن عنصرن لاءِ ڪنهن به آپريشن (+، -، *، /) جا نتيجا ڳولڻ جي قابل ٿي وڃو.
مضمون جي آخر ۾ انهن اهم مسئلن تي ادب جا حوالا ڏنا ويا آهن.
ن ۽ م جو انتخاب
عمل ۾ ن ۽ م کي ڪيئن چونڊيو؟ عملي طور تي، ڊيٽا اسٽوريج سسٽم ۾، بيڪار ڪوڊ استعمال ڪيا ويندا آهن خلا کي بچائڻ لاء، تنهنڪري m هميشه n کان گهٽ چونڊيو ويندو آهي. انهن جا مخصوص قدر ڪيترن ئي عنصر تي منحصر آهن، جن ۾ شامل آهن:
- ڊيٽا اسٽوريج جي قابل اعتماد. وڏو m، ڊسڪ جي ناڪامين جو وڏو تعداد جيڪو بچي سگهجي ٿو، اهو آهي، اعلي اعتماد.
- بيڪار اسٽوريج. جيترو وڌيڪ m/n تناسب هوندو، اوترو وڌيڪ اسٽوريج بيڪار ٿيندو، ۽ سسٽم وڌيڪ مهانگو هوندو.
- پروسيسنگ وقت جي درخواست ڪريو. جيتري وڏي رقم n + m هوندي، اوترو وڌيڪ درخواستن جو جواب وقت هوندو. جيئن ته پڙهڻ واري ڊيٽا (بحالي دوران) پڙهڻ جي ضرورت آهي n مختلف ڊسڪ تي ذخيرو ٿيل n بلاڪ، پڙهڻ جو وقت تمام سست ڊسڪ ذريعي طئي ڪيو ويندو.
ان کان علاوه، ڪيترن ئي DC ۾ ڊيٽا کي محفوظ ڪرڻ n ۽ m جي چونڊ تي اضافي پابنديون لاڳو ڪري ٿو: جيڪڏهن 1 DC بند ٿيل آهي، ڊيٽا اڃا تائين پڙهڻ لاء دستياب هجڻ گهرجي. مثال طور، 3 ڊي سي ۾ ڊيٽا محفوظ ڪرڻ وقت، هيٺين شرطن کي پورو ڪرڻ گهرجي: m >= n/2، ٻي صورت ۾ اها صورتحال ٿي سگهي ٿي جتي ڊيٽا پڙهڻ لاءِ دستياب نه هجي جڏهن 1 DC بند هجي.
3. LRC - مقامي تعميراتي ڪوڊ
Reed-Solomon ڪوڊس استعمال ڪندي ڊيٽا کي بحال ڪرڻ لاء، توهان کي استعمال ڪرڻو پوندو n صوابديدي ڊيٽا بلاڪ. هي ورهايل ڊيٽا اسٽوريج سسٽم لاء هڪ تمام اهم نقصان آهي، ڇاڪاڻ ته هڪ ٽٽل ڊسڪ تي ڊيٽا کي بحال ڪرڻ لاء، توهان کي ٻين مان اڪثر ڊيٽا کي پڙهڻو پوندو، ڊسڪ ۽ نيٽ ورڪ تي هڪ وڏو اضافي لوڊ ٺاهيندي.
سڀ کان وڌيڪ عام غلطيون آهن ڊيٽا جي هڪ بلاڪ جي رسائي جي ناڪامي يا هڪ ڊسڪ جي اوورلوڊ جي ڪري. ڇا اهو ممڪن آهي ته ڪنهن به طرح هن (سڀ کان عام) صورت ۾ ڊيٽا جي وصولي لاء اضافي لوڊ کي گهٽائڻ لاء؟ اهو ظاهر ٿئي ٿو ته توهان ڪري سگهو ٿا: هتي آهن LRC بيڪار ڪوڊ خاص طور تي هن مقصد لاءِ.
LRC (Local Reconstruction Codes) Microsoft پاران ونڊوز Azure Storage ۾ استعمال ڪرڻ لاءِ ايجاد ڪيل ريڊنڊنسي ڪوڊس آهن. 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 ۾ ريڊ-سليمن ڪوڊس سان قياس سان ڪيو ويو آهي. redundancy code blocks جي لفظن کي ڳڻڻ لاءِ مساواتون ھيون:
انگن اکرن کي چونڊڻ لاءِ الفا، بيٽا، گاما، ڊيلٽا، ڊيٽا جي بحالي جي امڪان کي يقيني بڻائڻ لاءِ ڪجهه شرطن کي پورا ڪرڻ لازمي آهي (يعني مساوات سسٽم کي حل ڪرڻ). توھان ان بابت وڌيڪ پڙھي سگھو ٿا .
پڻ عملي طور تي، 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 ڪوڊز ۾، ڊيٽا جي هڪ بلاڪ کي به حاصل ڪرڻ لاء، توهان کي استعمال ڪرڻ جي ضرورت آهي n بلاڪ، ۽ LRC ۾، ڊيٽا جي هڪ بلاڪ کي بحال ڪرڻ لاء، اهو ڪافي آهي n/l بلاڪ استعمال ڪرڻ (اسان جي مثال ۾ n/2). ٻئي طرف، LRC قابل اجازت غلطين جي وڌ ۾ وڌ تعداد جي لحاظ کان ريڊ-سليمن ڪوڊس کان گھٽ آھي. مٿي ڏنل مثالن ۾، ريڊ-سليمن ڪوڊس ڊيٽا کي بحال ڪري سگھن ٿا 4 غلطين لاءِ، ۽ LRC لاءِ 2 غلطين جا 4 مجموعا آھن جڏھن ڊيٽا واپس نه ٿي سگھي.
ڇا وڌيڪ اهم آهي ان جو دارومدار مخصوص صورتحال تي آهي، پر گهڻو ڪري بچت جي اضافي لوڊ ۾ جيڪا LRC مهيا ڪري ٿي، جيڪا ٿوري گهٽ قابل اعتماد اسٽوريج کان وڌيڪ آهي.
4. ٻيا redundancy ڪوڊ
ريڊ-سليمن ۽ LRC ڪوڊس کان علاوه، ٻيا به ڪيترائي بيڪار ڪوڊ آھن. مختلف فالتو ڪوڊ مختلف رياضي استعمال ڪن ٿا. هتي ڪجھ ٻيا فالتو ڪوڊ آهن:
- XOR آپريٽر استعمال ڪندي بيڪار ڪوڊ. XOR آپريشن n ڊيٽا بلاڪ تي ڪيو ويندو آھي، ۽ 1 بلاڪ بيڪار ڪوڊ حاصل ڪيو ويندو آھي، اھو آھي، ھڪڙو اين + 1 اسڪيم (اين ڊيٽا بلاڪ، 1 بيڪار ڪوڊ). ۾ استعمال ڪيو ويو ، جتي ڊيٽا جا بلاڪ ۽ ريڊنڊنسي ڪوڊ سائيڪل جي ترتيب جي سڀني ڊسڪ تي لکيل آهن.
- XOR آپريشن جي بنياد تي ايون-اوڊ الگورتھم. توھان کي اجازت ڏئي ٿو 2 بلاڪس جي بيڪار ڪوڊس، اھو آھي، n + 2 اسڪيم.
- XOR آپريشن جي بنياد تي اسٽار الگورتھم. توھان کي اجازت ڏئي ٿو 3 بلاڪس جي بيڪار ڪوڊس، اھو آھي، n + 3 اسڪيم.
- Pyramide ڪوڊس Microsoft کان هڪ ٻيو فالتو ڪوڊ آهن.
5. Yandex ۾ استعمال ڪريو
Yandex انفراسٽرڪچر پروجيڪٽ جو هڪ انگ قابل اعتماد ڊيٽا اسٽوريج لاءِ فالتو ڪوڊ استعمال ڪن ٿا. هتي ڪجهه مثال آهن:
- MDS اندروني اعتراض اسٽوريج، جنهن بابت مون آرٽيڪل جي شروعات ۾ لکيو.
- - Yandex جو MapReduce سسٽم.
- (Yandex DataBase) - نئون ايس ايس ايل ورهايل ڊيٽابيس.
MDS استعمال ڪري ٿو LRC بيڪار ڪوڊس، 8-2-2 اسڪيم. ڊيٽا بيڪار ڪوڊ سان گڏ 12 مختلف ڊسڪ تي 3 مختلف ڊي سيز ۾ مختلف سرورن ۾ لکيو ويو آهي: 4 سرور هر DC ۾. انهي بابت وڌيڪ پڙهو ۾ .
YT ٻئي استعمال ڪري ٿو ريڊ-سليمن ڪوڊس (اسڪيم 6-3)، جيڪي لاڳو ڪرڻ وارا پهريان هئا، ۽ LRC ريڊنڊنسي ڪوڊ (اسڪيم 12-2-2)، جنهن ۾ LRC کي ترجيحي اسٽوريج جو طريقو آهي.
YDB استعمال ڪري ٿو بي مثال بي بنياد ڪوڊس (شڪل 4-2). اڳ ۾ ئي YDB ۾ بيڪار ڪوڊ بابت .
مختلف بيڪار ڪوڊ اسڪيمن جو استعمال سسٽم لاءِ مختلف ضرورتن جي ڪري آهي. مثال طور، MDS ۾، LRC استعمال ڪندي ذخيرو ٿيل ڊيٽا هڪ ڀيرو 3 DCs ۾ رکيل آهي. اسان لاءِ اهو ضروري آهي ته ڊيٽا پڙهڻ لاءِ موجود رهي جيڪڏهن ڪنهن DCs مان 1 ناڪام ٿئي ٿو، تنهن ڪري بلاڪس کي سڀني DCs ۾ ورهايو وڃي ته جيئن جيڪڏهن ڪو DC موجود نه هجي ته ناقابل رسائي بلاڪن جو تعداد اجازت کان وڌيڪ نه هجي. 8-2-2 اسڪيم ۾، توهان هر ڊي سي ۾ 4 بلاڪ رکي سگهو ٿا، پوءِ جڏهن ڪنهن به ڊي سي کي بند ڪيو ويندو، 4 بلاڪ موجود نه هوندا، ۽ ڊيٽا پڙهي سگهجي ٿو. اسان جيڪا به اسڪيم چونڊيندا آهيون جڏهن ان کي 3 DCs ۾ رکڻ گهرجي، ڪنهن به صورت ۾ اتي هجڻ گهرجي (r + l) / n >= 0,5، يعني اسٽوريج جي بيڪارگي گهٽ ۾ گهٽ 50٪ هوندي.
YT ۾ صورتحال مختلف آهي: هر YT ڪلستر مڪمل طور تي 1 DC ۾ واقع آهي (مختلف DC ۾ مختلف ڪلستر)، تنهنڪري اهڙي ڪا پابندي ناهي. 12-2-2 اسڪيم 33٪ ريڊنڊنسي مهيا ڪري ٿي، يعني ڊيٽا کي محفوظ ڪرڻ سستو آهي، ۽ اهو پڻ MDS اسڪيم وانگر 4 هڪ ئي وقت ۾ ڊسڪ آئوٽيجز تائين زنده رهي سگهي ٿو.
ڊيٽا اسٽوريج ۽ پروسيسنگ سسٽم ۾ ريڊنڊنسي ڪوڊس جي استعمال جون ٻيون به ڪيتريون ئي خاصيتون آهن: ڊيٽا جي وصولي جي nuances، سوال جي عمل جي وقت تي وصولي جو اثر، ڊيٽا رڪارڊنگ جون خاصيتون، وغيره. مان انهن ۽ ٻين خاصيتن بابت الڳ الڳ ڳالهائڻ وارو آهيان. عملي طور تي redundancy ڪوڊ جي استعمال جي، جيڪڏھن موضوع دلچسپ ٿيندو.
6. لنڪس
- ريڊ-سليمن ڪوڊس ۽ گيلوس فيلڊ بابت آرٽيڪل جو هڪ سلسلو:
اُهي پهچندڙ ٻوليءَ ۾ رياضيءَ تي تمام گهڻي غور ڪن ٿا. - LRC بابت Microsoft کان آرٽيڪل:
سيڪشن 2 مختصر طور تي نظريي جي وضاحت ڪري ٿو ۽ پوءِ عملي طور LRC سان تجربن تي بحث ڪري ٿو. - هموار اسڪيم:
- اسٽار اسڪيم:
- Pyramid ڪوڊ:
- MDS ۾ بيڪار ڪوڊ:
- YT ۾ بيڪار ڪوڊ:
- YDB ۾ بيڪار ڪوڊ:
جو ذريعو: www.habr.com