فصل ۸ — دردسر سیستم‌های توزیع‌شده

Hey I just met you The network's laggy But here's my data So store it maybe — Kyle Kingsbury، Carly Rae Jepsen and the Perils of Network Partitions (۲۰۱۳)

موضوعی تکرارشونده در چند فصل اخیر این بوده که سیستم‌ها چگونه با بروز مشکل برخورد می‌کنند. مثلاً درباره failover رپلیکا («مدیریت خرابی گره‌ها» در صفحه ۱۵۶)، تأخیر رپلیکاسیون («مشکلات تأخیر رپلیکاسیون» در صفحه ۱۶۱)، و کنترل همزمانی برای تراکنش‌ها («سطوح ایزولاسیون ضعیف» در صفحه ۲۳۳) بحث کردیم. با درک بهتر حالت‌های مرزی که در سیستم‌های واقعی ممکن است رخ دهند، در مدیریت آن‌ها ماهرتر می‌شویم.

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

کار با سیستم‌های توزیع‌شده اساساً با نوشتن نرم‌افزار روی یک رایانه تکی متفاوت است — و تفاوت اصلی این است که راه‌های جدید و هیجان‌انگیز زیادی برای خراب شدن چیزها وجود دارد [۱، ۲]. در این فصل، طعم مشکلاتی را که در عمل پیش می‌آیند می‌چشیم و درک می‌کنیم به چه چیزهایی می‌توانیم تکیه کنیم و به چه چیزهایی نمی‌توانیم.

i. با یک استثنا: فرض می‌کنیم خطاها غیربیزانسی هستند (به «خطاهای بیزانسی» در صفحه ۳۰۴ مراجعه کنید).

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

این فصل مروری کاملاً بدبینانه و دل‌گیر از چیزهایی است که ممکن است در سیستم توزیع‌شده خراب شوند. به مشکلات شبکه («شبکه‌های غیرقابل اعتماد» در صفحه ۲۷۷)، ساعت‌ها و مسائل زمان‌بندی («ساعت‌های غیرقابل اعتماد» در صفحه ۲۸۷) می‌پردازیم؛ و بررسی می‌کنیم تا چه حد قابل اجتناب‌اند. پیامدهای همه این مسائل گیج‌کننده است، بنابراین بررسی می‌کنیم چگونه درباره وضعیت سیستم توزیع‌شده فکر کنیم و چگونه درباره اتفاقاتی که افتاده است استدلال کنیم («دانش، حقیقت و دروغ» در صفحه ۳۰۰).

خطاها و خرابی‌های جزئی

وقتی روی یک رایانه تکی برنامه می‌نویسید، معمولاً رفتار نسبتاً قابل پیش‌بینی دارد: یا کار می‌کند یا نمی‌کند. نرم‌افزار باگ‌دار ممکن است بدهد رایانه گاهی «روز بدی دارد» (مشکلی که اغلب با reboot حل می‌شود)، اما این بیشتر نتیجه نرم‌افزار بدنوشته است.

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

این انتخاب عمدی در طراحی رایانه‌هاست: اگر خطای داخلی رخ دهد، ترجیح می‌دهیم رایانه کاملاً crash کند تا نتیجه اشتباه برگرداند، چون نتایج اشتباه برخورد با آن‌ها دشوار و گیج‌کننده است. بنابراین رایانه‌ها واقعیت فیزیکی مبهم زیربنای خود را پنهان می‌کنند و مدل سیستم ایده‌آلی ارائه می‌دهند که با کمال ریاضی کار می‌کند. دستور CPU همیشه یک کار را می‌کند؛ اگر داده‌ای در حافظه یا دیسک بنویسید، سالم می‌ماند و تصادفی خراب نمی‌شود. این هدف طراحی محاسبه همیشه درست، تا اولین رایانه دیجیتال برمی‌گردد [۳].

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

در تجربه محدودم با پارتیشن‌های شبکه طولانی‌مدت در یک دیتاسنتر (DC)، خرابی PDU [واحد توزیع برق]، خرابی سوئیچ، قطع برق تصادفی کل رک‌ها، خرابی backbone کل DC، قطع برق کل DC، و راننده‌ای با قند خون پایین که وانت Fordش را به سیستم HVAC [گرمایش، تهویه و تهویه مطبوع] DC کوبیده بود، برخورد کرده‌ام. و من حتی اپراتور هم نیستم. — Coda Hale

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

این غیرقطعیت و امکان خرابی جزئی، کار با سیستم‌های توزیع‌شده را دشوار می‌کند [۵].

رایانش ابری و ابررایانه

طیفی از فلسفه‌ها برای ساخت سیستم‌های محاسباتی بزرگ وجود دارد:

• در یک سر طیف، حوزه رایانش با کارایی بالا (HPC) است. ابررایانه‌ها با هزاران CPU معمولاً برای کارهای محاسباتی علمی سنگین، مثل پیش‌بینی آب‌وهوا یا دینامیک مولکولی (شبیه‌سازی حرکت اتم‌ها و مولکول‌ها) به کار می‌روند.
• در سر دیگر، رایانش ابری (cloud computing) تعریف روشنی ندارد [۶] اما اغلب با دیتاسنترهای چندمستأجره، رایانه‌های کالایی متصل با شبکه IP (اغلب Ethernet)، تخصیص منابع الاستیک/برحسب تقاضا، و صورتحساب اندازه‌گیری‌شده مرتبط است.
• دیتاسنترهای سنتی سازمانی جایی بین این دو قرار دارند.

با این فلسفه‌ها، رویکردهای بسیار متفاوتی برای مدیریت خطا می‌آید. در ابررایانه، یک job معمولاً گاه‌به‌گاه وضعیت محاسبه را در ذخیره‌سازی پایدار checkpoint می‌کند. اگر یک گره خراب شود، راه‌حل رایج این است که کل بار کاری خوشه را متوقف کنید. پس از تعمیر گره معیوب، محاسبه از آخرین checkpoint از سر گرفته می‌شود [۷، ۸]. بنابراین ابررایانه بیشتر شبیه رایانه تکی است تا سیستم توزیع‌شده: با اجازه دادن به تشدید خرابی جزئی به خرابی کامل برخورد می‌کند — اگر هر بخشی خراب شود، همه چیز را crash بگذارید (مثل kernel panic روی یک ماشین).

در این کتاب روی سیستم‌های پیاده‌سازی سرویس‌های اینترنتی تمرکز داریم که معمولاً با ابررایانه‌ها بسیار متفاوت‌اند:

• بسیاری از برنامه‌های مرتبط با اینترنت آنلاین‌اند، یعنی باید هر زمان با تأخیر کم به کاربران سرویس دهند. غیرقابل‌دسترس کردن سرویس — مثلاً توقف خوشه برای تعمیر — قابل قبول نیست. در مقابل، jobهای آفلاین (دسته‌ای) مثل شبیه‌سازی آب‌وهوا را می‌توان با تأثیر نسبتاً کم متوقف و از سر گرفت.
• ابررایانه‌ها معمولاً از سخت‌افزار تخصصی ساخته می‌شوند که هر گره نسبتاً قابل اعتماد است و گره‌ها از طریق حافظه مشترک و remote direct memory access (RDMA) ارتباط برقرار می‌کنند. در مقابل، گره‌های سرویس ابری از ماشین‌های کالایی ساخته می‌شوند که به‌خاطر صرفه‌جویی مقیاس عملکرد معادل با هزینه کمتر می‌دهند، اما نرخ خرابی بالاتری هم دارند.
• شبکه‌های بزرگ دیتاسنتر اغلب بر پایه IP و Ethernet و توپولوژی Clos برای پهنای باند bisection بالا هستند [۹]. ابررایانه‌ها اغلب توپولوژی‌های شبکه تخصصی مثل مش‌های چندبعدی و torus [۱۰] دارند که برای بارهای HPC با الگوهای ارتباطی شناخته‌شده عملکرد بهتری می‌دهند.
• هرچه سیستم بزرگ‌تر شود، احتمال خراب بودن یکی از اجزا بیشتر است. با گذشت زمان، چیزهای خراب تعمیر و چیزهای جدید خراب می‌شوند، اما در سیستمی با هزاران گره، منطقی است فرض کنیم همیشه چیزی خراب است [۷]. وقتی استراتژی مدیریت خطا فقط تسلیم شدن است، سیستم بزرگ ممکن است بخش زیادی از وقتش را صرف بازیابی از خطا کند نه کار مفید [۸].
• اگر سیستم بتواند گره‌های خراب را تحمل کند و همچنان به‌عنوان کل کار کند، برای عملیات و نگهداری بسیار مفید است: مثلاً می‌توانید به‌روزرسانی تدریجی (rolling upgrade؛ فصل ۴) انجام دهید و یک گره را در هر بار restart کنید، در حالی که سرویس بدون وقفه به کاربران سرویس می‌دهد. در محیط ابری، اگر یک ماشین مجازی خوب کار نمی‌کند، می‌توانید آن را kill کنید و یکی جدید بخواهید (امیدوارید جدید سریع‌تر باشد).
• در استقرار جغرافیایی توزیع‌شده (نگه‌داشتن داده نزدیک کاربران برای کاهش تأخیر دسترسی)، ارتباط احتمالاً از اینترنت می‌گذرد که نسبت به شبکه‌های محلی کند و غیرقابل اعتماد است. ابررایانه‌ها معمولاً فرض می‌کنند همه گره‌ها نزدیک هم‌اند.

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

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

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

ساخت سیستم قابل اعتماد از اجزای غیرقابل اعتماد

شاید بپرسید آیا این منطقی است — شهوداً به نظر می‌رسد سیستم فقط به اندازه کم‌قابل‌اعتمادترین جزءش (ضعیف‌ترین حلقه) قابل اعتماد است. اینطور نیست: در واقع ایده قدیمی در رایانش است که سیستم قابل‌اعتمادتر از پایه کم‌قابل‌اعتمادتر بسازیم [۱۱]. مثلاً:

• کدهای تصحیح خطا اجازه می‌دهند داده دیجیتال با دقت روی کانال ارتباطی که گاهی بیت‌ها را اشتباه می‌کند منتقل شود، مثلاً به‌خاطر تداخل رادیویی در شبکه بی‌سیم [۱۲].
• IP (پروتکل اینترنت) غیرقابل اعتماد است: ممکن است بسته‌ها را drop، تأخیر، تکرار یا مرتب‌سازی مجدد کند. TCP (پروتکل کنترل انتقال) لایه انتقال قابل‌اعتمادتر روی IP فراهم می‌کند: اطمینان می‌دهد بسته‌های گم‌شده دوباره ارسال، تکراری‌ها حذف و بسته‌ها به ترتیب ارسال مونتاژ شوند.

اگرچه سیستم می‌تواند قابل‌اعتمادتر از اجزای زیرینش باشد، همیشه حدی برای میزان قابلیت اطمینان بیشتر وجود دارد. مثلاً کدهای تصحیح خطا با تعداد کمی خطای تک‌بیتی برخورد می‌کنند، اما اگر سیگنال زیر تداخل غرق شود، محدودیت بنیادی برای مقدار داده‌ای که از کانال ارتباطی عبور می‌دهد وجود دارد [۱۳]. TCP می‌تواند از دست رفتن، تکرار و مرتب‌سازی مجدد بسته را از شما پنهان کند، اما نمی‌تواند تأخیرهای شبکه را جادویی حذف کند.

اگرچه سیستم سطح بالاتر قابل‌اعتمادتر کامل نیست، باز هم مفید است چون برخی خطاهای سطح پایین پیچیده را مدیریت می‌کند و خطاهای باقی‌مانده معمولاً استدلال و برخورد با آن‌ها آسان‌تر است. این موضوع را در «استدلال end-to-end» در صفحه ۵۱۹ بیشتر بررسی می‌کنیم.

شبکه‌های غیرقابل اعتماد

همان‌طور که در مقدمه بخش دوم بحث شد، سیستم‌های توزیع‌شده‌ای که در این کتاب بررسی می‌کنیم سیستم‌های shared-nothing هستند: یعنی دسته‌ای ماشین متصل به شبکه. شبکه تنها راه ارتباط آن ماشین‌هاست — فرض می‌کنیم هر ماشین حافظه و دیسک خود را دارد و یک ماشین نمی‌تواند به حافظه یا دیسک ماشین دیگر دسترسی داشته باشد (مگر با درخواست به سرویس از طریق شبکه).

shared-nothing تنها روش ساخت سیستم نیست، اما به رویکرد غالب برای سرویس‌های اینترنتی تبدیل شده، به چند دلیل: نسبتاً ارزان است چون سخت‌افزار خاص لازم ندارد، از سرویس‌های ابری کالایی استفاده می‌کند، و با افزونگی در چند دیتاسنتر جغرافیایی توزیع‌شده قابلیت اطمینان بالا می‌دهد.

اینترنت و بیشتر شبکه‌های داخلی دیتاسنترها (اغلب Ethernet) شبکه‌های بسته‌ای ناهمگام‌اند. در این نوع شبکه، یک گره می‌تواند پیام (بسته) به گره دیگر بفرستد، اما شبکه تضمینی درباره زمان رسیدن یا رسیدن اصلاً نمی‌دهد. اگر درخواست بفرستید و پاسخ انتظار دارید، چیزهای زیادی ممکن است خراب شود (برخی در شکل ۸-۱ نشان داده شده):

