Concurrency Control In Multi-Player Games Using Aerospike

Home  >>  Aerospike  >>  Concurrency Control In Multi-Player Games Using Aerospike

Concurrency Control In Multi-Player Games Using Aerospike

6
Sep,2015

1

Concurrency control is one of the main aspects of multi-player games where all the checks, conditional writes and game state updates must be made as fast as possible and with minimal client/server calls in order to keep the game fair and square. This is especially critical in turn-based games where careless implementation (such as putting code that alters the game state in the client) can lead to concurrency related “race condition” from creeping in.

For example, consider a tic-tac-toe game between John and Jane. If John played three moves simultaneously by opening different browser windows before Jane played her turn, sequence of updates would result in John winning the game by way of “cheating.” Good for John but not so much for Jane! (Till she figures out the same technique… yea, John!)

In this post we will look at a web-based tic-tac-toe game with multiple players playing against each other at the same time. This application uses the Aerospike Node.js Client to store and retrieve game data and AngularJS web framework to illustrate end-to-end application development in Aerospike DB.

In this application, concurrency control is achieved by putting conditional writes and game state updates on the server using User Defined Functions. UDFs are a powerful feature of Aerospike DB and they can be used to extend the capability of the Aerospike DB engine both in terms of functionality and performance. For more information on UDFs, click here. But wait, there’s more! Since the UDFs reside and execute on the server, the logic within it gets executed closer to the data with minimal client/server calls. Effectively providing much better performance in addition to concurrency control. BooYah!

Technical Know-how Prerequisites

Even though this is a pretty lightweight application, I’ve used different technologies to make it decent enough – visually & functionally – and covering all aspects as well as walking through the entire codebase is beyond the scope of this post. So, good understanding and working knowledge of the following technologies is presumed.

  • Node.js
  • AngularJS
  • Aerospike DB
  • Aerospike Node.js Client
  • Lua
  • Socket.io
  • Express

Application At A Glance

At a higher-level, here’s what happens — after creating an account and/or logging into an existing account, a user can:

  1. Start a new game by inviting someone to play
  2. Accept (pending) invite to play

NOTE: Users are notified of new game invites in real-time via Socket.io. Therefore, in this version of the application both users must be logged in to see the invites. In the future, I will enhance the app such that users will be able to see all pending invites as well as games they’ve already played. Stay tuned!

As the game progresses with every move, here’s what must happen in order to keep the game fair and square:

  1. The following conditions must be checked

    • Is the game already over? If so, is there a winner and who won?
    • Is it current user’s turn?
    • Is the selected square already taken?
  2. If the above three conditions result in NO, YES, NO respectively, the state of the game needs to be modified as follows:

    • Selected square’s value needs to be set to current user’s username
    • Value of turn needs to be swapped out to the other user
    • Record needs to be updated in the database to reflect this state
  3. Then, taking into account the current state (which now includes the latest move), following conditions needs to be checked and state of the game needs to be updated once again in preparation for the next move:

    • Is the game now over? If so, set status to “DUNZZO” and if there is a winner, set winner to current user’s username

Data Modeling

Before we get to the code, let’s examine the data model. This is important because data modeling is key to having a well performing application with data models at the core. Data models not only define how the data is structured and stored but sometimes they also tend to drive the UI and UX of the application.

In Aerospike DB, a Set (similar to tables in traditional RDBMs) is a collection of records, and each record is a collection of Bins (similar to columns in traditional RDBMs.) In this tic-tac-toe example, the application stores all game data in a Set called “games.” When a user initiates a new tic-tac-toe game by inviting another user to play, the application creates a new record in the “games” Set.

The “games” Set contains these Bins:

NAME DESCRIPTION
gameKey Stores unique ID generated by the application. It is set once when the record is created.
initiated Stores username of the user initiating the game. It is set once when the record is created.
opponent Stores username of the user invited to play the game. It is set once when the record is created.
status Stores current status of the game. Initially set to “PENDING” and other possible values are “IN_PROGRESS” and “DUNZZO”
turn Stores username of the user whose turn it is to make the next move which could either be the initiator or the opponent. Initially set to the opponent and then updated with every turn/move.
winner Stores username of the user who won. In case the game is tied, it will retain its default blank (“”) value.
TopLeft Stores username of the user who picked that square. Initially set to blank (“”) value.
TopMiddle Stores username of the user who picked that square. Initially set to blank (“”) value.
TopRight Stores username of the user who picked that square. Initially set to blank (“”) value.
MiddleLeft Stores username of the user who picked that square. Initially set to blank (“”) value.
MiddleMiddle Stores username of the user who picked that square. Initially set to blank (“”) value.
MiddleRight Stores username of the user who picked that square. Initially set to blank (“”) value.
BottomLeft Stores username of the user who picked that square. Initially set to blank (“”) value.
BottomMiddle Stores username of the user who picked that square. Initially set to blank (“”) value.
BottomRight Stores username of the user who picked that square. Initially set to blank (“”) value.

It’s That Time, Yo!

It’s time to look at some code. In Aerospike DB, UDFs are written in Lua. Lua is a powerful, fast, lightweight, embeddable scripting language. For more information on Lua, click here.

UDF Code

Below are the contents of UDF (/lib/udf/updateGame.lua) that checks, sets and updates state of the game in a single-record transaction manner. It accepts three parameters and returns a map with attributes status and message back to the client.

