Improving the Latency in a Redis backed Leaderboard Service

This is an overview of a techniques to reduce latency between a Redis server and the App server in a distributed system using OpenResty and Lua.

At Yarsa Games, we build real-time multiplayer games played by people all around the world. Our application servers are provisioned automatically to distribute the load from all around the world. Even a single second of latency is not acceptable because of the nature of real-time multiplayer games. In this story, I'm sharing how we introduced OpenResty and Lua in our real-time leaderboard service to cut down latency to half. We were able to decrease the round-trips by piping the Redis commands together.

Background Information

In small to medium application servers, the database server is usually installed in the same physical server, or at least in the same virtual private cloud (VPC). There is little to negligible latency between the application server and the database server. However, in large applications where application code runs in multiple data centers scattered across the globe, the database is hosted in different locations. The latency due to the physical distance between the application server and database server is quite noticeable.

The Latency

In the worst case, an application server and database server are apart, and the latency is approximately 1000 ms ignoring the database operation time. Now let’s take an example query where you need to update bulk data (say n = 4) for four players after a match ends. You might be tempted to run four different commands, eventually leading to a 4 seconds delay in updating the scores for all four players.

Reducing the Latency

When you're developing on your local machine, it's easy to fall prey to all kinds of mistakes that increase latency without even realizing it.

Avoid Database Operations Inside a Loop

...
for ( const player: Player of players ) {
  // calculate score
  const gameScore: number = calculateScore(player);
    
  // publish to redis (takes 1000 ms)
  await publishScore(player, gameScore);
}

// total latency: (1000ms x players.length)
...
Database operation inside a loop.

Notice line #7 in the above example code. Not only are we connecting to a remote server to publish each player's score, but we're also performing an unsafe operation here. The scores will be totally messed up if the database server stops functioning in the middle of the operation. We need to have a different system to roll back the previous operations in case of failure.

Instead of looping through the results and running the database operation commands, we can fetch the data first, then use bulk operations instead. For example:

...
const scores: { score: number; player: Player }[] = []

for ( const player of players ) {
  // calculate score
  const gameScore: number = calculateScore(player);
  
  // push to scores
  scores.push({ score: gameScore, player: player })
}

// publish to redis (takes 1000 ms)
await publishScores(scores);
    

// total latency: (1000ms)
...
Database operation outside a loop.

Use Redis Pipelining

Redis supports pipelines that help us avoid multiple round trips to the server by combining multiple queries. Read more about using pipelining to speed up Redis queries here.

The Leaderboard Use Case

I was using a Redis server to store player’s leaderboards in sorted sets. The leaderboard would reset every day so the new players could also have a place in the leaderboard.

Let's assume we have a sorted set called scores in our Redis database. When a match ends, I had to increase or decrease each player’s score.

In some cases, I had to fetch multiple items from multiple sets and perform mathematical operations to the existing ones, then push the changes back to Redis. Performing mathematical operations on the application service introduced unavoidable latency. While Redis supports some bulk operations for fetching multiple values from a sorted set and setting values like the zrevrange command, it does not support bulk mathematical operations on commands like zincrby. That's why some of the processing had to be done outside of Redis.

Introducing OpenResty and Lua

As we needed a wrapper around our Redis server to perform the mathematical operations, and preferably an API that would make interacting with the Redis server easier, I started looking for options. One option that I considered was writing a thin Node.js application. I'd eventually need a web server or a load balancer on top of the Node.js app for SSL termination, dynamic routing, throttling and more. I thought OpenResty with Lua would be a good fit. OpenResty is a fork of the Nginx web server, and it supports Lua scripting out of the box.

I installed OpenResty on the Redis server and decided to write the logic of the operation in Lua. Introducing OpenResty didn't impact the performance of the Redis server because Redis was mostly heavy on memory and sparsely used the CPU resources. OpenResty is heavier on the CPU, so cramming one more process into the machine didn't cause any significant difference in performance. As good as it gets, there's an official plugin called Lua-Resty-Redis, that is directly connected to the Redis server running in the same machine. This setup could only reduce latency!

Combining this setup with the Redis pipeline for bulk zincr on the sorted set, I was able to take away the last bit of latency there was. Look at the sample code to understand how I put everything together.

Bulk Set Operation

In most cases, we need to increase or decrease the scores of the players after every match. In some cases, we need to update multiple leaderboards at once. However complex the scenario may be, you can send a complex object as the request body to the OpenResty server.

[
  {
    "leaderboard": "coins",
    "score": 40,
    "player_id": 1
  },
  {
    "leaderboard": "coins",
    "score": -40,
    "player_id": 2
  },
]
Example Data for Bulk Update

Here, for the sake of simplicity, look at the above example data sent after a match between two players. The first player's coins need to be increased by 40, whereas the second player's coins need to be decreased by 40.

You can use Lua to parse the request body, traverse the list, or normalize the data structure to fit your needs. Then use Redis pipelines to perform the bulk operation in a single go.

http {
	...
    
    server {
        ...

        # bulk increase player scores to a leaderboard
        
        # body: an array containing leaderboard name, score & player_id
        
        location /set {
            default_type 'text/plain';
            content_by_lua_block {
                ngx.req.read_body()
                
                -- plugins to parse json & connect to redis
                local json = require('cjson')
                local redis = require('resty.redis')

                -- connect to redis
                local red = redis:new()
                local ok, err = red:connect("127.0.0.1", 6379)

                -- read and decode data in body
                local body = ngx.req.get_body_data()
                local your_data = json.decode(body)

                -- initialize redis pipeline
                red:init_pipeline()
                
                for i = 1, #traverse your_data
                do
                    local lb = your_data[i]['leaderboard_name']
                    local scores = your_data[i]['score']
                    local player_id = your_data[i]['player_id']
                    
                    red:zincrby(lb, score, player_id)
                end
                
                -- commit the redis pipeline
                red:commit_pipeline()
            }
        } #end /set
        
        ...
        ...<get>
        ...<del>
        ...
        
    } #end server
} #end http
Bulk ZINCRBY Operations on Redis using Lua

Bulk Fetch Operation

Every time a player wants to see the leaderboard, they are also interested in their rank in the leaderboard. We cannot get both the list of items and their rank from the Redis using a single command. We had to do a double round-trip to fetch the leaderboard. Pipelining wouldn't be useful in this scenario. Fortunately, we can use Lua to fetch the leaderboard list and the player's rank with one round-trip to the Redis server.

# fetches the sorted scores for the leaderboard,
# and the palyer's rank, from the leaderboard

# params: leaderboard, player_id

location /get {
    default_type 'text/plain';
    set_unescape_uri $name $arg_name;
    set_unescape_uri $id $arg_id;
    content_by_lua_block {
    
    	-- plugins
        local json = require('cjson')
        local redis = require('resty.redis')

        -- redis connection
        local red = redis:new()
        local ok, err = red:connect("127.0.0.1", 6379)

        local nameOfSet = ngx.var.name
        local returnData = {}

        -- leaderboard with scores
        local data, err = red:zrevrange(leaderboard, 0, 100, 'withscores')
        
        --  the rank of player
        local rank, err = red:zrevrank(leaderboard, ngx.var.player_id)

        if data then
            returnData['leaderboard'] = data
        end
        
        if rank then
            returnData['rank'] = rank
        end
        
        ngx.say(json.encode(returnData))
    }
} #end /get
Using Lua to Fetch Multiple Information from a Redis Set

Bulk Delete Operation

In any decent game, there are several leaderboards, and the players are a part of a bunch of them. When a player is no longer available, it's a good idea to remove them from the leaderboard. Using pipelines, removing a player from multiple leaderboards (sets) could have been done simply on the application server. Still, since I was already into Lua, I decided to implement the bulk delete operation in Lua itself.

...

# delete player from leaderboards
# params: leaderboards, player_id

location /del {
    default_type 'text/plain';
    set_unescape_uri $name $arg_name;
    set_unescape_uri $sets $arg_sets;
    
    content_by_lua_block{
        -- plugins
        local json = require('cjson')
        local redis = require('resty.redis')

        -- redis connection
        local red = redis:new()
        local ok, err = red:connect("127.0.0.1", 6379)

        -- get all keys, then remove user from those sets
        local keys = json.decode(ngx.var.leaderboards)
        local keys, err = red:keys("*")
        if keys then
        	red:init_pipeline()
        	for i = 1, #keys
        	do
        		red:zrem(keys[i], ngx.var.player_id)
        	end
        	red:commit_pipeline()
        end
    }
} #end /del
...
Using Redis Pipeline for Bulk ZREM Operation

The above examples do not include code that validates the incoming requests, sanitizes the data, and post-processing before sending a response.

In a nutshell, you can write Lua code on top of Redis using OpenResty. This way, you can make a Redis server programmable. Then you can perform all bulk operations using the Lua code on the same server as your Redis database, instead of the application server running thousands of miles away.