A friend of mine was recently asked this question in an interview.

Lets say there is a continuous stream of incoming events E1, E2 each with timestamp of entry associated with them. Write a java module to Make a call to raiseAlert() if at any point of time there are more than 1000 elements incoming at the same time. Remember its a continuous stream. Assume there is a getnextevent() to process incoming events

What ds would best suit (he said queue with a monitoring on timestamps on front and rear) and how would the module look in Java?


For the question as posed, a queue would work OK. Though the monitoring would need to include the total number of events in the queue, too. Monitoring the timestamps of the head and tail is optional, perhaps a nice-to-have. A Java BlockingQueue would offer most of the things we need. The network side can use the [offer](http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html#offer(E, long, java.util.concurrent.TimeUnit)) method to enqueue new items. The server code side would use poll if this is the only queue it serves.

However the implementation would need to independently keep track of the size since the existing size() method always returns zero. Hence you would also need to protect the size data member with a mutex.

We're not going to write the code for you, this isn't the point of this StackExchange forum.

But the premise of the question, is, very subtly, wrong. The context is that we're worried about overload (i.e. too many events are queued). Supposing the incoming requests have a deadline, if you use a queue, every event you serve from the queue is always the oldest event in the queue, by design. This maximises it chance of being past its deadline before you even look at it.

If your server is not overloaded (i.e. is processing events as fast as they arrive) there will be zero events in your data structure. Therefore the design and sizing of your data structure is really relevant only for handling overload conditions.

There are two simple fixes for our problem, one useful where events must be processed in-order, and the other where that restriction does not exist.

For guaranteed in-order processing, simply reduce the length of the queue by a lot. You can use Little's Law to figure out what size queue to use given the average time to serve a request, the requests' usual deadline and the target throughput. The only real purpose of the queue is to handle spikes in incoming requests (note: Little's Law doesn't really hold for transients). The advantage of the shorter queue is that when a request comes in after the queue is already full, the server doesn't give the misleading impression that it's going to deal with it. Depending on the transport layer, the client may even get a notification that their event could not be served right now. In any case, you would simply call raiseAlert when you fail to enqueue an event.

If in-order processing is not required there is a better, but less intuitive, technique: use a stack instead of a queue. What difference does this make? None at all when the server is processing events at least as fast as they come in. If there are zero events in it, it doesn't matter whether it is a queue or a stack, it behaves the same way (since it does nothing). As soon as we have an overload, with a stack we have an invariant that the server always processes the newest event, which is the event with the lowest chance of already having exceeded its deadline. This maximises the proportion of client requests that don't time out.

If it's cheap to destroy request objects (specifically: much cheaper than actually handling the request), you could implement the stack with a dequeue, and poll the bottom of the stack for expired events, in order to discard them. This allows you somewhat to control memory pressure under overload conditions.

  • As an API consumer, I would be very unhappy if I learned that an API was using a stack to service requests. – Brian May 9 '16 at 14:59
  • @Brian The whole point of this design is that it is equivalent under normal conditions and better under overload. So, leaving aside the emotional reaction you anticipate, do you have a technical criticism? – James Youngman May 9 '16 at 22:44
  • Firstly, a gut feeling criticism is highly relevant if API consumers are paying customers. As an API consumer, I don't consider it better under overload; it introduces several problems. 1) I can no longer ask a question like, "how many people are ahead of me; how long will it take to bring me to the front of the queue." 2) I will never receive an immediate answer to the question, "has this request been rejected due to overload?" 3) API consumers can send duplicate requests to receive a response faster, and those requests may be serviced. 4) Responses are not in order. – Brian May 10 '16 at 12:56
  • Taking the points as numbered, (1) I've never run an API where it was possible to ask such a question, it seems a strange query interface to offer. Have you done this? (2) You would not receive an immediate reply to that question in the queue implementation either (since requests' wait time is maximised by a queue). (3) True - but a public API without abuse protection is a terrible idea, and you also need this for a queue-based implementation. (4) True - which is why I proposed something else for that case; see "For guaranteed in-order processing..." in my answer. – James Youngman May 11 '16 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.