ZooKeeper vs Chubby
От: A13x США  
Дата: 17.03.20 01:09
Оценка: 70 (1)
Читал ли кто-то публичную документацию по Chubby [1]?
Интересно было бы узнать, насколько близко к нему приближены его open source аналоги [2]?

Самое по-видимому скрупулезное исследование в публичном доступе содержит смешанные результаты:

Use Zookeeper. It’s mature, well-designed, and battle-tested. Because the consequences of its connection model and linearizability properties are subtle, you should, wherever possible, take advantage of tested recipes and client libraries like Curator, which do their best to correctly handle the complex state transitions associated with session and connection loss.


В то же время:

Update 2019-07-23: @insumity explains that ZooKeeper sync+read is not, in fact, linearizable–there are conditions under which it might return stale reads.


Из замеченных различий еще то, что KeepAlive в ZooKeeper сделан поверх TCP, а не UDP как в Chubby. Видимо может сыграть роль в случае high congestion.
Еще API в ZooKeeper кажется несколько переусложненным, в отличии от API Chubby.

Возможные альтернативы ZooKeeper'у — etcd — по-видимому не предоставляет safe leases —

etcd locks are fundamentally unsafe...


из этого исследования

Вопрос — работал ли кто-то с ZooKeeper или его альтернативами [2] — и насколько по-вашему в работе проявлялись недостатки как отсутствие linearizability в ZooKeeper и насколько проблемы consistency мешают в реализации насколько возможно корректного leader election используя ZooKeeper/альтернативый вариант как distributed lock service?

---

[1]

* Official Paper
* Medium Article
* Chubby Design on Slideshare
* Youtube Presentation Video

[2] Open-Source аналоги chubby: https://www.g2.com/products/zookeeper/competitors/alternatives
Отредактировано 17.03.2020 1:10 A13x . Предыдущая версия .
Re: ZooKeeper vs Chubby
От: maxkar  
Дата: 23.03.20 09:37
Оценка: 85 (3)
Здравствуйте, A13x, Вы писали:

A>Вопрос — работал ли кто-то с ZooKeeper или его альтернативами [2] — и насколько по-вашему в работе проявлялись недостатки как отсутствие linearizability в ZooKeeper и насколько проблемы consistency мешают в реализации насколько возможно корректного leader election используя ZooKeeper/альтернативый вариант как distributed lock service?


Я работал с zookeeper пару лет назад. Были серьезные проблемы с "well-designed & battle-tested". Та версия, которую я использовал, кэшировала IP-адреса серверов при старте и больше никогда их не меняла. В результате при отказе/ротации узлов (и смене IP) клиенты тихо умирали . Я сейчас посмотрел код, эту конкретную проблему они вроде бы починили. Но у меня сомнения, может ли он корректно обрабатывать изменения кластера во время работы приложения (например, добавилось еще пять узлов — подхватит ли их новый клиент или нужен перезапуск и изменение конфигурации?).

По поводу linearizability. Это вопрос терминологии. Линейность (неизменность/монотонность видимого порядка операций) zookeeper обеспечивает именно в силу своей архитектуры — это replicated log shipping. Т.е. лог изменений с единственного мастера реплицируется на slaves и всегда гарантирует относительный порядок операций. А вот видимость изменений при чтении может отставать от мастера. На реализацию корректного leader election возможные задержки на чтение не влияют. Как я делал выборы:

  1. В группе "кандидатов" создаем ephemeral sequential запись со своими данными (свой ID или чего там нужно). Вызов даст нам ID записи.
  2. Читаем эту группу (getChildren) кандидатов с watch.
  3. Ждем, когда наш ID будет минимальным среди детей. В реализации именно сортируем и сравниваем с нашим ID.
  4. Поздравляю, мы — лидер!

Задержки репликации здесь не мешают. Если вдруг нашего ID нет, изменения еще не дошли (клиент же жив, ephemeral nodes исчезают только с disconnect). Если минимальный — значит все предыдущие умерли (никто не сможет вставить запись "перед" нами — это и есть линейность).

Вопросы поведения zookeeper в случае, когда на мастер кластера упал метеорит, я не рассматривал — у нас zookeeper был существующим сервисом. Тут нужно смотреть, какие именно гарантии записи. Т.е. есть ли потенциальная потеря данных или мастер успешно подтверждает запись только после репликации в majority. Вот это — потенциальная проблема. Но я очень надеюсь, что клиент в таком случае упадет и нужно будет перезапускать соединение (и устраивать новые выборы).

Последний момент. После того, как выборы завершились, за соединением нужно следить. Если оно вдруг упало — мы больше не лидер. У меня на проекте это было не критично — важные операции мы делали на том же zookeeper client. Т.е. если операция прошла (клиент не падал в промежутке) — мы все еще лидер. Если у вас только выборы — может быть момент времени, когда клиент уже упал а остальной код считает, что данный экземпляр приложения — все еще лидер. Но эта гонка ничем не решается. Ну кроме как использования zookeeper и для других операций (и это же снижает проблемы даже с отказом master node с потерей данных).
Re[2]: ZooKeeper vs Chubby
От: A13x США  
Дата: 24.03.20 23:16
Оценка:
Здравствуйте, maxkar, Вы писали:

M>...


M>По поводу linearizability. Это вопрос терминологии. Линейность (неизменность/монотонность видимого порядка операций) zookeeper обеспечивает именно в силу своей архитектуры — это replicated log shipping. Т.е. лог изменений с единственного мастера реплицируется на slaves и всегда гарантирует относительный порядок операций. А вот видимость изменений при чтении может отставать от мастера. На реализацию корректного leader election возможные задержки на чтение не влияют.


Насколько я понимаю сам по себе, без дополнительных телодвижений "replicated log shipping" не может обеспечить линейность, во всяком случае при отсутствии проверки на recency при чтении со standby.

И если я правильно понимаю то это может работать так:

1. Запрос на запись приходит на мастер. Мастер делает log shipping этих изменений и завершает операцию успешно в том и только в том случае если изменение реплицировано на majority. Изменяемая запись содержит Lamport Timestamp растущий при каждом изменении.
2. Чтение осуществляется не с одного нода, а с majority, recency guarantee (=> linearizability) обеспечивается тем, что берется запись с max timestamp.

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

M>Как я делал выборы:

M>

    M>
  1. В группе "кандидатов" создаем ephemeral sequential запись со своими данными (свой ID или чего там нужно). Вызов даст нам ID записи.
    M>
  2. Читаем эту группу (getChildren) кандидатов с watch.
    M>
  3. Ждем, когда наш ID будет минимальным среди детей. В реализации именно сортируем и сравниваем с нашим ID.
    M>
  4. Поздравляю, мы — лидер!
    M>

M>Задержки репликации здесь не мешают. Если вдруг нашего ID нет, изменения еще не дошли (клиент же жив, ephemeral nodes исчезают только с disconnect). Если минимальный — значит все предыдущие умерли (никто не сможет вставить запись "перед" нами — это и есть линейность).


Кажется я понял, все же уточню — я правильно понимаю, что это может работать только в том случае если операция происходит с группой составляющей majority?
Re: ZooKeeper vs Chubby
От: WolfHound  
Дата: 25.03.20 13:05
Оценка: 80 (2)
Здравствуйте, A13x, Вы писали:

A>насколько проблемы consistency мешают в реализации насколько возможно корректного leader election используя ZooKeeper/альтернативый вариант как distributed lock service?

Проблема распределённого консенсуса с почти нулевыми накладными расходами решена.
К сожалению, автор оказался не хорошим человеком. Запатентовал алгоритм и начал делать на нём очередной биткоин.
https://www.hedera.com/whitepaper
кнопка Download the whitepaper
раздел
THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM: FAIR, FAST, BYZANTINE FAULT TOLERANCE
Если из алгоритма выкинуть криптографию (она не для всех задач нужна) то латентность должна быть не больше чем у любого другого алгоритма.
Лично я почти уверен, что это оптимальное решение.
Ну, или очень близкое к нему. Просто по тому, что накладных расходов почти нет. Оптимизировать почти нечего.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: ZooKeeper vs Chubby
От: maxkar  
Дата: 26.03.20 13:59
Оценка: 10 (1)
Здравствуйте, A13x, Вы писали:

A>Насколько я понимаю сам по себе, без дополнительных телодвижений "replicated log shipping" не может обеспечить линейность, во всяком случае при отсутствии проверки на recency при чтении со standby.

A>И если я правильно понимаю то это может работать так:

Первое — все еще вопрос терминологии. Я, кажется, вижу, где у нас разница в понимании. Поэтому план изложения такой:

  1. Я коротко пройдусь по вашей модели, показывая важные моменты
  2. Изложу детальную модель того, какие гарантии обещаются и пример того, как оно может быть реализовано (Я не гарантирую, что zookeeper именно так делает. Всего лишь объясняю, что модель реализуема и валидна).
  3. Немного прокомментирую исследование от Jepsen (ваша первая ссылка в стартовом сообщении).

Итак, поехали.

Комментарии на модель


A>1. Запрос на запись приходит на мастер. Мастер делает log shipping этих изменений и завершает операцию успешно в том и только в том случае если изменение реплицировано на majority. Изменяемая запись содержит Lamport Timestamp растущий при каждом изменении.


Там не Lamport (это частичный порядок). В zookeeper глобальный монотонный счетчик всех операций. Успешная запись возвращает номер выполненной операции (как работает неуспешная запись — дальше). В стате линейность записи никто не отрицает.

A>2. Чтение осуществляется не с одного нода, а с majority, recency guarantee (=> linearizability) обеспечивается тем, что берется запись с max timestamp.


Все банальнее. Клиент на чтение посылает значение счетчика. Сервер не отвечает на запрос до тех пор, пока не получит достаточно логов (т.е. его log head будет иметь id не меньше, чем полученный от клиента). Поэтому клиент и видит всю историю в одном направлении (он не может увидеть старое состояние, узел просто не ответит). Но может увидеть с задержкой (задержка репликации).

Лучшая модель


Я начну с повторения терминологии. "Linearizability" в контексте zookeper обозначает наличие глобального порядка операций. Т.е. если есть две записи А и Б, всегда можно сказать, кто был раньше и кто позже. Т.е. можно сказать А < Б. Более того, в рамках одного клиента есть еще и порядок подписки (т.е. watch можно отсортировать с записями). Наличие полного порядка дает возможность иметь один глобальный счетчик операций на весь кластер. Более того, с помощью глобального счетчика это можно и реализовать.

Запись с точки зрения клиента и мастера


Запись производится почти так, как вы описали:

  1. Запрос приходит на мастер
  2. Мастер увеличивает "operationId" на 1 и пишет транзакцию в лог
  3. Запись реплицируется в majority.
  4. Мастер считает операцию успешной и возвращает клиенту результат и operationId его операции

Чтение (одинаково для всех узлов)


Тут используется наличие total order:

  1. Клиент посылает запрос на сервер включая operationId (который он получил в своей последней операции)
  2. Сервер сравнивает клиентский operationId и head из подтвержденного transaction log
  3. Если у клиента ID больше — сервер ждет новых записей лога и их подтверждения
  4. Когда head(confirmed log) >= client.operationId — сервер возвращает ответ и свой текущий operationId (т.е. head).

На мастере чтение пройдет сразу, на slave может быть задержка.

Теперь самый интересный момент:

Запись с точки зрения slave


Slave nodes получают записи от мастера (он их распределяет на каждую операцию) и сохраняют у себя. Но при этом не начинают сразу же использовать данные. Потому что может быть ситуация, когда кластер развалился и slave остался в minority (т.е. операция не совершится) а majority пишет операцию с тем же id. Вместо этого slave нужен консенсус о том, что запись есть у всех. Этот консенсус по поводу (leaderId, operationId) поддерживается постоянно и тесно связан с leader election. Точнее, важен даже не конкретный leader, а период правления (это ситуация от одного успешного election до следующего).

Узлам удобнее работать с periodId (периодами правления). Это глобальный счетчик, увеличивается с выборами нового лидера (т.е. когда достигнут новый консенсус, устанавливается и новое значение). Т.е. один и тот же узел может быть мастером в разные периоды. Зато в каждом периоде один мастер. Кластер поддерживает консенсус о (periodId (и masterNode), operationId). Если не поддерживается — значит, узел отвалился и нужно восстанавливать связь и делать новые выборы .

Во время записи каждый slave пишет (periodId0, operationId0, operationData) в логе но не использует. Пусть он затем получает консенсус про (periodId1, operationId1). Если periodId1 == periodId0 (правитель не сменился), node коммитит (начинает использовать на чтение, уведомляет watches и т.п.) все операции до operationId1 включительно. Иначе periodId1 > periodId0 и в какой-то момент были перевыборы. В этом случае запись (period0, operation0, operationData) может быть не валидна (может принадлежать minority). Узел запрашивает у мастера или majority актуальные транзакции между последней своей подтвержденной операцией и новым актуальным состоянием. Весь буфер от старого мастера просто выбрасывается.

В данной реализации на выборах побеждает узел с наибольшим (periodId, operationId) (период — первый в сравнении). Кластер устанавливает консенсус в (periodId + 1, operationId).

Еще — эта реализация — не Lamport clock! Period — это идентификатор "ветки альтернативной истории". Он используется для определения того, какой вариант события operationId считать верным при наличии конфликтов.


A>Кажется я понял, все же уточню — я правильно понимаю, что это может работать только в том случае если операция происходит с группой составляющей majority?


Нет, не обязательно. Как я (надеюсь, понятным способом) объяснил выше, достаточно линейно растущего operationId, который обрабатывается и передается клиентом. Да, могут быть задержки. Но они не отличимы от "медледнной сети". Поэтому то клиент и видит все записи в одном и том же порядке. Выделение в предыдущем предложении — не случайно, потому что есть следующая секция:

Jepsen & Curator


Статья в сообщении использует Curator. Я с куратором тоже знаком. Более того, я смотрел его исходный код и оценивал, сколько он решает проблем и сколько добавляет новых.

Что вообще такое curator? Это набор всевозможных patterns, включая leader election и т.п. Плюс они реализуют разные вещи вроде reconnection, повторения операции после восстановления связи и т.п. Что немного странно. В документации к ZooKeeper (клиент) прямым текстом написано, что он сам делает reconnect, реализует правильный backoff и до фатальных ошибок (вроде неверного пароля) вообще ничего предпринимать для восстановления не надо (с их кэшированием IP это сомнительно было, но в целом — да, оно само работает). В то же время Curator повторно реализует всю подобную функциональность. У него есть конфигурируемые backoff strategy и т.п. В рамках этих стратегий он пересоздает (как минимум — так было 2-3 года назад) ZooKeeper client. И вот здесь то и наблюдается проблема! Линейность гарантируется только в рамках одного ZooKeeper instance! А при создании нового клиента — линейность теряется!

Т.е. если при ошибках пересоздавать клиент, вполне возможна следующая ситуация:

  1. Мы имеем кластер из 5 узлов (N1-N5). У него лидер N1 и у нас последняя операция 425.
  2. Пропадает связь. Кластер разваливается на два сегмента, N1-N2 и N3-N5. Происходят выборы в majority и побеждает N5.
  3. Клиент соединяется с majority и выполняет запись. Она завершается успешно, operationId = 426 возвращается от сервера.
  4. Пропадает связь между клиентом и кластером
  5. (Новый) клиент соединяется с N1 (потому что может)
  6. Производится чтение. N1 отвечает старыми данными (он в изоляции но для реплики это не важно, плюс он может еще не осознавать network split).

Если бы использовался старый instance, на чтение пошел бы запрос Read(operationId >= 246) и узел бы ждал лога (может быть — ответил бы, что есть split и нужно пробовать другие серверы). А так — это новое соединение без определенной позиции в логе.

Вот таким образом своя реализация reconnect'ов — это собственоручно аккуратно разложенные грабли.

В целом curator мне не понравился на тот момент. Он не использует возможности zookeeper (вроде watches и т.п.). Те реализации, которые я видел, можно запускать на базе данных или с rest API в качестве backend. Там общие таймауты, чтение/проверка состояний и т.п. Мне было проще реализовать алгоритмы на zkClient чем разбираться, корректно ли работает curator.

Пара практических рекомендаций


В целом на zookeeper работать просто. Созадете клиент (один!) и не меняете до тех пор, пока он не сигнализирует фатальную ошибку. Повторы соединений и прочий fault tolerance он сделает сам. В рамках экземпляра у вас есть строгая линейность (вы не видите старых данных, клиент следит за позицией в логе и двигает ее только вперед). В случае отказов вы скорее получите ошибку связи. Потом клиент восстановится и вы можете повторить операцию. Immediate consistency у вас нет, но линейность есть.

И еще. Для всяких вещей вроде leader election вам нужно работать с сессией в рамках клиента. Т.е. leader привязан не к zkClient, а к сессии. Умерла сессия (вроде бы есть watch) — нужно все начинать с начала. Сессия связана с понятием "keep alive". Вы считаетесь online только в рамках одной сессии. Когда она упала — все ephemeral nodes удаляются (и может возникнуть другой лидер). Но при этом zkClient все равно может корректно хранить глобальный счетчик операций кластера и восстанвливать чтение в "правильной" точке журнала.
Re[2]: ZooKeeper vs Chubby
От: A13x США  
Дата: 26.03.20 21:35
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, A13x, Вы писали:


A>>насколько проблемы consistency мешают в реализации насколько возможно корректного leader election используя ZooKeeper/альтернативый вариант как distributed lock service?

WH>Проблема распределённого консенсуса с почти нулевыми накладными расходами решена.
WH>К сожалению, автор оказался не хорошим человеком. Запатентовал алгоритм и начал делать на нём очередной биткоин.
WH>https://www.hedera.com/whitepaper
WH>кнопка Download the whitepaper
WH>раздел
WH>THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM: FAIR, FAST, BYZANTINE FAULT TOLERANCE
WH>Если из алгоритма выкинуть криптографию (она не для всех задач нужна) то латентность должна быть не больше чем у любого другого алгоритма.
WH>Лично я почти уверен, что это оптимальное решение.
WH>Ну, или очень близкое к нему. Просто по тому, что накладных расходов почти нет. Оптимизировать почти нечего.

Интересный вариант. Нарыл еще ссылку на несколько deep dive talks: https://hipnplay.com/en/download/deep-dive-formal-methods-hedera18-LS02cTE1eXRJT0UzVQ которые еще не было времени прослушать.

Хочу еще отметить, что прелесть lock service типа Chubby в том, что при желании использующим его сервисам не нужно использовать на своей стороне consensus protocol основанный на majority. Выбрать master (=> make progress) можно даже при наличии двух или даже одного участника:

Developer friendliness: it is far easier to add locking semantics than consensus-based mechanics.

Event notification with data: most frequent use case — an application needs to write and read small amount of data in a consistent manner.

Application progress: paxos requires majority of applications to be up to make progress. In centralized lock service even a single one would suffice
as long as it has correct access to locks.

Re[3]: ZooKeeper vs Chubby
От: WolfHound  
Дата: 26.03.20 22:18
Оценка:
Здравствуйте, A13x, Вы писали:

A>Хочу еще отметить, что прелесть lock service типа Chubby в том, что при желании использующим его сервисам не нужно использовать на своей стороне consensus protocol основанный на majority. Выбрать master (=> make progress) можно даже при наличии двух или даже одного участника:

Hashgraph тоже может. Там большинство определяется не большинством узлов, а большинством голосов. У каждого узла может быть разное количество голосов.
Причем суммарное количество голосов и количество голосов у конкретного узла может меняться со временем.

Собственно так hedera и работает.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: ZooKeeper vs Chubby
От: Cyberax Марс  
Дата: 29.03.20 04:19
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Проблема распределённого консенсуса с почти нулевыми накладными расходами решена.

WH>К сожалению, автор оказался не хорошим человеком. Запатентовал алгоритм и начал делать на нём очередной биткоин.
WH>https://www.hedera.com/whitepaper
Я не вижу в чём отличие от обычных известных уже CRDT — https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

Они в любом случае не решают проблемы, которыми занимается ZooKeeper. В частности, гарантированные блокировки.
Sapienti sat!
Re[3]: ZooKeeper vs Chubby
От: WolfHound  
Дата: 29.03.20 15:37
Оценка:
Здравствуйте, Cyberax, Вы писали:

C>Я не вижу в чём отличие от обычных известных уже CRDT — https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

Хотя бы в том, что CRDT всегда находятся в валидном состоянии.
Тут же для прогресса нужно общение.
Хвост очереди не упорядочен.

