   Multithreaded MMO Engine Design
  Inspired by the entity component system threads of the past couple of months, I had my own thoughts about how to create a flexible, multithread and easily enhanceable system.Basically, there are no entity objects, instead, entities only exist in form of an EntityId and a common datastructure shared by all components, I call it ComponentSharedData.So there is no event system that handles inter component communication, this adds hidden dependencies, but with some care of the programmer these won t cause many problems.The creation of an entity looks like this.ComponentSharedData data = new ComponentSharedData();EntityId entityid = GenerateUniqueId();CreateComponent("physicscomponent",entityid,data,params);CreateComponent("renderable",entityid,data,params);CreateComponent("useable",entityid,data,params);class Component{  ComponentSharedData data;public:  Component(ComponentSharedData _data, ParameterList params)  {data = _data;// use params to initialize what ever you want  }}class ComponentSharedData{  map< key, value >  data;private:  Lock();  Unlock();public:  voidRegisterVariable(key);  void SetVariable(key,value);  void ExistsVariable(key);  value GetVariable(key);}Whats missing now is the game logic, I did not use a "gamelogiccomponent" at the creation example, for a reason.The logic depends on all other components, position, health, mana, ... an endless list, thus it is pointless to factor it into a component.Components should only contain logic that is, and I emphasize that, "data dependent".The "renderable" is only interested in position and geometry data, the "physicscomponent" is interested inposition, velocity, surface properties and collision meshes.The "useable" component depends on its own flags or constraints only and maybe some actor attributes.A "gamelogic" component has more complex dependencies, such as visibility, which is clearly not a data dependency.How to implement the game logic then? Well, with Jobs.Each action that takes place can be represented by a "Job" that has to be done. Most likely a "Job" is composed of many "Action"s that are performed in a row.Let me give you an example.A mage casts a spell "blizzard" to do area dmg.The "Job" may look like this:- Find entities in <range> around <position> and store in <list>- Actor <entityid>(the mage's entityid) deals damage to all entities whose <entityid> is in <list>class Action{ Execute(entityid, data, params);}class ActionFindEnemiesInRangeAroundPosition : public Action{ Execute(entityid, data, params) {    SceneGraph.FindEntities(params.position, params.range,data.entities); }}class ActionApplyDmg : public Action{  Execute(...)  {foreach(entity in data.entities){   HealthSystem.ApplyDmg(entity, somevalue, invoker);}  }}class Job{  EntityId invoker;  DataContainer data;  list< Actions > actions;  params;  Execute()  { foreach( action in actions) {action.Execute(invoker,data,params); }  }}Its amazing how you could create tons of spells with a view simple components.Now comes the trickier part, the whole system shall be multithreaded, which causes several problems.As an example, you got a TerrainSystem that allows for modification of the terrain at runtime by player interaction.If you perform such modifications and at the same time want to cull/render the terrain or want to perform collision detection against it, you will need tons of mutexes to lock access to the objects, which tends to become error prone on the long run and certainly stalls other threads.The solution is simple, dont do everything in parallel, instead you could introduce a 4 stage process.Stage 1 T1="read network input", T2="terrain modifications"T1 reads network input and stored it into priority queue which are handled later on, infact T1 could always run in parallel of any other thread, but this makes no difference as the data will not be handle earlier.Stage 2 T3="physics", T4="gamelogic", T5="culling and rendering"Stage 3 T6="apply physic state changes and rebuild hierarchies", "network output"One can execute these stages in a row using semaphores.Stage1:  Semaphore1 = 2;  Semaphore2 = 0;  Semaphore3 = 0;End of Stage 1:  Semaphore1 = 0;  Semaphore2 = 3;  Semaphore3 = 0;...Each thread call SemaphoreWait(SemaphoreX) where X stands for its stage it belongs to.Now there is one problem, what if an action creates and entity that is to be used right away?We have to defere the jobs execution to the next frame.This can easily be done by inserting a new "Job" into the already existing JobQueue.This approach, implemented with care, allows you to implement a multithreaded game engine with a minimum of locking operations, to make optimal use of multicore architectures.The core of my private mmo project will be based on this architecture, so I am really interested in your feedback. Maybe you have some suggestions to improve it? Or found a mistake I made in my mind.I am looking forward to the discussion that hopefully arises.[Edited by - Basiror on June 14, 2009 2:55:06 PM]
  You have generic 'data' and 'params': how are you handling those? Boost::Any, or some similar variant type? How do you handle invalid values?Why pass that empty data object to each Component? Wouldn't you create different data objects and populate them first, before passing them in? Might it not just be easier to hide ComponentSharedData completely and instead just insert values directly into the Components?Regarding Jobs: again, you have arbitrary data and params fields. What goes in what? Your 'data' object can't be a ComponentSharedData since you're accessing an 'entities' field, which ComponentSharedData lacks. (Perhaps this isn't C++, rather some language which offers properties?) Also, what 'params' would be useful to be applied to more than one action? Surely each action would have very different parameters? I'd think all the relevant information would need to be passed via the data field, since there doesn't seem to be a useful distinction.If data is a generic scratchpad that you pass into a job for each action to read and write from, have you considered instead just using a scripting language in each case? Most scripting languages will allow you to run a script in an arbitrary context, so your 'data' object becomes the initial context/global scope/namespace (depending on your language) and actions can be implemented as scripted routines, rather than composited groups of actions.You have "SceneGraph.FindEntities" : but does that mean SceneGraph is global? If not, how does it end up in the job? And doesn't FindEntities require locking the scenegraph?I don't understand your concurrency description. You mention a 4-stage process but then provide an example with only 3 stages but 6 tasks. If each thread is waiting on a previous one to complete then you could end up with no concurrency gains at all. If you're careful you can get it pipelined so that Thread 1 is working on frame 3 while Thread 2 is working on frame 2 and Thread 3 is working on frame 1, for example. But that requires extra copies of external data which you've not described.   ;  HiThe ComponentSharedData class provides interfaces for the most common datatype you are going to store, I don t want to use a generic data representation, becausea) the data type is known at compile timeb) I don t like type conversions all over and validation of the resultse.g.intvector3long long...At first I indented to implement is as a locking structure, but I decided to go the data duplication way, all frames work on data of frame #i (read only) and set data for frame #i+1 via this centralized structure that takes care of automated duplication upon modification.After all threads of a stage have finished their work I can spawn several threads that loop through all the ComponentSharedData objects and merge the duplicated data. This is perfectly parallelizable.All threads that run inside one stage have read only access to all other systems to avoid race conditions.Now the jobs part, no FindEntity doesn t require the SceneGraph to be locked upon searching, thats due to the fact that Jobs, Physics and Culling/Rendering are executed during the same stage and do only have read access.SceneGraph is, well not a global in the sence of singletonitis, it gets passed in during construction and jobs can be created using a JobManager as a factory.The DataContainer is just there to allow actions to read and store data they need, it is implemented like the ComponentSharedData, maybe I will merge them to one.Of course you could implement actions as scripts, but you could just as well implement a class ActionScript : public Action and mix C++ and maybe Lua actions.I just need to make sure that lua can handle 64 bit integers, as all my entity handles are 64 bit, probably a waste of memory, but I am on the safe side according to my calculations.The aim is to spawn additional threads on many-core machines on demand. So a lock free system is a must in order gain any performance and it makes development considerably easier. Hunting down a dead lock that only occasionally happends is really a pain.   ;Quote:Original post by Basiror...but I decided to go the data duplication wayI went down this route, except I went mad and developed my AtomicDatabase, a transactional lock-free(ish) database.This way I don't have to care about the rest of the design, I know each transaction will see a consistent view of the world.My entity design is a simple class with each field wrapped by a VersionedValue (the main class in my atomic database), all generated from an XML file.RegardselFarto;  ELFARTO! :) hahahahahahahahahaha   ;Quote:Original post by elFartoQuote:Original post by Basiror...but I decided to go the data duplication wayI went down this route, except I went mad and developed my AtomicDatabase, a transactional lock-free(ish) database.This way I don't have to care about the rest of the design, I know each transaction will see a consistent view of the world.My entity design is a simple class with each field wrapped by a VersionedValue (the main class in my atomic database), all generated from an XML file.RegardselFartoThe problem is, if for example your physics engine changes the object's position and the culling system is working with the old position you have no way to detect this.a) make a copy of the old position to be used through out this frameb) somehow signal the scenegraph to reinsert this objectc) or defer the application of variable changes one frameYou could implement connectors to simulate access rights to objects to avoid modification by the multiple threads during the same frame#e.g.:ComponentSharedData data;PhysicsComponent:ref<SomeType> position(data.Get("position"));Renderable:const_ref<SomeType position(data.Get("position"));ref<> and const_ref<>this only grants the PhysicsComponent write access to "position", but sometimes it is desireable to grant multiple components write access, for example if you implement a spell "teleport" using the Job system I described earlier.One solution would be to:// stage 2 where all jobs are handledconst SomeType reset() { return 0; };Job:ref<SomeType> offset(data.Get("offset));// add a callback, we only want to teleport oncesoffset.onread = reset;offset = newposition;// stage 3 during application and hierarchy rebuilding, thus no more writes from stage 2 threads, thus no lockingPhysicsComponent:ref<SomeType> offset(data.Get("offset"));position += offset;//executes offset.onread and resets it;Quote:Original post by BasirorThe solution is simple, dont do everything in parallel, instead you could introduce a 4 stage process.Look here.If implemented properly, such system requires no locking, except for transitions between systems.;  On the server side, I'd recommend looking at just doing single threaded processes.It's amazing how much scaling you can get by spawning multiple processes to take advantage of multiple cores rather than having a single process with multiple threads, and it saves a ton of work in terms of concurrency issues.   ;Quote:Original post by kyoryuOn the server side, I'd recommend looking at just doing single threaded processes.It's amazing how much scaling you can get by spawning multiple processes to take advantage of multiple cores rather than having a single process with multiple threads, and it saves a ton of work in terms of concurrency issues.I dont see the advantages, surely multi process information sharing is harder than multi threading.   ;Quote:Original post by BasirorAs an example, you got a TerrainSystem that allows for modification of the terrain at runtime by player interaction.If you perform such modifications and at the same time want to cull/render the terrain or want to perform collision detection against it,you will need tons of mutexes to lock access to the objects, which tends to become error prone on the long run and certainly stalls other threads.The solution is simple, dont do everything in parallel, instead you could introduce a 4 stage process.Quote:Original post by AntheusLook here.If implemented properly, such system requires no locking, except for transitions between systems.I'm working on a similar idea, which would work much the same way:1) Entity sub-system updates the player2) player calls: terrain.Modify( position, changeInHeight )3) terrain stores (terrain,Modify,position,changeInHeight) in the terrain sub-system4) At the same time, the rendering subsystem is drawing the (unmodified) terrain mesh5) When the entity and rendering subsystem jobs are complete, the terreain subsystem job is started.6) The terrain subsystem processes queued function calls,e.g. It would take the data from earlier (terrain,Modify,position,changeInHeight) and call terrain.DoModify( position, changeInHeight )I'm also working on allowing components to double-buffer their state, so that you don't even have to worry about these data dependencies.Each object has a public thread-safe (lock/wait-free) queue of actions to be performed next cycle, a private queue of actions to be performed this cycle, and each object maintains two copies (one private/writable and one public/read-only) of it's state ("state" being any variables that can be accessed by other components in any way).At the start of a cycle (the only syncpoint) every object1) Copies it's public action queue into it's private one (and clears the public/thread-safe queue).2) Copies it's private state over it's public state.Then, once this is done: in parallel, every object works through it's private action queue, which in turn modifies it's private state, and pushes new actions into the public action queues of other objects..This allows all objects to be updated in parallel, with no data dependencies and only a single sync point per cycle (but you would have multiple cycles per-frame).This does require a large storage overhead though, which isn't that much of a problem on PC but might trouble a console. However I have heard MS recommend double-buffered state in order to take advantage of the 360's multi-core CPU.[EDIT]Quote:Original post by bzroomQuote:Original post by kyoryuIt's amazing how much scaling you can get by spawning multiple processes to take advantage of multiple cores rather than having a single process with multiple threads, and it saves a ton of work in terms of concurrency issues.I dont see the advantages, surely multi process information sharing is harder than multi threading.Maybe something like this: http://farrarfocus.blogspot.com/2009/06/factoring-out-job-scheduler.html ?[Edited by - Hodgman on June 17, 2009 1:34:34 AM]