فصل ۵ — تکثیر

تفاوت اصلی بین چیزی که ممکن است خراب شود و چیزی که اصلاً نمی‌تواند خراب شود این است که وقتی چیزی که اصلاً نمی‌تواند خراب شود خراب می‌شود، معمولاً دسترسی به آن یا تعمیرش غیرممکن می‌شود. — داگلاس آدامز، Mostly Harmless (۱۹۹۲)

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

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

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

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

با تکثیر trade-offهای زیادی وجود دارد: مثلاً استفاده از تکثیر همگام یا ناهمگام، و نحوه برخورد با replicaهای خراب. این‌ها اغلب گزینه‌های پیکربندی در پایگاه‌های داده هستند، و هرچند جزئیات بسته به پایگاه داده متفاوت است، اصول کلی در پیاده‌سازی‌های مختلف مشابه است. پیامدهای چنین انتخاب‌هایی را در این فصل بحث می‌کنیم.

تکثیر پایگاه‌های داده موضوعی قدیمی است — اصول از دهه ۱۹۷۰ که مطالعه شدند تغییر زیادی نکرده‌اند [1]، چون محدودیت‌های بنیادی شبکه‌ها همان‌طور باقی مانده‌اند. با این حال، خارج از تحقیقات، بسیاری از توسعه‌دهندگان مدت‌ها فرض می‌کردند پایگاه داده فقط یک نود دارد. استفاده رایج از پایگاه‌های داده توزیع‌شده جدیدتر است. چون بسیاری از توسعه‌دهندگان برنامه در این حوزه تازه‌کارند، سوءتفاهم زیادی درباره مسائلی مثل سازگاری نهایی (eventual consistency) وجود دارد. در «مشکلات تأخیر تکثیر» در صفحه ۱۶۱ دقیق‌تر درباره سازگاری نهایی صحبت می‌کنیم و چیزهایی مثل تضمین‌های read-your-writes و خواندن یکنواخت (monotonic reads) را بررسی می‌کنیم.

رهبرها و پیروان

هر نودی که یک کپی از پایگاه داده را نگه می‌دارد replica نامیده می‌شود. با چند replica، پرسشی ناگزیر مطرح می‌شود: چگونه مطمئن شویم همه داده به همه replicaها می‌رسد؟

هر نوشتن به پایگاه داده باید توسط هر replica پردازش شود؛ وگرنه replicaها دیگر همان داده را ندارند. رایج‌ترین راه‌حل برای این مسئله تکثیر مبتنی بر رهبر (leader-based replication؛ که active/passive یا master–slave replication هم نامیده می‌شود) است و در شکل ۵-۱ نشان داده شده. این‌طور کار می‌کند:

1. یکی از replicaها به‌عنوان رهبر (leader؛ که master یا primary هم نامیده می‌شود) تعیین می‌شود. وقتی clientها می‌خواهند به پایگاه داده بنویسند، باید درخواست‌هایشان را به رهبر بفرستند؛ رهبر ابتدا داده جدید را در ذخیره‌سازی محلی خود می‌نویسد.
2. replicaهای دیگر پیرو (follower؛ read replica، slave، secondary، یا hot standby) نامیده می‌شوند.i هر وقت رهبر داده جدید را در ذخیره‌سازی محلی می‌نویسد، تغییر داده را هم به همه پیروانش به‌عنوان بخشی از لاگ تکثیر یا جریان تغییر (change stream) می‌فرستد. هر پیرو لاگ را از رهبر می‌گیرد و کپی محلی پایگاه داده را مطابق آن به‌روزرسانی می‌کند، با اعمال همه نوشتن‌ها به همان ترتیبی که روی رهبر پردازش شدند.
3. وقتی client می‌خواهد از پایگاه داده بخواند، می‌تواند از رهبر یا هر یک از پیروان پرس‌وجو کند. با این حال، نوشتن فقط روی رهبر پذیرفته می‌شود (از دید client، پیروان فقط خواندنی هستند).

i. افراد مختلف تعاریف متفاوتی برای سرورهای standby داغ (hot)، گرم (warm)، و سرد (cold) دارند. در PostgreSQL مثلاً hot standby برای replicaای به کار می‌رود که خواندن از clientها را می‌پذیرد، در حالی که warm standby تغییرات رهبر را پردازش می‌کند اما پرس‌وجوی client را پردازش نمی‌کند. برای اهداف این کتاب، تفاوت مهم نیست.

شکل ۵-۱. تکثیر مبتنی بر رهبر (master–slave).

این حالت تکثیر ویژگی داخلی بسیاری از پایگاه‌های داده رابطه‌ای است، مثل PostgreSQL (از نسخه ۹.۰)، MySQL، Oracle Data Guard [2]، و AlwaysOn Availability Groups در SQL Server [3]. در برخی پایگاه‌های داده غیررابطه‌ای هم استفاده می‌شود، از جمله MongoDB، RethinkDB، و Espresso [4]. در نهایت، تکثیر مبتنی بر رهبر محدود به پایگاه‌های داده نیست: کارگزارهای پیام توزیع‌شده مثل Kafka [5] و صف‌های با دسترس‌پذیری بالا در RabbitMQ [6] هم از آن استفاده می‌کنند. برخی سیستم‌فایل‌های شبکه‌ای و دستگاه‌های بلوک تکثیرشده مثل DRBD هم مشابه‌اند.

تکثیر همگام در مقابل ناهمگام

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

به شکل ۵-۱ فکر کنید، جایی که کاربر یک وب‌سایت تصویر پروفایلش را به‌روزرسانی می‌کند. در نقطه‌ای، client درخواست به‌روزرسانی را به رهبر می‌فرستد؛ اندکی بعد، رهبر آن را دریافت می‌کند. در نقطه‌ای، رهبر تغییر داده را به پیروان می‌فرستد. در نهایت، رهبر به client اطلاع می‌دهد که به‌روزرسانی موفق بود.

شکل ۵-۲ ارتباط بین اجزای مختلف سیستم را نشان می‌دهد: client کاربر، رهبر، و دو پیرو. زمان از چپ به راست جریان دارد. پیام درخواست یا پاسخ با فلش ضخیم نشان داده شده.

شکل ۵-۲. تکثیر مبتنی بر رهبر با یک پیروی همگام و یک پیروی ناهمگام.

در مثال شکل ۵-۲، تکثیر به پیرو ۱ همگام است: رهبر منتظر می‌ماند تا پیرو ۱ تأیید کند که نوشتن را دریافت کرده، قبل از گزارش موفقیت به کاربر و قبل از قابل مشاهده کردن نوشتن برای clientهای دیگر. تکثیر به پیرو ۲ ناهمگام است: رهبر پیام را می‌فرستد، اما منتظر پاسخ از پیرو نمی‌ماند.

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

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

به همین دلیل، غیرعملی است همه پیروان همگام باشند: خرابی هر نود باعث توقف کل سیستم می‌شود. در عمل، اگر تکثیر همگام را در پایگاه داده فعال کنید، معمولاً یعنی یکی از پیروان همگام است و بقیه ناهمگام. اگر پیروی همگام در دسترس نباشد یا کند شود، یکی از پیروان ناهمگام همگام می‌شود. این تضمین می‌کند حداقل روی دو نود کپی به‌روز داده دارید: رهبر و یک پیروی همگام. این پیکربندی گاهی نیمه‌همگام (semi-synchronous) [7] هم نامیده می‌شود.

اغلب، تکثیر مبتنی بر رهبر کاملاً ناهمگام پیکربندی می‌شود. در این حالت، اگر رهبر خراب شود و قابل بازیابی نباشد، هر نوشتنی که هنوز به پیروان تکثیر نشده از دست می‌رود. یعنی نوشتن تضمین ماندگاری (durability) ندارد، حتی اگر به client تأیید شده باشد. با این حال، پیکربندی کاملاً ناهمگام مزیت دارد که رهبر می‌تواند به پردازش نوشتن ادامه دهد، حتی اگر همه پیروان عقب مانده باشند.

ضعیف کردن ماندگاری شاید trade-off بدی به نظر برسد، اما تکثیر ناهمگام با این حال به‌طور گسترده استفاده می‌شود، به‌ویژه اگر پیروان زیاد باشند یا جغرافیایی توزیع شده باشند. در «مشکلات تأخیر تکثیر» در صفحه ۱۶۱ به این مسئله برمی‌گردیم.

تحقیق درباره تکثیر

از دست رفتن داده در سیستم‌های تکثیرشده ناهمگام وقتی رهبر خراب می‌شود می‌تواند مشکل جدی باشد، بنابراین پژوهشگران به بررسی روش‌های تکثیر که داده از دست نمی‌دهند اما همچنان عملکرد و دسترس‌پذیری خوبی ارائه می‌دهند ادامه داده‌اند. مثلاً chain replication [8, 9] گونه‌ای از تکثیر همگام است که در چند سیستم مثل Microsoft Azure Storage [10, 11] با موفقیت پیاده‌سازی شده. ارتباط قوی بین سازگاری تکثیر و اجماع (توافق چند نود روی یک مقدار) وجود دارد، و این حوزه نظری را در فصل ۹ با جزئیات بیشتر بررسی می‌کنیم. در این فصل روی اشکال ساده‌تر تکثیر که در عمل در پایگاه‌های داده رایج‌تر است تمرکز می‌کنیم.

راه‌اندازی پیروان جدید

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

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

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

1. در نقطه‌ای از زمان، snapshot سازگار از پایگاه داده رهبر بگیرید — در صورت امکان، بدون قفل کردن کل پایگاه داده. بیشتر پایگاه‌های داده این قابلیت را دارند، چون برای پشتیبان‌گیری هم لازم است. در برخی موارد، ابزارهای شخص ثالث لازم است، مثل innobackupex برای MySQL [12].
2. snapshot را به نود پیروی جدید کپی کنید.
3. پیرو به رهبر متصل شود و همه تغییرات داده‌ای را که از زمان گرفتن snapshot رخ داده درخواست کند. این نیاز دارد snapshot با موقعیت دقیقی در لاگ تکثیر رهبر مرتبط باشد. آن موقعیت نام‌های مختلف دارد: مثلاً PostgreSQL آن را log sequence number می‌نامد، و MySQL binlog coordinates.
4. وقتی پیرو backlog تغییرات داده از زمان snapshot را پردازش کرد، می‌گوییم به‌روز شده (caught up). حالا می‌تواند به پردازش تغییرات داده از رهبر همان‌طور که رخ می‌دهند ادامه دهد.

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

مدیریت خروج نود از سرویس

هر نودی در سیستم ممکن است از سرویس خارج شود، شاید به‌طور غیرمنتظره به‌خاطر خرابی، اما به همان اندازه احتمالاً به‌خاطر نگهداری برنامه‌ریزی‌شده (مثلاً reboot ماشین برای نصب patch امنیتی kernel). توانایی reboot نودهای جداگانه بدون downtime مزیت بزرگی برای عملیات و نگهداری است. بنابراین، هدف ما این است که سیستم به‌عنوان کل در برابر خرابی نودهای جداگانه به کار ادامه دهد، و تأثیر خروج نود را تا حد امکان کوچک نگه داریم.

چگونه با تکثیر مبتنی بر رهبر دسترس‌پذیری بالا به دست آورید؟

خرابی پیرو: بازیابی با جبران عقب‌ماندگی

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

خرابی رهبر: failover

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

failover می‌تواند دستی باشد (به مدیر اطلاع داده می‌شود رهبر خراب شده و مراحل لازم برای ساخت رهبر جدید را انجام می‌دهد) یا خودکار. فرآیند failover خودکار معمولاً شامل این مراحل است:

1. تشخیص اینکه رهبر خراب شده. چیزهای زیادی ممکن است خراب شود: crash، قطع برق، مشکلات شبکه، و بیشتر. راه قطعی برای تشخیص چه چیزی خراب شده وجود ندارد، بنابراین بیشتر سیستم‌ها از timeout استفاده می‌کنند: نودها مرتب پیام‌ها را بین خود رد و بدل می‌کنند، و اگر نودی برای مدتی — مثلاً ۳۰ ثانیه — پاسخ ندهد، مرده فرض می‌شود. (اگر رهبر عمداً برای نگهداری برنامه‌ریزی‌شده خاموش شود، این اعمال نمی‌شود.)
2. انتخاب رهبر جدید. این می‌تواند از طریق فرآیند انتخاباب (election) انجام شود (رهبر توسط اکثریت replicaهای باقی‌مانده انتخاب می‌شود)، یا رهبر جدید توسط نود کنترل‌کننده‌ای که قبلاً انتخاب شده منصوب شود. بهترین کاندید برای رهبری معمولاً replicaای است که به‌روزترین تغییرات داده را از رهبر قدیمی دارد (برای کمینه کردن از دست رفتن داده). توافق همه نودها روی رهبر جدید مسئله اجماع است که در فصل ۹ با جزئیات بحث می‌شود.
3. پیکربندی مجدد سیستم برای استفاده از رهبر جدید. clientها حالا باید درخواست‌های نوشتن را به رهبر جدید بفرستند (در «مسیریابی درخواست» در صفحه ۲۱۴ بحث می‌کنیم). اگر رهبر قدیمی برگردد، ممکن است هنوز فکر کند رهبر است و نداند replicaهای دیگر آن را مجبور به کناره‌گیری کرده‌اند. سیستم باید مطمئن شود رهبر قدیمی پیرو شود و رهبر جدید را بشناسد.

