DataShard: распределённые транзакции

На основе идей Calvin в YDB реализованы распределённые транзакции. Они состоят из множества произвольных (не обязательно детерминированных) операций, выполняемых над заранее известным набором участников, например DataShard'ами. В процессе выполнения транзакции, она подготавливается на каждом из участников, и получает позицию (временную метку) в глобальном порядке выполнения через одну из таблеток координатора в базе данных. Каждый участник получает часть потока транзакций с их участием, с сохранением их относительного порядка выполнения. Далее каждый участник выполняет свою часть распределённых транзакций в соответствии с этим порядком, и несмотря на то, что разные участники могут выполнять эти транзакции с разной скоростью и не одновременно, с точки зрения временных меток они выполняются в одной и той же точке, учитывая все эффекты, произошедшие с более ранними временными метками.

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

1. Фаза чтения. Участник производит чтение, фиксацию и отправку данных, которые необходимы другим участникам. Сейчас на коммите KQP транзакций (тип транзакции TX_KIND_DATA с заполненным полем TDataTransaction.KqpTransaction и типом KQP_TX_TYPE_DATA) в этой фазе происходит только проверка оптимистичных блокировок, если результат этой проверки нужен другим участникам. В более старых MiniKQL транзакциях (тип транзакции TX_KIND_DATA с заполненным полем TDataTransaction.MiniKQL) выполняется чтение и отправка произвольных данных. Другой пример, где происходит чтение в этой фазе - распределённая транзакция удаления строк по TTL, которая используется для фильтрации подходящих под условие строк и одновременного их удаления из основной таблицы и индексов.
2. Фаза ожидания. Участник ждёт получения необходимых ему данных от других участников.
3. Фаза выполнения. Участник на основе локальных и полученных с других участников данных принимает решение о выполнении, либо отмене транзакции, формирует и применяет эффекты в соответствии с телом транзакции. Тело транзакции написано таким образом, что участники принимают решение на одинаковых данных, и либо все принимают решение о выполнении, либо все принимают решение об отмене транзакции.

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

Начиная с версии 24.1 в YDB появилась поддержка "волатильных" распределённых транзакций. Основное отличие "волатильных" транзакций в том, что все участники (в том числе координатор), могут хранить информацию о транзакциях в памяти (и терять любое упоминание о них в случае рестарта) до момента их выполнения и записи эффектов в персистентное хранилище, в том числе отказываться от выполнения любой такой транзакции с гарантированной отменой на других участниках. Это позволяет исключить ожидание ответа от персистентного хранилища до выполнения распределённой транзакции на участниках и уменьшает время отклика.

В текущих версиях YDB, в процессе выполнения пользовательских YQL транзакций, в виде распределённых транзакций выполняется только финальный коммит, применяющий эффекты в read-write транзакциях. Запросы до коммита YQL транзакции выполняются как одношардовые с использованием оптимистичных блокировок, а консистентность обеспечивается с помощью глобального MVCC снимка.

Базовый протокол выполнения распределённых транзакций

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

В качестве примеров акторов, которые выполняют оркестрацию распределённых транзакций, можно привести:

• TKqpDataExecutor выполняет DML запросы, в том числе распределённые коммиты
• SchemeShard выполняет распределённые схемные транзакции
• TDistEraser выполняет распределённые транзакции удаления строк в таблицах с индексами для целей TTL

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

0. Определение списка участников. Выбирается набор конкретных шардов (TabletId), которые будут участвовать в её выполнении. Например, таблица может состоять из множества шардов (таблеток DataShard с уникальными TabletId), но если для конкретной транзакции набор затрагиваемых ключей попадает на один шард, такая транзакция будет одношардовой с единственным участником. В дальнейшем этот набор участников не может быть изменён.
1. Фаза подготовки. На участников отправляется специальное сообщение (обычно оно называется TEvProposeTransaction, в случае DataShard таблеток с недавнего времени появился специализированный вариант TEvWrite), в котором указывается уникальный в рамках кластера TxId (идентификатор транзакции), и которое описывает необходимые операции и их параметры (тело транзакции). Участники валидируют возможность выполнения транзакции, выбирают для неё допустимый диапазон позиций в глобальном порядке (процедура выбора MinStep и MaxStep описана ниже), в случае успеха запоминают транзакцию и отвечают статусом PREPARED.
   • Если транзакция одношардовая, в сообщении указывается режим "немедленного выполнения" (Immediate). Шард выполняет такую транзакцию как можно скорее (с учётом требований консистентности), а вместо PREPARED отвечает результатом выполнения. Фаза планирования при этом пропускается. В некоторых специализированных вариантах одношардовых операций (например TEvUploadRowsRequest для реализации BulkUpsert) допускается также отсутствие TxId.
   • Тело персистентной транзакции надёжно сохраняется в локальной базе и участник гарантирует её выполнение в будущем, В некоторых случаях (например "слепой" UPSERT в несколько шардов) участник даже должен гарантировать успешность выполнения.
   • Тело "волатильной" транзакции (Volatile) запоминается в памяти и участник сразу отвечает PREPARED. При этом выполнение или успешное выполнение этой транзакции не гарантируется.
   • Процесс переходит к следующей фазе только после того, как будут получены ответы от всех участников.
   • В общем случае (за исключением схемных транзакций), сообщения TEvProposeTransaction нельзя отправлять на участников повторно.
2. Фаза планирования. После того, как от всех участников был получен ответ PREPARED, на основе ответов выбирается общий MinStep и MaxStep, а также выбирается координатор, через которого будет происходить планирование транзакции. На координатор отправляется сообщение TEvTxProxy::TEvProposeTransaction с указанием TxId транзакции и списком её участников.
   • Выполнение транзакции возможно только между участниками одной базы данных. Каждый участник в ответе из фазы подготовки сообщает свои ProcessingParams, и в случае если все участники в одной базе данных, наборы координаторов и медиаторов будут идентичны.
   • Выбор координатора происходит на основе полученных ProcessingParams по историческим причинам, т.к. запросы выполнялись без указания базы данных, и узнать список координаторов можно было только от самих участников.
   • В случае, если сообщение TEvTxProxy::TEvProposeTransaction отправляется на координатор повторно, транзакция может быть запланирована на несколько временных меток одновременно. Это не является проблемой (и является нормой для схемных транзакций), в этом случае транзакция будет выполнена в минимальной временной метке, а остальные временные метки будут проигнорированы участниками, т.к. к этому моменту транзакция уже выполнена и более не существует.
3. Фаза выполнения. В этой фазе актор ожидает ответы от координатора и участников, собирая общий результат выполнения транзакции.
   • В некоторых случаях (временная потеря связи, рестарт таблеток) актор может восстанавливать подключение к участникам и продолжать ожидание результата, если к этому моменту транзакция ещё не была выполнена.
   • В случае потери связи и невозможности получить результат выполнения от какого-либо участника, пишущая транзакция завершается со статусом UNDETERMINED.

Фаза подготовки в таблетке DataShard

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

• TEvDataShard::TEvProposeTransaction точка входа для транзакций разных типов
• TDataEvents::TEvWrite специальная точка входа для операций записи данных и коммитов

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

• MinStep выбирается на основе текущего медиаторного/настенного времени
• MaxStep выбирается с добавлением таймаута планирования, который сейчас равен 30 секундам для обычных транзакций

После валидации и выбора параметров планирования, транзакция сохраняется на диск (в случае обычных транзакций), либо в памяти (в случае волатильных транзакций), шард отвечает статусом PREPARED и начинает ожидание плана с указанием PlanStep для данного TxId. Таймаут планирования используется на случай нештатного завершения актора, запускающего распределённую транзакцию. Шард не может достоверно выяснить, успел ли актор запустить фазу планирования до своего завершения, однако после успешной валидации транзакции должен гарантировать её потенциальное выполнение без возможности отмены по инициативе шарда (за исключением волатильных транзакций). Это блокирует многие конфликтующие операции (например, изменение схемы или партиционирования), и необходим таймаут, после которого гарантируется отсутствие возможности запланировать эту транзакцию. Когда медиаторное время превышает MaxStep без появления плана, гарантируется, что транзакция не сможет быть запланирована, и такая транзакция может быть безопасно удалена.

За хранение транзакций в памяти и на диске отвечает класс TTransQueue. В случае персистентных транзакций основная информация о транзакциях сохраняется в таблице TxMain и загружается целиком на старте шарда. Потенциально большое тело транзакции сохраняется в таблице TxDetails и может не задерживаться в памяти на время ожидания. Тело транзакции загружается в память повторно перед добавлением в очередь на выполнение и начала анализа конфликтов с другими транзакциями.

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

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

• SendingShards - шарды из этого множества отправляют ReadSet'ы на все шарды из множества ReceivingShards
• ReceivingShards - шарды из этого множества ожидают получение ReadSet'ов от всех шардов из множества SendingShards

В случае волатильных транзакций предполагается, что все шарды указываются в SendingShards (любой шард может отменить транзакцию и должен сообщить об этом на другие шарды), а шарды, применяющие эффекты, обязательно указываются в ReceivingShards (успешность применения эффектов зависит от других шардов). При этом через ReadSet'ы перадаются сериализованные сообщения TReadSetData с указанием единственного поля Decision.

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

Фаза планирования

После ответов PREPARED от всех участников, оркестрирующий актор выбирает максимум среди MinStep, минимум среди MaxStep, выбирает конкретный экземпляр координатора, и отправляет сообщение TEvTxProxy::TEvProposeTransaction с указанием TxId и списком участников (исторически для каждого участника также указывается тип операции над шардов - чтение или запись, но на практике это никак не используется). Соответствующий координатор выбирает ближайший подходящий PlanStep (шаг планирования) и добавляет в него указанный TxId со списком участников. Для персистентных транзакций это соответствие надёжно сохраняется на диске, обычно выбирая шаг планирования не чаще, чем каждые 10 миллисекунд. Для волатильных транзакций выбирается ближайший PlanStep среди тех, которые надёжно зарезервированы за текущим поколением координатора, а очередной шаг планирования (при наличии транзакций, либо при наличии запросов на продвижение медиаторного времени) выделяется каждую миллисекунду, и происходит без какой-либо записи на диск.

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

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

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

Медиаторы получают потоки шагов планирования через сообщения TEvTxCoordinator::TEvCoordinatorStep от каждого из координаторов и объединяют их по совпадению PlanStep. Объединённые шаги планирования, которые меньше или равны минимуму среди последних полученных шагов от каждого координатора, считаются полными и направляются на участников через сообщения TEvTxProcessing::TEvPlanStep. При этом на каждого участника приходит сообщение с указанием PlanStep, а также список TxId, которые должны быть выполнены в этом PlanStep. Транзакции в рамках одного PlanStep упорядочиваются по увеличению TxId. Пары (Step, TxId) в дальнейшем используется как глобальная MVCC версия в системе.

Участники подтверждают получение шагов планирования (и их надёжную запись в случае персистентных транзакций) через отправку сообщения TEvTxProcessing::TEvPlanStepAccepted отправителю (в таблетку медиатора) и сообщений TEvTxProcessing::TEvPlanStepAck в таблетки координатора. После получения этих сообщений соответствующие шаги планирования считаются доставленными на участника, удаляются из памяти и из локальной базы координатора, и не будут повторно доставляться.

На основе сообщений TEvTxProcessing::TEvPlanStepAccepted медиаторы также запоминают, до какого PlanStep включительно все шаги планирования были доставлены до всех участников. Такой максимальный PlanStep называется медиаторным временем и распространяется на ноды с участниками по подпискам через сервис TimeCast. В общем случае медиаторное время показывает, что до соответствующего PlanStep все сообщения TEvTxProcessing::TEvPlanStep были получены и подтверждены участником, и участнику должно быть известно обо всех транзакциях до этого времени включительно. Полезность медиаторного времени прежде всего в том, что позволяет шардам узнавать о продвижении времени в системе, даже когда они не участвуют в распределённых транзакциях. Для эффективности шарды сейчас распределяются по нескольким timecast бакетам на каждом медиаторе, и время в бакете продвигается когда все участники в этом бакете подтверждают получение TEvTxProcessing::TEvPlanStep. Само медиаторное время предоставляется шардам в виде подписки (через отправку TEvRegisterTablet в сервис time cast на старте шарда) на атомарную переменную (адрес которой приходит в сообщении TEvRegisterTabletResult после успешной регистрации в сервисе time cast) и позволяет избегать дорогих веерных рассылок сообщений на простаивающие шарды.

DataShard обрабатывает сообщения TEvTxProcessing::TEvPlanStep в транзакции TTxPlanStep, при этом найденным по TxId транзакциям назначается соответствующий Step и в дальнейшем они по очереди добавляются в Pipeline через PlanQueue в рамках ограничений на количество одновременно работающих активных транзакций.

Фаза выполнения в таблетке DataShard

Шаг выполнения PlanQueue разрешает запуск следующей распределённой транзакции в соответствии с увеличением (Step, TxId) и после опциональной загрузки тела транзакции с диска (для персистентных транзакций) KQP транзакция финализирует план выполнения и попадает в шаг выполнения BuildAndWaitDependencies. На этом шаге анализируются ключи, которые заявлены для чтения и записи в теле транзакции, на основе которых между транзакциями возникают зависимости. Например, если транзакция A пишет по ключу K, а более поздняя транзакция B читает по ключу K, то у транзакции B возникает зависимость на транзакцию A и транзакция B не может быть выполнена до завершения выполнения транзакции A. Транзакция выходит из шага BuildAndWaitDependencies только когда у неё не остаётся прямых зависимостей от других транзакций.

Перед выполнением персистентная KQP транзакция выполняет фазу чтений с формированием исходящих OutReadSet'ов (шаг BuildKqpDataTxOutRS), куда входит в том числе проверка оптимистичных блокировок. Далее на шаге StoreAndSendOutRS исходящие OutReadSet'ы и лог проверки блокировок сохраняются на диск. Если блокировки содержали незакомиченные изменения, у них выставляется флаг Frozen для предотвращения их отмены до завершения транзакции, в противном случае корректность обеспечивается через правильный порядок выполнения конфликтующих транзакций. Операция, которая формирует исходящие OutReadSet'ы либо проверяет блокировки, добавляется в Incomplete множество: конфликтующие транзакции должны обеспечить корректность уже произошедших чтений (например, выбирая MVCC версию для новых пишущих операций, которая больше чем версия операции), но при этом новые чтения могут не блокироваться на ожидании завершения этой операции и продолжать читать с версией, которая меньше чем версия операции.

Наконец, персистентные KQP транзакции подготавливают структуры данных для ожидания входящих InReadSet'ов (шаг PrepareKqpDataTxInRS) и переходят к ожиданию всех необходимых ReadSet'ов от других участников (шаг LoadAndWaitInRS). В некоторых случаях, например слепая запись в несколько шардов без проверки блокировок, может происходить без обмена ReadSet'ами, и в этом случае шаги по обработки ReadSet'ов ничего не делают и пропускаются. В качестве исключения для волатильных транзакций шаги работы с ReadSet'ами также ничего не делают и пропускаются.

Наконец, операция переходит к фазе выполнения (шаг ExecuteKqpDataTx), ещё раз проверяет локальные блокировки (на этот раз используя сохранённый ранее AccessLog), проверяет ReadSet'ы, полученные от других участников, и в случае успеха выполняет тело транзакции и завершается успешно. Если проверка блокировок (локальных или удалённых) не проходит успешно и обнаруживается конфликт, то операция завершается с ошибкой ABORTED.

Особенности выполнения волатильных транзакций

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

В основе волатильных транзакций лежит поддержка персистентных незакомиченных изменений в локальной базе. На фазе выполнения все эффекты записываются как незакомиченные (при этом используется глобально уникальный TxId распределённой транзакции), с добавлением транзакции в VolatileTxManager в состоянии ожидания решения о коммите от всех участников. Успешный ответ отправляется клиенту только после того как эффекты надёжно записаны, и все участники приняли решение о коммите. Последующие чтения используют TxMap чтобы видеть ещё ожидающие изменения, но проверяют их статус с помощью TxObserver. Если оказывается, что результат чтения зависит от волатильных изменений в состоянии ожидания, то такая операция подписывается на принятие решения о коммите волатильной транзакции и в конечном итоге перезапускается (либо прочитав теперь уже закомиченные изменения, либо пропустив их после отмены).

Наличие ещё незакомиченных и не отменённых волатильных транзакций накладывает ограничения на выполнение слепых операций на шарде. Из-за того, что незакомиченные изменения в локальной базе должны обязательно коммититься в том же порядке, в котором они происходили по каждому ключу, а информация о ключах транзакции не остаётся в памяти после её выполнения, DataShard вынужден делать чтение по ключу перед каждой записью для поиска конфликтов. Эти конфликты могут возникать как из-за незакомиченных изменений в рамках оптимистичных блокировок (в этом случае такие оптимистичные блокировки ломаются), так и принадлежать ещё ожидающим волатильным транзакциям. Чтобы не блокировать запись на время ожидания, даже не волатильная операция может переключиться на волатильный коммит. Для этого при необходимости выделяется GlobalTxId (уникальный в рамках кластера идентификатор транзакции, необходимые в случае отсутствия TxId в запросе, например BulkUpsert), а запись изменений по конфликтующим ключам переходит на волатильный коммит. Изменения при этом записываются как незакомиченные с указанием GlobalTxId, а в VolatileTxManager транзакция добавляется без указания других участников, и сразу оказывается закомиченной. Такие транзакции не блокируют последующие чтения, и после того как нижестоящие транзакции закоммитятся или отменятся, эти изменения также будут закоммичены в локальной базе.

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

Стоит заметить, что на таблице может быть настроена отгрузка потока изменений (асинхронные индексы и/или CDC). Формирование потока изменений в этом случае ничем не отличается от незакомиченных изменений в транзакциях. Для волатильной транзакции происходит формирование незакомиченного потока изменений, который в дальнейшем либо атомарно добавляется в общий поток, либо удаляется. В зависимости от настроек, для формирования потока изменений может потребоваться чтение текущего состояния строки. Если предыдущее состояние строки зависит от других ожидающих волатильных транзакций, образуется зависимость и последующий рестарт транзакции как и с обычным чтением. Это может сильно замедлять очередь распределённых транзакций, что впрочем мало чем отличается от возникновения зависимостей между персистентными распределёнными транзакциями с проверкой блокировок.

Одновременно с записью эффектов волатильная транзакция формирует и пишет на диск OutReadSet'ы для других участников распределённой транзакции из множества ReceivingShards. А после того, как ещё незакомиченные изменения успешно записаны на диск эти ReadSet'ы отправляются другим участникам.

Шарды после рестарта забывают о существовании волатильных транзакций, которые не успели сохранить эффекты на диске, и никогда уже не отправят ReadSet'ы другим участникам по своей инициативе. Чтобы даже в этом случае оперативно получать решение, шарды после успешного выполнения тела транзакции заранее отправляют другим участникам специальное сообщение, которое информирует об их ожидании входящего ReadSet'а (это называется ReadSet Expectation). Перезапустившиеся шарды увидят запрос на ReadSet по транзакции, про которую они ничего не знают, и отправят специальный ReadSet без данных. Благодаря таким ReadSet'ам без данных все участники узнают об отмене транзакции и также отменят её.

Гарантии на волатильные транзакции

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

Возможные источники ошибок при выполнении транзакций:

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

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

Это достигается следующим образом:

1. ReadSet'ы с DECISION_COMMIT отправляются другим участникам только после успешной записи незакомиченных изменений, описания транзакции и исходящих ReadSet'ов на диск. Таким образом сообщения с DECISION_COMMIT являются персистентными и продолжат отправляться на других участников до момента их подтверждения, независимо от того коммитится ли в итоге транзакция.
2. ReadSet'ы подтверждаются только после успешной записи чего-либо на диск, либо после подтверждения readonly lease на момент получения сообщения (актуально в случае получения более не актуальных ReadSet'ов). Таким образом невозможна ситуация, когда предыдущее (устаревшее) поколение таблетки подтверждает получение ReadSet'а для неизвестной транзакции, которая была подготовлена на более позднем поколении таблетки. Локальная база гарантирует, что новое поколение таблетки запускается после того как readonly lease на предыдущих поколениях истекает (при условии, что частота монотонных часов не отличается больше чем в два раза). Успешная запись на диск также подтверждает актуальность текущего лидера.
   • Для волатильных транзакций используется оптимизация, когда приходящие ReadSet'ы для них не записываются на диск. Подтверждение о получении отправляется только после завершения коммита или отмены транзакции, когда итоговое состояние надёжно записано на диск.
   • Таким образом, в случае, если все участники сформировали ReadSet'ы с DECISION_COMMIT, шарды гарантированно продолжат их получать, пока окончательно не закоммитят все эффекты транзакции и не отправят подтверждение.
