نستمر في النظر في أمثلة لاستخدام سلسلة النسخ المتماثل. تم تقديم التعريفات الأساسية والبنى في الجزء الأول ، أوصي بأن تتعرف عليها قبل قراءة الجزء الثاني.

في هذه المقالة ، سوف ندرس الأنظمة التالية:

• Hibari هو مستودع موزعة للتسامح مع الأخطاء مكتوب بلغة إيرلانج.
• HyperDex - وحدة تخزين ذات قيمة موزعة مع دعم للبحث السريع حسب السمات الثانوية والبحث عن النطاق.
• ChainReaction - الاتساق السببية + والتكرار الجغرافي.
• بناء نظام موزع دون استخدام عمليات مراقبة / إعادة تهيئة خارجية إضافية.

5. هيباري

Hibari هو مستودع KV موزع للتسامح مع الأخطاء مكتوب بلغة إيرلانج. يستخدم تكرار السلسلة (النهج الأساسي) ، أي يحقق الاتساق الصارم. في الاختبارات ، يعرض Hibari أداءً عاليًا - يتم تحقيق عدة آلاف من التحديثات في الثانية على خوادم مؤلفة من وحدتين (طلبات 1 كيلو بايت)

5.1 العمارة

يستخدم التجزئة المستمر لوضع البيانات. أساس التخزين عبارة عن كتل مادية ومنطقية. الطوب المادي هو خادم يعمل بنظام Linux ، وربما نسخة EC2 ، وبشكل عام ، VM ككل. الطوب المنطقي هو مثيل للتخزين تعمل به العمليات الرئيسية للمجموعة ، وكل كتلة هي عقدة في أي سلسلة واحدة . في المثال أدناه ، تم تكوين الكتلة مع كتلتين منطقيتين على كل كتلة فعلية وبطول سلسلة من 2. لاحظ أن العقد من السلسلة "لطخت" على الكتل المادية لزيادة الموثوقية.

العملية الرئيسية (انظر التعريف في الجزء الأول) تسمى خادم المسؤول .

يتم تخزين البيانات في "جداول" ، والتي يتم تقسيمها ببساطة إلى مساحات أسماء ، ويتم تخزين كل جدول في سلسلة واحدة على الأقل ، وكل سلسلة تخزن البيانات في جدول واحد فقط.

يتلقى عميل Hibari التحديثات من خادم المسؤول مع قائمة بجميع رؤوس وسلاسل كل السلاسل (وجميع الجداول). وبالتالي ، يعرف العملاء فورًا العقدة المنطقية لإرسال الطلب إليها.

5.2 التجزئة

يستخدم هيباري زوجًا $$$\ {T ، K \}$ لتحديد اسم السلسلة التي تخزن المفتاح $$$K$ في الجدول $$$T$ : مفتاح $$$K$ تعيين إلى الفاصل $$$[0.1 ، 1.0) دولا$ (باستخدام MD5) ، الذي ينقسم إلى أقسام تكون سلسلة واحدة مسؤولة عنها. يمكن أن يكون للأقسام عرض مختلف ، اعتمادًا على "وزن" السلسلة ، على سبيل المثال:



وبالتالي ، إذا كانت بعض الكتل المادية قوية جدًا ، فيمكن إعطاء سلاسل موجودة عليها أقسام أوسع (ثم تسقط عليها المزيد من المفاتيح).

6. HyperDex

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

6.1 العمارة

فكرة تجزئة المساحة الفائقة هي البناء $$$ن$ مساحة-الأبعاد حيث تتوافق كل سمة مع محور إحداثي واحد. على سبيل المثال ، بالنسبة للكائنات (الاسم الأول ، الاسم الأخير ، رقم الهاتف) ، قد تبدو المساحة كما يلي:



يمر hyperplane الرمادي من خلال كافة المفاتيح ، حيث اسم العائلة = Smith ، الأصفر - عبر كافة المفاتيح ، حيث الاسم الأول = John. يشكل تقاطع هذه الطائرات استجابةً لأرقام هواتف استعلام البحث الخاصة بالأشخاص الذين يحملون الاسم John واللقب Smith. لذلك طلب ل $$$ك$ سمات العودة $$$(ن ك)$ فضاء جزئي الأبعاد.

مساحة البحث مقسمة إلى $$$ن$ المناطق مفككة الأبعاد ، ويتم تعيين كل منطقة إلى خادم واحد. يتم تخزين كائن مع إحداثيات من منطقة على خادم هذه المنطقة. وبالتالي ، يتم بناء التجزئة بين الكائنات والخوادم.

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

هناك مشكلة واحدة في هذا النهج - عدد الخوادم المطلوبة ينمو أضعافا مضاعفة من عدد السمات ، أي إذا سمات $$$ك$ فأنت بحاجة $$$O (2 ^ k)$ خوادم. لحل هذه المشكلة ، يقوم HyperDex بتطبيق قسم من مساحة التشعب في مسافات فرعية (ذات بعد أقل) مع مجموعة فرعية من السمات على التوالي:

6.2 النسخ المتماثل

لضمان الاتساق التام ، طور المؤلفون نهجا خاصا يعتمد على تسلسل سلسلة معتمدة على النسخ المتماثل ، حيث يتم تحديد كل عقدة لاحقة عن طريق تجزئة السمة المقابلة. على سبيل المثال ، المفتاح $$$("John" ، "Smith")$ أولاً ، سيتم تجزئته في المساحة الرئيسية (نحصل على سلسلة الرأس ، وتسمى أيضًا نقطة القائد ) ، ثم التجزئة من$$ $ المضمنة "جون" $ المضمنة للتنسيق على المحور المقابل وهلم جرا. (انظر الصورة أدناه للحصول على مثال التحديث. $$$u_1$ )

تمر كل التحديثات عبر قائد نقاط ، والذي يطلب الطلبات (الخطية).



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

7. ChainReaction

يتم استخدام نموذج التقارب السببي + ، مما يضيف شرط التقارب الخالي من النزاع إلى التقارب السببي (السببي). لتحقيق التقارب السببي ، تتم إضافة بيانات التعريف إلى كل طلب ، مما يشير إلى إصدارات جميع المفاتيح التي تعتمد على السبب. تسمح لك ChainReaction بالقيام بالنسخ المتماثل الجغرافي في العديد من مراكز البيانات كما أنها تطور آخر لفكرة CRAQ.

7.1 العمارة

يتم استخدام البنية من FAWN مع تغييرات طفيفة - يتكون كل DC من خوادم البيانات - الخلفية (تخزين البيانات ، والنسخ المتماثل ، وتشكيل حلقة DHT) والوكلاء العميل - الأمامية (إرسال طلب إلى عقدة محددة). يتم نسخ كل مفتاح إلى عقد R متتالية ، وتشكيل سلسلة. تتم معالجة طلبات القراءة عن طريق الذيل ، والكتابة رأسا على عقب.

7.2 مركز بيانات واحد

نلاحظ خاصية واحدة مهمة الناشئة عن تكرار سلسلة - إذا العقدة $$$ك$ متوافق مع بعض العمليات العميلة ، ثم جميع العقد السابقة - أيضًا. لذلك إذا كانت العملية $$$المرجع$ شوهد آخر مرة من قبلنا على الموقع $$$j$ ، ثم كل تعتمد على السببية (من $$$المرجع$ ) يمكن قراءة عمليات القراءة فقط على العقد من الرأس إلى $$$j$ . حالما $$$المرجع$ سيتم تنفيذها على الذيل - لن يكون هناك قيود القراءة. تشير إلى عمليات الكتابة التي تم تنفيذها بواسطة ذيل في العاصمة $$$د$ مثل DC- الكتابة مستقرة (د) .

يخزن كل عميل قائمة (بيانات أولية) بجميع المفاتيح التي يطلبها العميل بالتنسيق (المفتاح ، الإصدار ، chainIndex) ، حيث يمثل chainIndex موضع العقدة في السلسلة الذي أجاب على الطلب الأخير لمفتاح المفتاح. يتم تخزين بيانات التعريف فقط للمفاتيح التي لا يعرفها العميل ما إذا كان DC-Write-Stable (d) أم لا .

7.2.1 عملية الكتابة

لاحظ أنه بمجرد أن تصبح العملية DC-Write-Stable (d) ، فلن يتمكن أي قراءة من قراءة الإصدارات السابقة.

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



بمجرد تخزين القيمة الجديدة على $$$ك$ العقد من السلسلة ، يتم إرسال إشعار إلى العميل (مع فهرس العقدة الأخيرة). يقوم العميل بتحديث chainIndex ويزيل البيانات التعريفية للمفاتيح المرسلة ، كما أصبح معروفًا عنهم أنهم DC-Write-Stable (d). في موازاة ذلك ، يستمر التسجيل أكثر - انتشار كسول . وبالتالي ، تعطى الأولوية لكتابة العمليات على الأولى $$$ك$ العقد. بمجرد أن يخزن tail الإصدار الجديد من المفتاح ، يتم إرسال إخطار إلى العميل ويتم إرساله إلى جميع نقاط السلسلة حتى يتم تمييز المفتاح على أنه مستقر.

7.2.2 قراءة العملية

يرسل وكيل العميل طلب قراءة إلى $$ العقدة في الدائرة ، أثناء توزيع الحمل. استجابة لذلك ، ترسل العقدة قيمة وإصدار هذه القيمة. يتم إرسال الاستجابة إلى العميل ، بينما:

• إذا كانت النسخة مستقرة ، فإن السلسلة الجديدةإندكس تساوي حجم السلسلة.
• إذا كان الإصدار الأحدث ، فعندها سلسلة جديدة = فهرس.
• خلاف ذلك ، chainIndex لا يتغير.

7.2.3 فشل عقدة

إنها مطابقة تمامًا للنهج الأساسي ، مع وجود بعض الاختلافات في حقيقة أن chainIndex على العميل تصبح غير صالحة - يتم تحديد ذلك بسهولة عند تنفيذ الطلبات (لا يوجد مفتاح مع هذا الإصدار) ويتم إعادة توجيه الطلب إلى رأس السلسلة للبحث عن العقدة بالإصدار المطلوب.

7.3 عدة ( $$$N$ ) مراكز البيانات (النسخ المتماثل الجغرافي)

نحن نأخذ خوارزميات أساس من بنية خادم واحد ونعدلها إلى الحد الأدنى. بالنسبة للمبتدئين ، في البيانات الوصفية ، بدلاً من قيم الإصدار و chainIndex فقط ، نحتاج إلى متجهات إصدارية ذات أبعاد N.

نعرّف Global-Write-Stable بطريقة مماثلة مع DC-Write-Stable (d) - تعتبر عملية الكتابة Global-Write-Stable إذا تم تنفيذها على ذيول في جميع البلدان النامية.

يظهر مكون جديد في كل وحدة تحكم - remote_proxy ، وتتمثل مهمتها في تلقي / إرسال التحديثات من وحدات تحكم المجال الأخرى.

7.3.1 إجراء عملية الكتابة (على الخادم $$$i$ )

البداية تشبه بنية خادم واحد - فنحن نؤدي عمليات قراءة الحظر ، والكتابة إلى الأولى $$$ك$ عقدة من سلسلة. في هذه المرحلة ، يرسل الوكيل العميل العميل متجهًا chainIndex جديدًا ، حيث توجد الأصفار في كل مكان ، باستثناء الموقع $$$i$ - هناك معنى $$$ك$ . التالي - كالعادة. عملية إضافية في النهاية - يتم إرسال التحديث إلى remote_proxy ، والذي يجمع عدة طلبات ثم يرسل كل شيء.

مشكلتان تنشأ هنا:

• كيفية ضمان التبعيات بين التحديثات المختلفة القادمة من مختلف البلدان النامية؟
  
  يخزن كل remote_proxy متجه إصدار محلي $$ الأبعاد $$$N$ الذي يخزن عدد التحديثات المرسلة والمستلمة ، ويرسلها في كل تحديث. وبالتالي ، عند تلقي تحديث من وحدة تحكم أخرى ، يتحقق remote_proxy من العدادات ، وإذا كان العداد المحلي أقل ، يتم حظر العملية حتى يتم تلقي التحديث المقابل.
• كيفية توفير التبعيات لهذه العملية في البلدان النامية الأخرى؟
  
  يتم تحقيق ذلك باستخدام مرشح Bloom. عند إجراء عمليات الكتابة / القراءة من وكيل العميل ، بالإضافة إلى البيانات الوصفية ، يتم أيضًا إرسال عامل تصفية bloom لكل مفتاح (يسمى عوامل تصفية الاستجابة). يتم تخزين عوامل التصفية هذه في قائمة AccessedObjects ، وعند إرسال عمليات الكتابة / القراءة ، ترسل بيانات التعريف أيضًا مفاتيح عوامل التصفية المرسلة (تسمى مرشح التبعية). وبالمثل ، بعد عملية الكتابة ، يتم حذف المرشحات المقابلة. عند إرسال عملية الكتابة إلى وحدة تحكم أخرى ، يتم أيضًا إرسال مرشح التبعية ومرشح الاستجابة لهذا الطلب.
  
  علاوة على ذلك ، يتحقق جهاز التحكم عن بُعد DC ، بعد استلام كل هذه المعلومات ، من أنه إذا تزامنت وحدات البت المحددة لمرشح الاستجابة مع وحدات البت المحددة في عدة عوامل تصفية للاستعلام ، فمن المحتمل أن تكون هذه العمليات معتمدة على عارضة. يحتمل - لأن مرشح ازهر.

7.3.2 قراءة العملية

على غرار بنية خادم واحد ، تم ضبطها لاستخدام متجه chainIndex بدلاً من العددية واحتمال عدم وجود مفتاح في DC (لأن التحديثات غير متزامنة) - ثم انتظر أو أعد توجيه الطلب إلى DC آخر.

7.3.3 حل النزاعات

بفضل البيانات الوصفية ، يتم دائمًا تنفيذ العمليات المعتمدة على السببية بالترتيب الصحيح (في بعض الأحيان يكون عليك حظر العملية الخاصة بذلك). لكن التغييرات التنافسية في البلدان النامية المختلفة يمكن أن تؤدي إلى تعارضات. لحل مثل هذه المواقف ، يتم استخدام عمليات Last Last Wins ، والتي يوجد لها زوج في كل عملية تحديث $$$(ساعة ، ق)$ اين $$$ج$ - ساعات على الوكيل ، و $$$s$ - معرف العاصمة.

7.3.4 معالجة فشل العقدة

على غرار العمارة خادم واحد.

8. الاستفادة من المشاركة في تصميم بروتوكولات النسخ المتماثل القابل للتحجيم

الهدف من هذه الدراسة هو بناء نظام موزع مع القطع ومع النسخ المتماثل دون استخدام عملية رئيسية خارجية لإعادة تشكيل / مراقبة الكتلة.

في النهج الحالية الرئيسية ، يرى المؤلفون العيوب التالية:

النسخ المتماثل:

• أساسي / نسخ احتياطي - يؤدي إلى وجود تعارض في الحالة إذا تم تحديد "خطأ أساسي" على أنه فشل.
• النصاب التقاطع - قد يؤدي إلى تباين الحالة أثناء إعادة تشكيل الكتلة.

الاتساق الصارم:

• تعتمد البروتوكولات على خوارزميات التصويت بالأغلبية (مثل Paxos) عند الاقتضاء $$$2 * N + 1$ إسقاط عقدة $$$N$ العقد.

الكشف عن فشل العقدة:

• يتضمن P / B و CR وجود اكتشاف مثالي للعقد الفاشلة باستخدام نموذج توقف التوقف ، وهو أمر لا يمكن تحقيقه في الممارسة ويجب عليك اختيار فاصل مسح مناسب.
• يخضع ZooKeeper لنفس المشكلات - مع وجود عدد كبير من العملاء ، يلزم توفير قدر كبير من الوقت (> ثانية واحدة) لتحديث التكوين.

الطريقة التي اقترحها المؤلفون ، والتي تسمى النسخ المتماثل المرن ، خالية من أوجه القصور هذه ، ولها الخصائص التالية:

• الاتساق الصارم.
• لتحمل السقوط $$$N$ يجب أن يكون العقد $$$N + 1 دولا$ عقدة.
• إعادة التكوين دون فقدان الاتساق.
• ليست هناك حاجة إلى بروتوكولات الإجماع على أساس تصويت الأغلبية.

لوحة ملخص:

8.1 تنظيم النسخ المتماثلة

كل قشرة تحدد سلسلة من التكوينات $$$\ mathcal {C} = C_1 :: C_2 :: C_3 \ dots$ على سبيل المثال ، لا يحتوي التكوين الجديد على نوع من النسخ المتماثلة الساقطة $$$\ mathcal {C} = \ mathcal {C}: :( النسخ المتماثلة \ setminus R_j)$

يتكون كل عنصر من عناصر تسلسل التكوين من:

• النسخ المتماثلة - مجموعة من النسخ المتماثلة.
• معرف الطلب من نسخة متماثلة لها دور خاص (انظر أدناه).

يتم تمثيل كل قشرة بمجموعة من النسخ المتماثلة (حسب الإنشاء - $$$N$ ) ، أي نحن لا نقسم أدوار "قشرة" و "نسخة طبق الأصل".

يخزن كل نسخة متماثلة البيانات التالية:

• conf - معرّف التكوين الذي تنتمي إليه هذه النسخة المتماثلة.
• orderer - ما هي النسخة المتماثلة في هذا التكوين.
• وضع - وضع نسخة متماثلة ، واحدة من ثلاثة: $$$معلق$ (جميع النسخ المتماثلة من غير $$$C_1$ ) ، $$ (جميع النسخ المتماثلة من $$$C_1$ ) ، $$$IMMUTABL$ .
• التاريخ - تسلسل العمليات على البيانات المتماثلة الفعلية $$$op_1 :: op_2 :: \ dots$ (أو مجرد شرط).
• ثابت - الحد الأقصى لطول بادئة السجل الذي تم إصلاحه بواسطة هذه النسخة المتماثلة. من الواضح ، $$$0 <= مستقر <= طول (سجل)$ .

الهدف الأساسي من طلب النسخ المتماثل هو إرسال طلبات إلى بقية النسخ المتماثلة والحفاظ على بادئة أكبر محفوظات:

8.2 تنظيم القطع

يتم دمج القطع في حلقات تسمى العصابات المرنة . ينتمي كل قشرة إلى حلقة واحدة فقط. رائد كل قشرة $$$X$ يؤدي دورًا خاصًا - إنه جهاز تسلسل له. مهمة المنظم هو إعطاء خلفه تكوينًا جديدًا في حالة فشل النسخ المتماثلة.


شرطان مطلوبان:

• يحتوي كل شريط مرن على قشرة واحدة على الأقل ونسخة متماثلة واحدة تعمل.
• يحتوي كل شريط مرن على قشرة واحدة على الأقل ، تعمل فيها جميع النسخ المتماثلة.

يبدو الشرط الثاني صارمًا جدًا ، لكنه يعادل الشرط "التقليدي" الذي لا تسقط فيه العملية الرئيسية مطلقًا.

8.3 باستخدام سلسلة النسخ المتماثل

كما كنت قد خمنت ، يتم تنظيم النسخ المتماثلة كسلسلة (النهج الأساسي) - سيكون الطالب رأس ، مع وجود اختلافات بسيطة:

• في حالة الفشل في CR ، يتم طرح العقدة خارج السلسلة (واستبدالها بعقد جديد) ، في ER - يتم إنشاء سلسلة جديدة.
• تتم معالجة الطلبات المقروءة في السجل التجاري حسب الذيل ، وفي ER ، تمر عبر السلسلة بأكملها بنفس طريقة طلبات الكتابة.

8.5 إعادة التكوين في حالة حدوث عطل

• تتم مراقبة النسخ المتماثلة بواسطة كل من النسخ المتماثلة لشظرك والنسخ المتماثلة لقشرة التسلسل.
• بمجرد اكتشاف الفشل ، ترسل النسخ المتماثلة أمرًا بهذا الشأن.
• يرسل Sequencer تكوين جديد (بدون نسخة متماثلة فاشلة).
• يتم إنشاء نسخة متماثلة جديدة تقوم بمزامنة حالتها مع الشريط المطاطي.
• بعد ذلك ، يرسل جهاز التسلسل التكوين الجديد مع النسخة المتماثلة المضافة.

المراجع

• هيباري
• hyperdex.orgerdex.org
• HyperDex: مخزن مفتاح موزعة وقابل للبحث
• Chainreaction
• الاستفادة من المشاركة في تصميم بروتوكولات النسخ المتماثل القابلة للتحجيم