Тестирование менеджера транзакций
Привет, Хабр! Меня зовут Георгий Лебедев, я учусь на 4-м курсе ФРКТ МФТИ и работаю в команде разработки ядра Тарантула. В этой статье я хочу поделиться методикой тестирования менеджера транзакций, которая применяется в Тарантуле.
Менеджер транзакций можно встретить в любой системе с конкурентным доступом, гарантирующей ACID, прежде всего в СУБД. Менеджер транзакций — это система, которая может находиться в огромном числе значимых состояний. Причем их все невозможно охватить написанными вручную тестовыми сценариями. Для этого используются автоматические методы тестирования, генерирующие набор транзакций и валидирующие корректность их обработки базой данных.
Для начала сверим словари: что такое транзакция
Транзакцию можно определить двумя ключевыми свойствами:
- Это логически неделимая группа последовательных операций с базой данных. Она может быть выполнена либо целиком и успешно, с соблюдением целостности данных и независимо от параллельно идущих других транзакций, либо не выполнена вообще, и тогда она не должна произвести никакого эффекта.
- Это абстракция, создающая иллюзию монопольной работы с базой данных.
Расписание и сериализуемость
Набору транзакций ставится в соответствие расписание. Расписание — это абстракция, отражающая результат выполнения транзакций.
В приведенной таблице отражены транзакции T1 и T2, а также изменения переменных, которые эти транзакции затрагивают. Это пример последовательного расписания — в нем транзакции выполняются без чередования.
Сериализуемость — это свойство расписания быть эквивалентным результату некоторого последовательного применения того же набора транзакций.
В таблице ниже порядок выполнения операций не такой, как в последовательном расписании (операции чередуются), но в итоге это расписание дает тот же результат, что и последовательное.
Сериализуемость может нарушаться при возникновении конфликтов (зависимостей) между транзакциями: одна транзакция прочитала значение, измененное другой транзакцией, или две транзакции перезаписали одно и то же значение. В итоге результат расписания изменится при перестановке двух таких операций.
Для формирования сериализуемого расписания конфликтующие транзакции должны взаимоисключаться — то есть только одна из двух конфликтующих транзакций может присутствовать в расписании. Поэтому по завершении транзакция может быть либо подтверждена, либо отменена.
Граф сериализации
Сериализуемость можно визуализировать и формализовать с помощью теории графов. Граф сериализации некоторого расписания — это направленный граф, вершинами которого являются транзакции этого расписания, а ребра выражают отношение конфликта между транзакциями. Причем направление ребра определяется порядком выполнения операций: ребро идет от более ранее операции к более поздней.
Алгоритм построения графа следующий:
- Для каждой транзакции Ti создать узел.
- Для каждого случая, когда транзакция Tj выполняет операцию чтения записи по ключу X после операции записи по ключу X транзакции Ti, создать ребро из Ti в Tj.
- Для каждого случая, когда транзакция Tj выполняет операцию обновления записи по ключу X после операции чтения по ключу X транзакции Ti, создать ребро из Ti в Tj.
- Для каждого случая, когда транзакция Tj выполняет операцию обновления записи по ключу X после операции записи по ключу X транзакции Ti, создать ребро из Ti в Tj.
По графу сериализации можно однозначно определить, является ли расписание сериализуемым: его ацикличность гарантирует сериализуемость, и его можно использовать для тестирования корректности поведения менеджера транзакций.
Рассмотрим следующее расписание:
Для приведенного выше расписания граф сериализации будет выглядеть следующим образом:
Граф сериализации не содержит циклов — следовательно, расписание сериализуемое.
Немного изменим вторую транзакцию из расписания, которое мы рассмотрели выше:
Этому расписанию соответствует следующий граф сериализации:
Теперь граф сериализации содержит цикл — значит, расписание не сериализуемое из-за конфликта между первой и второй транзакцией.
Управление транзакциями
Управление транзакциями главным образом заключается в следующем:
- Отслеживать набор прочитанных и измененных транзакцией данных и возникающих конфликтов.
- Создавать для клиента иллюзии (абстракции) монопольной работы с базой данных, то есть изолировать клиента.
До недавнего времени в «Тарантуле» для In-memory-движка хранения memtx использовался довольно простой подход: если файбер с активной транзакцией передает управление (делает yield), то его транзакция отменяется. Несколько лет назад в «Тарантуле» для этого движка хранения появился основанный на MVCC менеджер транзакций, описание которого можно найти в статье.
Важно отметить, что в «Тарантуле» транзакции естественным образом сериализуются в порядке их подтверждения. Менеджер транзакций подтверждает транзакцию только в том случае, когда последовательное выполнение транзакций дало бы такой же результат.
В «Тарантуле» есть только один поток, обрабатывающий транзакции. Конкурентность достигается за счет использования среды кооперативной многозадачности, основанной на файберах, которая позволяет чередовать операции из различных транзакций. За счет этого можно без больших накладных расходов (по сравнению с многопоточной моделью исполнения) поддерживать полную сериализуемость, то есть наивысший уровень изоляции, Serializable.
Тестирование менеджеров транзакций
Менеджер транзакций — это система с большим и сложным пространством состояний. В связи с этим тестировать такую систему традиционными методами недостаточно из-за невозможности покрыть все состояния вручную написанными тестовыми сценариями. Для таких систем оказывается эффективным применение алгоритмов рандомизированного тестирования.
Рандомизированное тестирование менеджера транзакций заключается в:
- генерации случайных операций для транзакций;
- исполнении этих транзакций;
- получении расписания транзакций, то есть упорядоченного набора транзакций, которые были подтверждены;
- проверке сериализуемости полученного расписания.
Тестирование с помощью графа сериализации
State-of-the-art-рандомизированное тестирование менеджеров транзакций основано на анализе графов сериализации. Графы сериализации являются наиболее общим подходом и позволяют проверять различные уровни изоляции. Помимо нахождения аномалий, с помощью графа сериализации также можно найти ложные конфликты, то есть когда транзакция была отменена, несмотря на то что она ни с кем не конфликтовала.
Например, такой подход используется в YDB. У этого проекта есть свой собственный тестовый фреймворк для генерации транзакций и проверки их расписания на сериализуемость.
Также этот подход используется в Elle — инструменте проекта Jepsen для тестирования консистентности транзакций, с помощью которого было найдены новые аномалии и баги в ведущих СУБД, например в Postgres.
Тестирование с помощью линеаризации расписаний
Мы в «Тарантуле» разработали новый менеджер транзакций для In-memory-движка хранения memtx. После разработки нам понадобилось провести рандомизированное тестирование для выявления аномалий и багов и для достижения большего покрытия кода.
Мы обратили внимание на особенность «Тарантула», которая позволяет легко поддерживать наивысший уровень изоляции Serializable, то есть исключительно сериализуемые расписания. За счет этого можно использовать гораздо более простой подход, чем построение графов сериализаций.
В итоге мы пришли к следующей идее. Мы ожидаем, что расписание, которое у нас получится в результате генерации, является упорядоченным (по времени подтверждения) и сериализуемым. Поэтому мы можем прогнать операции из наших транзакций в соответствии с порядком транзакций и должны получить те же результаты. Иными словами, мы можем линеаризовать расписание, которое получаем, и воспроизвести его. Любое расхождение результатов означает наличие аномалии, а допущение такой аномалии — баг в менеджере транзакций.
Мы реализовали тестовый фреймворк для генерации случайных транзакций, их линеаризации и воспроизведения с поиском расхождений. Как приятный побочный бонус: наш тестовый фреймворк позволяет моментально получить скрипты для воспроизведения аномалий, что является немаловажным при рандомизированном тестировании.
Заключение
На сегодняшний день наш тестовый фреймворк выявил 29 багов и позволил нам существенно улучшить покрытия кода менеджера транзакций, открыв путь для его рефакторинга и оптимизаций.
Рассмотрение уникальных свойств системы может помочь упростить решение некоторых задач, как, например, в рассмотренной задаче тестирования менеджера транзакций.
Рассмотренный нами подход к тестированию применим не только к «Тарантулу», но и к любым другим транзакционным системам с линеаризуемыми расписаниями. При этом он гораздо проще в реализации, чем анализ графов сериализации.
