I would like to know how matchmaking in fps games is done. Is there a main server which has has the list of all the other logic handling servers? I don't think this is the case cos it will increase the lag when 40k+ players are searching for a match. I am extremely new to the topic of production-ready multiplayer games. I have only worked on sample multiplayer web games that run on a single server.

Matchmaking 40,000 players isn't actually impossible for a single server. That's not THAT many players.

However, systems often shard vertically by region (Europe vs US vs Asia vs Australia vs South America for example.)

They can also shard horizontally by, say, game type, or perhaps skill level range. Map the ten percentage ranges to ten servers – percentile 0 - 10 get server 1, 10 - 20 get server 2, … You could make people “close” to an edge be handled by two different servers – if I'm at percentile 20, maybe I get matched in the 10-20 range, or maybe I get matched in the 20-30 range.

In general, production game servers are only slightly different from production web servers – web servers can use HTTP proxies, and can use a CDN for non-real-time data, but there's always a front-end load balancer of some sort, which probably also works as a firewall and reverse NAT, and then there's a pool of servers that incoming requests get spread across. Sometimes there's a “master redirector” that tells each connection where to go, other times you just get a random shard and the shards end up connecting in a mesh to talk to each other.

If you have more specific questions, feel free to keep asking!

If you have 40,000 players simultaneously searching for a match, then you've got other issues. Since matchmaking is usually only a tiny slice of the game, that means you're likely having many hundred thousand concurrent players. Success is a terrible problem for networking.

Even in popular games there are usually only dozens or sometimes hundreds of people in active matchmaking sessions. Even if a game is tremendously popular like Fortnite or LoL, at any given moment there are only a small number of matches being put together. A modern PC can handle billions of operations per second, sorting the score of 30 open lobbies (or even 3000 open lobbies) is not a big deal at all.

But apart from that, H+ handled the bulk of it. Player rank, server regions, player ‘niceness' values (bundle the suspected cheaters together, bundle players with high complaint rates together), and many other factors can all be turned into a numeric score. Location is another good one, with both player-specified regions and geo-ip working together, which he didn't mention. Two players estimated to be 500 miles apart is fine, two players 10000 miles apart is a problem for lag. Replaying with people you've seen recently is another possible feature, either preferring or rejecting matches based on recent play.

Coming up with the score can be however you want. Factors may add, subtract, multiply, or divide. Having a wrong map may multiply by 0, giving a bad score that you'll never join. Use whatever math you want to produce a number. This room has a score of 73253, that room has a score of 103213, another room has a score of 150. The server can iterate through the open rooms, look at the matchmaking criteria, and compute a score. Filling out the final few players can have a better score than an empty room, closer estimated physical distance can have a better score, having similarly-ranked players can have a better score. Use whatever math you want to produce a number.

Sort the list, take the highest score. If no room has a sufficiently high score, start a new matchmaking room containing that player alone.

Many good ideas from frob. Additionally, in addition to “what is the score of joining this particular room,” you will for skill-based games end up with the question of “what is a potential group of good-match players?”

This ends up being harder than a single list, because every player could potentially have a different sub-graph of who they'd work well with. In general, this is a graph query, and looking into efficient graph algorithms will help a lot here.

There are a number of cool algorithm tweaks possible, or even necessary. For example, if you sort player skill level ("MMR" or somesuch) and sweep from bottom to top, trying to put together groups where everybody is within 10% of everybody else in each group, you'll get a number of good groups. You'd start with player P, and then gather players into a group while you find players below skill P*1.1. If you get to the group size, you're done. if not, then start losing players from the “tail” of the group, adding players to the “head” of the group, until you get the group size. Once you have a gruop, declare that group as matched, and remove them from the waiting list, and set P to the next un-matched player in the sorted sweep.

But what if players can “block” other players? You'll want to not include players with a blocking relationship in the same group. This means you'll have “random dots” of players along the sorted axis not joined to groups. To avoid those players having to wait forever, you might want to sweep not bottom-to-top, but instead sweep starting at the longest-waiting player, and build multiple groups in parallel. (This ends up being a clustering algorithm, which ends up being a graph subset algorithm, again!)