دا هغه څه دي چې بې ځایه ښکاري

بې ځایه کوډونه * په پراخه کچه د کمپیوټر سیسټمونو کې کارول کیږي ترڅو د معلوماتو ذخیره کولو اعتبار زیات کړي. په Yandex کې دوی په ډیری پروژو کې کارول کیږي. د مثال په توګه ، زموږ د داخلي څیز ذخیره کې د نقل پرځای د بې ځایه کوډونو کارول د اعتبار قرباني کولو پرته ملیونونه خوندي کوي. مګر د دوی د پراخه کارونې سره سره ، د بې ځایه کوډونو د کار څرنګوالي روښانه توضیحات خورا لږ دي. هغه څوک چې غواړي پوه شي د نږدې لاندې سره مخ دي (له ويکيپېډيا):

زما نوم Vadim دی، په Yandex کې زه د داخلي څیز ذخیره MDS رامینځته کوم. په دې مقاله کې، زه به په ساده الفاظو کې د بې ځایه کوډونو نظریاتي بنسټونه بیان کړم (ریډ سلیمان او LRC کوډونه). زه به تاسو ته ووایم چې دا څنګه کار کوي، پرته له پیچلي ریاضياتو او نادر شرایطو. په پای کې به زه په Yandex کې د بې ځایه کوډونو کارولو مثالونه وړاندې کړم.

زه به په تفصیل سره یو شمیر ریاضیاتي توضیحات په پام کې ونیسم، مګر زه به د هغو کسانو لپاره لینکونه چمتو کړم څوک چې غواړي ژور ډوب کړي. زه به دا هم یادونه وکړم چې ځینې ریاضیاتي تعریفونه ممکن سخت نه وي، ځکه چې مقاله د ریاضي پوهانو لپاره نه ده، مګر د انجنیرانو لپاره چې غواړي د مسلې په ماهیت پوه شي.

* د انګلیسي ژبې په ادبیاتو کې، بې ځایه کوډونه اکثرا د پاکولو کوډونو په نوم یادیږي.

1. د بې ځایه کوډونو جوهر

د ټولو بې ځایه کوډونو جوهر خورا ساده دی: ډیټا ذخیره کړئ (یا لیږدئ) ترڅو دا له لاسه ورنکړل شي کله چې خطاګانې رامینځته شي (د ډیسک ناکامي ، د ډیټا لیږد غلطی ، او داسې نور).

په ډیری * بې ځایه کوډونو کې، ډاټا په n ډیټا بلاکونو ویشل شوي، د کوم لپاره چې د بې ځایه کوډونو m بلاکونه شمیرل کیږي، په پایله کې د n + m بلاکونو ټولیز. بې ځایه کوډونه په داسې ډول جوړ شوي چې د ډیټا n بلاکونه یوازې د n + m بلاکونو یوې برخې په کارولو سره بیرته ترلاسه کیدی شي. بیا، موږ به یوازې د بلاک بې ځایه کوډونه په پام کې ونیسو، دا هغه دي چې ډاټا په بلاکونو ویشل شوي.

د ډیټا د ټولو n بلاکونو بیرته ترلاسه کولو لپاره ، تاسو اړتیا لرئ لږترلږه n + m بلاکونه ولرئ ، ځکه چې تاسو نشئ کولی یوازې د n-1 بلاک په درلودلو سره n بلاکونه ترلاسه کړئ (په دې حالت کې ، تاسو باید 1 بلاک "د پتلي څخه واخلئ. هوا"). ایا د n + m بلاکونو تصادفي بلاکونه د ټولو معلوماتو بیرته ترلاسه کولو لپاره کافي دي؟ دا د بې ځایه کوډونو ډول پورې اړه لري، د بیلګې په توګه، د ریډ - سلیمان کوډونه تاسو ته اجازه درکوي چې د خپل سري n بلاکونو په کارولو سره ټول معلومات بیرته ترلاسه کړئ، مګر د LRC بې ځایه کوډونه تل نه کوي.

د معلوماتو ذخیره

