ну раз ты так говоришь, то ладно

а потом будем говорить что рафт не масштабируется на большое число узлов, так?

еще б это правда такая сложность была, damn

но тебе виднее

потому что мы будем по каждому ack пробегать по списку limbo и делать ++!

*каждой* entry в списке

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

все верно, ты победил

блин, мой заговор раскрыт

как жить теперь с этим?-)

теперь я отправлюсь в изгнание

и это ещё не самое оптимальное что есть.

Рассмотрим, какова сложность коммита N синхронных транзакций. Во-первых, достаточно очевидно, что это будет "что-то" * N. Потому что как минимум нужно разбудить файбер каждой закоммиченной транзакции, и саму транзакцию из памяти удалить. Каждую из N. Но каково значение этого множителя "что-то"?

В это значение входит как минимум сборка аков. И собирать их есть два способа. Первый - ак транзакции сразу увеличивает в ней счетчик ack_count. Если видно, что аков у транзакции набралось >= quorum, то коммитим ее. Аков надо собрать quorum штук. Обозначим его Q. Итого, алгоритмическая сложность такого способа: Q. Столько инкрементов ack_count будет сделано на транзакцию.

Тогда такой способ на коммит N транзакций дает сложность O(N * Q). И не важно, приходят подтверждения транзакций пачкой с реплики или нет. В любом случае такой способ подразумевает Q раз увеличить N счетчиков, разбудить N файберов, и удалить N struct txn объектов (раз уж мы тут исходниками кидаемся).

Я подчеркиваю, что Q - это просто ++ в С. Кроме того, Q <= 31, так как это максимальное число реплик в репликасете. В синхронном репликасете их почти всегда будет 3-5.

По такому раскладу я не понимаю, как эти 3-5 инкрементов int переменной в С способны повлиять на что-либо. Особенно в алгоритме, реализация которого вовлекает работу с сетью.


Но есть еще второй способ. Он поможет, если транзакции подтверждаются пачками. Для этого надо вспомнить, что ack пачки транзакций от реплики описывается LSN (наибольший среди подтвержденных транзакций. См статью Влада, кто не понимает.).

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

Тогда коммит N транзакций, если они пришли пачкой со всех реплик (самый лучший случай), будет стоить N * "сложность обновления вот этой структуры данных с LSN-ами".

Что это за структура? Я понятия не имею. Но по требованиям выглядит похоже на binary heap. Только нам надо за O(1) находить не самый меньший элемент, а самый меньший такой, что Q других элементов в этой куче >= него. Допустим, такой алгоритм существует. И обновление такой кучи будет как у любой кучи - O(log(Q)) (я беру Q, так как там всегда будет >= Q элементов).

Тогда самое оптимальное, что можно получить в теории будет O(N * log(Q)). А теперь вспомним, что Q - это обычно 3-5. То есть мы говорим о разнице N * 5 vs N * log(5). Это будет примерно 5N vs 3N. В количестве операций записи в переменную в С. Я тут не беру, что будет еще N побудок файберов и освобождений памяти транзакции, таплов, и тд.

Мне бы очень хотелось увидеть бенч, на котором эти инкременты ack_count на компилируемом языке будут жрать больше, чем апдейт такого вот мифического хипа. На фоне работы с сетью. Измеримо больше.

По поводу ссылки от Кости. Если ее открыть, то там можно увидеть следующее: "insertionSort(srt)". То есть они пошли по второму пути, но вместо некой специальной кучи используют сортированный массив или что-то вроде того. Я не уверен. Что правда будет хуже, чем линейная сложность наверное. Но опять же, мы говорим о 5 vs log(5) примерно. Это ничто.

Добрый вечер! Подскажите про совместимость реплик между 1.10 и 2.6.2
Задумали мы обновить существующую реплику с 1.10  до 2.6.2. Возник вопрос: когда то тут проскакивала мысль о несовместимости реплик. Толи вообще не совместимы, толи апгрейд/даунгрейд. Страх в чем, если начать перезапускать тарантулы по очереди в реплике, будет ли оно одновременно работать(временно, на время рестарта всех тарантулов в репликасете) - часть на 1.10, часть на уже 2.6.2. И если да, то как это правильно сделать(обновиться)?

Может кто уже прошел этот путь?

1.10 и 2.6 совместимы
Можно работать так, что мастер - 1.10, а реплики - 2.6
Процедура апгрейда такая. Берём одну реплику и перезапускаем на 2.6
Она должна подцепиться к мастеру и работать нормально.
Если всё хорошо, то остальные реплики тоже перезапускаем на 2.6
Дальше переключаем мастера на один из узлов 2.6, а старого мастера рестартим.
И последний шаг - на новом мастере позвать
‘box.schema.upgrade()’
И затем ‘box.snapshot()’

Кажется, 1.10 тоже может быть репликой до 2.6, но надо проверить

а если M-M реплика?

Тоже всё должно быть хорошо