[MUD-Dev] C&C and Event Rescheduling

[Shawn Halpenny]

clawrenc at cup.hp.com wrote:
> 
> In <33CFCE6E.41C67EA6 at iname.com>, on 07/18/97
>    at 01:22 PM, Shawn Halpenny <malachai at iname.com> said:
> 
> >Yep, a slight change is necessary.  Now (and again, roughly):
> >1.  A client C requests object O from the database.
> >2.  Add C to list of clients using O.
> >3.  Return OC (a client-only copy of O) to C.
> >4.  A client D (which may or may not be the same as C, but is on the
> >    using-list for O) returns OC'.
> >5.  If O has not changed since D's request for it (a different client
> >    may have committed changes to O while D was processing), OC' is
> >    atomically committed to the database, replacing O.  D is removed
> >    from O's using-list.
> >6.  If O has changed since D's request for it, OC' is discarded and D
> >    receives notification that OC' couldn't commit.
> >7.  Clients in the using-list for O are asynchronously notified that
> >    O has changed.
> 
> Given that this basic pattern extend to all the objects which comprise
> a given event or transaction, this is identical in principle to my
> model.

It does govern all involved objects.

>   Re: #3.  I do some folding here, largely due to the fact that I
> haven't seperated my clients from my DB as thoroughly as you.  For me,
> upon a READ request for an object X I return a reference to the
> read-only copy of that object that's already in the DB cache.  If a
> transaction attempts to modify object X (remember, all it has is a
> read-only reference), then I make a writable transaction-specific copy
> (ie unique to that specific transaction) for the changes made by that
> transaction, and a seperate read-only copy of the original value of
> object X.  Then, when the transaction attempts to commit, the original
> copy is compared to the current copy, and if they match, the changed
> copy is committed.

This is a sensible optimization, and one I'll likely implement, since
my objects will already do it whenever one of them is duplicated
(completely external to the DB, since the objects can have their own
copy procedures, with the DB only supplying a new object ID and a
place to put the thing).  It is simple enough to move the
copy-on-write code up one level, from the objects into the DB.

>   Re: #5.  How do you determine that the object has changed during the
> execution of the event?  I do this by always keeping an original copy
> of the object to compare to the copy current in the DB and then do a
> bit-wise comparison of the two objects.  The original copy is the
> second copy made above for a modification.
>
>   Aside: I'm actually getting *slightly* neater than this as the
> current plan encludes only making a copy of the object
> attribute/member which is changed, and then only comparing that at
> C&C.

Right now, my design is to just do a bitwise comparison just like
above, but I'm also thinking of something involving an object
checksum of sorts computed when an object is committed.  Do your
events keep track of the attributes they touch or is that handled
entirely by the DB?  Is there a problem with a situation where a
single object with attributes touched by two events within the
duration of a third event using the same object could cause some
attributes touched by the third event to falsely pass the
comparison?

>   Re: #7.  Similarly I post messages (flags really) to all the members
> of the interested parties lists for all the objects that a
> successfully committed transaction modified.  The effect of those
> flags is that the next time those events traverse a block boundary
> (essentially any piece of code wrapped in {braces}, such as entering
> or leaving an IF, or WHILE etc), the flag gets checked and if TRUE,
> the event aborts to reschedule.

I do much the same, using the exception mechanism of the internal language.

> Concern:
> 
>   An event generated IO.  How do you handle when it reschedules?
> Think about things like SAY, TELL, LOOK, etc for example cases.

As of yet, I don't.  In the last few weeks I've been doing the "formal"
design of the base systems (network, DB, event handling).  Handling
commands where events that have to touch a number of objects that have
likely changed by the time the event is processed isn't something I've
worked on yet.  Therein lies the difficulty.

[ C&C based on touched attributes ]

[ large number of events contending for small number of objects resulting
  in slow-motion execution of the events as they all fail/retry ]

[ solution is to split events into small, fast units, touching as few
  objects as possible ]

>   Going back to the case of the two rooms A and B, and the 50 players
> moving between them.
> 
>   If you can, split your room/motion model so that moving between
> rooms requires two events:
> 
>   #1 Move out of current room.
> 
>   #2 After sucessfully doing #1, move into new room.
> 
> The question of course is "where" the player is having compleated #1,
> and processing on #2.  

Indeed.  What happens where an event occurs expecting Bubba to
be in a room, yet he is technically in between?


[ channel verbs are a similar case.  Perhaps use a root "tell" object that
spawns events to handle I/O to each player. ]

> Note: I dug into this TELL implemenation a while back on the list,
> along with details on how to handle channels, SAY, WHISPER etc
> efficiently in this sort of event driven C&C model.  If you want I'll
> try and dig it up.

If you could, thank you.  At the moment, I'm thinking along the lines of
the "tell" verb posting an event for each receiving player, rather than a
root object to handle it.

> > [JCL:]
> >> Note: Events have a very short maximum time they must execute within.
> >> Event's which take longer than that time are killed and not
> >> rescheduled.  This maximum time is reduced as events are rescheduled
> >> and ascend the above priority list (ie I give them more chance to get
> >> their job done, but less time to do it).
> 
> >Not so for me.  Am I missing something while standing here at the
> >drawing board? :)
> 
> Look at it this way:
> 
>   50 events are simultaneously executing on your server.  Under those
> conditions a new event X (say Bubba moving from room A to room B) can
> expect to compleat in T real world clock ticks.
> 
>   Due to rescheduling, priority levels, or just a paucity of events,
> there are no __NO__ events executing on your server.  Under those
> conditions a new event X (say Bubba moving from room A to room B) can
> expect to compleat in U real world clock ticks where U<T.
> 
> Part of my attention here is that I don't want events which are
> borderline on their time values managing to C&C only because they
> throw the system into single-threaded mode and then squeak thru
> because they have the whole damn CPU to themselves.
> 
> Note: A lot of this is obviated by hanging the way you measure an
> event's execution time.  I originally crafted the above schema when I
> was measuring event time in real world CPU clock ticks.  I have slated
> to change this to some sort of measurement of internal processing
> time, but have yet to come up with a decent system.

Can this sort of thing be remedied with smaller time units?  If
events can only begin execution on the edge of a tick, you'd likely
have more contention within each tick than with smaller granularity.

--
Shawn Halpenny

"It is impossible to make anything foolproof because fools are so
 ingenious."