Raluca Diaconu explains Kiwano
When we started working on mixed reality we faced a problem: to cover the whole planet, with all its inhabitants, we had to overcome a huge scalability issue: it was admitted that only a few hundred users can simultaneously be together in a virtual world.
We tried to understand how others deal with this issue. For sure, if you connect everyone to the same server, they will be together but at some point the server runs out of resources. The actual limit is very low: a server can handle at most one thousand users. So we need to add more servers, we need a distributed system.
An early solution for scalability were the shards, invented by Ultima online. They distributed the users onto many copies of the world. This was great because it was possible to have many players connected at the same time. This solution is also used in World of Warcraft. But, at the end, the users might be in completely separated worlds, if they are not in the same shard they cannot play together.
And then there was this great idea of dividing the space into zones, each zone being hosted by a server. This solution was successfully implemented in Second Life. However, the approach has its drawbacks: as people want to socialize and concentrate where the crowds are, many zones remain empty while a few become overcrowded. Since exactly the most attractive zones are saturated, Second Life still faces important scalability issues.
There are many available resources: data-centers with a myriad of computers. There are social services with millions of users. Yet, virtual worlds remained limited to just a few hundred. The problem, we thought, must be redefined from scratch.
We realized that handling the decor and handling the avatars are two different problems. They should be addressed separately. Google Earth, for instance, is a sort of empty virtual world, huge in extension and browsed by many users.
Avatars move, talk, dance, and so on. It would be too costly to send these events to everyone. The server needs to compute who is concerned, who sees the acting avatar.
But as avatars move their positional configuration changes.
This repeated computation is costly: the server needs to find quickly who is in sight, out of a haystack of moving avatars.
The bottleneck resides in the avatars movement from one position to another.
In this context we came up with a new solution, where servers are allocated to groups of users based on their geographic proximity.
In a virtual world users are concerned with what is happening nearby. That’s also why most virtual worlds assume that events have only a local effect.
So, for each avatar there is a neighboring zone around its position that will provide the complete scene, the visible decor and all the events. Thus, avatars need to be notified of all the events produced by those located in their neighborhood.
It is assumed that, the neighborhood is the space and objects within a certain range distance. But this does not take into consideration variations in density. An area of interest with a fixed size often can be too large, when there are many people around, or too small, where the density is lower. Also, if avatars have areas of interest of different sizes this can produce asymmetry: you see your neighbor, but she does not see you.
In a crowded space you will pay attention to people in the immediate proximity. If you are in an open space you can see someone far away.
Then given a set of avatar positions, what is a good way to connect them?
We have seen that connecting everyone to everyone is not efficient. Moreover, any direction you look in, you should see who is the closest. Fortunately, the Delaunay triangulation, provides this property. The Delaunay Triangulation is a classical computational geometry tool, widely used in computer graphics.
This is also the basic data structure of Kiwano, the system we have designed to scale virtual worlds.
An important feature of this approach is that it preserves locality: moving an object produces only local changes and those who are concerned by this event are the old and the new neighbors only. Accordingly, the Delaunay structure offers efficient, constant time access to the neighbors, which enables us to send notifications timely, before the source has moved further.
In Wold of Warcraft they succeed to balance the load by evenly distributing the users among realms. In Second Life the problem is that the zones do not match the distribution of the avatars.
Ideally, each zone should handle the same load, so the zones should not be shaped by the geography. They should be shaped by avatar distribution.
And because avatars move, we can expect the distribution to change in time; this is why we need zones that shape dynamically.
In Kiwano, a zone is the space covering a group of avatars, selected by proximity. Each zone handles roughly the same number of avatars, ensuring load balancing.
Each zone is taken care of by one server. Its size will not exceed the server’s capacity. And, because each zone communicates only with its neighboring zones to maintain the frontier, we can add as many servers as we need. The more people are connecting, the more servers we add.
According to the tests we ran, our 8 core servers supported around ten thousand users each.
In World of Warcraft, at any given moment only 5% of users are connected and playing. Using the same ratio of active users versus connected users, Kiwano can support 200 thousand active users per server, this is a cost effective solution.
That’s why we are confident that virtual and hybrid worlds with millions will be common in a near future.