<!-- MHonArc v2.4.4 --> <!--X-Subject: Re: [MUD-Dev] C&C and Event Rescheduling --> <!--X-From-R13: pynjerapNphc.uc.pbz --> <!--X-Date: from major.globecomm.net [207.51.48.5] by in11.ibm.net id 869271971.46952-1 Sat Jul 19 00:26:11 1997 CUT --> <!--X-Message-Id: 199707190025.RAA09888#xsvr3,cup.hp.com --> <!--X-Content-Type: text/plain --> <!--X-Reference: 33CFCE6E.41C67EA6#iname,com --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, Re: [MUD-Dev] C&C and Event Rescheduling</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:clawrenc#cup,hp.com"> </head> <body background="/backgrounds/paperback.gif" bgcolor="#ffffff" text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000"> <font size="+4" color="#804040"> <strong><em>MUD-Dev<br>mailing list archive</em></strong> </font> <br> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] <br clear=all><hr> <!--X-Body-Begin--> <!--X-User-Header--> <!--X-User-Header-End--> <!--X-TopPNI--> Date: [ <a href="msg00203.html">Previous</a> | <a href="msg00205.html">Next</a> ] Thread: [ <a href="msg00200.html">Previous</a> | <a href="msg00228.html">Next</a> ] Index: [ <A HREF="author.html#00204">Author</A> | <A HREF="#00204">Date</A> | <A HREF="thread.html#00204">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>Re: [MUD-Dev] C&C and Event Rescheduling</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A></LI> <LI><em>Subject</em>: Re: [MUD-Dev] C&C and Event Rescheduling</LI> <LI><em>From</em>: <A HREF="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</A></LI> <LI><em>Date</em>: Fri, 18 Jul 97 14:59:23 -0700</LI> <LI><em>Reply-to</em>: <A HREF="mailto:claw#null,net">claw#null,net</A></LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> In <<A HREF="msg00200.html">33CFCE6E.41C67EA6#iname,com</A>>, on 07/18/97 at 01:22 PM, Shawn Halpenny <malachai#iname,com> said: >clawrenc#cup,hp.com wrote: >> In <<A HREF="msg00101.html">33C69FC6.41C67EA6#iname,com</A>>, on 07/11/97 >> at 02:07 PM, Shawn Halpenny <malachai#iname,com> said: ...model ellided... >> This is pretty well identical to my model. Concerns: >> >> Most events modify more than one object. eg Bubba (object X) moves >> from room A to room B. Minimally objects A, B, and X will be modified >> by this event (containment pointers/lists). >> >> How do you intend to handle the cases of an event requesting object >> Q just to check the value of a data member (ie no modification), where >> that data member has then been changed by the time the event commits >> (see the dragon's dinner example, and look at the door)? >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. Notes: Re: #2. I call this the "interested parties list". To me it communicates a bit better that this is a list of things that care about the state of the item. A moot point of course. 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. There is reason behind all this madness: It reduces the number of data copies needed for transactions. By using this sort of layered scheme I manage to delay making a copy of the object until I absolutely need one (ie someone has attempted to modify the object). I find that the majority of objects referenced by MUD events are actually only read, and not modified (all the flag, can-I-do-this, and state checks). Comparitively only a fraction of the total number of objects referenced by a typical events are actually modified by the event. 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. Re: #5 & #6. I call this stage the "Compare and Commit", or C&C or short. (I think I owe this tag to AlexO here on the list) 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. Concern: An event generated IO. How do you handle when it reschedules? Think about things like SAY, TELL, LOOK, etc for example cases. >This with the intent that all clients (usually events, in this case) >will reschedule upon notification that their changes couldn't commit. Ack. >Step 7 is not entirely necessary, since after any change to O, all >clients using O will (when they terminate their processing and return >their OC' 's for commit) receive notification that what they did is >no longer applicable. Step 7 just lets them know about it sooner. The advantage of such early warning is that it allows a doomed event to recycle and possibly compleat sooner than if it had had to attempt to compleat, fail C&C, and reschedule. It adds a certain level of responsiveness to the system. >> Do you have a concept of a "transaction" where a transaction is >> effectively synonymous with an event, and involves the possible >> requesting of read-only copies of N objects, and the possible >> modification of M objects where M is a subset of N? What I'm looking >> for here is the idea that a transaction or event can only commit if >> all of its component objects resolve correctly to their commit state >> (ie everything compares right). >This is now the case: if one of those M objects has changed since an >event's beginning, reschedule that event since the data it has >already made a decision on may have changed (i.e. the door is shut >now so the dragon, who was moving through it, now has to reevaluate >its movement). Bingo. >I think that fits the above criteria. Yep. >> What about the case of an object with two attributes, say object A, >> with attributes A::X, and A::Y. Two events, Q and R, then occur. Q >> modifies the value of A::X. R modifies the value of A::Y. Both >> events run simultaneously and commit in arbitrary order. Should one >> event fail and be rescheduled? >Yes. The attributes that are read/written in A from Q and R are not >monitored by the DB, since the DB has no way of knowing what >attributes an event is going to access next. I'm partially thru splitting this as mentioned above so that the C&C only checks the specific object attributes and members which were referenced by the event in question. Reason: Unlike most standard (ie non-game real world) DB environments, MUD worlds tend to have many events all contending for a small number of objects while the rest of the DB/world remains unreferenced. This sort of C&C DB model is not optimised for this case. Consider the pessimal case of 50 players all standing in a single room A. All 50 decide to move west into the next room, B. Of a sudden, the objects for room A, room B, and the exits between A and B (if you have exits as objects), are all under heavy contention. Ever event is attempting to modify all the objects, and each one needs a clean cut at all of them to C&C. The result is that almost all the events are going to end up failing C&C at least once (one will make it thru the door and the rest will fail as they note that the current room, and target room are now changed as they have different contents lists), and rescheduling various numbers of times until the finally make it thru C&C. The result is that the events get done in slow motion as they start, fail/reschedule/fail/reschedule/fail...and finally compleat. Okay, 50 players in a room all moving west is unlikely. How about 50 players in or near a room, some moving out the various doors, some coming back into the room having left, others picking up or dropping various objects (changes to the contents lists), Every single event is now compeating for the chance to get a single unmodified copy of that room when it C&C's. Now that I've cast doom and gloom. This need not be a huge problem. The fix is to change the manner in which you write events/transactions. The requirement is to split events into the smallest, fastest executing, logically consistant units you can. The idea is that by making the runtime of an individual event as short oas possible the chance of collision by other events is minimised. Further, by making the runtime short, the probability is that what a given event sequence contends with on its first step will not be contended for on its next step. eg: 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. This is also not a wonderful example to work this area with. The TELL verb gives a good case: Worst possible TELL implementation: The TELL verb attempts to put IO to every single player object in the game. It's almost never going to work. At least one of the players in the entire list of players on the game is going to have changed during the execution of the verb, the verb will fail, and it will have to reschedule and try again. and fail, retry etc. Possibly decent TELL implementation: The TELL verb sends a message to a root "TELL" object with the IO for the TELL. The root "TELL" object spawns events, perhaps one per player, or one per small group or list of players (there are advantages to both models), where each event passes on the message to its target player(s) only. 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. >[ how to prevent events from starving ] >> I don't have a pure solution. I (rough memory) follow the following >> course: >> >> A rescheduled event is given a higher than default priority. All >> this means is that it gets first crack at getting a thread to execute >> on as versus a "normal" event which will have to wait until all >> higher-priority events have threads. >> >> A 5*rescheduled event forces the Executor to cease assigning events >> to threads until the 5*rescheduled event terminates. >> >> A 10*rescheduled event (I think its 10) forces the Executor to cease >> assigning events to threads until the 10*rescheduled event >> successfully terminates (ie it heads toward and finally goes into >> single-tasking mode). >> >> A 20*rescheduled event (have no idea what the real number is) >> signals all other executing events to block until this event has >> terminated. This just shuts down the multi-threading until the event >> has run. >Ahh. I had settled on using execution priorities as well, but not >quite like this. I don't think I'll keep track of the number of >times an event has been rescheduled. I don't actoually keep track of the number of reschedules directly. The priority level keeps incrementing, and that in turn (reasonably well) maps directly to the number of reschedules. Note: Almost all events come in at a standardised low priority. A very few events are authorised to come in at a higher priority. As such the priority level is not an exact measure of the reschedule count, but in practice I don't care. The fact that a high priority event has problems C&C'ing is just as significant as an originally low priority event now at the same priority level thru rescheduling having C&C problems. >Instead, I've a fixed number of >possible priorities, with the top one reserved for internal use. An >event will have its priority increased each time it is rescheduled. >If it reaches the top priority, it is run to completion before any >further event processing. If you think about it, this is almost exactly the same model. >> 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. -- J C Lawrence Internet: claw#null,net (Contractor) Internet: coder#ibm,net ---------------(*) Internet: clawrenc#cup,hp.com ...Honorary Member Clan McFUD -- Teamer's Avenging Monolith... </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <ul compact><li><strong>Follow-Ups</strong>: <ul> <li><strong><A NAME="00228" HREF="msg00228.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></strong> <ul compact><li><em>From:</em> Shawn Halpenny <malachai#iname,com></li></ul> </UL></LI></UL> <!--X-Follow-Ups-End--> <!--X-References--> <UL><LI><STRONG>References</STRONG>: <UL> <LI><STRONG><A NAME="00200" HREF="msg00200.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></STRONG> <UL><LI><EM>From:</EM> Shawn Halpenny <malachai#iname,com></LI></UL></LI> </UL></LI></UL> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00203.html">Re: [MUD-Dev] META: Making the list public?</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00205.html">Graphical MUDs</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00200.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00228.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00204"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00204"><STRONG>Thread</STRONG></A></LI> </UL> </LI> </UL> <!--X-BotPNI-End--> <!--X-User-Footer--> <!--X-User-Footer-End--> <ul><li>Thread context: <BLOCKQUOTE><UL> <LI><strong><A NAME="00101" HREF="msg00101.html">C&C and Event Rescheduling</A></strong>, Shawn Halpenny <a href="mailto:malachai#iname,com">malachai#iname,com</a>, Sat 12 Jul 1997, 04:04 GMT <UL> <LI><strong><A NAME="00151" HREF="msg00151.html">Re: [MUD-Dev] META: C&C and Event Rescheduling</A></strong>, clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Thu 17 Jul 1997, 03:13 GMT </LI> <LI><strong><A NAME="00152" HREF="msg00152.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></strong>, clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Thu 17 Jul 1997, 03:33 GMT <UL> <LI><strong><A NAME="00200" HREF="msg00200.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></strong>, Shawn Halpenny <a href="mailto:malachai#iname,com">malachai#iname,com</a>, Sat 19 Jul 1997, 03:13 GMT <UL> <LI><strong><A NAME="00204" HREF="msg00204.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></strong>, clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Sat 19 Jul 1997, 07:26 GMT <UL> <LI><strong><A NAME="00228" HREF="msg00228.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></strong>, Shawn Halpenny <a href="mailto:malachai#iname,com">malachai#iname,com</a>, Thu 24 Jul 1997, 00:21 GMT <UL> <LI><strong><A NAME="00235" HREF="msg00235.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></strong>, clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Fri 25 Jul 1997, 08:17 GMT <UL> <LI><strong><A NAME="00242" HREF="msg00242.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></strong>, Shawn Halpenny <a href="mailto:malachai#iname,com">malachai#iname,com</a>, Sat 26 Jul 1997, 00:14 GMT <UL> <LI><strong><A NAME="00278" HREF="msg00278.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></strong>, clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Wed 30 Jul 1997, 06:09 GMT </LI> </UL> </LI> </UL> </LI> </UL> </LI> </UL> </LI> </UL> </LI> </UL> </LI> </UL> </LI> </UL></BLOCKQUOTE> </ul> <hr> <center> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] </center> <hr> </body> </html>