[erlang-questions] Priority Queue

Sat Jul 7 21:00:33 CEST 2007

Sorry, in second round reading only I understood what Jay explains better.
According to that router doesn't have a message queue, since as soon as a
message comes to it's queue, it reads and if message is not a control
message, it places the message in its internal priority queues.

I think that's a good model. However I will still let the sender to set the
message priority. I have to check the overhead involved in added message
passing (3N) and queue management in this case.

Originator -> Router (message)
Router manages the it's internal priority queues
Router -> Worker (message)
Worker -> Router (control message)

With this model, router can drop non-priority messages after a threshold, if
the logic requires. This is not possible with Erlangs' processes' message
queue.

Thanks Jay & Ulf,
- Eranga

-----Original Message-----
From: erlang-questions-bounces@REDACTED
[mailto:erlang-questions-bounces@REDACTED] On Behalf Of Eranga Udesh
Sent: Sunday, July 08, 2007 12:01 AM
To: 'Jay Nelson'; erlang-questions@REDACTED
Subject: Re: [erlang-questions] Priority Queue

Thanks for the detailed explanation.

However using a router process, I still don't see the priority queue problem
resolved, other than using a selective receive. Let's say there's a router
process, when received a message for processing, finds a free worker and
pass the message for it to process. The worker sends a control message to
the router when the processing finishes. Still that message comes to
routers' message queue and to extract it by giving it priority, the router
has to does a selective receive.

Taking your answering machine example, you know your message is important
and you are expecting Bill Gates to give priority for your message over the
other. Let's say Steve Jobs, Larry Ellison and you, all left messages in
Bill Gates answering machine, while he's out in Charity work. When Gates
returns and plays his answering machine, unless he listens to all 3
messages, he has no way of knowing what is important to him. So it requires
a mechanism for the message leaver to flag important messages (eg. key
press). To retrieve the urgent messages first, the answering machine needs
to have,
1. Have a second button to listen to urgent messages
2. Place the urgent message as the 1st message in listening queue
3. Gates will sound names or numbers of people or keywords in descending
priority order or program answering machine with that order (ignores the
priority flag by the message leaver)

(3) above is very much impractical. 

It's like "Importance" flag in Email. It's up to the sender to mark the
message as important, but it's always receivers' who will accept it's as
important or not (for actioning). Therefore,
1. Sender should be able to say a message is important or not.
2. Sender flags the message is important or not.
3. Receiver gets the important message before non-important messages in the
queue.

BRgds,
- Eranga

-----Original Message-----
From: erlang-questions-bounces@REDACTED
[mailto:erlang-questions-bounces@REDACTED] On Behalf Of Jay Nelson
Sent: Saturday, July 07, 2007 10:12 PM
To: erlang-questions@REDACTED
Subject: Re: [erlang-questions] Priority Queue

As Ulf pointed out I wrote some charts about priority messages for  
the 2006 EUC.  While it covers the topic, some of the notes now seem  
a little cryptic because they are in briefing format rather than as a  
descriptive document.  More embarrassingly the references to N!  
complexity should really be 2(N+1) (instead of multiplying the  
factors N, N-1, N-2 ... 1 they should be added to get the complexity  
since the position of messages in the queue is never modified).  So  
in the end it turns out to be linear complexity, but with large  
queues the problem is big enough to cause serious delays as others  
pointed out earlier.

The discussions about extending the language were concluded with no  
change because it really is an internal optimization issue.  The  
current mechanism in the messaging system is simple and reliable, but  
could be improved to handle selective receive better -- although all  
the suggestions only sped up simple cases and made no difference in a  
complicated set of multiple selective receive statements.

The main discussion in the slides was geared at beginner to  
intermediate erlang programmers, but was also intended for experts to  
step back and remember the fundamentals.  It is easy to get overly  
sophisticated in messaging situations when adhering to a few simple  
principles can make a complicated solution simpler.  And simplicity  
can often lead to the discovery of more efficient or better  
performing solutions.

Selective receive is indeed the most powerful approach, however, it  
also is easier to make a mistake with by leaving messages in the  
queue that choke the system over time, or by creating too many scans  
across the message queue.  When you find yourself confronted with  
multiple receive statements spread across separate functions and a  
poorly performing system, consider revisiting the problem and adding  
processes to filter the queue more finely.  Especially now that we  
have SMP support.

Eranga wrote:

 > A simple solution would be to extend Erlang process/message  
passing model to
 > enable to originate priority and normal type messages. When it's a  
priority
 > message, the message is placed at the beginning (head) of the  
queue. When
 > it's a normal message, it's placed at the end of the queue.
 >
 > Taking gen_server as an exmaple there're 2 functions,
 >	gen_server:pri_call/2/3
 >	gen_server:pri_cast/2
 > when run, it places the new message at the beginning of the  
message queue to
 > the gen_server process?

Philosophically, I don't believe it is correct for the sender of a  
message to determine the priority.  If I call Bill Gates and leave an  
urgent message on his answering machine, I may not be aware that he  
is currently in negotiations with Steve Jobs about a new product (my  
standing falls below Jobs but above Larry Ellison) and thus should  
not be urgent.  The point is that the sender of the message has no  
information other than that it would like a response quickly.  Only  
the aggregator or receiver has a global view (and even then it might  
not be inclusive, as new processes are added later) and can determine  
the proper priority.  It would be even worse to rearrange the message  
order externally rather than tagging the messages, but even tags  
require the entire system to have global knowledge of all  
priorities.  Any adjustments would ripple through every process that  
can send a message to the priority queue process.

A better design encapsulates the knowledge in one place so that it  
can be tweaked and tuned to improve performance without modifying the  
rest of the system.  Create a router process and send the  
undifferentiated stream of messages to it.  The router can be a pure  
erlang implementation of the mailbox semantics you would like to  
see.  It should immediately unload every message to an internal queue  
(with only two priorities you can use two queue instances, with more  
you may need the ets or gb_trees approach).  The messages can then be  
forwarded from the router to different processes.  The problem is  
that you need to pause all processes except the highest one that  
currently has messages in the queue, thus the need for control  
messages between router and workers and the desire to keep the worker  
queues empty so that the signals can be recognized without much  
overhead.

The big advantage with a router process is that you don't have to  
allow high process to hog all the CPU.  If you recognize the  
situation where high outnumbers low by a lot, you can periodically  
cede control to the low priority processes.  You can only determine  
if this is necessary in a running system by measurement and tuning.

So here is the real tradeoff when trying to do priority messaging:

1) The cost of selective receive could be high when a burst of  
messages arrives
2) Splitting to a router gives more control, but more latency in the  
message delivery and more overall resources used by the erlang node

Use technique #1 and model your message traffic profile.  If it is a  
problem your queue will get large and stay that way for a minute or  
more, and you will start to see large latency in the handling of  
messages.  Switch to method #2 and see if you can reduce overall  
packet latency by managing the routing yourself.  The key to getting  
this right will be the method used for controlling which process runs  
and how the traffic is doled out.  If you have a problem in case #1,  
you should be able to improve latency using case #2 even though there  
is an intermediary for messages -- the problem will come if the  
router collects messages faster than it can get them serviced.

jay

_______________________________________________
erlang-questions mailing list
erlang-questions@REDACTED
http://www.erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
erlang-questions@REDACTED
http://www.erlang.org/mailman/listinfo/erlang-questions