A distributed match-making service – part 2

This is a post from the match-making series. You can check the part 1 here

If you wanna check the code in the exact state the project was for this post, get Coulomb @ tag v0.1 on GitHub

Last post we decided what we need in a system like this. We got a simple view on what a match-making looks like, and also saw what other companies are providing.

This time I’m gonna lay out what the workflow for a match search should look like, and what alternatives I have thought to approach it.

Coulomb? Like the one in electromagnetism?

Before we procceed, I’d like to introduce you the name I gave to our match-making service: Coulomb.

The name sounds nice, and was thought upon Charles-Augustin de Coulomb. Who described the electrostatic force of attraction and repulsion.

Coulomb's Law pictured
Coulomb’s Law pictured, CC BY 3.0 taken from Wikipedia

From now on, when you read Coulomb, think of “the match-making service we are creating”.

Workflow of a match-making service

There are many variants on how the process can go.  I’m gonna describe the one we’re following. Where applicable, I’ll show what could’ve been different, and why.

Step 1 – The user wants to find a match

Once the user press the UI button to find a match, the client should tell the server which kind of match the user wants.

The client might be either a game, a web browser or whatever else.

A persistent connection protocol should be used when the user communicates with the server. You might for example choose TCP or UDP with a keep-alive.

You can make it work with a connection protocol that is not persistent, like UDP without a keep-alive, or HTTP (HTTP have TCP under the hood which IS persistent. But most backend frameworks won’t tell you when a connection was lost). But you’ll suffer from users that change their mind and don’t want that match anymore. You’ll keep searching the match for them, just to find out they don’t want that match anymore.

Step 2 – The server tells Coulomb to find a match

Once the server has the info on what kind of match the user wants, it should create an unique identifier for that request and ask Coulomb to find a match using the user data.

Coulomb will use the identifier to keep track of the request internally and to help the backend server associate the received response once the match is found.

The identifier just needs to be unique in that moment, not globally. Using the user own ID is fine, since most of the time, the user can only find one match at a time. The unique identifier might be a generated UUID as well, but that means one more complexity to handle on the server side.

Since the server can reliably tell Coulomb when a request should be canceled, the server can communicate with Coulomb with any kind of protocol. To put this in emphasis, Coulomb will probably have more than one “front-end”.

Step 3 – Coulomb looks for a match

This is the part we’re thriving to do, the heart of Coulomb. I’m going to describe it very abstractly and we should not come to a conclusion on the algorithm and storage used on this part for now. This is so important that it’s going to be on a separate post.

As requests come into Coulomb, it should save this request in some kind of storage.

Every time a new request come, Coulomb will check the storage to see if there is a new match. As we relax some parameters on a time basis, Coulomb still check for matches made from time to time.

Once Coulomb finds a match, the server will have an answer with which identifiers were paired, and which kind of match they are in.

Step 4 – The server tells the users about the match

With the match info, the server might want to do stuff like register the match in a room server.

The server might want to decorate the response with more info, before telling the user the match is found. Good examples are info about who are their opponents and which kind of match they are going to play.

When telling the user about the match, the server might even ask for a confirmation. The match will be made only if every user confirms. Otherwise, the match is cancelled and the server start looking for a match again.

What are our goals?

In all this process, we are interested in the services that Coulomb will provide. The ways to ease the communication between the actors is also of our concern.

The server and the client-side are not our main goals, but they might be explored a little.


Play with it!

I dropped on the first few paragraphs a link to the Coulomb project repository on GitHub. On the tag v0.1 you can test the project with already some of the functionality we talked about here.

Running the server

You can run the project with gradle. Go to the root of the project, and run it:

gradle :bootRun

You’ll know when it’s running once you see:

DEBUG c.t.coulomb.matching.MatchMaker - Waiting for new match requests.

As we talked earlier, even if no new matches requests come, you’ll see every few seconds a message

DEBUG c.t.coulomb.matching.MatchMaker - Processing requests

This means that it’s trying to look for a new match.

Sending requests

For now, we have only one “front-end” which is the HTTP one. You can register match-making requests by making HTTP requests. It’s straight-forward and simple:

Open a new terminal tab, and send a request, for example:

curl -isS localhost:8080/?id=einstein

Coulomb will log

DEBUG c.t.coulomb.web.MatchController - Receiving match make request

Wait for a moment. You’ll see that for as long as other request do not come, curl will hang. So lets make another request on a separated terminal tab.

curl -isS localhost:8080/?id=coulomb

Both requests should have returned with the following info:

HTTP/1.1 200 OK
Connection: keep-alive
Transfer-Encoding: chunked
Content-Type: application/json;charset=UTF-8
X-Application-Context: application
Date: Sun, 08 Jan 2017 02:36:39 GMT

{
    "peers":[
        "coulomb",
        "einstein"
    ]
}

So it works! We’re making matches of two people.

Terminal showing Coulomb's match-making working
It works!

Extra: Design choices

I made some decisions in this workflow which might seem odd at first. Here are my thoughts on why I took them:

Clients can’t talk to Coulomb directly. A server should do it.

This was an interesting question and took me a while to finally decide it. Quoting the first post, I thought of Coulomb as:

a service that I send a request saying who am I, and what modes I want to play. Some time later that request must be answered with who I have paired which, and with which server should I continue the conversation to start my game.

But that was too idealistic.

First, if Coulomb actually knew who the user is, it would also need to know how to authenticate users. Is the user who they are telling to be? Can this user really play this kind of game? Does Coulomb need to know this user ELO/MMR? If not, can Coulomb trust the value the user is saying to have? That would already increase the complexity a lot.

Second, Coulomb would have to know which room servers were available and how to load balance them. Having to also know how to register a match in a room server would be quite bad too.

So to avoid all this coupling. Coulomb is simply a match-making service. Coulomb is not a game coordinator. This simplify stuff and will make it far more reusable.

Users MUST use a persistent connection with the server.

This came to me once I was developing Coulomb’s proof-of-concept over HTTP and found out that cancelling a request wouldn’t stop the search. As I thought Coulomb would be facing the users, this became a high concern to me.

Of course this is only a recommendation, since we can only control Coulomb. But things are much simpler if you make a coordinator this way.

If you want to make a fast matching application (like chat roulette), maybe you can get away with this.

If your backend framework tells you when a user cancels the request, or gives you a broken pipe exception, maybe you can get away with this.


Next steps

On the next post we should decide on some architectural choices and talk a little about “The Algorithm”

Part 3 is not out yet…

  • Pingback: A distributed match-making service - part 1 - Gustavo Maciel()

  • Isaac James

    Why are you calling this “Distributed”? This is the opposite of distributed. This is centralized.

    Distributed would be if the clients talked to each other and found matches.

    • Gustavok

      Hi Isaac! Because a Coulomb cluster is going to take care of making the matches. Just like a Cassandra cluster is able to decide where to store and retrieve your data.

      I still haven’t even begun talking about how the match making will go!

      I’m not sure I’ll still follow this approach I first thought of though. But let’s see what turns out 🙂