Теорема СAP (consistency, availability, partition tolerance)

Понятие Базы Данных

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

1) Atomicity – атомарность. Подразумевает, что транзакция либо полностью выполняется, либо полностью не выполняется.

T: A, B –> A’, B’. Состояния A’,B, A,B’ невозможны.

2) Consistency – целостность, связность. Сохранение целостности данных. Если данные между собой связаны, то связи не должны быть нарушены. Изменение объектов А и В может означать неявное изменение объектов С или каких-нибудь еще объектов.

T: A, B –> A’, B’, C’.

Пример: в социальной сети у пользователя есть список групп, в которых он состоит (С). Если пользователь добавлен в группу, то это означает, что в списке пользователей группы должна возникнуть обратная ссылка на пользователя (изменится С).

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

T1: A,B –> A’,B’

T2: A,B –> A’’,B’’

Состояния A’,B’’ и A’’, B’ невозможны.

4) Durability – сохранность, постоянство. Если пользователь получил подтверждение завершения транзакции, то он должен получить гарантии того, что транзакционные данные не потеряны.

Если вернулась ошибка, то возможны 2 варианта: 1) транзакция выполнена; 2) транзакция не выполнена. Но следует исходить из того, что транзакция не выполнена.

В распределенной системе невозможно обеспечить согласованность и готовность одновременно с устойчивостью системы к разделению.

Пусть распределенная система состоит из двух узлов. Транзакция Т1 охватывает объект А на узле 1, объект В на узле 2 и переводит состояния объектов в А’ и B’.

T1: A, B –> A’, B’.

Согласованность подразумевает, что если транзакция Т1 выполняет действия, то транзакция Т2 никогда не будет работать с данными А’ и В.

Устойчивость (терпимость) системы к разделению – поведение системы, при условии, что связь между узлами может временно пропасть, временно один из узлов может выйти из строя.

В распределенной системе нет узкого места – единой точки напряжения.

Если происходит транзакция Т1, которая обновляет объект А на узле 1 и В на узле 2, а связь между узлами потеряна, то транзакция Т1 может сохранить объект на узле 1, но не может сохранить объект на узле 2, т.е. готовность системы не обеспечена при разделении. Это означает, что для того чтобы обеспечить готовность, нужно обеспечить избыточность.

Пусть узлы 1 и 2 используют хранение данных, дублируя данные друг друга, с целью обеспечения готовности. Тогда если между узлами 1 и 2 пропала связь, то изменения объекта А и В обозначают изменения объекта А на одном из узлов и объекта В на одном из узлов.

Обеспечивается репликация – копирование, перенос данных. В этом случае если мы разделили систему, то транзакция, которая выполняет работу с объектом, сможет ее выполнить, но если система будет разделена, то изменения произойдут только на узле, к которому обратился пользователь. Однако в то же время другой пользователь может обратиться к другому узлу с транзакцией Т2 при разделенной системе.

Проблема: система обеспечивает высокую готовность за счет избыточности данных (узлы дублируют друг друга) и даже при разделении системы обеспечивается возможность выполнения некоторого действия (чтения, изменения), но возникает дилемма: если вы изменили данные в транзакции Т1 и Т2, пока система была разделена, когда связь будет восстановлена, в какое состояние должна перейти система? Предположим, что было решено отдать приоритет второй транзакции. Возникает возможность, что пока данные не перешли в состояние Т2, могут быть прочтены разные значения А и В (А’, B’, A’’, B’’). Худший вариант – когда клиент прочтет новые данные (A’’, B’’), а затем – старые (А’, B’), что приведет к потере хронологии значений. Если необходимо лишить пользователя возможности случайно видеть такие результаты, то на некоторое время необходимо пожертвовать готовностью системы, т.е. пока система разделена, запросы пользователя не должны обрабатываться.

Теорема показывает, что при разделении системы пропадает либо согласованность данных, либо их готовность.

CAP–теорема была математически доказана. Но она не запрещает создание распределенных систем, устойчивых к разделению, которые обеспечивают высокий уровень готовности и согласованности данных. Теорема является ограниченной, т.к.:

1) она доказана для очень частного случая разделения системы;

2) система живет во времени, и существуют длительности интервалов, когда в системе обеспечивается либо готовность, либо согласованность. Если эти интервалы достаточно малы, то достаточно отложить выдачу ответа до следующего состояния готовности или согласованности.

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

Решение проблемы согласованности для БД привело к созданию систем БД, в которых не обеспечивается распределенная транзакционность, но обеспечивается высокая готовность (хранилище пар вида «ключ – значение»).

Дата добавления: 2014-11-16