پروتکل Paxos

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

مسئله اجماع در سیستم‌ های توزیع‌ شده

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

چالش‌ها در اجماع

1. خرابی گره‌ها: گره‌ها ممکن است به دلایل مختلفی مانند مشکلات سخت‌افزاری یا خطاهای نرم‌افزاری از کار بیفتند.
2. رفتار غیرقابل پیش‌بینی (Byzantine Behavior): برخی گره‌ها ممکن است اطلاعات نادرست یا متناقض ارسال کنند.
3. ناهمگامی (Asynchrony): در سیستم‌ های توزیع‌شده، پیام‌ها ممکن است با تأخیرهای غیرقابل پیش‌بینی ارسال یا دریافت شوند.
4. شبکه‌های غیرقابل اعتماد: پیام‌ها ممکن است در مسیر ارسال گم شوند یا دوباره ارسال شوند.

مفاهیم پایه در پروتکل اجماع Paxos

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

1. پیشنهاددهنده (Proposer): این گره وظیفه دارد مقداری را برای توافق پیشنهاد دهد. پیشنهاددهنده درخواست خود را به اکثریت گره‌ها (که به آن‌ها پذیرنده گفته می‌شود) ارسال می‌کند.
2. پذیرنده (Acceptor): پذیرنده‌ها مسئول بررسی و تأیید پیشنهادها هستند. اگر اکثریت پذیرنده‌ها یک پیشنهاد خاص را بپذیرند، آن پیشنهاد نهایی می‌شود. پذیرنده‌ها همچنین ملزم هستند تاریخچه پیشنهادهای قبلی را حفظ کنند تا سازگاری تضمین شود.
3. یادآور (Learner): گره‌هایی هستند که نتیجه نهایی اجماع را مشاهده و برای سایر سیستم‌ها اعمال می‌کنند. یادآورها در فرآیند تصمیم‌گیری نقشی مستقیم ندارند.
4. شماره‌گذاری پیشنهادها: هر پیشنهاد دارای یک شماره یکتا است که به ترتیب افزایش می‌یابد. این شماره‌ها برای شناسایی و اولویت‌بندی پیشنهادها ضروری هستند.

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

Paxos یکی از مهم‌ترین پروتکل‌های اجماع (Consensus) است که توسط لِزلی لمپورت (Leslie Lamport) در سال 1989 معرفی شد.

مراحل پروتکل اجماع Paxos

پروتکل Paxos برای دستیابی به اجماع از سه مرحله کلیدی تشکیل شده است که هر کدام نقش حیاتی در تضمین سازگاری و ایمنی دارند:

1. مرحله آماده‌سازی (Prepare Phase)

• پیشنهاددهنده یک شماره یکتا و افزایشی به عنوان شماره پیشنهاد ($nnn$) انتخاب می‌کند.
• درخواست آماده‌سازی ($Prepare(n)\text{Prepare}(n)Prepare(n)$) را به همه پذیرنده‌ها ارسال می‌کند.
• هر پذیرنده اگر قبلاً تعهدی برای شماره پیشنهادی بزرگ‌تر نداشته باشد، این درخواست را می‌پذیرد و به پیشنهاددهنده پاسخ می‌دهد. پاسخ شامل بزرگ‌ترین شماره پیشنهادی ($nlastn_{\text{last}}nlast​$) و مقدار مرتبطی است که پذیرنده قبلاً پذیرفته است.

2. مرحله پیشنهاد (Propose Phase)

• پیشنهاددهنده، پس از دریافت پاسخ از اکثریت پذیرنده‌ها، مقداری را پیشنهاد می‌دهد.
• اگر پذیرنده‌ها مقدار دیگری را با شماره پیشنهادی بزرگ‌تر پذیرفته باشند، پیشنهاددهنده آن مقدار را مجدداً پیشنهاد می‌دهد. در غیر این صورت، مقدار جدیدی انتخاب می‌کند.
• پیشنهاددهنده پیام ($Propose(n,v)\text{Propose}(n, v)Propose(n,v)$) را ارسال می‌کند که در آن $vvv$ مقدار پیشنهادی است.
• پذیرنده، اگر تعهد جدیدی برای شماره بزرگ‌تر نداشته باشد، این مقدار را می‌پذیرد و به همه گره‌ها اطلاع می‌دهد.

3. مرحله یادگیری (Learn Phase)

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

این فرآیند با تکیه بر اکثریت گره‌ها و شماره‌گذاری ترتیبی پیشنهادها، تضمین می‌کند که پروتکل Paxos حتی در شرایط خرابی، تصمیم‌های سازگار و ایمن اتخاذ کند.

مثال عملی از پروتکل Paxos در یک سیستم بانکی
فرض کنید یک بانک آنلاین دارای چندین سرور است که باید با هم هماهنگ باشند تا اطلاعات حساب مشتریان همواره یکسان و به‌روز باشد. بانک نمی‌خواهد حتی در صورت بروز خرابی در یک سرور، تناقضی در موجودی حساب‌ها ایجاد شود.
اکنون، یک مشتری درخواست برداشت ۱۰۰ دلار از حساب خود را ارسال می‌کند. این درخواست باید در تمام سرورها به‌طور هماهنگ تأیید و ثبت شود. برای این کار، Paxos اجرا می‌شود.
مرحله آماده‌سازی (Prepare Phase)
یکی از سرورها (مثلاً سرور A) به‌عنوان پیشنهاددهنده (Proposer) عمل می‌کند.
🔹 سرور A یک شماره یکتا برای پیشنهاد خود انتخاب می‌کند، فرضاً شماره ۱۰.
🔹 سپس به همه سرورهای دیگر (پذیرنده‌ها) پیام می‌فرستد:
“من درخواست دارم که پیشنهاد شماره ۱۰ را در نظر بگیرید. آیا قبلاً پیشنهادی پذیرفته‌اید؟ اگر بله، مقدار آن چه بوده است؟”
🔹 سایر سرورها پاسخ می‌دهند:
سرور B: “قبلاً هیچ تراکنشی را تأیید نکرده‌ام.”
سرور C: “من هم پیشنهادی ثبت نکرده‌ام.”
سرور D: “من پیشنهادی با شماره ۷ را تأیید کرده بودم که موجودی قبلی ۵۰۰ دلار بود.”
📌 نتیجه: سرور A متوجه می‌شود که فقط سرور D پیشنهادی قدیمی دارد، اما بقیه هیچ مقدار قبلی ثبت نکرده‌اند.
مرحله پیشنهاد و یادگیری (Propose & Learn Phase)
🔹 اکنون سرور A باید تصمیم بگیرد چه مقدار را پیشنهاد دهد:
اگر هیچ سروری مقدار قبلی نداشته باشد، مقدار جدید (برداشت ۱۰۰ دلار) را پیشنهاد می‌دهد.
اگر یک مقدار قبلاً پذیرفته شده باشد، همان مقدار را دوباره پیشنهاد می‌دهد.
🔹 سرور A مقدار برداشت ۱۰۰ دلار از حسابی که ۵۰۰ دلار داشت را پیشنهاد می‌دهد و به همه سرورها اعلام می‌کند:
“با شماره پیشنهاد ۱۰، درخواست می‌کنم که موجودی جدید را ۴۰۰ دلار ثبت کنیم.”
🔹 سایر سرورها بررسی می‌کنند که آیا قبلاً پیشنهاد بزرگ‌تری دریافت کرده‌اند یا نه. چون شماره ۱۰ بزرگ‌ترین شماره پیشنهادی است، همه سرورها این مقدار را قبول می‌کنند.
📌 نتیجه:
✅ تمام سرورها توافق می‌کنند که پس از برداشت ۱۰۰ دلار، موجودی جدید ۴۰۰ دلار است.
✅ حالا این مقدار به‌عنوان مقدار نهایی ذخیره می‌شود و دیگر تغییر نخواهد کرد.
✅ اگر یک مشتری دیگر در همان لحظه سعی کند ۱۰۰ دلار دیگر برداشت کند، سرورها به او پاسخ خواهند داد که موجودی حساب ۴۰۰ دلار است، نه ۵۰۰ دلار!

تضمین‌ امنیت و کارایی Paxos

پروتکل Paxos با طراحی دقیق خود تضمین‌هایی را فراهم می‌کند که برای دستیابی به اجماع در سیستم‌های توزیع‌شده حیاتی هستند:

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

این تضمین‌ها پروتکل Paxos را به یکی از قابل‌اعتمادترین روش‌های اجماع در سیستم‌های توزیع‌شده تبدیل کرده‌اند و آن را در مواجهه با خرابی‌ها و ناپایداری‌ها مقاوم می‌کنند.

ویژگی‌های شماره پیشنهاد (Proposal ID) در پروتکل Paxos

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

چرا Proposal ID اهمیت دارد؟

1. جلوگیری از ناسازگاری: اگر دو پیشنهاد به‌طور هم‌زمان ارسال شوند، پروتکل تضمین می‌کند که فقط یکی از آن‌ها پذیرفته شود.
2. ردگیری نسخه‌های جدیدتر: اگر یک مقدار قبلاً پذیرفته شده باشد، پیشنهاددهنده باید مقدار جدید را بر اساس آخرین مقدار پذیرفته‌شده تنظیم کند.
3. هماهنگی بین گره‌ها: با استفاده از Proposal ID، تمام گره‌های سیستم می‌توانند بفهمند که کدام پیشنهاد جدیدتر و معتبرتر است.

مثال ساده برای درک Proposal ID:

فرض کنید در یک شرکت چندین مدیر در حال پیشنهاد حقوق جدید برای یک کارمند هستند:

• مدیر A پیشنهاد افزایش به ۵۰۰۰ دلار را با Proposal ID = ۱۰ ارسال می‌کند.
• مدیر B پیشنهاد افزایش به ۵۲۰۰ دلار را با Proposal ID = ۱۵ ارسال می‌کند.

