EVE Technology Lab

Hello everyone,

I just took in this semester Computer Networks I and our task right now is to examine an existing server application and give a report on how they work. Many choose Apache, some chose ProFTPd and so on... So our task is to look at different ways to handle TCP connections and later write a TCP server and client that follows that approach.

So I decided to go a bit... more technical and try and look at some Game Server's Server side source code. I found none thus I will most likely write my own report on some open source application's design however I became interested:

Creating a blocking IO model based TCP server just doesn't seem viable with so much net traffic going on. Imagine that there is a blocking IO based TCP server listening at CCP's side and whenever there is something happening on client side all the other clients have to wait for the first client's network connection to finish. With a few hundred connections I can imagine that that could be fast enough but with 40-50.000?

So I came to the conclusion that it must be a non blocking IO and async TCP server at CCP's side. So whenever a client connects he either gets a thread to handle his connection or gets a connection resource from a pool. I very much doubt that CCP would want 40-50000 threads running on their servers since that would mean a lot of context changes that takes up a lot of CPU time and memory.
Another problem with Async IO is: the execution order of the threads are not dependent on the time they were created so they have no way to ensure say a FiFo order of execution. Depends on the OS scheduler. Imagine what would happen if say you hit warp and a little later you opponent in PVP hits on the scrambler. In a real world scenario I'd imagine that warp should be executed first and you stay alive, but it is entirely possible that client 2's scram request gets executed first. You are doomed O_o
If Async IO is used how do they ensure this FiFo stack of events?

I heard some rumors that CCP is using microthreads with stackless python. Would a python application have the power to serve so many connections? As well that would mean that the application would have to run on a single core over multiple cores. Not very ... efficient...

Cluster to serve 1 universe

Another thing that just came to me while not related to my original problem but is still interesting:
Whenever there is an event on client side: say you hit on F1 through F8 to kill that SoB, the server gets notified of it. There are a lot of such events occurring concurrently. 1 Server would not be unable to keep up with all that information to be processed so they need a lot of servers in a cluster. This is actually what CCP has.. I am wondering tho how they solved the issue of having a computer's core dedicated to a solar system.
There must be an entry server that deserializes the object that has been sent over to the cluster and forwards that "message" to the appropriate execution node which in turn will add it to a "message" stack and do what needs to be done and sends back the response.
As far as I know CCP uses a gzipped python pickle's for this purpose. I'd love a field trip at CCP's HQ. :) hehe

Don't worry, your pseudo code was perfectly understandable.

I figured that EVE is using the latter, so the async way. There is only the question remaining how they maintain the FiFo order of things. I suppose that is the task of the proxy servers, to unmarshal or deserialize the data that is received and decide which one goes first?

Edit:
found a few dev blogs:
http://www.eveonline.com/devblog.asp?a=blog&bid=286
http://www.eveonline.com/devblog.asp?a=blog&bid=678

That just sais stackless IO. Where do you get your information from that each connection is handled separately?

Hullo.
You pose some good questions. As one of the architects of the EVE networking, erm, architecture, I think I can be of assistance:

1. Connection model: There is a single client connection maintained between the client and the game server. As observed, a classic blocking model is untenable because of the sheer amount of threads that would be required for this.
Instead, we use asynchronous communications, with Stackless Python microthreads. Each microthread (or Tasklet as they are more correctly known) sees its communications as being blocking, but behind the scenes an IO scheduler thus blocks it and wakes it up again when IO is ready.
The particular implementation we use is based on Windows IO Completion ports. This does not make use of the select() system call, which would be very inefficient with thousands of connections being handled by a single process. In stead, the scheduler gets a callback on an arbitrary worker thread from the OS every time IO is ready. The scheduler then proceeds to locate the tasklet that was blocked, prepares the results for it, and unblocks it.
The end result is, from the application programmer's perspective, a blocking IO model.


2. Syncronosity: The problem you describe is solved by careful application of Homer's law: Ignoring it and it goes away.
Seriously, think about the problem you describe for a bit:
"if say you hit warp and a little later you opponent in PVP hits on the scrambler."
Realize that you and your friend are sitting in different locations. You are seeing, on your monitors, different representations of the state of the game. Even if you have synchronized atomic clock displays on your wall (ignoring for a bit relativistic effects), you might be in Essex while your friend could be in Tonga. So, according to your atomic clock, you would see everything slightly before him. But even more importantly: His percection of what you are doing is also skewed. He observes your actions through server latency, and sees them long after you initiated them, as measured by your atomic clocks. And the reverse is also true! You observe your friend's actions after the fact too. So, there is a biased symmetric delay mechanic in action between the pair of you.
This makes any notion of simultaneity an feeble concept at best, and the phrase "a little later" becomes meaningless.

On a different level, your intuition about IO scheduling is right, but useless, for a different reason: There are so many levels of delays and reordering present in the physical and virtual networks, that it becomes pointless. Even assuming equal distances to both clients, the order of arrival of the network packets to the host hardware is completely arbitrary. What the network interface hardware then does to it is a black box. So is the operating system which is beyond our control. Even for a blocking model, there is absolutely no guarantee that the first packet in on the wire will cause the corresponding blocked thread to be scheduled before the other. And even if it were, there is no reason why the threads in question could not be arbitrarily rescheduled by the preemptive scheduler before they could even so much as acquire a critical section.
The above should make it clear to you that there exists no inherent order between data arriving on separate TCP connections and therefore it is pointless to pretend that there is and try to somehow maintain it.

Having said all that though, we are careful to try to maintain whatever ordering is presented to our user level program. Since we work with tasklets, explicitly scheduled microthreads, we do schedule them to be run in the order that the IO callbacks from the OS are made to our application (barring of course preemtive thread scheduling of the already executing callbacks.) And we do go to certain lengths to ensure that the tasklets are executed in a round-robin fashion to guarantee fairness to all parties.

Hope that clears things up a bit.

If each connection were handled separately, we'd be talking about a forking daemon that spawns off a child for every connection made. The C10K problem is usually solved by way of asynchronous IO, which means that there is one single application running that handles every connection - separately, yes, they're isolated from eachother, but it's one process that does it.

I also want to clarify that my using select() as an example is hideously oldfashioned. Most *nixes have some form of implementation that allows for registration of callbacks when data is ready, and as such can merrily build on this if needed.

A late addition to this topic, but I stumbled upon that article and thought it might me of interest

http://www.talkunafraid.co.uk/2010/01/eve-scalability-explained/

Cheers

Nathan