Multi-Paxos Implementation (RSM)

Наивная реализация алгоритма консенсуса Multi-Paxos на языке Go. Проект создан в образовательных целях для изучения алгоритмов распределенного консенсуса.

Описание

Это экспериментальная реализация алгоритма Multi-Paxos - одного из фундаментальных алгоритмов консенсуса в распределенных системах. Реализация включает в себя основные компоненты:

• Proposer - узел, который предлагает значения для консенсуса
• Acceptor - узел, который принимает или отклоняет предложения
• Log - структура для хранения принятых значений
• Service - сервисный слой для управления процессом консенсуса

⚠️ Внимание: Данная реализация имеет множество недостатков и не предназначена для использования в продакшене. Она создана исключительно для изучения принципов работы алгоритма.

Архитектура проекта

rsm/
├── cmd/
│   └── main.go              # Точка входа в приложение
├── internal/
│   ├── entities/            # Основные сущности
│   │   ├── accepter.go      # Реализация Acceptor
│   │   ├── proposer.go      # Реализация Proposer
│   │   └── log.go           # Структура лога
│   └── service/             # Сервисный слой
│       ├── service.go       # Основной сервис
│       └── proposer.go      # Сервис для работы с Proposer
├── go.mod                   # Go модуль
└── go.sum                   # Зависимости

Как попробовать

Установка и запуск

1. Клонируйте репозиторий:

   git clone https://github.com/Murolando/m_rsm.git
   cd m_rsm/rsm

2. Установите зависимости:

   go mod download

3. Запустите приложение:

   go run cmd/main.go

Что происходит при запуске

При запуске программы создается:

1. 5 Acceptor'ов с ID от 1 до 5
2. 2 Proposer'а с ID 0 и 1
3. Запускается несколько горутин, которые параллельно предлагают различные значения:
   • "murolando"
   • "ninja"
   • "alexyB"
   • "oleg"
   • "joomba"

Программа демонстрирует работу алгоритма консенсуса в условиях конкурентного доступа нескольких proposer'ов.

Общая структура алгоритма

Фаза Prepare

1. Proposer генерирует уникальный номер ballot
2. Отправляет Prepare сообщения всем Acceptor'ам
3. Acceptor'ы отвечают Promise, если номер больше уже обещанного

Фаза Accept

1. При получении кворума Promise, Proposer отправляет Accept
2. Acceptor'ы принимают значение, если номер не меньше обещанного
3. При получении кворума Accept значение считается принятым

p.s Версия которая представлена тут, работает несколько иначе, например проблема восстановления лога решается с помощью полной ее репликации при проталкивании значения, что супер неотпимально, но мне все равно

Полезные ссылки

Материалы, использованные при разработке:

• Реализация Paxos на Go: создаем алгоритм консенсуса без готовых решений
• Multi-Paxos Algorithm
• Research Paper on Multi-Paxos