В чём состоит дополнительное требование линейризуемости по сравнению с последовательной согласованностью?
Линейризуемость требует не только существования единого последовательного порядка операций, сохраняющего порядок операций каждого клиента, но и соблюдения реального времени: если одна операция завершилась до начала другой, первая должна идти раньше второй. Последовательная согласованность сохраняет порядок операций внутри каждого клиента, но не обязана учитывать временной порядок операций между разными клиентами.
Эти модели появились как способы формально описывать поведение конкурентных и распределённых объектов. Одной последовательности операций недостаточно: система может выдать результат, который формально согласован, но противоречит тому, что уже наблюдал клиент.
Линейризуемость делает объект похожим на обычный локальный объект с мгновенным выполнением каждой операции. Это упрощает рассуждение клиентов о состоянии системы, но обычно требует более строгой координации между узлами.
Предположим, клиент А записал значение и получил успешный ответ. После этого клиент Б начал чтение, но увидел старое значение. Если операции выполняются на разных репликах, такое поведение может быть допустимо для более слабой модели согласованности.
При линейризуемости оно недопустимо: завершившаяся запись должна находиться раньше начавшегося после неё чтения в едином порядке операций. При последовательной согласованности система может поместить чтение клиента Б перед записью клиента А, если это не нарушает порядок операций внутри самого клиента Б.
Линейризуемость требует, чтобы каждой операции можно было назначить единую точку между её началом и завершением. Все операции должны образовывать последовательный порядок, а операции, не перекрывающиеся во времени, обязаны сохранять реальный порядок.
Последовательная согласованность слабее. Для неё достаточно найти такой общий порядок, который сохраняет порядок операций каждого отдельного клиента. Временные отношения между операциями разных клиентов, если они не выражены через наблюдение или последующую операцию одного из клиентов, могут быть переставлены.
Практическое следствие: после успешной записи линейризуемое чтение через другую реплику обязано учитывать эту запись. Для этого применяют, например, чтение у узла, подтвердившего актуальное состояние, ожидание достижения нужной версии репликации или координацию через консенсус.
Цена такой гарантии — дополнительные задержки и снижение доступности при сетевом разделении. Если узел не может доказать, что располагает актуальным состоянием, он должен отклонить операцию или ждать восстановления связи; иначе он рискует нарушить линейризуемость.
Линейризуемость не означает, что транзакции автоматически сериализуемы во всех отношениях. Она описывает порядок отдельных операций или атомарных объектов, тогда как сериализуемость относится к эквивалентности выполнения набора транзакций некоторому последовательному выполнению.
Сервис управления доступом записывает отзыв разрешения пользователя в одну реплику, а сервис авторизации читает состояние с другой. При асинхронной репликации пользователь может сразу после отзыва продолжить доступ: чтение попало на реплику, ещё не получившую новую версию.
Рассматривались три варианта. Локальный кэш с коротким временем жизни имел низкую задержку, но не давал строгой гарантии. Ожидание репликации уменьшало вероятность ошибки, однако без проверки версии не гарантировало нужный порядок. Линейризуемое хранилище или чтение через узел, подтвердивший актуальную версию, давало требуемую безопасность, но увеличивало задержку и могло временно отказать во время разделения сети.
Для отзыва разрешений выбрали линейризуемую проверку, потому что ошибочный кратковременный доступ был опаснее недоступности операции. Некритичные данные профиля оставили на асинхронных репликах. В результате строгая гарантия применялась только к узкому пути авторизации, а не ко всем чтениям системы.
1. Обязана ли линейризуемость сохранять порядок двух перекрывающихся операций?
Нет. Если операции перекрываются по времени, линейризуемость допускает любой порядок, совместимый с их индивидуальными результатами. Требование реального времени обязательно только для операций, у которых первая завершилась до начала второй.
Например, две конкурентные записи могут получить порядок по решению лидера или по версии, назначенной хранилищем. Линейризуемость не требует выбирать порядок по времени начала и не запрещает одному из клиентов получить результат операции, начавшейся раньше, но завершившейся позже.
2. Достаточно ли читать с лидера, чтобы получить линейризуемость?
Нет. Чтение с текущего лидера помогает, но само по себе не доказывает, что узел действительно остаётся действующим лидером. После сетевого разделения старый лидер может продолжать обслуживать чтения или не знать, что его полномочия утрачены.
Нужны механизм проверки актуальности лидерства, подтверждение от кворума или другой способ установить, что операция находится в допустимом порядке относительно остальных операций. Иначе чтение может вернуть состояние, которое уже не соответствует линейризуемому порядку.
3. Связана ли линейризуемость с теоремой CAP?
Да, если под доступностью понимать продолжение успешного обслуживания запросов во время сетевого разделения. В присутствии разделения сети система не может одновременно гарантировать линейризуемость и принимать все конфликтующие операции на изолированных сторонах.
Обычно линейризуемая система продолжает работать только на стороне, располагающей необходимым кворумом, а другая сторона отклоняет или приостанавливает операции. Это не означает, что линейризуемость запрещает отказоустойчивость вообще: она ограничивает возможность сохранять строгую согласованность при одновременной доступности изолированных частей кластера.