arendjr, just keep in mind that using a database doesn't mean you have to query it at every turn. I am currently only using my PG-backed store for persistence. It was less work than rolling even a flatfile store. Especially given that Postgres handles I/O scheduling and has lots of great integrity/consistency checks built in. This is basically all there is to it: https://github.com/gtaylor/dott/blob/mas...

180 lines, of which 80-90 of those are comments and whitespace, my verbose indention, or other not strictly necessary stuff.

Well, you quoted 5 paragraphs, the fourth of which said this very important bit: When an event starts, you don't know in advance where it will end. This is why a spatial algorithm isn't gonna help you, as the result is not simply a function of distance. Distance is one of many factors, but even then I calculate travelled distance, rather than absolute distance. I also mentioned things like fog and line-of-sight. Again, the database is not going to do that for you. At the very best, you could use a spatial query as sort of prefetcher if you really insist on using databases, but by definition it would be either too optimistic (leading to additional queries during the algorithm) or too pessimistic (leading to overly large result sets and slower queries).

The funny thing about this thread is that it seems a lot of you would never consider the possibility of not using a database, thus making a database a requirement for your minimal viable product.

@Kelvin: You speak about 180 lines of code, of which 100 are highly relevant. I can post my relevant code, and you'll see it's about the same amount:

bool DiskUtil::writeFile(const QString &path, const QString &content) {

    QFile file(path);
    if (!file.open(QIODevice::WriteOnly)) {
        qWarning() << "Could not open file" << file.fileName() << "for writing.";
        return false;
    }

    file.write(content.toUtf8());
    file.flush();
#ifdef Q_OS_LINUX
    fdatasync(file.handle());
#else
    fsync(file.handle());
#endif
    return true;
}

bool DiskUtil::writeGameObject(const QString &objectType, uint id, const QString &content) {

    return writeFile(gameObjectPath(objectType, id), content);
}

QString DiskUtil::dataDir() {

    static QString path;
    static bool defined = false;

    if (!defined) {
        path = qgetenv("PT_DATA_DIR");
        defined = true;
    }
    return path;
}

QStringList DiskUtil::dataDirFileList(const QString &subdirectory) {

    QDir dir(DiskUtil::dataDir() + subdirectory);
    return dir.entryList(QDir::Files);
}

QString DiskUtil::gameObjectPath(const QString &objectType, uint id) {

    return dataDir() + QString("/%1.%2").arg(objectType.toLower()).arg(id, 9, 10, QChar('0'));
}

GameObject *GameObject::createFromFile(Realm *realm, const QString &path) {

    QFileInfo fileInfo(path);
    QString fileName = fileInfo.fileName();
    QStringList components = fileName.split('.');
    if (components.length() != 2) {
        throw GameException(GameException::InvalidGameObjectFileName);
    }

    QString objectType = Util::capitalize(components[0]);
    GameObject *gameObject = createByObjectType(realm, GameObjectType::fromString(objectType),
                                                       components[1].toUInt());
    gameObject->load(path);
    return gameObject;
}

void GameObject::load(const QString &path) {

    QFile file(path);
    if (!file.open(QIODevice::ReadOnly)) {
        throw GameException(GameException::CouldNotOpenGameObjectFile, path);
    }

    loadJson(file.readAll());
}

bool GameObject::save() {

    if (m_deleted) {
        bool result = QFile::remove(DiskUtil::gameObjectPath(m_objectType.toString(), m_id));

        m_realm->enqueueEvent(new DeleteObjectEvent(m_id));

        return result;
    } else {
        return DiskUtil::writeGameObject(m_objectType.toString(), m_id,
                                         toJsonString((Options) (SkipId | IncludeTypeInfo)));
    }
}

void Realm::init() {

    for (const QString &fileName : DiskUtil::dataDirFileList()) {
        if (!fileName.startsWith("realm.")) {
            createFromFile(this, DiskUtil::dataDir() + "/" + fileName);
        }
    }

    // […]
}

That's all. That code is responsible for loading and saving objects from/to disk. Given the amount of code involved, where is this magical time-saving element that makes databases a must-have?

Heh.. the magical time-saving element comes from indexing. It used to also come from the RDBMS doing a better job of delayed I/O and buffering than the OS, but that's probably a non-issue these days. :)

Also note, that while it's trivial to change your flat file structure to a database schema, and read/write objects to the database… that by itself doesn't buy you much. To really use SQL to your advantage, you have to have a schema that leaves your data accessible to SQL. That way, you can let the database handle validation (via constraint triggers) for you, and you can do complex queries to filter down to the result you want without having to read things in that you won't use.

You *COULD* accomplish your effect propogation in a database which allows stored procedures (PostgreSQL, and most of the higher-end non-free ones). Fog, door states, etc… *COULD* be accessible, and a query written with stored procedures to more dynamically filter the results would probably yield good results.

Is it worth doing so? Only if you plan it that way from the start *AND* you know your coders have a good solid handle on SQL. The downside of using SQL is that it's very easy to write VERY inefficient queries… and a single bad join can make a query that should have used 2M of RAM balloon out to 2G of RAM.

I think the magical effect of a database is that if you actually go to all the trouble of storing your entire game state in a database, presto… you have a viable, massively scalable MMORPG engine, on top of which you can run multiple multi-threaded front-end server instances, survive the crash of any front end server without losing player data, etc..

That's pretty magical.

And not true.

As soon as you start having an in-memory representation and doing tricks like long-running transactions to compensate for the overhead of the database you've limited yourself to a single instance. Even if you don't do that, running multiple instances will require you to use proper transactions for all updates, or else you might still find your instances overwriting each other's data. You will be confined to a single master database, which will immediately be your bottleneck because of all the locking you're going to do. An easy solution to that would be sharding by game area for example, but that's possible without a database too. No matter what technology you use, you should assume you *don't* have a viable, massively scalable anything until you've proven otherwise :)


@quixadhal: Yeah, I can understand that viewpoint. But I understand you wouldn't be using an in-memory representation then, right? My in-memory representation means I have barely any need for indices, and it will outperform a database hands down. So I'd rather implement everything directly in C++ with one memory model, rather than attempt the balancing act between C++ and SQL, and additionally maintain a database schema as well. But at that point it is pretty much personal preference of course :)

No, there is no need for an in-memory representation of game state. What I am speaking of is a completely different model. Game state is maintained strictly, completely, in a database. The front end parses player commands, queries that database, and issues atomic, transactional updates to the database. It has to deal with user facing issues such as parsing, character set translation, rewriting internal markup language into external presentation / HTML / Telnet / whatever. Possibly area data such as room descriptions, etc are cached, but every single bit of player or active mobile data is stored in the database.

The salient point is that if all game state is maintained in a single database, yes, the database is the bottleneck, but since the database provides the single transaction point, you are free to multi-thread or multi-server host above that database as you see fit.

Seeing as flash storage is becoming affordable now, and seeing as we can relax the guaranteed durability requirements of data a bit (after all this is games, not financial transactions), we are no longer limited by spindle speed here and the database model becomes attractive if you want to support scaling.

Personally, I see no need to scale to this level. But there are many reasons isolating the data inside an atomic transaction source, which is exactly what a database provides, makes it more feasible.

Ah, now you're back to maintaining all state in the database. It seems you're at least using the right model then if you want to have the possibility of having multiple server instances connect to your database :)
The problem is this model is much, much slower than an in-memory one.


Okay, so you say that yes, indeed you do have a bottleneck. For sure you are not massively scalable anymore. You may indeed have gained some limited scalability though, which might indeed give you some extra leeway to compensate with multiple server instances what a single server with an in-memory model could achieve. I realize we've come to a point where I won't be able to back this up with hard numbers, but don't expect your scalability to account for too much, and definitely not be "viable, massively scalable". It seems right here you have exactly fallen into the trap of over-engineering a distributed model without knowing what is necessary or what it's capabilities really are.

This is getting pretty silly. This database "bottleneck" isn't a bottleneck at all. Postgres, MySQL, or any number of other DB servers can and do run excellently under the kind of conditions we'd subject them to. It's not just relational DBs, either, so let's discard the jabbering about SQL.

The flatfile approach is just re-inventing the DB/doc store wheel, but worse. You have no transactions, you are not atomic, you don't get some of the consistency checks that a DB server does to prevent issues, and you have no sane means of replication or failover.

It's OK to be "worse", just don't try to paint it as the better way to go. The DB/doc store approach has its own characteristics, but let's not pretend that the flat file approach is better at all (it isn't, at best it is about the same for a MUD). If you're not writing anything superior, and you're not saving any time, the flatfile approach fails the "MVP check" mentioned in the article.

It is if you're trying to create a "viable, massively scalable MMORPG engine" as Telgar was arguing. But I agree it's a hypothetical argument, if that's what you're saying :)


I'm not arguing that flat files are superior (they're not). What I'm arguing is two things:
- We don't need the vast majority of what a database offers. We don't need transactions, nor do we need atomicity (as there's typically one game thread anyway). You only need a minimum of consistency checks, no database required. You don't need replication, as you'll have a single master setup anyway. Failover could be an argument, but hands up anyone who uses it…
- An in-memory model has much higher performance than using an external database.


If you don't require any of the features you claim you do, and you're not saving any time, the database approach fails the "MVP check" mentioned in the article.

Very much disagree. If it requires no additional effort to future-proof yourself, and the two choices require about the same amount of initial effort, why not go the more future-proof route? Running into issues in the future due to limitations of the flatfile approach actually fails the MVP check, in that it's a preventable sidetrack into something unnecessary (fixing a flawed, re-invented wheel).

Okay, that's a fair question. I think it can be summarized as follows:

• Before I started I set myself a number of targets towards which I wanted to be able to scale. I want to support worlds up to 1,000,000 rooms big, and I want to support at least 100 *concurrent* players. Of course I currently have nowhere near these numbers, but that's what I'm aiming for. I realized that as long as my implementation was sufficiently efficient, this can be done with just a single server. So according to the targets I set myself I'm as scalable as need be. I explicitly wanted to avoid any additional complexity that might be necessary for anything beyond the targets I won't reach in a long time.


• Getting good performance to support many concurrent players was an explicit objective, which is _part of_ the reason I chose to implement the core server is C++ and why I use an in-memory model.


• Given that I use an in-memory model, many scalability advantages that would have resulted from using a database are already nullified. So I really had no use for a database other than its storage layer. As you can see higher up in the thread, the storage layer is trivial enough and no more effort than integrating a database in the first place. In addition, not using a database means fewer dependencies, easier setup and I save myself the work of maintaining a database schema. Finally there's the advantage where my storage format now plays nice with version control.

I hope you will understand that the steps I took are very much like the MVP check in the article. I set my targets and I decided upon my requirements, and I made a design that would accomplish this and leave out unneeded complexities. The way I approached this I figured a database was an unwanted complexity, so I left it out.

Of course, someone who approaches the problem differently, has different requirements, and/or comes up with a different design may come to a different conclusion, and may find he does want to use a database. All I'm saying is, he doesn't have to :)

Have you calculated what is the minimum memory a room take ? So you know what amount of ram you will need as a minimum for that ? in 64bit now, so it is even bigger than in 32bit.
Curious if you did.



Dismiss this one, dumping tables in a cvs format is trivial.

Rather than address these points individually, I'll just go back to the point I hammered in the original article: Even with 100 concurrent, and a million rooms, we're still building a setup that isn't performance-sensitive. I don't think concerns about performance justifies re-inventing the wheel in this case, nor should choice of language even be in the discussion (you can make just about any modern, reasonably capable language perform for a MUD). I think we're falling back into nerd land.

I hesitate to even address the technical side of this discussion, my primary gripe is with your rationale for determining what to re-invent. There are lots of great existing solutions that have had years of development poured into them. Given that fact, and given that there is minimal complexity involved in using a mature component, why not do it? It doesn't even necessarily need to be a traditional RDBMS.

And to be clear, I'm not picking on you, arendjr, I think this is just a great example of a point I was trying to make: Don't re-invent unless there is a freaking strong reason (and I don't think you had one). You're probably going to do it worse, you've got to maintain what you re-invent, and re-inventing is almost always boring.

For those on the "the database is too slowwwww" side of the fence….

Do you REALLY think World of Warcraft uses flat files to store data?

What do you think Wall Street uses to track and maintain the stock market data, which has many millions of critical transactions every second? Punch cards?

No, a database is not a magic bullet that makes all your coding easier, makes things magically fast and secure, and fixes you toast in the morning. It's not EASY to get a database to perform well and still retain the kind of data protection you want. That's why good DBA's get paid much more than good Software Engineers. But saying the database is too slow just means YOU don't know how to USE it correctly for the task at hand.

Personally, I don't care. If you dislike SQL, or are more comfortable implementing your own storage/lookup system, go for it! But don't spread misinformation about database engines. I've worked on large scale systems with databases (not quite a terabyte, but this was 10 years ago), and I can assure you that almost every time someone complained about the database being slow, we found it wasn't the database's fault, but rather some poorly written client code or a badly written query.

**** Below here is more a personal take/rant on scalability… you have been warned. :)

Also, you aren't as scalable as you think. 1M rooms isn't that big, especially in games which have large overland expanses. That's only a 1000 x 1000 grid. How much RAM is the minimal room going to take up? Perhaps a couple dozen properties and a handful of string descriptions? I think a room description could be averaged around 1K, and some other strings around 256 bytes each… assume the properties are ints or short strings…. then add in the class wrapper overhead. 8K seems like a ballpark figure on a 64-bit platform.

BAM! You just sucked up 8G of RAM for your wilderness grid. It's a decent size, but not enormous… assuming you limit the speed people can walk/run/etc to 1 room per second (many have no limit), it would take you 17 minutes to traverse the world from one side to the other.

Now, let's look at it from the other side. You are a successful MUD and have 100 players online. They are happily running around killing stuff, fetching spoons for Lord LazyPants, and whatever else your players do. How many rooms are likely to actually be in use at any given time?

So, obviously, 100 * however many rooms need to be loaded for your events/description propogation. I'll assume a radius of 6 and also assume a square instead of a circle, because I hate math. So, that's 100 * (13^2) rooms in use, or 17K. That is about 2% of your grid size of 1M rooms. So, while you COULD accomplish the same thing using 136M of RAM (round it up to 256M to account for preloading adjacent blocks), you're using 8G by keeping it ALL loaded.

Does that matter? Well… not to me. I have 16G of RAM in my server. However, to people who still pay a monthly fee for hosting and think themselves lucky to have 512M of RAM to use… they're gonna be less happy about it. :)

Then again, I won't be happy either, eventually. See, I don't like having a fixed size wilderness. I actually want the game to generate my wilderness on the fly, as people walk around and explore. Like minecraft. My goal, if I ever sit down and decide to work on it, is to have a game which generates the wilderness as you wander it, and when you find somewhere "cool" to build something, you just start editing those rooms and they override what would be auto-generated at that point. Players like myself love to wander and see what's over the next hill, so there are freaks like me who will just head in a straight line for an hour….

I'm just not thinking that the technical argument is worthwhile, here. Let's just assume the following:

• There are people and organizations who have spent years/decades working on their respective data stores. These are data store nerds. It's what they do.


• These nerds have designed databases and doc stores that are resilient, adaptable, capable, and often easy-to-use.


• Anything you hack together in a few days, or even a few years, is probably not going to be as good.


• If you need certain characteristics in your data store, choose the one that is most appropriate and don't re-invent it. There are lots of options. If you have a lot of memory to burn and need excellent responsiveness, there are options that fit. If you are making extensive use of asynchronous patterns and don't care as much about memory residency, there are even more options.

The technical arguments here just aren't that important since the following stated reasons cover the technical stuff without getting into a slogging match.

Needless re-invention is the enemy of shipping. "Not Invented Here Syndrome" is evil. If you're going to do it, you should have a super compelling argument that isn't just technical.

