Разъяснение по CAP-теореме

    Статья "Недопонимание CAP-теоремы" и комментарии к ней свидетельствуют, что непонимание действительно есть. И связано оно не только с неправильным толкованием термина «partitioning», но и с ментальными ошибками на других уровнях. Попробую внести ясность.

    Условности

    Для начала, договоримся об уровне абстракций.
    В рамках теоремы бессмысленно заявлять, что в «реальном мире» не может быть гарантированной связи между узлами распределенной системы. С тем же успехом можно сказать, что такое свойство как «availability» недостижимо в принципе, поскольку любая система перестанет быть доступной при отказе достаточного числа узлов (например, при отказе всех ее узлов).

    Поэтому давайте условимся, что речь идет все-таки о модели и в ней сделаны некоторые допущения.
    Мы будем считать, что вероятность отказа критического числа узлов системы пренебрежимо мала — это даст нам возможность говорить, что гарантировать availability все-таки можно.
    Мы не будем рассматривать устройство узлов и характер связи между ними — для теоремы это неважно.

    Технически, мы можем создать систему, в которой вероятность потери связи между узлами будет еще меньше, чем вероятность отказа критического числа узлов (которую мы считаем пренебрежимо малой). Благодаря этому мы можем говорить, что распределенная система с гарантированной связью между узлами (невозможностью partitioning'а) — возможна.

    Как конкретно этого добиться — неважно. Возможно, понадобится миллионократное дублирование систем связи или изобретение сверхнадежного гравитонного передатчика, который на тучу порядков устойчивей к любым воздействиям, чем наши грубые кремниевые поделки. Факт, что это можно сделать, если кому-то правда приспичит. Делают же компьютеры, в которых 4 процессора считают одно и то же только чтобы перепроверить друг друга. С той же тщательностью можно подойти к гарантиям обеспечения связи.

    Смерть милее

    Важно понимать, что смерть узла системы и потеря с ним связи не эквивалентны.
    Разница проста — умерший узел не может совершать действий, которые «по неведению» окажутся деструктивными по отношению к остальной системе. Всегда можно устроить так, чтобы он умирал навсегда, или приходя в себя первым делом консультировался с остальной системой, чтобы ненароком ничего не сломать.

    При разрыве связи все печальнее. Узел не может позволить себе умереть, потому что возможно только он и обеспечивает работоспособность (без связи с другими узлами невозможно понять, есть ли еще кто-то живой). Не может он и синхронизировать свою работу с остальными — связи-то нет. Остается действовать вслепую, на свой страх и риск.

    Рассмотрим происходящее на конкретном примере

    Допустим, в нашей системе ровно 2 совершенно одинаковых узла — A и B. Каждый из них хранит копию данных второго и может независимо обрабатывать запросы извне. Каждый, обрабатывая запрос, уведомляет второго об изменениях, чтобы данные оставались согласованы.

    Вариант 1: узел A умирает.
    Система продолжает работать как ни в чем не бывало — B продолжает обрабатывать запросы. Когда A приведут в чувство, он первым делом синхронизируется с B и они вдвоем продолжат работать дальше. Ни доступность, ни согласованность не страдают.

    Вариант 2: A и B живы, но связь между ними прервана.
    При этом каждый из них продолжает принимать запросы извне, но не может уведомить второго об изменениях. Для каждого узла все выглядит так, будто второй узел умер и он действует в одиночку. Эту ситуацию часто называют «split-brain» — мозг разделился на два полушария, каждое из которых считает себя единственным хозяином ситуации. Система заболела шизофренией.

    Если в этот момент на A был обработан запрос на удаление некой записи R, а на B был обработан запрос на модификацию той же самой записи, то данные стали несогласованы. Когда связь между A и B восстановится, при синхронизации всплывет конфликт — удалить R или оставить модифицированную версию? Тут можно выкручиваться разными стратегиями разрешения конфликтов, но consistency мы уже потеряли.

    Альтернативный способ решения проблемы — A и B, видя, что потеряли связь друг с другом, перестают обрабатывать запросы. В этом случае согласованность не нарушится, но будет потеряна availability.

    Ближе к реальности

    Конечно, системы ровно из двух узлов встречаются нечасто. Но то же самое верно, если считать что A и B не два отдельных узла, а два набора узлов. При этом считаем, что общение между двумя любыми узлами в пределах A и в пределах B осталось возможным, но узлы из A не могут взаимодействовать с узлами из B. При этом оба набора продолжают получать и обрабатывать запросы извне.

    По сути это описание типичной ситуации, когда прервалась связь между двумя датацентрами. Split-brain надежно обеспечивает системе шизофрению даже в таком простом случае. Если же сплитов несколько или в разных группах оказались доступны неполные наборы данных, все может оказаться еще хуже.

    Возвращаясь к теореме

    Теорема гласит, что CA достигается только потерей устойчивости к нарушению связи между узлами. На практике это означает, что CA-системы правильно использовать в случаях, когда мы считаем вероятность потери связи пренебрежимо малой.

    Какими путями мы этого добиваемся — теореме пофиг. Не нужно призывать «реальный мир», чтобы показать, что чуваки чего-то не догоняли. Теорема существует в рамках модели. Как она верна сейчас, также она будет верна и послезавтра, когда наконец изобретут гравитонный передатчик.

    Но даже без гравитонного передатчика не так все плохо. Потеря связи между датацентрами — явление не столь частое. В пределах одного датацентра — еще реже. Да, если сплит возникнет, придется решать конфликты. Возможно даже руками, хотя огромное число задач позволяет разрешить многие конфликты автоматически. Но, возможно, прелести CA-системы привлекут нас гораздо больше, чем отпугнет необходимость чинить что-то руками в случае маловероятного сплита. В этом случае мы с чистым сердцем будем считать вероятность возникновения проблем пренебрежимо малой, даже не опираясь на супертехнологии будущего.

    Ну а если в своем проекте вы считаете вероятность сплита достаточно высокой, можно переформулировать теорему таким образом: при возниконовении сплита остается только выбирать — A или C.

    Лирическое отступление

    Существуют приемы, позволяющие смягчить CAP-теорему в разных частных случаях. Человеку не обязательно нужна система, работающая идеально. Часто хватает того, чтобы она работала достаточно хорошо, хотя бы в большинстве случаев.

    Эти приемы включают как попытки автоматического восстановления целостности, после того как страшное случилось, так и попытки недопустить потери целостности, при этом не скатываясь в полный отказ от доступности.

    Простейший пример: каждый узел автоматически прекращает обрабатывать запросы извне, если видит меньше чем половину остальных узлов. Это гарантирует, что если система разделится на две неравные части, то одна из них продолжит работу, а другая автоматически совершит харакири, чтобы не наделать глупостей.

    Другое дело, что оставшись с половиной мощности, система скорее всего целиком ляжет под нагрузкой. Но можно применить еще одну хитрость — узлы, оставшиеся в изоляции, могут продолжить работать на чтение, не создавая конфликтов. Для систем с интенсивным чтением вполне оправданный ход. Правда, отдаваемые данные не всегда будут актуальны, но часто это лучше чем ничего. Однако при разделении на несколько частей, уже ни одна из них не сможет обрабатывать запросы на запись. Хотя можно придумать что-нибудь и похитрее…

    Как ни изворачивайся, в целом CAP-теорему не обойти. Но в большинстве проектов есть огромные просторы для поисков способа выкрутиться, сводя вероятность проблемных сценариев к минимуму.

    PS javaspecialist, спасибо за повод для написания этой статьи.
    Поделиться публикацией
    Похожие публикации
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 15
      –1
      >При разрыве связи все печальнее. Узел не может позволить себе умереть, потому что возможно только он и обеспечивает работоспособность (без связи с другими узлами невозможно понять, есть ли еще кто-то живой).

      Печальней ли?
      linux-ha.org/wiki/Cluster_Concepts#Determination_of_Quorum
        +2
        Конечно, печальнее.

        Цитирую статью по вашей ссылке: «Nevertheless, no quorum algorithm can provide an absolute guarantee of this property in the presence of arbitrary failures. Different quorum implementations provide different degrees of certainty for any given configuration and set of expected failures.»

        Именно про простейший вариант кворума написано в «лирическом отступлении». Читайте внимательнее.
        0
        Эх, всё равно не до конца понятно, давайте по полочкам:
        CP —
        A и B, видя, что потеряли связь друг с другом, перестают обрабатывать запросы. В этом случае согласованность не нарушится, но будет потеряна availability.

        AP —
        Когда связь между A и B восстановится, при синхронизации всплывет конфликт — удалить R или оставить модифицированную версию? Тут можно выкручиваться разными стратегиями разрешения конфликтов, но consistency мы уже потеряли.

        CA — ?
          0
          CA означает, что система неустойчива к сплитам. Соответственно, пока сплита нет, мы имеем СА. Как только произошел сплит — выбирайте, С или А. В первом случае это может быть DOS (или работа только на чтение, например), во втором -несогласованность данных.
            0
            Тогда получается либо если нету P то нету и CA — либо просто C, либо просто A, a если есть P — то CP либо CA. так?
              0
              Не совсем. Имеет смысл «выбирать» СА только в случае, если мы можем гарантировать целостность системы, то есть отсутствие сплитов. В таком случае мы считаем, что система целостна, и СА есть.
              В этой теореме РТ немного глубже, чем А и С.
              0
              Ошибся в последнем сообщении: без P — A или C, с P — CP или AP.
              CA как таковой не существует? Потому как «система неустойчива к сплитам» не очень вяжется с «пока сплита нет» — если неустойчива к сплитам, оценивать нужно по худшей ситуации, т.е. сплит есть.
                +9
                Очень даже вяжется.

                «Система неустойчива к сплитам» как раз и означает, что как только сплит — мы ничего не гарантируем. Все в силе только «пока сплита нет».

                Представьте, вам предлагают построить дом, в котором ничего не сделано для защиты от ураганов. Пока урагана нет — все хорошо. Как только ураган — вам ничего не гарантируют.
                Купите вы такой дом? — Почему бы и нет, если вы живете не в Канзасе и про ураганы разве что читали в «Волшебнике Изумрудного города».

                Или вы станете «оценивать по худшей ситуации» и жить в бункере с защитой от цунами, взрывов водородной бомбы и пятью линиями вооруженной охраны, испытывая все связанные с таким непростым местом жительства неудобства?
                  +2
                  Этот комментарий доходчивее отвечает на поставленный вопрос, чем статья.
                    0
                    Да, спасибо автору за ответы
            +1
            Не «брейнсплит», а «сплитбрейн». Вечная проблема для любых кластерных систем.
              0
              спасибо, поправил
              0
              Дмитрий, спасибо большое за подробное разъяснение. К сожалению, статью увидел только сегодня, поэтому и коммент пишу только сейчас.

              В целом, я с Вами абсолютно согласен, действительно, теорема построена и доказана для модели. Я в своем топике, в комментариях, к сожалению ушел от темы теоремы и стал рассуждать о возможности построения CA системы в «реальном мире». Хотя, впрочем, теоретическая часть теоремы мне не очень интересна, мне важно ее применение на практике.

              Но все же напишу пару слов о некоторых ваших высказываниях, которые меня немного покоробили:

              1. Чисто формально в теореме Avalability — это способность давать ответ не упавших компонент. Т.е. пример о невозможности построения системы со 100% avalability в терминах теоремы не совсем корректен. Мне все таки кажется создать систему полностью согласованной или полностью доступной в терминах теоремы все же можно, в отличие от системы без 100% потерь связи. Но Вы совершенно правы, в теореме мы имеем дело с моделью, поэтому об этом говорить можно.

              2. Ваш пример CA системы, где придется что-то чинить руками в случае маловероятного сплита, мне кажется не совсем хорошим, так как во время починки, ваша система уже не будет A, соответственно, и не будет CA.

              3. Вы привели очень хороший пример с домом. И я как практик с вами очень даже соглашусь. Но как теоретик, я призадумаюсь. Ведь, если уж мы говорим о теореме с моделью, то как-то называть систему сначала CA, а потом, когда что-то произошло называть CP или AP, не кажется мне очень логичным. Все таки в теореме мы говорим о постоянном свойстве системы, с обозначенными свойствами модели.

              Еще раз повторю, что с мыслью проходящей сквозь весь Ваш топик я абсолютно согласен. Теорема — эта модель и, что ее нельзя получить в реальном мире, ее это мало волнует. Однако переходя все же из теоремы в реальный мир, я вижу очень полезное утверждение, которое напрямую следует из этой теоремы. Так как в реальном мире устойчивость к сплиту достичь на 100% невозможно (но вы совершенно верно, невозможно пока), то и построить систему на 100% удовлетворяющую CA невозможно. Ну или можно еще сформулировать как это Вы сделали, т.е. можно, но до первой потери сообщения.

              Нда, немного противоречивый комментарий получился. Ну уж какой есть :)
                0
                Господа, ощущение что нам нужен еще один топик для продолжения обсуждения, или даже два. Обзор стратегий разрешения конфликтов для обеспечения, собственно, Eventual Consistency, и обзор борьбы со brainsplit-ом (кворумы и прочее, какие техники применяются в распределенныхт системах, например, в Oracle Coherence).
                  0
                  Так напишите статью )
                  Мои знания по теме поверхностны.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое