Rudimentary MySQL-based message queues and long polling

[andrewjbaker]

Hi all,

Over the past month or so I have been slowly beavering away at the rudiments of a survival horror RPG. I have a very simple Web page that allows me to move around a map.

I had originally intended to use individual tiles for my map but I came to the conclusion that this was too much effort for too little reward, so... I'm now using OpenStreetMap data and the OpenLayers JavaScript library to render the PC's immediate location based on Ordnance Survey grid references.

I have also made the switch to AJAX; I'm using jQuery to issue commands to my server-side command multiplexer. The multiplexer simply executes methods (like goNorth(), carry($item), etc.), which in turn triggers alterations to state (held in MySQL) before feeding back any updates to the client-side JavaScript as JSON.

So far, so good. But now I'm beginning to reach a point where I'm considering the multi-user environment, where game state needs to remain in-sync. between one client and the next.

Everything happens immediately at the moment which is fine for a single-player game, but I don't want to make 'I am Legend' online; I want friends (and foes). :-)

I'm considering using the long polling technique coupled with a message queue arrangement (persisted to MySQL). Basically, whenever someone clicks in the UI, an AJAX request is sent to my multiplexer. The multiplexer is now largely responsible for simply INSERTing commands into the message queue... and every five seconds (or some other arbitrary number) messages will be plucked from the queue and executed. Then, once the queue is empty (or 100 messages have been processed, or whatever) I'll post-back the JSON necessary to update each clients' UI, thus completing the long poll.

The five second pause I can introduce by maintaining a 'last tick' variable and checking whether time() > $last_tick + 5 each time the multiplexer script is executed.

This sounds 'workable' but what about the practicalities? Am I barking up the wrong tree? :-s

Cheers, Andy.

[lolninja]

Implementing the polling on the client side is pretty simple as you mentioned, for those reading for insite see example...

Code: [Select]

$(document).ready(function(){
// Gogo recursive ajax
(function(){
var updateWorld = function(){
$.getJSON('http://www.example.com/data.json', function(){
setTimeout(function(data){
console.log(data);

updateWorld();
}, 1000);
})
};
updateWorld();
})();
});

What this does is every 1000ms or 1 second pull a json document from the server and does something with it, currently its only console.logging it, but you could fire off any number of actions based on this.

Now the problem with this kind of system is when you have say 100 players on a game all polling your server every 1-3 seconds is your going to have between 2000 and 6000 requests per minute, so goggling around tells me that a small dedicated server can handle around 12000 requests per minute, which is between 200 and 600 users online.

Now if that number is what you were hoping for, awesome stop reading... If your still hear I assume that 200-600 was kind of disappointing, well that just means its time to get a bit creative, jquery supports jsonp, which is the same as json, but its wrapped in a self executing function. Now I hear you say "lolninja, why mention jsonp" well, what jsonp does is avoid calls to remote servers being block, as its just downloading text, and text never hurt anyone So now we can execute json requests to remote domains, in this hypothetical situation remote domains will be subdomains under your tld.

This little step means you can drop more servers into your game and scale in multiples of 200-600 users, so for example if your main content is on www.example.com you could have your multiplexer on multiple servers using dynamic1.example.com, dynamc2.example.com... and scale till your eyes bleed.

Now this is all find and well, but what about your database, wouldn't having multiple servers accessing one database is bad, well if you get to this point firstly congrats, secondly you tweak your database access code to allow it to read from multiple slave mysql servers, but write to one, this allows you to scale even more

If none of that makes sense it likely means I got the wrong end of the stick, and failed to answer your question

[andrewjbaker]

200-600 users?! That sounds fantastic. End.

Only jokin'... that really is good to know. If I hit 200-600 concurrent users I'll be very happy; I had been aiming for somewhere in the region of 50 concurrent users to begin with.

I'm pleased to hear that the approach I'm looking at adopting is workable and, what's more, with the introduction of JSONP, it's also highly scalable to boot.

I must admit that I'm still slightly unclear how all this is going to work in practice, but I guess the best way to find out is to suck it up and get coding.

Cheers.

Oh, one other thing... I also found this article (http://www.michaelhamrah.com/blog/2008/12/event-pooling-with-jquery-using-bind-and-trigger-managing-complex-javascript/) that discusses firing events in jQuery (all client-side) so perhaps I can use bind and trigger too. That way... the recursive long polling routine can simply fire a client-side event when it receives the data. Big, big grin... :-D

[lolninja]

Nps

You'll need to be careful, if your updates do much more than access the database, make some changes it'll hurt your performance, and you may need to tweak your apache settings to get more out of it, but its defiantly doable.

If you need to ask questions on possible ways of doing stuff just post in here, and I'll see if I can help

[andrewjbaker]

I have another related question... but this time using the opposite technique of a pull-based approach.

Presumably I can reduce server load by making HEAD requests to the server and only sending back data when there's something truly available. Is this technique equally workable?

[Harkins]

If you're thinking of making a HEAD request and setting a header to indicate when a client should do a full GET, don't bother. You'll add a lot of complexity but could get the same effect by always doing GET and having the server give a 0-byte response when there's no content. (And this is a reminder to delete any unneeded headers, the bandwidth adds up in AJAX-heavy apps.)

If you mean do a HEAD and the server will sleep() until there's data and then do a GET. Again, might as well do a GET and sleep(). And you'll probably run out of Apache processes because you'll have one per tab each online player has open. This is why folks turn off KeepAlive.

[lolninja]

Right just to clarify, please ignore if I'm getting myself in a muddle, but the system we've been discussing isn't long polling, its just polling, the long bit means that your server leaves open a connection, that it writes messages to and after a period of time the connection closes and a new one is opened.

The problem with this kind of setup is that it leaves connections open for a period of time, so if your using apache you can cut your concurrent user limit right down to 15-30. This is because apache spawns a new thread per request, which is ace for traditional sites, as you dont have to worry about memory usage, as once the request is over, everything closes neatly.

The benefit of long polling is events happen in a faux real time, though this can be better implemented by a custom solution or modifying a comet server, which isn't for the faint hearted.


If your going with a polling system, where by you ask your server for updates on a timed bases then the code example from my first reply will do the trick, the problem with this is that you lose the faux realtime, but increase your persistance count.

So assuming your wanting to roll with a polling system you can optimise the transmitted dataset by culling all items that exceed a set radius, so depending how your database is setup you can do something like...

Code: [Select]

SELECT *
FROM world as w
WHERE w.x > 50 AND w.x < 100 AND w.y > 50 AND w.y < 100
// this can get a lot more sophisticated, by doing a subselect to find a specific user, then using that character's location as the base for the region-ing.

This will limit the about of data your returning, which should optimise it a bunch, remember if your database is correctly setup it'll be faster use the where statement to cull what you dont want than to get more data than you need and limit it via your server side language.

If there is nothing happening in a specific region you can return the header code 204 or 'No Content'. Which limits the data you send down the line.

It might also be worth implementing your recursiveAjax call so that you can scale the update frequency from the server, this can be as simple as including updateFrequency in your json, and in your js moving the 1000 into its own variable, see example, this way you can implement some kind of logging on the server to monitor load, and if you notice a spike, just lower the frequency.

Code: [Select]

$(document).ready(function(){
// Gogo recursive ajax
(function(){
var updateFrequency = 1000;
var updateWorld = function(){
$.getJSON('http://www.example.com/data.json', function(){
setTimeout(function(data){
console.log(data);
if (data.updateFrequency) {
updateFrequency = data.updateFrequency;
}
updateWorld();
}, updateFrequency);
})
};
updateWorld();
})();
});


[andrewjbaker]

Ah... OK. Not long polling... right. I had read this article (http://blog.perplexedlabs.com/2009/05/04/php-jquery-ajax-javascript-long-polling/) that discusses the use of long polling to keep the connection open. But, like you say, I'd be restricting myself to 15-30 concurrent users which isn't what I want.

WRT the recursive function call... I know there aren't any arguments being passed to the function (so that'll help to reduce the amount of stack space that's eaten up) but surely the continuous recursive calls will eventually reduce the amount of stack space available. Or, have I missed something here? Once my UI is displayed, the Web page never refreshes; AJAX is the only method used to update the UI. :-s

Oh, I really like the idea of being able to control the AJAX timeout from the server BTW.

Thanks.

[andrewjbaker]

@Harkins: Thanks for pointing out that removing unnecessary headers will reduce overhead of AJAX calls. Do you know how I can achieve that in PHP?

[Harkins]

@Harkins: Thanks for pointing out that removing unnecessary headers will reduce overhead of AJAX calls. Do you know how I can achieve that in PHP?

Code: [Select]

header_remove('Name')

But I think this only works on the headers that PHP itself sets, which is not much besides cookies.

So tell Apache to use mod_headers (ships with Apache by default) to remove things. You can add this to your .htaccess or Apache config (but if you can edit Apache config, probably better to poke around and just turn them off in the first place).

Code: [Select]

Header unset Name

And to tell what headers there are to delete, well, of course Firebug does it (in the Net panel). Though I often do 'curl -I'.

[Chris]

INSERTing commands into the message queue... and every five seconds (or some other arbitrary number) messages will be plucked from the queue and executed.

I do not make online games with maps, so I could be wrong, but I'm almost sure a simple "go to the next spot on the tiled map" could be done much, much simplier...

[lolninja]

WRT the recursive function call... I know there aren't any arguments being passed to the function (so that'll help to reduce the amount of stack space that's eaten up) but surely the continuous recursive calls will eventually reduce the amount of stack space available. Or, have I missed something here? Once my UI is displayed, the Web page never refreshes; AJAX is the only method used to update the UI. :-s

Right this is more faux recursion, if you were directly calling updateWorld when you receive the payload then you'd run out of stack space over a period of time, whats happening is your executing a function, that adds a single operation to the state, that after a period of time calls a function, it just happens that its calling the function that added the recall.
So you get the benefit of recursion, without the memory spam, in addition if your server is under load and say takes 3 seconds to return your payload your client will automatically wait 'var updateFrequency = 1000;' before recalling it, if you used setInterval that would basically try and abuse your server, assing as it would periodically send a new request even if the prior one has yet to complete.

Yeah so with this approach your pages downloads and the Javascript is executed, your recursive ajax call then constantly polls your server until you decide to stop, to stop just down call setTimeout, you then use the data you get in the json to modify your dom.

For for example say on your server your response is build like...

Code: [Select]

<?php

$data = array(
'updateFrequency'=> 2000,
'gold'=> 123456,
'troops'=> array(
array(
array(
'name'=> 'lolninja',
'type'=> 'ninja',
'x'=> 50,
'y'=> 50
),
array(
'name'=> 'someone else',
'type'=> 'warrior',
'x'=> 60,
'y'=> 40
)
)
)
);

echo json_encode($data);

Would give you the JSON

Code: [Select]

{"updateFrequency":2000,"gold":123456,"troops":[[{"name":"lolninja","type":"ninja","x":50,"y":50},{"name":"someone else","type":"warrior","x":60,"y":40}]]}

So taking this data and mixing it with the prior example you'd get something like...

Code: [Select]

$(document).ready(function(){
// Gogo recursive ajax
(function(){
var updateFrequency = 1000;
var updateWorld = function(){
$.getJSON('http://www.example.com/data.json', function(){
setTimeout(function(data){
if (data.updateFrequency) {
updateFrequency = data.updateFrequency;
}
if (data.gold) {
$('#gold').text(data.gold);
}
if (data.troops) {
$(data.troops).each(function(id, troop){
var dom = $('#troops').find('#' + troop.name);
if (!dom.hasClass(troop.type)) {
dom.addClass(troop.type);
}
dom.animate({
left: troop.x,
top: troop.y
});
});
}
updateWorld();
}, updateFrequency);
})
};
updateWorld();
})();
});

What this will do is check to see if we send a new gold value, if we did update the dom, then check to see if the troops array was sent, if it was then we loop though its contents. We find the div tag from within the document, then make sure it has the right display class, and animates it to the new location.

This is pretty primitive, as you'd want to add div tags to your dom encase the mentioned character doesn't exist, and you'd want to check that the x, y and type are set.

Using a technique like this your able to have a constantly updating interface, and have your characters move around the map.

For bonus marks you could take the current vector for the actor, and the one that its ment to be at, find the distance using trig, then do time = distance/speed to find the duration, then plug this into jquery.animate's duration variable and have everything move around at the same pace.

[dsheroh]

If there is nothing happening in a specific region you can return the header code 204 or 'No Content'. Which limits the data you send down the line.

If you're not sending any cookies or other unnecessary headers back (disclaimer: I have no idea how difficult that might be to arrange in PHP), a 0-byte response will work just as well.  Although "200 OK" and a Content-Type header is technically longer than "204 No Content" and nothing else, the response will fit into a single TCP packet either way.

INSERTing commands into the message queue... and every five seconds (or some other arbitrary number) messages will be plucked from the queue and executed.

I do not make online games with maps, so I could be wrong, but I'm almost sure a simple "go to the next spot on the tiled map" could be done much, much simplier...

Yes, it could... if you want people to move across the map as fast as they can click, but that doesn't appear to be what the OP wants.  If you don't want events to complete immediately when the user clicks, then you pretty much have to use some variation on "put the events into a queue and process them when the appropriate time comes".

Which then gets into the "(pseudo-)real-time vs. action points" design question...

[Chris]

INSERTing commands into the message queue... and every five seconds (or some other arbitrary number) messages will be plucked from the queue and executed.

I do not make online games with maps, so I could be wrong, but I'm almost sure a simple "go to the next spot on the tiled map" could be done much, much simplier...

Yes, it could... if you want people to move across the map as fast as they can click, but that doesn't appear to be what the OP wants.  If you don't want events to complete immediately when the user clicks, then you pretty much have to use some variation on "put the events into a queue and process them when the appropriate time comes".

Which then gets into the "(pseudo-)real-time vs. action points" design question...

I'm not sure... Ages ago I was making an isometric RPG (single player) with fluid movement and I faintly remember that I was making locks on a grid you attempt to enter (to avoid NPC/monster collision). So it was displayed as realtime but in fact it worked as action based where any character was occupying 2 grids at once. It was working and no queues of any kind were needed.

Another thing, in Diablo 2 on LAN you can end up with 2 characters on different grids depending on the machine (once we got locked because everyone was accusing the other person that the other person is blocking the entrance ). The point is, if Blizzard was willing to afford such imperfection for the sake of performance/simplicty, then maybe you could to? I mean, if you make a free BBG (which means a lot of users and low income) and almost everything needs server side computation you might end up limited severly by hardware.

[andrewjbaker]

Please accept my apologies for not replying sooner. I and my family spent the last week at the seaside on holiday.

Thanks for all the code you've thrown together; it'll help me greatly. And thank you also for allaying my fears WRT the faux recursion.

dsheroh is correct; I need to trigger 'movement' events after a predetermined period of time, not instantly.

It isn't really an issue for me at the moment in terms of imposing a maximum number of PCs at a specific grid reference (map tile), though I'm pleased Chris mentioned what he did... otherwise I might've allowed upwards of 10,000 PCs to huddle together in a public toilet. :-s