Server Scaling and Performance Tuning

From Multiverse

Multiverse Servers

Installing  •  Installing on Linux  •  Running  •  Troubleshooting  •  FAQ  •  Release Notes  •  Updating  •  JMX Monitoring & Mgmt.

Infrastructure

Platform Architecture  •  Registering a World  •  Proxy Server  •  Event Handling  •  World Manager  •  Voice Server

Messaging System

Perception Messaging  •  Using Extension Messages  •  Message Marshalling  •  Multi-subject Messaging  •  Message Catalog

Object Architecture

World Instancing  •  Server Object Search  •  Server Regions  •  Server Markers

Scalability and Performance

Overview  •  Scalability Testing

Reference

File Layout  •  Property File  •  Logging  •  API

Contents 1 Overview 2 World manager Server 2.1 The quadtree 2.2 Dynamic Load Balancing 2.3 World Nodes and Perceivers 3 Zoning

Overview

Multiverse has a plug-in server architecture. Plug-in servers include functionality such as:

• World manager: controls a world's geography and what PCs and mobs are able to see.
• Mob server plug-in: controls movements and actions of mobs.
• Combat plug-in: controls combat events and results.
• Others, including questing, resources, and crafting, and so on. Multiverse provides a set of key plugins. You can develop your own plug-in services in Java or Python

The Multiverse architecture provides for both horizontal scaling (adding more server hardware units) and vertical scaling (increasing power or resources of individual servers) without decreasing efficiency. In general, the Multiverse architecture is more sensitive to horizontal scaling than to vertical scaling. This document will focus on horizontal scaling.

Player characters (PCs) and mob AI are two main contributors to load, including CPU load, network load and database load. You can control mob AI load but not always user load, which is a common cause of server crashes in other systems. Thus, it is important to provide for the anticipated peak user load, not just the expected average user load.

Multiverse provides two general ways to distribute load among multiple servers: based on geography, and by distributing plug-in services.

Geographical load balancing and tuning parameters include:

• Maximum number of objects per quadtree node. See The Quadtree for details.
• Server perceiver range. See World Nodes and Perceivers for details.
• Mob perceiver radius. See World Nodes and Perceivers for details.

Because Multiverse plug-in services are location-independent, you can distribute them among multiple physical systems. Each plug-in server can be run on a separate system, based on load. This feature provides a great deal of flexibility in load balancing. If you notice one server consuming a lot of resources, you can move it to a separate physical server. In fact, as described below, you can distribute a server across multiple servers.

Since each plugin shows up in the OS process list separately, you can easily monitor the resources they consume. Currently, the distribution of plug-in services is static. That is, you must configure it on server startup. A planned enhancement will enable you to dynamically distribute services at runtime as needed.

You can also distribute a single plugin server across multiple servers. For example, you could partition the mob/AI server among multiple servers such that one server controls only orcs, another controls only wolves, and so on. This effectively distributes the load across multiple servers.

As another example, since trading involves two players, you could easily write a function to stochastically distribute trading among multiple servers based upon the object IDs of the trading parties involved. So, for example, you could add the two object IDs, and if the sum is odd the transaction would be handled by server A; if the sum is even, then the transaction would be handled by server B.

The flexible distribution of plug-in services is possible because services are message based, using Multiverse's powerful messaging system. See Multiverse messaging system for more details.

World manager Server

The world manager is the most fundamental plug-in because it controls the geography of a world and movement within it. The world manager provides information to an object about other objects it can see and their location. Unlike other plugin services, world manager communicates directly with other services, because other services may be location-dependent.

A world is represented by one or more zones. A zone is the highest level concept of geography for the Multiverse system and is defined by a three-dimensional grid of integers, with a one millimeter resolution. That is, the spacing of the points in the grid is one millimeter. Each axis of the grid goes from -2 billion to +2 billion. Thus, the size of a zone is a cube four thousand kilometers on a side.

Every zone:

• Is the same size: 4,000km x 4,000km x 4,000km = 64,000,000,000km³
• Has its own coordinate system.
• Can run on more than one server to distribute load.

One or more objects can occupy a point in the grid at any given time.

The quadtree

The world manager dynamically partitions a zone into a quadtree consisting of four equal quadrants, called quadtree nodes.

For each world manager, you configure a maximum number of objects allowed to be in a single quadtree node. When a node exceeds that limit, the world manager partitions that node into four again until the child nodes no longer exceed the maximum. Maximum objects per quadtree node is a tuning parameter, because it affects how much and how quickly a zone's quadtree is partitioned. For example, consider Figure 1 through Figure 3, which illustrate the quadtree subdivision process.

Suppose you set a limit of four objects per quadtree node. This figure shows a zone that has reached but not yet exceeded the limit, and thus has not yet been subdivided into quadrants.

When a fifth object is added, the server partitions the zone into four nodes until none of the nodes exceeds the object limit.

When more objects are added, the process continues. In this example, the lower left node is further subdivided into quadrants.

The four new nodes are called the children of the node that was subdivided (the parent node). The four new nodes cumulatively cover the entire space of their parent node. Thus, the entire zone can be seen as a tree, in which each branching has four "limbs".

As leaf-nodes (nodes that have no children) become populated by objects, the server will further subdivide nodes using the same algorithm.

Using the quadtree enables the server to consider only a subset of all objects when performing distance checks. For example, when a user comes close to an object, the server tells the client about the new object. Using the quadtree nodes, the server compares the client's distance with only objects in quadtree nodes within the object's perceiver radius, as described in the next section.

Each quadtree node can run on a separate server. In theory, one server can run any number of quadtree nodes, though in practice this will be limited by performance, depending on the number of objects, hardware limitations, and so on. A planned enhancement will dynamically load-balance the quadtree among multiple servers.

Even though the quadtree can be distributed, there is a one-to-one correspondence between world managers and objects. That is, one world manager always controls one object.

Although the quadtree optimizes server performance, it doesn't solve the overall scaling issue. At some point the server can have more objects and users than it can handle. So, you can load balance by moving a portion of the quadtree to another server.

You can distribute quadtree nodes among servers depending on the load they incur. For example, in the figure at left, server 1 runs the four nodes along the top of the zone, server 2 runs the three in the lower left, and server 3 runs the three in the lower right.

Dynamic Load Balancing

Dynamic load balancing is a planned enhancement. When enabled, a world manager will automatically choose a region and move it to another server as needed. Doing so will serialize all objects and send them over to the new server. When a client moves into the transferred region, the server will hand-off the client to the new server. The parent server still runs all adjacent regions. The parent server will remain in communication with the sub-server and if the subregion becomes unpopulated, can trigger a re-integration. When a client is near an edge which is run by two different servers, it will get information about both regions from the parent server.

World Nodes and Perceivers

A Multiverse world node is an abstraction that consists of:

• An object such as a mob, tree, building, or even a boat that can contain other objects.
• A locator that specifies its location at any given instant.
• A perceiver that determines what other world nodes it perceives; that is, objects that this object "knows about." There are two kinds of perceivers: Mobile (mob) perceivers and fixed (server) perceivers

When a mob moves around, its locator sends messages out that specify its location and velocity. Velocity is a three-dimensional vector which indicates an object's speed and direction of motion. The server engine interpolates the positions of moving objects based on the last known location and velocity. The server does not interpolate acceleration.

Each perceiver has a square "radius" around it that determines which objects it can perceive, as illustrated here for a mob. The dotted line represents the object's perceiver radius. An object perceives all objects in quadtree nodes that overlap its perceiver radius. Thus, in the figure, the mob can perceive objects in all the shaded nodes because its perceiver radius overlaps with them.

Each world manager has fixed perceivers associated with it. As with mobile perceivers, the server can perceive objects in quadtree nodes that overlap its perceiver radius. The perceiver radius may extend beyond the nodes the server manages--its managed area. The fixed perceiver range indicates the distance between the edges of its managed area and its perceiver radius. Thus, a server can perceive objects that are outside of its managed area.

Each quadtree node is managed by the server shown within the node. So, server3 manages the three nodes in the lower right corner of the zone. The dotted lines represent the fixed perceiver ranges for server1 and server3. Server1's fixed perceiver range overlaps with the four nodes immediately below its managed nodes: thus, it perceives all objects in these nodes as well as those in its managed area. Server3's fixed perceiver range overlaps all but the two upper left nodes.

As described below in Zoning, a server can control objects that are not actually in its managed area, if the object has recently moved across the boundary. There is hysteresis control so that when and object crosses the boundary control does not immediately change. This avoids issues with zoning back and forth at boundaries.

Zoning

The publish/subscribe system enables objects to easily transfer between world managers running on different servers without interacting with other plug-ins. For example, the Multiverse Proxy Server relays messages from the world manager and other plug-ins to the client. When a client logs in, the Proxy Server subscribes to several message types (such as location updates, chat messages, etc) about the player.

Zoning is when a mob moves from an area controlled by one world manager to an area controlled by another world manager. When this occurs, hand-off of message processing happens as follows:

1. The original world manager puts messages from the mob (for example, location updates originating from the client) into a temporary queue.
2. The world manager broadcasts a transfer message, with the object ID and location of the PC in the message.
3. The world manager that controls the area responds to the transfer message. All world managers subscribe to "transfer" messages, with their managed area as the filter, which guarantees that one, and only one world manager responds.
4. The new world manager subscribes to the same set of messages as the original.
5. The original world manager continues processing messages for the object while all of this happens, even though the player is not within the original world manager's managed area. Once the new world manager replies to the request, the original world manager then unsubscribes to subscriptions for the mob.
6. The new world manager does not immediately start to process messages for the mob. Rather, it waits for the original world manager to forward the messages it was queuing. These are messages that the original world manager has processed. The new world manager eliminates these messages from the messages it had accumulated and starts processing new messages. This procedure eliminates duplicate message processing,

For this algorithm to work, the messaging system must guarantee that messages from a given source are delivered in sequence, so the new world manager can easily remove duplicate messages. Subscription requests do not return until all producers are made aware of the new subscriptions. Thus, there are no dropped messages.

From the perspective of the Proxy Server or other plug-in servers, this entire process is completely transparent. Other plug-in services continue to operate without regard to the world manager controlling the mob.