Тестирование Tarantool с помощью Jepsen

Рассказ о тестировании СУБД Tarantool смотрите в статье Тестирование СУБД: 10 лет опыта , a здесь я расскажу о своём опыте разработки Jepsen тестов для тестирования консистентности в Tarantool. В статье я буду придерживаться структуры, которой обычно придерживается Kyle Kingsbury, автор библиотеки Jepsen, в опубликованных им отчётах для других СУБД.

TL;DR

• Мы сделали тесты для Tarantool с помощью Jepsen, см.
• Добавили тестирование в непрерывную интеграцию Tarantool
• Исходный код тестов доступен публично, https://github.com/tarantool/jepsen.tarantool
• For the current suite of Jepsen tests for Tarantool DB that we have tested in a loop, there are no correctness failures detected by Jepsen.
• Мы работаем над добавлением новых тестов

Что такое Tarantool?

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

Tarantool представляет собой сервер приложений на языке Lua, интегрированный с СУБД. В основе Tarantool лежат файберы (корутины с некоторыми отличиями), что означает, что несколько Tarantool-приложений могут работать в одном потоке, при этом каждый экземпляр Tarantool-сервера может одновременно запускать несколько потоков для обработки ввода-вывода данных и фоновых задач.

В архитектуре серверной части СУБД Tarantool реализована концепция «движков» базы данных, где в разных ситуациях используются разные наборы алгоритмов и структуры данных. В Tarantool есть два встроенных движка: движок memtx, который держит все данные и индексы в оперативной памяти, и дисковый движок vinyl. Оба движка поддерживают механизм транзакций и репликацию, поскольку они используют единый механизм упреждающей записи (WAL = write ahead log). Этот механизм обеспечивает согласованность и сохранность данных при сбоях. Таким образом, изменения не считаются завершенными, пока не проходит запись в лог WAL. Подсистема записи в журнал также поддерживает групповые коммиты.

In-memory движок базы данных Tarantool (memtx) хранит все данные в оперативной памяти, поэтому у него низкое значение задержки чтения. Кроме того, когда пользователи запрашивают снимки данных (snapshots), этот движок создает персистентные копии данных в энергонезависимой памяти, например на диске. Если экземпляр сервера прекращает работать и данные в оперативной памяти теряются, то при следующем запуске сервер загрузит в память самый свежий снимок и воспроизведет все транзакции из журнала. Таким образом, данные не теряются.

В штатных ситуациях in-memory движок работает без блокировок. Вместо многопоточных примитивов, которые предлагает операционная система (таких как mutex’ы), Tarantool использует кооперативную многозадачность для работы с тысячами соединений одновременно. В Tarantool есть фиксированное количество независимых потоков управления (thread), и у них нет общего состояния. Для обмена данными между потоками используются очереди сообщений с малой перегрузкой. Хотя такой подход накладывает ограничение на количество процессорных ядер, которые может использовать экземпляр, в то же время он позволяет избежать борьбы за шину памяти, а также дает запас масштабируемости по скорости доступа к памяти и производительности сети. В результате даже при большой нагрузке экземпляр Tarantool в среднем использует процессор менее чем на 10%.

Дисковый движок базы данных Tarantool совмещает в себе подходы, заимствованные из современных файловых систем, журнально-структурированных деревьев со слиянием (LSM-дерево, log-structured merge trees) и классических B-деревьев.

Дизайн:

• http://kostja.github.io/misc/2017/01/24/tarantool-design-principles.html

Гарантии согласованности в Tarantool

The task of enumerating what a database promises can be surprisingly hard, especially given that distributed databases are complex. But fortunately, there are some models that make this possible.

CAP Theorem

In terms of the CAP theorem, Tarantool DB is a consistent and partition-tolerant (CP) database, while ensuring high availability (HA) for most practical situations. Thus, the Jepsen test suite needs to verify strong consistency of data in the presence of partitions and failures. That brings us to the next question – what does strong consistency mean in Tarantool DB?

ACID Transactions

YugaByte DB’s replication protocol is strongly consistent, and this is essential for being an ACID compliant distributed database in the face of failures (such as node death). ACID stands for the following:

• Atomicity – All the work in a transaction must be treated as one atomic unit - either all of it is performed or none of it is.
• Consistency – The database must always be in a consistent internal state after updates. For example, failed writes or partial writes must not be stored in the database.
• Isolation – Determines how and when changes made by a transaction become visible to the others. YugaByte DB currently supports Snapshot Isolation, which detects write-write conflicts.
• Durability – Successful writes must be permanently stored in the database.

Our Jepsen test suite verifies each of the above properties of the database while subjecting it to various failure scenarios.

Мы считаем, что в случае использования единственного процесса Tarantool модель консистентности соответствует Serializable и Linearizable с одной оговоркой: если не возникло внешних причин для отката транакции, например нехватка дискового пространства.

TODO: найти цитату из документации подтверждающую Linearizable.

https://www.tarantool.io/ru/doc/latest/book/box/atomic/#transactions

“In Tarantool, transaction isolation level is serializable with the clause «if no failure during writing to WAL». In case of such a failure that can happen, for example, if the disk space is over, the transaction isolation level becomes read uncommitted.”

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

In Tarantool, transaction isolation level is serializable with the clause «if no failure during writing to WAL». In case of such a failure that can happen, for example, if the disk space is over, the transaction isolation level becomes read uncommitted.

In vynil, to implement isolation Tarantool uses a simple optimistic scheduler: the first transaction to commit wins. If a concurrent active transaction has read a value modified by a committed transaction, it is aborted.”

Для тестирования изоляции транзакций в vinyl мы портировал набор тестов hermitage от Мартина Клеппмана - vinyl/hermitage.test.lua.

TODO: картинка с иерархией моделей консистентности и отметкой Serializable (мы сейчас здесь). (https://jepsen.io/consistency)

Синхронная репликация

В 2020 году в Tarantool 2.6 (см. анонс) добавили поддержку синхронной репликации и алгоритм автоматического выбора лидера Raft. Позднее ещё появился транзакционный менеджер с поддержкой MVCC (Multi Version Concurrency Control) и мы решили попробовать сделать для нее Jepsen тесты. Разработкой тестов занимался я, поэтому информация в статье из первых рук.

Про синхронную репликацию, историю разработки, архитектурные решения можно почитать в отдельной статье Синхронная репликация в Tarantool и докладе Влада Шпилевого: доклад Изобретая синхронную репликацию или посмотреть доклад с Highload 2021:

Про Raft и детали добавления его в Tarantool есть статья от Сергея Петренко - Raft в Tarantool. Как это работает и как этим пользоваться.

Синхронная репликация и транзакционный менеджер добавляют гарантий сохранности данных. Они сложные в реализации (объяснить почему) и тестирование их нетривиально. В статье я расскажу о нашем опыте тестирования консистентности и уровней изоляции в СУБД Tarantool. Но в то же время при появлении синхронной репликации появлялась проблема с “dirty reads” (https://github.com/tarantool/tarantool/issues/5229). Мы заранее предполагали существование этой проблемы и планировали решить с помощью нового транзакционного менеджера (TXM). Он появился в экспериментальном режиме в версии 2.6, по умолчанию TXM выключен, но его можно включить опцией memtx_use_mvcc_engine.

Начались проблемы:

• проверить баг “dirty read” https://github.com/tarantool/tarantool/issues/5229
• баг Влада ‘dirty read’ https://github.com/tarantool/tarantool/issues/5522
• https://github.com/tarantool/tarantool/issues/5515 от Олега
• Transaction manager does not detect a conflict #5559 https://github.com/tarantool/tarantool/issues/5559

У нас нет системных тестов, которые бы полноценно тестировали изоляцию и консистентность. Мы рассматривали разные варианты и в итоге выбрали фреймворк Jepsen.

Что такое Jepsen?

The tool itself, also called Jepsen, is a Clojure framework used to set up distributed systems tests, run operations against them, and verify the operation history is sane and possible given the claims of the project. Then, it can generate some nice graphs out of that data.

It’s kind of like a really flexible failure-injecting fuzzer.

In many cases, Jepsen tests for linearizability by using Knossos to prove that a given history (from a test) is non-linearizable. Jepsen also frequently tests for timing-related issues using libfaketime to create clock skew.

Jepsen itself doesn’t rigorously enforce any specific tests, it’s up to the tester to determine which claims, under which conditions, they wish to attempt to disprove. Once these claims are written, the framework can attempt to find examples in invalid states.

While the specifics of tests are up to the author, there is a common suite of tests for testing certain claims, such as how required for snapshot isolation or sequential consistency.

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

https://blog.acolyer.org/2018/01/23/why-is-random-testing-effective-for-partition-tolerance-bugs/

Random simulation is the primary mode of testing systems with large and complex state spaces across many different domains… Our results are a step towards a theoretical understanding of random testing: we show that the effectiveness of testing can be explained in certain scenarios by providing lower bounds on the probability that a single random test covers a fixed coverage goal. For network partition tests, we introduce a set of coverage goals inspired by actual bugs in distributed systems and show lower bounds on the probability of a random test covering a goal.

Why is random testing effective for partition tolerance bugs? Majumdar & Niksic, POPL 18, TODO: pdf

Simple Testing Can Prevent Most Critical Failures: An Analysis of Production Failures in Distributed Data-intensive Systems Ding Yuan, Yu Luo, Xin Zhuang, Guilherme Rodrigues, Xu Zhao, Yongle Zhang, Pranay U. Jain, and Michael Stumm:

Almost all (98%) of the failures are guaranteed to manifest on no more than 3 nodes. 84% will manifest on no more than 2 nodes…. It is not necessary to have a large cluster to test for and reproduce failures.

TODO: Примеры истории операций, которую пишет Jepsen.

Библиотека Jepsen хорошо себя зарекомендовала в тестировании распределенных систем. Это подтверждают и отчёты о тестировании различных СУБД с описанием найденных проблем и публикации исследователей с анализом причин эффективности подхода, используемого в Jepsen. В то же время разработка тестов в новом проекте может быть затруднена как минимум из-за использования языка Clojure, на котором написана библиотека. Clojure не настолько популярен среди разработчиков и тестировщиков распределенных систем как, например, Python. При разработке синхронной репликации в Tarantool Core мы тоже использовали Jepsen и разработали на её основе набор тестов, которые сейчас интегрированы в систему непрерывной интеграции проекта. Я расскажу о нашем опыте использования этой библиотеки при тестировании Tarantool, о том c какими проблемами мы столкнулись. Мы пристально рассмотрим библиотеку Jepsen и разберем её на кусочки, чтобы понять как она работает и из каких частей состоит тест. Далее мы вместе напишем небольшой тест для etcd с использованием подхода, используемого в Jepsen, но на Lua вместо Clojure и используем корутины (кооперативная многозадачность) вместо тредов Java (кооперативная многозадачность). С помощью этого теста найдём баг с нарушением согласованности операций чтения в etcd. Доклад будет интересен разработчикам и тестировщикам распределенных систем, сторонникам подхода тестирования с помощью свойств (PBT), противникам кооперативной многозадачности и сторонникам вытесняющей многозадачности. Для прослушивания доклада знание Clojure и Lua не потребуется.

TODO: эффективность и причины успеха, примеры, демонстрирующие успешность использования jepsen в тестировании

Разработка тестов для Tarantool

Фреймворк Jepsen написан на языке Clojure и перед тем, как разрабатывать тесты нужно было разобраться с тем, как подключаться к Tarantool из Clojure. Tarantool поддерживает два способа удалённых подключений: нативные коннекторы и вариант с использованием ODBC/JDBC и использованием языка запросов SQL. На данный момент у нас ограниченная поддержка SQL (beta) и я выбрал первый вариант с использованием коннектора из-за потенциальной гибкости - всю недостающую функциональность можно было бы реализовать с помощью Lua. Для Tarantool есть официальные коннекторы, которые поддерживает команда разработки и неофициальные, написанные людьми из сообщества. До сих пор у нас не было потребность использовать Tarantool в Clojure, поэтому официального коннектора для Clojure нет. Но есть два коннектора, исходный код которых я нашел на Гитхабе: первый коннектор (https://github.com/fl00r/tarantool-clj-1.7) работает с сырыми данными с помощью протокола IPROTO и MsgPack, второй (https://github.com/fl00r/tarantool-clj) использует официальный коннектор для Java и является обвязкой для него. После небольших экспериментов я решил поискать другие варианты: в новой версии Clojure обновилась библиотека async и оба коннектора требовали обновления, автор обоих коннекторов давно забросил код, не реагирует на PR, a делать форк проектов на тот момент мне не хотелось. К тому же коннекторы использовали отдельные подключения к каждому спейсу Tarantool, что я посчитал неудобным.

Далее я рассмотрел возможность использования интерфейса JDBC. Для этого в Clojure есть библиотека clojure.jdbc. Наш драйвер JDBC работает в экспериментальном режиме и одно из его ограничений это отсутствие поддержки интерактивных транзакций. Библиотека clojure.jdbc по умолчанию пытается включить интерактивные транзакции, но из-за отсутствия их поддержки в нашем Java коннекторе срабатывает исключение:

public void setAutoCommit(boolean autoCommit) throws SQLException {
    checkNotClosed();
    if (!autoCommit) {
        throw new SQLFeatureNotSupportedException();
    }
}

Тогда я решил попробовать другую JDBC библиотеку - next.jdbc. С ней всё стало работать так, как надо. В перспективе мы не исключаем вероятности использования нативного коннектора для тестов Jepsen. Но в текущей версии тесты используют только SQL интерфейс.

Дизайн тестов

TODO: составляющие теста Jepsen: тест с генераторами нагрузки и сбоев + проверка корректности https://github.com/jepsen-io/jepsen#design-overview

The Jepsen tests for Tarantool DB are designed to verify atomicity, consistency, isolation and durability in the face of a various failure scenarios. Since we induce various failures while performing operations against the database, it is natural to expect that some individual operations may fail, but correctness should not be compromised. The expectation on the operations across all of the tests is that they return one of the following based on the result of the operation:

OK: The operation was successful. For example, a successful update must be persisted in the DB and comply with ACID.

FAIL: The operation failed. For example, a failed update must not be stored in the DB and behaves the same as the update never having occurred.

UNKNOWN: The result of the operation is unknown. For example, in the case of an update, there could be a timeout (possibly because of a network partition). The update could either have been applied, or not been applied.

Each test logs every operation it performs along with the result of the operation. At the end of the test, a checker validates that the results are consistent with the sequence of the operations.

The unique key-value inserts test creates a table with one primary key column and one value column. It inserts unique key-values pairs into the table, and verifies durability (by checking if successfully written values can be read back) and consistency (by ensuring failed writes are not present in the database).

The single-key ACID transactions test performs concurrent read, write and read-modify-write (compare and set) operations on a single row in a table. It checks the consistency of the database and the atomicity of these operations by introducing various failures. The distributed ACID transactions test creates a key-value table spanning multiple nodes and performs concurrent multi-row transactions, each of which updates two different keys with the same value. At the end of these tests, a checker validates that the result of the sequence of operations recorded, which is the client observed view of the data, is ACID compliant.

Сделали тесты: cas-register, bank, set, counter.

We verify the linearizability of operations on single keys by performing randomized writes, reads, and compare-and-set operations on individual records, then checking that the resulting history is linearizable using the Knossos linearizability checker.

В тесте используются три операции: Read, Write и CAS (Compare And Set). И хотя в Tarantool нет встроенной операции CAS (Compare And Set) её можно реализовать с помощью Lua функции и обращаться как к SQL команде: (https://www.tarantool.io/en/doc/latest/reference/reference_sql/sql_plus_lua/#calling-lua-routines-from-sql)

box.schema.func.create('_CAS',
   {language = 'LUA',
    returns = 'boolean',
    body = [[function(id, old_value, new_value, table)
             local rc = false
             box.begin()
             local tuple = box.space[table]:get{id}
             if tuple then
                 if tuple[2] == old_value then
                     box.space[table]:update({id}, {{'=', 2, new_value}})
                     rc = true
                 end
             end
             box.commit()

             return rc
             end]],
    is_sandboxed = false,
    param_list = {'integer', 'integer', 'integer', 'string'},
    exports = {'LUA', 'SQL'},
    is_deterministic = true})

https://www.tarantool.io/en/doc/latest/book/box/data_model/

The syntax of upsert() is similar to the syntax of update(). However, the execution logic of these two requests is different. UPSERT is either UPDATE or INSERT, depending on the database’s state. Also, UPSERT execution is postponed until after transaction commit, so, unlike update(), upsert() doesn’t return data back.

Внедрение сбоев

In addition to these tests, Jepsen uses Nemeses, an error injection tool which introduces failures to a system. A Nemesis can create partitions, fail processes, and cause other types of actions.

The Jepsen framework subjects the tests to a number of failure scenarios, rightfully called nemesis failures.

clock-skew - cover a range of issues related to the clock synchronization across different machines. There are a number of different clock skews introduced – small (~100ms), medium (~250ms), large (~500ms) and xlarge (~1 secs). Used libfaketime to simulate some node clocks, both CLOCK_REALTIME and CLOCK_MONOTONIC, running up to 5x faster than others. Маловероятно, что такой вид fault injection поможет найти какие-то проблемы в Tarantool. Потому что в репликации (и синхронной и асинхронной) Tarantool использует векторные часы.

• kill (SIGKILL) - kill and restart a randomly chosen database process that is a part of the cluster.

• pause - process pauses (SIGSTOP)

• partition - introduce network partitions into the cluster that isolates a randomly chosen node from the rest of the nodes in the cluster.

• partition-half - n/2+1 splits. Это вид сбоя должен спровоцировать разделение кластера на две самостоятельные части, который называется split brain. В случае включенного автоматического выбора лидера у нас такой ситуации возникнуть не может, потому что кворум должен быть всегда больше N/2. В противном случае функциональность автоматического выбора лидера не будет работать.

• partition-one - isolate single nodes

• partition-ring - introducing network partitions dividing the cluster in two, or into overlapping rings of 3/5 nodes each, such that every node observed a majority, but no two nodes agreed on what that majority was.

Результаты и выводы

• Jepsen это не магия, а обычное тестирование
• Каждому по силам написать аналог Jepsen без погружения в Clojure
• команда должна понимать как работает инструмент
• вопросы доверия к самописным тестам
• отчуждаемость верификатора историй от самой библиотеки
• Clojure: https://kimh.github.io/clojure-by-example/