пятница, 20 января 2012 г.

Несколько мыслей про CAP теорему

Навеяно обсуждением на Хабре (Недопонимание CAP-теоремы) и постами Ивана Сагалаева в его блоге - раздва. Я решил вынести мои комментарии в отдельной пост, чтобы они воспринимались более целостно. К тому же, я хотел бы обобщить свое понимание некоторых аспектов этой теоремы своими словами, максимально просто и доступно.

Прежде всего, что такое CAP-теорема - читать тут. Если совсем вкратце, одним предложением - "В (идеальной) распределенной системе можно обеспечить одновременно выполнение только двух из следующих трех свойств - Consistency, Availability, и Partition tolerance", откуда, собственно,  и название теоремы - CAP.

Под Consistency в этой теореме понимается целостность данных, так, как они видимы для пользователей системы. Т.е. не должно быть такого, что пользователь А логинится и видит одно, а пользователь Б, смотрящиq на те же (логически) данные в тот же момент времени - видит другое. Здесь важный момент - что такое логические данные. Допустим, оба пользователя смотрят на статус некоторого третьего пользователя С. Поскольку в распределенной системе для обеспечения сохранности данных при выходе из строя узлов кусочки данных (chunks) обычно хранятся в нескольких копиях на разных узлах системы, очевидно, что пользователь А может смотреть на одну копию данных, где хранится статус С, а пользователь Б может смотреть на другую копию (например, если это пользователи из разных регионов, и в системе присутствует load balancing по примерному географическому адресу, который установливается на основе IP адреса из http-запроса). Тогда, consistency требует, чтобы в любой момент времени, если пользователи А и Б смотрят на статус С, они видели один и тот же статус.

Возникает вопрос - а как обеспечить consistency? Очевидно, существует два базовых способа - это синхронная и асинхронная репликация данных при каждом их изменении.

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

Дальше первая фаза - мастер-нод отдает обоим нодам с данными команду применить обновление, но не коммитить транзакцию, и сообщить мастер-ноду, как только все будет готово и останется только сделать коммит (понятие "транзакция готова, останется только сделать коммит", само по себе может быть непростым.. Например, для СУБД Oracle транзакция считается закоммиченной, когда сгенерирован SCN (уникальный system change number, и соответствующий redo-log файл с информацией, необходимой для наката транзакции с нуля, сброшен на диск).

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

Итак, очевидно, синхронная репликация позволяет нам добиться Consistency, так как гарантируется, что данные либо обновляются во всех копиях, либо ни в одной. И вот тут в игру вступает Availability. Чем больше у нас копий данных, чем больше серверов, тем дольше будет занимать каждая операция обновления (из-за издержек на проведение двухфазных транзакций).

Все становится совсем плохо, если вспомнить о Partition Tolerance. PT требует, чтобы система могла функционировать тогда, когда нарушается сетевое соединение между отдельными узлами (группами узлов) кластера, либо когда произвольные узлы уходят в даун.

Что, если у нас пропало соединение между двумя узлами, на которых лежат порции данных, причем пропало так, что мастер нод через который работает пользователь А может достучаться только до нода 1, а мастер нод через который работает пользователь Б, может достучаться только до нода 2? Например, пользователь А, нод 1, и один из мастер нодов в Украине, пользователь Б, нод 2 и соотв. мастер нод в Беларуси, и магистральное соединение нарушилось.  Что произойдет, когда пользователи А и Б хотят прочитать статус С? Они могут это сделать, если пользователь А все еще имеет доступ к ноду 1, а пользователь Б - к ноду 2. Но вот обновить свой статус пользователь С теперь не сможет (если мы хотим обеспечить целостность данных). В самом деле, любое обновление повиснет на ожидании ответа от нода с протиположной стороны.

Каким образом мы можем позволить пользователю С обновлять свой статус в таких условиях? Очевидно, используя асинхронную репликацию, которая подразумевает т.н. Eventual Consistency. Т.е. когда пользователь С пытается изменить свой статус, мы меняем данные на ноде 1, а ноду 2, до которого достучаться не можем, посылаем каким-либо образом асинхронное сообщение о том, что статус надо бы изменить. До  момента восстановления соединения, пользователь А будет видеть свежие изменение, а пользователь Б, которому, предположим, доступен только узел 2 - будет временно видеть старые данные, что, согласитесь, часто лучше чем ничего.

Когда соединение до нода 2 восстановится, нод 2 обновит свои данные с нода 1, и информация о статусе пользователя С снова будет консистентной во всей системе. Единственная проблема - что если в промежутке времени после потери соединения между нодами 1 и 2, на обоих были произведены некоторые изменения? После восстановления соединения нам надо будет решить, как нам смержить данные в единую версию, которая и будет считатьcя новой консистентной версией данных в системе. Как именно делать мерж - зависит от семантики приложения. В случае со статусом пользователя, можно тупо брать брать версию с самым поздним timestamp-ом. В каких-то случаях (для текстовых файлов в распределенных системах контоля версий или чем-то подобном) можно делать трехсторонний merge (три версии - предыдущая консистентная версия до потери соединения, сохраненная где-либо, версия на ноде 1, версия на ноде 2).

Итак, считая, что Partition Tolerance - требование для распределенной системы, работающей в несовершенном реальном мире, необходимое, у нас есть выбор между двумя типами систем - такими, в которых за основу взято Consistency (я думаю, в качестве примера можно привести банковские и разнообразные платежные системы, там, где нет сверхвысоких требований к latency), и системами, в которых во главе угла стоит Availability (некоторые интернет-мазазины, например, всемирно известный Amazon), социальные сети и пр.

1 комментарий: