Timed based events in milliseconds

Question

I have a Webapp that schedules events to happen in the future with, hopefully, milliseconds accuracy. I'm currently using a backend process that checks the database (kind of an anti pattern) and triggers the event when the time has just passed .

This system has its faults:

• database polling
• poor performance on multiple events happening close to each other

I have considered using something like beanstalkd, which can be used to schedule tasks to be triggered in the future, but only with seconds accuracy.

I wonder if there's any other alternative to my current setup

Answer 1

As @Ewan has said, millisecond accuracy is really hard. There are multiple things to consider and the rabbit hole is deep.

Disclaimer: I have not yet implemented such a system. I see a few clear ways of achieving it but I have no practical experience with any more caveats involved than I can think of right now.

Millisecond accuracy

We first have to talk about what that event is. If milliseconds matter then the device that triggers the event is also the device that takes the action. Otherwise, networking will be involved. And with networking, second accuracy is the best you can possibly hope for.

Also, the system time of all computers involved in this process must be synchronized with the same accuracy. If your end-users can schedule such events that also involves their computers: there is no point in millisecond accuracy when you're still uncertain for ±1 minute which millisecond it will actually be.

Programming Language

In my experience, millisecond accuracy is far out of reach of interpreted languages/scripting languages. The interpreter will slow you down and you don't have that fine-grained control over CPU cures.

You'll have to at least go as low as Java / .Net. You might get better results with more access to system-level APIs, so D or Go would be options. But all of those have a garbage collector that you'll have to think about. If you use a GCed language you'll have to clean up as much of the memory that you use yourself to avoid stop-the-world GC events. Doing it yourself is deterministic; you have control about when it happens.

If GCed languages don't yield the accuracy that you need, you'll have to go even lower to C / C++ / Rust and similar languages. You cannot just go ahead and write code in these languages. You'll have to spend time learning to use them properly (shooting yourself in the foot with those languages is far easier than the typical web-programmer thinks - looking at you, Ruby, PHP and NodeJS).

Triggering the event

You are only going to get millisecond accuracy when you have exclusive access to a processing core. And that means one core per timer:

Any type of threading that involves more threads then there are CPU cores will introduce an inaccuracy in the range of 10s to 100s of milliseconds. Many programming languages support things like Javas Thread.sleep(milliseconds). With such API you can put a thread to sleep for at least a certain amount of time. But that does not guarantee that it will wake up instantly after that time has elapsed. Maybe it will, but more likely it wont. Another thread will be running and the thread that has just been sleeping will have to wait, possibly a couple of milliseconds.

This is not only true for the thread scheduler of higher level programming languages but also for the process scheduler in most OSes. So you need to get around that process scheduler. I see two ways this is possible:

1. Use a large cluster of microcontrollers on which no other software than yours is running. This will work 100% of the time and you could possibly reach greater precision (maybe .1ms, or even .01ms). But then again, those will have to be able to execute whatever action is associated with the event.

2. Use machines with multiple cores (e.g. 8 or 16 cores), hope that the OS does not use more than 2 cores and leaves the rest of the cores to you. In my experience, thread schedulers can do a good job at picking unused cores. This means that if you start a new thread on such a machine and do a Thread.sleep(500) it is very likely that no other process or thread is using the same core as your thread and thus your thread will wake up after that 500ms; most of the time.
   To get this to work in even 50% of the cases, the OS must be minimal; any sort of deamon that is running in the background can totally ruin your precision. This means that the services running on that machine to help you fulfill the event action is also extremely limited. Also, you can only have as many events waiting to trigger at the same time as there are CPU cores in the machine that are guaranteed not to be used.

This leads us to another aspect:

Scheduling the event triggers

However you decide to trigger the events, the amount hardware resources is proportional to the the number of events that you can have sitting and waiting to trigger at the same time.

So you'll need to schedule your event triggers carefully in order not to waste expensive resources. Here, the delay of determining the events to trigger comes into play. Lets assume you know about an event that is to be triggered at least 5 seconds beforehand. Within that time, you'll need to get the exact timestamp of the event across to the machine that will trigger + execute. Again, I see two solutions here:

1. You can either use one core in every trigger machine for network communication and storage of the events that are to be triggered. Those are stored into memory and the threads that trigger the events pick them. You'll then also have to deal with thread safety in order to prevent the same event from being triggered multiple times.

2. Every core triggers an event and then polls a network resource for the next event to trigger. Once it has one, it stops doing networking, goes to sleep for the remaining time until the event is to be triggered, executes the action necessary and then starts polling for the next event, again.

Managing the events to be triggered

Database polling might work out but I'd rather use a message queue. I'll not explain why database polling is a bad idea here. A message queue will serve you just as well. Again, you can set up a dedicated service for those events. It knows all events and sends them out to the triggering machines with an accuracy of maybe 3-5 seconds; the triggering machines then handle the millisecond accuracy.

---

The bottom line is: there might be a couple of more gotchas that I didn't mention (because I don't know them, either). In your place, I'd talk to whoever is the "product owner" of the software and see whether 10ms or 100ms accuracy will also do:

• If 10ms accuracy is acceptable, you could get away with many threads on a few processing cores and a compiled programming language with GC. Of course, sleep calls are not guaranteed to be that accurate but its not that hard to achieve if you offload work to other servers/machines as much as possible.

• If 100ms accuracy is acceptable you'll probably get there using an interpreted language with GC. After all, 100ms is a lot of time from the perspective of a CPU core running at 3Ghz.

Answer 2

To achieve millisecond accuracy then you will need to use a modified polling approach. Persisting your scheduled events in a database is fine, and polling is required, however your polling process will want to wake up every minute or two and build an in memory queue of scheduled items to be processed within some arbitrary time period. Let's say 3 minutes.

Another process will fetch the next item off the queue and can spin CPU cycles until the exact millisecond is reached that the task should be run.

A separate thread should be created to run the scheduled task itself, so the scheduled task process can continue onto the next item in the queue immediately.

This could be load balanced to multiple machines, but would probably run most efficiently on a machine with at least 3 CPU cores, one for each thread (Polling, Waiting, Executing) to run simultaneously.