فالتو پن ایسا لگتا ہے۔

ڈیٹا سٹوریج کی بھروسے کو بڑھانے کے لیے فالتو کوڈ* کمپیوٹر سسٹمز میں بڑے پیمانے پر استعمال ہوتے ہیں۔ Yandex میں وہ بہت سے منصوبوں میں استعمال کیا جاتا ہے. مثال کے طور پر، ہمارے اندرونی آبجیکٹ اسٹوریج میں نقل کے بجائے فالتو کوڈز کا استعمال قابل اعتمادی کی قربانی کے بغیر لاکھوں کی بچت کرتا ہے۔ لیکن ان کے وسیع پیمانے پر استعمال کے باوجود، بے کار کوڈز کے کام کرنے کے طریقے کی واضح وضاحتیں بہت کم ہیں۔ جو لوگ سمجھنا چاہتے ہیں انہیں تقریباً درج ذیل کا سامنا کرنا پڑتا ہے (سے وکیپیڈیا):

میرا نام Vadim ہے، Yandex میں میں اندرونی آبجیکٹ اسٹوریج MDS تیار کر رہا ہوں۔ اس مضمون میں، میں سادہ الفاظ میں فالتو کوڈز (ریڈ-سلیمن اور ایل آر سی کوڈز) کی نظریاتی بنیادوں کو بیان کروں گا۔ میں آپ کو بتاؤں گا کہ یہ کیسے کام کرتا ہے، پیچیدہ ریاضی اور نایاب اصطلاحات کے بغیر۔ آخر میں میں Yandex میں فالتو کوڈ استعمال کرنے کی مثالیں دوں گا۔

میں ریاضی کی متعدد تفصیلات پر تفصیل سے غور نہیں کروں گا، لیکن میں ان لوگوں کے لیے لنک فراہم کروں گا جو گہرائی میں غوطہ لگانا چاہتے ہیں۔ میں یہ بھی نوٹ کروں گا کہ کچھ ریاضی کی تعریفیں سخت نہیں ہوسکتی ہیں، کیونکہ مضمون کا مقصد ریاضی دانوں کے لیے نہیں ہے، بلکہ ان انجینئرز کے لیے ہے جو مسئلے کے جوہر کو سمجھنا چاہتے ہیں۔

* انگریزی زبان کے ادب میں، فالتو کوڈز کو اکثر مٹانے والے کوڈز کہا جاتا ہے۔

1. بے کار کوڈز کا جوہر

تمام فالتو کوڈز کا جوہر انتہائی آسان ہے: ڈیٹا کو اسٹور (یا ٹرانسمٹ) کریں تاکہ غلطیاں ہونے پر یہ ضائع نہ ہو (ڈسک کی ناکامی، ڈیٹا کی منتقلی کی خرابیاں، وغیرہ)۔

زیادہ تر* فالتو کوڈز میں، ڈیٹا کو n ڈیٹا بلاکس میں تقسیم کیا جاتا ہے، جس کے لیے redundancy کوڈز کے m بلاکس کو شمار کیا جاتا ہے، جس کے نتیجے میں کل n + m بلاکس ہوتے ہیں۔ فالتو کوڈز اس طرح بنائے جاتے ہیں کہ ڈیٹا کے n بلاکس کو صرف n + m بلاکس کے ایک حصے کا استعمال کرتے ہوئے بازیافت کیا جا سکتا ہے۔ اگلا، ہم صرف بلاک فالتو کوڈز پر غور کریں گے، یعنی وہ جن میں ڈیٹا کو بلاکس میں تقسیم کیا گیا ہے۔

ڈیٹا کے تمام n بلاکس کو بازیافت کرنے کے لیے، آپ کے پاس کم از کم n + m بلاکس ہونے کی ضرورت ہے، کیونکہ آپ صرف n-1 بلاک رکھنے سے n بلاکس حاصل نہیں کر سکتے (اس صورت میں، آپ کو 1 بلاک "پتلے میں سے" لینا پڑے گا۔ ہوا")۔ کیا n + m بلاکس کے n بے ترتیب بلاکس تمام ڈیٹا کو بازیافت کرنے کے لیے کافی ہیں؟ یہ ریڈنڈنسی کوڈز کی قسم پر منحصر ہے، مثال کے طور پر، Reed-Solomon کوڈز آپ کو صوابدیدی n بلاکس کا استعمال کرتے ہوئے تمام ڈیٹا کو بازیافت کرنے کی اجازت دیتے ہیں، لیکن LRC فالتو کوڈز ہمیشہ ایسا نہیں کرتے ہیں۔

ڈیٹا اسٹوریج

ڈیٹا سٹوریج کے نظام میں، ایک اصول کے طور پر، ڈیٹا بلاکس اور فالتو کوڈ بلاکس میں سے ہر ایک کو الگ ڈسک پر لکھا جاتا ہے۔ پھر، اگر کوئی صوابدیدی ڈسک ناکام ہو جاتی ہے، تو اصل ڈیٹا اب بھی بحال اور پڑھا جا سکتا ہے۔ ڈیٹا بازیافت کیا جاسکتا ہے یہاں تک کہ اگر بیک وقت کئی ڈسکیں ناکام ہوجائیں۔

ڈیٹا کی منتقلی۔

فالتو کوڈز کا استعمال قابل اعتماد نیٹ ورک پر ڈیٹا منتقل کرنے کے لیے کیا جا سکتا ہے۔ منتقل شدہ ڈیٹا کو بلاکس میں تقسیم کیا جاتا ہے، اور ان کے لیے فالتو کوڈز کا حساب لگایا جاتا ہے۔ ڈیٹا بلاکس اور فالتو کوڈ بلاکس دونوں نیٹ ورک پر منتقل کیے جاتے ہیں۔ اگر صوابدیدی بلاکس (بلاکس کی ایک خاص تعداد تک) میں غلطیاں ہوتی ہیں، تو ڈیٹا کو بغیر کسی غلطی کے نیٹ ورک پر منتقل کیا جا سکتا ہے۔ مثال کے طور پر، Reed-Solomon کوڈز کو آپٹیکل کمیونیکیشن لائنوں اور سیٹلائٹ کمیونیکیشنز میں ڈیٹا منتقل کرنے کے لیے استعمال کیا جاتا ہے۔

* ایسے فالتو کوڈز بھی ہیں جن میں ڈیٹا کو بلاکس میں تقسیم نہیں کیا جاتا، جیسے ہیمنگ کوڈز اور CRC کوڈز، جو ایتھرنیٹ نیٹ ورکس میں ڈیٹا کی ترسیل کے لیے بڑے پیمانے پر استعمال ہوتے ہیں۔ یہ غلطی کو درست کرنے والے کوڈنگ کے کوڈز ہیں، یہ غلطیوں کا پتہ لگانے کے لیے بنائے گئے ہیں، نہ کہ ان کو درست کرنے کے لیے (ہیمنگ کوڈ غلطیوں کی جزوی اصلاح کی بھی اجازت دیتا ہے)۔

2. ریڈ سلیمان کوڈز

Reed-Solomon کوڈز سب سے زیادہ استعمال ہونے والے فالتو کوڈز میں سے ایک ہیں، جو 1960 کی دہائی میں ایجاد ہوئے اور پہلی بار 1980 کی دہائی میں بڑے پیمانے پر کمپیکٹ ڈسکس کی پیداوار کے لیے استعمال ہوئے۔

Reed-Solomon کوڈز کو سمجھنے کے لیے دو اہم سوالات ہیں: 1) فالتو کوڈز کے بلاکس کیسے بنائیں؛ 2) فالتو کوڈ بلاکس کا استعمال کرتے ہوئے ڈیٹا کو کیسے بازیافت کریں۔ آئیے ان کے جوابات تلاش کرتے ہیں۔
سادگی کے لیے، ہم مزید فرض کریں گے کہ n=6 اور m=4۔ دیگر اسکیموں کو مشابہت سے سمجھا جاتا ہے۔

فالتو کوڈ بلاکس کیسے بنائیں

فالتو کوڈز کے ہر بلاک کو دوسروں سے آزادانہ طور پر شمار کیا جاتا ہے۔ تمام n ڈیٹا بلاکس کو ہر بلاک کو شمار کرنے کے لیے استعمال کیا جاتا ہے۔ نیچے دیے گئے خاکے میں، X1-X6 ڈیٹا بلاکس ہیں، P1-P4 فالتو کوڈ بلاکس ہیں۔

تمام ڈیٹا بلاکس کا سائز ایک جیسا ہونا چاہیے اور صف بندی کے لیے صفر بٹس استعمال کیے جا سکتے ہیں۔ نتیجے میں فالتو کوڈ کے بلاکس ڈیٹا بلاکس کے سائز کے ہی ہوں گے۔ تمام ڈیٹا بلاکس کو الفاظ میں تقسیم کیا گیا ہے (مثال کے طور پر، 16 بٹس)۔ ہم کہتے ہیں کہ ہم ڈیٹا بلاکس کو k الفاظ میں تقسیم کرتے ہیں۔ پھر فالتو کوڈز کے تمام بلاکس کو بھی k الفاظ میں تقسیم کیا جائے گا۔

ہر فالتو بلاک کے i-th لفظ کو شمار کرنے کے لیے، تمام ڈیٹا بلاکس کے i-th الفاظ استعمال کیے جائیں گے۔ ان کا حساب درج ذیل فارمولے کے مطابق کیا جائے گا۔

یہاں ویلیو x ڈیٹا بلاکس کے الفاظ ہیں، p redundancy کوڈ بلاکس کے الفاظ ہیں، تمام الفا، بیٹا، گاما اور ڈیلٹا خاص طور پر منتخب کردہ نمبرز ہیں جو تمام i کے لیے یکساں ہیں۔ یہ فوری طور پر کہنا ضروری ہے کہ یہ تمام اقدار عام اعداد نہیں ہیں، بلکہ گیلوس فیلڈ کے عناصر ہیں؛ آپریشنز +، -، *، / ہم سب کو واقف آپریشن نہیں ہیں، لیکن گیلوئس کے عناصر پر متعارف کرائے گئے خصوصی آپریشنز ہیں۔ میدان

Galois کے میدانوں کی ضرورت کیوں ہے؟

ایسا لگتا ہے کہ سب کچھ آسان ہے: ہم ڈیٹا کو بلاکس میں، بلاکس کو الفاظ میں تقسیم کرتے ہیں، ڈیٹا بلاکس کے الفاظ کا استعمال کرتے ہوئے ہم فالتو کوڈ بلاکس کے الفاظ گنتے ہیں - ہمیں فالتو کوڈ بلاکس ملتے ہیں۔ عام طور پر یہ اس طرح کام کرتا ہے، لیکن شیطان تفصیلات میں ہے:

1. جیسا کہ اوپر بیان کیا گیا ہے، لفظ کا سائز مقرر ہے، ہماری مثال میں 16 بٹس۔ Reed-Solomon کوڈز کے لیے اوپر دیے گئے فارمولے اس طرح کے ہیں کہ جب عام عددی عدد استعمال کرتے ہیں، p کا حساب لگانے کا نتیجہ درست سائز کے لفظ کا استعمال کرتے ہوئے قابل نمائندگی نہیں ہو سکتا۔
2. ڈیٹا کو بازیافت کرتے وقت، اوپر دیے گئے فارمولوں کو مساوات کے نظام کے طور پر سمجھا جائے گا جسے ڈیٹا کی بازیافت کے لیے حل کرنا ضروری ہے۔ حل کے عمل کے دوران، یہ ضروری ہو سکتا ہے کہ عدد کو ایک دوسرے سے تقسیم کیا جائے، جس کے نتیجے میں ایک حقیقی نمبر بنتا ہے جسے کمپیوٹر میموری میں درست طریقے سے ظاہر نہیں کیا جا سکتا۔

یہ مسائل Reed-Solomon کوڈز کے لیے عدد کے استعمال کو روکتے ہیں۔ مسئلے کا حل اصل ہے، اسے اس طرح بیان کیا جا سکتا ہے: آئیے خصوصی نمبرز کے ساتھ آتے ہیں جن کی نمائندگی مطلوبہ لمبائی کے الفاظ (مثال کے طور پر 16 بٹس) کے ذریعے کی جا سکتی ہے، اور ان تمام کارروائیوں کو انجام دینے کا نتیجہ جس پر (اضافہ) ، گھٹاؤ، ضرب، تقسیم) کو بھی کمپیوٹر میموری میں مطلوبہ لمبائی کے الفاظ استعمال کرتے ہوئے پیش کیا جائے گا۔

اس طرح کے "خصوصی" نمبروں کا ریاضی نے طویل عرصے سے مطالعہ کیا ہے؛ انہیں فیلڈز کہتے ہیں۔ فیلڈ عناصر کا ایک مجموعہ ہے جس میں اضافے، گھٹاؤ، ضرب اور تقسیم کی کارروائیاں ان کے لیے بیان کی گئی ہیں۔

Galois* فیلڈز وہ فیلڈز ہیں جن کے لیے فیلڈ کے کسی بھی دو عناصر کے لیے ہر آپریشن (+, -, *, /) کا ایک منفرد نتیجہ ہوتا ہے۔ Galois کے میدان ایسے اعداد کے لیے بنائے جا سکتے ہیں جو 2:2، 4، 8، 16، وغیرہ کی طاقتیں ہیں۔ مثال کے طور پر، 2 بٹ الفاظ کے لیے، یہ 16 عناصر پر مشتمل ایک فیلڈ ہے، جس میں سے ہر ایک جوڑے کے لیے آپ کسی بھی آپریشن (+, -, *, /) کا نتیجہ تلاش کر سکتے ہیں۔ اوپر دی گئی مساوات سے x، p، الفا، بیٹا، گاما، ڈیلٹا کی قدروں کو حساب کے لیے گیلوئس فیلڈ کے عناصر سمجھا جائے گا۔

اس طرح، ہمارے پاس مساوات کا ایک نظام ہے جس کے ساتھ ہم مناسب کمپیوٹر پروگرام لکھ کر فالتو کوڈ کے بلاکس بنا سکتے ہیں۔ مساوات کے اسی نظام کا استعمال کرتے ہوئے، آپ ڈیٹا کی وصولی کو انجام دے سکتے ہیں۔

* یہ کوئی سخت تعریف نہیں ہے، بلکہ ایک وضاحت ہے۔

ڈیٹا کو بازیافت کرنے کا طریقہ

بحالی کی ضرورت ہے جب کچھ n + m بلاکس غائب ہوں۔ یہ ڈیٹا بلاکس اور فالتو کوڈ بلاکس دونوں ہو سکتے ہیں۔ ڈیٹا بلاکس اور/یا فالتو کوڈ بلاکس کی عدم موجودگی کا مطلب یہ ہوگا کہ متعلقہ x اور/یا p متغیر اوپر دی گئی مساوات میں نامعلوم ہیں۔

Reed-Solomon کوڈز کی مساوات کو مساوات کے ایک نظام کے طور پر دیکھا جا سکتا ہے جس میں تمام الفا، بیٹا، گاما، ڈیلٹا کی قدریں مستقل ہیں، دستیاب بلاکس کے مطابق تمام x اور p معلوم متغیر ہیں، اور باقی x اور p نامعلوم ہیں

مثال کے طور پر، ڈیٹا بلاکس 1، 2، 3 اور فالتو کوڈ بلاک 2 کو دستیاب نہ ہونے دیں، پھر الفاظ کے i-th گروپ کے لیے مساوات کا درج ذیل نظام ہوگا (نامعلوم کو سرخ رنگ میں نشان زد کیا گیا ہے):

ہمارے پاس 4 نامعلوموں کے ساتھ 4 مساوات کا ایک نظام ہے، جس کا مطلب ہے کہ ہم اسے حل کر سکتے ہیں اور ڈیٹا کو بحال کر سکتے ہیں!

مساوات کے اس نظام سے Reed-Solomon کوڈز (n data blocks, m redundancy code blocks): ڈیٹا کی بازیابی کے بارے میں متعدد نتائج اخذ کیے جاتے ہیں۔

• اگر کوئی ایم بلاکس یا اس سے کم گم ہو جائیں تو ڈیٹا بازیافت کیا جا سکتا ہے۔ اگر m+1 یا اس سے زیادہ بلاکس ضائع ہو جائیں تو ڈیٹا کو بحال نہیں کیا جا سکتا: m + 1 نامعلوم کے ساتھ m مساوات کے نظام کو حل کرنا ناممکن ہے۔
• یہاں تک کہ ایک ڈیٹا بلاک کو بحال کرنے کے لیے، آپ کو بقیہ بلاکس میں سے کوئی n استعمال کرنے کی ضرورت ہے، اور آپ کسی بھی فالتو کوڈ کو استعمال کر سکتے ہیں۔

آپ کو اور کیا جاننے کی ضرورت ہے۔

اوپر کی تفصیل میں، میں بہت سے اہم مسائل سے بچتا ہوں جن پر غور کرنے کے لیے ریاضی میں گہرا غوطہ لگانے کی ضرورت ہے۔ خاص طور پر، میں مندرجہ ذیل کے بارے میں کچھ نہیں کہہ رہا ہوں:

• Reed-Solomon codes کے لیے مساوات کے نظام میں نامعلوم کے کسی بھی امتزاج کے لیے ایک (منفرد) حل ہونا چاہیے (m unknowns سے زیادہ نہیں)۔ اس ضرورت کی بنیاد پر الفا، بیٹا، گاما اور ڈیلٹا کی قدریں منتخب کی جاتی ہیں۔
• مساوات کا ایک نظام خود بخود تعمیر ہونے کے قابل ہونا چاہئے (اس بات پر منحصر ہے کہ کون سے بلاکس دستیاب نہیں ہیں) اور حل کیا جائے۔
• ہمیں ایک Galois فیلڈ بنانے کی ضرورت ہے: ایک دیئے گئے لفظ کے سائز کے لیے، کسی بھی دو عناصر کے لیے کسی بھی آپریشن (+, -, *, /) کا نتیجہ تلاش کرنے کے قابل ہوں۔

مضمون کے آخر میں ان اہم مسائل پر ادب کے حوالے ہیں۔

ن اور ایم کا انتخاب

عملی طور پر 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 کا آئیڈیا ہر ممکن حد تک آسان ہے: تمام ڈیٹا بلاکس کو دو (یا زیادہ) گروپس میں تقسیم کریں اور ہر گروپ کے لیے فالتو کوڈ بلاکس کا کچھ حصہ الگ سے پڑھیں۔ پھر کچھ فالتو کوڈ بلاکس کو تمام ڈیٹا بلاکس کا استعمال کرتے ہوئے شمار کیا جائے گا (LRC میں انہیں عالمی فالتو کوڈ کہا جاتا ہے)، اور کچھ - ڈیٹا بلاکس کے دو گروپوں میں سے ایک کا استعمال کرتے ہوئے (انہیں مقامی فالتو کوڈ کہا جاتا ہے)۔

LRC کو تین نمبروں سے ظاہر کیا جاتا ہے: nrl، جہاں n ڈیٹا بلاکس کی تعداد ہے، r عالمی فالتو کوڈ بلاکس کی تعداد ہے، l مقامی فالتو کوڈ بلاکس کی تعداد ہے۔ ڈیٹا کو پڑھنے کے لیے جب ایک ڈیٹا بلاک دستیاب نہ ہو، آپ کو صرف n/l بلاکس کو پڑھنے کی ضرورت ہے - یہ Reed-Solomon کوڈز کے مقابلے میں l گنا کم ہے۔

مثال کے طور پر، LRC 6-2-2 اسکیم پر غور کریں۔ X1–X6 — 6 ڈیٹا بلاکس، P1، P2 — 2 عالمی فالتو بلاکس، P3، P4 — 2 مقامی فالتو بلاکس۔

