Реплицируемый объект. Часть 1: Введение

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

Аннотация

1. Есть страдание.
2. Есть причина страдания.
3. Есть прекращение страдания.
4. Есть путь, ведущий к избавлению от страданий.

4 благородные истины буддизма

Настоящая статья содержит описание раннего прототипа, который вводит понятие реплицируемого объекта (replicated object) или сокращённо replob. Такой объект является дальнейшим переосмыслением борьбы со сложностью кода, возникающего при программировании распределённых систем. Replob устраняет зависимость от стороннего сервиса и реализует согласованное изменение любых пользовательских объектов, представляющих соответствующие данные и функциональность. Эта идея основана на использовании выразительности языка C++ и объектно-ориентированного подхода, что позволяет использовать сложную логику внутри распределённых транзакций. Это позволяет значительно упростить разработку отказоустойчивых приложений и сервисов. Последующие статьи будут более детально объяснять развиваемый подход.

Введение

ПРЕДУПРЕЖДЕНИЕ. Почти все методы, указанные в статье, содержат грязные хаки памяти и ненормальное использование языка C++. Так что, если вы не толерантны к таким извращениям, пожалуйста, не читайте эту статью.

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

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

Обзор

Как показывает жизнь, счастье в меньшей степени зависит от внешних вещей, чем полагает большинство.

Уорен Коупер

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

Современные системы используют отказоустойчивые сервисы, такие как Zookeeper (в основном) или etcd (в стадии активной разработки). Они используют алгоритмы распределённого консенсуса: Zab (Zookeeper) или Raft (etcd), чтобы обеспечить линеаризуемость операций. Идея здесь заключается в следующем. На первом шаге избирается лидер, затем назначенный лидер (мастер) фиксирует сообщения в определенной последовательности, что обеспечивает необходимый уровень консистентности. Несмотря на то, что документация Zookeeper утверждает, что Zookeeper реализует подход с использованием первичной резервной копии, а не репликации конечного автомата, очевидно, что единственная разница между этими подходами состоит в том, что первичная резервная копия основана на очередности, задаваемой репликами, а репликация конечного автомата основана на последовательности, задаваемой клиентом. Я думаю, что тут важно то, что оба подхода договариваются о последовательности детерминированных операций с использованием разработанных алгоритмов консенсуса на основе мастера.

Обсуждение существующих подходов

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

Эпиктет

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

1. Chubby: большинство проблем длилось около 15 секунд или меньше, 52 из которых были в районе 30 секунд.
2. MongoDB: время варьировалось, однако реплики выбирали мастера в течение минуты… Во время выбора мастера кластер был недоступен для записи.
3. Zookeeper: новый лидер был избран через 15 секунд или около того, и запись снова продолжилась. Тем не менее, только клиенты, которые имели доступ к одной из нод [n3 n4 n5] могли писать, а клиенты, подключенные к нодам [n1 n2] завершали свою обработку с таймаутом при попытке соединения с лидером.

Транзакционная семантика и нетривиальные сценарии

Логика – это искусство ошибаться с уверенностью в своей правоте.

Дж. У.Крач

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

1. Загрузка некоторой части данных из хранилища в память процесса для работы.
2. Применение нетривиальной логики для обработки данных и получения результата.
3. Сохранение полученного результата в хранилище.

Этот сценарий может быть решен путем применения нескольких подходов.

Пессимистическая блокировка

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

1. Получение эксклюзивной блокировки для выполнения операции.
2. Выполнение операций, описанных выше (загрузка, применение и сохранение).
3. Снятие блокировки.

Недостаток этой схемы непосредственно вытекает из требования эксклюзивности доступа:

1. Эксклюзивная блокировка значительно увеличивает время ожидания при совершении операций блокировки/разблокировки. Что, в свою очередь, ухудшает общее время совершаемых операций.
2. В случае падения процесса в середине выполнения операций мы потенциально можем получить неконсистентные данные (к счастью, Zookeeper имеет функциональность для атомарного применения нескольких операций на этапе разблокировки). Это требует дополнительного времени на обнаружение падения процесса и последующей разблокировки ресурса, что увеличивает общее время такой операции.

Я хотел бы подчеркнуть, что системы, подобные Zookeeper, не имеют явных функций блокировки и разблокировки. Для пессимистической блокировки необходимо использовать специальный рецепт, однако он вносит дополнительную задержку для подобного рода транзакций (см также: Addressing the ZooKeeper Synchronization Inefficiency).

В связи с этим на сцене появляется иной способ решения задачи.

Оптимистическая блокировка

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

1. Загрузка состояния текущих данных из хранилища.
2. Локальное применение нетривиальной логики и создание набора операций для записи.
3. Атомарная проверка, что никакая другая транзакция не изменила данные, и фиксирование набора операций для записи.
4. Если проверка завершилась неудачно => повторение операций, начиная с первого шага.

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

Однако и эта схема имеет недостатки:

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

Кроме того, для пессимистичной и оптимистичной блокировки мы должны сериализовывать наши внутренние данные в иерархическом пространстве ключей соответствующей системы (например, Zookeeper «znodes» или etcd «nodes»). Все упомянутые факты усложняют разрабатываемое приложение, при этом подход становится подвержен различного рода ошибкам. Поэтому я хотел бы пойти совершенно в другом направлении.

Концепция реплицируемого объекта

К сложному надо подходить просто, иначе мы никогда его не поймём.

Джиджу Кришнамурти

Давайте сделаем шаг назад и вспомним про объектно-ориентированное программирование (ООП). Здесь у нас есть понятие объектов. Каждому такому объекту принадлежат определенные данные, представляющие состояние объекта. При этом объект содержит набор методов, которые преобразует объект из одного состояния в другое.

Таким образом, идея заключается в реплицировании действий (методов объекта) между нодами кластера вместо репликации самих данных (состояния объекта). Эти действия детерминировано изменяют состояние объекта и создают иллюзию того, что реплицируется сам объект. При этом линеаризумость гарантирует, что все реплики принимают одну и ту же последовательность действий, таким образом получая консистентное состояние рассматриваемого распределённого объекта. Это очень похоже на модель репликации конечного автомата. Разница состоит лишь в том, что я использую обычный объект для представления состояния и методы для представления событий, трансформирующих объект. Такое отображение значительно снижает сложность разработки и позволяет использовать мощь языка C++, поскольку он изначально поддерживает использование ООП без раздувания кода.

Свойства реплицируемого объекта

Мой реплицируемый объект (или просто replob) имеет следующие свойства:

1. Встроенный.
2. Без мастера.
3. Хранение в памяти.
4. Линеаризуемая консистентность.
5. FIFO гарантия для процесса.
6. Быстрые локальные чтения.
7. Конкурентные гибкие распределённые транзакции.
8. Поддержка опции независимых параллельных транзакций.
9. Поддержка любых нативных структур данных.
10. Можно настраивать САР.
11. Плавная деградации набора реплик.
12. Безопасность и живучесть при различных сетевых проблемах:
    
    1. Нарушение сетевой связности.
    2. Частичное нарушение сетевой связности типа «мост».
    3. Временная нестабильность сети.
    4. Частичное направление сетевых пакетов.
    
    

Ниже я кратко рассмотрю каждый пункт.

При многословии не миновать греха, а сдерживающий уста свои разумен.

Экклезиаст

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

Без мастера. Алгоритм не имеет выделенного мастера (лидера). Таким образом, каждый узел неотличим друг от друга. Это значительно снижает задержки при восстановлении после сбоев, а также создает более предсказуемое поведение в большинстве случаев.

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

Линеаризуемая консистентность. Алгоритм реплицируемых объектов предоставляет гарантию линеаризуемости операций.

FIFO гарантия для процесса. Для указанного процесса все операции будут завершены в порядке их планирования этим процессом (FIFO-порядок).

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

Конкурентные гибкие распределённые транзакции. Внутри транзакций можно использовать детерминированную последовательность операций любой степени сложности. Такие транзакции обрабатываются конкурентным образом.

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

Поддержка любых нативных структур данных. Разработчик может использовать любые стандартные контейнеры, например std::vector, std::map и т.д., а также boost::optional,boost::variant или другие структуры данных, поддерживающие семантику копирования.

Можно настраивать САР. Пользователь может выбирать между линеаризуемостью и доступностью в случаях нарушения сетевой связности.

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

Безопасность и живучесть при различных сетевых проблемах. Существует немалое количество различных сетевых проблем (см. Aphyr: The network is reliable). При этом алгоритм сохраняет консистентность и работоспособность в указанных случаях.

Все эти пункты будут подробно рассмотрены в последующих статьях.

Примеры

Непобедимым быть можешь, если не вступишь ни в какой бой, в котором победа от тебя не зависит.

Эпиктет

Чтобы продемонстрировать всю гибкость и мощь подхода я рассмотрю достаточно простой пример.

Пример: хранилище типа ключ-значение

Давайте реализуем реплицируемое хранилище со следующим интерфейсом (я опускаю пространства имен std:: и boost:: для краткости):

struct KV
{
    optional<string> get(const string& key) const;
    void set(const string& key, const optional<string>& value);
private:
    unordered_map<string, string> kv_;
};

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

optional<string> KV::get(const string& key) const
{
    if (kv_.count(key) == 0)
        return {};
    return kv_.at(key);
}

void KV::set(const string& key, const optional<string>& value)
{
    if (value)
        kv_[key] = *value;
    else
        kv_.erase(key);
}

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

DECL_REPLOB(KV, get, set)

Hint

Подсказка: реализация DECL_REPLOB такова:

#define DECL_REPLOB    DECL_ADAPTER

И тогда я могу использовать следующую строку кода для репликации моих данных по набору реплик:

replob<KV>().set(string{"hello"}, string{"world!"});

После завершения вызова KV::set все экземпляры типа KV из набора реплик будут содержат указанную пару. Заметьте, что на экземпляр можно ссылаться через тип KV, что означает, что каждая реплика содержит свой собственный единственный экземпляр этого объекта.

Чтобы прочитать данные с линеаризуемым уровнем консистентности, следует написать:

auto world = replob<KV>().get(string{"hello"});

Но чтобы улучшить производительность для этой операции чтения я просто пишу:

auto localWorld = replobLocal<KV>().get(string{"hello"});

Вот так!

Транзакции

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

auto world = replobLocal<KV>().get(string{"hello"}).value_or("world!");
replob<KV>().set(string{"hello"}, "hello " + world);

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

MReplobTransactInstance(KV) {
    auto world = $.get(string{"hello"}).value_or("world!");
    $.set(string{"hello"}, "hello " + world);
};

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

Транзакции с результатами

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

// use local instance because we do not need to update the object
auto valueLength = MReplobTransactLocalInstance(KV) {
    return $.get(string{"hello"}).value_or("").size();
};

Такой же подход можно использовать операции изменения объекта:

auto valueLength = MReplobTransactInstance(KV) {
    auto world = $.get(string{"hello"});
    $.set(string{"another"}, world);
    return world.value_or("").size();
};

Все указанные операции применяются на репликах атомарно.

Транзакции с несколькими replob

Давайте предположим, что у нас есть два независимых экземпляра хранилищ типа ключ-значение: KV1 и KV2. Мы можем объединить операции для разных экземпляров в одну транзакцию, используя модификатор MReplobTransact:

// the first transaction is distributed
// performs value copying from KV2 to KV1 for the same key
MReplobTransact {
    $.instance<KV1>().set(
        string{"hello"},
        $.instance<KV2>().get(string{"hello"}));
};
// the second transaction is applied locally
// returns total value size calculation for the same key
auto totalSize = MReplobTransactLocal {
    auto valueSize = [](auto&& val) {
        return val.value_or("").size();
    };
    return valueSize($.instance<KV1>().get(string{"hello"}))
         + valueSize($.instance<KV2>().get(string{"hello"}));
};

Следует ли мне упомянуть то, что все эти действия выполняются атомарно, при этом первая транзакция является распределённой и выполняется на всех репликах?

Продвинутый пример

Давайте рассмотрим итерацию по коллекции с использование функции, определяемой пользователем:

struct KV
{
    optional<string> get(const string& key) const;
    void set(const string& key, const optional<string>& value);

    // generic method to iterate through the collection
    template<typename F>
    void forEach(F f) const
    {
        for (auto&& v: kv_)
            f(v);
    }

private:
    unordered_map<string, string> kv_;
};

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

auto valuesSize = MReplobTransactLocalInstance(KV) {
    size_t sz = 0;
    $.forEach([&sz](auto&& v) {
        sz += v.second.size();
    });
    return sz;
};

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

Дальнейшие направления

Если вы заранее знаете, к чему вы хотите прийти, то шаги в этом направлении – это совсем не эксперимент.

Джиджу Кришнамурти

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

1. Божественный адаптер.
2. Неблокирующая синхронизация без взаимной блокировки или субъекторная модель.
3. Однородная акторная модель или фунакторная модель.
4. Сверхобобщенная сериализация.
5. Модификаторы поведения.
6. IO и сопрограммы.
7. Консистентность и вопросы применимости CAP теоремы.
8. Phantom, replob и алгоритм консенсуса без мастера.
9. Примеры реализации:
   
   1. Атомарный детектор отказов.
   2. Распределённый планировщик.

Выводы

Зрелость – это переход от опоры на окружающих к опоре на самого себя.

Фредерик Пёрлз

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

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

Хочу выразить отдельное спасибо Sergey Polovko, Yauheni Akhotnikau и Petr Prokhorenkov за полезные комментарии и советы.

Вопросы для самопроверки

Единственная сложность состоит в том, чтобы задать правильный вопрос.

Фредерик Пёрлз

1. Как реализован DECL_REPLOB?
2. В чем разница между локальными и нелокальными операциями?
3. Возможно ли реализовать алгоритм консенсуса без мастера?
4. Укажите все упомянутые в статье модификаторы поведения.

Список литературы

[1] Документация: Zookeeper.
[2] Документация: etcd.
[3] Статья: Zab: High-performance Broadcast For
Primary-Backup Systems
[4] Статья: In Search of an Understandable Consensus Algorithm
(Extended Version)
[5] Документация Zookeeper: Zab vs. Paxos.
[6] Статья: The Chubby Lock Service For Loosely-Coupled Distributed Systems.
[7] Документация MongoDB: How long does replica set failover take?
[8] Aphyr blog: Zookeeper.
[9] Документация: ZooKeeper Recipes and Solutions: Locks.
[10] Статья: Addressing the ZooKeeper Synchronization Inefficiency.
[11] Документация: Zookeeper znodes.
[12] Документация: etcd nodes.
[13] Wikipedia: State Machine Replication.
[14] Aphyr blog: The Network Is Reliable.
[15] Статья: ZooKeeper: Wait-Free Coordination For Internet-Scale Systems.