Distributed server architecture for load balancing

Started by
50 comments, last by _winterdyne_ 18 years, 6 months ago
Quote:
When the ship lurches, you want the player to lurch, too, not just stay rock solid on the ship's deck. In fact, gravity doesn't change when the ship moves, but the ship changes. If you run an actual physical simulation, it would be simpler to simply change the ship, keeping everything in world coordinates, because the physical simulation will take care of everything. ("having to update all the objects" is not a problem -- because they are simulated, they are updated every frame anyway)


I see what you're saying here, but this doesn't really affect the relevance graph, unless you consider falling from one POR to another. It does affect the physics layer for player position checking and may alter pathfinding hierarchies.

The effect you're describing could be achieved by using a matrix stack to concatenate transformations as the hierarchy is traversed, effectively giving each POR a transformation specific to its orientation and position.

Rather than simply having position, a POR has a matrix (or quat/vector) to dictate where it is. In most cases there won't be any rotation, just translation, since blocks are easier to work with in design terms.

The most complex objects, in terms of physics abstraction (collision hull), at any time on the server are likely to be static POR geometry sets. Other items are likely to be simple boxes, particles, spheres, cylinders, or self-righting cylinder entities such as creatures. I don't intend to implement rag-doll physics on the server, nor do I intend to model 'long footprint' entities (think a horse from above). All of these are transformed by the matrix stack.

In order to lurch (or indeed rotate relative to gravity), we do actually need to inverse-transform the inherited gravity vector which will dirty the physical abstractions for the POR. New accelerations can be calculated for them and they can then update as normal. Route paths for certain movement types will have to be recalculated based on the altered gravity vector (a floor may become a wall) so angular tolerances for paths on the route finding node map must be checked.
Since self-righters will have to self-right, a player associated with the simulation entity can receive a 'I have self righted by [optional quaternion]' message to make their avatar 'stagger', in full on Star Trek styley. The quaternion can be used to determine direction of stagger. Immediately following may be an 'I am falling' message.

Any POR can specify a new gravity vector - although this is intended for spaceships with no global gravity vector - allowing us to model artificial gravity environments but NOT centripetal force environments.
Winterdyne Solutions Ltd is recruiting - this thread for details!
Advertisement
Quote:
Also are there any additional complexities for an event that dont just have a simple origin and spherical effect (shout) but have more directional interactions (ie- an arrow fired) that may need to do a collision check/ LOS (line of site) and/or non-instantaneous (a traveling arrow) that itself moves over time and ack! may have secondary effects (like being visible/viewed by other obects as it moves...).


For a typical MMOG, I'd probably not model items such as arrow shots as explicit entities. An arrow shot would be calculated to either miss or hit, and the visible representation of it would be handled on the client. A standard spherical event would be used to notify of the shot, or the entry of the shot to a POR.

The mobile POR is designed to segregate a chunk of hierarchy - ideally within itself. Typically, the mobile POR would be 'teleported' into, rather than entered through a neighbour relation. It's not really designed for its contents to be interacted with.

Assuming you have a ship, with a deck, and belowdecks section, with several PORs. The deck, and entry to belowdecks (potentially visible) I'd model as a standard mobile limpet, with a complex collision hull. Mobiles on deck are linked to the limpet, characters below decks are not, they are tied to a mobile POR, since they are 'separated' from the world at large.
Linking the mobile POR to the limpet for the ship as well gives us a single point of control; Rotating the limpet (according to the normal of the bit of sea its on) rotates the mobile POR (but not its physical abstractions which are separate, but do get a modified gravity vector etc. as described).
Anything linked to the limpet inherits its transformation when updated, so any physical abstractions may get dirtied.

This allows the ship itself to be interacted with, as well as people on decks, as standard occupants of the fixed POR the ship is in, whilst keeping local interactions below decks separate from the world at large (keeping network updates down).

Winterdyne Solutions Ltd is recruiting - this thread for details!
Quote:Unfortunately you will have to decide where you want the 'realism' to stop (in order to make a game that doesnt require a supercomputer to run in real time). Sure you could have the player lurch about (and check all the friction effects that keep objects in place most of the time) but what of the entire structure of the ship/boat. Do you want to have to calculate all those structures effects by every force upon them to calculate all the transformations for positions (culling methods would help this some). Its probably more cost effective to apply the various 'lurch' forces to the player and other 'moveables' within a local coordinate system to minimize the CPU load.



OK, I respectfully disagree. My daytime job includes a distributed simulation system that simulates all physical entities in global space, and it works very well. We've solved all the problems the OP talks about (although differently from his suggestion), and we've been operating since 2001. The servers, and clients, are regular x86 PC hardware, not supercomputers.
enum Bool { True, False, FileNotFound };
Bear in mind that I'm aiming for very small clusters with this library - it's intended use is for low-budget / indie projects, so a large cluster performing complex simulation of a large number of entities is out of the window.

Instead, since there may be large numbers of small items lying around, simplified physics have to be used serverside(particles for objects). Performing true physics on such items seems like a lot of work for a tiny cluster, which is preoccupied with game event handling.
Winterdyne Solutions Ltd is recruiting - this thread for details!
Quote:Original post by hplus0603
Quote:Unfortunately you will have to decide where you want the 'realism' to stop (in order to make a game that doesnt require a supercomputer to run in real time). Sure you could have the player lurch about (and check all the friction effects that keep objects in place most of the time) but what of the entire structure of the ship/boat. Do you want to have to calculate all those structures effects by every force upon them to calculate all the transformations for positions (culling methods would help this some). Its probably more cost effective to apply the various 'lurch' forces to the player and other 'moveables' within a local coordinate system to minimize the CPU load.



OK, I respectfully disagree. My daytime job includes a distributed simulation system that simulates all physical entities in global space, and it works very well. We've solved all the problems the OP talks about (although differently from his suggestion), and we've been operating since 2001. The servers, and clients, are regular x86 PC hardware, not supercomputers.




Frame rate (or simulation cycles per second) ??
Total Object count??
Average number of objects in an overlapping vicinity??
Average events per object per cycle??
Seamless boundries??
Complex terrain (mobile vehicles where other object navigate in)??


Some game have a much higher simulation complexity than others.

Im considering scaleability since game worlds are getting bigger and more complex AND have situations where large numbers of very active players congregate in a small area (ie- like a battle or the 'bank').


We don't have all of the data public, but yes, it's a continuous world that scales up by the amount of hardware you plug into the cluster; the actual mapping from world to hardware is heterogenous (not just same-sized squares). We step everything at 30 Hz (client and server), and the number of messages per object is "whatever interactions actually happen" (it's not really a limitation in the system). The limits to scalability are mainly related to how dense you want the congregations of simulated objects to be, and how complex they are, as well as what the CPU memory speed is.

You can check out the web site at http://www.forterrainc.com/ and you can also try the older version of the platform via the free trial download of http://www.there.com/ . Other things we do include simulation of an entire round planet, the size of Earth; a very believable model of human emotions; a fully working virtual economy driven by player-created content; and integrated voice chat that routes through the server (all interactions are server authenticated). There.com runs on pretty old server hardware; it has some "city plaza" type locations with hundreds of avatars and more hundreds of other simulated objects (user-customizable buildings, trees, etc).

And, yes, some players have taped down the "forward" button and driven vehicles around the entire world. It takes them about three weeks ;-)
enum Bool { True, False, FileNotFound };
Nice product!

Somewhat larger scale than I'm aiming, but similar goals.

I'm interested in what happens with large, active congregations in your system.
I assume your quadtree is stored on a centralised for the operating grid so node relations can be queried centrally, and I assume you're tracking stats for each node on that server as well. I assume that each node knows where the master server is (probably its own machine in the grid). I also assume that you can isolate a quadtree node that's causing lag, and I assume each process is aware of at least a portion of the quadtree to allow direct inter-process communication (given that you've mentioned a smart switch for the grid).

When a particular node in your quadtree is known to be causing lag, what do you do with it? You've mentioned that each node has its own process - are you moving processes to machines with less lag using beowulf as you mentioned earlier? Are you subdividing the node (similarly to the mechanism I have planned) and distributing the subnodes? As you mentioned, this doesn't cause problems with non-seamless worlds, but your reference to continuous implies its seamless, so taking a process out of the loop whilst shifting it in its entirity is going to cause synchronisation issues, made worse by the amount of active content in the node.

Hehe, here comes the 'I could tell you, but I'd have to kill you' post. ;-)
Winterdyne Solutions Ltd is recruiting - this thread for details!
I could tell you how it all works, but first you'd have to sign a bunch of legal papers :-)

Quote:node relations can be queried centrally


The only thing we really need central querying for in the entire system is the relation "given this object ID, what is the home storage server for that object". Everything else is distributed, and scales by adding more discrete hardware, in one way or another.

We don't use Beowulf, but instead built our own application-layer clustering infrastructure.

Simulating objects will never make a remote query within the time of a single step -- doing that would kill performance. In fact, we could probably tolerate having a distributed data center (different servers in different centers), although that's not something we're officially supporting nor currently working to support.

We run one server process per machine. Running multiple processes has no advantage, because the area served by our processes can be irregular in shape (and even discontiguous, although that's usually not a great idea for other reasons). If we need to shift load, we change the area that each machine is responsible for, rather than moving the processes. Each simulating object knows how to move itself to the "most optimal" server for that object, so when we change around mappings, the appropriate objects will automatically migrate. Usually the players won't notice when their objects migrate (because of the "seamless streaming world" implementation, which already involves real-time migration).
enum Bool { True, False, FileNotFound };
Quote:Original post by hplus0603
I could tell you how it all works, but first you'd have to sign a bunch of legal papers :-)


Isn't that always the way? :-)

Quote:
We run one server process per machine. Running multiple processes has no advantage, because the area served by our processes can be irregular in shape (and even discontiguous, although that's usually not a great idea for other reasons). If we need to shift load, we change the area that each machine is responsible for, rather than moving the processes. Each simulating object knows how to move itself to the "most optimal" server for that object, so when we change around mappings, the appropriate objects will automatically migrate. Usually the players won't notice when their objects migrate (because of the "seamless streaming world" implementation, which already involves real-time migration).


So, given a change in area on a particular machine/process that change has to be migrated to all processes in the grid? You've stated you use a modified quadtree, I take it this is used to determine which is the most optimal server, given an objects extents and the known areas covered by each process in the grid. Elegant, given a fixed origin coordinate system. I also assume you are generally dealing with a 2D world (as far as zones are concerned).

Couple of questions, I was reading up on DungeonSiege's continuous world design and they ran across floating point precision errors at large distances. In short they overcame this by using an alterable point of reference. Are you using sliding scales for determining quadtree nodes (a 10km tree vs a 1m tree)?

Also, given an irregular shape, how do you determine continuity? Colinear edges on area perimeters? It's one of the reasons my fixed POR's have AABBs rather than arbitrary - I considered the design difficulties of placing continuous arbitrary hulls nightmarish, not to mention the fact I always hated Tetris, especially in 3d, whereas most people can easily figure out how to put together axis aligned box.



Winterdyne Solutions Ltd is recruiting - this thread for details!
Quote:Original post by hplus0603
I could tell you how it all works, but first you'd have to sign a bunch of legal papers :-)

Quote:node relations can be queried centrally


The only thing we really need central querying for in the entire system is the relation "given this object ID, what is the home storage server for that object". Everything else is distributed, and scales by adding more discrete hardware, in one way or another.

We don't use Beowulf, but instead built our own application-layer clustering infrastructure.

Simulating objects will never make a remote query within the time of a single step -- doing that would kill performance. In fact, we could probably tolerate having a distributed data center (different servers in different centers), although that's not something we're officially supporting nor currently working to support.

We run one server process per machine. Running multiple processes has no advantage, because the area served by our processes can be irregular in shape (and even discontiguous, although that's usually not a great idea for other reasons). If we need to shift load, we change the area that each machine is responsible for, rather than moving the processes. Each simulating object knows how to move itself to the "most optimal" server for that object, so when we change around mappings, the appropriate objects will automatically migrate. Usually the players won't notice when their objects migrate (because of the "seamless streaming world" implementation, which already involves real-time migration).





It must be pretty messy shifting boundries (to do load leveling) with irregular/discontinuous areas. How long does a transition usually take when an entire area has to be locked down so that the new boundries can be send to the adjacent areas (a new area created...) and any objects reassigned to that new area?? I suppose some work could be done ahead of time to build up the data for a new area (adjacent areas prompted for the change..) before the actual transition.

At what degradation of the 30hz cycling target is a overly busy area split up ??
The heuristics for controling this automaticly must be nasty.

It always happens that whatever the worst case scenarios are, the players will wind up doing it. I would think that small busy areas would not really be fixable by this method because interzone events would still have to be transmitted to the adjacent areas (unless event filtering greatly lowers the number sent between areas or you still have the N^2 problem...).

[Of course its possible that you might have simulations with a very high load from NPC AI activation/reactive scenery and other secondary processing near players that requires farming out to more machines and would greatly outweigh the inter-machine event transfer overhead.]

I assume there is also an area anealing done as well....


This topic is closed to new replies.

Advertisement