از آنجا که پیشنهاد B شماره بزرگ‌تری دارد (۱۵ > ۱۰)، سیستم فقط پیشنهاد B را قبول می‌کند، حتی اگر پیشنهاد A زودتر ارسال شده باشد.

📌 نتیجه: Proposal ID فقط برای مدیریت اولویت پیشنهادها است و مقدار نهایی را تعیین نمی‌کند، بلکه تضمین می‌کند که همه گره‌ها روی یک مقدار یکسان توافق کنند.

محدودیت‌های Paxos

هرچند Paxos بسیار قدرتمند است، اما محدودیت‌هایی نیز دارد:

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

توسعه و بهبود پروتکل Paxos

پروتکل Paxos به دلیل پیچیدگی‌های عملیاتی و هزینه‌های ارتباطی بهبودهای متعددی را تجربه کرده است:

1. Multi-Paxos: نسخه‌ای بهینه‌شده برای سناریوهایی که اجماع به‌صورت مکرر انجام می‌شود. این روش مراحل اولیه (Prepare) را کاهش داده و تنها بر فاز پیشنهاد (Propose) تمرکز می‌کند.
2. Fast Paxos: با کاهش تأخیر در برخی حالات، امکان اجماع در دو مرحله را فراهم می‌آورد، اما نیازمند شرایط خاصی مانند تأخیر پایین شبکه است.
3. Cheap Paxos: تعداد گره‌های موردنیاز را برای عملیات اجماع در صورت خرابی‌ها کاهش می‌دهد و در محیط‌های با منابع محدود کاربرد دارد.
4. EPaxos: نسخه‌ای با تأکید بر عملکرد و موازی‌سازی که تأخیر را با اجازه سفارش نسبی درخواست‌ها کاهش می‌دهد.

کاربردهای عملی Paxos

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

1. سیستم‌های مدیریت پایگاه داده‌های توزیع‌شده

پروتکل Paxos به‌طور گسترده در پایگاه داده‌های توزیع‌شده مانند Google Spanner و CockroachDB استفاده می‌شود. در این سیستم‌ها، اجماع برای هماهنگی تغییرات در داده‌ها و اطمینان از پایداری نسخه‌های مختلف پایگاه داده ضروری است. Paxos از تضاد در داده‌ها جلوگیری کرده و سازگاری قوی را تضمین می‌کند.

2. سامانه‌های فایل توزیع‌شده

در سامانه‌هایی مانند Ceph و Google File System (GFS)، Paxos برای مدیریت متاداده‌های فایل‌ها و تصمیم‌گیری درباره قفل‌گذاری و تغییرات فایل‌ها استفاده می‌شود. این پروتکل اطمینان می‌دهد که گره‌ها وضعیت فایل‌ها را به‌درستی هماهنگ نگه می‌دارند.

3. سیستم‌های پیام‌رسان و صف پیام

پروتکل‌هایی مانند Kafka یا RabbitMQ از مفاهیم اجماع برای مدیریت صف پیام‌ها و هماهنگی بین گره‌ها بهره می‌برند. Paxos می‌تواند تضمین کند که پیام‌ها به ترتیب صحیح دریافت و پردازش شوند.

4. سیستم‌های مقیاس‌پذیر ابری و اورکستراسیون

در سیستم‌های مقیاس‌پذیری مانند Kubernetes و Zookeeper، Paxos برای هماهنگی سرویس‌ها، مدیریت منابع و اجماع در عملیات خوشه‌ای (Cluster Operations) استفاده می‌شود.

5. شبکه‌های بلاکچین و رمزنگاری

گرچه بلاکچین‌ها معمولاً از پروتکل‌های اجماع دیگر مانند Proof of Work استفاده می‌کنند، اما مفاهیم مشابه Paxos برای اجماع سریع و ایمن در برخی زنجیره‌های خصوصی یا کنسرسیومی مورد استفاده قرار می‌گیرد.

این کاربردهای گسترده نشان‌دهنده اهمیت Paxos در ایجاد سیستم‌های مقاوم، هماهنگ و توزیع‌شده هستند.

نتیجه‌گیری

پروتکل Paxos یکی از مهم‌ترین دستاوردها در زمینه اجماع در سیستم‌های توزیع‌شده است که با ارائه تضمین‌های ایمنی، سازگاری و پیشرفت، به‌عنوان استانداردی در بسیاری از برنامه‌های عملیاتی شناخته می‌شود. این پروتکل، حتی در حضور خرابی گره‌ها یا ارتباطات ناپایدار، امکان دستیابی به اجماع قابل‌اعتماد را فراهم می‌کند. علی‌رغم پیچیدگی‌های مفهومی و هزینه‌های ارتباطی اولیه، بهبودهای متعددی مانند Multi-Paxos و EPaxos این پروتکل را بهینه‌تر و کاربردی‌تر کرده‌اند. از پایگاه داده‌های توزیع‌شده گرفته تا سیستم‌های مدیریت فایل و اورکستراسیون ابری، Paxos در معماری‌های مدرن نقش حیاتی ایفا می‌کند.

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