[MUD-Dev] TECH: Distributed Muds

[Eli Stevens]

----- Original Message -----
From: "J C Lawrence" <claw at 2wire.com>
To: <mud-dev at kanga.nu>
Sent: Friday, April 27, 2001 12:27 AM
Subject: Re: [MUD-Dev] Re: TECH: Distributed Muds


> Why design your model so that the incremental unit in the working
> set definition is so large as a zone?  What if the bas (world)
> incremental unit was smaller, perhaps even at the individual object
> level?

...

I had been wondering about this myself.  Unfortunately, my relative
inexperience with large scale systems make my ponderings less useful
than they might be.  Still, what I had been thinking seems to match
your question somewhat.  :)

So...  Am I an idiot?  Would this work well?  At all?

Suppose that the world is divided up into tiles that are a significant
fraction of the average character's perception distance to some level
of detail (perhaps at 300 feet avatars can recognize faces, so the
tiles are 300 square feet).  The size of the tile should be limited by
the pessimal case (say, wall to wall people all casting fireballs at
maximum range), to insure that a server can always handle the events
in at least one tile, no matter what.  The events in each tile are
totally deterministic.  Given an initial state and a series of
happenings and the exact time of their occurrence, it is possible to
compute the current world state precisely.  A backlog of a few seconds
is kept in case events arrive out of order, etc.

Each member of the server farm subscribes to the happenings of one or
more tiles at one of two levels of interest.  A server that is
"responsible" for a tile computes everything pertinent to that tile,
including effects that may originate from other tiles, what characters
can perceive from other tiles, etc.  Servers that are "interested" in
a tile only care about the effects that can be perceived from the
tiles that the server is responsible for.  A server can both decide to
become interested in a tile based on actions originating from its
responsible set, and because of events originating outside of the
responsible / interested set.  Most likely, interest level would
actually be some sort of gross to fine scale, to account for distance
and observability.

  Examples: any servers responsible for a character looking through a
  crystal ball would become interested in the location of the scrying
  target.  Similarly, if a balista crew on the other side of a hill
  started launching missiles at the above gypsy, then the servers
  responsible for the gypsy's tile would become interested in the tile
  on the other side of the hill.

Multiple servers would routinely be responsible for the same tile.
When a server's load increased to a point that would be in danger of
lagging, tiles with shared responsibility would be dropped.
Conversely, if a server was idling, it would pick up other tiles until
its load was acceptable.

Capitals indicate responsibility, lowercase indicate interest.
Servers A, B and C are online, although C is not responsible for or
interested in any tiles we are looking at currently.

       1   2   3   4
    1  A-- Ab- AB- aB-
    
    2  Ab- Ab- AB- aB-
    
    3  aB- aB- aB- -B-
    
    4  -B- -B- aB- -B-

The gypsy at row 1, col 2 is scrying (4, 3).  The city at (1, 1) is
busy, and is loading server A heavily, and so A decides to drop a few
tiles to make the load more manageable.  (1, 3) and (2, 3) are chosen
to be discarded, as the city spans the square from (1, 1) to (2, 2).

       1   2   3   4
    1  A-- Ab- aB- -B-

    2  Ab- Ab- aB- -B-
    
    3  aB- aB- -B- -B-
    
    4  -B- -B- aB- -B-

Now B's load is too high, as all but one square of the city is at
least on the interested list.  A third server, C, is entered into the
picture (presumably it was either waiting for a situation like this,
or was responsible for other areas of the world).


       1   2   3   4
    1  A-- Abc aBC -BC
    
    2  Ab- Abc aBC -BC
    
    3  aB- aB- -Bc -BC
    
    4  -B- -B- aBc -Bc

In response, B drops the upper right hand corner of the map to lessen
its memory load.

       1   2   3   4
    1  A-- A-c a-C --C
    
    2  Ab- Abc abC --C
    
    3  aB- aB- -Bc -bC
    
    4  -B- -B- aBc -Bc

And so on.

The result would hopefully be some servers clustering up around high
traffic areas, such as cities, with others spreading out over larger,
quieter areas such as forests.  The overlap rate should be fairly
high, so if a group of characters made a dash for the forest, the
server responsible for those tiles should be able to drop border tiles
fairly quickly to concentrate on the new activity.

Of course, there are problems with this approach.

  - When a highly intersecting dataset has to span two servers, the
  same information will be processed twice (at least), which will
  compound the problem of not having enough cycles / memory /bandwidth
  in the first place.

  - Bandwidth in general will be used heavily (the broadcast /
  multicast of events to all responsible / interested servers, the
  copying of tile state, etc.).

    - A fair amount of intelligence will have to be coded into the
    module responsible for making the loading decisions.  If it cannot
    handle every loading situation well, the game will fall apart
    sooner or later.  Even if it does handle everything without
    overloading a server, it will most likely not be an optimal
    workload distribution.

And many more I am sure.  :) But, I guess the question is, are any of
these enough to kill the idea, or would it work?  Well enough to be
worth it?

Dunno.
Eli

 ---
"Ultimately, if it is possible for a consumer to hear or see protected
 content, then it will be technically possible for the consumer to copy
 that content."
 --- Dr. Edward Felon




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