• Post Reply Bookmark Topic Watch Topic
  • New Topic

Developing a queuing mechanism  RSS feed

 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I am working on a POC. I have to develop a queue implementation which can be used for bulk message transfer(high throughput). What all parameters should I consider to design it?

Thanks
Ravi
 
Tim Cooke
Marshal
Posts: 4037
239
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Have you tried using the Queue implementations that come with the Java language? I'd recommend testing the throughput performance of those before you embark on writing your own implementation. Once you've profiled each of the existing implementations, and have concluded that none of them are suitable, you then have a baseline for comparison when writing your own.

Do you have some performance requirements that you need to achieve? I'm talking about hard numbers here, not whimsical stuff like 'high throughput' or 'very fast'.
 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Our approach right now is the opposite one. We are trying to build a queue specific for our project. If it is unable to reach the performance level of existing queue frameworks, we will use the existing queues.

I have tried out chronicle queue so far and I was able to achieve 17000 messages/second with it.

The scope defined by our leads is to reach 100000 messages/second.
 
Tim Cooke
Marshal
Posts: 4037
239
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm going to be quite blunt here. Your approach is stupid. Evaluate the suitability of the tools you have first, then build your own if necessary using the knowledge you've gained and a good understanding of how the existing tools are deficient.

I'm also hoping that you've identified that the queue is the bottleneck in the system? It's no good having a 100k message/second queue if your producer(s) or consumer(s) can only process 100 messages/second.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Yeah, queuing messaging frameworks have to deal with... well... queuing ...   .... ie. load balancing, delivery confirmation, redelivery, etc. In my opinion, if you don't need any of that, or if you only have one queue producer and one consumer, then perhaps a topic based messaging is better.

Henry

 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I too prefer looking for existing solutions, but am told to create custom implementation for two reasons: 1) learning intricate details of a queuing mechanism 2) having a customized solution specific to our requirement.

Because I get to learn something new, this sounds good to me. There is not specific timeline for this task.

Producer or consumer components are out of scope for my task. So, I cannot evaluate their maximum throughput.

Does it still sound like a waste of effort?
 
Junilu Lacar
Sheriff
Posts: 11476
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have to echo Tim's sentiments here about your approach. It has elements that indicate NIH (not invented here) syndrome and PHB (pointy-haired boss) syndrome. Both of these are anchored in naïveté at best. We're not saying you're stupid but there's also an inherent guilt by association bias that's involved.
 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
These are the requirements I can think of for the queue implementation:

1. All the messages need to be delivered.
2. Maximum throughput for read and write
3. Communication will always happens within same jvm.

On an entirely different note; how about using a simple blocking queue for this task? I can add and remove element and it will block if there are not elements to process.
 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:I have to echo Tim's sentiments here about your approach. It has elements that indicate NIH (not invented here) syndrome and PHB (pointy-haired boss) syndrome. Both of these are anchored in naïveté at best. We're not saying you're stupid but there's also an inherent guilt by association bias that's involved.


I agree with your point. But what I am saying is that this is not my decision.

I already put my perspective to my leads. Now if they intend to go for our own implementation, not much I can argue with.

Also, its the learning opportunity also that looks good to me. This is just a POC.

Not that we have to integrate this into our project right away. That call will be taken later.
 
Junilu Lacar
Sheriff
Posts: 11476
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
s ravi chandran wrote:On an entirely different note; how about using a simple blocking queue for this task? I can add and remove element and it will block if there are not elements to process.

Now you've really shown that you're venturing to climb Mt. Everest with a fork and dressed only in a T-shirt and shorts. That idea is as compatible with "high volume throughput" as a lawn mower is to F1 racing. Or maybe I missed something. Care to elaborate more? How is that going to help you achieve a 100k messages per sec throughput?
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16057
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you really want to re-invent / re-implement this yourself for whatever reason, then you will need to do research on queueing mechanisms and protocols.

You'll need to think about your requirements:
s ravi chandran wrote:
1. All the messages need to be delivered.
2. Maximum throughput for read and write
3. Communication will always happens within same jvm.

And think about how you are going to make sure that these requirements are met.

Especially the first one: How are you going to guarantee that all messages are delivered? What kind of message delivery guarantee needs the system to have: at least once, at most once, exactly once? Does a client that receives a message has to send an acknowledgement signal to the queue so that the queue knows that the message is delivered?

