CAP-теорема Брюера

По большей части эта статья — изложение сути статьи "Brewer's CAP Theorem" Джулиана Брауна. В оригинале много полезных ссылок и интересных примеров, поэтому если позволяет время и знание языка, почитайте его. А здесь у меня просто самая суть, покороче и по-русски.

В 2000 году Эрик Брюер выдвинул гипотезу, касающуюся ключевых свойств распределённых систем, которую затем доказали в MIT, и с тех пор она называется теоремой Брюера или теоремой CAP (Consistency-Availability-Partition tolerance). Вольная формулировка:

В распределённой системе невозможно обеспечить одновременное выполнение всех трёх условий: корректности, доступности, устойчивости к сбоям узлов.

Что это за свойства.

Корректность (Consistency): Говорит о том, что система всегда выдаёт только логически непротиворечивые ответы. То есть не бывает такого, что вы добавили в корзину товар, а после рефреша страницы его там не видите.
Доступность (Availability): Означает, что сервис отвечает на запросы, а не выдаёт ошибки о том, что он недоступен.
Устойчивость к сбоям сети (Partition tolerance): Означает, что распределённая по кластеру система работает в расчёте на случаи произвольной потери пакетов внутри сети.

Для лучшего осознания, вот три соответствующих примера того, что могут представлять собой системы без одного из этих свойств:

+Availability +Consistency -Parition tolerance: Система, которая рассчитывает на то, что сеть абсолютно надёжна, и благодаря этому может обеспечить консистентность данных на всех живых узлах. Или, в вырожденном случае, система из одного узла, где неконсистентности быть не может, и которая доступна всегда, когда доступен её узел. Другими словами, на практике таких систем или не существует, или они не являются распределёнными (см. также).
+Consistency +Partition tolerance -Availability: Система с несколькими мастер-базами, которые обновляются синхронно. Она всегда корректна, потому что транзакция отрабатывает, только если изменения удалось распространить по всем серверам БД. Она продолжает корректно работать по крайней мере на чтение, если один из серверов падает. А вот попытки записи будут обрываться или сильно задерживаться, пока система не убедится в своей консистентности.
+Availability +Partition tolerance -Consistency: Система с несколькими серверами, каждый из которых может принимать данные, но не обязуется в тот же момент распространять их по всему кластеру. Система переживает падения части серверов, но когда они входят в строй, они будут выдавать пользователям старые данные.

Важность того, что невозможность обеспечить все три свойства сразу, доказана математически, избавляет нас (тупых инженеро́в :-) ) от тщетных попыток создать некую идеальную систему, которая никогда-никогда не ломается. Вместо этого мы теперь можем делать привычный нам инженерный выбор двух из трёх.

Как в известном предложении клиенту: "быстро, дёшево, качественно — выбирайте любые два".

Причём, как в большинстве инженерных ситуаций, этот выбор не стоит как "всё или ничего". Система может располагаться где угодно в пределах этого воображаемого треугольника, быть "более" консистентной, "менее" доступной и "слегка" нецелой. В анти-идеале можно написать систему, у которой будет плохо со всеми тремя компонентами. Уверен, вы с такими встречались :-).

Одно из интересных практических следствий этой теоремы в том, что в последнее время многие бизнесы решили для себя, что совсем не обязательно упираться в принципы дизайна ACID, который ставит во главу угла Consistency, жертвуя двумя другими свойствами. Теперь у нас есть такая альтернатива, как BASE (известная также как "eventual consistency"), которую например очень любят и используют в Amazon. Там во главе угла стоит Availability.

А ещё один дядька — Гай Пардон — вообще предлагает инженерное решение, которое обходит проблему CAP. Правда, он немного читерствует (с математикой трудно спорить), говоря, что хоть и нельзя обеспечить все три свойства одновременно, можно построить систему так, чтобы она достигала желаемого постепенно.

P.S. Андрей, спасибо за давешнюю ссылку на описание BASE.

Комментарии: 19 (особо ценных: 2)

zerkms

Особо ценный комментарий

В своё время, когда общался с более опытным товарищем на эту тему, он поделился ссылкой. Надеюсь она и вам понравится:

http://javathink.blogspot.com/2010/01/characterizing-enterprise-systems-using.html?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed:+blogspot/thinkinginjava+(Thinking+In+Java)&utm_content=Google+Reader

Вкратце: по ссылке описан ряд хранилищ и выбор стратегии CAP.

Денис Баженов

Еще одна интересная ссылка где CTO Amazon'а Werner Vogels объясняет принципы eventual consistency и то почему у них "во главе угла того самого треугольника" стоит Availability. За одну минуту downtime'а Amazon способен потерять около $3000. Так что выбор вполне очевиден.

http://www.allthingsdistributed.com/2008/12/eventually_consistent.html

http://claimid.com/vlasovskikh

Полезное напоминание о CAP. Спасибо за заметку.

Fulcrum

Первый случай формально удоволетворяет свойству Partion tolerance, просто это не распределенная система.

Ivan Sagalaev

Fulcrum, и правда. Поменял пример. Теперь подходит?

Twitter Trackbacks for Маниакальный Веблог » CAP-теорема Брюера [softwaremaniacs.org] on Topsy.com

Маниакальный Веблог » CAP-теорема Брюера

rra

"Шардированная СУБД" - уникальный термин. Google выдает одну ссылку, угадайте куда.

http://tinyurl.com/ygdyzwo

Ivan Sagalaev

"Шардированная СУБД" - уникальный термин.

%-))))

Я сначала не поверил...

Роман Петрухин

Ваня, я не знаю почему,:-) но у меня словосочетание "в MIT доказали теорему" всегда вызывает воспоминания об одном классном тексте :-) Вот цитата из него:

Ходили по Массачусетскому Технологическому Институту (MIT) два несносных вундеркинда-кибернетика Карл Хьюитт и Терри Виноград. Несноснее Карла в MIT был разве, что Терри, и наоборот. И ничего, MIT и не такое видал. Ни один Нобелевский лауреат от этого не пострадал. Кстати, говорят, что, кроме MIT, Нобелевские лауреаты водятся иногда и в других местах. Короче, детские диалоги Карла и Терри были малопонятны окружающим лауреатам и кончились тем, что Карл (в 23 года) прославился созданием языка PLANNER, ставшего классикой ИИ, а Терри - один из основоположников в сфере ПОНИМАНИЯ естественного языка компьютером. Оба увлекались игрой в кубики.

Текст целиком: http://arbuz.uz/t_ii.html Но, я думаю, ты его читал :-)

Ivan Sagalaev

Веришь ли, не читал :-)

nvy

Важность того, что невозможность обеспечить все три свойства сразу, доказана математически,

А ссылочку на сие слабо дать?

P.S.Я Вам на слово верю есличо:)

Ivan Sagalaev

Во втором абзаце поста: http://people.csail.mit.edu/sethg/pubs/BrewersConjecture-SigAct.pdf

Николай Власов

Большое спасибо за ссылки - очень интересная статья. Однако, у вас есть небольшая нетчность в переводе формулировки теоремы. В оригинале она выглядит следующим образом (стр.1): it is impossible for a web service to provide the following three guarantees: - Consistency - Availability - Partition-tolerance Под веб сервисом в доказательстве понимаются асинхронные и частично-синхронные распределенные системы и это понятно, так как синхронизовать часы на всех устройствах, подключенных к такой сети как Интерет, например, практически нереально :) Однако, если предположить, что в распределенной системе все ее компоненты имеют синхронизованное время, то доказательство теоремы для них, строго говоря, работать не будет.

Тем не менее с ваши выводы верны, но с той лишь оговоркой, что это справедливо для веб сервисов!

kroki

Особо ценный комментарий

Устойчивость к сбоям узлов (Partition tolerance)

В оригинале "Partition tolerance" означает не "устойчивость к сбоям партиций", а как раз наоборот, "устойчивость к появлению партиций", то есть ситуации, когда отказывает сеть, кластер делатся на две (или более) партиции, при этом каждая из партиций продолжает обслуживать свой набор клиентов (этого требует availability), в том числе принимает обновления от клиентов. Тогда после восстановления сетевых соединений мы можем обнаружить, что одни и те же данные на разных партициях были изменены несовместимым образом, то есть будет нарушена consistency.

Алексей

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

allweeks.ru » CAP теорема

http://softwaremaniacs.org/blog/2010/01/31/brewers-cap-theorem/

Artem Danilov

Я не совсем согласен с вашей интерпретацией CAP-теоремы. Я утверждаю, что распределенную систему, в которой бы на 100% выполнялась согласованность и доступность, построить в реальном мире невозможно. Мне кажется в Вашем примере шардированной БД нет avalability. В коментариях сложно много писать, поэтому предлагаю ознакомиться с моим мнением на хабре: http://habrahabr.ru/blogs/nosql/136305. В конце есть несколько ссылок, где эта идея описана более развернуто. Но основная идея в том, что CAP-теорема сформулирована для идеальной системы, чего на самом деле не бывает.

Ivan Sagalaev

Артём, спасибо за комментарий и ссылку. Камень с души сняли :-). Ответил подробнее постом.

Распределенная согласованность — Часть 1 — Введение | sufr

CAP теорема гласит, что в системе одновременно можно выбрать только две вещи з трех: корректность, доступность, устойчивость к разделению сети. В распределенных системах недоступность некоторых узлов неизбежна и система должна быть устойчивой к этому, поэтому CAP означает, что мы не можем одновременно поддерживать корректность и 100% доступности.

Добавить комментарий

zerkms

Особо ценный комментарий

В своё время, когда общался с более опытным товарищем на эту тему, он поделился ссылкой. Надеюсь она и вам понравится:

http://javathink.blogspot.com/2010/01/characterizing-enterprise-systems-using.html?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed:+blogspot/thinkinginjava+(Thinking+In+Java)&utm_content=Google+Reader

Вкратце: по ссылке описан ряд хранилищ и выбор стратегии CAP.
Денис Баженов

Еще одна интересная ссылка где CTO Amazon'а Werner Vogels объясняет принципы eventual consistency и то почему у них "во главе угла того самого треугольника" стоит Availability. За одну минуту downtime'а Amazon способен потерять около $3000. Так что выбор вполне очевиден.

http://www.allthingsdistributed.com/2008/12/eventually_consistent.html
http://claimid.com/vlasovskikh

Полезное напоминание о CAP. Спасибо за заметку.
Fulcrum

Первый случай формально удоволетворяет свойству Partion tolerance, просто это не распределенная система.
Ivan Sagalaev

Fulcrum, и правда. Поменял пример. Теперь подходит?
Twitter Trackbacks for Маниакальный Веблог » CAP-теорема Брюера [softwaremaniacs.org] on Topsy.com

Маниакальный Веблог » CAP-теорема Брюера
rra

"Шардированная СУБД" - уникальный термин. Google выдает одну ссылку, угадайте куда.

http://tinyurl.com/ygdyzwo
Ivan Sagalaev

"Шардированная СУБД" - уникальный термин.

%-))))

Я сначала не поверил...
Роман Петрухин

Ваня, я не знаю почему,:-) но у меня словосочетание "в MIT доказали теорему" всегда вызывает воспоминания об одном классном тексте :-) Вот цитата из него:

Ходили по Массачусетскому Технологическому Институту (MIT) два несносных вундеркинда-кибернетика Карл Хьюитт и Терри Виноград. Несноснее Карла в MIT был разве, что Терри, и наоборот. И ничего, MIT и не такое видал. Ни один Нобелевский лауреат от этого не пострадал. Кстати, говорят, что, кроме MIT, Нобелевские лауреаты водятся иногда и в других местах. Короче, детские диалоги Карла и Терри были малопонятны окружающим лауреатам и кончились тем, что Карл (в 23 года) прославился созданием языка PLANNER, ставшего классикой ИИ, а Терри - один из основоположников в сфере ПОНИМАНИЯ естественного языка компьютером. Оба увлекались игрой в кубики.

Текст целиком: http://arbuz.uz/t_ii.html Но, я думаю, ты его читал :-)
Ivan Sagalaev

Веришь ли, не читал :-)
nvy

Важность того, что невозможность обеспечить все три свойства сразу, доказана математически,

А ссылочку на сие слабо дать?

P.S.Я Вам на слово верю есличо:)
Ivan Sagalaev

Во втором абзаце поста: http://people.csail.mit.edu/sethg/pubs/BrewersConjecture-SigAct.pdf
Николай Власов

Большое спасибо за ссылки - очень интересная статья. Однако, у вас есть небольшая нетчность в переводе формулировки теоремы. В оригинале она выглядит следующим образом (стр.1): it is impossible for a web service to provide the following three guarantees: - Consistency - Availability - Partition-tolerance Под веб сервисом в доказательстве понимаются асинхронные и частично-синхронные распределенные системы и это понятно, так как синхронизовать часы на всех устройствах, подключенных к такой сети как Интерет, например, практически нереально :) Однако, если предположить, что в распределенной системе все ее компоненты имеют синхронизованное время, то доказательство теоремы для них, строго говоря, работать не будет.

Тем не менее с ваши выводы верны, но с той лишь оговоркой, что это справедливо для веб сервисов!
kroki

Особо ценный комментарий

Устойчивость к сбоям узлов (Partition tolerance)

В оригинале "Partition tolerance" означает не "устойчивость к сбоям партиций", а как раз наоборот, "устойчивость к появлению партиций", то есть ситуации, когда отказывает сеть, кластер делатся на две (или более) партиции, при этом каждая из партиций продолжает обслуживать свой набор клиентов (этого требует availability), в том числе принимает обновления от клиентов. Тогда после восстановления сетевых соединений мы можем обнаружить, что одни и те же данные на разных партициях были изменены несовместимым образом, то есть будет нарушена consistency.
Алексей

Как я понимаю, практически можно искать компромиссы вроде синхронизации шардов через общий авто-инкремент, или синхронизации часов для сведения вероятности неконсистентности к практически равной нулю и т.д.
allweeks.ru » CAP теорема

http://softwaremaniacs.org/blog/2010/01/31/brewers-cap-theorem/
Artem Danilov

Я не совсем согласен с вашей интерпретацией CAP-теоремы. Я утверждаю, что распределенную систему, в которой бы на 100% выполнялась согласованность и доступность, построить в реальном мире невозможно. Мне кажется в Вашем примере шардированной БД нет avalability. В коментариях сложно много писать, поэтому предлагаю ознакомиться с моим мнением на хабре: http://habrahabr.ru/blogs/nosql/136305. В конце есть несколько ссылок, где эта идея описана более развернуто. Но основная идея в том, что CAP-теорема сформулирована для идеальной системы, чего на самом деле не бывает.
Ivan Sagalaev

Артём, спасибо за комментарий и ссылку. Камень с души сняли :-). Ответил подробнее постом.
Распределенная согласованность — Часть 1 — Введение | sufr

CAP теорема гласит, что в системе одновременно можно выбрать только две вещи з трех: корректность, доступность, устойчивость к разделению сети. В распределенных системах недоступность некоторых узлов неизбежна и система должна быть устойчивой к этому, поэтому CAP означает, что мы не можем одновременно поддерживать корректность и 100% доступности.