One topic that I've found to be interesting is the architecture of online games. Games that run on a single server are pretty straightforward and easy to understand. What I find interesting are the different methods of hosting one game on multiple servers.

In thinking about online games, I decided to abstract a game as a database - that is a collection of data that can be read or written by clients. In the case of a realtime game, the clients are notified right away when data is modified. The big problem with a multi-server game is that the data is split between servers. This produces several issues that have to be taken care of:

1) Data on one server interacting with data on another server. Example: Water begins flowing in a dry riverbed, and must flow on to the other server's area.
2) Client must receive updates of data on two servers. Example: Client avatar is at the "edge" and can see objects on two servers.
3) Client must update data on two servers. Example: Client avatar triggers "wireless" device that is located on other server.

I have thought of several types of architectures that can provide these three facilities. Each type of architecture has its own advantages and disadvantages that make it suitable for certain situations.

* Database mirroring
Database mirroring requires two or more servers. Each server stores a complete copy of the game world (the database). Updates must be sent to each server, consuming a lot of bandwidth. There is also delay as the updates are transferred between servers. Some examples of database mirroring are: IRC, Age of Empires, Descent, Descent II, Doom.

One problem for mirrored databases are collisions and race conditions.

* Collisions
Collisions occur when one object is updated simultaneously on two servers. The game architecture must handle this situation and decide which update to keep and which to deny. If the updates were generated by clients, then the client whose update was rejected must be informed so it can keep its "view" of the database up-to-date. One example of a collision is in Descent when you fire a mega-missile and then are instantly destroyed by an opponent. The mega missile vanishes in flight because your death was calculated by your opponent's computer as happening before your computer calculated the launch of the mega missile. Obviously, collisions are a real problem. But there is a more subtle problem that is even more important to solve.

* Atomic operations
An atomic operation is an operation that occurs instantaneously in the database. For example, the turning on of a light could be an atomic operation. At the same instant the light switch is flipped, the light is on. Atomic operations are important because they maintain the integrity of the data. Imagine a non-atomic light-switch operation that is interfered with by another player: The first player flips the light switch. At the same instant, a second player breaks the light bulb. Then the light bulb comes on. Obviously a broken light bulb should not come on, so the game database design must prevent this. Operations like this must be made atomic and must occur instantaneously on the data. If the update occurs instantaneously, then all of the objects being updated must exist on one server. This introduces the idea of authority: which server has authority to perform updates on which data?

* Update Authority
The simplest architecture would have a single server that has authority over the entire database. This "master" server would receive all update requests, process them, and then send the updates to all of the other servers. This design requires the "master" server to have a lot of bandwidth. There is also a time delay for relaying the update requests and updates between the servers. In order to distribute the bandwidth load, the database could be divided into regions. Each region would be assigned to a different server. This allows the client to get the best "ping times" by connecting to the server that is authoritative for the region of the database that the client is interacting with. Ideally, the client program would perform such a connection silently and automatically. The user playing the game would not realize that they had walked across an invisible boundary line and had switched servers.

More topics to discuss:
Edge Mirroring (servers mirror data at their borders)
Simultaneous Connections (client must connect to other servers when near borders in order to "see" what happens on the other side of the boundary)
Zone systems: Quad-trees for 2D space, Oct-trees for 3D space
Dynamic zone systems that reform to optimize server load distribution

* Edge Mirroring

In this architecture, the game's space is divided into regions, each assigned to a different server. Each server holds the data for its region and a portion of each adjacent region. This allows the client avatar to be located at the edge of a region and still see what goes on across the border. When the avatar nears the border, the client program would then connect to the neighboring server and prepare to cross over to it. As soon as the avatar steps over the border, the client would begin sending updates to the new server. The connection to the previous server would be kept open in case the avatar turns around again.

The edge mirroring architecture reduces the amount of data that must be relayed between servers. Only updates for the edges of the region must be relayed to the "neighboring" servers.

The size of the database stored on each server would also be minimized. Only the specific region and the small bordering areas would be held in memory.

* Simultaneous Connections

Consider a game world that is divided into regions. Each region is assigned to a specific server. The only communication required between servers is for the interaction of game objects on the borders between the servers. Clients nearing the border would have to connect to the neighboring server in order to receive updates to the bordering region. Client crossovers would occur as in the edge mirroring architecture.

* Zone Systems

Games can use a system that divides space into equal regions. A one dimensional interval may be divided in half. Each of those halves may be divided in half. And so on... What we get is a tree representing each interval - a binary tree.

For two dimensional space, we deal with squares. A square may be divided into four equal subsquares, and so on... yielding a quad tree. Square A is divided into four squares: B, C, D, and E. The tree of this space has A at the root, and four child nodes: B, C, D, and E.

In three dimensional space, a cube may be divided into eight sub-cubes. This yields an oct-tree.

Trees are very useful in computer programming. Consider a map with a thousand objects evenly distributed over region A. For my program to find the object that is nearest to some point P, it would have to compute the distance from P to all 1000 objects. By utilizing trees, the program can save a lot of work. Instead of having all the objects exist in region A, A is divided into sub-regions B, C, D, and E. Thus the program can determine which sub-region P is in, and then check the 250 objects that are in that sub-region. If the program were to further divide the sub-regions, even more computation might be saved.

A multi-server game might use quad or oct trees to represent the space of the game world. Each server could be assigned a certain region.

* Dynamic Zones

Consider a game with many servers and many clients. The game world may be divided evently, but the game's objects may be not. One region might be very popular and could have an enormous number of objects and clients. Too many clients and the game slows down for everyone.

One solution to the problem of unequal client distribution is to change the division of the game world so that each region has a similar number of clients. A game could periodically check the number of clients in each region, and then come up with new region boundaries. The changeover to the new regions would require that each server allocate memory for the new region, retreive the game data for that region from all of the servers that currently hold it. The server would have to keep getting updates for the regions until it is ready for the switch. Clients would need to connect to their new region servers ahead of time.

Such a dynamic zone system would require that each server have about twice as much memory as is required for normal operation. Each server would also need enough network bandwidth to prepare the new region and keep it updated while still servicing its clients.

By thinking about games as databases, we can design advanced game architectures. Mirroring, Edge Mirroring, and Simultaneous Connections are methods of distributing game data between servers and clients. Proper database authority must be implemented to prevent collisions and to provide atomic operations that prevent race condiditions. Zone systems are a logical method of dividing game space into regions. Dynamic zone systems can reconfigure the game space so as to equally distribute load amongst the available servers.

Yikes... I just brain-dumped most of my ideas about this topic. Does anyone else have ideas about game architectures or any related topic? Have any of you tried to make a multiplayer game before? What kind of architecture did you use?

I doubt ne one reads all this... :^( ...prolly the serious game proggers...

Well now :)

Just a few thoughts - most of them aren't tested or so, but it's a interesting topic, and deserves some thinking :)

** Dynamic Zones: I tried to create a dynamic scene graph (only for managing geometry and simplifying collision detection, so no networking here). Anyway, there are some problems I ran into...
The idea was to use simple geometric shapes (spheres or axis aligned boxes) to sudivide the scene into a tree. If too many objects entered a volume, it would be subdivided and the objects would be placed in its new children...
The main problem was to find the appropriate volumes without any big overlappings. The fact that the objects move didn't make the task much easier =)
I started to run into complicated cluster analysis algorithms pretty fast, at which point I decided to try something simpler.

** Oc- / Quadtrees: Pretty easy to implement; something one could look into is "loose oc- / quadtrees" (there's a article in the GameProgrammingGems book on that). In a loose *tree the nodes overlap slightly - this overlapped area could be used as the edge region which is mirrored on both servers (and used for object transitions etc).

** Authority: (just a crazy idea I had right now) What about implementing the server system as a tree? The topmost node is a single sever which handles global events (= events affecting multiple zones). Only other "lesser" servers can communicate with this root-server. The lesser servers take care of zones and whatever you need (and communicate with clients).

Hmm, what about trying to build a small sample system? If we could get a few active volunteers, we could put together a simply system "demonstrating" this kind of stuff...
(The most difficult part is probably the getting-a-few-active-volunteers thing :/ )

CViper,

I can see how your dynamic scene graph algorithms would get complicated. The beauty of quad-trees is that they're simple and easy to code. Unfortunately they don't lead to the most efficient trees. But the nice thing about having uniform square regions is that it's very simple to move objects between zones. So the decreased efficiency of searching the tree can be offset by the increased efficiency of moving objects from one node to another when they cross a boundary line.

The loose tree technique is intriguing. Would an object existing in the overlapping region be linked to both region's tree node? If that's the case then an object could conceivably be linked to four regions if it was at the corner of a region. Hmm... I can see how overlapping regions could help solve a problem in collision detection where you must test for collision near the edge of a region. Without overlapping regions, you would need to test all of the objects in the adjacent regions. But as long as your overlap depth is bigger than the maximum collision distance of any two objects in your game, then the loose quad tree could really save a lot of computation. Cool!

Let's design a game protocol and architecture right here in this forum. Then we can write reference implementations for it. It would be easier to make a simple architecture first, and then move on to a more complicated one. Let's design a mirrored database with one master, but keep in mind the other architectures when designing the details. What do you think?

Sure, sounds like a good idea.
Proper design and planning is the most important part (as I recently found out the hard way), and who knows, if we start designing the stuff here in the forums, someone else might come along and give some input =)

About the loose trees: the article in GPG only used them for culling, and thus only stored each entity in a single node. Obviously for collision detection it's easier to place the entity in all nodes it is resident.

Here are some ideas to get started:

Let's start simple... The game will be tile-structured and realtime. The map is divided into uniform squares. Each avatar is drawn as a circle with their nickname inside. We can add graphical avatars, scenery, and NPCs later.

Master server starts first:
* initializes the game database
* opens a port for clients
* opens a port for servers
* starts the game clock

Subordinate server starts:
* connects to master server port
* requests a database "window" that encompasses the entire db
* receives snapshot of database
* begins receiving updates from server
* opens a port for clients
* enters update/relay loop

Client starts:
* connects to server
* sends nickname
* informs server of its preferred database "window"
* begins receiving updates from the server
* begins monitoring user interface

If we go with this general order of operations, then we need to define these protocol elements:
* server greeting
* client greeting (includes nickname)
* database window message
* database update message
* quit message

Maybe we could have the database be real simple-like... Each object has a number and several data fields. Objects of different type can have different numbers of fields, and the fields can store different kinds of data. Data types are: INTEGER, STRING
Integers are always unsigned and are represented in decimal like this: 12345
Strings are always enclosed by quotes, like this:
"I like vanilla"
The double quote character, ", is illegal inside strings. Client programs should translate the double quote into the single quote. The newline character is also illegal inside strings. Maybe later we can add escape codes for the quote and newline characters.

I suggest we use a basic ASCII line based protocol.
greeting: PROTOCOLNAME1 SERVER "Game name"\n
client greeting: PROTOCOLNAME1 CLIENT "Nick Name"\n
database window: WINDOW left top right bottom\n
example window with corners (0, 10) and (20, 15) is:
WINDOW 0 10 20 15\n
database update: UPDATE recordNum DATA,DATA,DATA,...\n
If a field is empty then that field is not updated. Example: Object 12 is an avatar record with the form: "Nick Name",XPOS,YPOS. This update message will change the x-position but leave the nickname and y-position unchanged:
UPDATE 12 ,103,\n
If no fields are present, then the record is discarded:
UPDATE 12\n
Later on we can add messages for creating and destroying objects. Right now let's just have all the objects be avatars.

quit message: QUIT\n

I think we should define a limit on the size of any message. 16384 bytes should be safe. This limit includes the final newline character.

Let's also define a generic error message that we can use for debugging:
ERROR "Error description"\n

What do you think? I wrote this in a hurry so there are probably some inconsistencies with it...

For developing a ASCII based protocol might be good (it's easy to debug), but later one would need something faster =)

A small problem I see, is if one wants to update the y-position only; as I see it, that's currently impossible (except by resending the original x-position)
[EDIT:] Nevermind, I just saw that little comma there [/EDIT]

One question, why would a suboridinate server need the whole database? Isn't that something one should try to avoid (save memory, bandwith etc)? It would be enough if the server is aware of its "nearest surroundings", i.e. any transition areas.

(Early in the morning here, I'll give it some though under the day...)

You're reinventing the wheel when you start to worry about the implementation details of network communications. I don't know of any good solution, which is why I wrote http://taubz.for.net/jnc a year ago.

- taubz

Reinventing the wheel is usually a good way to learn something... Anyway, I do not know of any useful general purpose protocols - at some point your application will define the way data is exchanged, and thus use a protocol of its own.

Some thoughts to the protocol above, I think we might as well force a certain mesage structure; when moving to binary packets it becomes easier to operate on well-known structures.

Also, the client should not be required to send its ID when updating itself - the server can easily distinguish clients by their connection (which is safer, because it's hard to fake the connection ID, whereas sending a false record ID is easy).

One should also try to avoid having all clients connected to the main server (with the global database); the lesser servers should notify the main server of important events (transactions, zoning, logout, ...)
Logins would probably still need to go through the main server.

Main Server:
* initializion
* listen for incoming sub-server connections
* listen for incoming clients (and relay to correct sub-server)
* keep track of global events (client changing zone, logout...)

Sub Server:
* connect to main server
* request local database and sync clock
* listen for incoming clients
* handle local clients; notify main server of global events (client zoning, logout/errors)
* if necessary, move client to new sub server

Client:
* connect to main server and login/recive global data ( sync clock etc)
* move to correct sub server
* loop (user interaction, ...)

I'll try to draw up some primitive protocol on paper and post it when I feel that it could work.

Oops, I forgot to say that the above proposal is for a database mirroring architecture. I'm sure I originally had that, but in the process of revising the post, I must have deleted that sentence. Anyway, I think that a mirrored database system would be the simplest. If we don't want clients connecting to the master server, then we can just have it not listen for incoming clients.

Also, maybe we should start out with a simple one-zone system?

I agree that if we want to implement a binary protocol that we should make a rigid message structure. But text based protocols are so much easier to deal with. And although they send "unneeded" information like spaces and extra words, they can be compressed pretty easily. Let's go with the non-rigid text protocol for now and then worry about bandwidth efficiency later.

I think it is neccessary for the client to send the record number with its update command. For this version of the game, we have only one object (the client avatar). But later on, the client will need create other records and then update them. Consider the action of dropping an item - the client would need to create the item in the game world. Checking the client commands will be handled by the authoritative server. We can design the database to have object handlers and table handlers that are able to check updates and perform other automatic stuff. I'm imagining a real database system for the game. Anyway that is all down the road and I'm sure we will learn lots of things that will make everything we've come up with so far to be obsolete.

Should we really add another message just so the master server can relay the client to a subordinate server? I had imagined two situations where the mirrored database would be used:

1) Protected master server - master server sits behind a hefty firewall. Only subordinate servers are allowed to communicate with it (maybe even through a multiple proxies). This protects the master server from DOS attacks and direct infiltration.

2) Dynamic master server - All servers link together and have an election to decide who is master. If master fails then remaining servers automatically hold another election. This prevents game delays of more than 2 minutes (1 min for the TCP connections to fail and 1 min for the election).

As far as logins are concerned... eventually we could have a system like this: Client connects to the server and receives a 32-bit random number in the greeting. The server stores this number in the database as a ClientConnection object, along with the other information like the IP address, reverse dns, etc. The client can use the 32-bit number to create an authentication response that is included in the message it sends to create the player's avatar. Because all messages will be handled by specific functions, the authentication code will be checked before the avatar object is created.

We could implement the game on the Postgres database by using its native function capability. I think a real game would need a custom database engine that is optimized for the game as well as the game's protocol. Database design is a really big topic, and I haven't researched it very much. I do want to investigate it in the future though (through a project like this).

Doh! I should be doing my Japanese homework right now!

I'll read all of this when it comes out in paperback, since you probably addressed this problem already but...

For the multiple servers handeling different zones of the grand map and the conflict of the borders, maybe there would be some simple communication and buffering between the neighbouring servers, i.e.:

Server 1: The antelope is running off of my side at B,5
Server 2: Fine then, I'll place it on myself at B,0
Server 1: There is a green kangeroo standing on my B,5
Server 2: Alright, I'll put in in my border-buffer
Server 1: Fine then! Be that way! Be a bossy alliteration making know-it-all!
Client 1: Erm, Server 2, I'm at B,0 and I can't see infont of me.
Server 2: Oh, you see I've buffered that area, and once your completely inside it and you can't see any of me any more I'll sneakily switch you to server 1
Server 1: werd.

I thought of an alternate "login procedure":
Once the client is registered (logged in) on the main server, the main server stores the IP address and whatever data is needed.
Now, when a client attempts to connect to a sub-server, the sub-server queries the main server using the IP address of the client. If the IP address is registered, the client is logged in and valid, if not .. well...
It's pretty hard to fake a IP address in a two-way communication, so it should be pretty secure. Obviously if the connection to the client is lost/the client is logging out, the IP address should be unregistered.

(I'm still "working" on this stuff, but school is getting a bit busy right now - <3 more weeks school until I'm through that stuff forever [university is the next stop then])

What happens if you're dialed up on a modem, get disconnected, and then someone else dials up to your ISP and gets your old IP address? They would be able to connect to any sub-server and hijack your avatar.

For the now, let's not have any login at all. But later on, we'll definately need an authentication process for each connection. I'd like to eventually use robust cryptography and cryptographic identities to secure communications, avatars, and objects.

This is the middle of the quarter at my school, so everyone has mid-term exams this week. I had an exam yesterday and three today. Actually one is tonight - in 2 hours... and I'm going to resume studying for it right now.