Scalability

[zilly]

I have created a few online games. I even created an online role playing game before. However, it was far from massive. The most players online was under 20, but it was a persistent world. The problem was that I didn't use a database and I coded the server in a scripting language. Later I figured that would certainly cause some speed issues.

For my next project, though, I'd like to know that I could maintain at least 100 players in a persistent world. I don't have any experience having servers communicate with each other, so I'm hoping I can accomplish that on a single server. I don't think that is to absurd of a goal.

The game is going to be 2d, but the world is going to be massive. The size of the world that I want is the main reason I don't think I can accomplish all of this on a single server. I plan for it to be at least as large as any commercial MMO with the possibility of expanding even larger and even perhaps much larger (I'm wondering if I should use two doubles to store each coordinate, that is how big I want the world to be). The problem with this is not really with the players, but with the sheer amount of ai I'll be asking the server to execute. The ai isn't very intense when it isn't interacting with a player, but it is still going to be 50k+ deep I would imagine (My last game was 1k+ deep. I guess that isn't so bad since C++ alone is probably 50 times faster than an interpreted language.)

I can worry about having several servers at a later point. I just don't feel like purchasing a whole bunch of servers if I never get more then 50 players. The only problem is I think that most of the trouble is going to come from the size of the world and not the amount of players.

I plan to code the server in C++ and back it with MySQL. If I have to have a separate server for the database that isn't a problem. I figure not running MySQL on the server might really not be that much of an advantage since I'd have to transfer more data. But that is why I'm here before I go off coding like a mad man.

I think I have a pretty good idea for how to manage all the small things since I have a little bit of experience. I'll be able to manage items extremely easily and movement will be a non-issue. All I am really worried about is managing this massive world.

Does anyone have any tips on how I would go about managing something that large on a single server?

I know C++, but I don't have any experience coding an online role playing game on it. So, I don't want to just go in and program all the NPCs ai as if I were programming a simple role playing game.

This is a really broad issue, but I want to know if it is reasonable to think I could pull of a world of this scale. I don't know how many people can honestly answer that question, but even if you can take an educated guess is good enough for me. From my educated guess I think managing 100+ players is not much of a task, but managing a massive world is. Perhaps it is the other way around.

I'm going to be posting this question around on a lot of forums. I just want to get as many opinions/educated guesses as possible.

Thank you.

[AndyKorth]

I really doubt you should have trouble with 100 players on a single computer. A lot of muds would run with several hundred players and they barely tax a modern cpu. Also, consider the amount of data you'll really have to keep track of, and determine if a database is really necessary. A mud with 10,000 rooms can run in 9 MB of memory. If you're just going to have a 2D game, with tiles, you just need a few big arrays of tile ids.

Depending on your AI algorithms, things could get pretty expensive pretty quickly. That's why most MMO games have mobs with very simple ai.

What do you mean when you say your AI is "50k+ deep"?

Did you run into performance problems with 20 players on your first game?

[zilly]

I meant that there will be 50,000 plus mobs hogging ai resources (taking an estimate based on the size of my last game verse the size I want this game).

I had no networking problems in my last game. As I said earlier, the online players isn't going to be the problem. It is going to be maintaining a massive persistent world. The problem with my last game was maintaining the persistent world. However, the server for that game was coded in an interpreted language.

Even with very simple ai, 50,000 plus mobs is going to take a tax on a server. Especially because it isn't like that is all the server is doing. The server has to update all player movements and figure out which players need which packets etc...

I want to use a database because the whole objective is I want this to be a somewhat scalable online role playing game. I don't plan on making the next WoW, but it would be nice if I could pull of something like UO. I think that is a feasible task, but I'm not really sure.

Thank you for your opinion AndyKroth. Keep them coming.

[AndyKorth]

Ahh, okay. I understand.

A few suggestions then that will help you on your way.

If you've got 50,000 mobs, presumably they aren't all different types. Thus, you won't want to duplicate data across them- avoid it as much as possible. If there are 5,000 rabbits, make sure each of them has an x, y, hp, and a pointer to a single actual "rabbit" object. This actual rabbit object will be the one that keeps track of everything that's the same between each rabbit- such as the graphics and model, the ai script, the name, the max hp, etc. This way, you need very little memory for each mob you add to the game world.

