Architecture Course Home / Основы распределённых систем

Модели согласованности

При изучении репликации я сознательно опустил модели согласованности. Настало время вернуться к этому вопросу.

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

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

Согласованность в конечном счёте (eventual consistency)

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

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

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

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

Факт возврата старого результата на запрос Боба является нарушением модели строгой слогласованноси, но прекрастно демонстрирует согласованность в конечном счёте.

Trade-Offs
ПреимуществаНедостатки
Производительность системы на запись. Не нужно согласовывать значение на всех репликах

На примере Алисы и Боба мы видим, что пользовательский опыт может страдать


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

Строгая согласованность

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

На рисунке ниже изображено как клиенты конкурентно просматривают и записывают реестр.

Каждая шкала — сделанный клиентом запрос; начало ее соответствует времени, когда клиент отправил запрос, а конец — когда получил ответ. Из-за различных задержек в сети клиент не знает точно, когда система обрабатывала его запрос. Он лишь знает, что это произошло где-то между отправкой запроса и получением ответа.

На рассмотренном рисунке значение регистра x первоначально равно 0. Клиент C выполняет запрос на запись с целью присвоить ему значение 1. Пока это происходит, клиенты A и B несколько раз опросили систему данных, чтобы узнать последнее значение. Какие ответы могут получить A и B для своих запросов на чтение?

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

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

При соблюдении правила хранометража история Алисы и Боба уже не повторится. Как только Алиса узнала счет матча, Боб не может получить более старое значение.

Реализация линеаризуемых систем

Поскольку линеаризуемость, в сущности, означает «вести себя так, как будто существует только одна копия данных и все операции над ней являются атомарными», самым простым ответом было бы действительно использовать только одну такую копию. Однако этот вариант не позволяет справляться с отказами: если узел, содержащий единственную копию данных, претерпел сбой, то данные будут потеряны или по крайней мере недоступны до тех пор, пока узел не заработает снова.

Наиболее распространенным методом обеспечения отказоустойчивости системы является использование репликации.

Репликация с одним ведущим узлом

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

Репликация с несколькими ведущими узлами

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

Репликация без ведущего узла

Не всегда линеаризуемая.

Наверное одна из интереснейших для меня тем. Я подробно не хотел расписывать эту тему, но неоднозначность понимания согласованности в Cassandra заставила меня подробно расписать эту тему.

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

image2023-10-5_14-39-36.png

Начальное значение x равно 0 и клиент, инициирующий запись, обновляет x до 1, отправив запрос записи на все три реплики (n = 3, w = 3). В это же время клиент А считывает данные по кворуму (r = 2) и видит новое значение 1 на одном из них. Кроме того, одновременно с записью клиент B считывает данные из другого кворума, также состоящего из двух узлов, и получает из обоих старое значение 0.

Условие кворума выполнено (w + r > n), но эта операция тем не менее нелинеаризуема: запрос клиента B начинается после запроса клиента A, но клиент B получает старое значение, а клиент A — новое.

Интересно отметить, что:

  1. кворумы можно линеаризовать за счет снижения производительности: операция чтения должна выполнить синхронное разрешение конфликта чтения, прежде чем возвращать результат приложению.
  2. однако в случае нескольких конкурентных операций записи с одним ключом линеаризуемость теряется из-за разрешения конфликтов методом «выигрывает последний».

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


Trade-Offs
ПреимуществаНедостатки
Такие системы понятнее для пользователя и разработчикаСущественным недостатком таких систем можно считать производительность и доступность




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

Теорема CAP

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

Пара компромиссов при работе с линеаризуемостью:

Таким образом, приложения, не требующие линеаризуемости, более устойчивы к неполадкам в сети. Это представление широко известно как теорема CAP, 

названная так Эриком Брюером в 2000г

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

Обычно CAP теорему изображают в виде треугольника к вершинах которого находятся: Consistency, Availability, Partition tolerance.

image

Грани CAP треугольника можно описать так:

Критика теоремы

Есть две важных проблемы которые опускает теорема, а конкретно:


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

Теорема PACELC

PACELC основана на модели CAP, но, помимо согласованности, доступности и устойчивости к разделению также включает временную задержку (L, Latency) и логическое исключение между сочетаниями этих понятий. Согласно PACELC, в случае сетевого разделения (P) в распределенной системе необходимо выбирать между доступностью (A) и согласованностью (C), как и в CAP- теореме, но в остальном (E, ELSE), даже при нормальной работе системы без разделения, нужно выбирать между задержкой (L) и согласованностью (C). В логическом выражении PACELC формулируют следующим образом: IF P -> (C or A), ELSE (C or L). Так PACELC расширяет и уточняет CAP-теорему, регламентируя необходимость поиска компромисса между временной задержкой и согласованностью данных в распределенных системах.

PACELC Theorem - GeeksforGeeks

Оригинал на wiki