فصل ۹ — سازگاری و اجماع

بهتر است زنده و اشتباه باشی یا درست و مرده؟ — Jay Kreps، A Few Notes on Kafka and Jepsen (۲۰۱۳)

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

در این فصل، نمونه‌هایی از الگوریتم‌ها و پروتکل‌ها برای ساخت سیستم‌های توزیع‌شده تحمل‌پذیر خطا را بررسی می‌کنیم. فرض می‌کنیم همه مشکلات فصل ۸ ممکن است رخ دهند: بسته‌ها در شبکه ممکن است گم، مرتب‌سازی مجدد، تکرار یا با تأخیر دلخواه شوند؛ ساعت‌ها در بهترین حالت تقریبی‌اند؛ و گره‌ها ممکن است در هر لحظه مکث کنند (مثلاً به‌خاطر garbage collection) یا crash کنند.

بهترین راه ساخت سیستم‌های تحمل‌پذیر خطا، یافتن چند انتزاع عمومی با تضمین‌های مفید، پیاده‌سازی یک‌بار آن‌ها و سپس تکیه برنامه‌ها بر آن تضمین‌هاست. همان رویکردی که در فصل ۷ با تراکنش‌ها داشتیم: با استفاده از تراکنش، برنامه می‌تواند وانمود کند crashی رخ نداده (atomicity)، کس دیگری همزمان به پایگاه داده دسترسی ندارد (isolation)، و دستگاه‌های ذخیره‌سازی کاملاً قابل اعتمادند (durability). حتی اگر crash، race condition و خرابی دیسک رخ دهد، انتزاع تراکنش این مشکلات را پنهان می‌کند تا برنامه نگران آن‌ها نباشد.

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

وقتی پیاده‌سازی اجماع دارید، برنامه‌ها می‌توانند آن را برای اهداف مختلف به کار ببرند. مثلاً فرض کنید پایگاه داده‌ای با رپلیکاسیون single-leader دارید. اگر leader بمیرد و باید به گره دیگری failover کنید، گره‌های باقی‌مانده پایگاه داده می‌توانند از اجماع برای انتخاب leader جدید استفاده کنند. همان‌طور که در «مدیریت خرابی گره‌ها» در صفحه ۱۵۶ بحث شد، مهم است فقط یک leader وجود داشته باشد و همه گره‌ها بدانند leader کیست. اگر دو گره هر دو فکر کنند leader هستند، وضعیت split brain پیش می‌آید و اغلب به از دست رفتن داده منجر می‌شود. پیاده‌سازی‌های درست اجماع به جلوگیری از چنین مشکلاتی کمک می‌کنند.

بعداً در این فصل، در «تراکنش‌های توزیع‌شده و اجماع» در صفحه ۳۵۲، به الگوریتم‌های حل اجماع و مسائل مرتبط می‌پردازیم. اما ابتدا باید دامنه تضمین‌ها و انتزاعاتی را که در سیستم توزیع‌شده قابل ارائه‌اند بررسی کنیم.

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

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

تضمین‌های سازگاری

در «مشکلات تأخیر رپلیکاسیون» در صفحه ۱۶۱ به برخی مسائل زمان‌بندی در پایگاه داده رپلیک‌شده نگاه کردیم. اگر در یک لحظه به دو گره پایگاه داده نگاه کنید، احتمالاً داده متفاوتی می‌بینید، چون درخواست‌های نوشتن در زمان‌های مختلف به گره‌های مختلف می‌رسند. این ناسازگاری‌ها صرف‌نظر از روش رپلیکاسیون (single-leader، multi-leader یا leaderless) رخ می‌دهند.

بیشتر پایگاه‌های داده رپلیک‌شده حداقل سازگاری نهایی (eventual consistency) را فراهم می‌کنند: یعنی اگر نوشتن به پایگاه داده را متوقف کنید و مدت نامشخصی صبر کنید، در نهایت همه درخواست‌های خواندن همان مقدار را برمی‌گردانند [۱]. به عبارت دیگر، ناسازگاری موقتی است و در نهایت برطرف می‌شود (با فرض اینکه خطاهای شبکه هم در نهایت تعمیر شوند). شاید نام بهتری برای eventual consistency همگرایی (convergence) باشد، چون انتظار داریم همه رپلیکاها در نهایت به یک مقدار همگرا شوند [۲].

با این حال، این تضمین بسیار ضعیفی است — چیزی درباره زمان همگرایی نمی‌گوید. تا زمان همگرایی، خواندن‌ها ممکن است هر چیزی یا هیچ چیزی برگردانند [۱]. مثلاً اگر مقداری بنویسید و بلافاصله بخوانید، تضمینی نیست همان مقدار را ببینید، چون خواندن ممکن است به رپلیکای دیگری هدایت شود (به «خواندن نوشته‌های خودتان» در صفحه ۱۶۲ مراجعه کنید).

سازگاری نهایی برای توسعه‌دهندگان برنامه سخت است چون با رفتار متغیرها در برنامه تک‌نخی معمولی تفاوت دارد. اگر به متغیری مقدار بدهید و کمی بعد بخوانید، انتظار مقدار قدیمی یا شکست خواندن را ندارید. پایگاه داده ظاهراً شبیه متغیری است که می‌توانید بخوانید و بنویسید، اما در واقع معناشناسی پیچیده‌تری دارد [۳].

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

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

بین مدل‌های سازگاری توزیع‌شده و سلسله‌مراتب سطوح ایزولاسیون تراکنش که قبلاً بحث کردیم [۴، ۵] (به «سطوح ایزولاسیون ضعیف» در صفحه ۲۳۳) شباهتی هست. اگرچه همپوشانی دارند، عمدتاً مستقل‌اند: ایزولاسیون تراکنش عمدتاً درباره جلوگیری از race condition به‌خاطر تراکنش‌های همزمان است، در حالی که سازگاری توزیع‌شده عمدتاً درباره هماهنگ‌سازی وضعیت رپلیکاها در برابر تأخیر و خطا است.

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

• با یکی از قوی‌ترین مدل‌های سازگاری رایج، خطی‌پذیری (linearizability)، شروع می‌کنیم و مزایا و معایبش را بررسی می‌کنیم.
• سپس مسئله مرتب‌سازی رویدادها در سیستم توزیع‌شده («تضمین‌های مرتب‌سازی» در صفحه ۳۳۹)، به‌ویژه علیت و ترتیب کل، را بررسی می‌کنیم.
• در بخش سوم («تراکنش‌های توزیع‌شده و اجماع» در صفحه ۳۵۲) نحوه commit اتمی تراکنش توزیع‌شده را بررسی می‌کنیم که در نهایت به راه‌حل‌های مسئله اجماع می‌رسد.

خطی‌پذیری

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

ایده پشت خطی‌پذیری [۶] (که atomic consistency [۷]، strong consistency، immediate consistency یا external consistency [۸] هم نامیده می‌شود) همین است. تعریف دقیق خطی‌پذیری ظریف است و در ادامه این بخش بررسی می‌کنیم. اما ایده اصلی این است که سیستم طوری به نظر برسد گویی فقط یک نسخه از داده وجود دارد و همه عملیات روی آن اتمی‌اند. با این تضمین، حتی اگر در واقعیت چند رپلیکا باشد، برنامه نگران آن‌ها نیست.

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

شکل ۹-۱. این سیستم خطی‌پذیر نیست و طرفداران فوتبال را گیج می‌کند.

شکل ۹-۱ مثالی از وب‌سایت ورزشی غیرخطی‌پذیر [۹] را نشان می‌دهد. Alice و Bob در یک اتاق نشسته‌اند و هر دو گوشی‌شان را برای دیدن نتیجه فینال جام جهانی ۲۰۱۴ FIFA چک می‌کنند. بلافاصله پس از اعلام نتیجه نهایی، Alice صفحه را refresh می‌کند، برنده را می‌بیند و با هیجان به Bob می‌گوید. Bob باور نمی‌کند و reload می‌زند، اما درخواستش به رپلیکای پایگاه داده که عقب مانده می‌رود و گوشی‌اش نشان می‌دهد بازی هنوز در جریان است.

اگر Alice و Bob همزمان reload می‌زدند، گرفتن دو نتیجه متفاوت کمتر عجیب بود، چون نمی‌دانستند درخواست‌هایشان دقیقاً چه زمانی پردازش شده. اما Bob می‌داند دکمه reload (شروع query) را بعد از شنیدن فریاد Alice زده، پس انتظار دارد نتیجه query حداقل به‌اندازه Alice تازه باشد. اینکه query نتیجه کهنه برگرداند نقض خطی‌پذیری است.

چه چیزی سیستم را خطی‌پذیر می‌کند؟

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

شکل ۹-۲ سه کلاینت را نشان می‌دهد که همزمان همان کلید x را در پایگاه داده خطی‌پذیر می‌خوانند و می‌نویسند. در ادبیات سیستم‌های توزیع‌شده، x یک رجیستر (register) نامیده می‌شود — در عمل می‌تواند یک کلید در key-value store، یک سطر در پایگاه داده رابطه‌ای یا یک سند در document database باشد.

شکل ۹-۲. اگر درخواست خواندن همزمان با درخواست نوشتن باشد، ممکن است مقدار قدیمی یا جدید برگردد.

برای سادگی، شکل ۹-۲ فقط درخواست‌ها را از دید کلاینت نشان می‌دهد، نه درون پایگاه داده. هر میله یک درخواست کلاینت است: شروع میله زمان ارسال درخواست و پایان آن زمان دریافت پاسخ توسط کلاینت است. به‌خاطر تأخیر متغیر شبکه، کلاینت دقیقاً نمی‌داند پایگاه داده چه زمانی درخواست را پردازش کرده — فقط می‌داند بین ارسال درخواست و دریافت پاسخ باید رخ داده باشد.i

در این مثال، رجیستر دو نوع عملیات دارد:

• read(x) ⇒ v یعنی کلاینت خواست مقدار رجیستر x را بخواند و پایگاه داده مقدار v را برگرداند.
• write(x, v) ⇒ r یعنی کلاینت خواست رجیستر x را روی v تنظیم کند و پایگاه داده پاسخ r (که می‌تواند ok یا error باشد) را برگرداند.

در شکل ۹-۲، مقدار اولیه x برابر ۰ است و کلاینت C درخواست نوشتن برای تنظیم آن روی ۱ می‌دهد. در این حین، کلاینت‌های A و B مرتباً پایگاه داده را poll می‌کنند تا آخرین مقدار را بخوانند. پاسخ‌های ممکن برای A و B چیست؟

• اولین خواندن A قبل از شروع نوشتن تمام می‌شود، پس حتماً مقدار قدیمی ۰ را برمی‌گرداند.
• آخرین خواندن A بعد از اتمام نوشتن شروع می‌شود، پس اگر پایگاه داده خطی‌پذیر باشد حتماً مقدار جدید ۱ را برمی‌گرداند: می‌دانیم نوشتن بین شروع و پایان عملیات نوشتن پردازش شده و خواندن بین شروع و پایان عملیات خواندن. اگر خواندن بعد از پایان نوشتن شروع شده، خواندن بعد از نوشتن پردازش شده و باید مقدار جدید را ببیند.
• هر خواندی که در زمان با نوشتن همپوشانی دارد ممکن است ۰ یا ۱ برگرداند، چون نمی‌دانیم نوشتن در زمان پردازش خواندن اثر گذاشته یا نه. این عملیات‌ها با نوشتن همزمان (concurrent)‌اند.

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

i. جزئیات ظریف این نمودار فرض وجود ساعت جهانی است که محور افقی نشان می‌دهد. اگرچه سیستم‌های واقعی معمولاً ساعت دقیق ندارند (به «ساعت‌های غیرقابل اعتماد» در صفحه ۲۸۷)، این فرض برای تحلیل الگوریتم توزیع‌شده قابل قبول است، به شرطی که الگوریتم به آن دسترسی نداشته باشد [۴۷]. در عوض، الگوریتم فقط تقریب مخدوش زمان واقعی را می‌بیند که از نوسان‌ساز کوارتز و NTP می‌آید.

ii. رجیستری که اگر خواندن با نوشتن همزمان باشد ممکن است مقدار قدیمی یا جدید برگرداند رجیستر معمولی (regular register) نامیده می‌شود [۷، ۲۵].

برای خطی‌پذیر کردن سیستم، باید قید دیگری اضافه کنیم، همان‌طور که در شکل ۹-۳ نشان داده شده.

شکل ۹-۳. پس از اینکه یک خواندن مقدار جدید را برگرداند، همه خوانده‌های بعدی (روی همان یا کلاینت‌های دیگر) نیز باید مقدار جدید را برگردانند.

در سیستم خطی‌پذیر تصور می‌کنیم نقطه‌ای در زمان (بین شروع و پایان عملیات نوشتن) وجود دارد که مقدار x از ۰ به ۱ به‌صورت اتمی تغییر می‌کند. پس اگر خواندن یک کلاینت مقدار جدید ۱ را برگرداند، همه خوانده‌های بعدی نیز باید مقدار جدید را برگردانند، حتی اگر عملیات نوشتن هنوز تمام نشده باشد.

این وابستگی زمانی با فلش در شکل ۹-۳ نشان داده شده. کلاینت A اولین کسی است که مقدار جدید ۱ را می‌خواند. بلافاصله پس از برگشت خواندن A، B خواندن جدیدی شروع می‌کند. چون خواندن B دقیقاً بعد از خواندن A است، باید ۱ برگرداند، حتی اگر نوشتن C هنوز در جریان باشد. (همان وضعیت Alice و Bob در شکل ۹-۱: بعد از خواندن مقدار جدید توسط Alice، Bob هم انتظار مقدار جدید را دارد.)

می‌توانیم این نمودار زمانی را دقیق‌تر کنیم تا هر عملیات در نقطه‌ای از زمان اتمی اثر کند. مثال پیچیده‌تری در شکل ۹-۴ [۱۰] آمده است.

در شکل ۹-۴ علاوه بر خواندن و نوشتن، نوع سوم عملیات داریم:

• cas(x, vold, vnew) ⇒ r یعنی کلاینت عملیات اتمی compare-and-set درخواست کرد (به «Compare-and-set» در صفحه ۲۴۵). اگر مقدار فعلی رجیستر x برابر vold باشد، باید اتمی روی vnew تنظیم شود. اگر x ≠ vold باشد، عملیات رجیستر را بدون تغییر می‌گذارد و خطا برمی‌گرداند. r پاسخ پایگاه داده است (ok یا error).

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

شکل ۹-۴. تجسم نقاط زمانی که خواندن و نوشتن به نظر اثر کرده‌اند. آخرین خواندن B خطی‌پذیر نیست.

چند جزئیات جالب در شکل ۹-۴:

• اول B درخواست خواندن x فرستاد، بعد D درخواست تنظیم x روی ۰، بعد A درخواست تنظیم x روی ۱. با این حال، مقدار برگشتی به B برای خواندنش ۱ است (مقدار نوشته‌شده توسط A). این قابل قبول است: یعنی پایگاه داده اول نوشتن D، بعد A و در نهایت خواندن B را پردازش کرده. اگرچه این ترتیب ارسال درخواست‌ها نیست، قابل قبول است چون سه درخواست همزمان‌اند. شاید درخواست خواندن B کمی در شبکه تأخیر یافته و فقط بعد از دو نوشتن به پایگاه داده رسیده.
• خواندن B مقدار ۱ را برگرداند قبل از اینکه A پاسخ موفقیت نوشتن ۱ را از پایگاه داده بگیرد. این هم قابل قبول است: یعنی مقدار قبل از نوشتن خوانده نشده، فقط پاسخ ok به A کمی در شبکه تأخیر یافته.
• این مدل هیچ ایزولاسیون تراکنشی فرض نمی‌کند: کلاینت دیگر ممکن است هر لحظه مقدار را تغییر دهد. مثلاً C اول ۱ و بعد ۲ می‌خواند، چون B مقدار را بین دو خواندن تغییر داده. عملیات compare-and-set (cas) اتمی می‌تواند بررسی کند مقدار همزمان توسط کلاینت دیگر تغییر نکرده: درخواست‌های cas B و C موفق می‌شوند، اما cas D شکست می‌خورد (وقتی پایگاه داده آن را پردازش می‌کند، مقدار x دیگر ۰ نیست).
• آخرین خواندن B (در میله سایه‌دار) خطی‌پذیر نیست. عملیات با نوشتن cas C همزمان است که x را از ۲ به ۴ به‌روز می‌کند. در غیاب درخواست‌های دیگر، خواندن B می‌توانست ۲ برگرداند. اما A قبلاً مقدار جدید ۴ را خوانده قبل از شروع خواندن B، پس B مجاز نیست مقدار قدیمی‌تری از A بخواند. باز هم همان وضعیت Alice و Bob در شکل ۹-۱.

این شهود پشت خطی‌پذیری است؛ تعریف رسمی [۶] دقیق‌تر توصیف می‌کند. ممکن است (اگرچه از نظر محاسباتی گران است) با ثبت زمان‌بندی همه درخواست‌ها و پاسخ‌ها بررسی کرد آیا رفتار سیستم خطی‌پذیر است و آیا می‌توان آن‌ها را در ترتیب متوالی معتبری چید [۱۱].

خطی‌پذیری در برابر سریال‌پذیری

خطی‌پذیری به‌راحتی با سریال‌پذیری (serializability؛ به «سریال‌پذیری» در صفحه ۲۵۱) اشتباه می‌شود، چون هر دو ظاهراً یعنی «قابل چیدن در ترتیب متوالی». اما دو تضمین کاملاً متفاوت‌اند و تمایز مهم است:

سریال‌پذیری سریال‌پذیری ویژگی ایزولاسیون تراکنش است که هر تراکنش ممکن است چند شیء (سطر، سند، رکورد) بخواند و بنویسد — به «عملیات تک‌شیء و چندشیء» در صفحه ۲۲۸. تضمین می‌کند تراکنش‌ها طوری رفتار کنند گویی در ترتیب سریالی اجرا شده‌اند (هر تراکنش تا پایان قبل از شروع بعدی). آن ترتیب سریالی می‌تواند با ترتیب واقعی اجرا متفاوت باشد [۱۲].

خطی‌پذیری خطی‌پذیری تضمین تازگی روی خواندن و نوشتن یک رجیستر (یک شیء منفرد) است. عملیات را در تراکنش گروه نمی‌کند، پس از مشکلاتی مثل write skew (به «Write Skew و Phantoms» در صفحه ۲۴۶) جلوگیری نمی‌کند، مگر اقدامات اضافی مثل materialize کردن تعارض‌ها (به «Materializing conflicts» در صفحه ۲۵۱).

پایگاه داده ممکن است هم سریال‌پذیری و هم خطی‌پذیری را بدهد؛ این ترکیب سریال‌پذیری سخت (strict serializability) یا strong one-copy serializability (strong-1SR) [۴، ۱۳] نامیده می‌شود. پیاده‌سازی‌های سریال‌پذیری مبتنی بر two-phase locking (به «Two-Phase Locking (2PL)» در صفحه ۲۵۷) یا اجرای سریال واقعی (به «Actual Serial Execution» در صفحه ۲۵۲) معمولاً خطی‌پذیرند. اما Serializable Snapshot Isolation (SSI؛ به «Serializable Snapshot Isolation (SSI)» در صفحه ۲۶۱) خطی‌پذیر نیست: عمداً از snapshot سازگار می‌خواند تا contention قفل بین خواننده و نویسنده کم شود. هدف snapshot سازگار این است که نوشتن‌های جدیدتر از snapshot را شامل نشود، پس خواندن از snapshot خطی‌پذیر نیست.

تکیه بر خطی‌پذیری

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

قفل‌گذاری و انتخاب leader

سیستمی با رپلیکاسیون single-leader باید مطمئن شود واقعاً فقط یک leader وجود دارد، نه چند (split brain). یکی از راه‌های انتخاب leader استفاده از قفل است: هر گرهی که بالا می‌آید سعی می‌کند قفل را بگیرد و برنده leader می‌شود [۱۴]. هر طور این قفل پیاده شود، باید خطی‌پذیر باشد: همه گره‌ها باید بدانند کدام گره صاحب قفل است؛ وگرنه بی‌فایده است.

سرویس‌های هماهنگی مثل Apache ZooKeeper [۱۵] و etcd [۱۶] اغلب برای قفل توزیع‌شده و انتخاب leader به کار می‌روند. آن‌ها از الگوریتم‌های اجماع برای پیاده‌سازی عملیات خطی‌پذیر به‌شکل تحمل‌پذیر خطا استفاده می‌کنند (چنین الگوریتم‌هایی را بعداً در «اجماع تحمل‌پذیر خطا» در صفحه ۳۶۴ بحث می‌کنیم).iii هنوز جزئیات ظریف زیادی برای پیاده‌سازی درست قفل و انتخاب leader وجود دارد (مثلاً مسئله fencing در «leader و قفل» در صفحه ۳۰۱)، و کتابخانه‌هایی مثل Apache Curator [۱۷] با دستورالعمل‌های سطح بالاتر روی ZooKeeper کمک می‌کنند. با این حال، سرویس ذخیره‌سازی خطی‌پذیر پایه این کارهای هماهنگی است.

قفل‌گذاری توزیع‌شده در سطح ریزتر هم در برخی پایگاه‌های داده توزیع‌شده مثل Oracle Real Application Clusters (RAC) [۱۸] به کار می‌رود. RAC قفل به ازای هر صفحه دیسک دارد و چند گره به همان سیستم ذخیره‌سازی دیسک مشترک دسترسی دارند. چون این قفل‌های خطی‌پذیر در مسیر بحرانی اجرای تراکنش‌اند، استقرار RAC معمولاً شبکه interconnect اختصاصی برای ارتباط بین گره‌های پایگاه داده دارد.

iii. دقیق‌تر، ZooKeeper و etcd نوشتن خطی‌پذیر می‌دهند، اما خواندن ممکن است کهنه باشد چون به‌طور پیش‌فرض از هر رپلیکا سرویس می‌دهد. می‌توانید اختیاری خواندن خطی‌پذیر بخواهید: etcd آن را quorum read [۱۶] می‌نامد و در ZooKeeper باید قبل از خواندن sync() بزنید [۱۵]؛ به «پیاده‌سازی ذخیره‌سازی خطی‌پذیر با total order broadcast» در صفحه ۳۵۰.

قیدها و تضمین یکتایی

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

این وضعیت شبیه قفل است: وقتی کاربر در سرویس شما ثبت‌نام می‌کند، می‌توانید بگویید «قفل» نام کاربری انتخابی را گرفته. عملیات همچنین شبیه compare-and-set اتمی است: نام کاربری را روی شناسه کاربری که آن را گرفته تنظیم می‌کند، به شرطی که نام قبلاً گرفته نشده باشد.

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

در برنامه‌های واقعی گاهی قابل قبول است چنین قیدها را شل تفسیر کنید (مثلاً اگر پرواز overbook شده، مسافر را جابه‌جا و جبران کنید). در این موارد شاید خطی‌پذیری لازم نباشد و در «به‌موقع بودن و یکپارچگی» در صفحه ۵۲۴ چنین قیدهای شل را بحث می‌کنیم.

اما قید یکتایی سخت، مثل آنچه معمولاً در پایگاه‌های داده رابطه‌ای می‌بینید، به خطی‌پذیری نیاز دارد. قیدهای دیگر مثل foreign key یا قید attribute را می‌توان بدون خطی‌پذیری پیاده کرد [۱۹].

وابستگی‌های زمانی بین کانال‌ها

جزئیات شکل ۹-۱: اگر Alice نتیجه را فریاد نزده بود، Bob نمی‌فهمید نتیجه query کهنه است. چند ثانیه بعد دوباره refresh می‌زد و نتیجه نهایی را می‌دید. نقض خطی‌پذیری فقط به‌خاطر کانال ارتباطی اضافی در سیستم (صدای Alice به گوش Bob) آشکار شد.

وضعیت مشابه در سیستم‌های کامپیوتری پیش می‌آید. مثلاً وب‌سایتی دارید که کاربران عکس آپلود می‌کنند و فرآیند پس‌زمینه عکس‌ها را برای دانلود سریع‌تر به thumbnail کوچک می‌کند. معماری و جریان داده در شکل ۹-۵ آمده است.

شکل ۹-۵. وب‌سرور و image resizer هم از طریق file storage و هم message queue ارتباط دارند و امکان race condition وجود دارد.

image resizer باید صریحاً برای resize دستور بگیرد و این دستور از وب‌سرور از طریق message queue فرستاده می‌شود (فصل ۱۱). وب‌سرور کل عکس را روی صف نمی‌گذارد چون بیشتر message brokerها برای پیام کوچک طراحی شده‌اند و عکس ممکن است چند مگابایت باشد. در عوض، عکس اول در سرویس file storage نوشته می‌شود و پس از اتمام نوشتن، دستور resize روی صف قرار می‌گیرد.

اگر سرویس file storage خطی‌پذیر باشد، سیستم درست کار می‌کند. اگر نباشد، خطر race condition هست: message queue (گام‌های ۳ و ۴ در شکل ۹-۵) ممکن است سریع‌تر از رپلیکاسیون داخلی storage باشد. در این صورت وقتی resizer عکس را می‌گیرد (گام ۵)، ممکن است نسخه قدیمی یا هیچ چیز ببیند. اگر نسخه قدیمی را پردازش کند، عکس full-size و resized در storage برای همیشه ناسازگار می‌مانند.

این مشکل به‌خاطر دو کانال ارتباطی متفاوت بین وب‌سرور و resizer است: file storage و message queue. بدون تضمین تازگی خطی‌پذیری، race condition بین این دو کانال ممکن است. شبیه شکل ۹-۱ است که race بین رپلیکاسیون پایگاه داده و کانال صوتی واقعی بین دهان Alice و گوش Bob بود.

خطی‌پذیری تنها راه جلوگیری از این race نیست، اما ساده‌ترین برای فهم است. اگر کانال اضافی را کنترل کنید (مثل message queue، برخلاف Alice و Bob)، می‌توانید رویکردهایی شبیه «خواندن نوشته‌های خودتان» در صفحه ۱۶۲ به کار ببرید، با هزینه پیچیدگی بیشتر.

پیاده‌سازی سیستم‌های خطی‌پذیر

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

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

رایج‌ترین رویکرد برای تحمل خطا رپلیکاسیون است. روش‌های رپلیکاسیون فصل ۵ را مرور کنیم و ببینیم کدام می‌تواند خطی‌پذیر شود:

رپلیکاسیون single-leader (احتمالاً خطی‌پذیر)

در سیستم با رپلیکاسیون single-leader (به «Leaderها و Followerها» در صفحه ۱۵۲)، leader نسخه اصلی داده برای نوشتن دارد و followerها نسخه پشتیبان روی گره‌های دیگر نگه می‌دارند. اگر از leader یا followerهای به‌روزشده همزمان بخوانید، پتانسیل خطی‌پذیری وجود دارد.iv اما هر پایگاه داده single-leader واقعاً خطی‌پذیر نیست، یا عمداً (مثلاً snapshot isolation) یا به‌خاطر باگ همزمانی [۱۰].

خواندن از leader به فرض اینکه مطمئید leader کیست تکیه دارد. همان‌طور که در «حقیقت توسط اکثریت تعریف می‌شود» در صفحه ۳۰۰ گفتیم، ممکن است گرهی فکر کند leader است در حالی که نیست — و اگر آن leader توهمی به سرویس‌دهی ادامه دهد، احتمالاً خطی‌پذیری را نقض می‌کند [۲۰]. با رپلیکاسیون ناهمگام، failover ممکن است حتی نوشتن‌های commit‌شده را از دست بدهد (به «مدیریت خرابی گره‌ها» در صفحه ۱۵۶)، که هم durability و هم خطی‌پذیری را نقض می‌کند.

الگوریتم‌های اجماع (خطی‌پذیر)

برخی الگوریتم‌های اجماع که بعداً بحث می‌کنیم شبیه رپلیکاسیون single-leader‌اند، اما اقداماتی برای جلوگیری از split brain و رپلیکاهای کهنه دارند. به‌خاطر این جزئیات، الگوریتم‌های اجماع می‌توانند ذخیره‌سازی خطی‌پذیر را امن پیاده کنند. ZooKeeper [۲۱] و etcd [۲۲] این‌گونه کار می‌کنند.

رپلیکاسیون multi-leader (خطی‌پذیر نیست)

سیستم‌های multi-leader معمولاً خطی‌پذیر نیستند چون نوشتن را همزمان روی چند گره پردازش و ناهمگام به گره‌های دیگر رپلیک می‌کنند. بنابراین نوشتن‌های متعارض تولید می‌کنند که نیاز به حل دارند (به «مدیریت تعارض نوشتن» در صفحه ۱۷۱). چنین تعارض‌ها ناشی از نبود تک‌نسخه داده است.

رپلیکاسیون leaderless (احتمالاً خطی‌پذیر نیست)

برای سیستم‌های leaderless (سبک Dynamo؛ به «رپلیکاسیون Leaderless» در صفحه ۱۷۷)، گاهی می‌گویند با quorum خواندن و نوشتن (w + r > n) می‌توان «سازگاری قوی» گرفت. بسته به پیکربندی دقیق quorum و تعریف strong consistency، این کاملاً درست نیست.

روش‌های حل تعارض «آخرین نوشتن برنده» مبتنی بر ساعت روز (مثلاً در Cassandra؛ به «تکیه بر ساعت‌های همگام» در صفحه ۲۹۱) تقریباً قطعاً غیرخطی‌پذیرند چون به‌خاطر clock skew نمی‌توان timestamp را با ترتیب واقعی رویدادها سازگار دانست. Sloppy quorumها («Sloppy Quorumها و Hinted Handoff» در صفحه ۱۸۳) هم هر شانسی برای خطی‌پذیری را از بین می‌برند. حتی با strict quorum، رفتار غیرخطی‌پذیر ممکن است، همان‌طور که بخش بعد نشان می‌دهد.

iv. پارتیشن‌بندی (sharding) پایگاه داده single-leader، با leader جدا به ازای هر پارتیشن، بر خطی‌پذیری اثر نمی‌گذارد چون فقط تضمین تک‌شیء است. تراکنش‌های بین‌پارتیشنی موضوع جداست (به «تراکنش‌های توزیع‌شده و اجماع» در صفحه ۳۵۲).

خطی‌پذیری و quorumها

شهوداً به نظر می‌رسد strict quorum خواندن و نوشتن در مدل سبک Dynamo باید خطی‌پذیر باشد. اما با تأخیر متغیر شبکه، race condition ممکن است، همان‌طور که شکل ۹-۶ نشان می‌دهد.

شکل ۹-۶. اجرای غیرخطی‌پذیر، با وجود strict quorum.

در شکل ۹-۶، مقدار اولیه x برابر ۰ است و کلاینت نویسنده x را با ارسال نوشتن به هر سه رپلیکا (n = 3، w = 3) به ۱ به‌روز می‌کند. همزمان، کلاینت A از quorum دو گره (r = 2) می‌خواند و مقدار جدید ۱ را روی یکی می‌بیند. همزمان با نوشتن، کلاینت B از quorum دیگری از دو گره می‌خواند و مقدار قدیمی ۰ را از هر دو می‌گیرد.

شرط quorum برقرار است (w + r > n)، اما این اجرا باز هم خطی‌پذیر نیست: درخواست B بعد از اتمام درخواست A شروع می‌شود، اما B مقدار قدیمی و A مقدار جدید برمی‌گرداند. (باز همان وضعیت Alice و Bob در شکل ۹-۱.)

جالب است می‌توان quorumهای سبک Dynamo را با هزینه عملکرد کمتر خطی‌پذیر کرد: خواننده باید read repair (به «Read repair و anti-entropy» در صفحه ۱۷۸) را همزمان قبل از برگرداندن نتیجه به برنامه انجام دهد [۲۳]، و نویسنده باید قبل از ارسال نوشتن، آخرین وضعیت quorum گره‌ها را بخواند [۲۴، ۲۵]. اما Riak به‌خاطر جریمه عملکرد read repair همزمان انجام نمی‌دهد [۲۶]. Cassandra برای خواندن quorum منتظر اتمام read repair می‌ماند [۲۷]، اما اگر چند نوشتن همزمان روی همان کلید باشد به‌خاطر last-write-wins خطی‌پذیری را از دست می‌دهد.

علاوه بر این، فقط عملیات خواندن و نوشتن خطی‌پذیر این‌طور پیاده می‌شوند؛ عملیات compare-and-set خطی‌پذیر نه، چون به الگوریتم اجماع نیاز دارد [۲۸].

خلاصه، امن‌ترین فرض این است که سیستم leaderless با رپلیکاسیون سبک Dynamo خطی‌پذیری نمی‌دهد.

هزینه خطی‌پذیری

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

در فصل ۵ کاربردهای مختلف روش‌های رپلیکاسیون را دیدیم؛ مثلاً multi-leader اغلب برای رپلیکاسیون چند دیتاسنتری خوب است (به «عملیات چند دیتاسنتری» در صفحه ۱۶۸). نمونه استقرار در شکل ۹-۷ آمده است.

شکل ۹-۷. قطع شبکه که انتخاب بین خطی‌پذیری و دسترس‌پذیری را اجباری می‌کند.

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

در پایگاه داده multi-leader، هر دیتاسنتر عادی کار می‌کند: چون نوشتن‌ها از یک دیتاسنتر ناهمگام به دیگری رپلیک می‌شوند، در صف می‌مانند و با برقراری شبکه مبادله می‌شوند.

اگر single-leader استفاده شود، leader باید در یکی از دیتاسنترها باشد. هر نوشتن و هر خواندن خطی‌پذیر باید به leader فرستاده شود — پس برای کلاینت‌های متصل به دیتاسنتر follower، درخواست‌های خواندن و نوشتن باید همزمان از شبکه به دیتاسنتر leader بروند.

اگر در تنظیم single-leader شبکه بین دیتاسنترها قطع شود، کلاینت‌های متصل به follower نمی‌توانند به leader برسند، پس نه می‌توانند بنویسند و نه خطی‌پذیر بخوانند. از follower می‌توانند بخوانند، اما ممکن است کهنه (غیرخطی‌پذیر) باشد. اگر برنامه خواندن و نوشتن خطی‌پذیر می‌خواهد، قطع شبکه باعث unavailable شدن برنامه در دیتاسنترهایی می‌شود که به leader نمی‌رسند.

اگر کلاینت‌ها مستقیماً به دیتاسنتر leader وصل شوند، آنجا مشکل نیست. اما کلاینت‌هایی که فقط به follower می‌رسند تا تعمیر لینک شبکه outage می‌بینند.

قضیه CAP

این مسئله فقط نتیجه single-leader و multi-leader نیست: هر پایگاه داده خطی‌پذیر این مشکل را دارد، هر طور پیاده شده باشد. مخصوص multi-datacenter هم نیست؛ روی هر شبکه غیرقابل اعتماد، حتی داخل یک دیتاسنتر، رخ می‌دهد. مبادله این است:v

• اگر برنامه خطی‌پذیری می‌خواهد و به‌خاطر مشکل شبکه برخی رپلیکاها از بقیه جدا شده‌اند، برخی رپلیکاها تا تعمیر شبکه یا برگرداندن خطا نمی‌توانند درخواست پردازش کنند (در هر صورت unavailable می‌شوند).
• اگر برنامه خطی‌پذیری نمی‌خواهد، می‌توان طوری نوشت که هر رپلیکا مستقل درخواست پردازش کند حتی اگر از بقیه جدا باشد (مثلاً multi-leader). در این صورت برنامه در برابر مشکل شبکه available می‌ماند، اما رفتارش خطی‌پذیر نیست.

v. این دو انتخاب گاهی CP (سازگار اما در پارتیشن شبکه available نیست) و AP (available اما در پارتیشن شبکه سازگار نیست) نامیده می‌شوند. اما این طبقه‌بندی چند نقص دارد [۹] و بهتر است اجتناب شود.

پس برنامه‌هایی که خطی‌پذیری نمی‌خواهند تحمل‌پذیرتر مشکلات شبکه‌اند. این بینش به‌نام قضیه CAP [۲۹، ۳۰، ۳۱، ۳۲] شناخته می‌شود، که Eric Brewer در ۲۰۰۰ نامگذاری کرد، اگرچه مبادله از دهه ۱۹۷۰ برای طراحان پایگاه‌های داده توزیع‌شده شناخته بود [۳۳، ۳۴، ۳۵، ۳۶].

CAP در ابتدا به‌عنوان قاعده سرانگشتی بدون تعریف دقیق، برای شروع بحث مبادله در پایگاه‌های داده پیشنهاد شد. آن زمان بسیاری از پایگاه‌های داده توزیع‌شده روی معناشناسی خطی‌پذیر روی خوشه با ذخیره مشترک تمرکز داشتند [۱۸] و CAP مهندسان را به کاوش فضای طراحی گسترده‌تر سیستم‌های shared-nothing توزیع‌شده، مناسب‌تر برای سرویس‌های وب بزرگ، تشویق کرد [۳۷]. CAP شایسته اعتبار این تحول فرهنگی است — انفجار فناوری‌های پایگاه داده جدید از اواسط ۲۰۰۰ها (NoSQL).

قضیه CAP بی‌فایده

CAP گاهی به‌صورت Consistency، Availability، Partition tolerance: ۲ تا از ۳ را انتخاب کنید ارائه می‌شود. متأسفانه این گمراه‌کننده است [۳۲] چون پارتیشن شبکه نوعی خطاست و انتخابی نیست: خواهید خواه نخواهید رخ می‌دهد [۳۸].

وقتی شبکه درست کار می‌کند، سیستم می‌تواند هم سازگاری (خطی‌پذیری) و هم دسترس‌پذیری کامل بدهد. وقتی خطای شبکه رخ دهد، باید بین خطی‌پذیری یا دسترس‌پذیری کامل یکی را انتخاب کنید. پس بهتر است CAP را Consistent یا Available وقتی Partitioned بیان کنیم [۳۹]. شبکه قابل‌اعتمادتر این انتخاب را کمتر اجباری می‌کند، اما در نهایت اجتناب‌ناپذیر است.

در بحث CAP تعاریف متناقض زیادی از availability وجود دارد و رسمی‌سازی به‌عنوان قضیه [۳۰] با معنای معمول آن [۴۰] نمی‌خواند. بسیاری از سیستم‌های «بسیار available» (تحمل‌پذیر خطا) در واقع تعریف عجیب CAP از availability را برآورده نمی‌کنند. در کل، سوءتفاهم و سردرگمی زیاد حول CAP است و به فهم سیستم کمک نمی‌کند، پس بهتر است CAP اجتناب شود.

قضیه CAP به‌صورت رسمی [۳۰] دامنه بسیار محدودی دارد: فقط یک مدل سازگاری (خطی‌پذیری) و یک نوع خطا (پارتیشن شبکه،vi یعنی گره‌های زنده اما از هم جدا) را در نظر می‌گیرد. چیزی درباره تأخیر شبکه، گره مرده یا مبادله‌های دیگر نمی‌گوید. پس اگرچه CAP تاریخاً تأثیرگذار بوده، ارزش عملی کمی برای طراحی سیستم دارد [۹، ۴۰].

نتایج غیرممکن بودن جالب‌تری در سیستم‌های توزیع‌شده وجود دارد [۴۱] و CAP اکنون با نتایج دقیق‌تر جایگزین شده [۲، ۴۲]، پس عمدتاً اهمیت تاریخی دارد.

vi. همان‌طور که در «خطاهای شبکه در عمل» در صفحه ۲۷۹ گفتیم، در این کتاب partitioning یعنی تقسیم عمدی مجموعه داده بزرگ به کوچک‌تر (sharding؛ فصل ۶). پارتیشن شبکه نوع خاصی از خطای شبکه است که معمولاً جدا از سایر خطاها در نظر نمی‌گیریم. اما چون P در CAP است، در این مورد از سردرگمی نمی‌توانیم اجتناب کنیم.

خطی‌پذیری و تأخیر شبکه

اگرچه خطی‌پذیری تضمین مفیدی است، شگفت‌آورند چند سیستم در عمل واقعاً خطی‌پذیرند. مثلاً حتی RAM روی CPU چند هسته‌ای مدرن خطی‌پذیر نیست [۴۳]: اگر نخ روی یک هسته بنویسد و نخ دیگر کمی بعد همان آدرس را بخواند، تضمینی نیست مقدار نوشته‌شده توسط نخ اول را ببیند (مگر memory barrier یا fence [۴۴]).

دلیل: هر هسته CPU حافظه cache و store buffer خود را دارد. دسترسی حافظه اول به cache می‌رود و تغییرات ناهمگام به حافظه اصلی نوشته می‌شوند. چون cache خیلی سریع‌تر از حافظه اصلی است [۴۵]، برای عملکرد CPU مدرن ضروری است. اما اکنون چند نسخه داده وجود دارد (یکی در حافظه اصلی و شاید چند تا در cacheها) که ناهمگام به‌روز می‌شوند، پس خطی‌پذیری از دست می‌رود.

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

همین برای بسیاری از پایگاه‌های داده توزیع‌شده که خطی‌پذیری نمی‌دهند صادق است: عمدتاً برای افزایش عملکرد است، نه تحمل خطا [۴۶]. خطی‌پذیری کند است — همیشه، نه فقط در خطای شبکه.

آیا پیاده‌سازی کارآمدتر ذخیره‌سازی خطی‌پذیر ممکن است؟ به نظر می‌رسد نه: Attiya و Welch [۴۷] اثبات می‌کنند اگر خطی‌پذیری می‌خواهید، زمان پاسخ درخواست‌های خواندن و نوشتن حداقل متناسب با عدم قطعیت تأخیر شبکه است. در شبکه با تأخیر بسیار متغیر، مثل بیشتر شبکه‌های کامپیوتری (به «Timeoutها و تأخیرهای نامحدود» در صفحه ۲۸۱)، زمان پاسخ خواندن و نوشتن خطی‌پذیر ناگزیر بالا خواهد بود. الگوریتم سریع‌تر برای خطی‌پذیری وجود ندارد، اما مدل‌های سازگاری ضعیف‌تر می‌توانند خیلی سریع‌تر باشند، پس این مبادله برای سیستم‌های حساس به تأخیر مهم است. در فصل ۱۲ رویکردهایی برای اجتناب از خطی‌پذیری بدون قربانی صحت را بحث می‌کنیم.

تضمین‌های مرتب‌سازی

قبلاً گفتیم رجیستر خطی‌پذیر طوری رفتار می‌کند گویی فقط یک نسخه داده وجود دارد و هر عملیات در یک نقطه زمانی اتمی اثر می‌کند. این تعریف یعنی عملیات‌ها در ترتیب مشخصی اجرا می‌شوند. در شکل ۹-۴ با وصل کردن عملیات‌ها به ترتیبی که به نظر اجرا شده‌اند، مرتب‌سازی را نشان دادیم.

مرتب‌سازی موضوع تکرارشونده در این کتاب بوده و نشان می‌دهد ایده بنیادی مهمی است. خلاصه‌ای از بسترهای دیگر بحث مرتب‌سازی:

• در فصل ۵ دیدیم هدف اصلی leader در رپلیکاسیون single-leader تعیین ترتیب نوشتن‌ها در لاگ رپلیکاسیون است — یعنی ترتیبی که followerها آن نوشتن‌ها را اعمال می‌کنند. بدون leader واحد، به‌خاطر عملیات همزمان تعارض پیش می‌آید (به «مدیریت تعارض نوشتن» در صفحه ۱۷۱).
• سریال‌پذیری که در فصل ۷ بحث شد درباره تضمین این است که تراکنش‌ها طوری رفتار کنند گویی در ترتیب سریالی اجرا شده‌اند. می‌توان با اجرای واقعی سریال یا اجرای همزمان با جلوگیری از تعارض سریال‌سازی (قفل یا abort) به دست آورد.
• استفاده از timestamp و ساعت در سیستم‌های توزیع‌شده در فصل ۸ (به «تکیه بر ساعت‌های همگام» در صفحه ۲۹۱) تلاش دیگری برای نظم در دنیای آشفته است، مثلاً تعیین کدام یک از دو نوشتن دیرتر بوده.

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

مرتب‌سازی و علیت

چند دلیل دارد مرتب‌سازی مدام مطرح می‌شود؛ یکی حفظ علیت (causality) است. در طول کتاب چند مثال دیدیم که علیت مهم است:

• در «خواندن پیشوند سازگار» در صفحه ۱۶۵ (شکل ۵-۵) ناظر گفتگو اول پاسخ سؤال و بعد خود سؤال را دید. گیج‌کننده است چون شهود علت و معلول را نقض می‌کند: اگر سؤال جواب داده شده، سؤال باید اول بوده باشد، چون پاسخ‌دهنده سؤال را دیده (فرض نمی‌کنیم روشن‌بین است). می‌گوییم بین سؤال و پاسخ وابستگی علی وجود دارد.
• الگوی مشابه در شکل ۵-۹ دیدیم: بین سه leader رپلیکاسیون بود و برخی نوشتن‌ها به‌خاطر تأخیر شبکه از دیگران «سبقت» می‌گرفتند. از دید یکی از رپلیکاها به‌نظر می‌رسید سطری که وجود ندارد به‌روز شده. علیت اینجا یعنی سطر باید اول ساخته شود بعد به‌روز شود.
• در «تشخیص نوشتن‌های همزمان» در صفحه ۱۸۴ دیدیم اگر عملیات A و B داریم، سه حالت: A قبل از B، B قبل از A، یا A و B همزمان. رابطه happened before بیان دیگر علیت است: اگر A قبل از B بود، B ممکن است از A خبر داشته یا بر آن تکیه کرده باشد. اگر همزمان‌اند، پیوند علی نیست؛ یعنی مطمئنیم هیچ‌کدام از دیگری خبر نداشته.
• در زمینه snapshot isolation برای تراکنش‌ها («Snapshot Isolation و Repeatable Read» در صفحه ۲۳۷) گفتیم تراکنش از snapshot سازگار می‌خواند. «سازگار» اینجا یعنی سازگار با علیت: اگر snapshot پاسخی دارد، باید سؤال پاسخ‌داده‌شده را هم داشته باشد [۴۸]. دیدن کل پایگاه داده در یک نقطه زمانی با علیت سازگار است: اثر همه عملیات‌هایی که علیاً قبل از آن نقطه بودند دیده می‌شود، اما عملیات علیاً بعد از آن نه. Read skew (خواندن غیرتکرارپذیر، شکل ۷-۶) یعنی خواندن وضعیتی که علیت را نقض می‌کند.
• مثال‌های write skew بین تراکنش‌ها (به «Write Skew و Phantoms» در صفحه ۲۴۶) وابستگی علی نشان دادند: در شکل ۷-۸ Alice اجازه off call گرفت چون تراکنش فکر می‌کرد Bob هنوز on call است و برعکس. رفتن off call علیاً به مشاهده اینکه کی on call است وابسته است. Serializable Snapshot Isolation (SSI؛ به «Serializable Snapshot Isolation (SSI)» در صفحه ۲۶۱) write skew را با ردیابی وابستگی‌های علی بین تراکنش‌ها تشخیص می‌دهد.
• در مثال Alice و Bob و فوتبال (شکل ۹-۱)، اینکه Bob بعد از شنیدن فریاد Alice نتیجه کهنه از سرور گرفت نقض علیت است: فریاد Alice علیاً به اعلام نتیجه وابسته است، پس Bob هم باید بعد از شنیدن Alice نتیجه را ببیند. همان الگو در «وابستگی‌های زمانی بین کانال‌ها» در صفحه ۳۳۱ در قالب سرویس resize تصویر بود.

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

اگر سیستم ترتیب تحمیل‌شده توسط علیت را رعایت کند، سازگار علی (causally consistent) می‌گوییم. مثلاً snapshot isolation سازگاری علی می‌دهد: وقتی از پایگاه داده می‌خوانید و بخشی از داده را می‌بینید، باید هر داده‌ای که علیاً قبل از آن بوده را هم ببینید (با فرض حذف نشده باشد).

ترتیب علی، ترتیب کل نیست

ترتیب کل (total order) اجازه می‌دهد هر دو عنصر را مقایسه کنید؛ همیشه می‌گویید کدام بزرگ‌تر و کدام کوچک‌تر است. اعداد طبیعی ترتیب کل دارند: هر دو عدد را بدهید، مثلاً ۵ و ۱۳، می‌گویید ۱۳ از ۵ بزرگ‌تر است.

اما مجموعه‌های ریاضی ترتیب کل ندارند: آیا {a, b} از {b, c} بزرگ‌تر است؟ قابل مقایسه نیستند چون هیچ‌کدام زیرمجموعه دیگر نیست. ناقابل مقایسه‌اند؛ مجموعه‌های ریاضی ترتیب جزئی (partial order) دارند: گاهی یک مجموعه از دیگری بزرگ‌تر است (اگر همه عناصر دیگری را داشته باشد)، گاهی ناقابل مقایسه‌اند.

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

خطی‌پذیری

در سیستم خطی‌پذیر ترتیب کل عملیات داریم: اگر سیستم طوری رفتار کند گویی تک‌نسخه داده و هر عملیات اتمی است، برای هر دو عملیات همیشه می‌گوییم کدام اول بود. این ترتیب کل به‌صورت خط زمانی در شکل ۹-۴ نشان داده شده.

علیت

گفتیم دو عملیات اگر هیچ‌کدام قبل از دیگری نبود همزمان‌اند (به «رابطه happens-before و همزمانی» در صفحه ۱۸۶). به عبارت دیگر، دو رویداد اگر علیاً مرتبط‌اند مرتب‌اند (یکی قبل از دیگری)، اما اگر همزمان‌اند ناقابل مقایسه‌اند. علیت ترتیب جزئی تعریف می‌کند، نه کل: برخی عملیات نسبت به هم مرتب‌اند، برخی نه.

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

همزمانی یعنی خط زمانی شاخه و دوباره ادغام شود — عملیات روی شاخه‌های مختلف ناقابل مقایسه (همزمان)‌اند. در فصل ۵ دیدیم: شکل ۵-۱۴ خط مستقیم ترتیب کل نیست، بلکه عملیات همزمان درهم است. فلش‌ها وابستگی علی — ترتیب جزئی عملیات — را نشان می‌دهند.

اگر با سیستم‌های کنترل نسخه توزیع‌شده مثل Git آشنا هستید، تاریخچه نسخه‌ها شبیه گراف وابستگی‌های علی است. اغلب یک commit بعد از دیگری در خط مستقیم است، اما گاهی شاخه می‌گیرید (چند نفر همزمان کار می‌کنند) و merge وقتی ساخته می‌شود که commitهای همزمان ادغام شوند.

خطی‌پذیری قوی‌تر از سازگاری علی است

رابطه ترتیب علی و خطی‌پذیری چیست؟ خطی‌پذیری علیت را تضمین می‌کند: هر سیستم خطی‌پذیر علیت را درست حفظ می‌کند [۷]. به‌ویژه اگر چند کانال ارتباطی در سیستم باشد (مثل message queue و file storage در شکل ۹-۵)، خطی‌پذیری تضمین می‌کند علیت خودکار حفظ شود بدون کار خاص (مثل رد و بدل timestamp بین اجزا).

اینکه خطی‌پذیری علیت را تضمین می‌کند سیستم‌های خطی‌پذیر را ساده و جذاب می‌کند. اما همان‌طور که در «هزینه خطی‌پذیری» در صفحه ۳۳۵ گفتیم، خطی‌پذیر کردن سیستم می‌تواند به عملکرد و دسترس‌پذیری آسیب بزند، به‌ویژه با تأخیر شبکه زیاد (مثلاً توزیع جغرافیایی). برخی سیستم‌های داده توزیع‌شده خطی‌پذیری را رها کرده‌اند تا عملکرد بهتری بگیرند، اما کار با آن‌ها سخت‌تر می‌شود.

خبر خوب این است که میانه‌راه ممکن است. خطی‌پذیری تنها راه حفظ علیت نیست — راه‌های دیگر هم هست. سیستم می‌تواند سازگار علی باشد بدون جریمه عملکرد خطی‌پذیری (به‌ویژه قضیه CAP اعمال نمی‌شود). در واقع سازگاری علی قوی‌ترین مدل سازگاری است که به‌خاطر تأخیر شبکه کند نشود و در برابر خطای شبکه available بماند [۲، ۴۲].

در بسیاری موارد سیستم‌هایی که به نظر خطی‌پذیری می‌خواهند در واقع فقط سازگاری علی می‌خواهند که کارآمدتر پیاده می‌شود. بر این اساس، پژوهشگران انواع جدید پایگاه داده‌ای را بررسی می‌کنند که علیت را با ویژگی‌های عملکرد و دسترس‌پذیری شبیه سیستم‌های سازگار نهایی حفظ می‌کنند [۴۹، ۵۰، ۵۱].

این پژوهش نسبتاً تازه است و هنوز زیاد وارد تولید نشده؛ چالش‌هایی باقی است [۵۲، ۵۳]. اما جهت امیدوارکننده‌ای برای سیستم‌های آینده است.

ثبت وابستگی‌های علی

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

برای حفظ علیت باید بدانید کدام عملیات قبل از کدام دیگر بود. این ترتیب جزئی است: عملیات همزمان می‌توانند به هر ترتیبی پردازش شوند، اما اگر یکی قبل از دیگری بود، روی هر رپلیکا باید به همان ترتیب پردازش شوند. پس وقتی رپلیکا عملیاتی را پردازش می‌کند، باید مطمئن شود همه عملیات‌های علیاً قبلی (همه عملیاتی که قبل بودند) قبلاً پردازش شده‌اند؛ اگر عملیات قبلی کم است، عملیات بعدی باید منتظر بماند.

برای تعیین وابستگی‌های علی به روشی برای توصیف «دانش» یک گره نیاز دارید. اگر گره هنگام نوشتن Y قبلاً مقدار X را دیده، X و Y ممکن است علیاً مرتبط باشند. تحلیل از سؤالاتی شبیه تحقیقات کلاهبرداری است: آیا مدیرعامل هنگام تصمیم Y از X خبر داشت؟

تکنیک‌های تعیین اینکه کدام عملیات قبل از کدام دیگر بود شبیه «تشخیص نوشتن‌های همزمان» در صفحه ۱۸۴ است. آن بخش علیت در پایگاه داده leaderless را بحث کرد — تشخیص نوشتن همزمان روی همان کلید برای جلوگیری از از دست رفتن به‌روزرسانی. سازگاری علی فراتر می‌رود: وابستگی‌های علی را در کل پایگاه داده ردیابی می‌کند، نه فقط یک کلید. version vectorها را می‌توان تعمیم داد [۵۴].

برای تعیین ترتیب علی، پایگاه داده باید بداند برنامه کدام نسخه داده را خوانده. به همین دلیل در شکل ۵-۱۳ شماره نسخه عملیات قبلی هنگام نوشتن به پایگاه داده برگردانده می‌شود. ایده مشابه در تشخیص تعارض SSI («Serializable Snapshot Isolation (SSI)» در صفحه ۲۶۱): وقتی تراکنش می‌خواهد commit کند، پایگاه داده بررسی می‌کند نسخه‌ای که خوانده هنوز به‌روز است. برای این کار ردیابی می‌کند کدام داده را کدام تراکنش خوانده.

مرتب‌سازی با شماره توالی

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

راه بهتر: از شماره توالی یا timestamp برای مرتب‌سازی رویدادها استفاده کنیم. timestamp لزوماً از ساعت روز (یا ساعت فیزیکی با مشکلات زیاد؛ به «ساعت‌های غیرقابل اعتماد» در صفحه ۲۸۷) نیست؛ می‌تواند از ساعت منطقی (logical clock) بیاید — الگوریتمی برای تولید دنباله اعداد شناسایی عملیات، معمولاً با شمارنده‌ای که برای هر عملیات افزایش می‌یابد.

چنین شماره توالی یا timestamp فشرده است (چند بایت) و ترتیب کل می‌دهد: هر عملیات شماره توالی یکتا دارد و همیشه دو شماره را مقایسه می‌کنید کدام بزرگ‌تر است (کدام عملیات دیرتر بود).

به‌ویژه می‌توان شماره توالی در ترتیب کل سازگار با علیت ساخت:vii قول می‌دهیم اگر عملیات A علیاً قبل از B بود، A در ترتیب کل قبل از B باشد (شماره توالی A کمتر از B). عملیات همزمان می‌توانند دلخواه مرتب شوند. چنین ترتیب کل همه اطلاعات علیت را می‌گیرد، اما بیش از آنچه علیت strictly لازم دارد مرتب‌سازی تحمیل می‌کند.

در پایگاه داده با رپلیکاسیون single-leader (به «Leaderها و Followerها» در صفحه ۱۵۲)، لاگ رپلیکاسیون ترتیب کل نوشتن‌ها سازگار با علیت تعریف می‌کند. leader برای هر عملیات شمارنده را افزایش می‌دهد و شماره توالی یکنواخت افزایشی به هر عملیات در لاگ می‌دهد. اگر follower نوشتن‌ها را به ترتیب ظاهر در لاگ اعمال کند، وضعیت follower همیشه سازگار علی است (حتی اگر از leader عقب باشد).

مولدهای شماره توالی غیرعلی

بدون leader واحد (شاید multi-leader یا leaderless یا پارتیشن‌بندی)، تولید شماره توالی برای عملیات کمتر روشن است. روش‌های رایج:

• هر گره مجموعه مستقل شماره توالی تولید می‌کند. مثلاً با دو گره، یکی فقط فرد و دیگری زوج. عموماً چند بیت در نمایش دودویی شماره توالی برای شناسه یکتای گره رزرو می‌شود تا دو گره هرگز شماره یکسان نسازند.
• به هر عملیات timestamp از ساعت روز (ساعت فیزیکی) الصاق می‌شود [۵۵]. این‌ها متوالی نیستند، اما با وضوح بالا شاید برای ترتیب کل عملیات کافی باشند — در last write wins (به «Timestampها برای مرتب‌سازی رویدادها» در صفحه ۲۹۱).
• بلوک‌های شماره توالی از پیش تخصیص می‌شوند. مثلاً گره A بلوک ۱ تا ۱۰۰۰ و گره B بلوک ۱۰۰۱ تا ۲۰۰۰ را می‌گیرد. هر گره مستقل از بلوک خود شماره می‌دهد و وقتی تمام شد بلوک جدید می‌گیرد.

این سه گزینه بهتر و مقیاس‌پذیرتر از عبور همه عملیات از یک leader با شمارنده هستند. برای هر عملیات شماره توالی یکتا و تقریباً افزایشی می‌دهند. اما مشکل دارند: شماره‌های تولیدشده با علیت سازگار نیستند.

مشکلات علیت چون این مولدها ترتیب عملیات بین گره‌های مختلف را درست نمی‌گیرند:

• هر گره ممکن است تعداد متفاوتی عملیات در ثانیه پردازش کند. اگر یکی فرد و دیگری زوج تولید کند، شمارنده زوج ممکن است از فرد عقب یا جلو بماند. با یک عملیات فرد و یک زوج نمی‌توان دقیق گفت کدام علیاً اول بود.
• timestamp ساعت فیزیکی تحت clock skew است و ممکن است با علیت ناسازگار باشد. مثلاً شکل ۸-۳: عملیاتی که علیاً دیرتر بود timestamp پایین‌تری گرفت.viii
• در تخصیص بلوکی، یک عملیات شماره ۱۰۰۱–۲۰۰۰ و عملیات علیاً دیرتر شماره ۱–۱۰۰۰ می‌گیرد. شماره توالی با علیت ناسازگار است.

vii. ترتیب کل ناسازگار با علیت ساختن آسان است اما بی‌فایده. مثلاً UUID تصادفی برای هر عملیات و مقایسه lexicographic برای ترتیب کل — ترتیب کل معتبر است اما UUID تصادفی نمی‌گوید کدام عملیات واقعاً اول بود یا همزمان بودند.

viii. می‌توان timestamp ساعت فیزیکی را با علیت سازگار کرد: در «ساعت‌های همگام برای snapshotهای سراسری» در صفحه ۲۹۴ Spanner گوگل clock skew را تخمین می‌زند و قبل از commit نوشتن فاصله عدم قطعیت را صبر می‌کند تا تراکنش علیاً دیرتر timestamp بزرگ‌تر بگیرد. اما بیشتر ساعت‌ها معیار عدم قطعیت لازم را نمی‌دهند.

Timestampهای Lamport

اگرچه سه مولد شماره توالی بالا با علیت ناسازگارند، روش ساده‌ای برای تولید شماره توالی سازگار با علیت وجود دارد: timestamp Lamport، پیشنهاد Leslie Lamport در ۱۹۷۸ [۵۶]، یکی از پراستنادترین مقالات حوزه سیستم‌های توزیع‌شده.

استفاده timestamp Lamport در شکل ۹-۸ آمده. هر گره شناسه یکتا دارد و شمارنده تعداد عملیات پردازش‌شده را نگه می‌دارد. timestamp Lamport جفت (counter, node ID) است. دو گره گاهی counter یکسان دارند، اما با node ID هر timestamp یکتا می‌شود.

شکل ۹-۸. timestampهای Lamport ترتیب کل سازگار با علیت می‌دهند.

timestamp Lamport ربطی به ساعت فیزیکی روز ندارد، اما ترتیب کل می‌دهد: اگر دو timestamp دارید، آن با counter بزرگ‌تر بزرگ‌تر است؛ اگر counter برابر است، آن با node ID بزرگ‌تر بزرگ‌تر است.

تا اینجا اساساً همان شمارنده‌های فرد/زوج بخش قبل است. ایده کلیدی Lamport که آن را با علیت سازگار می‌کند: هر گره و هر کلاینت بیشینه counter دیده‌شده را نگه می‌دارد و در هر درخواست آن بیشینه را می‌فرستد. وقتی گره درخواست یا پاسخی با بیشینه counter بزرگ‌تر از counter خود می‌گیرد، فوراً counter خود را به آن بیشینه می‌برد.

