Эта статья взята из: [блог InTheWorld] (Добро пожаловать, чтобы оставить сообщение и обменяться)
Алгоритм Paxos должен быть одним из самых известных алгоритмов распределенного консенсуса. Но, к стыду своему, мое понимание алгоритмов Paxos всегда было запутанным. Во время праздника Национального дня я читал «SRE Google Operation and Maintenance Decryption», главу «Распределенная система консенсуса» (то есть Chubby), а также делал упор на алгоритм Paxos. Просто воспользуйтесь этой возможностью, чтобы узнать и обобщить.
Алгоритм Paxos можно разделить на две формы: Basic Paxos и Multi-Paxos. Их основные особенности заключаются в следующем. Для сравнения они перечислены здесь:
● Базовый Паксос («единый указ»):
- Один или несколько серверов инициируют предложение
- Система согласится на выбранное предложенное значение
- Будет выбрано только одно предложенное значение
● Мультипаксос:
- Multi-Paxos формирует согласованность в столбце значений с помощью нескольких раундов алгоритма Basic Paxos.Эта серия значений эквивалентна журналу повторов, а ее согласованность эквивалентна согласованности конечных автоматов каждого сервера.
Конечно, их характеристики не ограничиваются вышеуказанным содержанием, и для объяснения требуется более глубокий анализ знаний. Давайте сначала взглянем на Basic Paxos!
1. Basic Paxos
Сначала определимся с основными понятиями:
Предложение: предложение = предлагаемая стоимость + номер предложения;
Предложение: Инициатор предложения;
Акцептор: акцептор предложения;
Ученик: предполагаемый ученик;
Игнорируйте здесь Ученика и изучайте только взаимодействие между Предлагающим и Принимающим.
Для удобства понимания я размещаю здесь картинку, представляющую собой блок-схему алгоритма Basic Paxos.
Обсудите процесс Basic Paxos в соответствии с последовательностью процессов на рисунке выше;
- Генерация идентификатора предложения; Генерация идентификатора предложения имеет некоторые особенности, Basic Paxos требует, чтобы идентификатор предложения был уникальным, и не требует, чтобы идентификатор предложения увеличивался глобально. Но если сам идентификатор предложения является случайным UUID, он, скорее всего, будет отклонен принимающей стороной на этапе p1b. Basic Paxos допускает одного или нескольких Proposer (ов), и действительно сложно увеличить идентификатор глобально, Другими словами, если реализован глобально инкрементный идентификатор, то Basic Paxos нужно только пройти процесс принятия. Таким образом, более реалистичным способом является использование примерно поэтапного и уникального предложения. Метод генерации идентификатора. Чем если использовать комбинацию maxRound + ID сервера. Знак «плюс» здесь относится к соединению старших и младших битов.Младший идентификатор сервера и локально увеличенный maxRound обеспечивают уникальность.
- Ответьте на Prepare(n); первое, что нужно сделать здесь, это при необходимости обновить minProposal. Также ответьте в соответствии с отношением между minProposal и N. Вот несколько переменных на сервере акцепторов, которые необходимо объяснить. Среди них minProposal – это "максимальный идентификатор предложения", полученный акцептором (не принятым). Название этого minProposal происходит от ppt (см. Ссылки). Должно быть, это опечатка, но не обращайте внимания на имя, просто знать его значение. acceptProposal – это самый большой идентификатор принятого предложения. А acceptValue — самое большое принятое предложение. Значение, соответствующее идентификатору. Конечно, в алгоритме Basic Paxos, поскольку в конечном итоге будет выбрано только одно значение, «максимум» здесь не имеет большого значения. (Эти значения относятся ко всем жестким дискам, которые необходимо сохранить напрямую, чтобы гарантировать возможность восстановления состояния после сбоя).
- В другом случае ответа Prepare(n), n
- В положительном случае (n > minProposal) в ответ на Prepare(n) есть еще два подслучая. Первый заключается в том, что акцептор никогда не принимал предложение, тогда как acceptProposal, так и acceptValue равны нулю; другой заключается в том, что акцептор принял предложение, тогда два значения не равны нулю. Оба случая разумны, но содержание сообщения Promise() отличается.
- После того, как Proposer получает ответ от большинства машин, если acceptValue пусто, он помещает значение, которое он хочет предложить, в сообщение accept!(); в противном случае он использует значение предложения, соответствующее наибольшему идентификатору предложения. Это также подтверждает, что Basic Paxos может согласовать только одно значение.
Что касается других частей процесса, я не буду здесь описывать, у команды WeChat есть более подробный обмен, и ссылка будет прикреплена к задней части блога, если вам интересно, вы можете взглянуть.
2. Multi-Paxos
Базовый Paxos может согласовать только одно значение, что трудно удовлетворить практическим сценариям применения. Поэтому нам нужен алгоритм Multi-Paxos, который может достичь консенсуса по набору значений в распределенной системе. Multi-Paxos обычно использует лидера для единообразной инициации предложения, и только лидер может инициировать предложение. Первая половина предложения не является строгой, потому что Multi-Paxos фактически состоит из двух состояний: состояния обслуживания лидера и состояния избрания лидера. Мы не будем обсуждать последнее состояние здесь.
Поскольку только лидер может инициировать предложение, в состоянии обслуживания лидера все становится проще. Короче говоря, этап подготовки алгоритма Basic Paxos становится ненужным и переходит непосредственно к этапу принятия. Что касается того, почему Multi-Paxos может согласовывать несколько значений, посмотрите на рисунок ниже, чтобы понять.
И сообщение Accept!(), и сообщение Accepted() здесь имеют дополнительный I, и этот I является порядковым номером значения. Как упоминалось выше, этот W на самом деле является журналом повторов.Все журналы повторов складываются вместе для достижения согласованности конечного автомата в распределенной системе.
Учащиеся, знакомые с Zookeeper или понимающие его, должны знать, что старший бит ZXID — это идентификатор эпохи, а младший бит — это порядковый номер добавочной транзакции. Этот ZXID на самом деле почти эквивалентен комбинации N и I здесь. Другой контент Multi-Paxos, честно говоря, я еще только изучаю, поэтому на этом остановлюсь.
Использованная литература:
【1】woohoo.info Q.com/talent/articles…