[MUD-Dev] Design patterns for game database implementations

[Caliban Tiresias Darklock]

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.

The obvious solution for the search is to use some simple and
well-known mechanism like a red-black tree, which can be used to
index the array by pointer to allow both operations in a reasonable
amount of time (retrieval by ID is O(1), retrieval by name is O(log2
n)). 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.

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. 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.

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. Right now, anything will work just fine --
the system is playable by only one player at a time, and only a
half-dozen or so players will exist. Even if I create a whole slew
of players automatically and scatter them around the game at random,
I'm just not going to get anything close to an accurate
representation of how the access pattern will really work until I
reach production. That's the WORST possible time to get your first
clear picture of how the data handling performs under real-world
conditions.

So what I'm wondering is, how have other people managed their game
databases, and what successes and failures have come to light in
those efforts?

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