مکانیزم Multi-Leader Replication و مصائب Write Conflict

نمیدونم چقدر راجع‌به مکانیزم Multi-Leader Replications توی دیتابیس‌ها می‌دونید. به‌طور خلاصه اینه که به‌جای این‌که یک نود مستر (Leader، Main یا هرچی) داشته باشیم که درخواست‌های رایت فقط روی اون serve بشند، چندین نود داشته باشیم که این کار رو برای ما انجام بدن. درواقع، Writeهایی که روی هر کدوم از نودها میان، روی باقی نودها Propagate می‌شن.

این کار یک‌سری مزیت داره، اولیش High Availabilityـه. اینطوری اگر یکی از نودهای مستر Fail بشه و به هر دلیلی نتونه به درخواست ما رسیدگی کنه، نودهای دیگه‌ای هستند که این کار رو انجام بدن.

مزیت بعدی Scalability و امکان Load Balancingـه. فرض کنید که تعداد رایت‌هایی که روی نود مستر می‌شه این‌قدر زیاده که I/O نمی‌تونه به همه‌ی درخواست‌ها جواب بده. تو این مکانیزم، ما می‌تونیم لود رو روی نودهای مستر دیگه که به‌طبع روی سرورها و دیتاسنترهای مختلف وجود دارند توزیع کنیم و Response Time رو بیاریم پایین. هر وقت هم که احساس کردیم این تعداد نود کافی نیست، می‌تونیم نودهای مستر جدید به سیستم اضافه کنیم.

با تمام این ویژگی‌های وسوسه‌برانگیز، اما هر آدم عاقلی شما رو تا جای ممکن از این‌که بخواید به این سمت حرکت کنید برحذر می‌داره. علت؟ پیچیدگی بالا و ریسک بالای Write Conflict و در ادامه Data Inconsistencyـه.

چرا این اتفاق می‌افته؟ فکر کنید یک Collaborative Editor درست مثل گوگل داک نوشتید. جایی که آدم‌های مختلف می‌تونن هم‌زمان با هم یک داکیومنت رو ویرایش کنن. یکی از سناریوهای محتمل که به ذهن خیلی‌ها حتما رسیده اینه:

توی خط اول داکیومنت نوشته:

Edited by Alireza

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

Edited by Ali

درست همون موقع که علی این تصمیم رو گرفته، رضا هم برمی‌داره و اونو این‌طور تغییر می‌ده:

Edited by Reza

و هر دوی این تغییرات به سمت هر کدومشون ارسال می‌شه و اتفاقی که می‌افته اینه که:

درخواست تغییر علی قرار بود عبارت Alireza رو به Ali تغییر بده. وقتی رسیده سمت رضا، برنامه دیده که Alirezaیی در کار نیست که بخواد تغییر بده و فقط Reza وجود داره. از طرف دیگه، وقتی درخواست تغییر رضا به کلاینت علی رسیده، خبری از Alireza که بخواد به Reza تغییر کنه نیست چون اون‌جا نوشته Ali.

این دقیقاً همون Write Conflictـه که راجع‌بهش صحبت می‌کردیم. همین مشکل دقیقاً تو سمت دیتابیس هم وجود داره. کلاینت ۱ درخواست رایت رو روی Node A ارسال می‌کنه. در همون زمان، کلاینت ۲ درخواست رایت رو برای Node B ارسال می‌کنه و هرکدوم از این نودها این رایت‌ها رو Propagate می‌کنن و باز هم Write Conflict.

برای رفع این مشکل چه کار می‌شه کرد؟ اولین و بهترین روش: پیش‌گیری! تا جای ممکن نباید سراغ این سناریو رفت. رفع کانفلیکت پیچیده‌ست و شما رو وارد یک Trade-off جدید می‌کنه. اما واقعاً چه راهکارهایی برای این ماجرا وجود داره؟ چطور میشه حداقل در نهایت، به یک Convergent رسید؟

یک روش که احتمالاً به ذهن شما هم رسیده اینه که جدیدترین (آخرین Writeای که اتفاق افتاده) رو همیشه در نظر بگیریم. این یکی از روش‌های متداولیه که اتفاقاً توی سیستم‌های جدی‌ای مثل Cassandra هم پیاده شده (و تنها روشیه که به‌کار می‌ره). به این الگوریتم می‌گن Last Write Wins یا به اختصار LWW. برای پیاده‌سازیش، در کنار درخواست Write، یک Timestamp هم ارسال می‌شه. این‌طوری هر نود می‌تونه با مقایسه‌ی Timestampها آخرین رایت رو جایگزین مقدار قبلی کنه. مشکل این روش اما فدا کردن Durabilityـه. این‌طور فرض کنید که توی چند تا کلاینت مختلف، به‌صورت هم‌زمان درخواست رایت ارسال شده و همه‌ی کلاینت‌ها فکر کردن درخواست اون‌ها موفق بوده. این در حالیه که فقط یکی از اون‌ها که دیرتر از بقیه ایجاد شده قبول شده و باقی در نظر گرفته نشدن. در سیستم‌هایی که هیچ‌نوع از دست‌دادن داده‌ای قابل پذیرش نیست، استفاده از LWW چندان مناسب به‌نظر نمی‌رسه.

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

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

۱- Operational Transformation (OT)

مثالی که راجع‌به collaborative document editing زدم، دقیقا مورد کاربرد این الگوریتمه. گوگل از همین الگوریتم برای رفع مشکل کانفلیکت‌هاش توی live editor‌ش استفاده کرده (البته میگن که الان دیگه از این استفاده نمیکنه و رفته سرغ CRDT. ولی من چیزی راجع‌بهش نمیدونم.)

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

