Java bounded non-blocking buffer for high concurrent situation

Question

Basically I need a data structure to store the temporary chatting messages on the server side. It should be:

• bounded: because I don't need store too many messages, the client will send request to get the new messages every second. I think the bound size should be the max. mount of concurrent requests in one second. When the buffer is full, the old messages will be removed.

• suitable for high concurrent access: I don't want to use the data structure like Collections.synchronizedXXXX, because during the iteration, if other thread changes the data structure, e.g. adds a message, it will throw an Exception, so I have to lock the whole data structure, actually I don't really care if the client request can get the most last inserted message, because they will send a new request after one second, on the other side the write operation should be never delayed. The classes under the package java.util.concurrency seems the solution, but...

• non-blocking: LinkedBlockingQueue, ArrayBlockingQueue they could be bounded and won't throw exception during iteration, but they are all blocking queue. When the queue is full, I want to add the new element to the tails and remove the old element from head instead of blocking there and wait for someone to remove the header.

So my question is there any good implementation from 3rd library? For example Google Guava? Or maybe you have better idea about storing the temporary chatting messages on server?

thank you very much!

Answer 1

You can use LinkedBlockingQueue with the non-blocking methods offer (or add) and poll to access it. You can create it with a fixed capacity to make it bounded.

LinkedBlockingQueue<String> myStrings = new LinkedBlockingQueue<String>(100);
myStrings.offer("Hi!"); // returns false if limit is reached
myStrings.add("Hi, again!"); // throws exception if limit is reached
String s = myStrings.poll(); // returns null if queue is empty

Answer 2

You could utilize the Apache Commons CircularFifoBuffer. It meets your first and last criteria. To support concurrency, you can wrap the base buffer in it's synchronized version like so:

Buffer fifo = BufferUtils.synchronizedBuffer(new CircularFifoBuffer());

Good luck on the project.

Answer 3

Did you take a look at ConcurrentLinkedQueue? The page says

This implementation employs an efficient "wait-free" algorithm...

Wait-freedom is one of the strongest guarantee you can obtain....

Answer 4

You can add non-blocking behaviour to an ArrayBlockingQueue by surrounding it with a conditional offer() statement, where failure of the queue to accept the offer results in the head being dropped and the offer being re-made:

    public class LearnToQueue {


    public static void main(String[] args){
        Queue<Integer> FIFO = new ArrayBlockingQueue<Integer>(4);

        int i = 0;

        while ( i < 10 ){

            if (!FIFO.offer(i)){
            // You can pipe the head of the queue anywhere you want to
                FIFO.remove();
                FIFO.offer(i);
            }
            System.out.println(FIFO.toString());
            i++;

        }
    }

    }

Answer 5

LinkedTransferQueue is a blocking, unbounded queue that doesn't enforce strict FIFO ordering. It will only block when taking from an empty queue, but never on adding to one. You could add a soft cap to evict elements by adding either a size or read & write counters.

Depending on your requirements, you may be able to write a custom lock-free ring buffer.