Designing Data-Intensive Application Book

سلام :)
این خلاصه کتاب Designing Data-Intensive Application هست و خب چون خیلی شلوغم نرسیدم دوباره بخونمش و ویرایش کنم و چون سال‌ها درفت مونده بود، گفتم پابلیش کنمش با این حال هم شاید به کسی کمک کرد که کتاب رو بتونه مرور کنه و خلاصه‌ای فارسی از کتاب موجود باشه. اگر پیشنهاد ویرایش هم داشتین قطعا استقبال می‌کنم.

Reliability

در نرم‌افزار معمولا انتظارات ما از یک سیستم reliable این‌هاست:

• برنامه، عملکردی رو داشته باشه که کاربر انتظار داره.

• اگر کاربر اشتباهی انجام بده و یا نرم‌افزار در مسیر غیر منتظره‌ای عمل کنه، سیستم می‌تونه تحملش کنه.

• به اندازه کافی برای یوزکیس‌های ضروری زیر بار و حجم مورد انتظار، خوب عمل می‌کنه.

• سیستم از هرگونه دسترسی و سواستفاده غیر مجاز، جلوگیری می‌کنه.

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

چیزایی که درست پیش نمی‌رن بهشون می‌گیم faults و به سیستمی که بتونه این خطاها رو پیش‌بینی کنه و باهاشون کنار بیاد رو می‌گیم fault-tolerant یا resilient. گاهی وقتا ما به صورت عمدی در سیستم خطا ایجاد می‌کنیم که مطمئن بشیم در این زمان سیستم به درستی از پسش برمیاد، Netflix Chaos Monkey یک نمونه از این روش هست.

خطاهای سخت‌افزاری

خطاهایی مثل کرش کردن هارد دیسک، مشکل خوردن رم، قطع شدن برق سرور یا قطعی شبکه و... مثلا یک هارد دیسک عمری بین ۱۰ تا ۵۰ سال داره، پس یک دیتاسنتر با ۱۰ هزار دیسک، معمولا روزی یکی از دیسک‌هاش می‌میره. برای این مشکلات راهکار وجود داره، میشه دیسک‌ اضافه گذاشت و RAID کرد، برای دیتاسنتر ژنراتور برق گذاشت و... معمولا در بسیاری از موارد افزونگی (redundancy) قطعات سخت‌افزار مشکل رو حل می‌کنه و تا حد قابل‌قبول سیستم رو از این جنبه قابل اتکا می‌کنه.

خطاهای نرم‌افزاری

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

خطاهای انسانی

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

• سیستم طوری طراحی بشه که فرصت بروز خطا حداقل بشه. به عنوان مثال، طراحی خوب abstraction, API ها و رابط مدیریتی.

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

• در تمام سطح‌ها تست انجام بدید، از unit test تا تست integration کل سیستم و تست‌های دستی.

• امکان بازیابی سریع ارورهای انسانی رو ایجاد کنین. به عنوان مثال سریع بشه تغییرات تنظیمات رو roll back کرد. کد جدید رو به تدریج دپلوی کنین و ابزارهایی تهیه کنین که داده‌ها رو دوباره حساب کنن.

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

• آموزش‌ها و تمرین‌های مدیریتی خوب پیاده سازی کنین - جنبه‌های پیچیده و مهم و فراتر از حوزه این کتاب.

Scalability

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

تعریف Load: ما به یک تعریف مختصر برای لود در سیستم‌مون نیاز داریم. لود می‌تونه با چندتا عدد بیان بشه که بهش load parameters می‌گیم. می‌تونه تعداد کاربر همزمان باشه، نسبت نوشتن به خوندن دیتابیس باشه، تعداد درخواست در ثانیه به سرور باش، hit rate کش باشه و ...

تعریف Performance: برای فهمیدن تاثیر لود بر عملکرد ما نیاز به اعداد مرتبط با عملکرد داریم. این می‌تونه تعداد رکوردی که در ثانیه می‌تونن پردازش بشن در سیستمی مثل Hadoop باشه. می‌تونیم برای این منظور میانه (median - 50th percentile) رو در نظر بگیریم و یا ۹۵٪ یا ۹۹٪ و یا ۹۹.۹٪ رو در نظر بگیریم.

راهکارهای وفق پیدا کردن با لود: معمولا دو راهکار داریم. scaling up یا همون رشد عمودی (vertical scaling) یعنی افزایش قدرت ماشین و scaling out یا رشد افقی (horizontal scaling) که یعنی پخش کردن لود میان چند ماشین کوچک‌تر.

Maintainability

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

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

• اصل Simplicity: فهم سیستم رو با حذف هر پیچیدگی ممکن از سیستم برای مهندسان جدید آسون کنین. به کار نبردن کاپلینگ ماژول‌ها، وابستگی‌های درهم تنیده، نام‌ها و اصطلاحات غیر استاندارد، کارهای ابداعی برای افزایش عملکرد و... یکی از بهترین راه‌های خذف پیچیدگی، استفاده از abstraction هست.

• اصل Evolvability: کار ایجاد تغییرات آینده روی سیستم رو برای مهندسان آسون کنین، با یوزکیس‌های پیش‌بینی نشده که به دلیل تغییر نیازمندی‌ها به وجود میان، سازگارش کنین که این مورد با این اسامی هم می‌گیم: extensibility, modifiability, or plasticity

Data Models and Query Languages

Relational Model Versus Document Model

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

• نوع schema-on-read: ساختار دیتا ضمنی تعریف شده و تنها زمانی تفسیر میشه که دیتا خونده میشه.

• نوع schema-on-write: روش سنتی دیتابیس‌های رابطه‌ای، الگو صریح تعریف شده و دیتابیس مطمئن میشه همه دیتاهایی که می‌خوان نوشته بشن در اون قالب هستن.

ساختار با schema-on-read برای زمانی مفیده که اشیای با ساختارهای متفاوتی داریم که نمی‌خوایم برای هرکدوم یک جدول جداگانه داشته باشیم و یا زمانی که ساختار دیتا مرتبط با یک منبع بیرونیه و ممکنه تغییر کنه.

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

Query Languages for Data

• نوع imperative language: در روش‌های قدیمی باید مشابه حلقه تمام عناصر رو چک می‌کردیم و اونی که می‌خواستیم رو پیدا می‌کردیم. یعنی ما روش انجام دادن رو باید مشخص می‌کردیم.

• نوع declarative query language: این روش مشابه SQL فقط الگو رو مشخص می‌کنه و با اینکه اون پشت چطور انجام میشه کاری نداره.

• نوع MapReduce programming model: این روش نه declarative و نه کامل imperative هست، بلکه یک چیزی بین این دو هست. منطقش با یک تیکه کد بیان میشه و به طور مکرر به‌وسیله چارچوب پردازش، فراخونی میشه. این کار بر اساس نقشه (map - یکسری تغییرات یا دیتای جدید ایجاد کنی) و کاهش (reduce - فیلتر و عملیات روی خروجیت انجام بدی) که در خیلی از زبان‌های برنامه‌نویسی وجود داره، انجام میشه. مپ‌ردیوس فقط روی دیتایی که بهش به عنوان ورودی پاس داده شده عمل می‌کنه و نمی‌تونه عملیات دیتابیس بیشتری انجام بده. اما اینکه بخوای دو تابع جاوا اسکریپتی توی کدت بنویسی کار رو از اینکه بخوای یک کوئری بنویسی سخت تر می‌کنه، این بود که مونگو aggregation pipeline رو اضافه کرد.

Graph-Like Data Models

اگر روابط چند-به-چند از روابط اصلی برنامه‌تون هست، گفتیم که مدل داکیومنتی مناسبتون احتمالا نیست. اگر روابط بین دیتاها پیچیده‌تر بشن، طبیعی‌تره که مدل‌سازی داده‌ها رو گراف کنیم. گراف دو بخش داره، نودها (vertices - nodes - entities) و لبه‌ها (edges - relationships - arcs) انواع مختلفی از دیتاها می‌تونن به صورت گراف مدل‌سازی بشن. سوشال‌ها: نودها افراد و یال‌ها نمایانگر افرادی که هم رو می‌شناسن. گراف وب: نودها صفحات وب و یال‌ها لینک‌های به صفحات دیگر. می‌تونه این گراف‌ها اینقدر همگن نباشه و اشیای متفاوتی رو نگه داره. مثلا فیسبوک یک گراف بزرگ داره با انواع مختلف نودها مثل افراد، لوکیشن‌ها، ایونت‌ها، کامنت‌ها و... هر لبه یا یال شامل شناسه نودی که ازش شروع شده و شناسه نودی که بهش ختم شده، یک لیبل که نوع رابطه بین دو نود رو نشون میده و یک کالکشن از جزئیات مرتبطش هست. گراف‌ها برای تکامل‌پذیری عالی هستن، وقتی یک امکان جدید به برنامه اضافه می‌کنی، یک گراف می‌تونه به راحتی گسترش پیدا کنه تا تغییرات رو پوشش بده.

The Cypher Query Language

سایفر یک declarative query language است که برای Neo4j تولید شده. نمونه کد ایجاد نود و یال:

CREATE
    (NAmerica:Location {name:'North America', type:'continent'}),
    (USA:Location           {name:'United States',   type:'country'   }),
    (Idaho:Location         {name:'Idaho',                 type:'state'       }),
    (Lucy:Person              {name:'Lucy' }),
    (Idaho)  -[:WITHIN]->     (USA)    -[:WITHIN]->  (NAmerica),
    (Lucy)    -[:BORN_IN]->  (Idaho)

حالا فرض کن دنبال کسایی بخوایم بگردیم که از آمریکا به اروپا مهاجرت کردن:

MATCH
    (person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
    (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name

Graph Queries in SQL

ما می‌تونیم دیتای گراف رو در دیتابیس‌ها رابطه‌ای هم قرار بدیم، اما سوال اینجاست که با SQL می‌تونیم روش کوئری بزنیم؟ جواب بله هست اما کار سختیه، باید با جوین پیش‌بریم و تعداد جوین‌ها ممکنه ثابت نباشه. برای همین بود که چیزی به نام recursive common table expressions ارائه شد. همین کد ۴ خط بالا در ۲۹ خط با این روش پیاده‌سازی میشه.

Triple-Stores and SPARQL

این مدل معادل property graph model هست، در این مدل همه اطلاعات در سه بخش بیان میشن: فاعل، بیان‌کننده و مفعول (subject, predicate, object) به عنوان مثال: حمزه، دوست دارد، سیب. به روش Turtle format میشه چندین مورد رو در یک خط بیان کرد:

@prefix : <urn:example:>.
_:lucy           a :Person;     :name "Lucy"                   :bornIn _:idaho.
_:idaho        a :Location;  :name "Idaho"                  :type "state"     :within _:usa.
_:usa            a :Location;  :name "United States"   :type "country" :within _:namerica.
_:namerica  a :Location;  :name "North America" :type "continent".

The RDF data model

زبان Turtle که مثالش رو آوردیم، فرمت قابل خوندن انسان از چارچوب شرح منابع (Resource Description Framework) هست. گاهی هم RDF در فرمت XML نوشته میشه. این چارچوب برای تبادل داده در سراسر اینترنت طراحی شده.

The SPARQL query language

زبان SPARQL برای استفاده از دیتا مدل RDF در triple-stores هاست. نمونه کوئری مشابه:

PREFIX : <urn:example:>
SELECT ?personName WHERE {
    ?person :name ?personName.
    ?person :bornIn / :within* / :name "United States".
    ?person :livesIn / :within* / :name "Europe".
}

The Foundation: Datalog

زبان Datalog از SPARQL و یا Cypher قدیمی‌تره و خیلی از این نوع زبان‌ها بر پایه اون نوشته شدن. مشابه triple هست با این تفاوت: predicate(subject, object). این روش نیاز به تفکر متفاوتی نسبت به سایر زبان کوئری‌هایی که گفتیم داره اما روش بسیار قدرتمندی هست چون می‌تونه کوئری‌های متفاوت رو باهم ترکیب و دوباره استفاده کنه. این باعث میشه که با دیتاهای پیچیده همخوانی بیشتری داشته باشه.

Storage and Retrieval

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

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

Hash Index

با ایندکس‌های دیتا key-value شروع کنیم. این نوع دیتا شبیه دیکشنری هست که به صورت hash map (hash table) پیاده‌سازی شده. ساده‌ترین استراتژی ایندکس کردن اینه که توی مموری هش‌مپ رو نگه داریم که هر کلید مپ شده به محل قرار گیری دیتا روی هارد دیسک. برای جلوگیری از اینکه لاگ فایل روی دیسک خیلی بزرگ بشه و کمبود فضا ایجاد نشه، میتونیم فرآیند فشرده سازی (compaction) انجام بدیم، چون ما هیچوقت فایل لاگ رو آپدیت نمی‌کنیم. در یک فایل جدید، کلیدهای تکراری رو حذف می‌کنیم و فقط آخرین به‌روزرسانی از هر کلید رو ذخیره می‌کنیم. وقتی این فرآیند تموم شد از سگمنت جدید برای خوندن استفاده می‌کنیم و سگمنت قدیمی رو با خیال راحت پاک می‌کنیم. خوندن به این صورت خواهد بود که اول میریم سراغ جدیدترین نسخه hash map و اگر اونجا کلیدمون نبود به ترتیب می‌ریم سراغ نسخه‌های قدیمی‌تر.

SSTables and LSM-Trees

ما می‌تونیم بیایم و اجباری کنیم که ترتیب key-value ها براساس key مرتب بشه. به این فرمت Sorted String Table می‌گیم. همینطور اجبار می‌کنیم که هر کلید فقط یکبار در سگمنت مرج‌شده وجود داشته باشه.

الگوریتم Log-Structured Merge-Tree (LSM-tree) الگوریتمی هست که در levelDB و RocksDB استفاده میشه. storage engine مشابه‌ای در Cassandra و HBase استفاده میشه که هردو الهام گرفته از Google Bigtable paper هستن. به استوریج انجین‌هایی که بر اساس اصل ادغام و فشرده‌سازی فایل‌های مرتب شده کار می‌کنن، اغلب LSM storage engine می‌گن. Lucene که یک ایندکسینگ انجین برای full-text search هست که توسط Elasticsearch و Solar استفاده میشه، از روش مشابه‌ای برای ذخیره دیکشنری خود استفاده می‌کنن که البته خیلی روش پیچیده‌تری از key-value هست. دو نوع compaction متداول داریم:

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

• فشرده‌سازی size-tiered: در این روش انتخاب برای فشرده‌سازی SSTable براساس سایزشونه. کوچکترین انتخاب میشه و با بزرگ‌ترین مرج میشه.

B-Tree

ایندکس متداول اکثر دیتابیساس، مشابه SSTables جفت key-value مرتب شده بر اساس ایندکس رو نگه می‌داره. اما شیوه کارش اینطوره که دیتابیس رو به بلاک‌ها / پیج‌هایی با سایز مشخص می‌شکنه، (4KB یا بیشتر) و در هر زمان در یک پیج می‌نویسه یا می‌خونه. هر پیج می‌تونه به یک پیج دیگه رفرنس بده، البته داخل دیسک بجای مموری. وقتی در یک پیج جا برای اضافه کردن نباشه، اون پیج به دو پیج نیمه پر تقسیم میشه. B-Tree با n کلید، همیشه عمق O(log n) داره.

فرض کنین وسط دو نیم کردن پیج‌ها دیتابیس کرش کنه و رفرنس والدشون آپدیت نشده باشه، اونوقته که دو تا پیج یتیم خواهیم داشت که رفرنسی بهشون نداریم، برای این مشکل از دیتا استراکچر دیکه‌ای روی دیسک استفاده می‌کنیم به نام write-ahead log یا redo log که به صورت append-only file هست که هر تغییرات B-Tree قبل از انجام درون این فایل نوشته میشه تا در صورت کرش براون اساس بازسازی بشه. همینطور برای حل مشکل همزمانی از latches یا همون lightweight locs استفاده میشه.

OLAP (Online Analytical Processing): Data Warehouse

OLTP (Online Transaction Processing): It supports day-to-day business operations.

وقتی واقعا دیتا زیاد باشه، انجام کارهای تحلیلی می‌تونه سیستم اصلی که داره به مشتری سرویس میده رو با اختلال روبرو بکنه. برا همین یک نسخه readonly از اطلاعات رو در data warehouse نگهداری می‌کنیم که قابلیت کوئری‌های پیچیده رو داره. به طور مثال Microsoft SQL Server and SAP HANA

Distributed Data

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

• پایداری بیشتر به دلیل اینکه ترافیک رو بین اون‌ها می‌تونیم بالانس کنیم.

• در دسترس بودن و خطاناپذیری بیشتر به دلیل اینکه حتی اگر کل دیتاسنتر هم بیاد پایین، یکی دیگه هست که جایگزینش بشه.

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

ما می‌تونیم به صورت عمودی رشد بدیم، یعنی CPU و RAM رو قدرتش رو دو برابر کنیم که این هزینه‌اش بیشتر از استفاده از دو سیستم مجزاست و هم از طرفی لزوما خروجی دو برابر نمیشه. اگرم بیایم از دو سیستم مجزا و یک دیسک اشتراکی استفاده کنیم دردسر محدودیت‌های قفل دسترسی هر سیستم برای scale کردن ایجاد میشه. راهکار دیگه معماری shared-nothing هست که به صورت افقی رشد می‌دیم. در ادامه درباره این روش صحبت می‌کنیم.

Replication Vs. Partitioning

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

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

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

Replication

به هر نودی که یک کپی از دیتابیس رو نگه‌ می‌داره، می‌گیم رپلیکا. هر دیتایی که نیازه در دیتابیس نوشته بشه باید توسط همه رپلیکاها پردازش بشه. راه‌حل متداول به نام leader-based replication شناخته میشه (یا
atcive/passive و یا master/slave). که به این صورت کار می‌کنه:

• یکی از رپلیکاها به عنوان لیدر شناخته میشه (master or primary) زمانی که کاربر می‌خواد توی دیتابیس بنویسه، باید درخواستش رو به لیدر بفرسته که دیتای جدید رو در استوریج خودش بنویسه.

• سایر رپلیکاها که به عنوان دنبال‌کننده شناخته میشن (read replica, slave, secondries or hot standbys) زمانی که لیدر دیتای جدید رو در استوریج خودش نوشت، همنیطور تغییرات دیتا رو برای همه دنبال‌کننده‌هاش به عنوان بخشی از replication log یا change stream می‌فرسته. هر دنبال‌کننده، لاگ رو از لیدر می‌گیره و کپی خودش رو بر اون اساس آپدیت می‌کنه.

• زمانی که کاربر می‌خواد دیتا رو از دیتابیس بخونه، می‌تونه به لیدر یا هرکدوم از دنبال‌کننده‌ها کوئری بزنه.

این روش پیش‌فرض بسیاری از دیتابیس‌ها و حتی message broker هاست.

حالا این به روز رسانی دنبال‌کننده‌ها می‌تونه به دو صورت باشه:

• به صورت synchronous: لیدر صبر می‌کنه که دنبال‌کننده تایید کنه که تغییرات رو دریافت کرده و بعد به کاربر تایید رو بر می‌گردونه.

• به صورت asynchronous: لیدر بدون صبر کردن برای گرفتن تایید از دنبال‌کننده، به کاربر تایید رو میده.

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

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

• یک snapshot از لیدر می‌گیریم.

• در نود دنبال‌کننده جدید کپی می‌کنیم.

• دنبال‌کننده به لیدر متصل میشه و تمامی دیتاهای تغییرات از زمانی که snapshot گرفته شده به بعد رو دریافت می‌کنه که نیازمند که جایگاه replication log اون snapshot ای که گرفتیم مشخص باشه که در PostgreSQL بهش log sequence number و در MySQL بهش binlog cordinates می‌گیم.

• وقتی همه تغییرات گرفته و اعمال شد می‌گیم که caught up کرده و از اینجا به بعد تغییرات لیدر رو لحظه‌ای دریافت می‌کنه.

زمانی که یک دنبال‌کننده به هر دلیلی مشکل می‌خوره به کمک لاگی که داره می‌دونه که آخرین تغییری که اعمال کرده چی بوده و همه تغییرات بعد اون رو از لیدر دریافت می‌کنه و خودش رو به روز می‌کنه.

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

• تعیین به مشکل خوردن لیدر: معمولا در صورتی که از یک تایمی بیشتر پاسخ‌دهی طول بکشه (مثلا ۳۰ ثانیه) بجز مواردی که برای maintenance خودمون آوردمیش پایین، لیدر رو مرده در نظر می‌گیریم.

• انتخاب لیدر جدید: این فرآیند می‌تونه از طریق روند انتخابات که توسط اکثریت دنبال‌کننده‌ها انتخاب بشه و یا انتخاب از قبل توسط controller node انجام بشه. معمولا مناسب‌ترین نود برای لیدر شدن، نودی هست که به‌روز ترین تغییرات رو داره تا دیتای کمتری از دست بره.

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

یکسری مشکلات درطی فرآیند failover ممکنه رخ بده:

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

• این پاک کردن دیتاهای رپلیکیت نشده زمانی که یک سیستم ذخیره‌سازی بیرون از دیتابیس متصل به دیتابیسه، می‌تونه خطرناک باشه، مثلا ردیسی که داره از id که به صورت auto increment دیتابیس استفاده می‌کنه و بعد از تغییر لیدر، یکسری از این id ها توسط لیدر قبلی ارسال شده و بعد چون رپلیکیت نشده بوده دوباره این id ها استفاده میشن.

• یا سناریویی که دو نود فکر کنن لیدر هستن.

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

همه این موارد باعث میشه که گاهی در سیستم‌هایی که امکان اتومات کردن فرآیند failover وجود داره، باز هم به صورت دستی انجام بشه.

انواع پیاده‌سازی Replication Logs:

• روش Statement-based replication: ساده‌ترین روش، لیدر هر درخواست نوشتن رو لاگ می‌گیره و به دنبال‌کننده‌ها می‌فرسته. در ورژن‌های قبل ۵.۱ MySQL استفاده میشده.

• روش Write-ahead log shipping: به روش log-structured storage engine (SSTables and LSM-Trees) و یا به روش B-Trees که قبلا در موردشون صحبت کردیم. در هر دو روش لاگ به صورت append-only sequence ای از بایت‌ها که شامل همه نوشتن‌ها در دیتابیس میشه هست. در PosgreSQL و Oracle استفاده میشه. استفاده از روش WAL این بدی رو داره که لاگ‌ها براساس ساختار دیتابیس هستن و در نتیجه این امکان رو نداریم که فرمت استوریج متفاوتی در لیدر و دنبال‌کننده‌ها داشته باشیم. این یعنی مثلا برای upgrade ورژن دیتابیس‌ها نیاز به downtime داری و نمیشه اول دنبال‌کننده‌ها و بعد لیدر رو به‌روز کرد.

• روش Logical (row-based) log replication: روش جایگزینی که بهمون این امکان رو میده که replication log از storage engine به صورت decouple باشه. یک logical log یک مجموعه از رکورد‌هاست که نوشتن در دیتابیس رو به این صورت شرح میدن: برای ردیف insert شده، لاگ شامل مقادیر جدید همه ستون‌هاست. برای ردیف پاک شده، لاگ شامل اطلاعات کافی برای شناسایی ردیف پاک شده‌است. برای ردیف آپدیت شده، لاگ شامل اطلاعات شناسایی ردیف یکتا آپدیت شده‌ به همراه مقادیر همه ستون‌هاست (حداقل مقادیر جدید همه ستون‌هایی که تغییر کردن). MySQL binlog از این روش استفاده می‌کنه. این روش برای ارسال دیتاها به data warehouse یا ساخت کاستوم ایندکس‌ها یا کش‌ها مناسبه.

• روش Trigger-based replication: تمامی روش‌هایی که صحبت شد بدون درگیر شدن با کد اپ بودن، اما گاهی ما می‌خوایم یکسری دیتای خاص رو فقط رپلیکیت کنیم یا از یک نوع دیتابیس به یک نوع دیگه رپلیکیت کنیم یا لازم داریم که یک منطق حل تعارض رو پیاده کنیم، نیاز خواهیم داشت که رپلیکیشن رو در لایه اپلیکیشن انجام بدیم. در بسیاری از دیتابیس‌های رابطه‌ای این فیچر برای این کار وجود داره: triggers and stored procedures - یک تریگر این امکان رو میده که کدی رو رجیستر کنیم که زمانی که دیتا تغییر کرد اتومات اجرا بشه. این روش سربار بیشتری داره و احتمال ایجاد باگ هم افزایش پیدا می‌کنه ولی آزادی عمل بیشتری میده.

Problems with Replication Lag

read-your-writes consistency (read-after-write consistency):

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

• دیتایی که کاربر ممکنه ویرایش کرده باشه از لیدر خونده بشه و سایر دیتاها از فالورها خونده بشه. مثلا همیشه اطلاعات پروفایل خود کاربر از لیدر خونده میشه.

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

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

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

اگر کاربر به طور همزمان با چند دیوایس مثل گوشی و سیستمش با برنامه کار کنه، پیچیدگی بیشتری می‌تونه اضافه بشه که بتونه در لحظه در دیوایس دیگرش تغییرات رو ببینه:

cross-device read-after-write consistency:

• روشی که نیاز به ذخیره آخرین زمان ایجاد تغییر کاربر داشت، نیاز داره که centralized بشه که در هر دو دیوایس بتونه زمان رو داشته باشه.

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

Monotonic Reads

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

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

Consistent Prefix Reads

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

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

Multi-Leader Replication

این مدل به بیش از یک نود امکان نوشتن رو میده، ولی همچنان رپلیکیشن وجود داره و هر نودی که عملیات نوشتن رو انجام میده باید تغییرات رو به همه نودها ارسال کنه. در این روش هر لیدر نسبت به بقیه لیدرها نقش فالور رو هم داره. به این مدل master-master و یا active/active replication هم می‌گن.

معمولا به ندرت منطقی میاد که در یک دیتاسنتر از این مدل استفاده بشه.

موارد استفاده:

Multi-datacenter operation

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

ابزارهایی که برای پیاده سازی این روش می‌شه استفاده کرد: Tungsten Replicator for MySQL, BDR for PostgreSQL, and GoldenGate for Oracle
این روش نقاط منفی‌ای هم داره: اگر دیتای یکسانی به طور همزان در دو دیتاسنتر تغییر کنه، این کانفلیکت نوشتن باید مدیریت بشه. و یا مواردی مثل auto-incrementing keys, triggers, and integrity constraints می‌تونن در این روش، ایجاد مشکل بکنن.

Clients with offline operation

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

Handling Write Conflicts

بزرگترین مشکل رپلیکیشن مولتی لیدر اینه که کانفلیکت نوشتن ممکنه رخ بده و این یعنی وجود conflict resolution ضروریه. مثالش اینه که دو کاربر به طور همزمان عنوان یک مقاله رو تغییر بدن.

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

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

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

• به هر نوشتن یک شناسه یکتا یا timestamp بدیم که بر اون اساس بالاترینش به عنوان وضعیت نهایی شناخته بشه. (به این روش Last Write Wins می‌گیم) این روش می‌تونه منجر به از دست رفتن دیتا بشه.

• به هر رپلیکا یک شناسه یکتا بدیم و نوشتن‌هایی که از رپلیکای با شناسه بالاتره در اولویت باشه، این روش هم منجر به از دست دادن دیتا میشه.

• به روشی مقادیر رو باهم ترکیب کنیم، مثلا به ترتیب الفبا مرتب کنیم و باهم ترکیب کنیم، مثلا میشه (عنوان اول/عنوان دوم)

• مغایرت رو در یک ساختار داده که همه اطلاعات رو نگه‌داره ذخیره کنیم و کدی بنویسیم که بعدا به یک روشی در آینده مغایرت رو حل کنه. (شاید با پرسیدن از کاربر)

Custom conflict resolution logic

منطق حل مغایرت میشه در زمان نوشتن یا خواندن فراخوانی بشه، توجه داشته باشین که این حل مغایرت در سطح یک رکورد یا داکیومنت انجام میشه و نه در سطح atomic transaction.

Multi-Leader Replication Topologies

• توپولوژی دایره‌ای (circular): به تریتب به صورت دایره‌ای لیدرها بهم تغییرات رو اطلاع میدن.

• توپولوژی ستاره‌ای (star): یک لیدر در مرکز قرار می‌گیره و سایر لیدرها با اون تغییرات‌شون به اشتراک میذارن.

• توپولوژی همه به همه (all-to-all): تمام لیدرها با هم تغییرات‌شون رو به اشتراک میذارن.

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

Leaderless Replication

در روش‌های قبلی، لیدر تصمیم می‌گیره که به چه ترتیبی نوشتن انجام بشه و دنبال‌کننده‌ها به همون ترتیب، نوشتن رو انجام میدن. اما یک راهکار متفاوت اینه که همه رپلیکاها مستقیما نوشتن رو از کاربر قبول کنن، این روش که به Dynamo-style شناخته میشه در Dynamo, Riak, Cassandra, Voldmort استفاده میشه. در بعضی از پیاده‌سازی ها خود کاربر اطلاعات رو به رپلیکا‌ها میفرسته و در بعضی‌ها یک نود هماهنگ‌کننده، از طرف کاربر این کار رو انجام میده.

اگر در روش لیدر دار، یک رپلیکا از دسترس خارج میشد، بعد برگشت failover اجرا میشد. اما در روش بدون لیدر، سناریو failover وجود نداره. دیتا به ۳ رپلیکا میره و دوتاشون ok میدن و سومی هیچ پاسخی نمیده. کاربر اوکی در نظر میگیره و ادامه میده. بعدا موقع دریافت اطلاعات، اطلاعات رو از هر سه سرور می‌گیره، به همراه یک Version number که برای مشخص کردن این که کدوم اطلاعات جدیدتره استفاده میشه.

Read repair and anti-entropy

الگو رپلیکایی باید بتونه مطمئن بشه که در نهایت همه دیتاها در همه رپلیکاها کپی میشه. بعد بازیابی یک نود، دو راهکار وجود داره:

• راهکار Read Repair: وقتی کاربر از چندین نود به طور موازی خوند، می‌تونه دیتای غیربه‌روز رو شناسایی کنه و دیتای جدید‌تر رو دوباره به رپلیکایی که دیتاش به‌روز نیست بنویسه. این راهکار برای مقادیری که به طور مکرر خونده میشن مناسبه.

• راهکار Anti-entropy process: بعضی از datastore ها یک پردازش بک‌گراند دارن که که به طور مرتب به دنبال تفاوت دیتا بین رپلیکاها می‌گردن و هر دیتای از دست رفته رو از یک رپلیکا در رپلیکای دیگه کپی می‌کنن. در این روش، هیچ ترتیب خاصی برای کپی نوشتن‌ها وجود نداره و ممکنه تاخیر زیادی قبل کپی کردن داده‌ها وجود داشته باشه.

Quorums for reading and writing

برای اینکه بدونیم حداقل تعداد رپلیکایی که باید تایید نوشتن رو بدن و در خوندن باید ازشون دیتا رو گرفت رو بدونیم، بیان تعداد کل رپلیکاها رو n و هر نوشتن باید توسط تعداد w نود تایید بشه تا نوشتن موفق در نظر گرفته بشه و هر کوئری باید حداقل از r نود خونده بشه. تا زمانی که w + r > n باشه، ما انتظار داریم که دیتای به روز در خوندنمون دریافت کنیم چون حداقل یکی از r نودمون، دیتای به روز رو خواهد داشت. این مقادیر n, w, r کانفیگور میشه. به طور معمول n یک عدد فرد و w = r = (n + 1) / 2 در نظر گرفته میشه.

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

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

• ارور برگردونیم.

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

به روش دوم sloppy quorum می‌گیم. نوشتن و خوندن همچنان به w و r پاسخ موفق نیاز دارن، اما ممکن شامل نودهایی باشن که به عنوان نود home اون مقادیر تعریف نشدن. وقتی مشکل شبکه برطرف شد، هر نوشتنی که یک نود از طرف نود دیگه به طور موقت پذیرفته بوده، به نود home مربوطه‌اش ارسال میشه که به این کار hinted handoff می‌گیم. توی این روش نمی‌تونیم مطمئن باشیم که داده کهنه خونده نمیشه، چون آخرین مقدار ممکنه در یک نود خارج از n نود نوشته شده باشه. این روش در همه پیاده‌سازی‌های Dynamo اختیاری هست و در Riak پیش‌فرض فعاله، در Cassandra و Voldemort پیشفرض غیرفعاله.

در معماری بدون لیدر پیاده سازی چند دیتاسنتری هم امکان‌پذیره. Cassandra و Voldemort اینطوره که n رو همه نودها در همه دیتاسنترها در نظر می‌گیرن و کاربر معمولا به حدنصابی از نودها در همون دیتاسنتر برای نوشتن نیاز داره. و بعد به صورت async به بقیه دیتاسنترها منقل میشه. در Riak عدد n تعداد رپلیکاها در یک دیتاسنتر رو نشون میده.

به طور کلی در قبال دو عملیات A و B، سه حالت وجود داره، عملیات A قبل از B رخ داده باشه، عملیات B قبل از A رخ داده باشه و یا A و B به طور همزمان (concurrent) رخ داده باشن. اگر یک عملیات قبل از دیگری رخ داده باشه، ما عملیات قبلی رو overwrite می‌کنیم، اما اگر به صورت همزمان رخ داده باشن، ما یک کانفلیکت داریم که باید حل بشه. در واقع معنی concurrent این نیست که در یک زمان انتفاق افتاده باشن، چون ممکنه به‌دلیل کندی شبکه، به طور همزمان به ما نرسن، اما همچنان concurrent هستن، در واقع concurrent یعنی دو عملیات که از یکدیگر باخبر نباشن.

Partitioning

هر پارتیشن یک دیتابیس کوچیکه. دلیل اصلی پارتیشن‌بندی داده، scalability هست. پارتیشن‌های متفاوت می‌تونن در نودهای مختلف قرار بگیرن. پارتیشن‌بندی معمولا همراه با رپلیکیشن انجام میشه که کپی هر پارتیشن در چندین نود نگهداری بشه. روی یک نود می‌تونه چندین پارتیشن باشه، که یکی‌شون لیدر هست و بقیه فالور سایر پارتیشن‌ها. اگر این پارتیشن‌بندی طوری انجام بشه که فشار روی یک نود باقی بمونه و باقی پارتیشن‌ها بیکار باشن به این پارتیشن با لود بالای نامتناسب می‌گیم hot spot. برای حلش می‌تونیم رکورد‌ها رو به نود ها به طور رندوم اساین کنیم اما به این روش نمی‌دونیم چی کجاس و به طور همزمان باید به همه نود‌ها کوئری بزنیم.
پارتیشن‌بندی با رنج کلید: اگر دیتا مدل‌مون به صورت key-value باشه میشه مشابه دیکشنری براساس کلید به صورت پیداش کرد. یک راه پارتیشن‌بندی، اساین کردن یک رنج از کلیدها به هر پارتیشنه. این رنج می‌تونه لزوما مساوی نباشه. برای پخش‌کردن دیتا به صورت مساوی، حدود پارتیشن‌ها لازمه که براساس دیتاها مشخص بشه. در هر پارتیشن می‌تونیم کلیدها رو به صورت سورت شده نگه‌داریم. بدی این روش اینه که می‌تونه موجب hot spot بشه، مثلا دیتابیسی که براساس تاریخ پارتیشن بندی شده و دیتای سنسورها درونش ذخیره میشه، همه نوشتن‌ها به یک دیتابیس واحد میرن. راهکارش اینه که از کلید دیگه‌ای بجای تاریخ استفاده کنیم.
پارتیشن‌بندی با کلیدهای هش: به دلیل ریسک hot spot بسیاری از distributed datastore‌ها از این روش استفاده می‌کنن. فرض کن هش ۳۲ بیتی داری، هرچقدر رشته ورودیت مشابه هم باشه، هش‌اش به طور مساوی در محدوده اعداد توزیع شده است. حالا فرض کن در یک شبکه اجتماعی همه پست‌های یک کاربر در یک بازه زمانی رو می‌خوایم، با این روش، هرکدومشون توی یک شارد هست و باید به همه ریکوئست بزنیم. راهکاری که کاساندرا داره اینه که compound primary key داره که شامل چند ستونه، فقط بخش اول کلید هش هست که پارتیشن رو مشخص کنه اما بقیه ستون‌ها به عنوان index پیوسته برای سورت دیتا استفاده میشه.
اما اگر بیشتر خوندن و نوشتن‌ها برای یک کلید یکسان باشه، بازم ما hot spot رو داریم. فرض کن یک سلبریتی در شبکه اجتماعی با میلیون‌ها فالور می‌تونه طوفان راه بندازه و کلی نوشتن بیاره سمت یک نود، یک راهکار اینه که به اول یا آخر کلید یک عدد رندوم دو رقمی اضافه کنیم، با اینکار به ۱۰۰ کلید به طور مساوی تقسیمش کردیم، اما باید حواسمون به تریدآف‌اش هم باشه که موقع خوندن هم باید به ۱۰۰ کلید متفاوت رجوع کنیم و این ۱۰۰ کلید رو باهم ترکیب کنیم. بهتره که این راهکار رو فقط برای hot key های خاصی انجام بدیم و یکجا ذخیره کنیم که کدوم کلیدها split شدن.
پارتیشن‌بندی secondary index با Document: وقتی ایندکس ثانویه داریم، در این روش هرپارتیشن کاملا مجزا است و هرکدوم جداگانه ایندکس ثانویه‌اش رو نگه می‌داره که فقط داکیومنت‌های توی همون پارتیشن رو پوشش میده. به همین دلیل document-partitioned index به local index هم شناخته میشه. به این روش که به همه پارتیشن‌ها درخواست میزنیم و دیتا رو دریافت و ترکیب می‌کنیم و برمی‌گردونیم، می‌گیم scatter/gather.
پارتیشن‌بندی secondary index با Term: یک گلوبال ایندکس می‌سازیم که همه دیتاها در همه پارتیشن‌ها رو پوشش میده. اگرچه همه اون ایندکس رو روی یک پارتیشن نمی‌تونیم ذخیره کنیم. گلوبال ایندکس هم باید پارتیشن‌بندی بشه ولی می‌تونه به صورت متفاوتی از key index پارتیشن‌بندی بشه به این روش term-partitioned می‌گیم. این‌کار خوندن رو سریع‌تر می‌کنه اما باعث کندتر شدن نوشتن میشه.

Rebalancing Partitions

به فرایند انتقال داده از یک نود به نود دیگه در یک کلاستر، میگیم rebalancing. حداقل نیازمندی‌های این کار ایناس:

• بعد ریبالانسینگ، لود (نگهداری داده‌ها، خوندن و نوشتن‌ها) به صورت منصفانه‌ای بین نودهای کلاستر تقسیم شده باشه.

• در حین ریبالانسیگ، دیتابیس به پذیرفتن خوندن و نوشتن‌ها ادامه بده.

• بیشتر از دیتاهای ضروری، نباید بین نودها جابه‌جا بشه که مطمئن باشیم ریبالانسینگ، سریع و با مینیموم لود شبکه و دیسک انجام میشه.

استراتژی‌های ریبالانسینگ:

کاری که نباید بکنی: hash mod N: توی این روش می‌گیم که خب مثلا ۱۰ تا پارتیشن داریم که از ۰ تا ۹ هستن، پس بیایم hash % 10 بگیریم و خروجیش یک عدد بین ۰ تا ۹ هست و بریم تو اون پاریتیشن ذخیره کنیم، مشکل این روش اینه که اگر تعداد پارتیشن‌ها بشه ۱۱ تا، نتیجه hash % 11 برای همه ایندکس‌ها متفاوت میشه و همه رو باید جابه‌جا کنیم.

• و fixed number of partitions: فرض کن یک دیتاست یک کلاستر با ۱۰ نود داره که به ۱۰۰۰ پارتیشن از بیرون تقسیم شده، پس حدودا ۱۰۰ پارتیشن به هر نود اساین شده. الان اگر یک نود به کلاستر اضافه بشه، این نود از هر نود دیگه می‌تونه چند پارتیشن قاپ بره تا دوباره به طور مساوی تقسیم بشن. اگر هم نودی از کلاستر حذف بشه، معکوس همین حالت اتفاق میوفته. فقط همه پارتیشن بین نودها جابه‌جا میشه. تعداد پارتیشن‌ها تغییری نمی‌کنه و فقط assignment پارتیشن به نودها تغییر می‌کنه.

• و Dynamic partitioning: برای دیتابیس‌هایی که key range partitioning هستن، اینکه یک تعداد ثابت پارتیشن با حدود ثابت داشتن می‌تونه راضی کننده نباشه. در این روش یک thershold تعریف میشه و اگر یک پارتیشن به سقف محدوده رسید، به دو پارتیشن مساوی می‌شکنه و اگر به کف محدوده رسید، با پارتیشن مجاورش ترکیب میشه. خوبی این روش اینه که بنا به حجم داده، تعداد پارتیشن‌ها کم و زیاد میشه.

• و Partitioning proportionally to nodes: در دو مورد قبلی، تعداد پارتیشن‌ها ثابت بود، اما در این مورد، پارتیشن‌ها هم متناسب با تعداد نودهاست. در این مورد، سایز پارتیشن متناسب با دیتاست تغییر می‌کنه، بدون اینکه تعداد نودها تغییر کنه. وقتی یک نود اضافه میشه، بخشی از داده‌های هر پارتیشن به صورتی که درنهایت ترافیک عادلانه‌ای روی همه نودها باشه، برداشته میشه و به نود جدید منتقل میشه.

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

درباره Request Routing:

سه راهکار وجود داره:

• اوکی باشه که کاربر به هر نودی خواست درخواست بده، اگر نود بتونه اون درخواست رو پاسخ میده و گرنه به نودی که مرتبطه می‌فرسته و جواب رو می‌گیره و به کاربر میده.

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

• لازمه که کلاینت از پارتیشن‌بندی و وظایف‌شون باخبر باشه و با نود مربوطه مستقیم ارتباط برقرار کنه.

در همه این حالت‌ها لازمه که از تغییرات باخبر باشن که بتونن درست عمل کنن. معمولا از سرویس‌های coordination مثل Zoo-Keeper استفاده میشه که از تغییرات routing باخبر میشن.

Transactions

در دیتاسیستم‌ها کلی فاجعه می‌تونه رخ بده، سخت‌افزار یا نرم‌افزار به مشکل بخوره، اپ کرش کنه، مشکل شبکه پیش بیاد، race condition بوجود بیاد و...

معنی transaction یک روش برای برنامه‌هاست که چندین خوندن و نوشتن رو باهم گروه کنن و تبدیل به یک واحد منطقی بکنن. درواقع یعنی همه خوندن و نوشتن‌ها در یک عملیات انجام بشن. حالا می‌خواد همه‌اش انجام بشه (commit) یا خطا بخوره (abort, rollback) و اینطوری می‌تونیم مطمئن باشیم که عملیاتی نصفه انجام نشده.

The Meaning of ACID

به گارانتی ایمنی که transaction میده غالبا ACID می‌گن که مخفف Atomicity, Consistency, Isolation, Durability هست.

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

معنی Consistency: خیلی معنی گسترده‌ای داره، ولی در ACID یعنی اینکه وقتی توی داده‌هات منطقی داری که باید همیشه درست باشه، مثلا توی سیستم حسابداریت اعتبار و بدهی‌ها باید همیشه بالانس باشه. اگر قبل ترنزکشن بالانس بوده و عملیات ترنزکشن هم بالانس باقی میذارش، می‌تونی مطمئن باشی که بعد انجام ترنزکشن هم بالانس خواهد بود.

معنی Isolation: اگر به طور همزمان چندین کاربر به یک دیتا بخوان دسترسی پیدا کنن، ممکنه مشکل concurrency (race condition) بوجود بیاد. Isolation در اینجا یعنی اینکه ترنزکشن‌های همزمان از یکدیگه ایزوله هستن و نمی‌تونن روی هم تاثیر بذارن.

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

Weak Isolation Levels

زمانی concurrency رخ میده که یک ترنزکشن دیتایی بخونه که همون موقع داره توسط ترنزکشن دیگه‌ای تغییر داده میشه و یا زمانی که دو ترنزکشن هم‌زمان دارن یک دیتا رو تغییر میدن. پیدا کردن مشکل کانکارنسی، واقعا سخته و با تست‌کردن واقعا سخته بخوای پیداش کنی. برای همین دیتابیس سعی می‌کنه این مشکل به سمت لایه اپ نیاد، به طوری که انگار اصلا مشکل کانکارنسی وجود نداره. اما مثلا serializable isolation که یعنی در هر زمان فقط یک درخواست اجرا بشه، هزینه زیادی داره و در بعضی از اپ‌ها ممکنه نخوایم این هزینه رو بدیم.

بررسی چند Isolation level

سطح Read Committed:

اولیه‌ترین سطح ایزوله کردنه. دو تا گارانتی میده:

• وقتی داری از دیتابیس می‌خونی، فقط چیزی رو می‌بینی که کامیت شده (no dirty reads). اگر یک ترنزکشن درحال نوشتن یکسری داده در دیتابیس باشه و هنوز کامیت یا abort نکرده باشه‌اش، آیا ترنزکشن دیگه می تونه ببینه‌اش؟ اگر آره، بهش می‌گیم dirty read. دو تا دلیل داره که ازش استفاده کنیم، اول اینکه تغییرات کامل نشده هنوز: مثلا می‌بینه ایمیل جدید اومده اما هنوز کانتر ایمیل جدید اضافه نشده. دوم اینکه ممکنه بعد اینکه دیتارو گرفتیم، ترنزکشن ناموفق بشه و roll back بشه ولی ما دیتاش رو گرفتیم.

• وقتی داری در دیتابیس می‌نویسی، فقط چیزی رو تغییر میدی که کامیت شده (no dirty writes). یعنی نوشتن، تا زمانی که ترنزکشن قبلی کامیت یا abort بشه، به تعویق میوفته. این راهکار مساله race condition اضافه کردن دو پردازش به مقدار یک counter همزمان رو حل نمی‌کنه. اما این مشکل که فرض کن دو نفر می‌خوان یک ماشین رو بخرن و برای یکی نمایش پیغام خرید بده و برای اون یکی ایمیل خرید بره رو حل می‌کنه.

سطح Snapshot isolation:

هر ترنزکشن، از consistent snapshot دیتابیس داده‌ها رو می‌خونه. یعنی فقط دیتاهایی رو می‌خونه که تا قبل از شروع ترنزکشن در دیتابیس کامیت شدن. اینطوری وقتی یک بک‌آپ طولانی می‌گیریم. یکسری دیتاها در طول پروسه بک‌آپ آپدیت نمیشن. برای این کار، دیتابیس چندین نسخه از کامیت‌های مختلف نگه میداره (Multi-Version Concurrency Control) برای اینکار، هر کامیت یک ID می‌گیره و بر اون اساس مشخص میشه که کدوم نسخه کامیت به ازای هر ترنزکشن استفاده بشه. در این روش، زمانی که garbage collector میاد و نسخه‌ای که هیچ ترنزکشنی ازش استفاده نمی‌کنه رو پاک می‌کنه، index های مرتبط با اون نسخه رو هم پاک می‌کنه. اسم دیگه ای که بهش می‌گن repeatable read هست.

Preventing Lost Updates

دو سطح ایزولیشن که تا الان صحبت کردیم، درباره ترنزکشن‌هایی بود که در حال خوندن نوشتن‌های همزمان بودن که کاری برای مشکل lost update (همزمان اضافه کردن یک کانتر) نمی‌کنن که این مشکل در چرخه read-modify-write پیش میاد.

Atomic write operations

خیلی از دیتابیس‌ها امکان نوشتن اتومیک رو میدن که با این روش نیازی به چرخه read-modify-write نیست:

UPDATE counters SET value = value + 1 WHERE key = 'foo';

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

Explicit locking

با استفاده از FOR UPDATE دیتابیس همه row ها روهایی که کوئری SELECT برمی‌گردونه رو lock می‌کنه:

BEGIN TRANSACTION;

SELECT * FROM figures
    WHERE name = 'robot' AND game_id = 222
      FOR UPDATE;

-- Check whether move is valid, then update the position
-- of the piece that was returned by the previous SELECT.
UPDATE figures SET position = 'c4' WHERE id = 1234;

COMMIT;

Automatically detecting lost updates

دیتابیس‌ها می‌تونن به صورت اتومات lost update ها رو شناسایی کنن و ترنزکشن رو متوقف کنن و مجبور به تلاش مجدد بکننش. در ایزولیشن repeatable PostgreSQL, serialization Oracle, snapshot isolation SQL Server به طور اتومات جلوی این اتفات گرفته میشه.

Compare-and-set

دیتابیس‌هایی که ترنزکشن ندارن، گاهی عملیات aotmic compare and set دارن. در این روش اگر مقدار از آخرین باری که خونده تغییر نکرده باشه، آپدیت اجرا نمیشه و باید بعدش چک کنیم که در صورتی که انجام نشده، تکرار بشه.

-- This may or may not be safe, depending on the database implementation
UPDATE wiki_pages SET content = 'new content'
    WHERE id = 1234 AND content = 'old content';

Write Skew and Phantoms

نوع دیگه‌ای از race condition بجز dirty writes و lost updates داریم، که بهش می‌گیم write skew، فرض کن شیفت آن‌کال بیمارستان اینطوره که باید حداقل یک دکتر همیشه باشه و امروز هلن و جک آن‌کال هستن، هر دوشون احساس مریضی می‌کنن و تقریبا به طور همزمان درخواست مرخصی می‌دن، هر دو ترنزکشن هم‌زمان، تعداد دکتر آن‌کال رو ۲ دریافت می‌کنن و هردو مرخصی می‌گیرن، حالا هیچ دکتری آن‌کال نیست که براساس قوانین درست نیست. write skew زمانی اتفاق میوفته که دوتا ترنزکشن به طور همزمان یک object رو می‌خونن و بخشی از اون رو آپدیت می‌کنن (ممکنه object های مختلفی رو آپدیت کنن).
در این مورد، atomic single-object operation کمکی نمی‌کنه چون چند object درگیرن. همینطور automatic detection هم نمی‌تونه این مورد رو شناسایی کنه. بهترین راهکار اگر نخوایم از serializable isolation استفاده کنیم، استفاده از explicity lock هست.

در همه موارد write skew این سه گام وجود داره:

• یک کوئری SELECT که با جستجو کردن یکسری شرایط، چک می‌کنه آیا شرایط خاصی وجود داره؟

• بنا به نتیجه کوئری اول، کد برنامه تصمیم می‌گیره که چطور ادامه بده.

• اگر برنامه تصمیم می‌گیره که ادامه بده، یک نوشتنی (INSERT, UPDATE, DELETE) در دیتابیس انجام میده. براساس این تغییر ایجاد شده، اگر نتیجه کوئری اول رو مجدد بگیری، نتیجه متفاوتی دریافت می‌کنی.

معنی phantom به این افکت می‌گن که نوشتن در یک ترنزکشن، روی کوئری سرچ در ترنزکشن دیگه تغییر ایجاد کنه.

Materializing conflicts

فرض کن سیستم رزرو اتاق جلسه می‌خوایم بنویسیم که افراد یک اتاق رو برای یک بازه زمانی خاص رزرو می‌کنن. اینجا اگر از SELECT FOR UPDATE استفاده کنیم، چیزی SELECT نمیشه، پس چیزی هم lock نمیشه. راهکار می‌تونه این باشه که یک جدول تعریف کنیم و برای بازه‌های زمانی مثلا ۱۵ دقیقه‌ای به ازای هر اتاق و بازه زمانی یک ردیف تعریف کنیم، مثلا برای بازه زمانی ۶ ماه آینده. اینطور، حالا می‌تونیم از SELECT FOR UPDATE استفاده کنیم. به این روش Materializing conflicts می‌گیم. اما این جذاب نیست که پای کنترل concurrency به کدمون برسه و بیاد داخل data model مون، برای همین این راهکار آخرین گزینه‌مون هست و مثلا serializable isolation خیلی گزینه بهتری هست.

Serializability

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

در اجرای ترنزکشن‌ها یک بخش خوبی از زمان صرف ارتباطات شبکه بین برنامه و دیتابیس میشه و اگر بخوایم فقط یک ترنزکشن در زمان پردازش کنیم، توان عملیاتی وحشتناک میشه، چون دیتابیس بیشتر زمانش رو باید منتظر بمونه. راهکار می‌تونه این باشه که از multi-statement transactions ها استفاده نکنیم و بجاش همه کد ترنزکشن رو به صورت stored procedure به دیتابیس بفرستیم. به این صورت ترنزکشن خیلی سریع‌تر بدون انتظار disk I/O یا شبکه، انجام میشه. اما معایبی هم داره که باعث شده محبوبیتش از دست بره، هر دیتابیسی زبون خودش رو داره و به روز نشدن و زشت به نظر میرسن. کدهای تو دیتابیس، مدیریت کردنشون سخته، سخته دیباگ بشن و مدیریت ورژن‌، مانیتورینگ، دپلوی‌شون سخته. دیتابیس خیلی پرفورمنسش مهمه و اگر کدش بد زده بشه، خیلی بدتر از کد بد سمت اپ هست. با این حال بعضی از دیتابیس‌ها از زبان‌های برنامه‌نویسی پشتیبانی می‌کنن. سریع‌ترن. اگر برنامه‌ای با نوشتن خیلی زیاد داشته باشیم، اینکه پردازش single-threaded transaction داشته باشیم، می‌تونه bottleneck جدی ایجاد کنه که یک راهکار می‌تونه پارتیشن‌بندی باشه که هر کدوم به طور جداگانه نوشتن رو انجام بدن.

Two-Phase Locking (2PL)

برای حدود ۳۰ سال این الگوریتم به طور گسترده برای serializability دیتابیس استفاده میشد. به این صورت عمل می‌کنه که چندین ترنزکشن این اجازه رو دارن که به طورهمزمان یک شی رو بخونن، با این شرط که هیچ‌کس در حال نوشتن اون نباشه. اما به محض اینکه یکی بخواد بنویسه، دسترسی اختصاصی، اجباری میشه. در این روش نه فقط نوشتن سایر نوشتن‌ها رو بلاک می‌کنه، بلکه خوندن‌ها رو هم بلاک می‌کنه و برعکس. این روش همه نوع race condition ها رو جلوگیری می‌کنه. برخلاف snapshot isolation که هیچ‌وقت reader ها writer ها رو بلاک نمی‌کردن و نه writerها readerها رو بلاک می‌کردن.

• اگر ترنزکشن A یک شی رو خونده و ترنزکشن B می‌خواد روی شی بنویسه، B باید صبرکنه تا A کارش رو commit یا abort کنه.

• اگر ترنزکشن A درحال نوشتن روی شی باشه و B بخواد مقدارش رو بخونه، B باید صبر کنه تا A کارش رو commit یا abort کنه.

برای پیاده‌سازی این روش دو نوع قفل داریم، shared mode و exclusive mode. هر ترنزکشنی که می‌خواد بخونه میاد و lock in shared mode می‌کنه، چندین ترنزکشن می‌تونن به طور همزمان این نوع قفل رو بکنن. اما اگر ترنزکشنی exclusive lock روی شی‌ای زده باشه، باید صبر کنن. اگر ترنزکشنی بخواد بنویسه، در صورتی می‌تونه که هیچ‌کدوم از دو نوع قفل روش نباشه و اون موقع exclusive lock میزنه. وقتی ترنزکشنی قفل زد، باید اون lock رو تا پایان ترنزکشن نگه‌داره. بزرگترین مشکل این روش پرفرمنسشه که بخاطر کار با lock ها و از سمت دیگه وقوع deadlockهاست.

حالت deadlock حالتیه که ترنزکشن A همینطور منتظر آزاد کردن lock توسط B گیر می‌کنه. در این موارد دیتابیس اتومات deadlock ها رو شناسایی و abort می‌کنه‌شون و لازمه که این ترنزکشن‌ها از سمت اپ دوباره انجام بشن.

Predicate locks

در روش predicate lock به این روش عمل می‌کنیم:

• اگر ترنزکشن A می‌خواد شی‌ای رو بخونه که یک condition ای داره (SELECT query) باید shared mode prediacate lock روی اون شرط کوئری بذاره. اگر ترنزکشن همزمان B روی اون شرایط exclusive lock گذاشته باشه، A باید صبر کنه.

• اگر ترنزکشن A بخواد insert, update or delete انجام بده، باید چک کنه که مقادیر جدید و قدیم با هیچ predictate lock ای شامل میشن، اگر شامل بودن باید صبر کنه تا ترنزکشنی که قفل رو زده، تموم بشه.

این روش، قفل روی حتی objectهایی که هنوز وجود ندارن و ممکنه در آینده بوجود بیان هم میزنه (phantoms). اگر two-phase locking شامل predictate lock بشه، دیتابیس جلوی همه write skew و انواع race condition‌ها میشه و ایزولیشنش serializable خواهد بود.

Index-range locks

متاسفانه predicate lockها به خوبی عمل نمی‌کنن، اگر کلی قفل توسط ترنزکشن‌های فعال وجود داشته باشه، چک کردن برای قفل‌های مرتبط، کار زمان‌بری میشه. برای همین معمولا بجاش از index-range locking استفاده میشه (بهش next-key locking هم می‌گن). روش کارش روی مثال سیستم رزرو اتاق به این صورته:

• میگه که index روی room_id هست، و دیتابیس میاد از این ایندکس برای پیدا کردن رزروهای اتاق ۱۲۳ استفاده می‌کنه و به سادگی روی نتایجش قفل میزنه.

• یا روش جایگزین، اگر time-based index استفاده شده باشه برای پیدا کردن رزروهای درحال انجام، قفل روی این رنج زمانی همه اتاق‌ها گذاشته میشه.

درواقع قفل روی فیلدی گذاشته میشه که براش index تعریف شده و رنج بیشتری رو نسبت به روش قبلی لاک می‌کنه.

Serializable Snapshot Isolation (SSI)

الگوریتم SSI بهمون full serializability رو میده اما مشکل پرفرمنس کمی نسبت به snapshot isolation داره. به روش Two-phase locking بهش مکانیزم pessimistic concurrenct control میگیم: بر این اساسه که هرچیزی ممکنه بد پیش بره، پس بهتره صبر کنن تا موقعیت امن باشه تا هر اقدامی انجام بشه. شبیه mutual exclusion برای محافظت از ساختار داده ها در برنامه‌نویسی‌های multi-thread هست. serial execusion نهایت این pessemistic هست که کل دیتابیس یا پارتیشن رو قفل می‌کنیم تا ترنزکشن انجام بشه. در مقابل serializable snapshot isolation یک تکنتیک کنترل همزمانی optimistic هست. که به این صورته که بجای متوقف کردن هرچیزی که ممکنه خطرناک باشه، ترنزکشن‌ها کارشون ادامه میدن، به این امید که همه چی خوب پیش بره، موقع کامیت کردن، دیتابیس چک می‌کنه که آیا اتفاق بدی ممکنه بیوفته؟ اگر بله، ترنزکشن abort میشه و باید retry کنه. در محیط‌هایی که ترنزکشن‌های زیادی اتفاق میوفته، روش خوبی نیست چون کلی ترنزکشن abort میشن.

Detecting stale MVCC reads

شناسایی خوندن تاریخ‌گذشته در MVCC: ایزولیشن snapshot معمولا با multy-version concurrency control پیاده‌سازی میشه. اینطور که ترنزکشن بعد شروع، تمام خوندن‌هاش رو از snapshot ای که موقع شروع ترنزکشن گرفته شده می‌خونه و بعد موقع کامیت، دیتابیس چک می‌کنه که آیا هیچ‌کدوم از نوشتن‌هایی که بعد از گرفتن snapshot نادیده گرفته شدن، کامیت شدن؟ اگر بله، ترنزکشن باید abort بشه. چرا صبر می‌کنیم تا کامیت که abort کنیم؟ چون که شاید ترنزکشن اصلا نوشتن نداشته باشه.

روش Serializable Snapshot Isolation نسبت به two-phase locking سریع‌تره، چون نیازی به صبر کردن پشت lock برای ترنزکشن‌ها نیست و مشابه snapshot isolation نوشتن‌ها، خوندن‌ها رو بلاک نمی‌کنن و برعکس. و در مقایسه با serial execution، این روش محدود به توان عملیاتی یک هسته CPU نیست و می‌تونه conflict های کل ماشین و حتی پارتیشن‌های مختلف در چند ماشین رو شناسایی کنه. چیزی که پرفرمنس کلی SSI رو مشخص می‌کنه نرخ abort هاست که برای کاهشش لازمه که read-write transaction ها تا حد خوبی کوتاه باشن (ترنزکشن‌هایی که فقط می‌خونن و طولانی هستن، اوکی می‌تونن باشن).

Network Faults in Practice

بنا به دلایل مختلف ممکنه بخشی از سیستم به مشکل بخوره، خیلی از سیستم‌ها لازمه که به طور اتومات بخش مشکل‌خورده رو شناسایی کنن:

• لودبالانسر لازمه که ارسال درخواست‌ها رو به نودی که مرده متوقف کنه.

• در دیتابیس‌های distributed با single-leader replication اگر لیدر مشکل خورد، یکی از دنبال‌کننده‌ها لازمه که تبدیل به لیدر جدید بشه.

خبر گرفتن از نودها می‌تونه راهکار خوبی باشه اما نمیشه روش حساب کرد، اگر TCP acknowledge بگه که packet رسیده، بازم ممکنه اپ قبل هندل کردنش کرش کرده باشه، برای اینکه مطمئن شیم موفق بوده، لازمه که پاسخ مثبت از برنامه رو بگیریم. اگر timeout تنها راه شناسایی مشکل باشه، چقد باید واستیم تا بگیم مشکل خورده؟ زیاد واستیم، کاربر باید منتظر بمونه، اگر کم واستیم، ممکنه اشتباهی بخاطر تاخیر در پاسخ، فکر کنیم که نود مرده با اینکه یک تاخیر موقت بوده. وقتی یک نود مرده در نظر گرفته میشه، مسئولیتش باید به یک نود دیگه منتقل بشه، که این‌کار فشار بیشتری به نودهای دیگه و شبکه وارد می‌کنه و تهش می‌تونه باعث cascading failure بشه. متاسفانه زمان مشخصی وجود نداره برای زمان جابجایی پکت (d) و زمان پردازشش (r) که بگیم اگر 2d+r طول کشید، یعنی از دست رفته. برای همین اینکه یک نود رو به طور دائم مرده در نظر بگیریم، مشکل سازه. مشابه موقع رانندگی که زمان طی مسیر وابسته به ترافیکه، شبکه هم همینطوره. انواع تاخیر در packet ها ممکنه اتفاق بیوفته:

• اگر چندین نود به طور همزمان تلاش کنن که پکت به یک مقصد یکسان ارسال کنن، network switch باید به صف کنه‌شون و دونه دونه به لینک شبکه مقصد ارسال کنه. در لینک شبکه‌های شلوغ، ممکنه لازم شه که یک پکت صبر کنه تا یک slot بتونه بگیره (بهش network congestion می‌گیم) و اگر خیلی زیاد باشن که صف پر بشه، پکت drop میشه و این یعنی اینکه با اینکه نتورک اوکیه، اما باید دوباره ارسال بشه.

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

• در محیط‌های virtualized، سیستم‌عامل گاهی برای ده‌ها میلی‌ثانیه متوثق میشه تا سیستم‌عامل دیگه‌ای از هسته‌های CPU استفاده کنه. در این زمان VM نمی‌تونه دیتایی که از شبکه اومده رو مصرف کنه و اون دیتا buffer میشه و این تاخیر شبکه رو بیشتر می‌کنه.

• در flow control که TCP داره، که هر نود، نرخ ارسالش رو محدود می‌کنه تا از overload جلوگیری کنه. که این یعنی یک صف بیشتر در ارسال‌کننده حتی قبل از اینکه دیتا وارد شبکه بشه.

از این گذشته، TCP اگر acknowledge در یک timeout به دستش نرسه، پکت رو از دست‌رفته در نظر می‌گیره و مجدد ارسال می‌کنه. اگرچه اپ این از دست‌رفتن پکت و ارسال دوباره رو نمی‌بینه و چیزی که میبینه یک تاخیر در شبکه‌اس.

تفاوت UDP با TCP: بعضی از برنامه‌هایی که نسبت به تاخیر حساس هستن، مثل ویدئوکنفرانس یا voice over IP از UDP بجای TCP استفاده می‌کنن. یک trade-off بین reliability و variability of delays وجود داره: در UDP دیگه flow control اجرا نمیشه و دوباره پکت‌های ازدست‌رفته رو ارسال نمی‌کنه. مناسب زمانیه که دیتا اگر تاخیر بخوره، بی‌ارزش میشه.

در public cloud و دیتاسنترهای اشتراکی، کلی از منابع بین کلی از مشتری‌ها مشترک هستن و میزان تاخیر متغیره، بهتره که بجای قرار دادن یک timeout ثابت، سیستم‌ها به طور مستمر زمان پاسخ رو اندازه بگیرن و یک مقدار متغیری (jitter) بهش اضافه کنن.

Synchronous Versus Asynchronous Networks

بیان خط تلفن‌های سیمی رو تصور کنیم، یک تماس تلفنی، نیاز به یک ارتباط نقطه به نقطه با یک پهنای باند ثابت داشت که دیتای صدا رو منتقل کنه، این روش هم قابل اتکا بود و هم زمان طی مسیر شبکه، ثابت و مشخص بود. به این صورت که مقدار بیت لازم از شبکه در موقع تماس رزرو شده بود و گارانتی شده بود که دقیقا ۱۶ بیت از صدا هر ۲۵۰ میکروثانیه منتقل میشه. به این نوع شبکه‌ها Synchronous می‌گیم. اما در شبکه‌های الان دیتاهای متفاوتی با سایزهای متفاوت و نامشخصی منتقل میشن و شبکه رزرو یک ارتباط نمیشه و طوری طراحی شدن که در سریع‌ترین حالت، دیتا در شبکه منتقل بشه.

Unreliable Clocks

در اپ‌ها زمان و Clock مهمه و از جنبه‌های متفاوتی بهش وابسته هستن:

• آیا ریکوئست timeout شده؟

• زمان پاسخ‌دهی صدک ۹۹ این سرویس چقدره؟

• چه مقدار کوئری در ثانیه به طور میانگین در ۵ دقیقه اخیر توسط سرویس هندل شده؟

• چقدر زمان هرکاربر در سایت گذرونده؟

• چه زمانی مقاله منتشر شده؟

• در چه تاریخ و زمانی، ایمیل یادآوری ارسال شده؟

• چه زمانی کش منقضی میشه؟

• زمان timestamp روی پیام ارور برای چه زمانی هست؟

کامپیوترهای مدرن حداقل دو نوع مختلف clock دارن: time-of-day clock و monotonic clock.

و time-of-day clock: بر اساس تقویم میاد و تاریخ و زمان رو برمی‌گردونه. که براساس تعداد ثانیه‌های گذشته از نیمه شب 1 jan 1970 هست. معمولا time-of-day با Network Time Protocol سینک میشه که این یعنی timestamp یک ماشین با بقیه ماشین‌ها یکیه. اگر ساعت محلی خیلی جلوتر از سرور NTP باشه، به اجبار تنظیم مجدد میشه و این یعنی در زمان به عقب برمی‌گرده.

و Monotonic clocks: مناسب اندازه گیری مدت زمان هستن (فاصله زمانی بین دو اتفاق) مثل timeout یا زمان پاسخگویی سرویس. مقدار خود clock بی‌معنی می‌تونه باشه، مثلا تعداد نانوثانیه‌هایی که از روشن کردن سیستم می‌گذره و بین دو تا سیستم، عدد متفاوتی بهت میده. در سرورهای با چند CPU می‌تونه تایمر جداگانه‌ای به ازای هر CPU باشه. اگر فرکانس ساعت بیشتر از 0.05% تندتر یا کندتر باشه، NTP درستش می‌کنه. اما این باعث جلو یا عقب پریدن ساعت نمیشه.

ساعت monotonic نیازی به synchronization نداره اما ساعت time-of-day لازمه که براساس NTP سرور یا یک منبع زمان خارجی ست بشه. روش‌های ما برای دریافت ساعت، به روش‌های متفاوتی می‌تونه صحیح نباشه:

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

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

• اگر یک نود به طور اتفاقی پشت فایروال برای NTP سرور قرار بگیره، ممکنه زمان اشتباهش تا مدتی قابل شناسایی نباشه.

• همگام‌سازی NTP بنا به تاخیر شبکه می‌تونه تحت تاثیر قرار بگیره.

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

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

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

• در نتیجه‌ی Leap seconds ما دقایقی خواهیم داشت که ۵۹ یا ۶۱ ثانیه هستن، که این فرضیات زمانی سیستم رو بهم می‌ریزه.

این امکان‌پذیره که به دقت خیلی بالا به کمک دریافت‌کننده‌های GPS و Percision Time Protocol دست پیدا کنیم. اما این نیاز به تلاش و تخصص زیادی داره و کلی مسیر برای اشتباه شدن ساعت وجود داره.

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

یک سناریو رو تصور کنیم که در multi-leader replication کلاینت اول روی نود ۱ یک کانتر رو مقدار میده و این مقدار replicate میشه به نود ۳ و اونجا، کانتر یکی بهش اضافه میشه ولی توی نود ۳ کلاک ۴ میلی‌ثانیه عقبه و وقتی رپلیکیت میشه به نود ۲، timestamp‌ اش عقب‌تر از مقدار دهی اولیه نود ۱ هست، در نتیجه به روش Last Write Wins مقدار نود ۱ به عنوان مقدار نهایی در نظر گرفته میشه و تغییر نود ۲ میپره. راهکارش اینه که بجای استفاده از monotonic clock که بهش phisical clocks هم می‌گیم، از logical clocks استفاده کنیم که به این صورته که بجای اندازه‌گیری زمان روز، ترتیب relative رویدادها رو نشون میده. در روش snapshot isolation معمولا از شمارشگر شناسه ترنزکشن استفاده میشه و اینطور میفهمه که ترتیب انجام ترنزکشن‌ها چیه، اما اگر دیتابیس‌ها distributed باشن، این کار شدنی نیست و باید از synchronized time-of-day clock استفاده کرد و برای رفع چالش معمولا از TrueTime API استفاده می‌کنن که یک بازه زمان رو میده که شامل حداقل و حداکثر (earliest, lastes) زمانه و با مقایسه این بازه با بازه ترنزکشن دیگه، بررسی می‌کنن که کدوم زودتر اتفاق افتاده، ولی برای مثال گوگل از GPS receiver و یا atomic clock ها در دیتاسنتر‌هاش استفاده می‌کنه.

سناریو دیگه‌ای که ساعت در سیستم‌های distributed می‌تونه خطرناک باشه، زمانیه که دیتابیس single leader per partioion داریم، لیدر فقط زمانی می‌تونه نوشتن‌ها رو قبول کنه که هنوز لیدر باشه و یک راهش اینه که lease رو از نودهای دیگه بگیره، lease یک چیزی شبیه lock هست که مشخص می‌کنه کدوم نود تا یک بازه زمانی مشخص leader هست و قبل منقضی شدن باید renew بشه وگرنه یک نود دیگه می‌گیردش. حالا فرض کنیم که مثلا ۱۰ ثانیه قبل منقضی شدن، نود لیدر تمدیدش می‌کنه ولی آخرین بار که چک کرده، ۱۵ ثانیه برنامه متوقف بشه و بعدش ادامه پیدا کنه، در این حالت، دیگه لیدر نیست ولی تا iteration بعدی متوجه نمیشه که دیگه لیدر نیست. و متاسفانه دلایل زیادی وجود داره که اجرای برنامه برای مدتی متوقف بشه:

• خیلی از زبان‌ها garbage collector دارن و حتی اگر به طور همزمان هم اجرا بشه، به طور کامل نمی‌تونه موازی اجرا بشه. و در بدترین حالتش برنامه رو بارها متوقف می‌کنن.

• در VM ها، ماشین مجازی می‌تونه suspend و resume بشه.

• در وسایل کاربر، مثل لب‌تابش، اجرا ممکنه متوقف و ادامه پیدا کنه، مثلا وقتی در لپ‌تاپ می‌بنده.

• در سیستم عامل‌ها content-switch به یک thread دیگه یا hyper switch به یک VM دیگه، می‌تونه اجرا رو متوقف کنه.

• اگر برنامه به صورت sync با دیسک کار کنه، ممکنه thread به دلیل کندی عملیات disk I/O متوقف بشه.

• اگر سیستم‌عامل طوری تنظیم شده باشه که اجازه swapping به دیسک رو بده، موقع دسترسی به memory ممکنه لازم باشه که از دیسک به مموری لود بشه و thread به دلیل کندی عملیات I/O متوقف بشه.

• در سیستم‌های Unix ممکنه که پردازش با ارسال سیگنال SIGNSTOP متوقف بشه و تا زمانی که سیگنال SIGCONT نیاد، ادامه پیدا نمی‌کنه.

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

برای محدود کردن اثر garbage collection میشه این زمان‌های کوتاه از دسترس خارج شدن رو برنامه‌ریزی کرد و درخواست‌ها رو در اون زمان به نودهای دیگه ارسال کرد و صبر کرد تا GC pause تموم بشه و به این روش درخواستی درحال پردازش متوقف نمیشه. راهکار دیگه اینه که از GC فقط برای short-lived object ها استفاده کنیم که سریع کالکت میشن و هر از چندگاهی پردازش‌ها رو رستارت کنیم و توی این زمان رستارت، ترافیک به سایر نودها بره.

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

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

• فقط یک نود لیدر در پارتیشن دیتابیس باشه.

• فقط یک ترنزکشن یا کاربر اجازه داشته باشه که lock یک منبع یا شی رو داشته باشه.

• فقط یک کاربر بتونه یک نام‌کاربری خاص رو بگیره.

برای این کار، quorum پاسخگو نیست، چون اگر مثلا نود لیدر متوقف شده باشه و حدنصاب نودها یک لیدر دیگه انتخاب کنه و نود لیدر قبلی بازیابی بشه و فک کنه هنوز لیدره، بازم مشکل در سیستم ایجاد می‌کنه. یا می‌تونیم client رو مجبور کنیم که lease رو قبل از دسترسی به فایل از lock server بگیره، اما اگر بازم کارش زیاد طول بکشه و lease منقضی بشه و کاربر دیگه تو این تایم lease رو بگیره و تغییرات بده، وقتی کاربر متوقف شده برگرده، فک می‌کنه lease معتبر داره و میاد در فایل می‌نویسه و فایل رو مشکل‌دار می‌کنه. برای حل این مشکل نیاز به راهکاری داریم که درخواست‌کننده بفهمه که باور "اون انتخاب شده بودنش" غلطه. یک راهکار ساده اسمش fencing هست. فرض کنین هروقت که lock server میاد lease میده، همراهش یک fencing token هم بده، که یک شمارشگره که هر بار لاک گرفته میشه یکی بهش اضافه میشه و هروقت کاربر درخواست نوشتن میده همراهش این توکن رو هم میفرسته و در صورتی که شماره توکن کمتر از آخرین نوشتنی باشه که انجام شده، رد میشه. اگر ZooKeeper به عنوان lock server استفاده بشه این اتفاق رو می‌تونه هندل کنه. اما مثلا برای مدیریت فایل میشه که این توکن رو توی نام فایل بیاریم.

Byzantine Faults

مشکل سیستم‌های distributed سخت‌تر میشه اگر ریسک این وجود داشته باشه که یک نود دروغ بگه، ارسال پاسخ‌های معیوب. مثلا ادعا کنه که یک پیام رو دریافت کرده اما در واقع نکرده باشه. به این نوع رفتارها Byzantine fault می‌گیم و به فرآیند به نتیجه رسیدن در همچین فضای بدون اعتمادی می‌گیم Byzantine Generals Problem. زمانی این اتفاق میوفته که یک نود از پروتکل‌ها پیروی نمی‌کنه و توسط attacker ها به شبکه نفوذ شده. مثلا در محیط هوا فضا، ممکنه مموری یا CPU در اثر تشعشعات دیتاهاشون ناقص بشه. یا در سیستم‌های چند سازمانی، بعضی از اونها، ممکنه بخوان دیگران رو فریب بدن. مثل شبکه بیت‌کوین.

اگر همه نودها برای سازمان خودتون و در دیتاسنتر باشه، این مشکل احتمالش کم خواهد بود اما اگر به طور کلی نودها رو صادق هم در نظر بگیریم، جا داره که سیستم رو دربرابر دروغ‌ها کوچیک با مکانیزم‌های ساده مقاوم کنیم: ممکنه بعضی از packet های نتورک ناقص بشن و از دست checksum که TCP, UDP دارن، در بره و خوبه که برای چنین مواردی چک‌سام در لایه اپلیکیشن داشته باشیم. و همینطور همه ورودی‌های کاربر رو چک کنیم که در محدوده‌ی محدودیت‌هامون باشن. یا NTP client ها رو با چندین آدرس سرور کانفیگ کنیم که از همه‌شون time range رو استعلام بگیرن و اگر سروری همگام نبود متوجه بشن.

برای تعریف system model یکسری فرضیه باید در نظر بگیریم. در خصوص فرضیه‌های timing این سه سیستم مدل رو داریم:

• مدل Synchronous: در این مدل، تاخیر شبکه، process pause و clock error ها در یک محدوده مشخص هستن.

• مدل Partially synchronous: در این مدل بیشتر اوقات در محدوده هستن اما گاهی ممکنه بیشتر بشه. مدل واقع‌گرایانه اس.

• مدل Asynchronous: در این مدل هیچ فرضیه‌ای درباره زمان وجود نداره و حتی timeout معنایی نداره.

و در مورد مشکل‌خوردن نود‌ها سه سیستم مدل متداول زیر رو داریم:

• مدل Crash-stop faults: یک نود که مشکل میخوره، میره و هیچوقت بر نمی‌گرده.

• مدل Crash-recovery faults: نود که مشکل می‌خوره، احتمالا بعد از یک زمان نامشخص شروع به پاسخگویی می‌کنه، اینطور فرض میشه که نودها یک stable storage دارن.

• مدل Byzantine (arbitrary) faults: نودها ممکنه هرکاری بکنن، از جمله تلاش برای فریب نودهای دیگه.

دو ویژگی safety و liveness و سیستم مدل، درستی یک الگوریتم distributed رو به خوبی نشون میدن:

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

Consistency and Consensus

توی این فصل روش‌های قوی‌تر consistency model در سیستم‌های distributed رو بررسی خواهیم کرد که خب در مقایسه با روش‌های ضعیف‌تر پرفرمنس پایین‌تر و نسبت به خطاها آسیب‌پذیرتر هستن.

Linearizability

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

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

سیستم single-leader replication لازمه مطمئن بشه که فقط یک لیدر هست و split brain اتفاق نیوفتاده. یک راه انتخاب لیدر به کمک lock هست. هر نودی که شروع به کار می‌کنه، سعی می‌کنه که lock رو بگیره و تنها یکی که موفق میشه، لیدر میشه. روش پیاده‌سازی lock مهم نیست، مهمه که فقط linearizable باشه: همه نودها موافق باشن که کدوم نود lock رو داره. Apache ZooKeeper، Apache Curator و linear storage service ها کمک می‌کنن.

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

پیاده‌سازی Linearizability:

در Single-leader replication این امکان وجود داره، در الگوریتم Consensus اینطور هست، در Multi-leader replication به دلیل اینکه ممکنه conflict در نوشتن بوجود بیاد و نیازمند resolution هست، امکانش وجود نداره، در Leaderless replication بستگی به چطور تعریف کردن quorum ها داره و احتمالا نیست (دو روش Last write wins و Sloppy Auorums and Hinted Handoff نیستن و در صورتی که از روش read repair به طور synchronous استفاده کنیم Linearizability خواهیم داشت اما به شرطی که بعدش last-write-wins نداشته باشیم).

فرض کنیم که دو تا دیتاسنتر داریم و ارتباط بین این دو قطع شده، اگر از مولتی-لیدر دیتابیس استفاده کنیم، هر دو دیتاسنتر به طور معمول به کارشون ادامه میدن و نوشتن‌ها queue میشن و زمانی که ارتباط شبکه برقرار شد منتقل میشن. اگر از سینگل-لیدر استفاده کنیم، نوشتن‌ها و خوندن‌هایی که linearizabile هستن در دیتاسنتری که دنبال‌کننده‌اس متوقف میشه و فقط خوندن‌های stale که غیر linearizable هستن امکان‌پذیره.

قضیه CAP:

این مشکل فقط مختص single-leader یا multi-leader replication نیست و هر دیتابیس linearizable این مشکل رو داره و همینطور فقط مخصوص multi-datacenter نیست و در هر شبکه غیر قابل اعتماد ممکنه رخ بده:

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

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

گاهی CAP رو به عنوان Consistency, Availability, Partition tolerance: pick 2 out of 3 معنی می‌کنن. اما وقتی شبکه به درستی کار می‌کنه، سیستم می‌تونه هر دو consistency (Lineariziblity) و total availability رو در اختیارمون بذاره، زمانی که در شبکه مشکل پیش بیاد، باید بین linearizability و total availability یکی رو انتخاب کنی، پس بنابراین بهتره که CAP رو اینطور معنی کنیم: Consistent or Available when Partioned. این یک تئوری قدیمیه که فقط درباره قطع شدن ارتباط صحبت می‌کنه و هیچی درباره تاخیر در شبکه یا نود مرده یا trade-off های دیگه چیزی نمیگه.

در اکثر پیاده‌سازی‌ها یک کپی از اطلاعات در حافظه اصلی هستن و چند کپی دیگر در کش‌های مختلف برای افزایش سرعت هستن و این کپی‌ها به صورت Async به‌روز میشن، پس Linearizability از دست میره، معمولا دلیل اصلی استفاده نکردن از linearizibility پرفرمنس هست و نه fault tolerance.

Ordering Guarantees

دلایل زیادی برای توجه به ترتیب وجود داره که یکی‌شون حفظ رابطه علیت هست که بارها بهش اشاره کردیم: مثل consistent prefix read که میگه انتظار داریم اول سوال رو ببینیم و بعد پاسخ. یا چند لیدری که انتظار داریم ردیف اول ایجاد بشه و بعد بخواد آپدیت بشه. و یا در snapshot isolation انتظار داریم که اگر در اسنپ‌شات پاسخ یک سوال هست، خود سوال هم باشه. یا در مورد write skew و phantoms اجازه میده سارا از شیفت مرخصی بگیره چون فک می‌کنه باب هنوز شیفت هست که البته SSI این رو شناسایی می‌کنه. یا در مورد فوتبال نگاه کردن سارا و باب، باب نتیجه تاریخ گذشته رو از سرور بعد اینکه سارا نتیجه جدید رو می‌گه، می‌گیره که به دلیل cross-channel timing dependencies هست (اطلاعات از دو کانال میره، مثلا از یک سمت از صف میاد و از یک سمت از file storage). اگر سیستم از ترتیب علیت پیروی کنه، می‌گیم که casually consistent هست.

در linearizability رابطه علیت رعایت میشه ولی همونطور که قبلا صحبت شد، مسائل پرفرمنسی رو داره، اما خوشبختانه راه میانه‌ای وجود داره، causal consistency قوی‌ترین نوع consistency هست که با کند شدن شبکه کند نمیشه و در صورت قطع شدن شبکه، در دسترس باقی می‌مونه. برای این‌کار به روشی برای شرح knowledge نود در سیستم نیاز داریم، اگر نود مقدار X رو موقعی که در خواست نوشتن Y رو داده دیده باشه و رابطه این دو ممکنه از نوع علیت باشه، تحلیلگر باید بتونه بگه که آیا مقدار X رو موقعی که Y رو تولید می‌کردی مطلع بودی؟ برای مشخص کردن ترتیب علیت، دیتابیس باید بدونه که کدوم ورژن از داده توسط برنامه خونده شده، به این دلیل شماره ورژن عملیات قبلی موقع نوشتن به دیتابیس برگردونده میشه. ایده مشابه‌ای در شناسایی conflict توسط SSI استفاده میشه.

Sequence Number Ordering

توی خیلی از برنامه‌ها، کاربرا کلی اطلاعات رو قبل از نوشتن چیزی، می‌خونن و شناسایی رابطه علیت یک overhead زیادی داره. راه دیگه اینه که از sequence number یا timestamp استفاده کنیم تا ترتیب رویدادها رو مشخص کنیم. timestamp نیازی نیست که از time-of-day clock بیاد و می‌تونه از logical clock بیاد که یک الگوریتم برای تولید توالی اعداد برای مشخص‌کردن عملیات‌هاس که معمولا یک increment به‌ازای هر عملیاته. در single leader replication، لیدر می‌تونه یک کانتر رو برای هر عملیات اضافه کنه و به هرکدوم در replication log مرتبط کنه. حالا اگر دنبال کننده lag هم داشته باشه، همیشه ترتیب رو خواهد دونست.

اما اگر یک لیدر نباشه، multi-leader or leader-less، راه روشنی برای تضمین ترتیب اعداد برای عملیات‌ها وجود نداره. این راهکارها در عمل استفاده میشه:

• هر نود به طور مستقل توالی اعداد تولید می‌کنه. مثلا اگر دوتا لیدر داریم، یکی فقط اعداد فرد و دیگری فقط اعداد زوج تولید می‌کنن. می‌تونیم چند بیت در نمایش باینتری توالی اعداد رو برای unique node identifier رزرو کنیم که مطمئن بشیم هیچ توالی یکسانی تولید نخواهد شد.

• می‌تونیم time-of-day clock timestamp به هر عملیات الحاق کنیم. این timestamp توالی نیست اما اگر دقت خوبی داشته باشه می‌تونه بطور موثر ترتیب عملیات‌ها رو مشخص کنه. این روش برای last write wins conflict resolution استفاده میشه.

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

اما هیچکدوم از این روش‌ها consistent with causality نیستن. یک روش به نام Lamport timestamp وجود داره که این گارانتی رو میده. به این صورت که هر نود یک unique identifier داره و هر کدوم از نودها یک شمارنده اعداد داره و Lamport timestamp به سادگی جفتی از (counter, node ID) است. اگر دوتا timestamp داشته باشی، اونی که conter value بزرگتری داره، بزرگتره، اگر هم مقدارشون یکسان باشه، اونی که node ID بزرگتری داره، بزرگتره. فرق این روش با شمارنده زوج/فرد اینه که هر نود حواسش به max شمارنده هست، یعنی اگر درخواستی دریافت می‌کنه که مقدار شمارنده‌اش بیشتر از شمارنده خودشه، بلافاصله مقدار کانترش رو با اون max یکی می‌کنه.

Total Order Broadcast

برای پیاده‌سازی یک چیزی که نیاز به uniqueness constraint داره، مثل انتخاب نام کاربری، داشتن ترتیب عملیات‌ها کارایی لازم رو نداره و به دونستن اینکه چه زمانی اون درخواست نهایی شده هم نیاز داریم. به این مطلع بودن از اینکه چه زمانی total order نهایی شده Total order broadcast می‌گیم.

اگر سیستم یک هسته CPU داشته باشه،تعریف total order عملیات‌ها آسونه، ترتیبی هست که در CPU اجرا میشن، اما در سیستم‌های distributed اینکه همه نودها روی یک ترتیب کلی موافقت کنن کمی سخته. در single-leader replication ترتیب کلی همه عملیات‌ها توسط یک نود که لیدره انجام میشه. چالش اینجاست که سیستم رو چطور scale کنیم که بتونیم توان عملیاتی بیشتری از توان یک نود رو هندل کنیم و همینطور چطور مردن لیدر رو هندل کنیم. در ادبیات سیستم‌های توزیع‌شده این مشکل با نام total order broadcast یا atomic broadcast شناخته میشه. برای این کار همیشه به این دو مورد نیاز داریم:

• به Reliable delivery: هیچ پیامی از دست نره: اگر پیامی به یک نود رسید، به همه نودها رسیده.

• و Totally ordered delivery: پیام‌ها به همه نودها با ترتیب یکسانی برسن.

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

سرویس‌های اجماعی مثل ZooKeeper و etcd درواقع این روش رو پیاده‌سازی کردن. چیزی که برای database replication دقیقا نیاز داریم همین total order broadcast هست. همینطور برای پیاده‌سازی serializable transactions می‌تونه استفاده بشه. همینطور برای پیاده‌سازی lock service که fencing token ها رو ارائه میده کاربردیه. در Total order broadcast به صورت async هست پیام‌ها گارانتی میشه که با ترتیب ثابتی برسه اما گارانتی‌ای برای اینکه کی برسه وجود نداره. اما در linearizablity گارانتی recency وجود داره که گارانتی می‌کنه که آخرین مقدار نوشته شده خونده بشه. البته که بر روی total order broadcast میشه linearizable storage رو ساخت.
پیاده‌سازی total order broadcast به کمک append-only log:

• اضافه کردن لاگ به صورت آزمایشی که نشون بده اون نام‌کاربری رو می‌خوای.

• خوندن لاگ و صبر کردن برای پیامی که تو اضافه کردی تا دوباره بهت تحویل بشه.

• چک کردن هرپیامی که نام‌کاربری که خواستی رو بخواد، اگر اولین پیام برای درخواست اون نام‌کاربری برای خودته، یعنی موفق بوده و درخواست ثبت نام‌کاربری رو میفرستی و به کاربر تایید رو میدی.

حالا اگر بخوای همین پروسه رو linearizable هم بکنی، این گزینه‌ها وجود داره:

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

• اگر لاگ بهت این امکان رو میده که جایگاه آخرین پیام رو به صورت linearizable بگیری، صبر کنی که تا اون جایگاه، پیام‌ها بهت تحویل بشه و بعد خوندن رو انجام بده.

• می‌تونی خوندنت رو از یک رپلیکا که به صورت sync آپدیت میشه انجام بدی.

پیاده‌سازی total order broadcast به کمک linearizable storage:

فک کن یک linearizable register که یک integer ذخیره می‌کنه داری که یک عملیات اتومیک increment-and-get رو داره. به ازای هر پیام که می‌خوای از طریق total order broadcast بفرستی، اون linearizable int رو increment-and-get می‌کنی و مقدارش رو به عنوان sequence number به پیام الحاق می‌کنی. و پیام رو به همه نودها میفرستی (اگر ناموفق شد دوباره میفرستی) و دریافت کننده ها پیام‌ها رو براساس این شماره ترتیب، مرتب می‌کنن و اعمال می‌کنن. اما مشکل زمانی پیش میاد که این نودی که شمارشگر توالی رو تولید میکنه مشکل بخوره یا شبکه‌اش تاخیر بخوره، اینجاس که باز راهکار اجماعه و باید بریم سراغ مشکل اجماع.

Distributed Transactions and Consensus

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

• انتخاب Leader: در single-leader replication همه نودها باید روی یک نود به عنوان لیدر توافق داشته باشن. اگر تعدادی از نودها به دلیل مشکل در شبکه، نتونن با بقیه ارتباط برقرار کنن جایگاه رهبر باید به بحث گذاشته باشه. در این موقعیت توافق مهمه که خروجیش موقعیت split brain نشه که موجب inconsistenct و data loss میشه.

• در موقعیت Atomic commit: در دیتابیس وقتی که از transaction در چندین نود یا پارتیشن پشتیبانی میشه، این مشکل رو خواهیم داشت که ترنزکشن ممکنه در بعضی از نودها مشکل بخوره و در بعضی‌ها موفق باشه. اگر بخوایم Atomicity رو حفظ کنیم، باید همه نودها توافق کنن که خروجی ترنزکشن: ناموفق بوده و باید roll back بشه یا همه commit کنن. به این اجماع میگن مساله atomic commit.

Atomic Commit and Two-Phase Commit (2PC)

اگر در چندین نود بخوایم یک ترنزکشن رو انجام بدیم راهکار چیه؟ نمیشه به سادگی به صورت مجزا به هر نود یک ترنزکشن کامیت کرد، اگر این‌کار رو بکنیم به سادگی ممکنه در چند نود کامیت موفق باشه و در بقیه ناموفق بشه که خب این، گارانتی atomicity رو نقض می‌کنه. بعضی از نودها شاید conflict یا constraint violation بخورن و اجرای ترنزکشن رو متوقف کنن. ممکنه بعضی از درخواست‌های کامیت در شبکه از دست برن و به دلیل تایم‌اوت متوقف بشن. بعضی از نودها ممکنه قبل از اینکه کامل نوشته بشن، مشکل بخوردن و بعد ریکاوری roll back بشن. ترنزکشن بعد اینکه کامیت شده، دیگه نمیشه نامعتبر بشه و نظرمون رو عوض کنیم، برای همین فقط در صورتی باید کامیت بشه که مطمئن باشیم باقی ترنزکشن‌ها کامیت خواهند شد.

Introduction to two-phase commit

یک الگوریتم برای دست‌یابی به ترنزکشن اتومیک در چند نود هست که مطمئن میشه همه نودها commit و یا abort خواهند کرد. روش کارش هم به این صورته که درخواست‌های نوشتن به دو نود میره و بعد در دوفاز کامیت انجام میشه، در فاز اول استعلام prepare بودن از همه نودها گرفته میشه و اگر همه جواب مثبت دادن، در فاز بعدی درخواست commit برای همه‌شون میره.

حواسمون باشه که two-phase commit و two-phase locking (برای ایجاد serializable isolation بود) که قبلا درباره‌اش صحبت کردیم، دو موضوع کاملا متفاوت هستن.

در 2PC از یک کامپوننت جدید که استفاده میشه که به طور معمول در single-node transaction ها وجود نداره: coordinator که با نام transaction manager هم شناخته میشه. در صورتی که در طی درخواست prepare مشکلی پیش بیاد یا time out بشه، coordinator ترنزکشن رو abort می‌کنه، اما اگر پاسخ مثبت دادن و درخواست commit ارسال شد، دیگه هیچ راه برگشتی وجود نداره و اگر نودی با مشکل برخورد، اونقدر coordinator تلاش مجدد می‌کنه تا تایید کامیت رو بگیره. اگر نود جواب مثبت به prepare داد، و در این حین coordinator مشکل خورد یا شبکه مشکل پیدا کرد و درخواست commit به نود نرسید، نود کاری بجز صبر کردن نمی‌تونه بکنه، به این حالت in doubt یا uncertain می‌گیم. در این حالت تنها راه اینه که صبر کنه coordinator دوباره بازیابی بشه، برای همین کوردینیتور باید تصمیم commit یا abort شدن رو قبل از ارسال درخواست commit یا abort به participant ها، در transaction log بر روی دیسک بنویسه.

به two-phase commit اصطلاحا blocking atomic commit protocol هم می‌گن، چون وقتی که منتظر بازیابی coordinator میشه، متوقف میشه. اما راهکار جایگزینی به نام three-phase commit هست که nonblocking هست، اما برای استفاده ازش باید بتونیم با قطعیت بگیم که نود crash کرده یا نه تا بتونه atomicity رو گارانتی کنه. اما در عمل نمیشه با قطعیت این رو گفت و ممکنه شبکه تاخیر خرده باشه و نود سالم باشه، در نتیجه همچنان از 2PC استفاده میشه.

Distributed Transactions in Practice

در عمل سعی میشه از distributed transaction ها استفاده نشه، مثلا در MySQL گزارش شده که بیش از ۱۰ برابر از single-node transaction کندتره. یک بخش خوبی از این هزینه بخاطر disk forcing در 2PC برای بازیابی از مشکله. ترنزکشن‌ها در دیتابیس‌های توزیع شده به دو صورت می‌تونن باشن:

• به صورت Database-internal distributed transactions: یکسری دیتابیس توزیع شده که از replication یا partitioning استاندارد خودشون استفاده می‌کنن و از ترنزکشن داخلی بین نودهای دیتابیس پشتیبانی می‌کنن. در این مدل همه نودها در ترنزکشنی که در نرم‌افزار یکسان دیتابیس درحال اجراس، شرکت می‌کنن.

• به صورت Heterogeneous distributed transactions: شرکت‌کننده‌ها از دو یا چند تکنولوژی متفاوت هستن و حتی سیستم‌های غیر دیتابیسی مثل message broker ها. distributed transaction در این سیستم‌ها باید از atomic commit اطمینان حاصل کنه.

استاندارد XA transactions: مخفف eXtended Architecture هست و یک استاندارد برای پیاده‌سازی two-phase commit در تکنولوژی‌های ناهمگنه. این یک پروتکل شبکه نیست و فقط یک C API هست که ارتباط با transaction cordinator رو واسطه میشه.

اگر coordinator مشکل بخوره و رستارت بشه باید وضعیت‌اش رو از روی لاگ بازیابی کنه و in-doubt transaction ها رو تعیین تکلیف کنه. اگر چه اگر in-doubt transaction های یتیمی وجود داشته باشه (به دلیل از دست رفتن لاگ و یا باگ نرم‌افزاری) این موارد اتومات نمی‌تونن حل بشن و تا ابد حتی با رستارت سرور دیتابیس قفل باقی می‌مونن. اینجا مسئولش باید به صورت دستی تصمیم بگیره که ترنزکشن کامیت بشه یا متوقف.
برای چنین موقعیتی بیشتر XA ها یک راهکار فرار به نام heuristic decisions دارن که این اجازه رو میده که تصمیم بگیری که این ترنزکشن‌ها متوقف یا کامیت بشن.

محدودیت‌های ترنزکشن‌های توزیع‌شده: باید توجه کنیم که خود coordinator هم یک نوع دیتابیسه و باید با مراقبت‌های مشابه با هر پیاده‌سازی دیتابیس دیگه‌ای باهاش رفتار بشه:

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

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

• چون XA با تعداد زیادی از دیتا سیستم‌ها کار می‌کنه، کمترین مشترکات رو پوشش میده. مثلا نمی‌تونه deadlock ها رو در سیستم‌های مختلف شناسایی کنه و یا با SSI نمی‌تونه کار کنه چون نیاز به پروتکلی برای شناسایی conflict ها در سیستم‌های مختلف داره.

Fault-Tolerant Consensus

الگوریتم consensus باید موارد زیر رو ارائه بده:

• ویژگی Uniform agreement: هیچ دو نودی تصمیم‌های متفاوتی نگیرن.

• ویژگی Integrity: هیچ نودی دوبار تصمیم نگیره.

• ویژگی Validity: اگر نودی تصمیم v رو گرفت، تصمیم v توسط نودی پیشنهاد داده شده باشه. مثلا همیشه یک نود به مقدار null رای نده.

• ویژگی Termination: هر نودی که crash نکرده در نهایت روی یک مقداری تصمیم بگیره. مثلا نمیشه از روش 2PC استفاده کرد چون اگر کوردینیتور پایین بیاد، نودها تصمیمی نمی‌گیرن، یا نمیشه نودها به صورت هارد کد از تصمیم یک نود دیگه پیروی کنن، چون اگر اون نود پایین بیاد، دیگه تصمیمی گرفته نمیشه.

بهترین الگورتیم شناخته شده اجماع، Viewstamped Replication, Paxos, Raft and Zab هست. شباهت‌هایی بین‌شون وجود داره اما یکی نیستن، خوبه که ایده کلی رو که بین‌شون مشترک هست رو بدونین وگرنه خودتون میرین پیاده‌سازیش می‌کنین که توصیه نمیشه چون سخته.

اکثرشون اینطور که اینجا گفتیم روی یک عدد واحد اجماع نمی‌کنن و بجاش روی یک دنباله از مقدارها تصمیم‌گیری می‌کنن که تبدیلشون می‌کنه به الگوریتم‌های total order broadcast.

در single-leader replication اگر leader دستی و توسط یک نفر در تیم عملیات انتخاب بشه، الگوریتم اجماع رو خواهیم داشت اما بخاطر اینکه نیاز به دخالت انسانی داره، راضی‌کننده نیست. بعضی از دیتابیس‌ها انتخاب لیدر و بازیابی از مشکل رو اتومات انجام میدن. برای این‌کار ما نیاز به اجماع داریم که split brain رخ نده و برای اجماع نیاز به الگوریتم total order broadcast داریم و برای این نیاز به اجماع داریم و... چطور حالا ازین حلقه بی‌نهایت بیایم بیرون؟

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

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

Membership and Coordination Services

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

• عملیات‌های Linearizable atomic: با استفاده از عملیات atomic compare-and-set، می‌تونی یک lock رو پیاده‌سازی کنی.

• عملیات‌های Total ordering: توسط total ordering و دادن یک transaction ID (zxid) و version number (cversion) به هر عملیات fencing token رو پیاده‌سازی می‌کنه که از conflict جلوگیری کنه.

• شناسایی شکست: یک long-lived session هر کلایت برروی سرور ZooKeeper داره و سلامت هر نود چک میشه و در صورت منقضی شدن session همه lock های مرتبط با اون نشست آزاد میتونن بشن.

• اطلاع‌رسانی تغییرها: همه client ها می‌تونن lockها و مقادیر رو watch کنن. در نتیجه می‌تونن وضعیت نودهای دیگه و یا زمان پیوست یک client دیگه به کلاستر رو متوجه بشن.

از این سرویس‌ها برای پیداکردن سرویس‌ هم استفاده میشه، چه آدرس IP ای باید وصل بشیم تا به سرویس مشخصی دسترسی پیدا کنیم.

Derived Data

awk, grep, and sort

Batch Processing Systems

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

MapReduce

یک الگوریتم batch processing هست که اجازه پردازش موازی در چندین ماشین بدون نیاز به کدی که موازی عمل کنه رو میده. بخش‌های اصلیش ایناس:

• بخش Mapper: پردازش رکوردهای ورودی و تولید جفت key-value.

• بخش Reducer: گرفتن جفت‌های key-value از mapper و گرفتن value ها از کلیدهای یکسان و پردازش اونها.

مثال: میخوایم تعداد هر کلمه در چند داکیومنت رو در بیاریم:

• فاز Map: هر داکیومنت رو به طور جداگانه پردازش می‌کنیم و کلمات رو با تکرارشون مشخص می‌کنیم.

• فاز Shuffle and Sort: تکرار هر کلمه رو گروه بندی می‌کنیم. (the, [1, 1, 1])

• فاز Reduce: مقدار sum برای هر کلمه رو حساب می‌کنه. (the, 3)

Dataflow Systems

سیستم‌هایی کلی شده از مدل MapReduce هستن که workflow های پیچیده‌تر با پردازش real-time رو پشتیبانی می‌کنن. شامل شکستن عملکرد برنامه به مجموعه‌ای از سرویس‌هاست که باهم از طریق asynchronous message streams بجای synchronous request/response در ارتباط هستن. مزیتش اینه که در مقابل مشکل خوردن ایمن‌تر هستن چون ارتباط async هست. قابلیت رشد سیستم بیشتره چون اجازه توسعه مستقل سیستم‌ها رو میده. همینطور امکان مشخص کردن ترتیب پیام‌ها به طور موثر رو هم میده. نمونه‌هاش Apache Beam و Apache Spark هستن.

Stream Processing

ایده کلی‌اش پردازش داده به طور پیوسته در زمان رسیدنشه. کار اصلیش هندل کردن جریان پیام‌هاست. برای دیتاهای با طول عمر کوتاه که بعد consume شدن پاک میشن، بهینه شده. عملیات‌های async رو پشتیبانی می‌کنه و مناسب سیستم‌هایی که client ها میان و میرن. به طور مثال RabbitMQ, Kafka, ActiveMQ رو میشه نام برد. اما دیتابیس برای نگهداری طولانی‌مدت داده‌ها و پشتیبانی از query ها و index های پیچیده طراحی شدن. میشه چندین consumer داشت تا پیام‌ها لود بین‌شون بالانس بشه و پردازش موازی داشته باشیم (Load Balancing). و یا میشه هر پیام رو به همه consumer ها رسوند (Fan-out).