Доказательство теоремы CAP — теперь с картинками!
Теорема CAP гласит, что распределенная система может отвечать только двум требованиям из трех: согласованная, доступная и устойчивая к фрагментации.
Почему так? Ответы в
коротком иллюстрированном гайде по ссылке — ну, или у нас в посте, но без иллюстраций. Гайд не углубляется в тонкости, но знакомит с основными понятиями.
🔜 Представим простую распределенную систему — два сервера, которые обмениваются данными друг с другом и с внешним клиентом. На них хранятся данные о значении некой переменной V.
У этой системы могут быть следующие свойства:
🔵 Согласованность (Consistency) — если клиент отправляет запись V = 1 на один сервер, то второй при чтении должен вернуть такое же значение. Если на одном сервере V = 1, а на втором все еще V = 0, то система не согласована.
🔵 Доступность (Availability) — оба сервера, если только никто не пролил на один из них чай, отвечают на запросы клиента на запись и чтение данных.
🔵 Устойчивость к фрагментации (Partition tolerance) — система продолжает работу, даже если какое-то количество сообщений от одного сервера не доходят до второго.
🔜 Наконец-то подходим к доказательству.
🔵 Если система устойчива к фрагментации и доступна, она не может гарантировать согласованность — рано или поздно возникнет ситуация, когда клиент отправит запись на один сервер, а до второго она не дойдет. Тогда один выдаст V = 1, а второй V = 0.
🔵 Чтобы обеспечить устойчивость и согласованность, системе придется пожертвовать доступностью — то есть отказаться вносить данные, если она не может гарантировать, что все ее узлы получат обновление.
🔵 Практически в любой реальной распределенной системе неизбежны потери данных между нодами. При этом, она, скорее всего, не упадет — то есть она будет устойчива к фрагментации. А если она устойчива к фрагментации, то мы возвращаемся к пункту 1.
🔜 Все так просто?
На самом деле нет. К каждому пункту из поста можно добавить звездочку и написать дополнение, которое все усложняет, но это уже не влезет в пост.