[MUD-Dev] Design patterns for game database implementations

[Sean Kelly]

From: "Caliban Tiresias Darklock" <caliban at darklock.com>

> Here's something of a nuts-and-bolts problem I'm facing right now.

> My system's implementation (obviously) requires a database. That
> database needs a very very small set of functionality: "retrieve
> by ID" and "retrieve by type and name". The problem I'm hitting is
> that the complexity of the database is a middle-of-the-road
> problem: too much for a hand tool, but not enough to really
> justify a power tool. If I just read the files into arrays,
> retrieval by ID is simple but retrieval by name is pathological;
> if I sort the array by name, the reverse situation arises and
> insertions become problematic. On the other hand, if I use an
> industrial strength technology like GDBM or some variety of SQL
> database, about 98% of that technology is wasted.

MySQL is free.  So is PostgresSQL (?)  Though it sounds like what
you need could be solved by various STL containers (if you're a C++
person) -- either std::map or std::hash_map (for newer
implementations).

> The obvious solution for the search is to use some simple and
> well-known mechanism like a red-black tree

This is now std::map and std::set are generally implemented.

> This will work well enough for most of the world objects, but
> player records begin to represent a problem. Since a player record
> in my system consists of only about 200 bytes of information --
> login, password, character name, email address, and a few timer
> values for periodic player purges -- it doesn't make any sense to
> shove them into separate files, which will waste about 20 times
> the space due to cluster sizing. On the other hand, it's likely
> that there will be far too many of them to stick into an in-memory
> structure.

Could you use a hash or a tree (as above) to store an indicator of
which file the record is in?  Actually, if you had a good hash
algorithm, you could purposefully make the hash array a tad small
and represent each hash value as a file.  With any luck, you would
end up with an even distribution of player records in each file.
You could store the filename at the index location and even an
offset in the bucket along with a pointer.  If the class is there
then use it, otherwise load it from the file.

> What I'm considering right now is a basic index file -- ID, name,
> offset -- and some sort of auto-aging process to throw
> infrequently accessed records out of memory. (I figure most player
> records that don't belong to online players will be accessed in
> short flurries; a player or group will do some stuff with -- or to
> -- another player, and then be done with it.) That seems like the
> best solution so far, but I don't think it's really the *right*
> solution.

FIFO is a good way to manage user records.  You could do periodic
garbage collection of the hash table or maintain another index of
some sort that stored pointers to records by access time.  I guess
it depends on memory requirements and how you use the records.  I
wouldn't want to implement too fancy a solution if they're only 200
bytes or you'd end up wasting more space than you'd save.

> I've thought about several ways to handle this, ranging from the
> simple to the extreme, and none of them strike me as being
> "right". I have some vague idea that what I really want is a hash
> table, but then collision resolution becomes an issue and I'm not
> really sure which direction to go with that.

In the case I suggested above, you *want* collisions.  Implement the
hash table as the kind that has a linked-list at each hash value and
consider each list a file.

> The real problem here is that I *know* this problem has been
> solved already by any number of other people -- some well, some
> badly -- but I don't have any access to their previous
> experience. I know enough about basic data structures and
> algorithms to come up with a dozen different approaches to the
> problem, and implement all of them in less than a week. What I
> *don't* know is how other people have found various approaches to
> perform in the Real World, and that's the most important part.

Don't be so quick to dismiss SQL just because you think it's
overkill.  If you can get an implementation for free (like MySQL),
your only cost is the learning curve.

Sean

_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev