مدل‌های CAP و سازگاری

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

Definition

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

Scope

این موضوع مدل‌های رسمی سازگاری — خطی‌سازی (linearizability)، سازگاری ترتیبی (sequential consistency)، سازگاری علّی (causal consistency) و سازگاری نهایی (eventual consistency) — و ترتیب قدرت آن‌ها را پوشش می‌دهد؛ قضیه CAP و بیان دقیق و اثبات آن؛ و اصلاحاتی مانند PACELC که همچنین مبادله تأخیر-سازگاری را در غیاب تقسیم‌بندی‌ها در نظر می‌گیرند. این موضوع واژگان لازم برای تعیین و مقایسه تضمین‌های سیستم‌های تکراری را فراهم می‌کند.

Core questions

• خطی‌سازی، سازگاری ترتیبی، علّی و نهایی از نظر قدرت چه تفاوتی با یکدیگر دارند؟
• قضیه CAP دقیقاً چه چیزی را ممنوع می‌کند و چه چیزی را مجاز می‌شمارد؟
• چگونه ملاحظات تأخیر، مبادله سازگاری را در غیاب تقسیم‌بندی اصلاح می‌کنند؟

Key theories

خطی‌سازی و سازگاری ترتیبی

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

قضیه CAP

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

اصلاح PACELC

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

Clinical relevance

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

History

لامپورت (Lamport) سازگاری ترتیبی را در سال 1979 تعریف کرد و هرلیهی (Herlihy) و وینگ (Wing) خطی‌سازی را در سال 1990 رسمی کردند؛ بروئر (Brewer) مبادله CAP را در سال 2000 مطرح کرد، گیلبرت (Gilbert) و لینچ (Lynch) آن را در سال 2002 اثبات کردند، و بازنگری PACELC توسط عبادی (Abadi) در سال 2012 روشن کرد که تأخیر، نه تنها تقسیم‌بندی‌ها، انتخاب‌های سازگاری را هدایت می‌کند.

Debates

آیا CAP اغلب به اشتباه تفسیر می‌شود؟

CAP اغلب به صورت «دو از سه را انتخاب کنید» خلاصه می‌شود، اما نتیجه دقیق تنها یک انتخاب سازگاری-در دسترس بودن را در طول یک تقسیم‌بندی تحمیل می‌کند؛ منتقدان استدلال می‌کنند که این ساده‌سازی بیش از حد، مبادله تأخیر-سازگاری روزمره مرتبط‌تر را که توسط PACELC به تصویر کشیده شده است، پنهان می‌کند.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

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

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