Colyseus: Match-making in a clustered environment

[endel]

This question pops up often in the gitter channel. Currently there's no cluster support for Colyseus.

The rough idea is to separate match-making server from room handler (game session) processes:

• [x] Match-making should be a central unit to determine which server/node should the client join
• [x] Vertical scaling: Room handlers can live on multiple processes
• [x] Release version 0.5.0!

Any thoughts and ideas are welcome :)

[darkyen]

I'm implementing my owns system for this and here are the highlights of my system and how I'm achieving those things. Although I did not have knowledge of Colyseus and this is a fairly simple system I implemented for my own requirements which is slightly similar to bucket sort. I'd also be happy if the more experienced people would like to loop into this. I'm currently porting this to use colyseus

I have an interface Requester (peer) which must implement a function getInfo which may return data about the peer. This function is called when initializing the peer and can be fetched from a database/in-memory adapter etc.

The Requester goes inside a bucket called Room. Each room has a function matches(arg) which accepts the info returned by Requester.getInfo and returns 0 - 1 to measure the suitability for the player in this room. In my simple implementation I have a min. skill level and max. skill level which which check if the user's skill.

There is a singleton MatchMaker which does the actual match-making the algorithm for match making is as follows. Please note all the methods here are async and things can wait for completion.

Expand step:

• Every time a new peer arrives
  
  
  
  • Find the best room for the peer based on the matches.
  
  
  • If no match satisfies this criteria create a new room. This maybe left unimplemented if a single static list of rooms/servers is to exist.
  
  
  • Add player to the found or created room.
    
    
    
    
    
    • If the room is full start the room.
    
    
    
  
  
  • Increment time to wait for other people to join before we start the crunch step.
  
  

Crunch step:

• When we have waited long enough and the room cannot be started
  
  
  
  • If there are lower players waiting then needed.
    
    
    
    
    
    • Handle this (create a bot, tell player not happening, something else?).
    
    
    
  
  
  • For every room which is waiting expand the criteria.
    
    
    
    
    
    • This can be done either by merging rooms with closer avg. skill level.
    
    
    
    • Wait for next cycle.
    
    
    
  
  

The advantage of this simple algorithm is that it can read from a global state and as both getInfo and matches are provided by the developer. This can handle very complex scenario's like ping to servers, multiple skill differences, team balancing etc in the matches method. Bonus is that this can live in its own package and can be independent of colyseus the matched players array can then be sent to the server & client in the "start" method handler which will then connect to one another.

The disadvantage is that this system will punish a game with lower number of clients and even more when the gamers average skill level is higher. This will require a centralized authority and will not very well (or at all) in disturbed environment. Although multiple instances can vote for a leader which decides the pairing and then initiates pairing on that master. Wait times can be reduced by making the clients and rooms wait aware so that they compensate for waiting clients.

[endel]

Apparently, socketcluster solves pretty well scaling vertically/horizontally. I'm starting to investigate how to integrate the cluster module in the framework.

[endel]

Here are my thoughts at the moment:

• Rooms/sessions are stateful and they'll live in some process.
• The server will spawn multiple processes for handling sessions, and a single process for match-making.
• New connections will only be able to communicate with the match-making process
• Once the user joins a room/session, all his messages will be forwarded to the process that session lives (by using sticky sessions)
• New rooms/sessions will be spawned on the process with least number of spawned sessions.
• After the user leave the room/session, his connection will be forwarded back to match-making process

Following this new architecture, it won't be possible to join to multiple rooms re-using the same connection. If the game you're building need to connect to multiple rooms at the same time, multiple connections will be necessary.

What are your thoughts? I'd appreciate your input on this! Cheers!

[TinyDobbins]

I support the idea one connection to one process. can't imagine the case when client need to connect to multiple rooms in the game.

[endel]

Update: A simpler approach would be that all workers in the cluster have the same responsibility, and they all can perform match-making and host game sessions.

Therefore the match-making module should be stateless, and store/fetch data from a single source. I don't want to increase complexity by adding Redis as a dependency for that, so I'm thinking about writing a simple redis-like in-memory database that passes messages between master and worker nodes in the cluster.

Game sessions will remain stateful as always.

[endel]

I've started a project called memshared to manage the memory sharing between workers. Some basic list commands are still missing: https://github.com/endel/memshared/issues/3

The idea is to keep things simple and not make the framework strictly dependent on an external service like Redis. While, at the same time, allow to migrate to Redis eventually when there's an actual need for it.

[endel]

Update!

Cluster support is on its way! The main problem I have right now is how to treat passing a socket to a child process differently, based if it's a WebSocket or a regular HTTP request. Some discussion about this problem here

Here's the state of what I have right now:

1. Identify a WebSocket connection in the upgrade callback, and pass it to a child process. (See source)
2. As @lpinca suggested on https://github.com/websockets/ws/issues/154#issuecomment-304611958, it is possible to identify a regular HTTP request on the request callback, but I didn't have success on handling the connection in the child process itself.

The WebSocket connections work fine. The problem is regular HTTP requests that are getting stuck.

Breaking changes

Version 0.5.0 will introduce a couple of breaking changes, in the client and in the server. You can find a draft of the current migration guide here. I'm glad to discuss their impact and improvements before the final release.

[endel]

Version 0.5.0 has been released with this feature!