6

The title of my question is general because I feel like this problem is of a general nature, but to set the stage I'm going to provide a specific example.

We use a homegrown workflow engine that is driven by database tables. Within those tables lurks a directed graph that represents the workflow. The graph contains Stages and Activities; a line is drawn between two Stage nodes, and the resulting Activity node contains code to be executed. We use CSScript to compile and execute the code on the fly.

Within the workflow, Task records represent the work to be executed. Each Task contains some relevant metadata in XML form. The Task records traverse the directed graph, and the code is executed as the Task passes through the activity. So at any given moment, each stage might contain x number of tasks, waiting to be executed on an activity.

To execute a Task on an activity, it needs to be scheduled. A Schedule record containing a datetime, taskid, stageid and activityid determines when and where this Task gets executed next. Periodically, we execute a query that returns Schedule records that are due, and then for each record so returned we stand up an Activity instance and execute it, handing it the Task record as a parameter.

This query used to run 10 times per second. Recently, I added some code that counts how many times the query returns no records, and if this count gets to 60, I reduce the query interval to once per second, and start counting again. If the count reaches 60 again, I reduce the interval to once per minute. If a record appears in the query result, I set the interval back to 10 times per second, and begin the counting process again. The net effect is that the schedule table is rapidly polled during busy activity periods, and sparsely polled during quiet periods. We expect to save a few hundred dollars per Azure instance per month, just from this one simple change.

So here's my question.

This is obviously a polling pattern. Is there a way to make it "event-driven," so that the database is only hit when a schedule record is due, without having to constantly poll the database?

  • I see you say Azure... is this on prem or in the cloud? – Matthew Whited Oct 26 '16 at 15:40
  • I don't understand what you mean. It's full-scale Azure instances; we pay for the usage (CPU time?). – Robert Harvey Oct 26 '16 at 15:40
  • Have you considered using SqlDependency to get notification when your table changes? – Matthew Oct 26 '16 at 16:32
  • @Matthew: The table may not change. Once the schedule record is written, the system waits for GetDate() to catch up. – Robert Harvey Oct 26 '16 at 16:34
  • 2
    @ErikEidt: Potentially, I could find the place(s) where schedule records are being inserted, and add code in those places to maintain a NextScheduleDate property on the Server object. – Robert Harvey Oct 26 '16 at 17:34
4

The general solution is to use a database that supports asynchronous notifications. Several do:

  • Oracle - Allows registration for notification of changes on objects (object change notification or OCN) and changes in the results of specified queries (query result change notification or QRCN).
  • PostgreSQL - Simple notification containing a tag and an optional payload generated using the NOTIFY statement as a standalone command or as part of a function. (The latter could be part of a trigger.) Clients can subscribe to notifications by issuing a LISTEN statement and selecting on the connection handle (exactly how varies with language binding).
  • SQL Server - Built-in queuing system where clients can use a combination of the WAITFOR and RECEIVE statements to listen for events. May also have (or have had) Oracle-like OCN/QRCN.
  • Sybase - Has registered procedures that allow invocation of callbacks on the clients if they've asked for it. (Not positive about this one.)

If you're stuck with one of those that doesn't (MySQL, DB2), it will have to be done out-of-band using one of the methods described in the other answers.

Once you have a method for the database to notify you that something has changed, you can do a query that determines how long it is until the next event is supposed to happen and then wait that long for a notification. If you get a notification, repeat the query/wait cycle. If you don't get a notification, it means the time you calculated has arrived and it's time to do whatever the event dictates. This should get you down to the point where you're only querying the database when you know for sure something needs to happen.

1

Repeated queries to a database for a Schedule that is due, especially where you are polling multiple times per second tells me that you would greatly benefit from an in-memory cache of Schedule objects.

Assuming your application servers are horizontally scalable and load distributed, when a node in your cluster comes online it can perform an initialization to build its global thread safe queue. Maintaining each schedule task in an in-memory queue makes sense as it is sortable data. This would constitute a single database query for each node process in your cluster at first.

Poll the Queue

The cost of the poll operation is essentially a peek at the first element in the sorted queue. The queue being in memory this operation can be measured in nanoseconds. If the earliest item is due, now this process should start.

Event Driven Activity Generation

This is where something like MQ can be useful. When you pop the next Task off of the queue you can place a message in an MQ with the Task details. A set of Activity instance generation processes can listen on this queue, meaning the most available or quickest Node to fetch will obtain the message and own responsibility for executing the Activity.

What about new Scheduled Tasks?!

Use another MQ with a different listening process for adding new Scheduled Tasks into the system. It is these processes that will take responsibility for updating the database tables with the new Schedules and Tasks. You still need though to update all of the in memory process lists. There are various ways you might be able to achieve this but something like a Topic is a great solution for such a use case.

More information on Topics here: http://activemq.apache.org/how-does-a-queue-compare-to-a-topic.html

Each Node process can Subscribe to your Topic which it uses to apply new Scheduled Tasks to its in memory queue.

Why is this a great approach?

It has some complexity but the great part about it is that it is Scalable, Resilient, Efficient, and quickly Recoverable. Nodes can drop off or be added, and the database is merely used as a ledger that gets a new Node correctly initialized such that it can start contributing.

1

This isn't an event-driven solution but I think it may be a possible alternative solution to your particular problem.

It seems to me that the problem that you are running into is typical of the risk/reward trade off that you encounter anytime you are deciding whether to store some piece of information in volatile or non-volatile memory. Non-volatile memory may be cheaper and safer but data retrieval takes significantly longer and typically size is limited by system constratints.

This metadata you describe for each task certainly sounds like it is appropriately being saved in your database as does your long term scheduled items. But in your post you describe a process that is continually scanning your database in order to know what to run next. This immediate queue is certainly crucial to your application but it doesn't sound to me like it is something that necessarily needs to persist after the application is shut down for the night. Your app just needs to know what to execute now and then move forward.

I may be making light of what could be a significant refactor but I wonder if you can't move that part of your scheduler off of the database and up to the application layer in the form of a data structure. If rather than poll the database directly for all scheduled tasks, it only did this say once an hour (or any time segment you defined) to identify any long-scheduled tasks that need to be run during the next time segment and placed them in an application layer data structure, this would significantly reduce the amount of database calls your application would need to make. Your scheduler could then poll this locally stored data structure directly in order to execute immediate tasks. This would, of course, require that your scheduling class be aware of this processing time segment and slot any immediately scheduled tasks directly into the data structure (as opposed to the database).

But the end result would be essentially the same system you have currently except that you are limiting your database for truly long term storage by better leveraging your application layer for immediate processing.

0

The only thing I can think of is to use web service calls of some sort to proactively notify the Watcher process that a task needs to be executed.

Going one step further, you can utilize a notification system like RabbitMQ to send a message to a queue continuing the info required to execute that task. The Watcher can subscribe to this queue and only hit the database when there is something to process.

That being said, you would need a way to run a pending task in cases where the RabbitMQ server goes down - this increases the need for your system to be highly fault-tolerant.

0

As I understand it, a task needs to run because

  • It is now due to run
  • Or it has just been created by anther task
  • Or it has just transitioned to the next step and is ready to run

Do you care that a task that is due to run, runs a few seconds after when it should run? (I am assuming not)

Therefore run the query to find new tasks every 60 seconds and every time you add to the task table. This will result in newly created “run now” tasks being quick, but much less polling.

Or use SqlDependency to get notified when task are added to the table. Then have your query return low long it is until the next task is due, as well as all task that are due.

  • Do you care that a task that is due to run, runs a few seconds after when it should run? -- Yes. Tasks are scheduled on a staggered basis for load-balancing reasons, so it's very important that they run when they are supposed to. – Robert Harvey Nov 9 '16 at 17:49
  • Therefore run the query to find new tasks every 60 seconds... In the interim, I have added some new code that counts the number of times a poll resulted in no schedule records returned. If that count hits a certain threshold, I reduce the polling interval until a poll actually results in schedule records returned. – Robert Harvey Nov 9 '16 at 17:50
  • @RobertHarvey, therefore have your query return how long you should wait until the next pol, but with some logic to cope when new tasks are created. – Ian Nov 9 '16 at 17:55
  • @RobertHarvey, can you return task that are due to run in the next few seconds, then delay running them with logic on the C# side? – Ian Nov 9 '16 at 17:56
  • That won't pick up records that are scheduled between the time you run the query and the time the tasks are executed anyway. – Robert Harvey Nov 9 '16 at 17:58
0

You can solve this without polling.

I assume that you are only interested in time events.

  • you have a database-table with all non-executed time events.
  • you have a sql-query "getNextEvent" that returns next not yet execute minimum event-datetime.
  • getNextEvent is executed every time the event-datetime-queue is modified or when a time-event-action has finished.
  • if this event-datetime is before now (in the past) then the event is overdue and can be executed immediately.
  • if this event-datetime is in the future your event-time-egine can sleep until that datetime.

The battery efficient android alarm-clock works this way

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.