История CAP теоремы
@shark_in_itС чего начался CAP
Недавно (~ в середине марта 2021 года) меня триггернуло на фразу "CAP теорема — это миф" от интервьювера. В этом посте мы поговорим о том, как вообще эта теорема появилась на свет, что она значит, и немного затронем важность ограничений, при чтении любых работ по Computer Science.
Началось все в 2000 году, когда Eric Brewer (ныне — VP of infrastructure в гугле) выступил вот с этой презентацией на кейноуте симпозиума по принципам распределенных систем (PODC). Это большая крутая конференция про все распределенное, которая проходит ежегодно уже почти 40 лет. К моменту его доклада, мир уже оперировал аббревиатурой BASE на равне с ACID, но вот фундаментальный трейд-офф между C — Consistency, A — Availability и P — partition tolerance был объявлен именно здесь (как минимум, так обычно считается в литературе).
В изначальной постановке трейд-офф звучит как "Consistency, Availability, Partition Tolerance. You can have at most two of these properties for any shared-data system". В этой же презентации приводятся примеры всех трех видов систем. В качестве CA систем приводятся Single-site databases и LDAP. Это важное замечание, так как через какое-то время, различные работы придут к выводу, что разделить CA и CP системы довольно сложно. Хотя бы потому что кратковременное отсутствие сети можно моделировать через отсутствие availability и наоборот (Такого мнения спустя 12 лет придерживается как сам автора, так и спустя 10 лет не только автор).
Вторая важная вещь, озвученная в кейноуте — это DQ principle. Вводится он следующим образом:
Data/query * Queries/sec = constant = DQ
Количество данных, получаемых в одном запросе, помноженное на количество запросов в секунду является константной величиной для заданной ноды, с заданными версиями операционной системы и версией программы.
Data/query — это сколько корректных данных возвращается из одного запроса, queries/second — производительность ака throughput. Здесь надо оговориться, что речь идет про очень большие и распределенные продукты, а сам кейноут должен нести практический смысл. В реальных системах часть данных может сначала попасть в системы, а лишь затем реплецироваться. Т.е. данные есть, а запросы на чтения пока их не возвращают (Пример: запись на write в мастер прошла, а до read реплик еще не докатилась) . Именно поэтому понятие "количество корректных данных" (data/query) имеет значимый смысл.
Данный принцип утверждает, что в рамках работающей системы нельзя одновременно повысить и качество данных (data/query) и количество обрабатываемых запросов (queries/second). Как минимум без изменения программы / ос / сервера. Забавно, что этот трейдофф consistency/throughput/latency будет через десяток лет рассматриваться уже другими учеными, но об этом мы еще поговорим.
Но вернемся к CAP. В презентации утверждение про "возьми 2 из 3" формулируется как теорема, что фактически неверно. Теорема должна иметь доказательство, т.е. правильнее это было бы назвать другим словом, например принцип CAP или гипотеза CAP, как это делают многие последующие работы.
Формальное доказательство
Когда принцип CAP стал теоремой? Это произошло в 2002 году в вайтпейпере под авторством Seth Gilbert и Nancy Lynch. Я очень советую почитать сам вайтпейпер, т.к. доказательство элементарное в рамках тех ограничений, которые задаются для рассматриваемой системы. Если что, то же самое доказательство есть с картинками, тут уж точно все станет понятно (Нет, серьезно, универские доказательства из матана в десятки раз более замудренные, чем то что написано в работе по CAP).
Как известно, когда дело доходил до формальных доказательств, нельзя просто так брать и рассматривать все множество доступных вычислений. Нужно оперировать некими определениями, ограничениями и моделями. В частности в этой работе вводятся следующие ограничения:
- Рассматривается асинхронная модель взаимодействия. Асинхронная это значит несколько вещей. Во-первых, части системы общаются только через обмен сообщениями. Во-вторых, любое сообщение может доставляться и обрабатываться неопределенное, но не бесконечное время. Как следствие, невозможно отличить отказ ноды от медленной обработки сообщения.
- Consistency рассматривается, как атомарность или линеаризуемость. Это значит, что система для внешнего наблюдателя всегда выглядит так, словно она состоит из одного сервера. Более формально, в линеаризуемой системе всегда существует линейная упорядоченность (total order) абсолютно всех операций относительно единственно-верных часов.
- Partition Toleranse вернее partition (разделение сети) рассматривается как бессрочное разделение.
- Availability. Здесь формулируется как "любая не вышедшая из строя нода должна возвращать корректный результат".
Сама формулировка теоремы следующая:
It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties:
- Availability
- Atomic consistency
in all fair executions (including those in which messages are lost)
Обратите внимание, что уже на уровне формулировки не учитывается возможность существования CA систем. Формулировка вообще ничего не говорит про "выбери 2 из 3". После этой теоремы, идет еще следствие из нее, в котором говорится, что условие недостижимо даже при отсутствии пропавших сообщений.
Приблизительно здесь заканчивается первая половина всей работы! Во второй рассматриваются менее строгие системы, а именно системы, оперирующие в partially synchronous модели. Это модель, в которой у каждой ноды есть свои часы (не синхронизированные между друг другом). Через такие часы можно реализовать таймауты, например. Так вот, в такой системе все еще невозможность обеспечить одновременно availability и atomic consistency в общем случае, но это становится возможно если не потерять ни одного сообщения.
Давайте перейдем теперь к самому интересному... Что не так с CAP? Ответ выходит прямиком из ограничений, необходимых для доказательства теоремы.
Во-первых, консистентность как линеаризуемость. Это очень жесткое требование, и большинство современных хранилищ данных, в принципе не могут функционировать линеаризуемо.
Во-вторых, разделение сети рассматривается как бессрочное. Большинство современных систем надеются на то что связь когда-нибудь восстановится. Таким образом ограничение теоремы про бесконечные промежутки разделения сети имеет мало общего с реальным миром.
В-третьих, доступность. В ограничениях теоремы указывается, что система доступна, когда любая работающая нода отвечает корректно. В реальном мире обычно достаточно, когда какое-то подмножество нод возвращает корректный результат.
В-четвертых, рассматривается только асинхронная система. На практике у вас всегда есть хотя бы не синхронизированные часы, а значит возможность делать таймауты, ретраи, и прочие методы повышения доступности.
Получается, что главная проблема CAP теоремы в целом заключается в том, что модель и ограничения, в рамках которых она рассматривается, практически неприменима для реального мира. Тем не менее эта работа все еще корректна и верна! Неприменима вовсе не то же самое, что неверна. С другой стороны, раз уж она не применима практически всегда, почему вендоры хранилищ данных так любят говорить CP у них или AP? Вот это уже вопрос, на который у меня нет ответа.
12 лет спустя
Следующая важная веха вокруг CAP теоремы случилась аж спустя 12 лет с момента первой презентации. Автором этого огромного поста снова стал Eric Brewer. Забавно, что факт доказательства теоремы им практически полностью игнорируется. Но с другой стороны, оно и понятно, потому что у CAP есть 2 жизни. Первая — это формальные доказательства, задача которых задать верхнюю и нижнюю границу возможного. А вторая — это реальные системы, в которых существуют реальные трейдоффы. Им и посвящен этот пост.
Статья начиная с разъяснений, почему нельзя просто так брать определение из теоремы и кричать, что тут у вас AP, а тут CP — настоящие системы слишком сложны.
Во-первых, partition tolerance предполагает, что система знает о разделении. Это, к сожалению, не всегда так. Сеть может разрываться в неожиданных местах, так что при разрыве у нас может появится не два множества нод, знающих друг о друге, а три или больше. Более того, независимые части системы в целом могут продолжать работу даже при разделении сети. Возьмем, например, сервис такси в Северной Америке и Европе. Всегда ли необходимо наличие связи между ними? Скорее всего нет, так как никто не будет вызывать такси из Вашингтона в Амстердам. При этом эти 2 части могут продолжать обрабатывать запросы, даже когда сети между ними нет.
Во-вторых, разделение сети — далеко не единственная возможная проблема. Часть запросов по сети просто пропадает из-за ненадежности сети. Система вполне может потерять и доступность, и консистентность после неудачного релиза. А для некоторых систем недоступностью будет слишком высокие задержки, хотя запросы все еще будут обрабатываться (например, биржевые роботы). Строго говоря, консистентность и доступность — это не бинарные понятия. Является ли доступной система, которая успешно возвращает 99% данных, а 1% произвольно дропает? С точки зрения формальных определений — нет. С точки зрения стриминг-портала, вполне себе рабочий вариант.
В-третих, чему посвящена основная часть статьи, отказ от консистентности в пользу доступности часто недостижим. Лучше что можно сделать — это отложить момент наступления консистентности. Никто не любит, когда их данные теряются. Как быть?
Для начала, было бы хорошо обнаруживать недоступность между компонентами. Здесь человечество изобрело уже множество подходов от синхронных health чеков с таймаутами (напомню, что формально CAP рассматривается в асинхронной системе. Синхронных операций в такой системе нет) до алгоритмов консенсуса. Следующие шаг — перейти в явный режим работы при разделении сети, а при восстановлении, собственно, провести компенсации.
Звучит хорошо, на практике все не так просто. Чтобы корректно восстановить консистентность, после возобновления сетевой доступности, нужно знать как минимум все инварианты системы. Инварианты — это условия, которые должна оставаться верными в любой ситуации. Баланс не может быть меньше нуля, у пользователя может быть ровно 1 аккаунт, по одному закажу должен быть ровно один платеж и прочие-прочие-прочие ситуации. Знать и учитывать все это сложно. Еще сложнее, уметь корректно разрешать конфликтные ситуации. Пусть за время конфликта один и тот же заказ сначала отменился, а чуть попозже взял и оплатился. Что делать? Поди его там разбери, что хотел сделать пользовать!
Поэтому предлагается решать такие конфликты аж четырьмя способами:
1. После обнаружения разделения сети, не позволять делать часть операций. Дубовый и прямолинейный способ, единственное что, пользователи страдают, а также определить, какие операции опасные, а какие нет для конфликтов восстановления — задача непростая.
2. Собирать отладочную информацию. Например, собирать version vectors, а после восстановления, объединять их в консистентное состояние. В теории хорошо, на практике зависит от того, как долго длится разъединение, и какие операции происходят.
3. Использовать коммутативные и иммутабельные операции, а еще лучше conflict-free replicated data types. Проблема в том что не все можно реализовать на CRDT. Особенно тяжело для них выполнять инварианты. Сложить несколько плюсов и минусов баланса — просто. Сложить две разные корзины товаров, как множества тоже просто. Сделать так, чтобы ни одна операция не вывела баланс за нуль — сложно.
4. Вести аудит операций, а затем запускать компенсирующую логику. Подход похож на version vectors, но может быть реализован самыми неожиданными способами. Например, банк может взимать плату за овердрафт, в качестве компенсации за то что баланс уменьшился ниже нуля, если сможет доказать, что это пользовать сам одновременно снял деньги в банкомате и перевел на другой счет.
Как обычно, в реальном мире простых решений нет. Формальные доказательства не спасают, а только заставляются задумываться. Но история CAP теоремы все еще не закончена...
Утверждение PACELC
Следующая важная работа для истории CAP это "утверждение" PACELC (произносится pass-elk) под авторством Daniel J. Abadi. Иногда ее называют "теорема PACELC", что совершенно неверно, т.к. сама работа не содержит формальных доказательств, это скорее рассуждения и логические выводы. Исторически она вышла на пару месяцев раньше, чем 12-лет-спустя, но статьи друг от друга не зависят и представляют разные элементы одних и тех же трейдоффов.
Формулировка следующая:
PACELC: if there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?
Если в 12-лет-спустя говорится, что от консистентности нельзя в принципе оказаться, то тут автор предлагает задуматься, какие трейдоффы нужно делать еще до того, как разделение сети произойдет. А трейдоффы здесь между консистеностью и задержками (latency). Забавно что в самой-самой первой презентации от Eric Brewer (о ней см. первую часть здесь или в телеге пост #1) было аналогичное утверждение в виде DQ принципа. Нельзя одновременно улучшить и консистентность и производительность vs нельзя одновременно улучшить консистеность и latency.
Рассуждения строятся следующим образом. Если система highly available, то потеря ноды с данными не должна автоматически приводить к потере данных. Значит, данные нужно реплицировать. Рассмотрим все возможные методы репликации и посмотрим, какие в них вылезают трейдоффы.
Вариант 1: Данные реплицируются во все n реплик одновременно. Если вся репликация синхронная — любой отказ это недоступность, а мы строим "highly available". Если отказ одной реплики не проблема, значит автоматически должен существовать алгоритм репликации, который включает восстановление как минимум корректного порядка сообщений. Значит есть какая-то лишняя работа == есть задержки. Нужно между более консистентный, но медленным алгоритмом или наоборот.
Вариант 2: Данные направляются в определенные ноды, а лишь затем реплицируются. Например write master - read slave репликация. По этому пути есть 2 дороги:
- 2.1: Синхронная репликация. Общая задержка равна времени на самый длительный запрос в лучшем случае. В худшем и того больше. Нужно выбирать на сколько нод реплицировать, т.е. прямо сразу приходим к consistency vs latency.
- 2.2: Асинхронная репликация. Здесь могут быть такие проблемы с консистентность, как Read Your Writes, Write Follow Reads и прочие интересные особенности (см. правый кусок дерева здесь). Их можно так или иначе обойти, но об этом надо думать, принимать решение, и писать исполняемый код, а значит трейдвофф между задержками и консистентностью тоже есть.
Вариант 3: Данные направляются в произвольную ноду (не прямо произвольную, конечно, а например в любую из какого-то кворума). В сущности что здесь, что в варианте 2 проблемы и решения совершенно одинаковые, так что снова есть тредофф latency vs consistency.
С подходом PACELC система может классифицироваться 4 буквами. В качестве примера автор говорит, что MongoDB это PA/EC. При наличии партиций (PA) она остается доступной, т.к. отделенная от остального кластера нода продолжает писать в rollback директорию. При этом без партиций (EC) гарантируется консистеность в первую очередь... Как минимум в соответствии с документацией. Кому интересно, в статье еще рассматривается VoltDB/H-Store (PC/EC), PNUTS (PC/EL) и DynamoDB, Cassandra, Riak (PA/EL). Хотя "рассматривается" это сильно сказано, там по одному параграфу.
Критика CAP теоремы
Последняя работа, о которой я бы хотел упомянуть, это критика CAP от Martin Kleppman, того самого автора книжки с кабанчиком.
Первая часть посвящена, собственно, разбору CAP из 3 частей. Что не так, что не понятно, где термины даются не четко, и какие из этого всего вытекают проблемы. К концу даже доказывается ряд теорем, очень похожих на CAP, но без двусмысленных формулировок. Эта часть на 100% формальная, и мы её пропустим, но сама терминология и доказательство поразительно лаконичны. Рекомендую почитать, если вам нравится такой формат.
Вторая часть рассказывает про фреймворк delay-sensitivity. Идея заключается в том, что в настоящий момент существует пропасть между теоретическими изысканиями, такими как формальное доказательство CAP теоремы и практическими системами. Например, в современном мире слишком высокая задержка (latency) приравнивается к недоступности сервиса (SLA/O, вот это все). Значит нужно построить такую модель терминов, которая помогла бы разговаривать на одном языке исследователям и разработчикам, при этом покрывала бы реальные кейсы.
Модель выстраивается в 2 этапа. Сначала задаются теоретические нижние границы времени выполнения операций чтения и записи для разных уровней консистентности в зависимости от сетевых задержек (обозначаются здесь через d). Каждый уровень сопровождается ссылкой на доказательство.
- linearizability — и чтение, и запись O(d). Пруф.
- sequential consistency — либо чтение, либо запись O(d). Второе из двух может быть O(1). Пруф.
- casual consistency — обе операции за O(1). Пруф 1, пруф 2.
Следует помнить, что наличие формального доказательства вовсе не обозначает применимость в реальном мире. Например, оказывается что casually consistent хранилище может и читать и писать за константу. Вот только для этого нужно передавать еще мешок данных, по которым можно определить эту самую casualty, что в реальных системах может быть нецелесообразно. Поэтому на практике существуют более слабые гарантии, например eventually consistent системы.
А дальше идет терминология delay-sensitivity фреймворка:
- Availability следует считать эмпирической величиной, равной проценту успешных запросов от количества общих в период времени. Чуть подробнее про эмпирическое значение availability я писал тут.
- Delay-sensitive — это свойство алгоритма, обозначающее, что ему нужно ждать задержку d пока шаг выполнится. В противоположность ставиться delay-insensitive, которым ждать не нужно. Как пример — запись в мастер может сделаться сразу же, а вот репликация данных в другие ноды минимум за d.
- Network Faults. Должны включать в себя не только полный network partition, но так же и периодические потери пакетов (ака "сеть моргнула") и внезапное превышение средних задержек. Все три показателя важны для реальной системы.
- Fault Tolerance — следует использовать вместо понятия partition tolerance. Алгоритм должен описывать какие ошибки он может пережить (например, потерю менее половины нод), а также что происходит, если лимит ошибок превышен.
- Consistency должна обозначать одну из известных моделей. Слово strong consistency не имеет смысла и лишь усложняет понимание.
Приживется ли терминология, покажет лишь время. Работа молодая, она выпущена в 2015 году, т.е. ей едва ли стукнуло 6 лет!
А на этом наш сказ про CAP закончился. Осталось только подвести итог:
- Под словом CAP понимают две вещи. Первая — формально доказанное утверждение, которое практически не имеет применений в реальности. Вторая — набор суждений про вечный трейдофф consistency / availability / latency / throughput / что-угодно-ещё.
- Разделение сети (partition tolerance) — это возможная, но далеко не единственная ошибка, которая может возникнуть в системе. В реальном мире нужно защищаться от всего.
- Доступность (Availability) в литературе и в реальном мире — две в сущности независимые вещи. В работах это "возможность получить результат", в мире — эмпирическая метрика.
- Даже без явных ошибок, в распределенной системе есть трейдоффы, а все эти консистентности и доступности — не бинарные величины, а точки на спектре.
С вами был человек-акула в IT https://t.me/shark_in_it.