Походу никак... :)

у тебя там на 115 строке баг:

if (!ind>=0)

лишний "!"

в итоге условие всегда истинное, даже когда ind === -1. В этих случаях splice мгновенно, за O(1), удаляет последний элемент. Массив стремительно уменьшается, последующие итерации отрабатывают быстрее.

Если поправить баг, то всё норм.

для этого давным-давно придуманы самобалансирующиеся деревья. Красно-черное, АВЛ, и т.д.

И действительно.
Исправил.

Все зависит от работы с этим деревом. Когда мы говорим про O(log2N), то мы оцениваем количество операций сравнений при поиске в дереве. Когда работа - часто-часто ищем и иногда добавляем/удаляем, то все хорошо.
Когда работа - найти, если нашли удалить, если не нашли добавить - то самобалансировка будет происходить очень часто. А она тоже требует времени. А если сравнивать время на операцию сравнения, и время на балансировку, то не понятно сильно ли большим будет выигрыш.

voraa,
балансировка - накладные расходы, это да. Но она занимает по времени не более O(ln(n)), т.е. на больших объемах это всё равно копейки по сравнению с возможным растягиванием дерева и временем O(n).

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

а какая проверка делается в п.3? всей очереди, или только первого элемента?

и как извлекается первый элемента? как устроена очередь? если это просто массив с операцией shift, то может работать долго на длинной очереди.

Логичнее было бы любой приходящий запрос помещать в очередь.
А когда какой то запрос реализуется и элементы из buffer удалятся, проверять всю очередь в поисках запросов, которые могут быть исполнены в данный момент.
Очередь в виде списка можно сделать.

Когда запрос приходит, можно быстро проверить по хэшмэпу обоих его участников и если свободны, сразу отправить в обработку. Зачем им кого-то ждать? Автор ничего не говорил про лимит одновременных обработок...

а вот кейс проверки всей очереди выглядит как узкое место, если очередь длинная. Здесь и надо как-то оптимизировать. Самое простое - сделать хэшмэп с очередями по каждому участнику. Освободилась пара [Вася, Петя], берем очереди по Васе и Пете и просматриваем их параллельно (в элементах очереди должен быть ещё таймстамп, когда добавили). В итоге мы найдем либо задачу снова [Вася, Петя], либо задачи [Вася, Х] и [Петя, Y], где X и Y отсутствуют в хэшмепе занятых. Вот эти задачи можно запускать в обработку, не забыв удалить элементы из персональных очередей для Вася, Петя, X и Y.
Худший случай - когда в этих очередях будет дохрена пар [Вася, А] и [Петя, Б], где А и Б - занятые. Что с этим делать, как их быстро поскипать, пока не совсем понятно.

про очередь в виде списка согласен. Можно добавить ещё пул элементов, чтобы их переиспользовать, не создавать каждый раз новые объекты.

Тут вопрос очередности. В какой момент мы берем только что пришедший запрос, и в какой момент из очереди.
Допустим косяком идут запросы со свободными, и вдруг появляются в очереди запросы, которые могут быть исполнены
Например освободились А и Б. Но в очереди есть А-Б и приходит запрос Б-А. Усложняется алгоритм выбора, какой запрос исполнять.
А поместив пришедший в очередь, и если просматривать всю очередь, а не только начальный, мы все равно выберем то, что может быть исполнено.

Пул свободных это ведь тоже список.
Нам не ведомо, что быстрее на js создание нового объекта (это какая то внутренняя достаточно быстрая операция) или помещение и извлечение объекта из списка. (это уже программа, с интерпретацией байткода, вызовы функций, что тоже не самая дешевая операция)

Тут все дело в конкретных условиях. Если в очереди тысячи запросов, то как то надо оптимизировать. Если десятки, то вся эта оптимизация съесть все время.

При освобождении А и Б, из очереди немедленно будет забрана задача А-Б. Запрос Б-А никак не сможет воткнуться между этими действиями и в любом случае добавляется в очередь.

Меня тут больше смущает другой кейс: обрабатывается А-Б, в очереди сидит А-С, пришёл запрос С-Д. Вроде как он свободен и можно запускать, но тогда для участника С он выполнится до предыдущего. Если так нельзя, то надо проверять участников не только в хешмэпе текущих обрабатываемых, но ещё в хешмэпе персональных очередей, о котором я говорил выше. И если там нашлось, то ставить в очередь.

Ну это понятно :) мы тут обсуждаем оптимизацию, предполагая что там дохрена всего и оптимизировать надо )

Ну если там ТАК много запросов, тут тут уж пора кластеризацию обсуждать, микросервисы там, Redis, Kafka, связность, отказоустойчивость... :D

А на деле у автора вопроса там по 3,5 запроса в час.)

И всего этого можно избежать, если просто сразу поставить в очередь

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

Это тоже самое, что использовать WordPress или Bitrix для одностраничного сайта с одним номером телефона. Мало того, что они сами по себе тормозы лютые, так и ещё самое главное — зачем?

Готовые решения здесь совершенно неуместны, потому что они все избыточны, создают дополнительные зависимости, требуют бОльших мощностей и значительно отбирают скорость.

Исходя из логики программы — большинство запросов должны быть уникальными и выполняться сразу без использования очередей. Но мы должны быть готовы и к внеплановым ситуациям.

Лучшим решением всегда будет то, что создано специально под конкретную задачу с нуля.

Здесь играет роль только то, есть ли участники нового запроса в buffer или нет. Исходя из вашего примера С-Д выполнится первее, чем А-С, и это совершенно нормальное и правильное положение событий. Кто первый встал, того и тапки, как говорится.

Исходя из выше сказанного
это не так
А сначала должен что то передать С, что бы потом С мог передать это Д
Если сначала выполнять С-Д, то у С может этого не быть.
Задачу на корректнее ставить.

Так проверка наличия чего-либо проверяется как раз в момент операции. И эти данные участников хранятся в другом месте, не в очереди.

Если в момент операции выясняется, что у С нет того, что надо передать Д, то будет возвращен ответ "Операция не выполнена — не достаточно того-то".

И какой смысл С что-то передавать Д, если у него этого нет? Только если для DDOS-атаки.

Более того, т.к. операции выполняются считанные микросекунды, то выполнять предварительную проверку "Есть ли у С то, что он хочет передать Д?" перед добавлением в buffer — некорректно. Проверка может сказать "ДА, True, у C есть то, что он хочет передать Д", но пока эта проверка проводилась, то успела произойти другая операция и по итогу у С уже нет того, что он хочет передать Д.

Странно это для клиентов будет.
Я посылаю запрос А передает С 10 бочек апельсинов.
Потом посылаю запрос С передает Д 5 бочек апельсинов.
Мне приходит ответ, что у С ничего нет. И я долго чешу репу, куда же они делись. Ведь он должен был от А получить 10.

Корректнее выполнять операции с участием С, когда остальные операции с его участием уже выполнились.

Мы уже провели 100500 тысяч тестов и выяснили, что массивы чрезвычайно медленные. Для buffer идеальный кандидат Set(). Для pool — Map(). А так для обоих случаев может быть кандидатом и Object() — но он не всегда себя показывает достойно в тестах.

Т.к. в buffer (список обрабатываемых участников) хранятся только имена участников, то Set отлично подходит для этой задачи — как в реализации, так и в скорости.

В pool (очередь участников, которые не смогли попасть в buffer) у нас уже хранятся сами операции, состоящие из 2-х имен участников и действии, которые первый участник хочет сделать для второго. Т.к. Set может хранить только уникальные значения без ключей, то для pool подходит либо Map, либо Object.

:haha: Отправлять запрос может только сам участник инициатор операции — никто за него это сделать не сможет.

Если вы знаете, что вам участник А должен передать 10 бочек апельсинов, то очевидно же что вы не будете пытаться передать участнику Д 5 бочек, пока не убедитесь, что на вашем складе больше или равно 5 бочек.

А что для операции <A op B> в этом случае для Map является ключом, а что значением?
И как последовательно (или еще как) просматривать Map, не превращая его в массив?

Как можно просматривать этот пул? Взять одну операцию, посмотреть, может ли она быть выполнена, взять следующую и т.д.?

Что же в этом корректного? Исходя из такой логики операции вообще смогут никогда не выполниться, т.к. все будут постоянно друг друга ждать.

Нет не будут ждать. Как только очередная операция выполняется ее члены удаляются из буфера и просматривается очередь, на предмет того, какая операция может быть выполнена. Первая, которая может - выполняется. Можно и дальше просматривать, что бы послать на выполнение все, которые в этот момент могут быть выполнены. Но это гарантирует, что операции, например с участником А будут выполняться строго в последовательности, как они пришли.

Кстати да, неоднократно этот вопрос вставал как это делать. И сейчас пришла мысль — а может вообще отказаться от этого пула? Сейчас пришла такая мысль:

1. Если участников операции нет в buffer - добавляем в него и выполняем.
2. Если хотя бы один из участников есть в buffer, то делаем setTimeout() и пробуем до тех пор, пока не получится как в п.1

Причем это можно сделать как на стороне сервера, так и на стороне клиента.

Не самое лучшее, на мой взгляд, решение.
А пул - простой список.
Пришедшие операции добавляются в конец.
Есть два события: 1 - операция добавилась 2 - какая то операция выполнилась.
По каждому из этих событий мы просматриваем очередь от начала до конца. Если какая то операция может быть выполнена, то она отправляется на выполнение.

Опять же все завит от условий. Если в пуле десятки записей, то и массив с операциями push и splice будет прекрасно работать. Это внутренние хорошо оптимизированные операции.

Вообще pool хз откуда появился. Первоначально была задача решить реализацию buffer. И сейчас я понимаю, что этот pool просто не нужен. Это же не очередь за квартирой в Москве или какая-то доставка пиццы, где важно хранить очерёдность (потому что это занимает продолжительное время).

В 99% случаев для каждого участника операции будет свободное место в buffer. А если и не будет - то оно очень скоро освободится.

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

Если вы писали, что буфер на десятки тысяч (т.е это столько запросов, которые в данный момент выполняются / 2) , и даже больше, а в 99% случаев там нет участников очередного запроса, то на сколько же участников рассчитана эта система?

С чего это создастся очередь событий таймеров?) Сервер просто отправит сообщение браузеру типа "Щас не могу, попробуй попозже". На браузере принимается ответ и ставится таймер. По времени не более 1 секунды — иначе пользовательский UX начнет страдать. Оптимально 250-500 мс. Этого времени должно быть более чем достаточно, чтобы buffer освободился для ожидающего участника, т.к. операции выполняются мгновенно.

Опять же, вы забываете учитывать факт того, что это во всех случаях исключение, а не стандартный процесс.

Если бы участникам приходилось каждый раз ожидать, то здесь очевидно было бы реализация очереди. Но в 99,9999% случаев им ждать совершенно не придётся.

У меня сейчас такое впечатление складывается, что с внедрением очереди можно только навредить. Нет очереди — нет проблем.

Было сказано, что в буфер может добавляться до 30 тысяч участников в секунду — и это только на данный момент, в будущем пропускная способность может быть увеличена (есть зависимость от используемого алгоритма проверки).

А про реальную нагрузку было сказано, что это должно обрабатывать в районе не менее 1500 участников в секунду.

И заново отправляет тот же запрос? А потом в случае чего опять заново...
Во первых лишняя нагрузка на сеть, туда сюда гонять запросы с ответами, что выполнить не может. Нагрузка на сервер - получать лишние запросы, которые уже были.
Возможна такая ситуация, что пользователь А хочет что то передать С,
но идет много других запросов с С, которые по несчастливой случайности обрабатываются первыми, пока А сидит с timeout-ом. И он все сидит, сидит, запросы все идут и отклоняются.

Чем плоха очередь на сервере, я так и не понял.
Но вам виднее, я всей задачи не знаю.

Вы правы. Этому есть место быть.

Получается надо общую очередь всех запросов изначально хранить? Такая логика?:

1. На сервер поступают запросы и помещаются в pool

2. Из pool операции добавляются в buffer и удаляются. Если в buffer не может добавиться, то перемещается в конец pool

Так?

Не совсем.
pool - это не совсем очередь. Добавляется только в конец. А выбирается при просмотре от начала до конца все операции, которые могут быть выполнены.
Просмотр пула делается так
Берем операцию.
Проверяем, может ли она быть выполнена (участников нет в буфере).
Если может, то отправляем операцию на выполнение. При этом ее участники добавляются в буфер.
Берем след. операцию из пула
и т.д.
Т.е добавляем мы только в конец, а взять можем откуда угодно, просматривая пул. При этом взятая операция, конечно, удаляется из пула.

Просмотр пула инициируется при двух событиях:
- Новая операция добавлена в конец пула,

- Выполнилась какая то ранее отправленная на выполнение операция. При этом ее участники удаляются из буфера.

Такой алгоритм я предлагаю.

Получается что общая очередь всех операций не нужна?

Ваще так всё и предполагалось делать. Оставался вопрос лишь в реализации. Думаю для этого отлично подойдёт Map() с автоинкрементом по ключу.

Следующий найти будет трудно, если мы изъяли какие то после текущего.
Придется в цикле ключи перебирать.
И как взять первый? Перебрать все и найти минимальный?