Loading...
user can start a game, server match a user for it.
user can make a move
user can regret chess
server return success/failure after move.
CAP: Prioritize consistency, compromised availability
latency: see move in realtime
scalability:
fault tolerance:
10M DAU, each user play 1 game/day, each game last 10min
each game has 50moves in average
10M * 1 / 2 * 50 / 86400 = 2.5k/s peak 5k/s
read write ratio : 1 : 1
bandWidth 2.5k * 30B = 75KB/s
storage store 1 year
5M * 50 * 30B = 7.5GB
7.5 * 365 = 3TB/year
getBoard
get /api/v1/board/
request userID, gameId
response board
move
post /api/v1/move
request userId, fromPos, toPost
response status(win or loss or running)
start game
post /api/v1/game/start
request userId
response gameId, serverID
Move Db(nosql)
moveID --pk
from
to
userId
gameId
type //move or regret
lastUpdated
game DB(sql)
gameID --pk
user1
user2
status
winner
Board Cache (in-memory cache)
key boardId
value board
As for the high level design, we have match Service, which takes in the user ID and match another user and return. And the Match Service contact connects with the Web Socket Manager to get a corresponding web server and return the web server and game ID to client.
And the match Service also creates a new game in the game database. And after that, users set up a web socket connection to the corresponding game server.
The game server is state 4. And now user can start playing the games. So a user, when user send a move request to.
The move. Service it, the move service will validate whether the move is valid, whether the current user can move, and whether after the moves, the game will end.
So, if it's invalid, just return invalid. And if the. After moving the state, the game is an end date. The moved service will update game database and move data game database as well.
And each time after move, the move service also updates the board in the board catch.
That's how it works.
Next, I'll discuss the war recourse flow. So when user start a game, it send a start request to the match serve to load balancer, load Balancer root recourse to match server and match server start matching and hold requests.
And after maybe several seconds, Match Service, match a user and the return us. Then match service, select a state for Game Server from the web Socket manager, and return the server and game ID to the client.
Next client can initialize a connection with the game server. That's how the client starts a game for move. Client send a request to them state for serve to the game server and game send server send requesting move service and then move service validate the move.
If the move is invalid, just return force. And if the move is valid, it's going to insert the move into the move database and update board catch as well.
And then it checks whether the game is over. If the game is over, it just update game status. Okay, next Move Server returns the request.
Move service return the response to the game.
A stateful game server and game server send it back to the client via the web sockets manager. So sorry, web socket.
For regret, it's quite similar.
Also calling the move step.
The regrets request goes to the state for server and state for server goes to move service checks, move database to see if there's any, to see if last move is s is another user.
To see if the last move is currently user. If the last move is currently user, just insert a regret move record into the move database and insert it into the broad catch about catch.
And after that, move service, return to game state for Game server and Game server will send this move to both two players.
Yeah.
Next, I'm going to discuss concurrency issues. Because if one user send a move, while another user send a regret, this will cause a concurrent issues.
So the id, the solution that we can have a distributed Lark. So before one user start a move, it will lock the game ID in the correspond in distributed Lark storage and set a time to set TTL after it finish the move, it unlocks.
Basically unlocks that lock. This can make sure that each time only one user is modifying the database. We're not using locks in the Move d database directly, because.
We have like 10th of moves. It's not possible to have a lock to all these moves, right? And actually, we're inserting a new move in the move database.
So I think it's to lock this, we have to use a range lock to lock this part, and I don't think it's necessary.
That's why we use a distributed lock.
And for the catch part, I also dive deep into the catch part. For catch, we have basically have two kinds of strategies.
That's catch aside and write through for catch aside policy, the management match move services responsible for maintaining the consistency between move DB and broad catch for right through move catch, move Service Index with broad can catch directly and catch it in responsible for maintaining the consistency between move DB and catch.
And in our design, because the catch and database stores different formats of data, we are, so we are using cache side policy.
So when the Match service visited Move DB, it immediately, it first invalidate the broadcast. And after move.
Because we already have a distributed Lark, so we can maintain a consistency between catch and database. We don't need to invalidate the bar catch, right?
Okay, that's pretty much.
SQL vs NOSQL
sql: strucutred data, acid, complex join
nosql: unstructured data, heavy write load, natively support horizontal scaling.
for move db, we have to handle heavy write load, and horizontal scalling, it's better to use nosql.
for gameDB, it's strucutred, low write qps, we need acid, so we use sql.
for board, it's not important and if data loss, we can rebuild it from moves, for fast access, we store it in in-memory cache.
push vs pull
Next, we're making trade off between polling long, Paul.
Okay, so because it's a real time event, so we have to make sure that server can proactively send, if send records to user side.
So we have to use like pouring. We're making tradeoff between push or pull. Push is server side push records to client side.
Pool is client side periodically pour the server. So for pool, sorry, for pool, we have pool and long Pauling base is basically user periodically pause the database and.
It can increase load of the server. It's not good idea and for long, pory. It's that server make us client side send a pool to server side and server side do when the data is not variable, server side hold the long pouring request and.
Until the data becomes available for long pouring, it's difficult to design the timeout time because if the timeout time is too short, it becomes.
It becomes pooling, right? But if the time of time is too long, the holding the records can occupy a lot of server side resources.
So we are using push approach here. For push, we have basically have two ways, service and events. And hdp web socket is by directional, is by their work.
You know, while service and events only allows user server to send events to user side. Because in our design, here is a s is a bi directional communication.
To discuss the fourth tolerance and bottleneck for the Match Service, Move service, they're both state less. So if one service crashes, it load balance will root it to another's service.
So it's okay for the database. We basically have two kinds of replication strategies. Must use, must slaver replication and.
Peer to peer application for mass slave replication must node is responsible for read of, sorry, must know is responsible for right.
And slaver node is responsible for read. So, read a note, replicate data from master node. So if must node crashes slave, a note will be elected as a new leader.
And if a slaver note crashes, when a new slaver mode becomes a variable, it will replicate data from must node again. And for peer to peer application.
The two algorithms are use here that is consistent, harsh and column consensus. A consistent harsh when a right records RES arrives, it will go clockwise and until it reach the first node and then replicate the data to the next several nodes in the harsh ringing clockwise order.
And when half of these notes replied, ace acknowledged the right the state it will treat the right as success. So in this case, I, if one node crashes another node in the clockwise or the next node in hush ring in clockwise order, will the serve that read write records.
As for web sockets, this state servers are state 4. So if one user, if one server crashes, both two users will lose connection, but the users will visit the web socket Manager and reset the web socket connection again.
And after that, the users will use the get API to get the keyboard from server side. So it can also recover from the failure.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?