[MUD-Dev] World Persistence, flat files v/s DB v/s ??

[J C Lawrence]

On Tue, 24 Mar 1998 21:42:41 PST8PDT 
Vadim Tkachenko<vt at freehold.crocodile.org> wrote:
> Chris Gray wrote:
>> [Vadim Tkachenko:]

>> Some potential problems:
>> 
>> - if multiple threads are updating the single image of the DB
>> (whether those threads are local or remote), then you need some
>> kind of consistency mechanism. If you use locks, then you are
>> vulnerable to a client vanishing when it holds locks - you will
>> have to detect that and rip the locks away.

> Sure, that's why there is a concept of a business logic - client
> doesn't hold any locks at all. Everything is split into
> transactions, and any possible locks are handled by the business
> logic.

Most (I'm pretty sure all but one?) transaction models require locks.
If you don't take the roll-back approach I use, then then you are
going to have locks, no matter how you try and wrap or re-phrase it.

> When the client dies, there are two possibilities - one, it drops
> the connection, which automatically leads to the IOException and
> depending on the higher-level protocol handling it's either
> disconnected or put into the linkdead state. Two, it lags out, which
> is worse but can be handled somehow - any comments on this case?

Given that TCP/IP has no concept of link state maintenance (at least
not in the same way as the SNA world where you'll know within 3ms if
the other end goes way or if anything at _ALL_ happens to the
connection), this makes for a latency problem: How to tell if the
other end is just being slow, or has gone away?  Do you postpone later
dependant transactions until you have determined the state of the
connection (expensive if by timeout) or do you just proceed willy
nilly and attempt to figure out how to recover if it then turns out
that the other end really did go away (logical dependency nightmare).

>> This also means that your execution model has to be very complete
>> with respect to locks,

> Always :-)

Then again, you can always use a lockless model, which has other
expenses, and tends to require a lot more rigour in your world design.

>> With remotely held locks, you can get some *very* large latencies.

> Never have the remotely held locks, then :-)

Okay.  How?

>> Alternatively, you might try Chris L's lockless scheme, or some
>> variant.

> What is that? Can you give me a reference, please?

Its not original to me.  I copied it in turn from Demo's DOME project
(http://autos.cs.tu-berlin.de/~demos/dome.html).  The basic model is
well known in the DB world, and has been hashed and rehashed here many
many times.

LING: Demo's DOME project should be in the FAQ, as should the
description of the lockless model, and the dragon's dinner scenario
quoted below should be inserted into the definitions part of the FAQ
whole cloth.

-<cut>-

A Lockless Server or DB design
------------------------------

Events request objects from the DB.  

If the object is not in the cache, the DB loads the object.

The DB replies to the event with a read-only shared reference to the
object.

The event is added to the "interested parties" list for the object.

If the event attempts to modify the object, a new local,
event-specific copy of the object is made, and the changes are made to
that.  A copy of the original reference however is still kept.

The event (loosely) attempts to keep track of what members of the
object it referenced.

During the execution of an event. all external IO is buffered and held.

Upon the event terminating it compares its copy of the original object
(the local reference) with the object that's actually in the DB (may
have been changed by events commiting during the current event's
execution).  Some intelligence is attempted here to only compare those
values etc which were referenced by the event.

Should the original copy and the current-in-DB copy compare OK, then
the event commits, the IO is released, and all its changes in its
written-to copies are commited atomically.  This is the
Compare&Commit, or C&C.

If the C&C fails, the event is thrown away, all the copies are
released, the IO is discarded, and the event is rescheduled to try
again.

There is also some background intelligence here where the DB watches
the objects that are affected by event's C&C'ing, and will signal the
other events that are members of those object's interested party list
that they may be invalidated by the other event's C&C and so should
kill themselves and reschedule.

-<cut>-

Background data:

-<cut>-

            /(o__.       _____|  \                     |OcO|
 ---------/|-/|-(  ,__)-------|    |   |--------+++++++++/|_| - |_ -----------
       /\/ |/ |/ _ \++++++C+O+M+P+L|E+X+I+T+Y+++++O+F+++/f|  `-'  |
    |\/         / \/      "++++++D+|+S+T+R+I+B+U+T+E+D+( u|       |
 ___| . .____. /______________|   "|++++++S+Y+S+T+E+M+S+\n|_)___(_/-----------
  _| /| |_  || |_             |____|   |        "++++++++\| | | | \
 /__/LL__,) LL__,)                 |  /                    (__|__) \

Pretty picture depicting the famous `` Dragon's Dinner'' problem, by
Jutta Degener. 

The Dragon's dinner problem
---------------------------

One of the original goals for the DOME project was to provide a
parallel/distributed execution envirionment for an LPmud game
driver. LPmud is programmed in a langauge called LPC, which is derived
from C and enriched with constructs to enable object oriented
programming, complex data types such as associative arrays and lambda
closures. This is interpreted by the game driver which provides single
threaded execution semantics.  Items in the game are represented by
LPC objects which provide methods specifiying how they interact with
other objects in the game.

Consider the following problem (dubbed "Dragon's Dinner"). Assume, in
an asynchronous distributed system, that there are two room objects
(r1, r2) and a door object (d) that connects them. R1 contains a
hungry dragon (hd) and r2 contains an adventurer (a). The door is
currently open, the adventurer has just fled from r1 and is about to
close the door. The dragon, on the other hand, wants to go after the
adventurer. Code for the dragon is something like:

        if (d->is_open())
                hd->move_to(r2);

And the code for closing the door is something like:

        d->close();

Now what if the following happens: The thread that executes the
dragon's action has checked that the door is indeed open, while the
other thread which is concurrently executing on a different processor,
closes the door. This succeeds and the adventurer sees the door
closing. However, when control returns to the dragon's thread, it
still believes that the door is open and steps through it, much to the
surprise of the adventurer who sees the dragon walking through a
closed door, before being devoured by the dragon.

Naturally this is merely a race-condition dictated by the asynchronous
execution of two data-dependent threads. The main goal of the DOME
project is to provide a system where the component objects can be
programmed in a sequential fashion, but have the run-time support
resolve such race-conditions (in a deadlock free manner) so that
parallel execution can be achieved.

Alexander Weidt [June 1995] 

-<cut>-

<sigh> Once I get the web archives up, we'll be quoting URL's here
instead of text blob's, or more likely pithy statements to the effect
of, "Read The F'ing Archives on XXX!".  I'm not sure if that's a good
thing tho.  It does increase signal, but removes context from readers
unfamiliar with the prior traffic (ie it requires significantly more
work of them to maintain context).  Hurm.  Methinks I prefer text over
external references.

>> In either case, information generated by a thread run often
>> produces output that must go to several clients. Does each client
>> know about all other clients, and so can send directly, or does
>> that information have to bounce through the server?

> I'd probably have a special kind of 'broadcast handler' business
> logic (BL) to do that (as I mentioned before, the BL adaptors are
> stackable, and there may be three ways of handling the request by
> the BL adaptor:

Note that your handling of IO is heavily dependant on your
transactional model.  No matter what model you adapt however, you
*CAN'T* deliver IO from a transaction until after that transaction
commits.  After all, you can't rollback IO...

>> - threads often need a fair amount of context (mostly read-only) to
>> run.  Getting the up-to-date version of that to the clients can up
>> your latency quite a bit. You can cache information like that on
>> the clients, but see recent discussion on that for some hazards.

> Can't answer this yet, the first thought is that I try to follow the
> MVC paradigm, and everything on the other end of the connection is
> either V or C for me, so all the data you're talking about here will
> probably end up in the BLs on the server side.

The MVC model assumes a high bandwidth connection between M, V, and C.
Yes, this can be worked around.  No, I don't think its worth it as you
end up working extremely hard in order to preserve a model which is
not suited (at that purity level) for the application.  its much
easier to put cacheing and other state concepts into each layer (M, V,
and C) in order to minimise the bandwidth requirements of
synchronising the data transfers between them.

--
J C Lawrence                               Internet: claw at null.net
(Contractor)                               Internet: coder at ibm.net
---------(*)                     Internet: claw at under.engr.sgi.com
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...