search

OptimalBits / bull

Premium Queue package for handling distributed jobs and messages in NodeJS.
Other
15.26k stars 1.43k forks source link

Performant Priority Queues #1866

Open zebulonj opened 3 years ago

zebulonj commented 3 years ago

I've been using Bull for more than a year in a large-scale, high-performance application (1000+ jobs per minute, 24/7)... and am very happy with it. On the horizon I have the need to add priority to our queues, but O(N) performance per insert is likely going to pose a problem (I expect to be dumping upwards of a million jobs at a time into queues on a regular basis). Opening this issue because I'm interested in learning whether there has been any discussion of more performant architectures for handling priority via Bull queues. Off the top of my head, I'd be interested in running three or four fixed priority queues (where each queue represented jobs of the same priority), with the set of queues feeding into workers that each pull from the highest priority queue with a pending job... thereby removing the need to sort jobs within a queue based on priority.

I'm happy to toss around ideas and ultimately contribute code. Just thought I'd raise this with the community before I invest in any particular path.

manast commented 3 years ago

The original implementation of priority queues used a queue for every priority, but it gets messy and difficult to avoid all special cases. The current implementation is much more solid and simple so thats a really good thing. Ideally, what we would like is to use a ZADD to store the prioritized jobs which will get us O(log(n)). However in redis we lack commands for reliably consume from a ZSET in blocking fashion. Blocking is actually not super important with the current design, since next jobs are returned after the completion of the current job, so if we add polling it would only be used when the queue is drained waiting for new jobs to arrive, for busy queues it would be no different than now, and for non busy queues it wouldn't matter since they are not busy :). So, it would be possible to re-implement priority queues using ZSET, however I do not think that would be implemented in Bull but rather in BullMQ. If it is done smart it could be done without breaking backwards compatibility.

zebulonj commented 3 years ago

However in redis we lack commands for reliably consume from a ZSET in blocking fashion.

Would ZPOPMIN and BZPOPMIN not be effective? Mostly an academic question, since you say blocking is not important in the current design.

manast commented 3 years ago

@zebulonj they are not good enough because they just pop the element from the set, so if the guy popping the element dies for some reason, that job will be in a undefined state. We would need a command like "BZPOPMINLPUSH", that pops and atomically pushes the element to a list, then you can safely move a job from priority list to active list.

manast commented 3 years ago

but if we do not care about blocking then it is trivial, we can just have a command that consumes from ZSET and pushes in LIST atomically using lua.

stale[bot] commented 2 years ago

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

roggervalf commented 3 days ago

this is better handled since bullmq v4 https://github.com/taskforcesh/bullmq/blob/master/docs/gitbook/changelogs/changelog-v4.md#400-2023-06-21 where insertions is O(log(N))