[MUD-Dev] DBs and Events

[Felix A. Croes]

Nathan Yospe <yospe at hawaii.edu> wrote:
> On Tue, 10 Feb 1998, Greg Munt wrote:
> :On Tue, 10 Feb 1998, Nathan Yospe wrote:
>
> :> On Tue, 10 Feb 1998, Greg Munt wrote:
>
> :> :Also, any references to caches?
>
> :> Again, can't help you. I've done caches, but not for my mud... and there
> :> is such a broad spectrum of things that qualify as cache. Do you want to
> :> know more about cached in-memory storage for a disk-based DB? 
>
> :Yes.
>
> The best sources for this would be J C, any of the Cold people, or, if a
> member of the DGD development team is still around... was that the LPmud
> disk-based project?

There never actually was a DGD development team, unless a team can be
one person.  But yes, still here.

All data in DGD is local to objects.  Storage in the "swap file" is
allocated in sectors of a certain size; each object in the swap file
takes up at least one sector.  This imposes considerable overhead,
since not all sectors will be fully used, but it allows for sector
allocation and deletion to be O(1) operations.  Moreover, the sector
size can be set to (a power-of-two portion of) the filesystem sector
size.

When an object is loaded from the swap file, the relevant sectors are
loaded in the sector cache, which is organized as a FIFO queue with
a given maximum size.  Whenever a sector is accessed, it is placed at
the tail of the queue.  Sectors that drop off at the head are written
to the swap file if necessary, and then discarded from the queue.

>From the information in the sectors, the object is loaded in memory.
Only those parts that are actually used are loaded, so most objects
will be partially expanded.  Whenever a part is accessed that is
not yet in memory, the relevant sector is found (also a O(1)
operation) and loaded in the sector cache, after which the data
is extracted.  Data in sectors is stored in a packed format to
save space.

Objects in memory are linked in a priority queue.  Each time an
object is accessed, its priority increases, which may mean that
it changes places with one or more objects in front.  Every second
or so, a portion of objects at the head of the queue is swapped
out: the data of the object is written to one or more sectors,
and the in-memory copy of the object is discarded.  The portion
of objects that will be swapped out is fixed: for instance, if
the portion of objects swapped out is 1/100th, and there are
N objects in memory, N/100 will be swapped out.  This means
that there is always some swapping going on, unless there are
less than 100 objects in memory.

DGD's swap file is not actually a proper database, since it
doesn't contain enough information to restart the server with.
A proper database ("dump file" in DGD's terminology) is created
at a checkpoint: the swapfile is brought in a consistent state
by copying all new or changed objects back to it without actually
discarding them from memory, after which all dirty sectors in
the sector cache are written to the swapfile.  Thereafter,
some additional tables are quickly appended at the end of the
swapfile, and some header info is written to the first sector.
The swapfile is then renamed to the dump file, and a new
swapfile is then created by copying sectors from the dump file
at low priority.  In this fashion, a checkpoint can be performed
without forking, and without taking the mud down (it may take
only a few seconds, depending on the amount of objects in memory
and the size of the sector cache).

Felix Croes (DGD development team)