[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
Thanks Jay & Ulf,
[mailto:] On Behalf Of Eranga Udesh
Sent: Sunday, July 08, 2007 12:01 AM
To: 'Jay Nelson';
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
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
[mailto:] On Behalf Of Jay Nelson
Sent: Saturday, July 07, 2007 10:12 PM
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
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.
> 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
> message, the message is placed at the beginning (head) of the
> it's a normal message, it's placed at the end of the queue.
> Taking gen_server as an exmaple there're 2 functions,
> 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
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
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.
erlang-questions mailing list
erlang-questions mailing list
More information about the erlang-questions