|
i know this problem has existed for quite a while and there have been a few discussions over it but i've been thinking more and more about it as i've studied code from darkstar, reddwarf, dimdwarf, app engine, and plenty of articles in regards to distributed game server architectures.
in general a server will handle game logic tasks / dispatch game logic events in a single-thread which implicitly locks state during each task. this effectively prevents you from parallelising such tasks because as mentioned before consistency issues become easily apparent if you consider two tasks handling attacking a player executing concurrently and modifying the same data. this is to prevent unintentional concurrency contentions, especially race conditions. two tasks that modify the same data provide internal inconsistency to the client. this is called pessimistic concurrency control.
as should also be very simple to realize, some tasks *can* be parallelized with no negative effects. example, a task that moves a player can easily be run concurrently with another task that moves another player (well, if you manage them in lists per tile then you'd hope that you aren't sharing tiles between players). there is no need for parallelism here because they do not share any data and therefore do not have any issues. you could try to run all tasks in parallel and hope for the best. in case of inconsistencies, one could check for concurrent modification before committing any changes to the shared game state (the domain objects that compose the server-side world model). obviously you incur penalties if an inconsistency is found, however it can perform much better than the pessimistic alternative. this is known as optimistic concurrency control.
the last choice is a hybrid of the two, executing most in a serial, single-thread ordered manner, while concurrently executing tasks which do not cause inconsistency issues in parallel. this is known as semi-optimistic concurrency control. a popular example suggested originally by blakeman8192 and subsequently implemented by several users here employs parallelism only in the case of preparing client update events. such tasks share nothing and therefore can be safely run in parallel, while running everything else in a serial single-threaded manner. usually one picks a type of concurrency control for every task when developing it. this may seem to be premature optimization at first although in some situations can provide the benefits of optimistic and pessimistic concurrency controls without their respective pitfalls.
the way to look at accessing the shared game domain objects is as being stored in an in-memory database shared among tasks. modifications are done via transactions which are atomic, consistent, isolated, and durable -- that is, they are ACID compliant. in a model where you have a cluster of machines handling game logic tasks, you can keep an object store (in darkstar/reddwarf it's backed by berkeley databases in high-availability mode that replicate on every node. dimdwarf however uses a custom in-memory shared-nothing object store (think distributed hash tables) which needs no redundant replication) and tasks manage transactions involving the game domain object database.
i realize this post is really long and not particularly organized however i hope i opened a door to community discussion on something useful.
I would only consider parallelism when it really matters. Executing small tasks in parallel may not be beneficial. So what's considered small? That's something I would decide at a later stage of the development cycle.
With semi-optimistic concurrency control, one thing you could do is have two types of tasks. One type that must be executed serially, and another type that can be executed in parallel, because inconsistencies cannot happen. This sounds more elegant than simply presuming which tasks need to be executed in parallel because they're heavy etc. This may not even perform better on whatever system you'll be running the server, which is what I meant previously.
from what i can gather from your post wouldn't it get messy if you are running multiple tasks using the hybrid version where as if you are using the paralleled version it would be running without any interruptions etc
i thought i brought that up in my post, but maybe i didn't afterall...
sub, the way i did this a while ago was with batches of tasks and their execution policy. the player updating group had a parallel policy, while tasks triggered by events decoded from packets had a serial policy. in a true semi-optimistic system you'd mark the tasks explicitly with their policy like this
I think that the best solution is to handle all modifications (whether it be by an event architecture, a ton of if/else if, etc.) in a single thread, with the exception of preparing client update packets.
Designing and implementing an architecture like you have suggested, where modifications are made as transactions and executed safely in a non-concurrent environment, but the modification transactions are themselves prepared in a concurrent environment, simply runs into the problem of too much work to accomplish small tasks. The benefit of parallelism is huge, but the overhead of creating a transaction system would be nothing short of ridiculous. I have always been a big fan of keeping things simple.
Preparing client updates, however, is a different playing field. The simple fact of the matter is that it performs zero or almost zero (depending on the local player list implementation) so a simple and minimal locking system can be implemented. Through testing I have discovered that the client updating packets (player and NPC) account for a vast majority of processing time - when using RuneSource as a test subject I found that updating 2,000 clients took 120ms on a single threaded system, and only 30ms on a parallel system (running on a quad-core CPU which improved speed by four times).
Robustness and stability are huge factors in the design of any server system. The complexity of a parallel modification environment is just asking for a crash unless it has been meticulously designed, tested, and debugged by the creator. In a single threaded system, you don't have any worries, you don't have any concurrent modification checking, and it's much easier to design game content without the worry of race conditions and other crazy consequences of faulty concurrent systems. A single thread guarantees decent stability (as long as proper exception handling exists) and does not have any operational overhead.
Again, I believe that the best solution is to keep all of the modifications in a single thread and not have the overhead of concurrent modification checking systems and other preventative measures. If you are implementing a system where the code to keep it safe takes as long or longer to run as the difference between that system and another system, just stick with the other (aka single threaded) system for sake of simplicity and stability.
with a distributed architecture in order for horizontal scalability you *need* to have at the very least a semi-optimistic concurrency control system as locking across multiple machines is expensive and stupid
If you look into the RS scalability, you'd notice that they mainly run a single server with a limited capacity of 2000 players on a single machine. RS runs multiple machines with multiple servers, if RS scaled horizontally, they scale in number of worlds to keep the capacity of players. In that specific case, locking systems across multiple machines isn't needed, as each of the worlds (game servers) run indevidually. Considering this and keeping this in mind, I agree blakeman8192 to keep it simple with single threading rather then creating complexibility without reason or purpose.
[edit]
I do like to point out that I'm mainly speaking on servers or code of 317 and not about 660 which is much newer and where probabliy both paralel and serial threading should be used to fully use the capacity and capeability of Java and get the best performing server.
who said i would be horizontally scaling with multiple distinct worlds? the whole point is to have one consistent world which can improve in performance not only through vertical scaling (more DIMMs, faster memory bus, smaller transistors, more core dies, larger caches, co-processors, etc) but also horizontal (adding more computers). this can be much more practical of a solution. if you need an example of why one would need this, think of a game world in runescape e.g. world 2. there are plenty of places in world 2 that had distinct "hot spots" where players accumulated in large numbers... would you like to be handling these both in the same thread where you could execute most of the load in parallel by splitting among two machines (well you'd need a trick or 2 when dealing with edges and interactions out of local server authority)
Blake, keeping everything on one thread utterly rapes the potential performance level.. With 6 core processors at $200, the availability of extreme hardware at a low cost makes it insane to only take advantage of 1/6 of the processor's theoretical potential.
« Previous Thread | Next Thread » |
Thread Information |
Users Browsing this ThreadThere are currently 1 users browsing this thread. (0 members and 1 guests) |