Scheduling events: how to do it?

[Marek]

I have implemented a scheduling system, which I describe below. As a proof of concept, it works. My question, directed especially at database or optimization gurus: Is this feasible, performance-wise? And, directed at anyone with imagination: any ideas for other, better ways to do this? (other than using cron, which has flaws of its own.)

Let's call this a "Scheduled action system" for the purpose of discussion. The idea is that the game unfolds in real non-quantized time. However, between page requests, since no php is being run, the game state is frozen. But this is okay, since nobody can see its state. When a page request is made, the game "catches up" chronologically to the present moment, and then displays the request, pretending it never was frozen.

How things happen, under this proposed so-called SAS:

• Actions can be "scheduled" by inserting a db row that specifies the action and the timestamp when it is scheduled.
• Example: you click "build tower" which has time of 3 hours. A db row is inserting with a timestamp of "now + 3hrs".
• A "time remaining" value can be determined by querying the scheduled action to find out the timestamp of completion.
• Actions are "executed" by calling a designated callback function,  for instance, which can update the db or do anything, really.
• On every page request, a check is made: are any scheduled event *in the past*? If so, *retroactively* execute the action associated with each (example: update tower status to "construction complete")
• Here it gets complex: If one scheduled action will result in new actions being scheduled (for example, chained actions) then we have to recheck if those new actions also have taken place, because it might have been a while since the last time someone requested a page. There might be some backlog to go through.
  

Why I'm *hoping* the performance might not be TOO bad: while more active players will equal more load on the system, more page requests will mean the load will be more distributed. But this is not known. I would really appreciate everyone and anyone's thoughts!

[Harkins]

It make sense. Two hitches:

• Example: you click "build tower" which has time of 3 hours. A db row is inserting with a timestamp of "now + 3hrs".

You're going to need some mechanism for deleting untriggered actions. Otherwise someone could cancel the tower's build and still end up with a tower. Or their city could be destroyed by another player and, still, there's a tower there 3h later.

• On every page request, a check is made: are any scheduled event *in the past*? If so, *retroactively* execute the action associated with each (example: update tower status to "construction complete")

You'll need to lock the table for reading (an SQL transaction) when you do this check, otherwise you might do things twice if two people load pages at the same time.

[Chris]

I'm using similar system (athough my is simplier), I would say, go for cron. This "virtual cron" is nice because you don't have to setup it separately for each game/world/server (which is a valid point for me since I have more than 30 games), also it makes coding and testing a bit easier, but apart of it only trouble

• On every page request, a check is made: are any scheduled event *in the past*? If so, *retroactively* execute the action associated with each (example: update tower status to "construction complete")

You'll need to lock the table for reading (an SQL transaction) when you do this check, otherwise you might do things twice if two people load pages at the same time.

It is much more important than you suspect. And you can not test it, since it becomes an issue with hundreds active players, and when it turns into trousands it gets broken again
(transaction would be an overkill in my opinion, since transaction friendly tables are generally slower, it is better to be done in some cunning way, but these cunning ways are usually flawed )

The most important question: do other players need to have this data updated or is it per player only? The latter is very nice to do via virtual cron (almost no way of being triggered twice)


A note: from my experience, and to my surprise, load balancing of such "cronish" actions is irrelevant, it won't bog down your server, lags comes from active players.

[Nox]

Chris
What do you mean by "virtual" cron?

For common cron I'd say bulk updates are more suitable...I'd say necessity of updating info for 1 player would depend on frequency of updates since if we would update most players all the time than do it one by one would be quite a performance hit.

Out of common ones ... InnoDB is not that slower than MyISAM from what I've been reading recently + Codestryke advocates row-locking engines which would be very beneficial for per-player updates

A note: from my experience, and to my surprise, load balancing of such "cronish" actions is irrelevant, it won't bog down your server, lags comes from active players.

I think it was good to note that

----------
Related:
http://community.bbgamezone.net/index.php/topic,1815.0.html (cron)
http://community.bbgamezone.net/index.php/topic,2204.0.html (database)

[Marek]

You'll need to lock the table for reading (an SQL transaction) when you do this check, otherwise you might do things twice if two people load pages at the same time.

Absolutely right. An important thing to do, and yet an easy thing to mess up! Bugs caused by forgetting to lock can show up obscurely and rarely, making them so hard to fix. It's best to adhere to strict practices of making sure every query is done with appropriate locking, if any.

The issue of MyISAM locking entire tables might SOUND like a drawback, but there's an easy way to investigate into it: MySQL provides a statistic of how many queries needed to wait for a table. I think you will see that even with moderate traffic, the number of queries that wait is usually very low. So performance loss is probably going to be negligible for most cases, unless you are having high traffic. But the very fact that coinciding queries happen rarely makes those bugs the hardest to spot.

Thanks for the thread links Nox, a lot of interesting discussion there.

[JGadrow]

I can think of a possible way to "test" a concurrent access for this. Mind you, I've not tried this...

Create a script that CURLs the URL or calls the relevant function at a specified time that you supply via query parameter.

To do this, get the current script execution time and determine the difference to the requested execution timestamp. Then sleep your script that many seconds.

In this manner, you can do:
url: http://localhost/path/to/script.php?execute=[timestamp]

And pull up the url in a few browser tabs / windows. This should, in theory, cause the issue to occur. Allowing you to test if your code is safe.

If anyone tries this and is successful, it would be nice to post and state that it is possible to test for these conditions.

[Chris]

Chris
What do you mean by "virtual" cron?

What you described above, a virtual/auto cron, a solution to emulate cron-like behaviour without the usage of cronjobs. Unless you were trying to achieve something else?

Out of common ones ... InnoDB is not that slower than MyISAM from what I've been reading recently + Codestryke advocates row-locking engines which would be very beneficial for per-player updates

For per-player you don't need locking of any kind. Player can trigger only his own part of the table "WHERE id=$playerid" It is extremely unlikely for *one* player to click so fast (using different tabs) as to trigger the code twice.

[JGadrow]

I have to disagree a bit on the "per-player" locking. This might be the case with some games but other games allow one player to update a different player's record. Thus, you have a potential condition that would conflict.

For example: Player A is attacked by Player B at Coord 0,0 and defeated. The system must track that Player A now has 0 units in Coord 0,0. Thus, Player B triggered an update to a row based on Player A. But, perhaps at the same moment, Player A issued a move command to move their units to Coord 1,0. The attack likely took a moment to resolve so Player B would be granted a victory, yet Player A would retain their units because they're no longer located in Coord 0,0.

There's some obvious ways around this one, but it's only meant as a quick example.

[codestryke]

I think we as web developers try to make things fit into the technologies that we understand best and forgo thinking truly outside of the box. We've had other threads about this topic and how best to schedule "to the minute" scheduling. The game Travian (which I've never played) almost always comes up when discussing this topic. Honestly I don't know how they do there scheduling but as a company I'm sure they can and do pull programmers to develop a technology that extends outside the L/W AMP technology structure.

In the past we've discussed CRON which could work (Harkins posted somewhere about a per second CRON or something before). The catch up has been discussed as well but never needing this type of fast scheduling I've never attempted it but I see numerous problems and, personally, would go another route.

The route I would take to develop something like this would be to actually create my own service daemon. The service would auto run upon the systems boot sequence (after mySQL of course). Being lazy and wanting to get it to just work right away I would simply create a PHP script that would poll the database, get the next timestamp and then issue a sleep command until that time. The PHP script itself would always run in the background. Once finished with the script and had enough player's playing the game to make it work while to convert I would move said daemon to something like C/C++, Python or maybe even PERL. I don't know enough about PHP's garbage collection so the only reason to convert would be to make sure that all memory is cleared after every run to prevent any type of memory leakage.

For per-player you don't need locking of any kind. Player can trigger only his own part of the table "WHERE id=$playerid" It is extremely unlikely for *one* player to click so fast (using different tabs) as to trigger the code twice.

I beg to differ on this point. We've had and still have players that run multiple tabs / windows on the games. One player can have multiple writes to his/her account almost simultaneously either by being to fast or trying to piggy back requests (an absurdly easy way to cheat on an unprotected system).

I've stated before Chris' players must be the most honest player's on the web because he's never seems to have these types of problems, we on the other hand don't have this luxury

[Marek]

The route I would take to develop something like this would be to actually create my own service daemon. The service would auto run upon the systems boot sequence (after mySQL of course). Being lazy and wanting to get it to just work right away I would simply create a PHP script that would poll the database, get the next timestamp and then issue a sleep command until that time. The PHP script itself would always run in the background.

Interesting approach. But what if there are new events added into the DB after the daemon goes to sleep? If those new events have timestamps that are before the wakeup time of the daemon, they will never be executed.


JGadrow
That's a great idea for testing. It could be further extended to run a bunch of various scripts at once, to see if any negative interactions arise. I'm going to note this idea down.

[Chris]

I have to disagree a bit on the "per-player" locking. This might be the case with some games but other games allow one player to update a different player's record. Thus, you have a potential condition that would conflict.

For example: Player A is attacked by Player B at Coord 0,0 and defeated. The system must track that Player A now has 0 units in Coord 0,0. Thus, Player B triggered an update to a row based on Player A. But, perhaps at the same moment, Player A issued a move command to move their units to Coord 1,0. The attack likely took a moment to resolve so Player B would be granted a victory, yet Player A would retain their units because they're no longer located in Coord 0,0.

There's some obvious ways around this one, but it's only meant as a quick example.

I was reffering to "cron type" update, which means a kind of update that is not caused by players interaction but by a time trigger. Players interaction concurrency problem is another issue.

Sigh, I wish someone invented some standard BBG dev terms, so we could communicate clearly without the need to use lenghty and misleading statements

I beg to differ on this point. We've had and still have players that run multiple tabs / windows on the games. One player can have multiple writes to his/her account almost simultaneously either by being to fast or trying to piggy back requests (an absurdly easy way to cheat on an unprotected system).

I've stated before Chris' players must be the most honest player's on the web because he's never seems to have these types of problems, we on the other hand don't have this luxury Wink

Indeed, when I read about some of your SQL experience it sounds to me as story from another planet Wonder why...
No, I never got the problem of players trying to cheat by causing server stress, I do get sometimes problems from unintentional concurrency, but intentional, never. I also don't know how could they benefit this way... Maybe it is my coding style? I assumed from the start that SQL will be unreliable so in all queries I use add or substract variable, almost never set it (this way if they get double request they will be just charged twice and get twice the goods they should, it could lead to temporary imbalance which will be restored upon next purchase (negative goods)). Or maybe it is storage engine type? But then I with MyISAM should get it before you with Inno. Or maybe hardware? But I was running for a long time on shared, so your worst hardware was better than my then. Or maybe you are referring to the problems with old software that do not happen nowadays?
The theory of my players being more honest is quite unlikely

[codestryke]

Interesting approach. But what if there are new events added into the DB after the daemon goes to sleep? If those new events have timestamps that are before the wakeup time of the daemon, they will never be executed.

That would depend on your setup. If the fastest build you could have is 10 minutes then you could set the sleep default to 10 minutes to recheck the data (assuming it's empty). Or you could go with checking every minute, but that would be a lot of queries. Maybe go with a file write to read a file. The game would do the check at the time of build request to see if anything is coming sooner and update the text file. Multiple ways to skin the cat without using CRON or doing it within the game

[Marek]

Well, thanks for the advice on the topic, everyone. I'm now working on polishing the system that I described in the first post.

I'm having a bit of a snag with the issue of table locking, though. When I fetch the event row from the scheduler, I have to lock the scheduling table. But, I also have to lock any other tables that will be used. But at that moment I don't yet know which tables will be used, because I don't yet know which callback will be called (since that depends on what I will find in the event row).

The only fix I see is blindly lock ALL potentially accessed tables before fetching the event. Not pretty.

Is there a solution?

[Harkins]

How did you decide to deal with canceling pending events?