Теорема CAP и репликация баз данных

1. ТиМДКС Теорема CAP лекция 5

Проф. каф. ИВТ СамГТУ д.т.н. С.Л.Гавлиевский
САМАРА
Весна 2025

2.

РЕПЛИКАЦИЯ
БАЗЫ ДАННЫХ
На рис. 1.5
показана ведущая
база данных с
несколькими
ведомыми.

3.

Теорема CAP
Теорема CAP гласит, что распределенная система может
обеспечивать не больше двух из следующих трех свойств:
согласованность,
доступность
и
устойчивость
к
секционированию. Дадим несколько определений.
Согласованность. Означает, что все клиенты одновременно
видят одни и те же данные, к какому бы узлу они ни
подключились.
Доступность. Означает, что любой клиент, запрашивающий
данные, получает ответ, даже если некоторые из узлов
недоступны.

4.

Устойчивость
к
секционированию.
Секционирование свидетельствует о нарушении
связи между двумя узлами. Устойчивость к
секционированию
означает,
что
система
продолжает работать вопреки нарушению
связи в сети.
Согласно теореме CAP, одним из этих свойств
необходимо пожертвовать, чтобы обеспечить
поддержку двух других .

5.

6.

Кузя выяснил причину: ночью, после запуска рекламной
кампании, на сайт устремились тысячи новых пользователей и
база данных с фотографиями котиков не выдержала и “упала” от
возросшей нагрузки.
Кузя и сайт с котиками
Отказала база данных, загрузить фото котиков или
посмотреть альбомы стало невозможно

7.

Для решения проблемы,
• Кузя добавил еще один сервер и сделал так, что теперь за работу отвечали 2 экземпляра
базы данных.
• Так же, он настроил их таким образом, что оба сервера и записывают и показывают котиков.
• При этом базы постоянно синхронизируются друг с другом, для того чтобы в обеих
базах были одинаковые данные.
• Пользователям теперь показываются только те фотографии, которые помечены как
“синхронизированные”.
А так как базы теперь 2 - этого с головой хватает на то, чтобы справляться с нагрузкой.
Кузя распределил хранилище системы на два узла
Отказоустойчивость системы возросла, но важно тут то, что при этом у нее появилось
свойство: система стала Разделяемой (Partitioning tolerance).

8.

Один узел хранилища отказал, теперь система отдает только те данные, которые были
синхронизированы на момент отказа
Единственная база данных продолжала получать и записывать фотографии,
но вот отдавала пользователям только те, которые уже были помечены как
“синхронизированные” на момент аварии.

9.

Чтобы обе базы могли работать независимо друг от друга, добавим им еще
одно свойств: Доступность (Availability).
Теперь, если узлы определят что произошла авария, будут отдавать в том
числе несинхронизированные данные

10.

Нарушение связи между узлами распределенного хранилища
привело к тому, что разные пользователи начали получать разные
альбомы с котиками

11.

12.

13.

14.

15.

16.

17.

18.

CAP (Consistency, Availability, Partition Tolerance
доступность, устойчивость к секционированию»).
— «согласованность,
Сейчас хранилища типа «ключ–значение» классифицируются в зависимости от
того, какие две характеристики CAP они поддерживают:
Системы CP (согласованность и устойчивость к секционированию).
Жертвуют доступностью.
Системы AP (доступность и устойчивость к секционированию).
Жертвуют согласованностью.
Системы CA (согласованность и доступность). Жертвуют устойчивостью к
секционированию. Поскольку сетевые сбои неизбежны, распределенные
системы должны справляться с разделением сети. В связи с этим системы
CA не существуют в реальных условиях.

19.

20.

Hассмотрим несколько конкретных примеров.
В распределенных системах данные обычно реплицируются
больше одного раза.
Предположим, что у нас есть три узла-реплики: n1, n2 и n3, как
показано на рис. 6.2.

21.

Идеальная ситуация
В идеальном мире секционирование сети не происходит. Данные,
записанные в n1, автоматически реплицируются в n2 и n3. Этим
достигается как согласованность, так и доступность.

22.

Реальные распределенные системы
В распределенной системе разделение неизбежно, и, когда оно
происходит, мы должны сделать выбор между согласованностью
и доступностью.
На рис. 6.3 узел n3 отказывает и больше не может
взаимодействовать с n1 и n2. Данные, которые клиенты
записывают в n1 или n2, не могут дойти до n3.
Если же кто-то запишет данные в n3 и они не успеют дойти до n1
и n2, это будет означать, что содержимое n1 и n2 неактуально.

23.

CAP (Consistency,
Availability,
Partition Tolerance —
«согласованность,
доступность,
устойчивость
к секционированию»)
Если мы предпочтем согласованность вместо доступности
(система CP), нам придется заблокировать все операции записи
на узлах n1 и n2, чтобы избежать рассинхронизации данных между
этими тремя серверами. Этим мы сделаем систему недоступной.

24.

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

25.

Если же мы отдадим предпочтение доступности перед
согласованностью (система AP), система продолжит
принимать операции чтения, несмотря на то что она
может вернуть устаревшие данные.
Что касается операций записи, то они останутся
доступными на узлах n1 и n2, а после устранения сетевых
неполадок данные будут синхронизированы с n3.

26.

Консистентность #
Консистентность (Consistency) - одно из трех свойств,
которое рассматривается в CAP теореме.
Оно определяет, что каждый узел в распределенной системе
должен иметь доступ к одному и тому же состоянию
данных в любой момент времени.
Если система обладает свойством консистентности, то
любые изменения данных, которые происходят в одном
узле, должны быть немедленно доступны во всех
остальных узлах системы.

27.

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

28.

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

29.

Доступность #
Доступность (Availability) - одно из трех свойств, рассматриваемых в CAP
теореме.
Это свойство определяет, что каждый запрос, отправленный к системе, должен
получить ответ, даже если произошел сбой в системе.
Если система обладает свойством доступности, то каждый узел должен быть
доступен для обработки запросов в любое время, даже если другие узлы системы
недоступны.
Одним из примеров систем, которые требуют высокой степени доступности,
являются системы поиска в Интернете, такие как Google. В таких системах
отсутствие доступности может привести к потере клиентов и доходов.

30.

Другой пример - системы управления транспортом,
которые должны быть доступны для обработки запросов в
любое время, чтобы предотвратить возможные аварии и
несчастные случаи.
С другой стороны, поддержание высокой степени доступности
может привести к ухудшению консистентности и
устойчивости к разделению системы. Если система не
имеет возможности поддерживать все узлы в едином
состоянии,
то
могут
возникнуть
проблемы
с
консистентностью.
Таким образом, доступность является одним из важнейших
свойств,
которые
нужно
учитывать
при
разработке
распределенных
систем,
но
при
этом
она
может

31.

Устойчивость к разделению #
Устойчивость к разделению (Partition Tolerance) - одно из трех свойств,
рассматриваемых в CAP теореме.
Оно определяет, что система должна продолжать функционировать, даже если
происходит разделение сети на две или более частей.
Если система обладает свойством устойчивости к разделению, то каждый узел
должен продолжать работать независимо от других узлов, даже если эти узлы
временно не могут связаться друг с другом.
Одним из примеров систем, которые требуют высокой степени устойчивости к
разделению, являются системы авиационного контроля и управления
полетами. В таких системах могут возникнуть различные проблемы, такие как
потеря связи с самолетом, но система должна продолжать работать, чтобы
обеспечить безопасность пассажиров и экипажа.

32.

С другой стороны, поддержание высокой степени устойчивости к
разделению может привести к ухудшению консистентности и
доступности.
Если система не может обеспечить коммуникацию между всеми
узлами, то могут возникнуть проблемы с консистентностью данных и
доступностью сервисов.
Таким образом, устойчивость к разделению является одним из
важнейших свойств, которые нужно учитывать при разработке
распределенных систем, но при этом она может конфликтовать с
другими свойствами, такими как консистентность и доступность.

