Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services

Я уже рассказывал про знаменитую CAP теорему за авторством Eric Brewer. А сегодня я расскажу про whitepaper 2002 года от Seth Gilbert и Nancy Lynch, в котором гипотеза стала теоремой. Сама гипотеза для доказательства звучит так

It is impossible for a web service to provide the following three guarantees: consistency, availability, partition-tolerance

Все эти свойства желательны в реальных системах. Но для того, чтобы доказать это утверждение, требуется для начала формализовать все три свойства

1) Начать стоит с consistency, где авторы идут в сторону atomic data objects или линеаризуемой консистентности (linearizable consistency)

Under this consistency guarantee, there must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time.

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

2) Второй характеристикой является availability, где для непрерывной доступности каждый запрос, попавший на несбойную ноду системы должен получить свой ответ. Таким образом любой алгоритм для генерации ответа сервисов должен оканчиваться в конечном счете (eventually terminate). Интересно, что это слабое определение доступности, так как нет верхней границы на время ответа - это позволяет unbounded computation. Но если рассматривать это с позиции устойчивости к разделению, то это может рассматриваться как сильное определение доступности - даже если происходят сбои в сети, каждый запрос должен завершиться.

3) Для моделирования partition-tolerance авторы предлагают считать, что в сети может теряться произвольное количество сообщений, что отправляются от одной ноде к другой. А значит мы можем моделировать любой паттерн потерь

When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost. (And any pattern of message loss can be modeled as a temporary partition separating the communicating nodes at the exact instant the message is lost.)

Дальше авторы переходят к доказательствам

1) Начнем сначала с асинхронных систем

Theorem 1 It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties:
• Availability
• Atomic consistency
in all fair executions (including those in which messages are lost).

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

2) В реальном мире у нас используются не полностью асинхронные системы, а частично синхронные. В них у нод есть свои часы, которые позволяют замерять время и использовать таймауты. Но даже в более мощном сетапе мы получаем похожий результат

Theorem 2 It is impossible in the partially synchronous network model to
implement a read/write data object that guarantees the following properties:
• Availability
• Atomic consistency
in all executions (even those in which messages are lost).

Доказательство тут похоже на предыдущее как две капли воды:)

Оставшаяся часть white paper посвящена Delayed-t consistency в частично синхронных системах, про которую мы тут говорить не будем.

А в следующем посте поговорим про теорему PACELC.

#Software #Architecture #DistributedSystems #SystemDesign