I assume that you'll be running some kind of updateAI() method on every mob every 3 seconds or so. This probably won't be as expensive as you think, but you can always decide to ignore mobs if there is no player within 50 units of them.

Make sure you have good bounding box code for your mobs and players- it'll be a big help.

Also, you'll find that even with 100-200 players, they won't be spread across the world evenly. Most of them will spend a lot of time bunched up in cities. There will be a lot of cases where there will be no one near many of the mobs.

Take a look at "Designing Virtual Worlds" by Richard Bartle.

[Fenris]

I must second that book recommendation.

Also, think about amortizing calculation costs across updates. One way to easily cut the workload in half is to only update half of the agents on every update cycle, alternating between the first and second half. The impact will be negligable in most cases.

[wyrmmage]

Desining Virtual Worlds is a great book, as has been said :)
You could always keep the information in the server executable and then perform an update on the mysql database every hour or so in case of power failure and what not.
-wyrmmage

[zilly]

Also, think about amortizing calculation costs across updates. One way to easily cut the workload in half is to only update half of the agents on every update cycle, alternating between the first and second half. The impact will be negligable in most cases.

This is something I take extensive use of. I've found that next to nothing needs to be computed every cycle and I always split the large tasks up as much as possible.

If you've got 50,000 mobs, presumably they aren't all different types. Thus, you won't want to duplicate data across them- avoid it as much as possible. If there are 5,000 rabbits, make sure each of them has an x, y, hp, and a pointer to a single actual "rabbit" object. This actual rabbit object will be the one that keeps track of everything that's the same between each rabbit- such as the graphics and model, the ai script, the name, the max hp, etc. This way, you need very little memory for each mob you add to the game world.

This is something I never really thought of doing that I think is a great idea. However, you mentioned the ai script. I thought functions were not stored in memory for each instance of an object. So, all I would need to do is create one object to maintain all of their variables, right? In which case, I don't even use an object. I just use a vector of arrays and I store the id of the location I keep all the information about the class that is constant. Is that sort of the same concept?

And thank you for the book recommendation. I'll have to check that out.

Feel free to keep the comments coming.

[AndyKorth]

However, you mentioned the ai script. I thought functions were not stored in memory for each instance of an object. So, all I would need to do is create one object to maintain all of their variables, right? In which case, I don't even use an object. I just use a vector of arrays and I store the id of the location I keep all the information about the class that is constant. Is that sort of the same concept?


You're right, functions aren't stored in memory for each instance of an object- there's only one of them. I think I was making some assumptions about your AI system (namely, that it worked the same way as mine). My apologies.

There are a lot of ways to implement AI. Right now, mine is pretty simple. I basically assign a pointer to "WanderingAI" to my rabbits, my birds, etc. I run a stateless (seems like an appropriate word) ai system, so the AI doesn't keep track of anything- the mobs have no memory, aside from an active target (doh, I forgot about that, I will need to make sure my code is okay here). This is a very easy AI system to implement. If you want mobs to remember shortest paths between locations and travel along them, this probably won't work for you.

And, yes, your approach as I understand it would work just fine. The main point is to avoid duplication of mob data in memory, so whatever is a convenientway of doing that should be fine.

[zilly]

I have my mobs very intelligent, which is one reason why I worry about having so many of them. I have them do a lot of things to interact with their surroundings and other mobs. And their combat intelligence is pretty demanding. One of the things that is kind of different about my game is that it is pretty difficult to kill a mob if you don't play smart. Another thing is that my calculations for damage and what are pretty intense. I'm not sure if that will be much of an issue since C++ is several times faster at math calculations than an interpreted language, but if it is maybe I should tone them down some?

I'm really not worried as much about bandwidth and networking issues as I am with memory issues. I've already figured out how to cut bandwidth down a lot, but I've always been a bit of a memory hog. So, I'm a little worried about dealing with all the NPCs and mobs and spawning of herbs, ore, etc...

Also, I know that logging in/out can be a bit of an issue, I think this is probably only for huge games like Everquest and WoW, but I'm going to be having a separate server to deal with logging in/out.

What do you think about a separate server for the database? I would imagine this is what a lot of the bigger games do. This wouldn't be very hard to program at all. In fact, it really wouldn't be any harder at all. So, if it is the better option for scalability than that is what I want to do.

[AndyKorth]

A seperate machine for a database is a pretty good option, although you'll need _a lot_ of players before you need something like that. Until then, however, you can run the database on the same computer as the game server. When this machine becomes stressed, you can seperate them.

For large large games, the following approaches are used:
One server per "area" of the map. WoW splits up their machines into: Azeroth, Kalimdor, Instances, Battlegrounds, Outlands. (Instances and Battlegrounds have sometimes been on the same machine) Eve online uses a different cluster for each region. You'll notice in these games that everything you interact with is within your own machine. (Eve's markets, etc).

Now, there are some exceptions. In both of these games you can chat with people on different computers in that cluster (Chat with your friends in Stormwind while you are in an instance). This is accomplished by another machine that is dedicated to worldwide communication. All players are connected to this machine and it's just responsible for these activities.

Computers are really fast at math, even in interpreted languages. Unless you've got high comlpexity algorithms in your AI, you really should be okay.... I imagine all your combat calculations are constant time. How much of your AI is already done right now?

[zilly]

I havn't even started coding for this game yet. I'm still planning how to set up my servers. But the AI from the other game had to do a lot of calculations to pick different abilities during combat, and for this game I plan on having the mobs do a lot of interaction with each other and the environment. And one of the things that has always been a problem is that my spawn AI seems to be a little too much. I have it spawn different numbers at different times depending on a lot of conditions, but again I don't know if this is as much of an issue on C++ as it was on an interpreted language.

I never thought to do a separate server for chat, but I think I will do that since it won't be very difficult. And I can run all the servers on one computer until it starts to get stressed and then split them up anyways.

As for splitting the game up into regions, I have instances, but I was always just running them on the same server. I guess splitting instances up wouldn't be all too difficult. The problem with splitting the game into regions is that I would have to do something like WoW does with that loading screen when you go from Kalimdor to Azeroth. I would like to have the entire game with no loading screens. Except for possibly going into instances. It is pretty unreasonable to think that I could load all those textures without a pause.

So, is there a way to split up regions into different servers without having a pause when the player is connecting to the other server?

All of these separate servers isn't really much harder to code than putting it on a single server. So, I'll do the extra work if it means my game is going to be scalable. But I really want the entire world to be streaming.

Thank you.

[kelvin]

My recommendations:

Asynchronous MOB updates. Run your AI as a service that connects to your main game world. This will allow you to strictly control the resources required.
Use a DB abstraction layer like Hibernate (hibernate.org). This'll make keeping your database schema normalized dirt simple. And will make scaling easier because it removes the data management chunk.
If you use a DB abstraction layer, then you can easily use features like Database Sharding. Also, it means that you can use the same API for connecting to and transacting with the distributed database as the local machine.
Partition the game world to run on multiple instances of the game (e.g. disparate areas run on the same code with configuration tweaks) If they are properly connected, your players will be able to seamlessly jump from server to server.


All these techniques can be implemented on a single machine. Multiple services talking to a single arbitrating appserver. The bonus is that finding bugs will be easier as the system grows and you can just move services off to other machines as the load becomes large.

The data flow goes something like this:
[client] -> [connection service | parser/command interpreter | output node] -> [multiple services]

where your multiple services include chat, emoting, multiple shared game instances, etc. Then, your MOB AI can also connect to the game instances. Game instances are connected to each other where areas converge. So in essence you divide your large game world into many smaller, connected game worlds and then delegate universal features to their own separate services.

This is also good because you can take down or reboot areas without shutting the whole game. Plus, as your user base grows, you can just throw more servers at parsing/logging.

Taken a step further, you can have areas dynamically resize to handle capacity. I.e. subdivide areas and have multiple servers keep state.

Or if none of that made sense, just look up database sharding.