В распределенной системе из-за различных причин, таких как отказ узла, задержка сети и т. д., в соответствии с теорией CAP мы можем гарантировать толькоНепротиворечивость, доступность, устойчивость к разделамдва из.
Для систем, требующих высокой согласованности, таких как банковские кассовые аппараты, они предпочтут пожертвовать доступностью и отказаться от обслуживания в случае сбоя. MongoDB, Redis, MapReduce используют эту схему.
Для статических веб-сайтов и баз данных запросов со слабой производительностью в режиме реального времени согласованность будет принесена в жертву, а несогласованность будет разрешена в течение определенного периода времени. По этой схеме используется простой распределенный протокол Gossip, база данных CouchDB, Cassandra.
фигура 1
Как показано на рис. 1, проблему непротиворечивости можно разделить на две категории в зависимости от наличия вредоносных узлов. Злонамеренный узел означает, что узел потеряет, повторно отправит и не ответит на сообщение, но не будет подделывать сообщение. Злоумышленники могут подделывать сообщения. Проблема вредоносных узлов называется проблемой византийских генералов и выходит за рамки сегодняшнего обсуждения. Paxos хорошо решает проблему распределенной согласованности вредоносных узлов.
задний план
В 1990 году Лесли Лэмпорт предложил алгоритм Паксоса в статье «Парламент неполный рабочий день». Из-за того, что в статье используются истории без математических доказательств, поначалу она не привлекла особого внимания. Бумага не была официально принята до 1998 года. Позже, в 2001 году, Лэмпорт реорганизовал газету и опубликовал"Паксос - это просто". Как один из первых разработчиков распределенных систем, Лэмпорт получил премию Тьюринга 2013 года.
Алгоритм Paxos широко используется в распределенных системах.Майк Барроуз, автор Google Chubby, сказал: «Существует только один согласованный протокол, и это Paxos».
Более поздний алгоритм Raft, упрощение и улучшение Paxos, стал проще для понимания и реализации.
Паксос тип
Изначально Паксос был островом в вымышленной истории, где парламент проголосовал за достижение консенсуса. Но депутаты могут уйти, мессенджеры могут потеряться или сообщения могут повторяться. Соответствует отказам узлов и отказам сети распределенных систем.
фигура 2
Как показано на рисунке 2, предположим, что конгрессмен хочет предложить, что съесть на обед. Если один или несколько человек предлагают одновременно, но одновременно может быть передано только одно предложение, это Basic Paxos, который является самым простым протоколом в Paxos.
Очевидно, что Basic Paxos недостаточно эффективны.Если Basic Paxos распараллелены и одновременно выдвигаются несколько предложений, например, что поесть на обед, куда пойти после еды и кому угостить гостей, участники также могут передать несколько предложения одновременно. Это протокол Multi-Paxos.
Basic Paxos
Роль
Алгоритм Paxos имеет три роли: Предлагающий, Принимающий и Ученик, В реализации узел может играть несколько ролей.
изображение 3
- Предлагающий несет ответственность за внесение предложений
- Акцептант отвечает за голосование по предложениям
- Учащийся получает результаты голосования и помогает распространить информацию
Обучающийся не участвует в процессе голосования, для упрощения описания мы прямо игнорируем эту роль.
алгоритм
Процесс выполнения разделен на два этапа: этап подготовки и этап принятия.
Предлагающий должен сделать два запроса: Подготовить запрос и Принять запрос. Акцептор принимает или отклоняет предложения на основе собранной информации.
Подготовить этап
- Предлагающий выбирает номер предложения n и отправляет запрос Prepare(n) более чем половине (или более) принимающих.
- После того, как акцептор получит сообщение, если n больше, чем число, которое он видел ранее, он ответит на сообщение и не будет принимать предложения меньше n в будущем. Кроме того, если предложение меньше n было принято ранее, ответьте на этот номер и содержание предложения Предлагающему.
Принять этап
- Когда предлагающий получает более половины ответов, он может отправить запрос Accept(n, value). n — номер собственного предложения, а значение — значение, соответствующее наибольшему номеру предложения, на которое ответил Принимающий.Если Принимающий не отвечает ни на одно предложение, значением является содержание собственного предложения Предлагающего.
- После того, как акцептор получит сообщение, если n больше или равно наибольшему числу, которое он видел ранее, он записывает номер и содержание предложения и отвечает на запрос, чтобы указать на принятие.
- Когда Предлагающий получает более половины ответов, это означает, что его предложение принято. В противном случае вернитесь к первому шагу, чтобы снова инициировать предложение.
Полный алгоритм показан на рисунке 4:
Рисунок 4
Acceptor должен постоянно хранить три значения minProposal, acceptProposal и acceptValue.
три условия
Существует три возможных сценария процесса консенсуса Basic Paxos. Они представлены отдельно ниже.
Случай 1: Предложение принято
Как показано на рисунке 5. X, Y представляют клиента, S1-S5 — сервер, представляющий как предлагающего, так и принимающего. Во избежание повторения нумерация, предложенная Предлагающим, состоит из двух частей:
序列号.Server ID
Например, номер предложения, предложенный S1, равен 1.1, 2.1, 3.1...
Рисунок 5 Приведенные выше фотографии взяты изPaxos lecture (Raft user study)стр. 13
Этот процесс означает, что S1 получает предложение X от клиента, поэтому S1 действует как предлагающий и отправляет запрос на подготовку (3.1) S1-S3.Поскольку акцептор S1-S3 не принял ни одного предложения, он принимает предложение. Затем предлагающий S1-S3 отправляет запрос Accept(3.1, X), и предложение X успешно принимается.
После того как предложение X принято, S5 получает предложение Y от клиента, а S5 отправляет запрос Prepare (4.5) на S3-S5. Для S3 4.5 больше, чем 3.1, и принял X, он ответит на предложение (3.1, X). Получив ответ от S3-S5, S5 заменяет свой собственный Y на X, а затем отправляет запрос Accept(4.5, X). S3-S5 принимают предложение. В конце концов все акцепторы приходят к соглашению и имеют одинаковое значение X.
Результат этой ситуации:Новый Предлагающий будет использовать принятое предложение
Случай 2: предложение не принято, новый предлагающий виден
Изображение 6 Приведенные выше фотографии взяты изPaxos lecture (Raft user study)стр. 14
Как показано на рисунке 6, S3 принимает предложение (3.1, X), но S1-S2 еще не получили запрос. В это время S3-S5 получает Prepare(4.5), S3 ответит на принятое предложение (3.1, X), S5 заменяет значение предложения Y на X и отправляет Accept(4.5, X) на S3-S5, для S3 , число 4,5 больше, чем 3,1, поэтому это предложение будет принято.
Затем S1-S2 принимает Accept(3.1, X), и, наконец, все акцепторы приходят к соглашению.
Результат этой ситуации:Новый Предлагающий будет использовать отправленные значения, и оба предложения будут успешными.
Случай 3: предложение не принято, а новый предлагающий не виден
Рисунок 7 Приведенные выше фотографии взяты изPaxos lecture (Raft user study)стр. 15
Как показано на рисунке 7, S1 принимает предложение (3.1, X), S3 сначала получает «Подготовить» (4.5), а затем получает «Принять» (3.1, X). Поскольку 3.1 меньше 4,5, он напрямую отклонит предложение. Таким образом, предложение X не может получить более половины ответов, и предложение блокируется. Предложение Y можно пройти гладко.
Результат этой ситуации:Новый предлагающий использует собственное предложение, старое предложение заблокировано
живой замок
Вероятность живой блокировки мала, но она может серьезно повлиять на производительность. Это ситуация, когда два или более предлагающих опережают друг друга на этапе подготовки.
Рисунок 8 Приведенные выше фотографии взяты изPaxos lecture (Raft user study)стр. 16
Решение состоит в том, чтобы дать случайное время ожидания после сбоя Proposer, тем самым уменьшив вероятность одновременных запросов.
Multi-Paxos
Livelock, упомянутый в предыдущем разделе, также может быть решен с помощью Multi-Paxos. Он выберет Лидера из Предложившего и отправит Предложение только Лидером, а также может сохранить стадию Подготовки и уменьшить потери производительности. Конечно, также можно напрямую передавать несколько механизмов Proposer Basic Paxos, но производительность недостаточно высока.
После распараллеливания Basic Paxos несколько предложений могут обрабатываться одновременно, поэтому для возможности хранения разных предложений должен быть гарантирован порядок предложений.
Структура Acceptor показана на рисунке 9, каждый блок представляет собой запись, которая используется для хранения значения предложения. Вход отличается возрастающим Индексом.
Рисунок 9
Multi-Paxos нужно решить несколько задач, рассмотрим их по порядку.
1. Выборы лидера
Один из самых простых методов выборов — стать лидером с наибольшим идентификатором сервера.
Каждый сервер отправляет пакеты пульса другим серверам с интервалом времени T. Если сервер не получает пульс от более высокого идентификатора в течение 2T, он становится лидером.
Другие Предлагающие должны отклонить запрос клиента или направить запрос Лидеру.
Конечно, можно использовать и другие более сложные методы выборов, которые здесь подробно описываться не будут.
2. Пропустите этап подготовки
Роль Подготовка состоит в том, чтобы блокировать старые предложения и проверять принятые значения предложений.
Когда только один лидер отправляет предложение, подготовка не будет конфликтовать, а фазу подготовки можно опустить, что может сократить количество запросов RPC вдвое.
Логика запроса Prepare изменена на:
- Акцептор записывает глобальное максимальное количество предложений
- Ответ на максимальное количество предложений, если текущая запись и все последующие записи не приняли ни одного предложения, ответ noMoreAccepted
Когда Лидер получает более половины ответов noMoreAccepted, фаза Подготовка не требуется, и нужно отправить только запрос Принять. До тех пор, пока Accept не будет отклонено, снова требуется этап Prepare.
3. Полный информационный поток
Информация пока неполная.
- Базовый Paxos требует согласия только более половины узлов. Но в Multi-Paxos этот метод может помешать некоторым узлам получить полную информацию о входе. Мы хотим, чтобы каждый узел имел всю информацию.
- Только Предлагающий знает, было ли предложение принято (на основе полученных ответов), а Акцептант не имеет возможности узнать об этом.
Решение первой проблемы очень простое, то есть Proposer отправляет всем узлам запрос Accept.
Второй вопрос немного сложнее. Во-первых, мы можем добавить Success RPC, чтобы предлагающий явно сообщал акцептору, какое предложение было принято.Это вполне осуществимо, но его можно оптимизировать, чтобы уменьшить количество запросов.
В запросе Accept мы добавляем параметр firstUnchosenIndex для указания первого непринятого индекса предлагающего.Этот параметр означает, что для предлагающего были приняты предложения, меньшие индекса. Таким образом, Acceptor может использовать эту информацию, чтобы пометить предложения меньше Index как принятые. Кроме того, следует отметить, что может быть помечено только предложение этого Предлагающего, потому что, если происходит смена лидера, разные Предлагающие могут иметь разную информацию, и это может быть несогласованным, если они отмечены напрямую без различия между Предлагающими.
Рисунок 10
Как показано на рисунке 10, предлагающий готовится отправить запрос на принятие с индексом = 2, 0 и 1 являются принятыми предложениями, поэтому firstUnchosenIndex = 2. Когда акцептор получает запрос и сравнивает индекс, он может пометить предложение Dumplings как принятое.
Из-за ранее упомянутой ситуации переключения Лидера для получения полной информации по-прежнему требуется явный запрос. Когда Acceptor отвечает на сообщение Accept, приносит свой собственный firstUnchosenIndex. Если он меньше, чем у Предложившего, то вам нужно отправить Success(index, value), Принимающий помечает полученный индекс как принятый, а затем отвечает новым firstUnchosenIndex и так далее, пока два индекса не сравняются.
Суммировать
Paxos — важный алгоритм консенсуса в задачах распределенного консенсуса. В этой статье представлены самые основные Basic Paxos и Multi-Paxos, которые можно распараллелить.
В Basic Paxos представлены три основные роли: Предлагающий, Принимающий и Учащийся, а также три основные ситуации, которые могут возникнуть во время предложения. В Multi-Paxos вводятся три проблемы, которые необходимо решить: выбор лидера, подготовка к упущению и завершение потока информации.
В следующей статье мы реализуем простую демонстрацию для проверки этого алгоритма, а процесс реализации будет включать в себя более подробную информацию.
Reference
Алгоритмы распределенной согласованности и консенсуса
Алгоритм Paxos и алгоритм Raft
Paxos lecture (Raft user study)
YouTube | Paxos lecture (Raft user study)
авторское право
В этой работе используетсяЛицензионное соглашение CCBY 4.0, просьба указывать ссылку при перепечатке.