Привет, Хабр!

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

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

Основы Paxos

Задача Paxos — получить согласие всех участников на предложенное значение. Это достигается за счёт трёх фаз:

1. Фаза подготовки (Prepare phase): предложитель посылает запросы другим узлам (акцепторам), чтобы те подтвердили готовность принять его предложение. Запросы содержат номер предложения. Если акцептор не встречал предложение с таким номером, он говорит «Да», готов принять это предложение.

2. Фаза предложения (Propose phase): после того как большинство акцепторов подготовилось, предложитель отправляет окончательное предложение с номером и значением. Акцепторы принимают его, если они не отклонили более раннее предложение с таким номером.

3. Фаза обучения (Learn phase): когда предложение принято большинством, обучающие узнают об этом решении.

Реализация

Для начала подготовим проект. Запускаем терминал и создаём структуру каталогов.

mkdir paxos-go
cd paxos-go
go mod init paxos-go

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

paxos-go/
├── main.go
├── paxos/
│   ├── acceptor.go
│   ├── proposer.go
│   └── learner.go
└── README.md

Теперь есть проект, и можно переходить к реализации самих компонентов.

Начнём с Acceptor. Задача акцептора — быть строгим и честным, принимать предложения или отклонять их. Всё на самом деле не так сложно. Просто решаем, какой номер предложения можем принять, а какой нет.

// paxos/acceptor.go
package paxos

import (
    "fmt"
    "sync"
)

type Acceptor struct {
    mu        sync.Mutex
    promised  int
    accepted  int
    value     interface{}
}

func NewAcceptor() *Acceptor {
    return &Acceptor{}
}

func (a *Acceptor) Prepare(n int) (int, interface{}) {
    a.mu.Lock()
    defer a.mu.Unlock()
    if n > a.promised {
        a.promised = n
        return a.accepted, a.value
    }
    return -1, nil
}

func (a *Acceptor) Accept(n int, v interface{}) bool {
    a.mu.Lock()
    defer a.mu.Unlock()
    if n >= a.promised {
        a.accepted = n
        a.value = v
        return true
    }
    return false
}

Здесь мы просто проверяем, был ли уже принят номер предложения больше, чем тот, что мы пытаемся предложить. Если да — отклоняем. Если нет — принимаем.

Теперь идём дальше. Реализуем Proposer, который отправляет свои предложения акцепторам. Важно, что предложители не могут просто так предложить значение. Они должны сначала убедиться, что все акцепторы готовы принять это предложение. И только после этого можно переходить к финишной прямой.

// paxos/proposer.go
package paxos

import (
    "fmt"
    "sync"
)

type Proposer struct {
    mu        sync.Mutex
    id        int
    value     interface{}
    quorum    int
    acceptors []*Acceptor
}

func NewProposer(id int, value interface{}, quorum int, acceptors []*Acceptor) *Proposer {
    return &Proposer{id: id, value: value, quorum: quorum, acceptors: acceptors}
}

func (p *Proposer) Propose() bool {
    p.mu.Lock()
    defer p.mu.Unlock()

    // Фаза 1: Prepare
    promises := 0
    for _, a := range p.acceptors {
        if _, v := a.Prepare(p.id); v != nil {
            promises++
        }
    }

    if promises < p.quorum {
        return false
    }

    // Фаза 2: Accept
    accepted := 0
    for _, a := range p.acceptors {
        if a.Accept(p.id, p.value) {
            accepted++
        }
    }

    return accepted >= p.quorum
}

Предложитель сначала проходит через фазы подготовки, собирает обещания, а потом — если всё ок — просит акцепторов принять его предложение.

Ну и, конечно, Learner. Это компонент, который просто должен «узнать» результат. Он не участвует в процессе согласования, но важно, чтобы все обучающие узлы получили информацию о принятом значении.

// paxos/learner.go
package paxos

import (
    "fmt"
    "sync"
)

type Learner struct {
    mu     sync.Mutex
    value  interface{}
    accepted int
}

func NewLearner() *Learner {
    return &Learner{}
}

func (l *Learner) Learn(a *Acceptor) {
    l.mu.Lock()
    defer l.mu.Unlock()
    if a.accepted > l.accepted {
        l.accepted = a.accepted
        l.value = a.value
    }
}

func (l *Learner) GetValue() interface{} {
    l.mu.Lock()
    defer l.mu.Unlock()
    return l.value
}

Теперь можно запускать:

// main.go
package main

import (
    "fmt"
    "paxos-go/paxos"
    "sync"
)

func main() {
    // Создаём приёмников
    acceptors := []*paxos.Acceptor{
        paxos.NewAcceptor(),
        paxos.NewAcceptor(),
        paxos.NewAcceptor(),
    }

    // Создаём обучающего
    learner := paxos.NewLearner()

    // Создаём предложителя
    proposer := paxos.NewProposer(1, "Hello, Paxos!", 2, acceptors)

    // Предлагаем значение
    if proposer.Propose() {
        fmt.Println("Значение принято!")
    } else {
        fmt.Println("Не удалось достичь консенсуса.")
    }

    // Обучаем
    for _, a := range acceptors {
        learner.Learn(a)
    }

    // Получаем значение
    value := learner.GetValue()
    fmt.Printf("Принятое значение: %v\n", value)
}

Запускаем это:

go run main.go

Процесс будет следующим:

В начале создаются три акцептора с помощью paxos.NewAcceptor(). Эти узлы будут участвовать в процессе согласования и принимать или отклонять предложения, в зависимости от их состояния.

После чего создается объект learner, который будет следить за принятыми значениями и в конечном итоге «учить» себя тому, какое решение было выбрано большинством акцепторов.

Далее создается предложитель proposer с id = 1 и значением "Hello, Paxos!", который пытается предложить это значение акцепторам. При этом предложитель требует, чтобы минимум два акцептора (это определяется переменной quorum) согласились на предложение, чтобы оно считалось принятым.

Запуск процесса предложения:

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

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

Если предложитель успешно получает нужное количество согласий на своё предложение, то выводится сообщение "Значение принято!". В противном случае — "Не удалось достичь консенсуса."

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

В завершение, обучающий узел получает окончательное принятые значение и выводит его на экран.

Если все прошло успешно и консенсус был достигнут, то можно увидить следующий вывод:

Значение принято!
Принятое значение: Hello, Paxos!

Если по каким-то причинам не удалось достичь консенсуса, например, из-за недостаточного количества акцепторов, которые согласились, результат будет следующим:

Не удалось достичь консенсуса.

Больше про языки программирования эксперты OTUS рассказывают в рамках практических онлайн-курсов. С полным каталогом курсов можно ознакомиться по ссылке.

Всех разработчиков на Go приглашаем на открытые уроки января:

13 января: «Индивидуальный план развития Go-инженера от Junior до Middle». Записаться
22 января: «Кошелек или жизнь? Фича или баг? Хелсчеки в k8s». Записаться