Открыть список
Как стать автором
Обновить

Комментарии 17

Это очень круто! Будет интересно почитать про реализацию. Планируете выложить библиотеку в паблик?
Да, весь исходный код будет опубликован. По мере написания статей будут появляться соответствующие куски и библиотеки.
Алгоритм домашнего, так сказать, изготовления, или один из известных и математически доказанных? Как гарантируется консистентность? Чем лучше того же Raft, если вылеты мастера редки? Как ваша реализация относится к большим задержкам в сети, типа 20-50мс? Какая скорость сходимости после проблем со связностью?
Вопросы очень хорошие. Но имеет смысл на них отвечать после рассмотрения самого алгоритма. Что касательно самого алгоритма, то это новый алгоритм.

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

Например, развалилась связанность 5 -> 2, 3 консистентность можно сохранить только перейдя в RO
Я правильно понял?
В любом случае жду продолжения
В данном случае при развале 5 -> 3+2 мы получаем, что для большинства нод (3) можно продолжать операции изменения данных, а для 2 — допускаются только локальные чтения. После этого, у 3-х нод одна может упасть, тогда получается переход 3 -> 2 с сохранением консистентности. Итого, получаем переход 5 -> 2.
после 5->3+2, те ноды, которые попали в сегмент где 3 (есть кворум) — полностью функциональны, ноды в сегменте, где 2 — имеют доступ к вероятно не актуальным данным, ценность которых несколько сомнительна. Когда от оставшегося сегмента из 3 отвалилась одна, не исключена вероятность того, что она подключилась к другому сегменту, где до этого было 2 ноды. Кворум переместился, но данные противоречивы. Можно прогнать до последней известной версии объектов, но где гарантия, что эта версия будет актуальной?
Какая функциональность подразумевается под консистентностью? Непротиворечивость в рамках транзакционности или актуальность данных?
Ответил ниже
Для этого ведь нужно специально вывести две упавшие реплики из кластера, тогда действительно кластер станет из трёх реплик. Такую логику разрешают многие системы, что в этом уникального?
Во-первых, я не утверждал, что эта фича является уникальной. А во-вторых, можете привести ссылки с такой логикой? Мне было бы очень интересно ознакомиться.
В Raft, например, это находится в разделе 6 статьи In Search of an Understandable Consensus Algorithm, который называется Cluster membership changes.

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



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

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

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

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