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

بنابراین، بیایید تصور کنیم. 5 گربه در اتاق قفل شده اند و برای اینکه صاحبش را بیدار کنند، همه آنها باید در این مورد بین خودشان توافق کنند، زیرا فقط می توانند در را باز کنند که پنج تای آنها به آن تکیه داده باشند. اگر یکی از گربه ها گربه شرودینگر باشد و گربه های دیگر از تصمیم او اطلاعی نداشته باشند، این سوال پیش می آید: "چگونه می توانند این کار را انجام دهند؟"

در این مقاله به بیان ساده در مورد مولفه نظری دنیای سیستم های توزیع شده و اصول عملکرد آنها خواهم پرداخت. من همچنین به صورت سطحی ایده اصلی زیربنای Paxos را بررسی خواهم کرد.

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

در اصل، ضمانت‌هایی که ما داریم، ضمانت‌های تامین‌کننده هستند. آنها در مستندات به شرح زیر توضیح داده شده اند: "این سرویس کاملاً قابل اعتماد است، دارای یک SLA است، نگران نباشید، همه چیز به طور توزیع شده همانطور که انتظار دارید کار خواهد کرد."

ما به بهترین ها اعتقاد داریم، زیرا افراد باهوش از شرکت های بزرگ به ما اطمینان دادند که همه چیز خوب خواهد بود. ما این سؤال را نمی پرسیم: در واقع چرا این کار اصلاً می تواند کار کند؟ آیا توجیه رسمی برای عملکرد صحیح چنین سیستم هایی وجود دارد؟

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

اکثر سیستم های توزیع شده مدرن از الگوریتم اجماع Paxos و تغییرات مختلف آن استفاده می کنند. جالب ترین چیز این است که اعتبار و اصولاً امکان وجود این الگوریتم را می توان به سادگی با یک قلم و کاغذ اثبات کرد. در عمل، این الگوریتم در سیستم‌های بزرگی که روی تعداد زیادی گره در ابرها اجرا می‌شوند، استفاده می‌شود.

تصویری روشن از آنچه در ادامه مورد بحث قرار خواهد گرفت: وظیفه دو ژنرالبیایید نگاهی به یک گرم کردن بیاندازیم وظیفه دو ژنرال.

ما دو ارتش داریم - قرمز و سفید. نیروهای سفیدپوست در شهر محاصره شده مستقر هستند. نیروهای سرخ به رهبری ژنرال های A1 و A2 در دو طرف شهر مستقر هستند. وظیفه مو قرمزها حمله به شهر سفید و پیروزی است. با این حال، ارتش هر ژنرال سرخ به طور جداگانه کوچکتر از ارتش سفید است.

شرایط پیروزی قرمزها: هر دو ژنرال باید همزمان حمله کنند تا برتری عددی نسبت به سرخپوشان داشته باشند. برای انجام این کار، ژنرال های A1 و A2 باید با یکدیگر به توافق برسند. اگر همه جداگانه حمله کنند، مو قرمزها شکست خواهند خورد.

برای دستیابی به توافق، ژنرال های A1 و A2 می توانند از طریق قلمرو شهر سفید برای یکدیگر پیام رسان بفرستند. پیام رسان ممکن است با موفقیت به یک ژنرال متحد برسد یا ممکن است توسط دشمن رهگیری شود. سوال: آیا چنین ترتیبی از ارتباطات بین ژنرال های مو قرمز وجود دارد (توالی ارسال پیام رسان از A1 به A2 و بالعکس از A2 به A1) که در آن تضمین می شود که آنها در مورد حمله در ساعت X توافق کنند. تضمین به این معنی است که هر دو ژنرال تأیید صریح خواهند داشت که یک متحد (ژنرال دیگر) قطعاً در زمان تعیین شده X حمله خواهد کرد.

فرض کنید A1 یک پیام رسان با این پیام به A2 ارسال می کند: "امروز در نیمه شب حمله کنیم!" ژنرال A1 نمی تواند بدون تایید ژنرال A2 حمله کند. اگر پیام رسان A1 وارد شده باشد، ژنرال A2 تأییدیه را با این پیام ارسال می کند: "بله، بیایید امروز سفیدها را بکشیم." اما اکنون ژنرال A2 نمی داند که آیا پیام رسان او رسیده است یا نه، او هیچ تضمینی ندارد که حمله همزمان باشد یا خیر. اکنون General A2 دوباره نیاز به تأیید دارد.

اگر ارتباطات آنها را بیشتر توضیح دهیم، روشن می شود که صرف نظر از تعداد چرخه های تبادل پیام، هیچ راهی برای تضمین اینکه هر دو ژنرال پیام های خود را دریافت کرده اند وجود ندارد (با فرض اینکه هر یک از پیام رسان ها می توانند رهگیری شوند).

مسئله دو ژنرال یک تصویر عالی از یک سیستم توزیع شده بسیار ساده است که در آن دو گره با ارتباط غیرقابل اعتماد وجود دارد. این بدان معنی است که ما تضمین 100٪ برای همگام شدن آنها نداریم. مشکلات مشابه فقط در مقیاس بزرگتر بعداً در مقاله مورد بحث قرار می گیرند.

ما مفهوم سیستم های توزیع شده را معرفی می کنیم

یک سیستم توزیع شده گروهی از رایانه ها است (از این پس آنها را گره می نامیم) که می توانند پیام ها را مبادله کنند. هر گره منفرد نوعی موجودیت مستقل است. یک گره می تواند وظایف خود را پردازش کند، اما برای برقراری ارتباط با گره های دیگر، نیاز به ارسال و دریافت پیام دارد.

اینکه دقیقاً چگونه پیام ها پیاده سازی می شوند ، از چه پروتکل هایی استفاده می شود - در این زمینه برای ما جالب نیست. مهم است که گره های یک سیستم توزیع شده بتوانند با ارسال پیام، داده ها را با یکدیگر مبادله کنند.

خود تعریف چندان پیچیده به نظر نمی رسد، اما باید در نظر بگیریم که یک سیستم توزیع شده دارای تعدادی ویژگی است که برای ما مهم است.

ویژگی های سیستم های توزیع شده

1. هم زمان - امکان وقوع رویدادهای همزمان یا همزمان در سیستم. علاوه بر این، تا زمانی که ترتیب مشخصی از وقوع این رویدادها را نداشته باشیم، رویدادهایی را که در دو گره مختلف رخ می‌دهند، به طور بالقوه همزمان در نظر خواهیم گرفت. اما، به عنوان یک قاعده، ما آن را نداریم.
2. بدون ساعت جهانی. به دلیل نبود ساعت جهانی، ترتیب مشخصی از رویدادها نداریم. در دنیای معمولی مردم، ما به این واقعیت عادت کرده ایم که ساعت و زمان کاملاً داریم. همه چیز در مورد سیستم های توزیع شده تغییر می کند. حتی ساعت‌های اتمی بسیار دقیق هم حرکت می‌کنند، و ممکن است موقعیت‌هایی پیش بیاید که نتوانیم بگوییم کدام یک از دو رویداد اول اتفاق افتاده است. بنابراین نمی توانیم به زمان هم تکیه کنیم.
3. شکست مستقل گره های سیستم. مشکل دیگری وجود دارد: ممکن است مشکلی پیش بیاید زیرا گره های ما برای همیشه دوام نمی آورند. ممکن است هارد دیسک از کار بیفتد، ماشین مجازی موجود در فضای ابری ممکن است راه اندازی مجدد شود، شبکه ممکن است چشمک بزند و پیام ها از بین بروند. علاوه بر این، ممکن است شرایطی وجود داشته باشد که گره ها کار کنند، اما در عین حال بر علیه سیستم کار کنند. آخرین دسته از مشکلات حتی یک نام جداگانه دریافت کردند: مشکل ژنرال های بیزانسی. محبوب ترین نمونه از یک سیستم توزیع شده با این مشکل، بلاک چین است. اما امروز ما این دسته خاص از مشکلات را در نظر نخواهیم گرفت. ما به شرایطی علاقه مند خواهیم بود که در آن یک یا چند گره ممکن است از کار بیفتند.
4. مدل های ارتباطی (مدل های پیام رسانی) بین گره ها. ما قبلاً ثابت کرده‌ایم که گره‌ها با تبادل پیام‌ها با هم ارتباط برقرار می‌کنند. دو مدل پیام رسانی معروف وجود دارد: همزمان و ناهمزمان.

مدل های ارتباط بین گره ها در سیستم های توزیع شده

مدل سنکرون - ما به یقین می دانیم که یک دلتای محدود زمانی وجود دارد که طی آن پیام تضمین شده از یک گره به گره دیگر می رسد. اگر این زمان گذشته باشد و پیام نرسیده باشد، به جرات می توان گفت که گره شکست خورده است. در این مدل زمان انتظار قابل پیش بینی داریم.

مدل ناهمزمان – در مدل‌های ناهمزمان، زمان انتظار محدود است، اما چنین دلتای زمانی وجود ندارد که بتوانیم تضمین کنیم که گره از کار افتاده است. آن ها زمان انتظار برای یک پیام از یک گره می تواند خودسرانه طولانی باشد. این یک تعریف مهم است و در ادامه در مورد آن صحبت خواهیم کرد.

مفهوم اجماع در سیستم های توزیع شده

قبل از تعریف رسمی مفهوم اجماع، بیایید مثالی از موقعیتی را در نظر بگیریم که در آن به آن نیاز داریم، یعنی - تکرار ماشین حالت.

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

به عبارت دیگر: هیچ یک از گره ها مخالفت نکردند که اطلاعات مرتبط بیشتری دارد و مقدار پیشنهادی نادرست بود. توافق بین گره ها و توافق بر روی یک مقدار صحیح پذیرفته شده واحد، توافق در یک سیستم توزیع شده است. در مرحله بعد، ما در مورد الگوریتم هایی صحبت خواهیم کرد که به یک سیستم توزیع شده اجازه می دهد تضمین شود که به توافق برسد.

به طور رسمی تر، ما می توانیم یک الگوریتم اجماع (یا به سادگی یک الگوریتم اجماع) را به عنوان یک تابع مشخص تعریف کنیم که یک سیستم توزیع شده را از حالت A به حالت B منتقل می کند. علاوه بر این، این حالت توسط همه گره ها پذیرفته می شود و همه گره ها می توانند آن را تایید کنند. همانطور که مشخص است، این کار به هیچ وجه آنقدرها که در نگاه اول به نظر می رسد پیش پا افتاده نیست.

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

الگوریتم اجماع باید سه ویژگی داشته باشد تا سیستم به وجود خود ادامه دهد و در حرکت از حالتی به حالت دیگر پیشرفت داشته باشد:

1. توافق - همه گره هایی که به درستی کار می کنند باید مقدار یکسانی داشته باشند (در مقالات به این ویژگی به عنوان ویژگی ایمنی نیز گفته می شود). تمام گره‌هایی که در حال حاضر کار می‌کنند (از بین نرفته‌اند یا ارتباط خود را با دیگران از دست نداده‌اند) باید به توافق برسند و مقدار مشترک نهایی را بپذیرند.

   درک این نکته مهم است که گره‌های موجود در سیستم توزیع‌شده مورد نظر ما می‌خواهند توافق کنند. یعنی اکنون در مورد سیستم هایی صحبت می کنیم که در آنها چیزی به سادگی می تواند خراب شود (مثلاً برخی از گره ها از کار می افتد) اما در این سیستم قطعاً هیچ گره ای وجود ندارد که عمداً علیه دیگران کار کند (وظیفه ژنرال های بیزانسی). با توجه به این ویژگی، سیستم ثابت باقی می ماند.

2. تمامیت - اگر همه گره های به درستی کار می کنند مقدار یکسانی را ارائه دهند v، به این معنی که هر گره ای که به درستی کار می کند باید این مقدار را بپذیرد v.
3. ختم - تمام گره‌هایی که به درستی کار می‌کنند، در نهایت مقدار معینی را به خود می‌گیرند (ویژگی زنده بودن)، که به الگوریتم اجازه می‌دهد در سیستم پیشرفت کند. هر گره ای که به درستی کار می کند دیر یا زود باید مقدار نهایی را بپذیرد و آن را تأیید کند: "برای من، این مقدار درست است، من با کل سیستم موافقم."

نمونه ای از نحوه عملکرد الگوریتم اجماع

در حالی که ممکن است ویژگی های الگوریتم کاملاً مشخص نباشد. بنابراین، ما با یک مثال نشان خواهیم داد که ساده‌ترین الگوریتم اجماع در سیستمی با مدل پیام‌رسانی همزمان چه مراحلی را طی می‌کند، که در آن همه گره‌ها مطابق انتظار عمل می‌کنند، پیام‌ها از بین نمی‌روند و هیچ چیز خراب نمی‌شود (آیا این واقعاً اتفاق می‌افتد؟).

1. همه چیز با پیشنهاد ازدواج (پیشنهاد) شروع می شود. بیایید فرض کنیم یک کلاینت به یک گره به نام "گره 1" متصل شده و یک تراکنش را شروع کرده و یک مقدار جدید را به گره ارسال می کند - O. از این پس، "گره 1" را فراخوانی می کنیم. پیشنهاد. به عنوان یک پیشنهاد دهنده، "گره 1" اکنون باید به کل سیستم اطلاع دهد که داده های جدیدی دارد، و به همه گره های دیگر پیام می فرستد: "ببین! معنی "O" به من آمد و می خواهم آن را بنویسم! لطفاً تأیید کنید که "O" را نیز در گزارش خود ثبت خواهید کرد.

   

2. مرحله بعدی رای دادن به مقدار پیشنهادی (Voting) است. این برای چیست؟ ممکن است اتفاق بیفتد که گره‌های دیگر اطلاعات جدیدتری دریافت کرده‌اند و داده‌های مربوط به همان تراکنش را داشته باشند.

   
   
   هنگامی که گره "Node 1" پیشنهاد خود را ارسال می کند، سایر گره ها گزارش های خود را برای داده های مربوط به این رویداد بررسی می کنند. اگر هیچ تناقضی وجود نداشته باشد، گره ها اعلام می کنند: "بله، من هیچ داده دیگری برای این رویداد ندارم. مقدار "O" آخرین اطلاعاتی است که ما شایسته آن هستیم."

   در هر حالت دیگری، گره ها می توانند به "گره 1" پاسخ دهند: "گوش دهید! من اطلاعات جدیدتری در مورد این تراکنش دارم. نه "O"، بلکه چیزی بهتر."

   در مرحله رای گیری، گره ها به یک تصمیم می رسند: یا همه آنها یک مقدار را می پذیرند، یا یکی از آنها رای منفی می دهد، که نشان می دهد اطلاعات جدیدتری دارد.

3. اگر دور رای گیری موفقیت آمیز بود و همه موافق بودند، سیستم به مرحله جدیدی می رود - پذیرش ارزش. "گره 1" تمام پاسخ ها را از گره های دیگر جمع آوری می کند و گزارش می دهد: "همه بر روی مقدار "O" توافق کردند! اکنون رسماً اعلام می کنم که "O" معنای جدید ما است، برای همه یکسان است! آن را در کتاب کوچک خود بنویسید، فراموش نکنید. آن را در گزارش خود بنویسید!»

   

4. گره‌های باقی‌مانده تأییدیه (Accepted) را ارسال می‌کنند که مقدار «O» را یادداشت کرده‌اند؛ در این مدت هیچ چیز جدیدی وارد نشده است (نوعی تعهد دو فازی). پس از این رویداد مهم، ما در نظر می گیریم که تراکنش توزیع شده تکمیل شده است.
   

بنابراین، الگوریتم اجماع در یک مورد ساده از چهار مرحله تشکیل شده است: پیشنهاد، رأی (رای دادن)، قبول (پذیرش)، تأیید پذیرش (پذیرفته شده).

اگر در مرحله ای نتوانستیم به توافق برسیم، الگوریتم با در نظر گرفتن اطلاعات ارائه شده توسط گره هایی که از تأیید مقدار پیشنهادی خودداری کردند، دوباره شروع می شود.

الگوریتم اجماع در یک سیستم ناهمزمان

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

اکنون که می دانیم اصولاً الگوریتم اجماع چگونه کار می کند، یک سوال برای آن دسته از خوانندگان کنجکاوی که تا اینجا پیش رفته اند: چند گره در یک سیستم از گره های N با مدل پیام ناهمزمان می توانند از کار بیفتند تا سیستم همچنان بتواند به اجماع برسد؟

پاسخ صحیح و توجیه پشت اسپویلر است.پاسخ صحیح است: 0. اگر حتی یک گره در یک سیستم ناهمزمان از کار بیفتد، سیستم نمی تواند به اجماع برسد. این بیانیه در قضیه FLP که در محافل خاص معروف است (1985، فیشر، لینچ، پاترسون، پیوند به اصل در پایان مقاله) ثابت شده است: «عدم امکان دستیابی به یک اجماع توزیع شده در صورت شکست حداقل یک گره "

بچه ها، پس ما یک مشکل داریم، ما عادت کرده ایم که همه چیز ناهمزمان باشد. و اینجاست. چگونه به زندگی ادامه دهیم؟

ما فقط در مورد نظریه صحبت می کردیم، در مورد ریاضیات. ترجمه از زبان ریاضی به زبان ما - مهندسی - "اجماع نمی توان به دست آورد" به چه معناست؟ این بدان معنی است که "همیشه نمی توان به دست آورد"، یعنی. موردی وجود دارد که در آن اجماع حاصل نمی شود. این چه نوع موردی است؟

این دقیقاً نقض خاصیت زنده بودن است که در بالا توضیح داده شد. ما توافق مشترک نداریم و سیستم نمی تواند پیشرفت داشته باشد (نمی تواند در یک زمان محدود تکمیل شود) در موردی که از همه گره ها پاسخی نداشته باشیم. زیرا در یک سیستم ناهمزمان ما زمان پاسخگویی قابل پیش بینی نداریم و نمی توانیم بدانیم که آیا یک گره از کار افتاده است یا فقط زمان زیادی برای پاسخ دادن نیاز دارد.

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

در عمل، ما با مدل های ارتباطی تا حدی همزمان سروکار داریم. همزمانی جزئی به صورت زیر درک می شود: در حالت کلی، ما یک مدل ناهمزمان داریم، اما مفهوم خاصی از "زمان تثبیت جهانی" در یک نقطه زمانی خاص به طور رسمی معرفی شده است.

این لحظه از زمان ممکن است برای مدت زمان زیادی فرا نرسد، اما باید یک روز بیاید. ساعت مجازی زنگ دار زنگ می زند و از آن لحظه می توانیم دلتای زمانی که پیام ها برای آن می رسند را پیش بینی کنیم. از این لحظه به بعد، سیستم از ناهمزمان به همزمان تبدیل می شود. در عمل دقیقاً با چنین سیستم هایی سروکار داریم.

الگوریتم Paxos مسائل اجماع را حل می کند

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

اما ثابت شد که به دور از بی اهمیت بودن. اولین انتشار فقط در سال 1998 (33 صفحه) با توصیف الگوریتم منتشر شد. همانطور که مشخص شد، درک آن بسیار دشوار بود و در سال 2001 توضیحی درباره مقاله منتشر شد که 14 صفحه طول کشید. حجم انتشارات به این منظور ارائه شده است که نشان دهد در واقع مشکل اجماع اصلاً ساده نیست و پشت چنین الگوریتم‌هایی حجم عظیمی از کار توسط باهوش‌ترین افراد نهفته است.

جالب است که خود لزلی لمپورت در سخنرانی خود خاطرنشان کرد که در مقاله توضیحی دوم یک بیانیه وجود دارد، یک خط (وی مشخص نکرد کدام یک) که می تواند به طرق مختلف تفسیر شود. و به همین دلیل، تعداد زیادی از پیاده سازی های مدرن Paxos کاملاً درست کار نمی کنند.

تجزیه و تحلیل دقیق کار Paxos بیش از یک مقاله طول می کشد، بنابراین من سعی خواهم کرد به طور خلاصه ایده اصلی الگوریتم را بیان کنم. در پیوندهای انتهای مقاله من، مطالبی برای بررسی بیشتر در این موضوع پیدا خواهید کرد.

نقش ها در Paxos

الگوریتم Paxos مفهومی از نقش ها دارد. بیایید سه مورد اصلی را در نظر بگیریم (اصلاحاتی با نقش های اضافی وجود دارد):

1. پیشنهاد دهندگان (از اصطلاحات ممکن است استفاده شود: رهبران یا هماهنگ کنندگان). اینها افرادی هستند که ارزش های جدیدی از کاربر یاد می گیرند و نقش رهبر را بر عهده می گیرند. وظیفه آنها راه اندازی دور پیشنهادی برای ارزش جدید و هماهنگ کردن اقدامات بعدی گره ها است. علاوه بر این، Paxos امکان حضور چندین رهبر را در شرایط خاص فراهم می کند.
2. پذیرندگان (رای دهندگان). اینها گره هایی هستند که به پذیرش یا رد یک مقدار خاص رأی می دهند. نقش آنها بسیار مهم است، زیرا تصمیم به آنها بستگی دارد: پس از مرحله بعدی الگوریتم اجماع، سیستم به چه وضعیتی خواهد رفت (یا نخواهد رفت).
3. زبان آموزان. گره هایی که به سادگی می پذیرند و مقدار جدید پذیرفته شده را زمانی که وضعیت سیستم تغییر کرده است می نویسند. آنها تصمیم نمی گیرند، آنها فقط داده ها را دریافت می کنند و می توانند آن را به کاربر نهایی بدهند.

یک گره می تواند چندین نقش را در موقعیت های مختلف ترکیب کند.

مفهوم حد نصاب

ما فرض می کنیم که ما یک سیستم از N گره ها و از آنها حداکثر F گره ها ممکن است شکست بخورند. اگر گره های F شکست بخورند، حداقل باید داشته باشیم 2F+1 گره های پذیرنده

این لازم است تا ما همیشه اکثریت، حتی در بدترین شرایط، گره های "خوب" را داشته باشیم که به درستی کار می کنند. به این معنا که F+1 گره های "خوب" که توافق کردند، و مقدار نهایی پذیرفته خواهد شد. در غیر این صورت، ممکن است شرایطی پیش بیاید که گروه‌های محلی مختلف ما معانی متفاوتی پیدا کنند و نتوانند بین خودشان توافق کنند. بنابراین برای کسب رای به اکثریت مطلق نیاز داریم.

ایده کلی نحوه عملکرد الگوریتم اجماع Paxos

الگوریتم Paxos شامل دو فاز بزرگ است که به نوبه خود به دو مرحله تقسیم می شود:

1. فاز 1a: آماده سازی. در مرحله آماده سازی، رهبر (پیشنهاد کننده) به همه گره ها اطلاع می دهد: «ما در حال شروع مرحله رأی گیری جدید هستیم. دور جدید داریم تعداد این دور n است. حالا ما شروع به رای گیری می کنیم." در حال حاضر، به سادگی شروع یک چرخه جدید را گزارش می دهد، اما مقدار جدیدی را گزارش نمی کند. وظیفه این مرحله این است که یک دور جدید را آغاز کند و تعداد منحصر به فرد آن را به همه اطلاع دهد. عدد دور مهم است، باید مقداری بیشتر از تمام اعداد رای قبلی از همه رهبران قبلی باشد. زیرا به لطف عدد گرد است که سایر گره‌های سیستم متوجه می‌شوند که داده‌های رهبر چقدر جدید هستند. این احتمال وجود دارد که گره های دیگر از قبل نتایج رای گیری را از دورهای بعدی داشته باشند و به سادگی به رهبر می گویند که او از زمان عقب مانده است.
2. فاز 1b: قول. هنگامی که گره های پذیرنده شماره مرحله رای گیری جدید را دریافت کردند، دو نتیجه ممکن است:
   • تعداد n رای جدید بیشتر از هر رای قبلی است که پذیرنده در آن شرکت کرده است. سپس پذیرنده قولی به رهبر می فرستد که دیگر در رای با عدد کمتر از n شرکت نخواهد کرد. اگر پذیرنده قبلاً به چیزی رأی داده باشد (یعنی قبلاً در مرحله دوم مقداری ارزش را پذیرفته باشد) ارزش پذیرفته شده و تعداد رأیی که در آن شرکت داشته است را به قول خود ضمیمه می کند.
   • در غیر این صورت، اگر پذیرنده از قبل از رای با شماره بالاتر اطلاع داشته باشد، می تواند به سادگی مرحله آماده سازی را نادیده بگیرد و به لیدر پاسخ ندهد.
3. فاز 2a: پذیرش. رهبر باید منتظر پاسخ از حد نصاب (اکثر گره‌های سیستم) باشد و اگر تعداد پاسخ‌های لازم دریافت شود، دو گزینه برای توسعه رویدادها دارد:
   • برخی از پذیرندگان مقادیری را ارسال کردند که قبلاً به آن رای داده بودند. در این صورت رهبر مقدار را از رای با حداکثر تعداد انتخاب می کند. بیایید این مقدار را x بنامیم، و پیامی را به همه گره‌ها ارسال می‌کند: «Accept (n, x)»، که در آن اولین مقدار، عدد رای‌گیری از مرحله Propose خودش است، و مقدار دوم چیزی است که همه برای آن جمع‌آوری کرده‌اند. یعنی ارزشی که ما در واقع به آن رای می دهیم.
   • اگر هیچ یک از پذیرندگان ارزشی ارسال نکردند، اما آنها صرفاً وعده رای دادن در این دور را دادند، رهبر می تواند از آنها دعوت کند که به ارزش آنها رای دهند، ارزشی که در وهله اول برای آن رهبر شد. بیایید آن را y بنامیم. این پیام را به همه گره ها ارسال می کند: "Accept (n, y)"، مشابه نتیجه قبلی.
4. فاز 2b: پذیرفته شده است. علاوه بر این، گره‌های پذیرنده، با دریافت پیام «Accept(...)» از رهبر، با آن موافقت می‌کنند (برای همه گره‌ها تأیید می‌کنند که با مقدار جدید موافق هستند) تنها در صورتی که برخی (سایر موارد) را قول نداده باشند). رهبر برای شرکت در رای گیری با شماره دور n' > n، در غیر این صورت درخواست تایید را نادیده می گیرند.

   اگر اکثر گره ها به رهبر پاسخ دهند و همه آنها مقدار جدید را تایید کنند، آنگاه مقدار جدید پذیرفته شده در نظر گرفته می شود. هورا! اگر اکثریت به دست نیامد یا گره هایی وجود داشته باشند که از پذیرش مقدار جدید خودداری کنند، همه چیز از اول شروع می شود.

الگوریتم Paxos اینگونه عمل می کند. هر یک از این مراحل دارای ظرافت های بسیاری هستند، ما عملاً انواع مختلف خرابی ها، مشکلات چندین رهبر و بسیاری موارد دیگر را در نظر نگرفتیم، اما هدف این مقاله تنها معرفی خواننده با دنیای محاسبات توزیع شده در سطح بالا است.

همچنین شایان ذکر است که Paxos تنها در نوع خود نیست، الگوریتم های دیگری نیز وجود دارد، به عنوان مثال، قایق، اما این موضوع برای مقاله دیگری است.

پیوند به مواد برای مطالعه بیشتر

سطح مقدماتی:

• اجماع توزیع شده چگونه کار می کند؟، پریتی کاسیردی، مقاله وبلاگ در Medium
• Paxos ساده ساخته شده است. واقعا - جدا، آدی کانچرلا، مقاله وبلاگ در مدیوم
• افکار غیر متمرکزایتتای آبراهام، وبلاگ
• همزمانی، ناهمزمانی و همزمانی جزئی، Ittai Abraham، مقاله وبلاگ

سطح لزلی لمپورت:

• عدم امکان اجماع توزیع شده با یک فرآیند معیوب (عدم امکان FLP)، فیشر، لینچ و پاترسون، مقاله تحقیقاتی، 1985
• پارلمان پاره وقت، لسلی لامپورت، مقاله تحقیقاتی، 1998
• Paxos ساده ساخته شده است، لسلی لامپورت، مقاله تحقیقاتی، 2001

منبع: www.habr.com