There are existing queue protocols such as AMQP that are most likely worth investigating.

Java has a standard API for message queueing: JMS.

I agree with Tim and Junilu that inventing and implementing something like this yourself is only worth it if you are doing this because you want to learn exactly how this works for yourself. If you just need a queue for some system that is being built for the company, it will be much cheaper and cost a lot less time to use an existing, proven queue implementation. It will not only be much cheaper now, but also later, when the software has to be maintained. Especially if you are not an expert in how to do this, the chance that your own home-invented queue system will have a lot more bugs and much worse performance than existing products is very high.

Saying that you want to invent and build your own because you think that existing queueing products might not perform as you like, is like saying that you want to build your own racing car because you think that those Ferraris might not be fast enough, while you have no idea what goes into building a racing car.
 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay. This sounds reasonable.

I will stop doing random experiments and check out the AMQP.

About the requirement:


This needs to be reliable, but I was not given any specific instruction like persisting the data which can be recovered later. So, I am considering that the reliability of message delivery stops at the point where the system crashes.

I know that existing queuing products have a reasonable performance else they would not sell.

For now I am just focusing on the learning part. Whatever reason my leads have, I have my own. :-)

I will check out the link you mentioned and come up with more doubts I have from them.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
s ravi chandran wrote:
I will stop doing random experiments and check out the AMQP.

About the requirement:


This needs to be reliable, but I was not given any specific instruction like persisting the data which can be recovered later. So, I am considering that the reliability of message delivery stops at the point where the system crashes.


All current AMQP implementations are done via to brokers, so, they all support persistence, high availability, disaster recovery, etc.

And BTW, the AMQP link provided above doesn't seem to mention the commercial products. Ultra Messaging (Informatica) and WebSphere MQ (IBM) also support the AMQP protocol.

Henry
 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Broker service will be like a client server model, right?

I like the way JMS works, just have producer consumer implementations and you are done. But it does involve serialization- deserialization each time.

The fastest way to communicate would to through bytes. So, I would have to define a format of data that will be produced and consumed.

This format has to have a header with relevant identifiers like destination, payload size, message sequence count etc. Then a certain bytes of actual payload bytes.

Then I have to provide some read and write implementations which can be used in any class directly.

Recovery is not relevant for me. I will just be supporting message delivery with proper sequencing.

Do all queuing frameworks support buffering of message before dispatching? They have to support unknown rate of message writes, is this assumption valid?
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
s ravi chandran wrote:
I like the way JMS works, just have producer consumer implementations and you are done. But it does involve serialization- deserialization each time.


JMS only specifies the API. It doesn't specify the protocol -- so, the answer would be dependent on your setup, and configuration of that setup.

And I guess, this also affects your follow up questions too.

Henry
 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, I was considering that we would use ByteMessage in JMS, whichever implementation we use.

Coming back to the original topic. If I have to build my own queuing mechanism, what all do I need?

I am thinking of these things:


Any relevant aspect that I am missing here? Persistence, recovery or load balancing is not my requirement.
 
Tim Cooke
Marshal
Posts: 4037
239
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This latest set of requirements is sounding more like a communication protocol for use over an unreliable transport, whereas earlier you stated a requirement as "Communication will always happens within same jvm" which suggests you're just passing messages in memory between Objects.

Which is it?

If you're simply looking for a very fast Queue implementation, then I'd recommend reading up on the LMAX Disruptor. I'd very much doubt you'd write one faster than that yourself, I know I certainly couldn't.
 
s ravi chandran
Ranch Hand
Posts: 579
6
Java jQuery
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, I might have deviated from my objective.

These would be the requirements then:


Does this look reasonable ?

I am not trying to improve existing Queue products, I am learning the mechanism by making one.
 
Stephan van Hulst
Saloon Keeper
Posts: 7962
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
1. Since the message is passed within the same JVM instance, its form is unimportant. You can just create a generic queue that passes any type of object.
2. Looks good. You can add listeners to your queue.
3. Not interesting. This is an implementation detail. If we could write a queue without having to store the messages in memory, we would.
4. Not sure what you mean by this.

Here are some other considerations:
  • Does the queue have a fixed capacity to hold messages?
  • Does the queue need to block when it's full/empty?
  • Is the queue thread-safe?
  • Does the queue pull or push?
  • If the queue is push-based, does it have a fixed capacity to hold consumers?
  • If the queue supports multiple consumers, when is a message removed from the queue?
  •  
    Tim Cooke
    Marshal
    Posts: 4037
    239
    Clojure IntelliJ IDE Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Stephan brings up an interesting point. Thread safety.

    It may sound counter intuitive, but if you're looking for raw throughput for your queue then a single producer and single consumer system is likely going to be best solution. The overhead required to deal with the concurrency problems present with multi-producer and multi-consumer systems will likely outweigh any perceived efficiency gains. If you design for single producer, single consumer, you can simplify your design and it's possible to implement a very fast queue solution. The LMAX Disruptor is excellent evidence of this.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks for the reply.

    This may not be relevant. read and write positions are already defined.

    Other considerations:

    Does the queue have a fixed capacity to hold messages?  I wish to keep it unbounded. Would it not be optimal that way?
    Does the queue need to block when it's full/empty?   Yes.
    Is the queue thread-safe?     Basic version wont be thread safe.
    Does the queue pull or push?  This queue will be push based model
    If the queue is push-based, does it have a fixed capacity to hold consumers?  Yes.
    If the queue supports multiple consumers, when is a message removed from the queue? Not applicable in current design


    This is what I have come up from our discussion so far.

          
  • I will have one producer and one consumer.


  •       
  • I would like to store object in memory and share it's location between producer and consumer.


  •       
  • When there is no element left to be processed by the consumer, the consumer will block. When producer adds more data, consumer will  start processing again.


  • Now I need a message/event handler which should be used by the consumer for processing. how do I link this handler with consumer? one way would be to have the handler implementation implicitly passed to the consumer.

    Does something like look better?
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 7962
    143
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    s ravi chandran wrote:I wish to keep it unbounded. Would it not be optimal that way?

    Not if your producer produces more than the consumer can consume. Your queue will grow until memory runs out.

    Basic version wont be thread safe.

    How are you going to guarantee reliable message passing if there is one thread for the producer, and one thread for the queue?

    When there is no element left to be processed by the consumer, the consumer will block. When producer adds more data, consumer will  start processing again.

    This means the thread that notifies consumers has to wait inside the queue, until it's notified of a new element by the producer thread.

    Now I need a message/event handler which should be used by the consumer for processing. how do I link this handler with consumer? one way would be to have the handler implementation implicitly passed to the consumer.

    Does something like [...] look better?

    Why have a custom class for consumers anyway? Java already provides a Consumer interface. In the simplest form, you can just pass a lambda expression or a method handle to an addConsumer() method on the queue.
     
    Junilu Lacar
    Sheriff
    Posts: 11476
    180
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Stephan van Hulst wrote:
    Why have a custom class for consumers anyway? Java already provides a Consumer interface. In the simplest form, you can just pass a lambda expression or a method handle to an addConsumer() method on the queue.

    Be careful about confusing the java.util.function.Consumer functional interface with the javax.jms.MessageConsumer messaging API interface. The two have vastly different semantics. The former can be implemented as a lambda expression, the latter cannot.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Okay. For bounded queue size I can take a number like 100. For learning purpose this should suffice.

    How are you going to guarantee reliable message passing if there is one thread for the producer, and one thread for the queue?

    If I have a basic queue where I add to the end and remove from the start, will it have conflict?

    This means the thread that notifies consumers has to wait inside the queue, until it's notified of a new element by the producer thread.

    Yes.  Blocking will save some cpu cycles.

    Why have a custom class for consumers anyway? Java already provides a Consumer interface. In the simplest form, you can just pass a lambda expression or a method handle to an addConsumer() method on the queue.

    So, I implement this consumer interface. How will producer and consumer know about each other? as they both share common queue, will using a lock condition be the right way to communicate between them?
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 7962
    143
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    s ravi chandran wrote:If I have a basic queue where I add to the end and remove from the start, will it have conflict?

    Yes it will, if you're using separate threads for the producer and the pushing mechanism. You can implement a concurrent, bounded, blocking queue by writing a circular buffer with locks.

    So, I implement this consumer interface. How will producer and consumer know about each other? as they both share common queue, will using a lock condition be the right way to communicate between them?

    The producer and consumer shouldn't know about each other. The producer just adds messages to the queue, and the queue's pushing mechanism notifies the registered consumer when a message is available.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Stephan van Hulst wrote:
    s ravi chandran wrote:If I have a basic queue where I add to the end and remove from the start, will it have conflict?

    Yes it will, if you're using separate threads for the producer and the pushing mechanism. You can implement a concurrent, bounded, blocking queue by writing a circular buffer with locks.

    So, I implement this consumer interface. How will producer and consumer know about each other? as they both share common queue, will using a lock condition be the right way to communicate between them?

    The producer and consumer shouldn't know about each other. The producer just adds messages to the queue, and the queue's pushing mechanism notifies the registered consumer when a message is available.

    When I say from producer, shouldn't it add directly to the queue?
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    If I am understanding it correctly, the working has to be like this:

     
    Stephan van Hulst
    Saloon Keeper
    Posts: 7962
    143
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    That's a bit of a roundabout way of doing things. It should actually be like this:
     
    Junilu Lacar
    Sheriff
    Posts: 11476
    180
    Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Stephan van Hulst wrote:That's a bit of a roundabout way of doing things. It should actually be like this:

    I'm confused. A Queue exists so that a Producer can produce messages at whatever rate it can and not have to wait on Consumers to pick up previous messages first. The Producer drops messages into the Queue so that Consumers can pick them up at the time and rate at which they are able to. So, essentially, the Queue IS the buffer. What is this intermediate buffer for? Are you guys mixing levels of abstraction here, with the intermediate buffer being something of an implementation detail?
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 7962
    143
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Yes, I was using buffer and queue interchangeably.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    okay, I was initially thinking of using the queue as the only datastructure in this mechanism. Got confused with what Stephan told.

    So, does this look appropriate:



    Do I need an observer pattern here to notify all consumers registered to this queue?
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Created the queue class over which all the operation will happen.




    The overflow and underflow conditions are not proper. I get exception in both the cases. Not sure which part is wrong here.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    one more question that needs to be resolved is when an element is consumed. how to reclaim it for new elements.
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    These are the final classes I have created. The queue still goes out of sync and consumer gets null after few iterations.

    Queue.java


    EventProducer.java
    EventConsumer.java


    EventHandler.java


    Main.java


    Logical flow looks right. There are technical flaws in the code.  I have tried making Queue front and rear pointers volatile, but still the queue goes out of sequence.

    How should I enhance it to make it work properly?

    Am I missing some component that is required here?
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Fixed the underflow and overflow of queue.

    Queue.java



    These cases are still to be handled:

     
    Tobias Bachert
    Ranch Hand
    Posts: 86
    18
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Regarding your queue implementation (ignoring everything regarding concurrency):

    You are currently missing the main intent of a queue, the circular array usage (you are currently filling the array with elements and iterating over it once).
    The update of front (identical for rear) should be something like

    and for the sake of performance, capacity should be a power of 2 to allow using the following code instead:

    If you permit null values, then you need an additional flag to handle the full/empty state, otherwise you can use (whereas front and rear have to start at any index [0, capacity)):

    Additionally you are currently not nulling values out, your dequeue method should end with
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks for the response.

    I had enhanced the queue to make circular, but it was somehow missing elements in dequeue, so did not add the code here.

    Here is the same objective in my requirement:


    I am using rear pointer to add elements and front pointer to remove elements. Will it change the sequence of conditions you mentioned?

    I have added the conditions you suggested. I am taking double of whatever capacity is given to make sure the capacity is some power of 2.

    So, in current code, capacity will be 20. Somehow the index condition becomes 0 after rear =4. Did I miss something here?

     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    This is my original methods of the Queue that are not working in Dequeue after certain index:

     
    Tobias Bachert
    Ranch Hand
    Posts: 86
    18
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Multiplying by two doesnt give you a power of two, you need exactly one bit set in the capacity. I use most of the time the following code to get the next larger power of two:

    Additionally your starting index of rear is still invalid, would throw an ArrayIndexOutOfBoundsException if you would call dequeue prior calling enqueue, below a few changes:
     
    s ravi chandran
    Ranch Hand
    Posts: 579
    6
    Java jQuery
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thanks for fixing the code.

    If I have to give support for multiple consumers, how should I enhance it?

     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!