Реплицируемый объект. Часть 1: Введение

[bak]

Это очень круто! Будет интересно почитать про реализацию. Планируете выложить библиотеку в паблик?

[gridem]

Да, весь исходный код будет опубликован. По мере написания статей будут появляться соответствующие куски и библиотеки.

[ToSHiC]

Алгоритм домашнего, так сказать, изготовления, или один из известных и математически доказанных? Как гарантируется консистентность? Чем лучше того же Raft, если вылеты мастера редки? Как ваша реализация относится к большим задержкам в сети, типа 20-50мс? Какая скорость сходимости после проблем со связностью?

[gridem]

Вопросы очень хорошие. Но имеет смысл на них отвечать после рассмотрения самого алгоритма. Что касательно самого алгоритма, то это новый алгоритм.

По поводу доказанности соображения следующие. Вот взять, к примеру, raft. С доказанностью и у него всё хорошо, вот только эта доказанность рассмотрена в рамках определенной модели. Реальность всегда богаче, и raft может при определённых условиях встать колом, несмотря на всю свою «доказанность». Опять же, имеет смысл это обсуждать в рамках статьи про сам алгоритм.

[Uint32]

Не очень себе представляю, как

>>Система сохраняет консистентность даже в условиях, когда число реплик уменьшается значительно. Например, количество реплик может уменьшиться от пяти до двух,

Например, развалилась связанность 5 -> 2, 3 консистентность можно сохранить только перейдя в RO
Я правильно понял?
В любом случае жду продолжения

[gridem]

В данном случае при развале 5 -> 3+2 мы получаем, что для большинства нод (3) можно продолжать операции изменения данных, а для 2 — допускаются только локальные чтения. После этого, у 3-х нод одна может упасть, тогда получается переход 3 -> 2 с сохранением консистентности. Итого, получаем переход 5 -> 2.

[Uint32]

после 5->3+2, те ноды, которые попали в сегмент где 3 (есть кворум) — полностью функциональны, ноды в сегменте, где 2 — имеют доступ к вероятно не актуальным данным, ценность которых несколько сомнительна. Когда от оставшегося сегмента из 3 отвалилась одна, не исключена вероятность того, что она подключилась к другому сегменту, где до этого было 2 ноды. Кворум переместился, но данные противоречивы. Можно прогнать до последней известной версии объектов, но где гарантия, что эта версия будет актуальной?
Какая функциональность подразумевается под консистентностью? Непротиворечивость в рамках транзакционности или актуальность данных?

[gridem]

Ответил ниже

[ToSHiC]

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

[gridem]

Во-первых, я не утверждал, что эта фича является уникальной. А во-вторых, можете привести ссылки с такой логикой? Мне было бы очень интересно ознакомиться.

[ToSHiC]

В Raft, например, это находится в разделе 6 статьи In Search of an Understandable Consensus Algorithm, который называется Cluster membership changes.

[gridem]

Самая мутная и нетривиальная часть Raft алгоритма, причем не без багов.

[shai_xylyd]

Я написал пару постов про Paxos и про измемение размера кластера. Если кратко, то я объединил подход Vertical Paxos (разные кворумы на чтение и на запись) с joint consensus Raft'а:

• How Paxos works
• Read write quorums in Paxos
• Best of both worlds: Raft's joint consensus + Single Decree Paxos

До TLA+ руки еще не дошли, но я попрактиковался в ручном теоремодоказательстве и привел его в статьях, упомянутых выше. Буду рад вопросам :)

[gridem]

Интересные идеи. Надо будет ознакомиться.

[Mingun]

После такого длительного вступления ожидал всё же, что вы покажете реализацию, но судя по списку освещаемых тем ждать её не стоит. Я прав?

[gridem]

Покажу, но в другой статье. В списке она есть под номером 8.

[gridem]

Когда от оставшегося сегмента из 3 отвалилась одна, не исключена вероятность того, что она подключилась к другому сегменту

Такая возможность исключена, т.е. алгоритм такого сделать не позволит.

Какая функциональность подразумевается под консистентностью? Непротиворечивость в рамках транзакционности или актуальность данных?

Я не очень понял вопрос, но отвечу. Под консистентностью я понимаю линеаризуемость. Что это такое, почитать, например, в википедии. Если я как-то не так ответил, то хочется услышать более чёткий вопрос, т.к. мне не очень понятно, как можно под консистентностью понимать функциональность. В линеаризуемости задается достаточно чётко условия об актуальности и согласованности данных.