Sign in to follow this  
ganbree

MMORPG Data Storage

Recommended Posts

I've been thinking about how MMORPG's handle data storage but I'm not very knowledgeable about the efficiencies of certain methods. I know that databases are quicker at most things than files, but... The data storage requirements for a character would have to contain data on say 10,000 quests... Now if you had a column for each quest could that have a negative affect on performance or space in RAM/Disk. This data would have to be check every time an action is performed related to the quest. Such as the NPC which gives the quest coming into view (whether to flag a ! or ? symbol above them). This is why the data must be quickly accessible. Would having separate columns for each quest, using BLOBS or flat files be better? Maybe some combination of them where a table of logged in characters, containing quicker access form and a offline characters table where it is stored in low storage requirement form.

Share this post


Link to post
Share on other sites
Normalize your database.

CREATE TABLE `character` (
`id` INT NOT NULL AUTO_INCREMENT,
`level` INT NOT NULL,
`strength` INT NOT NULL,
`dexterity` INT NOT NULL,
`health` INT NOT NULL,
`maxhealth` INT NOT NULL,
PRIMARY KEY(`id`));

CREATE TABLE `quest` (
`id` INT NOT NULL AUTO_INCREMENT,
`text` TEXT NOT NULL,
`script` TEXT NOT NULL,
PRIMARY KEY(`id`));

CREATE TABLE `completed` (
`character` INT NOT NULL REFERENCES(`character`.`id`),
`quest` INT NOT NULL REFERENCES(`quest`.`id`),
PRIMARY KEY(`character`, `quest`));

SELECT COUNT(*) FROM `completed`
WHERE `character` = #charid#
AND `quest` = #questid#

Share this post


Link to post
Share on other sites
I'd just like to add a caveat to Toohrvyk's excellent advice: a fully normalised schema can turn out to perform suboptimally. On the other hand, it's hard to know how to best flatten your schema until your game is mostly complete and you have some real usage statistics.

As a compromise, I suggest using a fully normalised schema to start with, but using stored procedures as the interface between code and DB. That way you can tune the underlying schema for performance laster, fix up your stored procedures, and not have to change any application code. Also, many DB systems can optimise, cache, and recommend indexing changes based on queries in stored procedures.

Share this post


Link to post
Share on other sites
Quote:
Original post by ganbree

This data would have to be check every time an action is performed related to the quest.


Jost a tiny subset, on the data already in memory.

Quote:
Such as the NPC which gives the quest coming into view (whether to flag a ! or ? symbol above them). This is why the data must be quickly accessible.


It's why it's usually done on client-side. Each NPC that comes into view offers a set of quests, which are stored in client-agnostic manner (1 ID per quest). It's the client that classifies what to display.

Even if done fully server-side, the checks itself can be performed once, and then stored in a transient object for each client.

Quote:
Maybe some combination of them where a table of logged in characters, containing quicker access form and a offline characters table where it is stored in low storage requirement form.


The client's quest state is loaded on login. The only changes are then performed when quest state needs to be persisted, which would likely be once every 10 minutes, probably even less on average.

Quest logic however is static and loaded once.

Share this post


Link to post
Share on other sites
Quote:
Original post by ganbree
The data storage requirements for a character would have to contain data on say 10,000 quests... Now if you had a column for each quest could that have a negative affect on performance or space in RAM/Disk.


no no and no! this is NOT how databases work! you create another table of quests and have it have a column for the user who the quest belongs to. each quest for each user gets its own row.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
Original post by ganbree

This data would have to be check every time an action is performed related to the quest.


Jost a tiny subset, on the data already in memory.

Quote:
Such as the NPC which gives the quest coming into view (whether to flag a ! or ? symbol above them). This is why the data must be quickly accessible.


It's why it's usually done on client-side. Each NPC that comes into view offers a set of quests, which are stored in client-agnostic manner (1 ID per quest). It's the client that classifies what to display.

Even if done fully server-side, the checks itself can be performed once, and then stored in a transient object for each client.

Quote:
Maybe some combination of them where a table of logged in characters, containing quicker access form and a offline characters table where it is stored in low storage requirement form.


The client's quest state is loaded on login. The only changes are then performed when quest state needs to be persisted, which would likely be once every 10 minutes, probably even less on average.

Quest logic however is static and loaded once.


I am currently working on a server for a private mmo project.
I plan to realize this by using a DataObject for each player on the server.

If a player is connected to the server, the server has to know the players information. How big will it be ? Less than 1mb.
So i thought the easiest way is to serialize and deserialize the DataObject on login-logout. Maybe sync it with the client.
I am planning to use xml serialization (the server is written in c#). You could save the xml-data in a database or as a flat file for example.




Share this post


Link to post
Share on other sites
Quote:
Original post by HeftiSchlumpf

So i thought the easiest way is to serialize and deserialize the DataObject on login-logout. Maybe sync it with the client.


What happens if player is logged in for 9 hours, and has just looted The Sword of Thousand Truths, then server crashes?

Share this post


Link to post
Share on other sites
Even worse than players losing items on a server crash, is that any server crash lets players duplicate items / money if you only update the database on logout:

1. Player A gives all his items to player B.
2. Player B logs out saving himself to the database.
3. Server crashes throwing away the in memory data.
4. When the server is back up player A will still have everything he gave to B.
5. B gives everything back to A. A has now doubled up on everything.

If that process is repeated starting say with 1000 gold, you'll have over 1,000,000 after 10 server crashes. For that reason you must sync with the database directly (and ideally atomically) when one player trades with another. That includes indirect trades such as dropping items on the floor that someone else can pick up.

Stopping players from losing too much progress on a server crash is simpler to fix - just do an occasional save of player state.

Share this post


Link to post
Share on other sites
Quote:
What happens if player is logged in for 9 hours, and has just looted The Sword of Thousand Truths, then server crashes?


The player becomes unhappy. Tough luck :-) The server should not crash in the first place.

You have to decide on a specific level of consistency, and design to that. Building to an "always persistent, always consistent" level of service is a lot more expensive than building to an "occasionally checkpointed, with consistency in trades" model.

Share this post


Link to post
Share on other sites
i think storing everything in a xml blob is a bad idea.

The reason is that you have to write everything everytime something changes (xp, level, etc). Guild wars uses this approach (only they have it binary)

Stick with a normalized datamodel and once you have something to test on denormalize parts for performance.

Share this post


Link to post
Share on other sites
I'll throw this into the mix. From Wikipedia, here's how the old UO dupe bug worked:
Quote:
It was accomplished by placing items on the ground (most often gold and reagents), teleporting far away, and shutting down the client before arriving at the destination. The virtual world had many computers (servers) controlling the different regions, and by moving a long distance, the character would be transferred between two computers, but by shutting down the client, the character would be lost in the transfer. When the player logged back in, the server would use its last backup of the character, which included the now-duplicated items.

http://en.wikipedia.org/wiki/Criticism_of_Ultima_Online#Duping

So to be an annoying pedant, I'd say it's all item movement that needs to be atomic. Maybe for the sake of optimization you can very carefully exclude certain one-way transfers that aren't exploitable, like taking loot from a monster. Then stamp every generated item with its own unique ID for good measure.

Share this post


Link to post
Share on other sites
Quote:
Original post by drakostar
I'll throw this into the mix. From Wikipedia, here's how the old UO dupe bug worked:
Quote:
It was accomplished by placing items on the ground (most often gold and reagents), teleporting far away, and shutting down the client before arriving at the destination. The virtual world had many computers (servers) controlling the different regions, and by moving a long distance, the character would be transferred between two computers, but by shutting down the client, the character would be lost in the transfer. When the player logged back in, the server would use its last backup of the character, which included the now-duplicated items.

http://en.wikipedia.org/wiki/Criticism_of_Ultima_Online#Duping

So to be an annoying pedant, I'd say it's all item movement that needs to be atomic. Maybe for the sake of optimization you can very carefully exclude certain one-way transfers that aren't exploitable, like taking loot from a monster. Then stamp every generated item with its own unique ID for good measure.


It looks like the main bug is that they didn't save the character before sending him off to another server. Before giving up control, one should make sure that if they can't give up control that the state can be restored properly.

This is why when you move a file from one disk to another (or one server to another), it copies the file and removes the original upon success. This provides some assurance that if the move fails for any reason, the everything isn't lost.

There may be a chance of item duplication (or lost items) if the server crashes, but the server crashing should not be a common thing (especially if the product is released).

Share this post


Link to post
Share on other sites
Quote:
Original post by nprz
It looks like the main bug is that they didn't save the character before sending him off to another server. Before giving up control, one should make sure that if they can't give up control that the state can be restored properly.


The point is that bugs like this are always possible. I think nearly every notable MMORPG has had at least one. So preventing it at a low level seems like the most effective approach to me, rather than relying on the programmers to get it right. If there's only one way to commit an item move to the database, and it's atomic, that's that.

Share this post


Link to post
Share on other sites
I've come up with my own method for storing data in my MMO.

I first started by building a VersionedValue class and a Transaction class. The VersionedValue class stores a list of values and the Transaction that set the value.

A Transaction can only 'see' another Transaction if it's startTime is greater than the other Transaction's commitTime and that it is committed. This allows me to detect when one Transaction changes a value at the same time as another.

The VersionedValue class is used by my Entity Database to store the entities and by the entities themselve to store their fields.

Since all the information is versioned, to save the database out to disk, I just need to create a new Transaction, iterate through all the Entity and write each one to disk.

The only downside is that you need a separate thread todo a cleanup, that is remove old values that can no longer been seen by any Transaction.

A big plus to all this, is that there are no locks anywhere as all the field updates are atomic.

Regards
elFarto

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
If there are no locks, then how does one transaction see all other concurrent transactions?

They don't. If it's not committed, you don't see it. Why would you want one transaction to see another transactions uncommited, probably inconsistant values?

Regards
elFarto

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
If there is no locking, and you support multi-threading, how can you commit a transaction in an atomic manner?


That's the clever part.

A VersionedValue class stores it's values as a linked-list of values and the Transaction object that committed it.

When another Transaction wants a value, it steps through the list and finds the first value it can 'see', where 'see' is defined as:

   protected boolean canSee(Transaction t)
{
return this == t || (t.isComitted() && startTime >= t.commitTime);
}


When you rollback a Transaction, the isCommitted() function will return false, meaning you can't see it and that value will be skipped over. Committing a Transaction just means setting the committedTime field on the Transaction class.

When you attempt to set a value that has already been set by a newer Transaction it just throws an exception, and the current Transaction is rolled-back.

I can send you the source code if you're interested in taking a peek.

Regards
elFarto

Share this post


Link to post
Share on other sites
Quote:
Original post by elFarto
A VersionedValue class stores it's values as a linked-list of values and the Transaction object that committed it.


So, if two different threads attempt to change a value, both will have to change the linked list, which means there will be a lock involved.

Quote:
When you attempt to set a value that has already been set by a newer Transaction it just throws an exception, and the current Transaction is rolled-back.
This sounds like a (somewhat awkward) lock-based system. Also, I don't see how this prevents concurrent issues. Consider the following sequence:

  1. Thread A begins a transaction and modifies the value.
  2. Thread B begins a transaction for the same value, modifies the value, then it checks if another transaction already committed and gets the answer "no", so it prepares to commit.
  3. Thread A also determines that no commit happened yet, and so it commits its modification.
  4. Thread B commits its modification.


So, the modifications from Thread A were dropped.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by elFarto
A VersionedValue class stores it's values as a linked-list of values and the Transaction object that committed it.


So, if two different threads attempt to change a value, both will have to change the linked list, which means there will be a lock involved.

Quote:
When you attempt to set a value that has already been set by a newer Transaction it just throws an exception, and the current Transaction is rolled-back.
This sounds like a (somewhat awkward) lock-based system.

No lock. It's an atomic compare-and-set. One thread will succeed, the other will fail. The exception is thrown when the CAS fails.

I also only insert new nodes into the linked-list's head. So I construct a new node, pointing to the current head, then CAS the new node with the current head.

Regards
elFarto

Share this post


Link to post
Share on other sites
Quote:
Original post by elFarto
No lock. It's an atomic compare-and-set. One thread will succeed, the other will fail. The exception is thrown when the CAS fails.


It is a lock. I'm not saying you used a lock, I'm saying you unknowingly implemented one. What should a thread do to get its modifications across? Basically, it will be
while (exception is thrown) 
attempt to change data
This looks suspiciously like the typical naïve implementation of a lock:
while (compare-and-swap failed) 
attempt compare-and-swap;


It's a consequence of transaction-based memory modifications: since transactions have to be serialized, any transaction will have to wait for all other previous transactions to be done, which in effect is equivalent to the transactions locking the modified resource. My point here is that, regardless of the transaction handling techniques you use (with or without locks, or whatever), transactions related to the same pieace of data still have to be done one after another, and thus cannot benefit from parallel processing.

I agree with your other point (lock-less atomic insertion at the head of a singly linked list).

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk

  • Thread B begins a transaction for the same value, modifies the value,
  • OK.

    Quote:
    then it checks if another transaction already committed and gets the answer "no",
    Exactly after this point, the value is changed by another thread.

    Quote:
    so it prepares to commit.
    And you commited stale value.

    [quote]
  • Thread A also determines that no commit happened yet,[quote]After exactly this point, the change happens.

    Quote:
    and so it commits its modification.
    And it too commits stale value.

    Quote:
  • Thread B commits its modification.
  • During which point, actual value may be anything, since two threads already modified the data in between.

    Quote:
    So, the modifications from Thread A were dropped.


    No, they succeeded, since atomic swap doesn't prevent other threads from moving on, and atomic swap succeeded.

    The problem here isn't in atomic swap, those can check for validity. The problem lies in the fact that there's no transaction-wide guarantees.
    if (atomic_compare(a,b)) {
    commit();
    }
    is not safe, unless entire statement is within a lock, or it atomic_compare is commit by itself. But as soon as you have two statements, you no longer have transactional guarantees.

    To me, this sounds exactly like the problem with the following:

    LockelssLinkedList ll;

    1) ll.add("An Item");
    2) assert(ll.pop_first() == "An Item");
    3) assert(ll.count() == 0);

    Though modifications are lock-less, the whole algorithm isn't a transaction.

    Count() is a nice example of an operation which is hard/impossible to implement on lock-less structures, or at best, has no real meaning. Although the list maintains integrity through entire process, the users operate on some non-deterministic data set.

    One problem that arises in relation to this is how to dynamically allocate the data (internal nodes) used by linked list. Even though you attempt to delete a pointer you retrieved from the list, there's no guarantee those contents are not being currently accessed by another thread within the LinkedList.

    IMHO, the whole system sounds like STM, and those are notoriously hard to get working right, especially with decent performance during contention. But it's been a while since I checked on progress, perhaps something has changed.

    Then again, I could be missing something.

    Share this post


    Link to post
    Share on other sites
    Quote:
    Original post by Antheus

    Er... Antheus, my post already was an example of how things could go wrong... [smile] and the modifications by thread A were dropped (that's the whole issue: they were commited, yet dropped) since the final value is the result of the commit by thread B, ignoring the modifications done by thread A.

    Share this post


    Link to post
    Share on other sites
    Quote:
    Original post by ToohrVyk
    It is a lock. I'm not saying you used a lock, I'm saying you unknowingly implemented one. What should a thread do to get its modifications across? Basically, it will be
    while (exception is thrown) 
    attempt to change data
    This looks suspiciously like the typical naïve implementation of a lock:
    while (compare-and-swap failed) 
    attempt compare-and-swap;


    True, I guess I've never considered it a lock, as it doesn't cause threads to be stopped waiting to aquire the lock. When a transaction fails, it's simply rescheduled to be re-run.

    The advantage to this is 1 transaction can be used across multiple fields.

    Quote:
    Original post by ToohrVyk
    It's a consequence of transaction-based memory modifications: since transactions have to be serialized, any transaction will have to wait for all other previous transactions to be done, which in effect is equivalent to the transactions locking the modified resource.

    That's not entirely true in a system with more than one field. Most transactions will be independent of each other. I apologise for not making it clear that 1 transaction covers multiple fields, e.g.

    Transaction t = new Transaction();
    Enemy e = EntityDB.get(id);
    e.setFoo(t, "new foo");
    Object o = e.getBar(t);
    EntityDB.add(t, new SuperEnemy());
    t.commit();


    All those changes will only become visible when the commit line is reached.

    Also, the example you (ToohrVyk) posted cannot happen. Which ever thread attempted to set (not commit) the value second would lose.

    Regards
    elFarto

    Share this post


    Link to post
    Share on other sites

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

    Sign in to follow this