Special Conditions and PriorityBlockingQueue

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Special Conditions and PriorityBlockingQueue

David Walend
In the SomnifugiJMS project, I'm getting close to implementing the  
full JMS specification. The last big technical hurdle is implementing  
message selectors for JMS Queues. (Message selectors are these odd  
bits of SQL92 that make sure a particular queue only receives  
messages with particular properties represented as key/value pairs.)

Currently, JMS Queues are wrapped around BlockingQueues, usually  
PriorityBlockingQueues. I just looked at the PriorityBlockingQueue  
code, which wraps a ReentrantLock and a notEmpty Condition around a  
PriorityQueue.

Message selectors in Topics were fairly easy. Each subscriber to a  
topic gets its own BlockingQueue. If a subscriber's message selector  
doesn't match the message, the message doesn't drop into that  
subscriber's BlockingQueue.

That approach won't work for JMS Queues. All QueueReceivers currently  
work off the same BlockingQueue, and I'd like to keep that abstraction.

I have two vague ideas for how to get message selectors working for  
JMS Queues, neither of which is great. I'd like to get some feedback  
before trying either.

Multiple Conditions: Write a custom BlockingQueue with a Condition  
for each message selector. Start with the code for  
PriorityBlockingQueue. Add custom code to create a Map<JMS  
QueueReceiver with a MessageSelector,Condition>, that holds waiting  
receivers. When a message enters the queue, check the waiting  
receivers to see if any message selectors match the message; if so,  
signal that receiver's take() or poll() call. When a receiver first  
take()s or poll()s or is signaled by its Condition, iterate through  
the queue for a matching message. If there's a message, return it and  
(if needed) remove the entry from the Map. If no message matches, add  
the receiver to the Map.

Multiple BlockingQueues: Use a Map<MessageSelector,BlockingQueue>,  
with one entry for each MessageSelector plus one for all messages:  
When a new QueueReceiver with a new MessageSelector is created, add a  
new entry to the Map. When a message is sent, check all the  
MessageSelectors, and place the message in all the corresponding  
BlockingQueues. When a QueueReceiver takes() a message successfully,  
remove() it from all the BlockingQueues. Fold all this into a class  
that implements BlockingQueue.

Neither approach is without problems. The first requires creating  
Conditions dynamically, which the example code doesn't do, plus  
iterating through the queue (could be mitigated by holding onto the  
matching message). The second has this traffic jam of remove()ing  
from multiple Queues. I'll take any advice on where to start.

Thanks,

Dave

David Walend
[hidden email]


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Special Conditions and PriorityBlockingQueue

tpeierls
No responses! Maybe because your analysis seems to be bang-on: neither approach is very satisfactory. Maybe the problem is inherently not addressable (at least not nicely) by composing BlockingQueues?

I can't find a clear statement in the JMS spec of just what is required here, otherwise I'd try to figure out another approach. If you expanded a little on your introductory paragraph, I bet you could make it clear.

--tim

On 9/23/06, David Walend <[hidden email]> wrote:
In the SomnifugiJMS project, I'm getting close to implementing the
full JMS specification. The last big technical hurdle is implementing
message selectors for JMS Queues. (Message selectors are these odd
bits of SQL92 that make sure a particular queue only receives
messages with particular properties represented as key/value pairs.)

Currently, JMS Queues are wrapped around BlockingQueues, usually
PriorityBlockingQueues. I just looked at the PriorityBlockingQueue
code, which wraps a ReentrantLock and a notEmpty Condition around a
PriorityQueue.

Message selectors in Topics were fairly easy. Each subscriber to a
topic gets its own BlockingQueue. If a subscriber's message selector
doesn't match the message, the message doesn't drop into that
subscriber's BlockingQueue.

That approach won't work for JMS Queues. All QueueReceivers currently
work off the same BlockingQueue, and I'd like to keep that abstraction.

I have two vague ideas for how to get message selectors working for
JMS Queues, neither of which is great. I'd like to get some feedback
before trying either.

Multiple Conditions: Write a custom BlockingQueue with a Condition
for each message selector. Start with the code for
PriorityBlockingQueue. Add custom code to create a Map<JMS
QueueReceiver with a MessageSelector,Condition>, that holds waiting
receivers. When a message enters the queue, check the waiting
receivers to see if any message selectors match the message; if so,
signal that receiver's take() or poll() call. When a receiver first
take()s or poll()s or is signaled by its Condition, iterate through
the queue for a matching message. If there's a message, return it and
(if needed) remove the entry from the Map. If no message matches, add
the receiver to the Map.

Multiple BlockingQueues: Use a Map<MessageSelector,BlockingQueue>,
with one entry for each MessageSelector plus one for all messages:
When a new QueueReceiver with a new MessageSelector is created, add a
new entry to the Map. When a message is sent, check all the
MessageSelectors, and place the message in all the corresponding
BlockingQueues. When a QueueReceiver takes() a message successfully,
remove() it from all the BlockingQueues. Fold all this into a class
that implements BlockingQueue.

Neither approach is without problems. The first requires creating
Conditions dynamically, which the example code doesn't do, plus
iterating through the queue (could be mitigated by holding onto the
matching message). The second has this traffic jam of remove()ing
from multiple Queues. I'll take any advice on where to start.

Thanks,

Dave

David Walend
[hidden email]


_______________________________________________
Concurrency-interest mailing list
[hidden email]
<a href="http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)"> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

ACM OOPSLA Conference - Java Concurrency Tutorials

David Holmes-3
In reply to this post by David Walend
The annual ACM OOPSLA conference is being held in Portland, Oregon, from
October 22 - 26.

http://www.oopsla.org/2006/

As usual some familiar names will be presenting tutorials on concurrent
programming in Java:

http://www.oopsla.org/2006/submission/tutorials/intro_to_concurrent_programm
ing_in_java_5.0.html

http://www.oopsla.org/2006/submission/tutorials/effective_concurrent_program
ming_in_java.html

So tell your colleagues, tell your friends, ...

Cheers,
David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ACM OOPSLA Conference - Java Concurrency Tutorials

Vijay Saraswat
And on X10 :-)!

http://www.oopsla.org/2006/submission/tutorials/concurrent_object-oriented_programming_for_modern_architectures.html

David Holmes wrote:

>The annual ACM OOPSLA conference is being held in Portland, Oregon, from
>October 22 - 26.
>
>http://www.oopsla.org/2006/
>
>As usual some familiar names will be presenting tutorials on concurrent
>programming in Java:
>
>http://www.oopsla.org/2006/submission/tutorials/intro_to_concurrent_programm
>ing_in_java_5.0.html
>
>http://www.oopsla.org/2006/submission/tutorials/effective_concurrent_program
>ming_in_java.html
>
>So tell your colleagues, tell your friends, ...
>
>Cheers,
>David Holmes
>
>_______________________________________________
>Concurrency-interest mailing list
>[hidden email]
>http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
>  
>


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Special Conditions and PriorityBlockingQueue

David Walend
In reply to this post by David Walend
On Sep 23, 2006, at 12:00 PM, concurrency-interest-
[hidden email] wrote:

> From: David Walend <[hidden email]>
> Subject: [concurrency-interest] Special Conditions and
> PriorityBlockingQueue
>
/snip/

> Multiple Conditions: Write a custom BlockingQueue with a Condition
> for each message selector. Start with the code for
> PriorityBlockingQueue. Add custom code to create a Map<JMS
> QueueReceiver with a MessageSelector,Condition>, that holds waiting
> receivers. When a message enters the queue, check the waiting
> receivers to see if any message selectors match the message; if so,
> signal that receiver's take() or poll() call. When a receiver first
> take()s or poll()s or is signaled by its Condition, iterate through
> the queue for a matching message. If there's a message, return it and
> (if needed) remove the entry from the Map. If no message matches, add
> the receiver to the Map.

Is there a way to remove a Condition once Lock.newCondition() has  
been called? If not, how much overhead does the Condition take if  
it's never .signal()ed?

Thanks,

Dave

David Walend
[hidden email]


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Special Conditions and PriorityBlockingQueue

Doug Lea
David Walend wrote:
>
> Is there a way to remove a Condition once Lock.newCondition() has  
> been called?

No.

> If not, how much overhead does the Condition take if  
> it's never .signal()ed?

Not much -- when there are no waiters, Conditions just
maintain a few bookkeeping fields.
And they are GCable once unreferenced.
And they are also pretty cheap to construct.

I don't recall anyone ever exploiting all this to build
something with lots of dynamically created Conditions, but
I can't think of any reason not to try.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest