Cloudflare بهتازگی از Meerkat رونمایی کرده است؛ یک سرویس اجماع توزیعشدهٔ آزمایشی که برای مدیریت صفحهٔ کنترل جهانی داخلی این شرکت طراحی شده است. Meerkat بر پایهٔ الگوریتم اجماع تازهای کار میکند که پژوهشگرانی به نام Tennage و Băsescu و همکارانشان آن را منتشر کردهاند و QuePaxa نام دارد (۲۰۲۳).
QuePaxa انتخابی غیرمعمول است؛ بیشتر سیستمهای اجماع از الگوریتمهای جاافتادهای مانند Raft، (Multi-)Paxos یا Viewstamped Replication استفاده میکنند. این الگوریتمها بهخوبی شناخته شدهاند، پیادهسازیهای بالغی دارند و معمولاً خوب کار میکنند.
با این حال، الگوریتمهای اجماع رایج در شبکههای گستردهای که اتصال و تأخیر شبکه در آنها نوسان دارد، یعنی شبکههایی مثل اینترنت که Meerkat در آن اجرا میشود، اغلب دچار مشکل میشوند. این الگوریتمها به این وابستهاند که یک فرایند رهبر در دسترس باشد و تأخیر آن قابل پیشبینی باشد. اگر رهبر از کار بیفتد، تأخیری بیش از حد معمول تجربه کند یا اتصالش قطع شود، کل سیستم اجماع کند میشود یا تا زمانی که رهبر جایگزین شود از دسترس خارج میشود. این وضعیت برای Meerkat پذیرفتنی نیست.
محیط استقرار جهانی Meerkat ما را به الگوریتم اجماع تازهتری به نام QuePaxa رساند که وعدهٔ پایداری بیشتر در برابر نوسانها را میدهد؛ تا حد زیادی به این دلیل که برای پیشرفت به رهبر متکی نیست. در این نوشته توضیح میدهیم چرا QuePaxa را انتخاب کردیم و الگوریتم QuePaxa چگونه کار میکند.
چه میسازیم و چرا متفاوت است
Meerkat یک سیستم توزیعشده است که در آن رپلیکاها بر سر یک لاگ مرتب از رویدادها به توافق میرسند و هر رویداد را یک الگوریتم اجماع تعیین میکند.
الگوریتمهای اجماع به گروهی از ماشینها امکان میدهند بر سر یک حقیقت مشترک واحد توافق کنند، حتی اگر برخی از این ماشینها از کار بیفتند یا اتصالشان قطع شود. این الگوریتمها تضمین مهمی ارائه میدهند: ماشینها هرگز مقادیر متناقض تعیین نمیکنند. این تضمین باعث میشود لاگ رپلیکاهای Meerkat هرگز از هم جدا نشود.
Meerkat از این لاگ مبتنی بر اجماع برای ارائهٔ برنامههایی مانند یک ذخیرهساز کلید-مقدار استفاده میکند که در آن هر ورودی لاگ یک دستور get یا put است. چون الگوریتم اجماع تضمین میکند لاگ رپلیکاها هرگز از هم جدا نشود، همهٔ آنها وضعیت کلید-مقدار (KV) یکسانی میسازند. سیستمهای مشابه مبتنی بر اجماع شامل Consul، etcd و Apache ZooKeeper میشوند.
اما برخلاف سیستمهای مشابه، Meerkat برای مقیاس جهانی طراحی شده است. یک خوشهٔ Meerkat ممکن است میان قارهها توزیع شده باشد و پیوندهایی آنها را به هم وصل کند که اغلب تأخیر بالا و متغیری دارند. این چیدمان برای سیستمهای اجماع غیرمعمول است؛ چنین سیستمهایی معمولاً در شبکههای کوچکتر و محلیتر مستقر میشوند و الزامات سختگیرانهای برای تأخیر دارند.
چالشهای اجماع در مقیاس جهانی
همهٔ الگوریتمهای اجماع تضمین میکنند که رپلیکاها بر سر یک مقدار واحد توافق کنند، اما بسیاری از آنها وقتی شرایط شبکه بدتر میشود (بدون آنکه ماشینها از کار بیفتند) بهطور نامتناسبی کند یا غیرقابلدسترس میشوند. ما خودمان این را از نزدیک دیدهایم: در سال ۲۰۲۰، خرابی جزئی یک سوئیچ شبکهٔ اصلی Cloudflare باعث شد یک سیستم مبتنی بر اجماع دچار افت عملکرد شود و داشبورد به مدت شش ساعت ۸۰ برابر کندتر از حد معمول کار کند. نکتهٔ مهم این است که سیستم هیچ دادهای را از دست نداد، اما تا رفع مشکل برای نوشتن در دسترس نبود و این پذیرفتنی نیست.
در حالت ایدهآل، یک الگوریتم اجماع باید بتواند با وجود جهشهای تأخیر و اتصالهای قطعشده، نه فقط خرابی رپلیکاها، پیشرفت کند. این مسئله در مقیاس جهانی بیشتر خود را نشان میدهد، جایی که احتمال اینکه خطاها از شبکه سرچشمه بگیرند و نه از سرورهای خودمان، بیشتر است.
بیایید دو ویژگی رایج الگوریتمهای اجماع را بررسی کنیم که میتوانند در شرایط خصمانهٔ شبکه به افت عملکرد منجر شوند: تداخل مخرب و تشخیص خطا. بعداً خواهیم دید QuePaxa چگونه از هر دوی این مشکلات دوری میکند.
تداخل مخرب و رهبران
Paxos را در نظر بگیرید؛ نیای راستین بیشتر الگوریتمهای اجماع. بسیاری از الگوریتمهای اجماع ساختار Paxos را به ارث بردهاند؛ هم بخشهای خوبش را و هم بخشهای نهچندان خوبش را.
بدون پرداختن به جزئیات فراوان، Paxos اینگونه کار میکند. دو نوع فرایند وجود دارد: پیشنهاددهندهها و پذیرندهها. بهطور انتزاعی، هدف سیستم این است که اکثریتی از پذیرندهها بر سر مقداری که یکی از پیشنهاددهندهها پیشنهاد کرده توافق کنند. دو فاز وجود دارد: فاز آمادهسازی و فاز پذیرش. در فاز آمادهسازی، هر پیشنهاددهندهای میتواند یک شمارهٔ رأی را برای اکثریتی از پذیرندهها بفرستد. این شمارهٔ رأی بهمنزلهٔ یک تعهد عمل میکند: پذیرندهها فقط پیشنهادهایی با همان شمارهٔ رأی یا بالاتر را میپذیرند. سپس در فاز پذیرش، پیشنهاددهنده پیشنهاد خود را همراه با شمارهٔ رأی دوباره برای اکثریتی از پذیرندهها میفرستد. اگر اکثریتی از پذیرندهها هنوز شمارهٔ رأی آن پیشنهاد را داشته باشند، اکثریت آن را میپذیرند و پیشنهاددهنده میتواند با خیال راحت آن پیشنهاد را تعیین کند.
چالشها زمانی پیش میآید که دو یا چند پیشنهاددهنده همزمان پیشنهادهایی ارائه کنند. بهطور مشخص، پیشنهاددهندهٔ دیگری میتواند شمارهٔ رأی بالاتر خود را میان دو فاز جا بیندازد و هر رأی پایینتری را مسدود کند. دو پیشنهاددهنده میتوانند بارها و بارها جلوی پیشرفت یکدیگر را بگیرند؛ یعنی عملاً بر سر پذیرش با هم رقابت کنند.
وقتی پیشنهاددهندهها اینگونه رقابت میکنند و جلوی یکدیگر را میگیرند، میگوییم میان آنها تداخل مخرب رخ داده است. تداخل مخرب با افزایش تعداد پیشنهاددهندههایی که رأی خودشان را پیشنهاد میکنند بدتر میشود. هر چه پیشنهاددهندههای همزمان بیشتر باشند، احتمال اینکه سیستم در چرخهٔ پیشنهاد دادن مکرر گیر کند بیشتر است. حتی اگر هیچیک از رپلیکاها از کار نیفتاده یا در دسترس نباشد، چند پیشنهاددهنده و شبکههای بدرفتار میتوانند Paxos را مسدود کنند. بهطور صوری میگوییم Paxos بدون این فرض که در نقطهای همهٔ پیامها در زمانی کراندار میرسند، زندهبودن (یعنی اینکه پیشنهادها در نهایت تعیین شوند) را تضمین نمیکند؛ فرضی که به آن همگامی جزئی میگویند.
برای جلوگیری از رقابت مداوم چند پیشنهاددهنده، بیشتر الگوریتمهای اجماع مستقرشده مانند Raft، Multi-Paxos و Viewstamped Replication یک پیشنهاددهندهٔ رهبر ویژه اضافه میکنند. رهبر تنها رپلیکایی است که میتواند پیشنهاد بدهد. متمرکز کردن قدرت پیشنهاد در یک رپلیکا به درخواستهای همزمان نظم میدهد، از رقابت پیشنهادها جلوگیری میکند و این مزیت را دارد که تصمیمگیری در یک رفتوبرگشت بهینهٔ شبکه انجام شود، نه دو رفتوبرگشت. تا زمانی که رهبر سالم است و شبکه رفتار درستی دارد، پروتکلهای مبتنی بر رهبر سریعاند.
اما هزینهٔ این کار این است که رهبر باید فعال و در دسترس بماند. وقتی رهبر از کار میافتد، بیش از حد کند میشود یا اتصالش با خوشه قطع میشود، سیستم متوقف میشود. تنها راه این است که رپلیکاهای باقیمانده تشخیص دهند رهبر از کار افتاده و رهبر جدیدی بهجای او انتخاب کنند.
وقتی بازیابی رهبر ناپایدار است
وقتی رهبر از کار میافتد، سیستم باید با انتخاب رهبر جدید بازیابی شود. جالب اینکه بازیابی رهبر اغلب همان مسیری است که تداخل مخرب از آن دوباره به یک سیستم مبتنی بر رهبر نفوذ میکند.
Raft را در نظر بگیرید. به دلایل ایمنی، Raft رهبر جدید را با رأی اکثریت انتخاب میکند. رپلیکایی که گمان میکند رهبر از کار افتاده، خود را نامزد رهبری اعلام میکند و از رپلیکاهای دیگر درخواست رأی میکند. اگر بیش از نیمی از رپلیکاها به آن نامزد رأی بدهند، او رهبر جدید میشود. اگر رأی ندهند، انتخاب تازهای برگزار میشود و نامزدها دوباره تلاش میکنند.
چند رپلیکا میتوانند نامزد شوند؛ تنها کاری که باید بکنند این است که تشخیص دهند رهبر از کار افتاده است. سپس ممکن است همهٔ نامزدها همزمان برای گرفتن رأی اکثریت تلاش کنند. مشکل این است که نامزدها بر سر رأی اکثریت رقابت میکنند؛ یعنی انتخابات Raft دچار همان تداخل مخربی میشود که در Paxos دیدیم: دو رپلیکا میتوانند بهطور متقابل مانع شوند که یکدیگر از اکثریت رأی بگیرند و رهبر شوند. هر چه انتخابات بیشتری شکست بخورد، رپلیکاهای بیشتری تلاش میکنند خودشان رهبر شوند.
حتی اگر رهبر دیگر خراب نباشد، انتخابات همچنان آنچه میتوانست عملکرد عادی سیستم باشد مختل میکند. به این وضعیت خرابی شبهپایدار میگویند: الگوی خرابیای که حتی پس از رفع علت اولیهٔ خرابی، خود را ادامه میدهد. یک قطعی دوثانیهای شبکه — یا یک سوئیچ شبکهٔ لحظهای معیوب — میتواند رهبر را معیوب جلوه دهد و انتخاب رهبر را تحمیل کند؛ انتخاباتی که ممکن است شکست بخورد و انتخابات بیشتری را تحمیل کند. قطعی در دو ثانیه تمام میشود، اما انتخابات میتواند بسیار بیشتر ادامه یابد، چون نامزدها همچنان جلوی یکدیگر را میگیرند.
در حالت ایدهآل، الگوریتمهای اجماع به هیچ فرایند بازیابیای نیاز نداشتند، چون این فرایندها پیچیدهاند، مستعد تداخلاند و منبع دیگری برای ازکارافتادگی ایجاد میکنند.
وقتی تشخیص خطا از مسیر خارج میشود
مشکل تداخل مخرب در انتخابات رهبر با تشخیص خطای شتابزده، بهویژه در شبکههای گسترده، تشدید میشود. برای اینکه الگوریتمهای اجماع مبتنی بر رهبر رهبر جدیدی انتخاب کنند، رپلیکاها ابتدا باید تشخیص دهند رهبر از کار افتاده است. اما اگر رپلیکاها خرابی رهبر را نادرست تشخیص دهند، سیستم ممکن است زمان بیش از حد زیادی را صرف بازیابی کند و به درخواستها رسیدگی نکند.
در یک سیستم توزیعشده که ماشینها با شبکه از هم جدا شدهاند، تشخیص خطا در نهایت به انتظارات وابسته است. یک فرایند نمیتواند مستقیماً ببیند که فرایندی راه دور از کار افتاده است؛ فقط میتواند ببیند پیام مورد انتظار رسیده یا نرسیده است. ما به الگوی ارتباطی قابل پیشبینی، مانند ضربانهای قلب یا تأییدها، نیاز داریم تا بفهمیم ماشینی سالم است. اگر پیام مورد انتظار در زمان مورد انتظار نرسد، به خطا مشکوک میشویم. دشواری در مدیریت همین انتظارات است.
در شبکههای واقعی، بهویژه شبکههای گسترده، پیامها همیشه در زمان پیشبینیشده نمیرسند. هیچ کران بالای تضمینشدهای برای زمان رسیدن پیامها وجود ندارد. این به معنای کندی یا غیرقابلاعتماد بودن شبکه نیست؛ بیشتر پیامها در همان زمانی میرسند که انتظار داریم. در عوض، جهشهای ناگهانی تأخیر و از دست رفتن اتصال میتوانند بهطور لحظهای و بدون هشدار، زمان عبور هر پیام از شبکه را افزایش دهند. چنین شبکههایی را ناهمگام مینامیم.
مشکل بزرگ شبکههای ناهمگام این است که اگر سروری در مدت زمانی مشخص پاسخ ندهد، واقعاً نمیدانیم سرور از کار افتاده یا شبکه فقط کند است؛ این دو از دید شبکه قابل تفکیک نیستند. هر تشخیصدهندهٔ خطای عملی باید بر اساس مدت انتظار در مقایسه با انتظارش حدس بزند و گاهی این حدس اشتباه خواهد بود.
در الگوریتمهای مبتنی بر رهبر، همین حدس است که دقیقاً انتخابات رهبر را به راه میاندازد. گاهی رهبر از کار افتاده است؛ گاهی پیامهایش دیر رسیدهاند یا اتصال بیصدا قطع شده است. پروتکل پیش از واکنش نمیتواند بداند کدامیک رخ داده است. اگر حدس اشتباه باشد و رپلیکایی رهبر را معیوب بداند در حالی که واقعاً معیوب نیست، انتخاباتی آغاز میشود و کل سیستم باید متوقف شود. تا زمانی که رهبر جایگزین نشود، هیچ پیشرفتی حاصل نمیشود — و همانطور که دیدیم، این کار میتواند مدتی طول بکشد.
تشخیص خطا در شبکههای ناهمگام اساساً مستعد خطاست و وقتی تشخیصدهنده اشتباه کند، با ازکارافتادگی روبهرو میشویم.
وقتی تشخیص خطا کند است
حتی وقتی تشخیصدهندهٔ خطا درست حدس میزند هم مشکلاتی وجود دارد. تشخیصدهندههای خطا با مشاهدهٔ پیامها روی شبکه به خرابیها واکنش نشان میدهند و بنابراین زمان پاسخ آنها باید با تأخیر شبکه مقیاس بگیرد؛ مهلت تشخیصدهنده نمیتواند کمتر از تأخیر شبکه باشد. به همین دلیل Raft معمولاً با مهلت انتخاب پنج تا ده برابر زمان رفتوبرگشت شبکه مستقر میشود. این مهلت باید بهقدر کافی بالا باشد تا به رهبر فرصت دهد زندهبودن خود را اعلام کند و از فعالشدن نادرست انتخابات جلوگیری شود. مهلت انتخاب میتواند بسیار کمتر از این باشد، اما چون انتخابات رهبر سیستم را کاملاً متوقف میکند، مهلتها معمولاً محافظهکارانه بالا تنظیم میشوند.
تقریباً میتوان گفت رفتوبرگشت تا نیمهٔ راه دورترین نقطهٔ جهان با صدها میلیثانیه سنجیده میشود. اگر مهلت انتخاب چند رفتوبرگشت باشد، تشخیص هماهنگکنندهٔ ازکارافتاده حدود یک ثانیه طول میکشد. حتی وقتی تشخیص خطا کاملاً دقیق است، کند است و در شبکههای جهانی با تأخیر بالا کندترین حالت را دارد. تا زمانی که تشخیصدهنده واکنش نشان دهد، سیستم از کار افتاده است.
چرا QuePaxa انتخاب مناسب است
دریافتیم که هر الگوریتمی که به رهبر سختگیرانه یا مهلتهای دقیق متکی باشد، در یک سیستم اجماع که روی اینترنت اجرا میشود ناگزیر متوقف خواهد شد. به دنبال الگوریتمهای اجماعی گشتیم که برای محیطهای ناهمگام طراحی شدهاند؛ پروتکلهایی که برای کارکردن به شبکهٔ خوشرفتار یا زمانبندی دقیق متکی نیستند. این ما را به QuePaxa رساند که در سال ۲۰۲۳ توسط Tennage و Băsescu و همکارانشان منتشر شد.
قابلتوجهترین ویژگی QuePaxa این است که در شرایط مطلوب شبکه میتواند بهطور کارآمد در یک رفتوبرگشت به اجماع برسد، اما در برابر جهشهای تأخیر، مشکلات اتصال و خرابی سرور هم عملکردش را بهنرمی کاهش میدهد. QuePaxa این کار را با حل دقیقاً همان مشکلاتی که بحث کردیم، از طریق سه انتخاب طراحی کلیدی انجام میدهد: داشتن رهبر اختیاری، حذف کامل اتکا به تشخیص خطا، و طراحی برای تداخل سازنده میان پیشنهاددهندهها.
در QuePaxa، بسیار شبیه به Paxos، دو نقش وجود دارد: پیشنهاددهندهها و رکوردرها. پیشنهاددهندهها پیشنهادهایی برای تعیین ارائه میکنند و رکوردرها بهعنوان واسطه میان پیشنهاددهندهها عمل میکنند و هر پیشنهادی را که میبینند ثبت میکنند.
در QuePaxa، بهجای اینکه پیشنهاددهندهها برای تعیین پیشنهادهای خودشان رقابت کنند، بهصورت همکارانه به سمت پیشنهادی حرکت میکنند که همه از آن پشتیبانی میکنند. QuePaxa این کار را با اختصاص یک اولویت به هر پیشنهاد، در قالب یک عدد تصادفی، انجام میدهد. رهبر اختیاری یک اولویت حداکثری انحصاری میگیرد. در حین اجرا، پیشنهاددهندهها پیشنهادهای خود را به رکوردرها میفرستند و رکوردرها پیشنهاد را به سایر پیشنهاددهندههای فعال منتشر میکنند. وقتی پیشنهاددهندهها پیشنهادی با اولویت بالاتر از پیشنهاد خود از یک رکوردر دریافت میکنند، آن پیشنهاد جدید را بهعنوان پیشنهاد خود برمیگزینند؛ یعنی شروع به پخش پیشنهاد با اولویت بالاتر میکنند. بهطور کلی، پیشنهاددهندهها در QuePaxa با هم کار میکنند تا بر سر پیشنهادی با بالاترین اولویت که بهطور جمعی میشناسند توافق کنند. این یعنی پیشنهاددهندهها نمیتوانند یکدیگر را بهطور نامحدود از تعیین یک پیشنهاد بیرون نگه دارند.
یک نکتهٔ احتیاطی این است که ممکن است انتشار پیشنهادها بهقدر کافی خوب نباشد که بر سر یک پیشنهاد توافق شود و بنابراین پیشنهاددهندهها باید دوباره تلاش کنند؛ هر تلاش یک دور محسوب میشود. اما هر چه پیشنهاددهندههای بیشتری پیشنهاد بدهند، احتمال همگرایی آنها روی پیشنهاد با بالاترین اولویت بیشتر میشود. همین QuePaxa را به یک الگوریتم تصادفی تبدیل میکند: اولویتهای تصادفی تولیدشده توسط پیشنهاددهندههای غیررهبر بهاحتمال زیاد — اما نه با تضمین — در یک دور به اجماع بر سر بالاترین اولویت شناختهشده میرسند. با این حال، با تعداد کافی دور، تضمین میشود که پیشنهاددهندهها بر سر یک پیشنهاد توافق کنند.
یک پیشنهاددهنده بهعنوان رهبر تعیین میشود. رهبر تنها پیشنهاددهندهای است که میتواند در یک رفتوبرگشت تصمیم بگیرد. رهبر همیشه با بالاترین اولویت پیشنهاد میدهد؛ اگر رهبر بداند پیشنهادش را پیش از هر پیشنهاددهندهٔ دیگری پخش کرده است، میتواند فوراً تصمیم بگیرد. کلاینتها مجبور نیستند درخواستهایشان را به رهبر بفرستند؛ هر پیشنهاددهندهای میتواند پیشنهاد بدهد. اگر رهبر از کار بیفتد، کلاینتها میتوانند به ارسال درخواست به سایر پیشنهاددهندهها ادامه دهند. رهبر کاملاً اختیاری است. رهبر فقط احتمال بیشتری دارد که تصمیم بگیرد و این کار را سریعتر، در یک رفتوبرگشت، انجام دهد.
اما چون رهبر تنها کسی است که میتواند در یک رفتوبرگشت تصمیم بگیرد، میخواهیم هر جا ممکن است از آن استفاده کنیم. برای بهرهگیری از این مسیر سریع بدون ایجاد نقطهٔ شکست واحد، کلاینتهایی که پیشنهاد به سیستم میفرستند ریسک را پخش میکنند: درخواستهای پیشنهاد خود را به همهٔ رپلیکاها میفرستند و رپلیکاهای غیررهبر برای مدت کوتاهی صبر میکنند تا رهبر بتواند خودش پیشنهاد بدهد و تصمیم بگیرد. در پیادهسازی خودمان از QuePaxa، در واقع از مقاله منحرف شدهایم و بهجای رپلیکاها، کلاینتها را وادار میکنیم مهلت پوششی (هج) را منتظر بمانند تا تعداد پیامهایی که روی شبکه میفرستیم کاهش یابد، اما نتیجهٔ کلی همان است.
این مهلت پوششی با مهلتهای استفادهشده در Raft یا Multi-Paxos بسیار متفاوت است. این مهلت تشخیص خطا نیست و بنابراین به تأخیر شبکه محدود نمیشود؛ بهصورت محلی توسط رپلیکاها تعیین میشود و میتواند به هر اندازهای که بخواهند کوچک باشد. در Raft، داشتن مهلتی پنجمیلیثانیهای در شبکهای با تأخیر ۱۰۰ میلیثانیهای سیستم را کاملاً قفل میکرد. اما در QuePaxa، مهلت پوششی پنجمیلیثانیهای فقط تعداد پیشنهاددهندههای فعال را افزایش میدهد.
اما پوششدهی رایگان نیست: هر چه پیشنهاددهندهها بیشتر باشند، پیشنهادهای بیشتری پخش میشود و احتمال اینکه رپلیکاها در یک دور به تصمیم نرسند بیشتر میشود. در عوض، پوششدهی یک موازنه فراهم میکند: میتوانیم با کاهش مهلت پوششی سریعتر به تغییرات رهبر واکنش نشان دهیم، اما هزینهٔ پهنای باند اضافی میپردازیم و ممکن است تصمیمگیری بیشتر طول بکشد. این موازنهای است که با کمال میل حاضریم انجام دهیم.
اگر رهبر QuePaxa از کار بیفتد، میتوانیم به هر سرعتی که بخواهیم بازیابی کنیم؛ ما به تأخیر شبکه محدود نیستیم. QuePaxa اینگونه از تشخیص خطا دوری میکند: چون هر کسی میتواند پیشنهاد بدهد، نه فقط رهبر، QuePaxa میتواند با پوششدهی بهصورت پیشدستانه با خرابی رهبر مقابله کند، نه اینکه به خرابیها واکنش نشان دهد.
QuePaxa در زیر پوستش چگونه کار میکند
برای درک اینکه QuePaxa چگونه همهٔ این ویژگیهای خوب را به ما میدهد، بیایید ببینیم QuePaxa در واقع چگونه کار میکند.
QuePaxa در دورهایی متشکل از چهار فاز کار میکند. اگر پیشنهادی در فاز آخر تعیین نشده باشد، دور جدیدی آغاز میشود و QuePaxa از نو شروع میکند. در آغاز هر فاز، پیشنهاددهندهها پیشنهاد فعلی برگزیدهٔ خود را برای همهٔ رکوردرها پخش میکنند. وقتی پیشنهاددهندهای از اکثریتی از رکوردرها پاسخ دریافت میکند، به فاز بعدی میرود. طرح کلی فازها اینگونه است:
فاز ۰ (پیشنهاد و پذیرش): پیشنهاددهندهها بهصورت تصادفی یک اولویت انتخاب میکنند، پیشنهادهای خود را به رکوردرها میفرستند و پیشنهادی با بالاترین اولویت را که از اکثریتی از رکوردرها دریافت میکنند برمیگزینند. اگر دور اول باشد و رهبر بداند پیشنهادش نخست به اکثریتی از رکوردرها رسیده است، رهبر فوراً تصمیم میگیرد.
فاز ۱ (پخش): پیشنهاددهندهها پیشنهاد برگزیدهٔ خود را به اکثریتی از رکوردرها پخش میکنند.
فاز ۲ (بررسی و تصمیم): پیشنهاددهندهها از اکثریتی از رکوردرها بالاترین اولویت پیشنهاد مشاهدهشده در فاز قبل را میپرسند. اگر با پیشنهاد برگزیدهٔ خودشان مطابقت داشته باشد، آن را تعیین میکنند.
فاز ۳ (انتقال به جلو): هر پیشنهاددهندهای که موفق به تصمیمگیری نشده، با پذیرش بهترین پیشنهادی که از اکثریتی از رکوردرها میبیند، برای دور بعد آماده میشود.
بیایید چند نمونه اجرا را مرور کنیم و بررسی کنیم هر فاز چگونه به رفتار کلی مورد نظرمان از QuePaxa کمک میکند. هر اجرا دو پیشنهاددهنده (که یکیشان رهبر است) و سه رکوردر خواهد داشت.
مسیر سریع رهبر (فاز ۰): فاز اول سه کار مهم انجام میدهد: اولویتها را تصادفی میکند (کاری که برای دور زدن قضیهٔ عدمامکان FLP باید انجام دهد)، بررسی میکند آیا رهبر نخست به اکثریتی از پشتیبانی رسیده است یا نه، و اگر رهبر نرسیده باشد به همگرایی پیشنهاددهندهها کمک میکند. پیشنهاد رهبر تصادفی نیست و همیشه بالاترین اولویت ممکن را دارد.
در مثال بالا، پیشنهاد رهبر پیش از هر کس دیگری به اکثریتی از رکوردرها میرسد و پاسخهایی دریافت میکند که آن را تأیید میکنند. رهبر میتواند با خیال راحت فوراً تصمیم بگیرد. این ممکن است خطرناک به نظر برسد، اما به لطف ویژگیای به نام اشتراک اکثریتها کاملاً ایمن است: هر دو اکثریت از رکوردرها همیشه حداقل یک رکوردر مشترک دارند. چون رهبر به اکثریت رسیده است، هر پیشنهاددهندهٔ دیگری که از اکثریتی پرسوجو کند ناگزیر با پیشنهاد رهبر روبهرو میشود و آن را برمیگزینند. چون پیشنهاد رهبر بالاترین اولویت را دارد، هر پیشنهاددهندهٔ دیگری پیشنهاد رهبر را برمیگزینند. تعیین هر پیشنهاد دیگری ناممکن است.
مسیر کند همزمان (فازهای ۰ تا ۳): اما وقتی پیشنهاددهندههای همزمان وجود دارند، تضمین نمیشود که رهبر فوراً تصمیم بگیرد. ممکن است رهبر نتواند نخست به اکثریتی از رکوردرها برسد، یا پاسخی تک دریافت کند که از پیشنهاددهندهٔ دیگری پشتیبانی میکند. بیایید ببینیم وقتی پیشنهاددهندهٔ دیگری با رهبر رقابت میکند چه اتفاقی میافتد.
فاز ۰: در تصویر زیر، پیشنهاددهندهٔ دوم (که با رنگ قرمز نشان داده شده) پیش از رهبر به رکوردرهای دوم و سوم میرسد. مسیر سریع مسدود میشود. پیشنهاددهندهها بهجای رقابت، پیشنهادی با بالاترین اولویت را که از اکثریتی دریافت میکنند برمیگزینند و به فاز دوم میروند. دو پیشنهاددهنده میتوانستند در همین فاز هر دو به پیشنهاد رهبر همگرا شوند. برای روشنشدن مطلب، مثال ما با تأخیر انداختن در پیامهای رهبر از همگرایی جلوگیری میکند.
فاز ۱: پیشنهاددهندهها پیشنهادی را که همین حالا در فاز ۰ پذیرفتهاند به اکثریتی از رکوردرها پخش میکنند. رکوردرها بالاترین اولویت پیشنهادی را که مشاهده میکنند پیگیری میکنند. این گامی ساده اما حیاتی است: مانع میشود پروتکل بعداً بر سر پیشنهادی با اولویت پایینتر تصمیم بگیرد. این هم باز به لطف اشتراک اکثریتها ممکن است: هر اکثریتی که در فاز بعد پرسوجو شود باید حداقل یک رکوردر را شامل شود که در این فاز پیشنهاد برگزیدهشده را دیده است. برای روشنشدن مطلب، در این فاز با تأخیر انداختن در پیام رهبر به رکوردر سوم از همگرایی جلوگیری میکنیم تا آن رکوردر پیشنهاد رهبر را نپذیرد.
فاز ۲: حالا تصمیمگیری میتواند رخ دهد. هر پیشنهاددهنده با پرسیدن بالاترین اولویت پیشنهاد مشاهدهشده در فاز ۱ از اکثریتی از رکوردرها تعیین میکند آیا پیشنهادی با اولویت بالاتر پشتیبانی کافی برای پیشی گرفتن از پیشنهاد خودش را به دست آورده است یا نه. اگر بالاترین پیشنهاد بازگشته هنوز همان پیشنهاد برگزیدهٔ خودشان باشد، تصمیم میگیرند. در نمودار ما، رهبر میبیند که اکثریت پیشنهاد خودش را بازگرداندهاند و با خیال راحت تصمیم میگیرد. پیشنهاددهندهٔ دیگر خلاصههای متناقضی دریافت میکند و بنابراین هنوز نمیتواند تصمیم بگیرد. مانند فاز ۱، رکوردرها بالاترین اولویت پیشنهادی را که دریافت کردهاند پیگیری میکنند.
فاز ۳: اگر پیشنهاددهندهای در فاز ۲ تصمیم نگیرد، به فاز نهایی پاکسازی میرود تا برای دور بعد آماده شود. پیشنهاددهندهها پیشنهادهای خود را دوباره پخش میکنند و بهترین پیشنهادی را که میان اکثریتی از رکوردرها مییابند برمیگزینند. در اینجا، پیشنهاددهندهٔ باقیمانده پیشنهاد تعیینشده را کشف میکند و آن را برمیگزینند و به دور بعد میرود.
این کار عمدی است: اگر در فاز قبل تصمیمی گرفته شده باشد، اکثریتی از رکوردرها آن پیشنهاد را خواهند داشت و تضمین میشود که هر پیشنهاددهندهٔ باقیماندهای آن را برمیگزینند. اینجا نمونهٔ دیگری از همکاری میان پیشنهاددهندهها را میبینیم: حتی وقتی یک دور شکست میخورد، پیشنهاددهندهها تلاش میکنند با همان پیشنهاد به دور بعد بروند.
رفتن به دور بعد: پس از فاز چهارم، پیشنهاددهندهها به دور بعد میروند. در این نقطه، دیگر مسیر سریع رهبر وجود ندارد و تنها راه تصمیمگیری، همگرایی در فاز سوم است. مهم اینکه به لطف پذیرش پیشنهاد، تصمیمگیری با پیشرفت دورها بهصورت نمایی آسانتر میشود. مقالهٔ QuePaxa پیشبینی میکند هر دور ۵۰٪ شانس تصمیمگیری دارد، اما در عمل این احتمال به لطف همگرایی بسیار بالاتر است.
با کنار هم گذاشتن هر چهار فاز، میتوانیم ببینیم QuePaxa مقاومت خود را از کجا میگیرد. فاز اول مسیر سریع یکرفتوبرگشتی را به رهبر میدهد. اگر آن مسیر سریع شکست بخورد، اولویتهای تصادفی و پذیرش پیشنهاد به پیشنهاددهندهها کمک میکند بهجای رقابت، همگرا شوند. فازهای دوم و سوم به لطف اشتراک اکثریتها تصمیمگیری را ایمن میکنند و فاز چهارم، در صورتی که پیشنهاددهندهها تصمیم نگیرند، آنچه پیشنهاددهندهها آموختهاند را به دور بعد منتقل میکند.
هیچ پیشنهاددهندهای مجبور نیست پیش از پیشرفت، تشخیص دهد رهبر از کار افتاده است و یک دور شکستخورده کار انجامشده را دور نمیریزد. وقتی شبکه رفتار درستی دارد، QuePaxa سریع است. وقتی ندارد، QuePaxa به حرکت ادامه میدهد.
QuePaxa چگونه Meerkat را ممکن میکند
در ارزیابیهای خودمان از Meerkat، که سرورهایی در تقریباً همهٔ قارهها داشتیم، مستقیماً تأثیر QuePaxa بر عملکرد کلی و دسترسپذیری سیستم را تجربه کردهایم. Meerkat حتی وقتی رهبر از کار میافتد، اتصالش قطع میشود یا فقط کند میشود، به پردازش درخواستها ادامه میدهد. هیچوقت ندیدهایم که کاملاً متوقف شود. این دقیقاً همان چیزی است که میخواستیم.
نرخ رسیدگی Meerkat به درخواستها هم بهطور کلی قابل پیشبینی بوده است. بیشتر تصمیمها — بیش از ۹۵٪ — توسط رهبر در فاز اول گرفته میشوند که توان عملیاتی ما را نسبتاً پایدار نگه میدارد. در مواردی که تصمیمی در فاز اول گرفته نمیشود، توان عملیاتی بهطور لحظهای افت میکند و حداکثر به یکسوم نرخ معمول میرسد؛ نشانهٔ اینکه برای تصمیمگیری به سه رفتوبرگشت — یعنی سه فاز — نیاز بوده است، نه فقط یکی. سیستم کند میشود، اما از حرکت نمیایستد.
QuePaxa این امکان را هم به ما میدهد که در حین اجرای خوشه، با اطمینان تعیین کنیم کدام رکوردر نقش رهبر را ایفا کند. چون رهبر تنها عامل تصمیمگیری نیست و پیشنهاددهندهها با هم همکاری میکنند، رهبری که موقتاً بهینه نیست چندان محدودکننده نمیشود؛ در الگوریتمهای دیگر، پیکربندی نادرست رهبر میتواند سیستم را کاملاً متوقف کند. ما میتوانیم بهصورت پویا تنظیم کنیم کدام پیشنهاددهنده رهبر باشد، بدون آنکه نگرانی زیادی دربارهٔ تأثیر آن بر پایداری خوشهٔ Meerkat داشته باشیم.
آنچه در ادامه نشان خواهیم داد
طراحی Meerkat برای یک شبکهٔ جهانی ما را ناچار کرد دوباره بررسی کنیم که چگونه به اجماع توزیعشده نزدیک میشویم. بهجای پایبندی به پیشفرضهای آشنایی که با محدودیتهای ما چندان سازگار نبودند، به دههها پژوهش دانشگاهی و صنعتی روی آوردیم. همین جستوجو ما را به QuePaxa رساند.
انتخاب QuePaxa یعنی انتخاب مسیری کمرفتوآمدتر. این الگوریتم به اندازهٔ Raft یا Paxos در محیط عملیاتی آزموده نشده است و ما طراحی اصلی توقف-خرابی آن را نیز گسترش میدهیم تا بازیابی پس از خرابی را پشتیبانی کند. این کار مهندسی دقیق و شواهد قویتری از درستی، بیش از آنچه در سیستمهای معمول لازم است، میطلبد.
به همین دلیل است که پیادهسازی QuePaxa و کل Meerkat را بهصورت رسمی و همراه با شبیهسازی گسترده و آزمون تزریق خطا بررسی میکنیم. نوشتههای بعدی این مجموعه توضیح خواهند داد چگونه درستی Meerkat و پیادهسازی Rust آن از QuePaxa را بررسی میکنیم، چگونه خرابیهایی را آزمایش میکنیم که بازتولیدشان در محیط عملیاتی دشوار است، بنچمارکها چه میگویند و در مسیر تبدیل یک پروتکل دانشگاهی به یک سیستم عملیاتی چه آموختهایم.
برای اطلاع از بهروزرسانیهای بعدی Meerkat، وبلاگ Cloudflare را دنبال کنید و اگر میخواهید دربارهٔ پژوهش در Cloudflare بیشتر بدانید، نگاهی به کارهای ما در Cloudflare Research بیندازید.



