رمز المحو

الموسوعة الحرة

في نظرية الترميز ، يُعدّ رمز المحو رمز تصحيح الأخطاء الأمامية (FEC) بافتراض محو البتات (بدلاً من حدوث أخطاء في البتات)، حيث يحوّل رسالةً مكوّنةً من k رمزًا إلى رسالة أطول (كلمة رمزية) مكوّنة من n رمزًا، بحيث يمكن استعادة الرسالة الأصلية من مجموعة فرعية من الرموز n . يُطلق على النسبة r  = k / n معدل الترميز . أما النسبة k'/k ، حيث k' يُمثّل عدد الرموز اللازمة للاستعادة، فتُسمى كفاءة الاستقبال . يفترض خوارزمية الاستعادة معرفة أيّ الرموز n مفقودة. 

تاريخ

تم اختراع ترميز المحو بواسطة إيرفينغ ريد وغوستاف سولومون في عام 1960. [ 1 ]

توجد العديد من أنظمة ترميز المحو المختلفة. ومن أشهرها ترميز ريد-سولومون ، وترميز التحقق من التكافؤ منخفض الكثافة (رموز LDPC)، ورموز التوربو . [ 1 ]

اعتبارًا من عام 2023، يمكن تصميم أنظمة تخزين البيانات الحديثة بحيث تتحمل الفشل الكامل لعدد قليل من الأقراص دون فقدان البيانات ، وذلك باستخدام أحد الأساليب الثلاثة التالية: [ 2 ] [ 3 ] [ 4 ]

  • النسخ
  • RAID (مصفوفة زائدة من الأقراص غير المكلفة )
  • ترميز المحو

على الرغم من أن تقنية RAID تُعتبر تقنيًا نوعًا من أنواع ترميز المحو، [ 5 ] إلا أن RAID تُطبق عادةً على مصفوفة متصلة بجهاز حاسوب مضيف واحد (وهو ما يُمثل نقطة فشل واحدة )، بينما يشير مصطلح "ترميز المحو" عمومًا إلى عدة مضيفات، [ 3 ] ويُطلق عليها أحيانًا اسم مصفوفة زائدة من الخوادم منخفضة التكلفة (RAIS). يسمح ترميز المحو باستمرار العمليات عند توقف أي من هذه المضيفات. [ 4 ] [ 6 ]

بالمقارنة مع أنظمة RAID على مستوى الكتل، يتميز ترميز مسح تخزين الكائنات ببعض الاختلافات الهامة التي تجعله أكثر مرونة. [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]

رموز المسح المثلى

تتميز رموز المحو المثلى بخاصية أن أي k من رموز الكلمات المشفرة n كافية لاستعادة الرسالة الأصلية (أي أنها تتمتع بكفاءة استقبال مثلى). وتُعرف رموز المحو المثلى برموز الفصل ذات المسافة القصوى (رموز MDS).

التحقق من التكافؤ

يُعدّ فحص التكافؤ حالة خاصة حيث n  = k + 1. من مجموعة من k قيمة   {vأنا}1≤أنا≤ك{\displaystyle \{v_{i}\}_{1\leq i\leq k}}يتم حساب مجموع التحقق وإلحاقه بقيم المصدر k :

vك+1=-∑أنا=1كvأنا.{\displaystyle v_{k+1}=-\sum _{i=1}^{k}v_{i}.}

مجموعة القيم k  +  1{vأنا}1≤أنا≤ك+1{\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}أصبح الآن متسقًا فيما يتعلق بمجموع التحقق. إذا كانت إحدى هذه القيم،vهـ{\displaystyle v_{e}}إذا تم مسحها، فيمكن استعادتها بسهولة عن طريق جمع المتغيرات المتبقية:

vهـ=-∑أنا=1،أنا≠هـك+1vأنا.{\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}

يُعد RAID 5 تطبيقًا شائع الاستخدام لرمز مسح التحقق من التكافؤ باستخدام XOR. [ 1 ]

أخذ العينات الزائدة متعددة الحدود

مثال: بريد إلكتروني خاطئ ( k  =  2)

في الحالة البسيطة حيث k  =  2، يمكن إنشاء رموز زائدة عن طريق أخذ عينات من نقاط مختلفة على طول الخط الواصل بين الرمزين الأصليين. يوضح ذلك مثال بسيط يُسمى err-mail:

تريد أليس إرسال رقم هاتفها (555629) إلى بوب باستخدام خدمة البريد الإلكتروني الاحتياطي (err-mail). تعمل خدمة البريد الإلكتروني الاحتياطي تمامًا مثل البريد الإلكتروني العادي، باستثناء بعض العيوب.

  1. يضيع حوالي نصف البريد.
  2. الرسائل التي يزيد طولها عن 5 أحرف غير قانونية.
  3. إنها مكلفة للغاية (مماثلة للبريد الجوي).

بدلاً من أن تطلب من بوب تأكيد استلام الرسائل التي ترسلها، ابتكرت أليس الخطة التالية.

  1. تقوم بتقسيم رقم هاتفها إلى جزأين a = 555 و b = 629، وترسل رسالتين – "A=555" و "B=629" – إلى بوب.
  2. تقوم بإنشاء دالة خطية،و(أنا)=أ+(ب-أ)(أنا-1){\displaystyle f(i)=a+(ba)(i-1)}في هذه الحالةو(أنا)=555+74(أنا-1){\displaystyle f(i)=555+74(i-1)}بحيثو(1)=555{\displaystyle f(1)=555}وو(2)=629{\displaystyle f(2)=629}.

  1. تقوم بحساب القيم f (3) و f (4) و f (5)، ثم ترسل ثلاث رسائل زائدة: "C=703" و "D=777" و "E=851".

يعلم بوب أن شكل الدالة f ( k ) هوو(أنا)=أ+(ب-أ)(أنا-1){\displaystyle f(i)=a+(ba)(i-1)}حيث يمثل a و b جزئي رقم الهاتف. لنفترض الآن أن بوب تلقى "D=777" و "E=851".

يستطيع بوب إعادة بناء رقم هاتف أليس بحساب قيمتي a و b من القيمتين ( f (4) و f (5)) اللتين استلمهما. يمكن لبوب تنفيذ هذه العملية باستخدام أي رسالتي خطأ، لذا فإن نسبة رمز المحو في هذا المثال هي 40%.

لاحظ أن أليس لا تستطيع تشفير رقم هاتفها في رسالة خطأ واحدة فقط، لأنه يتكون من ستة أحرف، وأن الحد الأقصى لطول رسالة الخطأ الواحدة هو خمسة أحرف. إذا أرسلت رقم هاتفها على أجزاء، وطلبت من بوب تأكيد استلام كل جزء، فسيتعين إرسال أربع رسائل على الأقل (رسالتان من أليس، ورسالتان من بوب للتأكيد). لذا، فإن رمز الحذف في هذا المثال، الذي يتطلب خمس رسائل، يُعدّ اقتصاديًا للغاية.

هذا المثال مصطنع بعض الشيء . للحصول على رموز محو عامة حقًا تعمل على أي مجموعة بيانات، سنحتاج إلى شيء آخر غير f ( i ) المعطاة.

الحالة العامة

يمكن تعميم البنية الخطية المذكورة أعلاه لتشمل الاستيفاء متعدد الحدود . بالإضافة إلى ذلك، يتم الآن حساب النقاط على حقل منتهٍ .

نختار أولًا حقلًا منتهيًا F برتبة لا تقل عن n ، ولكنها عادةً ما تكون قوة للعدد 2. يُرقّم المُرسِل رموز البيانات من 0 إلى k - 1 ويرسلها. ثم يُنشئ متعدد حدود (لاغرانج) p ( x ) من الرتبة k بحيث يكون p ( i ) مساويًا لرمز البيانات i . ثم يُرسل p ( k )، ...، p ( n - 1). يمكن للمُستقبِل الآن استخدام استيفاء متعدد الحدود لاستعادة الحزم المفقودة، بشرط أن يستقبل k رمزًا بنجاح. إذا كانت رتبة F أقل من 2b ، حيث b هو عدد البتات في الرمز، فيمكن استخدام عدة متعددات حدود.    

يستطيع المرسل إنشاء الرموز من k إلى n − 1 "أثناء الإرسال"، أي توزيع عبء العمل بالتساوي بين إرسال الرموز. إذا أراد المُستقبِل إجراء حساباته "أثناء الإرسال"، فيمكنه إنشاء متعددة حدود جديدة q ، بحيث تكون q ( i ) = p ( i ) إذا تم استلام الرمز i < k بنجاح، و q ( i ) = 0 إذا لم يتم استلام الرمز i < k . الآن، لنفترض أن r ( i ) = p ( i ) − q ( i ). أولًا، نعلم أن r ( i ) = 0 إذا تم استلام الرمز i < k بنجاح. ثانيًا، إذا تم استلام الرمز i ≥ k بنجاح، فيمكن حساب r ( i ) = p ( i ) − q ( i ). بالتالي، لدينا نقاط بيانات كافية لإنشاء r وتقييمها للعثور على الحزم المفقودة. لذا فإن كل من المرسل والمستقبل يتطلبان O ( n ( n − k )) عملية و O ( n − k ) مساحة فقط للعمل "أثناء التشغيل".                    

تطبيق عملي في العالم الحقيقي

يتم تنفيذ هذه العملية بواسطة رموز ريد-سولومون، مع كلمات رمزية مبنية على حقل محدود باستخدام مصفوفة فاندرموند .

معظم رموز المحو العملية هي رموز منهجية - يمكن العثور على كل رمز من الرموز الأصلية k منسوخًا، غير مشفر، كواحد من رموز الرسالة n . [ 12 ] (رموز المحو التي تدعم مشاركة الأسرار لا تستخدم أبدًا رمزًا منهجيًا).

رموز محو شبه مثالية

تتطلب رموز المحو شبه المثلى  (1 +  ε) k رمزًا لاستعادة الرسالة (حيث ε>0). ويمكن تقليل قيمة ε على حساب وقت وحدة المعالجة المركزية. تُوازن رموز المحو شبه المثلى بين إمكانيات التصحيح والتعقيد الحسابي: إذ يمكن للخوارزميات العملية التشفير وفك التشفير بتعقيد زمني خطي.

تُعدّ رموز النافورة (المعروفة أيضًا برموز المحو غير المحددة المعدل ) أمثلةً بارزةً على رموز المحو شبه المثلى . فهي قادرة على تحويل رسالة مكونة من k رمزًا إلى شكل مشفر لا نهائي عمليًا، أي أنها قادرة على توليد عدد غير محدود من رموز التكرار التي يمكن استخدامها جميعًا لتصحيح الأخطاء. ويمكن للمستقبلين بدء فك التشفير بعد استلامهم ما يزيد قليلًا عن k رمزًا مشفرًا.

تُعالج رموز إعادة التوليد مشكلة إعادة بناء (أو إصلاح) الأجزاء المشفرة المفقودة من الأجزاء المشفرة الموجودة. وتحدث هذه المشكلة في أنظمة التخزين الموزعة حيث تُشكل الاتصالات اللازمة للحفاظ على التكرار المشفر تحديًا. [ 12 ]

تطبيقات ترميز المحو في أنظمة التخزين

أصبح ترميز المحو الآن ممارسة معيارية لتخزين البيانات بشكل موثوق. [ 13 ] [ 14 ] [ 15 ] على وجه الخصوص، تُستخدم تطبيقات مختلفة لترميز ريد-سولومون للمحو في أباتشي هادوب ، ونظام RAID-6 المدمج في لينكس، ومايكروسوفت أزور، وفيسبوك كولد ستوريج، وباك بليز فولتس. [ 15 ] [ 12 ]

كانت الطريقة التقليدية لاستعادة البيانات بعد الأعطال في أنظمة التخزين هي استخدام النسخ المتماثل. إلا أن النسخ المتماثل يُكبّد النظام تكلفة إضافية كبيرة من حيث البيانات المهدرة. لذلك، تلجأ أنظمة التخزين ذات الأحجام المتزايدة، كتلك المستخدمة في مراكز البيانات، إلى استخدام التخزين المُشفّر بالمحو. يُعدّ رمز ريد-سولومون (RS) الشكل الأكثر شيوعًا لتشفير المحو في أنظمة التخزين ، وهو عبارة عن صيغة رياضية متقدمة تُستخدم لتمكين استعادة البيانات المفقودة من أجزاء من البيانات المعروفة، والتي تُسمى كتل التكافؤ. في رمز RS من النوع ( k , r )، يتم تشفير مجموعة معينة من k كتلة بيانات، تُسمى "أجزاء"، إلى ( k + r ) أجزاء. تُشكّل المجموعة الكاملة من الأجزاء شريطًا . يتم التشفير بحيث يُمكن استعادة البيانات بالكامل طالما أن k جزءًا على الأقل من أصل ( k + r ) جزء متوفرة. هذا يعني أن التخزين المُشفّر برمز RS من النوع ( k , r ) يُمكنه تحمّل ما يصل إلى r عطل. (يختلف هذا عن الترميز القياسي RS( n , k ) ، حيث n = k + r .)           

RS(10,4)

مثال: في كود RS(10,  4)، المستخدم في فيسبوك لنظام ملفات Hadoop الموزع (HDFS ) (الذي أصبح الآن جزءًا من أباتشي هادوب)، تُقسّم 10 ميجابايت من بيانات المستخدم إلى عشرة كتل، كل منها 1 ميجابايت. ثم تُنشأ أربع كتل تكافؤ إضافية، كل منها 1 ميجابايت، لتوفير التكرار. يمكن لهذا النظام تحمّل ما يصل إلى 4 حالات فشل متزامنة. تبلغ تكلفة التخزين الإضافية هنا 14/10 = 1.4 × 10. [ 16 ]

في حالة النظام المُكرَّر بالكامل، يجب تكرار بيانات المستخدم البالغة 10 ميجابايت أربع مرات لتحمُّل ما يصل إلى 4 حالات فشل متزامنة. وستكون تكلفة التخزين الإضافية في هذه الحالة 50/10  =  5.0×.

وهذا يعطي فكرة عن انخفاض تكلفة التخزين الإضافية للتخزين المشفر بالمحو مقارنة بالنسخ الكامل، وبالتالي جاذبيته في أنظمة التخزين الحالية.

يمكن دمج مخطط Hitchhiker مع ترميز RS لتقليل حجم العمليات الحسابية ونقل البيانات اللازمة لإعادة بناء كتل البيانات. كما يتم تنفيذه كبرنامج ترميز HDFS، على الرغم من أنه سيتعين تحديد سياسة يدويًا لاستخدامه. [ 12 ]

بيانات ساخنة

في البداية، استُخدمت رموز المحو لتقليل تكلفة تخزين البيانات "الباردة" (التي نادراً ما يتم الوصول إليها) بكفاءة؛ ولكن يمكن أيضاً استخدام رموز المحو لتحسين أداء خدمة البيانات "الساخنة" (التي يتم الوصول إليها بشكل متكرر) مقارنةً بمخططات التكرار الأبسط (النسخ المتطابق). [ 12 ]

يُعدّ RAID 5 مثالًا كلاسيكيًا على تحسين الأداء من خلال ترميز المسح ، حيث يوفر نفس الحماية من فشل محرك أقراص واحد مع الحاجة إلى عدد أقل من محركات الأقراص الصلبة مقارنةً بـ RAID 1. ويمكن استخدام محركات الأقراص الصلبة الإضافية لتخزين المزيد من البيانات والاستفادة من مُضاعِف سرعة القراءة/الكتابة المُحسَّن في RAID 5. وينطبق هذا أيضًا على RAID 6 (التكرار المزدوج: رمز تكافؤ واحد ورمز مسح واحد)، بافتراض كفاية قوة المعالجة. [ 1 ] يمكن لـ RAID المُعمَّم العمل مع أي عدد من محركات الأقراص الاحتياطية. وهناك ترميزان لـ RAID المُعمَّم: RAID7. يشير x إلى نظام يحتوي على x من محركات الأقراص الاحتياطية، مما يسمح بالاستعادة عند تعطل x من هذه المحركات. [ 17 ] بدلاً من ذلك، يشير RAID N+M إلى N من محركات أقراص البيانات العادية مع M من محركات الأقراص الاحتياطية، مما يُمكّن من استعادة جميع البيانات عند تعطل أي من M من هذه المحركات. [ 1 ]

من الأمثلة الأكثر تطورًا ذاكرة التخزين المؤقت EC-Cache ، وهي ذاكرة تخزين مؤقت موزعة على عدة عُقد. قد تعاني هذه الأنظمة من عدم توازن الأحمال عندما تستضيف إحدى العُقد عناصر أكثر استخدامًا، ومن الطرق الشائعة لمعالجة هذه المشكلة النسخ الانتقائي ، أي إنشاء نسخ إضافية للعناصر الأكثر استخدامًا. مع ذلك، فإن هذه الطريقة محدودة بكمية الذاكرة المتاحة. من خلال تقسيم كل عنصر على حدة إلى k أجزاء و r وحدات تكرار، يمكن تحقيق توازن مثالي للأحمال مع الحد الأدنى من هدر الذاكرة. [ 12 ]

أمثلة

فيما يلي بعض الأمثلة على تطبيقات الرموز المختلفة:

رموز محو شبه مثالية

رموز نافورة شبه مثالية (محو بدون معدل)

رموز المسح المثلى

انظر أيضاً