1. درخواست شما ممکن است گم شده باشد (شاید کسی کابل شبکه را کشیده).
2. درخواست شما ممکن است در صف باشد و بعداً تحویل شود (شاید شبکه یا گیرنده overload شده).
3. گره راه‌دور ممکن است خراب شده باشد (شاید crash کرده یا خاموش شده).
4. گره راه‌دور ممکن است موقتاً پاسخ ندهد (شاید pause طولانی garbage collection دارد؛ «مکث‌های فرآیند» در صفحه ۲۹۵)، اما بعداً دوباره پاسخ دهد.
5. گره راه‌دور ممکن است درخواست را پردازش کرده باشد، اما پاسخ در شبکه گم شده (شاید سوئیچ شبکه misconfigure شده).
6. گره راه‌دور ممکن است درخواست را پردازش کرده باشد، اما پاسخ تأخیر یافته و بعداً تحویل شود (شاید شبکه یا ماشین شما overload شده).

شکل ۸-۱. اگر درخواست بفرستید و پاسخ نگیرید، نمی‌توان بین (الف) گم شدن درخواست، (ب) down بودن گره راه‌دور، یا (ج) گم شدن پاسخ تمایز قائل شد.

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

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

خطاهای شبکه در عمل

دهه‌هاست شبکه‌های رایانه‌ای می‌سازیم — شاید امیدوار باشیم تا حالا قابل اعتمادشان کرده باشیم. اما به نظر می‌رسد هنوز موفق نشده‌ایم.

مطالعات سیستماتیک و شواهد تجربی زیاد نشان می‌دهند مشکلات شبکه شگفت‌انگیزانه رایج‌اند، حتی در محیط‌های کنترل‌شده مثل دیتاسنتر تحت مدیریت یک شرکت [۱۴]. یک مطالعه در دیتاسنتر متوسط حدود ۱۲ خطای شبکه در ماه یافت که نیمی یک ماشین و نیمی کل رک را قطع می‌کرد [۱۵]. مطالعه دیگری نرخ خرابی اجزایی مثل سوئیچ‌های top-of-rack، aggregation و load balancer را اندازه گرفت [۱۶] و یافت افزودن تجهیزات شبکه افزونگی به اندازه امید، خطا را کاهش نمی‌دهد، چون در برابر خطای انسانی (مثلاً misconfigure سوئیچ) که علت عمده outage است محافظت نمی‌کند.

سرویس‌های ابری عمومی مثل EC2 به خاطر glitchهای گذرای شبکه مکرر بدنام‌اند [۱۴]، و شبکه‌های خصوصی خوب‌مدیریت‌شده پایدارترند. با این حال هیچ‌کس مصون نیست: مثلاً مشکل در به‌روزرسانی نرم‌افزار سوئیچ می‌تواند بازپیکربندی توپولوژی شبکه را تحریک کند که در آن بسته‌ها بیش از یک دقیقه تأخیر یابند [۱۷]. کوسه‌ها ممکن است کابل‌های زیردریایی را گاز بگیرند و آسیب بزنند [۱۸]. خطاهای شگفت‌انگیز دیگر شامل رابط شبکه‌ای است که گاهی همه بسته‌های ورودی را drop می‌کند اما خروجی را موفق می‌فرستد [۱۹]: فقط به‌خاطر کار کردن لینک در یک جهت، کار کردن در جهت مخالف تضمین نمی‌شود.

پارتیشن‌های شبکه

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

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

اگر مدیریت خطای شبکه تعریف و تست نشود، چیزهای بد دلخواه ممکن است رخ دهد: مثلاً خوشه deadlock شود و برای همیشه نتواند درخواست سرویس دهد، حتی وقتی شبکه بازیابی شود [۲۰]، یا حتی همه داده‌ها را حذف کند [۲۱]. اگر نرم‌افزار در موقعیت غیرمنتظره قرار گیرد، ممکن است کارهای غیرمنتظره دلخواه انجام دهد.

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

تشخیص خطا

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

• load balancer باید درخواست به گره مرده نفرستد (از چرخش خارج کند).
• در پایگاه داده توزیع‌شده با رپلیکاسیون single-leader، اگر leader خراب شود، یکی از followerها باید leader جدید شود («مدیریت خرابی گره‌ها» در صفحه ۱۵۶).

متأسفانه عدم قطعیت درباره شبکه تشخیص اینکه گره کار می‌کند یا نه را دشوار می‌کند. در شرایط خاص ممکن است بازخوردی صریح بگیرید که چیزی کار نمی‌کند:

• اگر به ماشینی که گره باید روی آن باشد دسترسی دارید اما هیچ فرآیندی روی پورت مقصد گوش نمی‌دهد (مثلاً چون crash کرده)، سیستم‌عامل با ارسال بسته RST یا FIN اتصال TCP را می‌بندد یا رد می‌کند. اما اگر گره در حین پردازش درخواست crash کرده، نمی‌دانید چقدر داده واقعاً پردازش شده [۲۲].
• اگر فرآیند گره crash کرده (یا توسط مدیر kill شده) اما سیستم‌عامل گره هنوز کار می‌کند، اسکریپتی می‌تواند گره‌های دیگر را از crash مطلع کند تا گره دیگر بدون انتظار timeout سریع جایگزین شود. مثلاً HBase این کار را می‌کند [۲۳].
• اگر به رابط مدیریت سوئیچ‌های شبکه دیتاسنتر دسترسی دارید، می‌توانید آن‌ها را query کنید تا خرابی لینک در سطح سخت‌افزار تشخیص دهید (مثلاً اگر ماشین راه‌دور خاموش است). این گزینه اگر از اینترنت وصل شوید، یا دیتاسنتر مشترک بدون دسترسی به سوئیچ‌ها، یا به‌خاطر مشکل شبکه به رابط مدیریت نرسید، حذف می‌شود.
• اگر router مطمئن باشد IP مقصد unreachable است، ممکن است با بسته ICMP Destination Unreachable پاسخ دهد. اما router هم قابلیت تشخیص جادویی خطا ندارد — همان محدودیت‌های سایر شرکت‌کنندگان شبکه را دارد.

بازخورد سریع درباره down بودن گره راه‌دور مفید است، اما نمی‌توان به آن تکیه کرد. حتی اگر TCP تأیید کند بسته تحویل شده، برنامه ممکن است قبل از پردازش crash کرده باشد. اگر مطمئن شوید درخواست موفق بوده، به پاسخ مثبت خود برنامه نیاز دارید [۲۴].

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

timeoutها و تأخیرهای نامحدود

اگر timeout تنها راه مطمئن تشخیص خطاست، timeout چقدر باید باشد؟ متأسفانه پاسخ ساده‌ای نیست.

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

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

وقتی گره مرده اعلام می‌شود، مسئولیت‌هایش باید به گره‌های دیگر منتقل شود که بار اضافی روی آن‌ها و شبکه می‌گذارد. اگر سیستم از قبل تحت بار بالا باشد، اعلام زودهنگام مرگ گره‌ها ممکن است وضعیت را بدتر کند. ممکن است گره واقعاً مرده نبوده بلکه فقط به‌خاطر overload کند پاسخ داده — انتقال بارش به گره‌های دیگر می‌تواند خرابی آبشاری (cascading failure) ایجاد کند (در حد افراط، همه گره‌ها یکدیگر را مرده اعلام کنند و همه چیز متوقف شود).

سیستم فرضی با شبکه‌ای که حداکثر تأخیر برای بسته‌ها تضمین می‌کند — هر بسته یا در زمان d تحویل می‌شود یا گم می‌شود، اما تحویل هرگز بیش از d طول نمی‌کشد — و فرض کنید گره غیرخراب همیشه درخواست را در زمان r پردازش می‌کند. در این صورت می‌توانید تضمین کنید هر درخواست موفق در زمان 2d + r پاسخ می‌گیرد — و اگر در آن زمان پاسخ نگیرید، می‌دانید شبکه یا گره راه‌دور کار نمی‌کند. اگر این درست بود، 2d + r timeout معقولی بود.

متأسفانه بیشتر سیستم‌هایی که با آن‌ها کار می‌کنیم هیچ‌کدام از این تضمین‌ها را ندارند: شبکه‌های ناهمگام تأخیر نامحدود دارند (سعی می‌کنند بسته‌ها را سریع تحویل دهند، اما حد بالایی برای زمان رسیدن بسته نیست)، و بیشتر پیاده‌سازی‌های سرور نمی‌توانند تضمین کنند درخواست را در زمان حداکثری پردازش می‌کنند («تضمین‌های زمان پاسخ» در صفحه ۲۹۸).

برای تشخیص خطا، کافی نیست سیستم بیشتر وقت‌ها سریع باشد: اگر timeout پایین باشد، یک spike گذرا در زمان round-trip کافی است تا سیستم از تعادل خارج شود.

ازدحام شبکه و صف‌بندی

وقتی با ماشین رانندگی می‌کنید، زمان سفر در شبکه‌های جاده‌ای بیشتر به‌خاطر ازدحام ترافیک متغیر است. به همین ترتیب، تغییرپذیری تأخیر بسته در شبکه‌های رایانه‌ای اغلب به‌خاطر صف‌بندی (queueing) [۲۵] است:

• اگر چند گره همزمان بسته به یک مقصد بفرستند، سوئیچ شبکه باید آن‌ها را صف کند و یکی‌یکی به لینک مقصد بدهد (شکل ۸-۲). در لینک شلوغ، بسته ممکن است مدتی منتظر slot بماند (network congestion). اگر داده ورودی زیاد باشد و صف سوئیچ پر شود، بسته drop می‌شود و باید دوباره ارسال شود — با وجود اینکه شبکه سالم است.
• وقتی بسته به ماشین مقصد می‌رسد، اگر همه هسته‌های CPU مشغول باشند، درخواست ورودی از شبکه توسط سیستم‌عامل صف می‌شود تا برنامه آماده پردازش شود. بسته به بار ماشین، این ممکن است مدت دلخواهی طول بکشد.
• در محیط مجازی‌سازی، سیستم‌عامل در حال اجرا گاهی ده‌ها میلی‌ثانیه pause می‌شود تا ماشین مجازی دیگر از هسته CPU استفاده کند. در این مدت VM نمی‌تواند داده شبکه مصرف کند و داده ورودی توسط virtual machine monitor صف (buffer) می‌شود [۲۶] و تغییرپذیری تأخیر شبکه بیشتر می‌شود.
• TCP کنترل جریان (congestion avoidance یا backpressure) انجام می‌دهد و گره نرخ ارسال را محدود می‌کند تا لینک شبکه یا گره گیرنده overload نشود [۲۷]. این یعنی صف‌بندی اضافی در فرستنده قبل از ورود داده به شبکه.

شکل ۸-۲. اگر چند ماشین ترافیک شبکه به یک مقصد بفرستند، صف سوئیچ آن می‌تواند پر شود. اینجا پورت‌های ۱، ۲ و ۴ همه سعی می‌کنند بسته به پورت ۳ بفرستند.

علاوه بر این، TCP اگر بسته در timeout تأیید نشود گم‌شده فرض می‌کند و بسته‌های گم‌شده خودکار دوباره ارسال می‌شوند. اگرچه برنامه از دست رفتن و ارسال مجدد را نمی‌بیند، تأخیر ناشی از آن را می‌بیند (انتظار برای timeout و سپس تأیید بسته ارسال‌شده مجدد).

TCP در برابر UDP

برخی برنامه‌های حساس به تأخیر، مثل ویدئوکنفرانس و VoIP، به‌جای TCP از UDP استفاده می‌کنند. این trade-off بین قابلیت اطمینان و تغییرپذیری تأخیر است: چون UDP کنترل جریان و ارسال مجدد بسته‌های گم‌شده ندارد، برخی دلایل تأخیر متغیر شبکه را اجتناب می‌کند (هرچند هنوز در معرض صف سوئیچ و تأخیر scheduling است).

UDP در موقعیت‌هایی که داده تأخیریافته بی‌ارزش است انتخاب خوبی است. مثلاً در تماس VoIP، احتمالاً زمان کافی برای ارسال مجدد بسته گم‌شده قبل از پخش روی بلندگو نیست. در این صورت ارسال مجدد بی‌فایده است — برنامه باید جای خالی بسته را با سکوت پر کند (قطع کوتاه صدا) و در جریان ادامه دهد. retry در لایه انسان انجام می‌شود. («می‌توانید تکرار کنید؟ صدا لحظه‌ای قطع شد.»)

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

در ابرهای عمومی و دیتاسنترهای چندمستأجره، منابع بین مشتریان زیاد به اشتراک گذاشته می‌شود: لینک‌ها و سوئیچ‌های شبکه، و حتی رابط شبکه و CPU هر ماشین (روی VM) مشترک‌اند. بارهای دسته‌ای مثل MapReduce (فصل ۱۰) به‌راحتی لینک‌های شبکه را saturate می‌کنند. چون کنترل یا بینش استفاده مشتریان دیگر از منابع مشترک ندارید، تأخیر شبکه می‌تواند بسیار متغیر باشد اگر همسایه پرسر و صدا (noisy neighbor) منابع زیاد مصرف کند [۲۸، ۲۹].

در چنین محیط‌هایی، timeoutها را فقط آزمایشی انتخاب می‌کنید: توزیع زمان round-trip شبکه را در دوره طولانی و روی ماشین‌های زیاد اندازه بگیرید تا تغییرپذیری مورد انتظار تأخیر را تعیین کنید. سپس با توجه به ویژگی‌های برنامه، trade-off مناسب بین تأخیر تشخیص خطا و ریسک timeout زودهنگام را تعیین کنید.

بهتر از timeout ثابت پیکربندی‌شده، سیستم‌ها می‌توانند مدام زمان پاسخ و تغییرپذیری آن (jitter) را اندازه بگیرند و timeout را بر اساس توزیع مشاهده‌شده تنظیم کنند. این با Phi Accrual failure detector [۳۰] انجام می‌شود که مثلاً در Akka و Cassandra [۳۱] به کار می‌رود. timeoutهای ارسال مجدد TCP هم مشابه کار می‌کنند [۲۷].

شبکه‌های همگام در برابر ناهمگام

سیستم‌های توزیع‌شده اگر می‌توانستیم به شبکه برای تحویل بسته با حداکثر تأخیر ثابت و بدون drop تکیه کنیم خیلی ساده‌تر بودند. چرا در سطح سخت‌افزار حل نکنیم و شبکه را قابل اعتماد کنیم تا نرم‌افزار نگران نباشد؟

برای پاسخ، مقایسه شبکه‌های دیتاسنتر با شبکه تلفن ثابت سنتی (غیرسلولی، غیر-VoIP) جالب است که بسیار قابل اعتماد است: فریم‌های صوتی تأخیریافته و تماس‌های قطع‌شده بسیار نادرند. تماس تلفنی به تأخیر end-to-end کم ثابت و پهنای باند کافی برای نمونه‌های صدا نیاز دارد. آیا قابلیت اطمینان و پیش‌بینی‌پذیری مشابه در شبکه‌های رایانه‌ای ممکن نیست؟

وقتی از شبکه تلفن تماس می‌گیرید، مدار (circuit) برقرار می‌شود: مقدار ثابت و تضمین‌شده پهنای باند برای تماس در کل مسیر بین دو طرف اختصاص می‌یابد. این مدار تا پایان تماس باقی می‌ماند [۳۲]. مثلاً شبکه ISDN با نرخ ثابت ۴۰۰۰ فریم در ثانیه کار می‌کند. وقتی تماس برقرار می‌شود، ۱۶ بیت فضا در هر فریم (در هر جهت) اختصاص می‌یابد. بنابراین در طول تماس، هر طرف تضمین می‌کند هر ۲۵۰ میکروثانیه دقیقاً ۱۶ بیت داده صوتی بفرستد [۳۳، ۳۴].

این نوع شبکه همگام است: حتی وقتی داده از چند router عبور می‌کند، صف‌بندی نمی‌بیند چون ۱۶ بیت فضای تماس از قبل در hop بعدی رزرو شده. و چون صف نیست، حداکثر تأخیر end-to-end شبکه ثابت است. به این تأخیر محدود (bounded delay) می‌گوییم.

آیا نمی‌توان تأخیر شبکه را قابل پیش‌بینی کرد؟

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

اگر شبکه‌های دیتاسنتر و اینترنت circuit-switched بودند، می‌شد هنگام برقراری مدار حداکثر زمان round-trip تضمین‌شده داشت. اما نیستند: Ethernet و IP پروتکل‌های packet-switched‌اند که از صف‌بندی و بنابراین تأخیر نامحدود رنج می‌برند. مفهوم مدار ندارند.

چرا دیتاسنترها و اینترنت packet switching به کار می‌برند؟ چون برای ترافیک burst بهینه‌اند. مدار برای تماس صوتی یا ویدیویی خوب است که در طول تماس نرخ نسبتاً ثابت بیت در ثانیه می‌خواهد. درخواست صفحه وب، ارسال ایمیل یا انتقال فایل نیاز پهنای باند خاصی ندارد — فقط می‌خواهیم سریع تمام شود.

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

تلاش‌هایی برای شبکه‌های ترکیبی با circuit switching و packet switching بوده، مثل ATM.iii InfiniBand شباهت‌هایی دارد [۳۵]: کنترل جریان end-to-end در لایه لینک دارد که نیاز به صف در شبکه را کم می‌کند، هرچند هنوز از تأخیر به‌خاطر ازدحام لینک رنج می‌برد [۳۶]. با QoS دقیق (اولویت‌بندی و زمان‌بندی بسته) و admission control (محدودسازی نرخ فرستنده‌ها) می‌توان circuit switching را روی شبکه بسته‌ای شبیه‌سازی کرد یا تأخیر آماری محدود داد [۲۵، ۳۲].

ii. شاید به‌جز بسته keepalive گاه‌به‌گاه، اگر TCP keepalive فعال باشد.

iii. Asynchronous Transfer Mode (ATM) در دهه ۱۹۸۰ رقیب Ethernet بود [۳۲]، اما خارج از سوئیچ‌های هسته شبکه تلفن پذیرش نگرفت. ربطی به خودپرداز ندارد، با وجود مخفف مشترک. شاید در جهان موازی اینترنت بر پایه چیزی شبیه ATM باشد — در آن جهان تماس ویدیویی اینترنتی احتمالاً قابل‌اعتمادتر از جهان ما باشد چون از بسته‌های drop و تأخیریافته رنج نمی‌برد.

تأخیر و بهره‌برداری از منابع

به‌طور کلی‌تر، تأخیر متغیر را می‌توان پیامد تخصیص پویای منابع دانست.

سیم بین دو سوئیچ تلفن که تا ۱۰۰۰۰ تماس همزمان حمل می‌کند را در نظر بگیرید. هر مداری که روی این سیم switch می‌شود یکی از slotهای تماس را اشغال می‌کند. بنابراین سیم منبعی است که تا ۱۰۰۰۰ کاربر همزمان به اشتراک می‌گذارند. منبع به‌شکل ثابت تقسیم می‌شود: حتی اگر تنها تماس روی سیم باشید و ۹۹۹۹ slot بلااستفاده، مدار شما همان پهنای باند ثابت را دارد که وقتی سیم کاملاً utilize است.

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

در CPU هم وضعیت مشابه است: اگر هسته CPU به‌صورت پویا بین چند thread تقسیم شود، یک thread گاهی در صف اجرای سیستم‌عامل منتظر می‌ماند در حالی که thread دیگر اجرا می‌شود و thread ممکن است مدت‌های متغیر pause شود. اما سخت‌افزار بهتر از تخصیص ثابت چرخه CPU به هر thread utilize می‌شود («تضمین‌های زمان پاسخ» در صفحه ۲۹۸). بهره‌برداری بهتر سخت‌افزار انگیزه مهمی برای VM هم است.

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

تأخیر متغیر در شبکه‌ها قانون طبیعت نیست، بلکه نتیجه trade-off هزینه/فایده است.

با این حال، چنین QoS در دیتاسنترهای چندمستأجره و ابرهای عمومی، یا هنگام ارتباط از اینترنت، فعلاً فعال نیست.iv فناوری مستقر فعلی اجازه تضمین تأخیر یا قابلیت اطمینان شبکه را نمی‌دهد: باید فرض کنیم ازدحام شبکه، صف‌بندی و تأخیر نامحدود رخ می‌دهد. بنابراین مقدار «درست» برای timeout وجود ندارد — باید آزمایشی تعیین شوند.

iv. توافق‌های peering بین ISPها و برقراری مسیر از طریق BGP شباهت بیشتری به circuit switching دارد تا خود IP. در این سطح می‌توان پهنای باند اختصاصی خرید. اما مسیریابی اینترنت در سطح شبکه‌هاست نه اتصالات فردی بین میزبان‌ها، و در مقیاس زمانی بسیار طولانی‌تر.

ساعت‌های غیرقابل اعتماد

ساعت‌ها و زمان مهم‌اند. برنامه‌ها به روش‌های مختلف به ساعت‌ها متکی‌اند تا به سؤالاتی پاسخ دهند:

1. آیا این درخواست timeout شده؟
2. صدک ۹۹ زمان پاسخ این سرویس چقدر است؟
3. این سرویس در پنج دقیقه گذشته به‌طور میانگین چند query در ثانیه پردازش کرد؟
4. کاربر چقدر روی سایت ما بود؟
5. این مقاله چه زمانی منتشر شد؟
6. ایمیل یادآوری در چه تاریخ و ساعتی ارسال شود؟
7. این ورودی cache چه زمانی منقضی می‌شود؟
8. timestamp این پیام خطا در فایل log چیست؟

مثال‌های ۱ تا ۴ مدت زمان (فاصله بین ارسال درخواست و دریافت پاسخ) را اندازه می‌گیرند، اما ۵ تا ۸ نقطه در زمان (رویداد در تاریخ و ساعت خاص) را توصیف می‌کنند.

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

علاوه بر این، هر ماشین در شبکه ساعت خود را دارد که سخت‌افزار واقعی است: معمولاً نوسانگر کریستال کوارتز. این دستگاه‌ها کاملاً دقیق نیستند، پس هر ماشین مفهوم زمان خود را دارد که ممکن است کمی سریع‌تر یا کندتر از ماشین‌های دیگر باشد. می‌توان ساعت‌ها را تا حدی همگام کرد: مکانیزم رایج Network Time Protocol (NTP) است که ساعت رایانه را بر اساس زمان گزارش‌شده از گروهی سرور تنظیم می‌کند [۳۷]. سرورها به نوبه خود از منبع دقیق‌تر مثل گیرنده GPS زمان می‌گیرند.

ساعت‌های monotonic در برابر time-of-day

رایانه‌های مدرن حداقل دو نوع ساعت دارند: ساعت time-of-day و ساعت monotonic. هر دو زمان را اندازه می‌گیرند، اما تمایز آن‌ها مهم است چون کاربردهای متفاوتی دارند.

ساعت‌های time-of-day

ساعت time-of-day همان کاری را می‌کند که از ساعت انتظار دارید: تاریخ و زمان فعلی را بر اساس تقویمی برمی‌گرداند (wall-clock time). مثلاً clock_gettime(CLOCK_REALTIME) در Linux و System.currentTimeMillis() در Java تعداد ثانیه (یا میلی‌ثانیه) از epoch را برمی‌گرداند: نیمه‌شب UTC در ۱ ژانویه ۱۹۷۰ بر اساس تقویم میلادی، بدون شمارش ثانیه‌های کبیسه. برخی سیستم‌ها تاریخ مرجع دیگری دارند.

ساعت‌های time-of-day معمولاً با NTP همگام می‌شوند، یعنی timestamp از یک ماشین (ایده‌آل) همان معنای timestamp روی ماشین دیگر را دارد. اما ساعت‌های time-of-day عجیبگی‌های مختلفی هم دارند، همان‌طور که در بخش بعد می‌آید. به‌ویژه اگر ساعت محلی خیلی جلوتر از سرور NTP باشد، ممکن است اجباری reset شود و به نقطه قبلی در زمان بپرد. این پرش‌ها، و اینکه اغلب ثانیه‌های کبیسه را نادیده می‌گیرند، ساعت‌های time-of-day را برای اندازه‌گیری زمان سپری‌شده نامناسب می‌کنند [۳۸].

ساعت‌های time-of-day تاریخاً وضوح درشت‌تری داشتند، مثلاً در گام‌های ۱۰ میلی‌ثانیه در Windows قدیمی [۳۹]. در سیستم‌های اخیر این کمتر مشکل است.

ساعت‌های monotonic

ساعت monotonic برای اندازه‌گیری مدت (فاصله زمانی) مناسب است، مثل timeout یا زمان پاسخ سرویس: clock_gettime(CLOCK_MONOTONIC) در Linux و System.nanoTime() در Java ساعت monotonic‌اند. نام از این می‌آید که همیشه جلو می‌روند (ساعت time-of-day ممکن است به عقب بپرد).

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

در سرور با چند سوکت CPU ممکن است timer جدا برای هر CPU باشد که لزوماً با CPUهای دیگر همگام نیست. سیستم‌عامل اختلاف را جبران می‌کند و سعی می‌کند نمای monotonic به threadهای برنامه بدهد، حتی وقتی روی CPUهای مختلف schedule می‌شوند. اما بهتر است این تضمین monotonicity را با احتیاط بپذیرید [۴۰].

NTP ممکن است فرکانس حرکت ساعت monotonic را تنظیم کند (slewing) اگر ببیند کوارتز محلی سریع‌تر یا کندتر از سرور NTP حرکت می‌کند. به‌طور پیش‌فرض NTP اجازه می‌دهد نرخ ساعت تا ۰٫۰۵٪ سرعت یا کندی یابد، اما نمی‌تواند ساعت monotonic را به جلو یا عقب بپرد. وضوح ساعت‌های monotonic معمولاً خوب است: در بیشتر سیستم‌ها فاصله زمانی را در میکروثانیه یا کمتر اندازه می‌گیرند.

در سیستم توزیع‌شده، استفاده از ساعت monotonic برای زمان سپری‌شده (مثلاً timeout) معمولاً خوب است، چون فرض همگام‌سازی بین ساعت گره‌ها نمی‌کند و به نادرستی‌های جزئی اندازه‌گیری حساس نیست.

همگام‌سازی ساعت و دقت

ساعت‌های monotonic به همگام‌سازی نیاز ندارند، اما ساعت‌های time-of-day باید بر اساس سرور NTP یا منبع زمان خارجی تنظیم شوند تا مفید باشند.

متأسفانه روش‌های ما برای زمان درست ساعت به اندازه امید قابل اعتماد و دقیق نیستند — ساعت سخت‌افزاری و NTP می‌توانند سرکش باشند. چند نمونه:

• ساعت کوارتز در رایانه خیلی دقیق نیست: drift دارد (سریع‌تر یا کندتر از باید). drift به دمای ماشین بستگی دارد. Google برای سرورها drift ۲۰۰ ppm فرض می‌کند [۴۱]، معادل ۶ میلی‌ثانیه drift برای ساعتی که هر ۳۰ ثانیه با سرور همگام می‌شود، یا ۱۷ ثانیه برای همگام‌سازی روزانه. این drift بهترین دقت ممکن را محدود می‌کند، حتی اگر همه چیز درست کار کند.
• اگر ساعت رایانه خیلی با سرور NTP فرق کند، ممکن است از همگام‌سازی امتناع کند یا ساعت محلی اجباری reset شود [۳۷]. برنامه‌هایی که زمان قبل و بعد از reset را می‌بینند ممکن است زمان به عقب برود یا ناگهان بپرد.
• اگر گره تصادفی از سرورهای NTP با firewall جدا شود، misconfiguration ممکن است مدتی پنهان بماند. شواهد تجربی نشان می‌دهد این در عمل رخ می‌دهد.
• همگام‌سازی NTP فقط به اندازه تأخیر شبکه خوب است، پس دقت محدود است وقتی روی شبکه شلوغ با تأخیر متغیر بسته هستید. یک آزمایش حداقل خطای ۳۵ میلی‌ثانیه روی اینترنت نشان داد [۴۲]، هرچند spikeهای تأخیر گاهی خطای حدود یک ثانیه ایجاد می‌کند. بسته به پیکربندی، تأخیرهای بزرگ شبکه ممکن است باعث شود کلاینت NTP کاملاً تسلیم شود.
• برخی سرورهای NTP اشتباه یا misconfigure‌اند و ساعتی چند ساعت جلو یا عقب گزارش می‌کنند [۴۳، ۴۴]. کلاینت‌های NTP نسبتاً مقاوم‌اند چون چند سرور را query و outlierها را نادیده می‌گیرند. با این حال، تکیه صحت سیستم‌ها به زمانی که از غریبه اینترنت شنیده‌اید نگران‌کننده است.
• ثانیه‌های کبیسه دقیقه‌ای ۵۹ یا ۶۱ ثانیه‌ای ایجاد می‌کنند که فرض‌های زمان‌بندی سیستم‌هایی که برای ثانیه کبیسه طراحی نشده‌اند را به هم می‌ریزد [۴۵]. اینکه ثانیه کبیسه سیستم‌های بزرگ زیادی را crash کرده [۳۸، ۴۶] نشان می‌دهد فرض‌های نادرست درباره ساعت چقدر راحت در سیستم نفوذ می‌کند. بهترین روش شاید «دروغ گفتن» سرورهای NTP با تنظیم تدریجی ثانیه کبیسه در طول روز (smearing) [۴۷، ۴۸] باشد، هرچند رفتار واقعی سرورهای NTP متفاوت است [۴۹].
• در ماشین‌های مجازی، ساعت سخت‌افزاری مجازی‌سازی می‌شود که چالش اضافی برای برنامه‌هایی که زمان‌بندی دقیق می‌خواهند ایجاد می‌کند [۵۰]. وقتی هسته CPU بین VMها به اشتراک گذاشته می‌شود، هر VM ده‌ها میلی‌ثانیه pause می‌شود. از دید برنامه، این pause به‌صورت پرش ناگهانی ساعت به جلو دیده می‌شود [۲۶].
• اگر نرم‌افزار روی دستگاهی اجرا می‌شود که کاملاً کنترل ندارید (موبایل یا embedded)، شاید اصلاً نتوانید به ساعت سخت‌افزاری اعتماد کنید. برخی کاربران عمداً ساعت را اشتباه تنظیم می‌کنند، مثلاً برای دور زدن محدودیت زمانی بازی. ساعت ممکن است در گذشته یا آینده دور تنظیم شود.

اگر به اندازه کافی اهمیت دهید، دقت ساعت بسیار خوب ممکن است. مثلاً مقررات پیش‌نویس MiFID II اتحادیه اروپا برای مؤسسات مالی می‌خواهد صندوق‌های معاملات پرتکرار ساعت‌ها را در ۱۰۰ میکروثانیه UTC همگام کنند تا ناهنجاری‌های بازار مثل «flash crash» و دستکاری بازار را debug کنند [۵۱].

چنین دقتی با گیرنده GPS، Precision Time Protocol (PTP) [۵۲] و استقرار و پایش دقیق ممکن است. اما تلاش و تخصص زیاد می‌خواهد و راه‌های زیادی برای خراب شدن همگام‌سازی ساعت وجود دارد. اگر daemon NTP misconfigure باشد یا firewall ترافیک NTP را block کند، خطای ساعت به‌خاطر drift خیلی سریع بزرگ می‌شود.

تکیه به ساعت‌های همگام‌شده

مشکل ساعت‌ها این است که ساده و آسان به نظر می‌رسند، اما دام‌های زیادی دارند: روز شاید دقیقاً ۸۶۴۰۰ ثانیه نباشد، ساعت‌های time-of-day ممکن است به عقب بپرد، و زمان یک گره ممکن است با گره دیگر خیلی فرق کند.

در ابتدای فصل درباره drop و تأخیر دلخواه بسته‌های شبکه بحث کردیم. اگرچه شبکه بیشتر وقت‌ها خوب رفتار می‌کند، نرم‌افزار باید فرض کند گاهی شبکه معیوب است و باید graceful برخورد کند. با ساعت‌ها هم همین است: اگرچه بیشتر وقت‌ها خوب کار می‌کنند، نرم‌افزار مقاوم باید برای ساعت نادرست آماده باشد.

بخشی از مشکل این است که ساعت نادرست به‌راحتی دیده نمی‌شود. اگر CPU معیوب یا شبکه misconfigure باشد، احتمالاً اصلاً کار نمی‌کند و زود دیده و تعمیر می‌شود. اما اگر کوارتز یا کلاینت NTP misconfigure باشد، بیشتر چیزها خوب به نظر می‌رسند در حالی که ساعت تدریجاً از واقعیت دور می‌شود. اگر نرم‌افزاری به ساعت همگام‌شده دقیق متکی باشد، نتیجه احتمالاً از دست رفتن داده خاموش و ظریف است نه crash دراماتیک [۵۳، ۵۴].

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

timestampها برای مرتب‌سازی رویدادها

موقعیتی خاص را در نظر بگیرید که وسوسه‌انگیز اما خطرناک است تکیه به ساعت: مرتب‌سازی رویدادها بین چند گره. مثلاً اگر دو کلاینت به پایگاه داده توزیع‌شده بنویسند، کدام زودتر رسید؟ کدام نوشتن جدیدتر است؟ شکل ۸-۳ استفاده خطرناک ساعت time-of-day در پایگاه داده با رپلیکاسیون multi-leader را نشان می‌دهد (مشابه شکل ۵-۹). کلاینت A روی گره ۱ می‌نویسد x = 1؛ نوشتن به گره ۳ رپلیکا می‌شود؛ کلاینت B روی گره ۳ x را افزایش می‌دهد (اکنون x = 2)؛ و در نهایت هر دو نوشتن به گره ۲ رپلیکا می‌شوند.

شکل ۸-۳. نوشتن کلاینت B از نظر علّی بعد از نوشتن کلاینت A است، اما timestamp نوشتن B زودتر است.

در شکل ۸-۳، وقتی نوشتن به گره‌های دیگر رپلیکا می‌شود، با timestamp ساعت time-of-day گره مبدأ برچسب می‌خورد. همگام‌سازی ساعت در این مثال خیلی خوب است: skew بین گره ۱ و ۳ کمتر از ۳ میلی‌ثانیه است که احتمالاً بهتر از عمل است.

با این حال، timestampها در شکل ۸-۳ رویدادها را درست مرتب نمی‌کنند: نوشتن x = 1 timestamp ۴۲٫۰۰۴ ثانیه دارد، اما x = 2 timestamp ۴۲٫۰۰۳ ثانیه، در حالی که x = 2 قطعاً بعدتر رخ داده. وقتی گره ۲ این دو رویداد را می‌گیرد، اشتباه نتیجه می‌گیرد x = 1 جدیدتر است و نوشتن x = 2 را دور می‌ریزد. در عمل، افزایش کلاینت B از دست می‌رود.

این استراتژی حل تعارض آخرین نوشتن برنده (last write wins؛ LWW) نامیده می‌شود و در رپلیکاسیون multi-leader و پایگاه‌های بدون leader مثل Cassandra [۵۳] و Riak [۵۴] («آخرین نوشتن برنده (دور ریختن نوشتن‌های همزمان)» در صفحه ۱۸۶) رایج است. برخی پیاده‌سازی‌ها timestamp را روی کلاینت نه سرور تولید می‌کنند، اما مشکلات بنیادی LWW را عوض نمی‌کند:

• نوشتن‌های پایگاه داده ممکن است ناپیدا شوند: گره با ساعت عقب‌افتاده نمی‌تواند مقادیری را که گره با ساعت سریع نوشته بازنویسی کند تا skew ساعت بین گره‌ها بگذرد [۵۴، ۵۵]. این می‌تواند باعث از دست رفتن دلخواه داده بدون گزارش خطا به برنامه شود.
• LWW نمی‌تواند بین نوشتن‌های متوالی سریع (در شکل ۸-۳، افزایش B قطعاً بعد از نوشتن A است) و نوشتن‌های واقعاً همزمان (هیچ نویسنده از دیگری خبر نداشت) تمایز قائل شود. مکانیزم‌های ردیابی علّیت اضافی مثل version vector برای جلوگیری از نقض علّیت لازم است («تشخیص نوشتن‌های همزمان» در صفحه ۱۸۴).
• دو گره ممکن است مستقل نوشتن با همان timestamp تولید کنند، به‌ویژه وقتی ساعت فقط وضوح میلی‌ثانیه دارد. tiebreaker اضافی (مثلاً عدد تصادفی بزرگ) برای حل تعارض لازم است، اما این هم می‌تواند نقض علّیت ایجاد کند [۵۳].

پس اگرچه وسوسه‌انگیز است با نگه‌داشتن «جدیدترین» مقدار تعارض حل شود، باید بدانید تعریف «جدید» به ساعت time-of-day محلی بستگی دارد که ممکن است نادرست باشد. حتی با ساعت‌های NTP محکم همزمان، ممکن است بسته‌ای با timestamp ۱۰۰ میلی‌ثانیه (طبق ساعت فرستنده) با timestamp ۹۹ میلی‌ثانیه (طبق گیرنده) برسد — پس انگار بسته قبل از ارسال رسیده، که غیرممکن است.

آیا همگام‌سازی NTP می‌تواند آنقدر دقیق شود که چنین ترتیب نادرستی رخ ندهد؟ احتمالاً نه، چون دقت همگام‌سازی NTP خودش به زمان round-trip شبکه و منابع خطا مثل drift کوارتز محدود است. برای ترتیب درست، منبع ساعت باید از چیزی که اندازه می‌گیرید (تأخیر شبکه) به‌طور قابل توجهی دقیق‌تر باشد.

ساعت‌های منطقی [۵۶، ۵۷] که بر شمارنده‌های افزایشی نه کریستال کوارتز نوسان‌کننده استوارند، جایگزین امن‌تری برای مرتب‌سازی رویدادها هستند («تشخیص نوشتن‌های همزمان» در صفحه ۱۸۴). ساعت‌های منطقی زمان روز یا ثانیه سپری‌شده را اندازه نمی‌گیرند، فقط ترتیب نسبی رویدادها (کدام قبل یا بعد از دیگری). در مقابل، ساعت‌های time-of-day و monotonic که زمان واقعی سپری‌شده را اندازه می‌گیرند ساعت فیزیکی نامیده می‌شوند. مرتب‌سازی را در «تضمین‌های مرتب‌سازی» در صفحه ۳۳۹ بیشتر می‌بینیم.

خواندن ساعت بازه اطمینان دارد

شاید بتوانید ساعت time-of-day را با وضوح میکروثانیه یا نانوثانیه بخوانید. اما حتی با اندازه‌گیری ریز، لزوماً به آن دقت ندارید — در واقع احتمالاً ندارید؛ drift کوارتز نادرست به‌راحتی چند میلی‌ثانیه است، حتی با همگام‌سازی هر دقیقه با سرور NTP محلی. با سرور NTP عمومی اینترنت، بهترین دقت شاید ده‌ها میلی‌ثانیه باشد و خطا در ازدحام شبکه از ۱۰۰ میلی‌ثانیه هم بیشتر شود [۵۷].

پس خواندن ساعت را نقطه در زمان نگیرید — بیشتر بازه زمانی با بازه اطمینان است: مثلاً سیستم ۹۵٪ مطمئن است زمان الان بین ۱۰٫۳ و ۱۰٫۵ ثانیه گذشته از دقیقه است [۵۸]. اگر فقط زمان را ±۱۰۰ میلی‌ثانیه می‌دانید، رقم‌های میکروثانیه timestamp عملاً بی‌معناست.

مرز عدم قطعیت را می‌توان از منبع زمان محاسبه کرد. اگر گیرنده GPS یا ساعت اتمی (caesium) مستقیم به رایانه وصل است، بازه خطای مورد انتظار سازنده گزارش می‌کند. اگر از سرور زمان می‌گیرید، عدم قطعیت بر اساس drift کوارتز از آخرین همگام‌سازی، عدم قطعیت سرور NTP و زمان round-trip شبکه (تقریباً، با فرض اعتماد به سرور) است.

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

استثنای جالب TrueTime API گوگل در Spanner [۴۱] است که صریح بازه اطمینان ساعت محلی را گزارش می‌کند. وقتی زمان فعلی می‌خواهید، دو مقدار برمی‌گردد: [earliest, latest]، یعنی زودترین و دیرترین timestamp ممکن. ساعت می‌داند زمان واقعی جایی در این بازه است. عرض بازه به‌ویژه به مدت زمان از آخرین همگام‌سازی کوارتز محلی با منبع دقیق‌تر بستگی دارد.

ساعت‌های همگام‌شده برای snapshot سراسری

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

رایج‌ترین پیاده‌سازی ایزولاسیون snapshot به شناسه تراکنش monotonic افزایشی نیاز دارد. اگر نوشتن بعد از snapshot بود (شناسه تراکنش بزرگ‌تر از snapshot)، آن نوشتن برای تراکنش snapshot نامرئی است. در پایگاه تک‌گره، شمارنده ساده برای شناسه تراکنش کافی است.

اما وقتی پایگاه بین ماشین‌های زیاد، احتمالاً در چند دیتاسنتر توزیع شده، تولید شناسه تراکنش سراسری monotonic افزایشی (در همه پارتیشن‌ها) سخت است چون هماهنگی می‌خواهد. شناسه تراکنش باید علّیت را منعکس کند: اگر تراکنش B مقداری را که تراکنش A نوشته خواند، B باید شناسه بالاتر از A داشته باشد — وگرنه snapshot سازگار نیست. با تراکنش‌های کوچک سریع زیاد، تولید شناسه تراکنش در سیستم توزیع‌شده گلوگاه می‌شود.vi

آیا می‌توان از timestamp ساعت‌های time-of-day همگام‌شده به‌عنوان شناسه تراکنش استفاده کرد؟ اگر همگام‌سازی به اندازه کافی خوب باشد، ویژگی درست را دارند: تراکنش‌های بعدی timestamp بالاتر. مشکل البته عدم قطعیت دقت ساعت است.

Spanner ایزولاسیون snapshot بین دیتاسنترها را این‌طور پیاده می‌کند [۵۹، ۶۰]. از بازه اطمینان ساعت که TrueTime API گزارش می‌کند استفاده می‌کند و بر این مشاهده استوار است: اگر دو بازه اطمینان دارید، هر کدام earliest و latest (A = [Aearliest, Alatest] و B = [Bearliest, Blatest])، و بازه‌ها همپوشانی ندارند (یعنی Aearliest < Alatest < Bearliest < Blatest)، آنگاه B قطعاً بعد از A رخ داده — شکی نیست. فقط اگر بازه‌ها همپوشانی داشته باشند در ترتیب A و B مطمئن نیستیم.

برای اینکه timestamp تراکنش علّیت را منعکس کند، Spanner عمداً به اندازه طول بازه اطمینان قبل از commit تراکنش خواندن-نوشتن منتظر می‌ماند. این تضمین می‌کند هر تراکنشی که ممکن است داده را بخواند به اندازه کافی دیرتر است تا بازه‌های اطمینان همپوشانی نداشته باشند. برای کوتاه نگه داشتن انتظار، Spanner باید عدم قطعیت ساعت را کم نگه دارد؛ برای این منظور Google در هر دیتاسنتر گیرنده GPS یا ساعت اتمی مستقر می‌کند و ساعت‌ها را در حدود ۷ میلی‌ثانیه همگام می‌کند [۴۱].

استفاده از همگام‌سازی ساعت برای semantics تراکنش توزیع‌شده حوزه تحقیق فعال است [۵۷، ۶۱، ۶۲]. ایده‌ها جالب‌اند اما هنوز در پایگاه‌های جریان اصلی خارج از Google پیاده نشده‌اند.

vi. تولیدکننده‌های شناسه دنباله توزیع‌شده مثل Snowflake توییتر شناسه‌های منحصربه‌فرد تقریباً monotonic افزایشی را مقیاس‌پذیر تولید می‌کنند (مثلاً با تخصیص بلوک‌های فضای شناسه به گره‌های مختلف). اما معمولاً نمی‌توانند ترتیبی سازگار با علّیت تضمین کنند، چون مقیاس زمانی تخصیص بلوک‌ها از مقیاس خواندن و نوشتن پایگاه داده طولانی‌تر است. «تضمین‌های مرتب‌سازی» در صفحه ۳۳۹ را هم ببینید.

مکث‌های فرآیند

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

یک گزینه این است leader از گره‌های دیگر lease بگیرد، شبیه قفل با timeout [۶۳]. در هر لحظه فقط یک گره lease دارد — پس وقتی lease می‌گیرد، می‌داند برای مدتی leader است تا lease منقضی شود. برای ماندن leader، باید دوره‌ای lease را تمدید کند.

حلقه پردازش درخواست شاید شبیه این باشد:

while (true) {
    request = getIncomingRequest();

    // Ensure that the lease always has at least 10 seconds remaining
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew();
    }

    if (lease.isValid()) {
        process(request);
    }
}

مشکل این کد چیست؟ اول، به ساعت همگام‌شده متکی است: زمان انقضای lease توسط ماشین دیگر تنظیم می‌شود (مثلاً زمان فعلی به‌علاوه ۳۰ ثانیه) و با ساعت محلی System.currentTimeMillis() مقایسه می‌شود. اگر ساعت‌ها بیش از چند ثانیه out of sync باشند، کد رفتار عجیب می‌کند.

دوم، حتی اگر فقط از ساعت monotonic محلی استفاده کنیم، مشکل دیگری هست: کد فرض می‌کند بین بررسی زمان (System.currentTimeMillis()) و پردازش درخواست (process(request)) زمان کمی می‌گذرد. معمولاً این کد خیلی سریع اجرا می‌شود و بافر ۱۰ ثانیه برای اینکه lease در میانه پردازش منقضی نشود کافی است.

اما اگر pause غیرمنتظره در اجرای برنامه باشد چه؟ مثلاً thread حدود خط lease.isValid() ۱۵ ثانیه متوقف شود و بعد ادامه دهد. در آن صورت احتمالاً lease هنگام پردازش درخواست منقضی شده و گره دیگر leader شده. اما چیزی به thread نمی‌گوید ۱۵ ثانیه pause بوده، پس تا تکرار بعدی حلقه متوجه انقضای lease نمی‌شود — و شاید تا آن موقع کاری ناامن انجام داده باشد.

آیا فرض pause ۱۵ ثانیه‌ای دیوانگی است؟ متأسفانه نه. دلایل مختلفی دارد:

• بسیاری از runtimeهای زبان (مثل JVM) garbage collector (GC) دارند که گاهی همه threadهای در حال اجرا را متوقف می‌کند. این pauseهای «stop-the-world» GC گاهی چند دقیقه طول کشیده [۶۴]! حتی GCهای «همزمان» مثل CMS در HotSpot JVM هم کاملاً موازی با کد برنامه نیستند — گاهی باید world را متوقف کنند [۶۵]. اگرچه pauseها با تغییر الگوی تخصیص یا تنظیم GC کاهش می‌یابند [۶۶]، برای تضمین‌های مقاوم باید بدترین را فرض کنیم.
• در محیط مجازی‌سازی، VM می‌تواند suspend شود (همه فرآیندها pause و محتوای حافظه روی دیسک ذخیره شود) و resume شود. این pause در هر نقطه اجرا و برای مدت دلخواه ممکن است. گاهی برای live migration VM بدون reboot استفاده می‌شود و طول pause به نرخ نوشتن فرآیندها به حافظه بستگی دارد [۶۷].
• روی دستگاه‌های کاربر نهایی مثل لپ‌تاپ، اجرا هم ممکن است دلخواه suspend و resume شود، مثلاً با بستن در لپ‌تاپ.
• وقتی سیستم‌عامل به thread دیگر context-switch می‌کند، یا hypervisor به VM دیگر (روی VM)، thread فعلی در هر نقطه دلخواه کد pause می‌شود. در VM، زمان CPU صرف‌شده در VMهای دیگر steal time نامیده می‌شود. اگر ماشین تحت بار سنگین باشد — صف طولانی threadها برای اجرا — ممکن است مدتی طول بکشد تا thread pause‌شده دوباره اجرا شود.
• اگر برنامه دسترسی همزمان به دیسک انجام دهد، thread ممکن است منتظر I/O کند دیسک بماند [۶۸]. در بسیاری از زبان‌ها دسترسی دیسک غیرمنتظره رخ می‌دهد — مثلاً classloader جاوا فایل کلاس را lazy بار می‌کند. pauseهای I/O و GC ممکن است ترکیب شوند [۶۹]. اگر دیسک در واقع filesystem شبکه یا block device شبکه (مثل Amazon EBS) باشد، تأخیر I/O به تغییرپذیری شبکه هم وابسته است [۲۹].
• اگر سیستم‌عامل swap به دیسک (paging) مجاز باشد، دسترسی ساده به حافظه ممکن است page fault ایجاد کند و thread در I/O کند pause شود. اگر فشار حافظه بالا باشد، ممکن است صفحه دیگری swap out شود. در حد افراط، سیستم‌عامل بیشتر وقتش را صرف swap می‌کند (thrashing). برای جلوگیری، paging اغلب روی سرورها غیرفعال است (ترجیح kill فرآیند به thrashing).
• فرآیند Unix با سیگنال SIGSTOP متوقف می‌شود، مثلاً Ctrl-Z در shell. این سیگنال فوراً فرآیند را از CPU قطع می‌کند تا با SIGCONT از سر گرفته شود. حتی اگر محیط شما معمولاً SIGSTOP نمی‌زند، ممکن است اپراتور تصادفاً بزند.

همه این‌ها می‌توانند thread در حال اجرا را در هر نقطه preempt کنند و بعداً از سر بگیرند، بدون اینکه thread متوجه شود. مشکل شبیه thread-safe کردن کد چندنخی روی یک ماشین است: نمی‌توان درباره زمان‌بندی فرض کرد، چون context switch و موازی‌سازی دلخواه ممکن است.

برای کد چندنخی روی یک ماشین ابزارهای نسبتاً خوبی برای thread-safe بودن داریم: mutex، semaphore، شمارنده اتمی، ساختارهای lock-free، صف blocking و غیره. متأسفانه این ابزارها مستقیم به سیستم توزیع‌شده ترجمه نمی‌شوند، چون سیستم توزیع‌شده حافظه مشترک ندارد — فقط پیام از شبکه غیرقابل اعتماد.

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

تضمین‌های زمان پاسخ

در بسیاری از زبان‌ها و سیستم‌عامل‌ها، threadها و فرآیندها ممکن است مدت نامحدود pause شوند. این دلایل pause با تلاش زیاد قابل حذف‌اند.

برخی نرم‌افزارها در محیطی اجرا می‌شوند که عدم پاسخ در زمان مشخص آسیب جدی می‌زند: رایانه‌های کنترل هواپیما، موشک، ربات، خودرو و اشیای فیزیکی دیگر باید سریع و قابل پیش‌بینی به ورودی سنسور پاسخ دهند. در این سیستم‌ها مهلت مشخصی دارند؛ اگر رعایت نشود، کل سیستم ممکن است خراب شود. این‌ها سیستم‌های real-time سخت (hard real-time) نامیده می‌شوند.

آیا real-time واقعاً real است؟

در embedded، real-time یعنی سیستم با دقت طراحی و تست شده تا در همه شرایط تضمین‌های زمان‌بندی مشخص را برآورده کند. این با معنای مبهم‌تر real-time در وب — سرورهای push به کلاینت و stream processing بدون محدودیت سخت زمان پاسخ (فصل ۱۱) — متفاوت است.

مثلاً اگر سنسورهای خودرو تشخیص دهند تصادف رخ داده، نمی‌خواهید باز شدن کیسه هوا به‌خاطر GC نابه‌جا در سیستم کیسه هوا تأخیر یابد.

تضمین real-time در همه سطوح stack نرم‌افزار نیاز دارد: سیستم‌عامل real-time (RTOS) که فرآیندها را با تخصیص تضمین‌شده CPU در بازه‌های مشخص schedule کند؛ کتابخانه‌ها باید بدترین زمان اجرا را مستند کنند؛ تخصیص پویای حافظه ممکن است محدود یا ممنوع شود (GC real-time وجود دارد، اما برنامه باید مطمئن شود کار زیادی به GC نمی‌دهد)؛ و تست و اندازه‌گیری زیاد برای اطمینان از برآورده شدن تضمین‌ها.

همه این‌ها کار اضافی زیاد می‌خواهد و دامنه زبان‌ها، کتابخانه‌ها و ابزارها را شدید محدود می‌کند (چون بیشتر آن‌ها تضمین real-time نمی‌دهند). توسعه سیستم real-time بسیار گران است و بیشتر در دستگاه‌های embedded ایمنی‌بحرانی به کار می‌رود. «real-time» همسان «کارایی بالا» نیست — سیستم real-time ممکن است throughput کمتر داشته باشد چون پاسخ به‌موقع بر همه چیز مقدم است («تأخیر و بهره‌برداری از منابع» در صفحه ۲۸۶).

برای بیشتر سیستم‌های پردازش داده سمت سرور، تضمین real-time اقتصادی یا مناسب نیست. این سیستم‌ها باید pauseها و ناپایداری ساعت محیط غیر-real-time را تحمل کنند.

محدود کردن اثر garbage collection

اثرات منفی pause فرآیند را می‌توان بدون تضمین‌های زمان‌بندی real-time گران کاهش داد. runtimeهای زبان انعطافی در زمان‌بندی GC دارند چون نرخ تخصیص شیء و حافظه آزاد باقی‌مانده را دنبال می‌کنند.

ایده نوظهور این است که pauseهای GC را مثل outage کوتاه برنامه‌ریزی‌شده گره بدانید و گره‌های دیگر درخواست کلاینت‌ها را بپذیرند. اگر runtime به برنامه هشدار دهد گره به‌زودی به GC نیاز دارد، برنامه می‌تواند درخواست جدید به آن گره نفرستد، منتظر اتمام درخواست‌های جاری بماند، و GC را وقتی درخواستی در جریان نیست انجام دهد. این ترفند pauseهای GC را از کلاینت پنهان و صدک‌های بالای زمان پاسخ را کاهش می‌دهد [۷۰، ۷۱]. برخی سیستم‌های معاملات مالی حساس به تأخیر [۷۲] از این رویکرد استفاده می‌کنند.

گونه‌ای از این ایده استفاده GC فقط برای اشیاء کوتاه‌عمر (جمع‌آوری سریع) و restart دوره‌ای فرآیندها قبل از انباشت اشیاء بلندمدت که GC کامل می‌خواهد [۶۵، ۷۳]. یک گره در هر بار restart می‌شود و ترافیک قبل از restart منتقل می‌شود، مثل rolling upgrade (فصل ۴).

این اقدامات pauseهای GC را کاملاً حذف نمی‌کنند، اما اثرشان را مفید کاهش می‌دهند.

دانش، حقیقت و دروغ

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

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

بحث‌های این سیستم‌ها به فلسفه نزدیک می‌شود: در سیستم چه چیزهایی را درست یا نادرست می‌دانیم؟ چقدر می‌توانیم به این دانش مطمئن باشیم اگر ابزار ادراک و اندازه‌گیری غیرقابل اعتمادند؟ آیا نرم‌افزار باید از قوانین دنیای فیزیکی مثل علت و معلول پیروی کند؟

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

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

حقیقت توسط اکثریت تعریف می‌شود

شبکه‌ای با خطای نامتقارن تصور کنید: گره همه پیام‌های ورودی را می‌گیرد، اما هر پیام خروجی drop یا تأخیر می‌یابد [۱۹]. گره کاملاً سالم است و درخواست می‌گیرد، اما گره‌های دیگر پاسخش را نمی‌شنوند. پس از timeout، گره‌های دیگر آن را مرده اعلام می‌کنند. وضعیت مثل کابوس است: گره نیمه‌قطع فریاد «من مرده نیستم!» می‌زند — اما کسی نمی‌شنود و تشییع جنازه با عزم ادامه می‌یابد.

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

سناریوی سوم: گره pause طولانی stop-the-world GC دارد. همه threadها یک دقیقه preempt می‌شوند، درخواستی پردازش نمی‌شود و پاسخی ارسال نمی‌شود. گره‌های دیگر منتظر، retry و بی‌حوصله می‌شوند و گره را مرده اعلام و روی آمبولانس می‌گذارند. بالاخره GC تمام می‌شود و threadها انگار هیچ اتفاقی نیفتاده ادامه می‌دهند. گره‌های دیگر تعجب می‌کنند وقتی گره «مرده» سرش را از تابوت بیرون می‌آورد و شاد با رهگذران حرف می‌زند. گره GC‌شده حتی نمی‌فهمد یک دقیقه گذشته و مرده اعلام شده — از دیدش تقریباً هیچ زمانی نگذشته.

درس این داستان‌ها: گره لزوماً نمی‌تواند به قضاوت خودش درباره وضعیت اعتماد کند. سیستم توزیع‌شده نمی‌تواند فقط به یک گره تکیه کند، چون گره هر لحظه ممکن است خراب شود و سیستم گیر کند. بسیاری از الگوریتم‌های توزیع‌شده به quorum، یعنی رأی‌گیری بین گره‌ها («quorum برای خواندن و نوشتن» در صفحه ۱۷۹) متکی‌اند: تصمیم‌ها به حداقل تعداد رأی از چند گره نیاز دارند تا وابستگی به یک گره خاص کم شود.

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

رایج‌ترین quorum اکثریت مطلق بیش از نیمی از گره‌هاست (هرچند quorumهای دیگر هم ممکن است). اکثریت مطلق اجازه می‌دهد سیستم با خرابی گره‌های فردی ادامه دهد (با سه گره یک خرابی تحمل می‌شود؛ با پنج گره دو خرابی). اما ایمن است چون فقط یک اکثریت در سیستم می‌تواند باشد — دو اکثریت با تصمیم‌های متضاد همزمان نمی‌توانند وجود داشته باشند. استفاده از quorum را در فصل ۹ با الگوریتم‌های consensus بیشتر بحث می‌کنیم.

leader و قفل

اغلب سیستم فقط یکی از چیزی را می‌خواهد. مثلاً:

• فقط یک گره leader پارتیشن پایگاه داده باشد تا split brain نشود («مدیریت خرابی گره‌ها» در صفحه ۱۵۶).
• فقط یک تراکنش یا کلاینت قفل منبع یا شیء خاص را داشته باشد تا نوشتن همزمان و خرابی نشود.
• فقط یک کاربر نام کاربری خاص را ثبت کند چون نام کاربری باید منحصربه‌فرد باشد.

پیاده‌سازی این در سیستم توزیع‌شده نیاز به دقت دارد: حتی اگر گره باور کند «برگزیده» است (leader پارتیشن، دارنده قفل، handler درخواست کاربری که نام کاربری را گرفت)، لزوماً quorum گره‌ها موافق نیستند! گره شاید قبلاً leader بوده، اما اگر گره‌های دیگر در این فاصله آن را مرده اعلام کرده‌اند (مثلاً به‌خاطر قطع شبکه یا pause GC)، تنزل یافته و leader دیگری انتخاب شده.

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

مثلاً شکل ۸-۴ باگ خرابی داده به‌خاطر پیاده‌سازی نادرست قفل را نشان می‌دهد (باگ تئوری نیست: HBase قبلاً این مشکل را داشت [۷۴، ۷۵]). می‌خواهید فقط یک کلاینت در هر لحظه به فایل در سرویس ذخیره‌سازی دسترسی داشته باشد، چون نوشتن همزمان چند کلاینت فایل را خراب می‌کند. با الزام گرفتن lease از سرویس قفل قبل از دسترسی به فایل این را پیاده می‌کنید.

شکل ۸-۴. پیاده‌سازی نادرست قفل توزیع‌شده: کلاینت ۱ باور دارد lease هنوز معتبر است در حالی که منقضی شده و فایل را در storage خراب می‌کند.

مشکل نمونه‌ای از «مکث‌های فرآیند» در صفحه ۲۹۵ است: اگر کلاینت دارنده lease خیلی pause شود، lease منقضی می‌شود. کلاینت دیگر lease همان فایل را می‌گیرد و شروع به نوشتن می‌کند. وقتی کلاینت pause‌شده برمی‌گردد، اشتباه باور دارد lease معتبر است و به نوشتن ادامه می‌دهد. نوشتن‌های کلاینت‌ها تداخل و فایل خراب می‌شود.

توکن‌های fencing

وقتی از قفل یا lease برای محافظت از منبع (مثل ذخیره‌سازی فایل در شکل ۸-۴) استفاده می‌کنید، باید مطمئن شوید گرهی که اشتباه باور دارد «برگزیده» است بقیه سیستم را مختل نکند. تکنیک نسبتاً ساده fencing است (شکل ۸-۵).

شکل ۸-۵. ایمن کردن دسترسی به storage با اجازه نوشتن فقط به ترتیب توکن‌های fencing افزایشی.

فرض کنید هر بار سرویس قفل قفل یا lease می‌دهد، توکن fencing هم برمی‌گرداند — عددی که هر بار قفل داده می‌شود افزایش می‌یابد (مثلاً توسط سرویس قفل). سپس می‌توانید الزام کنید هر بار کلاینت درخواست نوشتن به سرویس storage می‌فرستد، توکن fencing فعلی را هم بفرستد.

در شکل ۸-۵، کلاینت ۱ lease با توکن ۳۳ می‌گیرد، اما pause طولانی می‌شود و lease منقضی می‌شود. کلاینت ۲ lease با توکن ۳۴ (عدد همیشه افزایش می‌یابد) می‌گیرد و درخواست نوشتن با توکن ۳۴ به storage می‌فرستد. بعد کلاینت ۱ زنده می‌شود و با توکن ۳۳ می‌نویسد. اما storage به‌خاطر دارد نوشتن با توکن بالاتر (۳۴) را پردازش کرده و درخواست با توکن ۳۳ را رد می‌کند.

اگر ZooKeeper سرویس قفل باشد، شناسه تراکنش zxid یا نسخه گره cversion می‌تواند توکن fencing باشد. چون monotonic افزایشی تضمین شده‌اند، ویژگی لازم را دارند [۷۴].

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

بررسی توکن سمت سرور شاید معایب به نظر برسد، اما خوب است: عاقلانه نیست سرویس فرض کند کلاینت‌ها همیشه خوب‌رفتارند، چون کلاینت‌ها اغلب توسط افرادی با اولویت‌های متفاوت از اپراتورهای سرویس اجرا می‌شوند [۷۶]. پس محافظت سرویس از کلاینت‌های سوءاستفاده‌کننده تصادفی ایده خوبی است.

خطاهای بیزانسی

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

در این کتاب فرض می‌کنیم گره‌ها غیرقابل اعتماد اما صادق‌اند: ممکن است کند باشند یا هرگز پاسخ ندهند (به‌خاطر خطا)، و وضعیتشان قدیمی باشد (به‌خاطر pause GC یا تأخیر شبکه)، اما اگر پاسخ دهند «حقیقت» می‌گویند: تا جایی که می‌دانند طبق پروتکل بازی می‌کنند.

مشکلات سیستم‌های توزیع‌شده اگر خطر «دروغ گفتن» گره‌ها (پاسخ‌های دلخواه معیوب یا فاسد) باشد بسیار سخت‌تر می‌شود — مثلاً گره ادعا کند پیامی را گرفته در حالی که نگرفته. این خطای بیزانسی (Byzantine fault) نامیده می‌شود و رسیدن به consensus در این محیط بی‌اعتماد مسئله فرماندهان بیزانسی (Byzantine Generals Problem) [۷۷] است.

مسئله فرماندهان بیزانسی

مسئله فرماندهان بیزانسی تعمیم مسئله دو فرمانده [۷۸] است: دو فرمانده ارتش باید روی نقشه نبرد توافق کنند. چون در دو اردوگاه‌اند، فقط با پیام‌رسان ارتباط دارند و پیام‌رسان‌ها گاهی تأخیر یا گم می‌شوند (مثل بسته در شبکه). این مسئله consensus را در فصل ۹ بحث می‌کنیم.

در نسخه بیزانسی، n فرمانده باید توافق کنند و در میانشان خائنین هستند. بیشتر فرماندهان وفادارند و پیام درست می‌فرستند، اما خائنین پیام جعلی یا نادرست می‌فرستند (در حالی که مخفی بمانند). از قبل معلوم نیست خائنین کی‌اند.

بیزانتیوم شهر یونانی باستان بود که بعداً قسطنطنیه شد — جایی که امروز استانبول در ترکیه است. شواهد تاریخی نشان نمی‌دهد فرماندهان بیزانتیوم بیش از جاهای دیگر توطئه‌چین بودند. نام از معنای بیزانسی به‌معنای بیش‌ازحد پیچیده، بوروکراتیک و فریبکار در سیاست، قبل از رایانه‌ها، می‌آید [۷۹]. Lamport می‌خواست ملیتی انتخاب کند که کسی را آزرده نکند و به او گفت «مسئله فرماندهان آلبانیایی» ایده خوبی نیست [۸۰].

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

• در محیط هوافضا، داده در حافظه یا رجیستر CPU ممکن است به‌خاطر تشعشع خراب شود و گره به شکل غیرقابل پیش‌بینی به گره‌های دیگر پاسخ دهد. چون خرابی سیستم بسیار گران است (سقوط هواپیما، برخورد موشک با ایستگاه فضایی)، سیستم‌های کنترل پرواز باید خطای بیزانسی را تحمل کنند [۸۱، ۸۲].
• در سیستمی با چند سازمان شرکت‌کننده، برخی ممکن است تقلب کنند. در چنین شرایطی امن نیست گره ساده به پیام گره دیگر اعتماد کند. شبکه‌های peer-to-peer مثل Bitcoin و blockchainها را می‌توان راهی برای توافق طرف‌های بی‌اعتماد درباره وقوع تراکنش بدون مرجع مرکزی دانست [۸۳].

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

برنامه‌های وب باید رفتار دلخواه و مخرب کلاینت‌های تحت کنترل کاربر نهایی (مثل مرورگر) را انتظار داشته باشند. به همین دلیل اعتبارسنجی ورودی، sanitization و escape خروجی مهم است: برای جلوگیری از SQL injection و cross-site scripting. اما اینجا معمولاً از پروتکل تحمل خطای بیزانسی استفاده نمی‌کنیم، بلکه سرور مرجع تصمیم درباره رفتار مجاز کلاینت است. در شبکه peer-to-peer بدون مرجع مرکزی، تحمل خطای بیزانسی مرتبط‌تر است.

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

به‌طور مشابه، جذاب است اگر پروتکل در برابر آسیب‌پذیری، نفوذ امنیتی و حمله محافظت کند. متأسفانه این هم واقع‌بینانه نیست: در بیشتر سیستم‌ها اگر مهاجم یک گره را compromise کند، احتمالاً همه را compromise می‌کند چون همان نرم‌افزار را اجرا می‌کنند. پس مکانیزم‌های سنتی (احراز هویت، کنترل دسترسی، رمزنگاری، firewall و غیره) همچنان محافظت اصلی در برابر مهاجمان‌اند.

اشکال ضعیف دروغ گفتن

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

• بسته‌های شبکه گاهی به‌خاطر سخت‌افزار یا باگ در سیستم‌عامل، driver، router و غیره خراب می‌شوند. معمولاً checksumهای TCP و UDP آن‌ها را می‌گیرند، اما گاهی از تشخیص فرار می‌کنند [۸۵، ۸۶، ۸۷]. اقدامات ساده مثل checksum در پروتکل سطح برنامه معمولاً کافی است.
• برنامه عمومی باید ورودی کاربران را با دقت sanitize کند: بررسی محدوده معقول، محدود کردن اندازه رشته برای جلوگیری از denial of service با تخصیص حافظه بزرگ. سرویس داخلی پشت firewall شاید بررسی کمتر داشته باشد، اما بررسی اولیه مقادیر (مثلاً در parse پروتکل [۸۵]) ایده خوبی است.
• کلاینت‌های NTP را می‌توان با چند آدرس سرور پیکربندی کرد. هنگام همگام‌سازی، همه را query می‌کند، خطا را تخمین می‌زند و بررسی می‌کند اکثریت سرورها در بازه زمانی توافق کنند. تا وقتی بیشتر سرورها سالم‌اند، سرور NTP misconfigure که زمان نادرست گزارش می‌کند outlier تشخیص و از همگام‌سازی حذف می‌شود [۳۷]. چند سرور NTP را مقاوم‌تر از یک سرور می‌کند.

مدل سیستم و واقعیت

الگوریتم‌های زیادی برای حل مشکلات سیستم‌های توزیع‌شده طراحی شده — مثلاً در فصل ۹ راه‌حل‌های consensus را می‌بینیم. برای مفید بودن، این الگوریتم‌ها باید خطاهای مختلف سیستم‌های توزیع‌شده‌ای که در این فصل بحث شد را تحمل کنند.

الگوریتم‌ها باید طوری نوشته شوند که زیاد به جزئیات پیکربندی سخت‌افزار و نرم‌افزار وابسته نباشند. این نیاز دارد نوعی خطاهای مورد انتظار را رسمی کنیم. این کار را با تعریف مدل سیستم (system model) انجام می‌دهیم — انتزاعی که توصیف می‌کند الگوریتم چه چیزهایی را می‌تواند فرض کند.

درباره فرض‌های زمان‌بندی، سه مدل سیستم رایج است:

مدل همگام (Synchronous model) مدل همگام فرض می‌کند تأخیر شبکه، pause فرآیند و خطای ساعت محدود است. این به معنای ساعت‌های کاملاً همگام یا تأخیر صفر شبکه نیست؛ فقط یعنی می‌دانید تأخیر شبکه، pause و drift ساعت از حد بالای ثابتی تجاوز نمی‌کند [۸۸]. مدل همگام برای بیشتر سیستم‌های عملی واقع‌بینانه نیست چون (همان‌طور که در این فصل دیدیم) تأخیر و pause نامحدود رخ می‌دهد.

مدل نیمه‌همگام (Partially synchronous model) نیمه‌همگامی یعنی سیستم بیشتر وقت‌ها همگام است، اما گاهی از حدود تأخیر شبکه، pause فرآیند و drift ساعت تجاوز می‌کند [۸۸]. این مدل واقع‌بینانه بسیاری از سیستم‌هاست: بیشتر وقت‌ها شبکه و فرآیندها خوب‌رفتارند — وگرنه کاری پیش نمی‌رود — اما باید بدانیم هر فرض زمان‌بندی گاهی نقض می‌شود. وقتی این اتفاق بیفتد، تأخیر شبکه، pause و خطای ساعت می‌تواند دلخواه بزرگ شود.

مدل ناهمگام (Asynchronous model) در این مدل، الگوریتم اجازه هیچ فرض زمان‌بندی ندارد — حتی ساعت هم ندارد (پس نمی‌تواند از timeout استفاده کند). برخی الگوریتم‌ها برای مدل ناهمگام طراحی می‌شوند، اما بسیار محدودکننده است.

علاوه بر زمان‌بندی، باید خرابی گره را در نظر گرفت. سه مدل رایج برای گره‌ها:

خطای crash-stop در مدل crash-stop، الگوریتم فرض می‌کند گره فقط یک‌طور خراب می‌شود: crash. یعنی گره ممکن است ناگهان پاسخ ندهد و بعد برای همیشه از بین برود — هرگز برنمی‌گردد.

خطای crash-recovery فرض می‌کنیم گره‌ها هر لحظه ممکن است crash کنند و شاید بعد از مدتی نامعلوم دوباره پاسخ دهند. در مدل crash-recovery، گره‌ها ذخیره‌سازی پایدار (دیسک غیرفرار) دارند که از crash حفظ می‌شود، اما وضعیت درون‌حافظه از دست می‌رود.

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

برای مدل‌سازی سیستم‌های واقعی، مدل نیمه‌همگام با خطای crash-recovery معمولاً مفیدترین است. اما الگوریتم‌های توزیع‌شده چگونه با این مدل کنار می‌آیند؟

صحت الگوریتم

برای تعریف صحت الگوریتم، ویژگی‌هایش را توصیف می‌کنیم. مثلاً خروجی الگوریتم مرتب‌سازی ویژگی دارد که برای هر دو عنصر متمایز خروجی، عنصر سمت چپ کوچک‌تر از عنصر سمت راست است. این تعریف رسمی «مرتب بودن» لیست است.

به همین ترتیب، ویژگی‌هایی که از الگوریتم توزیع‌شده می‌خواهیم را می‌نویسیم تا صحت را تعریف کنیم. مثلاً اگر توکن fencing برای قفل تولید می‌کنیم («توکن‌های fencing» در صفحه ۳۰۳)، ممکن است الگوریتم این ویژگی‌ها را بخواهد:

• یکتایی (Uniqueness): هیچ دو درخواست توکن fencing مقدار یکسان برنگرداند.
• دنباله monotonic (Monotonic sequence): اگر درخواست x توکن tx و درخواست y توکن ty برگرداند و x قبل از شروع y تمام شد، آنگاه tx < ty.
• دسترس‌پذیری (Availability): گرهی که توکن fencing می‌خواهد و crash نمی‌کند، در نهایت پاسخ می‌گیرد.

الگوریتم در مدل سیستم صحیح است اگر همیشه ویژگی‌هایش را در همه موقعیت‌هایی که در آن مدل ممکن است فرض می‌کنیم برآورده کند. اما این چگونه معنا دارد؟ اگر همه گره‌ها crash کنند یا همه تأخیرهای شبکه بی‌نهایت شوند، هیچ الگوریتمی کاری نمی‌تواند بکند.

ایمنی و زنده‌مانی

برای روشن‌سازی، دو نوع ویژگی را تفکیک می‌کنیم: ایمنی (safety) و زنده‌مانی (liveness). در مثال بالا، یکتایی و دنباله monotonic ویژگی ایمنی‌اند، اما دسترس‌پذیری ویژگی زنده‌مانی است.

تفاوت چیست؟ سرنخ این است که ویژگی‌های زنده‌مانی اغلب کلمه «در نهایت» (eventually) در تعریف دارند. (و بله — consistency نهایی ویژگی زنده‌مانی است [۸۹].)

ایمنی را غیررسمی «هیچ بدبختی رخ نمی‌دهد» و زنده‌مانی را «چیز خوبی در نهایت رخ می‌دهد» تعریف می‌کنند، اما بهتر است زیاد به این تعاریف غیررسمی تکیه نکنیم چون «خوب» و «بد» ذهنی‌اند. تعاریف واقعی ایمنی و زنده‌مانی دقیق و ریاضی‌اند [۹۰]:

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

مزیت تفکیک ایمنی و زنده‌مانی این است که با مدل‌های سیستم دشوار کنار می‌آید. برای الگوریتم‌های توزیع‌شده، رایج است ویژگی‌های ایمنی همیشه در همه موقعیت‌های ممکن مدل سیستم برقرار باشند [۸۸]. یعنی حتی اگر همه گره‌ها crash کنند یا کل شبکه خراب شود، الگوریتم نباید نتیجه اشتباه برگرداند (ویژگی‌های ایمنی برقرار بمانند).

اما برای ویژگی‌های زنده‌مانی می‌توان استثنا قائل شد: مثلاً بگوییم درخواست فقط اگر اکثریت گره‌ها crash نکرده‌اند و شبکه در نهایت از outage بازیابی شد پاسخ می‌گیرد. تعریف مدل نیمه‌همگام می‌خواهد سیستم در نهایت به حالت همگام برگردد — یعنی هر قطعی شبکه فقط مدت محدودی طول بکشد و بعد تعمیر شود.

نگاشت مدل سیستم به دنیای واقعی

ویژگی‌های ایمنی و زنده‌مانی و مدل‌های سیستم برای استدلال درباره صحت الگوریتم توزیع‌شده بسیار مفیدند. اما در پیاده‌سازی عملی، واقعیت آشفته دوباره گاز می‌گیرد و روشن می‌شود مدل سیستم انتزاع ساده‌شده واقعیت است.

مثلاً الگوریتم‌ها در مدل crash-recovery معمولاً فرض می‌کنند داده ذخیره‌سازی پایدار از crash جان سالم به در می‌برد. اما اگر داده روی دیسک خراب شود، یا به‌خاطر خطای سخت‌افزار یا misconfiguration پاک شود [۹۱]؟ اگر سرور باگ firmware داشته باشد و پس از reboot دیسک‌ها را نشناسد، با وجود اتصال درست [۹۲]؟

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

توصیف نظری الگوریتم می‌تواند بگوید برخی چیزها ساده فرض می‌شوند اتفاق نیفتند — و در سیستم‌های غیربیزانسی باید فرض‌هایی درباره خطاهای ممکن و غیرممکن داشته باشیم. اما پیاده‌سازی واقعی شاید هنوز کدی برای حالتی که «غیرممکن» فرض شده داشته باشد، حتی اگر فقط printf("Sucks to be you") و exit(666) باشد — یعنی اپراتور انسانی مرتب کند [۹۳]. (شاید این تفاوت علوم رایانه و مهندسی نرم‌افزار باشد.)

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

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

خلاصه

در این فصل طیف گسترده‌ای از مشکلات ممکن در سیستم‌های توزیع‌شده را بحث کردیم، از جمله:

• هر بار که بسته از شبکه می‌فرستید، ممکن است گم یا با تأخیر دلخواه برسد. پاسخ هم ممکن است گم یا تأخیر یابد، پس اگر پاسخ نگیرید، نمی‌دانید پیام رسیده یا نه.
• ساعت گره ممکن است با گره‌های دیگر به‌طور قابل توجهی out of sync باشد، ناگهان به جلو یا عقب بپرد، و تکیه به آن خطرناک است چون احتمالاً بازه خطای ساعت را خوب نمی‌دانید.
• فرآیند ممکن است در هر نقطه اجرا مدت قابل توجهی pause شود (شاید به‌خاطر GC stop-the-world)، توسط گره‌های دیگر مرده اعلام شود، و بدون اطلاع از pause دوباره زنده شود.

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

برای تحمل خطا، گام اول تشخیص است، اما حتی آن هم سخت است. بیشتر سیستم‌ها مکانیزم دقیق تشخیص خرابی گره ندارند، پس بیشتر الگوریتم‌های توزیع‌شده به timeout برای تشخیص در دسترس بودن گره راه‌دور متکی‌اند. اما timeout بین خرابی شبکه و گره تمایز نمی‌گذارد، و تأخیر متغیر شبکه گاهی باعث مظنون شدن نادرست crash گره می‌شود. گاهی گره در وضعیت تخریب‌شده است: مثلاً رابط Gigabit به‌خاطر باگ driver ناگهان به ۱ Kb/s throughput می‌رسد [۹۴]. گره «لنگان» اما نه مرده گاهی از گره تمیز خراب‌شده سخت‌تر است.

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

اگر به نوشتن نرم‌افزار در کمال ریاضی ایده‌آل یک رایانه عادت دارید — جایی که همان عملیات همیشه قطعاً همان نتیجه را می‌دهد — رفتن به واقعیت فیزیکی آشفته سیستم‌های توزیع‌شده شوک است. برعکس، مهندسان سیستم‌های توزیع‌شده اگر مسئله روی یک رایانه حل شود ساده می‌دانند [۵]، و درست است که یک رایانه امروز کار زیادی می‌کند [۹۵]. اگر بتوانید جعبه پاندورا را باز نکنید و همه چیز روی یک ماشین بماند، معمولاً ارزش دارد.

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

در این فصل هم به انحرافاتی پرداختیم که آیا غیرقابل اعتماد بودن شبکه، ساعت و فرآیندها قانون اجتناب‌ناپذیر طبیعت است. دیدیم نیست: می‌توان تضمین‌های پاسخ real-time سخت و تأخیر محدود در شبکه داد، اما بسیار گران است و بهره‌برداری سخت‌افزار را کم می‌کند. بیشتر سیستم‌های غیرایمنی‌بحرانی ارزان و غیرقابل اعتماد را به گران و قابل اعتماد ترجیح می‌دهند.

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

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

منابع

[1] Mark Cavage: "There's Just No Getting Around It: You're Building a Distributed System," ACM Queue, volume 11, number 4, pages 80-89, April 2013. doi:10.1145/2466486.2482856

[2] Jay Kreps: "Getting Real About Distributed System Reliability," blog.empathybox.com, March 19, 2012.

[3] Sydney Padua: The Thrilling Adventures of Lovelace and Babbage: The (Mostly) True Story of the First Computer. Particular Books, April 2015. ISBN: 978-0-141-98151-2

[4] Coda Hale: "You Can't Sacrifice Partition Tolerance," codahale.com, October 7, 2010.

[5] Jeff Hodges: "Notes on Distributed Systems for Young Bloods," somethingsimilar.com, January 14, 2013.

[6] Antonio Regalado: "Who Coined 'Cloud Computing'?," technologyreview.com, October 31, 2011.

[7] Luiz André Barroso, Jimmy Clidaras, and Urs Hölzle: "The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines, Second Edition," Synthesis Lectures on Computer Architecture, volume 8, number 3, Morgan & Claypool Publishers, July 2013. doi:10.2200/S00516ED2V01Y201306CAC024, ISBN: 978-1-627-05010-4

[8] David Fiala, Frank Mueller, Christian Engelmann, et al.: "Detection and Correction of Silent Data Corruption for Large-Scale High-Performance Computing," at International Conference for High Performance Computing, Networking, Storage and Analysis (SC12), November 2012.

[9] Arjun Singh, Joon Ong, Amit Agarwal, et al.: "Jupiter Rising: A Decade of Clos Topologies and Centralized Control in Google's Datacenter Network," at Annual Conference of the ACM Special Interest Group on Data Communication (SIGCOMM), August 2015. doi:10.1145/2785956.2787508

[10] Glenn K. Lockwood: "Hadoop's Uncomfortable Fit in HPC," glennklockwood.blogspot.co.uk, May 16, 2014.

[11] John von Neumann: "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components," in Automata Studies (AM-34), edited by Claude E. Shannon and John McCarthy, Princeton University Press, 1956. ISBN: 978-0-691-07916-5

[12] Richard W. Hamming: The Art of Doing Science and Engineering. Taylor & Francis, 1997. ISBN: 978-9-056-99500-3

[13] Claude E. Shannon: "A Mathematical Theory of Communication," The Bell System Technical Journal, volume 27, number 3, pages 379–423 and 623–656, July 1948.

[14] Peter Bailis and Kyle Kingsbury: "The Network Is Reliable," ACM Queue, volume 12, number 7, pages 48-55, July 2014. doi:10.1145/2639988.2639988

[15] Joshua B. Leners, Trinabh Gupta, Marcos K. Aguilera, and Michael Walfish: "Taming Uncertainty in Distributed Systems with Help from the Network," at 10th European Conference on Computer Systems (EuroSys), April 2015. doi:10.1145/2741948.2741976

[16] Phillipa Gill, Navendu Jain, and Nachiappan Nagappan: "Understanding Network Failures in Data Centers: Measurement, Analysis, and Implications," at ACM SIGCOMM Conference, August 2011. doi:10.1145/2018436.2018477

[17] Mark Imbriaco: "Downtime Last Saturday," github.com, December 26, 2012.

[18] Will Oremus: "The Global Internet Is Being Attacked by Sharks, Google Confirms," slate.com, August 15, 2014.

[19] Marc A. Donges: "Re: bnx2 cards Intermittantly Going Offline," Message to Linux netdev mailing list, spinics.net, September 13, 2012.

[20] Kyle Kingsbury: "Call Me Maybe: Elasticsearch," aphyr.com, June 15, 2014.

[21] Salvatore Sanfilippo: "A Few Arguments About Redis Sentinel Properties and Fail Scenarios," antirez.com, October 21, 2014.

[22] Bert Hubert: "The Ultimate SO_LINGER Page, or: Why Is My TCP Not Reliable," blog.netherlabs.nl, January 18, 2009.

[23] Nicolas Liochon: "CAP: If All You Have Is a Timeout, Everything Looks Like a Partition," blog.thislongrun.com, May 25, 2015.

[24] Jerome H. Saltzer, David P. Reed, and David D. Clark: "End-To-End Arguments in System Design," ACM Transactions on Computer Systems, volume 2, number 4, pages 277–288, November 1984. doi:10.1145/357401.357402

[25] Matthew P. Grosvenor, Malte Schwarzkopf, Ionel Gog, et al.: "Queues Don't Matter When You Can JUMP Them!," at 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI), May 2015.

[26] Guohui Wang and T. S. Eugene Ng: "The Impact of Virtualization on Network Performance of Amazon EC2 Data Center," at 29th IEEE International Conference on Computer Communications (INFOCOM), March 2010. doi:10.1109/INFCOM.2010.5461931

[27] Van Jacobson: "Congestion Avoidance and Control," at ACM Symposium on Communications Architectures and Protocols (SIGCOMM), August 1988. doi:10.1145/52324.52356

[28] Brandon Philips: "etcd: Distributed Locking and Service Discovery," at Strange Loop, September 2014.

[29] Steve Newman: "A Systematic Look at EC2 I/O," blog.scalyr.com, October 16, 2012.

[30] Naohiro Hayashibara, Xavier Défago, Rami Yared, and Takuya Katayama: "The ϕ Accrual Failure Detector," Japan Advanced Institute of Science and Technology, School of Information Science, Technical Report IS-RR-2004-010, May 2004.

[31] Jeffrey Wang: "Phi Accrual Failure Detector," ternarysearch.blogspot.co.uk, August 11, 2013.

[32] Srinivasan Keshav: An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network. Addison-Wesley Professional, May 1997. ISBN: 978-0-201-63442-6

[33] Cisco, "Integrated Services Digital Network," docwiki.cisco.com.

[34] Othmar Kyas: ATM Networks. International Thomson Publishing, 1995. ISBN: 978-1-850-32128-6

[35] "InfiniBand FAQ," Mellanox Technologies, December 22, 2014.

[36] Jose Renato Santos, Yoshio Turner, and G. (John) Janakiraman: "End-to-End Congestion Control for InfiniBand," at 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), April 2003. Also published by HP Laboratories Palo Alto, Tech Report HPL-2002-359. doi:10.1109/INFCOM.2003.1208949

[37] Ulrich Windl, David Dalton, Marc Martinec, and Dale R. Worley: "The NTP FAQ and HOWTO," ntp.org, November 2006.

[38] John Graham-Cumming: "How and why the leap second affected Cloudflare DNS," blog.cloudflare.com, January 1, 2017.

[39] David Holmes: "Inside the Hotspot VM: Clocks, Timers and Scheduling Events – Part I – Windows," blogs.oracle.com, October 2, 2006.

[40] Steve Loughran: "Time on Multi-Core, Multi-Socket Servers," steveloughran.blogspot.co.uk, September 17, 2015.

[41] James C. Corbett, Jeffrey Dean, Michael Epstein, et al.: "Spanner: Google's Globally-Distributed Database," at 10th USENIX Symposium on Operating System Design and Implementation (OSDI), October 2012.

[42] M. Caporaloni and R. Ambrosini: "How Closely Can a Personal Computer Clock Track the UTC Timescale Via the Internet?," European Journal of Physics, volume 23, number 4, pages L17–L21, June 2012. doi:10.1088/0143-0807/23/4/103

[43] Nelson Minar: "A Survey of the NTP Network," alumni.media.mit.edu, December 1999.

[44] Viliam Holub: "Synchronizing Clocks in a Cassandra Cluster Pt. 1 – The Problem," blog.logentries.com, March 14, 2014.

[45] Poul-Henning Kamp: "The One-Second War (What Time Will You Die?)," ACM Queue, volume 9, number 4, pages 44–48, April 2011. doi:10.1145/1966989.1967009

[46] Nelson Minar: "Leap Second Crashes Half the Internet," somebits.com, July 3, 2012.

[47] Christopher Pascoe: "Time, Technology and Leaping Seconds," googleblog.blogspot.co.uk, September 15, 2011.

[48] Mingxue Zhao and Jeff Barr: "Look Before You Leap – The Coming Leap Second and AWS," aws.amazon.com, May 18, 2015.

[49] Darryl Veitch and Kanthaiah Vijayalayan: "Network Timing and the 2015 Leap Second," at 17th International Conference on Passive and Active Measurement (PAM), April 2016. doi:10.1007/978-3-319-30505-9_29

[50] "Timekeeping in VMware Virtual Machines," Information Guide, VMware, Inc., December 2011.

[51] "MiFID II / MiFIR: Regulatory Technical and Implementing Standards – Annex I (Draft)," European Securities and Markets Authority, Report ESMA/2015/1464, September 2015.

[52] Luke Bigum: "Solving MiFID II Clock Synchronisation With Minimum Spend (Part 1)," lmax.com, November 27, 2015.

[53] Kyle Kingsbury: "Call Me Maybe: Cassandra," aphyr.com, September 24, 2013.

[54] John Daily: "Clocks Are Bad, or, Welcome to the Wonderful World of Distributed Systems," basho.com, November 12, 2013.

[55] Kyle Kingsbury: "The Trouble with Timestamps," aphyr.com, October 12, 2013.

[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] Sandeep Kulkarni, Murat Demirbas, Deepak Madeppa, et al.: "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases," State University of New York at Buffalo, Computer Science and Engineering Technical Report 2014-04, May 2014.

[58] Justin Sheehy: "There Is No Now: Problems With Simultaneity in Distributed Systems," ACM Queue, volume 13, number 3, pages 36–41, March 2015. doi:10.1145/2733108

[59] Murat Demirbas: "Spanner: Google's Globally-Distributed Database," muratbuffalo.blogspot.co.uk, July 4, 2013.

[60] Dahlia Malkhi and Jean-Philippe Martin: "Spanner's Concurrency Control," ACM SIGACT News, volume 44, number 3, pages 73–77, September 2013. doi:10.1145/2527748.2527767

[61] Manuel Bravo, Nuno Diegues, Jingna Zeng, et al.: "On the Use of Clocks to Enforce Consistency in the Cloud," IEEE Data Engineering Bulletin, volume 38, number 1, pages 18–31, March 2015.

[62] Spencer Kimball: "Living Without Atomic Clocks," cockroachlabs.com, February 17, 2016.

[63] Cary G. Gray and David R. Cheriton: "Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency," at 12th ACM Symposium on Operating Systems Principles (SOSP), December 1989. doi:10.1145/74850.74870

[64] Todd Lipcon: "Avoiding Full GCs in Apache HBase with MemStore-Local Allocation Buffers: Part 1," blog.cloudera.com, February 24, 2011.

[65] Martin Thompson: "Java Garbage Collection Distilled," mechanical-sympathy.blogspot.co.uk, July 16, 2013.

[66] Alexey Ragozin: "How to Tame Java GC Pauses? Surviving 16GiB Heap and Greater," java.dzone.com, June 28, 2011.

[67] Christopher Clark, Keir Fraser, Steven Hand, et al.: "Live Migration of Virtual Machines," at 2nd USENIX Symposium on Symposium on Networked Systems Design & Implementation (NSDI), May 2005.

[68] Mike Shaver: "fsyncers and Curveballs," shaver.off.net, May 25, 2008.

[69] Zhenyun Zhuang and Cuong Tran: "Eliminating Large JVM GC Pauses Caused by Background IO Traffic," engineering.linkedin.com, February 10, 2016.

[70] David Terei and Amit Levy: "Blade: A Data Center Garbage Collector," arXiv:1504.02578, April 13, 2015.

[71] Martin Maas, Tim Harris, Krste Asanović, and John Kubiatowicz: "Trash Day: Coordinating Garbage Collection in Distributed Systems," at 15th USENIX Workshop on Hot Topics in Operating Systems (HotOS), May 2015.

[72] "Predictable Low Latency," Cinnober Financial Technology AB, cinnober.com, November 24, 2013.

[73] Martin Fowler: "The LMAX Architecture," martinfowler.com, July 12, 2011.

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

[75] Enis Söztutar: "HBase and HDFS: Understanding Filesystem Usage in HBase," at HBaseCon, June 2013.

[76] Caitie McCaffrey: "Clients Are Jerks: AKA How Halo 4 DoSed the Services at Launch & How We Survived," caitiem.com, June 23, 2015.

[77] Leslie Lamport, Robert Shostak, and Marshall Pease: "The Byzantine Generals Problem," ACM Transactions on Programming Languages and Systems (TOPLAS), volume 4, number 3, pages 382–401, July 1982. doi:10.1145/357172.357176

[78] Jim N. Gray: "Notes on Data Base Operating Systems," in Operating Systems: An Advanced Course, Lecture Notes in Computer Science, volume 60, edited by R. Bayer, R. M. Graham, and G. Seegmüller, pages 393–481, Springer-Verlag, 1978. ISBN: 978-3-540-08755-7

[79] Brian Palmer: "How Complicated Was the Byzantine Empire?," slate.com, October 20, 2011.

[80] Leslie Lamport: "My Writings," research.microsoft.com, December 16, 2014. This page can be found by searching the web for the 23-character string obtained by removing the hyphens from the string alllamportspubsontheweb.

[81] John Rushby: "Bus Architectures for Safety-Critical Embedded Systems," at 1st International Workshop on Embedded Software (EMSOFT), October 2001.

[82] Jake Edge: "ELC: SpaceX Lessons Learned," lwn.net, March 6, 2013.

[83] Andrew Miller and Joseph J. LaViola, Jr.: "Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin," University of Central Florida, Technical Report CS-TR-14-01, April 2014.

[84] James Mickens: "The Saddest Moment," USENIX ;login: logout, May 2013.

[85] Evan Gilman: "The Discovery of Apache ZooKeeper's Poison Packet," pagerduty.com, May 7, 2015.

[86] Jonathan Stone and Craig Partridge: "When the CRC and TCP Checksum Disagree," at ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), August 2000. doi:10.1145/347059.347561

[87] Evan Jones: "How Both TCP and Ethernet Checksums Fail," evanjones.ca, October 5, 2015.

[88] 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

[89] 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

[90] Bowen Alpern and Fred B. Schneider: "Defining Liveness," Information Processing Letters, volume 21, number 4, pages 181–185, October 1985. doi:10.1016/0020-0190(85)90056-0

[91] Flavio P. Junqueira: "Dude, Where's My Metadata?," fpj.me, May 28, 2015.

[92] Scott Sanders: "January 28th Incident Report," github.com, February 3, 2016.

[93] Jay Kreps: "A Few Notes on Kafka and Jepsen," blog.empathybox.com, September 25, 2013.

[94] Thanh Do, Mingzhe Hao, Tanakorn Leesatapornwongsa, et al.: "Limplock: Understanding the Impact of Limpware on Scale-out Cloud Systems," at 4th ACM Symposium on Cloud Computing (SoCC), October 2013. doi:10.1145/2523616.2523627

[95] Frank McSherry, Michael Isard, and Derek G. Murray: "Scalability! But at What COST?," at 15th USENIX Workshop on Hot Topics in Operating Systems (HotOS), May 2015.