33.

Следствие 1 #
Одним из основных следствий CAP теоремы является то, что
распределенная система может обеспечить только два из трех свойств
- консистентность (Consistency), доступность (Availability) и
устойчивость к разделению (Partition Tolerance).
Это означает, что при разработке распределенных систем необходимо
выбрать, какие свойства являются для данной системы наиболее
важными.

34.

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

35.

Следствие 2 #
Другим следствием CAP теоремы является то, что при проектировании
распределенных систем необходимо учитывать множество факторов, включая
пропускную способность сети, нагрузку на узлы, объем данных и многое другое.
Кроме того, необходимо принимать во внимание возможные сбои в системе и
различные виды атак на безопасность.
Для обеспечения требуемого уровня производительности, надежности и
безопасности распределенной системы могут использоваться различные подходы,
такие как репликация данных, шардинг, резервирование ресурсов и многое другое.
Однако каждый из этих подходов имеет свои преимущества и недостатки, и их
необходимо выбирать с учетом требований к консистентности, доступности и
устойчивости к разделению.

36.

Кроме того, CAP теорема показывает, что в реальном мире не существует
универсального решения для всех распределенных систем.
Вместо этого разработчики должны анализировать требования каждой конкретной
системы и выбирать наиболее подходящие технологии и методы, чтобы обеспечить
наилучшую производительность, надежность и безопасность.
Наконец, CAP теорема является основой для многих современных распределенных
систем и технологий, таких как Apache Cassandra, Amazon DynamoDB, MongoDB и
многие другие.
Эти системы используют различные подходы для обеспечения требуемого уровня
консистентности, доступности и устойчивости к разделению в зависимости от
конкретных требований к системе.

37.

Доступность и Консистентность (CA) #
Пересечение доступности (Availability) и консистентности
(Consistency) в CAP теореме является одним из наиболее
важных аспектов распределенных систем.
Оно относится к тому, что в некоторых случаях невозможно
обеспечить одновременно идеальную доступность и
идеальную консистентность в распределенной системе.

38.

Для обеспечения идеальной доступности в распределенной системе необходимо,
чтобы каждый запрос был обработан успешно, без задержек и сбоев.
Это означает, что каждый узел должен быть доступен для обработки запросов в
любое время.
В то же время, для обеспечения идеальной консистентности необходимо, чтобы
все узлы в системе имели одинаковое представление о состоянии данных в
системе.
Это означает, что если произошло изменение данных, оно должно быть сразу же
доступно для всех узлов системы.
Однако, чтобы обеспечить идеальную доступность, узлы системы должны
работать независимо друг от друга, что может приводить к отсутствию
консистентности данных.

39.

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

40.

Доступность и Устойчивость к разделению (AP) #
Пересечение доступности (Availability) и устойчивости к разделению (Partition
Tolerance) в CAP теореме также имеет важное значение для распределенных
систем.
Доступность означает, что каждый запрос к системе должен быть обработан
успешно без задержек и сбоев, вне зависимости от возможных сбоев узлов в
системе.
Устойчивость к разделению означает, что система должна продолжать работу при
разделении сети на несколько частей.
В случае разделения сети на несколько частей, узлы в каждой части могут
продолжать работу независимо друг от друга. Однако, в этом случае возникает
риск того, что данные в каждой части сети могут не синхронизироваться друг
с другом. Это может привести к тому, что у разных узлов будет разное
представление о состоянии данных в системе.

41.

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

42.

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

43.

Консистентность и Устойчивость к разделению (CP) #
Пересечение консистентности (Consistency) и устойчивости к
разделению (Partition Tolerance) в CAP теореме означает, что
распределенная система должна сохранять консистентность данных
при возможном разделении сети на несколько частей.
Консистентность данных означает, что все узлы в системе должны
иметь одинаковое представление о текущем состоянии данных в
системе.
При этом, любое изменение данных должно быть видимо для всех
узлов системы. доступности системы, производительности и
масштабируемости.

44.

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

45.

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

46.

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