Я реализовал алгоритм консенсуса Raft (хрестоматийный пример распределённого алгоритма) на Python. Реализация получилась довольно плохой! Но при этом (в какой-то мере) корректной.
Вот несколько заметок, которыми я хотел бы поделиться со всеми, кому интересно взяться за похожую задачу.
Оглядываясь назад, я считаю эти материалы самыми полезными для изучения Raft и его корректной реализации.
- Статья о Raft (прочитайте до раздела 5 и почаще сверяйтесь с рисунком 2)
- Руководство по Raft для студентов
- одна из самых распространённых реализаций Raft
- клонируйте репозиторий, бегло просмотрите
raft.goи в диалоге с LLM разберитесь в кодовой базе и принятых проектных решениях
- клонируйте репозиторий, бегло просмотрите
- Серия статей в блоге Эли Бендерски
Я бы посоветовал сначала потратить около часа на чтение статьи, а затем набросать код UDP- или TCP-сервера, который считывает входящие байты и добавляет их в массив. Затем я следовал примеру реализации Эли, добавляя возможности в свою реализацию Raft в том же порядке.
Когда у меня заработало что-то похожее на выборы лидера, я начал искать баги в коде и ошибки в своём понимании алгоритма. Я попеременно обращался к руководству для студентов, рисунку 2 в статье о Raft и своей реализации, внимательно разбираясь, в чём моя реализация совпадает с описанием (или отличается от него). Я также активно использовал LLM для проверки этого кода, добавляя в контекст материалы из перечисленных выше источников.
Повторите этот процесс для репликации журнала, сохранения состояния и т. д.
о реализации
В своей реализации я принял несколько проектных решений для упрощения задачи. В произвольном порядке:
- каждый узел работает и обрабатывает сообщения в одном потоке
- использовать «логические часы» для отслеживания локального «времени» в системе (например, вызывать
tick()и увеличивать собственный счётчик каждого узла вместо использования системного времени) - «свалить всё в кучу» в реализации, поместив всё в один файл, например разбор сетевых сообщений, хранение/сохранение состояния, основной алгоритм Raft и утилиты/команды для управления самим узлом
Решение 2 кажется разумным и корректным (логические часы используются в реализации etcd). Решение 3, пожалуй, лучше подходит для обучения/преподавания. Удобно, когда всё находится в одном файле и можно видеть всё сразу; к тому же такую реализацию удобно перекраивать, чтобы понять, какие абстракции лучше всего подходят алгоритму.
По-моему, решение 1 — уже немного перебор. Оно действительно сильно упрощает реализацию (меньше приходится думать о взаимных блокировках и атомарных обновлениях внутреннего состояния узла), но в итоге получается не совсем Raft. Для первой реализации это кажется вполне допустимым. Алгоритм достаточно сложен, и, думаю, лучше потратить время на отладку логических ошибок в самом алгоритме Raft, чем возиться с мьютексами.
Я бы рассматривал реализацию Raft таким способом как проект на ~30 часов. На первое прочтение статьи о Raft и ознакомление с сопутствующими материалами должно уйти несколько часов. Основную часть кода я написал за ~3 дня во время праздников, работая по 6–8 часов в день. В текущей реализации мне ещё есть что доработать и улучшить (например, исправить несколько неочевидных багов), и на это может уйти ещё полдня.
В целом, не так уж плохо для того, чтобы разобраться в одном из ключевых алгоритмов, который лежит в основе стольких инфраструктурных систем.