هذا ما يبدو عليه التكرار
تُستخدم رموز التكرار * على نطاق واسع في أنظمة الكمبيوتر لزيادة موثوقية تخزين البيانات. يستخدمهم Yandex في الكثير من المشاريع. على سبيل المثال ، يؤدي استخدام رموز التكرار بدلاً من النسخ المتماثل في وحدة تخزين العناصر الداخلية لدينا إلى توفير الملايين دون المساس بالموثوقية. ولكن على الرغم من توزيعها الواسع ، إلا أن الوصف الواضح لكيفية عمل رموز التكرار نادر جدًا. أولئك الذين يريدون أن يفهموا يواجهون شيئًا مثل التالي (من ):
اسمي فاديم ، في Yandex أقوم بتطوير وحدة تخزين كائنات MDS داخلية. في هذه المقالة ، سأصف بعبارات بسيطة الأسس النظرية لرموز التكرار (أكواد Reed-Solomon و LRC). سأخبرك كيف يعمل ، بدون رياضيات معقدة ومصطلحات نادرة. في النهاية ، سأقدم أمثلة على استخدام أكواد التكرار في Yandex.
لن أخوض في عدد من التفاصيل الرياضية بالتفصيل ، لكنني سأقدم روابط لأولئك الذين يريدون الغوص بشكل أعمق. ألاحظ أيضًا أن بعض التعريفات الرياضية قد لا تكون صارمة ، لأن المقالة ليست مخصصة لعلماء الرياضيات ، ولكن للمهندسين الذين يرغبون في فهم جوهر المسألة.
* في الأدب الإنجليزي ، غالبًا ما يشار إلى رموز التكرار باسم رموز المحو.
1. جوهر رموز التكرار
جوهر جميع رموز التكرار بسيط للغاية: تخزين (أو نقل) البيانات بحيث لا تختفي عند حدوث أخطاء (فشل القرص ، أخطاء نقل البيانات ، إلخ).
في معظم * أكواد التكرار ، يتم تقسيم البيانات إلى n من كتل البيانات ، والتي يتم حساب m كتل من رموز التكرار ، لإجمالي كتل n + m. يتم إنشاء أكواد التكرار بطريقة تجعل من الممكن استرداد n من كتل البيانات باستخدام جزء صغير فقط من كتل n + m. علاوة على ذلك ، سننظر فقط في رموز التكرار ، أي تلك التي يتم فيها تقسيم البيانات إلى كتل.
لاستعادة جميع الكتل n من البيانات ، تحتاج إلى الحصول على n من الكتل n + m على الأقل ، نظرًا لأنه لا يمكنك الحصول على n من الكتل مع كتل n-1 فقط (في هذه الحالة ، يجب أن تأخذ كتلة واحدة "من فراغ" "). هل n كتل عشوائية من كتل n + m كافية لاستعادة جميع البيانات؟ يعتمد ذلك على نوع أكواد التكرار ، على سبيل المثال ، تسمح لك أكواد Reed-Solomon باستعادة جميع البيانات باستخدام كتل n عشوائية ، وأكواد التكرار LRC لا تفعل ذلك دائمًا.
تخزين البيانات
في أنظمة تخزين البيانات ، كقاعدة عامة ، تتم كتابة كل من كتل البيانات وكتل رموز التكرار على قرص منفصل. بعد ذلك ، إذا فشل قرص عشوائي ، فلا يزال من الممكن استعادة البيانات الأصلية وقراءتها. يمكن استرداد البيانات حتى في حالة فشل عدة أقراص في نفس الوقت.
نقل البيانات
يمكن استخدام رموز التكرار لنقل البيانات بأمان عبر شبكة غير موثوق بها. يتم تقسيم البيانات المرسلة إلى كتل ، ويتم احتساب رموز التكرار لها. يتم إرسال كتل البيانات وكتل رموز التكرار عبر الشبكة. إذا حدثت أخطاء في الكتل العشوائية (حتى عدد معين من الكتل) ، فلا يزال من الممكن نقل البيانات بدون أخطاء عبر الشبكة. تُستخدم أكواد Reed-Solomon ، على سبيل المثال ، لنقل البيانات عبر خطوط الاتصالات الضوئية وفي اتصالات الأقمار الصناعية.
* هناك أيضًا رموز تكرار لا يتم فيها تقسيم البيانات إلى كتل ، مثل أكواد هامنج ورموز CRC ، والتي تستخدم على نطاق واسع لنقل البيانات في شبكات Ethernet. هذه رموز لترميز تصحيح الأخطاء ، وهي مصممة لاكتشاف الأخطاء ، وليس لتصحيحها (يسمح لك رمز Hamming أيضًا بتصحيح الأخطاء جزئيًا).
2. رموز ريد سليمان
تعد رموز Reed-Solomon واحدة من أكثر رموز التكرار استخدامًا ، وقد تم اختراعها في وقت مبكر من الستينيات واستخدمت لأول مرة على نطاق واسع في الثمانينيات للإنتاج التسلسلي للأقراص المدمجة.
هناك سؤالان أساسيان لفهم رموز Reed-Solomon: 1) كيفية إنشاء كتل من رموز التكرار. 2) كيفية استرداد البيانات باستخدام كتل من رموز التكرار. دعونا نجد إجابات لهم.
للتبسيط ، سنفترض أيضًا أن n = 6 و m = 4. يتم النظر في المخططات الأخرى عن طريق القياس.
كيفية إنشاء كتل من رموز التكرار
يتم اعتبار كل مجموعة من رموز التكرار بشكل مستقل عن المجموعات الأخرى. يتم استخدام جميع كتل البيانات n لحساب كل كتلة. في الرسم البياني أدناه ، X1-X6 عبارة عن كتل بيانات ، و P1-P4 عبارة عن كتل رموز متكررة.
يجب أن تكون جميع كتل البيانات بنفس الحجم ، ويمكن استخدام بتات صفرية للمحاذاة. كتل التكرار المتلقاة سيكون لها نفس حجم كتل البيانات. يتم تقسيم جميع مجموعات البيانات إلى كلمات (على سبيل المثال ، 16 بت لكل منها). لنفترض أننا قسمنا كتل البيانات إلى كلمات k. ثم سيتم أيضًا تقسيم جميع مجموعات رموز التكرار إلى كلمات k.
لحساب الكلمة i لكل فدرة تكرار ، سيتم استخدام الكلمات i لكل كتل البيانات. سيتم حسابها وفقًا للصيغة التالية:
هنا تكون قيم x عبارة عن كلمات كتلة بيانات ، و p هي كلمات كتلة رمز التكرار ، وجميع أرقام alpha و beta و gamma و delta هي أرقام محددة خصيصًا ، وهو نفس الشيء بالنسبة لجميع i. يجب أن يقال على الفور أن كل هذه القيم ليست أرقامًا عادية ، ولكن عناصر حقل جالوا ، والعمليات + ، - ، * ، / ليست عمليات مألوفة لنا جميعًا ، ولكنها عمليات خاصة مقدمة على عناصر من حقل جالوا.
لماذا هناك حاجة إلى حقول جالوا
يبدو أن كل شيء بسيط: نقسم البيانات إلى كتل ، كتل - إلى كلمات ، باستخدام كلمات كتل البيانات ، نحسب كلمات كتل من رموز التكرار - نحصل على مجموعات من رموز التكرار. بشكل عام هذه هي طريقة عملها ، ولكن الشيطان يكمن في التفاصيل:
- كما ذكرنا أعلاه ، حجم الكلمة ثابت ، في مثالنا 16 بت. الصيغ أعلاه لرموز Reed-Solomon هي أنه عند استخدام الأعداد الصحيحة العادية ، قد لا تكون نتيجة حساب p قابلة للتمثيل باستخدام كلمة ذات حجم قانوني.
- عند استعادة البيانات ، سيتم التعامل مع الصيغ أعلاه كنظام من المعادلات التي يجب حلها لاستعادة البيانات. في عملية الحل ، قد يصبح من الضروري تقسيم الأعداد الصحيحة على بعضها البعض ، مما ينتج عنه رقم حقيقي لا يمكن تمثيله بدقة في ذاكرة الكمبيوتر.
تمنع هذه المشكلات استخدام الأعداد الصحيحة لرموز Reed-Solomon. حل المشكلة أصلي ويمكن وصفه على النحو التالي: لنخرج بأرقام خاصة يمكن تمثيلها باستخدام كلمات بالطول المطلوب (على سبيل المثال ، 16 بت) ، ونتيجة إجراء جميع العمليات التي (إضافة) ، الطرح ، الضرب ، القسمة) في ذاكرة الكمبيوتر باستخدام كلمات من الطول المطلوب.
لطالما درست الرياضيات هذه الأرقام "الخاصة" ، ويطلق عليها اسم الحقول. الحقل عبارة عن مجموعة من العناصر مع تحديد عمليات الجمع والطرح والضرب والقسمة لها.
حقول Galois * هي الحقول التي توجد لها نتيجة فريدة لكل عملية (+ ، - ، * ، /) لأي عنصرين من عناصر الحقل. يمكن إنشاء حقول الوا للأعداد التي هي قوى 2: 2 ، 4 ، 8 ، 16 ، وما إلى ذلك (في الواقع قوة أي عدد أولي p ، لكن من الناحية العملية نحن مهتمون فقط بقوى 2). على سبيل المثال ، بالنسبة للكلمات ذات 16 بت ، هذا حقل يحتوي على 65 عنصرًا ، يمكنك العثور على نتيجة أي عملية لكل زوج منها (+ ، - ، * ، /). تعتبر قيم x و p و alpha و beta و gamma و delta من المعادلات أعلاه عناصر من حقل Galois للحسابات.
وبالتالي ، لدينا نظام معادلات يمكن استخدامه لبناء كتل من أكواد التكرار عن طريق كتابة برنامج كمبيوتر مناسب. باستخدام نفس نظام المعادلات ، يمكنك إجراء استعادة البيانات.
* هذا ليس تعريفًا صارمًا ، بل هو وصف.
كيفية استعادة البيانات
الاستعادة مطلوبة عندما تكون بعض الكتل من كتل n + m مفقودة. يمكن أن تكون كتل بيانات وكتل من أكواد التكرار. قد يعني عدم وجود كتل بيانات و / أو كتل من رموز التكرار أن المتغيرات المقابلة x و / أو p غير معروفة في المعادلات أعلاه.
يمكن النظر إلى معادلات أكواد Reed-Solomon كنظام معادلات تكون فيه جميع قيم alpha و beta و gamma و delta ثوابت ، وكل x و p المقابلة للكتل المتاحة متغيرات معروفة ، أما x و p المتبقيان غير معروفين.
على سبيل المثال ، دع كتل البيانات 1 و 2 و 3 وكتلة التكرار 2 غير متوفرة ، ثم بالنسبة للمجموعة الأولى من الكلمات ، سيكون هناك نظام المعادلات التالي (يتم تمييز المجهول باللون الأحمر):
لدينا نظام من 4 معادلات مع 4 مجاهيل ، حتى نتمكن من حلها واستعادة البيانات!
من نظام المعادلات هذا ، يتبع عدد من الاستنتاجات حول استعادة البيانات لرموز Reed-Solomon (n كتل بيانات ، m كتل من رموز التكرار):
- يمكن استعادة البيانات في حالة فقد أي كتل أو أقل. في حالة فقدان m + 1 أو أكثر من الكتل ، لا يمكن استعادة البيانات: من المستحيل حل نظام من المعادلات m مع m + 1 غير معروف.
- لاستعادة كتلة واحدة من البيانات ، تحتاج إلى استخدام أي من الكتل المتبقية ، ويمكنك استخدام أي من أكواد التكرار.
ماذا أحتاج أن أعرف؟
في الوصف أعلاه ، أتجاوز عددًا من القضايا المهمة التي تتطلب الغوص بشكل أعمق في الرياضيات. على وجه الخصوص ، أنا لا أقول شيئًا عن ما يلي:
- يجب أن يحتوي نظام المعادلات الخاصة برموز Reed-Solomon على حل (فريد) لأي مجموعة من المجهول (ليس أكثر من m مجهولة). بناءً على هذا المطلب ، يتم تحديد قيم alpha و beta و gamma و delta.
- يجب أن يكون نظام المعادلات قادرًا على البناء تلقائيًا (اعتمادًا على الكتل غير المتوفرة) وحلها.
- من الضروري بناء حقل جالوا: لطول كلمة معين ، تكون قادرًا على إيجاد نتيجة أي عملية (+ ، - ، * ، /) لأي عنصرين.
في نهاية المقال توجد روابط للأدبيات المتعلقة بهذه القضايا المهمة.
اختيار 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 (رموز إعادة البناء المحلية) هي رموز تكرار اخترعتها Microsoft لاستخدامها في Windows Azure Storage. فكرة LRC بسيطة قدر الإمكان: قسّم جميع كتل البيانات إلى مجموعتين (أو أكثر) وقم بحساب جزء من كتل التعليمات البرمجية المتكررة لكل مجموعة على حدة. ثم سيتم حساب جزء من كتل أكواد التكرار باستخدام جميع كتل البيانات (في LRC يطلق عليها رموز التكرار العالمية) ، وجزءًا - باستخدام إحدى مجموعتي كتل البيانات (يطلق عليها رموز التكرار المحلية).
يُرمز إلى LRC بثلاثة أرقام: nrl ، حيث n هو عدد كتل البيانات ، و r هو عدد كتل التكرار العالمية ، و l هو عدد كتل كود التكرار المحلية. لقراءة البيانات عند عدم توفر كتلة بيانات واحدة ، تحتاج إلى قراءة كتل n / l فقط - وهذا أقل بمقدار l مرة من أكواد Reed-Solomon.
على سبيل المثال ، ضع في اعتبارك مخطط LRC 6-2-2. X1-X6 - 6 كتل بيانات ، P1 ، P2 - كتلتان احتياطيتان عالميتان ، P2 ، P3 - كتلتان محليتان فائضتان عن الحاجة.
يتم حساب كتل التكرار P1 و P2 باستخدام جميع كتل البيانات. كتلة كود التكرار P3 مع كتل البيانات X1-X3 ، كتلة كود التكرار P4 مع كتل البيانات X4-X6.
يتم إجراء الباقي في LRC عن طريق القياس مع أكواد Reed-Solomon. معادلات حساب كلمات كتل التكرار هي كما يلي:
لتحديد الأرقام alpha و beta و gamma و delta ، تحتاج إلى استيفاء عدد من الشروط التي تضمن إمكانية استعادة البيانات (أي حل نظام المعادلات). يمكنك قراءة المزيد عنها في .
أيضًا ، من الناحية العملية ، تُستخدم عملية XOR لحساب رموز التكرار المحلية P3 و P4.
يتبع عدد من الاستنتاجات من نظام المعادلات لـ LRC:
- لاستعادة أي كتلة بيانات واحدة ، يكفي قراءة كتل n / l (n / 1 في مثالنا).
- إذا كانت كتل 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 أخطاء عندما يتعذر استرداد البيانات.
والأهم من ذلك ، أنه يعتمد على الموقف المحدد ، ولكن غالبًا ما تفوق المدخرات العامة التي يوفرها LRC موثوقية التخزين الأقل قليلاً.
4. رموز التكرار الأخرى
بالإضافة إلى أكواد Reed-Solomon و LRC ، هناك العديد من رموز التكرار الأخرى. رموز التكرار المختلفة تستخدم رياضيات مختلفة. فيما يلي بعض رموز التكرار الأخرى:
- رمز التكرار باستخدام عامل تشغيل XOR. يتم تنفيذ عملية XOR على n من كتل البيانات ، مما يؤدي إلى كتلة واحدة من أكواد التكرار ، أي مخطط n + 1 (كتل بيانات n ، رمز تكرار واحد). مستعمل في ، حيث تتم كتابة كتل البيانات ورموز التكرار دوريًا على جميع الأقراص الموجودة في المصفوفة.
- خوارزمية زوجية-فردية تعتمد على عملية XOR. يسمح لك ببناء كتلتين من أكواد التكرار ، أي المخطط n + 2.
- خوارزمية STAR على أساس عملية XOR. يسمح لك ببناء 3 مجموعات من أكواد التكرار ، أي المخطط n + 3.
- أكواد Pyramide هي رموز تكرار أخرى من Microsoft.
5. استخدم في Yandex
يستخدم عدد من مشاريع البنية التحتية في Yandex رموز التكرار لتخزين البيانات بشكل موثوق. وهنا بعض الأمثلة:
- تخزين الكائن الداخلي MDS ، والذي كتبت عنه في بداية المقال.
- - نظام Yandex MapReduce.
- (قاعدة بيانات Yandex) هي قاعدة بيانات موزعة newSQL.
يستخدم MDS رموز التكرار LRC ، مخطط 8-2-2. تتم كتابة البيانات ذات رموز التكرار على 12 قرصًا مختلفًا في خوادم مختلفة في 3 مراكز تحكم مختلفة: 4 خوادم في كل وحدة تحكم. اقرأ المزيد عن هذا في .
تستخدم 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 مراكز تحكم ، في أي حال يجب أن يكون (r + l) / n> = 0,5 ، أي أن التكرار التخزيني سيكون 50٪ على الأقل.
في YouTube ، يختلف الوضع: كل مجموعة على YouTube تقع بالكامل في وحدة تحكم واحدة (مجموعات مختلفة في DCs مختلفة) ، لذلك لا يوجد مثل هذا التقييد. يعطي مخطط 1-12-2 فائضًا بنسبة 2 ٪ ، أي أنه من الأرخص تخزين البيانات ، بينما يمكنهم أيضًا تحمل ما يصل إلى 33 حالات انقطاع متزامنة للقرص ، مثل المخطط في MDS.
هناك العديد من الميزات لاستخدام رموز التكرار في أنظمة تخزين البيانات ومعالجتها: الفروق الدقيقة في استعادة البيانات ، وتأثير الاسترداد على وقت تنفيذ الاستعلام ، وميزات تسجيل البيانات ، وما إلى ذلك. سأتحدث بشكل منفصل عن هذه وغيرها. ميزات استخدام رموز التكرار في الممارسة ، إذا كان الموضوع مثيرًا للاهتمام.
6. الروابط
- سلسلة من المقالات حول أكواد Reed-Solomon وحقول Galois:
يلقون نظرة أعمق على الرياضيات بلغة يسهل الوصول إليها. - مقال من Microsoft حول LRC:
يشرح القسم 2 النظرية بإيجاز ، ثم يناقش تجربة تطبيق مركز مصادر التعلُّم عمليًا. - مخطط زوجي فردي:
- مخطط ستار:
- رموز الهرم:
- رموز التكرار في MDS:
- رموز التكرار في YouTube:
- رموز التكرار في YDB:
المصدر: www.habr.com