Handling Multi-Priority Requests

Wibble has asked for the wisdom of the Perl Monks concerning the following question:

Hi Monks,

I'm looking for some design oriented "I don't want to re-invent the wheel" type advice. I have a situation where multiple 'producers' on my quick and dirty servers (A,B,C,D,E) send asynchronous HTTP requests to a virtual IP address hosted on a load balancer which distributes the requests fairly across some slow and chunky closed VB 'consumers' on servers (X1, X2, X3, Y1, Y2, Y3, Z1, Z2, Z3). This is all fine and dandy and works a treat with LWP::UserAgent requests.

Whilst those requests are roughly the same, some of them are paid for and some are free. Therefore I would like to prioritise the paid for requests over the free requests - especially when the 'producers' get busy. I have considered dedicating some of the 'consumers' for paid for requests but this is less than efficient and doesn't handle peaks in free/paid request categories very well.

In this Internet age if you can think it then someone has done it, so I naturally thought of Perl. So I did some CPAN searching and came across the POE and POE::Queue::Array modules. I read around a bit on the success stories and examples and these modules look like a great starting point.

One solution, as I see it, is a piece of POE enabled perl-middleware sitting between my 'producers' and the 'consumers' sitting behind the load balanced virtual IP (VIP). The middleware would receive the asynchronous requests into a queue and leapfrog any paid-for requests over any free-requests before sending the requests onto the 'consumers' via the VIP.

Am I right to suspect that this is something that could be built using POE? Are there any Monks out there with any advice either way?

Cheers...

Comment on Handling Multi-Priority Requests

Replies are listed 'Best First'.
Re: Handling Multi-Priority Requests by jdporter (Paladin) on May 13, 2003 at 15:13 UTC
I just have one bit of advice. I wouldn't leap-frog the paid request ahead of all the free ones, because then, under heavy loads, the free requests get completely starved out until all the paid requests have been handled. Instead, I'd leap-frog each paid request ahead of all but one of the free requests. Then, under a typical heavy load, free and paid requests are popped from the queue in alternating order, but paid requests still get dispatched sooner (i.e. lower queue wait times) than free ones. (Update) Note that this will only make a difference when the rate of free request generation is significantly greater than the rate of paid request generation. jdporter The 6th Rule of Perl Club is -- There is no Rule #6.	[reply]
Re: Re: Handling Multi-Priority Requests by demerphq (Chancellor) on May 13, 2003 at 16:08 UTC
Instead, I'd leap-frog each paid request ahead of all but one of the free requests. A suprisingly subtle solution to an interesting problem. I like it. ++ to you. I'm actually somewhat suprised I've not heard of this before. --- demerphq _{<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...}	[reply] [d/l]
Re: Re: Handling Multi-Priority Requests by Wibble (Beadle) on May 13, 2003 at 16:17 UTC
Hmmm - I too hadn't heard of this method of being fair to free requests. I had thought of promoting free requests to paid requests the longer they wait, but this does seem easier. A ++ to you. Thanks for the Tip.	[reply]
Re: Handling Multi-Priority Requests by rcaputo (Chaplain) on May 13, 2003 at 16:26 UTC
POE::Queue::Array works stand-alone, so you could incorporate it into your existing program without using the rest of POE. You would create and manage your own POE::Queue::Array instance, enqueuing new requests as they arrive and dequeueing them in priority order. Following the UNIX convention, lower priorities are more important, so you might assign all paid requests a priority of 1000. Free requests would be assigned 2000 and would fall into line after the paid ones. POE's implementation ensures that items having the same priority are dequeued in first-in/first-out (FIFO) order. All the tasks within a service class are dequeued in the order they were enqueued. As jdporter pointed out, using a strictly priority-based queue will allow paid requests to starve out free ones. If you later need parallel processing and have the time, you can adopt the rest of POE and translate your (I assume) declarative program into something that works with events and callbacks. In the meantime, you don't have to do all that to take advantage of priority queues. Other priority queue modules to consider: Heap::Priority List::Priority Heap POE::Queue::Array (works stand-alone) POE::Component::JobQueue (requires the rest of POE, does many additional things)	[reply]
Re: Handling Multi-Priority Requests by derby (Abbot) on May 13, 2003 at 15:54 UTC
Or combine POE (or really any of the Priority modules) with this neat mod_perl load balancer to replace your VIP. Okay, maybe that's too much (too little?) for production use but it would be fun to play with. -derby	[reply]
Re: Handling Multi-Priority Requests by jackdied (Monk) on May 13, 2003 at 20:51 UTC
As the respones imply, the question was really "what is a fair priority algo for this?" Which is a more fickle question. Google can give you more answers than you care for. If the machines can handle all the requests, but you just want to have the paid requests have the quickest turn around times, then almost anything will work. If you don't have enough CPU for everyone, almost nothing will be satisfying. I'd go with a decorated list of (priority, request) items. Set the priority of paid requests to half of free requests (lower is better). Before you pop the top request subtract one from all the priorities and re-sort the list. Unless you have a billion items this will be so cheap in CPU time that fancier solutions aren't neccessary. -jack	[reply]
Re: Handling Multi-Priority Requests by cfedde (Novice) on May 14, 2003 at 03:51 UTC
The window of benefit for priority queuing in this scenario comes at the same point were the system starts to run into other performance bottlenecks. Consider this. When the system is lightly loaded there is not enough work in queue that prioritizing that work will make a significant improvement in performance. If anything a queuing algorithm will add a fixed overhead and reduce the base line performance by that amount. As the transaction rate increases and you start to see multiple transactions in queue then ordering them will start to make some difference between low and high priority work. But why is there a queue of transactions in the first place? It is because some system resource is at capacity and work has to wait for that resource to come available. So at the same time that we are getting some benefit from ordering the transaction queue transaction time itself is going up. Now the queuing algorithm is prioritizing the higher value transactions which is good. But each transaction is taking longer, which is bad. I am arguing that the benefits of the queuing algorithm are off set by the penalty of running the system at high enough loads for the algorithm to pay off.	[reply]
Re: Handling Multi-Priority Requests by Anonymous Monk on May 13, 2003 at 18:22 UTC
I think that adding a biasing factor to low priority work would be nearly as effective as complex queuing models with just about as much performance overhead. A simple implementation would be causing the producer to sleep for a few milliseconds before submitting low priority requests to the consumer.	[reply]