نقشهٔ صفحه‌ها · ۱۴ صفحه

نوشته‌شده برای: مهندسان بک‌اند و سیستم‌های توزیع‌شده

1. 1

   رفت به‌طور عمیق: اجماعی که می‌شود دنبالش کرد

   • رفت الگوریتم اجماعی است که پیش از هر چیز برای فهمیده شدن طراحی شده است.
   • این ارائه رفت را بخش به بخش باز می‌کند: نقش‌ها، انتخابات، تکثیر لاگ و ایمنی.
   • مخاطب: مهندسان بک‌اند و سیستم‌های توزیع‌شده.
2. 2

   ماشین حالت تکثیرشده

   • هر سرور یک لاگ از فرمان‌های کلاینت نگه می‌دارد.
   • ماژول اجماع همهٔ لاگ‌ها را با فرمان‌های یکسان و ترتیب یکسان نگه می‌دارد.
   • هر ماشین حالت لاگش را به ترتیب اجرا می‌کند، پس همهٔ سرورها به یک حالت می‌رسند.
   • تا وقتی اکثریت سرورها برقرارند، خوشه به کار ادامه می‌دهد.
3. 3

   چرا دنبال کردن پکسوس دشوار است

   • پکسوس بر پایهٔ توافق روی فقط یک مقدار بنا شده و دو مرحلهٔ آن شهود ساده‌ای ندارد.
   • برای پکسوس چندتصمیمی الگوریتم کامل و مورد توافقی وجود ندارد.
   • هستهٔ آن متقارن است و رهبر فقط به‌عنوان بهینه‌سازی اضافه می‌شود.
   • در نتیجه هر سیستم واقعی نسخهٔ اثبات‌نشدهٔ خودش را می‌سازد.
4. 4

   طراحی برای فهم‌پذیری

   • هر جا دو طرح کار می‌کردند، طرحی برگزیده شد که توضیحش آسان‌تر بود.
   • اجماع به چهار زیرمسئله تجزیه شد: انتخاب رهبر، تکثیر لاگ، ایمنی و تغییر اعضا.
   • فضای حالت کوچک شد: لاگ بدون حفره و یک رهبر قوی.
   • تصادف فقط در یک جا به کار رفت: مهلت‌های انتخابات.
5. 5

   حالت‌های سرور و دوره‌ها

   • هر سرور در هر لحظه پیرو، نامزد یا رهبر است.
   • زمان به دوره‌های شماره‌دار تقسیم می‌شود و هر دوره با انتخابات آغاز می‌شود.
   • در هر دوره حداکثر یک رهبر وجود دارد و ممکن است دوره‌ای بی‌رهبر تمام شود.
   • سروری که دورهٔ بالاتری ببیند، آن را می‌پذیرد و به پیرو برمی‌گردد.
6. 6

   انتخاب رهبر با مهلت‌های تصادفی

   • پیرویی که تا پایان مهلتش ضربانی دریافت نکند، نامزد می‌شود و دوره را یکی بالا می‌برد.
   • نامزد به خودش رأی می‌دهد و هم‌زمان از همهٔ سرورها درخواست رأی می‌کند.
   • هر سرور در هر دوره فقط یک رأی می‌دهد، به اولین درخواست.
   • مهلت‌های تصادفی باعث می‌شوند آرای تقسیم‌شده کم پیش بیاید.
7. 7

   تکثیر لاگ

   • رهبر فرمان کلاینت را به لاگ خودش می‌افزاید و برای پیروها می‌فرستد.
   • ورودی‌ای که روی اکثریت ذخیره شود، قطعی است.
   • رهبر ورودی قطعی را اجرا می‌کند و به کلاینت پاسخ می‌دهد.
   • پیروها ورودی‌های قطعی را به ترتیب لاگ اجرا می‌کنند.
8. 8

   لاگ‌ها چگونه هماهنگ می‌مانند

   • اگر دو لاگ در یک اندیس ورودی‌ای با دورهٔ یکسان داشته باشند، تا آن نقطه کاملاً یکسان‌اند.
   • هر پیام افزودن، اندیس و دورهٔ ورودیِ قبل از ورودی‌های تازه را همراه دارد.
   • پیرو در صورت ناسازگاری رد می‌کند و رهبر یک ورودی عقب می‌رود.
   • در نقطهٔ تطابق، ورودی‌های ناسازگار پیرو با ورودی‌های رهبر جایگزین می‌شوند.
9. 9

   قواعد ایمنی: چه کسی می‌تواند رهبر شود

   • رأی‌دهنده به نامزدی که لاگش کمتر به‌روز است رأی نمی‌دهد.
   • دورهٔ آخرِ بالاتر به‌روزتر است؛ در دورهٔ برابر، لاگ بلندتر.
   • به همین دلیل هر رهبر تازه همهٔ ورودی‌های قطعی را از قبل دارد.
   • رهبر فقط نسخه‌های ورودی‌های دورهٔ خودش را برای قطعی کردن می‌شمارد.
10. 10

    دو فراخوانی راه دور: RequestVote و AppendEntries

    • الگوریتم اصلی فقط به دو فراخوانی راه دور نیاز دارد.
    • نامزدها با درخواست رأی، رأی جمع می‌کنند.
    • رهبر با پیام افزودن ورودی‌ها را تکثیر می‌کند؛ پیام خالی همان ضربان است.
    • هر فراخوانی دورهٔ فرستنده را همراه دارد.
11. 11

    تغییر اعضا و گرفتن اسنپ‌شات

    • تغییر اعضا از یک پیکربندی مشترک میان مجموعهٔ قدیم و جدید می‌گذرد.
    • در حالت مشترک، هر تصمیم به اکثریت هر دو مجموعه نیاز دارد.
    • هر سرور از حالت قطعی خودش اسنپ‌شات می‌گیرد و لاگ قبلی را دور می‌ریزد.
    • رهبر اسنپ‌شات را برای پیروهای خیلی عقب‌مانده می‌فرستد.
12. 12

    پژوهش فهم‌پذیری

    • ۴۳ دانشجو هر دو الگوریتم را یاد گرفتند و در دو آزمون شرکت کردند.
    • میانگین نمرهٔ آزمون رفت ۲۵٫۷ و آزمون پکسوس ۲۰٫۸ از ۶۰ بود.
    • منبع: نسخهٔ مفصل مقالهٔ اونگارو و اوسترهوت، دانشگاه استنفورد.

    نمودار ستونی: میانگین نمرهٔ آزمون ۴۳ دانشجو پس از یادگیری هر الگوریتم. منبع: In Search of an Understandable Consensus Algorithm (Extended Version) · بررسی‌شده در 2026-10-10

13. 13

    انتخابات چقدر طول می‌کشد

    • کمی تصادف در مهلت انتخابات کافی است تا آرای تقسیم‌شده کم شود.
    • با مهلت ۱۵۰ تا ۱۵۵ میلی‌ثانیه، میانهٔ مدت بی‌رهبری ۲۸۷ میلی‌ثانیه بود.
    • با مهلت ۱۲ تا ۲۴ میلی‌ثانیه، میانگین ۳۵ و طولانی‌ترین آزمایش ۱۵۲ میلی‌ثانیه بود.
    • این اندازه‌گیری‌ها روی خوشه‌ای پنج‌سروری انجام شد.

    نمودار میله‌ای: مدت بی‌رهبری پس از از کار افتادن، بر پایهٔ بازهٔ مهلت انتخابات (پنج سرور). منبع: In Search of an Understandable Consensus Algorithm (Extended Version) · بررسی‌شده در 2026-10-10

14. 14

    بده‌بستان‌ها و جای خواندن مقالهٔ کامل

    • رهبر قوی استدلال را ساده می‌کند، اما همهٔ نوشتن‌ها از یک سرور می‌گذرد.
    • حد نصاب اکثریت خرابی اقلیت را تاب می‌آورد، اما بی اکثریت سیستم می‌ایستد.
    • خواندن خطی‌پذیر نیاز دارد رهبر مطمئن شود هنوز رهبر است.
    • مقالهٔ کامل را در raft.github.io بخوانید و از بخش ۵ شروع کنید.