Что такое двухфазный коммит

Согласованность данных в высоконагруженных системах

Проблематика

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

Классический пример, объясняющий, что такое согласованность данных – операция перевода денежных средств с одного счёта на другой. В момент, когда операция изменения баланса одного счёта уже выполнилась, а другого – ещё не успела, может произойти сбой. Тогда с одного счёта средства будут списаны, а на другой не поступят. Такое состояние данных системы называется рассогласованным, и, пожалуй, нет необходимости объяснять, к каким последствиям это может привести. Реляционные СУБД предоставляют механизм транзакций, гарантирующий согласованность данных в любой момент времени. Транзакция – это конечный набор операций, который переводит одно согласованное состояние в другое согласованное состояние. В случае ошибки на любом шаге СУБД отменяет все выполненные ранее операции и возвращает данные к первоначальному согласованному состоянию. Иными словами – либо выполнятся все операции, либо ни одной.

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

Решение проблемы согласованности данных

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

Простой протокол для фиксации глобальных транзакций — двухфазный коммит (2PC). Узел, выполняющий транзакцию, считается координатором. На подготовительной фазе (prepare) координатор сообщает остальным узлам о фиксации транзакции и дожидается от них подтверждения, что они готовы выполнить фиксацию. Если хотя бы один узел не готов — транзакция обрывается. На фазе фиксации (commit) координатор сообщает всем узлам о решении зафиксировать транзакцию. При получении от всех подтверждения, что все ок, координатор тоже фиксирует транзакцию.

Рисунок 1 – Общая схема двухфазного коммита

Этот протокол позволяет обойтись минимумом сообщений, но не устойчив к сбоям. Например, при отказе координатора после фазы prepare, остальные узлы не имеют информации о том, должна ли транзакция быть зафиксирована или отменена (им придется ждать устранения сбоя). Ещё один серьёзный недостаток 2PC (и других протоколов распределённых транзакций, например 3PC) – при росте количества узлов кластера производительность двухфазных коммитов падает.

Рисунок 2 – Зависимость скорости выполнения двухвазного коммита от количества серверов в кластере СУБД

Кроме того, подход распределённых транзакций накладывает ограничение: все модули системы должны использовать одну и туже СУБД, что не всегда удобно.

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

В обычных транзакциях, а также в двухфазных коммитах, все операции контролируются механизмом транзакций (с использованием блокировок), и это делается с целью обеспечить возможность откатить любую операцию (пессимистический подход – любую операцию считаем потенциально вызывающей сбой). Это является узким местом системы. Альтернативный вариант – так называемый оптимистический подход: считаем, что большинство операций завершаются успешно. Дополнительные же действия производим уже по факту произошедшего сбоя. Т.е. уменьшаем издержки для большинства операций, что приводит к повышению производительности.

Что такое Saga (Сага) и как она работает

Альтернативой транзакциям для микросервисной архитектуры является Saga. Saga (сага) представляет собой набор шагов, выполняемых различными модулями системы (сервисами); так же требуется сервис саги, отвечающий за операцию (бизнес-транзакцию) в целом. Шаги связаны через граф событий. После выполнения саги система должна перейти из одного согласованного состояния в другое (в случае успешного выполнения), или вернутся к предыдущему согласованному состоянию (в случае отмены).

Как реализовать такой возврат или откат бизнес-транзакции? Для этого в сагах используется механизм отменяемости шагов (компенсирующие действия). Например, один из шагов был выполнен успешно (допустим в таблицу базы данных пользователей была добавлена запись), но на одном из следующих шагов произошёл сбой, и всю сагу следует отменить. Тогда этому же сервису поступает команда – отменить действие. Но в СУБД сервиса локальная транзакция уже завершена, запись пользователя добавлена. Тогда для возврата к предыдущему состоянию сервис должен выполнить компенсирующее действие (в нашем примере – удалить запись). Отменяемость шагов позволяет реализовать в рамках саги атомарность (Atomicity) – «всё или ничего» — все шаги выполняются или компенсируются.

Рисунок 3 – Механизм работы Saga и природа компенсирующего действия

На рисунке 3 шаги саги обозначены как T1. T4, компенсирующие действия: C1. C4.
Саги поддерживают идемпотентность шагов (действие, многократное повторение которого эквивалентно однократному). Подход саг обеспечивает возможность повторить любой шаг (например, если не получили отклик об успешном завершении). Так же идемпотентность позволяет восстановить состояние при потере данных на каком-либо узле (сбой и восстановление). При выполнении шага каждый сервис должен определять (по ключу идемпотентности) выполнял он уже этот шаг, или нет (если нет – выполнить, иначе — пропустить). Для компенсирующих действий тоже возможно добавление ключей идемпотентности и повторы операций (обеспечение персистентности/устойчивости).

Резюме

Из четырёх требований к транзакционной системе ACID (атомарность, согласованность, изолированность, устойчивость) механизм саг позволяет реализовать три – все, кроме изолированности. Отсутствие изолированности может приводить к аномалиям («грязные чтения», «неповторяющиеся чтения», перезапись изменений между различными бизнес-транзакциями и т.д.). Для преодоления подобных ситуаций требуется использовать дополнительные механизмы, например версионность изменяемых объектов.

Саги позволяют решить следующие задачи:

Область применения и примеры применения

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

Наша компания имеет опыт разработки системы учёта для крупного предприятия, которая была рассчитана на несколько десятков пользователей и все данные хранились в одной реляционной СУБД. Проблема возникла при реализации автоматического расчёта запланированных работ: в некоторых случаях расчёты были очень большими и требовали вставки миллионов записей в таблицы СУБД, что значительно нагружало СУБД и замедляло работу всей системы.

Было найдено решение — вынести логику расчёта работ в отдельный сервис со своей отдельной СУБД для хранения самих работ и сопутствующих объектов. Согласованность данных обеспечивалась при помощи саги. Если при расчёте происходил сбой, то в основной модуль приложения поступала команда отменить логическую операцию расчёта.

Источник

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

СОДЕРЖАНИЕ

Предположения

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

Базовый алгоритм

Фаза запроса фиксации (или голосования)

Фаза фиксации (или завершения)

Успех

Если координатор получил сообщение о согласии от всех участников на этапе запроса фиксации:

Отказ

Если какой-либо участник голосует против во время фазы запроса фиксации (или истекает тайм-аут координатора):

Поток сообщений

Знак * рядом с типом записи означает, что запись принудительно помещена в стабильное хранилище.

Недостатки

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

Реализация протокола двухфазной фиксации

Общая архитектура

Во многих случаях протокол 2PC распространяется в компьютерной сети. Его легко распределить путем реализации нескольких выделенных компонентов 2PC, похожих друг на друга, обычно называемых менеджерами транзакций (TM; также называемыми агентами 2PC или мониторами обработки транзакций), которые выполняют выполнение протокола для каждой транзакции (например, The Open Group » s X / Открыть XA ). В базах данных, участвующих в распределенной транзакции, участники, как координатор, так и участники, регистрируются для закрытия TM (обычно находящихся на соответствующих узлах сети, что и участники) для завершения этой транзакции с использованием 2PC. Каждая распределенная транзакция имеет специальный набор TM, TM, в которых регистрируются участники транзакции. Лидер, TM координатора, существует для каждой транзакции, чтобы координировать 2PC для нее, обычно TM базы данных координатора. Однако роль координатора может быть передана другому TM по соображениям производительности или надежности. Вместо того, чтобы обмениваться сообщениями 2PC между собой, участники обмениваются сообщениями со своими соответствующими TM. Соответствующие TM взаимодействуют между собой, чтобы выполнить указанную выше схему протокола 2PC, «представляющую» соответствующих участников для завершения этой транзакции. В этой архитектуре протокол полностью распределен (не требует какого-либо компонента центральной обработки или структуры данных) и эффективно масштабируется с увеличением количества сетевых узлов (размера сети).

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

Оптимизация протокола

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

Предполагаемое прерывание и предполагаемое совершение

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

Протокол двухфазной фиксации дерева

Источник

Calvin: обеспечение принципов ACID для высоконагруженных распределенных систем

Недавно в хабе Serverless вышла статья Бессерверная альтернатива традиционным базам данных от @olalala. В комментариях к статье пользователи просили рассказать о Calvin — подходе, который используется внутри Yandex Database. Нам понравилась эта идея и я решил коротенько рассказать об этом.

Calvin — это подход к фиксации транзакций, который позволяет сохранить принципы ACID в распределенных системах без потери производительности. Впервые он был упомянут в работе Йельского университета в 2012 году. Calvin хорошо вписывается в целый класс бессерверных СУБД. Мы знаем как минимум две системы, в которых он используется: Yandex Database и FaunaDB, но, возможно, есть и другие.

Двухфазный коммит — основная проблема традиционных распределенных СУБД

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

Координатор отправляет транзакцию на каждый узел, а затем ждет подтверждения, что выполнение транзакции возможно.

Если все узлы выполнили транзакцию, координатор отправляет им команду зафиксировать изменения, то есть сделать их постоянными.

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

Схема двухфазного коммита на примере двух узлов

С точки зрения распределенных систем, в таком подходе есть две большие проблемы:

Очень много «общения» между координатором и узлами. Распределенные СУБД, как правило, находятся в нескольких ЦОД, которые расположены в разных регионах или странах. Поэтому, чем больше узлы «общаются» между собой, тем больше сетевые задержки.

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

Тут можно вспомнить про системы NoSQL, которые решают проблему низкой производительности, но жертвуют всеми или многими принципами ACID.

Принципы Calvin и детерминированные базы данных

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

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

Соглашение о том, какие транзакции и в каком порядке выполнять. Это своего рода глобальная очередь, которая формируется до того, как узлы начнут обрабатывать транзакции.

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

Но что будет, если во время выполнения транзакции один из узлов не сможет зафиксировать изменения? Это может произойти по следующим причинам:

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

Детерминированные причины. Проблемы в логике транзакции, например повтор первичного ключа, нарушение ссылочной целостности или уникальности.

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

В случае с Calvin и детерминированными системами, недетерминированное событие не отменяет транзакцию целиком. Все узлы, кроме отказавшего, выполняют команды по утвержденному плану. А проблемный узел после восстановления «накатит» изменения по своему же плану или по логам другого узла.

Архитектура Calvin

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

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

Уровень планирования (scheduler). Система использует детерминированный протокол блокировки для управления выполнением транзакции. Это гарантирует, что транзакции будут выполнены строго в том порядке, в котором они были запланированы на уровне упорядочивания.

Уровень хранения (storage). Система обрабатывает всю физическую структуру данных. К Calvin можно подключить любой механизм хранения с базовым интерфейсом CRUD.

Высокоуровневая схема архитектуры Calvin. Источник: clck.ru/XSwPC

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

Параллелизм, блокировки и ожидание диска

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

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

Чтобы избавиться от этой задержки, Calvin старается убедиться, что транзакции не удерживают блокировки и не ожидают дискового ввода-вывода. Для этого каждый раз, когда sequencer получает запрос на транзакцию, которая может вызвать остановку диска, он:

создает искусственную задержку перед отправкой запроса на уровень планирования;

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

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

В заключение

В заключение стоит добавить, что подход Calvin хорошо вписывается в распределенные высоконагруженные системы. Мы уже говорили, что используем его в нашей бессерверной СУБД Yandex Database. Вы можете бесплатно попробовать ее на нашей платформе. В рамках free tier вы каждый месяц получаете первый миллион операций (в единицах Request Unit) и первый гигабайт хранения данных бесплатно. Этого вполне достаточно, чтобы протестировать технологию или даже запустить пет-проект.

Кроме того, если вам интересна экосистема Serverless-сервисов и все, что с этим связано, заходите в наше сообщество в Telegram, где можно обсудить serverless в целом.

Источник

Однофазная и многофазная фиксация транзакции

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

Если транзакция включает несколько ресурсов, необходимо выполнить двухфазную фиксацию (2PC). Протокол двухфазной фиксации (фаза подготовки и фаза фиксации) гарантирует, что при завершении транзакции все изменения, произведенные над всеми ресурсами, либо полностью фиксируются, либо полностью откатываются. После завершения транзакции результат сообщается всем участникам. Подробное описание протокола двухфазной фиксации см. в книге «обработка транзакций: основные понятия и методики (Morgan Кауфманн Series в управление данными Systems) ISBN: 1558601902«, Джим серый.

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

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

Двухфазная фиксация (2PC)

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

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

Фаза подготовки (фаза 1)

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

Диспетчеру ресурсов, реализующему интерфейс IEnlistmentNotification, сначала необходимо реализовать метод Prepare(PreparingEnlistment), как показано в следующем простом примере.

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

После того, как диспетчер ресурсов завершил свои операции подготовки, ему необходимо проголосовать за фиксацию или откат путем вызова метода Prepared или ForceRollback. Обратите внимание, что класс PreparingEnlistment наследует метод Done от класса Enlistment. Если вызвать этот метод для обратного вызова PreparingEnlistment в фазе подготовки, он сообщает диспетчеру транзакций, что зачисленный ресурс доступен в режиме «только чтение» (т. е. диспетчеры ресурсов могут читать, но не могут изменять защищенные транзакцией данные), и диспетчер ресурсов не получает дальнейших уведомлений от диспетчера транзакций относительно результата транзакции в фазе 2.

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

Фаза фиксации (фаза 2)

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

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

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

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

Реализация метода InDoubt

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

Оптимизация однофазной фиксации

Протокол однофазной фиксации наиболее эффективен при использовании во время выполнения, поскольку все изменения производятся без какой-либо явной координации. Дополнительные сведения об этом протоколе см. в статье Оптимизация с использованием однофазных фиксаций и уведомления с одним этапом продвижения.

Источник