Author Topic: multi-threaded versus single threaded mud servers  (Read 12365 times)

Offline silenus

  • BFF
  • ***
  • Posts: 199
    • View Profile
multi-threaded versus single threaded mud servers
« on: September 19, 2007, 12:35:19 pm »
I am in the early stages of designing a new driver which hopefully I can implement over the course of time. One issue for me is the advantage and extent that multi-threading should be used in a driver or server design. I know for certain types of applications the speed up you get from using OS threads might be quite limited. I am curious if mudding is one of those applications where if you even exposed fully a nice parallel model that was easy to work with and fast would the inherent limitations of the application restrict the speed up.

I would be curious to hear different peoples opinions on this.

Thanks in advance,

Offline cratylus

  • Your favorite and best
  • Administrator
  • ***
  • Posts: 1022
  • Cratylus@Dead Souls <ds> np
    • View Profile
    • About Cratylus
Re: multi-threaded versus single threaded mud servers
« Reply #1 on: September 19, 2007, 01:01:41 pm »
I don't have an opinion, so much as an observation and
a question. My observation is that folks have for a long
time discussed the advantages of multithreaded LP muds,
but there are very few actual implementations (I actually am
not aware of any that are available for download).

Beyond whether it is possible, which I'm sure it is (we put a
man on the moon, after all, using sticks and stones), I guess
my first question is: what problem do you solve by doing
that? Perhaps the reason it hasn't been done yet is that
CPU power has grown so much, coincidentally as mud
processing demands grow, that there just hasn't been a need.

-Crat

PS: I'm sure MMORPG's like WoW are multithreaded servers.
It might be enlightening to research the advantage to which they
put it, and how they solve the dragon's dinner:

Quote
The Dragon's dinner problem
---------------------------

One of the original goals for the DOME project was to provide a
parallel/distributed execution envirionment for an LPmud game
driver. LPmud is programmed in a langauge called LPC, which is derived
from C and enriched with constructs to enable object oriented
programming, complex data types such as associative arrays and lambda
closures. This is interpreted by the game driver which provides single
threaded execution semantics.  Items in the game are represented by
LPC objects which provide methods specifiying how they interact with
other objects in the game.

Consider the following problem (dubbed "Dragon's Dinner"). Assume, in
an asynchronous distributed system, that there are two room objects
(r1, r2) and a door object (d) that connects them. R1 contains a
hungry dragon (hd) and r2 contains an adventurer (a). The door is
currently open, the adventurer has just fled from r1 and is about to
close the door. The dragon, on the other hand, wants to go after the
adventurer. Code for the dragon is something like:

        if (d->is_open())
                hd->move_to(r2);

And the code for closing the door is something like:

        d->close();

Now what if the following happens: The thread that executes the
dragon's action has checked that the door is indeed open, while the
other thread which is concurrently executing on a different processor,
closes the door. This succeeds and the adventurer sees the door
closing. However, when control returns to the dragon's thread, it
still believes that the door is open and steps through it, much to the
surprise of the adventurer who sees the dragon walking through a
closed door, before being devoured by the dragon.

Naturally this is merely a race-condition dictated by the asynchronous
execution of two data-dependent threads. The main goal of the DOME
project is to provide a system where the component objects can be
programmed in a sequential fashion, but have the run-time support
resolve such race-conditions (in a deadlock free manner) so that
parallel execution can be achieved.

Alexander Weidt [June 1995]



Offline detah

  • BFF
  • ***
  • Posts: 190
  • Ruler of 2D
    • View Profile
Re: multi-threaded versus single threaded mud servers
« Reply #2 on: September 19, 2007, 02:05:00 pm »
In other words, its not twice as fast, because you still have to wait on the previous command to execute, regardless of how fast each thread can process a command.

-Detah@Arcania

Offline Tricky

  • BFF
  • ***
  • Posts: 189
  • I like what I code and I code what I like!
    • View Profile
Re: multi-threaded versus single threaded mud servers
« Reply #3 on: September 19, 2007, 02:08:44 pm »
I'm sure there will some speed up in other areas as there will be many objects that are dealing with different things in different areas, for example a weather daemon has nothing to do with combat and so can they can quite happily do there own thing independently of each other. Of course this assumes that the code is executed in a parallel fashion.

As for the Dragon's Dinner, read up on threads and mutex semaphores. The door object can be locked (not in the key locking type of way) to prevent other objects from accessing the door data.

Tricky

Offline silenus

  • BFF
  • ***
  • Posts: 199
    • View Profile
Re: multi-threaded versus single threaded mud servers
« Reply #4 on: September 19, 2007, 03:43:00 pm »
One issue that concerns me is how much performance will the lock entry and exit code soak up for the mutex's. Making code thread safe often means the code will run slower so this offsets some of the speed up again you gain from MP as well.

Offline quixadhal

  • BFF
  • ***
  • Posts: 642
    • View Profile
    • WileyMUD
Re: multi-threaded versus single threaded mud servers
« Reply #5 on: September 19, 2007, 04:15:22 pm »
For me, the question boils down to benefit vs. cost.  There are benefits from having multi-threaded lpc execution, but those benefits don't really show through to the end user unless you design a really different kind of real-time game.  Something like the hand-to-hand combat in Gladiator Pits comes to mind.  The driver itself can already be multi-threaded to handle things like blocking I/O, DNS lookups, etc.

The costs though, are quite a bit more immediate.  As others have said, you have to sprinkle mutex code all throughout every aspect of your game.  Consider a simple fight where a mob hits you and you cast a spell of reflect damage.  In a single threaded driver, this is easy.  If you go first, the attack bounces and damages the mob.  If they go first, you take the damage and either flub the spell, or it goes up late and the next attack hits it.

In a multi-threaded interpreter, if you don't mutex lock the combat events, one thread may start doing the attack, get to the part where it gives you damage... then the spell thread goes through... then perhaps the attack thread picks up and sees there's a spell effect, and does the damage to the mob as well.

Not a great example, but somewhere, mutex's have to be put into play to avoid partial effects that aren't intended.

The real cost though, is in debugging.

Have you ever debugged a multi-threaded application?  It's not pretty, and even when you lock things down in gdb, it's still a pain to have to flip back and forth between threads to look at the states of everything and figure out which part is firing out of sequence.  Without a real debugger that can step through LPC code in multiple threads (and how would you do THAT in a live mud?), it would be down to debugging statements and timestamps.

So, the question is.... is there ANYTHING you've ever tried to do in a mud which has ever come even close to hitting the CPU limit of a reasonable machine these days?  If the answer is no, don't even worry about multi-threading at that level.

If you just want to do some multi-threaded programming... how about a database script which handles transactions between lpc threads as an external proxy?  The discworld folks are using sockets to do their database activity through a python script instead of trying to get the MudOS driver to do it... a multi-threaded version of that might be pretty cool.

Offline Tricky

  • BFF
  • ***
  • Posts: 189
  • I like what I code and I code what I like!
    • View Profile
Re: multi-threaded versus single threaded mud servers
« Reply #6 on: September 19, 2007, 06:28:22 pm »
In a multi-threaded interpreter, if you don't mutex lock the combat events, one thread may start doing the attack, get to the part where it gives you damage... then the spell thread goes through... then perhaps the attack thread picks up and sees there's a spell effect, and does the damage to the mob as well.

Get it right and you could have each player/NPC killing each other at the same time. :)

Tricky

Offline silenus

  • BFF
  • ***
  • Posts: 199
    • View Profile
Re: multi-threaded versus single threaded mud servers
« Reply #7 on: September 19, 2007, 07:46:23 pm »
Yes I have done some debugging of multi-threaded code and from my limited experience it's not pleasant. On a multicore platform even reproducing the error could be problematic since it might depend on if and when the thread of execution A executes instruction X relative to when thread of execution B does so.

I think someone published a paper call the problem with threads indicating that the amount of nondeterminism in the threading model makes coding of such systems in general perhaps too difficult and hard to debug. The thing I have been trying to look at is are there other types of parallel models or ways to make these sorts of things easier to debug before selecting to implement them into a mud server design.

My understanding is that certain languages have better built-in primitives than threads that could perhaps help alleviate some of the problems of programming in a thread model. Erlang again perhaps but I have yet to explore this avenue.

As to whether you can hit the CPU ceiling- I feel there are certain things you can do on a mud which are quite CPU intensive. One example is certain forms of pathfinding via A* which I find consumes alot of CPU time. I could think of other usages such as minimaxing AI's for combat etc. depending on the combat model and so on.


Offline daelaskai

  • BFF
  • ***
  • Posts: 174
    • View Profile
Re: multi-threaded versus single threaded mud servers
« Reply #8 on: September 19, 2007, 08:31:18 pm »
I'm sure there will some speed up in other areas as there will be many objects that are dealing with different things in different areas, for example a weather daemon has nothing to do with combat and so can they can quite happily do there own thing independently of each other. Of course this assumes that the code is executed in a parallel fashion.

As for the Dragon's Dinner, read up on threads and mutex semaphores. The door object can be locked (not in the key locking type of way) to prevent other objects from accessing the door data.

Tricky

I don't know what mutex semaphores or anything else is but I agree that for daemons such as weather or data collection (my roster command for instance) could be done as a separate thread.  It would also be interesting to know if someone could define a type of user object that works on the second thread, such as have players on one thread and admin/wizards on another.  I don't have a firm grasp on multi-threading so I could be way off base and misinterpreting what is being discussed here and if that is the case, I apologize in advance.

Daelas@Neverland

Offline daelaskai

  • BFF
  • ***
  • Posts: 174
    • View Profile
Re: multi-threaded versus single threaded mud servers
« Reply #9 on: September 19, 2007, 08:36:16 pm »
P.S. Would this in any way be possible for router/intermud or other communications?  Chat daemons and getting room descriptions and things like that too.  I don't know how much (if any) intermud communications or OOB mail and stuff affects the MUD.  The Liveupgrade system could be a perfect example of something that can be done on a separate thread.

Daelas

Offline Tricky

  • BFF
  • ***
  • Posts: 189
  • I like what I code and I code what I like!
    • View Profile
Re: multi-threaded versus single threaded mud servers
« Reply #10 on: September 20, 2007, 12:29:46 pm »
Yes, putting the communications in a separate thread wouldn't hurt. I'm sure Crat would agree if it helped to take some of the load off of the router. For that to really work well a separate messaging system would need to be designed for each of the threads to "talk" with each other.

In a way this is getting in to the realms of designing the driver as though it was an operating system. Look at what your box is doing right now. It is doing far more than the mud driver you are using at the moment, in fact it is running your mud driver and a whole suite of other things.

If Java can run things fast as byte compiled code, so can LPC.

Tricky

Offline wodan

  • BFF
  • ***
  • Posts: 434
  • Drink and code, you know you want to!
    • View Profile
Re: multi-threaded versus single threaded mud servers
« Reply #11 on: February 15, 2008, 05:03:34 pm »
there's a very good reason for never adding explicit threads to LPC...
most mud coders don't know anything about coding, and even less about threads, your mud would deadlock in no time at all :)


Offline chaos

  • BFF
  • ***
  • Posts: 291
  • Job, school, social life, sleep. Pick 2.5.
    • View Profile
    • Lost Souls
Re: multi-threaded versus single threaded mud servers
« Reply #12 on: February 16, 2008, 09:42:29 am »
I feel like I should expand on the deadlock thing a little further for the sake of the enthusiastic, since once upon a time one of my guys was all "hey, we should do threads!" with a proposed model that would be unskilled-developer-friendly because threads would automatically lock any objects they touched, and I had to introduce him to the concept of deadlock.  Which is more or less the last I ever heard from him...

Deadlock takes place like this.  Thread X has a lock on object A.  Thread Y has a lock on object B.  Thread X requests a lock on object B, and cannot proceed because object B is locked by thread Y.  Thread Y requests a lock on object A, and cannot proceed because object A is locked by thread X.  Both threads now wait for a lock until Ragnarok.

This will happen in any model where a thread can own more than one lock, or change a lock without releasing it.  (A deadlock-free thread model only allows you to own one lock, which cannot be changed without releasing it, so in order to lock additional resources, you have to release your lock and so allow other threads to lock what you had.  This is how MySQL addresses deadlock.  It works, but requires considerably more programmer skill in order to have your locking actually achieve its purpose.)  There is also such a thing as deadlock detection and resolution.  That's a black art unto itself, and as far as I know, it inescapably requires violating the intent of at least one of the locks involved.

In any event, it's an issue one can deal with, but anyone who's going to go down these roads had better be aware of it.

Offline silenus

  • BFF
  • ***
  • Posts: 199
    • View Profile
Re: multi-threaded versus single threaded mud servers
« Reply #13 on: February 16, 2008, 10:25:29 am »
I think introducing concurrency in some fashion has some merits but as noted the complexity involved in debugging multithreaded code and getting it right is quite difficult and alot of mud programmers might not have the skills or patience for it.

I guess since I started this my ideas have slowly changed. Originally I intended to write something which would be significantly different than LPC- but at least for the moment I find myself moving closer to something that resembles LPC.

I somewhat fancy the message passing semantics of Erlang (in most cases I assume one isnt passing aroun d huge quantities of data) which would basically turn objects into "micro" processes. I was wondering if an approach like this might be viable if one were to construct a fully multi-threaded VM + language.








Offline quixadhal

  • BFF
  • ***
  • Posts: 642
    • View Profile
    • WileyMUD
Re: multi-threaded versus single threaded mud servers
« Reply #14 on: February 17, 2008, 11:57:25 am »
The real problem with designing a game to be multi-threaded is how to partition the data, and how to partition the access to that data so that you aren't spending all your time and resources checking locks.

Most games that claim to be multi-threaded only say this because they've partitioned a few very specialized bits off into seperate threads.  A game like WoW, for example, has a farm of login servers which only access the accounting database (for user/password/account-active data), and probably a proxy server (which is connected the all the world servers to show which ones are up or down, and what their load is).  Once you log in, you get handed off to the world server of your choice, and it accesses your character data and another server to get zone information.  When you've picked a character, you are handed off to the zone server that's currently handling the zone you were last in.  At THAT point, you start getting information about the things around you.

That zone server is essentially the only thing that really knows anything about gameplay.  I would suspect it is multi-threaded, but not in the way we keep dreaming about.  Rather, there is probably a thread for each socket connection which just handles communication between the clients (chat channels are run on another seperate server, I'm talking when you hit 'w', the client sends a 'user-started-moving-forward' command).  There's probably a thread to handle database access (so the server doesn't need to wait for it).  Beyond that, there *might* be a thread to handle periodic effects wearing off (or being applied)... but unless all it does is decrement a counter and then let the main thread actually jiggle the numbers, every spot in the combat code would have to mutex-lock to avoid doing double damage at the moment your double-damage mod expired.

The other problem is that the server has to access quite a bit of data.  You might want each NPC or player to have a seperate thread, but then every time they interact with each other, or the world has to interact with several at once, you have to ensure locking again.

Consider.  Your player object sends a "cast fireball" message to the room object.  Now the room object has to mutex lock every player and NPC in the room to ensure that they all are frozen in place, and that all their various resistances don't change, while it calculates who gets hit, how much they get hit for, deducts the damage, and then checks for retaliatory triggers such as fireshield (which would automatically launch a counter-attack at the caster), and queues their messages up.  Now, you can release the locks.  In the middle of a large fight, you may have dozens of people using area effects, so any gains from concurrency get lost where you want them most.  Afterall, few people ever complain about lag when they're walking around the countryside by themselves.

Now, I will say that if you found a platform where all the locking was done transparently by the language itself, THEN it might indeed be worth writing a game with it.  I don't think things would run significantly slower with multi-threading, I just don't think they'll run any faster where you really want them to run faster.  If your code doesn't have to, itself, do the lock checking, the simplicity might be worth it.

You might want to check with Dworkin and the DGD folks to see what they're up to.  I know he was working on DGD-MP, which was meant to be a multi-processor driver, and I also know it isn't ready yet.  DGD already has the idea of atomic operations which either succeed or get rolled-back even if the LPC thread (non-concurrent) gets suspended.  I'm sure he can give you some pointers for just what kind of worms you're likely to encounter if you walk the paths of concurrency. :)