در شکل ۹-۸، کلاینت A counter مقدار ۵ از گره ۲ می‌گیرد و بیشینه ۵ را به گره ۱ می‌فرستد. آن زمان counter گره ۱ فقط ۱ بود، اما فوراً به ۵ رفت، پس عملیات بعدی counter افزایشی ۶ داشت.

تا وقتی بیشینه counter با هر عملیات همراه است، مرتب‌سازی از timestampهای Lamport با علیت سازگار است چون هر وابستگی علی timestamp را افزایش می‌دهد.

timestampهای Lamport گاهی با version vectorها («تشخیص نوشتن‌های همزمان» در صفحه ۱۸۴) اشتباه می‌شوند. شباهت‌هایی هست، اما هدف متفاوت است: version vectorها می‌توانند بگویند دو عملیات همزمان‌اند یا یکی علیاً به دیگری وابسته؛ timestampهای Lamport همیشه ترتیب کل تحمیل می‌کنند. از ترتیب کل Lamport نمی‌توان فهمید دو عملیات همزمان‌اند یا علیاً وابسته. مزیت Lamport بر version vector فشردگی بیشتر است.

مرتب‌سازی timestamp کافی نیست

اگرچه timestampهای Lamport ترتیب کل عملیات سازگار با علیت تعریف می‌کنند، برای حل بسیاری مشکلات رایج سیستم‌های توزیع‌شده کافی نیستند.

مثلاً سیستمی که نام کاربری یکتا حساب کاربری را تضمین کند. اگر دو کاربر همزمان حساب با همان نام کاربری بسازند، یکی باید موفق و دیگری شکست بخورد (به «leader و قفل» در صفحه ۳۰۱).

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

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

برای اطمینان از اینکه گره دیگری همزمان همان نام را با timestamp پایین‌تر نمی‌سازد، باید با همه گره‌ها بپرسید چه می‌کنند [۵۶]. اگر یکی خراب شده یا به‌خاطر شبکه در دسترس نیست، سیستم متوقف می‌شود. این سیستم تحمل‌پذیر خطایی نیست که نیاز داریم.

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

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

ایده دانستن زمان نهایی شدن ترتیب کل در موضوع پخش ترتیب کل (total order broadcast) گرفته می‌شود.

پخش ترتیب کل

اگر برنامه فقط روی یک هسته CPU اجرا شود، تعریف ترتیب کل عملیات ساده است: همان ترتیبی که CPU اجرا کرده. اما در سیستم توزیع‌شده، توافق همه گره‌ها روی همان ترتیب کل عملیات دشوار است. در بخش قبل timestamp یا شماره توالی را بحث کردیم و دیدیم به اندازه رپلیکاسیون single-leader قوی نیست (اگر با مرتب‌سازی timestamp قید یکتایی پیاده کنید، هیچ خطایی را تحمل نمی‌کنید).

همان‌طور که گفتیم، رپلیکاسیون single-leader با انتخاب یک گره به‌عنوان leader و توالی‌بندی همه عملیات روی یک هسته CPU روی leader ترتیب کل عملیات را تعیین می‌کند. چالش: اگر throughput بیش از ظرفیت یک leader باشد چگونه مقیاس دهیم، و اگر leader خراب شود چگونه failover کنیم (به «مدیریت خرابی گره‌ها» در صفحه ۱۵۶). در ادبیات سیستم‌های توزیع‌شده این مسئله total order broadcast یا atomic broadcast [۲۵، ۵۷، ۵۸] نامیده می‌شود.ix

دامنه تضمین مرتب‌سازی

پایگاه‌های داده پارتیشن‌شده با leader واحد به ازای هر پارتیشن اغلب فقط مرتب‌سازی درون پارتیشن را نگه می‌دارند، یعنی تضمین سازگاری (مثلاً snapshot سازگار، ارجاع foreign key) بین پارتیشن‌ها نمی‌دهند. ترتیب کل بین همه پارتیشن‌ها ممکن است اما هماهنگی اضافی می‌خواهد [۵۹].

total order broadcast معمولاً به‌عنوان پروتکل تبادل پیام بین گره‌ها توصیف می‌شود. به‌طور غیررسمی دو ویژگی ایمنی همیشه باید برقرار باشد:

تحویل قابل اعتماد (Reliable delivery)

هیچ پیامی گم نمی‌شود: اگر به یک گره تحویل شد، به همه گره‌ها تحویل می‌شود.

تحویل با ترتیب کل (Totally ordered delivery)

پیام‌ها به هر گره به همان ترتیب تحویل می‌شوند.

الگوریتم درست total order broadcast باید تضمین کند ویژگی‌های قابلیت اطمینان و مرتب‌سازی همیشه برقرارند، حتی اگر گره یا شبکه معیوب باشد. البته وقتی شبکه قطع است پیام تحویل نمی‌شود، اما الگوریتم می‌تواند retry کند تا با تعمیر شبکه برسند (و هنوز به ترتیب درست تحویل شوند).

ix. اصطلاح atomic broadcast سنتی است اما گیج‌کننده است چون با سایر کاربردهای atomic ناسازگار است: ربطی به atomicity در تراکنش ACID ندارد و فقط غیرمستقیم به عملیات اتمی (برنامه‌نویسی چندنخی) یا رجیسترهای اتمی (ذخیره‌سازی خطی‌پذیر) مربوط است. total order multicast مترادف دیگر است.

استفاده از total order broadcast

سرویس‌های اجماع مثل ZooKeeper و etcd در واقع total order broadcast پیاده می‌کنند. این نشانه پیوند قوی بین total order broadcast و اجماع است که بعداً بررسی می‌کنیم.

total order broadcast دقیقاً برای رپلیکاسیون پایگاه داده لازم است: اگر هر پیام یک نوشتن به پایگاه داده باشد و هر رپلیکا همان نوشتن‌ها را به همان ترتیب پردازش کند، رپلیکاها با هم سازگار می‌مانند (جز تأخیر موقت رپلیکاسیون). این اصل رپلیکاسیون ماشین حالت (state machine replication) [۶۰] نامیده می‌شود و در فصل ۱۱ برمی‌گردیم.

به‌همین‌ترتیب total order broadcast می‌تواند تراکنش‌های سریال‌پذیر پیاده کند: اگر هر پیام تراکنش قطعی برای اجرا به‌عنوان stored procedure باشد و هر گره آن پیام‌ها را به همان ترتیب پردازش کند، پارتیشن‌ها و رپلیکاهای پایگاه داده سازگار می‌مانند [۶۱].

جنبه مهم total order broadcast این است که ترتیب هنگام تحویل پیام ثابت می‌شود: گره مجاز نیست بعداً پیامی را در جایگاه قبلی ترتیب درج کند اگر پیام‌های بعدی قبلاً تحویل شده‌اند. این total order broadcast را قوی‌تر از مرتب‌سازی timestamp می‌کند.

نگاه دیگر: total order broadcast راه ساخت لاگ است (لاگ رپلیکاسیون، لاگ تراکنش، write-ahead log): تحویل پیام مثل append به لاگ است. چون همه گره‌ها باید همان پیام‌ها را به همان ترتیب تحویل بگیرند، همه می‌توانند لاگ را بخوانند و همان دنباله پیام را ببینند.

total order broadcast برای سرویس قفل با fencing token (به «Fencing tokenها» در صفحه ۳۰۳) هم مفید است. هر درخواست گرفتن قفل به‌عنوان پیام به لاگ append می‌شود و همه پیام‌ها به ترتیب ظاهر در لاگ شماره‌گذاری متوالی می‌شوند. شماره توالی می‌تواند fencing token باشد چون یکنواخت افزایشی است. در ZooKeeper این شماره zxid [۱۵] نامیده می‌شود.

پیاده‌سازی ذخیره‌سازی خطی‌پذیر با total order broadcast

همان‌طور که در شکل ۹-۴ در سیستم خطی‌پذیر ترتیب کل عملیات وجود دارد، آیا خطی‌پذیری همان total order broadcast است؟ نه دقیقاً، اما پیوندهای نزدیک دارند.x

total order broadcast ناهمگام است: پیام‌ها قابل اعتماد در ترتیب ثابت تحویل می‌شوند، اما تضمینی نیست کی تحویل شوند (یک گیرنده ممکن است از بقیه عقب بماند). در مقابل، خطی‌پذیری تضمین تازگی است: خواندن تضمین می‌کند آخرین مقدار نوشته‌شده را ببیند.

با این حال، اگر total order broadcast دارید، می‌توانید ذخیره‌سازی خطی‌پذیر روی آن بسازید. مثلاً یکتایی نام کاربری برای حساب کاربری. برای هر نام کاربری ممکن، رجیستر خطی‌پذیر با compare-and-set اتمی تصور کنید. هر رجیستر اول null است (نام گرفته نشده). وقتی کاربر نام می‌خواهد، compare-and-set روی رجیستر آن نام اجرا می‌کنید و شناسه حساب را می‌گذارید، به شرط مقدار قبلی null باشد. اگر چند کاربر همزمان همان نام را بگیرند، فقط یک compare-and-set موفق می‌شود چون بقیه مقداری غیر از null می‌بینند (به‌خاطر خطی‌پذیری).

چنین compare-and-set خطی‌پذیر را می‌توان با total order broadcast به‌عنوان لاگ فقط-append [۶۲، ۶۳] پیاده کرد:

1. پیامی به لاگ append کنید که موقتاً نام کاربری مورد نظر را claim می‌کند.
2. لاگ را بخوانید و منتظر بمانید تا پیام appendشده به شما تحویل شود.xi
3. پیام‌های claim همان نام را بررسی کنید. اگر اولین پیام برای نام شما پیام خودتان است، موفقید: claim را commit کنید (شاید پیام دیگری به لاگ append کنید) و به کلاینت تأیید دهید. اگر اولین پیام از کاربر دیگر است، عملیات را abort کنید.

چون ورودی‌های لاگ به همه گره‌ها به همان ترتیب تحویل می‌شوند، اگر چند نوشتن همزمان باشد همه گره‌ها توافق می‌کنند کدام اول بود. انتخاب اولین نوشتن متعارض به‌عنوان برنده و abort بقیه تضمین می‌کند همه گره‌ها بدانند نوشتن commit یا abort شد. رویکرد مشابه برای تراکنش‌های چندشیء سریال‌پذیر روی لاگ [۶۲].

این روش نوشتن خطی‌پذیر تضمین می‌کند اما خواندن خطی‌پذیر نه — اگر از storeی که ناهمگام از لاگ به‌روز می‌شود بخوانید، ممکن است کهنه باشد. (دقیق‌تر، روش توصیف‌شده سازگاری متوالی (sequential consistency) [۴۷، ۶۴] می‌دهد، گاهی timeline consistency [۶۵، ۶۶]، کمی ضعیف‌تر از خطی‌پذیری.) برای خطی‌پذیر کردن خواندن:

• خواندن را از طریق لاگ توالی دهید: پیام append کنید، لاگ بخوانید، و خواندن واقعی وقتی پیام به شما تحویل شد انجام دهید. موقعیت پیام در لاگ نقطه زمانی خواندن را تعریف می‌کند. (quorum read در etcd تقریباً این‌طور کار می‌کند [۱۶].)
• اگر لاگ اجازه می‌دهد موقعیت آخرین پیام لاگ را به‌شکل خطی‌پذیر بگیرید، آن موقعیت را query کنید، منتظر تحویل همه ورودی‌ها تا آن موقعیت بمانید، بعد بخوانید. (ایده پشت sync() در ZooKeeper [۱۵].)
• از رپلیکایی بخوانید که روی نوشتن همزمان به‌روز می‌شود و پس مطمئناً به‌روز است. (در chain replication [۶۳]؛ به «پژوهش رپلیکاسیون» در صفحه ۱۵۵.)

x. به‌معنای رسمی، رجیستر خواندن-نوشتن خطی‌پذیر مسئله «آسان‌تر» است. total order broadcast معادل اجماع است [۶۷] که در مدل ناهمگام crash-stop راه‌حل قطعی ندارد [۶۸]، در حالی که رجیستر خطی‌پذیر در همان مدل سیستم پیاده می‌شود [۲۳، ۲۴، ۲۵]. اما پشتیبانی عملیات اتمی مثل compare-and-set یا increment-and-get در رجیستر آن را معادل اجماع می‌کند [۲۸]. پس مسائل اجماع و رجیستر خطی‌پذیر نزدیک‌اند.

xi. اگر منتظر نمانید و بلافاصله پس از enqueue نوشتن تأیید دهید، چیزی شبیه مدل سازگاری حافظه پردازنده‌های x86 چند هسته‌ای [۴۳] می‌گیرید — نه خطی‌پذیر و نه sequentially consistent.

پیاده‌سازی total order broadcast با ذخیره‌سازی خطی‌پذیر

بخش قبل نشان داد چگونه compare-and-set خطی‌پذیر از total order broadcast ساخت. می‌توان برعکس کرد: فرض ذخیره‌سازی خطی‌پذیر و ساخت total order broadcast از آن.

ساده‌ترین راه: رجیستر خطی‌پذیر که عدد صحیح نگه می‌دارد و عملیات اتمی increment-and-get دارد [۲۸]. compare-and-set اتمی هم کافی است.

الگوریتم ساده است: برای هر پیامی که می‌خواهید از total order broadcast بفرستید، عدد خطی‌پذیر را increment-and-get کنید و مقدار گرفته‌شده را به‌عنوان شماره توالی به پیام الصاق کنید. پیام را به همه گره‌ها بفرستید (پیام‌های گم‌شده را دوباره بفرستید) و گیرندگان پیام‌ها را پشت‌سرهم با شماره توالی تحویل می‌دهند.

برخلاف timestampهای Lamport، اعداد از increment رجیستر خطی‌پذیر دنباله بدون شکاف می‌سازند. پس اگر گره پیام ۴ را تحویل داده و پیام ورودی با شماره ۶ می‌گیرد، می‌داند باید منتظر پیام ۵ بماند تا ۶ را تحویل دهد. با timestamp Lamport اینطور نیست — در واقع تفاوت کلیدی total order broadcast و مرتب‌سازی timestamp است.

ساخت عدد صحیح خطی‌پذیر با increment-and-get اتمی چقدر سخت است؟ اگر چیزها هرگز خراب نشوند، آسان: روی یک گره در متغیر نگه دارید. مشکل وقتی اتصال شبکه به آن گره قطع شود و با خرابی گره مقدار بازیابی شود [۵۹]. عموماً اگر به مولدهای شماره توالی خطی‌پذیر فکر کنید، به الگوریتم اجماع می‌رسید.

این تصادفی نیست: اثبات می‌شود رجیستر compare-and-set (یا increment-and-get) خطی‌پذیر و total order broadcast هر دو معادل اجماع‌اند [۲۸، ۶۷]. یعنی اگر یکی را حل کنید، به دیگری تبدیل می‌کنید. بینش عمیق و شگفت‌انگیزی است!

وقت آن است که سرانجام مسئله اجماع را مستقیم بررسی کنیم — در ادامه این فصل.

تراکنش‌های توزیع‌شده و اجماع

اجماع یکی از مهم‌ترین و بنیادی‌ترین مسائل در محاسبات توزیع‌شده است. ظاهراً ساده است: به‌طور غیررسمی، هدف فقط این است که چند گره درباره چیزی توافق کنند. ممکن است فکر کنید نباید خیلی سخت باشد. متأسفانه سیستم‌های شکسته زیادی با باور اشتباه به سادگی این مسئله ساخته شده‌اند.

اگرچه اجماع بسیار مهم است، بخش آن دیر در کتاب آمده چون موضوع ظریف است و درک ظرافت‌ها پیش‌نیاز می‌خواهد. حتی در جامعه پژوهشی، درک اجماع دهه‌ها تدریجاً متبلور شده با سوءتفاهم‌های زیاد. اکنون رپلیکاسیون (فصل ۵)، تراکنش‌ها (فصل ۷)، مدل سیستم (فصل ۸)، خطی‌پذیری و total order broadcast (این فصل) را دیدیم و آماده‌ایم مسئله اجماع را بگیریم.

موقعیت‌هایی هست که توافق گره‌ها مهم است. مثلاً:

انتخاب leader

در پایگاه داده با رپلیکاسیون single-leader، همه گره‌ها باید توافق کنند کدام گره leader است. اگر به‌خاطر خطای شبکه برخی گره‌ها با بقیه ارتباط ندارند، موقعیت رهبری ممکن است مورد مناقشه شود. در این صورت اجماع برای جلوگیری از failover بد مهم است که به split brain منجر شود — دو گره هر دو فکر کنند leader هستند (به «مدیریت خرابی گره‌ها» در صفحه ۱۵۶). اگر دو leader باشند، هر دو نوشتن می‌پذیرند و داده‌ها واگرا و ناسازگار می‌شوند.

Commit اتمی

در پایگاه داده‌ای که تراکنش‌های چند گره یا پارتیشن را پشتیبانی می‌کند، تراکنش ممکن است روی برخی گره‌ها شکست و روی برخی موفق شود. اگر atomicity تراکنش (به معنای ACID؛ به «Atomicity» در صفحه ۲۲۳) را می‌خواهیم، باید همه گره‌ها درباره نتیجه تراکنش توافق کنند: یا همه abort/rollback (اگر مشکلی پیش آمد) یا همه commit (اگر مشکلی نبود). این نمونه اجماع مسئله commit اتمی (atomic commit problem) نامیده می‌شود.xii

غیرممکن بودن اجماع

شاید درباره نتیجه FLP [۶۸] — Fischer، Lynch و Paterson — شنیده باشید که اثبات می‌کند اگر خطر crash گره باشد، هیچ الگوریتمی همیشه نتواند به اجماع برسد. در سیستم توزیع‌شده باید فرض کنیم گره‌ها ممکن است crash کنند، پس اجماع قابل اعتماد غیرممکن است. پس چرا درباره الگوریتم‌های اجماع بحث می‌کنیم؟

پاسخ: نتیجه FLP در مدل سیستم ناهمگام (به «مدل سیستم و واقعیت» در صفحه ۳۰۶) اثبات شده — مدل بسیار محدودکننده‌ای که الگوریتم قطعی بدون ساعت یا timeout فرض می‌کند. اگر الگوریتم اجازه timeout یا راه دیگری برای شناسایی گره‌های مشکوک crash (حتی اگر گاهی اشتباه باشد) داشته باشد، اجماع قابل حل می‌شود [۶۷]. حتی اجازه اعداد تصادفی به الگوریتم برای دور زدن نتیجه غیرممکن بودن کافی است [۶۹].

پس اگرچه نتیجه FLP از اهمیت نظری زیاد برخوردار است، سیستم‌های توزیع‌شده معمولاً در عمل به اجماع می‌رسند.

در این بخش ابتدا مسئله commit اتمی را عمیق‌تر بررسی می‌کنیم. به‌ویژه الگوریتم two-phase commit (2PC) را بحث می‌کنیم — رایج‌ترین راه حل commit اتمی که در پایگاه‌های داده، سیستم‌های پیام و application serverهای مختلف پیاده شده. 2PC نوعی الگوریتم اجماع است — اما خیلی خوب نیست [۷۰، ۷۱].

با یادگیری از 2PC به الگوریتم‌های اجماع بهتر می‌رسیم، مثل آنچه در ZooKeeper (Zab) و etcd (Raft) به کار می‌رود.

xii. commit اتمی کمی متفاوت از اجماع رسمی‌سازی شده: تراکنش اتمی فقط اگر همه شرکت‌کنندگان رأی commit دهند commit می‌شود و اگر هر کدام abort لازم بداند باید abort شود. اجماع می‌تواند هر مقداری که یکی از شرکت‌کنندگان پیشنهاد داده تصمیم بگیرد. اما commit اتمی و اجماع به یکدیگر قابل تبدیل‌اند [۷۰، ۷۱]. commit اتمی nonblocking سخت‌تر از اجماع است — به «three-phase commit» در صفحه ۳۵۹.

Commit اتمی و Two-Phase Commit (2PC)

در فصل ۷ دیدیم هدف atomicity تراکنش معناشناسی ساده وقتی در میانه چند نوشتن مشکلی پیش می‌آید است. نتیجه تراکنش یا commit موفق — همه نوشتن‌های تراکنش پایدار — یا abort — همه نوشتن‌ها rollback (لغو یا دور انداخته) می‌شوند.

Atomicity از litter کردن پایگاه داده با نتایج نیمه‌کاره و وضعیت نیمه‌به‌روز جلوگیری می‌کند. به‌ویژه برای تراکنش‌های چندشیء (به «عملیات تک‌شیء و چندشیء» در صفحه ۲۲۸) و پایگاه‌های داده با ایندکس ثانویه مهم است. هر ایندکس ثانویه ساختار داده جدا از داده اصلی است — پس اگر داده‌ای را تغییر دهید، تغییر متناظر در ایندکس ثانویه هم لازم است. Atomicity تضمین می‌کند ایندکس ثانویه با داده اصلی سازگار بماند (اگر ناسازگار شود خیلی مفید نیست).

از commit اتمی تک‌گره به توزیع‌شده

برای تراکنش‌هایی که روی یک گره پایگاه داده اجرا می‌شوند، atomicity معمولاً توسط storage engine پیاده می‌شود. وقتی کلاینت از گره پایگاه داده commit تراکنش می‌خواهد، پایگاه داده نوشتن‌های تراکنش را پایدار می‌کند (معمولاً در write-ahead log؛ به «قابل اعتماد کردن B-treeها» در صفحه ۸۲) و سپس رکورد commit را به لاگ روی دیسک append می‌کند. اگر پایگاه داده در میانه crash کند، تراکنش از لاگ هنگام راه‌اندازی بازیابی می‌شود: اگر رکورد commit قبل از crash روی دیسک نوشته شده، تراکنش commit شده؛ وگرنه نوشتن‌های آن rollback می‌شوند.

پس روی یک گره، commitment تراکنش crucially به ترتیب نوشتن پایدار داده به دیسک بستگی دارد: اول داده، بعد رکورد commit [۷۲]. لحظه کلیدی commit یا abort لحظه‌ای است که دیسک نوشتن رکورد commit را تمام می‌کند: قبل از آن هنوز می‌توان abort کرد (به‌خاطر crash)، بعد از آن تراکنش commit شده (حتی اگر پایگاه داده crash کند). پس یک دستگاه (کنترلر یک درایو دیسک خاص، متصل به یک گره) commit را اتمی می‌کند.

اما اگر چند گره در تراکنش باشند؟ مثلاً تراکنش چندشیء در پایگاه داده پارتیشن‌شده، یا ایندکس ثانویه term-partitioned (ورودی ایندکس ممکن است روی گره دیگری از داده اصلی باشد؛ به «پارتیشن‌بندی و ایندکس‌های ثانویه» در صفحه ۲۰۶). بیشتر datastoreهای توزیع‌شده «NoSQL» چنین تراکنش‌های توزیع‌شده را پشتیبانی نمی‌کنند، اما سیستم‌های رابطه‌ای خوشه‌ای مختلفی دارند (به «تراکنش‌های توزیع‌شده در عمل» در صفحه ۳۶۰).

در این موارد کافی نیست فقط درخواست commit به همه گره‌ها بفرستید و مستقل روی هر کدام commit کنید. به‌راحتی ممکن است commit روی برخی موفق و روی برخی شکست بخورد و تضمین atomicity نقض شود:

• برخی گره‌ها نقض قید یا تعارض تشخیص می‌دهند و abort لازم است، در حالی که برخی موفق commit می‌کنند.
• برخی درخواست‌های commit در شبکه گم می‌شوند و به‌خاطر timeout abort می‌شوند، در حالی که برخی می‌رسند.
• برخی گره‌ها قبل از نوشتن کامل رکورد commit crash می‌کنند و در بازیابی rollback می‌کنند، در حالی که برخی موفق commit می‌کنند.

اگر برخی گره‌ها commit و برخی abort کنند، گره‌ها با هم ناسازگار می‌شوند (مثل شکل ۷-۳). وقتی تراکنش روی یک گره commit شده، دیگر نمی‌توان اگر بعداً روی گره دیگر abort شد retract کرد. به همین دلیل گره فقط وقتی commit کند که مطمئن باشد همه گره‌های دیگر تراکنش هم commit خواهند کرد.

commit تراکنش باید غیرقابل برگشت باشد — مجاز نیست بعد از commit نظر عوض کنید و تراکنش را retroactively abort کنید. دلیل: وقتی داده commit شد، برای تراکنش‌های دیگر visible می‌شود و کلاینت‌های دیگر ممکن است به آن تکیه کنند؛ این اصل پایه ایزولاسیون read committed است (به «Read Committed» در صفحه ۲۳۴). اگر بعد از commit abort مجاز بود، تراکنش‌هایی که داده commit‌شده را خوانده‌اند بر داده‌ای تکیه کرده‌اند که retroactively اعلام شده وجود نداشته — پس آن‌ها هم باید revert شوند.

(اثر تراکنش commit‌شده می‌تواند بعداً با تراکنش جبرانی دیگر undo شود [۷۳، ۷۴]. اما از دید پایگاه داده این تراکنش جداست و الزامات صحت بین‌تراکنشی مسئله برنامه است.)

مقدمه‌ای بر two-phase commit

Two-phase commit الگوریتمی برای دستیابی به commit اتمی تراکنش بین چند گره است — تضمین اینکه یا همه گره‌ها commit یا همه abort کنند. الگوریتم کلاسیک پایگاه‌های داده توزیع‌شده [۱۳، ۳۵، ۷۵] است. 2PC درون برخی پایگاه‌های داده استفاده می‌شود و به برنامه‌ها به‌صورت تراکنش‌های XA [۷۶، ۷۷] (مثلاً پشتیبانی Java Transaction API) یا WS-AtomicTransaction برای سرویس‌های وب SOAP [۷۸، ۷۹] در دسترس است.

جریان اصلی 2PC در شکل ۹-۹ آمده. به‌جای یک درخواست commit مثل تراکنش تک‌گره، فرایند commit/abort در 2PC به دو فاز تقسیم می‌شود (نام 2PC).

شکل ۹-۹. اجرای موفق two-phase commit (2PC).

2PC را با 2PL اشتباه نگیرید

Two-phase commit (2PC) و two-phase locking (به «Two-Phase Locking (2PL)» در صفحه ۲۵۷) دو چیز کاملاً متفاوت‌اند. 2PC commit اتمی در پایگاه داده توزیع‌شده می‌دهد، 2PL ایزولاسیون سریال‌پذیر. برای جلوگیری از سردرگمی بهتر است مفاهیم کاملاً جدا بدانید و شباهت نام را نادیده بگیرید.

2PC از جزئی جدیدی استفاده می‌کند که در تراکنش تک‌گره معمولاً نیست: هماهنگ‌کننده (coordinator؛ transaction manager هم نامیده می‌شود). coordinator اغلب کتابخانه‌ای در همان فرایند برنامه‌ای است که تراکنش می‌خواهد (مثلاً embedded در Java EE container)، اما می‌تواند فرایند یا سرویس جدا باشد. مثال‌ها: Narayana، JOTM، BTM، MSDTC.

تراکنش 2PC با خواندن و نوشتن برنامه روی چند گره پایگاه داده شروع می‌شود، مثل عادی. این گره‌های پایگاه داده شرکت‌کننده (participant) تراکنش نامیده می‌شوند. وقتی برنامه آماده commit است، coordinator فاز ۱ را شروع می‌کند: به هر گره prepare می‌فرستد و می‌پرسد آیا می‌تواند commit کند. coordinator پاسخ شرکت‌کنندگان را ردیابی می‌کند:

• اگر همه «بله» بگویند و آماده commit باشند، coordinator در فاز ۲ commit می‌فرستد و commit واقعی انجام می‌شود.
• اگر هر کدام «نه» بگوید، coordinator در فاز ۲ abort به همه گره‌ها می‌فرستد.

این فرایند کمی شبیه مراسم ازدواج سنتی غربی است: کشیش از عروس و داماد جداگانه می‌پرسد آیا می‌خواهند با هم ازدواج کنند و معمولاً از هر دو «بله» می‌گیرد. پس از هر دو تأیید، کشیش زن و شوهر اعلام می‌کند: تراکنش commit شده و خبر به همه حاضران اعلام می‌شود. اگر عروس یا داماد «بله» نگوید، مراسم abort می‌شود [۷۳].

سیستم قول‌ها

از این توصیف کوتاه شاید روشن نباشد چرا 2PC atomicity را تضمین می‌کند اما commit یک‌فازی بین چند گره نه. درخواست‌های prepare و commit در 2PC هم به‌راحتی گم می‌شوند. چه چیز 2PC را متفاوت می‌کند؟

برای فهم باید فرایند را دقیق‌تر بشکنیم:

1. وقتی برنامه می‌خواهد تراکنش توزیع‌شده شروع کند، transaction ID از coordinator می‌گیرد. این ID سراسری یکتا است.
2. برنامه روی هر شرکت‌کننده تراکنش تک‌گره شروع می‌کند و transaction ID سراسری یکتا را به آن می‌چسباند. همه خواندن و نوشتن در یکی از این تراکنش‌های تک‌گره است. اگر در این مرحله مشکلی پیش آید (crash گره یا timeout درخواست)، coordinator یا هر شرکت‌کننده می‌تواند abort کند.
3. وقتی برنامه آماده commit است، coordinator prepare با transaction ID سراسری به همه شرکت‌کنندگان می‌فرستد. اگر هر کدام از این درخواست‌ها شکست یا timeout شود، coordinator abort برای آن transaction ID به همه شرکت‌کنندگان می‌فرستد.
4. وقتی شرکت‌کننده prepare می‌گیرد، مطمئن می‌شود تحت همه شرایط می‌تواند تراکنش را commit کند. شامل نوشتن همه داده تراکنش به دیسک (crash، قطع برق یا پر شدن دیسک عذر قابل قبول برای امتناع از commit بعدی نیست) و بررسی تعارض یا نقض قید. با پاسخ «بله» به coordinator، گره قول می‌دهد اگر درخواست شد بدون خطا commit کند. به عبارت دیگر، شرکت‌کننده حق abort تراکنش را واگذار می‌کند، اما هنوز commit نکرده.
5. وقتی coordinator پاسخ همه prepareها را گرفت، تصمیم قطعی commit یا abort می‌گیرد (فقط اگر همه «بله» داده باشند commit). coordinator باید تصمیم را در transaction log روی دیسک بنویسد تا اگر بعداً crash کرد بداند چه تصمیمی گرفته. این نقطه commit (commit point) نامیده می‌شود.
6. وقتی تصمیم coordinator روی دیسک نوشته شد، درخواست commit یا abort به همه شرکت‌کنندگان فرستاده می‌شود. اگر این درخواست شکست یا timeout شود، coordinator باید برای همیشه retry کند تا موفق شود. دیگر برگشتی نیست: اگر تصمیم commit بود، باید اجرا شود، هر چند retry لازم باشد. اگر شرکت‌کننده در میانه crash کرده، تراکنش هنگام بازیابی commit می‌شود — چون «بله» داده، نمی‌تواند در بازیابی از commit امتناع کند.

پس پروتکل دو نقطه «بدون بازگشت» حیاتی دارد: وقتی شرکت‌کننده «بله» می‌دهد، قول می‌دهد حتماً بعداً commit کند (اگرچه coordinator ممکن است abort انتخاب کند)؛ و وقتی coordinator تصمیم گرفت، تصمیم غیرقابل برگشت است. این قول‌ها atomicity 2PC را تضمین می‌کنند. (commit اتمی تک‌گره این دو رویداد را در یکی ادغام می‌کند: نوشتن رکورد commit به transaction log.)

برگشت به تشبیه ازدواج: قبل از «بله»، شما و عروس/داماد آزادی دارید با «نه» تراکنش را abort کنید. اما بعد از «بله» نمی‌توانید آن را پس بگیرید. اگر بعد از «بله» غش کنید و کلام «شما زن و شوهر هستید» را نشنیدید، تراکنش commit شده تغییر نمی‌کند. وقتی هوشیار شدید، با پرسیدن وضعیت transaction ID سراسری از کشیش یا منتظر retry commit کشیش (که در تمام دوره بیهوشی ادامه یافته) ازدواج بودن یا نبودن را می‌فهمید.

خرابی coordinator

بحث کردیم اگر شرکت‌کننده یا شبکه در 2PC خراب شود چه می‌شود: اگر prepare شکست یا timeout شود، coordinator abort می‌کند؛ اگر commit یا abort شکست شود، coordinator بی‌نهایت retry می‌کند. اما اگر coordinator crash کند چه می‌شود کمتر روشن است.

اگر coordinator قبل از ارسال prepareها crash کند، شرکت‌کننده می‌تواند امن abort کند. اما وقتی شرکت‌کننده prepare گرفته و «بله» داده، دیگر نمی‌تواند یک‌طرفه abort کند — باید منتظر coordinator بماند بگوید تراکنش commit یا abort شد. اگر coordinator crash کند یا شبکه در این نقطه خراب شود، شرکت‌کننده فقط می‌تواند منتظر بماند. تراکنش شرکت‌کننده در این وضعیت مشکوک (in doubt) یا نامشخص (uncertain) نامیده می‌شود.

وضعیت در شکل ۹-۱۰ آمده. در این مثال coordinator تصمیم commit گرفته و پایگاه داده ۲ درخواست commit را گرفته. اما coordinator قبل از ارسال commit به پایگاه داده ۱ crash کرده، پس پایگاه داده ۱ نمی‌داند commit یا abort کند. حتی timeout هم کمک نمی‌کند: اگر پایگاه داده ۱ یک‌طرفه بعد از timeout abort کند، با پایگاه داده ۲ که commit کرده ناسازگار می‌شود. یک‌طرفه commit هم امن نیست چون شرکت‌کننده دیگر ممکن است abort کرده باشد.

شکل ۹-۱۰. coordinator پس از رأی «بله» شرکت‌کنندگان crash می‌کند. پایگاه داده ۱ نمی‌داند commit یا abort کند.

بدون شنیدن از coordinator، شرکت‌کننده راهی برای دانستن commit یا abort ندارد. در اصل شرکت‌کنندگان می‌توانند با هم ارتباط برقرار کنند و ببینند هر کدام چه رأیی داده و به توافق برسند، اما این بخش پروتکل 2PC نیست.

تنها راه تکمیل 2PC انتظار برای بازیابی coordinator است. به همین دلیل coordinator باید تصمیم commit یا abort را قبل از ارسال به شرکت‌کنندگان در transaction log روی دیسک بنوید: وقتی coordinator بازیابی می‌شود، وضعیت همه تراکنش‌های مشکوک را از log می‌خواند. هر تراکنشی که رکورد commit در log coordinator ندارد abort می‌شود. پس نقطه commit 2PC به commit اتمی تک‌گره معمولی روی coordinator خلاصه می‌شود.

Three-phase commit

Two-phase commit به‌خاطر اینکه 2PC می‌تواند منتظر بازیابی coordinator گیر کند، پروتکل commit اتمی blocking نامیده می‌شود. در نظر، می‌توان پروتکل commit اتمی nonblocking ساخت که با خرابی گره گیر نکند. اما در عمل این کار ساده نیست.

جایگزین 2PC، الگوریتم three-phase commit (3PC) پیشنهاد شده [۱۳، ۸۰]. اما 3PC شبکه با تأخیر محدود و گره‌ها با زمان پاسخ محدود فرض می‌کند؛ در بیشتر سیستم‌های عملی با تأخیر شبکه نامحدود و مکث فرآیند (فصل ۸) نمی‌تواند atomicity را تضمین کند.

عموماً commit اتمی nonblocking به detector خطای کامل (perfect failure detector) نیاز دارد [۶۷، ۷۱] — مکانیزم قابل اعتماد برای تشخیص crash گره. در شبکه با تأخیر نامحدود timeout detector خطای قابل اعتماد نیست چون درخواست ممکن است به‌خاطر مشکل شبکه timeout شود حتی اگر گره crash نکرده. به همین دلیل 2PC با وجود مشکل شناخته‌شده خرابی coordinator همچنان استفاده می‌شود.

تراکنش‌های توزیع‌شده در عمل

تراکنش‌های توزیع‌شده، به‌ویژه با two-phase commit، شهرت مختلطی دارند. از یک سو، تضمین ایمنی مهمی می‌دهند که بدون آن سخت به دست می‌آید؛ از سو دیگر، به‌خاطر مشکلات عملیاتی، کشتن عملکرد و وعده بیش از توانشان مورد انتقادند [۸۱، ۸۲، ۸۳، ۸۴]. بسیاری سرویس‌های ابری به‌خاطر مشکلات عملیاتی تراکنش توزیع‌شده پیاده نمی‌کنند [۸۵، ۸۶].

برخی پیاده‌سازی‌ها جریمه عملکرد سنگین دارند — مثلاً تراکنش توزیع‌شده در MySQL گزارش شده بیش از ۱۰ برابر کندتر از تک‌گره [۸۷]، پس تعجبی نیست وقتی مردم از آن دوری می‌کنند. بخش زیادی از هزینه ذاتی 2PC به disk forcing (fsync) اضافی برای بازیابی crash و round-trip شبکه اضافی است [۸۸].

اما به‌جای رد کلی تراکنش توزیع‌شده، باید دقیق‌تر بررسی کنیم چون درس‌های مهمی دارد. ابتدا دقیق باشیم منظور از «تراکنش توزیع‌شده» چیست. دو نوع کاملاً متفاوت اغلب قاطی می‌شوند:

تراکنش توزیع‌شده درون پایگاه داده

برخی پایگاه‌های داده توزیع‌شده (با رپلیکاسیون و پارتیشن‌بندی در پیکربندی استاندارد) تراکنش‌های درونی بین گره‌های همان پایگاه داده را پشتیبانی می‌کنند. مثلاً VoltDB و موتور NDB در MySQL Cluster. در این حالت همه شرکت‌کنندگان تراکنش همان نرم‌افزار پایگاه داده را اجرا می‌کنند.

تراکنش توزیع‌شده ناهمگن (heterogeneous)

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

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

پردازش پیام exactly-once

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

اگر تحویل پیام یا تراکنش پایگاه داده شکست بخورد، هر دو abort می‌شوند و message broker می‌تواند پیام را بعداً امن redeliver کند. پس با commit اتمی پیام و اثرات جانبی پردازشش، تضمین می‌کنیم پیام effectively دقیقاً یک‌بار پردازش شود، حتی اگر چند retry لازم بود. abort اثرات جانبی تراکنش نیمه‌تمام را دور می‌اندازد.

چنین تراکنش توزیع‌شده فقط ممکن است اگر همه سیستم‌های تحت تأثیر تراکنش بتوانند از همان پروتکل commit اتمی استفاده کنند. مثلاً اگر اثر جانبی پردازش پیام ارسال ایمیل باشد و سرور ایمیل 2PC را پشتیبانی نکند، ممکن است ایمیل دو یا چند بار فرستاده شود اگر پردازش پیام شکست بخورد و retry شود. اما اگر همه اثرات جانبی پردازش پیام در abort تراکنش rollback شوند، گام پردازش را امن retry کنید گویی اتفاقی نیفتاده.

در فصل ۱۱ به پردازش پیام exactly-once برمی‌گردیم. ابتدا پروتکل commit اتمی که چنین تراکنش ناهمگن را ممکن می‌کند را ببینیم.

تراکنش‌های XA

X/Open XA (مخفف eXtended Architecture) استانداردی برای پیاده‌سازی two-phase commit بین فناوری‌های ناهمگن [۷۶، ۷۷] است. در ۱۹۹۱ معرفی شد و گسترده پیاده شده: XA توسط بسیاری پایگاه‌های داده رابطه‌ای سنتی (PostgreSQL، MySQL، DB2، SQL Server، Oracle) و message brokerها (ActiveMQ، HornetQ، MSMQ، IBM MQ) پشتیبانی می‌شود.

XA پروتکل شبکه نیست — فقط C API برای رابط با transaction coordinator است. binding این API در زبان‌های دیگر وجود دارد؛ مثلاً در Java EE، تراکنش‌های XA با Java Transaction API (JTA) پیاده می‌شوند که توسط driverهای JDBC پایگاه داده و JMS message broker پشتیبانی می‌شود.

XA فرض می‌کند برنامه از network driver یا client library برای ارتباط با پایگاه داده یا سرویس پیام شرکت‌کننده استفاده می‌کند. اگر driver از XA پشتیبانی کند، یعنی XA API را صدا می‌زند تا بداند عملیات باید بخشی از تراکنش توزیع‌شده باشد — و در این صورت اطلاعات لازم به سرور پایگاه داده می‌فرستد. driver هم callbackهایی دارد که coordinator از شرکت‌کننده می‌خواهد prepare، commit یا abort کند.

transaction coordinator پیاده‌سازی XA API را انجام می‌دهد. استاندارد نحوه پیاده‌سازی را مشخص نمی‌کند، اما در عمل coordinator اغلب کتابخانه‌ای است که در همان فرایند برنامه صادرکننده تراکنش بارگذاری می‌شود (نه سرویس جدا). شرکت‌کنندگان تراکنش را ردیابی می‌کند، پس از درخواست prepare پاسخ‌ها را جمع می‌کند (از طریق callback به driver) و با log روی دیسک محلی تصمیم commit/abort هر تراکنش را نگه می‌دارد.