failover پر از چیزهایی است که ممکن است خراب شود:

• اگر تکثیر ناهمگام استفاده شود، رهبر جدید ممکن است همه نوشتن‌های رهبر قدیمی را قبل از خرابی دریافت نکرده باشد. اگر رهبر قدیمی بعد از انتخاب رهبر جدید به کلاستر برگردد، با آن نوشتن‌ها چه باید کرد؟ رهبر جدید ممکن است در این فاصله نوشتن‌های متعارض دریافت کرده باشد. رایج‌ترین راه‌حل این است که نوشتن‌های تکثیرنشده رهبر قدیمی ساده دور ریخته شوند، که ممکن است انتظارات ماندگاری clientها را نقض کند.
• دور ریختن نوشتن‌ها به‌ویژه خطرناک است اگر سیستم‌های ذخیره‌سازی دیگر خارج از پایگاه داده باید با محتوای پایگاه هماهنگ شوند. مثلاً در یک حادثه در GitHub [13]، یک پیروی MySQL قدیمی به رهبر ارتقا یافت. پایگاه داده از شمارنده autoincrementing برای اختصاص کلیدهای اصلی به سطرهای جدید استفاده می‌کرد، اما چون شمارنده رهبر جدید از رهبر قدیمی عقب بود، برخی کلیدهای اصلی که قبلاً توسط رهبر قدیمی اختصاص یافته بودند دوباره استفاده شدند. این کلیدهای اصلی در Redis هم استفاده می‌شدند، بنابراین استفاده مجدد از کلیدهای اصلی باعث ناسازگاری بین MySQL و Redis شد که منجر به افشای داده خصوصی به کاربران اشتباه شد.
• در برخی سناریوهای خرابی (فصل ۸ را ببینید)، ممکن است دو نود هر دو فکر کنند رهبر هستند. این وضعیت split brain نامیده می‌شود و خطرناک است: اگر هر دو رهبر نوشتن بپذیرند و فرآیندی برای حل تعارض وجود نداشته باشد (به «تکثیر چند رهبره» در صفحه ۱۶۸ مراجعه کنید)، احتمالاً داده از دست می‌رود یا خراب می‌شود. به‌عنوان مکانیزم ایمنی، برخی سیستم‌ها اگر دو رهبر تشخیص داده شود یک نود را خاموش می‌کنند.ii با این حال، اگر این مکانیزم با دقت طراحی نشود، ممکن است هر دو نود خاموش شوند [14].

ii. این رویکرد fencing نامیده می‌شود، یا با تأکید بیشتر، Shoot The Other Node In The Head (STONITH). fencing را در «رهبر و قفل» در صفحه ۳۰۱ با جزئیات بیشتر بحث می‌کنیم.

• timeout مناسب قبل از اعلام مردن رهبر چقدر است؟ timeout طولانی‌تر یعنی زمان بازیابی بیشتر وقتی رهبر خراب می‌شود. با این حال، اگر timeout خیلی کوتاه باشد، ممکن است failoverهای غیرضروری رخ دهد. مثلاً، spike موقت بار ممکن است زمان پاسخ نود را بالای timeout ببرد، یا مشکل شبکه ممکن است باعث تأخیر بسته‌ها شود. اگر سیستم از قبل با بار بالا یا مشکلات شبکه در تلاش است، failover غیرضروری احتمالاً وضعیت را بدتر می‌کند، نه بهتر.

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

این مسائل — خرابی نود؛ شبکه‌های غیرقابل اعتماد؛ و trade-offهای سازگاری replica، ماندگاری، دسترس‌پذیری، و تأخیر — در واقع مسائل بنیادی در سیستم‌های توزیع‌شده هستند. در فصل ۸ و فصل ۹ با عمق بیشتر بحث می‌کنیم.

پیاده‌سازی لاگ‌های تکثیر

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

تکثیر مبتنی بر statement

در ساده‌ترین حالت، رهبر هر درخواست نوشتن (statement) که اجرا می‌کند را لاگ می‌کند و آن لاگ statement را به پیروان می‌فرستد. برای پایگاه داده رابطه‌ای، یعنی هر statement از نوع INSERT، UPDATE، یا DELETE به پیروان فوروارد می‌شود، و هر پیرو آن statement SQL را parse و اجرا می‌کند، گویی از client دریافت کرده.

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

• هر statementای که تابع غیرقطعی مثل NOW() برای تاریخ و زمان فعلی یا RAND() برای عدد تصادفی را فراخوانی کند، احتمالاً مقدار متفاوتی روی هر replica تولید می‌کند.
• اگر statementها از ستون autoincrementing استفاده کنند، یا به داده موجود در پایگاه وابسته باشند (مثلاً UPDATE … WHERE <some condition>)، باید دقیقاً به همان ترتیب روی هر replica اجرا شوند، وگرنه ممکن است اثر متفاوتی داشته باشند. این می‌تواند محدودکننده باشد وقتی چند تراکنش هم‌زمان در حال اجرا هستند.
• statementهایی با side effect (مثلاً trigger، stored procedure، تابع تعریف‌شده توسط کاربر) ممکن است باعث side effectهای متفاوت روی هر replica شوند، مگر side effectها کاملاً قطعی باشند.

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

تکثیر مبتنی بر statement در MySQL قبل از نسخه ۵.۱ استفاده می‌شد. گاهی امروز هم استفاده می‌شود، چون نسبتاً فشرده است، اما به‌طور پیش‌فرض MySQL حالا اگر غیرقطعی در statement باشد به تکثیر مبتنی بر سطر (row-based replication؛ که به‌زودی بحث می‌شود) سوئیچ می‌کند. VoltDB از تکثیر مبتنی بر statement استفاده می‌کند و با الزام قطعی بودن تراکنش‌ها آن را ایمن می‌کند [15].

ارسال لاگ write-ahead (WAL shipping)

در فصل ۳ بحث کردیم موتورهای ذخیره‌سازی چگونه داده را روی دیسک نمایش می‌دهند، و دیدیم معمولاً هر نوشتن به لاگ اضافه می‌شود:

• در مورد موتور ذخیره‌سازی ساختاریافته بر پایه لاگ (به «SSTableها و درخت‌های LSM» در صفحه ۷۶ مراجعه کنید)، این لاگ محل اصلی ذخیره‌سازی است. بخش‌های لاگ در پس‌زمینه فشرده و garbage-collect می‌شوند.
• در مورد درخت B (به «درخت‌های B» در صفحه ۷۹)، که بلوک‌های دیسک جداگانه را بازنویسی می‌کند، هر تغییر ابتدا به write-ahead log نوشته می‌شود تا ایندکس بعد از crash به حالت سازگار بازگردد.

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

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

این روش تکثیر در PostgreSQL و Oracle و غیره استفاده می‌شود [16]. معایب اصلی این است که لاگ داده را در سطح بسیار پایین توصیف می‌کند: WAL جزئیات اینکه کدام بایت‌ها در کدام بلوک‌های دیسک تغییر کرده‌اند را شامل می‌شود. این تکثیر را به موتور ذخیره‌سازی وابسته می‌کند. اگر پایگاه داده قالب ذخیره‌سازی را از یک نسخه به نسخه دیگر تغییر دهد، معمولاً نمی‌توان نسخه‌های مختلف نرم‌افزار پایگاه داده را روی رهبر و پیروان اجرا کرد.

این شاید جزئیات پیاده‌سازی کوچکی به نظر برسد، اما می‌تواند تأثیر عملیاتی بزرگی داشته باشد. اگر پروتکل تکثیر اجازه دهد پیرو از نسخه نرم‌افزار جدیدتر از رهبر استفاده کند، می‌توانید با ابتدا ارتقای پیروان و سپس failover برای تبدیل یکی از نودهای ارتقایافته به رهبر جدید، ارتقای بدون downtime نرم‌افزار پایگاه داده انجام دهید. اگر پروتکل تکثیر این عدم تطابق نسخه را اجازه ندهد، همان‌طور که اغلب با WAL shipping است، چنین ارتقاهایی نیاز به downtime دارند.

تکثیر لاگ منطقی (مبتنی بر سطر)

جایگزین استفاده از قالب‌های لاگ متفاوت برای تکثیر و برای موتور ذخیره‌سازی است، که اجازه می‌دهد لاگ تکثیر از جزئیات داخلی موتور ذخیره‌سازی جدا شود. این نوع لاگ تکثیر لاگ منطقی (logical log) نامیده می‌شود، برای تمایز از نمایش (فیزیکی) داده موتور ذخیره‌سازی.

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

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

تراکنشی که چند سطر را تغییر می‌دهد چند رکورد لاگ از این نوع تولید می‌کند، به‌دنبال رکوردی که نشان می‌دهد تراکنش commit شده. binlog در MySQL (وقتی برای تکثیر مبتنی بر سطر پیکربندی شده) از این رویکرد استفاده می‌کند [17].

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

قالب لاگ منطقی برای برنامه‌های خارجی هم parse کردن آسان‌تر است. این جنبه مفید است اگر بخواهید محتوای پایگاه داده را به سیستم خارجی بفرستید، مثل data warehouse برای تحلیل آفلاین، یا برای ساخت ایندکس‌ها و cache سفارشی [18]. این تکنیک change data capture نامیده می‌شود و در فصل ۱۱ به آن برمی‌گردیم.

تکثیر مبتنی بر trigger

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

برخی ابزارها، مثل Oracle GoldenGate [19]، می‌توانند تغییرات داده را با خواندن لاگ پایگاه داده در دسترس برنامه قرار دهند. جایگزین استفاده از قابلیت‌هایی است که در بسیاری پایگاه‌های داده رابطه‌ای موجود است: trigger و stored procedure.

trigger به شما اجازه می‌دهد کد برنامه سفارشی ثبت کنید که وقتی تغییر داده (تراکنش نوشتن) در سیستم پایگاه داده رخ می‌دهد، به‌صورت خودکار اجرا شود. trigger فرصت دارد این تغییر را در جدول جداگانه‌ای لاگ کند، که فرآیند خارجی می‌تواند آن را بخواند. آن فرآیند خارجی می‌تواند هر منطق برنامه لازم را اعمال کند و تغییر داده را به سیستم دیگر تکثیر کند. Databus برای Oracle [20] و Bucardo برای Postgres [21] مثلاً این‌طور کار می‌کنند.

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

مشکلات تأخیر تکثیر

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

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

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

متأسفانه، اگر برنامه از پیروی ناهمگام بخواند، ممکن است اطلاعات قدیمی ببیند اگر پیرو عقب مانده باشد. این به ناسازگاری ظاهری در پایگاه داده منجر می‌شود: اگر همان پرس‌وجو را همزمان روی رهبر و پیرو اجرا کنید، ممکن است نتایج متفاوت بگیرید، چون همه نوشتن‌ها در پیرو منعکس نشده. این ناسازگاری فقط حالت موقت است — اگر به پایگاه داده نوشتن را متوقف کنید و کمی صبر کنید، پیروان در نهایت به‌روز می‌شوند و با رهبر سازگار می‌شوند. به همین دلیل، این اثر سازگاری نهایی (eventual consistency) [22, 23] نامیده می‌شود.iii

واژه «نهایی» (eventually) عمداً مبهم است: به‌طور کلی، محدودیتی برای میزان عقب‌ماندگی replica وجود ندارد. در عمل عادی، تأخیر بین نوشتن روی رهبر و انعکاس روی پیرو — تأخیر تکثیر (replication lag) — ممکن است فقط کسری از ثانیه باشد و در عمل قابل توجه نباشد. با این حال، اگر سیستم نزدیک ظرفیت کار کند یا مشکل شبکه باشد، تأخیر به‌راحتی به چند ثانیه یا حتی چند دقیقه افزایش می‌یابد.

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

خواندن نوشتارهای خودتان

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

با تکثیر ناهمگام، مشکلی وجود دارد که در شکل ۵-۳ نشان داده شده: اگر کاربر اندکی بعد از نوشتن داده را ببیند، ممکن است داده جدید هنوز به replica نرسیده باشد. برای کاربر، به نظر می‌رسد داده‌ای که ارسال کرده گم شده، بنابراین طبیعتاً ناراضی می‌شود.

شکل ۵-۳. کاربر نوشتن انجام می‌دهد، سپس از replica قدیمی می‌خواند. برای جلوگیری از این ناهنجاری، به سازگاری خواندن پس از نوشتن (read-after-write consistency) نیاز داریم.

در این وضعیت، به سازگاری خواندن پس از نوشتن (read-after-write consistency)، که read-your-writes consistency [24] هم نامیده می‌شود، نیاز داریم. این تضمینی است که اگر کاربر صفحه را reload کند، همیشه به‌روزرسانی‌هایی که خودش ارسال کرده را ببیند. درباره کاربران دیگر وعده‌ای نمی‌دهد: به‌روزرسانی‌های دیگر کاربران ممکن است تا زمان بعدی قابل مشاهده نباشند. با این حال، به کاربر اطمینان می‌دهد ورودی خودش درست ذخیره شده.

چگونه سازگاری خواندن پس از نوشتن را در سیستمی با تکثیر مبتنی بر رهبر پیاده‌سازی کنیم؟ تکنیک‌های مختلفی ممکن است. چند مورد:

• وقتی چیزی را می‌خوانید که کاربر ممکن است تغییر داده باشد، از رهبر بخوانید؛ در غیر این صورت از پیرو. این نیاز دارد راهی برای دانستن اینکه آیا چیزی ممکن است تغییر کرده باشد، بدون پرس‌وجوی واقعی آن. مثلاً اطلاعات پروفایل کاربر در شبکه اجتماعی معمولاً فقط توسط مالک پروفایل قابل ویرایش است، نه هر کس دیگر. بنابراین، قاعده ساده: همیشه پروفایل خود کاربر را از رهبر بخوانید، و پروفایل هر کاربر دیگر را از پیرو.
• اگر بیشتر چیزها در برنامه توسط کاربر قابل ویرایش باشند، آن رویکرد مؤثر نیست، چون بیشتر چیزها باید از رهبر خوانده شوند (مزیت مقیاس‌پذیری خواندن را باطل می‌کند). در آن حالت، معیارهای دیگر برای تصمیم خواندن از رهبر استفاده می‌شود. مثلاً می‌توانید زمان آخرین به‌روزرسانی را ردیابی کنید و برای یک دقیقه بعد از آخرین به‌روزرسانی، همه خواندن‌ها را از رهبر انجام دهید. همچنین می‌توانید تأخیر تکثیر روی پیروان را پایش کنید و پرس‌وجو روی هر پیروی که بیش از یک دقیقه از رهبر عقب است را جلوگیری کنید.
• client می‌تواند timestamp آخرین نوشتن خود را به خاطر بسپارد — سپس سیستم می‌تواند مطمئن شود replicaای که خواندن‌های آن کاربر را سرویس می‌دهد به‌روزرسانی‌هایی را تا آن timestamp منعکس کند. اگر replica به‌اندازه کافی به‌روز نباشد، یا خواندن توسط replica دیگر انجام می‌شود یا پرس‌وجو منتظر می‌ماند تا replica به‌روز شود. timestamp می‌تواند timestamp منطقی (چیزی که ترتیب نوشتن‌ها را نشان می‌دهد، مثل log sequence number) یا ساعت واقعی سیستم باشد (که در آن صورت همگام‌سازی ساعت بحرانی می‌شود؛ به «ساعت‌های غیرقابل اعتماد» در صفحه ۲۸۷ مراجعه کنید).
• اگر replicaها در چند datacenter توزیع شده‌اند (برای نزدیکی جغرافیایی به کاربران یا دسترس‌پذیری)، پیچیدگی اضافی وجود دارد. هر درخواستی که باید توسط رهبر سرویس شود باید به datacenter حاوی رهبر مسیریابی شود.

پیچیدگی دیگر وقتی همان کاربر از چند دستگاه به سرویس شما دسترسی دارد، مثلاً مرورگر وب دسکتاپ و اپ موبایل. در این حالت ممکن است بخواهید سازگاری خواندن پس از نوشتن بین دستگاه‌ها (cross-device read-after-write consistency) فراهم کنید: اگر کاربر اطلاعاتی روی یک دستگاه وارد کند و روی دستگاه دیگر ببیند، باید اطلاعاتی که تازه وارد کرده را ببیند.

در این حالت، مسائل اضافی برای در نظر گرفتن وجود دارد:

• رویکردهایی که به خاطر سپردن timestamp آخرین به‌روزرسانی کاربر نیاز دارند سخت‌تر می‌شوند، چون کد روی یک دستگاه نمی‌داند چه به‌روزرسانی‌هایی روی دستگاه دیگر رخ داده. این metadata باید متمرکز شود.
• اگر replicaها در datacenterهای مختلف توزیع شده‌اند، تضمینی نیست اتصال از دستگاه‌های مختلف به همان datacenter مسیریابی شود. (مثلاً اگر کامپیوتر دسکتاپ کاربر از اتصال broadband خانگی و دستگاه موبایل از شبکه داده سلولی استفاده کند، مسیرهای شبکه دستگاه‌ها ممکن است کاملاً متفاوت باشند.) اگر رویکرد شما نیاز به خواندن از رهبر دارد، ممکن است ابتدا لازم باشد درخواست‌های همه دستگاه‌های یک کاربر به همان datacenter مسیریابی شوند.

خواندن یکنواخت

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

این می‌تواند رخ دهد اگر کاربر چند خواندن از replicaهای مختلف انجام دهد. مثلاً شکل ۵-۴ نشان می‌دهد کاربر ۲۳۴۵ همان پرس‌وجو را دو بار انجام می‌دهد، ابتدا از پیروی با تأخیر کم، سپس از پیروی با تأخیر بیشتر. (این سناریو اگر کاربر صفحه وب را refresh کند و هر درخواست به سرور تصادفی مسیریابی شود، کاملاً محتمل است.) پرس‌وجوی اول نظری را برمی‌گرداند که اخیراً توسط کاربر ۱۲۳۴ اضافه شده، اما پرس‌وجوی دوم چیزی برنمی‌گرداند چون پیروی عقب‌مانده هنوز آن نوشتن را دریافت نکرده. در عمل، پرس‌وجوی دوم سیستم را در نقطه زمانی زودتر از پرس‌وجوی اول مشاهده می‌کند. اگر پرس‌وجوی اول چیزی برنگردانده بود، چندان بد نبود، چون کاربر ۲۳۴۵ احتمالاً نمی‌دانست کاربر ۱۲۳۴ اخیراً نظری اضافه کرده. با این حال، برای کاربر ۲۳۴۵ بسیار گیج‌کننده است اگر ابتدا نظر کاربر ۱۲۳۴ را ببیند و سپس دوباره ناپدید شود.

شکل ۵-۴. کاربر ابتدا از replica تازه می‌خواند، سپس از replica قدیمی. زمان به نظر به عقب می‌رود. برای جلوگیری از این ناهنجاری، به خواندن یکنواخت (monotonic reads) نیاز داریم.

خواندن یکنواخت (monotonic reads) [23] تضمینی است که این نوع ناهنجاری رخ ندهد. تضمین ضعیف‌تری نسبت به سازگاری قوی (strong consistency) است، اما تضمین قوی‌تری نسبت به سازگاری نهایی. وقتی داده می‌خوانید، ممکن است مقدار قدیمی ببینید؛ خواندن یکنواخت فقط یعنی اگر یک کاربر چند خواندن پشت سر هم انجام دهد، زمان به عقب نرود — یعنی بعد از خواندن داده جدیدتر، داده قدیمی‌تر نخواند.

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

خواندن پیشوند سازگار

مثال سوم ناهنجاری‌های تأخیر تکثیر نقض علیّت (causality) است. این گفتگوی کوتاه بین آقای Poons و خانم Cake را تصور کنید:

آقای Poons: چقدر به آینده می‌توانید ببینید، خانم Cake؟ خانم Cake: معمولاً حدود ده ثانیه، آقای Poons.

وابستگی علیّی بین این دو جمله وجود دارد: خانم Cake سؤال آقای Poons را شنید و پاسخ داد.

حالا تصور کنید شخص سومی این گفتگو را از طریق پیروان گوش می‌دهد. حرف‌های خانم Cake از پیروی با تأخیر کم عبور می‌کند، اما حرف‌های آقای Poons تأخیر تکثیر بیشتری دارد (شکل ۵-۵ را ببینید). این ناظر موارد زیر را می‌شنود:

خانم Cake: معمولاً حدود ده ثانیه، آقای Poons. آقای Poons: چقدر به آینده می‌توانید ببینید، خانم Cake؟

برای ناظر به نظر می‌رسد خانم Cake قبل از اینکه آقای Poons سؤالش را بپرسد پاسخ می‌دهد. چنین قدرت‌های روانی‌ای تحسین‌برانگیز است، اما بسیار گیج‌کننده [25].

شکل ۵-۵. اگر برخی پارتیشن‌ها کندتر از بقیه تکثیر شوند، ناظر ممکن است پاسخ را قبل از سؤال ببیند.

جلوگیری از این نوع ناهنجاری به نوع دیگری از تضمین نیاز دارد: خواندن پیشوند سازگار (consistent prefix reads) [23]. این تضمین می‌گوید اگر دنباله‌ای از نوشتن‌ها به ترتیب خاصی رخ دهد، هر کسی که آن نوشتن‌ها را بخواند همان ترتیب را ببیند.

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

یک راه‌حل این است که مطمئن شوید هر نوشتنی که از نظر علیّی به نوشتن دیگر وابسته است به همان پارتیشن نوشته شود — اما در برخی برنامه‌ها این به‌صورت کارآمد ممکن نیست. الگوریتم‌هایی هم وجود دارند که صریحاً وابستگی‌های علیّی را ردیابی می‌کنند، موضوعی که در «رابطه happens-before و هم‌زمانی» در صفحه ۱۸۶ به آن برمی‌گردیم.

راه‌حل‌ها برای تأخیر تکثیر

وقتی با سیستم سازگاری نهایی کار می‌کنید، ارزش دارد فکر کنید اگر تأخیر تکثیر به چند دقیقه یا حتی چند ساعت افزایش یابد برنامه چگونه رفتار می‌کند. اگر پاسخ «مشکلی نیست» است، عالی. با این حال، اگر نتیجه تجربه بدی برای کاربران است، مهم است سیستم را طوری طراحی کنید که تضمین قوی‌تری مثل read-after-write بدهد. وانمود کردن که تکثیر همگام است در حالی که ناهمگام است، دستورالعمل مشکل‌سازی برای آینده است.

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

بهتر است توسعه‌دهندگان برنامه نگران مسائل ظریف تکثیر نباشند و فقط به پایگاه داده‌شان اعتماد کنند که «کار درست را انجام دهد». به همین دلیل تراکنش‌ها وجود دارند: راهی برای پایگاه داده تا تضمین‌های قوی‌تری بدهد تا برنامه ساده‌تر باشد.

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

iii. اصطلاح eventual consistency توسط Douglas Terry و همکاران [24] ابداع شد، توسط Werner Vogels [22] محبوب شد، و شعار بسیاری از پروژه‌های NoSQL شد. با این حال، فقط پایگاه‌های NoSQL سازگاری نهایی ندارند: پیروان در پایگاه داده رابطه‌ای تکثیرشده ناهمگام همان ویژگی‌ها را دارند.

تکثیر چند رهبره

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

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

گسترش طبیعی مدل تکثیر مبتنی بر رهبر این است که بیش از یک نود نوشتن را بپذیرد. تکثیر همچنان به همان شکل انجام می‌شود: هر نودی که نوشتن را پردازش می‌کند باید آن تغییر داده را به همه نودهای دیگر فوروارد کند. این را پیکربندی چند رهبره (multi-leader configuration؛ که master–master یا active/active replication هم نامیده می‌شود) می‌نامیم. در این تنظیم، هر رهبر همزمان به‌عنوان پیروی دیگر رهبرها عمل می‌کند.

موارد استفاده تکثیر چند رهبره

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

عملیات چند datacenter

تصور کنید پایگاه داده‌ای با replicaها در چند datacenter مختلف دارید (شاید برای تحمل خرابی کل datacenter، یا برای نزدیک‌تر بودن به کاربران). با تنظیم معمول تکثیر مبتنی بر رهبر، رهبر باید در یکی از datacenterها باشد و همه نوشتن‌ها باید از آن datacenter عبور کنند.

در پیکربندی چند رهبره، می‌توانید در هر datacenter یک رهبر داشته باشید. شکل ۵-۶ نشان می‌دهد این معماری چگونه ممکن است باشد. در هر datacenter، تکثیر معمول رهبر–پیرو استفاده می‌شود؛ بین datacenterها، رهبر هر datacenter تغییراتش را به رهبرهای datacenterهای دیگر تکثیر می‌کند.

شکل ۵-۶. تکثیر چند رهبره در چند datacenter.

بیایید ببینیم پیکربندی تک‌رهبره و چند رهبره در استقرار چند datacenter چگونه عمل می‌کنند:

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

تحمل خرابی datacenter در پیکربندی تک‌رهبره، اگر datacenter حاوی رهبر خراب شود، failover می‌تواند پیروی در datacenter دیگر را به رهبر ارتقا دهد. در پیکربندی چند رهبره، هر datacenter می‌تواند مستقل از بقیه به کار ادامه دهد، و تکثیر وقتی datacenter خراب برمی‌گردد به‌روز می‌شود.

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

برخی پایگاه‌های داده به‌طور پیش‌فرض پیکربندی چند رهبره را پشتیبانی می‌کنند، اما اغلب با ابزارهای خارجی هم پیاده‌سازی می‌شود، مثل Tungsten Replicator برای MySQL [26]، BDR برای PostgreSQL [27]، و GoldenGate برای Oracle [19].

اگرچه تکثیر چند رهبره مزایا دارد، معایب بزرگی هم دارد: همان داده ممکن است همزمان در دو datacenter مختلف تغییر کند، و آن تعارض‌های نوشتن باید حل شوند (در شکل ۵-۶ با «حل تعارض» نشان داده شده). این مسئله را در «مدیریت تعارض نوشتار» در صفحه ۱۷۱ بحث می‌کنیم.

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

clientهای با عملیات آفلاین

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

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

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

ابزارهایی هستند که هدفشان آسان‌تر کردن این نوع پیکربندی چند رهبره است. مثلاً CouchDB برای این حالت عملیات طراحی شده [29].

ویرایش همکاری‌ای

برنامه‌های ویرایش همکاری‌ای بلادرنگ به چند نفر اجازه می‌دهند همزمان یک سند را ویرایش کنند. مثلاً Etherpad [30] و Google Docs [31] به چند نفر اجازه می‌دهند همزمان یک سند متنی یا spreadsheet را ویرایش کنند (الگوریتم به‌اختصار در «حل تعارض خودکار» در صفحه ۱۷۴ بحث می‌شود).

معمولاً ویرایش همکاری‌ای را مسئله تکثیر پایگاه داده نمی‌دانیم، اما با مورد استفاده ویرایش آفلاین قبلی شباهت زیادی دارد. وقتی یک کاربر سندی را ویرایش می‌کند، تغییرات فوراً روی replica محلی (حالت سند در مرورگر وب یا برنامه client) اعمال می‌شود و به‌صورت ناهمگام به سرور و هر کاربر دیگری که همان سند را ویرایش می‌کند تکثیر می‌شود.

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

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

مدیریت تعارض نوشتار

بزرگ‌ترین مشکل تکثیر چند رهبره این است که تعارض نوشتار (write conflict) ممکن است رخ دهد، یعنی حل تعارض لازم است.

مثلاً صفحه wiki را در نظر بگیرید که همزمان توسط دو کاربر ویرایش می‌شود، همان‌طور که در شکل ۵-۷ نشان داده شده. کاربر ۱ عنوان صفحه را از A به B تغییر می‌دهد، و کاربر ۲ همزمان عنوان را از A به C تغییر می‌دهد. تغییر هر کاربر با موفقیت روی رهبر محلیش اعمال می‌شود. با این حال، وقتی تغییرات به‌صورت ناهمگام تکثیر می‌شوند، تعارض تشخیص داده می‌شود [33]. این مشکل در پایگاه داده تک‌رهبره رخ نمی‌دهد.

شکل ۵-۷. تعارض نوشتار ناشی از به‌روزرسانی همزمان همان رکورد توسط دو رهبر.

تشخیص تعارض همگام در مقابل ناهمگام

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

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

اجتناب از تعارض

ساده‌ترین استراتژی برای برخورد با تعارض اجتناب از آن است: اگر برنامه می‌تواند تضمین کند همه نوشتن‌های یک رکورد خاص از همان رهبر عبور کنند، تعارض رخ نمی‌دهد. چون بسیاری از پیاده‌سازی‌های تکثیر چند رهبره با تعارض‌ها به‌خوبی برخورد نمی‌کنند، اجتناب از تعارض رویکردی است که اغلب توصیه می‌شود [34].

مثلاً در برنامه‌ای که کاربر می‌تواند داده خودش را ویرایش کند، می‌توانید تضمین کنید درخواست‌های یک کاربر خاص همیشه به همان datacenter مسیریابی شوند و از رهبر آن datacenter برای خواندن و نوشتن استفاده شود. کاربران مختلف ممکن است datacenter «خانه» متفاوتی داشته باشند (شاید بر اساس نزدیکی جغرافیایی به کاربر انتخاب شود)، اما از دید هر کاربر، پیکربندی اساساً تک‌رهبره است.

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

همگرایی به حالت سازگار

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

در پیکربندی چند رهبره، ترتیب تعریف‌شده‌ای برای نوشتن‌ها وجود ندارد، پس مشخص نیست مقدار نهایی چه باید باشد. در شکل ۵-۷، در رهبر ۱ عنوان ابتدا به B و سپس به C به‌روزرسانی می‌شود؛ در رهبر ۲ ابتدا به C و سپس به B. هیچ‌کدام از ترتیب‌ها «درست‌تر» از دیگری نیست.

اگر هر replica ساده نوشتن‌ها را به ترتیبی که دیده اعمال کند، پایگاه داده به حالت ناسازگار می‌رسد: مقدار نهایی در رهبر ۱ C و در رهبر ۲ B خواهد بود. این قابل قبول نیست — هر طرح تکثیر باید تضمین کند داده در نهایت در همه replicaها یکسان است. بنابراین، پایگاه داده باید تعارض را به‌صورت همگرا (convergent) حل کند، یعنی همه replicaها وقتی همه تغییرات تکثیر شدند به همان مقدار نهایی برسند.

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

• به هر نوشتن شناسه یکتا بدهید (مثلاً timestamp، عدد تصادفی بلند، UUID، یا hash کلید و مقدار)، نوشتن با بالاترین شناسه را برنده انتخاب کنید، و بقیه نوشتن‌ها را دور بریزید. اگر timestamp استفاده شود، این تکنیک last write wins (LWW) نامیده می‌شود. اگرچه این رویکرد محبوب است، به‌شدت مستعد از دست رفتن داده است [35]. LWW را در پایان این فصل («تشخیص نوشتن‌های همزمان» در صفحه ۱۸۴) با جزئیات بیشتر بحث می‌کنیم.
• به هر replica شناسه یکتا بدهید، و نوشتن‌هایی که از replica با شماره بالاتر آمده‌اند همیشه بر نوشتن‌هایی که از replica با شماره پایین‌تر آمده‌اند اولویت داشته باشند. این رویکرد هم به معنای از دست رفتن داده است.
• به‌نوعی مقادیر را ادغام کنید — مثلاً به‌صورت الفبایی مرتب کنید و سپس concatenate کنید (در شکل ۵-۷، عنوان ادغام‌شده ممکن است چیزی مثل «B/C» باشد).
• تعارض را در ساختار داده صریحی ثبت کنید که همه اطلاعات را حفظ کند، و کد برنامه بنویسید که تعارض را در زمان بعدی حل کند (شاید با پرسیدن از کاربر).

منطق سفارشی حل تعارض

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

هنگام نوشتن به‌محض اینکه سیستم پایگاه داده تعارضی در لاگ تغییرات تکثیرشده تشخیص دهد، handler تعارض را فراخوانی می‌کند. مثلاً Bucardo به شما اجازه می‌دهد تکه‌ای Perl برای این منظور بنویسید. این handler معمولاً نمی‌تواند از کاربر بپرسد — در فرآیند پس‌زمینه اجرا می‌شود و باید سریع اجرا شود.

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

توجه کنید حل تعارض معمولاً در سطح یک سطر یا سند اعمال می‌شود، نه برای کل تراکنش [36]. بنابراین، اگر تراکنشی دارید که چند نوشتن مختلف را به‌صورت اتمی انجام می‌دهد (فصل ۷ را ببینید)، هر نوشتن برای اهداف حل تعارض جداگانه در نظر گرفته می‌شود.

حل تعارض خودکار

قواعد حل تعارض به‌سرعت پیچیده می‌شوند و کد سفارشی می‌تواند مستعد خطا باشد. Amazon مثال پراستنادی از اثرات غافلگیرکننده به‌خاطر handler حل تعارض است: مدتی منطق حل تعارض سبد خرید آیتم‌های اضافه‌شده به سبد را حفظ می‌کرد، اما آیتم‌های حذف‌شده را نه. بنابراین، گاهی مشتریان آیتم‌هایی را در سبدشان می‌دیدند که قبلاً حذف کرده بودند [37]. تحقیق جالبی درباره حل خودکار تعارض‌های ناشی از تغییر همزمان داده انجام شده. چند خط تحقیق ارزش ذکر دارند:

• Conflict-free replicated datatypes (CRDTها) [32, 38] خانواده‌ای از ساختارهای داده برای مجموعه‌ها، mapها، لیست‌های مرتب، شمارنده‌ها و غیره هستند که چند کاربر می‌توانند همزمان ویرایش کنند و به‌صورت خودکار تعارض‌ها را به‌شکل منطقی حل می‌کنند. برخی CRDTها در Riak 2.0 [39, 40] پیاده‌سازی شده‌اند.
• Mergeable persistent data structures [41] صریحاً تاریخچه را ردیابی می‌کنند، مشابه سیستم کنترل نسخه Git، و از تابع merge سه‌طرفه استفاده می‌کنند (در حالی که CRDTها از merge دوطرفه استفاده می‌کنند).
• Operational transformation [42] الگوریتم حل تعارض پشت برنامه‌های ویرایش همکاری‌ای مثل Etherpad [30] و Google Docs [31] است. به‌ویژه برای ویرایش همزمان لیست مرتبی از آیتم‌ها طراحی شده، مثل لیست کاراکترهایی که یک سند متنی را تشکیل می‌دهند.

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

تعارض چیست؟

برخی انواع تعارض آشکارند. در مثال شکل ۵-۷، دو نوشتن همزمان همان فیلد در همان رکورد را تغییر دادند و آن را به دو مقدار متفاوت تنظیم کردند. تردیدی نیست که این تعارض است.

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

پاسخ آماده سریعی وجود ندارد، اما در فصل‌های بعدی مسیر خوبی به سمت درک این مسئله ترسیم می‌کنیم. مثال‌های بیشتری از تعارض در فصل ۷ می‌بینیم، و در فصل ۱۲ رویکردهای مقیاس‌پذیر برای تشخیص و حل تعارض در سیستم تکثیرشده را بحث می‌کنیم.

توپولوژی‌های تکثیر چند رهبره

توپولوژی تکثیر (replication topology) مسیرهای ارتباطی را که نوشتن‌ها از یک نود به نود دیگر منتشر می‌شوند توصیف می‌کند. اگر دو رهبر دارید، مثل شکل ۵-۷، فقط یک توپولوژی محتمل وجود دارد: رهبر ۱ باید همه نوشتن‌هایش را به رهبر ۲ بفرستد و بالعکس. با بیش از دو رهبر، توپولوژی‌های مختلف ممکن است. برخی مثال‌ها در شکل ۵-۸ نشان داده شده.

شکل ۵-۸. سه مثال توپولوژی که تکثیر چند رهبره می‌تواند در آن‌ها راه‌اندازی شود.

عمومی‌ترین توپولوژی همه-به-همه (all-to-all) است (شکل ۵-۸ [c])، که هر رهبر نوشتن‌هایش را به همه رهبرهای دیگر می‌فرستد. با این حال، توپولوژی‌های محدودتر هم استفاده می‌شوند: مثلاً MySQL به‌طور پیش‌فرض فقط توپولوژی حلقه‌ای (circular) را پشتیبانی می‌کند [34]، که هر نود نوشتن‌ها را از یک نود دریافت می‌کند و آن نوشتن‌ها (به‌علاوه نوشتن‌های خودش) را به یک نود دیگر فوروارد می‌کند. توپولوژی محبوب دیگر شکل ستاره (star) دارد:v یک نود ریشه تعیین‌شده نوشتن‌ها را به همه نودهای دیگر فوروارد می‌کند. توپولوژی ستاره را می‌توان به درخت تعمیم داد.

در توپولوژی‌های حلقه‌ای و ستاره‌ای، یک نوشتن ممکن است قبل از رسیدن به همه replicaها از چند نود عبور کند. بنابراین، نودها باید تغییرات داده‌ای که از نودهای دیگر دریافت می‌کنند را فوروارد کنند. برای جلوگیری از حلقه‌های بی‌نهایت تکثیر، به هر نود شناسه یکتا داده می‌شود، و در لاگ تکثیر، هر نوشتن با شناسه‌های همه نودهایی که از آن‌ها عبور کرده tag می‌شود [43]. وقتی نود تغییر داده‌ای را دریافت می‌کند که با شناسه خودش tag شده، آن تغییر داده نادیده گرفته می‌شود، چون نود می‌داند قبلاً پردازش شده.

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

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

شکل ۵-۹. با تکثیر چند رهبره، نوشتن‌ها ممکن است به ترتیب اشتباه به برخی replicaها برسند.

در شکل ۵-۹، client A سطری را در جدول روی رهبر ۱ درج می‌کند، و client B همان سطر را روی رهبر ۳ به‌روزرسانی می‌کند. با این حال، رهبر ۲ ممکن است نوشتن‌ها را به ترتیب متفاوتی دریافت کند: ابتدا به‌روزرسانی را دریافت می‌کند (که از دیدش به‌روزرسانی سطری است که در پایگاه داده وجود ندارد) و فقط بعداً insert متناظر را (که باید قبل از به‌روزرسانی بود).

این مسئله علیّت است، مشابه آنچه در «خواندن پیشوند سازگار» در صفحه ۱۶۵ دیدیم: به‌روزرسانی به insert قبلی وابسته است، پس باید مطمئن شویم همه نودها ابتدا insert و سپس به‌روزرسانی را پردازش کنند. الصاق ساده timestamp به هر نوشتن کافی نیست، چون نمی‌توان به همگام‌سازی کافی ساعت‌ها برای ترتیب‌دهی درست این رویدادها در رهبر ۲ اعتماد کرد (فصل ۸ را ببینید).

برای ترتیب‌دهی درست این رویدادها، تکنیکی به نام بردار نسخه (version vectors) استفاده می‌شود که بعداً در این فصل بحث می‌کنیم (به «تشخیص نوشتن‌های همزمان» در صفحه ۱۸۴ مراجعه کنید). با این حال، تکنیک‌های تشخیص تعارض در بسیاری سیستم‌های تکثیر چند رهبره به‌خوبی پیاده‌سازی نشده‌اند. مثلاً در زمان نگارش، PostgreSQL BDR ترتیب علیّی نوشتن‌ها را فراهم نمی‌کند [27]، و Tungsten Replicator برای MySQL حتی تلاشی برای تشخیص تعارض نمی‌کند [34].

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

iv. اگر پایگاه داده پارتیشن‌شده است (فصل ۶ را ببینید)، هر پارتیشن یک رهبر دارد. پارتیشن‌های مختلف ممکن است رهبرهایشان روی نودهای مختلف باشند، اما هر پارتیشن با این حال باید یک نود رهبر داشته باشد.

v. نباید با star schema (به «ستاره‌ها و دانه‌برفی‌ها: اسکیما برای تحلیل» در صفحه ۹۳) اشتباه گرفت، که ساختار مدل داده را توصیف می‌کند، نه توپولوژی ارتباط بین نودها.

تکثیر بدون رهبر

رویکردهای تکثیر که تا اینجای فصل بحث کردیم — تکثیر تک‌رهبره و چند رهبره — بر این ایده استوارند که client درخواست نوشتن را به یک نود (رهبر) می‌فرستد و سیستم پایگاه داده کپی آن نوشتن را به replicaهای دیگر می‌رساند. رهبر ترتیبی که نوشتن‌ها باید پردازش شوند تعیین می‌کند و پیروان نوشتن‌های رهبر را به همان ترتیب اعمال می‌کنند.

برخی سیستم‌های ذخیره داده رویکرد متفاوتی دارند و مفهوم رهبر را کنار می‌گذارند و به هر replica اجازه می‌دهند مستقیماً از clientها نوشتن بپذیرد. برخی از قدیمی‌ترین سیستم‌های داده تکثیرشده بدون رهبر بودند [1, 44]، اما ایده در دوران تسلط پایگاه‌های داده رابطه‌ای عمدتاً فراموش شد. دوباره به‌عنوان معماری مد روز برای پایگاه‌های داده برگشت وقتی Amazon آن را برای سیستم داخلی Dynamo استفاده کرد [37].vi Riak، Cassandra، و Voldemort پایگاه‌های داده متن‌باز با مدل تکثیر بدون رهبر الهام‌گرفته از Dynamo هستند، پس این نوع پایگاه داده Dynamo-style هم نامیده می‌شود.

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

نوشتن در پایگاه داده وقتی نود از سرویس خارج است

تصور کنید پایگاه داده‌ای با سه replica دارید و یکی از replicaها فعلاً در دسترس نیست — شاید در حال reboot برای نصب به‌روزرسانی سیستم است. در پیکربندی مبتنی بر رهبر، اگر بخواهید به پردازش نوشتن ادامه دهید، ممکن است لازم باشد failover انجام دهید (به «مدیریت خروج نود از سرویس» در صفحه ۱۵۶ مراجعه کنید).

در مقابل، در پیکربندی بدون رهبر، failover وجود ندارد. شکل ۵-۱۰ نشان می‌دهد چه اتفاقی می‌افتد: client (کاربر ۱۲۳۴) نوشتن را به هر سه replica به‌صورت موازی می‌فرستد، و دو replica در دسترس نوشتن را می‌پذیرند اما replica در دسترس نبوده آن را از دست می‌دهد. فرض کنیم برای دو replica از سه replica تأیید نوشتن کافی است: بعد از دریافت دو پاسخ ok از کاربر ۱۲۳۴، نوشتن را موفق می‌دانیم. client ساده این واقعیت را که یکی از replicaها نوشتن را از دست داده نادیده می‌گیرد.

شکل ۵-۱۰. نوشتن حد نصابی (quorum write)، خواندن حد نصابی (quorum read)، و read repair بعد از خروج نود از سرویس.

حالا تصور کنید نود در دسترس نبوده دوباره آنلاین می‌شود و clientها شروع به خواندن از آن می‌کنند. هر نوشتنی که وقتی نود down بود رخ داده از آن نود گم شده. بنابراین، اگر از آن نود بخوانید، ممکن است مقادیر قدیمی (stale) به‌عنوان پاسخ بگیرید.

برای حل این مسئله، وقتی client از پایگاه داده می‌خواند، درخواست را فقط به یک replica نمی‌فرستد: درخواست‌های خواندن هم به چند نود به‌صورت موازی فرستاده می‌شوند. client ممکن است پاسخ‌های متفاوت از نودهای مختلف بگیرد؛ یعنی مقدار به‌روز از یک نود و مقدار قدیمی از نود دیگر. از شماره نسخه (version numbers) برای تعیین اینکه کدام مقدار جدیدتر است استفاده می‌شود (به «تشخیص نوشتن‌های همزمان» در صفحه ۱۸۴ مراجعه کنید).

read repair و anti-entropy

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

دو مکانیزم اغلب در پایگاه‌های داده Dynamo-style استفاده می‌شوند:

read repair وقتی client از چند نود به‌صورت موازی می‌خواند، می‌تواند پاسخ‌های قدیمی را تشخیص دهد. مثلاً در شکل ۵-۱۰، کاربر ۲۳۴۵ مقدار نسخه ۶ از replica ۳ و مقدار نسخه ۷ از replicaهای ۱ و ۲ می‌گیرد. client می‌بیند replica ۳ مقدار قدیمی دارد و مقدار جدیدتر را به آن replica می‌نویسد. این رویکرد برای مقادیری که اغلب خوانده می‌شوند خوب کار می‌کند.

فرآیند anti-entropy علاوه بر این، برخی پایگاه‌های داده فرآیند پس‌زمینه‌ای دارند که مداوم تفاوت‌های داده بین replicaها را جستجو می‌کند و هر داده گم‌شده را از یک replica به replica دیگر کپی می‌کند. برخلاف لاگ تکثیر در تکثیر مبتنی بر رهبر، این فرآیند anti-entropy نوشتن‌ها را به ترتیب خاصی کپی نمی‌کند و ممکن است تأخیر قابل توجهی قبل از کپی داده باشد.

همه سیستم‌ها هر دو را پیاده‌سازی نمی‌کنند؛ مثلاً Voldemort فعلاً فرآیند anti-entropy ندارد. توجه کنید بدون فرآیند anti-entropy، مقادیری که به‌ندرت خوانده می‌شوند ممکن است از برخی replicaها گم شوند و در نتیجه ماندگاری کاهش یابد، چون read repair فقط وقتی انجام می‌شود که برنامه مقداری را بخواند.

حد نصاب برای خواندن و نوشتن

در مثال شکل ۵-۱۰، نوشتن را موفق دانستیم حتی اگر فقط روی دو replica از سه replica پردازش شد. اگر فقط یک replica از سه replica نوشتن را بپذیرد چه؟ تا کجا می‌توانیم این را پیش ببریم؟

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

به‌طور کلی‌تر، اگر n replica داریم، هر نوشتن باید توسط w نود تأیید شود تا موفق در نظر گرفته شود، و برای هر خواندن باید حداقل r نود را پرس‌وجو کنیم. (در مثال ما، n = 3، w = 2، r = 2.) تا وقتی w + r > n، انتظار داریم هنگام خواندن مقدار به‌روز بگیریم، چون حداقل یکی از r نودی که از آن‌ها می‌خوانیم باید به‌روز باشد. خواندن‌ها و نوشتن‌هایی که این مقادیر r و w را رعایت می‌کنند خواندن و نوشتن حد نصابی (quorum reads and writes) [44] نامیده می‌شوند.vii می‌توانید r و w را حداقل تعداد رأی لازم برای معتبر بودن خواندن یا نوشتن در نظر بگیرید.

vii. گاهی این نوع حد نصاب strict quorum نامیده می‌شود، در تضاد با sloppy quorum (در «حد نصاب‌های شل و hinted handoff» در صفحه ۱۸۳ بحث می‌شود).

در پایگاه‌های داده Dynamo-style، پارامترهای n، w، و r معمولاً قابل پیکربندی هستند. انتخاب رایج این است که n را فرد کنند (معمولاً ۳ یا ۵) و w = r = (n + 1) / 2 (گرد شده به بالا) تنظیم کنند. با این حال، می‌توانید اعداد را به دلخواه تغییر دهید. مثلاً، بار کاری با نوشتن کم و خواندن زیاد ممکن است از w = n و r = 1 سود ببرد. این خواندن را سریع‌تر می‌کند، اما معایبش این است که فقط یک نود خراب باعث شکست همه نوشتن‌های پایگاه داده می‌شود.

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

شرط حد نصاب، w + r > n، به سیستم اجازه می‌دهد نودهای در دسترس نبوده را تحمل کند:

• اگر w < n، هنوز می‌توانیم نوشتن را پردازش کنیم اگر نودی در دسترس نباشد.
• اگر r < n، هنوز می‌توانیم خواندن را پردازش کنیم اگر نودی در دسترس نباشد.
• با n = 3، w = 2، r = 2 می‌توانیم یک نود در دسترس نبوده را تحمل کنیم.
• با n = 5، w = 3، r = 3 می‌توانیم دو نود در دسترس نبوده را تحمل کنیم. این حالت در شکل ۵-۱۱ نشان داده شده.
• معمولاً خواندن‌ها و نوشتن‌ها همیشه به‌صورت موازی به همه n replica فرستاده می‌شوند. پارامترهای w و r تعیین می‌کنند برای چند نود منتظر بمانیم — یعنی چند نود از n نود باید موفقیت گزارش کنند تا خواندن یا نوشتن را موفق بدانیم.

