Tip:
Highlight text to annotate it
X
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 wow 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.