Существует ли строго согласованный протокол членства в группе?

Question

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

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

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

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

Мое понимание заключается в том, что тот факт, что каждый новый раздел согласуется с другим набором членов в некотором смысле, означает, что часть согласованности из теоремы CAP ослаблена. Надеюсь, что такой протокол может существовать (?).

Answer 1

Консенсусный протокол (такой как Paxos, Raft и т. Д.) Не может использоваться для разработки протокола членства в нескольких группах. Это связано с тем, что все консенсусные протоколы основаны на фундаментальной идее о том, что любое решение может быть принято только в том случае, если большинство членов «согласились» его принять. Таким образом, избегается феномен «сплит-мозг», поскольку не может быть двух разделов (размером больше большинства: (n/2)+1), которые согласились на другого лидера (и, следовательно, набор членов), поскольку по меньшей мере один член будет членом обоих разделов и проголосовал бы за только один из разделов (тот, который просил сначала голосовать).

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

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

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

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

---

Другой альтернативный подход для протокола членства являются gossip-based membership protocols с реализации в реальной жизни быть интегрированы в различные инструменты в промышленности, таких как Consul.Чтобы использовать этот подход, вы можете испускать несколько разных классов сообщений от каждого члена, в зависимости от разных групп, которые вы хотите отслеживать. Однако снова эти группы статически определяются внутри протокола и, в конечном итоге, согласуются (что означает, что каждый отказ будет окончательно обнаружен всеми живыми членами).

---

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