Thread: exploiting parallelism in handling game server simulation logic

Page 1 of 5 123 ... LastLast
Results 1 to 10 of 42
  1. #1 exploiting parallelism in handling game server simulation logic 
    Renown Programmer
    veer's Avatar
    Join Date
    Nov 2007
    Posts
    3,746
    Thanks given
    354
    Thanks received
    1,370
    Rep Power
    3032
    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.
    Reply With Quote  
     


  2. #2  
    Community Veteran


    Join Date
    Jan 2008
    Posts
    2,659
    Thanks given
    494
    Thanks received
    627
    Rep Power
    980
    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.
    ~iKilem
    Reply With Quote  
     

  3. #3  
    sυввч

    Sub's Avatar
    Join Date
    Aug 2007
    Age
    24
    Posts
    4,352
    Thanks given
    1,205
    Thanks received
    359
    Rep Power
    2845
    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
    Reply With Quote  
     

  4. #4  
    Community Veteran


    Join Date
    Jan 2008
    Posts
    2,659
    Thanks given
    494
    Thanks received
    627
    Rep Power
    980
    Quote Originally Posted by Sub View Post
    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
    You have it the other way around I think. Only certain tasks that can be executed without the chance of concurrent modification would be executed in parallel in the hybrid version. With the "optimistic" version, you would have a problem if concurrent modification occured.
    ~iKilem
    Reply With Quote  
     

  5. #5  
    Renown Programmer
    veer's Avatar
    Join Date
    Nov 2007
    Posts
    3,746
    Thanks given
    354
    Thanks received
    1,370
    Rep Power
    3032
    Quote Originally Posted by iKilem View Post
    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.
    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
    Reply With Quote  
     

  6. Thankful users:


  7. #6  
    brb ridin da storm

    blakeman8192's Avatar
    Join Date
    Dec 2012
    Age
    31
    Posts
    2,012
    Thanks given
    818
    Thanks received
    1,361
    Rep Power
    329
    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.
    rest in peace Qemist, Izzy, Colton, TeChNo PuNk, Impulser, & bootnecklad
    Reply With Quote  
     

  8. #7  
    Renown Programmer
    veer's Avatar
    Join Date
    Nov 2007
    Posts
    3,746
    Thanks given
    354
    Thanks received
    1,370
    Rep Power
    3032
    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
    Reply With Quote  
     

  9. Thankful users:


  10. #8  
    Banned

    Join Date
    Apr 2008
    Age
    34
    Posts
    206
    Thanks given
    0
    Thanks received
    3
    Rep Power
    0
    Quote Originally Posted by super_ View Post
    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.
    Reply With Quote  
     

  11. Thankful user:


  12. #9  
    Renown Programmer
    veer's Avatar
    Join Date
    Nov 2007
    Posts
    3,746
    Thanks given
    354
    Thanks received
    1,370
    Rep Power
    3032
    Quote Originally Posted by WhiteFang View Post
    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)
    Reply With Quote  
     

  13. Thankful users:


  14. #10  
    Registered Member
    Mister Maggot's Avatar
    Join Date
    Dec 2008
    Posts
    7,227
    Thanks given
    3,283
    Thanks received
    2,875
    Rep Power
    5000
    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.
    Reply With Quote  
     

  15. Thankful user:


Page 1 of 5 123 ... LastLast

Thread Information
Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)


User Tag List

Similar Threads

  1. LoGic Iz here.
    By Logic in forum The Red Carpet
    Replies: 2
    Last Post: 08-16-2009, 02:48 AM
  2. Replies: 13
    Last Post: 10-27-2008, 11:38 PM
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •