الگوریتم Raft در سیستم‌های توزیع شده

رسیدن به اجماع توی سیستم‌های توزیع شده یکی از سخت‌ترین مسائل مهندسی نرم‌افزاره. اول از همه بگم منظورم چیه و مسئله رو روشن‌تر کنم.

وقتی چند سیستم با هم کار می‌کنن و باید وضعیت مشترکی رو با هم دیگه به روز نگه دارن، یک مسئله‌ی مهم توافق سر حالت‌های مختلف سیستمه. یه مثال بزنیم. یه سیستم ساده‌ی شمارنده رو در نظر بگیرین که خودش از ۳ تا سیستم تشکیل شده. حالا در هر لحظه این ۳ سیستم باید سر این‌که الان تا چه عددی شمارش کردن توافق کنن. این جاس که مسئله‌ی اصلی رخ می‌ده. چه طوری توافق کنن؟

برای حل این مسئله یک راه حل معروف وجود داره به نام الگوریتم Paxos. منتها پیاده‌سازی درست این الگوریتم به شکلی که کارایی مد نظر رو هم داشته باشه کار ساده‌ای نیست. یکی از دلایل اصلی پیدایش الگوریتم Raft همین بوده. یعنی در عین حال که کارایی الگوریتم Paxos رو حفظ کنیم، پیاده سازی ساده‌تری داشته باشیم.

خب الان که یه دید کلی داریم بریم با الگوریتم Raft بهتر آشنا بشیم. توی یک کلاستر Raft یکی از سرور‌ها به عنوان رهبر انتخاب می‌شه و مسئولیت هماهنگی رو به عهده می‌گیره. این رهبر دستور‌ها رو از client می‌گیره و بین کلاستر انتشار می‌ده و نتیجه رو به client اطلاع می‌ده.

برای این‌که یک کلاستر کار کنه و به پیام‌ها واکنش بده، حداقل تعداد سروری باید فعال باشن که این مقدار به حد نصاب معروفه (Quorum) و مقدارش یکی بیش‌تر از نصف تعداد سرور‌های کلاستره یعنی N/2 + 1. البته اگر تعداد از این عدد کمتر بشه، با وجود این‌که کلاستر دستور جدیدی رو پردازش نمی‌کنه، وضعیت موجود رو حفظ می‌کنه و می‌تونه اون وضعیت رو اطلاع بده.

کمی وارد جزئیات بشیم، الگوریتم Raft به یک مسئله‌ی اصلی پاسخ می‌ده که خودش به ۳ تا زیر مسئله شکسته می‌شه. انتخاب رهبر، لاگ توزیع شده و امنیت. (برای درک بهتر مفهوم لاگ لینک دوم منابع رو ببینید)

انتخاب رهبر

هر کدوم از اعضای کلاستر در لحظه می‌تونن در یکی از حالات رهبر، دنبال‌کننده و یا کاندیدا باشن. در مورد رهبر صحبت کردیم، دنبال کننده‌ها اعضای منفعل کلاستر هستند که صرفا به دستور‌های رهبر کلاستر واکنش نشون می‌دن. اما هر یک از این دنبال کننده‌ها در صورتی که رهبر در دسترس نباشه به یک کاندیدا تبدیل می‌شن و منتظر تایید کلاستر برای بر عهده گرفتن رهبری اون می‌شن.

در الگوریتم Raft زمان رو به بازه‌هایی به نام term تقسیم می‌کنیم. در ابتدای هر term یک رهبر انتخاب می‌شه و در صورت در دسترس بودن، تا آخر اون term رهبر باقی می‌مونه. وقتی رهبر انتخاب می‌شه، به صورت دوره‌ای به اعضای کلاستر سیگنال‌هایی می‌فرسته. تمام ارتباط بین اعضای کلاستر از نوع RPC هست و این سیگنال‌ها هم از این قاعده مستثنی نیستن. حالا اگه یه دنبال‌کننده در مدت زمان مشخصی از رهبر سیگنال دریافت نکنه، فرض می‌کنه که رهبر در دسترس نیست و به حالت کاندیدا می‌ره. در این حالت یک رویداد timeout رو در کلاستر منتشر می‌کنه و از بقیه‌ی اعضا رأی گیری می‌کنه تا خودش رهبر بشه (خودش هم به خودش رأی می‌ده). اگر اکثریت آرا رو جذب کرد به رهبر تبدیل می‌شه.

در این فرایند انتخاب رهبر ۲ تا مشکل ممکنه رخ بده؛ یکی این‌که ۲ عضو کاندیدا بشن و تعداد مساوی رای بیارن. در این صورت بلافاصله یک رای گیری جدید شروع می‌شه. به این حالت split vote گفته می‌شه و برای جلوگیری از تکرار این اتفاق زمان‌های timeout دنبال‌کننده‌ها به صورت رندم مشخص می‌شه تا مساوی نباشن. مشکل دوم زمانی رخ می‌ده که خود یک کاندیدا درخواست رای از یک کاندیدای دیگه دریافت کنه. در این حالت اگر term درخواست جدید از term انتخابی خودش بیش‌تر باشه، کاندیدا تسلیم می‌شه. برای درک بهتر این لینک رو ببینید که به صورت تصویری فرایند رو نشون می‌ده و می‌تونین توش دستکاری کنین تا متوجه بشین چه اتفاقی می‌افته.

انتشار لاگ

بعد از انتخاب رهبر نوبت به انتشار دستورات می‌رسه. رهبر کلاستر هر دستور یا لاگ رو قبل از همه دریافت می‌کنه. اون دستور رو موقتا اضافه می‌کنه و در کلاستر منتشر می‌کنه. اگر اکثریت کلاستر دریافت اون رو تایید کردن، کلاستر به صورت دائمی به لیست دستوراتش اضافه می‌کنه و دوباره پیغام اضافه کردنش رو در کلاستر منتشر می‌کنه. تصویر زیر خلاصه‌ای از این فرایند رو نشون می‌ده.

امنیت

نکته‌ی اول اینه که لاگِ رهبر کلاستر همیشه به روز باشه. این نیاز توسط Raft تضمین می‌شه چون اگر یک کاندیدا لاگ قدیمی‌تری نسبت به followerها داشته باشه، follower‌ها به درخواست رأی گیریش جواب منفی می‌دن و اون کاندیدا رهبر نمی‌شه. هم‌چنین Raft یک‌سری تضمین دیگه هم می‌ده که در ادامه می‌بینیم.

• امنیت انتخاب: در هر term حداکثر یک رهبر انتخاب می‌شه.
• حفظ اطلاعات قبلی: رهبر همیشه لاگ‌های جدید رو به لاگ‌های قدیمی اضافه می‌کنه و هیچ وقت لاگ‌های قدیمی رو حذف یا باطل نمی‌کنه.
• مطابقت لاگ‌ها: اگر دو لاگ یک عضو یکسان (term و index یکسان) داشته باشن، تمام اطلاعات اون دو لاگ تا این عضو کاملا یکسان خواهد بود.
• کامل بودن رهبر: اگر در مدت زمان یک term لاگی در لاگ‌های رهبر ثبت بشه، اون لاگ در همه‌ی term‌های آینده در لاگ‌های رهبر‌های کلاستر موجود خواهد بود.
• امنیت در index‌ها: اگر یکی از اعضای کلاستر لاگی رو با یک index ثبت نهایی کنه، هیچ عضو دیگه‌ای در کلاستر لاگی رو با index مشابه ثبت نخواهد کرد.

صبحت نهایی

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

با تشکر از سید مصطفی مشکاتی برای راهنمایی‌های فراوانش و محمد علی رضایی برای ویرایش و اصلاح متن.

منابع

1- Understanding distributed consensus with Raft

2- The log(from Linkedin engineering blog)

3- The Raft algorithm