По большей части эта статья — изложение сути статьи "Brewer's CAP Theorem" Джулиана Брауна. В оригинале много полезных ссылок и интересных примеров, поэтому если позволяет время и знание языка, почитайте его. А здесь у меня просто самая суть, покороче и по-русски.
В 2000 году Эрик Брюер выдвинул гипотезу, касающуюся ключевых свойств распределённых систем, которую затем доказали в MIT, и с тех пор она называется теоремой Брюера или теоремой CAP (Consistency-Availability-Partition tolerance). Вольная формулировка:
В распределённой системе невозможно обеспечить одновременное выполнение всех трёх условий: корректности, доступности, устойчивости к сбоям узлов.
Что это за свойства.
Говорит о том, что система всегда выдаёт только логически непротивречивые ответы. То есть не бывает такого, что вы добавили в корзину товар, а после рефреша страницы его там не видите.
Означает, что сервис отвечает на запросы, а не выдаёт ошибки о том, что он недоступен.
Означает, что распределённая по кластеру система продолжает работать корректно при недоступности нескольких серверов кластера (кроме случая, когда упали все сервера, конечно).
Для лучшего осознания, вот три соответствующих примера того, что могут представлять собой системы без одного из этих свойств:
Шардированная СУБД, в которой данные лежат только на собственных серверах. В ней не может произойти неконсистентностей, и она доступна, если пользователь пишет новые данные или читает данные с доступного шарда. Однако она перестаёт отвечать на запросах данных с упавших шардов.
Система с несколькими мастер-базами, которые обновляются синхронно. Она всегда корректна, потому что транзакция отрабатывает, только если изменения удалось распространить по всем серверам БД. Она продолжает корректно работать по крайней мере на чтение, если один из серверов падает. А вот попытки записи будут обрываться или сильно задерживаться, пока система не убедится в своей консистентности.
Система с несколькими серверами, каждый из которых может принимать данные, но не обязуется в тот же момент распространять их по всему кластеру. Система переживает падения части серверов, но когда они входят в строй, они будут выдавать пользователям старые данные.
Важность того, что невозможность обеспечить все три свойства сразу, доказана математически, избавляет нас (тупых инженеро́в :-) ) от тщетных попыток создать некую идеальную систему, которая никогда-никогда не ломается. Вместо этого мы теперь можем делать привычный нам инженерный выбор двух из трёх.
Как в известном предложении клиенту: "быстро, дёшево, качественно — выбирайте любые два".
Причём, как в большинстве инженерных ситуаций, этот выбор не стоит как "всё или ничего". Система может располагаться где угодно в пределах этого воображаемого треугольника, быть "более" консистентной, "менее" доступной и "слегка" неустойчивой. В анти-идеале можно написать систему, у которой будет плохо со всеми тремя компонентами. Уверен, вы с такими встречались :-).
Одно из интересных практических следствий этой теоремы в том, что в последнее время многие бизнесы решили для себя, что совсем не обязательно упираться в принципы дизайна ACID, который ставит во главу угла Consistency, жертвуя двумя другими свойствами. Теперь у нас есть такая альтернатива, как BASE (известная также как "eventual consistency"), которую например очень любят и используют в Amazon. Там во главе угла стоит Availability.
А ещё один дядька — Гай Пардон — вообще предлагает инженерное решение, которое обходит проблему CAP. Правда, он немного читерствует (с математикой трудно спорить), говоря, что хоть и нельзя обеспечить все три свойства одновременно, можно построить систему так, чтобы она достигала желаемого постепенно.
Комментарии: 12 (особо ценных: 1)
1.02.10 01:46
Особо ценный комментарий
В своё время, когда общался с более опытным товарищем на эту тему, он поделился ссылкой. Надеюсь она и вам понравится:
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.
1.02.10 02:37
Еще одна интересная ссылка где CTO Amazon'а Werner Vogels объясняет принципы eventual consistency и то почему у них "во главе угла того самого треугольника" стоит Availability. За одну минуту downtime'а Amazon способен потерять около $3000. Так что выбор вполне очевиден.
http://www.allthingsdistributed.com/2008/12/eventually_consistent.html
1.02.10 03:05
Полезное напоминание о CAP. Спасибо за заметку.
1.02.10 14:29
Первый случай формально удоволетворяет свойству Partion tolerance, просто это не распределенная система.
2.02.10 12:40
Fulcrum, и правда. Поменял пример. Теперь подходит?
4.02.10 06:10
4.02.10 20:53
"Шардированная СУБД" - уникальный термин. Google выдает одну ссылку, угадайте куда.
http://tinyurl.com/ygdyzwo
5.02.10 15:14
%-))))
Я сначала не поверил...
6.02.10 22:04
Ваня, я не знаю почему,:-) но у меня словосочетание "в MIT доказали теорему" всегда вызывает воспоминания об одном классном тексте :-) Вот цитата из него:
Ходили по Массачусетскому Технологическому Институту (MIT) два несносных вундеркинда-кибернетика Карл Хьюитт и Терри Виноград. Несноснее Карла в MIT был разве, что Терри, и наоборот. И ничего, MIT и не такое видал. Ни один Нобелевский лауреат от этого не пострадал. Кстати, говорят, что, кроме MIT, Нобелевские лауреаты водятся иногда и в других местах. Короче, детские диалоги Карла и Терри были малопонятны окружающим лауреатам и кончились тем, что Карл (в 23 года) прославился созданием языка PLANNER, ставшего классикой ИИ, а Терри - один из основоположников в сфере ПОНИМАНИЯ естественного языка компьютером. Оба увлекались игрой в кубики.
Текст целиком: http://arbuz.uz/t_ii.html Но, я думаю, ты его читал :-)
6.02.10 23:24
Веришь ли, не читал :-)
24.02.10 00:59
А ссылочку на сие слабо дать?
P.S.Я Вам на слово верю есличо:)
24.02.10 18:10
Во втором абзаце поста: http://people.csail.mit.edu/sethg/pubs/BrewersConjecture-SigAct.pdf