C>Они в любом случае не решают проблемы, которыми занимается ZooKeeper. В частности, гарантированные блокировки.

А hashgraph решает.
Имея очередь сообщение, у которой гарантирован идентичный порядок на всех узлах, сделать блокировки тривиально.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: ZooKeeper vs Chubby
От: Cyberax Марс  
Дата: 29.03.20 20:03
Оценка:
Здравствуйте, WolfHound, Вы писали:

C>>Они в любом случае не решают проблемы, которыми занимается ZooKeeper. В частности, гарантированные блокировки.

WH>А hashgraph решает.
WH>Имея очередь сообщение, у которой гарантирован идентичный порядок на всех узлах, сделать блокировки тривиально.
Я не очень понимаю как он это может сделать без обмена сообщениями между кворумом узлов кластера. И в чём конкретно тогда отличие от обычного кворумного голосования.
Sapienti sat!
Re[5]: ZooKeeper vs Chubby
От: WolfHound  
Дата: 29.03.20 20:19
Оценка:
Здравствуйте, Cyberax, Вы писали:

WH>>А hashgraph решает.

WH>>Имея очередь сообщение, у которой гарантирован идентичный порядок на всех узлах, сделать блокировки тривиально.
C>Я не очень понимаю как он это может сделать без обмена сообщениями между кворумом узлов кластера.
Несколько байт дополнительной нагрузки ему хватает, чтобы иметь нужную для консенсуса метаинформацию.
В остальном обыкновенная доставка сообщений госипом.

C>И в чём конкретно тогда отличие от обычного кворумного голосования.

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

У меня такое впечатление, что ты статью не прочитал.
Там очень подробно расписано, что да как.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[6]: ZooKeeper vs Chubby
От: Cyberax Марс  
Дата: 29.03.20 22:15
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>>>Имея очередь сообщение, у которой гарантирован идентичный порядок на всех узлах, сделать блокировки тривиально.

C>>Я не очень понимаю как он это может сделать без обмена сообщениями между кворумом узлов кластера.
WH>Несколько байт дополнительной нагрузки ему хватает, чтобы иметь нужную для консенсуса метаинформацию.
WH>В остальном обыкновенная доставка сообщений госипом.
Я тогда не очень понимаю что он вообще решает. В ZooKeeper и прочих Raft'ах основная проблема с пропускной способностью из-за того, что необходимо получить подтверждения от кворума участников. Я не вижу как это решается здесь.
Sapienti sat!
Re[7]: ZooKeeper vs Chubby
От: WolfHound  
Дата: 30.03.20 01:13
Оценка:
Здравствуйте, Cyberax, Вы писали:

C>Я тогда не очень понимаю что он вообще решает. В ZooKeeper и прочих Raft'ах основная проблема с пропускной способностью из-за того, что необходимо получить подтверждения от кворума участников. Я не вижу как это решается здесь.

Во всех остальных протоколах на каждое полезное сообщение будет О(количество узлов) дополнительных сообщений для согласования.
А тут каждое сообщение становится на несколько байт тяжелее и все. Сообщение тебе все равно придётся разослать на все узлы.
Кворум определяется локально глядя на эти несколько байт.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[8]: ZooKeeper vs Chubby
От: Cyberax Марс  
Дата: 30.03.20 04:46
Оценка:
Здравствуйте, WolfHound, Вы писали:

C>>Я тогда не очень понимаю что он вообще решает. В ZooKeeper и прочих Raft'ах основная проблема с пропускной способностью из-за того, что необходимо получить подтверждения от кворума участников. Я не вижу как это решается здесь.

WH>Во всех остальных протоколах на каждое полезное сообщение будет О(количество узлов) дополнительных сообщений для согласования.
WH>А тут каждое сообщение становится на несколько байт тяжелее и все. Сообщение тебе все равно придётся разослать на все узлы.
WH>Кворум определяется локально глядя на эти несколько байт.
Я не понимаю как это работает, даже после чтения статьи. Можно в двух словах?
Sapienti sat!
Re[9]: ZooKeeper vs Chubby
От: WolfHound  
Дата: 30.03.20 15:48
Оценка:
Здравствуйте, Cyberax, Вы писали:

C>Я не понимаю как это работает, даже после чтения статьи. Можно в двух словах?

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

Давай поиграем в техническую поддержку.
Ты точно читал раздел
THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM: FAIR, FAST, BYZANTINE FAULT TOLERANCE
Ибо в той PDF'ке много чего не относящегося к делу.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[10]: ZooKeeper vs Chubby
От: Cyberax Марс  
Дата: 30.03.20 17:36
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM: FAIR, FAST, BYZANTINE FAULT TOLERANCE

WH>Ибо в той PDF'ке много чего не относящегося к делу.
Что же, начнём.

Стр. 6

So for n members to agree on a single YES/NO question might require O(n^2) voting messages to be sent overthe network, as every member tells every other member their vote.

Ложь. В Raft при обычной работе нужно O(n) сообщений — подтверждения от половины кворума, при выборе лидера нужно O(n*log N). O(n^2) нужно совсем упоротый алгоритм.

В общем, дочитал. Чуда нет. Для тех же гарантий, которые даёт Raft, в Hashgraph требуется, чтобы подграф был "strongly seen". Что требует (барабанная дробь) консенсуса от кворума узлов.
Sapienti sat!
Re[11]: ZooKeeper vs Chubby
От: WolfHound  
Дата: 30.03.20 18:52
Оценка:
Здравствуйте, Cyberax, Вы писали:

C>Ложь. В Raft при обычной работе нужно O(n) сообщений — подтверждения от половины кворума, при выборе лидера нужно O(n*log N). O(n^2) нужно совсем упоротый алгоритм.

Да ты просто звиздец как из контекста вырываешь.

Most Byzantine fault tolerance protocols without a
leader
depend on members sending each other votes. So for n members to agree
on a single YES/NO question might require O(n2) voting messages to be sent over
the network, as every member tells every other member their vote.

Raft использует лидера.
Это показывает, как ты читал. Что называется "гляжу в книгу вижу фигу".

C>В общем, дочитал. Чуда нет. Для тех же гарантий, которые даёт Raft, в Hashgraph требуется, чтобы подграф был "strongly seen". Что требует (барабанная дробь) консенсуса от кворума узлов.

А для этого консунсуса не требуется посылать даполнительные сообщения.
Там где у raft O(N) у hashgraph O(0).
И при этом у hashgraph нет лидера и всех проблем с этим связанных.

Единственная ситуация когда нужно посылать пустые сообщения это если полезный трафик прекратился и в хвосте очереди есть неупорядоченные полезные сообщения.
А это значит, что нагрузка на систему в этот момент около нуля и дополнительный трафик нужный для согласования погоды не делает.
Если же система разгоняется, то пустой трафик исчезает. Всё согласование происходит исключительно за счёт полезного трафика.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[12]: ZooKeeper vs Chubby
От: Cyberax Марс  
Дата: 30.03.20 20:05
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Raft использует лидера.

WH>Это показывает, как ты читал. Что называется "гляжу в книгу вижу фигу".

Я про это писал уже дважды. Hashgraph НЕ РЕШАЕТ проблем, которые решают Raft/Paxos.

C>>В общем, дочитал. Чуда нет. Для тех же гарантий, которые даёт Raft, в Hashgraph требуется, чтобы подграф был "strongly seen". Что требует (барабанная дробь) консенсуса от кворума узлов.

WH>А для этого консунсуса не требуется посылать даполнительные сообщения.
Бред.

WH>Там где у raft O(N) у hashgraph O(0).

Бред.

Берём такой пример:
1. У Васи есть кошелёк с 10 монетами.
2. Петя посылает сообщение узлу А: "перевести деньги с кошелька Васи в кошелёк Пети".
3. Одновременно Вова посылает узлу Б: "перевести деньги с кошелька Васи в кошелёк Вовы".

Локально каждый узел А и Б сообщения принимают, так как они непротиворечивы. Но глобально только одно из них может быть зафиксировано. И вот чтобы увидеть какое из них реально прошло — нужно ждать, пока кворум узлов не выберет одно из них. Сложность этого — O(N).

Так же нет возможности сделать consistent read, кроме как если эмулировать его через запись-блокировку.

WH>И при этом у hashgraph нет лидера и всех проблем с этим связанных.

Да. У hashgraph'а нет лидера, так что они невозбранно решают проблемы, которые этим были созданы.
Sapienti sat!
Re[13]: ZooKeeper vs Chubby
От: WolfHound  
Дата: 30.03.20 21:50
Оценка:
Здравствуйте, Cyberax, Вы писали:

WH>>Raft использует лидера.

WH>>Это показывает, как ты читал. Что называется "гляжу в книгу вижу фигу".
C>
C>Я про это писал уже дважды. Hashgraph НЕ РЕШАЕТ проблем, которые решают Raft/Paxos.
1)Ты сказал, что автор лжёт. Я показал, что это ты читать не умеешь. Ну, или намеренно пытаешься ввести людей в заблуждение. Ибо автор говорил про характеристики алгоритмов без лидера, а ты начал размахивать характеристиками алгоритма с лидером.
И теперь вместо того чтобы признать что был не прав пытаешься соскочить с темы.
Боишься признать, что это ты не прав, а не автор.

2)Как это не решает?
Очередь, у которой порядок одинаковый на всех узлах решает все проблемы распределённого консенсуса.

WH>>А для этого консунсуса не требуется посылать даполнительные сообщения.

C>Бред.

WH>>Там где у raft O(N) у hashgraph O(0).

C>Бред.
Если ты что-то не понимаешь, то это не значит что это бред.
Как я уже говорил единственный случай, когда hashgraph должен посылать сообщения исключительно для консенсуса это низкая активность системы.
И даже в этом случае, который по понятным причинам совершенно не интересен, у нас дополнительных O(N) сообщений. И это без лидера.

C>Локально каждый узел А и Б сообщения принимают, так как они непротиворечивы. Но глобально только одно из них может быть зафиксировано. И вот чтобы увидеть какое из них реально прошло — нужно ждать, пока кворум узлов не выберет одно из них. Сложность этого — O(N).

Только в реальной жизни будет поток сообщений.
В случае с hashgraph Эти два сообщения попадут в конец очереди. И будут не упорядочены. По мере поступления новых сообщений в очередь hashgraph упорядочивает старые.
Как только сообщения получат порядок, они будут переданы на прикладной уровень. Для hashgraph сообщения просто набор байт. Что с этими байтами делать решает прикладной уровень.
Прикладной уровень просто выполняет сообщения последовательно.
Он переведёт деньги первый раз. А на второй раз скажет деньги кончились.
И так как у всех узлов одно состояние, один код и один порядок сообщений то все узлы получат один результат.

C>Так же нет возможности сделать consistent read, кроме как если эмулировать его через запись-блокировку.

Тебе какой уровень консистентности нужен?
Если тебя устроит что клиент всегда видит монотонную последовательность изменений вне зависимости от того к какому серверу обращается то это тривиально.
Нужно просто хранить номер раунда последнего чтения. Как вариант можно сообщения пронумеровать, это тривиально. И посылать его на сервер при очередном чтение. Если у состояния сервера номер меньше, то сервер ждёт пока не дойдут сообщения. Ожидание будет редким и не долгим. После чего отправляет консистентный ответ.
Это самая сильная практически полезная гарантия.
Зачем нужно что-то большее я вообразить не могу.

WH>>И при этом у hashgraph нет лидера и всех проблем с этим связанных.

C>Да. У hashgraph'а нет лидера, так что они невозбранно решают проблемы, которые этим были созданы.
Главная проблема алгоритмов без лидера минимум O(N^2) дополнительных сообщений.
У hashgraph их O(0).

Я вообще не понимаю, что ты пытаешься доказать?
Hashgraph работает. Это математически доказанный факт. Если ты что-то не понял это твои проблемы.
Hashgraph имеет почти нулевые накладные расходы при большой нагрузке это тоже факт.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[14]: ZooKeeper vs Chubby
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 31.03.20 01:59
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>В случае с hashgraph Эти два сообщения попадут в конец очереди. И будут не упорядочены. По мере поступления новых сообщений в очередь hashgraph упорядочивает старые.


Я, честно говоря, тоже не понял как будет сделано подчеркнутое на каждому из узлов без обмена сообщениями и кворума. Не затруднит разъяснить?
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.