اگر فرایند برنامه crash کند یا ماشین برنامه بمیرد، coordinator هم می‌رود. هر شرکت‌کننده‌ای با تراکنش prepare شده اما commit نشده در مشکوک می‌ماند. چون log coordinator روی دیسک محلی application server است، آن سرور باید restart شود و کتابخانه coordinator log را بخواند تا نتیجه commit/abort هر تراکنش را بازیابی کند. فقط آنگاه coordinator از callbackهای XA driver شرکت‌کنندگان را می‌خواهد commit یا abort کند. سرور پایگاه داده نمی‌تواند مستقیم با coordinator تماس بگیرد چون همه ارتباط باید از client library برود.

نگه داشتن قفل‌ها در حالت مشکوک

چرا اینقدر به تراکنش گیرکرده در مشکوک اهمیت می‌دهیم؟ آیا بقیه سیستم نمی‌تواند کار کند و تراکنش مشکوک را که بعداً پاک می‌شود نادیده بگیرد؟

مشکل قفل است. همان‌طور که در «Read Committed» در صفحه ۲۳۴ گفتیم، تراکنش‌های پایگاه داده معمولاً قفل انحصاری سطح سطر روی سطرهای تغییریافته می‌گیرند تا dirty write نشود. علاوه بر این، برای ایزولاسیون سریال‌پذیر، پایگاه داده با two-phase locking باید قفل اشتراکی روی سطرهای خوانده‌شده توسط تراکنش بگیرد (به «Two-Phase Locking (2PL)» در صفحه ۲۵۷).

پایگاه داده تا commit یا abort تراکنش نمی‌تواند این قفل‌ها را آزاد کند (ناحیه سایه‌دار در شکل ۹-۹). پس با 2PC، تراکنش باید قفل‌ها را در تمام مدت مشکوک بودن نگه دارد. اگر coordinator crash کند و ۲۰ دقیقه طول بکشد بالا بیاید، قفل‌ها ۲۰ دقیقه نگه داشته می‌شوند. اگر log coordinator به هر دلیلی کاملاً گم شود، قفل‌ها برای همیشه — یا تا حل دستی توسط مدیر.

تا وقتی قفل‌ها نگه داشته می‌شوند، تراکنش دیگر نمی‌تواند آن سطرها را تغییر دهد. بسته به پایگاه داده، تراکنش‌های دیگر حتی از خواندن آن سطرها هم مسدود می‌شوند. پس تراکنش‌های دیگر نمی‌توانند کارشان را ادامه دهند — اگر به همان داده دسترسی بخواهند مسدود می‌شوند. بخش زیادی از برنامه ممکن است تا حل تراکنش مشکوک unavailable شود.

بازیابی از خرابی coordinator

در نظر، اگر coordinator crash کند و restart شود، باید وضعیت را از log بازیابی کند و تراکنش‌های مشکوک را حل کند. اما در عمل، تراکنش‌های مشکوک یتیم (orphaned) رخ می‌دهد [۸۹، ۹۰] — تراکنش‌هایی که coordinator به هر دلیلی (مثلاً گم یا خراب شدن log به‌خاطر باگ نرم‌افزار) نمی‌تواند نتیجه را تعیین کند. این تراکنش‌ها خودکار حل نمی‌شوند، پس برای همیشه در پایگاه داده می‌مانند، قفل نگه می‌دارند و تراکنش‌های دیگر را مسدود می‌کنند.

حتی restart سرورهای پایگاه داده این را حل نمی‌کند، چون پیاده‌سازی درست 2PC باید قفل‌های تراکنش مشکوک را حتی پس از restart حفظ کند (وگرنه تضمین atomicity را نقض می‌کند). وضعیت سخت است.

تنها راه، تصمیم دستی مدیر برای commit یا rollback تراکنش‌هاست. مدیر باید شرکت‌کنندگان هر تراکنش مشکوک را بررسی کند، ببیند آیا کسی قبلاً commit یا abort کرده، و همان نتیجه را به بقیه اعمال کند. حل مشکل ممکن است تلاش دستی زیاد بخواهد، احتمالاً تحت استرس و فشار زمان در outage جدی تولید (وگرنه چرا coordinator در چنین وضع بدی باشد؟).

بسیاری پیاده‌سازی‌های XA راه فرار اضطراری تصمیم ابتکاری (heuristic decisions) دارند: اجازه به شرکت‌کننده برای یک‌طرفه abort یا commit تراکنش مشکوک بدون تصمیم قطعی coordinator [۷۶، ۷۷، ۹۱]. روشن است heuristic اینجا کنایه از احتمال شکستن atomicity است چون سیستم قول‌های 2PC را نقض می‌کند. پس تصمیم‌های ابتکاری فقط برای خروج از وضعیت فاجعه‌بار است، نه استفاده عادی.

محدودیت‌های تراکنش توزیع‌شده

تراکنش‌های XA مسئله واقعی و مهم نگه داشتن چند سیستم داده شرکت‌کننده با هم سازگار را حل می‌کنند، اما مشکلات عملیاتی بزرگ هم معرفی می‌کنند. برداشت کلیدی: transaction coordinator خود نوعی پایگاه داده است (که نتایج تراکنش در آن ذخیره می‌شود) و باید با همان دقت سایر پایگاه‌های داده مهم به آن نزدیک شود:

• اگر coordinator replicate نشود و فقط روی یک ماشین اجرا شود، تک نقطه شکست کل سیستم است (چون خرابی آن باعث می‌شود application serverهای دیگر روی قفل‌های تراکنش‌های مشکوک block شوند). شگفت‌آور است بسیاری پیاده‌سازی‌های coordinator به‌طور پیش‌فرض بسیار available نیستند یا فقط پشتیبانی replication ابتدایی دارند.
• بسیاری application server سمت سرور با مدل stateless (مورد علاقه HTTP) توسعه می‌یابند، با همه وضعیت پایدار در پایگاه داده — مزیت: می‌توان application server را آزادانه اضافه و حذف کرد. اما وقتی coordinator بخشی از application server است، ماهیت استقرار عوض می‌شود. ناگهان logهای coordinator بخش حیاتی وضعیت پایدار سیستم می‌شوند — به‌اندازه خود پایگاه‌های داده مهم، چون برای بازیابی تراکنش‌های مشکوک پس از crash لازم‌اند. چنین application serverهایی دیگر stateless نیستند.
• چون XA باید با طیف گسترده سیستم‌های داده سازگار باشد، ناگزیر کمترین مخرج مشترک است. مثلاً نمی‌توان deadlock بین سیستم‌های مختلف تشخیص داد (نیاز به پروتکل استاندارد تبادل اطلاعات قفل‌هایی که هر تراکنش منتظرشان است) و با SSI کار نمی‌کند (به «Serializable Snapshot Isolation (SSI)» در صفحه ۲۶۱) چون پروتکل شناسایی تعارض بین سیستم‌های مختلف لازم است.
• برای تراکنش توزیع‌شده درون پایگاه داده (نه XA) محدودیت‌ها کمتر است — مثلاً نسخه توزیع‌شده SSI ممکن است. اما مشکل باقی می‌ماند: برای commit موفق 2PC همه شرکت‌کنندگان باید پاسخ دهند. پس اگر هر بخشی از سیستم خراب باشد، تراکنش هم شکست می‌خورد. تراکنش توزیع‌شده تمایل دارد خطاها را تقویت کند، در تضاد با هدف ساخت سیستم تحمل‌پذیر خطا.

آیا این یعنی امید نگه داشتن چند سیستم با هم سازگار را از دست بدهیم؟ نه کاملاً — روش‌های جایگزین همان کار را بدون درد تراکنش توزیع‌شده ناهمگن ممکن می‌کنند. در فصل‌های ۱۱ و ۱۲ برمی‌گردیم. اما ابتدا موضوع اجماع را جمع‌بندی کنیم.

اجماع تحمل‌پذیر خطا

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

مسئله اجماع معمولاً این‌طور رسمی می‌شود: یک یا چند گره ممکن است مقدار پیشنهاد دهند و الگوریتم اجماع روی یکی از آن مقادیر تصمیم می‌گیرد. در مثال رزرو صندلی، وقتی چند مشتری همزمان آخرین صندلی را می‌خرند، هر گرهی که درخواست مشتری را handle می‌کند ممکن است شناسه مشتریش را پیشنهاد دهد و تصمیم نشان می‌دهد کدام مشتری صندلی را گرفت.

در این رسمی‌سازی، الگوریتم اجماع باید ویژگی‌های زیر را برآورده کند [۲۵]:xiii

توافق یکنواخت (Uniform agreement)

هیچ دو گره‌ای متفاوت تصمیم نمی‌گیرند.

یکپارچگی (Integrity)

هیچ گره‌ای دو بار تصمیم نمی‌گیرد.

اعتبار (Validity)

اگر گره‌ای مقدار v را تصمیم گرفت، v توسط برخی گره‌ها پیشنهاد شده بود.

خاتمه (Termination)

هر گره‌ای که crash نکرده در نهایت مقداری را تصمیم می‌گیرد.

توافق یکنواخت و یکپارچگی ایده اصلی اجماع را تعریف می‌کنند: همه روی یک نتیجه توافق می‌کنند و وقتی تصمیم گرفتید نمی‌توانید نظر عوض کنید. اعتبار عمدتاً برای رد راه‌حل‌های بدیهی است: مثلاً الگوریتمی که همیشه null تصمیم بگیرد صرف‌نظر از پیشنهاد — توافق و یکپارچگی را برآورده می‌کند اما اعتبار را نه.

اگر تحمل خطا مهم نباشد، برآورده کردن سه ویژگی اول آسان است: یک گره را «دیکتاتور» hardcode کنید و همه تصمیم‌ها را بگیرد. اما اگر آن گره خراب شود، سیستم دیگر تصمیم نمی‌گیرد. در واقع در 2PC دیدیم: اگر coordinator خراب شود، شرکت‌کنندگان مشکوک نمی‌توانند commit یا abort را تعیین کنند.

ویژگی خاتمه ایده تحمل خطا را رسمی می‌کند. اساساً می‌گوید الگوریتم اجماع نمی‌تواند برای همیشه بی‌حرکت بماند — باید پیشرفت کند. حتی اگر برخی گره‌ها خراب شوند، بقیه باید به تصمیم برسند. (خاتمه ویژگی زنده‌مانی (liveness) است، سه دیگر ویژگی‌های ایمنی (safety) — به «ایمنی و زنده‌مانی» در صفحه ۳۰۸.)

مدل سیستم اجماع فرض می‌کند وقتی گره «crash» می‌کند، ناگهان ناپدید می‌شود و برنمی‌گردد. (به‌جای crash نرم‌افزاری، زلزله‌ای تصور کنید که دیتاسنتر گره شما را با رانش خاک مدفون کرده و دیگر آنلاین نمی‌شود.) در این مدل، هر الگوریتمی که باید منتظر بازیابی گره بماند نمی‌تواند خاتمه را برآورده کند. به‌ویژه 2PC شرایط خاتمه را برآورده نمی‌کند.

xiii. این نوع خاص اجماع uniform consensus نامیده می‌شود که در سیستم‌های ناهمگام با failure detectorهای غیرقابل اعتماد معادل consensus معمولی است [۷۱]. ادبیات آکادمیک معمولاً process می‌گوید، اما در این کتاب برای سازگاری با بقیه از node استفاده می‌کنیم.

البته اگر همه گره‌ها crash کنند و هیچ‌کدام اجرا نشوند، هیچ الگوریتمی نمی‌تواند چیزی تصمیم بگیرد. حدی برای تعداد خطاهایی که الگوریتم تحمل می‌کند وجود دارد: اثبات می‌شود هر الگوریتم اجماع برای تضمین خاتمه حداقل به اکثریت گره‌ها نیاز دارد که درست کار کنند [۶۷]. آن اکثریت می‌تواند امن quorum تشکیل دهد (به «Quorum برای خواندن و نوشتن» در صفحه ۱۷۹).

پس خاتمه مشروط به فرض این است که کمتر از نیمی از گره‌ها crash یا unreachable باشند. اما بیشتر پیاده‌سازی‌های اجماع تضمین می‌کنند ویژگی‌های ایمنی — توافق، یکپارچگی و اعتبار — همیشه برقرارند، حتی اگر اکثریت گره‌ها خراب شوند یا مشکل شبکه شدید باشد [۹۲]. پس outage بزرگ ممکن است پردازش درخواست را متوقف کند، اما سیستم اجماع را با تصمیم نامعتبر خراب نمی‌کند.

بیشتر الگوریتم‌های اجماع فرض می‌کنند خطای Byzantine نیست، همان‌طور که در «خطاهای Byzantine» در صفحه ۳۰۴ بحث شد. یعنی اگر گره پروتکل را درست دنبال نکند (مثلاً پیام‌های متناقض به گره‌های مختلف بفرستد)، ممکن است ویژگی‌های ایمنی پروتکل را بشکند. می‌توان اجماع را در برابر خطای Byzantine مقاوم کرد تا وقتی کمتر از یک‌سوم گره‌ها Byzantine-faulty باشند [۲۵، ۹۳]، اما جا برای بحث جزئی آن الگوریتم‌ها در این کتاب نیست.

الگوریتم‌های اجماع و total order broadcast

شناخته‌شده‌ترین الگوریتم‌های اجماع تحمل‌پذیر خطا: Viewstamped Replication (VSR) [۹۴، ۹۵]، Paxos [۹۶، ۹۷، ۹۸، ۹۹]، Raft [۲۲، ۱۰۰، ۱۰۱]، و Zab [۱۵، ۲۱، ۱۰۲]. شباهت‌های زیادی بین این الگوریتم‌ها هست، اما یکسان نیستند [۱۰۳]. در این کتاب به جزئیات کامل الگوریتم‌های مختلف نمی‌رویم: آگاهی از ایده‌های سطح بالا مشترک کافی است، مگر اینکه خودتان سیستم اجماع پیاده کنید (که احتمالاً توصیه نمی‌شود — سخت است [۹۸، ۱۰۴]).

بیشتر این الگوریتم‌ها مستقیماً از مدل رسمی اینجا (پیشنهاد و تصمیم روی یک مقدار با برآورده کردن توافق، یکپارچگی، اعتبار و خاتمه) استفاده نمی‌کنند. در عوض، روی دنباله‌ای از مقادیر تصمیم می‌گیرند که آن‌ها را الگوریتم total order broadcast می‌کند (به «پخش ترتیب کل» در صفحه ۳۴۸).

به یاد آورید total order broadcast می‌خواهد پیام‌ها دقیقاً یک‌بار، به همان ترتیب، به همه گره‌ها تحویل شوند. اگر فکر کنید، معادل انجام چند دور اجماع است: در هر دور، گره‌ها پیامی که می‌خواهند بعدی بفرستند پیشنهاد می‌دهند و روی پیام بعدی برای تحویل در ترتیب کل تصمیم می‌گیرند [۶۷].

پس total order broadcast معادل دورهای مکرر اجماع است (هر تصمیم اجماع متناظر با یک تحویل پیام):

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

Viewstamped Replication، Raft و Zab مستقیماً total order broadcast پیاده می‌کنند چون از دورهای مکرر اجماع یک‌مقدار‌در‌هر‌بار کارآمدتر است. در Paxos این بهینه‌سازی Multi-Paxos نامیده می‌شود.

رپلیکاسیون single-leader و اجماع

در فصل ۵ رپلیکاسیون single-leader را بحث کردیم (به «Leaderها و Followerها» در صفحه ۱۵۲): همه نوشتن‌ها به leader و به همان ترتیب روی followerها اعمال می‌شوند و رپلیکاها به‌روز می‌مانند. آیا این اساساً total order broadcast نیست؟ چرا در فصل ۵ نگران اجماع نبودیم؟

پاسخ به نحوه انتخاب leader برمی‌گردد. اگر leader را اپراتورها دستی انتخاب و پیکربندی کنند، اساساً الگوریتم اجماع «دیکتاتوری» دارید: فقط یک گره مجاز است بنویسد (تصمیم ترتیب نوشتن در لاگ رپلیکاسیون) و اگر آن گره down شود، سیستم برای نوشتن unavailable می‌ماند تا اپراتورها گره دیگری را leader کنند. چنین سیستمی در عمل خوب کار می‌کند، اما خاتمه اجماع را برآورده نمی‌کند چون برای پیشرفت مداخله انسان لازم است.

برخی پایگاه‌های داده انتخاب leader و failover خودکار انجام می‌دهند و follower را leader جدید می‌کنند اگر leader قدیمی خراب شود (به «مدیریت خرابی گره‌ها» در صفحه ۱۵۶). این به total order broadcast تحمل‌پذیر خطا و حل اجماع نزدیک‌تر می‌کند.

اما مشکلی هست. قبلاً split brain را بحث کردیم و گفتیم همه گره‌ها باید توافق کنند leader کیست — وگرنه دو گره هر کدام فکر کنند leader هستند و پایگاه داده ناسازگار می‌شود. پس برای انتخاب leader به اجماع نیاز داریم. اما اگر الگوریتم‌های اجماع اینجا در واقع الگوریتم total order broadcast باشند، و total order broadcast شبیه رپلیکاسیون single-leader، و رپلیکاسیون single-leader به leader نیاز دارد، پس…

به نظر می‌رسد برای انتخاب leader، اول به leader نیاز داریم. برای حل اجماع، اول باید اجماع را حل کنیم. چگونه از این بن‌بست خارج شویم؟

شماره‌گذاری epoch و quorumها

همه پروتکل‌های اجماع بحث‌شده دروناً به شکلی از leader استفاده می‌کنند، اما یکتایی leader را تضمین نمی‌کنند. در عوض تضمین ضعیف‌تری می‌دهند: پروتکل‌ها شماره epoch تعریف می‌کنند (در Paxos ballot number، در Viewstamped Replication view number، در Raft term number) و تضمین می‌کنند در هر epoch leader یکتا است.

هر بار leader فعلی مرده فرض می‌شود، بین گره‌ها رأی برای انتخاب leader جدید شروع می‌شود. این انتخابابات شماره epoch افزایشی می‌گیرد، پس شماره‌های epoch ترتیب کل و یکنواخت افزایشی دارند. اگر بین دو leader در دو epoch مختلف تعارض باشد (شاید leader قبلی واقعاً مرده نبود)، leader با شماره epoch بالاتر برنده می‌شود.

قبل از اینکه leader اجازه تصمیم داشته باشد، باید بررسی کند leader دیگری با epoch بالاتر که تصمیم متعارض بگیرد وجود ندارد. leader چگونه می‌فهمد عزل نشده؟ به یاد آورید «حقیقت توسط اکثریت تعریف می‌شود» در صفحه ۳۰۰: گره نمی‌تواند لزوماً به قضاوت خودش اعتماد کند — فقط به‌خاطر اینکه فکر می‌کند leader است، لزوماً بقیه او را leader نمی‌پذیرند.

در عوض باید رأی از quorum گره‌ها جمع کند (به «Quorum برای خواندن و نوشتن» در صفحه ۱۷۹). برای هر تصمیمی که leader می‌خواهد بگیرد، مقدار پیشنهادی را به گره‌های دیگر می‌فرستد و منتظر پاسخ موافق quorum می‌ماند. quorum معمولاً (اما نه همیشه) اکثریت گره‌هاست [۱۰۵]. گره فقط اگر از leader دیگری با epoch بالاتر خبر نداشته باشد به پیشنهاد رأی موافق می‌دهد.

پس دو دور رأی داریم: یکی برای انتخاب leader، دومی برای رأی به پیشنهاد leader. بینش کلیدی: quorumهای این دو رأی باید همپوشانی داشته باشند: اگر رأی به پیشنهاد موفق شود، حداقل یکی از گره‌هایی که رأی دادند در آخرین انتخابابات leader شرکت کرده [۱۰۵]. پس اگر رأی به پیشنهاد epoch بالاتری نشان ندهد، leader فعلی می‌تواند نتیجه بگیرد انتخابابات leader با epoch بالاتر رخ نداده و هنوز رهبری دارد. آنگاه می‌تواند امن مقدار پیشنهادی را تصمیم بگیرد.

این فرایند رأی‌گیری ظاهراً شبیه two-phase commit است. بزرگ‌ترین تفاوت‌ها: در 2PC coordinator انتخاب نمی‌شود، و الگوریتم‌های اجماع تحمل‌پذیر خطا فقط به رأی اکثریت گره‌ها نیاز دارند، در حالی که 2PC به رأی «بله» هر شرکت‌کننده نیاز دارد. علاوه بر این، الگوریتم‌های اجماع فرایند بازیابی تعریف می‌کنند که گره‌ها پس از انتخاب leader جدید به وضعیت سازگار برسند و ویژگی‌های ایمنی همیشه برقرار بماند. این تفاوت‌ها کلید صحت و تحمل خطای الگوریتم اجماع‌اند.

محدودیت‌های اجماع

الگوریتم‌های اجماع پیشرفت بزرگی برای سیستم‌های توزیع‌شده‌اند: ویژگی‌های ایمنی مشخص (توافق، یکپارچگی، اعتبار) به سیستم‌هایی می‌دهند که همه چیز دیگر نامشخص است، و با این حال تحمل‌پذیر خطا می‌مانند (تا وقتی اکثریت گره‌ها کار می‌کنند و reachable‌اند). total order broadcast می‌دهند و بنابراین می‌توانند عملیات اتمی خطی‌پذیر را تحمل‌پذیر خطا پیاده کنند (به «پیاده‌سازی ذخیره‌سازی خطی‌پذیر با total order broadcast» در صفحه ۳۵۰).

با این حال، همه‌جا استفاده نمی‌شوند چون مزایا هزینه دارد.

فرایندی که گره‌ها قبل از تصمیم روی پیشنهادها رأی می‌دهند نوعی رپلیکاسیون همزمان است. همان‌طور که در «رپلیکاسیون همزمان در برابر ناهمگام» در صفحه ۱۵۳ گفتیم، پایگاه‌های داده اغلب رپلیکاسیون ناهمگام پیکربندی می‌شوند. در این پیکربندی، برخی داده commit‌شده ممکن است در failover از دست برود — اما بسیاری این ریسک را برای عملکرد بهتر می‌پذیرند.

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

بیشتر الگوریتم‌های اجماع مجموعه ثابتی از گره‌های شرکت‌کننده در رأی را فرض می‌کنند، یعنی نمی‌توانید گره را به خوشه اضافه یا حذف کنید. پسوندهای عضویت پویا (dynamic membership) به الگوریتم‌های اجماع اجازه می‌دهند مجموعه گره‌ها در طول زمان تغییر کند، اما خیلی کمتر از الگوریتم‌های عضویت ثابت فهمیده شده‌اند.

سیستم‌های اجماع عموماً برای تشخیص گره خراب به timeout تکیه می‌کنند. در محیط‌های با تأخیر شبکه بسیار متغیر، به‌ویژه سیستم‌های توزیع‌شده جغرافیایی، اغلب گره به‌اشتباه فکر می‌کند leader به‌خاطر مشکل گذرای شبکه خراب شده. اگرچه این خطا به ایمنی آسیب نمی‌زند، انتخابابات مکرر leader عملکرد وحشتناک می‌دهد چون سیستم ممکن است بیشتر وقتش را صرف انتخاب leader کند تا کار مفید.

گاهی الگوریتم‌های اجماع به مشکلات شبکه حساس‌اند. مثلاً نشان داده شده Raft حالت‌های مرزی ناخوشایندی دارد [۱۰۶]: اگر کل شبکه درست کار کند جز یک لینک خاص که مداوم غیرقابل اعتماد است، Raft می‌تواند به وضعیتی برسد که رهبری مدام بین دو گره جابه‌جا شود یا leader فعلی مدام مجبور به استعفا شود و سیستم عملاً هرگز پیشرفت نکند. الگوریتم‌های اجماع دیگر مشکلات مشابه دارند و طراحی الگوریتم‌های مقاوم‌تر به شبکه‌های غیرقابل اعتماد هنوز مسئله باز پژوهشی است.

عضویت و سرویس‌های هماهنگی

پروژه‌هایی مثل ZooKeeper یا etcd اغلب «key-value store توزیع‌شده» یا «سرویس هماهنگی و پیکربندی» نامیده می‌شوند. API چنین سرویسی شبیه پایگاه داده است: مقدار کلید را می‌خوانید و می‌نویسید و روی کلیدها iterate می‌کنید. پس اگر اساساً پایگاه داده‌اند، چرا الگوریتم اجماع پیاده می‌کنند؟ چه چیزی آن‌ها را از هر پایگاه داده دیگر متفاوت می‌کند؟

برای فهم، کوتاه ببینیم ZooKeeper چگونه استفاده می‌شود. به‌عنوان توسعه‌دهنده برنامه به‌ندرت مستقیم از ZooKeeper استفاده می‌کنید، چون برای پایگاه داده عمومی مناسب نیست. احتمالاً غیرمستقیم از پروژه دیگر به آن تکیه می‌کنید: HBase، Hadoop YARN، OpenStack Nova و Kafka همه در پس‌زمینه به ZooKeeper متکی‌اند. این پروژه‌ها چه می‌گیرند؟

ZooKeeper و etcd برای نگه‌داشتن مقدار کمی داده طراحی شده‌اند که کاملاً در حافظه جا می‌شود (اگرچه برای durability به دیسک هم می‌نویسند) — پس نمی‌خواهید همه داده برنامه را اینجا نگه دارید. آن مقدار کم داده با الگوریتم total order broadcast تحمل‌پذیر خطا بین همه گره‌ها رپلیک می‌شود. همان‌طور که گفتیم، total order broadcast دقیقاً برای رپلیکاسیون پایگاه داده لازم است: اگر هر پیام یک نوشتن باشد، اعمال همان نوشتن‌ها به همان ترتیب رپلیکاها را سازگار نگه می‌دارد.

ZooKeeper بر اساس سرویس قفل Chubb گوگل [۱۴، ۹۸] مدل شده و علاوه بر total order broadcast (و بنابراین اجماع)، مجموعه جالبی از ویژگی‌های دیگر دارد که برای ساخت سیستم توزیع‌شده مفید است:

عملیات اتمی خطی‌پذیر

با compare-and-set اتمی می‌توانید قفل پیاده کنید: اگر چند گره همزمان همان عملیات را بخواهند، فقط یکی موفق می‌شود. پروتکل اجماع تضمین می‌کند عملیات اتمی و خطی‌پذیر باشد، حتی اگر گره خراب شود یا شبکه در هر نقطه قطع شود. قفل توزیع‌شده معمولاً به‌صورت lease با زمان انقضا پیاده می‌شود تا اگر کلاینت خراب شد در نهایت آزاد شود (به «مکث‌های فرآیند» در صفحه ۲۹۵).

ترتیب کل عملیات

همان‌طور که در «leader و قفل» در صفحه ۳۰۱ گفتیم، وقتی منبعی با قفل یا lease محافظت می‌شود، به fencing token نیاز دارید تا در مکث فرآیند کلاینت‌ها با هم تعارض نکنند. fencing token عددی است که هر بار گرفتن قفل یکنواخت افزایش می‌یابد. ZooKeeper با ترتیب کل همه عملیات و دادن transaction ID یکنواخت افزایشی (zxid) و شماره نسخه (cversion) به هر عملیات [۱۵] این را فراهم می‌کند.

تشخیص خرابی

کلاینت‌ها session بلندمدت روی سرورهای ZooKeeper نگه می‌دارند و کلاینت و سرور دوره‌ای heartbeat رد و بدل می‌کنند تا زنده بودن طرف مقابل را چک کنند. حتی اگر اتصال موقتاً قطع یا گره ZooKeeper خراب شود، session فعال می‌ماند. اما اگر heartbeat بیش از مدت session timeout متوقف شود، ZooKeeper session را مرده اعلام می‌کند. قفل‌های نگه‌داشته‌شده توسط session می‌توانند طوری پیکربندی شوند که با timeout session خودکار آزاد شوند (ZooKeeper آن‌ها را ephemeral node می‌نامد).

اعلان تغییر

نه تنها یک کلاینت می‌تواند قفل‌ها و مقادیری که کلاینت دیگر ساخته بخواند، بلکه می‌تواند برای تغییر watch کند. پس کلاینت می‌فهمد کلاینت دیگر به خوشه پیوسته (بر اساس مقداری که در ZooKeeper نوشته) یا خراب شده (چون session timeout و ephemeral nodeها ناپدید می‌شوند). با اشتراک اعلان، کلاینت از polling مکرر برای تغییر اجتناب می‌کند.

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

تخصیص کار به گره‌ها

یک مثال که مدل ZooKeeper/Chubby خوب کار می‌کند: چند نمونه از فرایند یا سرویس دارید و یکی باید leader یا primary انتخاب شود. اگر leader خراب شود، گره دیگر باید جایگزین شود. برای پایگاه داده single-leader مفید است، اما برای job scheduler و سیستم‌های stateful مشابه هم.

مثال دیگر: منبع پارتیشن‌شده (پایگاه داده، جریان پیام، ذخیره فایل، سیستم actor توزیع‌شده و غیره) دارید و باید تصمیم بگیرید کدام پارتیشن به کدام گره تخصیص یابد. با پیوستن گره‌های جدید به خوشه، برخی پارتیشن‌ها باید از گره‌های موجود به گره‌های جدید منتقل شوند تا بار متعادل شود (به «متعادل‌سازی مجدد پارتیشن‌ها» در صفحه ۲۰۹). با حذف یا خرابی گره‌ها، گره‌های دیگر باید کار گره‌های خراب را بگیرند.

این کارها با استفاده آگاهانه از عملیات اتمی، ephemeral node و اعلان در ZooKeeper قابل انجام است. اگر درست انجام شود، برنامه می‌تواند بدون مداخله انسان از خطا بازیابی شود. آسان نیست، با وجود کتابخانه‌هایی مثل Apache Curator [۱۷] که ابزار سطح بالاتر روی API کلاینت ZooKeeper می‌دهند — اما باز هم بهتر از پیاده‌سازی الگوریتم‌های اجماع لازم از صفر، که سابقه موفقیت ضعیفی دارد [۱۰۷].

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

معمولاً داده‌ای که ZooKeeper مدیریت می‌کند کند تغییر می‌کند: اطلاعاتی مثل «گره روی 10.1.1.23 leader پارتیشن ۷ است» که شاید در مقیاس دقیقه یا ساعت عوض شود. برای وضعیت runtime برنامه که شاید هزاران یا میلیون‌ها بار در ثانیه عوض شود نیست. اگر وضعیت برنامه باید بین گره‌ها رپلیک شود، ابزارهای دیگر (مثل Apache BookKeeper [۱۰۸]) به کار می‌روند.

کشف سرویس (service discovery)

ZooKeeper، etcd و Consul اغلب برای service discovery به کار می‌روند — یعنی پیدا کردن IP برای اتصال به سرویس خاص. در دیتاسنتر ابری، جایی که ماشین‌های مجازی مدام می‌آیند و می‌روند، اغلب IP سرویس‌ها را از قبل نمی‌دانید. در عوض سرویس‌ها را طوری پیکربندی می‌کنید که هنگام بالا آمدن endpoint شبکه‌شان را در service registry ثبت کنند تا سرویس‌های دیگر پیدا کنند.

با این حال، کمتر روشن است آیا service discovery واقعاً به اجماع نیاز دارد. DNS راه سنتی جستجوی IP برای نام سرویس است و با چند لایه cache عملکرد و دسترس‌پذیری خوب می‌دهد. خواندن از DNS اصلاً خطی‌پذیر نیست و معمولاً اگر نتیجه DNS کمی کهنه باشد مشکل نیست [۱۰۹]. مهم‌تر این است DNS قابل اعتماد و مقاوم به قطع شبکه باشد.

اگرچه service discovery به اجماع نیاز ندارد، انتخاب leader نیاز دارد. پس اگر سیستم اجماع شما از قبل می‌داند leader کیست، منطقی است آن اطلاعات را برای کمک به سرویس‌های دیگر برای کشف leader هم به کار ببرید. برای این منظور، برخی سیستم‌های اجماع رپلیکاهای cache فقط-خواندنی پشتیبانی می‌کنند. این رپلیکاها ناهمگام لاگ همه تصمیم‌های الگوریتم اجماع را می‌گیرند اما فعال در رأی شرکت نمی‌کنند. بنابراین می‌توانند درخواست‌های خواندن که خطی‌پذیری لازم ندارند را سرویس دهند.

سرویس‌های عضویت (membership services)

ZooKeeper و مشابه‌ها را می‌توان بخشی از تاریخچه طولانی پژوهش در سرویس‌های عضویت دید که به دهه ۱۹۸۰ برمی‌گردد و برای ساخت سیستم‌های بسیار قابل اعتماد، مثلاً کنترل ترافیک هوایی [۱۱۰]، مهم بوده است.

سرویس عضویت تعیین می‌کند کدام گره‌ها اکنون عضو فعال و زنده خوشه‌اند. همان‌طور که در فصل ۸ دیدیم، به‌خاطر تأخیر نامحدود شبکه نمی‌توان قابل اعتماد تشخیص داد گره دیگر خراب شده یا نه. اما اگر تشخیص خرابی را با اجماع ترکیب کنید، گره‌ها می‌توانند درباره اینکه کدام گره‌ها زنده و کدام به‌خاطر timeout session مرده تلقی شوند توافق کنند.

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

جمع‌بندی

در این فصل موضوعات سازگاری و اجماع را از زوایای مختلف بررسی کردیم. عمیقاً به خطی‌پذیری، مدل سازگاری رایج، نگاه کردیم: هدفش این است که داده رپلیک‌شده طوری به نظر برسد گویی فقط یک نسخه وجود دارد و همه عملیات روی آن اتمی‌اند. اگرچه خطی‌پذیری جذاب است چون فهم آسان است — پایگاه داده مثل متغیر در برنامه تک‌نخی — معایبش کندی است، به‌ویژه با تأخیر شبکه زیاد.

علیت را هم بررسی کردیم که بر رویدادهای سیستم ترتیب تحمیل می‌کند (چه قبل از چه، بر اساس علت و معلول). برخلاف خطی‌پذیری که همه عملیات را روی یک خط زمانی ترتیب کل می‌چیند، علیت مدل سازگاری ضعیف‌تر می‌دهد: برخی چیزها می‌توانند همزمان باشند، پس تاریخچه نسخه شبیه خط زمانی با شاخه و ادغام است. سازگاری علی سربار هماهنگی خطی‌پذیری را ندارد و به مشکلات شبکه خیلی کمتر حساس است. اما حتی اگر ترتیب علی را بگیریم (مثلاً با timestamp Lamport)، دیدیم برخی چیزها این‌طور پیاده نمی‌شوند: در «مرتب‌سازی timestamp کافی نیست» در صفحه ۳۴۷ مثال یکتایی نام کاربری و رد ثبت‌نام همزمان همان نام را دیدیم. اگر گرهی قرار است ثبت‌نام را بپذیرد، باید بداند گره دیگری همزمان همان نام را ثبت نمی‌کند. این مسئله ما را به سمت اجماع برد.

دیدیم دستیابی به اجماع یعنی تصمیم‌گیری طوری که همه گره‌ها درباره تصمیم توافق کنند و تصمیم غیرقابل برگشت باشد. با کمی کاوش، طیف وسیعی از مسائل در واقع به اجماع قابل تبدیل‌اند و معادل یکدیگرند (اگر برای یکی راه‌حل دارید، به‌راحتی به دیگری تبدیل می‌کنید). چنین مسائل معادلی شامل:

رجیسترهای compare-and-set خطی‌پذیر

رجیستر باید اتمی تصمیم بگیرد آیا مقدارش را تنظیم کند، بر اساس اینکه مقدار فعلی با پارامتر عملیات برابر است یا نه.

Commit اتمی تراکنش

پایگاه داده باید تصمیم بگیرد تراکنش توزیع‌شده commit یا abort شود.

پخش ترتیب کل

سیستم پیام باید ترتیب تحویل پیام‌ها را تعیین کند.

قفل‌ها و leaseها

وقتی چند کلاینت برای گرفتن قفل یا lease رقابت می‌کنند، قفل تعیین می‌کند کدام موفق شد.

سرویس عضویت/هماهنگی

با failure detector (مثلاً timeout)، سیستم باید تعیین کند کدام گره‌ها زنده‌اند و کدام به‌خاطر timeout session مرده‌اند.

قید یکتایی

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

همه این‌ها اگر فقط یک گره دارید یا تصمیم‌گیری را به یک گره واگذار کنید ساده‌اند. در پایگاه داده single-leader همه قدرت تصمیم به leader واگذار می‌شود؛ به همین دلیل چنین پایگاه‌هایی می‌توانند عملیات خطی‌پذیر، قید یکتایی، لاگ رپلیکاسیون کاملاً مرتب و بیشتر بدهند.

اما اگر آن leader واحد خراب شود یا قطع شبکه leader را unreachable کند، سیستم نمی‌تواند پیشرفت کند. سه راه برخورد:

1. منتظر بازیابی leader بمانید و بپذیرید سیستم در این مدت block شود. بسیاری coordinatorهای تراکنش XA/JTA این را انتخاب می‌کنند. این اجماع را کامل حل نمی‌کند چون خاتمه را برآورده نمی‌کند: اگر leader بازیابی نشود، سیستم برای همیشه block می‌ماند.
2. Failover دستی با انتخاب انسان leader جدید و پیکربندی مجدد سیستم. بسیاری پایگاه‌های داده رابطه‌ای این کار را می‌کنند. نوعی اجماع با «اقدام خدا» — اپراتور انسان، خارج از سیستم کامپیوتری، تصمیم می‌گیرد. سرعت failover به سرعت انسان محدود است که معمولاً از کامپیوتر کندتر است.
3. از الگوریتم برای انتخاب خودکار leader جدید استفاده کنید. این رویکرد به الگوریتم اجماع نیاز دارد و توصیه می‌شود از الگوریتم اثبات‌شده‌ای استفاده کنید که شرایط شبکه نامساعد را درست handle کند [۱۰۷].

اگرچه پایگاه داده single-leader می‌تواند بدون اجرای الگوریتم اجماع روی هر نوشتن خطی‌پذیری بدهد، هنوز برای نگه‌داشتن رهبری و تغییر رهبری به اجماع نیاز دارد. پس به نوعی داشتن leader فقط «مسئله را به جلو می‌اندازد»: اجماع هنوز لازم است، فقط جای دیگر و کمتر تکرار می‌شود. خبر خوب این است که الگوریتم‌ها و سیستم‌های تحمل‌پذیر خطا برای اجماع وجود دارند و در این فصل به‌اختصار بحث کردیم.

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

با این حال، هر سیستم لزوماً به اجماع نیاز ندارد: مثلاً سیستم‌های رپلیکاسیون leaderless و multi-leader معمولاً از اجماع سراسری استفاده نمی‌کنند. تعارض‌های این سیستم‌ها (به «مدیریت تعارض نوشتن» در صفحه ۱۷۱) نتیجه نبود اجماع بین leaderهای مختلف است، اما شاید قابل قبول باشد: شاید بدون خطی‌پذیری کنار بیاییم و با داده‌ای که تاریخچه نسخه شاخه و ادغام دارد بهتر کار کنیم.

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

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

منابع

[1] Peter Bailis and Ali Ghodsi: "Eventual Consistency Today: Limitations, Extensions, and Beyond," ACM Queue, volume 11, number 3, pages 55-63, March 2013. doi:10.1145/2460276.2462076

[2] Prince Mahajan, Lorenzo Alvisi, and Mike Dahlin: "Consistency, Availability, and Convergence," University of Texas at Austin, Department of Computer Science, Tech Report UTCS TR-11-22, May 2011.

[3] Alex Scotti: "Adventures in Building Your Own Database," at All Your Base, November 2015.

[4] Peter Bailis, Aaron Davidson, Alan Fekete, et al.: "Highly Available Transactions: Virtues and Limitations," at 40th International Conference on Very Large Data Bases (VLDB), September 2014. Extended version published as pre-print arXiv:1302.0309 [cs.DB].

[5] Paolo Viotti and Marko Vukolić: "Consistency in Non-Transactional Distributed Storage Systems," arXiv:1512.00168, 12 April 2016.

[6] Maurice P. Herlihy and Jeannette M. Wing: "Linearizability: A Correctness Condition for Concurrent Objects," ACM Transactions on Programming Languages and Systems (TOPLAS), volume 12, number 3, pages 463–492, July 1990. doi:10.1145/78969.78972

[7] Leslie Lamport: "On interprocess communication," Distributed Computing, volume 1, number 2, pages 77–101, June 1986. doi:10.1007/BF01786228

[8] David K. Gifford: "Information Storage in a Decentralized Computer System," Xerox Palo Alto Research Centers, CSL-81-8, June 1981.

[9] Martin Kleppmann: "Please Stop Calling Databases CP or AP," martin.kleppmann.com, May 11, 2015.

[10] Kyle Kingsbury: "Call Me Maybe: MongoDB Stale Reads," aphyr.com, April 20, 2015.

[11] Kyle Kingsbury: "Computational Techniques in Knossos," aphyr.com, May 17, 2014.

[12] Peter Bailis: "Linearizability Versus Serializability," bailis.org, September 24, 2014.

[13] Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987. ISBN: 978-0-201-10715-9, available online at research.microsoft.com.

[14] Mike Burrows: "The Chubby Lock Service for Loosely-Coupled Distributed Systems," at 7th USENIX Symposium on Operating System Design and Implementation (OSDI), November 2006.

[15] Flavio P. Junqueira and Benjamin Reed: ZooKeeper: Distributed Process Coordination. O'Reilly Media, 2013. ISBN: 978-1-449-36130-3

[16] "etcd 2.0.12 Documentation," CoreOS, Inc., 2015.

[17] "Apache Curator," Apache Software Foundation, curator.apache.org, 2015.

[18] Morali Vallath: Oracle 10g RAC Grid, Services & Clustering. Elsevier Digital Press, 2006. ISBN: 978-1-555-58321-7

[19] Peter Bailis, Alan Fekete, Michael J Franklin, et al.: "Coordination-Avoiding Database Systems," Proceedings of the VLDB Endowment, volume 8, number 3, pages 185–196, November 2014.

[20] Kyle Kingsbury: "Call Me Maybe: etcd and Consul," aphyr.com, June 9, 2014.

[21] Flavio P. Junqueira, Benjamin C. Reed, and Marco Serafini: "Zab: High-Performance Broadcast for Primary-Backup Systems," at 41st IEEE International Conference on Dependable Systems and Networks (DSN), June 2011. doi:10.1109/DSN.2011.5958223

[22] Diego Ongaro and John K. Ousterhout: "In Search of an Understandable Consensus Algorithm (Extended Version)," at USENIX Annual Technical Conference (ATC), June 2014.

[23] Hagit Attiya, Amotz Bar-Noy, and Danny Dolev: "Sharing Memory Robustly in Message-Passing Systems," Journal of the ACM, volume 42, number 1, pages 124–142, January 1995. doi:10.1145/200836.200869

[24] Nancy Lynch and Alex Shvartsman: "Robust Emulation of Shared Memory Using Dynamic Quorum-Acknowledged Broadcasts," at 27th Annual International Symposium on Fault-Tolerant Computing (FTCS), June 1997. doi:10.1109/FTCS.1997.614100

[25] Christian Cachin, Rachid Guerraoui, and Luís Rodrigues: Introduction to Reliable and Secure Distributed Programming, 2nd edition. Springer, 2011. ISBN: 978-3-642-15259-7, doi:10.1007/978-3-642-15260-3

[26] Sam Elliott, Mark Allen, and Martin Kleppmann: personal communication, thread on twitter.com, October 15, 2015.

[27] Niklas Ekström, Mikhail Panchenko, and Jonathan Ellis: "Possible Issue with Read Repair?," email thread on cassandra-dev mailing list, October 2012.

[28] Maurice P. Herlihy: "Wait-Free Synchronization," ACM Transactions on Programming Languages and Systems (TOPLAS), volume 13, number 1, pages 124–149, January 1991. doi:10.1145/114005.102808

[29] Armando Fox and Eric A. Brewer: "Harvest, Yield, and Scalable Tolerant Systems," at 7th Workshop on Hot Topics in Operating Systems (HotOS), March 1999. doi:10.1109/HOTOS.1999.798396

[30] Seth Gilbert and Nancy Lynch: "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services," ACM SIGACT News, volume 33, number 2, pages 51–59, June 2002. doi:10.1145/564585.564601

[31] Seth Gilbert and Nancy Lynch: "Perspectives on the CAP Theorem," IEEE Computer Magazine, volume 45, number 2, pages 30–36, February 2012. doi:10.1109/MC.2011.389

[32] Eric A. Brewer: "CAP Twelve Years Later: How the 'Rules' Have Changed," IEEE Computer Magazine, volume 45, number 2, pages 23–29, February 2012. doi:10.1109/MC.2012.37

[33] Susan B. Davidson, Hector Garcia-Molina, and Dale Skeen: "Consistency in Partitioned Networks," ACM Computing Surveys, volume 17, number 3, pages 341–370, September 1985. doi:10.1145/5505.5508

[34] Paul R. Johnson and Robert H. Thomas: "RFC 677: The Maintenance of Duplicate Databases," Network Working Group, January 27, 1975.

[35] Bruce G. Lindsay, Patricia Griffiths Selinger, C. Galtieri, et al.: "Notes on Distributed Databases," IBM Research, Research Report RJ2571(33471), July 1979.

[36] Michael J. Fischer and Alan Michael: "Sacrificing Serializability to Attain High Availability of Data in an Unreliable Network," at 1st ACM Symposium on Principles of Database Systems (PODS), March 1982. doi:10.1145/588111.588124

[37] Eric A. Brewer: "NoSQL: Past, Present, Future," at QCon San Francisco, November 2012.

[38] Henry Robinson: "CAP Confusion: Problems with 'Partition Tolerance,'" blog.cloudera.com, April 26, 2010.

[39] Adrian Cockcroft: "Migrating to Microservices," at QCon London, March 2014.

[40] Martin Kleppmann: "A Critique of the CAP Theorem," arXiv:1509.05393, September 17, 2015.

[41] Nancy A. Lynch: "A Hundred Impossibility Proofs for Distributed Computing," at 8th ACM Symposium on Principles of Distributed Computing (PODC), August 1989. doi:10.1145/72981.72982

[42] Hagit Attiya, Faith Ellen, and Adam Morrison: "Limitations of Highly-Available Eventually-Consistent Data Stores," at ACM Symposium on Principles of Distributed Computing (PODC), July 2015. doi:10.1145/2767386.2767419

[43] Peter Sewell, Susmit Sarkar, Scott Owens, et al.: "x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors," Communications of the ACM, volume 53, number 7, pages 89–97, July 2010. doi:10.1145/1785414.1785443

[44] Martin Thompson: "Memory Barriers/Fences," mechanical-sympathy.blogspot.co.uk, July 24, 2011.

[45] Ulrich Drepper: "What Every Programmer Should Know About Memory," akkadia.org, November 21, 2007.

[46] Daniel J. Abadi: "Consistency Tradeoffs in Modern Distributed Database System Design," IEEE Computer Magazine, volume 45, number 2, pages 37–42, February 2012. doi:10.1109/MC.2012.33

[47] Hagit Attiya and Jennifer L. Welch: "Sequential Consistency Versus Linearizability," ACM Transactions on Computer Systems (TOCS), volume 12, number 2, pages 91–122, May 1994. doi:10.1145/176575.176576

[48] Mustaque Ahamad, Gil Neiger, James E. Burns, et al.: "Causal Memory: Definitions, Implementation, and Programming," Distributed Computing, volume 9, number 1, pages 37–49, March 1995. doi:10.1007/BF01784241

[49] Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen: "Stronger Semantics for Low-Latency Geo-Replicated Storage," at 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI), April 2013.

[50] Marek Zawirski, Annette Bieniusa, Valter Balegas, et al.: "SwiftCloud: Fault-Tolerant Geo-Replication Integrated All the Way to the Client Machine," INRIA Research Report 8347, August 2013.

[51] Peter Bailis, Ali Ghodsi, Joseph M Hellerstein, and Ion Stoica: "Bolt-on Causal Consistency," at ACM International Conference on Management of Data (SIGMOD), June 2013.

[52] Philippe Ajoux, Nathan Bronson, Sanjeev Kumar, et al.: "Challenges to Adopting Stronger Consistency at Scale," at 15th USENIX Workshop on Hot Topics in Operating Systems (HotOS), May 2015.

[53] Peter Bailis: "Causality Is Expensive (and What to Do About It)," bailis.org, February 5, 2014.

[54] Ricardo Gonçalves, Paulo Sérgio Almeida, Carlos Baquero, and Victor Fonte: "Concise Server-Wide Causality Management for Eventually Consistent Data Stores," at 15th IFIP International Conference on Distributed Applications and Interoperable Systems (DAIS), June 2015. doi:10.1007/978-3-319-19129-4_6

[55] Rob Conery: "A Better ID Generator for PostgreSQL," rob.conery.io, May 29, 2014.

[56] Leslie Lamport: "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, volume 21, number 7, pages 558–565, July 1978. doi:10.1145/359545.359563

[57] Xavier Défago, André Schiper, and Péter Urbán: "Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey," ACM Computing Surveys, volume 36, number 4, pages 372–421, December 2004. doi:10.1145/1041680.1041682

[58] Hagit Attiya and Jennifer Welch: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edition. John Wiley & Sons, 2004. ISBN: 978-0-471-45324-6, doi:10.1002/0471478210

[59] Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, et al.: "CORFU: A Shared Log Design for Flash Clusters," at 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI), April 2012.

[60] Fred B. Schneider: "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial," ACM Computing Surveys, volume 22, number 4, pages 299–319, December 1990.

[61] Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, et al.: "Calvin: Fast Distributed Transactions for Partitioned Database Systems," at ACM International Conference on Management of Data (SIGMOD), May 2012.

[62] Mahesh Balakrishnan, Dahlia Malkhi, Ted Wobber, et al.: "Tango: Distributed Data Structures over a Shared Log," at 24th ACM Symposium on Operating Systems Principles (SOSP), November 2013. doi:10.1145/2517349.2522732

[63] Robbert van Renesse and Fred B. Schneider: "Chain Replication for Supporting High Throughput and Availability," at 6th USENIX Symposium on Operating System Design and Implementation (OSDI), December 2004.

[64] Leslie Lamport: "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs," IEEE Transactions on Computers, volume 28, number 9, pages 690–691, September 1979. doi:10.1109/TC.1979.1675439

[65] Enis Söztutar, Devaraj Das, and Carter Shanklin: "Apache HBase High Availability at the Next Level," hortonworks.com, January 22, 2015.

[66] Brian F Cooper, Raghu Ramakrishnan, Utkarsh Srivastava, et al.: "PNUTS: Yahoo!'s Hosted Data Serving Platform," at 34th International Conference on Very Large Data Bases (VLDB), August 2008. doi:10.14778/1454159.1454167

[67] Tushar Deepak Chandra and Sam Toueg: "Unreliable Failure Detectors for Reliable Distributed Systems," Journal of the ACM, volume 43, number 2, pages 225–267, March 1996. doi:10.1145/226643.226647

[68] Michael J. Fischer, Nancy Lynch, and Michael S. Paterson: "Impossibility of Distributed Consensus with One Faulty Process," Journal of the ACM, volume 32, number 2, pages 374–382, April 1985. doi:10.1145/3149.214121

[69] Michael Ben-Or: "Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols," at 2nd ACM Symposium on Principles of Distributed Computing (PODC), August 1983. doi:10.1145/800221.806707

[70] Jim N. Gray and Leslie Lamport: "Consensus on Transaction Commit," ACM Transactions on Database Systems (TODS), volume 31, number 1, pages 133–160, March 2006. doi:10.1145/1132863.1132867

[71] Rachid Guerraoui: "Revisiting the Relationship Between Non-Blocking Atomic Commitment and Consensus," at 9th International Workshop on Distributed Algorithms (WDAG), September 1995. doi:10.1007/BFb0022140

[72] Thanumalayan Sankaranarayana Pillai, Vijay Chidambaram, Ramnatthan Alagappan, et al.: "All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications," at 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI), October 2014.

[73] Jim Gray: "The Transaction Concept: Virtues and Limitations," at 7th International Conference on Very Large Data Bases (VLDB), September 1981.

[74] Hector Garcia-Molina and Kenneth Salem: "Sagas," at ACM International Conference on Management of Data (SIGMOD), May 1987. doi:10.1145/38713.38742

[75] C. Mohan, Bruce G. Lindsay, and Ron Obermarck: "Transaction Management in the R* Distributed Database Management System," ACM Transactions on Database Systems, volume 11, number 4, pages 378–396, December 1986. doi:10.1145/7239.7266

[76] "Distributed Transaction Processing: The XA Specification," X/Open Company Ltd., Technical Standard XO/CAE/91/300, December 1991. ISBN: 978-1-872-63024-3

[77] Mike Spille: "XA Exposed, Part II," jroller.com, April 3, 2004.

[78] Ivan Silva Neto and Francisco Reverbel: "Lessons Learned from Implementing WS-Coordination and WS-AtomicTransaction," at 7th IEEE/ACIS International Conference on Computer and Information Science (ICIS), May 2008. doi:10.1109/ICIS.2008.75

[79] James E. Johnson, David E. Langworthy, Leslie Lamport, and Friedrich H. Vogt: "Formal Specification of a Web Services Protocol," at 1st International Workshop on Web Services and Formal Methods (WS-FM), February 2004. doi:10.1016/j.entcs.2004.02.022

[80] Dale Skeen: "Nonblocking Commit Protocols," at ACM International Conference on Management of Data (SIGMOD), April 1981. doi:10.1145/582318.582339

[81] Gregor Hohpe: "Your Coffee Shop Doesn't Use Two-Phase Commit," IEEE Software, volume 22, number 2, pages 64–66, March 2005. doi:10.1109/MS.2005.52

[82] Pat Helland: "Life Beyond Distributed Transactions: An Apostate's Opinion," at 3rd Biennial Conference on Innovative Data Systems Research (CIDR), January 2007.

[83] Jonathan Oliver: "My Beef with MSDTC and Two-Phase Commits," blog.jonathanoliver.com, April 4, 2011.

[84] Oren Eini (Ahende Rahien): "The Fallacy of Distributed Transactions," ayende.com, July 17, 2014.

[85] Clemens Vasters: "Transactions in Windows Azure (with Service Bus) – An Email Discussion," vasters.com, July 30, 2012.

[86] "Understanding Transactionality in Azure," NServiceBus Documentation, Particular Software, 2015.

[87] Randy Wigginton, Ryan Lowe, Marcos Albe, and Fernando Ipar: "Distributed Transactions in MySQL," at MySQL Conference and Expo, April 2013.

[88] Mike Spille: "XA Exposed, Part I," jroller.com, April 3, 2004.

[89] Ajmer Dhariwal: "Orphaned MSDTC Transactions (-2 spids)," eraofdata.com, December 12, 2008.

[90] Paul Randal: "Real World Story of DBCC PAGE Saving the Day," sqlskills.com, June 19, 2013.

[91] "in-doubt xact resolution Server Configuration Option," SQL Server 2016 documentation, Microsoft, Inc., 2016.

[92] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer: "Consensus in the Presence of Partial Synchrony," Journal of the ACM, volume 35, number 2, pages 288–323, April 1988. doi:10.1145/42282.42283

[93] Miguel Castro and Barbara H. Liskov: "Practical Byzantine Fault Tolerance and Proactive Recovery," ACM Transactions on Computer Systems, volume 20, number 4, pages 396–461, November 2002. doi:10.1145/571637.571640

[94] Brian M. Oki and Barbara H. Liskov: "Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems," at 7th ACM Symposium on Principles of Distributed Computing (PODC), August 1988. doi:10.1145/62546.62549

[95] Barbara H. Liskov and James Cowling: "Viewstamped Replication Revisited," Massachusetts Institute of Technology, Tech Report MIT-CSAIL-TR-2012-021, July 2012.

[96] Leslie Lamport: "The Part-Time Parliament," ACM Transactions on Computer Systems, volume 16, number 2, pages 133–169, May 1998. doi:10.1145/279227.279229

[97] Leslie Lamport: "Paxos Made Simple," ACM SIGACT News, volume 32, number 4, pages 51–58, December 2001.

[98] Tushar Deepak Chandra, Robert Griesemer, and Joshua Redstone: "Paxos Made Live – An Engineering Perspective," at 26th ACM Symposium on Principles of Distributed Computing (PODC), June 2007.

[99] Robbert van Renesse: "Paxos Made Moderately Complex," cs.cornell.edu, March 2011.

[100] Diego Ongaro: "Consensus: Bridging Theory and Practice," PhD Thesis, Stanford University, August 2014.

[101] Heidi Howard, Malte Schwarzkopf, Anil Madhavapeddy, and Jon Crowcroft: "Raft Refloated: Do We Have Consensus?," ACM SIGOPS Operating Systems Review, volume 49, number 1, pages 12–21, January 2015. doi:10.1145/2723872.2723876

[102] André Medeiros: "ZooKeeper's Atomic Broadcast Protocol: Theory and Practice," Aalto University School of Science, March 20, 2012.

[103] Robbert van Renesse, Nicolas Schiper, and Fred B. Schneider: "Vive La Différence: Paxos vs. Viewstamped Replication vs. Zab," IEEE Transactions on Dependable and Secure Computing, volume 12, number 4, pages 472–484, September 2014. doi:10.1109/TDSC.2014.2355848

[104] Will Portnoy: "Lessons Learned from Implementing Paxos," blog.willportnoy.com, June 14, 2012.

[105] Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman: "Flexible Paxos: Quorum Intersection Revisited," arXiv:1608.06696, August 24, 2016.

[106] Heidi Howard and Jon Crowcroft: "Coracle: Evaluating Consensus at the Internet Edge," at Annual Conference of the ACM Special Interest Group on Data Communication (SIGCOMM), August 2015. doi:10.1145/2829988.2790010

[107] Kyle Kingsbury: "Call Me Maybe: Elasticsearch 1.5.0," aphyr.com, April 27, 2015.

[108] Ivan Kelly: "BookKeeper Tutorial," github.com, October 2014.

[109] Camille Fournier: "Consensus Systems for the Skeptical Architect," at Craft Conference, Budapest, Hungary, April 2015.

[110] Kenneth P. Birman: "A History of the Virtual Synchrony Replication Model," in Replication: Theory and Practice, Springer LNCS volume 5959, chapter 6, pages 91–120, 2010. ISBN: 978-3-642-11293-5, doi:10.1007/978-3-642-11294-2_6

---

بخش سوم — داده مشتق

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

در واقعیت، سیستم‌های داده اغلب پیچیده‌ترند. در برنامه بزرگ اغلب باید به روش‌های مختلف به داده دسترسی و پردازش کنید و هیچ پایگاه داده‌ای نمی‌تواند همزمان همه نیازهای مختلف را برآورده کند. برنامه‌ها پس معمولاً ترکیبی از چند datastore، ایندکس، cache، سیستم تحلیل و غیره به کار می‌برند و مکانیزم جابه‌جایی داده بین storeها را پیاده می‌کنند.

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

سیستم‌های رکورد و داده مشتق

در سطح بالا، سیستم‌های ذخیره و پردازش داده را می‌توان به دو دسته گسترده تقسیم کرد:

سیستم‌های رکورد (systems of record)

سیستم رکورد، که منبع حقیقت (source of truth) هم نامیده می‌شود، نسخه معتبر داده شما را نگه می‌دارد. وقتی داده جدید می‌آید، مثلاً به‌عنوان ورودی کاربر، اول اینجا نوشته می‌شود. هر واقعیت دقیقاً یک‌بار نمایش داده می‌شود (نمایش معمولاً نرمال‌شده است). اگر بین سیستم دیگر و سیستم رکورد اختلاف باشد، مقدار سیستم رکورد (تعریفاً) درست است.

سیستم‌های داده مشتق (derived data systems)

داده در سیستم مشتق نتیجه گرفتن داده موجود از سیستم دیگر و تبدیل یا پردازش آن است. اگر داده مشتق را از دست بدهید، می‌توانید از منبع اصلی دوباره بسازید. مثال کلاسیک cache است: اگر در cache باشد از آن سرویس می‌دهید، وگرنه به پایگاه داده زیرین برمی‌گردید. مقادیر denormalize‌شده، ایندکس‌ها و viewهای materialize‌شده هم در این دسته‌اند. در سیستم‌های توصیه، داده خلاصه پیش‌بینی‌شده اغلب از لاگ استفاده مشتق می‌شود.

از نظر فنی، داده مشتق افزون است چون اطلاعات موجود را تکرار می‌کند. اما اغلب برای عملکرد خوب queryهای خواندن ضروری است. معمولاً denormalize است. می‌توانید چند مجموعه داده مختلف از یک منبع مشتق کنید و داده را از «دیدگاه‌های» مختلف ببینید.

همه سیستم‌ها در معماری‌شان بین سیستم رکورد و داده مشتق تمایز روشن نمی‌گذارند، اما تمایز بسیار مفید است چون جریان داده در سیستم را روشن می‌کند: کدام بخش‌ها چه ورودی و خروجی دارند و چگونه به هم وابسته‌اند.

بیشتر پایگاه‌های داده، موتورهای ذخیره‌سازی و زبان‌های query ذاتاً سیستم رکورد یا مشتق نیستند. پایگاه داده فقط ابزار است؛ نحوه استفاده به شما بستگی دارد. تمایز بین سیستم رکورد و داده مشتق به ابزار نیست، به نحوه استفاده در برنامه بستگی دارد.

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

مرور فصل‌ها

در فصل ۱۰ با سیستم‌های جریان داده batch-oriented مثل MapReduce شروع می‌کنیم و می‌بینیم چه ابزارها و اصولی برای ساخت سیستم‌های داده بزرگ می‌دهند. در فصل ۱۱ همان ایده‌ها را به جریان داده (data stream) اعمال می‌کنیم تا کارهای مشابه با تأخیر کمتر انجام دهیم. فصل ۱۲ کتاب را با ایده‌هایی درباره ساخت برنامه‌های قابل اعتماد، مقیاس‌پذیر و قابل نگهداری در آینده جمع‌بندی می‌کند.