From: richieb@bony1.bony.com (Richard Bielak)
Subject: RDB vs. OODB: Designing a queue
Organization: multi-cellular
Date: Wed, 30 Sep 92 20:23:15 GMT


In a earlier positing I mentioned that we were unable to design a
queue, using a relational database, and that this was the reason for
moving to OODB.  Few people suggested that I should post a more
detailed explanation.

Here it is. It can serve as an example of how OODB makes certain things
a lot easier.


PROBLEM DEFINITION:

  Implement a queue in a database. A queue is an ordered list of
items (we call them "messages"). Normally items are added at the end
and removed from the front (i.e. FIFO). Occasionally an item
has to be added at the front.

  Maximum concurrency is desired. That is, many programs maybe
adding/removing messages at the same. A program may lock a message for
a while (could be few minutes), however the queue should not be locked
for that long. For example, if the first message on the queue is
locked, another program should still be able to get to the second one.


RDB DESIGN:

The two main problems are: adding ordering to an rdb table and the
other is handling concurrency. 

Here are two ways we tried for adding ordering:

1) Have a column which specifies the sequence of insertion.

   Note that time stamp would not work, as we have to insert things
   at the head of the queue.

   You have to get a sequence number from somewhere. If this sequence
   number is in another table, then it will get locked until the
   transaction that also inserts into the queue is complete. This maybe
   too long. In most cases we need to keep the queue entry locked for
   a while (eg. while transmitting the message), but the queue should
   remain unlocked.

   Our solution was to use a server that would give out sequence numbers
   without locking the queue.

   How do you remove the first element from such a queue? You can do
   a READ MIN (or something like that in SQL) to get the first one.
   However, what if another program also wants to dequeue at the same time.
   The second program should get the second message. How do we get to 
   the second message in SQL?

   Now throw into this aborted transaction - eg. a program tried to
   dequeue something, but then gave up. The message should go back on
   the queue. This should work, while other programs are dequeueing
   at the same time.

2) Implement a doubly link list structure using rdb tables.

   We did not pursue this solution too far. You wind up with
   too many tables.

   This is like doing linked lists with arrays in FORTRAN.


Concurrency:

  The relational database we used did not provide row level locking, so
queue items could not be locked individually (unless of course you force
each row to be a database page). 

  The other problem is that SQL give you no control over locking things.
Locks are taken out by the database as it sees fit. There is also no
way to test if a given row is locked.




OODB DESIGN:


A queue is simply a doubly linked list of queue entries. Each queue
entry point to a message. The picture looks like this:


               *----------*
       ... --->|  next  --+---> ....
               |----------|
       ... <---+-previous |<--- ....
               |----------|
               |  item    |-----+
               *----------*     |
                                v
                             Message


If you have object level locking, a program can lock the "message" object,
without locking the "queue entry". The queue entries get locked only the point
when the is actually modified.


We implemented the OODB design and it works!


...richie


-- 
* Richie Bielak   (212)-815-3072   |                                          *
* Internet:       richieb@bony.com | Rule #1: Don't sweat the small stuff.    *
* Bang {uupsi,uunet}!bony1!richieb | Rule #2: It's all small stuff.           *
*    - Strictly my opinions -      |                                          *

-- 
* Richie Bielak   (212)-815-3072   |                                          *
* Internet:       richieb@bony.com | Rule #1: Don't sweat the small stuff.    *
* Bang {uupsi,uunet}!bony1!richieb | Rule #2: It's all small stuff.           *
*    - Strictly my opinions -      |                                          *