Adaptive/Dynamic Categorization

Any static partitioning of data flows using a static algorithm (like a geometric grid) will break down. Either due to something intrinsic, or because the players are evil, and delight in ignoring your simplifying assumptions.

So for stability and performance/scale reasons a categorization policy that is dynamic will be better. Periodically a centralized or distributed computation can inspect the in-use categories and determine whether there is a better mapping.

Imagine there was a flash-crowd come to see an epic battle. The initial mapping had that area mapped to one category. The area can be split into two area and given two distinct categories. At a specific point in time, the new mapping will be instituted. Call that the next epoch. We need to do that across all users of those categories. The easiest way would be to broadcast the new mapping. Once all participants have acknowledged they have the new mapping and re-subscribe using that mapping, producers can start using the new categories. Once all participants have acknowledged adopting the new mapping, the old categories can be unsubscribed from.

There are many interesting dynamic categorization policies. They are based on live measurement of the system as the game is being played. The new categorization is then applied live. Clearly this can provide better efficiency than offline analysis and updating a static mapping, since in-game patterns can change minute to minute.

• Split and merge geometric grid cells or triangles. This is how many mmo systems work today, so if that is your preference you can keep it while migrating to using categories.
• Compute "nearness" between producers and consumers, and identify clusters of entities. The set of entities identified is given a category. As entities move around, they subscribe to other clusters of entities. Once the interconnections become too "stretched", a new clustering can be computed. There are pretty simple clustering algorithms, such as inspecting R-squared for an Entity against various proposed clusters to find the nearest one inside some threshold. Note that this approach can be applied to individual entities incrementally as they move.
  
• A similar clustering algorithm can be applied to actual communication patterns as opposed to assuming that geometric nearness always indicates high interaction rates. The recategorization system would record and analyze metrics of interactions as they change in real time.
• The hosting software can detect overloads of various resources, and indicate to the recategorization system that splitting off instances of busy areas would be valuable (assuming your game design supports that approach).
• As dungeons or PvP arenas are spawned, a new set of categories especially for the players involved will be computed and used. Because the subscribers indicate which instance they are currently assigned to, the categorization policy will compute the Categories for that instance, and a player will not see anything from a different instance.
• A game may have unique capabilities like being able to add, remove or move land masses. As coordinate systems drift around, the categorization policy would need to take this into account. It may be able to do that using relative coordinates, or it may need to completely recategorize space.
• Changes in team or guild size may trigger recategorization.
  
• As a clarification, in contrast to dynamic categorization, consider this scenario: As density increases in an area, the policy can adjust the maximum sight distance. While this doesn't directly change the decomposition of the data, it will result in fewer categories being consumed. (This is really a subscription policy change, not a categorization policy change)

Really, the key thing is to consider that real time feedback can be used to help improve the data distribution performance of your system.

Obviously an algorithmic policy is better than an enumerated one, since distributing new parameters to factor into a computation requires less data than a complete enumeration of the descriptions for each category.

Like almost any distributed computation, recategorization can benefit from incremental changes. Local measurements and performance triggers can instigate a categorization change to just a few mappings, and may be able to be distributed to only a few machines. These incremental changes can quickly ripple through the category space and come to an approximately optimal mapping. One benefit of the incremental approach over the periodic approach is that the trigger to recompute can be an event as opposed to a polling of metrics and a recomputation that may have limited or no effect.

Static Categorization Policy

A Static Categorization policy is one that partitions the data flows in an online game using a fixed function (usually a function of the values of the data being partitioned). The algorithm used does not change, and the tuning values do not change during gameplay. The performance of the system is determined by the designer during development testing. There are many examples:

• A 2-d grid with infinite altitude. Any entity in a grid cell transmits to the associated category. Any entity that can see into that grid cell subscribes to that category. And the grid size does not change. This can lead to lots of categories (not a real problem if your categorization implementation is designed for that), too many entities in a cell (if the cells are tuned too large), too many subscription changes (if the cells are too small). Etc.
  
• Variations of the grid approach include non-uniform grids (quad-trees), or arbitrary polygon "tiling".
  
• The designer could identify rooms, or spaces between rendering portals. Each would be assigned a unique category, and all data within them would be grouped. Only when near doors would a consumer subscribe to more than one category.
  
• FPS engines have used BSP trees to optimize rendering and visibility (and auditory effects) calculations (e.g. http://developer.valvesoftware.com/wiki/BSP_Map_Optimization) Whether automatically computed ahead of time or defined with hints, these 3-d volumes could have a category each. It is easy to query the data structure to determine the category corresponding to the current position. Doing an approximate spherical or convex volume query of the BSP tree should also be easy for consumers to find all their needed categories.
  
• Data limited to team, quest party, or clan can be separated each into its own category. A consumer (client) always knows which "entity set" they are in, so can determine where to publish and where to consume. Same with chat channels.
  
• Chat channels are interesting in that you may want to use a 3rd party chat infrastructure, but use in-game position or group membership to determine connectivity. Categories can be very useful for that, or if you want, could be used to route chat through the game engine. That way gameplay mechanics could affect chat (jamming, ambient "noise", battery charge, ...)

Again, all these are considered static because the algorithm and tuning do not change. If something gets overloaded there is no recourse to retune at runtime. Best you can do is change the policy in the next patch.

Note that membership is dynamic, however. That is how the system is able to limit what data is received (for security and bandwidth reduction), but still get everything that is needed to the right consumers.

Dynamic categorization is even more fun, but has some interesting challenges. More next time.

Subscribing ahead

Interest management is the process of delivering interesting data to those interested. An entity ensures that its sensor model has all the correct entities available to it by subscribing to the set of categories known to contain those entities. That subscription fills the local cache with replicas of the interesting entities. Then the sensor can be implemented to immediately query the cache knowing that it contains accurate data.

The policy the application uses to fill the cache can be as simple as a grid, or as complex as a dynamically determined set of clusters of nearby entities. In either case, the consumer knows the category being used by any entities that might be within the consumer's area of interest, field of view, line of sight, range of hearing or what not. Note that the producer generally produces into a single category.

So now producers send updates, and interested consumers get them. But what if someone moves? They will change the category they produce into, or the set of categories they consume from. But what about latency? That is where it gets "fun". A consumer can use its maximum velocity and an estimate of subscription latency to compute the extra distance needed to guarantee that the cache contains those moving entities even when the producer and consumer are moving toward each other at maximum velocity. That will ensure that its cache is populated with any entities that will-be interesting in a few moments. The cache will necessarily have more entities than are logically visible, so the sensor algorithm must filter out ones that are too far away but have been delivered "just in case".

But what about producers that are moving? We use latency hiding and bandwidth optimization to reduce the number of updates being sent, and then predict where the producer is at the current time. But that increases the latency of the produced data. OK. We increase the subscription range even farther. But you have to factor in the producer's maximum velocity. And you don't know what type of entity it is. So you have to use the maximum velocity of the fastest entity in the game.

That can suck if there are a few jet fighters, but tons of infantry. The solution? Separate the fast movers from the slow movers and use two distinct "layers" of categories. You would subscribe out quite a bit further for fast movers, but wouldn't get any slow movers in that wide subscription because they are produced into a different layer. And there won't be very many fast movers to consume. If you think about it, there is just no way to consume all the data from fast movers that are far away and might suddenly move toward you if there are a lot of them. The worst case example is an entity that can teleport anywhere instantly. Consumers would have to be subscribed to everything. Or you would have to change the game design to hide the latency from subscribing on-demand (like making a poof of smoke, or invulnerable just after teleport, or something).

The beauty of category based subscription is that these game-specific factors can be reduced to a set of integer values that can be computed by both producer and consumer. The consumer doesn't need to know that there are entities in the interesting category. If there are, the publish/subscribe system will deliver them. All that system does is match up integer values: hey this thing goes to these guys. The system doesn't need to assume that the categories are related to geometry, or that they are a linear function, or anything. You can use them as sets. Or unique addresses for multi-point to point communication, or for radio broadcasts on a single station. Or anything.

But my point: you have to use prediction to reduce bandwidth. But you also have to use prediction when subscribing or might miss something "interesting".

Why would you want gateway boxes?

An important aspect of an MMO shard is where and how clients connect. My preference is to have a set of Gateway boxes that responsible for managing those connections. Their responsibilities include:

• Authentication handshakes with the client and account system
• Rapid filtering of malicious traffic (IP filtering or more), denial of service attacks, smurfing (billions of identical, apparently innocuous/legal requests), and so on
• Separation of responsibility. This is valuable in a memory and cache efficiency sense, in that a single machine is focusing on just one thing. Simulators don't have to keep track of clients. They only connect to GW boxes.
• Instead of N clients each connecting to up to K simulators (N*K connections), you have only N client connections, each to only one of J gateways and the K simulators only connect to the J gateways (N+J*K). Since N is much bigger than J, this is a huge advantage both in connection count, connection management processing overhead, and memory on both client and server hosts. Normally N is quite a bit bigger than J (say 4 times).
  
• Message exploding and the majority of connections are happening in the data center over high speed switches, and in a secure environment on the backend switch.
  
• By focusing only on GW functions, and not running game logic, they can be made much more reliable than simulator boxes/processes. This can help a lot with player experience during fault recovery
  
• The Gateway boxes are the only ones with public IP addresses, so it allows a large fraction of your shard to be secure by having no direct route from the WAN. The idea here is GW boxes have (at least) two NICs, one on the switch with the main firewall, the other on the backend network.
  
• This also has physical network topology benefits, since the back end hosts can be on their own switch.
• Message header overhead is reduced when sending to a client, since all data to one client is from a single shard host, and it can do bundling for over the WAN messages (most important).
• Gateways can also "be" the lobby or character selector prior to entering the game world.
• Non simulation messages like chat or game service stuff (auctions, guild management, email, patching/streaming of content, ...) don't bother the simulators.
• The sizing and configuration to optimize for the size of your peak player connections are now independent of that for the simulators and load balancing.
  

I also subscribe to the philosophy of persistent client connections (or with connectionless protocols, staying with one assigned gateway). The major benefit of this is that a client does not have to reauthenticate and renegotiate their connection with another host in the shard when their character moves around in the world, or some other load balancing activity changes the simulators they need to interact with.

To do this, the GW is also responsible for routing messages between the client and the simulators that are "of interest". This gets back to category based routing and channel managers discussed earlier. Data from multiple simulators is sent to the GW box and forwarded to each interested client.

Data from the client tends to be routed to the one Simulator that client is currently using. I.e. the one that owns its "controller" entity where client requests are validated, and (normally) their player character is owned/simulated.

You want multiple gateway processes (not multi threaded) per gateway box to avoid losing as many player connections if something should crash (and then reauthenticating, etc). This also helps deal with file descriptor limitations per process for the connections if your OS configuration limits you.

There are downsides, but not overwhelming:

• An extra hop for most messages. This hop is on a datacenter switch, and will be very fast.
• There are extra machines to buy. Well, not really, the same message handling work is being done but not directly by the simulators, so they can get more done each (and that has other more subtle communcation benefits). We just partition it, and use the same number of machines.
• An extra switch and extra NICs. You can use two VLANs on any decent switch, if you have to.
  

In summary, you are just moving some work from one place to another in the same sized shard, but getting a lot of system simplicity, security, and communication benefits.

Peer to What?

Ever notice how people use exactly the same word to make an important differentiation? Shorthand, laziness, different backgrounds, or maliciousness?

So in our industry what do people really mean, or think they mean when they ask "Hey. Does that support peer to peer?" Here are a couple of definitions and more clear terminology that I prefer. Maybe I can find some sources to back me up. BTW, I'm thinking of small-scale online today. Although many/most of my architectural biases apply here as well. (Other than whether the server is hosted or not).

Academically speaking, peer-to-peer is a communication topology that, in general, indicates that clients or players communicate directly with each other. Like peer-to-peer file sharing. It is used in contrast with the client-server topology where each client has a single connection to the server, and any interaction between clients is performed by means of the server. One benefit of the peer to peer topology is that data can move between clients with one hop of latency instead of two. One benefit of client-server is that each client can be presented the same data in the same order (deterministically).

However, many people are less concerned with whether two clients communicate directly, but instead use the term peer-to-peer to indicate they desire other features:

1. There is no part of the game hosted in a central location like a data center. Note that central-server or authoritative-server is not the same thing as hosted-server.
   
2. There is no stand-alone server that needs to be stood up ahead of time, possibly occupying another piece of hardware. When the player starts their client, the multiplayer game is automatically ready to go. There is no separate server process consuming extra resources on one of the user's machine.
   
3. There is no single point of failure in the distributed system. If the master (usually the first player to start) were to drop out of the game, there is no reason for the remaining players to go through matchmaking again.

It turns out that a client-server topology can be used and still achieve all three of the above features. Obviously, "hosted" or not in #1 is easy. Just run the server on someone's machine. The long-running server in #2 is easy. Either start one up and shut it down when the client is started or stopped, or you join someone else's game session. Or if you are resource constrained (like on a console), and can't abide the second process, make a dual-purpose client. The first player in would have their client become the master/authoritative server. #3 requires a little bit of technology. When the master drops out of the game, another of the clients must become the master, and the other clients connect directly to them. This gets a little tricky in a non-uniform network, but it is a problem that is solvable with automatable algorithms, so the players don't know that it is happening.

So even if you have some of the three problems above, you don't have to jump to the conclusion that client-server is therefore not approprite. And given how much easier it is to get a system running that assumes there is a single authoritative server, I'd recommend you look into it, and prove (ie. measure) whether you have an intractible problem with client server.

In the mean time, I'm going to continue to be skeptical when folks say "I need peer-to-peer". My question will be "what feature of peer-to-peer do you think you need?". My "favorite" topology for small scale non-hosted multiplayer is what I call "peered-server" to contrast it to hosted-server. Client server communication topology, single authoritative simulator, no central persistent hosted server process (other than a match maker, which is not the same thing as a simulator).

Really, the thing to keep in mind is that the process communication topology does not have to equate to the network communication topology. It could be a little more efficient if they match, but could be a lot harder to get your project finished.

How to ignore most emails (safely)

At work, I use Outlook. It has "organization" tools. One of the best is found here: View/ArrangeBy/Custom/AutomaticFormatting. It gives you a set of conditions and formatting for each line in the list view. I use the default of unread mail formatting with a bold font.

1) I use my favorite font color for emails that are sent only to me: select "where I am:" "the only person on the To line". Even if others are CC'd on this email, it was sent directly to you. You'd better read it. No one else will.

2) My second favorite font color for emails sent specifically to me (and others): select "where I am:" "on the To line with other people". Someone took the time to direct this email directly to you and some of your peers. You should probably read it. Maybe one of your peers will respond, but you never know.

3) My third favorite font color for emails that I was specifically CC'd on: select "where I am:" "on the CC line with other people." (also covers where you were the only person on the cc line). Someone took the time to include you on the thread, but you know it is FYI (for your information) only, so you can almost certainly ignore it without getting in trouble, or until you have some time. This allows you to decide based on the subject line, for example. Many #3's turn into someone else's thread, and I can get by with skimming only a couple of those.

4) My least favorite color is "all the rest", and will be the default formating. These will almost always be delivered to you because you are on an email group. These can almost always be ignored for several days. If you happen to be on one or two where that is not the case, make a custom rule to highlight these. If you are on a ton of groups that each need immediate attention, you are probably doing something else wrong that I can't give you emperical advice about. I know I wouldn't survive long under that kind of stress. Don't borrow that kind of trouble. Seriously consider whether your response in those forums is honestly needed so urgently. I'l bet if you ignore it and you are the only one that can respond, you are eventually going to get a #1 or #2 email on it.

I also use a custom font color for "followup" emails that I have specifically marked as needing my attention later. Not only do they show up as red, but they sort to the "bottom" of my list view (I read my list like a console window scrolls.

I don't empty my inbox. I think that is "busy work", and just puts important items out of view in other mail boxes where I wind up forgetting about them. I only open half or 2/3rds of my emails, and only when I decide I have time. I'll flip the window open (left on list view) and see if there are any #1's and then just close it. That means almost half my emails are left in the "bold" state, and I don't feel guilty about that. Those are emails that were broadcast, not sent "to" me expecting me to solve a problem. They were FYI to me. If it was an important broadcast, it probably had the "high priority" flag set.

I also use the preview window and set auto-read on (marks the item as read if you "preview" it for more than a few seconds). If I get the sense I need to read this more carefully or later, I'll manually flip it to unread so it stands out and I'll reevaluate it later.

These tricks work well in meetings when you think you need to glance at your queued emails, or any other time when you are very pressed for time. A simple glance at the font colors gets you focused on the one or two emails you should look inside. Often there is little or nothing to do with even those, so mark them unread for when you have a block of time to "clear" the backlog.

What does a "Flexible" architecture look like?

We've all heard the maxim that the only constant is change. This is true on a lot of levels. During the development of a title, the designer is going to come up with some doozies..."Hey, what if the player controls the character *and* his minions?" Maybe it is an important change, but if you have a big complicated (and maybe purpose-built) MMO system, things like that can give you nightmares.

So even if you know (or think that you know) what the game is going to look like, 3-5 years down the road, it won't, and you'll have a lot of difficult refactoring if you don't plan for change. Put in insulation layers so that big changes don't propagate very far. For example, don't assume you are going to be using SQL, and start coding Entity behaviors with embedded queries. Instead, define a persistence interface that could be implemented by any number of technologies. Maybe it starts as a flat file, or an XML DB. But by the time you go live, Microsoft bought your company and they want the DB on SQL Server. And while we are talking about the DB, don't *ever* talk to the DB with a synchronous query that blocks gameplay. You might be surprised by the variance in response times even a good Oracle DB will give. My horror story: chances were 50:50 that when we deployed a new version on TSO that had a schema change, that the DBA's would migrate the data in some hand-cobbled way. And (get this) an index file would disappear. Things looked ok until you got a few hundred live customers connected.

Where was I? Insulation. An architecture that can withstand or localize pretty radical changes is simultaneously flexible. You can use the parts in different ways, or replace things you don't like. And when you replace them the change doesn't ripple very far. I'm arguing you need to do this even for a purpose-build MMO-engine, so doing the same thing for a middleware MMO engine results in no net impact on performance or usability. And since a middleware developer wants to sell their engine to studios doing a variety of titles, that flexibility is required just to make the sale.

I like to think about sitting across from a hard-nosed tech-lead in a sales meeting who absolutely *NEEDS* a certain feature that we don't have. I can say: no, we didn't do that, but its flexible, and you can swap that peice out. They can start with what we have, and do the swap out if they have time; which I cynically think doesn't happen very often. When have you had "extra" time during development? Well, at least we made the sale. Its a lot better than saying no we don't do that, our way is more efficient, and it will be wicked-hard to change. OK, I have to share this too: GDC '07 or '06, I heard Tim Sweeny say: "Modularity is overrated". Makes you wonder why folks love to hate developing with Unreal.

How do you create insulation? Look into PIMPL (pointer to implementation) or Interfaces (pure virtual base classes) to hide all implementation detail from users of a module. Make the modules loosely coupled. Don't assume too much about ordering or synchronous interaction between modules. One of my favorite patterns is the publish/subscribe or producer/consumer pattern. One module sends a message that is categorized, and has no idea who might consume it. Modules that want that data or notification subscribe ahead of time, and run a handler when that message is sent. Now you can add new modules without even recompiling the sender code, much less adding a compile-time dependency. Turns out this approach is good for improved compile times too.

Loose coupling between software modules is really great. Take it to the next step, and avoid (run screaming from?) synchronous interaction between processes. E.g. I wouldn't use CORBA. Too easy to create deadlocks. Instead, prefer sending an asynchronous message. Don't use critical sections in blocks of code, or locks on all kinds of data structures. Too easy to create deadlocks. Instead prefer sending an asynchronous message.

I see a pattern developing here. It leads to the ability to map logical processes to other threads or other remote processes with very little change to your code. The event-oriented, message-based approach to distributed systems is very successful. I guess I've already talked about CSP (Communicating Sequention Processes) in an early post, so I'll just drift off.