این چیزی است که افزونگی به نظر می رسد

کدهای افزونگی* به طور گسترده در سیستم های کامپیوتری برای افزایش قابلیت اطمینان ذخیره سازی داده ها استفاده می شوند. در Yandex آنها در بسیاری از پروژه ها استفاده می شوند. به عنوان مثال، استفاده از کدهای افزونگی به جای تکرار در ذخیره سازی اشیاء داخلی، میلیون ها نفر را بدون از بین بردن قابلیت اطمینان، صرفه جویی می کند. اما علیرغم استفاده گسترده از آنها، توضیحات واضح در مورد نحوه عملکرد کدهای افزونگی بسیار نادر است. کسانی که می خواهند بفهمند تقریباً با موارد زیر روبرو می شوند (از ویکی پدیا):

نام من Vadim است، در Yandex در حال توسعه MDS ذخیره سازی اشیاء داخلی هستم. در این مقاله به بیان ساده مبانی نظری کدهای افزونگی (کدهای Reed-Solomon و LRC) می پردازم. من به شما خواهم گفت که چگونه کار می کند، بدون ریاضیات پیچیده و اصطلاحات نادر. در پایان مثال هایی از استفاده از کدهای افزونگی در Yandex ارائه خواهم داد.

من تعدادی از جزئیات ریاضی را با جزئیات در نظر نخواهم گرفت، اما پیوندهایی را برای کسانی که می خواهند عمیق تر غواصی کنند ارائه خواهم کرد. همچنین متذکر می شوم که برخی از تعاریف ریاضی ممکن است سختگیرانه نباشند، زیرا این مقاله برای ریاضیدانان در نظر گرفته نشده است، بلکه برای مهندسانی است که می خواهند ماهیت موضوع را درک کنند.

* در ادبیات انگلیسی زبان، کدهای اضافی اغلب کدهای پاک کردن نامیده می شوند.

1. ماهیت کدهای افزونگی

ماهیت همه کدهای افزونگی بسیار ساده است: داده ها را ذخیره کنید (یا انتقال دهید) به طوری که هنگام بروز خطا (شکست دیسک، خطاهای انتقال داده و غیره) از بین نرود.

در اکثر کدهای افزونگی*، داده ها به n بلوک داده تقسیم می شوند که برای آنها m بلوک کدهای افزونگی شمارش می شود و در مجموع n + m بلوک ایجاد می شود. کدهای افزونگی به گونه ای ساخته شده اند که n بلوک داده را می توان تنها با استفاده از بخشی از بلوک های n + m بازیابی کرد. در مرحله بعد، ما فقط کدهای افزونگی بلوک را در نظر می گیریم، یعنی آنهایی که در آنها داده ها به بلوک ها تقسیم می شوند.

برای بازیابی تمام n بلوک داده، باید حداقل n از n + m بلوک داشته باشید، زیرا با داشتن تنها n-1 بلوک نمی توانید n بلوک دریافت کنید (در این مورد، باید 1 بلوک را از بین ببرید. هوا»). آیا n بلوک تصادفی از n + m بلوک برای بازیابی همه داده ها کافی است؟ این بستگی به نوع کدهای افزونگی دارد، به عنوان مثال، کدهای Reed-Solomon به شما اجازه می دهند تا همه داده ها را با استفاده از n بلوک دلخواه بازیابی کنید، اما کدهای افزونگی LRC همیشه اینطور نیستند.

ذخیره سازی داده ها

در سیستم های ذخیره سازی داده ها، به عنوان یک قاعده، هر یک از بلوک های داده و بلوک های کد افزونگی در یک دیسک جداگانه نوشته می شود. سپس، اگر یک دیسک دلخواه از کار بیفتد، داده های اصلی همچنان می توانند بازیابی و خوانده شوند. حتی اگر چندین دیسک به طور همزمان از کار بیفتد، می توان اطلاعات را بازیابی کرد.

انتقال داده

کدهای افزونگی می توانند برای انتقال مطمئن داده ها از طریق یک شبکه غیرقابل اعتماد استفاده شوند. داده های ارسال شده به بلوک ها تقسیم می شوند و کدهای افزونگی برای آنها محاسبه می شود. هم بلوک های داده و هم بلوک های کد افزونگی از طریق شبکه منتقل می شوند. اگر خطا در بلوک های دلخواه (تا تعداد مشخصی از بلوک ها) رخ دهد، همچنان می توان داده ها را بدون خطا از طریق شبکه منتقل کرد. برای مثال، کدهای Reed-Solomon برای انتقال داده ها از طریق خطوط ارتباطی نوری و در ارتباطات ماهواره ای استفاده می شوند.

* کدهای افزونگی نیز وجود دارند که در آنها داده ها به بلوک تقسیم نمی شوند، مانند کدهای Hamming و کدهای CRC که به طور گسترده برای انتقال داده در شبکه های اترنت استفاده می شود. اینها کدهایی برای کدگذاری تصحیح خطا هستند، آنها برای شناسایی خطاها و نه برای تصحیح آنها طراحی شده اند (کد Hamming همچنین تصحیح جزئی خطاها را امکان پذیر می کند).

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

کدهای Reed-Solomon یکی از پرکاربردترین کدهای افزونگی هستند که در دهه 1960 اختراع شد و اولین بار در دهه 1980 به طور گسترده برای تولید انبوه دیسک های فشرده استفاده شد.

دو سوال کلیدی برای درک کدهای Reed-Solomon وجود دارد: 1) نحوه ایجاد بلوک‌های کدهای افزونگی. 2) نحوه بازیابی اطلاعات با استفاده از بلوک های کد افزونگی. بیایید پاسخ آنها را پیدا کنیم.
برای سادگی، بیشتر فرض می کنیم که n=6 و m=4. سایر طرح ها با قیاس در نظر گرفته می شوند.

نحوه ایجاد بلوک کد افزونگی

هر بلوک از کدهای افزونگی مستقل از بقیه شمارش می شود. تمام n بلوک داده برای شمارش هر بلوک استفاده می شود. در نمودار زیر، X1-X6 بلوک های داده، P1-P4 بلوک های کد افزونگی هستند.

همه بلوک های داده باید اندازه یکسانی داشته باشند و می توان از بیت های صفر برای تراز کردن استفاده کرد. بلوک‌های کد افزونگی حاصل به اندازه بلوک‌های داده خواهد بود. تمام بلوک های داده به کلمات (مثلاً 16 بیت) تقسیم می شوند. فرض کنید بلوک های داده را به k کلمه تقسیم کردیم. سپس تمام بلوک‌های کدهای افزونگی نیز به k کلمه تقسیم می‌شوند.

برای شمارش i-امین کلمه هر بلوک افزونگی، کلمه i-ام تمام بلوک های داده استفاده می شود. آنها طبق فرمول زیر محاسبه خواهند شد:

در اینجا مقادیر x کلمات بلوک‌های داده، p کلمات بلوک‌های کد افزونگی هستند، همه آلفا، بتا، گاما و دلتا اعداد ویژه انتخاب‌شده‌ای هستند که برای همه i یکسان هستند. باید فوراً گفت که همه این مقادیر اعداد معمولی نیستند، بلکه عناصر میدان Galois هستند؛ عملیات +، -، *، / عملیاتی برای همه ما آشنا نیستند، بلکه عملیات ویژه ای هستند که روی عناصر Galois معرفی شده اند. رشته.

چرا میدان های Galois مورد نیاز است؟

به نظر می رسد همه چیز ساده است: ما داده ها را به بلوک ها، بلوک ها را به کلمات تقسیم می کنیم، با استفاده از کلمات بلوک های داده، کلمات بلوک های کد افزونگی را می شماریم - بلوک های کد افزونگی را دریافت می کنیم. به طور کلی این روش کار می کند، اما شیطان در جزئیات است:

1. همانطور که در بالا گفته شد، اندازه کلمه ثابت است، در مثال ما 16 بیت. فرمول های بالا برای کدهای Reed-Solomon به گونه ای است که هنگام استفاده از اعداد صحیح معمولی، نتیجه محاسبه p ممکن است با استفاده از یک کلمه با اندازه معتبر قابل نمایش نباشد.
2. هنگام بازیابی اطلاعات، فرمول های بالا به عنوان یک سیستم معادلات در نظر گرفته می شوند که برای بازیابی داده ها باید حل شوند. در طول فرآیند حل، ممکن است لازم باشد اعداد صحیح را بر یکدیگر تقسیم کنیم و در نتیجه یک عدد واقعی به دست می‌آید که نمی‌تواند به طور دقیق در حافظه کامپیوتر نمایش داده شود.

این مشکلات از استفاده از اعداد صحیح برای کدهای Reed-Solomon جلوگیری می کند. راه حل مشکل اصلی است، می توان آن را به شرح زیر توصیف کرد: بیایید با اعداد خاصی که می توانند با استفاده از کلمات با طول مورد نیاز (به عنوان مثال، 16 بیت) نمایش داده شوند، و نتیجه انجام تمام عملیات هایی که بر روی آنها (جمع) ، تفریق، ضرب، تقسیم) نیز با استفاده از کلمات به طول مورد نیاز در حافظه کامپیوتر ارائه می شود.

چنین اعداد "ویژه" برای مدت طولانی توسط ریاضیات مورد مطالعه قرار گرفته اند، آنها را فیلد می نامند. فیلد مجموعه ای از عناصر با عملیات جمع، تفریق، ضرب و تقسیم برای آنها تعریف شده است.

فیلدهای Galois* فیلدهایی هستند که برای هر دو عنصر فیلد یک نتیجه منحصر به فرد از هر عملیات (+، -، *، /) وجود دارد. میدان های گالوا را می توان برای اعدادی که توان های 2 هستند ساخت: 2، 4، 8، 16 و غیره (در واقع توان های هر عدد اول p، اما در عمل ما فقط به توان های 2 علاقه مندیم). به عنوان مثال، برای کلمات 16 بیتی، این یک فیلد حاوی 65 عنصر است که برای هر جفت آن می توانید نتیجه هر عملیات (+، -، *، /) را پیدا کنید. مقادیر x، p، آلفا، بتا، گاما، دلتا از معادلات بالا عناصر میدان Galois برای محاسبات در نظر گرفته خواهند شد.

بنابراین، ما یک سیستم معادلات داریم که با نوشتن یک برنامه کامپیوتری مناسب می‌توانیم بلوک‌هایی از کدهای افزونگی بسازیم. با استفاده از همان سیستم معادلات، می توانید بازیابی اطلاعات را انجام دهید.

* این یک تعریف دقیق نیست، بلکه یک توصیف است.

نحوه بازیابی اطلاعات

زمانی که برخی از بلوک‌های n + m گم شده باشند، به بازیابی نیاز است. اینها می توانند هم بلوک های داده و هم بلوک های کد افزونگی باشند. عدم وجود بلوک های داده و/یا بلوک های کد افزونگی به این معنی است که متغیرهای x و/یا p متناظر در معادلات بالا ناشناخته هستند.

معادلات کدهای Reed-Solomon را می توان به عنوان یک سیستم معادلات مشاهده کرد که در آن همه مقادیر آلفا، بتا، گاما، دلتا ثابت هستند، تمام x و p مربوط به بلوک های موجود متغیرهای شناخته شده هستند، و x و p باقیمانده ناشناخته هستند.

به عنوان مثال، اجازه دهید بلوک های داده 1، 2، 3 و کد افزونگی بلوک 2 در دسترس نباشند، سپس برای گروه i-امین کلمات، سیستم معادلات زیر وجود خواهد داشت (ناشناخته ها با رنگ قرمز مشخص شده اند):

ما یک سیستم 4 معادله با 4 مجهول داریم، یعنی می توانیم آن را حل کنیم و داده ها را بازیابی کنیم!

از این سیستم معادلات تعدادی نتیجه گیری در مورد بازیابی اطلاعات برای کدهای Reed-Solomon (n بلوک داده، m بلوک کد اضافی):

• در صورت از بین رفتن m بلوک یا کمتر، می توان داده ها را بازیابی کرد. اگر بلوک های m+1 یا بیشتر گم شوند، داده ها قابل بازیابی نیستند: حل یک سیستم معادلات m با مجهولات m + 1 غیرممکن است.
• برای بازیابی حتی یک بلوک داده، باید از هر n بلوک باقی مانده استفاده کنید و می توانید از هر کد افزونگی استفاده کنید.

چه چیز دیگری باید بدانید

در توضیحات بالا، من از تعدادی از مسائل مهمی که نیاز به بررسی عمیق‌تر در ریاضیات دارند اجتناب می‌کنم. به ویژه در مورد موارد زیر چیزی نمی گویم:

• سیستم معادلات کدهای رید-سولومون باید برای هر ترکیبی از مجهولات (حداکثر m مجهول) راه حل (یکتا) داشته باشد. بر اساس این نیاز، مقادیر آلفا، بتا، گاما و دلتا انتخاب می شوند.
• یک سیستم معادلات باید بتواند به طور خودکار ساخته شود (بسته به اینکه کدام بلوک در دسترس نیست) و حل شود.
• ما باید یک فیلد Galois بسازیم: برای اندازه کلمه معین، بتوانیم نتیجه هر عملیات (+، -، *، /) را برای هر دو عنصر پیدا کنیم.

در پایان مقاله به ادبیات مربوط به این موضوعات مهم اشاره شده است.

انتخاب n و m

چگونه 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 (کدهای بازسازی محلی) کدهای افزونگی هستند که توسط مایکروسافت برای استفاده در Windows Azure Storage اختراع شده اند. ایده LRC تا حد امکان ساده است: تمام بلوک های داده را به دو گروه (یا بیشتر) تقسیم کنید و بخشی از بلوک های کد افزونگی را برای هر گروه به طور جداگانه بخوانید. سپس برخی از بلوک‌های کد افزونگی با استفاده از همه بلوک‌های داده شمارش می‌شوند (در LRC به آنها کدهای افزونگی جهانی می‌گویند) و برخی - با استفاده از یکی از دو گروه بلوک داده (به آنها کدهای افزونگی محلی می‌گویند).

LRC با سه عدد نشان داده می شود: nrl، که در آن n تعداد بلوک های داده، r تعداد بلوک های کد افزونگی جهانی، l تعداد بلوک های کد افزونگی محلی است. برای خواندن داده در زمانی که یک بلوک داده در دسترس نیست، باید فقط بلوک های n/l را بخوانید - این مقدار l برابر کمتر از کدهای Reed-Solomon است.

به عنوان مثال، طرح LRC 6-2-2 را در نظر بگیرید. X1–X6 — 6 بلوک داده، P1، P2 — 2 بلوک افزونگی جهانی، P3، P4 — 2 بلوک افزونگی محلی.

بلوک‌های کد افزونگی P1، P2 با استفاده از تمام بلوک‌های داده شمارش می‌شوند. بلوک کد افزونگی P3 - با استفاده از بلوک های داده X1-X3، بلوک کد افزونگی P4 - با استفاده از بلوک های داده X4-X6.

بقیه در LRC با قیاس با کدهای Reed-Solomon انجام می شود. معادلات شمارش کلمات بلوک های کد افزونگی به صورت زیر خواهد بود:

برای انتخاب اعداد آلفا، بتا، گاما، دلتا، یکسری شرایط باید رعایت شود تا امکان بازیابی اطلاعات (یعنی حل سیستم معادله) تضمین شود. می توانید در مورد آنها بیشتر بخوانید مقاله.
همچنین در عمل، عملیات 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.
• الگوریتم STAR بر اساس عملیات XOR. به شما امکان می دهد 3 بلوک از کدهای افزونگی بسازید، یعنی طرح n+3.
• کدهای هرمی یکی دیگر از کدهای افزونگی مایکروسافت است.

5. استفاده در Yandex

تعدادی از پروژه های زیرساختی Yandex از کدهای افزونگی برای ذخیره اطلاعات قابل اعتماد استفاده می کنند. در اینجا چند نمونه آورده شده است:

• ذخیره سازی اشیاء داخلی MDS که در ابتدای مقاله در مورد آن نوشتم.
• YT - سیستم MapReduce یاندکس.
• YDB (Yandex DataBase) - پایگاه داده توزیع شده newSQL.

MDS از کدهای افزونگی LRC، طرح 8-2-2 استفاده می کند. داده ها با کدهای افزونگی در 12 دیسک مختلف در سرورهای مختلف در 3 DC مختلف نوشته می شوند: 4 سرور در هر DC. در این مورد بیشتر بخوانید مقاله.

YT هم از کدهای Reed-Solomon (طرح 6-3) که اولین بار پیاده سازی شد و هم از کدهای افزونگی LRC (طرح 12-2-2) استفاده می کند که LRC روش ذخیره سازی ترجیحی است.

YDB از کدهای افزونگی مبتنی بر زوج و فرد استفاده می کند (شکل 4-2). درباره کدهای افزونگی در YDB در حال حاضر در هایلود گفته شد.

استفاده از طرح های کد افزونگی مختلف به دلیل نیازهای متفاوت برای سیستم ها است. به عنوان مثال، در MDS، داده های ذخیره شده با استفاده از LRC به طور همزمان در 3 DC قرار می گیرند. برای ما مهم است که در صورت خرابی 1 مورد از هر DC، داده‌ها برای خواندن در دسترس باقی بماند، بنابراین بلوک‌ها باید در بین DCها توزیع شوند تا در صورت در دسترس نبودن هر DC، تعداد بلوک‌های غیرقابل دسترسی بیشتر از حد مجاز نباشد. در طرح 8-2-2، می توانید 4 بلوک را در هر DC قرار دهید، سپس هنگامی که هر DC خاموش است، 4 بلوک در دسترس نخواهد بود و داده ها قابل خواندن هستند. هر طرحی که هنگام قرار دادن آن در 3 DC انتخاب کنیم، در هر صورت باید (r + l) / n >= 0,5 باشد، یعنی افزونگی ذخیره سازی حداقل 50٪ خواهد بود.

در YT وضعیت متفاوت است: هر خوشه YT به طور کامل در 1 DC قرار دارد (خوشه های مختلف در DC های مختلف)، بنابراین چنین محدودیتی وجود ندارد. طرح 12-2-2 33 درصد افزونگی را فراهم می کند، یعنی ذخیره داده ها ارزان تر است، و همچنین می تواند تا 4 قطع همزمان دیسک، درست مانند طرح MDS، زنده بماند.

استفاده از کدهای افزونگی در سیستم‌های ذخیره‌سازی و پردازش داده‌ها، ویژگی‌های بسیار بیشتری دارد: تفاوت‌های ظریف بازیابی اطلاعات، تأثیر بازیابی بر زمان اجرای پرس‌وجو، ویژگی‌های ضبط داده‌ها و غیره. قصد دارم به طور جداگانه در مورد این ویژگی‌ها و سایر ویژگی‌ها صحبت کنم. استفاده از کدهای افزونگی در عمل، اگر موضوع جالب باشد.

6. پیوندها

1. مجموعه ای از مقالات در مورد کدهای Reed-Solomon و زمینه های 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. طرح 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. کدهای افزونگی در 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