Thread: on the complexity of event-driven game server logic

Results 1 to 7 of 7
  1. #1 on the complexity of event-driven game server logic 
    Renown Programmer
    veer's Avatar
    Join Date
    Nov 2007
    Posts
    3,749
    Thanks given
    354
    Thanks received
    1,367
    Rep Power
    3032
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]

    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]

    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]

    just some links which are related to what i will be discussing here.

    events often times make our lives easier by reducing complexity of code and making it more efficient.

    for example, where in older private servers a dedicated thread was spawned per player for I/O, newer servers made use of event-driven interfaces which allowed one to demultiplex I/O.
    before, each thread would most likely be in a blocking state, only woken up and scheduled to take up CPU time when a read operation completed. this worked fine for small numbers of clients, but as the number grew, it failed to keep up.
    the [Only registered and activated users can see links. ] allowed us to conveniently only need one thread no matter the number of clients. using non-blocking I/O, there is no need for dedicated threads to be woken up. instead, the reactor explicitly states interest in events and was notified when they occurred. this avoided the cost of things like context switching and excessive pre-emption with CPU load saturation. logically, this scaled well and gracefully degraded with load.

    using events also helps prevent polling and redundancy.
    instead of continuously checking to see if a player is in an area (warning: bad code ahead)...
    Code:
    void tick() {
        for (Player player : players) {
            if (player.moved && player.x >= AREA_X1 && player.y >= AREA_Y1 && player.x <= AREA_X2 && player.y <= AREA_Y2) {
                ... area-specific logic here ...
            }
        }
    }
    we can implement something called inversion of control and decouple this into events and event listeners:
    Code:
    EventSubscriber<MovementEvent> movement_listener = EventSubscriber<MovementEvent>() {
    
                public boolean satisfied(MovementEvent event) {
                    Player player = event.player;
                    return player.x >= AREA_X1 && player.y >= AREA_Y1 && player.x <= AREA_X2 && player.y <= AREA_Y2;
                }
    
                public void handle(MovementEvent event) {
                    ... area-specific logic here ...
                }
            });
    this helps separate our concerns and make developing much easier.

    since events allow code to listen for specific changes, they are also used for completion events of asynchronous operations. this proactive use of completion events contrasts with the previously mentioned reactors and their readiness events.
    Code:
    ...
    Future<Set<?>> _results = database.query("select * from operations where blocking=1");
    /* this blocks the current thread waiting */
    Set<?> results = _results.get();
    ...
    traditionally, like earlier with sockets, one needed a dedicated thread for such blocking database I/O.

    with the advent of using thread pools for server logic, we introduced the idea of small, atomic units of work, or tasks. given that a thread pool uses a limited number of workers, tasks have a few logical constraints with them to acheive performance:
    But the thread pool is a leaky abstraction. That is, the pool hides a lot of details from us, but to use it effectively we do need to be aware of some things a pool does under the covers so that we can avoid inadvertently hitting performance and correctness pitfalls. Here's the summary up front:
    • Tasks should be small, but not too small, otherwise performance overheads will dominate.
    • Tasks should avoid blocking (waiting idly for other events, including inbound messages or contested locks), otherwise the pool won't consistently utilize the hardware well -- and, in the extreme worst case, the pool could even deadlock.
    (source: [Only registered and activated users can see links. ])

    now it becomes apparent that we can't do such blocking within the logic pool. instead, we rely on having another pool somewhere handling database I/O, and using the completion listener facility mentioned earlier:
    Code:
    ...
    database.query("select * from operations where blocking=1", new CompletionHandler<Set<?>>() {
    
        public void completed(Set<?> results) {
            /* complete our stuff here */
        }
    });
    /* return immediately and don't block */
    as it turns out, blocking operations don't necessarily always deal with low-level conceptualizations of I/O, through sockets and databases.

    in runescape, we actually see a lot of blocking operations that block instead on interaction (I/O) from players themselves.
    for example, take quests. quests are logically separated into discrete steps or stages. a stage associated with a player is state.
    quests themselves are easily modelled as event-driven finite-state machines:

    [Only registered and activated users can see links. ]
    Code:
    	public void handleNpc(Npc npc, Player owner) throws Exception {
    		owner.setBusy(true);
    		npc.blockedBy(owner);
    		Quest q = owner.getQuest(11);
    		if(q != null) {
    			if(q.finished()) {
    				questFinished(npc, owner);
    			} else {
    				switch(q.getStage()) {
    					case 0:	//Coming from Romeo
    						comingFromRomeo(npc, owner);
    						break;
    						
    					case 1:	//Has message for Romeo
    						hasMessage(npc, owner);
    						break;
    					case 2:	//Delivered message to Romeo
    						deliveredMessage(npc, owner);
    						break;
    					case 3:	//Talked to Father Lawrence
    						didYouFind(npc, owner);
    						break;
    					case 4:	//Talked to apothecary
    						if(owner.getInventory().countId(57) > 0) {
    							hasPotion(npc, owner);
    						} else {
    							notHasPotion(npc, owner);
    						}
    						break;
    					case 5:	//Given Juliet potion
    						afterPotion(npc, owner);
    						break;
    					
    				}
    			}
    		} else {
    			questNotStarted(npc, owner);
    		}
    	}
    using events here makes sense, as npcs react to player interaction in a way dependent on quest stage.

    a common issue people have with this system is that there are too many separate ways of dealing with the event. indeed, the logic for the quest crosses multiple distinct NpcHandlers here:
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]

    instead, it is proposed to centralize these smaller state machines across borders into one consistent interface. it is argued that the entirety of the quest logic ought to be placed under a single event-driven, state-dependent actor (minus the fact actors use a messaging system with explicit producers/consumers) representing the quest, whose incoming messages are events it has interest in. this way events for romeo, juliet, apothecary, and father lawrence all can be easily managed and associated with a single quest. these actors could be implemented in their own threads, blocking on some incoming event queue, or, much more logically, internally use fine event listeners which forward and demultiplex to a central actor event listener. in practice, both have similar semantics: actors wait for messages to be routed to them, and when they are, they react. using a thread (blocking on a message queue) is far more heavy-weight than than handling it in whatever thread dispatches events, though.
    On mainstream platforms such as the JVM [16], an equally attractive implementation was as yet missing. Their standard concurrency constructs, shared-memory threads with locks, suffer from high initialization and context-switching overhead as well as high memory consumption. Therefore, the interleaving of independent computations is often modelled in an event-driven style on these platforms. However, programming in an explicitly event-driven style is complicated and error-prone, because it involves an inversion of control.
    (source: [Only registered and activated users can see links. ])
    Code:
    ...
    class RomeoHandler implements NpcHandler {
    
        void handleNpc(Npc npc, Player owner) throws Exception {
            act(new NpcEvent(owner, npc));
        }
    }
    ...
    void act(Event evt) {
        switch (state) {
            case COMING_FROM_ROMEO:
                switch (evt.type) {
                    case NPC_EVENT:
                        ...
                        break;
                    ... 
                }
                break;
            ...
        } 
    }
    there is still a problem, however. take this code, for example:
    Code:
    	private final void comingFromRomeo(final Npc npc, final Player owner) {
    		World.getDelayedEventHandler().add(new DelayedQuestChat(owner, npc, new String[] {"Juliet, I come from Romeo", "He begs me tell you he cares still"}, true) {
    			public void finished() {
    				World.getDelayedEventHandler().add(new DelayedQuestChat(npc, owner, new String[] {"Take this message to him"}) {
    					public void finished() {
    						World.getDelayedEventHandler().add(new DelayedQuestChat(owner, npc, new String[] {"Certainly, I will deliver your message straight away"}) {
    							public void finished() {
    								World.getDelayedEventHandler().add(new DelayedQuestChat(npc, owner, new String[] {"It may be our only hope"}) {
    									public void finished() {
    										World.getDelayedEventHandler().add(new SingleEvent(owner, 1500) {
    											public void action() {
    												owner.sendMessage("Juliet gives you a message");
    												owner.getInventory().add(new InvItem(56, 1));
    												owner.sendInventory();
    												owner.incQuestCompletionStage(11);
    												owner.setBusy(false);
    												npc.unblock();
    											}
    										});
    									}
    								});
    							}
    						});
    					}
    				});
    			}
    		});
    	}
    a DelayedQuestChat represents an asynchronous operation, and it uses a similar completion listener mechanism as introduced earlier. it doesn't take very long, however, for the ugliness to become apparent in this approach. developers explicitly write callbacks for handling completion events, which themselves are nested in such callbacks etc. the flow of logic becomes fragmented and difficult to visualize.

    the actor solution to this problem is to expand the number of states and/or events to cope:
    Code:
    void act(Event evt) {
        switch (state) {
            case COMING_FROM_ROMEO_A:
                switch (evt.type) {
                    case COMPLETION_A:
                        ...
                        break;
                    case COMPLETION_B:
                        ...
                        break;
                    ...
                }
                break;
            case COMING_FROM_ROMEO_B:
                switch (evt.type) {
                    case COMPLETION_A:
                        ...
                        break;
                    case COMPLETION_B:
                        ...
                        break;
                    ...
                }
                break;
        }
    }
    note we've reached a trade-off here between state and input space sizes.
    our actors are merely finite state machines, or finite automata. two types of finite automata exist: deterministic and non-deterministic. a deterministic automaton has a definite successor state given a input, while non-deterministic ones do not.
    adapting our quest actor to handle the added completion events turns out to have majorly the same impact as converting an NFA into a DFA i.e. state explosion.
    as can be clearly seen, this exposed interface is not much cleaner to developers than the deeply nested completion listeners.

    the event interface here presents a known problem:
    For these high-concurrency systems, event-based programming tends to obfuscate the control flow of the application. For instance, many event systems “call” a method in another module by sending an event and expect a “return” from that method via a similar event mechanism. In order to understand the application, the programmer must mentally match these call/return pairs, even when they are in different parts of the code. Furthermore, these call/return pairs often require the programmer to manually save and restore live state. This process, referred to as “stack ripping” by Adya et al. [1], is a major burden for programmers who wish to use event systems. Finally, this obfuscation of the program’s control flow can also lead to subtle race conditions and logic errors due to unexpected message arrivals.
    (source: [Only registered and activated users can see links. ])
    The solution is to use non-blocking IO so that another thread of execution can work while one is waiting on IO. node.js is well known for doing this. However, the callback style used by node.js is much more difficult to write, maintain, and reason about, particularly when there are multiple IO actions in one request. Instead of a simple, synchronous flow, you have to have a callback for every IO action. Ruby was always fundamentally capable of non-blocking IO, especially after EventMachine was released, but that style of programming was never appealing.
    (source: [Only registered and activated users can see links. ])
    An event-driven model does not support a blocking wait abstraction. Therefore, programmers of such systems frequently need to use state machines to implement control flow for high-level logic that cannot be expressed as a single event handler. Unlike state machines that are part of a system specification, the control-flow state machines typically have no formal specication, but are created on-the-fly by the programmer. Experience has shown that the need for explicit state machines to manage control flow makes event-driven programming difficult [3, 25, 26, 35]. With the words of Levis et al. [26]: “This approach is natural for reactive processing and for interfacing with hardware, but complicates sequencing high-level operations, as a logically blocking sequence must be written in a state-machine style.”
    (source: [Only registered and activated users can see links. ])
    it's right:
    Code:
    	private final void questNotStarted(final Npc npc, final Player owner) {
    		npc.blockedBy(owner);
    		owner.setBusy(true);
    		World.getDelayedEventHandler().add(new DelayedQuestChat(npc, owner, new String[] {"romeo, romeo wherefore art thou romeo", "Bold adventurer, have you seen Romeo on your travels?", "Skinny guy, a bit wishy washy, head full of poetry"}, true) {
    			public void finished() {
    				World.getDelayedEventHandler().add(new SingleEvent(owner, 1500) {
    					public void action() {
    						final String[] options0 = {"Yes i have met him", "No, i think i would have remembered if I had", "I guess i could find him", "I think you could do better"};
    						owner.setBusy(false);
    						owner.sendMenu(options0);
    						owner.setMenuHandler(new MenuHandler(options0) {
    							public void handleReply(final int option, final String reply) {
    								owner.setBusy(true);
    								for(Player informee : owner.getViewArea().getPlayersInView()) {
    									informee.informOfChatMessage(new ChatMessage(owner, reply, npc));
    								}
    								switch(option) {
    									case 0:
    									case 1:
    										final String[] messages1 = {"Could you please deliver him a message?"};
    										World.getDelayedEventHandler().add(new DelayedQuestChat(npc, owner, messages1) {
    											public void finished() {
    												World.getDelayedEventHandler().add(new SingleEvent(owner, 1500) {
    													public void action() {
    														final String[] options1 = {"Certainly, I will do so straight away", "No, I have better things to do"};
    														owner.setBusy(false);
    														owner.sendMenu(options1);
    														owner.setMenuHandler(new MenuHandler(options1) {
    															public void handleReply(final int option, final String reply) {
    																owner.setBusy(true);
    																for(Player informee : owner.getViewArea().getPlayersInView()) {
    																	informee.informOfChatMessage(new ChatMessage(owner, reply, npc));
    																}
    																switch(option) {
    																	case 0:
    																		final String[] messages2 = {"It may be our only hope"};
    																		World.getDelayedEventHandler().add(new DelayedQuestChat(npc, owner, messages2) {
    																			public void finished() {
    																				owner.sendMessage("Juliet hands you a message");
    																				owner.getInventory().add(new InvItem(56, 1));
    																				owner.sendInventory();
    																				owner.addQuest(11, 5);
    																				owner.incQuestCompletionStage(11);
    																				owner.setBusy(false);
    																				npc.unblock();
    																			}
    																		});
    																		break;
    																	case 1:
    																		final String[] messages3 = {"I will not keep you from them, goodbye."};
    																		World.getDelayedEventHandler().add(new DelayedQuestChat(npc, owner, messages3) {
    																			public void finished() {
    																				owner.setBusy(false);
    																				npc.unblock();
    																			}
    																		});
    																		break;
    																}
    																owner.setBusy(false);
    																npc.unblock();
    															}
    														});
    													}
    												});
    											}
    										});
    										break;
    									case 2:
    										final String[] messages4 = {"That is most kind of you", "Could you please deliver a message to him?"};
    										World.getDelayedEventHandler().add(new DelayedQuestChat(npc, owner, messages4) {
    											public void finished() {
    												final String[] messages5 = {"Certainly, I will deliver your message straight away"};
    												World.getDelayedEventHandler().add(new DelayedQuestChat(owner, npc, messages5) {
    													public void finished() {
    														final String[] messages6 = {"It may be our only hope"};
    														World.getDelayedEventHandler().add(new DelayedQuestChat(npc, owner, messages6) {
    															public void finished() {
    																owner.sendMessage("Juliet hands you a message");
    																owner.getInventory().add(new InvItem(56, 1));
    																owner.sendInventory();
    																owner.addQuest(11, 5);
    																owner.incQuestCompletionStage(11);
    																owner.setBusy(false);
    																npc.unblock();
    															}
    														});
    													}
    												});
    											}
    										});
    										break;
    									case 3:
    										final String[] messages7 = {"He has his good points", "He doesn't spend all day on the internet at least"};
    										World.getDelayedEventHandler().add(new DelayedQuestChat(npc, owner, messages7) {
    											public void finished() {
    												owner.setBusy(false);
    												npc.unblock();
    											}
    										});
    										break;
    								}
    							}
    						});
    					}
    				});
    			}
    		});
    	}
    dealing with code like this is ugly and hard to work with for experienced programmers; how will content developers fare?

    the solution to this problem is to reconcile the scalable "evented" model with the easy "threaded" model.
    EVE uses a special Stackless version of Python to implement game logic, both on the server and the client. This approach makes the creation of game logic much simpler than traditionally possible. The control structures provided by Stackless allow for a more "procedural synchronous" model, rather than an "event driven asynchronous", or thread pooling.

    What this effectively means is that very many actors can perform tiny tasks without the added complexity or overhead of the other two execution models. Our game logic scripters are thus freed from many of the mundane tasks associated with models that don't benefit from the control structures provided by Stackless and often bogg down the creative process of writing interesting game behavior.
    (source: [Only registered and activated users can see links. ])
    The amazing opportunity with Ruby 1.9 is to use Ruby’s fibers to abstract away the callbacks and just write normal code that looks synchronous. Each IO action is performed inside a fiber that is paused during the IO, allowing other fibers to run. When the IO is finished, the fiber can be resumed. And this style is actually not that hard to manage- it only has to be done once by the library writer- the implementation details become transparent to the library user.
    (source: [Only registered and activated users can see links. ])

    fibers are light-weight processes of execution which utilize cooperative multitasking as opposed to preemption. they're often also called "microthreads", "protothreads", and "coroutines". fibers explicitly yield time to other tasks to execute, and map many-to-many across native, heavy-weight threads.
    over the already developed task framework used for writing server logic, fibers can be implemented over tasks to support blocking operations inherently in their design. when they block, they yield to other tasks as opposed to expensively wasting a pooled worker.

    internally, a fiber is often implemented using something called continuations. a continuation encapsulates the state of execution at any time. when a fiber yields, a snapshot of it's state is taken and the task is rescheduled. when a fiber is resumed, it restores state from the snapshot and jumps back into the code. in our case, a fiber would be resumed when the appropriate completion event arrives.
    Code:
    	private final void deliveredMessage(final Npc npc, final Player owner) {
    		World.getDelayedEventHandler().add(new DelayedQuestChat(npc, owner, new String[] {"Ah, it seems that you can deliver a message after all", "My faith in you is restored"},true) {
    			public void finished() {
    				owner.setBusy(false);
    				npc.unblock();
    			}
    		});
    	}
    could be rewritten as
    Code:
    juliet.bind(new EventSubscriber<NpcInteractionEvent>() {
    
        void handle(NpcInteractionEvent evt) {
            Player player = evt.player();
            Npc juliet = evt.target();
            Stage stage = player.progress(RomeoAndJulietQuest.this);
            switch (stage) {
                case DELIVERED_MESSAGE:
                    player.occupy(juliet);
                    /* we yield while tell() takes place asynchronously */
                    npc.tell(player, "Ah, it seems that you can deliver a message after all", "My faith in you is restored").yield();
                    player.release(juliet);
                    break;
                 ...
            }
        }
    });
    although in practice such logic would be implemented in a dynamic scripting language

    unfortunately, given the way the standard JVM works (the non-standard da vinci machine has an implementation), continuations are nearly impossible to implement in pure java without falling back to bytecode instrumentation.

    i'm currently working on implementing continuations in my own server as to simplify the complex event-driven logic, but i do also have to focus on school so i can't guarantee anything. there are however existing generalized solutions out there (though they're probably more difficult to deal with than a specialized solution):
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    Reply With Quote  
     


  2. #2  
    Registered Member Phyfiox's Avatar
    Join Date
    Jun 2008
    Posts
    52
    Thanks given
    4
    Thanks received
    13
    Rep Power
    24
    Nice use of the actor pattern.
    Also: [Only registered and activated users can see links. ]

    Edit: super_, what do you think about multithreaded blocking I/O server (after reading the Paul Tyma article)
    Is it possible for a thread-per-request design to scale, if implemented correctly (queueing)
    Reply With Quote  
     

  3. Thankful user:


  4. #3  
    Renown Programmer
    veer's Avatar
    Join Date
    Nov 2007
    Posts
    3,749
    Thanks given
    354
    Thanks received
    1,367
    Rep Power
    3032
    i don't think SEDA applies here
    also: [Only registered and activated users can see links. ]
    Reply With Quote  
     

  5. #4  
    Renown Programmer and Respected Member
    Maxi's Avatar
    Join Date
    Jun 2008
    Posts
    3,201
    Thanks given
    281
    Thanks received
    1,091
    Rep Power
    1365
    I don't see how this would be possible with plain java without bytecode instrumentation. Mind telling me why you said 'nearly impossible'?

    Edit: is there a way to access a thread's stack without using reflection to make the field accessible?
    Edit2: Oracle is working on an API for this btw.

    [Only registered and activated users can see links. ]

    Quote Originally Posted by John Rose
    Lukas Stadler (at Johannes Kepler University) has gone much farther, implementing resumption of continuations. He will be updating this patch soon. A recent update from Lukas gives an idea of where he is headed. I expect we can turn the power on, soon.
    Source: [Only registered and activated users can see links. ]

    Link to Lukas Stadler's update: [Only registered and activated users can see links. ]
    Reply With Quote  
     

  6. #5  
    Renown Programmer
    veer's Avatar
    Join Date
    Nov 2007
    Posts
    3,749
    Thanks given
    354
    Thanks received
    1,367
    Rep Power
    3032
    look at the links i've posted... the oracle blog post uses apache javaflow (which uses bytecode instrumentation)
    stradler has been working on a non-standard open source project, namely the da vinci machine. i already mentioned this, too: [Only registered and activated users can see links. ] [Only registered and activated users can see links. ]

    edit: that being said, an example of the ugly explicit continuation-passing-style code:
    [Only registered and activated users can see links. ]
    the state machine is not any prettier

    cooperative fibers for java (via continuations):
    [Only registered and activated users can see links. ]

    edit2: [Only registered and activated users can see links. ]
    this is very interesting
    Reply With Quote  
     

  7. #6  
    ̿ ̿|̿ ̿ |̶ ̶ ̶ ̶| |̶͇̿ ̶͇̿ ͇̿ Haskelle

    Join Date
    Nov 2007
    Age
    25
    Posts
    1,228
    Thanks given
    329
    Thanks received
    517
    Rep Power
    1133
    I got some more links that go about event loops etc,
    >> this got it all started <<
    [Only registered and activated users can see links. ]

    ___ troll responses that do teach us some about evented I/O ___
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]
    [Only registered and activated users can see links. ]

    Ted is the most beautiful troll ever, and all the fish nommed the bait, + we learn some new stuff about event loops!
    Monads are just Monoids in the category of Endofunctors. What is the problem?
    Costate Comonad Coalgebra is equivalent of Java's member variable update technology for haskell. Problem?
    Reply With Quote  
     

  8. Thankful user:


  9. #7  
    Renown Programmer
    veer's Avatar
    Join Date
    Nov 2007
    Posts
    3,749
    Thanks given
    354
    Thanks received
    1,367
    Rep Power
    3032
    this thread isn't about node.js issues nor the problems of event loops, it's about exploring the middle ground of light-weight threads that use events
    that being said, i've seen those all over the past few days in /r/programming. nodejs noobs are irritating
    Reply With Quote  
     

  10. Thankful user:



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. Replies: 41
    Last Post: 10-17-2011, 09:49 AM
  2. Replies: 20
    Last Post: 02-06-2011, 12:52 AM
  3. A Thread Pool for a Staged Event Driven Architecture
    By blakeman8192 in forum Tutorials
    Replies: 14
    Last Post: 08-20-2010, 01:08 PM
  4. Replies: 38
    Last Post: 07-30-2010, 02:03 AM
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •