چرا قضیه CAP ثابت می‌کند هیچ پایگاه داده توزیع‌شده‌ای نمی‌تواند هم‌زمان یکپارچه، در دسترس و مقاوم در برابر قطعی شبکه باشد

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

قضیه CAP که ابتدا در سال ۲۰۰۰ توسط اریک برور (Eric Brewer)، دانشمند علوم کامپیوتر، مطرح شد و در سال ۲۰۰۲ توسط ست گیلبرت (Seth Gilbert) و نانسی لینچ (Nancy Lynch) از دانشگاه MIT به‌طور رسمی به اثبات رسید، یک مرز مطلق برای ذخیره‌سازهای داده توزیع‌شده تعیین می‌کند. این قضیه بیان می‌کند که یک سیستم توزیع‌شده حداکثر می‌تواند دو مورد از سه تضمین زیر را ارائه دهد: یکپارچگی (Consistency)، در دسترس بودن (Availability) و تحمل‌پذیری پارتیشن یا قطعی شبکه (Partition tolerance). یکپارچگی حکم می‌کند که هر عملیات خواندن، جدیدترین داده نوشته‌شده را دریافت کند و تضمین می‌کند که همه کلاینت‌ها هم‌زمان داده‌های یکسانی را می‌بینند. در دسترس بودن ایجاب می‌کند که هر درخواستی که توسط یک گره (node) سالم دریافت می‌شود، به یک پاسخ منجر شود. تحمل‌پذیری پارتیشن به این معناست که سیستم به‌رغم حذف یا تأخیر تعداد دلخواهی از پیام‌ها توسط شبکه‌ای که گره‌ها را به هم متصل می‌کند، به کار خود ادامه می‌دهد.[1][5]

از آنجا که سیستم‌های توزیع‌شده روی شبکه‌های فیزیکی اجرا می‌شوند و شبکه‌ها ذاتاً در برابر خرابی‌های سخت‌افزاری، پیکربندی‌های اشتباه و قطع شدن کابل‌ها آسیب‌پذیرند، تحمل‌پذیری پارتیشن یک ویژگی اختیاری نیست. یک سیستم باید طوری طراحی شود که با این واقعیت کنار بیاید که اتصال بین دو دیتاسنتر در نهایت قطع خواهد شد. بنابراین، قضیه حکم می‌کند که وقتی یک قطعی (پارتیشن) رخ می‌دهد، سیستم مجبور به یک انتخاب صفر و یکی است: یا می‌تواند عملیات را برای تضمین یکپارچگی لغو کند، یا می‌تواند برای تضمین در دسترس بودن به عملیات ادامه دهد و این ریسک را بپذیرد که داده‌های ارائه‌شده قدیمی باشند.[3][5]

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

در دهه‌های پس از اثبات این قضیه، صنعت نرم‌افزار تا حد زیادی این محدودیت را پذیرفته است که منجر به ظهور پایگاه‌های داده NoSQL شده است؛ پایگاه‌هایی که صراحتاً یکپارچگی قوی را فدای در دسترس بودن بالا می‌کنند. سیستم‌هایی که برای مقیاس‌های عظیم طراحی شده‌اند، اغلب به‌طور پیش‌فرض روی «یکپارچگی نهایی» (eventual consistency) تنظیم می‌شوند و تنها تضمین می‌کنند که اگر به‌روزرسانی جدیدی انجام نشود، همه دسترسی‌ها در نهایت آخرین مقدار به‌روزرسانی‌شده را برمی‌گردانند. این بده‌بستان برای کاربردهایی مانند فید شبکه‌های اجتماعی یا سبد خرید، که در آن‌ها یک مغایرت موقت به قطعی کامل سیستم ترجیح داده می‌شود، قابل‌قبول تلقی می‌گردد.[2][3][4]

با این حال، زمانی که گوگل اسپانر (Spanner) را معرفی کرد، این روایت تغییر یافت. اسپانر یک پایگاه داده SQL توزیع‌شده در سطح جهانی است که داده‌های تکرارشده (replicated) را در مقیاسی بی‌سابقه مدیریت می‌کند. گوگل ادعا کرد که اسپانر هم یکپارچه است و هم در دسترس بودن بالایی دارد، که منجر به گمانه‌زنی‌های گسترده‌ای شد مبنی بر اینکه این شرکت به نحوی قضیه CAP را نقض کرده است. راز معماری اسپانر در TrueTime نهفته است؛ یک سیستم ساعت هماهنگ جهانی که به GPS و ساعت‌های اتمی متکی است و با یک شبکه فیبر نوری عظیم و خصوصی ترکیب شده که وابستگی به اینترنت عمومی را به حداقل می‌رساند.[6]

مهندسان گوگل اذعان دارند که اسپانر قوانین ریاضیات را نقض نمی‌کند. اریک برور در سال ۲۰۱۷ در مورد اینکه آیا اسپانر واقعاً یک سیستم یکپارچه و در دسترس است، نوشت: «پاسخ افراد کمال‌گرا 'خیر' است، زیرا قطعی‌ها می‌توانند رخ دهند و در واقع در گوگل رخ داده‌اند، و در طول برخی از قطعی‌ها، اسپانر یکپارچگی (C) را انتخاب کرده و در دسترس بودن (A) را فدا می‌کند.» این سیستم از نظر فنی یک سیستم CP است؛ یعنی در زمان قطعی، یکپارچگی را به در دسترس بودن ترجیح می‌دهد. با این حال، گوگل استدلال می‌کند که چون کل زیرساخت شبکه خود را کنترل می‌کند، احتمال وقوع قطعی بی‌نهایت کوچک است و به بیش از «پنج نُه» (۹۹.۹۹۹٪) در دسترس بودن، یا کمتر از یک خرابی در ۱۰۰,۰۰۰ مورد، دست می‌یابد.[6]

این بازتعریف عمل‌گرایانه از در دسترس بودن، مسیر گفتگو را از تضمین‌های مطلق ریاضی به احتمالات آماری تغییر می‌دهد. برای تمام مقاصد عملی، کاربران می‌توانند با اسپانر طوری رفتار کنند که گویی یک سیستم CA است، زیرا قطعی‌ها آن‌قدر نادر هستند که در مقایسه با سایر منابع خرابی اپلیکیشن، از نظر آماری بی‌اهمیت می‌شوند. با این حال، منتقدان این چارچوب‌بندی استدلال می‌کنند که بازتعریف در دسترس بودن به معنای «در دسترس بودن بالا در بیشتر مواقع»، تعریف دقیق قضیه CAP را که به رفتار بنیادین یک سیستم در حالت خرابی می‌پردازد و نه درصد آپ‌تایم آن، کم‌رنگ می‌کند.[2][6]

همان‌طور که خود برور در یک مقاله بازنگری در سال ۲۰۱۲ که در IEEE Computer منتشر شد اشاره کرد، فرمول‌بندی اولیه «دو از سه» تا حدودی گمراه‌کننده است، زیرا قطعی‌ها نادر هستند و سیستم‌ها می‌توانند در طول عملیات عادی، هم برای یکپارچگی و هم برای در دسترس بودن بهینه‌سازی شوند. این قضیه، در دسترس بودن و یکپارچگی بی‌نقص را تنها در صورت وجود قطعی شبکه ممنوع می‌کند. هدف مدرن در طراحی سیستم‌های توزیع‌شده، به حداکثر رساندن ترکیب‌هایی از یکپارچگی و در دسترس بودن است که برای کاربرد خاص منطقی باشد و شامل برنامه‌هایی برای عملیات در حین قطعی و بازیابی پس از آن شود.[2][4]

قضیه PACELC که در سال ۲۰۱۰ برای بسط قضیه CAP معرفی شد، این پویایی را بیشتر روشن می‌کند و بیان می‌دارد که حتی در غیاب قطعی شبکه، بده‌بستان دیگری بین تأخیر (latency) و یکپارچگی وجود دارد. اگر قطعی رخ دهد، بده‌بستان بین در دسترس بودن و یکپارچگی است؛ در غیر این صورت، بده‌بستان بین تأخیر و یکپارچگی خواهد بود. این چارچوب گسترده‌تر اذعان می‌کند که هزینه حفظ یکپارچگی بی‌نقص در یک شبکه جهانی اغلب با میلی‌ثانیه‌های تأخیر اندازه‌گیری می‌شود، که می‌تواند به اندازه یک قطعی کوتاه برای تجربه کاربری مخرب باشد.[4][5]

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

وقتی فیبر قطع می‌شود و گره‌ها نمی‌توانند ارتباط برقرار کنند، باید انتخابی صورت گیرد. سیستم می‌تواند دقیق باشد، یا می‌تواند در دسترس باشد، اما نمی‌تواند هر دو باشد. پیروزی‌های مهندسی در فضای ابری مدرن، قضیه CAP را از بین نبرده‌اند؛ آن‌ها صرفاً قطعی‌ها را آن‌قدر نادر کرده‌اند که ما می‌توانیم این تجمل را به خود بدهیم که وانمود کنیم این قضیه اصلاً وجود ندارد.[1][6]