В распределенных системах есть ряд фундаментальных проблем: эффективные распределенные транзакции, exactly-once обработка данных, точная синхронизация физических часов. Для решения последней проблемы были изобретены ^[1] разные виды логических часов ^[2].

Тем не менее, векторные часы ^[3] обладают неприятными свойствами: они вводят условную зависимость между событиями там, где ее нет, и теряют ее там, где она на самом деле есть.

Однако, можно придумать нечто более надежное — Kronos. В статье мы посмотрим на алгоритм учета причинно-следственной связи и его применение для построения Key-Value хранилища с распределенными транзакциями.

Проблемы

Как уже было сказано, с логическими часами есть ряд проблем:

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

• С другой стороны, логические часы учитывают взаимосвязь только через сообщения внутри системы. Если какие-то два события связаны, но вне системы, например, через пользователя (добавление товара в корзину в одной части системы -> оплата заказа), то логические часы могут упустить такую взаимосвязь.

• К логическим часам невозможно получить доступ извне, а также сложно связать между собой несколько независимых компонент (распределенная файловая система, сервисы обработки запросов, аналитика).

Решение

В статье 2014 года Kronos: The Design and Implementation of an Event Ordering Service ^[4] предлагается решение — отдельностоящий сервис, который будет заниматься учетом причинно-следственных связей в событиях.

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

Минимальное API можно определить следующим набором методов:

Метод	Результат	Комментарий
create_event()	e	Создает новое событие в Kronos
query_order([(e_1, e_2), ...])	[<-, concurrent, ->, ...]	Для каждой пары из запроса возвращает направление причинно-следственной связи, или одновременность событий
assign_order([(e_1, e_2, must), (e_3, e_4, prefer), ...])	OK/FAIL	Для каждой пары из запроса устанавливает направление причинно-следственной связи
acquire_ref(e)	OK	Увеличивает счетчик ссылок для данного события
release_ref(e)	OK	Уменьшает счетчик ссылок для данного события

Реализация

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

Как видно из API, запрос assign_order принимает также тип причинно-следственной связи: must или prefer. must соответствует строгим инвариантам — например, создание_объекта->удаление_объекта, prefer же может быть не применен, если он конфликтует с must связями. Пример использование prefer — запросы, которые пришли раньше, лучше обратыватывать раньше, но это не влияет на корректность.

Эффективный BFS

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

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

Сборка мусора

Как видно из таблицы, есть еще два метода: acquire_ref и release_ref.

Внутри Kronos для каждого события хранится счетчик ссылок. Пока какой-то сервис обрабатывает событие, или оставляет за собой возможность добавлять новые события, которые случаются после текущего, он хранит ссылку. Когда такая необходимость пропадает, сервис вызывает release_ref.

Kronos удалит событие, когда все условия будут выполнены:

1. Количество ссылок достигло нуля
2. Все события, предшествующие данному, уже удалены из графа

Такой подход не ограничивает возможные запросы, но экономит память внутри Kronos.

Приложения

Рассмотрим использование системы на примере Key-value хранилища с распределенными транзакциями.

Пусть есть несколько серверов, каждый сервер отвечает за диапазон ключей.

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

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

Заметим, что такие транзакции будут ACID ^[5]:

• Atomicity: транзакция либо не сможет быть запланирована в Kronos, либо будет запланирована к выполнению на всех узлах.
• Consistency: автоматически в KV-хранлищах.
• Isolation: если две транзакции пересекаются по данным, значит они будут связаны причинно-следственной связью в Kronos, а значит одна будет выполнена раньше другой.
• Durability: поскольку Kronos устойчив к падениям и предполагается, что каждая реплика хранилища тоже устойчива, единственное, что нужно доказать — персистентность данных незаконеченных транзакций. Действетльно, если транзакция помечена клиентом как успешная, но на сервере запись еще не выполнена, то такой факт легко установить, поскольку сервер также ведет учет выполненых частей транзакций.

Производительность

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

Более того, в сравнении с MongoDB система поверх Kronos уступает всего на 6%, при том, что в MongoDB не используются распределенные транзакции.

Анализ

Тем не менее, эксплуатация Kronos несет ряд недостатков.

• Во первых, возникают накладные расходы обращения к Kronos — каждый запрос потребует как минимум одно обращение.
• Kronos также будет являться единой точкой отказа — авторы статьи не предлагают способов партицирования графа событий.
• В систему неплохо было бы добавить ряд методов. Например, в примере с KV-хранилищем неплохо было бы иметь callback, который сообщал бы серверу о статусе транзакции — она успешно была добавлена в граф со всеми нужными зависимостями — или, наоброт, не удалось выполнить транзакцию.

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

Заключение

Примерно такому мы в Школе GoTo учим студентов и школьников на направлении Распределенных Систем.

А еще есть Алгоритмы и Приложения ^[6], Прикладное программирование, Биоинформатика и Анализ Данных ^[7]

Приезжайте к нам на осеннюю школу ^[8] 27 октября — 4 ноября или зимнюю школу ^[9] в начале января.

А если вы уже не студент и не школьник — приезжайте преподавать ^[10].

Автор: Omrigan

Источник ^[11]