Internet Game Server

[hgm]

I am currently developing a server for playing (human) games over the internet, based on the Jocly user interface. The latter is a JavaScript library for implementing a chess board in 2d or 3d (based on WebGL) display, and enforcing the game rules on it. It already supports a multitude of games, not only chess variants, but also Draughts, Amazons, Annexation, Spline, Scrum, Yohoho, ...

But everything in Jocly is trictly local; it runs in your web browser, and you can do local games with it, but it does not connect to any remote opponent, neither peer-to-peer nor to a server. So that is the functionality I aim to add.

To allow communication between remote users I opted for a Game Server that is embedded in a standard HTTP server, as a CGI 'script'. (In fact it is the executable of a compiled C program.) In such a design the Game Server does not run as a persistent process, handling one command after another. Instead a new process is started for every user (HTTP) request, to handle only that request, and deliver a response to it. The persistent state of the Game Server is completely implemented in the file system of the server machine. The CGI script gives the users read and (highly-restricted) write access to this state.

I try to keep the server side of this design as simple and general as possible. ('Minimalist' would be a good description.) As Jocly is already a very powerful piece of software running in the clients, it makes sense to delegate as many tasks as possible to that. So the Game Server doesn't have to worry about legality testing of game moves, or nicely formatting its output. To it, games are just a list of moves, and moves are blackboxes that it passes along. And data requested by the user are just provided as a number of lines, each a comma-separated list. Clients can convert this info (or the part of it they want to show) into HTML that would display nicely.

Overview of server tasks

The state of the Game Server is basically just the collection of games, where each game has its own state. The latter must be modifiable by the players of that game: they must add moves to it. Of course only the player that is on move must be allowed to add a move, so it must be possible to recognize and verify the identity of the users. For this a (not publicly accessible) password file is needed, storing identities as a (public) user / (secret) password combination. To not unnecessarily burden the server operator, the Game Server must also maintain that password file.

I opted for storing each game in a separate file, recognizable by a unique number. (Like game327.txt.) Each move is stored as a separate line, so submitting a move would just append the move text as a new line to it. The first two lines are reserved for the player names and the game type (e.g. 'brazilian-draughts').

Because users will frequently want to fetch a list of games, and it would be very cumbersome to open all game files to get the player names, the Game Server will also maintain a game-list file (gamelist.txt). In a fixed-size format this contains for each game the name of the white and black player, the game type, the player clocks, and a game-state indicator. The latter is a single character that indiates who is to move (w or b), whether a draw offer is pending (capital W or B), or whether the game is finished (+, = or -). The player names and game type are immutable once the game is created, but the state and clocks must of course be updated on every move. This requires random write access to the file (hence the fixed size of its elements).

List of user requests

* add a user / password combination to the password file
* read the user names in the password file
* read the game list (possibly filtered by a player name or game type)
* read a game file (possibly suppressing the moves he is already aware of)
* put a 'game request' (a game with as yet unknown opponent) in the game list
* satisfy a game request to initiate a game
* possibly delete a game request that no one wants to satisfy
* add a move to a game
* resign a game
* offer a draw in a game
* abort a game (?)

A server could also allow chatting between users. This would add extra state, and extra requests to read or modify that state. I haven't thought much about that yet.

[smatovic]

...
List of user requests

* add a user / password combination to the password file
* read the user names in the password file
* read the game list (possibly filtered by a player name or game type)
* read a game file (possibly suppressing the moves he is already aware of)
* put a 'game request' (a game with as yet unknown opponent) in the game list
* satisfy a game request to initiate a game
* possibly delete a game request that no one wants to satisfy
* add a move to a game
* resign a game
* offer a draw in a game
* abort a game (?)

A server could also allow chatting between users. This would add extra state, and extra requests to read or modify that state. I haven't thought much about that yet.

Hmm, just my pov,
but imo this (growing) feature list is a classic task for web development frameworks like PHP or Ruby on Rails with an SQL DBMS behind.
One advantage will be the implemented session handling.

--
Srdja

[odomobo]

I agree with Srdja. Also, dealing with plain text files will limit scalability after some point. And you pointed out that multiple processes will have to modify the same file at a time, which could introduce concurrency bugs. The simple solution (IMO) is to let a DB handle that complexity for you.

I guess a question I don't understand is the use case for the project. Is this primarily a hobby project, where usefulness is a secondary goal? Are there currently no good open-source servers like this already, so you'll be fulfilling a need that isn't being met? Will this be limited to serving no more than a few hundred games at a time, or should this be able to scale beyond that?

If it's more of a hobby project, with limited scalability requirements, then your approach seems fine. However, if the plan is to make something which could compete with, say, lichess, then I think you'd benefit from using traditional web technologies.

Those are just my 2c. Good luck with the project!

[hgm]

Hmm, just my pov,
but imo this (growing) feature list is a classic task for web development frameworks like PHP or Ruby on Rails with an SQL DBMS behind.

But all languages I do not know... It is bad enough that I had to learn JavaScript in order to understand the Jocly API. The idea is to build this in a few days. In C I know how to do everything and can do anything that the OS would allow.

And you pointed out that multiple processes will have to modify the same file at a time, which could introduce concurrency bugs

I don't think there is any such problem here. A game file can only be modified by one person: the player that is on move. The gamelist file can be written by many users simultaneously, for altering side to move and updating clock, but only in non-overlapping sections, where each section corresponds to one game, and only a single person at the time has the right to move in that game.

As to the goal of the project: there are not (m)any servers where you can play live games of, say, Elven Chess or Scirocco. Or even Gothic Chess. So the goal is to provide a unique facility. OTOH I don't expect that there would ever be thousands of players for Elven Chess, Scirocco and Gothic Chess combined, and the few that are there won't play all at the same time. To I don't expect a heavy load ever. If, against all expectations, it would attract so many users that this would become a problem, it would already be a success surpassing my wildest dreams. Then it might be worth spending serious time for developing something more efficient. But before that it would probably be a waste of time to aim for anything other that the quickest and most simple way to offer the functionality.

I must admit that I have no idea what the mentioned 'proven technologies' encompass. But I would be surprised if they would greatly outperform what I have in mind. Isn't it true that no matter what, they sooner or later will always have to commit the server state to file? So how could directly writing on a file with the C program that received the request be any slower? My largest worry is that unsuccessful polling consumes unnecessary bandwidth on the network.


HTTP interface

What I currently have is a CGI 'server engine' that supports the following arguments on HTTP GET requests:

Code: Select all

?list=NAME                                print all games with player NAME
?game=N                                   print game number N
?game=N&start=M                           same, but suppress first M lines
?cmd=who&user=NAME&pw=PASSWORD            print all users
?cmd=newuser&user=NAME&pw=PASSWORD        add NAME/PASSWORD to pw file
?white=VARIANT&user=NAME&pw=PASSWORD&tc=T request a game as white
?black=VARIANT&user=NAME&pw=PASSWORD&tc=T request a game as black
?attach=N&user=NAME&pw=PASSWORD           join request N
?move=MOVE&user=NAME&pw=PASSWORD&nr=N     submit move for game N
?move=resign&user=NAME&pw=PASSWORD&nr=N   resign game N
?move=draw&user=NAME&pw=PASSWORD&nr=N     offer/accept draw in game N

Here all requests that contain user and pw arguments are only executed if the USER/PASSWORD combination is found in the password file. VARIANT is the name of a game type, NAME in the 'list' command can also be a game type, as it is matched with both players and game type to decide which lines are printed. MOVE is a move, in whatever format the client likes. Move texts 'draw' and 'resign' are reserved for those actions. All requests are replied to with a message of MIME type text/plain; for requests that do not ask for data this contains a short confirmation (e.g. 'Move accepted') or error message both fit for displaying to the user.

'Live' games

The most interesting request is that to download a game. This also provides the info needed to reconstruct the time on the clock of the player that is on move. The gamelist file contains the clock times, but these 'clocks' are not actually ticking, but left statically at the value they had when the latest move was submitted. So the active clock would have to be corrected for the time elapsed since then. This correction is obtained by the Game Server from the modification time of the game file, and the current time, and is then appended to the data in the game file when sent to the client.

An optional start=M can be specified with this command to suppress the first M moves. This makes the command more suitable for polling for new moves, when your opponent is on move, or you are observing a game by others. If you suppress the moves you already received before, unsuccessful polls would then not consume so much bandwidth as when you would repeatedly get all moves of the entire game.

The plan is to implement a game requests that suppresses all moves as long polling (not tested yet). Instead of sending back and empty or explicit fail response immediately in such a case, the game server will delay the response for up to 30 sec, until the game file is written. The Linux 'inotify' system call can be used to suspend the process in the mean time, by setting a 'watch' for closing writing on that game file, and then doing a blocking read on the notify channel. After 30 sec that read will be interrupted by setting an alarm, and the poll will have failed (and a new one will be issued). But if in the mean time a HTTP request from the opponent will have deposited his move, the process serving the poll request will wake up immediately, read that move, and send it as a successful response. This allows instant transmission with rather infrequent polling; in a blitz game most moves should be obtained with the first poll.

[smatovic]

Hmm, just my pov,
but imo this (growing) feature list is a classic task for web development frameworks like PHP or Ruby on Rails with an SQL DBMS behind.

But all languages I do not know... It is bad enough that I had to learn JavaScript in order to understand the Jocly API. The idea is to build this in a few days. In C I know how to do everything and can do anything that the OS would allow.

Like Josh already said, it may depend on how many users you plan to serve.
I guess with about 10 concurrent users your approach might work,
but with about 100, or an whole online community,
then i doubt you will have much fun on the long road.

As web framework i can recommend Ruby on Rails,
here is an simple tutorial for an SQL based web application,

https://guides.rubyonrails.org/getting_started.html

If you understand the underlying MVC concept,
then you will quickly get into Rails,
it was designed for rapid web development,
and offers a lot of open source modules for things like user login etc.

--
Srdja

[odomobo]

What I currently have is a CGI 'server engine' that supports the following arguments on HTTP GET requests:

A couple things to note: you should never use HTTP GET for requests which update the state of the server. The way the HTTP protocol works is that GET requests are designed to be cachable anywhere between the server and the client, so the request isn't guaranteed to hit the server. In practice, it'll work until it doesn't... The easy solution is to use HTTP POST requests for any of these.

It's a bad idea to send username/password in the URL (i.e. as part of the query string). URLs are generally treated as non-secure, so the usernames and passwords will likely be saved as plaintext in places you wouldn't want (for example, in logs). The easiest solution IMO is to use http basic authentication. The username and password are stored essentially in plaintext (base64 encoded), but this is sent in the request header. It gets encrypted if you use HTTPS, so it's fairly secure. And, as a bonus, it's an established standard. Oh, I'd also recommend storing the PW hash on the server, instead of the PW.

The plan is to implement a game requests that suppresses all moves as long polling (not tested yet).

The WebSocket protocol was designed for this very purpose. However, I imagine it would be a big pain to implement without a library, and your solution sounds like it could work.

[hgm]

The current client looks like this:



If I would have 100 users in total (i.e. in the password file), it would already surprise me. They would not be all involved in live games simultaneously. They might all be involved in many correspondence games each simultaneously. But that just means they would each check perhaps once an hour if they have any games where they are on move (with the ?list=NAME request), and then play a move in some of those. A few hundred moves an hour hardly seems a challenge.

If the number of live users would become unacceptably high, my first thought would be to switch to a dedicated server similar to FICS, to which the clients connect through websockets which remain open during the game (or as long as he doesn't leave the web page in his browser). Apart from that it would use basically the same protocol, except that you would not have to accompany every request with a user/password once the TCP/IP channel is verified. (That would indeed save a lot of work on user verification.) This would require only minimal modification in the client, just the low-level connection method.

A couple things to note: you should never use HTTP GET for requests which update the state of the server. The way the HTTP protocol works is that GET requests are designed to be cachable anywhere between the server and the client, so the request isn't guaranteed to hit the server. In practice, it'll work until it doesn't...

I worked around that by having the low-level transmission routine append a unique &t=TIMESTAMP to each URL.

It's a bad idea to send username/password in the URL (i.e. as part of the query string).

Yeah, I was already a bit worried about that. But it is not like this is a bank. I already considered encrypting the password using the other arguments (and perhaps the number of moves in the associated game) as encryption key. Then the required password would be different for every request, so that simple copying would not help (as making a request that was already be given before is usually pointless; you can resign a given game only once, etc.). But of course people could get the encryption method from from analysing the client, and then they could decrypt the password. For now the trivial method seems to suffice; at this stage no one would be interested to make any effort towards identity theft. It is more intended as a safeguard so that you won't accidentally append moves to the wrong game. So my prime efforts should go into getting the polling for the live games to work, and making the client sufficiently easy to operate.

I will study the HTTPS method, to beef up security when the more urgent things are done.

[hgm]

Although it is true that there aren't any race conditions during game play, there still could be a problem when creating the games. E.g. several persons could try to satisfy the same game request simultaneously. Of course the execution of the 'attach' request tests if the mentioned game slot indeed contains a game request, and after execution that would be no longer true, so that later requests would fail. But if the testing and request->game conversion is not atomic, multiple processes could do the conversion. Which consists of overwriting the game slot to add the second player name, and set the game state to 'white to move'.

Now I understood that writing through a single write call is atomic, so what would happen in that case is that only the last write sticks. All others would effectively have failed, as they should have anyway, but the problem is that they won't know it. So they would return a success message telling the user he created a game. But when the user then tries to start playing it, he will get the error message that this in fact is another person's game. So it gives a reliability problem, with a small chance on the small annoyance to know that you were 'scooped' only one step later. For now I can live with that.

Another issue could be the allocation of an empty game slot for creating a game request. When these are simply appended to the gamelist file through atomic writes there never is a problem. But I do allow people to cancel game requests, by marking the slot 'empty' again. The allocation process then runs through the gamelist to find the first empty slot, and only appends at the end when there is none. This was probably a bad idea, as testing for emptiness and allocation by writing it will not be atomic. We then get the same syptoms if multiple users try to post a game request simultaneously: some may fail without knowing it. This is worse than with creating the game from a game request, because a game request is something you would not immediately visit again. So I should probably only allocate at the end of the gamelist file.

The life cycle of game requests

How much of a problem that is depends very much on the more hairy problem of how to handle other game requests by a user that gets one of his requests satisfied. On servers like FICS you can post multiple 'seeks', but they all disappear as soon as one provides you a game. Such a design would result in very many deleted seeks, and would thus waste a lot of space in the gamelist file if their slots are not reused. It also makes little sense for a turn-based server: typically you would want to start multiple correspondence games in parallel. OTOH, you would not want to start multiple blitz games in parallel. But on a server that supports many different game types, each with only slim chances to find an opponent, you would be much more likely to post a large number of game requests, in the hope that an opponent that at least wants to play one of those would drop by. It would be a bit annoying if you would have to repost all of those after doing a single game of blitz in one of them.

So the best treatment seems to be to always leave all game requests persist, except the one that was satisfied, or those the user explicitly removes. But then prevent those to be satisfied for as long as the player that posted them is tied up in a fast live game (say faster than 15 min). This could actually be left to the client: whenever it fetches a game list that would show the game requests of a given player, it would also show the games of that player (including clocks), so it can easily test if that player is currently tied up in 'urgent business', and suppress display of his game requests in that case.

Of course you would not want requests for live games to be satisfied when the player posting them is 'away from keyboard'. So perhaps there should be some mechanism for disabling them. So that they don't have to be removed when the player leaves, but can simply be re-enabled (instead of having to be reposted) when the player returns. IAfter all, it is very likely the player would be seeking the same games next time. To keep things simple a slot in the gamelist file could be used as a 'lock' on all game requests by that player. When the player returns he can then simply remove that lock. (That is, the client would automatically do that for him when he entered his name+password.) If such a lock is implemented as a request for a game of negative duration, it wouldn't even require any new HTTP requests to manipulate it. The Game Server could then interpret the absolute value of this 'duration' as the maximum TC of game requests that have to be disabled.

In any case, it seems that removal of game requests will be a reasonably common occurrence. But it always seems safe to reserve empty slots in the game list for reuse by just one single user. E.g. by the user that owned the game request that was removed there. This could never lead to race conditions, and would eventually lead to recycling of those empty slots as long as the user had not disappeared permanently: he would post new game requests in it, which sometimes would be satisfied, and turn into a game, which then lingers on forever. (Well, until you decide to do a big cleanup the server while it is down for preventive maintenance.)

[jdart]

>It's a bad idea to send username/password in the URL (i.e. as part of the query string).

On top of that, any hosted server that doesn't use HTTPS is insecure. But you can get a certificate for free via LetsEncrypt. You just need to install it and configure the site for HTTPS.

CGI is a very inefficient way to handle requests.

I don't know if you know Python? There are lot of Python web frameworks: the two main ones are Flask and Django. Both have a big ecosystem of add-ons for database access, authentication, and everything else a web app might need.

--Jon

[hgm]

Unfortunately I don't know Python either.

Why would CGI be inefficient? Is that because it needs execv() calls to invoke the CGI binary? That is what it seems to need extra compared to having the server process handle the request itself. At least, I suppose that the HTTP server would also fork off a worker for handling the request, be it a process or a thread.

But even if that in general would be the case, I doubt that it would be true here. Look at what the computer really has to do to service the request: it forks of a process, but because of the Linux 'copy on write' policy this inherits basically everything from the parent process, including the page tables. (Except that these will have to be set to read-only to catch later writes.) So it is not much more than creating a new entry in the process table, plus allocating perhaps a single page of stack memory to write the arguments for the execv() call.

Then it does execv(). This would have to load the image of the CGI binary. In my case that image is just 18 KB. But the code segment of that image would be shared between all instances of that program. And because of the long polling, there would always be an instance in memory already, as soon as there are two or more users waiting for opponent moves. (And below that point the load is less than 4 requests per minute, so that you can tolerate any degree of inefficiency.) So all that the execv() has to do is replace the pointer in the process table to the code memory from one existing page table to another one. And then allocate some zeroed memory for any data page the process starts writing in afterwards. Well, the CGI server doesn't use any large data structures, just a few stream buffers for stdin, stdout and at most two disk files, and a few text buffers of 20 or 100 bytes long. Allocating that should also be dirt cheap compared to actually reading the file that contains the requested data from disk (which would have to be done no matter what).