Storing server information for an MMORPG

I wanted to get some professional feedback(I hope) on which is the fastest way to store/retrieve/update/delete information for an MMORPG with the server coded in C++. For characters, monsters, items, objects, etc. What do games like World of Warcraft, and Lord of The Rings, and Star Wars use? Do they use linked-lists (stl, or a custom one)? Do they use vectors, arrays. Should I store them with vectors to make life easier? Should I come up with my own clever ways to quickly and efficiently retrieve/change/update massive amount of data?

I was reading on the web and it seems like linked-lists are the way to go. What are your thoughts? If one were to use either of the mentioned ways to store data, should it be broken down to even smaller sub-categories? For example, if I were to use linked-lists. Would I make linked-lists for items like weapon_on_ground, weapon_owned, armor_on_ground, armor_owned, belt_on_ground, belt_owned, etc. And do that for each type of linked-list and try and make each linked-list as small as possible? As I could see a potential problem having lets say 100k items in the world, and having to sift through them each time a player drops one, or causes it to be changed/updated/deleted.

I am in the middle of porting a project I was working on to a IOCP server. Before I was just storing all data into linked-lists called: player_info, items, monsters, objects, etc. But I fear that it might not be a smart idea, and maybe there are better ways of storing information on a server that I know of.

I hope I can get some great replies.

EDIT: The "project"(as in, it may or may not get finished) is going to be a 2D dungeon crawler MMO, with a lot of monsters, items, and NPCS. Lets say itll be a old school classic 2d rpg but MMO style.

• You may get more replies if you narrow the question a bit: what are you trying to do right now? My guess is that you're not going to sit down and code an entire MMORPG in the next three hours. – Shep Apr 20 '12 at 13:13
• @Shep, I was in the middle of tinkering with player data structures for movement on a node.js server, and it was playable to move around, login with chars and save, but I decided it would be best to code the server in C++ using an IOCP model, so I am porting the whole project and wanted to recode a lot of the ways I was storing data for scalability(I was using linked-lists). Can a mod just switch it there, or do I need to delete it or what? – user1328762 Apr 20 '12 at 13:19

Do they use linked-lists (stl, or a custom one)? Do they use vectors, arrays.

Of course they use them (hard to imagine C++ program without some kind of array/map/list-like container). However, it doesn't mean they use those data structures to store data on server. Let's put things into perspective. Let's say there is 1 million of people bombarding server with requests at once. Of course, they all do it asynchronously. Using stl or trying to "reinvent your own wheel from scratch" in this situation will be suicide (thread safety). A safe guess is that data is stored within database and most of server logic revolves around interacting with that database.

Anyway, if you want to make a MMORPG (not a very good idea, IMO) and didn't do your homework, you need to investigate existing software. There are couple of opensource MMORPGs that come with source code (ryzom, planeshift, few others). So you can download the source code and read it. I expect that unless game is trivial, it'll take month or two to get overall idea of "how engine works" even for a skilled programmer.

For non-opensource games, there is "private server software" floating around. Some of it might be even legal. You could attempt to get it, install it and see what it uses.

he "project"(as in, it may or may not get finished) is going to be a 2D dungeon crawler MMO, with a lot of monsters, items, and NPCS. Lets say itll be a old school classic 2d rpg but MMO style.

You need to investigate MUDs. They implement what you're asking for, although they normally do it using ASCII graphics (not much of a difference, though).

• I think the best way to go would be to load data from the database into ram, directly storing it there in a list of some sort. And only doing partial saves on important stuff. Lets say, if you drop an item on the ground, itll update the database, but if you take the item from your invi and equip it, itll change the server list that its on you. But my question was, what kinda list would be efficient, as in, not buckle if lets say a 1k people drop an item at the same time. – user1328762 Apr 20 '12 at 13:39
• @user1328762: "I think the best way to go would be to load data from the database into ram" Power failure -> data loss. Also it is quite possible that in a big MMO data won't fit into RAM. The best way would be to avoid reinventing the wheel and use existing database software. Something like MySQL will cache necessary information in RAM without your "help". – user15552 Apr 20 '12 at 13:54
• @user1328762: "Lets say" Grab existing source code of actual mmorpg and read it. See how THEY did it. "would be efficient" Never try to guess performance, profile program instead. "What would be efficient" depends on what kind of "MMO" you're trying to make. Since you provided no data about your game, you could as well ask fortune teller. – user15552 Apr 20 '12 at 13:56
• I see your point. So, the data needed per action is just retrieved from the database? Lets say I attack a monster, my player_stats are not actually in ram on the server, but the server just grabs my Strength and Weapon Item stats from the database, and calculates the damage, and then updates the monsters data hp? – user1328762 Apr 20 '12 at 14:00
• @user1328762 the main problem is you are thinking about single threads. One of the best architectures for an MMO server I have seen is one based off of the actor model (where each actor was a region) - unfortunately Blizzard seized the website and code so the actual documentation of how it worked isn't out there any more. "Lock free multi-threaded" should become very familiar to you if you are seriously considering doing this. – Jonathan Dickinson Apr 20 '12 at 14:01

Not really knowing how the "pro" games do it, I'd say the fastest way to do it is to use a rapid-development language such as python, on the server, keep the database in memory (because it won't be THAT big, after all), and persist it with the language's built-in serialisation.

After all, the MOST IMPORTANT thing to optimise, is developer time.

NB: the Python "Twisted" framework was actually developed to write a MMO server. This does not mean that you should use it though.

• At MMO scales, server hardware can be much more expensive than developer time. The tradeoff between CPU load and datacenter costs for our game work out to something like every additional millisecond per game tick works out to around \$1m of extra datacenter servers we need to buy. – Crashworks Apr 20 '12 at 18:59
• Yet you won't get to MMO scales if you start out worrying about the optimal way of doing everything. Better to start with decent algorithms and optimise once you know where the problem areas are. – Kylotan Apr 21 '12 at 10:43

A linked list is a fairly low level data structure. The type of software you're writing doesn't really affect the choice of data structures at this level. Generally speaking you use whatever data structures are provided by your language, with custom-made ones where necessary. (If you need to ask which structure to use, without a clear idea of why the default ones aren't sufficient, then you don't need a custom structure yet.)

C++ provides several useful default structures, eg. std::list, std::vector, and std::map. Most game developers, if they are using standard C++ rather than 3rd party frameworks, stick to using std::vector until they see a need for something else, because it is close to a traditional array and efficient for most tasks.

If you don't understand C++ well enough to make these decisions, then you would be better off staying with node.js. It's more important that you are able to tackle the high level problems such as getting players connected, saving data to disk, and implementing the game rules.

• Thanks for that reply. If vectors are the most common why is there such radical opinions on what to use? Do you think it matters at this day in age (since computers are so much faster) what type of data structure to use? – user1328762 Apr 21 '12 at 10:03
• Where are these radical opinions you speak of? If you ask people the difference between 2 data structures then they'll debate that, but it doesn't mean that there's a significant difference in real terms. Whether it matters at all depends on many factors, but it is the absolute least of your worries when you're starting out on a major project. – Kylotan Apr 21 '12 at 10:40