Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

For MMORPG, there is a tick function to update every object's state in a map. The function was triggered by a timer in fixed interval. So each map's update can be dispatch to different thread. At other side, server handle player incoming package have its own threads also: I/O threads. Generally, the handler of the corresponding incoming package run in I/O threads. So there is a problem: thread synchronization. I have consider two methods:

  1. Synchronize with mutex. I/O thread lock a mutex before execute handler function and map thread lock same mutex before it execute map's update.
  2. Execute all handler functions in map's thread, I/O thread only queue the incoming handler and let map thread to pop the queue then call handler function.

These two have a disadvantage: delay. For method 1, if the map's tick function is running, then all clients' request need to waiting the lock release. For method 2, if map's tick function is running, all clients' request need to waiting for next tick to be handle.

Of course, there is another method: add lock to functions that use data which will be accessed both in I/O thread & map thread. But this is hard to maintain and easy to goes incorrect. It needs carefully check all variables whether or not accessed by both two kinds thread.

My problem is: is there better way to do this? Or from practical view, the delay can be accepted because nothing will happen between 2 tick (the world is driven by continuous tick, all object will paused in 2 tick's interval) Generally, the interval is about 50ms to 100ms

Notice that I said map is logic concept means no interactions can happen between two map except transport. I/O thread means thread in 3rd part network lib which used to handle client request.

share|improve this question
    
This is probably a premature optimisation. Have you considered using a single-threaded server? –  MarkR Nov 5 '12 at 17:37
    
single thread only support hundreds people. for commercial purpose, it needs thousands –  jean Nov 6 '12 at 4:52

5 Answers 5

up vote 0 down vote accepted

I have consider two methods: Synchronize with mutex. I/O thread lock a mutex before execute handler function and map thread lock same mutex before it execute map's update.

If you do this, then there is hardly any point having separate threads, because only one runs at a time!

Execute all handler functions in map's thread, I/O thread only queue the incoming handler and let map thread to pop the queue then call handler function.

This seems closer to what you should do. The I/O thread should handle I/O - nothing more. It needs to be able to get exclusive access to the message queue or data buffers that let the network exchange data with the game, and that's all.

You would not have 1 single lock for your entire map. Each client has its own lock (or locks), guarding its input and output. Only when that client is sending data or receiving it would you need to lock it.

Of course, there is another method: add lock to functions that use data which will be accessed both in I/O thread & map thread. But this is hard to maintain and easy to goes incorrect. It needs carefully check all variables whether or not accessed by both two kinds thread.

This is not actually difficult at all. The answer is to make the shared data as small as possible. For example, use 2 queues, one for messages coming in (network -> server) and one for messages going out (server -> network). Lock the queue to add or remove messages, and ensure there is no other data shared across the I/O and logic sections.

share|improve this answer
    
In fact, my method 1 & 2 is almost same: all event handler of all clients and map's tick function are executed sequentially. Use queue still can not make then to be concurrent. In method 2, the map's tick function work like this: for each session do (for all message in queue do (execute logic which the message demand)) do tick function' update job. The consequence is same: no concurrent. Method 2 better at: it will not block I/O thread and have not overhead of mutex lock because one map's tick function always run in its own dedicated thread. –  jean Nov 6 '12 at 2:01
    
My method 3 can be viewed as improved method 2. It only add lock need to rather than method 2, it lock a "shared lock" whatever there need a thread synchronization or not. For example, a client message arrived, server need to set player's variable 'a' to 10. But this 'a' never accessed by map's tick function, so 'a' don't need to synchronize, then method 3 can save a lock. Notice that "a=10" is running in I/O thread. You said: "The I/O thread should handle I/O - nothing more", I agree that. But nowadays network lib supply this ability: dispatch job to I/O threads such as boost::asio, netty –  jean Nov 6 '12 at 2:20
    
If use method 2, then I/O thread only handle I/O. If use method 1 or 3, then its I/O thread will be used to run business logic job and have to consider thread synchronization problem: a share lock(method 1) or finer granularity locks(method 3) –  jean Nov 6 '12 at 2:24
    
You don't usually want to run a game's "business logic" concurrently anyway because that is difficult to make correct. You certainly wouldn't want to do it using the networking library's threading system. Use the I/O library to get a queue of messages and handle them sequentially. –  Kylotan Nov 6 '12 at 11:56

Here's an architecture you might want to consider:

You might want to use separate processes for these tasks:
- User authentication
- Realm selection
- Each realm (maybe broken into independent maps)
- Ingame subtasks, such as mail/global chat subsystem, item/npc cache, largely independent of other state, that does not need to further burden the map server.

Using different processes ensures that a faulty module won't bring down the whole system. Partial reboot's and hot swapping's inherently supported. It's easier to scalate this model to several different machines if your needs require it.

Each module's internal architecture's very similar: Your input threads just push messages into a queue. Your core module requests this list each update, and feeds its messages to the message consumers. These message consumers run the required actions through transactions - acquire locks on affected objects (player inventory, pickable item), run actions (pick item), free locks. Outbound messages are queued in a message consumer local queue, so no synchronization's required here. Once all incoming messages have been processed, these thread local queues are harvested, merged and its messages forwarded to their respective targets.

share|improve this answer
    
how is that helping? Maybe I got it wrong but he asked for something completely different. (maybe the last part is somewhat helpful) –  Layne Nov 5 '12 at 12:37
1  
I'm sorry I didn't explicitly state it. If you're receiving your login and your game/chat/etc messages in the same process, you're either locking the unique queue for each incoming message and then demultiplexing, or you're running separate incoming message queues for each role, further justifying the separation into processes. –  Pablo Nov 5 '12 at 13:16
    
The other functionality you mention definitely run in process respectively. So you prefer synchronize with queue. My worried thing is: does this involve delay that can feel by player? For example: player push a key send a attack command to server, when server receive this, it will not handle this immediately. It need wait for next tick of map, then the command will be executed. The largest delay is almost double interval of ticks. Plus network delay (generally less than 200ms), does it OK? –  jean Nov 6 '12 at 1:41

You can run your IO on background threads that just waits for a full wellformed packet to come in, and then puts the data in the packet into a queue for the main processing thread to process. The main thread can run in a small while loop like:

while(!shutdown)
{
    dequeue_player_input();
    process_objects();
}

In general a multi-process instead of a multi-thread approach will better suit an MMO design. On MMO's I've worked on, a single process could handle anything from the entire world to a 20x20 meter square of the world. And as player and NPC concentration increased, the server would spin up other processes to handle smaller and smaller pieces of the world. IE: Maybe we'd start with 100 processes spread over 15 machines for the world, then 5000 players would come to see an event in one spot. That one spot alone would be handled by 16 processes none of them guaranteed to be on any single machine.

share|improve this answer
    
Your first paragraph and example is what I was recommending: but I don't think I was clear enough. –  Kylotan Nov 6 '12 at 19:38
    
Multi-process(single machine or cluster) has a big problem: how to communicate with each other? Single machine's multi-process communication is more complex than multi-thread, need to use mapped-memory or signal or something else. Cluster's multi-process is a impossible mission to do communication, let alone the speed is much slower(1Gbps Ethernet vs memory), how to guarantee the 'happen-before' is extremely difficult(If two machine want to set variable 'a', first machine 1 set 'a' to 1, then machine 2 set 'a' to 'a'+1. You need to guarantee the execution order and feedback result to machines) –  jean Nov 7 '12 at 1:48
    
Yes and? There's a reason why MMOs are the hardest problem in computer science. See: gamedev.stackexchange.com/questions/90/… Every MMO I've worked on has to solve these type of problems every day. The answer to your question though is you don't solve that problem you bypass it. One process is authoritative for an object, all other edge processes have a slightly delayed read-only observation of the object. Then the difficulty comes in crossing server boundaries and handing off who is authoritative to the next server. –  Doug-W Nov 7 '12 at 2:26
    
I can't understand your solution, but I insist it is impossible, at least in a commercial product. Don't like other app like search engine, the time of data synchronization is not important, so it can have a large cluster. But MMO does not. If the time used to synchronize data between machine is long, it can not be accepted(delay), as you can imagine, the data needs to synchronized is big(every player, npc... on the map). And there is another problem: who's data in charge? Machine 1 set a=10, machine 2 set a=9. –  jean Nov 7 '12 at 3:05
    
Of course you can put all data needs share on single machine, use IPC or something else to access the map machine, but the speed will be very slow and programming model have a big change, for at least 100k code line project, it is heavy to afford this. I never heard there is a MMO work that this except some experimental project like reddwarf –  jean Nov 7 '12 at 3:06

Break down I/O threads and map threads into DP algorithms.

  • Quad/Oct-Trees are good just because they are simple.
  • Structure with moving objects (AABB), without having to rebuild a big part of the structure for each object
  • Depending on the amount of reliable packets you want to send and the pace of the RPG TCP should be fine. A lot of networking libraries implement TCP basically with UDP allowing reliable/unreliable packets.
  • Have a deep study on Synchronization architecture of Croquet Project will help you for better understanding.
share|improve this answer
    
What's the DP algorithms you mention? Dynamic Programming?? –  jean Nov 5 '12 at 5:49
    
@jean, Yes Dynamic Programming. –  Md. Mahbubur R. Aaman Nov 5 '12 at 5:52
    
How to do that? DP is method to solve problem which the solution can be accumulate with optimal solution of sub-problem. What's the relation with thread?? –  jean Nov 5 '12 at 6:00
    
@jean, sorry for any misunderstanding. :) To break down I/O threads and map threads into better tiny/small portions, for example, Qual/Oct-Trees, TCP+UDP where the best, etc. These total words i stated as DP algorithms. –  Md. Mahbubur R. Aaman Nov 5 '12 at 6:05

I use 2 from your suggested solutions; because my server is c#, this is can be handled very nicely with a lock-less queue of WorkItems which contain a delegate and an array of parameters.

The thread which processes WorkItems can be asleep until a message arrives from the client, or it can always process messages at a update fixed interval. Works very well for me.

share|improve this answer
    
My worried thing is: does this involve delay that can feel by player? For example: player push a key send a attack command to server, when server receive this, it will not handle this immediately. It need wait for next tick of map, then the command will be executed. The largest delay is almost double interval of ticks. Plus network delay (generally less than 200ms), does it OK? –  jean Nov 6 '12 at 1:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.