Requirements of a chess website
A chess website matches players from around the world and carries their moves to each other with low latency.
Three requirements:
- A matching engine. Players have ratings, and filters feed the matching so that games are between equally rated opponents.
- Latency. A move is accepted or rejected quickly, the opponent is notified, and the time a move spends on the server is minimized.
- An analysis engine, which sends players statistics on their games. It is done in batch.
A player makes a game challenge request: the user ID, the type of game, the color, and preferences such as the opponent's maximum and minimum rating. The matching engine service converts the relative ratings to absolute values and checks whether any existing challenge matches the new one.
The challenges live in a custom in-memory cache built on a sorted set, with a TTL of 30 seconds. A SQL database with range queries backs it up. When memory runs out the cache is sharded: multiple instances of the service, with users directed by user ID.
Handling connections at scale
A chess server notifies the opponent of every move, validates the move, and stays fair to players on slow connections.
Users connect to gateways, reverse proxies that route a request by user ID. HTTP has a client to server relationship: a server cannot send a request to a client. WebSockets give bidirectional communication, and a gateway database records which user is connected to which box.
A direct connection between two players over WebRTC saves bandwidth, but there is no mediator: a hacked client can cheat. A single source of truth needs the game engine.
The game engine keeps a cache of game ID to game state, so a move is checked against the chessboard. The cache is sharded: the game ID modulo the number of servers picks the game engine.
For fairness the server does not trust the client's timestamp beyond a maximum latency, 500 milliseconds. A claimed time within that limit is taken; an older claim is replaced by the time of receipt minus 500 milliseconds.
Consistent Hashing vs. Sharding
Consistent hashing reassigns buckets whenever a server is added or removed. With game state held in an in-memory cache on each server, that reassignment can produce an illegal state.
Server 5 joins the ring and takes the buckets from 351 to 0 from server 4. A service with a cached routing table sends request 388 to server 4, which drops it or redirects it to server 5.
The edge case is a slow hand-over:
- The load balancer tells server 5 to load buckets 351 to 0 from the database.
- The request asking server 4 to remove them is delayed, so 4 and 5 hold the same buckets.
- A black move goes to server 4 and is saved in the database.
- The next white move goes to server 5, which never saw the black move and rejects it.
Asking the load balancer or the database on every request fixes this, and neither is performant.
The chess design uses sharding instead: each server is the sole source of truth for a concrete range. Rebalancing means restarting the servers.
Connection related thundering herds
A thundering herd is a huge number of requests that arrive at the server suddenly.
Millions of users hold connections to three gateway boxes. When user A sends a message to user B, A's gateway finds B's gateway. Querying every other gateway eats bandwidth and fills request queues, so a connections database stores which user is connected to which box.
Adding a feature to the gateway service means a code change and a restart. In a parallel deployment all boxes restart at once:
- Every connection between the gateways and the users is lost.
- All the clients reconnect at the same time.
- The gateways are under tremendous load, and the system is down for a while.
The fix is a separate connection service. The gateway is a dumb service: it creates TCP sockets and forwards the raw data. The connection service holds the logic and the versioned clients of the internal services, such as profile, game and matcher. A client update restarts only the connection service, and the gateway loses no connections.
Request Batching and Conclusion
The chess design has standard services, non real time services and a real time core.
Profile, authentication and sessions are a standard set. Campaign announcements subscribe to events on message queues.
Three services run as a stream or a batch. The cheating checker compares a day's games with a chess engine, on moves and on timing. The rating engine receives wins and losses as a stream and writes ratings to its own database. The game analyzer runs for premium users.
All move requests go to the game engine, which shards its cache by game ID. The matching engine finds two requests that satisfy each other and creates a game.
The spectacle service broadcasts moves to spectators, and two or three seconds of delay is fine. With 10,000 spectators, 5,000 in India and 5,000 in the US, it sends one request to each gateway with the list of user IDs, and the gateway duplicates it at the last mile.
The design comes down to latency, bandwidth and the number of connections per box.