کاربر A تو اندیس سوم حرف «X» اضافه می‌کنه. همون موقع، کاربر B تو اندیس شماره ۱، حرف «Y» اضافه می‌کنه. بدون OT، مشخصا اگر اول تغییر B اعمال بشه، اندیس ۳ دیگه همونی نیست که کاربر A میخواست تغییر بده و این باعث تغییر اشتباه میشه. با OT، وقتی تغییر B اول اعمال شد، تغییر A transform میشه (چون حالا موقعیت ۳ شده ۴)، پس تغییر A اصلاح میشه و همه یک نتیجه یک‌سان رو می‌بینن.

برای مطالعه‌ی بیشتر: لینک۱ و لینک ۲

۲- Conflict-free Replicated Datatypes (CRDTs)

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

فرض کنید که دو تا پراسس (مولتی پراسسینگ خیلی شبیه سیستم‌های توزیع شده‌ست. واسه همین همچین مثالی میزنم. ولی شما میتونید دو تا کلاینت کاملا مستقل و یک دیتابیس در نظر بگیرید)، میخوان که مقدار counter رو توی یک shared memory که برابر ۰‌ه تغییر بدن. یکی میخواد اون رو +۲ کنه و یکی دیگه +۳.

چیزی که همه اینجا انتظار داریم اینه که یک حالت غییر قطعی پیش بیاد. یک بار counter=2 بشه یک‌بار counter=3. ولی ایده‌ی CRDT اینه که این‌ها رو باهم ترکیب کنیم. یعنی این که مستقل از ترتیب هرکدوم، در نهایت با به counter=5 برسیم:

counter = 0 + 2 + 3 = 5

یا توی مثال collaborative editor. دوباره همون فضا رو تصور کنید:

اول داکیومنت نوشته: Edited by Ali رضا میخواد که اول Ali یه aqa بذاره علی هم میخواد که بعد از Ali یه khan بذاره.

اتفاقی که توی CRDTمیفته اینه که هر کارکتر یک آی‌دی یونیک دارند و توی کیس ما تغییر رضا رو وقتی دریافت میکنه، اینطوره که قبل از آی‌دی مربوط به حرف A توی ایندکس ۱۰، یه aqa بذار. وقتی که درخواست علی رو هم میگیره میگه بعد از آی‌دی مربوط به کارکتر i تو اندیس ۱۲، یه khan میذاره. اینطوری خروجی اینطور خواهد بود:

Edited by aqa Ali khan

بدون این که هیچ کانفلیکتی وجود داشته باشه. نکته‌ای که راجع‌به CRDT و OT وجود داره اینه که الگوریتم CRDT برخلاف OT نیاز به یک co-ordination نداره و میشه که decentralized باشه.

برای مطالعه‌ی بیشتر: لینک‌ ۱، ویدیو‌ی Martin Kleppmann (نویسنده‌ی کتاب Designing Data Intensive Applications)، لینک ۳ (https://crdt.tech/)

۳- Mergable Persistent Data Structures (MPDS)

ساختمان‌داده‌هایی که اگر تغییری توشون بدین، اون تغییرات از بین نمیرند. درست همون‌طور که توی git هم داریم و میشه برنچ‌ها رو باهم مرج کرد. البته نه یک مرج عادی یا two-way merge (که توی CRDT استفاده میشد) که three-way merge. بذارید با مثال بهتر توضیح بدم:

فرض کنید یک لیستی داریم:

Persistent List: [1, 2, 3]

همزمان یک ترد به این لیست مقدار ۴ رو اضافه میکنه:

Persistent List: [1, 2, 3, 4]

و درست در همون زمان، یک ترد دیگه، مقدار ۵ رو:

Persistent List: [1, 2, 3, 5]

هردوی این نسخه‌ها توی لیست ما که Persistentعه ذخیره میشند. حالا هروقت که بخواییم این تغییرات رو باهم مرج کنیم، بنا به سیاست مرجی که داریم میتونیم این دو تا تغییر رو باهم ادغام کنیم. درست همون‌طور که دو تا برنچ رو باهم توی گیت مرج می‌کنیم. اما داستان مرج سه‌طرفه چیه؟ فرقش با مرج دوطرفه چیه؟ این مثال رو در نظر بگیرید:‌

نسخه‌ی Base ما اینه:

Hello world

نسخه‌ای که کاربر A تغییر میده اینه:‌

Hello A world

نسخه‌ای که کاربر B تغییر میده اینه:

Hello world B!

حالا ما برای مرج کردن، سه طرف دخیل در تصمیم گیری داریم:

Base=Hello world A=Hello A world B=Hello world B!

حالا با در نظر گرفتن Base میشه فهمید که A و ‌B هرکدوم چه تغییری دادند و تغییرات مستقل یا non-coflicting رو به صورت خودکار باهم ترکیب یا مرج کنیم.

درواقع برخلاف مرج دو‌طرفه که ما فقط تغییرات رو باهم بررسی می‌کردیم (مرج دو‌طرف درواقع همون diffـه)، توی این روش علاوه‌ بر مقایسه‌ی دوتایی، این امکان وجود داره که تغییرات هر کدوم رو با نسخه‌ی اورجینال هم مقایسه کنیم. برای درک بهتر ماجرا، این سوال استک‌اوورفلو و جواب‌هاش رو بخونید. این ویدیو‌هم به‌نظر جالب اومد.

برای مطالعه‌ی بیشتر راجع‌به MPDS: لینک ۱ ، لینک به جلسه‌ی Persistent Data Structures از کورس MIT Advanced Data Structures