Priority Queues

[Ulf Wiger (AL/EAB)]

You can do this (almost) using an ordered_set disc_copy
table in mnesia. The object key could be e.g. 
{Priority, erlang:now()} for prioritized FIFO, or
{Priority, negative(erlang:now())} for prioritized LIFO,
where

negative({MSec, Sec, MuSec}) ->
  {-MSec, -Sec, -MySec}.


1) Using dirty_first(Tab) and dirty_last(Tab), you can
   get to the first and last entries respectively.

2) The structure of the key determines the ordering.
   See above.

3) Not a big problem, but the entries will all be in 
   RAM (and logged to disk periodically)

4) Not constant time, but close enough (logN)

5) Persistence is taken care of by mnesia

6) To make this thread-safe, you need to either 
   serialize the operation using a server, or use 
   mnesia transactions. The transaction can for example
   return the next value for processing like so:
  
   mnesia:activity(
        dirty,
        fun() ->
            case mnesia:dirty_first(prio_queue) of
                '$end_of_table' -> queue_empty;
                Key ->
                    [Result] = mnesia:read(prio_queue, Key, write),
                    mnesia:delete(prio_queue, Key)
                    Result
            end
        end).

It's a little trickier if you want full atomicity, since there
is no mnesia:first/1. You can still do it like described above,
since you get synchronization on the read, and thus avoid the 
risk of race conditions or lost updates. However, you can get 
aborted transactions instead of proper serialization.

It's possible to use mnesia:select(Tab, Pattern, 1, write), 
which will, on an ordered_set, return the first object in the 
table matching Pattern, but it will be slightly more expensive
(esp. if this operation is called as a nested transaction, since 
the select() call has to scan the transaction store.)

Of course, the overhead of using transactions will be significant,
but mnesia:activity(dirty, ...) is not so bad. It's a very handy
way of packaging dirty operations.

/Uffe

> -----Original Message-----
> From: owner-erlang-questions@REDACTED
> [mailto:owner-erlang-questions@REDACTED]On Behalf Of 
> Rudolph van Graan
> Sent: den 16 maj 2005 08:24
> To: Erlang Questions
> Subject: Priority Queues
> 
> 
> Hi All,
> 
> I am currently thinking about the implementation of priority queues  
> in erlang. Specifically, what do you guys suggest as an 
> efficient way  
> to achieve the following:
> 
> 1. A queue with a definitive head and tail (i.e. first and 
> last records)
> 2. The items in the queue need to be sorted according to some  
> criteria that will always allow you to identify an entry as the  
> "first" or "next" one
> 3. The queue length can be massive (100's of thousands or 
> millions of  
> records)
> 4. Insertion time should be constant
> 5. The queue must be persistent (i.e. mnesia or dets)
> 6. Once the first/head entry has been processed, it will no 
> longer be  
> in the queue.
> 
> Any suggestions?
> 
> Rudolph van Graan
> 
>