Как реплики, возвращающиеся в сеть в PAXOS или RAFT, наверстывают упущенное?

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

С оригинальными документами Paxos это действительно остается упражнением для читателя. На практике с Paxos вы можете отправлять дополнительные сообщения, такие как отрицательные подтверждения, чтобы распространять больше информации по кластеру в качестве оптимизации производительности. Это можно использовать, чтобы сообщить узлу, что он отстает из-за потерянных сообщений. Как только узел узнает, что он отстает, ему нужно наверстать упущенное, что можно сделать с помощью дополнительных типов сообщений. Это описывается как повторная передача в Trex multi -paxos, который я написал, чтобы демистифицировать Paxos .

Документ Google Chubby Paxos Paxos Made Live критикует Paxos за оставляя многое на усмотрение людей, занимающихся реализацией. Лэмпорт учился на математика и пытался математически доказать, что у вас не может быть консенсуса по сетям с потерями, когда он нашел решение. Оригинальные документы в значительной степени предоставляют доказательства того, что это возможно, а не объясняют, как с их помощью создавать практические системы. Современные статьи обычно описывают применение каких-то новых методов, подкрепленных некоторыми экспериментальными результатами, а также предоставляют формальное доказательство, ИМХО, большинство людей пропускают его и принимают на веру. Неприступный способ введения Paxos означает, что многие люди, которые цитируют оригинальную статью, но не видят, что они описывают выборы лидеров и мульти-Paxos . К сожалению, Паксос по-прежнему преподается теоретически, а не в современном стиле, что заставляет людей думать, что это сложно, и упускают из виду его суть.

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

Например, Корфу и CURP обеспечивает невероятно высокую производительность, один использует Paxos только для метаданных, другой должен использовать Paxos только при одновременной записи на одни и те же ключи. Эти решения не дополняются Raft или Multi-Paxos напрямую, поскольку они предназначены для конкретных высокопроизводительных сценариев (например, магазинов k-v). Тем не менее, они демонстрируют, что стоит понимать, что для практических приложений существует огромное количество оптимизаций, которые вы можете сделать, если ваша конкретная рабочая нагрузка позволит вам использовать Paxos для какой-то части общего решения.

Это упоминается в Paxos made Simple:

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

А также в Рафт-бумаге:

Лидер поддерживает nextIndex для каждого ведомого, который является индексом следующей записи журнала, которую лидер отправит этому ведомому.

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

В случае сбоя последователя или кандидата будущие RPC RequestVote и AppendEntries, отправленные ему, завершатся ошибкой. Raft обрабатывает эти сбои, повторяя попытки бесконечно; если разбившийся сервер перезагрузится, то RPC завершится успешно.