مراجع

  1. ١ ٢ ٣ ٤ ٥ "RAID مقابل ترميز المحو. ما الفرق؟ | مدونة | Xinnor" . أسرع وأكثر برامج RAID موثوقية | Xinnor . ٢٠٢٣-٠٩-٠٣ . تم الاطلاع عليه بتاريخ ٢٠٢٤-٠٩-١٨ .
  2. ↑ "Ceph.io — ترميز المحو في Ceph" . ceph.io. 2014-04-07 . تم الاطلاع عليه بتاريخ 2024-09-18 .
  3. 1 2 لي، براندون (26-12-2023). "RAID مقابل ترميز المحو مقابل النسخ المتماثل" . BDRSuite . تم الاسترجاع في 18-09-2024 .
  4. 1 2 أورايلي، جيم. "RAID مقابل ترميز المحو" . www.networkcomputing.com . تم الاسترجاع في 18-09-2024 .
  5. ↑ ديمتري بيرتين، ألكسندر فان كيمبن، بينوا بارين، نيكولا نورماند. "مقارنة رموز محو RAID-6" . ورشة العمل الصينية الفرنسية الثالثة حول تكنولوجيا المعلومات والاتصالات، SIFWICT 2015، يونيو 2015، نانت، فرنسا. ffhal-01162047f
  6. ↑ "فهم خاصية تحمل الأعطال في إصدار IBM Spectrum Scale Erasure Code" . www.ibm.com . تاريخ الاسترجاع: 18-09-2024 .
  7. ↑ "ترميز محو التخزين الكائني مقابل RAID التخزين الكتلي" . مدونة MinIO . 27-07-2021 . تم الاطلاع عليه بتاريخ 18-09-2024 .
  8. ↑ "التشفير المحو مقابل تقنية RAID كطريقة لحماية البيانات | مجلة Computer Weekly" . ComputerWeekly.com . تاريخ الاسترجاع: 18 سبتمبر 2024 .
  9. ↑ كروث، بيتر (2023-10-04). "رمز المحو: RAID كما ينبغي أن يكون - مدونة هواوي" . مؤرشف من الأصل في 2023-10-04 . تم الاطلاع عليه في 2024-09-18 .
  10. ↑ "مقدمة في ترميز المحو" . مدونة MinIO . 25-04-2022 . تم الاطلاع عليه بتاريخ 18-09-2024 .
  11. ↑ بهاسكاران، دينش كومار (6 يوليو 2018). "لماذا يُعدّ ترميز المحو مستقبل مرونة البيانات" . مؤرشف من الأصل في 7 أغسطس 2020.
  12. 1 2 3 4 5 6 راشمي فيناياك. "ترميز المحو لأنظمة البيانات الضخمة: النظرية والتطبيق" . 2016. ص 2: قسم "الملخص". ص 9: قسم "الرموز المنهجية". ص 12: قسم "الرموز المُعاد توليدها".
  13. ↑ "ترميز المحو - الممارسة والمبادئ" . 2016.
  14. ↑ مات ساريل. "الترميز المحوي ​​101" . 2022.
  15. 1 2 برايان بيتش. "باكبليز يفتح شفرة المصدر لترميز ريد-سولومون للمحو" . 2015.
  16. ↑ شيا، مينغ يوان؛ ساكسينا، موهيت؛ بلاوم، ماريو؛ بيس، ديفيد أ. (2015). قصة رمزي محو في نظام ملفات Hadoop الموزع (HDFS ). مؤتمر FAST '15. الصفحات 213-226 . ISBN  978-1-931971-20-1.
  17. ↑ ليفينثال، آدم (ديسمبر 2009). "تقنية RAID ثلاثية التكافؤ وما بعدها: مع استمرار تجاوز سعات محركات الأقراص الصلبة لمعدلات نقل البيانات، فقد حان الوقت لمستوى جديد من تقنية RAID". مجلة ACM Queue . 7 (11): 30-39 . doi : 10.1145/1661785.1670144 .
  18. ↑ ديماكيس، ألكسندروس ج.؛ غودفري، ب. برايتن؛ وو، يونان؛ واينرايت، مارتن ج.؛ رامشاندرا، كانان (سبتمبر 2010). "ترميز الشبكة لأنظمة التخزين الموزعة". معاملات IEEE في نظرية المعلومات . 56 (9): 4539-4551 . arXiv : cs/0702015 . Bibcode : 2010ITIT...56.4539D . CiteSeerX : 10.1.1.117.6892 . doi : 10.1109/TIT.2010.2054295 . S2CID : 260559901 .  
  19. ↑ "الصفحة الرئيسية [ ويكي ترميز المحو للتخزين الموزع ] " . 31-07-2017. مؤرشف من الأصل في 31-07-2017 . تم الاسترجاع في 20-08-2023 .