فالتو کوڈ بلاکس P1، P2 کو تمام ڈیٹا بلاکس کا استعمال کرتے ہوئے شمار کیا جاتا ہے۔ ریڈنڈنسی کوڈ بلاک P3 - ڈیٹا بلاکس X1-X3 کا استعمال کرتے ہوئے، فالتو کوڈ بلاک P4 - ڈیٹا بلاکس X4-X6 کا استعمال کرتے ہوئے

باقی LRC میں ریڈ سلیمان کوڈز کے ساتھ مشابہت سے کیا جاتا ہے۔ فالتو کوڈ بلاکس کے الفاظ گننے کے لیے مساوات یہ ہوں گی:

الفا، بیٹا، گاما، ڈیلٹا کے نمبروں کو منتخب کرنے کے لیے، ڈیٹا کی بازیافت کے امکان کی ضمانت کے لیے متعدد شرائط کو پورا کرنا ضروری ہے (یعنی مساوات کے نظام کو حل کرنا)۔ آپ ان کے بارے میں مزید پڑھ سکتے ہیں۔ آرٹیکل.
عملی طور پر بھی، 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 بلاکس استعمال کرنے کی ضرورت ہے، اور LRC میں، ڈیٹا کے ایک بلاک کو بازیافت کرنے کے لیے، n/l بلاکس کا استعمال کرنا کافی ہے (ہماری مثال میں n/2)۔ دوسری طرف، LRC قابل اجازت غلطیوں کی زیادہ سے زیادہ تعداد کے لحاظ سے Reed-Solomon کوڈز سے کمتر ہے۔ مندرجہ بالا مثالوں میں، Reed-Solomon کوڈز کسی بھی 4 غلطیوں کے لیے ڈیٹا کو بازیافت کر سکتے ہیں، اور LRC کے لیے 2 غلطیوں کے 4 مجموعے ہیں جب ڈیٹا کو بازیافت نہیں کیا جا سکتا ہے۔

جو چیز زیادہ اہم ہے اس کا انحصار مخصوص صورتحال پر ہوتا ہے، لیکن اکثر اضافی بوجھ کی بچت جو LRC فراہم کرتی ہے قدرے کم قابل اعتماد اسٹوریج سے زیادہ ہوتی ہے۔

4. دیگر فالتو کوڈز

Reed-Solomon اور LRC کوڈز کے علاوہ، بہت سے دوسرے فالتو کوڈز ہیں۔ مختلف فالتو کوڈز مختلف ریاضی کا استعمال کرتے ہیں۔ یہاں کچھ دوسرے فالتو کوڈز ہیں:

• XOR آپریٹر کا استعمال کرتے ہوئے فالتو کوڈ۔ XOR آپریشن n ڈیٹا بلاکس پر کیا جاتا ہے، اور فالتو کوڈز کا 1 بلاک حاصل کیا جاتا ہے، یعنی ایک n+1 اسکیم (n ڈیٹا بلاکس، 1 فالتو کوڈ)۔ میں استعمال کیا جاتا RAID 5، جہاں ڈیٹا کے بلاکس اور فالتو کوڈز سرنی کی تمام ڈسکوں پر چکرا کر لکھے جاتے ہیں۔
• XOR آپریشن پر مبنی یکساں الگورتھم۔ آپ کو فالتو کوڈز کے 2 بلاکس بنانے کی اجازت دیتا ہے، یعنی n+2 اسکیم۔
• XOR آپریشن پر مبنی STAR الگورتھم۔ آپ کو فالتو کوڈز کے 3 بلاکس بنانے کی اجازت دیتا ہے، یعنی n+3 اسکیم۔
• پیرامائڈ کوڈز مائیکروسافٹ کے ایک اور فالتو کوڈ ہیں۔

5. Yandex میں استعمال کریں۔

Yandex کے بنیادی ڈھانچے کے متعدد منصوبے قابل اعتماد ڈیٹا اسٹوریج کے لیے فالتو کوڈ استعمال کرتے ہیں۔ یہاں کچھ مثالیں ہیں:

• MDS اندرونی آبجیکٹ اسٹوریج، جس کے بارے میں میں نے مضمون کے آغاز میں لکھا تھا۔
• YT - Yandex کا MapReduce سسٹم۔
• YDB (Yandex DataBase) - newSQL تقسیم شدہ ڈیٹا بیس۔

MDS LRC فالتو کوڈز، 8-2-2 اسکیم استعمال کرتا ہے۔ فالتو کوڈ کے ساتھ ڈیٹا 12 مختلف DC میں مختلف سرورز میں 3 مختلف ڈسکوں پر لکھا جاتا ہے: ہر DC میں 4 سرور۔ اس بارے میں مزید پڑھیں آرٹیکل.

YT دونوں Reed-Solomon کوڈز (سکیم 6-3) استعمال کرتا ہے، جو سب سے پہلے لاگو کرنے والے تھے، اور LRC فالتو کوڈز (اسکیم 12-2-2)، جس میں LRC کو ذخیرہ کرنے کا ترجیحی طریقہ ہے۔

YDB یکساں طاق پر مبنی فالتو کوڈ استعمال کرتا ہے (شکل 4-2)۔ YDB میں فالتو کوڈز کے بارے میں پہلے سے ہی ہائی لوڈ پر بتایا.

مختلف فالتو کوڈ اسکیموں کا استعمال سسٹمز کے لیے مختلف تقاضوں کی وجہ سے ہے۔ مثال کے طور پر، MDS میں، LRC کا استعمال کرتے ہوئے ذخیرہ کردہ ڈیٹا کو ایک ساتھ 3 DC میں رکھا جاتا ہے۔ ہمارے لیے یہ ضروری ہے کہ اگر کسی بھی DC میں سے 1 ناکام ہوجاتا ہے تو ڈیٹا پڑھنے کے لیے دستیاب رہتا ہے، اس لیے بلاکس کو تمام DCs میں تقسیم کیا جانا چاہیے تاکہ اگر کوئی DC دستیاب نہ ہو تو ناقابل رسائی بلاکس کی تعداد جائز سے زیادہ نہ ہو۔ 8-2-2 اسکیم میں، آپ ہر ڈی سی میں 4 بلاکس رکھ سکتے ہیں، پھر جب کوئی ڈی سی بند ہو جائے گا، تو 4 بلاکس دستیاب نہیں ہوں گے، اور ڈیٹا پڑھا جا سکتا ہے۔ اسے 3 DCs میں رکھتے وقت ہم جو بھی اسکیم منتخب کرتے ہیں، کسی بھی صورت میں (r + l) / n >= 0,5 ہونا چاہیے، یعنی اسٹوریج کی فالتو کم از کم 50% ہوگی۔

YT میں صورتحال مختلف ہے: ہر YT کلسٹر مکمل طور پر 1 DC (مختلف DCs میں مختلف کلسٹرز) میں واقع ہے، اس لیے ایسی کوئی پابندی نہیں ہے۔ 12-2-2 اسکیم 33% فالتو پن فراہم کرتی ہے، یعنی ڈیٹا اسٹور کرنا سستا ہے، اور یہ MDS اسکیم کی طرح بیک وقت 4 ڈسک بند ہونے سے بھی بچ سکتا ہے۔

ڈیٹا سٹوریج اور پروسیسنگ سسٹمز میں فالتو کوڈز کے استعمال کی اور بھی بہت سی خصوصیات ہیں: ڈیٹا ریکوری کی باریکیاں، استفسار کے وقت پر ریکوری کا اثر، ڈیٹا ریکارڈنگ کی خصوصیات وغیرہ۔ میں ان اور دیگر خصوصیات کے بارے میں الگ بات کرنے جا رہا ہوں۔ عملی طور پر فالتو کوڈ کے استعمال کے بارے میں، اگر موضوع دلچسپ ہوگا۔

6. لنکس

1. Reed-Solomon codes اور Galois کھیتوں کے بارے میں مضامین کا ایک سلسلہ: 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. سٹار سکیم: 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