Кратко про Raft и Paxos: путь к надежным распределенным базам данных

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

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

Среди множества подходов к решению проблемы достижения консенсуса в распределенных системах, Paxos и Raft являются самыми эффективными. Рассмотрим их подробней.

Алгоритм Paxos

Алгоритм Paxos был разработан Лесли Лэмпортом в конце 20-го века.

История Paxos начинается с попытки Лэмпорта создать алгоритм, который мог бы гарантировать согласованность данных в распределенной системе, несмотря на отказы отдельных компонентов. Вдохновение для названия и некоторых концепций алгоритма Лэмпорт черпал из метафорической истории о фиктивном парламенте на острове Paxos в Греции, где делегаты должны были достигать согласия по различным вопросам, несмотря на сложности с коммуникацией.

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

Фаза предложения (Proposal)

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

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

Фаза подтверждения (Acceptance)

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

1. Если акцептор уже обещал поддержать предложение с более высоким номером, он не может поддержать текущее предложение.

2. Предложение считается принятым, только если большинство акцепторов согласны его поддержать.

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

Примеры

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

В основе механизма согласованности Spanner лежит алгоритм TrueTime, который использует Paxos для репликации данных между различными географическими регионами. Paxos здесь применяется для обеспечения того, чтобы все изменения данных были согласованно применены на всех репликах.

Chubby Lock Service — это распределенная система управления блокировками и хранения небольших объемов данных, разработанная в Google для внутреннего использования. Chubby предоставляет координационные примитивы, такие как блокировки и условные переменные, которые используются различными распределенными системами внутри Google. Основная задача Chubby — обеспечить хранение метаданных и управление блокировками в среде, где узлы могут выходить из строя, а сетевые разделения не являются редкостью. Paxos используется в Chubby также для достижения консенсуса между репликами

Алгоритм Raft

Raft был создан с целью быть более понятным и легким в реализации по сравнению с его предшественником, Paxos.

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

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

Когда узлы теряют связь с лидером, они могут инициировать выборы для выбора нового лидера.

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

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

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

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

Если лидер теряет связь с большинством узлов, он перестает быть лидером, и начинаются новые выборы. Узлы, которые не могут связаться с лидером или другими узлами, могут стать изолированными и перейти в состояние кандидата, пытаясь инициировать новые выборы.

Примеры

etcd — это распределенная система управления конфигурацией, которая дает согласованное хранение ключ-значение для настройки распределенных систем. etcd использует Raft.

На go написать и затем прочитать значение из etcd можно так:

package main

import (
    "context"
    "log"
    "time"
    "go.etcd.io/etcd/client/v3"
)

func main() {
    cli, err := clientv3.New(clientv3.Config{
        Endpoints:   []string{"localhost:2379"},
        DialTimeout: 5 * time.Second,
    })
    if err != nil {
        log.Fatalf("Failed to connect to etcd: %v", err)
    }
    defer cli.Close()

    // запись значения
    ctx, cancel := context.WithTimeout(context.Background(), time.Second)
    _, err = cli.Put(ctx, "mykey", "myvalue")
    cancel()
    if err != nil {
        log.Fatalf("Failed to write to etcd: %v", err)
    }

    // чтение значения
    ctx, cancel = context.WithTimeout(context.Background(), time.Second)
    resp, err := cli.Get(ctx, "mykey")
    cancel()
    if err != nil {
        log.Fatalf("Failed to read from etcd: %v", err)
    }
    for _, ev := range resp.Kvs {
        log.Printf("%s: %s\n", ev.Key, ev.Value)
    }
}

Код подключается к etcd, записывает пару ключ-значение ("mykey": "myvalue") и затем считывает значение по ключу "mykey", выводя его в лог.

CockroachDB — это распределенная SQL база данных, которая использует Raft для репликации данных между узлами и обеспечения согласованности транзакций. В CockroachDB каждая запись данных принадлежит к определенному диапазону, и Raft используется для управления репликацией этих диапазонов данных.

Сравнение алгоритмов

Paxos заложил фундамент для понимания основ надежности и согласованности в распределенных системах. Однако его сложность и абстрактность стали проблемой и это вызвало появление Raft, который предлагает более интуитивно понятный и структурированный подход к консенсусу.

Статья подготовлена в преддверии старта курса "Базы данных". Узнать подробнее о курсе.