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

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

الهدف هو بيان المشكلة والمقارنة مع البروتوكول الأساسي / النسخ الاحتياطي.
تكرار السلسلة هو نهج أساسي.
تكرار السلسلة - الطلبات الموزعة.
FAWN: صفيف سريع من العقد Wimpy.

1. مقدمة

1.1 الغرض

لنفترض أننا نريد تصميم متجر بسيط ذي قيمة رئيسية. سيكون للمستودع واجهة بسيطة للغاية:

write (key، object): قيمة الحفظ / التحديث حسب مفتاح المفتاح.
read (key): إرجاع القيمة المخزنة بمفتاح المفتاح.

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

هدفنا هو تحمل عدد كبير من الطلبات ( إنتاجية عالية ، HT ) ، وتوافر عالٍ ( HA ) واتساق صارم ( SC ).

في العديد من الأنظمة ، يتم التضحية بـ SC من أجل HA + HT ، لأن تحقيق الخصائص الثلاثة هو مهمة غير تافهة. كانت أمازون دينامو قفزة هائلة إلى الأمام وأنتجت عددًا من قواعد البيانات على غرار دينامو مثل كاساندرا ، رياك ، فولدمورت ، إلخ.

1.2 الابتدائية / النسخ الاحتياطي

أحد أكثر الأساليب شيوعًا وبساطة لبناء نظام التخزين هذا هو استخدام النسخ الأساسي / النسخ الاحتياطي.
لدينا خادم أساسي واحد ، والعديد من خوادم النسخ الاحتياطي ، وعمليات الكتابة / القراءة تذهب فقط من خلال الخادم الأساسي.

تظهر الصورة هنا أحد بروتوكولات التفاعل الممكنة (ينتظر الأساسي ack من جميع النسخ الاحتياطية قبل إرسال ack إلى العميل) ، وهناك خيارات أخرى (ليست حصرية بشكل متبادل) ، على سبيل المثال:

ينظم الابتدائية بدقة طلبات الكتابة.
يرسل الأساسي ack بمجرد أن يستجيب أحد النسخ الاحتياطية مع ack.
ألمح النصاب القذر والتسليم.
إلخ.

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

من الواضح ، عاجلاً أم آجلاً ، أن أداء النسخ المتماثل الأساسي / النسخ الاحتياطي سيكون محدودًا من خلال اثنين من الاختناقات:

أداء الخادم الأساسي.
عدد خوادم النسخ الاحتياطي.

وكلما عرضت متطلبات الموثوقية / التناسق على الكتلة ، كلما جاءت هذه اللحظة بشكل أسرع.

هل هناك طرق أخرى لتحقيق هدفنا؟

1.3 تكرار السلسلة

بشكل عام ، يتكون النسخ المتسلسل من سلسلة (سلسلة) من الخوادم ، مع أدوار خاصة HEAD (الخادم الذي يتصل به العميل) و TAIL (نهاية السلسلة ، ضمان SC). تحتوي السلسلة على الخصائص التالية على الأقل:

يقاوم انخفاض خوادم n - 1.
لا تختلف سرعة الكتابة بشكل كبير عن سرعة SC Primary / Backup.
تحدث إعادة تكوين نظام المجموعة في حالة تعطل HEAD بشكل أسرع بكثير من الخادم الأساسي ، أما باقي الخوادم فهي نسبيًا أو أسرع من الابتدائية / الاحتياطية.

نقطة صغيرة ولكنها مهمة - مطلوب اتصال FIFO موثوق بين الخوادم.

دعونا نفحص بمزيد من التفصيل الطرق المختلفة لبناء النسخ المتماثل.

2. النهج الأساسي

2.1 الخوارزمية التشغيلية

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

2.2 بروتوكول النسخ المتماثل

نرقم الخوادم من الرأس إلى الذيل ، ثم على كل عقدة

$i$ بالإضافة إلى ذلك ، سنقوم بتخزين:

$Pending_i$ - قائمة بالطلبات المستلمة من العقدة التي لم يتم معالجتها بعد بواسطة الذيل.
$Sent_i$ - قائمة الطلبات التي يرسلها الخادم إلى خلفه والتي لم تتم معالجتها بعد بواسطة الذيل.
$History_i (مفتاح)$ - تاريخ التغييرات في القيمة الرئيسية (يمكنك تخزين التاريخ والقيمة الإجمالية فقط). لاحظ أن:
$م ف ت ا ح م ف ت ا ح ،$
$History_j (مفتاح) \ subseteq History_i (مفتاح) ، \ forall j> i$
وأيضًا:
$Sent_i \ subseteq Pending_i \\ History_i (key) = History_ {i + 1} (key) \ cup Sent_i$

2.3 تجاوز الفشل الخادم

كما ذكر في المقدمة ، نحن بحاجة إلى نوع من العمليات الرئيسية التي:

يحدد الخادم الفاشل.
يخطر سلفه وخلفه في التغييرات في الدائرة.
إذا كان الخادم ذيلًا أو رأسًا ، فإنه يخطر العملاء بتغييرهم.

نعتقد أن العملية الرئيسية مستقرة ولا تتعطل أبدًا. إن اختيار مثل هذه العملية هو خارج نطاق هذه المقالة.

الافتراض الثاني المهم جدًا هو أننا نفترض أن الخوادم تتوقف عن الفشل:

في حالة حدوث أي فشل (داخلي) ، يتوقف الخادم عن العمل ولا يعطي نتيجة غير صحيحة.
يتم تحديد فشل الخادم دائمًا من خلال العملية الرئيسية.

دعنا نرى كيف تتم إضافة خادم جديد:
من الناحية النظرية ، يمكن إضافة خادم جديد إلى أي مكان في السلسلة ، إضافة إلى الذيل يبدو الأقل صعوبة - تحتاج فقط إلى نسخ حالة الذيل الحالي إلى الخادم الجديد ، وإعلام المعالج بالتغيير في السلسلة وإخطار الذيل القديم الذي يحتاج الآن إلى إرسال المزيد من الطلبات.

أخيرًا ، ضع في اعتبارك ثلاثة سيناريوهات فشل محتملة:

2.3.1 سقوط الرأس
فقط قم بإزالة الخادم من السلسلة وقم بتعيين الرأس الجديد التالي. فقط فقدان تلك الطلبات من

$Pending_ {head}$ التي لم يتم إرسالها أكثر -

$Pending_ {head} \ setminus Sent_ {head}$

2.3.2 ذيل السقوط
نزيل الخادم من السلسلة ونعين السلسلة السابقة إلى الذيل الجديد قبل ذلك

$Sent_ {tail - 1}$ تم مسحها (تم تمييز كل هذه العمليات على أنها ذيل معالج) ، على التوالي

$Pending_ {tail - 1}$ يقلل.

2.3.3 هبوط العقدة الوسيطة

$k$
يقوم المعالج بإبلاغ العقد

$k-1$ و

$k + 1$ حول إعادة الترتيب في سلسلة.
خسارة محتملة

$Sent_ {k-1}$ إذا كانت العقدة

$k$ لم أتمكن من إرسالها إلى خليفي بعد ذلك ، بعد حذف العقدة

$k$ من السلسلة يتم إرسال أول شيء مرة أخرى

$Sent_ {k - 1}$ وفقط بعد تلك العقدة

$k - 1$ تواصل معالجة الطلبات الجديدة.

2.4 مقارنة مع بروتوكول النسخ الاحتياطي / الأساسي

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

تأخيرات تكرار سلسلة الفشل:

الرأس: لا تتم مقاطعة تنفيذ طلبات القراءة ، وتتأخر طلبات الكتابة برسالتين - من الرئيسي إلى جميع الخوادم حول الرأس الجديد ومن الرئيسي إلى جميع العملاء حول الرأس الجديد.
الخادم الوسيط: لا تتم مقاطعة طلبات القراءة. قد تتأخر طلبات التسجيل في وقت التشغيل $Sent_i$ لا توجد خسائر التحديث.
الذيل: تأخير طلبات القراءة والكتابة لرسالتين - الإخطار $inline$ حول الذيل الجديد وتنبيه العملاء بشأن الذيل الجديد.

تأخيرات عجز P / B:

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

كما ترون ، فإن أسوأ فشل ذيل للنسخ المتماثل هو أسرع من الأسوأ في P / B (أساسي).

أجرى مؤلفو هذا النهج اختبارات الحمل ، والتي أظهرت أداءً مشابهًا لبروتوكول P / B.

3. الاستعلامات الموزعة (النسخ المتماثل مع الاستعلامات المقسمة - CRAQ)

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

يصبح الذيل نقطة ساخنة ، أي خادم يعالج الطلبات أكثر بكثير من أي عقدة أخرى.
عند وضع سلسلة في عدة مراكز بيانات ، يمكن أن يكون الذيل بعيدًا جدًا ، مما سيؤدي إلى إبطاء طلبات الكتابة.

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

3.1 CRAQ

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

يمكن تخزين عدة نسخ من نفس الكائن في كل عقدة غير ذيل ، وتشكل الإصدارات تسلسلاً متزايدًا بشكل رتيب. لكل إصدار ، يتم إضافة سمة إضافية "نظيفة" أو "قذرة". في البداية ، جميع الإصدارات نظيفة.

بمجرد أن تتلقى العقدة طلب كتابة ، تضيف النسخة المستلمة إلى قائمة الإصدارات ، ثم:

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

بمجرد أن تتلقى العقدة تأكيدًا من الخلف ، فإنها تحدد الإصدار على أنه نظيف ويحذف جميع الإصدارات السابقة.

بمجرد أن تتلقى العقدة طلب قراءة:

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

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

يمكن وضع CRAQ في مركز بيانات واحد أو في عدة مراكز بيانات. وهذا يتيح للعملاء تحديد أقرب عقد لزيادة سرعة طلبات القراءة.

3.2 الاتساق في CRAQ

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

الاتساق الضعيف ممكن أيضًا:

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

3.3 تجاوز فشل الخادم

على غرار النهج الأساسي.

3.4 اختياري

يحتوي CRAQ على ميزة واحدة مثيرة للاهتمام - يمكنك استخدام البث المتعدد أثناء عملية التسجيل. افترض أن الرأس يرسل التغيير بواسطة الإرسال المتعدد ويرسل إلى أسفل بعض المعرّف لهذا الحدث فقط. إذا لم يصل التحديث نفسه إلى العقدة ، فيمكنه الانتظار واستلامه من العقدة التالية عندما يرسل Tail رسالة تأكيد للتغيير. وبالمثل ، يمكن أن يرسل الذيل تأكيدًا للتثبيت باستخدام الإرسال المتعدد.

4. FAWN: صفيف سريع من العقد Wimpy

دراسة مثيرة للاهتمام للغاية ، لا تتعلق مباشرة بموضوع هذه المقالة ، ولكنها تعمل كمثال على استخدام النسخ المتماثل للسلسلة.

تتميز مخازن التخزين ذات القيمة الرئيسية عالية الأداء (Dynamo و memcached و Voldemort) بخصائص مشتركة - فهي تتطلب إدخال / إخراج وحد أدنى من الحوسبة ووصول مستقل موازٍ للمفاتيح العشوائية بكميات كبيرة وقيم مفاتيح صغيرة تصل إلى 1 كيلوبايت.

الخوادم ذات محركات الأقراص الثابتة غير مناسبة لمثل هذه المجموعات بسبب عملية البحث الطويلة (وقت الوصول العشوائي) ، والخوادم التي تحتوي على عدد كبير من DRAM تستهلك قدرًا كبيرًا من الطاقة بشكل مدهش - 2 جيجا بايت DRAM تعادل 1 تيرابايت HDD.

الهدف من الدراسة الأصلية هو بناء مجموعة فعالة (عرض النطاق الترددي) مع الحد الأدنى من استهلاك الطاقة. 50 ٪ من تكلفة الخادم لمدة ثلاث سنوات هي تكاليف الكهرباء ، وأوضاع توفير الطاقة الحديثة ليست فعالة كما هو معلن عنها - في الاختبارات عند تحميل 20 ٪ ، ظل استهلاك وحدة المعالجة المركزية عند 50 ٪ ، بالإضافة إلى أن مكونات الخادم الأخرى لا تحتوي على أوضاع موفرة للطاقة على الإطلاق ( DRAM ، على سبيل المثال ، تعمل بالفعل كحد أدنى). من المهم ملاحظة أنه في مثل هذه المجموعات تتسع الفجوة بين CPU و I / O - تضطر وحدة المعالجة المركزية القوية إلى الانتظار حتى تكتمل عملية الإدخال / الإخراج.

4.1 العمارة

تم بناء مجموعة FAWN على خوادم قديمة مقابل 250 دولارًا (بأسعار 2009) ، مع وحدة معالجة مركزية مدمجة 500 ميجا هرتز ، 512 ميجا بايت رام ، 32 جيجا بايت SSD. إذا كنت على دراية بهندسة Amazon Dynamo أو التجزئة المتسقة ، فستكون على دراية بهندسة FAWN:

يحتوي كل خادم فعلي على عدة عُقد افتراضية ، لكل منها VID الخاص به.
تشكل VIDs حلقة ، كل VID مسؤول عن النطاق "خلف نفسه" (على سبيل المثال ، A1 مسؤول عن المفاتيح في النطاق R1).
لزيادة الموثوقية ، يتم نسخ البيانات إلى R للعقد التالية في اتجاه عقارب الساعة. (على سبيل المثال ، مع R = 2 ، يتم نسخ المفتاح على A1 إلى B1 و C1) ، لذلك نحصل على نسخ متماثل (النهج الأساسي).
تذهب طلبات القراءة إلى سلسلة الذيل ، أي قراءة المفتاح من A1 ستذهب إلى C1.
طلبات الكتابة تذهب إلى سلسلة الرأس وتستمر حتى النهاية.

يتم تخزين خريطة الخادم على مجموعة من خوادم الواجهة الأمامية ، وكل منها مسؤول عن قائمة VID الخاصة به ، ويمكنه إعادة توجيه الطلب إلى خادم واجهة أمامية آخر.

4.2 نتائج الاختبار

في اختبار الحمل ، يصل FAWN إلى QPS (استعلامات في الثانية) بنسبة 90٪ من QPS على محرك أقراص فلاش عشوائي للقراءة.

يقارن الجدول التالي بين التكلفة الإجمالية للملكية (TCO) لمختلف التكوينات ، حيث يكون الأساس لـ التقليدي هو خادم 1000 دولار باستهلاك 200 واط (أسعار 2009):

وبالتالي ، إذا:

البيانات الضخمة والاستفسارات القليلة: FAWN + 2Tb 7200 RPM
كمية صغيرة من البيانات ، الكثير من الطلبات: FAWN + 2GB DRAM
متوسط القيم: FAWN + 32GB SSD

تكرار السلسلة: بناء مستودع KV فعال (الجزء 1/2)