Persistent Matchmaking Groups

I'm DJ Hirko ([S2]Deejay), the lead programmer of Heroes of Newerth. I'm writing a post today to give you a look inside the nitty-gritty technical aspects of working on Heroes of Newerth.

One feature we've planned to add to HoN, and actually did have for a few hours, is persistent matchmaking groups. This would mean that after playing a matchmaking game with a group, you would still be in that group and wouldn't need to re-invite everyone next game. It's a very nice "quality of living" improvement for our loyal players.

The original matchmaking code was written to get good match-ups in a timely manner. It worked pretty well, but had scalability problems. These scalability problems laid dormant until the first attempt we made to add persistent matchmaking groups. Our stats showed the number of groups quadrupled, leading to very poor performance on the chat server. This was quickly pulled and has sat on the shelf ever since.

Now here's where it can get pretty technical. We've made huge changes on the chat server to improve its performance. Many O(N^2) algorithms were reduced to O(N) or even O(1) and we now use a separate process on the chat server to matchmake. After these changes, the chat server's peak frametime was lowered from 13000ms to 1200ms. This is a great improvement, but it's still higher than we're aiming for. In order to add support for persistent groups again, we need to further optimize the chat server, and that's where I/O completion ports come in.

Our profiling data shows that 41% of frametime (i.e. peaking at 480ms) on the chat server comes from polling sockets to see if there's data waiting, and if there is, receiving it. This time does not include processing the data - just polling and copying! Polling an individual socket is fast, but it's an O(N) problem - it grows linearly with the number of sockets (including clients and servers). The best solution to this problem that we've found is a Windows feature called I/O completion ports.

Windows supports I/O completion ports for a variety of asynchronous I/O functions - the pertinent one here being reading socket data. I/O completion ports are an OS level messaging system. When you call an asynchronous function that's hooked up with an I/O completion port, a message will be queued up when the function call is finished. Instead of processing the socket immediately, we instead associate the socket with a shared I/O completion port, call an asynchronous read, and then process the messages as they're created. This reduces the O(N) problem of polling socket data to an O(1) problem, since we no longer need to loop over all sockets - we just process the messages as they're posted to the single I/O completion port. This reduces our peak frametime from 1200ms to 760ms, leaving plenty of space for us to add a new feature like persistent matchmaking groups.

These changes will be going out soon and from there, you can expect to see persistent matchmaking groups being added in the near future.

I hope this was informative and thanks for reading!