Привет Хабр!

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

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

Алгоритм Паксоса

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

Лесли Лэмпорт

Лесли Лэмпорт

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

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

Этап предложения

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

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

Этап приемки

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

  1. Если принимающая сторона уже пообещала поддержать предложение с наибольшим номером, она не может поддержать текущее предложение.

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

ЧИТАТЬ   Google Now поддерживает еще 25 стран с новой политикой возврата структурированных данных

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

Источник: https://www.scylladb.com/

Источник: https://www.scylladb.com/

Примеры

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

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

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

Алгоритм Рафта

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

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

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

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

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

ЧИТАТЬ   Юморист, переехавший в Москву из Армении, раскрыл отношение к нему родных

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

Источник https://www.scylladb.com/

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

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

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

Примеры

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

Продолжайте, напишите, а затем прочитайте значение 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"опубликовав его в газете.

ЧИТАТЬ   Доллар, подожди: рубль снова падает — почему так происходит и что делать со сбережениями

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

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

Критерии

Паксос

Плот

Цель

Обеспечение консенсуса в высоконадежных распределенных системах.

Упростите процесс достижения консенсуса и упростите его понимание и реализацию.

Сложность понимания

Высокий. Паксос известен своей теоретической сложностью и абстракцией.

Слабый. Raft сделан более понятным и доступным.

Структура управления

Скрытый. Лидерство не является центральной частью алгоритма, хотя в целом его можно реализовать.

Явный. Raft построен на концепции лидера, что упрощает управление и воспроизводство.

Избирательный процесс

Не определено в базовом алгоритме

Четко определенный процесс с периодами выборов и временем ожидания

Репликация данных

На основе предложения и принятия «предложений» между узлами.

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

Управление отказами

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

Встроенная поддержка обработки сбоев и автоматического переизбрания лидера.

Приложение

SHU используется в теоретических исследованиях и некоторых специализированных реализациях.

Используется в практических распределенных системах, таких как etcd, CockroachDB.

Простота реализации

Сложно реализовать из-за абстрактности и сложности алгоритма.

Легче реализовать из-за структуры и документации.


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

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

Source

От admin