3. Любые сообщения, связанные с отменой транзакции, отправляются только после записи этой отмены на диск. Это нужно на случай гонок между несколькими поколениями одного из участников. Если новое поколение успешно коммитит транзакцию, то более старое поколение (без доступа к диску и с истёкшей readonly lease) может получить NO_DATA на запрос о ReadSet'е (т.к. получение уже было подтверждено более новым поколением). Однако в этом случае более старое поколение не сможет записать отмену на диск, и не сможет ошибочно ответить ошибкой на закомиченную транзакцию.
4. Успешный ответ после получения всех DECISION_COMMIT можно отправлять не дожидаясь окончательного коммита транзакции, но требует чтобы её эффекты были записаны на диск и не потерялись в случае рестарта. Это позволяет отвечать на успешно выполненные транзакции за 1RTT стораджа, при этом результат выполнения транзакции остаётся стабильным:
   • В случае рестарта эффекты транзакции записаны на диск, и в худшем случае она восстановится в состоянии ожидания (Waiting), т.к. перед ответом мы как-минимум дождались записи этого состояния на диск.
   • С точки зрения MVCC эта транзакция уже выполнена, и любое новое чтение будет выполняться с версией, которая включает в себя изменения из этой транзакции. Любая новая попытка чтения этих изменений будет запускать ожидание решения по этой транзакции.
   • Неподтверждённые ReadSet'ы будут переотправлены, и т.к. мы ранее получили DECISION_COMMIT от всех участников, мы снова получим тот же успешный результат.
5. Пока транзакция находится в очереди, и особенно пока для неё неизвестен шаг планирования, входящие ReadSet'ы запоминаются в памяти, но по ним не отправляются ответы. Ответы отправляются уже после её выполнения, или если транзакция отменяются досрочно (с гарантией, что она не была и не будет записана на диск).

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

1. Многошардовая транзакция Tx1 осуществляет слепую запись в два шарда, по ключам x и y.
2. Одношардовое чтение Tx2 читает ключ x и видит значение записанное в Tx1.
3. Одношардовое чтение Tx3 строго после завершения Tx2 читает ключ y и не видит значение записанное в Tx1.

Данная аномалия возникает, если шард с ключом x быстро получает шаг планирования с транзацией Tx1 и выполняет запись. Поступившее на него чтение из транзакции Tx2 выберет MVCC версию, которая включает изменение по ключу x. Однако, шард с ключом y может находиться на ноде, которая немного отстаёт в продвижении медиаторного времени, и данный шард мог ещё не получать шаг планирования с транзакцией Tx1 и ещё не знает, будет ли выполняться данная транзакция и когда. Чтение из транзакции Tx3 в этом случае может выбрать MVCC версию, которая не включает в себя изменения по ключу y. Несмотря на то, что транзакция Tx3 выполнялась строго после Tx2, с точки зрения глобального порядка транзакция Tx3 выполнилась до Tx2.

С волатильными транзакциями подобная аномалия невозможна, т.к. для завершения чтения по ключу x шард должен получить DECISION_COMMIT от шарда с ключом y. Это означает, что транзакция выполнена и записана на шарде с ключом y, и последующее чтение в Tx3 обязательно дождётся положительного решения по данной транзакции и также прочитает изменение по ключу y.

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

Косвенное планирование волатильных транзакций

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

Чтобы избежать таких задержек, после получения шага планирования хотя бы одним из участников и выполнения транзакции, этот шаг упоминается в запросах на ReadSet'ы и отправляемых ReadSet'ах. Учатники, получив такое сообщение, косвенно узнают в каком PlanStep должна быть выполнена транзакция и запоминают его как PredictedStep. Даже если шаг планирования оказался потерян, DataShard добавляет транзакцию в PlanQueue на соответствующем шаге при получении не меньшего шага планирования по другим транзакциям, либо при продвижении медиаторного времени. В случае же если полученный таким образом шаг планирования оказался в прошлом, транзакция быстро отменяется, аналогично таймауту планирования.

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