Priority queues

Here's an interesting concurrency problem. I have a working solution, but it's overly complex.

The problem: This is inside my client for a virtual world. Requests come in for "assets", which have an "id". Assets need to be fetched from a disk cache or HTTP and decoded, so this is a slow operation. Each request has a priority, which is a u32. Two queued requests for the same asset need to be combined into one, and the priorities added.

The queue feeds a number of worker threads which process the requests. If one thread is fetching an "id", no other thread should start working on that "id", since that would cause unnecessary I/O.

So here's the setup:

Requests->queue mgr thread->priority_queue->queue mgr thread->crossbeam_channel length 1->worker threads.

The queue mgr thread owns priority_queue, and provides an output channel of length 1 so the worker threads have something from which they can do a blocking read, waiting for work. The result is a "priority channel", which behaves like a channel but reorders and un-duplicates based on priority.

To prevent two threads from working on the same "id" at the same time, the worker threads share a struct which has a set of "id" values currently being worked on, and for each of those, a vector of stalled requests for that "id". When a worker thread gets a request from the channel which it can't do because "id" is in use, it puts that request on the vector of stalled requests for that "id" and skips it. When a worker thread working on "id" finishes with that "id", it checks the stalled requests for that "id" and handles them, then unlocks "id". Usually those additional requests are cheap, because the asset is now in memory and can be reused immediately.

All this works, but the way it behaves is unexpected. When a large number of requests for the same "id" come in all at once, and not all the worker threads are busy, a strange thing happens. Those requests ought to be combined in the priority queue. But if there's no backlog, each makes it through the priority queue immediately and is picked up by a worker thread. One worker thread starts work on the first request, and the others put the requests in the "stalled" vector. Then, one at a time, each request in the stalled vector is processed, discovered to be recently done, and discarded.

This is kind of silly. It doesn't actually hurt performance, because the silly case only comes up when there's no backlog and priorities don't matter. A cleaner solution would be nice, though.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.