Solutions for handling millions of timed (scheduled) messages?

Question

I'm evaluating possible solutions for handling a large quantity of queued messages, which must be delivered to workers at a certain date and time. The result of executing them is mostly updates to stored data, and they may or may not be originally triggered by user action.

For example, think of what you'd implement in a hypothetical large-scale StarCraft game server for storing and executing users' actions, like upgrading a building, hatching a soldier, all of which requires to be applied to the game state after several seconds or minutes after the player initiates them.

The problem is I can't seem to find the right term to name this problem area. There are several that looks similar, but different:

cron/task/job scheduler

• The content of the queue is not dynamic, it's predefined.
• Each task is scheduled.

message queue

• The content of the queue is dynamic.
• Each task is intended to be delivered immediately.

???

• The content of the queue is dynamic.
• Each task is scheduled.

If there are message queues that allow conditional delivery of messages, that might be it.

Summary:

1. What are these kind of technology called?
2. What are some of the solutions out there?

Answer 1

It seems to me that a queue-based solution would be best in this case for a number of reasons:

• Management. Most queuing solutions provide support for inspecting the content of queues which makes it easier to debug, easier to take action when certain threshold are exceeded, ...
• Performance. You can divide workload by having multiple enqueue/dequeue processes (gives you the ability to scale out).
• Prioritizing. Most queues support prioritizing of messages (probably not all messages are equally important).
• ...

Remaining problem is the immediate delivery of messages in the queue. You have two ways to solve this: either delay enqueuing of messages or delay execution of dequeued messages. I would go with the first approach, delayed enqueuing.

A message then has two properties: (content, delay). You provide the message to a component in your system that queues the message at the appropriate time.

I'm not sure what programming language you're using, but the MS .NET 4 framework has support for such a scenario (delayed execution of tasks).

Answer 2

This just sounds like a trivial priority queue on the surface. The priority in this case is the time of completion, and you check the front of the queue to see when the next event is due. Pretty much every language comes with a priority queue or something that can easily be used as one, so I'm not sure what the actual problem is here.

Is it that you're worried about scalability, when it comes to millions of messages? Obviously 'millions' is a meaningless term - if that's millions per day, it's a trivial problem. If it's millions per second, then you can just scale horizontally, splitting the queue across multiple processes. (And the benefit of such a queue system is that this parallelization is really simple.)

I would bet that when implementing a large scale real-time strategy game server you would hit networking problems long before you start hitting problems with the message queue.

Answer 3

For StarCraft, I would use the Red Dwarf server.

For a JEE app, I would use Quartz Scheduler.