[MUD-Dev] Collecting ideas for a MUD server... (fwd)

[J C Lawrence]

On Wed, 22 Dec 1999 21:54:37 -0500 (EST) 
Rahul Sinha <rsinha at glue.umd.edu> wrote:

> On Wed, 22 Dec 1999, J C Lawrence wrote:
>> On Wed, 22 Dec 1999 13:54:23 -0800 Justin Rogers
>> <justin at mlstoday.com> wrote:

> keep in mind, multiple threads ought not seperate themselves on
> seperate cpus due to cache coherency issues...

Careful there.  Cache coherency is important, yes, but depending on
the volatility of your working set flushing your local caches may
not be a significant factor in your general performance.  Given a
reasonably large and active world in fact, this is almost
guaranteed.

> the only reason to have threads is to eliminate wait for blocking
> operations. 

Not so fast.  That is one reason.  

One reason which I use is so that different operations may run
simultaneously at different process priorities.  Another reason is
to allow more fine grained process scaling on MP boxen.  Yet another
reason is to help give a facility to present a seemingly fine
cooperative grained parallel process model without actually having
to implement it or its complex lock semantics.  A yet further reason
is to gain the simplicity of inherently supporting the same data and
process model for local threaded operations as I do for distributed
processing operations.

> If you have one thread-per-zone, each thread can iterate across
> the actions provided by the users, and any blocking that needs be
> done (eg database access hits, which are fast, but if you want
> your ticks to be under a second, should be considered blocking
> operations) does not stop the entire program, the cpu can go work
> on another zone.

Ahem.  Consider the following, taken from a rather old post
describing my approach and minorly edited:

  The server itself knows nothing about the game it is representing.  It has
  no parser, game knowedge, or anything else application specific.  All it 
  does is represent a database and provide a scripting language.

  The database consists of records.  Each record defines an object in the 
  MUD world.  An object may have attributes, methods, verbs defined
  on it, an inheritance structure relating its content to other
  objects.

  The server is entirely event driven.  The definition of "event"
  below is not the typical systems definition of "event", but rather
  is used to reference an atomic processing action that occurs
  within the game-world's purview.  It is an "event" in the sense
  that it is a "happening", or an instance of a state change.

  Every event executes asynchronously in its own thread using a lockless 
  data model.

  I don't guarantee order of execution of two unrelated events.

  The server core consists of the following base units:
    -- DB
    -- Dispatchor
    -- Executor
    -- Connector

  The Dispatchor consists of two threads which own and operate the Event List.  

  The Event List contains an entry for every event which has been logged 
  with the system but not processed yet.  

  One thread in the dispatchor handles placement of new entries onto the 
  Event List.  The other thread processes the list looking for "ripe" events 
  (ie ones ready to be executed).

  Ripe events are sent to the Executor where they are placed in an Event 
  Queue.  The Event Queue is a priority queue with events ordered by their 
  own execution priority.

  The Executor manages the Event Pool, a local pool of threads (the number 
  dynamically grows and shrinks at runtime depending on load) which are used 
  to execute the events pulled off the Event Queue.  Threads in the Event Pool 
  are re-used to execute ripe events.

  Events are pulled off the Event Queue in priority order and handed to the 
  first available thread in the Event Pool.  

  Events that fail to commit are rescheduled with the Executor at a
  different priority and re-enter the priority queue and scheduling
  as appropriate.

  Event's have no effect upon the DB or state until and unless they
  commit. (see C&C and the lockless model in general)

  Compleated events can log futher/later events back to the Dispatchor for 
  subsequent animation.  This is how mobiles are animated for instance.
  
  User IO arrives thru the Connector.  The connector is essentially a pool of 
  threads which asynchronously manage the general pool of outside connections.  
  A seperate monitor is responsible for keeping the IO network tree happy.

  User commands arrive at the Connector and are immediately sent to the 
  Dispatchor as Execute-In-Zero-Time (ie no delay) events.  The event logged 
  is actually to parse the command as entered.  The dispatchor then routes 
  the event to the Executor, it runs the event and the resultant parse creates 
  a new event which is logged with the Dispatchor to actually execute the 
  intended action.  

You can read about the lockless DB model in the list archvies or the
list FAQ (recently posted).

> data coherency important, many threads accessing one datapoint
> bad.  

Amusingly for the general case the C&C model explicitly loses this
by making most data event-local.  Where you get nasty cache
contention is for actively referenced objects in the DB copy cache
that don't actually get modified by anyone -- but I don't seem to
run into that case too too much, especially given the fact that I'm
only running on 2-CPU boxes.

--
J C Lawrence                                 Home: claw at kanga.nu
----------(*)                              Other: coder at kanga.nu
--=| A man is as sane as he is dangerous to his environment |=--


_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev