но не вместе. 🙂

а если не делать вообще схема апдэйт? Что за франкенштейн будет? Т.о. можно и вернуться будет на 1.10?

Рассмотрим, какова сложность коммита 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) примерно. Это ничто.

Напишите true -- сработает?