الگوریتم های اجماع

1) توافق چیست و چرا مورد نیاز است

اجماع - مذاکره در مورد همان مقدار/دنباله ای از مقادیر بین گره های متعدد برای شکست و تاخیر. بهطور سنتی، مسئله تکرار حالت (تکرار ماشین حالت، SMR) حل شدهاست: یک ماشین حالت قطعی و یک نظم کلی از عملیات وجود دارد.

• اجماع (SMR): یک ترتیب کلی از دستورات → ذخیره سازی/رجیستری خطی، ابرداده خوشه ای، هماهنگ کننده های معاملات.
• عملیات Quorum بدون نظم کامل (Dynamo-like، CRDT): اجازه می دهد واگرایی و ادغام بعدی ؛ اجماع را جایگزین نکنید که در آن سریال سازی جهانی مورد نیاز است.

2) مدل زمان و شکست

2. 1 مدل زمان

شبکه ناهمزمان: تاخیر نامحدود است ؛ قضیه FLP ⇒ تضمین ایمنی و زنده بودن بدون فرضیات اضافی غیرممکن است.
نیمه همزمان (اغلب در عمل): پس از یک T ناشناخته، سیستم «همزمان» رفتار می کند - اکثر الگوریتم ها (Raft، Paxos) به این تکیه می کنند.
همزمان: محدودیت زمانی دقیق برای کانال (به ندرت در فروش، به جز برای شبکه های خاص/PRT).

2. 2 مدل شکست

Crash-fault tolerant (CFT): گره ها ممکن است سقوط کنند/آویزان شوند اما رفتار مخرب ندارند.
تحمل خطای بیزانس (Byzantine-fault tolerant (BFT)): گره ها می توانند پیام ها را دروغ/جعل کنند. نیاز به گره 3f + 1 برای تحمل به f بیزانس.

3) ویژگی های توافق

امنیت: سازگاری (دو گره صحیح مقادیر مختلف را حل نمی کنند).
زنده بودن: اگر شبکه «سالم» باشد، یک راه حل به دست می آید.
خطی بودن (linearity): عملیات به صورت اتمی در یک مرتبه واحد دیده می شوند.
دوام: تصمیمات گرفته شده به عقب رانده نمی شوند (حفاظت ورود/حد نصاب).

4) کورام ها، اکثریت ها و تقاطع ها

در جهان CFT، کلاسیک: quorum> N/2. سوابق و انتخابات رهبر از عبور از حد نصاب استفاده می کنند، بنابراین دو عملیات «معتبر» در تضاد نیستند.
در دنیای BFT: quorums 2f + 1 از 3f + 1 تقاطع حداقل f + 1 گره صادق را فراهم می کند.

قانون عبور: هر دو حد نصاب باید ≥1 گره عادلانه مشترک (CFT) یا ≥f+1 (BFT) داشته باشد.

5) تکرار حالت (ورود به سیستم + برنامه)

• عکس های فوری (یک تکه از دولت که پس از آن سوابق اولیه را می توان حذف/وارد شده).
• تراکم مجله و ورود به سیستم triem.
• بررسی قطعی (همان کد/نسخه پیکربندی).

6) رهبری و طرح های غیر رهبری

رهبری (Raft, Multi-Paxos, ZAB): یک رهبر سوابق را از نظر ذهنی و عملیاتی آسانتر می کند، تأخیر بهتر در یک رهبر پایدار.
بدون رهبر/چند رهبر (EPaxos، سزار): موازی سازی و تحمل بیشتر برای رهبر، اما اجرای سخت تر و راه حل درگیری ؛ سود با درگیری های کوچک تیم ها قابل مشاهده است.

7) الگوریتم های کلاسیک CFT

7. 1 Paxos/Multi-Paxos (و شیوه ها)

ایده: دو مرحله (آماده/پیشنهاد)، وعده های پذیرندگان، quorums اکثریت. Multi-Paxos یک «رهبر پایدار» را ترک می کند و پس از «گرم شدن» عملیات را به یک دور (برای ورودی های جدید) تبدیل می کند.

• انعطاف پذیر اما دشوار برای اجرای مدل.
• پیکربندی مجدد از طریق ورودی های ویژه (توافق مشترک).
• در عمل، کتابخانه ها/موتورها (نسل چاق/اسپانر).

7. 2 قایق

تجزیه برای یادگیری: انتخاب رهبر، تکرار ورود به سیستم، دوباره پیکربندی.

انتخابات: زمان بندی تصادفی، رای گیری مدت ؛ یک رهبر در هر دوره

AppendEntries: رهبر جریان سوابق، نظارت بر بازی از پیشوند (شاخص/مدت)، متعهد به تثبیت اکثریت.
خواندن مسیر: اجاره نامه خواندن (با یک رهبر قوی) و یا خواندن شاخص برای خواندن خطی.
«مشترک» - گره ها قبل از تعویض در دو خوشه رای می دهند.

مزایا: آسان تر برای توسعه/اشکال زدایی، ناورداهای قوی. معایب: رهبر یک نقطه فشار است.

7. 3 ZAB (پخش اتمی ZooKeeper )/تکرار نمایش داده شده (VRR)

ZAB: رهبر معاملات، مرحله بازیابی، zxid (epoch + index) را پخش می کند.
VRR: «دیدگاه ها» با یک تکرار کننده اولیه، شبیه به Multi-Paxos در روح است.

8) CFT های غیر رهبر/چند رهبر

8. 1 دستگاه EPaxos

هیچ رهبر دائمی وجود ندارد: هر گره می تواند یک فرمان را آغاز کند.
تیم های درگیری سفارش جزئی دریافت می کنند ؛ بدون درگیری - متعهد به 1-2 RTT به صورت محلی.
بدست آوردن توزیع جغرافیایی با درگیری کم، اما کدهای وابستگی/گراف پیچیده.

8. ۲ سزار، منسیوس

تغییرات که بهینه سازی تاخیر/تعادل و عملیات WAN.

9) الگوریتم های BFT و خانواده PoS

9. 1 PBFT (BFT عملی)

سه مرحله (پیش آماده/آماده/متعهد)، نیاز به 3F + 1 گره.
تاخیر کم در شبکه های محلی، جاده های چند مرحله ای و پیام های O (N ²).

9. 2 مناقصه (سبک BFT-PoS)

دور با پیشنهاد و دو رای (جلوگیری/precommit).
اعتبار سنج-پیشنهاد دهنده قطعی، زمان بندی، همگام سازی جزئی.
خوب برای شبکه های مجاز/PoS با ده ها/صدها اعتبار سنج.

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

طرح سه فاز به «بسته ها» با گواهینامه های quorum (QC) متحد شده است.
پیچیدگی خطی ارتباطات، پشتیبانی از بسته بندی و خط لوله موازی، برای پیاده سازی در بلاک چین ها مناسب است (به عنوان مثال، اکوسیستم Diem/Move).
با امضای آستانه، ترافیک کاهش می یابد.

9. 4 اجماع PoW/تجمعی (به طور خلاصه)

نه BFT به معنای دقیق کلمه، بلکه همگرایی احتمالی (زنجیره ای با بیشترین کار). مزایا: سادگی/باز بودن ؛ معایب: انرژی، ~ ثانیه دقیقه به پایان.

10) خوانده شده: خطی، متوالی و ذخیره شده

خواندن خطی: رهبر با اجاره فعال و یا از طریق خواندن شاخص (قایق) → تایید از طریق حد نصاب.
متوالی: می تواند از هر گره خوانده شود، اما بدون تضمین طراوت.
پیرو می خواند: مجاز تحت الزامات ضعیف ؛ برای انبارها - خوب.

11) پیکربندی مجدد (تغییر ترکیب خوشه)

نیاز به دو پیکربندی همپوشانی (اجماع مشترک): هر تعهد عبور quorums از هر دو پیکربندی → بدون «سوراخ».
اضافه کردن/حذف یکی در یک زمان، اندازه حد نصاب را رعایت کنید.
انتقال رهبری مکث را کاهش می دهد.

12) عملکرد و تنظیم

12. 1 تاخیر

الگوریتم های رهبری: 1 RTT در هر نوشتن (با یک رهبر پایدار) + تکرار.
توزیع جغرافیایی: WAN RTT غالب است → استفاده از مناطق محلی + تکرار بین منطقه ای یا رویکردهای EPaxos/HotStuff.

12. 2 توان عملیاتی

دسته بندی (گروه بندی دستورات)، AppendEntries موازی، کش صفحه ورود به سیستم، برنامه موازی (زمانی که عملیات تغییر می کنند).
دیسک ها: NVMe/Log در یک دستگاه جداگانه، 'O _ DIRECT '/AIO، فاصله بزرگ' fsync 'با محدودیت های SLA (سازش دوام/تاخیر).

12. 3 p99 دم

اجتناب از گره های داغ (همیشه یک رهبر وجود دارد): چرخش دوره ای یا خواندن بار بر روی پیروان.
مانیتور GC مکث (JVM/برو)، پین CPU، NUMA.

13) جغرافیا و توپولوژی

1 منطقه، 3 منطقه: خوشه کلاسیک CFT (N = 3/5).
2 منطقه: اجتناب کنید - هیچ سهمیه قابل اعتماد در تقسیم 1-1 وجود ندارد.
3 + مناطق: رهبر در الگوریتم «میانه» یا بدون رهبر ؛ پروکسی های منطقه ای/جبهه های محلی با ورود به سیستم ناهمزمان امکان پذیر است.

14) مسائل عملی عملیات

14. 1 عکس های فوری و بازیابی

آستانه اندازه مجله/تعداد معاملات.

انتقال یک تصویر لحظهای به گرههای جدید ؛ چک کردن چکها

14. 2 نظارت

رهبری: چه کسی رهبر است، چند اصطلاح (اصطلاح/دوره) تغییر کرده است.
Лаги: "append _ latency", "commit _ index - applied_index'.

سلامت حد نصاب: «آیا اکثریت زنده/2F + 1?»

اندازه ورود/سرعت فشرده سازی، صف عکس های فوری.

برای BFT: سهم رای، امضاکنندگان تخلیه، تاخیر QC

14. 3 امنیت کد/سازگاری

نسخه پروتکل بر روی سیم، مهاجرت با سازگاری ورود به سیستم.
نشانه شمشیربازی در اثرات خارجی (نگاه کنید به «قفل توزیع شده»): زمان سرب (مدت) برای انتقال به CRON/شغل.

15) ضد الگوهای

قرار دادن اجماع «به خاطر مد» که در آن یک DBMS یا حد نصاب می خواند بدون سریال سازی کافی است.
مخلوط CP و AP بدون مرزهای روشن (CAP) → UX غیر قابل پیش بینی.
بیش از حد برآورد PoW/PoS برای وظایف سازمانی با ده ها گره (دشوار/گران).
هنگامی که ترکیب تغییر می کند، پیکربندی مجدد و «quorums متقاطع» را نادیده بگیرید.
عدم خواندن مانع (اجاره نامه/خواندن شاخص) → خواندن کثیف.
اجرای خوشه های 2 گره (بدون اکثریت).
دست کم گرفتن دیسک ها و fsync: «همه چیز در حافظه پرواز می کند» - تا اولین راه اندازی مجدد.

16) چک لیست انتخاب

1. مدل شکست: CFT (سقوط) یا BFT (مخرب) ؟

2. جغرافیا: یک منطقه/سه منطقه یا WAN ؟ RTT تصمیم می گیرد.
3. خواندن معانی: آیا خواندن خطی ضروری است ؟ اجاره نامه/خواندن شاخص/پیگیری.
4. بار: انتظارات توسط p50/p99، توان ؛ آیا چند رهبری مورد نیاز است.
5. پیچیدگی عملیاتی: کتابخانه/موتور خارج از قفسه (etcd/ZK/Consul/Raft-libs) در مقابل اجرای بومی.
6. تنظیم مجدد: مکرر ؟ ما به توافق مشترک و ابزارهای مهاجرت نیاز داریم.

7. ادغام: عوارض جانبی خارجی - آیا شمشیربازی با دوره/اصطلاح وجود دارد ؟

8. امنیت: احراز هویت میزبان، رمزگذاری کانال، کنترل نسخه پروتکل.
9. تست playbooks: پارتیشن، GC-توقف، کشتن رهبر، دیسک آهسته، ساعت skew.
10. قابلیت مشاهده: معیارهای Leader/Lags/Journal و Alert تنظیم شده اند.

17) راهنمای مینی: زمانی که چه چیزی را می گیرید

etcd/خوشه قایق برای تنظیمات/قفل/هماهنگی در DC.
ZooKeeper/ZAB برای خدمات در حال حاضر به ZK گره خورده است (پشته های قدیمی، صف، رهبری).
Multi-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) سوالات متداول

س: چرا از دو گره و کراوات استفاده نمی کنید ؟

A: دو گره بدون داور سوم حد نصاب در تقسیم نمی دهد. شما نیاز به ≥3 (CFT) یا 3f + 1 (BFT) دارید.

س: قایق «ساده تر» Paxos چیست ؟

A: تجزیه روشن، unariants قابل درک از ورود و پیکربندی ؛ آسان تر برای پیاده سازی و نگهداری

س: چگونه بدون بارگیری رهبر سریع می خوانید ؟

A: دنبال کننده خواندن (متوالی) برای غیر بحرانی، یا اجاره نامه خواندن/خواندن شاخص برای خطی ؛ کش.

س: چه چیزی P99 را می کشد ؟

A: WAN-RTT، fsync دیسک، GC-توقف، رهبر بیش از حد گرم، عکس های فوری بزرگ در ساعت عجله.

س: آیا کش/کاتالوگ نیاز به اجماع دارد ؟

A: اگر به اندازه کافی سازگاری احتمالی - نه. اگر تغییر ناپذیر معامله لازم باشد، بله.

20) مجموع

اجماع یک ابزار برای نظم و ثبات است. انتخاب یک الگوریتم بر اساس مدل شکست و جغرافیا ؛ فراهم می کند عبور از حد نصاب، پیکربندی مجدد صحیح، خواندن خطی که در آن بحرانی و قابل مشاهده است. شمشیربازی برای جلوه های خارجی، عکس های فوری و نظم مجله را فراموش نکنید. سپس تکرار حالت قابل پیش بینی خواهد بود و حوادث نادر و قابل درک خواهد بود.