Введение
Давно хотел написать о мифах о CAP-теореме, но руки как-то не доходили.
Однако после прочтения еще один опус , схватился за голову и решил разложить всё по кусочкам, чтобы в мозгу сложилась целостная картина.
Событие, когда статья вызывает бурю эмоций, случается крайне редко.
Впервые это произошло, когда я прочитал о цепной репликации.
Они пытались убедить меня, что это мощный подход и что это лучшее, что может случиться с последовательной репликацией.
Сейчас не буду приводить причины, почему это плохо работает, а просто приведу красноречивую цитату из статьи Управление метаданными цепной репликации :
Управление разделенным мозгом — сложная проблема.В моем вольном пересказе это означает примерно следующее: «У нас здесь есть определенный алгоритм.Представленный здесь метод основан на прагматике.
Если это не сработает, не стоит серьезно беспокоиться, потому что для всех первых серьезных вариантов использования Machi требуется только режим AP. Если мы в конечном итоге вернемся к «использованию Riak Ensemble» или «использованию ZooKeeper», то, возможно, этого будет достаточно.
Мы не знаем, будет ли это работать правильно или нет. И для нас это не имеет значения».
По крайней мере, честно говоря, это сэкономило кучу времени, спасибо авторам.
И тут попадается вот эта статья: Спаннер, TrueTime и теорема CAP .
Разберем по кусочкам ближе к концу, вооружившись понятиями и знаниями.
Перед этим давайте рассмотрим наиболее распространенные мифы, связанные с теоремой CAP.
Миф 1: А означает доступность
А, конечно же, происходит от слова Availability, что означает доступность.Но что это за доступность? Какого рода? Доступность означает разные вещи в разных контекстах.
И здесь нам нужно различать как минимум 2 разных контекста, в которых оно используется:
- Наличие реального сервиса.
Эта доступность выражается в процентах: измеряется общее время простоя в течение года и составляется коэффициент, выраженный в процентах, указывающий вероятность доступности в течение длительного периода времени.
- Доступность в рамках модели теоремы CAP.
Чтобы распределенная система была постоянно доступна, каждый запрос, полученный исправным узлом в системе, должен привести к ответу.Это означает примерно следующее: «любой узел, который не упал в системе, должен ответить на запрос».
В этом определении есть несколько моментов, на которые я хотел бы обратить внимание:
- «Непадший».
Понятно, что упавший узел никак не может отреагировать.
Однако загвоздка в том, что если все узлы не работают, то с точки зрения определения такой сервис доступен.
В принципе, определение можно подкорректировать, добавив обстоятельство, что клиент должен получить ответ.
- «Я должен ответить».
Теорема не говорит точно, когда именно.
Ее совершенно не интересуют параметры времени.
Понятно, что узел не может ответить мгновенно.
А если не может, то ей достаточно когда-нибудь ответить.
Однако с точки зрения теоремы CAP здесь все в порядке и такая система будет доступна (контекст 2).
Поэтому А — это не доступность в общепринятом понимании, а так называемая полная доступность , которые пользователю могут быть вообще не интересны.
Миф 2: P означает сопротивление раздела сети.
Это определение можно встретить практически во всех статьях.
Чтобы понять, что здесь не так, нужно посмотреть на проблему под другим углом.
Возьмем любую систему, которая обменивается сообщениями.
Рассмотрим, как передаются сообщения между акторами — объектами системы.
Эти сообщения могут либо дойти до другого субъекта, либо нет. И здесь нужно различать 2 случая:
- В системе невозможно потерять сообщения.
- Возможно в системе теряются сообщения.
Здесь стоит отметить, что каждый пункт описывает свойства системы.
Те.
Мы еще даже не дошли до алгоритма.
Это будет иметь далеко идущие последствия.
Если рассматривать первый случай, когда сообщения никогда не теряются, то это означает, что в такой ситуации общий доступ к сети (разделение сети) просто невозможно.
Действительно, поскольку каждое сообщение от каждого субъекта может дойти без потерь, то нет смысла говорить о общий доступ к сети .
Во втором случае все наоборот: из-за потерь возможна ситуация, когда целый сегмент отделяется от другого, т.е.
произошла потеря связи между группой акторов.
В этом случае они говорят, что произошло общий доступ к сети .
Следует отметить, что свойство возможности изолировать группы акторов друг от друга является прямым следствием выполнения пункта 2. Если мы работаем с реальной сетью, то, как нетрудно догадаться, она подпадает под 2-й пункт. При этом мы еще не начали думать об алгоритме, но уже имеем возможность разделять и терять связность между группами акторов.
П заключается именно в том, что в системе возможно расщепление.
И это не свойство алгоритма, а свойство системы, в которой алгоритм работает. Почему важно учитывать именно случай потери сообщений? общий доступ к сети ? Потому что другие проблемы не доставляют столько хлопот и проблем, как разделение системы на независимые части.
В заключение этого мифа приведу цитату из блога Aphyr: кластер Percona XtraDB :
Толерантность к разделам не требует, чтобы каждый узел был доступен для обработки запросов.Таким образом, если рассматривать систему, которая работает в реальной ненадежной сети, то сбои сетевого подключения — это не исключительная ситуация, а то, с чем необходимо бороться.Это просто означает, что могут возникнуть разделы.
Если вы развертываете типичную IP-сеть, возникнут разделы; толерантность разделов в этих средах не является обязательной.
А буква П в данном контексте как раз и означает, что в системе может быть нарушение сетевого подключения.
Миф 3: систем переменного тока не существует.
Из предыдущего мифа может сложиться впечатление, что систем переменного тока не существует, потому что… нет надежных сетей, способных передавать данные.Для этого можно сразу попробовать предложить схему с дублирующими компонентами.
Однако если вероятность потери пакета на линии > 0, то как бы мы ни добавляли каналы, вероятность не может стать =0 чисто по математическим причинам.
А если так, то, согласно описанному выше, это может быть общий доступ к сети (разделение сети).
Но кто сказал, что CAP описывает только сетевые системы? CAP — это теоретическая модель, которую можно применять к очень широкому классу задач.
Например, можно взять многоядерный процессор:
- Каждое ядро представляет собой отдельный актер.
- Актеры (ядра) обмениваются сообщениями (информацией).
Есть ли в наличии ядра? Конечно, да, в любой момент мы можем получить доступ к любому ядру и получить из памяти любые данные, которые захотим.
А что насчет П? Процессор гарантирует, что в случае необходимости данные будут без проблем переданы на другое ядро.
Если по каким-то причинам этого не происходит, то такой процессор считается неисправным.
Таким образом, буква П отсутствует. Проблема согласованности также решается следующим образом.
Модель памяти определяет последовательная согласованность , что является высшим уровнем согласованности в такой системе.
При этом протоколы когерентности кэша, такие как MESI или MOESI, обычно реализуются внутри процессора, тем самым обеспечивая заданный уровень согласованности.
Таким образом, современный процессор представляет собой систему переменного тока с гарантированной доставкой сообщений между ядрами.
Миф 4: C означает последовательность.
C, несомненно, означает последовательность.
Однако какая последовательность? Ведь эвентуальная последовательность — это тоже последовательность, только крайне слабая.
Так что же это значит? Существует множество моделей согласованности, достаточно посмотреть на схему из статьи.
Согласованность в нетранзакционных распределенных системах хранения данных : 
И это только о распределенных нетранзакционных системах! Если вы добавите транзакционные соображения , то можно сразу похоронить идею разобраться, даже не начав.
В оригинальной статье о теореме CAP всегда обсуждалась линейность.
Суть линеаризуемости вкратце состоит в следующем.
Если произошло какое-либо действие (будь то чтение, запись или смешанное действие или действия), то результат этого действия доступен сразу после того, как мы получим ответ. Возникает естественный вопрос: а как насчет других моделей согласованности? Подпадают ли они под действие теоремы CAP? И тут в наших головах начинается полный бардак.
Некоторые люди думают, что, поскольку доказана линеаризуемость модели, ее следует использовать строго и исключительно для линеаризуемости.
Другие думают, что любая более слабая модель согласованности больше не подчиняется этой теореме.
Третьи вообще не понимают, в чем суть дискуссии.
Чтобы ответить на этот вопрос, рассмотрим замечательную картинку, взятую из статьи.
Высокодоступные транзакции : 
О чем она говорит? Красным отмечены так называемые модели недоступности, работающие в рамках теоремы CAP. Те.
невозможно достичь А и Р одновременно.
Однако существуют и другие модели, обладающие достаточным уровнем согласованности для ряда задач, которые тем не менее можно одновременно выполнять в связке с AP, получая CAP-систему без каких-либо скидок.
Типичный пример: Чтение зафиксировано (РК) и Монотонный атомарный вид (MAV) допускают соблюдение всех трех букв в CAP одновременно, но такие модели трудно назвать противоречивыми.
Такие модели согласованности, для которых теорема CAP нарушается, называются высокодоступный (высокодоступные модели).
Таким образом, когда мы говорим о непротиворечивости, мы имеем в виду широкую группу моделей непротиворечивости, называемых недоступные модели (недоступные модели).
Миф 5: Системы CP не обладают высокой доступностью
После предыдущего пункта это утверждение кажется вполне логичным, но в корне неверным.Напомню, что А означает полную доступность, а не доступность в пределах девяток.
Можно ли обеспечить высокую доступность системы CP? Здесь необходимо разделить модель и железо, т.е.
теорию и реальность.
Давайте сначала подумаем в рамках модели.
Доступность в рамках теоремы CAP означает полную доступность, т.е.
любой живой узел должен реагировать.
Однако зачем это вообще необходимо? Ведь мы можем написать логику клиента совершенно по-другому.
Предположим, что у нас есть 3 ноды, расположенные в разных дата-центрах.
Пишем в кворум из 2 нод, при этом 1 нода может полежать без потери живучести и консистентности всей системы.
И мы всегда читаем с любых 2-х узлов.
При этом если один узел ляжет, то правильный ответ даст другой узел.
Если придет 2 разных ответа, то мы можем выбрать самый последний.
Таким образом, если эта система гарантирует, что в любой момент времени может выйти из строя только один узел, то с точки зрения клиента система будет полностью доступна на 100% как для чтения, так и для записи.
И последовательно.
В действительности всегда существует ненулевая вероятность того, что приземлится не один, а 2 и более узлов.
В этом легко убедиться, ведь если существует ненулевая вероятность падения одного узла, то будет и ненулевая вероятность падения другого узла или узлов.
Более того, падение – это не самое худшее, что может случиться.
Помимо сбоев оборудования, также может произойти потеря связности, т.е.
поломка различного сетевого оборудования, в том числе магистрального.
Думаю, нет нужды напоминать вам, что все это имеет ненулевую вероятность.
Все эти вероятности складываются, давая лишь определенное, иногда очень маленькое, количество девяток.
Понятно, что чем больше резервирование узлов, тем большее количество девяток можно получить.
И я еще не учел саму программу, которую пишут программисты с ненулевой вероятностью внесения ошибки.
Те.
в теории мы имеем, что правильно написанный клиент может достичь 100% доступности, но на практике мы всегда имеем меньшую цифру.
Вся наука в том, чтобы набрать как можно больше девяток.
И в этом аспекте теорема CAP совершенно бесполезна.
Потому что речь идет совсем о другом.
Поэтому идея высокой доступности совершенно не противоречит тому факту, что это не A, а значит, CP может быть высокодоступным.
Миф 6: CP-системы имеют низкую производительность, большую задержку и плохо масштабируются
Очевидно, что чем выше уровень согласованности, тем менее продуктивна система.Возникает вопрос, насколько сильно будет падение производительности и будет ли оно критично для наших процессов.
Оказывается, даже строгая последовательность или Стронг-1SR (самый высокий уровень согласованности) может использоваться в системах реального времени.
У меня есть экспериментальное подтверждение этого факта, но здесь я приведу ряд практических аргументов в его пользу.
Идея состоит в том, чтобы использовать несколько независимых отказоустойчивых объектов.
Их можно запускать где угодно, они работают параллельно, а их количество фактически ограничено размером кластера.
Поверх этих сущностей создается транзакционный уровень, который связывает работу этих сущностей вместе.
Именно так это и работает Гаечный ключ и многие другие системы.
Это обеспечивает масштабируемость и производительность.
Миф 7: Системы AP просты в использовании, потому что они хорошо масштабируются.
Системы с AP позволяют упростить масштабирование, но только теоретически.
В действительности, вопросы согласованности все еще требуют решения в той или иной степени.
Практика показывает, что написание клиентского кода на основе такой системы — задача крайне нетривиальная, а иногда даже недостижимая.
Причина в том, что если система не обеспечивает каких-то базовых гарантий непротиворечивого хранения данных, то последующая обработка превращается в очень увлекательную шараду: применилась ли операция? увидят ли это пользователи? что они увидят? Можно ли получить последовательный фрагмент данных? будут ли разные клиенты видеть один и тот же набор данных? и т. д. Те.
Несмотря на относительную простоту создания таких систем, сложность их использования многократно возрастает.
Анализ статьи
Ну а теперь приступим к анализу статьи Спаннер, TrueTime и теорема CAP .Начнем с самого начала:
Теорема CAP [Bre12] гласит, что вы можете обладать только двумя из трех желательных свойств:Первое, на что следует обратить внимание, это ссылка [Bre12] под названием CAP двенадцать лет спустя: как изменились «правила» , датировано маем 2012 г.
- C: Согласованность, которую в этом обсуждении мы можем рассматривать как сериализуемость;
- О: 100% доступность как для чтения, так и для обновлений;
- P: устойчивость к разделам сети.
Почему вы выбрали ссылку, отличную от оригинальная статья - Я не знаю.
Более того, эта статья посвящена обсуждению теоремы CAP, а не выводу самой теоремы.
О буквах С, А и Р мы уже говорили, поэтому я не буду на них останавливаться.
Дальше:
Как только вы поверите, что разделение неизбежно, любая распределенная система должна быть готова отказаться от согласованности (AP) или доступности (CP), а это не тот выбор, который кто-либо хочет сделать.Первая часть звучит вполне разумно в рамках наших дискуссий, но после AP&CP происходит что-то странное, потому что вдруг мы не хотим делать этот выбор.
Почему мы не хотим делать такой выбор, в статье не написано.
Но тут были написаны правильные слова:
Фактическая теорема касается 100% доступности, а интересное обсуждение здесь касается компромиссов, необходимых для достижения реалистичной высокой доступности.Казалось бы, на этом можно было бы остановиться и сказать, что Spanner — это CP-система с доступностью 99,9.%, и положить этому конец.
Но нет, автор продолжает и пишет подзаголовок:
Как я показал выше, так называемые высокодоступный (высокодоступность) вовсе не означает А и уж точно не означает отсутствия Р.Спаннер утверждает, что он последователен и доступен.
Spanner утверждает, что он непротиворечив и имеет высокую доступность, что подразумевает отсутствие разделов, и поэтому многие относятся к этому скептически.
После этого начинается словесная балансировка, т.к.
из ошибочной посылки можно вывести много смешного.
Автору очень хочется, чтобы система была и С и А одновременно, ведь Р от слова пользователю вообще не нужен.
В то же время вводится новая концепция: эффективно ЦА .
Такое ощущение, что автор поигрался с понятиями и начал придумывать новые без всякого определения, потому что.
старые плохо описывали такую чудесную систему.
Читаем дальше:
Основываясь на большом количестве внутренних пользователей Spanner, мы знаем, что они полагают, что Spanner имеет высокую доступность.Сама фраза замечательная.
Оказывается, если внутренние пользователи говорят: «Мы предполагаем, что это высокая доступность», то это сразу подразумевает что-то о самой системе.
Было бы неплохо, если бы пользователи говорили: «да, это высокодоступно», тогда они говорили о чем-то, о чем только догадываются.
Далее следует завораживающее:
Если основными причинами сбоев Spanner не являются разделы, то CA в некотором смысле более точен.Те.
если же мы испытываем сбой, не связанный с нарушением сетевого подключения, то такую систему следует точнее в каком-то смысле (!) называть CA. Те.
если вероятность других сбоев больше, чем сбой соединения, то P отсутствует. В этом смысле следует понимать эту фразу? Далее следует маркетинговая ложь о том, что мы построили сверхнадежную систему, подтвержденную графиками.
Ниже, наконец, приведено определение, раскрывающее значение набора слов.
эффективно ЦА :
… требовать эффективно ЦА система должна находиться в таком состоянии относительных вероятностей:Те.Спаннер встречает обоих.
- Как минимум, на практике он должен иметь очень высокую доступность (чтобы пользователи могли игнорировать исключения) и
- поскольку речь идет о разделах, доля сбоев из-за разделов также должна быть небольшой.
система должна:
- на практике иметь высокую доступность, где пользователи могут игнорировать исключения, и
- вероятность разделения сети должна быть меньше, чем другие проблемы.
Ну а «игнорирование исключений пользователем» завершает всю неоднозначность и двусмысленность этого, страшно сказать, определения.
Как видите, это определение не подходит к модели, которая используется непосредственно в теореме CAP. Совершенно непонятно, к какой модели это относится.
Речь идет больше об экспериментальных наблюдениях, чем о теоретической модели.
И связи эксперимента с теорией в статье не прослеживается.
Я не буду вдаваться в подробности других аспектов статьи.
Скажу только, что некоторые абзацы стоит прочитать, например «Что происходит во время раздела».
Авторы заканчивают следующим великолепным отрывком:
Spanner обоснованно заявляет, что является «эффективной системой CA», несмотря на то, что работает на обширной территории, поскольку она всегда стабильна и обеспечивает доступность выше 5 девяток.Ну да, если мы определим, что наша система — это X, то наша система будет обладать свойствами X. Отлично, правда? Но это определение не имеет ничего общего с теоремой CAP. Это необходимо ясно понимать.
Авторы, видимо, очень хотели, чтобы там была не Р, а две другие буквы, потому что.
за них платит пользователь.
Почему их не устроил CP с высокой доступностью, мне неизвестно.
Даже в этом случае будут происходить сбои, и в этом случае Спаннер предпочитает стабильность, а не доступность.Что явно противоречит системе СА: в такой системе выбор не производится, потому что выбираются оба свойства, как мы видели выше на примере СА.
Наличие такого утверждения говорит о том, что это точно не СА.
Я не ожидал увидеть в такой статье взаимоисключающие абзацы.
Последний миф: теорема CAP устарела
Популярность этой темы привела к тому, что многие люди перестали понимать значение терминов; они стали расплываться, выхолащиваясь до совершенно вульгарного понимания.Спекуляции на терминах, переопределения и непонимания – вот неполный список родимых пятен этой многострадальной теоремы.
На волне популярности маятник качнулся в другую сторону, и люди стали понемногу забывать об этой теореме.
Стали появляться статьи о том, что, мол, Теорема CAP устарела И просить прекратить его использование .
Другие пробовали критиковать и вносить вклад в сокрытии и изменении смыслов.
Даже сам автор теоремы начинает подменять понятия и искажать первоначальный замысел.
Подобные нападки на теорему снова и снова лишь подчеркивают ее актуальность, раскрывая новые, доселе неизвестные грани.
Заключение
В свое время знакомство с теоремой CAP неплохо отрезвило мозг.Ведь теоретическая невозможность создания системы определенного типа давала основание не заниматься практикой решения трудноразрешимых задач и сосредоточиться на решении задач определенного класса.
В контексте распределенных систем имеет смысл говорить только о задачах AP или CP. Теоремы такого рода не устаревают, как не может устареть классическая механика, несмотря на наличие релятивистских эффектов или квантовой механики.
Ей просто нужно найти свое законное место, нам нужно помнить о ней и двигаться дальше.
Но все дело в том, что эта теорема есть лишь частный случай более общей фундаментальное свойство :
В этом свете теорема CAP является просто одним из примеров того фундаментального факта, что невозможно одновременно обеспечить безопасность и работоспособность в ненадежной распределенной системе.Те.
Теорема CAP — это просто один из примеров того фундаментального факта, что невозможно одновременно обеспечить безопасность и живучесть в ненадежной распределенной системе.
- С: Безопасность
- А: Жизненная сила
- П: Ненадежная распределенная система
Литература Управление метаданными цепной репликации в Machi, неизменяемом хранилище файлов Спаннер, TrueTime и теорема CAP Гипотеза Брюэра и возможность создания согласованной, доступной, устойчивой к разделению сети Джепсен: кластер Percona XtraDB Согласованность в нетранзакционных распределенных системах хранения данных Исследование условий согласованности Высокодоступные транзакции: преимущества и ограничения (расширенная версия) Spanner: глобально распределенная база данных Google. CAP двенадцать лет спустя: как изменились «правила» Забудьте о теореме CAP, поскольку она больше не актуальна.
Пожалуйста, прекратите звонить в базы данных CP или AP. Критика теоремы CAP Перспективы теоремы CAP YT: зачем Яндексу нужна собственная система MapReduce и как она работает Теги: #Алгоритмы #Системный анализ и проектирование #NoSQL #Распределенные системы #Промышленное программирование #доступность #yt #согласованность #теорема ограничения
-
Психология Платных Онлайн-Опросов
19 Oct, 24 -
Ковалевская Софья Васильевна
19 Oct, 24 -
Дрифтовать В Москве Просто Нереально =)
19 Oct, 24 -
Стив В Порядке
19 Oct, 24 -
Стартовал Конкурс «Премия Рунета – 2006».
19 Oct, 24
