17

I want to use java.util.ConcurrentLinkedQueue as a non-durable queue for a Servlet. Here's the blurb from the javadoc for the class.

An unbounded thread-safe queue based on linked nodes. A ConcurrentLinkedQueue is an appropriate choice when many threads will share access to a common collection. This queue does not permit null elements.

Now imagine I have 1000 concurrent requests on the servlet, and each thread will need to enque an object into the ConcurrentLinkedQueue. From the description, should I conclude that it will have no problems handling the load ? The guarantee that I will need is that:

  1. I automatically receive the thread-safe guarantee without needing to do my own synchronization.
  2. I will not lose any requests if the traffic load goes beyond 1000 concurrent request.

Thanks

ashitaka
  • 3,928
  • 7
  • 38
  • 43

4 Answers4

62

You're essentially asking three different questions (two of them explicitly and one implicitly.) Here they are, with my answers:

1. Do I need to do my own synchronization if I use java.util.ConcurrentLinkedQueue?

Atomic operations on the concurrent collections are synchronized for you. In other words, each individual call to the queue is guaranteed thread-safe without any action on your part. What is not guaranteed thread-safe are any operations you perform on the collection that are non-atomic.

For example, this is threadsafe without any action on your part:

queue.add(obj);

or

queue.poll(obj);

However; non-atomic calls to the queue are not automatically thread-safe. For example, the following operations are not automatically threadsafe:

if(!queue.isEmpty()) {
   queue.poll(obj);
}

That last one is not threadsafe, as it is very possible that between the time isEmpty is called and the time poll is called, other threads will have added or removed items from the queue. The threadsafe way to perform this is like this:

synchronized(queue) {
    if(!queue.isEmpty()) {
       queue.poll(obj);
    }
}

Again...atomic calls to the queue are automatically thread-safe. Non-atomic calls are not.

2. Am I guaranteed not to lose calls to java.util.ConcurrentLinkedQueue if there are 1000 simultaneous requests?

Because this is an unbounded implementation you are guaranteed that no matter how many simultaneous requests to make, the queue will not lose those requests (because of the queue's concurrency...you might run out of memory or some such...but the queue implementation itself will not be your limiting factor.) In a web application, there are other opportunities to "lose" requests, but the synchronization (or lack thereof) of the queue won't be your cause.

3. Will the java.util.ConcurrentLinkedQueue perform well enough?

Typically, we talk about "correctness" when we talk about concurrency. What I mean, is that Concurrent classes guarantee that they are thread-safe (or robust against dead-lock, starvation, etc.) When we talk about that, we aren't making any guarantees about performance (how fast calls to the collection are) - we are only guaranteeing that they are "correct."

However; the ConcurrentLinkedQueue is a "wait-free" implementation, so this is probably as performant as you can get. The only way to guarantee load performance of your servlet (including the use of the concurrent classes) is to test it under load.

Jared
  • 25,520
  • 24
  • 79
  • 114
  • 1
    Jared, I really liked your explanation. Thanks. – ashitaka Jan 13 '09 at 01:39
  • 1
    No problem - if this sufficiently answered your question, you might think about "Accepting" it (by clicking the checkmark to the left of the answer.) – Jared Jan 13 '09 at 15:56
  • 1
    If the consumer needs to block on poll, use a BlockingQueue, which has an atomic take() method that will block until the queue is not empty. – Adam Jaskiewicz Mar 05 '09 at 21:33
  • 7
    Synchronizing on the queue in this way won't do what you are trying to do. Other threads will still be able to poll/offer on the queue, even while you are in that block, unless you synchronize ALL access to the queue. Doing so would make using a ConcurrentLinkedQueue pretty pointless. – Adam Jaskiewicz Mar 05 '09 at 22:02
  • Good point, Adam. This answer will get re-written as soon as I squeeze in the time. – Jared Mar 05 '09 at 22:20
  • 1
    Since he didn't rewrite the answer due to lack of time (timestamps noted and his own statement), here is how to properly block: (1) Create placeholder Object foo; (2) wrap with synchronized (foo) // not the Queue itself. This is also basically how it's done in Collections.synchronizedList (). Be careful, though, that you don't overdo it or you will defeat speed benefits of this very concurrency construct. – ingyhere Oct 03 '13 at 12:35
  • came to this too late, but why not `obj = queue.poll(); if (obj != null) { process(obj); }`? this way we're not doing **check then get** – ryenus Jan 15 '15 at 11:53
3

Remember that the queue is only threadsafe for calls to a single member. Don't write code like this and expect it to work:

if (queue.Count!=0)
    queue.Dequeue().DoSomething();

In between these two operations, another thread may have dequeued the last element. I'm not intimate with Java collections, but I guess Dequeue in such a case would return null, giving you an exception.

Drew Noakes
  • 300,895
  • 165
  • 679
  • 742
  • ConcurrentLinkedQueue has an atomic dequeue operation called "poll()". – Thilo Jan 12 '09 at 11:07
  • What I plan to do is to do a ConcurrentLinkedQueue#peek() first, then call poll only if peek() does not return null. – ashitaka Jan 13 '09 at 01:40
  • Make sure you synchronize the call to peek and poll - remember, the two called together is a non-atomic call. – Jared Jan 13 '09 at 15:56
  • If I put poll() and peek() in a sync block, e.g. synchronized(lock) { q.peek(); q.poll(); } would that mean that I would need to do this when adding things to the queue e.g. synchronized(lock) { q.offer(obj); } ? – ashitaka Jan 14 '09 at 02:17
  • @ashitaka : Yes, but doing so would defeat the point of using a ConcurrentLinkedQueue. – Adam Jaskiewicz Mar 05 '09 at 22:35
  • @Adam: Could you please expand on the last point, does this mean that if you perform some operation on a shared resource non atomically, and lock it like ashitaka shows in his peek-poll example, then all other operations on the queue will have to be locked on the same object that was used earlier, even though the other calls are atomic? – Abhijeet Kashnia Jul 01 '11 at 07:25
1

  1. Since the queue is thread-safe, you do not need to perform any synchronizations to ensure thread-safety. However, you should ensure all threads have equal access to the queue to avoid starvation, busy-waiting, etc...

  2. Since the queue is unbounded, the size of the queue is limited only by the amount of memory you have available.

Yuval Adam
  • 161,610
  • 92
  • 305
  • 395
0

Yes, for your two questions.

The concurrent queue is thread-safe (and is efficient due to the block-free algorithm used underneath). Thread-safe implies that the number of concurrent accesses must not make any difference (I've not yet heard of a race-condition which is guaranteed not to happen below xyz concurrent accesses).

Other than that -- optimal performance in multi-threaded applications is more complex than that. But using a real concurrent collection is not a too bad start.

gimpf
  • 4,503
  • 1
  • 27
  • 40