This is a summary from our 2014 whitepaper, OneSim: Scaling Second Life with exaQuark. Some of the game statistic may be outdated
exaQuark is a distributed infrastructure that can scale virtual worlds. OpenSim is an open source, enhanced implementation of the Second Life servers. Combining these two systems we have designed OneSim, a distributed system to allow an unlimited number of users to exist together in one sim. All players run a OpenSim instance of the same region populate with their respective neighboring avatars.
Introduction
Second Life, a virtual world with a million unique visitors every month, is still popular ten years after its creation. However, despite a vibrant research community and an exponential growth in hardware performance, the per-region scalability has remained low with a maximum of few hundred users in a single region. Since the early 1970s, when the first multi-user graphic virtual world appeared, the algorithmic complexity of running Massively Multiuser Virtual Environments (MMVE) is O(N2), where N is the number of users together in the same region. Reducing the “visibility” to a smaller surrounding area doesn’t solve the problem: user density may vary sharply by some orders of magnitude, making the size of the area inadequate. With exaQuark we have taken a radical approach: users can see and interact only with their “neighbors”. exaQuark’s neighboring relation is designed so that the number of neighbors remains roughly constant regardless of the avatar density distribution. With exaQuark, the complexity for computing and transmitting interactions has been dramatically reduced to O(N). In exaQuark the overall complexity to maintain the neighborhood relation has a mean complexity of O(N). In other words, the per-user computing cost is constant and does not grow with N. This is the first step to scalability. Taking inspiration in Manycraft, an implementation to scale Minecraft, we designed OneSim, a distributed architecture to run OpenSim on top of exaQuark. With this architecture, there is no limit in the number of users.
exaQuark
exaQuark is a scalable distributed infrastructure for virtual worlds, designed to support an unlimited number of moving objects updating their position at arbitrary high frequencies. In exaQuark the set of avatars is distributed across many servers, each taking care of a group of avatars based on their geographical proximity. The positions are indexed using a distributed Delaunay triangulation for an efficient neighborhood access.
To free the application layer from the distributed internals, exaQuark provides an API to developers. When connecting, a client is assigned a proxy, the entry point to exaQuark for the entire session. Each proxy is connected to a subset of all users and, for each of them, maintains the communication with the corresponding zone and neighborhood. The proxy also maintains and regularly updates the states of the connected clients.
In order to scale, exaQuark spawns as many zone servers and proxies as needed. The exaQuark API receives two types of messages from clients: update entity state and message to neighbors. On the other side, it sends four types of notifications: the full list of neighbors, neighborhood updates, message from another client, and remove neighboring entities. Messages have an appdata field to carry data specific to the virtual world to scale.
This architecture exaQuark to be successfully employed for Manycraft, a distributed architecture to scale Minecraft, and HybridEarth, a social mixed reality world covering the whole planet.
OpenSim
In OpenSim, to enter the virtual world in a particular region, users connects their viewer to the simulator (a server) hosting this region. Simulators contain one or more regions and can be interconnected to form larger, continuous spaces known as grids. All simulators (sims) in a grid share a set of resources: login service, users accounts storage, assets storage, inventory storage, avatar storage. The viewer sends the avatar intended actions and movements, the sim applies physical rules and computes the interactions with the elements of the decor and the other avatars before replying with the actual action or movement – as seen by everyone. The cost of the simulation implies a limit in the number of avatars that can be hosted by a sim. The maximum number of users reported in a single sim is around one hundred.
OneSim
In our architecture each viewer is associated to a OneSim node. All the nodes are connected and communicate through exaQuark. A OneSim node consists of an instance of a regular sim, holding a local copy of the region, and a proxy to forward the avatars messages to exaQuark. In the local sim, the neighbors, provided by exaQuark, evolve as Non-Player Characters (NPCs). The packets between the viewer and the embedded sim are forwarded unmodified by the proxy. When the viewer sends a packet concerning the avatar (e.g. AvatarUpdate) the message in response from the sim (e.g. ImprovedTerseObjectUpdate) is intercepted to generate exaQuark updates and messages-to-neighbors. The message sent by the sim contains the result of the simulation and the actual position an d state of the avatar while the message from the viewer might carry extra data still needed for the final representation. The messages sent to exaQuark generates notifications for all neighbors and are used to control the corresponding NPC avatar. In addition to position updates, these messages also bear avatar animation, orientation, appearance, chat and other avatar actions. As each node hosts a simulation of the world this may lead to inconsistencies. This why in OneSim every non-static object has a master sim. For instance, the avatar and the inventory of a user have their reference state and position computed by the associated sim. Remote sims may computed different states but the master sim view prevails and is propagated to others. This way inconsistencies don’t last. As sometimes the state computed by a local simulator differs from what the master simulator dictates, the laws of physics may be temporarily not respected. Using OneSim in games with rapid pace actions might produce poor user experience. In dense crowds, the user experience might also differ from what we have been accustomed: we can only see the neighboring avatars and not the whole crowd in the visibility area. Today’s implementation of exaQuark provides an average of 70 neighbors. However the number of neighbors that can be handled by a node is limited by the capacity of the embedded sim. But as NPCs consume less resources than full avatars we can expect the total number of neighbors to be in the tens, for an end-user machine.
Conclusion
The infrastructure provided by exaQuark can be employed to scale diverse virtual worlds and a similar architecture, adapted to handle the Minecraft protocol messages, have been successfully implemented in Manycraft. In its intent to contribute to a long lasting research problem, the scalability of virtual worlds, exaQuark provides a novel approach that complement the widely used region-based and shard-based solutions.