د ډیټا ذخیره کولو سیسټمونو کې، د یوې قاعدې په توګه، هر یو د ډیټا بلاکس او بې ځایه کوډ بلاکونه جلا ډیسک ته لیکل کیږي. بیا، که یو خپلسري ډیسک ناکام شي، اصلي ډاټا لاهم ساتل کیدی شي او لوستل کیدی شي. ډاټا بیرته ترلاسه کیدی شي حتی که څو ډیسکونه په ورته وخت کې ناکام شي.

د ډاټا انتقال

بې ځایه کوډونه د اعتبار وړ شبکې ته د اعتبار وړ معلوماتو لیږدولو لپاره کارول کیدی شي. لیږدول شوي ډاټا په بلاکونو ویشل شوي، او د بې ځایه کوډونه د دوی لپاره حساب شوي. دواړه ډیټا بلاکونه او د بې ځایه کوډ بلاکونه په شبکه کې لیږدول کیږي. که په خپل سري بلاکونو کې تېروتنې رامنځ ته شي (تر یو ټاکلي شمیر بلاکونو پورې)، ډاټا لاهم په شبکه کې پرته له خطا لیږدول کیدی شي. د مثال په توګه د ریډ - سلیمان کوډونه د نظری مخابراتو لینونو او د سپوږمکۍ مخابراتو کې د معلوماتو لیږدولو لپاره کارول کیږي.

* د بې ځایه کوډونه هم شتون لري چې پکې ډیټا په بلاکونو نه ویشل کیږي ، لکه د هامینګ کوډونه او CRC کوډونه چې په ایترنیټ شبکو کې د ډیټا لیږد لپاره په پراخه کچه کارول کیږي. دا د غلطۍ سمولو کوډ کولو لپاره کوډونه دي، دوی د غلطیو موندلو لپاره ډیزاین شوي، نه د دوی د سمولو لپاره (د هیمینګ کوډ د غلطیو جزوی سمون ته هم اجازه ورکوي).

2. د ریډ - سلیمان کوډونه

د ریډ - سلیمان کوډونه یو له خورا پراخه کارول شوي بې ځایه کوډونو څخه دي چې په 1960s کې ایجاد شوي او لومړی په 1980s کې د کمپیک ډیسکونو د ډله ایز تولید لپاره په پراخه کچه کارول شوي.

د ریډ - سلیمان کوډونو د پوهیدو لپاره دوه مهمې پوښتنې شتون لري: 1) د بې ځایه کوډونو بلاکونو رامینځته کولو څرنګوالی؛ 2) د بې ځایه کوډ بلاکونو په کارولو سره د معلوماتو بیرته ترلاسه کولو څرنګوالی. راځئ چې دوی ته ځوابونه ولټوو.
د سادګۍ لپاره، موږ به نور هم فرض کړو چې n=6 او m=4. نور سکیمونه په نظر کې نیول کیږي.

د بې ځایه کوډ بلاکونو رامینځته کولو څرنګوالی

د بې ځایه کوډونو هر بلاک په خپلواک ډول د نورو څخه شمیرل کیږي. د ډیټا ټول بلاکونه د هر بلاک شمیرلو لپاره کارول کیږي. په لاندې انځور کې، X1-X6 د ډیټا بلاکونه دي، P1-P4 د بې ځایه کوډ بلاکونه دي.

ټول ډیټا بلاکونه باید ورته اندازه وي، او صفر بټونه د سمون لپاره کارول کیدی شي. د بې ځایه شوي کوډ بلاکونه به د ډیټا بلاکونو په څیر ورته اندازه وي. ټول ډیټا بلاکونه په کلمو ویشل شوي (د مثال په توګه، 16 بټونه). راځئ چې ووایو موږ د ډیټا بلاکونه په k کلمو ویشو. بیا به د بې ځایه کوډونو ټول بلاکونه هم په k کلمو وویشل شي.

د هر بې ځایه شوي بلاک د i-th کلمې شمیرلو لپاره، د ټولو ډیټا بلاکونو i-th کلمې به وکارول شي. دوی به د لاندې فورمول له مخې محاسبه شي:

دلته x ارزښتونه د ډیټا بلاکس کلمې دي، p د ریډنډنسی کوډ بلاکس کلمې دي، ټول الفا، بیټا، ګاما او ډیلټا په ځانګړي ډول ټاکل شوي شمیرې دي چې د ټولو i لپاره یو شان دي. دا باید سمدلاسه وویل شي چې دا ټول ارزښتونه عادي شمیرې ندي بلکه د ګالوس ساحې عناصر دي؛ عملیات +، -، *، / هغه عملیات ندي چې موږ ټولو ته پیژندل شوي، مګر ځانګړي عملیات د ګالوس عناصرو باندې معرفي شوي. میدان

ولې د ګالوس ساحو ته اړتیا ده؟

داسې بریښي چې هرڅه ساده دي: موږ ډیټا په بلاکونو ویشو ، بلاکونه په کلمو ویشو ، د ډیټا بلاکونو کلمو په کارولو سره موږ د بې ځایه کوډ بلاکونو ټکي حسابوو - موږ د بې ځایه کوډ بلاکونه ترلاسه کوو. په عموم کې دا څنګه کار کوي ، مګر شیطان په توضیحاتو کې دی:

1. لکه څنګه چې پورته یادونه وشوه، د کلمې اندازه ثابته شوې، زموږ په مثال کې 16 بټونه. د Reed-Solomon کوډونو لپاره پورته فورمول داسې دي چې کله د عادي عددونو په کارولو سره، د p محاسبه کولو پایله ممکن د اعتبار وړ اندازې کلمې په کارولو سره د نمایش وړ نه وي.
2. کله چې د معلوماتو بیرته ترلاسه کول، پورته فورمول به د معادلو سیسټم په توګه وګڼل شي چې باید د معلوماتو بیرته ترلاسه کولو لپاره حل شي. د حل د پروسې په جریان کې، دا ممکن اړین وي چې د یو بل په واسطه د عددونو ویشل، په پایله کې یو ریښتینې شمیره چې د کمپیوټر په حافظه کې په سمه توګه استازیتوب نشي کولی.

دا ستونزې د ریډ - سلیمان کوډونو لپاره د انټیجرونو کارولو مخه نیسي. د ستونزې حل اصلي دی، دا په لاندې ډول تشریح کیدی شي: راځئ چې د ځانګړو شمیرو سره راشي چې د اړتیا وړ اوږدوالی (د بیلګې په توګه، 16 بټ) د کلمو په کارولو سره ښودل کیدی شي، او د ټولو عملیاتو ترسره کولو پایله چې په کې (اضافه) ، فرعي، ضرب، ویش) به د کمپیوټر حافظه کې د اړتیا وړ اوږدوالي کلمو په کارولو سره وړاندې شي.

دا ډول "ځانګړي" شمیرې د ریاضیاتو لخوا د اوږدې مودې لپاره مطالعه شوي؛ دوی ته ساحې ویل کیږي. ساحه د عناصرو یوه ټولګه ده چې د اضافه، کمولو، ضرب او ویش عملیات لري.

Galois* فیلډونه هغه ساحې دي چې د ساحې د هر دوه عناصرو لپاره د هر عملیات (+، -، *، /) ځانګړې پایله لري. د ګالوس ساحې د هغو شمیرو لپاره جوړیدای شي چې د 2: 2، 4، 8، 16، او داسې نور ځواک لري (په حقیقت کې د هر لومړي نمبر p ځواک، مګر په عمل کې موږ یوازې د 2 قوتونو سره علاقه لرو). د مثال په توګه، د 16-bit کلمو لپاره، دا یوه ساحه ده چې 65 عناصر لري، د هرې جوړې لپاره چې تاسو کولی شئ د هر عملیات پایله ومومئ (+, -, *, /). د پورتنیو معادلو څخه د x، p، الفا، بیټا، ګاما، ډیلټا ارزښتونه به د محاسبې لپاره د ګالوس ساحې عناصر وګڼل شي.

په دې توګه، موږ د مساواتو یو سیسټم لرو چې موږ کولی شو د مناسب کمپیوټر پروګرام په لیکلو سره د بې ځایه کوډونو بلاکونه جوړ کړو. د مساواتو د ورته سیسټم په کارولو سره، تاسو کولی شئ د معلوماتو بیا رغونه ترسره کړئ.

* دا یو سخت تعریف ندی، بلکه یو توضیح دی.

د معلوماتو بیرته ترلاسه کولو څرنګوالی

بیا رغولو ته اړتیا ده کله چې ځینې n + m بلاکونه ورک وي. دا دواړه د ډیټا بلاکونه او د بې ځایه کوډ بلاکونه کیدی شي. د ډیټا بلاکونو او/یا بې ځایه کوډ بلاکونو نشتوالی به پدې معنی وي چې اړونده x او/یا p متغیرونه په پورته معادلو کې نامعلوم دي.

د ریډ - سلیمان کوډونو معادلې د معادلو سیسټم په توګه لیدل کیدی شي چې په کې ټول الفا، بیټا، ګاما، ډیلټا ارزښتونه ثابت دي، ټول x او p د شته بلاکونو سره مطابقت لري پیژندل شوي متغیرونه دي، او پاتې x او p. نامعلوم دي

د مثال په توګه، اجازه راکړئ چې د ډیټا بلاکس 1، 2، 3 او د ریډنډنسی کوډ بلاک 2 شتون ونلري، بیا د کلمو د i-th ګروپ لپاره به د مساواتو لاندې سیسټم وي (نامعلومات په سور نښه شوي):

موږ د 4 نامعلومو سره د 4 مساواتو سیسټم لرو، پدې معنی چې موږ کولی شو دا حل کړو او ډاټا بیرته راوړو!

د دې معادلې سیسټم څخه یو شمیر پایلې د ریډ - سلیمان کوډونو لپاره د ډیټا ریکوری په اړه تعقیب کیږي (د ډیټا بلاکس ، m بې ځایه کوډ بلاکونه):

• معلومات بیرته ترلاسه کیدی شي که چیرې کوم m بلاکونه یا لږ څه ورک شوي وي. که چیرې m+1 یا ډیر بلاکونه له لاسه ورکړي، ډاټا نشي بیرته راګرځیدلی: د m + 1 نامعلومو سره د m مساواتو سیسټم حل کول ناممکن دي.
• د حتی یو ډیټا بلاک بیرته ترلاسه کولو لپاره ، تاسو اړتیا لرئ د پاتې بلاکونو څخه کوم n وکاروئ ، او تاسو کولی شئ د بې ځایه کوډونو څخه کار واخلئ.

نور څه ته اړتیا لرئ چې پوه شئ

В описании выше я обхожу стороной ряд важных вопросов, для рассмотрения которых нужно глубже погружаться в математику. В частности, ничего не говорю про следующее:

• د ریډ - سلیمان کوډونو لپاره د معادلې سیسټم باید د نامعلومو ترکیبونو لپاره (بې ساري) حل ولري (له m ​​نامعلومو څخه ډیر نه وي). د دې اړتیا پر بنسټ، د الفا، بیټا، ګاما او ډیلټا ارزښتونه غوره شوي.
• د مساواتو سیسټم باید په اتوماتيک ډول جوړ شي (په دې پورې اړه لري چې کوم بلاکونه شتون نلري) او حل شي.
• موږ اړتیا لرو چې د ګالوس ساحه جوړه کړو: د یوې ټاکلې کلمې اندازې لپاره، د هر دوه عناصرو لپاره د هر عملیات (+، -، *، /) پایله ومومئ.

د مقالې په پای کې د دې مهمو مسلو په اړه د ادبیاتو حوالې شتون لري.

د ن او م انتخاب

څنګه په عمل کې n او m غوره کړئ؟ په عمل کې، د ډیټا ذخیره کولو سیسټمونو کې، بې ځایه کوډونه د ځای خوندي کولو لپاره کارول کیږي، نو m تل د n څخه لږ غوره کیږي. د دوی ځانګړي ارزښتونه په یو شمیر فکتورونو پورې اړه لري، په شمول:

• د معلوماتو ذخیره کولو اعتبار. هرڅومره لوی m ، د ډیسک ناکامیو شمیر خورا ډیر وي چې ژوندي پاتې کیدی شي ، دا د اعتبار لوړ دی.
• بې ځایه ذخیره کول. څومره چې د m/n نسبت لوړ وي، هغومره به د ذخیره کولو بې ځایه کېدنه لوړه وي، او سیسټم به ډیر ګران وي.
• د پروسس کولو وخت غوښتنه وکړئ. څومره چې n + m لوی وي، د غوښتنو لپاره د ځواب وخت به اوږد وي. څرنګه چې د معلوماتو لوستل (د بیا رغونې پرمهال) په مختلف ډیسکونو کې زیرمه شوي n بلاکونو لوستلو ته اړتیا لري ، نو د لوستلو وخت به د ورو ډیسک لخوا ټاکل کیږي.

سربیره پردې ، په څو DCs کې د معلوماتو ذخیره کول د n او m انتخاب باندې اضافي محدودیتونه وضع کوي: که چیرې 1 DC بند وي ، ډاټا باید لاهم د لوستلو لپاره شتون ولري. د مثال په توګه، کله چې په 3 DC کې ډاټا ذخیره کول، لاندې شرایط باید پوره شي: m >= n/2، که نه نو داسې حالت شتون لري چې ډاټا د لوستلو لپاره شتون نلري کله چې 1 DC بند شي.

3. LRC - د محلي بیارغونې کوډونه

د ریډ - سلیمان کوډونو په کارولو سره د معلوماتو بیرته ترلاسه کولو لپاره ، تاسو باید د خپل سري ډیټا بلاکونه وکاروئ. دا د توزیع شوي ډیټا ذخیره کولو سیسټمونو لپاره خورا مهم زیان دی ، ځکه چې په یو مات شوي ډیسک کې د ډیټا بحالولو لپاره ، تاسو باید د ډیری نورو څخه ډیټا ولولئ ، په ډیسکونو او شبکه کې لوی اضافي بار رامینځته کړئ.

ترټولو عام غلطۍ د ډیسک د ناکامۍ یا ډیر بار له امله د ډیټا یو بلاک ته لاسرسی نه دی. ایا دا ممکنه ده چې په دې (خورا عام) قضیه کې د معلوماتو د بیا رغونې لپاره اضافي بار کم کړئ؟ دا معلومه شوه چې تاسو کولی شئ: د دې هدف لپاره د LRC بې ځایه کوډونه شتون لري.

LRC (د ځایی بیارغونې کوډونه) بې ځایه کوډونه دي چې د مایکروسافټ لخوا په وینډوز Azure ذخیره کې د کارولو لپاره اختراع شوي. د 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 کې د ریډ - سلیمان کوډونو سره ورته والی سره ترسره کیږي. د بې ځایه کوډ بلاکونو کلمو شمیرلو لپاره معادل به دا وي:

د الفا، بیټا، ګاما، ډیلټا شمیرو غوره کولو لپاره، یو شمیر شرایط باید پوره شي ترڅو د معلوماتو د بیا رغونې امکان تضمین کړي (یعنې د مساوي سیسټم حل کول). تاسو کولی شئ د دوی په اړه نور ولولئ مقالې.
همدارنګه په عمل کې، د XOR عملیات د محلي بې ځایه کوډونو P3، P4 محاسبه کولو لپاره کارول کیږي.

د LRC لپاره د مساواتو سیسټم څخه یو شمیر پایلې تعقیبوي:

• د هر 1 ډیټا بلاک بیرته ترلاسه کولو لپاره ، دا د n/l بلاکونو لوستلو لپاره کافي دي (زموږ په مثال کې n/2).
• که چیرې r + l بلاکونه شتون ونلري، او ټول بلاکونه په یوه ګروپ کې شامل شوي وي، نو بیا ډاټا نشي ساتل کیدی. دا د مثال سره تشریح کول اسانه دي. اجازه راکړئ چې بلاکونه X1–X3 او P3 شتون ونلري: دا زموږ په قضیه کې 4 د ورته ګروپ څخه r + l بلاکونه دي. بیا موږ د 3 نامعلومو سره د 4 مساواتو سیسټم لرو چې نشي حل کیدی.
• په نورو ټولو قضیو کې د r + l بلاکونو شتون شتون نلري (کله چې لږترلږه یو بلاک د هرې ډلې څخه شتون ولري) ، په LRC کې ډیټا بحال کیدی شي.

په دې توګه، LRC د ریډ - سلیمان کوډونه د واحد غلطیو وروسته د معلوماتو بیرته راګرځولو کې ښه کوي. د ریډ - سلیمان کوډونو کې ، د ډیټا حتی یو بلاک بیرته ترلاسه کولو لپاره ، تاسو اړتیا لرئ د n بلاکونو کارولو ته اړتیا ولرئ ، او په LRC کې ، د ډیټا یو بلاک بیرته ترلاسه کولو لپاره ، دا د n/l بلاکونو کارولو لپاره کافي دي (زموږ په مثال کې n/2). له بلې خوا، LRC د ریډ - سلیمان کوډونو څخه ټیټ دی د ډیرو اجازه وړ غلطیتونو له مخې. په پورته مثالونو کې، د ریډ - سلیمان کوډونه کولی شي د هر 4 غلطیو لپاره ډاټا بیرته ترلاسه کړي، او د LRC لپاره د 2 غلطیو 4 ترکیبونه شتون لري کله چې ډاټا بیرته نشي ترلاسه کیدی.

هغه څه چې ډیر مهم دي په ځانګړي حالت پورې اړه لري، مګر ډیری وختونه په اضافي بار کې سپما چې LRC چمتو کوي د یو څه لږ باوري ذخیرې څخه ډیر وي.

4. نور بې ځایه کوډونه

د ریډ - سلیمان او 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) - نوی ایس کیو ایل ویشل شوی ډیټابیس.

MDS د LRC بې ځایه کوډونه کاروي، 8-2-2 سکیم. د بې ځایه کوډونو سره ډیټا په 12 مختلف DC کې په مختلف سرورونو کې 3 مختلف ډیسکونو ته لیکل کیږي: په هر DC کې 4 سرورونه. په دې اړه نور ولولئ مقالې.

YT دواړه د ریډ-سلیمون کوډونه (سکیم 6-3) کاروي، کوم چې لومړی پلي کول وو، او د LRC بې ځایه کوډونه (سکیم 12-2-2)، چې LRC د غوره ذخیره کولو طریقه ده.

YDB د مساوي پر بنسټ بې ځایه کوډونه کاروي (شکل 4-2). لا دمخه په YDB کې د بې ځایه کوډونو په اړه په Highload وویل.

د مختلف بې ځایه کوډ سکیمونو کارول د سیسټمونو لپاره د مختلف اړتیاو له امله دي. د مثال په توګه، په MDS کې، د LRC په کارولو سره زیرمه شوي معلومات په یو وخت کې په 3 DC کې ځای پرځای شوي. دا زموږ لپاره مهمه ده چې ډاټا د لوستلو لپاره شتون لري که چیرې د هرې DCs څخه 1 ناکام شي نو بلاکونه باید په DCs کې وویشل شي ترڅو که چیرې کوم DC شتون ونلري نو د لاسرسي وړ بلاکونو شمیر د جواز څخه ډیر نه وي. په 8-2-2 سکیم کې، تاسو کولی شئ په هر DC کې 4 بلاکونه ځای په ځای کړئ، بیا کله چې کوم DC بند شي، 4 بلاکونه به شتون ونلري، او ډاټا لوستل کیدی شي. هر هغه سکیم چې موږ یې غوره کوو کله چې دا په 3 DCs کې ځای په ځای کړو، په هر حالت کې باید (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 په اړه د مایکروسافټ مقاله: 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