خوارزميات الإجماع

1) ما هو توافق الآراء ولماذا هو مطلوب

توافق الآراء - التفاوض على نفس القيمة/تسلسل القيم بين العقد المتعددة للفشل والتأخير. تقليديا، يتم حل مشكلة تكرار الحالة (تكرار آلة الدولة، SMR): هناك آلة حالة حتمية وترتيب عام للعمليات.

• توافق الآراء (SMR): ترتيب إجمالي واحد للأوامر → التخزين/التسجيل القابل للخط، البيانات الوصفية العنقودية، منسقي المعاملات.
• عمليات النصاب القانوني بدون طلب كامل (Dynamo-like, CRDT): السماح بالتباعد والاندماج اللاحق ؛ لا تحل محل توافق الآراء حيثما تكون هناك حاجة إلى التسلسل العالمي.

2) نموذج الوقت والفشل

2. 1 نموذج الوقت

الشبكة غير المتزامنة: التأخير غير محدود ؛ نظرية FLP ⇒ من المستحيل ضمان السلامة والحيوية دون افتراضات إضافية.
متزامن جزئيًا (غالبًا في الممارسة العملية): بعد T غير معروف، «يتصرف» النظام بشكل متزامن - تعتمد معظم الخوارزميات (Raft، Paxos) على هذا.
متزامن: حدود زمنية صارمة للقنوات (نادرًا ما تكون في المبيعات، باستثناء الشبكات الخاصة/PRT).

2. 2 نموذج الفشل

تحمل خطأ التصادم (CFT): قد تسقط العقد/تتدلى ولكنها لا تتصرف بشكل خبيث.
متسامح مع الخطأ البيزنطي (BFT): يمكن أن تكذب العقد/رسائل ساخرة. يتطلب 3f + 1 عقدة للتسامح مع F البيزنطية.

3) خصائص توافق الآراء

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

4) النصاب والأغلبية والتقاطعات

في عالم CFT، الكلاسيكي: النصاب القانوني> N/2. تستخدم السجلات وانتخابات الزعماء عبور النصاب القانوني، لذلك لا تتعارض العمليتان «الصحيحتان».
في عالم BFT: النصاب 2f + 1 من 3f + 1 يوفر تقاطعًا لما لا يقل عن f + 1 عقد صادقة.

قاعدة العبور: يجب أن يكون لأي نصاب ≥1 عقدة عادلة مشتركة (CFT) أو ≥f+1 (BFT).

5) تكرار الحالة (تطبيق log +)

• لقطات (شريحة من الحالة يمكن بعدها حذف/تجميع السجلات المبكرة).
• Journal compaction and log triem.
• فحص الحتمية (نفس الشفرة/نسخة التهيئة).

6) مخططات القيادة وغير القيادية

القيادة (Raft، Multi-Paxos، ZAB): يقوم أحد القادة بتسلسل السجلات → أسهل عقليًا وتشغيليًا، وكمون أفضل لقائد مستقر.
عدم وجود قيادة/تعدد القادة (EPaxos، Caesar): المزيد من التوازي والتسامح مع القائد، ولكن التنفيذ وحل النزاعات أصعب ؛ الربح مرئي مع صراعات صغيرة بين الفرق.

7) خوارزميات CFT الكلاسيكية

7. 1 Paxos/Multi-Paxos (والممارسات)

الفكرة: مرحلتان (إعداد/اقتراح)، وعود المقبولين، ونصاب الأغلبية. تترك Multi-Paxos' قائدًا مستقرًا "وتحول العمليات إلى جولة واحدة (للإدخالات الجديدة) بعد" الإحماء ".

• نموذج مرن ولكن من الصعب تنفيذه.
• إعادة التشكيل عن طريق مدخلات خاصة (توافق آراء مشترك).
• في الممارسة العملية، المكتبات/المحركات (Chubby/Spanner generation).

7. 2 طوافة

متحلل للتعلم: اختيار القائد، تكرار السجل، إعادة التكوين.

الانتخاب: فترات زمنية عشوائية، وتصويت لمدة ولاية ؛ قائد واحد لكل فترة.
المدخلات الملحقة: يقوم القائد بتدفق السجلات، ويراقب تطابق البادئة (فهرس/مصطلح)، ويلتزم بتثبيت الأغلبية.
مسار القراءة: قراءة الإيجار (مع قائد قوي) أو فهرس القراءة للقراءات الخطية.
Reconfig: «مشترك» - تصويت العقد في مجموعتين قبل التبديل.

الإيجابيات: أسهل في التطوير/التنقيح، ثوابت ترتيب قوية. السلبيات: القائد نقطة ضغط.

7. 3 ZAB (ZooKeeper Atomic Broadcast )/النسخ المتماثل (VRR)

ZAB: الرائد يبث المعاملات، مرحلة الاسترداد، zxid (epoch + index).
VRR: «وجهات نظر» مع تكرار أساسي، على غرار Multi-Paxos في الروح.

8) CFTs غير الرائدة/متعددة القادة

8. 1 EPaxos

لا يوجد زعيم دائم: يمكن لأي عقدة أن تبدأ الأمر.
وتتلقى أفرقة النزاع طلبا جزئيا ؛ خالية من النزاعات - الالتزام بـ 1-2 RTT محليًا.
كسب في التوزيع الجغرافي مع تنازع منخفض، ولكن معقد التبعية/رموز الرسم البياني.

8. 2 قيصر، منسيوس

الاختلافات التي تعمل على تحسين زمن الوصول/الموازنة وتشغيل الشبكة الواسعة.

9) خوارزميات BFT وعائلة PoS

9. 1 PBFT (عملي BFT)

ثلاث مراحل (التحضير/التحضير/الالتزام)، تتطلب 3f + 1 عقد.
انخفاض زمن الوصول على الشبكات المحلية والطرق متعددة الخطوات ورسائل O (N ²).

9. 2 Tendermint (نمط BFT-PoS)

جولات مع اقتراح وصوتين (منع/التزام مسبق).
مصادق قطعي - مقدم اقتراح، مهلة، تزامن جزئي.
جيد لشبكات PoS المسموح بها مع العشرات/المئات من المعتمدين.

9. 3 HotStuff (والمشتقات)

تم توحيد المخطط المكون من ثلاث مراحل في «حزم» مع شهادات النصاب (QC).
التعقيد الخطي للاتصالات، ودعم التعبئة والتغليف الموازي، ملائم للتطبيقات في blockchains (على سبيل المثال، النظام البيئي Diem/Move).
مع توقيعات العتبة، يتم تقليل حركة المرور.

9. 4 برنامج عمل/توافق الآراء التراكمي (باختصار)

ليس BFT بالمعنى الدقيق، ولكن التقارب الاحتمالي (السلسلة مع معظم العمل). المزايا: البساطة/الانفتاح ؛ العيوب: الطاقة، ~ ثوانٍ إلى النهاية.

10) يقرأ: خطي ومتسلسل ومخبأ

يقرأ Linear: الرائد مع عقد إيجار نشط أو من خلال فهرس القراءة (Raft) → التأكيد من خلال النصاب القانوني.
متسلسل: يمكن قراءته من أي عقدة، ولكن بدون ضمانات للنضارة.
يقرأ المتابع: مسموح به بموجب متطلبات ضعيفة ؛ للمخابئ - حسنًا.

11) إعادة التشكيل (تغيير تكوين المجموعة)

يتطلب تكوينين متداخلين (توافق آراء مشترك): أي ارتكاب النصاب القانوني لكلا التشكيلين → بدون «ثقوب».
أضف/أزل واحدًا تلو الآخر، راقب حجم النصاب.
نقل القيادة يقلل من فترات التوقف.

12) الأداء والضبط

12. 1 تأخير

خوارزميات القيادة: 1 RTT لكل كتابة (مع قائد مستقر) + تكرار.
التوزيع الجغرافي: تهيمن شبكة WAN RTT → استخدام المناطق المحلية + التكرار عبر الإقليمي أو مناهج EPaxos/HotStuff.

12. 2 الإنتاجية

الدفع (تجميع الأوامر)، مدخلات التذييل الموازية، ذاكرة التخزين المؤقت لصفحة التسجيل، تطبيق مواز (عند تبديل العمليات).
الأقراص: NVMe/Log على جهاز منفصل، «O _ DIRECT »/AIO، فاصل زمني كبير« fsync »مع قيود SLA (تسوية المتانة/الكمون).

12. 3 ذيول p99

تجنب العقد الساخنة (يوجد دائمًا قائد واحد): التناوب الدوري أو تفريغ القراءة على المتابعين.
رصد توقف GC (JVM/Go)، دبابيس CPU، NUMA.

13) الجغرافيا والطوبولوجيا

منطقة 1، مناطق 3: مجموعة CFT الكلاسيكية (N = 3/5).
المناطق 2: تجنب - لا يوجد نصاب موثوق عند 1-1 الانقسام.
3 + المناطق: الرائد في خوارزميات «الوسط» أو بدون قيادة ؛ من الممكن وجود جبهات إقليمية/جبهات محلية ذات سجل غير متزامن.

14) المسائل العملية للتشغيل

14. 1 لقطات واستعادة

العتبة حسب حجم اليومية/عدد المعاملات.
نقل لقطة إلى عقد جديدة ؛ تحقق من الشيكات.

14. 2 الرصد

القيادة: من هو القائد، كم عدد المصطلحات (المصطلح/الحقبة) التي تغيرت.
Лаги: 'append _ latency', 'committe _ index - applied_index'.

صحة النصاب: «هل الأغلبية على قيد الحياة/2f + 1 ؟»

حجم السجل/سرعة الضغط، قائمة انتظار اللقطات.

بالنسبة لـ BFT: حصة التصويت، التخلص من الموقعين، تأخيرات QC

14. 3 أمن/اتساق الكود

وضع البروتوكول على السلك، والهجرات مع توافق السجل.
رموز المبارزة على التأثيرات الخارجية (انظر «الأقفال الموزعة»): المهلة (المدة) للانتقال إلى CRON/الوظائف.

15) الأنماط المضادة

ضع إجماعًا «من أجل الموضة» حيث يقرأ أحد DBMS أو النصاب القانوني دون تسلسل يكفي.
امزج CP و AP بدون حدود واضحة (CAP) → UX غير متوقع.
المبالغة في تقدير برنامج العمل/برنامج العمل لمهام المؤسسة مع عشرات العقد (صعبة/باهظة الثمن).
تجاهل إعادة التكوين و «النصاب المتقاطع» عندما يتغير التكوين.
نقص حاجز القراءة (الإيجار/فهرس القراءة) → القراءات القذرة.
تشغيل عنقودين (بدون أغلبية).
التقليل من شأن الأقراص و fsync: «كل شيء يطير في الذاكرة» - حتى إعادة التشغيل الأولى.

16) قائمة الاختيار المرجعية

1. نموذج الفشل: CFT (حوادث) أو BFT (ضار) ؟

2. الجغرافيا: منطقة واحدة/ثلاث مناطق أو شبكة واحدة ؟ يقرر RTT.
3. دلالات القراءة: هل القراءات الخطية ضرورية ؟ الإيجار/فهرس القراءة/المتابعة.
4. الحمل: التوقعات بنسبة p50/p99، الإنتاجية ؛ ما إذا كانت هناك حاجة إلى قيادة متعددة.
5. التعقيد التشغيلي: المكتبة/المحرك الجاهز (etcd/ZK/Consul/Raft-libs) مقابل التنفيذ المحلي.
6. إعادة التشكيل: متكرر ؟ نحن بحاجة إلى توافق آراء مشترك وأدوات هجرة.

7. التكامل: الآثار الجانبية الخارجية - هل يوجد سياج حسب العصر/المصطلح ؟

8. الأمان: مصادقة المضيف، تشفير القناة، التحكم في إصدار البروتوكول.
9. كتب اللعب الاختبارية: التقسيم، GC-stop، قتل القائد، القرص البطيء، انحراف الساعة.
10. إمكانية الملاحظة: تم إعداد مقاييس Leader/Lags/Journal and Alert.

17) دليل مصغر: متى تأخذ ماذا

etcd/Raft cluster للتكوينات/الأقفال/التنسيق داخل DC.
ZooKeeper/ZAB للخدمات المرتبطة بالفعل بـ ZK (الأكوام القديمة، قوائم الانتظار، القيادة).
Paxos المتعددة من خلال خدمة/مكتبة جاهزة في نظم عالية التخصص.
EPaxos للتوزيع الجغرافي وصراع القيادة المنخفضة.
Tendermint/HotStuff للشبكات المسموح بها/طبقة PoS مع عشرات إلى مئات من المؤكدات ومتطلبات النهاية.
Dynamo-like/CRDT عندما لا تكون هناك حاجة إلى توافق في الآراء، ولكن إمكانية الوصول/النطاق مع الاندماج اللاحق أمر مهم.

18) أمثلة على الواجهات (زائفة)

18. 1 سجلات الالتزام (نمط الطوافة)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18. 2 فهرس القراءة للقراءة الخطية (الطوافة)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18. 3 تكوين مشترك

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18. 4 BFT (HotStuff تقريبي)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) الأسئلة الشائعة

س: لماذا لا تستخدم عقدتين وكسر التعادل ؟

ج: عقدتان بدون حكم ثالث لا تعطي النصاب القانوني في الانقسام. تحتاج إلى ≥3 (CFT) أو 3f + 1 (BFT).

س: ما هو رافت «الأبسط» باكسوس ؟

أ: التحلل الواضح، الثوابت المفهومة للسجل والتكوين ؛ أسهل في التنفيذ والصيانة.

س: كيف تقرأ بسرعة دون تحميل القائد ؟

ج: يقرأ المتابع (متتاليا) للغير حرجة، أو يقرأ الإيجار/فهرس القراءة للخطي ؛ ذاكرة التخزين المؤقت.

س: ما الذي يقتل p99 ؟

ج: WAN-RTT، قرص fsync، GC-stops، قائد محموم، لقطات كبيرة في ساعة الذروة.

س: هل يحتاج المخبأ/الكتالوج إلى إجماع ؟

ج: إذا كان هناك اتساق نهائي كافٍ - لا. إذا كانت المعاملات الثابتة مطلوبة، نعم.

20) المجاميع

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