Условия гонки на параллельных экземплярах Paxos
Я запутался в использовании алгоритма Паксоса. Кажется, что Paxos может быть использован для такого сценария: несколько серверов (кластер, я предполагаю, что каждый сервер имеет все 3 роли, proposer, acceptor, leaner) должны поддерживать одинаковые последовательности команд для достижения согласованности и резервного копирования. Я предполагаю, что есть некоторые клиенты, отправляющие команды на этот сервер (клиенты могут отправлять параллельно). Каждый раз команда отправляется на несколько серверов одним экземпляром Paxos.
- Разные клиенты могут отправлять разные команды разным авторам, верно?
Если это так, одна команда от некоторого клиента вызовет экземпляр Paxos. Так,
- Несколько экземпляров Paxos могут работать одновременно?
Если это так, клиент-A отправляет команду "A += 1" в proposer-A, а клиент-B отправляет команду "B += 2" в proposer-B почти одновременно, я полагаю, что каждый сервер получил 2 команды "A += 1" и "B += 2".
Тем не мение,
При наличии 5 серверов, скажем, S1-S5, S1 отправляют команду "A += 1" и S5 отправляют команду "B += 1", S2 обещают S1, однако S3, S4 обещают S5, так что, наконец, S3,S4,S5 получили "B +" = 1 ", но S1,S2 ничего не получили, потому что число обещаний не большинство. Похоже, Паксос не помогает вообще. Мы не получаем ожидаемые "A += 1" и "B += 2" на всех 5 серверах?
Таким образом, я предполагаю, что при практическом применении Paxos параллельные экземпляры Paxos не допускаются? Если это так, то как избежать параллельных экземпляров Paxos, кажется, что нам все еще нужен централизованный сервер, чтобы указывать, работает ли Paxos или нет, если мы разрешили несколько клиентов и несколько предложений.
Также у меня есть вопросы по поводу номера заявителя. Я ищу в Интернете, и некоторые претензии следующие
является решением: 5 серверов, с соответствующим индексом k(0-4), каждый сервер использует номер 5*i + k для "i" -го предложения этого сервера.
Для меня это, кажется, не соответствует требованиям вообще, потому что первый номер предложения сервера-1 всегда равен 1, а первый номер предложения сервера-4 всегда равен 4, но сервер-4 может поднять предложение раньше, чем сервер-1, однако это предложение номер больше.
2 ответа
Таким образом, я полагаю, что при практическом применении Paxos параллельные экземпляры Paxos не допускаются? Если это так, то как избежать параллельных экземпляров Paxos, кажется, что нам все еще нужен централизованный сервер, чтобы указывать, работает ли Paxos или нет, если мы разрешили несколько клиентов и несколько предложений.
Вам не нужен централизованный сервис, нужны только узлы для перенаправления клиентов текущему лидеру. Если они не знают, кто является лидером, они должны выдать ошибку, и клиент должен выбрать другой узел из DNS/config, пока не найдет или не сообщит текущий лидер. Клиентам нужен только достаточно актуальный список узлов в кластере, чтобы они могли связываться с большинством текущих узлов, тогда они найдут лидера, когда он станет стабильным.
Если узлы разделяются во время сетевого раздела, вам может повезти, и это чистый и стабильный раздел, который ведет только к одному большинству, и он получит нового стабильного лидера. Если вы получаете нестабильный раздел или некоторые отброшенные направленные пакеты, так что два или узлы начинают быть "дуэльными лидерами", то вы можете использовать случайные тайм-ауты и адаптивное откат, чтобы минимизировать два узла, пытающихся быть избранными одновременно, что приводит к неудачным раундам и впустую сообщения. Клиенты будут получать бесполезные перенаправления, ошибки или тайм-ауты и будут сканировать лидера во время поединка, пока он не будет преобразован в стабильного лидера.
Фактически paxos идет на CP из CAP, поэтому он может потерять A (доступность) из-за дуэльных лидеров или отсутствия большинства способных общаться. Возможно, если бы на самом деле это был действительно высокий риск, люди писали бы о том, что узлы заносят в черный список любой узел, который неоднократно пытается привести, но который никогда не дойдет до фиксации из-за постоянных проблем с нестабильным сетевым разделом. Прагматично можно представить, что люди, которые следят за системой, получат оповещения, убьют такой узел и исправят сеть, прежде чем пытаться добавить сложные "работающие без присмотра, независимо от того, что", функции в их протокол.
Что касается количества предложений, простая схема представляет собой 64-битную длину с 32-битным счетчиком, упакованным в старшие биты, и 32-битным IP-адресом узла, упакованным в младшие биты. Это делает все числа уникальными и чередующимися и предполагает, что вы не запускаете несколько узлов на одном компьютере.
Если вы посмотрите на Multi-Paxos в Википедии, речь идет об оптимизации потока для стабильного лидера. Аварийные переключения должны быть действительно редкими, поэтому, как только вы получите лидера, он может скакать с принятием только сообщений и пропустить предложения. Когда вы скачете, если вы немного упаковываете идентичность лидера в номера событий, узел может видеть, что последующие приемы происходят от того же лидера и являются последовательными для этого лидера. Пропуск со стабильным лидером - это хорошая оптимизация, а создание нового лидера с предложениями - это дорогостоящая вещь, требующая сообщений с предложениями и риска дуэльных лидеров, поэтому следует избегать этого, если это не запуск или отказ кластера.
однако это номер предложения больше.
В этом и заключается смысл разделения пространства предложений. Правило состоит в том, что принимается только самое последнее предложение с наибольшим числом просмотров. Таким образом, если было разослано три предложения, только одно предложение с наибольшим числом когда-либо получит принятое большинство.
Если вы этого не сделаете, есть вероятность, что несколько сторон будут продолжать выдвигать предложения с просто увеличенными числами (nextNumber = ++highestNumberSeen) как сумасшедший и никогда не приходит к общему мнению.