شکل ۵-۱۱. اگر w + r > n، حداقل یکی از r replicaهایی که از آن‌ها می‌خوانید باید آخرین نوشتن موفق را دیده باشد.

اگر کمتر از w یا r نود لازم در دسترس باشند، نوشتن‌ها یا خواندن‌ها خطا برمی‌گردانند. نود ممکن است به دلایل زیادی در دسترس نباشد: چون down است (crash، خاموش)، به‌خاطر خطا در اجرای عملیات (نمی‌توان نوشت چون دیسک پر است)، به‌خاطر قطع شبکه بین client و نود، یا به هر دلیل دیگر. فقط به این اهمیت می‌دهیم که نود پاسخ موفق برگردانده یا نه و نیازی به تمایز بین انواع مختلف خرابی نداریم.

محدودیت‌های سازگاری حد نصاب

اگر n replica دارید و w و r را طوری انتخاب کنید که w + r > n، معمولاً می‌توانید انتظار داشته باشید هر خواندن جدیدترین مقدار نوشته‌شده برای یک کلید را برگرداند. این به این دلیل است که مجموعه نودهایی که به آن‌ها نوشته‌اید و مجموعه نودهایی که از آن‌ها خوانده‌اید باید همپوشانی داشته باشند. یعنی بین نودهایی که خوانده‌اید حداقل یکی باید جدیدترین مقدار را داشته باشد (در شکل ۵-۱۱ نشان داده شده).

اغلب، r و w طوری انتخاب می‌شوند که اکثریت (بیش از n/2) نودها باشند، چون این تضمین می‌کند w + r > n در عین حال که تا n/2 خرابی نود تحمل می‌شود. اما حد نصاب‌ها لزوماً اکثریت نیستند — فقط مهم است مجموعه نودهایی که عملیات خواندن و نوشتن استفاده می‌کنند حداقل در یک نود همپوشانی داشته باشند. تخصیص‌های حد نصاب دیگر هم ممکن است که انعطافی در طراحی الگوریتم‌های توزیع‌شده می‌دهد [45].

همچنین می‌توانید w و r را کوچک‌تر تنظیم کنید، طوری که w + r ≤ n (یعنی شرط حد نصاب برقرار نیست). در این حالت، خواندن‌ها و نوشتن‌ها همچنان به n نود فرستاده می‌شوند، اما تعداد کمتری پاسخ موفق برای موفقیت عملیات لازم است.

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

با این حال، حتی با w + r > n، احتمالاً edge caseهایی وجود دارد که مقادیر قدیمی برگردانده می‌شوند. این‌ها به پیاده‌سازی بستگی دارد، اما سناریوهای ممکن شامل:

• اگر sloppy quorum استفاده شود (به «حد نصاب‌های شل و hinted handoff» در صفحه ۱۸۳ مراجعه کنید)، نوشتن‌های w ممکن است روی نودهای متفاوتی از خواندن‌های r تمام شوند، پس دیگر همپوشانی تضمین‌شده بین نودهای r و w وجود ندارد [46].
• اگر دو نوشتن همزمان رخ دهد، مشخص نیست کدام اول اتفاق افتاده. در این حالت، تنها راه‌حل ایمن ادغام نوشتن‌های همزمان است (به «مدیریت تعارض نوشتار» در صفحه ۱۷۱ مراجعه کنید). اگر برنده بر اساس timestamp انتخاب شود (last write wins)، نوشتن‌ها ممکن است به‌خاطر clock skew از دست بروند [35]. در «تشخیص نوشتن‌های همزمان» در صفحه ۱۸۴ به این موضوع برمی‌گردیم.
• اگر نوشتن همزمان با خواندن رخ دهد، نوشتن ممکن است فقط روی برخی replicaها منعکس شود. در این حالت، نامشخص است آیا خواندن مقدار قدیمی یا جدید را برمی‌گرداند.
• اگر نوشتن روی برخی replicaها موفق و روی برخی ناموفق باشد (مثلاً چون دیسک برخی نودها پر است) و در مجموع روی کمتر از w replica موفق باشد، روی replicaهایی که موفق بوده rollback نمی‌شود. یعنی اگر نوشتن به‌عنوان ناموفق گزارش شد، خواندن‌های بعدی ممکن است مقدار آن نوشتن را برگردانند یا نه [47].
• اگر نودی که مقدار جدید دارد خراب شود و داده‌اش از replicaای با مقدار قدیمی بازیابی شود، تعداد replicaهایی که مقدار جدید را نگه می‌دارند ممکن است از w کمتر شود و شرط حد نصاب را بشکند.
• حتی اگر همه‌چیز درست کار کند، edge caseهایی وجود دارد که با بدشانسی در timing ممکن است اتفاق بیفتد، همان‌طور که در «خطی‌پذیری و حد نصاب‌ها» در صفحه ۳۳۴ خواهیم دید.

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

به‌ویژه، معمولاً تضمین‌های بحث‌شده در «مشکلات تأخیر تکثیر» در صفحه ۱۶۱ (خواندن نوشتارهای خودتان، خواندن یکنواخت، یا خواندن پیشوند سازگار) را نمی‌گیرید، پس ناهنجاری‌های ذکرشده ممکن است در برنامه‌ها رخ دهند. تضمین‌های قوی‌تر عموماً به تراکنش یا اجماع نیاز دارند. در فصل ۷ و فصل ۹ به این موضوع‌ها برمی‌گردیم.

پایش کهنگی

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

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

با این حال، در سیستم‌های بدون رهبر، ترتیب ثابتی برای اعمال نوشتن‌ها وجود ندارد که پایش را سخت‌تر می‌کند. علاوه بر این، اگر پایگاه داده فقط از read repair استفاده کند (بدون anti-entropy)، محدودیتی برای قدمت مقدار وجود ندارد — اگر مقداری به‌ندرت خوانده شود، مقداری که replica قدیمی برمی‌گرداند ممکن است بسیار کهنه باشد.

تحقیقاتی درباره اندازه‌گیری کهنگی replica در پایگاه‌های داده بدون رهبر و پیش‌بینی درصد مورد انتظار خواندن‌های قدیمی بسته به پارامترهای n، w، و r انجام شده [48]. متأسفانه این هنوز رایج نیست، اما خوب است اندازه‌گیری کهنگی را در مجموعه استاندارد معیارهای پایگاه داده گنجاند. سازگاری نهایی تضمین عمداً مبهمی است، اما برای قابلیت عملیاتی مهم است بتوان «نهایی» را کمی‌سازی کرد.

حد نصاب‌های شل و hinted handoff

پایگاه‌های داده با حد نصاب‌های مناسب می‌توانند خرابی نودهای جداگانه را بدون نیاز به failover تحمل کنند. همچنین می‌توانند نودهای کند را تحمل کنند، چون درخواست‌ها لازم نیست منتظر پاسخ همه n نود بمانند — وقتی w یا r نود پاسخ دادند می‌توانند برگردند. این ویژگی‌ها پایگاه‌های داده بدون رهبر را برای موارد استفاده‌ای که دسترس‌پذیری بالا و تأخیر کم می‌خواهند و می‌توانند گاهی خواندن قدیمی را تحمل کنند جذاب می‌کند.

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

در کلاستر بزرگ (با بسیار بیش از n نود) احتمالاً client در طول قطع شبکه می‌تواند به برخی نودهای پایگاه داده متصل شود، فقط نه به نودهایی که برای مونتاژ حد نصاب یک مقدار خاص لازم است. در آن حالت، طراحان پایگاه داده با trade-off روبه‌رو می‌شوند:

• آیا بهتر است به همه درخواست‌هایی که نمی‌توانیم به حد نصاب w یا r نود برسیم خطا برگردانیم؟
• یا باید نوشتن‌ها را به هر حال بپذیریم و روی برخی نودهای در دسترس بنویسیم که بین n نودی که مقدار معمولاً روی آن‌ها زندگی می‌کند نیستند؟

دومی sloppy quorum [37] نامیده می‌شود: نوشتن‌ها و خواندن‌ها همچنان به w و r پاسخ موفق نیاز دارند، اما آن‌ها ممکن است شامل نودهایی باشند که بین n نود «خانه» تعیین‌شده برای یک مقدار نیستند. به‌طور قیاسی، اگر از خانه قفل شده‌اید بیرون، ممکن است به در همسایه بزنید و بپرسید آیا موقتاً روی مبل آن‌ها بمانید.

وقتی قطع شبکه برطرف شد، هر نوشتنی که یک نود موقتاً از طرف نود دیگر پذیرفته به نودهای «خانه» مناسب فرستاده می‌شود. این hinted handoff نامیده می‌شود. (وقتی کلید خانه را پیدا کردید، همسایه مؤدبانه می‌خواهد از مبلشان بلند شوید و به خانه بروید.)

حد نصاب‌های شل به‌ویژه برای افزایش دسترس‌پذیری نوشتن مفیدند: تا وقتی w نود در دسترس باشد، پایگاه داده می‌تواند نوشتن بپذیرد. با این حال، این یعنی حتی وقتی w + r > n، نمی‌توانید مطمئن باشید جدیدترین مقدار یک کلید را می‌خوانید، چون جدیدترین مقدار ممکن است موقتاً روی برخی نودهای خارج از n نوشته شده باشد [47].

بنابراین، sloppy quorum در واقع در معنای سنتی حد نصاب نیست. فقط تضمین ماندگاری است، یعنی داده جایی روی w نود ذخیره شده. تضمینی نیست که خواندن r نود آن را ببیند تا hinted handoff تکمیل شود.

حد نصاب‌های شل در همه پیاده‌سازی‌های رایج Dynamo اختیاری هستند. در Riak به‌طور پیش‌فرض فعال‌اند، و در Cassandra و Voldemort به‌طور پیش‌فرض غیرفعال [46, 49, 50].

عملیات چند datacenter

قبلاً تکثیر بین datacenterها را به‌عنوان مورد استفاده تکثیر چند رهبره بحث کردیم (به «تکثیر چند رهبره» در صفحه ۱۶۸ مراجعه کنید). تکثیر بدون رهبر هم برای عملیات چند datacenter مناسب است، چون برای تحمل نوشتن‌های متعارض همزمان، قطع شبکه، و spikeهای تأخیر طراحی شده.

Cassandra و Voldemort پشتیبانی چند datacenter را در مدل معمول بدون رهبر پیاده‌سازی می‌کنند: تعداد replicaها n شامل نودها در همه datacenterهاست، و در پیکربندی می‌توانید مشخص کنید چند تا از n replica را در هر datacenter می‌خواهید. هر نوشتن از client به همه replicaها فرستاده می‌شود، صرف‌نظر از datacenter، اما client معمولاً فقط منتظر تأیید از حد نصاب نودها در datacenter محلی خود می‌ماند تا تحت تأثیر تأخیر و قطع لینک بین datacenterها نباشد. نوشتن‌های با تأخیر بالاتر به datacenterهای دیگر اغلب به‌صورت ناهمگام پیکربندی می‌شوند، اگرچه انعطافی در پیکربندی وجود دارد [50, 51].

Riak همه ارتباط بین clientها و نودهای پایگاه داده را محلی به یک datacenter نگه می‌دارد، پس n تعداد replicaها در یک datacenter را توصیف می‌کند. تکثیر بین datacenterها بین کلاسترهای پایگاه داده به‌صورت ناهمگام در پس‌زمینه انجام می‌شود، به سبکی مشابه تکثیر چند رهبره [52].

vi. Dynamo برای کاربران خارج از Amazon در دسترس نیست. گیج‌کننده است که AWS محصول پایگاه داده میزبانی‌شده‌ای به نام DynamoDB ارائه می‌دهد که معماری کاملاً متفاوتی دارد: بر پایه تکثیر تک‌رهبره است.

تشخیص نوشتن‌های همزمان

پایگاه‌های داده Dynamo-style به چند client اجازه می‌دهند همزمان روی همان کلید بنویسند، یعنی حتی با strict quorum هم تعارض رخ می‌دهد. وضعیت مشابه تکثیر چند رهبره است (به «مدیریت تعارض نوشتار» در صفحه ۱۷۱ مراجعه کنید)، اگرچه در پایگاه‌های Dynamo-style تعارض می‌تواند در read repair یا hinted handoff هم رخ دهد.

مسئله این است که رویدادها ممکن است به‌خاطر تأخیر متغیر شبکه و خرابی‌های جزئی به ترتیب متفاوتی به نودهای مختلف برسند. مثلاً شکل ۵-۱۲ دو client، A و B، را نشان می‌دهد که همزمان روی کلید X در پایگاه داده سه‌نودی می‌نویسند:

• نود ۱ نوشتن از A را دریافت می‌کند، اما به‌خاطر قطعی گذرا نوشتن از B را هرگز دریافت نمی‌کند.
• نود ۲ ابتدا نوشتن از A، سپس نوشتن از B را دریافت می‌کند.
• نود ۳ ابتدا نوشتن از B، سپس نوشتن از A را دریافت می‌کند.

شکل ۵-۱۲. نوشتن‌های همزمان در پایگاه داده Dynamo-style: ترتیب تعریف‌شده‌ای وجود ندارد.

اگر هر نود ساده مقدار یک کلید را هر وقت درخواست نوشتن از client دریافت کرد بازنویسی کند، نودها برای همیشه ناسازگار می‌شوند، همان‌طور که درخواست get نهایی شکل ۵-۱۲ نشان می‌دهد: نود ۲ فکر می‌کند مقدار نهایی X برابر B است، در حالی که نودهای دیگر فکر می‌کنند مقدار A است.

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

به‌اختصار به برخی تکنیک‌های حل تعارض در «مدیریت تعارض نوشتار» در صفحه ۱۷۱ اشاره کردیم. قبل از پایان این فصل، بیایید مسئله را کمی بیشتر بررسی کنیم.

آخرین نوشتن برنده (دور ریختن نوشتن‌های همزمان)

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

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

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

این الگوریتم حل تعارض، last write wins (LWW) نامیده می‌شود و تنها روش حل تعارض پشتیبانی‌شده در Cassandra است [53]، و ویژگی اختیاری در Riak [35].

LWW به هدف همگرایی نهایی می‌رسد، اما به قیمت ماندگاری: اگر چند نوشتن همزمان روی همان کلید باشد، حتی اگر همه به client موفق گزارش شده باشند (چون روی w replica نوشته شدند)، فقط یکی از نوشتن‌ها باقی می‌ماند و بقیه بی‌صدا دور ریخته می‌شوند. علاوه بر این، LWW ممکن است حتی نوشتن‌هایی که همزمان نیستند را هم از دست بدهد، همان‌طور که در «timestampها برای ترتیب‌دهی رویدادها» در صفحه ۲۹۱ بحث می‌کنیم.

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

تنها راه ایمن استفاده از پایگاه داده با LWW این است که تضمین کنید یک کلید فقط یک‌بار نوشته می‌شود و بعد immutable در نظر گرفته می‌شود، و از هر به‌روزرسانی همزمان روی همان کلید اجتناب کنید. مثلاً، روش توصیه‌شده استفاده از Cassandra این است که از UUID به‌عنوان کلید استفاده کنید و به هر عملیات نوشتن کلید یکتا بدهید [53].

رابطه happens-before و هم‌زمانی

چگونه تصمیم بگیریم دو عملیات همزمان هستند یا نه؟ برای شهود، چند مثال ببینیم:

• در شکل ۵-۹، دو نوشتن همزمان نیستند: insert کار A قبل از increment کار B اتفاق می‌افتد، چون مقداری که B increment می‌کند همان مقداری است که A insert کرده. به عبارت دیگر، عملیات B روی عملیات A بنا شده، پس B باید بعدتر اتفاق افتاده باشد. همچنین می‌گوییم B از نظر علیّی به A وابسته است.
• در مقابل، دو نوشتن در شکل ۵-۱۲ همزمان هستند: وقتی هر client عملیات را شروع می‌کند، نمی‌داند client دیگر هم روی همان کلید عملیات انجام می‌دهد. بنابراین، وابستگی علیّی بین عملیات‌ها وجود ندارد.

عملیات A قبل از عملیات B اتفاق می‌افتد (happens before) اگر B از A خبر داشته باشد، یا به A وابسته باشد، یا به‌نوعی روی A بنا شده باشد. اینکه یک عملیات قبل از عملیات دیگر اتفاق افتاده یا نه، کلید تعریف هم‌زمانی است. در واقع، می‌توانیم ساده بگوییم دو عملیات همزمان‌اند اگر هیچ‌کدام قبل از دیگری اتفاق نیفتاده (یعنی هیچ‌کدام از دیگری خبر ندارد) [54].

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

هم‌زمانی، زمان و نسبیت

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

ثبت رابطه happens-before

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

شکل ۵-۱۳ دو client را نشان می‌دهد که همزمان آیتم به همان سبد خرید اضافه می‌کنند. (اگر این مثال برایتان بی‌معناست، به‌جای آن دو کنترل‌کننده ترافیک هوایی را تصور کنید که همزمان هواپیما به بخشی که ردیابی می‌کنند اضافه می‌کنند.) در ابتدا سبد خالی است. بین آن‌ها، پنج نوشتن به پایگاه داده انجام می‌شود:

1. Client 1 شیر به سبد اضافه می‌کند. این اولین نوشتن آن کلید است، پس سرور با موفقیت ذخیره می‌کند و نسخه ۱ اختصاص می‌دهد. سرور مقدار را به client برمی‌گرداند، همراه شماره نسخه.
2. Client 2 تخم‌مرغ به سبد اضافه می‌کند، نمی‌داند client 1 همزمان شیر اضافه کرده (client 2 فکر می‌کرد تخم‌مرغ تنها آیتم سبد است). سرور نسخه ۲ به این نوشتن اختصاص می‌دهد و تخم‌مرغ و شیر را به‌عنوان دو مقدار جدا ذخیره می‌کند. سپس هر دو مقدار را به client برمی‌گرداند، همراه شماره نسخه ۲.
3. Client 1، بی‌خبر از نوشتن client 2، می‌خواهد آرد به سبد اضافه کند، پس فکر می‌کند محتوای فعلی سبد باید [milk, flour] باشد. این مقدار را به سرور می‌فرستد، همراه شماره نسخه ۱ که سرور قبلاً به client 1 داده بود. سرور از شماره نسخه می‌فهمد نوشتن [milk, flour] مقدار قبلی [milk] را supersede می‌کند اما با [eggs] همزمان است. بنابراین، سرور نسخه ۳ به [milk, flour] اختصاص می‌دهد، مقدار نسخه ۱ [milk] را بازنویسی می‌کند، اما مقدار نسخه ۲ [eggs] را نگه می‌دارد و هر دو مقدار باقی‌مانده را به client برمی‌گرداند.
4. در این فاصله، client 2 می‌خواهد ژامبون به سبد اضافه کند، بی‌خبر از اینکه client 1 تازه آرد اضافه کرده. client 2 دو مقدار [milk] و [eggs] را از سرور در آخرین پاسخ دریافت کرده، پس حالا آن مقادیر را merge می‌کند و ژامبون اضافه می‌کند و مقدار جدید [eggs, milk, ham] را به سرور می‌فرستد، همراه شماره نسخه قبلی ۲. سرور تشخیص می‌دهد نسخه ۲ [eggs] را بازنویسی می‌کند اما با [milk, flour] همزمان است، پس دو مقدار باقی‌مانده [milk, flour] با نسخه ۳ و [eggs, milk, ham] با نسخه ۴ هستند.
5. در نهایت، client 1 می‌خواهد بیکن اضافه کند. قبلاً [milk, flour] و [eggs] را از سرور در نسخه ۳ دریافت کرده، پس آن‌ها را merge می‌کند، بیکن اضافه می‌کند، و مقدار نهایی [milk, flour, eggs, bacon] را به سرور می‌فرستد، همراه شماره نسخه ۳. این [milk, flour] را بازنویسی می‌کند (توجه کنید [eggs] قبلاً در مرحله آخر بازنویسی شده) اما با [eggs, milk, ham] همزمان است، پس سرور آن دو مقدار همزمان را نگه می‌دارد.

شکل ۵-۱۳. ثبت وابستگی‌های علیّی بین دو client که همزمان سبد خرید را ویرایش می‌کنند.

جریان داده بین عملیات‌ها در شکل ۵-۱۳ به‌صورت گرافیکی در شکل ۵-۱۴ نشان داده شده. فلش‌ها نشان می‌دهند کدام عملیات قبل از کدام دیگر اتفاق افتاده، به این معنا که عملیات بعدی از عملیات قبلی خبر داشته یا به آن وابسته بوده.

شکل ۵-۱۴. گراف وابستگی‌های علیّی در شکل ۵-۱۳.

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

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

• سرور برای هر کلید شماره نسخه نگه می‌دارد، هر بار که آن کلید نوشته می‌شود شماره نسخه را افزایش می‌دهد، و شماره نسخه جدید را همراه مقدار نوشته‌شده ذخیره می‌کند.
• وقتی client کلیدی را می‌خواند، سرور همه مقادیری که بازنویسی نشده‌اند را برمی‌گرداند، همراه جدیدترین شماره نسخه. client باید قبل از نوشتن کلید را بخواند.
• وقتی client کلیدی می‌نویسد، باید شماره نسخه از خواندن قبلی را شامل کند و همه مقادیری که در خواندن قبلی دریافت کرده merge کند. (پاسخ درخواست نوشتن می‌تواند مثل خواندن باشد و همه مقادیر فعلی را برگرداند، که به زنجیره کردن چند نوشتن مثل مثال سبد خرید اجازه می‌دهد.)
• وقتی سرور نوشتنی با شماره نسخه مشخص دریافت می‌کند، می‌تواند همه مقادیر با آن شماره نسخه یا پایین‌تر را بازنویسی کند (چون می‌داند در مقدار جدید merge شده‌اند)، اما باید همه مقادیر با شماره نسخه بالاتر را نگه دارد (چون آن مقادیر با نوشتن ورودی همزمان‌اند).

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

ادغام مقادیر نوشته‌شده همزمان

این الگوریتم تضمین می‌کند داده بی‌صدا از دست نمی‌رود، اما متأسفانه به clientها کار اضافی وا می‌گذارد: اگر چند عملیات همزمان رخ دهد، clientها باید بعداً با ادغام مقادیر نوشته‌شده همزمان تمیزکاری کنند. Riak به این مقادیر همزمان siblings می‌گوید.

ادغام مقادیر sibling اساساً همان مسئله حل تعارض در تکثیر چند رهبره است که قبلاً بحث کردیم (به «مدیریت تعارض نوشتار» در صفحه ۱۷۱ مراجعه کنید). رویکرد ساده انتخاب یکی از مقادیر بر اساس شماره نسخه یا timestamp (last write wins) است، اما آن به معنای از دست رفتن داده است. پس، ممکن است لازم باشد در کد برنامه کاری هوشمندانه‌تر انجام دهید.

با مثال سبد خرید، رویکرد منطقی برای ادغام siblingها گرفتن اجتماع (union) است. در شکل ۵-۱۴، دو sibling نهایی [milk, flour, eggs, bacon] و [eggs, milk, ham] هستند؛ توجه کنید شیر و تخم‌مرغ در هر دو ظاهر می‌شوند، اگرچه هر کدام فقط یک‌بار نوشته شده. مقدار ادغام‌شده ممکن است چیزی مثل [milk, flour, eggs, bacon, ham] بدون تکرار باشد.

با این حال، اگر بخواهید به مردم اجازه دهید از سبدشان هم چیز حذف کنند، نه فقط اضافه، گرفتن اجتماع siblingها ممکن است نتیجه درست ندهد: اگر دو سبد sibling را merge کنید و آیتمی فقط در یکی حذف شده، آیتم حذف‌شده در اجتماع siblingها دوباره ظاهر می‌شود [37]. برای جلوگیری از این مشکل، آیتم نمی‌تواند ساده از پایگاه داده حذف شود وقتی حذف می‌شود؛ در عوض، سیستم باید marker با شماره نسخه مناسب بگذارد تا نشان دهد آیتم هنگام ادغام siblingها حذف شده. چنین marker حذفی tombstone نامیده می‌شود. (قبلاً tombstone را در زمینه فشرده‌سازی لاگ در «ایندکس‌های هش» در صفحه ۷۲ دیدیم.)

چون ادغام siblingها در کد برنامه پیچیده و مستعد خطاست، تلاش‌هایی برای طراحی ساختارهای داده‌ای که این ادغام را خودکار انجام دهند وجود دارد، همان‌طور که در «حل تعارض خودکار» در صفحه ۱۷۴ بحث شد. مثلاً پشتیبانی datatype در Riak از خانواده‌ای از ساختارهای داده به نام CRDTها [38, 39, 55] استفاده می‌کند که می‌توانند siblingها را به‌شکل منطقی ادغام کنند، از جمله حفظ حذف‌ها.

بردار نسخه

مثال شکل ۵-۱۳ فقط از یک replica استفاده کرد. الگوریتم وقتی چند replica وجود دارد اما رهبر نیست چگونه تغییر می‌کند؟

شکل ۵-۱۳ از یک شماره نسخه برای ثبت وابستگی‌ها بین عملیات‌ها استفاده کرد، اما وقتی چند replica همزمان نوشتن می‌پذیرند کافی نیست. در عوض، باید شماره نسخه به ازای هر replica و همچنین به ازای هر کلید استفاده کنیم. هر replica هنگام پردازش نوشتن شماره نسخه خود را افزایش می‌دهد و همچنین شماره نسخه‌هایی که از هر replica دیگر دیده را ردیابی می‌کند. این اطلاعات نشان می‌دهد کدام مقادیر بازنویسی و کدام به‌عنوان sibling نگه داشته شوند. مجموعه شماره نسخه‌ها از همه replicaها بردار نسخه (version vector) [56] نامیده می‌شود.

چند گونه از این ایده در حال استفاده است، اما شاید جالب‌ترین dotted version vector [57] است که در Riak 2.0 [58, 59] استفاده می‌شود. به جزئیات نمی‌پردازیم، اما نحوه کارشان شبیه آنچه در مثال سبد خرید دیدیم است.

همان‌طور که شماره نسخه‌ها در شکل ۵-۱۳، بردارهای نسخه وقتی مقادیر خوانده می‌شوند از replicaهای پایگاه داده به clientها فرستاده می‌شوند و باید وقتی مقدار بعداً نوشته می‌شود به پایگاه داده برگردانده شوند. (Riak بردار نسخه را به‌عنوان رشته‌ای encode می‌کند که causal context می‌نامد.) بردار نسخه به پایگاه داده اجازه می‌دهد بین بازنویسی و نوشتن همزمان تمایز قائل شود.

همچنین، مثل مثال تک‌replica، برنامه ممکن است لازم باشد siblingها را ادغام کند. ساختار بردار نسخه تضمین می‌کند ایمن است از یک replica بخوانید و بعد روی replica دیگر بنویسید. این ممکن است باعث ایجاد sibling شود، اما اگر siblingها درست ادغام شوند داده‌ای از دست نمی‌رود.

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

بردار نسخه گاهی vector clock هم نامیده می‌شود، اگرچه دقیقاً یکسان نیستند. تفاوت ظریف است — لطفاً به مراجع برای جزئیات مراجعه کنید [57, 60, 61]. به‌اختصار، وقتی حالت replicaها را مقایسه می‌کنید، بردار نسخه ساختار داده درست برای استفاده است.

خلاصه

در این فصل مسئله تکثیر را بررسی کردیم. تکثیر می‌تواند چند هدف را سرویس دهد:

دسترس‌پذیری بالا نگه‌داشتن سیستم در حال اجرا، حتی وقتی یک ماشین (یا چند ماشین، یا کل datacenter) از سرویس خارج می‌شود

عملیات قطع‌شده اجازه دادن به برنامه برای ادامه کار وقتی قطع شبکه وجود دارد

تأخیر قرار دادن داده جغرافیایی نزدیک به کاربران، تا کاربران سریع‌تر با آن تعامل کنند

مقیاس‌پذیری توانایی مدیریت حجم بیشتر خواندن نسبت به آنچه یک ماشین می‌تواند، با انجام خواندن روی replicaها

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

سه رویکرد اصلی تکثیر را بحث کردیم:

تکثیر تک‌رهبره clientها همه نوشتن‌ها را به یک نود (رهبر) می‌فرستند که جریان رویدادهای تغییر داده را به replicaهای دیگر (پیروان) می‌فرستد. خواندن می‌تواند روی هر replica انجام شود، اما خواندن از پیروان ممکن است قدیمی باشد.

تکثیر چند رهبره clientها هر نوشتن را به یکی از چند نود رهبر می‌فرستند، هر کدام می‌توانند نوشتن بپذیرند. رهبرها جریان رویدادهای تغییر داده را به یکدیگر و به هر نود پیرو می‌فرستند.

تکثیر بدون رهبر clientها هر نوشتن را به چند نود می‌فرستند، و از چند نود به‌صورت موازی می‌خوانند تا نودهای با داده قدیمی را تشخیص و اصلاح کنند.

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

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

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

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

خواندن یکنواخت بعد از اینکه کاربران داده را در یک نقطه زمانی دیده‌اند، نباید بعداً داده از نقطه زمانی زودتر ببینند.

خواندن پیشوند سازگار کاربران باید داده را در حالتی ببینند که از نظر علیّی معنا دارد: مثلاً دیدن سؤال و پاسخش به ترتیب درست.

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

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

منابع

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

[2] "Oracle Active Data Guard Real-Time Data Protection and Availability," Oracle White Paper, June 2013.

[3] "AlwaysOn Availability Groups," in SQL Server Books Online, Microsoft, 2012.

[4] Lin Qiao, Kapil Surlaker, Shirshanka Das, et al.: "On Brewing Fresh Espresso: LinkedIn's Distributed Data Serving Platform," at ACM International Conference on Management of Data (SIGMOD), June 2013.

[5] Jun Rao: "Intra-Cluster Replication for Apache Kafka," at ApacheCon North America, February 2013.

[6] "Highly Available Queues," in RabbitMQ Server Documentation, Pivotal Software, Inc., 2014.

[7] Yoshinori Matsunobu: "Semi-Synchronous Replication at Facebook," yoshinorimatsunobu.blogspot.co.uk, April 1, 2014.

[8] 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.

[9] Jeff Terrace and Michael J. Freedman: "Object Storage on CRAQ: High-Throughput Chain Replication for Read-Mostly Workloads," at USENIX Annual Technical Conference (ATC), June 2009.

[10] Brad Calder, Ju Wang, Aaron Ogus, et al.: "Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency," at 23rd ACM Symposium on Operating Systems Principles (SOSP), October 2011.

[11] Andrew Wang: "Windows Azure Storage," umbrant.com, February 4, 2016.

[12] "Percona Xtrabackup - Documentation," Percona LLC, 2014.

[13] Jesse Newland: "GitHub Availability This Week," github.com, September 14, 2012.

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

[15] John Hugg: "'All in' with Determinism for Performance and Testing in Distributed Systems," at Strange Loop, September 2015.

[16] Amit Kapila: "WAL Internals of PostgreSQL," at PostgreSQL Conference (PGCon), May 2012.

[17] MySQL Internals Manual. Oracle, 2014.

[18] Yogeshwer Sharma, Philippe Ajoux, Petchean Ang, et al.: "Wormhole: Reliable Pub-Sub to Support Geo-Replicated Internet Services," at 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI), May 2015.

[19] "Oracle GoldenGate 12c: Real-Time Access to Real-Time Information," Oracle White Paper, October 2013.

[20] Shirshanka Das, Chavdar Botev, Kapil Surlaker, et al.: "All Aboard the Databus!," at ACM Symposium on Cloud Computing (SoCC), October 2012.

[21] Greg Sabino Mullane: "Version 5 of Bucardo Database Replication System," blog.endpoint.com, June 23, 2014.

[22] Werner Vogels: "Eventually Consistent," ACM Queue, volume 6, number 6, pages 14–19, October 2008. doi:10.1145/1466443.1466448

[23] Douglas B. Terry: "Replicated Data Consistency Explained Through Baseball," Microsoft Research, Technical Report MSR-TR-2011-137, October 2011.

[24] Douglas B. Terry, Alan J. Demers, Karin Petersen, et al.: "Session Guarantees for Weakly Consistent Replicated Data," at 3rd International Conference on Parallel and Distributed Information Systems (PDIS), September 1994. doi:10.1109/PDIS.1994.331722

[25] Terry Pratchett: Reaper Man: A Discworld Novel. Victor Gollancz, 1991. ISBN: 978-0-575-04979-6

[26] "Tungsten Replicator," Continuent, Inc., 2014.

[27] "BDR 0.10.0 Documentation," The PostgreSQL Global Development Group, bdr-project.org, 2015.

[28] Robert Hodges: "If You Must Deploy Multi-Master Replication, Read This First," scale-out-blog.blogspot.co.uk, March 30, 2012.

[29] J. Chris Anderson, Jan Lehnardt, and Noah Slater: CouchDB: The Definitive Guide. O'Reilly Media, 2010. ISBN: 978-0-596-15589-6

[30] AppJet, Inc.: "Etherpad and EasySync Technical Manual," github.com, March 26, 2011.

[31] John Day-Richter: "What's Different About the New Google Docs: Making Collaboration Fast," googledrive.blogspot.com, 23 September 2010.

[32] Martin Kleppmann and Alastair R. Beresford: "A Conflict-Free Replicated JSON Datatype," arXiv:1608.03960, August 13, 2016.

[33] Frazer Clement: "Eventual Consistency – Detecting Conflicts," messagepassing.blogspot.co.uk, October 20, 2011.

[34] Robert Hodges: "State of the Art for MySQL Multi-Master Replication," at Percona Live: MySQL Conference & Expo, April 2013.

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

[36] Riley Berton: "Is Bi-Directional Replication (BDR) in Postgres Transactional?," sdf.org, January 4, 2016.

[37] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, et al.: "Dynamo: Amazon's Highly Available Key-Value Store," at 21st ACM Symposium on Operating Systems Principles (SOSP), October 2007.

[38] Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski: "A Comprehensive Study of Convergent and Commutative Replicated Data Types," INRIA Research Report no. 7506, January 2011.

[39] Sam Elliott: "CRDTs: An UPDATE (or Maybe Just a PUT)," at RICON West, October 2013.

[40] Russell Brown: "A Bluffers Guide to CRDTs in Riak," gist.github.com, October 28, 2013.

[41] Benjamin Farinier, Thomas Gazagnaire, and Anil Madhavapeddy: "Mergeable Persistent Data Structures," at 26es Journées Francophones des Langages Applicatifs (JFLA), January 2015.

[42] Chengzheng Sun and Clarence Ellis: "Operational Transformation in Real-Time Group Editors: Issues, Algorithms, and Achievements," at ACM Conference on Computer Supported Cooperative Work (CSCW), November 1998.

[43] Lars Hofhansl: "HBASE-7709: Infinite Loop Possible in Master/Master Replication," issues.apache.org, January 29, 2013.

[44] David K. Gifford: "Weighted Voting for Replicated Data," at 7th ACM Symposium on Operating Systems Principles (SOSP), December 1979. doi:10.1145/800215.806583

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

[46] Joseph Blomstedt: "Re: Absolute Consistency," email to riak-users mailing list, lists.basho.com, January 11, 2012.

[47] Joseph Blomstedt: "Bringing Consistency to Riak," at RICON West, October 2012.

[48] Peter Bailis, Shivaram Venkataraman, Michael J. Franklin, et al.: "Quantifying Eventual Consistency with PBS," Communications of the ACM, volume 57, number 8, pages 93–102, August 2014. doi:10.1145/2632792

[49] Jonathan Ellis: "Modern Hinted Handoff," datastax.com, December 11, 2012.

[50] "Project Voldemort Wiki," github.com, 2013.

[51] "Apache Cassandra 2.0 Documentation," DataStax, Inc., 2014.

[52] "Riak Enterprise: Multi-Datacenter Replication." Technical whitepaper, Basho Technologies, Inc., September 2014.

[53] Jonathan Ellis: "Why Cassandra Doesn't Need Vector Clocks," datastax.com, September 2, 2013.

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

[55] Joel Jacobson: "Riak 2.0: Data Types," blog.joeljacobson.com, March 23, 2014.

[56] D. Stott Parker Jr., Gerald J. Popek, Gerard Rudisin, et al.: "Detection of Mutual Inconsistency in Distributed Systems," IEEE Transactions on Software Engineering, volume 9, number 3, pages 240–247, May 1983. doi:10.1109/TSE.1983.236733

[57] Nuno Preguiça, Carlos Baquero, Paulo Sérgio Almeida, et al.: "Dotted Version Vectors: Logical Clocks for Optimistic Replication," arXiv:1011.5808, November 26, 2010.

[58] Sean Cribbs: "A Brief History of Time in Riak," at RICON, October 2014.

[59] Russell Brown: "Vector Clocks Revisited Part 2: Dotted Version Vectors," basho.com, November 10, 2015.

[60] Carlos Baquero: "Version Vectors Are Not Vector Clocks," haslab.wordpress.com, July 8, 2011.

[61] Reinhard Schwarz and Friedemann Mattern: "Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail," Distributed Computing, volume 7, number 3, pages 149–174, March 1994. doi:10.1007/BF02277859