function update(topRec,username,square)
       local result = map {status = 0, message = "Ok"}
    
       -- STEP: check if the game is over == won
       if topRec["status"] == 'DUNZZO' then
         result['status'] = -1
         if topRec["winner"] == '' then
            result['message'] = "THIS GAME IS DUNNZO -- NO WINNER!"
          else
            result['message'] = "THIS GAME IS DUNNZO -- WINNER IS " .. topRec["winner"]
          end
         return result
       end
    
       -- STEP: check if it is your turn
       if topRec["turn"] ~= username then
         result["status"] = -1
         result["message"] = topRec["turn"] .. " goes next. NOT YOU!"
         return result
       end
    
       -- STEP: check if the selected square is already taken
       if topRec[square] ~= '' then
         result['status'] = -1
         result['message'] = "That square is already taken. IT CANNOT BE YOURS!"
         return result
       end
    
       -- Update Square
       topRec[square] = username
    
       -- Update Turn
       if topRec["turn"] == topRec["initiated"] then
         topRec['turn'] = topRec["opponent"]
       else 
         topRec['turn'] = topRec["initiated"]
       end
    
       -- Update game record
       aerospike:update(topRec)
    
       local status = ''
       local winner = ''
    
       -- Update status
       if topRec["TopLeft"] == topRec["TopMiddle"] and topRec["TopLeft"] == topRec["TopRight"] then
         if topRec["TopLeft"] ~= '' then
            status = "DUNZZO"
            winner = topRec["TopLeft"] -- Top Row
         end
       elseif topRec["MiddleLeft"] == topRec["MiddleMiddle"] and topRec["MiddleLeft"] == topRec["MiddleRight"] then
         if topRec["MiddleLeft"] ~= '' then
            status = "DUNZZO"
            winner = topRec["MiddleLeft"] -- Middle Row
         end
       elseif topRec["BottomLeft"] == topRec["BottomMiddle"] and topRec["BottomLeft"] == topRec["BottomRight"] then
         if topRec["BottomLeft"] ~= '' then
            status = "DUNZZO"
            winner = topRec["BottomLeft"] -- Bottom Row
         end
       elseif topRec["TopLeft"] == topRec["MiddleLeft"] and topRec["TopLeft"] == topRec["BottomLeft"] then
         if topRec["TopLeft"] ~= '' then
            status = "DUNZZO"
            winner = topRec["TopLeft"] -- Left Column
         end
       elseif topRec["TopMiddle"] == topRec["MiddleMiddle"] and topRec["TopMiddle"] == topRec["BottomMiddle"] then
         if topRec["TopMiddle"] ~= '' then
            status = "DUNZZO"
            winner = topRec["TopMiddle"] -- Middle Column
         end
       elseif topRec["TopRight"] == topRec["MiddleRight"] and topRec["TopRight"] == topRec["BottomRight"] then
         if topRec["TopRight"] ~= '' then
            status = "DUNZZO"
            winner = topRec["TopRight"] -- Right Column
         end
       elseif topRec["TopLeft"] == topRec["MiddleMiddle"] and topRec["TopLeft"] == topRec["BottomRight"] then
         if topRec["TopLeft"] ~= '' then
            status = "DUNZZO"
            winner = topRec["TopLeft"] -- Diagonal
         end
       else 
          if topRec["TopLeft"] ~= '' and topRec["TopMiddle"] ~= '' and topRec["TopRight"] ~= '' and topRec["MiddleLeft"] ~= '' and topRec["MiddleMiddle"] ~= '' and topRec["MiddleRight"] ~= '' and topRec["BottomLeft"] ~= '' and topRec["BottomMiddle"] ~= '' and topRec["BottomRight"] ~= '' then
             status = "DUNZZO" -- Tied
          end
       end
    
       if status ~= '' then
          topRec["status"] = status
       end
       if winner ~= '' then
          topRec["winner"] = winner
       end
    
       -- Update game record
       aerospike:update(topRec)
    
       return result
    end

For every move (i.e. user selecting a square) all the client has to do is execute the UDF by passing in the game record key, current user’s username and the square he/she just clicked on. The UDF then takes care of the rest — checking, setting, and updating the state of the game in a single-record transaction — where it always interacts with the most recent (game) record unlike other implementation where conditional writes and updates are coded in the client; where the client can potentially operate on outdated game record and wrongly overwrite true state of the game.

UDF Registration And Execution Code

And here’s how the UDF is registered and executed from the client application (code snippet taken from /lib/controllers/api.js):

exports.updateGameViaUDF = function(req, res) {
  var params = req.body;
  var file = './lib/udf/updateGame.lua';

  client.udfRegister(file, function(err) {
    if ( err.code === aerospike.status.AEROSPIKE_OK) {
      var key = aerospike.key(aerospikeDBParams.dbName,aerospikeDBParams.gamesTable,params.key);  
      var udf = { module:'updateGame', funcname: 'update', args: [params.username, params.square]};
      client.execute(key, udf, function(err, result) {
        if ( err.code === aerospike.status.AEROSPIKE_OK) {
          if (result.status == 0) {
            res.json({status : 'Ok'});
          } else  {
            res.json({status: result.message});
          }
        } else  {
          res.json({status: err});
        }
      });
    } else  {
      res.json({status: err});
    }
  });
};

Note: aerospikeDBParams is defined in /lib/controllers/aerospike_config.js

Eye Candy

User ‘dash’ starts a new game and invites ‘eva’ to play

Invite

User ‘eva’ accepts a game request

Accept Game Request

After a tough battle ‘eva’ wins — shown here are two different browser windows one for ‘dash’ and the other for ‘eva’

Game Over

Game Over

So, Where’s The Entire Solution And How Can I Get My Own Game Going?

Well, the entire working solution as well as instructions on how to quickly get the app up and running are available on GitHub

One Comment so far:

  1. […] Concurrency Control In Multi-Player Games Using Aerospike – @iamontheinet […]

Leave a Reply