Concurrent mutual exclusive actions using atomic counters

A multi-player game scenario

Imagine you’re a game developer building a multi-player game and you would like to use client-side code only. You don’t want to write any server-side code let alone manage the required server infrastructure. The game action happens at each player’s device and you’re using some messaging BaaS (e.g. Realtime Cloud Messaging) to handle the game state sync between players.

In this game users concurrently compete with each other to get hold of game assets. It could be a weapon, extra-power or some other perk that will increase the player competitive advantage on the game.

If these assets can only be exclusively awarded to one player in the game you’re bound to face a problem: what happens if two or more players concurrently select the same asset at the same time? You can’t award it to all the contending players so you need to select only one and you need to do it fast in order to keep a great UX. What would you do?

Database transactions?

You could use a database transaction to read the status of the asset in order to check if it’s still available. If it is you would update the status to granted and commit the transaction. All the other pending transactions would resume and the player would be notified that he or she got the asset. But the keyword here is “pending”. Database transactions use locks and with high-levels of concurrency the UX could suffer from long delays. If several distinct games (e.g. different worlds or universes) were being played at the same time it wouldn't be difficult to design the database schema in a way where locks from a game would impact users from another game. Not good.

REST API with FIFO queue?

You could develop a REST API with a route that players would invoke whenever they want to select an asset. This REST API could be distributed into several frontend servers for scalability and each frontend server would push the player intent into a FIFO queue (I’m thinking REDIS). A backend worker would dequeue the intents one at a time and interact with the database using no locks. As you've probably spotted, this approach is also locking requests through the queue, so latency increase is expected as the requests frequency increases. But more importantly this approach requires server-side code and infrastructure management, something I've said in the beginning that you didn't want to do, so it’s not really a solution here.

Atomic counters

In concurrent programming, an operation is atomic if it appears to the rest of the system to occur instantaneously (more at http://en.wikipedia.org/wiki/Linearizability). A counter is some numeric property that can be incremented and decremented.

Given these definitions we could define an atomic counter as a number you can update “instantaneously” (increment/decrement).

Since the operation is “instantaneous” you don’t care if there are a lot of them happening concurrently because only one update will be performed at a given instant. When these atomic counters are available in a database management system, e.g. Realtime Cloud Storage, you get a powerful primitive to solve the mutual exclusive actions challenge.

How?

Each asset in the game is initialized with an atomic counter set to the integer value 1. We set it to 1 because we want to award the asset to only one player in the game (the rational is the same if you want to award the asset to a certain amount of players: just set the atomic counter to the number representing the maximum amount of players that can select the asset).

Whenever a player wants to select an asset it simply decrements the asset counter and inspects the result. In our case, if the result is 0 then the player gets the asset as it was the first one to capture it. If the result is lower than 0 then the player missed the opportunity as the asset was already awarded to another player.

The atomic property of the counter plays a crucial part in this solution. As it guarantees that only one decrement occurs “instantaneously” at a time and each player gets the end result of its own decrement, you don’t have to worry about concurrency. The players can all try to select the same asset at the same time but it will only be granted to the first one decrementing the counter. All the others will get negative values.

In your game logic you just need a simple condition to verify if the asset selection was successful (counter == 0). If that’s the case you can proceed with the asset grant logic in the winning player’s device. In the other players you can simply proceed with the “failed to grab asset” logic (maybe some warning buzz).

Using atomic counters-as-a-service with Realtime Cloud Storage

As stated before the Realtime Cloud Storage database, based on Amazon DynamoDB, allows you to use atomic counters as-a-service. This means you get all the benefits from the atomic counters at all levels of concurrency, without the need of managing the code and infrastructure that supports them.

But it gets even better! Through the Realtime Cloud Storage SDKs or REST API you can use the atomic counters directly from the player’s devices! This means “mission accomplished”: concurrent mutual exclusive selections without managing any server-side code and infrastructure.

Below is the required JavaScript code to implement a basic mutual exclusive selectAsset function using the Realtime Cloud Storage JavaScript SDK:

Conclusion

Atomic counters are a great primitive to control state in multi-player games and using them as-a-service with the Realtime Cloud Storage database is simple and cost-effective. With no server-side code to maintain and no infrastructure to manage you can spend more time improving and adding more features into your game.

Let me know what you think about this solution and if you have other atomic counters use cases please share, I’d love to hear from you.