Yes, I did. The 1,000,000 room scenario I want to fit on a server with 4GB RAM. Of course the RAM requirements are less when the world is smaller. Another advantage of not running a database too is that my application will have pretty much all available RAM to itself. Of course there are other factors besides rooms too, for example to amount of exits, items, characters, length of descriptions, etc.. This is to say the 1,000,000 is not exactly a hard number (as there're too many other factors), but it should be a reasonably useful metric.

Now, 1,000,000 rooms over 3GB (let's assume 1GB gets wasted on OS resources and memory for other things than the object model) yields 3KB per room. A plain room object uses about 300-500 bytes in my model. Let the average name + description for a room be a total of 8 lines of 80 character UTF-16 encoded text, then that's about 1280 bytes. Items and portals* typically don't have that much text, and have a smaller base size, so they can fit in 200-300 bytes each. So even if every room has 2 items and 2 portals on average, you might just fit it in the 3KB. So in theory it should be doable.

Of course I also have a JavaScript engine which will consume memory, of which I am less certain about the amounts. I hope my 1GB leeway will help me there. If necessary, I can start to be more aggressive towards saving memory by using UTF-8 encoded string for example, and actively try to reuse common strings. But so far I've had no need for that :)

*) A portal is a bidirectional exit. Given how common exits are (there are always more of them than rooms), it helps with memory usage to have half as many of them by defining them to be bidirectional (of course that's not the only reason for using bidirectional portals, but it was a factor).


@Kelvin: You keep insisting that I somehow have re-invented mature technology and what not, but I've built the engine and I didn't have to reinvent anything. There are no amounts of code that I have to maintain because of my decision. I'm probably not going to convince you anymore, but my point is: You don't need to reinvent what you're not using in the first place.


@quixadhal: While I think I can do with a bit less, you're largely right about the memory consumption stuff. It is a tradeoff I made to not care too much about memory usage in order to boost performance. You're right if I had used a database I would probably be more scalable when it comes to memory consumption.


Just to be clear, I've got plenty of experience with SQL, and I actually do got experience with multiple terabyte databases and scalability at a server farm of over 3000 servers. I'm used to stretching MySQL master-slave and multi-master setups to their limits, in fact I know where their limits are, where they will break, and what to do about it. I also know when to avoid a database, because yes, for many applications _databases_ _are_ _slow_. They give you luxury and scalability, at the expense of raw speed.

Remember how I mentioned the event propagation algorithm? I have profiled it a few months ago, and it allows me to propagate to 10,000 rooms in 13ms. If I had to use a database I wouldn't even be able to get the necessary data out of it in 13ms before I could even start the algorithm. In fact, given the lack of reliable prefetching for this use case I would be firing 100s, nay 1000s of queries during the execution of the algorithm, and it would take seconds at the very least. Maybe stored procedures would indeed be faster, but they're not gonna beat the 13ms by a longshot. For every object reference they'd have to do an index lookup, whereas my code only needs to reference a pointer. These things _will_ add up.


Anyway, by now I've wasted more time on this thread than I did implementing my storage layer, and it doesn't seem like I'm gonna convince you that life without a database is feasible, so I think I better leave it at this…

A wise man once said, model what you have to… fake what you don't. Another hippy said "if a tree falls in a forest, and nobody is there to hear it, does it matter if it makes a sound?"

While I'm sure propogating an event to 10K rooms in 13ms is indeed impressive, when do you actually need to do that?

Instead, you know your own coordinate, and you can get the coordinates of every NPC or player, so step 1 should be…

select id from players join npcs where fn_distance(coord_x, coord_y, ?, ?) < ?;

Now you know the entities who will care about the event, so iterate across each and publish the event to them. No need to waste time on the other 9,950 rooms that won't care.

Of course, you can do that without a database… and in fact it's probably easier. But my point is, there's no reason to model the propogation where it has no effect on the game world.

Now, if we're talking about an event like a FLOOD, where the change will be persistent, maybe that's a different story. But changing the room descriptions to account for the flood level is probably not gonna happen in 13ms, regardless. :)

Just to be clear, I'm not saying you need to use a database. I'm just saying, don't dismiss databases out of hand. It's very doubtful even the most popular text mud would ever need to stress a database to the point where it needs anything beyond the default configuration, let alone fancy things like pinning tables to different disk spindles or ram for performance.

I must have dropped a word. I meant that the requirements were in the first three paragraphs.
The requirement to provide acceptable user response time is a given.


This is a consequence of your implementation, not a requirement. You've implemented this in your mud as a graph with impedence functions on the edges. Your particular implementation doesn't appear to have notions of shape and size for rooms or objects, and that may be one reason you don't find any utility in spatial algorithms. Instead maybe your particular implementation is more suited for the Graph computation engine for MySQL.


It got all funny when you said it was impossible given your requirements.
It's not even improbable, rather, it's very possible.

At my job I once heard this story about a legacy system that our company wrote. I can't say what it did, but it had to have very high throughput and couldn't fail. And they succeeded at building it without using a database.

Fast forward 15 years and they asked themselves maybe we should have a database. So they paid oracle to come in and evaluate if they should convert their system to a database and it turned out they couldn't match the performance on that system.

Why? They had effectively built a custom database that was specific to what they had todo at hand. A commercial database is a good solution; but this particular problem required an optimized solution.

I once heard a person describe writing algorithm to the difference between driving a manual car and an automatic for saving gas. Sure you could do it. But you have to know exactly how an automatic car shifs gears and then know you can do better in such a way that an automatic engine can't follow. Rewritting a database engine is like the same. You have to understand how a database works, how the harddrive works, how its caching scheme works, how the processor caches and lastly how the application is going to query the database. Once you know all of that, its pretty easy to out perform a general purpose database for a specific application.

But its not going to be portable. Likely it isn't scalable (unless you thought about that at the beginning), and has as much reliability as you managed to program into it. Oh and don't forget security (which if you want has to be designed in from the beginning).

That being said, what did I use on my personal project? The Rom format. Why? because I already have it, works good enough for my purposes and simplifies the configuration. What am I sacrificing: reliability, scalability, portability and loading speed. Can I live with my sacrifice: yes.

Though I have to admit that sometimes I write something just because I can. My Christmas project was to write a full up webserver from scratch. Is this the best use of my time. prolly not. was it fun. yup. Best part is, in theory I should be able to keep up with the commerical webservers (the pipeline is pretty effecient, prolly one of my more effecient servers yet).

Most banking system using COBOL and flat files have a hard time migrating to 'pure database' as well. But we should not take them as an example for muds.