[MUD-Dev] Distributed Processing

[John Buehler]

Jeremy Gaffney writes:

> Distributed processing on MUDs/MMPs is a generically interesting
> proposition, but what you will find after examining the problem for
> a while is that your theoretical bottleneck is provably not CPU
> load, memory usage, or any per-machine spec, but rather inter-server
> bandwidth (especially user-MUX-DEMUX) for any interesting
> application.

Yup, I'm aware of that.  Thus the references to relying on separation
of object definitions so that pertinent data is already resident with
the machine that needs it.  Machines such as the 'location' servers
will be handling massive amounts of dynamic data that other machines
will require, and the trigger mechanism is an attempt at reducing the
frequency of updates to those machines.  In other words, the smell
machine may only be interested in hearing updates about movement of
interesting objects when they move more than 100 feet closer or
farther.

The point of the distribution mechanism is to keep data with the
algorithms that need it.  I may be underestimating the amount of
crosstalk that is the inevitable result.  I would think that updating
clients via the 56K pipe would be the real bottleneck.  As you
suggest, having a medieval town the size of 12th century Norfolk would
produce a lot of dynamic activity around any given character.  Even
the position updates of visible characters might prove prohibitive.
Broadband may be required by clients.

> Unfortunately, doing a split by skills/algorithms means that you
> will rapidly have a case that is intractable in its usage of
> bandwidth (since presumably any geographical or character result of
> the skill usage will need to be sent to the server owning the
> area/character).

Results of skill usage typically only affect the data cross section
that is pertinent to that skill.  That means that the primary data
modifiations are to local data.  Getting the data scope of a skill
system correct would be critical to the success of this system.  That
is what keeps the amount of crosstalk between systems to a minimum.
The less a skill requires precise geographical data, the less it has
to have the geographic system contact it about pertinent changes.  The
less a skill requires knowledge of character attributes (e.g. weight),
the less it will need to be updated whenever the character picks up or
drops an item.

> However, each new piece of hardware needs to communicate with some
> subset of the other CPUs/boxes/etc (in implementation, this isn't
> always via network, but could be by shared busses, files, or other
> things) Thus, this communication (which in worst case is an O(n^2)
> proposition) is the one bottleneck which will prevent arbitrary
> growth.

That's the specific problem I'm trying to tackle.  The question is one
of whether skill systems can actually be substantially separated into
isolated 'universes' of data and algorithms.

> In an optimally arranged setting, where each world server needs to
> talk to some small finite number (especially zero!) of other
> servers, if the communications path is shared with other servers
> communicating between themselves, it should become obvious that the
> shared pipe will become the single point of limitation - and, in
> fact, in every system I know running today, this would be the limit.
> If the communications path is not shared (i.e. each server has a
> devoted connection to each other server with which it needs to
> communicate) then how to distribute events or results to the clients
> of a given server is an interesting (though not intractable)
> proposition.

I have been assuming a mix, where greater demands requires more
specific treatment.

[EverQuest and Asheron's Call architecture comments]

One of the triggers for the idea was to seek out a cross section of
data and processing that was not geographically-aligned.

> Of course, a more challenging project is coming up with content to
> satisfy that many users.

Different problem, but one that I'm working on.  My first approach is
algorithmic generation of content, such as fractal terrain and so on.
Careful use of levels of detail as well, in order to select
intelligently among all that generated content.

> Or a system of socialization which provides sufficient organization
> to take us from our current "village" population levels up to a
> reasonable "city" population level without the game feeling too
> impersonal

Current games feel impersonal in any case.  You find your circle of
friends and you play with them.  This happens based on your
personality and your gaming goals.  I'm relying first and foremost on
providing more gaming goals.  Trades are viewed as a necessary evil in
many of these games, yet I'd like to make them completey on a par with
the combat aspects.  This means that many players that I would retain
would be interested in hanging out in town and socializing with people
there.  They'd be involved with their business or their craft.  Not
because they plan on becoming rich, raising an army and invading
another town, but because it's mildly entertaining and they can talk
with other players as they do it.  A bit like a fancy Microsoft Game
Zone, but with roleplaying opportunities, and a far richer multimedia
experience.

> Since the reason you'd look to a distributed system is to either get
> more people in a single shard, or more efficiently spread the load
> across an existing shard, I couldn't resist commenting - it's a
> fascinating problem, but unfortunately one that really warrants
> (IMO) examination after we solve the social/ content dilemmi.  If
> anyone invents a time machine, please go pop back to '94 and let me
> (and the other Turbinites of the time) know that - would have helped
> a lot. :)

There is also the pyschological dilemma, which you might include in
your social delimma.  What is a viable game structure that more
naturally draws players interested in being social, enjoying the game,
etc.  I am constantly reminded of the power of grief players and their
inevitable presence, yet I continue to work for some treatment of the
games that will either occupy the energies of grief players or permit
me to effectively remove them from the game environment.

> For those not dissuaded, you'll find that the dynamic load
> distribution problem reduces (if approached as a geometrical
> distribution) to a weighted edge graph cutting algorithm (weight
> being potential interserver traffic).

That would seem intuitive.

> This is an NP-complete algorithm, with some polynomial time
> approximations currently being examined in the distributed systems
> literature (based on what your edge weight approximation metric is,
> of course, which warrants a research paper in and of itself).  Given
> that you can have quite successful games without doing this (nasty,
> multi-year, bleeding-edge) research...  I might advise against doing
> it unless there is grant money involved.  Please do prove me wrong,
> however :)

I'd be happy to try.  I happen to have some 'grant' money available to
me, so I'll be occupying myself for a while.

> (Er, to summarize the above if it is unreadable technobabble (my
> fault, not yours!) - Dynamic load balancing is hard, both in CPU
> cost and brain strain.  But cool.  If you wanted to make a
> Gibson-style Cyberspace (i.e.  geographically distributed virtual
> space) you'll find it to be an identical problem, which is rather
> interesting.  So if you ignore me, and solve this, go make your MUD
> be the basis for the next rev of the WWW.:)

I am not considering geographically distributed compute servers, if
that seemed to be my intention.  I'm considering a room with racks of
machines using high speed, very local area technology.  Getting data
back to the clients is another problem.  I'm hoping to take so long
doing the job that we'll have more common broadband access by users :)

JB


_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev