Lobby Player API: help me!

[FliesLikeABrick]

As mentioned in this thread, the lobby will have a shiny new feature in the near future.  There's one aspect of the player tracking that I haven't thought of: how to know when a player leaves the server.

There's only one way that I thought to solve this: every time I get an update from the server that has player names (every minute), I do the following steps:
- Remove all entries in the player tracking table that are in this server (aka that match the server IP and port)
- Insert the player name, server IP and server port into the player-tracking table (for each player in the server)


The problem with this is that it creates a very small amount of time where there's no information on who is in that server.  Technically this just isn't good/is a race condition of sorts... and I don't like that.  I want a better way to do it


I need help to think of better ways to do this.  Maybe it involves keeping a timestamp on all of the entries in the player tracking table, and just removing stale entries from there.  I don't know, and need some other people to help me think outside the box on this one. 

Thoughts?

[urraka]

What information exactly do you get in every update from the server?
If you get the list of online players, you could check against the table to remove whoever isn't in that list from the tracking table, and also add whoever isn't on the table*. A timestamp doesn't sound very reliable, as a lot of people enter servers just to leave them.

*edited, i had wrote on the list twice lol

[chrisgbk]

What information exactly do you get in every update from the server?
If you get the list of online players, you could check against the table to remove whoever isn't in that list from the tracking table, and also add whoever isn't on that list. A timestamp doesn't sound very reliable, as a lot of people enter servers just to leave them.

The most it would be is 60 seconds, until the server updated with the lobby; and they would only show up in the first place if the server updated while they were in the server. But there is a better solution below.

As mentioned in this thread, the lobby will have a shiny new feature in the near future. There's one aspect of the player tracking that I haven't thought of: how to know when a player leaves the server.

There's only one way that I thought to solve this: every time I get an update from the server that has player names (every minute), I do the following steps:
- Remove all entries in the player tracking table that are in this server (aka that match the server IP and port)
- Insert the player name, server IP and server port into the player-tracking table (for each player in the server)


The problem with this is that it creates a very small amount of time where there's no information on who is in that server. Technically this just isn't good/is a race condition of sorts... and I don't like that. I want a better way to do it


I need help to think of better ways to do this. Maybe it involves keeping a timestamp on all of the entries in the player tracking table, and just removing stale entries from there. I don't know, and need some other people to help me think outside the box on this one.

Thoughts?

Serialize access to the tables.

http://mysql.communitech.net/doc/en/LOCK_TABLES.html

Then you CAN'T read from the table until you finish updating it. These mechanisms exist for this very scenario.

Code: [Select]

mysql> LOCK TABLES trans READ, customer WRITE;
mysql> SELECT SUM(value) FROM trans WHERE customer_id=some_id;
mysql> UPDATE customer SET total_value=sum_from_previous_statement
    ->        WHERE customer_id=some_id;
mysql> UNLOCK TABLES;


[DePhille]

Ooh, this is a good topic .

Some notes:
Imagine this situation:
Server A sends a query to the lobby server every minute on second 0. (10:50:00, 10:16:00, ...)
Server B sends a query to the lobby server every minute on second 30 (10:50:30, 10:16:30, ...)
Imagine a player leaving server A on 10:50:01 and joining server B on 10:50:20. This will go as follows:

10:50:00 - Server A sends the update to the lobby server, with the player still in the server.
10:50:01 - Player leaves server A
10:50:20 - Player joins Server B
10:50:30 - Server B sends the update to the lobby server, with the player in the server.
10:51:00 - Server A sends the update to the lobby server, WITHOUT the player in the server.

As you can see, you'll need timestamps or a similar value in connection with the time anyhow.
You must also remember to only delete the players with corresponding IP AND ServerIP and Port.
The above method will also have a moment where the player is in two servers, between 10:50:30 and 10:51:00.


A possible solution:
Make the PlayerIP field unique.
Make a field named "Updated" or something, int(1).
Then, when an update is recieved from the server:

Code: [Select]

<?php
//Try to insert the player into the database. This will fail if he'salready in it.
$query="INSERT INTO players (PlayerIP, Updated, ...) VALUES ('ip', 1, ...);";
if(!mysql_query($query)) {
 Â  Â  Â  //The query failed, so the player's aready in the database:
 Â  Â  Â  $query="UPDATE players SET PlayerIP='ip', Updated=1, ... ";
 Â  Â  Â  mysql_query($query);
}

// Remove the players from that server that have Updated set to 0
mysql_query("DELETE * FROM players WHERE ...");

//Set all Updated values of that server to 0:
mysql_query("UPDATE players SET Updated=0 WHERE ...");
?>
PS: I dont know what language the API will be written in, but it was very easy for me to explain it using PHP. Most of the code were queries anyhow.

The drawback (hey, correct spelling this time!) is that it takes quite alot of queries for the actual purpose. However, you could combine all the UPDATE queries into one query, and then execute it.

This is a solution I made up just now in a few minutes. i'll try to post a better one once I find one.

Grtz, DePhille

[DeMo]

Is the locking really necessary chris?
I remember reading the MySQL manual and it said that UPDATE queries by default have a higher priority than the SELECT ones. This means that if an UPDATE has been issued, the following SELECT queries will be delayed until the update is complete.

There's even a SELECT HIGH_PRIORITY statement that's used to force a SELECT even when an UPDATE has been issued before it.

[urraka]

I think it would be better to use the locking anyway, to avoid relying on that kind of specific information you tend to forget. Also, if more than one query is used for the update, i guess it would be necessary... I'm not really sure cause I haven't been much into this stuff.

[chrisgbk]

Is the locking really necessary chris?
I remember reading the MySQL manual and it said that UPDATE queries by default have a higher priority than the SELECT ones. This means that if an UPDATE has been issued, the following SELECT queries will be delayed until the update is complete.

There's even a SELECT HIGH_PRIORITY statement that's used to force a SELECT even when an UPDATE has been issued before it.

Because his operations are split into two mysql statements, yes, the locking is required for the desired behaviour.

When I said updating the table, I wasn't referring to UPDATE, I meant updating as the complete series of operations needed to be performed.

[ramirez]

Yeah, locking sounds the best approach to me as well, as it allows you to run all of the statements atomicly (DeMo, as chrisbk pointed out, without locking only that one UPDATE is run atomicly, thus there could be a SELECT query between the DELETE and the INSERT queries, locking prevents that). Depending on the table(s) type, you can also use transactions though, locking is a mechanism to emulate the behaviour of transactions on engines that doesn't support it (MyISAM for example).

[DePhille]

Well, I'm not a fan of the locking:
There are around 300 servers, let's say 100 with players, updating every minute.
Let's say each update locks the ENTIRE table for 0.05 seconds, which is already pretty fast.
Then I'd come up with some possible problems:
- That means the lobby is locked for 5 seconds per minute, or around 10% of the time.
- The locking slows down the other updates quite alot.

You need to take into account that there's no hartbeat, every server updates itself randomly, so you have multiple instances of the code running.
The locking will have the same problem, only on another area. Imagine the update being run by a server with 32 players and a server with only 1 player, almost at the same time. Update process 1 is the 32 player server, process 2 is the 1 player server.
Update process 1 locks the table
Update process 1 starts deleting the entries.
Update process 2 locks the table, but it's already locked so nothing happens.
Update process 2 starts deleting the entries.
Update process 2 finishes deleting the entries earlier than process 1 (only has to delete 1 entry instead of 32)
Update process 2 starts inserting the new entry.
Update process 1 finishes deleting the entries.
Update process 1 starts inserting the 32 queries, which will take significantly longer than inserting only one entry.
Update process 2 finishes.
Update process 2 UNLOCKS THE TABLE.
Update process 1 finishes inserting.
Update process 1 unlocks the table, but it is already unlocked so nothing happens.

The underlined part is yet another part where there is no data returned for that particular server. The only difference with the setup in the first post is that this occurs less often and for a shorter time. But the chance for a dead moment still lies around 0.1-1% which means one in thousand requests for players will return no players at all.

The trick is to delete only those players that are not needed anymore.

I've made some guesses but I always rounded down to the lowest possible value. If the server's busy, the locking will consume more than 10% of the time for example.

PS: I still haven't found a better way to do this as my suggestion or chrisgbk's suggestion. I'll keep thinking.

Grtz, DePhille

[FliesLikeABrick]

dephille, I think that one major flaw in your example you just provided is that you're talking about process 2 deleting entries after process 1 locked it (and while it is still locked).  The server doesn't just go "ok, it is already locked."  It will tell process 2 "you cannot lock this table, it is already locked by <this server connection>" thus forcing process 2 to wait.

I think using locking for this should clear it all up, that'll be the first thing I try once I get the base code written to handle player tracking.  I'll write it all at first as if I haven't taken this matter into account at all, so that I can get the system working before making it more complicated.

so if each process does the following, let me know what you think of it:
- lock table
- delete all people from this server
- add the current people
- unlock

I'm trying to think of a good way to minimize the number of queries though.  I don't want to have to delete all people and add all people back in, since odds are that only one or two people have left.  Suggestions?

edit: Even more reason not to delete everyone and add them back (and instead just update them) is so that I can know when they first came to the server, so that when queried I can say "this player has been in server foo for X minutes/hours" or "... since <date>"

A clear alternative is to simply loop through the players I just got from the server, see if they're already in the server.  If not, insert them.  If they are, update... but this is just as inefficient (still 2N queries).  This is probably the better option than deleting all and inserting all, but I'd still like to hear any thoughts on better ways to do it.

[Clawbug]

I am not very experienced with this kind of stuff, thus can not contribute much.

I think I am a bit lost here, but is there any way to compare who was in in last update, and who is right now? lock, get who were in last time, see who are in this time, delete/add the differences unlock.

I do not believe this is very efficient, and actually I did not really read all the replies properly.

[DePhille]

About the locking:
Hmm, if the other process has to wait until the table is unlocked again, the 'lock-time' of the table will be a bit more than 10% of the total time then. If you're also willing to know how long the player has been playing in that server then I'm almost pretty sure the easiest way is replacing the Update value with a timestamp and comparing it with the current time instead of with 0 and 1.

About the high number of queries:
I do not know what language the API will be written in but if the program will be running continuously, you could add all the player's IP and server details in an array. This would consume some memory but avoid a high load on the CPU and database. You don't also have to get the data out of the database to return it, you could simply read it from the memory and return it. It would also solve all the problems mentioned above - but, at the cost of more memory-usage.

Another quick option:
Serialize the playernames and then store them. This adds alot of other problems, but also solves some.
You could simply perform one query that would update the table:
UPDATE servers SET players=serialize($players)

It would be a very quick solution, there's no 'dead-moment', where the server's playerlist is empty and it only requires one query. Then again, there are some problems:
- If the player changes server in less than a minute, he'd be twice in the list for the remaining time of that minute.
- You'd have to use "SELECT players FROM servers WHERE players LIKE ..." to select something from the database, which would return several matches.
- Puts a bit of extra stress on the CPU if someone's requesting a player's location.

This was just a quick idea I got. Maybe someone else can make it into a more realistic idea.



Grtz, DePhille

[chrisgbk]

Well, I'm not a fan of the locking:
There are around 300 servers, let's say 100 with players, updating every minute.
Let's say each update locks the ENTIRE table for 0.05 seconds, which is already pretty fast.
Then I'd come up with some possible problems:
- That means the lobby is locked for 5 seconds per minute, or around 10% of the time.
- The locking slows down the other updates quite alot.

You need to take into account that there's no hartbeat, every server updates itself randomly, so you have multiple instances of the code running.
The locking will have the same problem, only on another area. Imagine the update being run by a server with 32 players and a server with only 1 player, almost at the same time. Update process 1 is the 32 player server, process 2 is the 1 player server.
Update process 1 locks the table
Update process 1 starts deleting the entries.
Update process 2 locks the table, but it's already locked so nothing happens.
Update process 2 starts deleting the entries.
Update process 2 finishes deleting the entries earlier than process 1 (only has to delete 1 entry instead of 32)
Update process 2 starts inserting the new entry.
Update process 1 finishes deleting the entries.
Update process 1 starts inserting the 32 queries, which will take significantly longer than inserting only one entry.
Update process 2 finishes.
Update process 2 UNLOCKS THE TABLE.
Update process 1 finishes inserting.
Update process 1 unlocks the table, but it is already unlocked so nothing happens.

The underlined part is yet another part where there is no data returned for that particular server. The only difference with the setup in the first post is that this occurs less often and for a shorter time. But the chance for a dead moment still lies around 0.1-1% which means one in thousand requests for players will return no players at all.

The trick is to delete only those players that are not needed anymore.

I've made some guesses but I always rounded down to the lowest possible value. If the server's busy, the locking will consume more than 10% of the time for example.

PS: I still haven't found a better way to do this as my suggestion or chrisgbk's suggestion. I'll keep thinking.

Grtz, DePhille

About the locking:
Hmm, if the other process has to wait until the table is unlocked again, the 'lock-time' of the table will be a bit more than 10% of the total time then. If you're also willing to know how long the player has been playing in that server then I'm almost pretty sure the easiest way is replacing the Update value with a timestamp and comparing it with the current time instead of with 0 and 1.

You really misunderstand what locking does, and what MySQL does internally with regard to locks (and the timing issues) =P. Locking prevents multiple processes from accessing the same thing until the previous process is finished, and there are mechanisms in place to make it impossible for multiple processes to enter simultaneously, eliminating race conditions. Internally, MYSQL operates as a priority queue, and processes them one at a time, except in cases where it's possible to safely allow multiple requests to execute (Such as read-only requests when no write operation is in progress; see below). There is 0 possibility for a "dead moment".

In actual fact, MySQL already does this locking internally on a per-statement basis; such things as UPDATE request a write access lock, which prevents reads or write, while SELECT and the like use a read access lock, which prevents writes, but allows reads from other processes.  As Ramirez said, this is for times when you have multiple statements that represent a single transaction and it's important to prevent reads and/or writes until you are finished with the entire transaction.

You can get more information on the internal locking system @ http://dev.mysql.com/doc/refman/4.1/en/internal-locking.html (or 5.0 or 5.1, just change version number in URL)

You can view how many queries were forced to wait due to locks in an existing database with 'SHOW STATUS LIKE 'Table%'; "Table_locks_immediate" is how many locks were obtained without waiting, while "Table_locks_waited" is how many were added to a queue to wait. As an example, a database that didn't use LOCK TABLE had the following:

Code: [Select]

+-----------------------+---------+
| Variable_name         | Value   |
+-----------------------+---------+
| Table_locks_immediate | 1151552 |
| Table_locks_waited    | 15324   |
+-----------------------+---------+
Out of 1166876 locks, 15324 waited; or 1.3%

Using LOCK TABLES is actually more efficient than a collection of individual statements, since only the entire section has to wait for a lock, instead of each individual statement; the more statements you have, the greater the cost savings become at a rate of (n-1)/n (1/2 saved, 2/3 saved, etc).

[ramirez]

edit: Even more reason not to delete everyone and add them back (and instead just update them) is so that I can know when they first came to the server, so that when queried I can say "this player has been in server foo for X minutes/hours" or "... since <date>"

A clear alternative is to simply loop through the players I just got from the server, see if they're already in the server.  If not, insert them.  If they are, update... but this is just as inefficient (still 2N queries).  This is probably the better option than deleting all and inserting all, but I'd still like to hear any thoughts on better ways to do it.

Even if you did, you'd still need to delete the players that have left, which would add more to that approach.

What I'd do is this:
1) First delete all the players who have left with something such as (this isn't supposed to be any programming language just SQL):

Code: [Select]

DELETE FROM track_players AS tp WHERE tp.server = $SERVER AND tp.name NOT IN($NAMES)$NAMES would be a string such as "'name1', 'name2', 'name3', 'etc'", which should be fairly easy to create in any language (for example in PHP you can simply use implode() ).

2) Next you insert new players. You simply do this by ignoring the already existing players:

Code: [Select]

INSERT IGNORE INTO track_players (server, name, ip, join_time, whatever) VALUES ($SERVER, $NAME, $IP, $TIME, $ETC)Now for this to work you just need one thing; An unique index. You can't simply create an unique index on name, since it's possible that different people with same name are on different servers at same time (eg. "Major"). So you create a multi-column UNIQUE index:

Code: [Select]

ALTER TABLE `track_players` ADD UNIQUE `server_player` ( `server` , `name` )I don't know how the lobby system works, to be more precise I don't know how it tracks servers. If it assigns each server that registers in lobby an unique ID upon registering itself for first time, and then using that unique ID for consequent updates, there shouldn't be no problem at all. But if it tracks the servers by its name as well, then this approach will have an issue with servers with duplicate names (if the lobby allows it). To be more precise, it wouldn't be possible to track two players with same name on different servers, if the servers have the exact same name. That should be a pretty rare case, but still it can happen. But if the servers are tracked by a numeric ID that is unique, then this won't be a problem at all.

After the UNIQUE key is there, everything should work smoothly. However the chances are that IF there's a player that already exists, instead of just ignoring it you might want to update some of the data (kills, deaths, the player's number if he left and rejoined the server between last update in which case the ID the server assigned him might've changed, etc). If that's wanted, change the query to this instead:

Code: [Select]

INSERT INTO track_players (server, name, ip, join_time, whatever) VALUES ($SERVER, $NAME, $IP, $TIME, $ETC) ON DUPLICATE KEY UPDATE kills=$KILLS, deaths=$DEATHSYou catch the drift.

[chrisgbk]

Now for this to work you just need one thing; An unique index. You can't simply create an unique index on name, since it's possible that different people with same name are on different servers at same time (eg. "Major"). So you create a multi-column UNIQUE index:

Code: [Select]

ALTER TABLE `track_players` ADD UNIQUE `server_player` ( `server` , `name` )I don't know how the lobby system works, to be more precise I don't know how it tracks servers. If it assigns each server that registers in lobby an unique ID upon registering itself for first time, and then using that unique ID for consequent updates, there shouldn't be no problem at all. But if it tracks the servers by its name as well, then this approach will have an issue with servers with duplicate names (if the lobby allows it). To be more precise, it wouldn't be possible to track two players with same name on different servers, if the servers have the exact same name. That should be a pretty rare case, but still it can happen. But if the servers are tracked by a numeric ID that is unique, then this won't be a problem at all.

Theres one way to guarantee that each server is unique; use the server IP and port. It's not possible for any 2 servers to have the same IP and port. That would solve that.

[ramirez]

Now for this to work you just need one thing; An unique index. You can't simply create an unique index on name, since it's possible that different people with same name are on different servers at same time (eg. "Major"). So you create a multi-column UNIQUE index:

Code: [Select]

ALTER TABLE `track_players` ADD UNIQUE `server_player` ( `server` , `name` )I don't know how the lobby system works, to be more precise I don't know how it tracks servers. If it assigns each server that registers in lobby an unique ID upon registering itself for first time, and then using that unique ID for consequent updates, there shouldn't be no problem at all. But if it tracks the servers by its name as well, then this approach will have an issue with servers with duplicate names (if the lobby allows it). To be more precise, it wouldn't be possible to track two players with same name on different servers, if the servers have the exact same name. That should be a pretty rare case, but still it can happen. But if the servers are tracked by a numeric ID that is unique, then this won't be a problem at all.

Theres one way to guarantee that each server is unique; use the server IP and port. It's not possible for any 2 servers to have the same IP and port. That would solve that.

Oh yeah, that's true and would work just well. The real benefit of using a numeric ID over a server name or ip:port is that since the column is indexed, it's faster to look up if it's an integer.

[chrisgbk]

Now for this to work you just need one thing; An unique index. You can't simply create an unique index on name, since it's possible that different people with same name are on different servers at same time (eg. "Major"). So you create a multi-column UNIQUE index:

Code: [Select]

ALTER TABLE `track_players` ADD UNIQUE `server_player` ( `server` , `name` )I don't know how the lobby system works, to be more precise I don't know how it tracks servers. If it assigns each server that registers in lobby an unique ID upon registering itself for first time, and then using that unique ID for consequent updates, there shouldn't be no problem at all. But if it tracks the servers by its name as well, then this approach will have an issue with servers with duplicate names (if the lobby allows it). To be more precise, it wouldn't be possible to track two players with same name on different servers, if the servers have the exact same name. That should be a pretty rare case, but still it can happen. But if the servers are tracked by a numeric ID that is unique, then this won't be a problem at all.

Theres one way to guarantee that each server is unique; use the server IP and port. It's not possible for any 2 servers to have the same IP and port. That would solve that.

Oh yeah, that's true and would work just well. The real benefit of using a numeric ID over a server name or ip:port is that since the column is indexed, it's faster to look up if it's an integer.

Theres always hashing; pick a decent hashing algorithm and you can pretty much guarantee you won't get collisions with this limited set of data.

edit:

Actually, since an IP can also be represented as a 4 byte integer, it's easy to also store it as a number. ie: 127.0.0.1 == 2130706433; you could also add the port into that and create an 8 byte number (well, 6 byte in reality, since the port is only 2 bytes); ie: 127.0.0.1:23071 could be represented as 139637976816159.

[FliesLikeABrick]

For anyone who is interested:

<ramirez> i was just curious that do you use MyISAM or InnoDB engine for lobby tables
<FliesLikeABrick> ah just sent you an e-mail
<FliesLikeABrick> because of that lobby api thread?
<ramirez> yeah
<ramirez> because with InnoDB you could do row-level locking
<ramirez> instead of locking entire tables
<FliesLikeABrick> row-level locking wouldn't be enough
<ramirez> which can speed up the lobby in case there's a lot of activity
<FliesLikeABrick> because I don't store player info in the server table
<FliesLikeABrick> I'm going to store player info in a player table separately, so that it is easier to query for stuff
<FliesLikeABrick> one row per player
<ramirez> well what i meant was that
* Cube` has quit (Read error: Connection reset by peer)
<FliesLikeABrick> if it was one row per server (which it is in the server table), and I stored player names as a serialized string, then it could be useful
<ramirez> you can lock multiple rows with InnoDB
<FliesLikeABrick> its MyISAM anyway
<FliesLikeABrick> right, but what would that gain me? 
<FliesLikeABrick> is that only useful for updates?
<FliesLikeABrick> or can I lock a bunch of rows, remove them, then unlock them to commit the removal?
<ramirez> yeah, exactly
<ramirez> InnoDB does reading bit differently than MyISAM, it doesn't lock the tables for reading
<FliesLikeABrick> but then I could have duplicates, as far as any second process is concerned
<ramirez> how so?
<FliesLikeABrick> because say that one person leaves a server and goes to another one
<FliesLikeABrick> unless I could read-lock the new rows as they're inserted
<ramirez> you can
<ramirez> basically, this is what you'd do
<FliesLikeABrick> and can I unlock the old rows and the new ones at the same time?
<FliesLikeABrick> (I'm just hunting for race conditions)
<ramirez> well
<ramirez> what you could do is something like this:
<ramirez> BEGIN; SELECT 1 FROM track_players WHERE server=$SERVER FOR UPDATE; /* Here you do all the updates on that specific server */ COMMIT;
<ramirez> even if other processes try to read that table at same time as it's updating
<ramirez> the data will be correct
<FliesLikeABrick> so pretty much it commits all of the things at once
<FliesLikeABrick> gotcha
<ramirez> because it'll use a "shadow" of the data
<FliesLikeABrick> so it "handles" which rows to lock on its own
<ramirez> yep
<ramirez> it works by indexes
<FliesLikeABrick> it is pretty much just ensuring that my transaction occurs all at once
<ramirez> server would need to be an indexed column for it to lock
<ramirez> but well
<ramirez> I'd first do it with MyISAM because MyISAM is faster generally.
<FliesLikeABrick>  yeah, and I am
<ramirez> InnoDB only gets really beneficial when there's a lot of activity
<FliesLikeABrick> table locking is sufficient and should be fine
<FliesLikeABrick> if not, I can convert this one table to InnoDB easily
<ramirez> yeah

I'll read the other new posts in this thread once I get to work, but I'll point this out:

In the server table, I have `serverIP`,`port` set as the primary key already.  In the player table, it is `serverIP`,`port`,`playerName`

I'm already a step ahead that way

[ramirez]

Then you should be pretty much set for the INSERT IGNORE/INSERT ON CONFLICT UPDATE approach.

[FliesLikeABrick]

I'm guessing that I should probably give servers unique IDs, so that lookups in the player table don't have to be done on two fields, just one