Напишите свой первый распределенный магазин KV на Raft для Java

Raft

предисловие

Цель этой статьи — описать, как использовать язык Java для реализации проекта распределенного хранилища со структурой KV на основе алгоритма Raft. Предыстория этого проекта заключается в глубоком понимании алгоритма Raft, чтобы глубоко понять, как добиться строгой согласованности данных в распределенной среде; цель этого проекта: в сложной распределенной среде несколько узлов хранения могут обеспечить надежную согласованность данных. . . .

адрес проекта:GitHub.com/state is0/way…

Добро пожаловать звезда :)

Что такое распределенное хранилище KV Raft для Java

Большинство людей уже понимают алгоритм Raft, и существует множество реализаций.Из GitHub кажется, что язык Golang реализует все более и более известные, такие как etcd. Для версии Java меньше реализаций для крупномасштабного использования в производственных средах;

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

Отличие Zookeeper в том, что ZK часто используется как служба именования, но это скорее координатор распределенной службы.

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

обратно к нам.

На этот раз наша языковая часть использует Java, фреймворк сетевого взаимодействия RPC использует Ant Financial SOFA-Bolt, базовое хранилище KV использует RocksDB, а ядро ​​Raft реализуется нами (если мы не реализуем его сами, то этот проект бессмысленен. ). Обратите внимание, что этот проект принесет в жертву некоторую производительность и удобство использования в погоне за максимально возможной согласованностью.

Зачем изобретать велосипед

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

Обычно есть 2 ответа:

  1. Если это служба без сохранения состояния, это не повлияет на использование.
  2. Если это служба с отслеживанием состояния, вы можете сохранить состояние в другом месте, например в Redis. Что делать, если Redis зависает? Потом поставить в ЗК.

Многие промежуточные программы будут использовать ZK для обеспечения согласованного состояния, например codis, kafka. Потому что использование ZK может сэкономить нам много времени. Но иногда пользователи промежуточного ПО считают, что внедрение стороннего промежуточного ПО затруднительно, поэтому разработчики промежуточного ПО пытаются добиться согласованности самостоятельно, например Redis Cluster, TiDB и т. д.

Обычно, если вы реализуете его самостоятельно, вы будете использовать алгоритм Raft.Некоторые люди спрашивают, почему бы не использовать «более мощный» алгоритм paxos? Извините, это немного сложно, по крайней мере, с открытым исходным кодом, масштабное использование алгоритма paxos в производственной среде еще не появилось, я слышал только о внутренней реализации Google или alibaba, как это выглядит, мы не обсуждать это здесь.

Вернемся к нашей теме, зачем изобретать велосипед? Ответ с 3 аспектов:

  1. Иногда ZK и etcd не могут решить наши проблемы, или, как упоминалось выше, внедрение другого промежуточного программного обеспечения слишком проблематично и тяжело для развертывания.
  2. Совершенно любопытно, почему Raft гарантирует согласованность (на это обычно можно ответить множеством статей)? Но как именно?
  3. Требования к распределенной разработке. Как программист, разрабатывающий распределенную систему, если вы сможете глубже понять основной алгоритм распределенной системы, это будет очень полезно для разумного проектирования распределенной системы.

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

Теоретическая основа Raft перед написанием

Любая практика – это прежде всего теория. Если вы уже хорошо знакомы с теорией Raft, вы можете пропустить этот раздел и сразу перейти к шагам реализации.

Рафт делит алгоритм на 4 части для понятности алгоритма.

  1. выборы лидера
  2. репликация журнала
  3. Изменение членства
  4. сжатие журнала

Как и zk, требуется лидер, и все операции записи инициируются лидером, чтобы гарантировать, что поток данных достаточно прост. Лидер выбирается путем сравнения логического времени (терма) размера каждого узла и размера лог-индекса (индекса).

Я только что сказал, что выбор лидера включает подписку на журналы, а затем будет обсуждаться репликация журналов. Можно сказать, что репликация журналов является ядром ядра Raft.Проще говоря, Raft обеспечивает согласованность журналов между несколькими узлами. Когда журналы непротиворечивы, мы можем думать, что состояние всей системы согласовано. Вы можете понять этот журнал как binlog mysql.

Raft обеспечивает корректность репликации логов с помощью различных патчей.

Узел-лидер Raft инкапсулирует запрос клиента в журнал и отправляет его каждому подписчику. Если более половины подписчиков в кластере ответят успешно, журнал может быть отправлен (зафиксирован). Эту фиксацию можно понимать как D КИСЛОТЫ, то есть Стойкости. Когда журнал сохраняется на диск, все остальное просто.

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

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

Выше приведено краткое описание алгоритма Raft. Дополнительные статьи об алгоритме Raft см. в других статьях в моем блоге (включая официальные версии статей, PPT, анимацию и другие статьи блога), адрес блога:thinkinjava.cn

шаги для достижения

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

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

Технический отбор:

  • Модуль согласованности является основной реализацией алгоритма Raft.Благодаря модулю согласованности гарантируется согласованность данных узлов кластера Raft.Здесь нам нужно реализовать это самостоятельно согласно описанию бумаги.
  • Для связи RPC можно использовать короткие соединения HTTP или длинные соединения TCP.Учитывая, что каждый узел в кластере обменивается данными часто, а узлы обычно находятся в локальной сети, мы выбираем длинные соединения TCP. Фреймворк длинных соединений Java-сообщества предпочитает Netty, здесь мы выбираем фреймворк сетевого взаимодействия SOFA-Bolt (на основе Netty) Ant Financial, который удобен для быстрой разработки.
  • Модуль журнала, в алгоритме Raft реализация журнала является основой.Учитывая фактор времени, мы выбрали RocksDB в качестве хранилища журнала.
  • Конечный автомат может быть любой реализацией, и его суть заключается в обработке содержимого лога. Это можно понимать как конкретные данные в бинарном журнале Mysql. Поскольку мы хотим реализовать хранилище KV, мы можем напрямую использовать компонент RocksDB модуля журнала.

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

Дизайн интерфейса:

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

  1. Консенсус, интерфейс модуля согласованности
  2. LogModule, интерфейс модуля журнала
  3. StateMachine, интерфейс конечного автомата
  4. RpcServer и RpcClient, интерфейс RPC
  5. Node, в то же время, чтобы агрегировать вышеперечисленные интерфейсы, нам нужно определить интерфейс Node, то есть узел, машинный узел, абстрагированный Raft.
  6. LifeCycle, Наконец, нам нужно управлять жизненным циклом вышеперечисленных компонентов, поэтому нам нужен интерфейс LifeCycle.

Далее нам нужно подробно определить основной интерфейс Consensus. Мы определяем 2 основных интерфейса в соответствии с документом:

   /**
     * 请求投票 RPC
     *
     * 接收者实现：
     *
     *      如果term < currentTerm返回 false （5.2 节）
     *      如果 votedFor 为空或者就是 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他（5.2 节，5.4 节）
     */
    RvoteResult requestVote(RvoteParam param);

    /**
     * 附加日志(多个日志,为了提高效率) RPC
     *
     * 接收者实现：
     *
     *    如果 term < currentTerm 就返回 false （5.1 节）
     *    如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false （5.3 节）
     *    如果已经存在的日志条目和新的产生冲突（索引值相同但是任期号不同），删除这一条和之后所有的 （5.3 节）
     *    附加任何在已有的日志中不存在的条目
     *    如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个
     */
    AentryResult appendEntries(AentryParam param);

Запросить голосование и прикрепить лог. Это основная функция нашего узла Raft, выбор лидера и репликация журнала. Реализация этих двух интерфейсов является сутью Raft.

Затем посмотрите на интерфейс LogModule. Это бесплатная игра. Учитывая характеристики журнала, я определил следующие интерфейсы:

void write(LogEntry logEntry);

LogEntry read(Long index);

void removeOnStartIndex(Long startIndex);

LogEntry getLast();

Long getLastIndex();

Это запись, чтение, удаление и, наконец, два интерфейса о Last.В Raft Last — очень критическая вещь, поэтому я определил здесь два метода, хотя они выглядят не очень :)

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

    /**
     * 将数据应用到状态机.
     *
     * 原则上,只需这一个方法(apply). 其他的方法是为了更方便的使用状态机.
     * @param logEntry 日志中的数据.
     */
    void apply(LogEntry logEntry);

    LogEntry get(String key);

    String getString(String key);

    void setString(String key, String value);

    void delString(String... key);

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

RpcClient и RPCServer ничего не говорят, они фактически отправляют и получают.

Затем есть интерфейс Node. Интерфейс Node также не определен Raft. Мы определяем несколько интерфейсов на основе нашего собственного понимания:


    /**
     * 设置配置文件.
     *
     * @param config
     */
    void setConfig(NodeConfig config);

    /**
     * 处理请求投票 RPC.
     *
     * @param param
     * @return
     */
    RvoteResult handlerRequestVote(RvoteParam param);

    /**
     * 处理附加日志请求.
     *
     * @param param
     * @return
     */
    AentryResult handlerAppendEntries(AentryParam param);

    /**
     * 处理客户端请求.
     *
     * @param request
     * @return
     */
    ClientKVAck handlerClientRequest(ClientKVReq request);

    /**
     * 转发给 leader 节点.
     * @param request
     * @return
     */
    ClientKVAck redirect(ClientKVReq request);

Во-первых, узлу обязательно нужен конфигурационный файл, поэтому есть интерфейс setConfig, Затем нужно обработать "голосование по запросам" и "дополнительные логи" При этом также необходимо принимать запросы от пользователей, то есть клиентов (откуда еще берутся данные?), поэтому есть обработчик ClientRequest Наконец, учитывая гибкость, мы позволяем каждому узлу получать запрос клиента, но узел-последователь не может обработать запрос, поэтому его необходимо перенаправить на ведущий узел, поэтому нам нужен интерфейс перенаправления.

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

    void init() throws Throwable;

    void destroy() throws Throwable;

Что ж, базовый интерфейс определен, а реализация позади. Реализация является ключевым моментом.

Осуществление выборов лидера

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

  1. Избиратель не должен быть лидером.
  2. Это должно быть тайм-аут перед выборами. Конкретное время тайм-аута зависит от вашего дизайна. Обратите внимание, что время тайм-аута для каждого узла не может быть одинаковым, и следует использовать случайный алгоритм для разнесения (ключевая реализация Raft), чтобы избежать ненужных взаимоблокировок. .
  3. Избиратели сначала избирают себя и превращаются в кандидатов.
  4. Первым шагом на выборах является добавление одного кандидата к вашему сроку.
  5. Затем отправьте запрос на голосование RPC, как и другие узлы, и параметры запроса относятся к статье, включая его собственный термин, его собственный lastIndex и lastTerm журнала. В то же время RPC для голосования по запросу должны запрашиваться параллельно.
  6. Должен быть контроль тайм-аута ожидания результата голосования, если таймаут истечет, ждать не будет.
  7. Наконец, если более половины ответов успешны, то он должен немедленно стать лидером и отправить пульс, чтобы предотвратить другие выборы.
  8. В случае неудачи требуются новые выборы. Обратите внимание, что в течение этого периода, если другие узлы отправляют пульсации, они также должны немедленно стать подписчиками, иначе возникнет бесконечный цикл.

Конкретные коды см.GitHub.com/state is0/way…

Вышеупомянутое на самом деле является реализацией запрашивающего в выборах Лидера, так как же это понимает получатель? После того, как получатель получит RPC «запрос на голосование», ему необходимо сделать следующее:

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

Конкретные коды см.GitHub.com/state is0/way…

На данный момент логика лидера лидера RATP может быть в основном реализована.

Обратите внимание, что такие параметры, как LastIndex, о которых мы упоминали выше, еще не реализованы, но это не влияет на то, что мы пишем псевдокод, ведь репликация логов гораздо сложнее, чем выбор лидера, наш принцип — от простого к сложному. :)

Реализация репликации логов

Репликация журналов лежит в основе реализации согласованности Raft.

Существует две формы репликации журнала: один пульсирующий, а другой реальный журнал.Содержимое журнала пульса пусто, а остальные части в основном одинаковы.То есть, когда получатель получает журнал, если он находит, что он пуст, Тогда он сердцебиение.

сердцебиение

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

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

Проверьте конкретный код:GitHub.com/state is0/way…

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

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

Конкретные коды см.GitHub.com/state is0/way…

После разговора о сердцебиении, давайте поговорим о добавлении реального журнала.

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

Таким образом, ведущий узел будет иметь интерфейс ClientKVAck handlerClientRequest(ClientKVReq request) для получения данных KV пользователя, и в то же время он будет параллельно реплицировать данные на другие узлы. Конкретные шаги следующие:

  1. Каждый узел может получить запрос клиента, но только лидер может его обработать, поэтому, если это не лидер, его нужно перенаправить лидеру.
  2. Затем инкапсулируйте данные KV пользователя в структуру журнала, включая термин, индекс, команду, и предварительно отправьте их на локальный сервер.
  3. Параллельная отправка данных на другие узлы, то есть репликация журнала.
  4. Если более половины узлов успешно возвращаются в течение указанного времени, отправьте этот журнал.
  5. Наконец, обновите ваш commitIndex, lastApplied и другую информацию.

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

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

Конкретные коды см.GitHub.com/state is0/way…

Давайте посмотрим на этапы реализации приемника логов:

  1. Как и сердцебиение, вы должны сначала проверить термин другой стороны.Если термин неверен, то нечего сказать.
  2. Если лог не совпадает, то вернитесь к ведущему, сообщите ему, уменьшите nextIndex и повторите попытку.
  3. Если локально существующий журнал конфликтует с журналом лидера, журнал лидера имеет преимущественную силу, а его собственный журнал будет удален.
  4. Наконец, примените журнал к машине состояний, обновите локальный индекс фиксации и успешно верните лидера.

Конкретные коды см.GitHub.com/state is0/way…

На этом часть репликации журнала завершена.

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

Проверьте «Выборы лидера» и «Репликация журнала».

После написания программы, как проверить, правильно ли она?

Конечно, написать программу проверки.

Сначала мы проверяем «Выборы Лидера». На самом деле это лучший тест.
  1. Настройте 5 элементов запуска приложения в идее, настройте основной класс как класс RaftNodeBootStrap, добавьте -DserverPort=8775 -DserverPort=8776 -DserverPort=8777 -DserverPort=8778 -DserverPort=8779 Конфигурация системы, представляющая 5 машинных узлов в распределенной среде.
  2. Запустите последовательно пять узлов RaftNodeBootStrap, порты 8775, 8776, 8777, 8778, 8779.
  3. Наблюдайте за консолью.Примерно через 6 секунд произойдет событие выбора.В это время будет сгенерирован лидер.Лидер немедленно отправит сердцебиение, чтобы сохранить свою позицию.
  4. Если порт лидера 8775, используйте идею, чтобы закрыть порт 8775, и смоделированный узел зависнет. Примерно через 15 секунд выборы будут перезапущены, а в оставшихся 4 узлах будет сгенерирован новый лидер. журналы.

Затем проверьте репликацию журнала, которая делится на 2 случая:

при нормальных условиях
  1. Настройте 5 элементов запуска приложения в идее, настройте основной класс как класс RaftNodeBootStrap, добавьте -DserverPort=8775 -DserverPort=8776 -DserverPort=8777 -DserverPort=8778 -DserverPort=8779
  2. Запустите последовательно пять узлов RaftNodeBootStrap, порты 8775, 8776, 8777, 8778, 8779.
  3. Запишите данные kv с помощью клиента.
  4. Уничтожьте все узлы, используйте тест junit, чтобы прочитать значение каждой базы данных rockDB и убедиться, что данные каждого узла непротиворечивы.
в ненормальном состоянии
  1. Настройте 5 элементов запуска приложения в идее, настройте основной класс как класс RaftNodeBootStrap, добавьте -DserverPort=8775 -DserverPort=8776 -DserverPort=8777 -DserverPort=8778 -DserverPort=8779
  2. Запустите последовательно пять узлов RaftNodeBootStrap, порты 8775, 8776, 8777, 8778, 8779.
  3. Запишите данные kv с помощью клиента.
  4. Убейте лидера (скажем, 8775).
  5. Запишите данные еще раз.
  6. Перезагрузите 8775.
  7. Закройте все узлы и прочитайте RocksDB, чтобы проверить согласованность данных.

Summary

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

Java-код проекта составляет около 2500 строк, а основной код оценивается более чем в 1000 строк. Вы даже можете сказать, что это игрушечный код, но я верю тому, что сказал мастер Би Сюань, после того, как игрушечный код будет оптимизирован, его также можно превратить в код, который может действительно надежно работать в коммерческой системе (привет java.info/?afraid=508):)

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

Я могу рассказать о нем немного.После написания проекта Lu-RPC я получил задание разработать каркас токоограничивающего выключателя, работающего в производственной среде.В это время опыт разработки Lu-RPC сделал меня более спокойно при разработке фреймворка.и свободно :)

Возвращаясь к Raft, хотя приведенные выше тестовые примеры были запущены и программа неоднократно тестировалась, это не означает, что программа верна на 100%, особенно в сложной распределенной среде. Если вам интересен Raft, добро пожаловать на общение :)

адрес проекта:GitHub.com/state is0/way…

Категории