[erlang-questions] Priority Queue

[Jay Nelson]

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