Starkiller
finding a path through the programming world
Posted on 02 May 2013

Redis is a wonderful in-memory data structure database, developed by Salvatore Sanfilippo. Enough has been written about the strengths, weaknesses, and use-cases of Redis; I'm going to focus on the extensibility of Redis to perform custom tasks. To start on a relatively simple note, I'll outline the steps required to add a custom command directly to the Redis codebase.

A strength of Redis from a programmer's perspective is the simplicity of the codebase. One of Sal's goals with the project is to minimize external dependencies, and thus Redis performs minimal linking with shared libraries. The simplicity and organization of the Redis codebase makes minor (and sometimes major) modifications fairly intuitive.

For this exercise, I am working off of the 2.6.13 codeline. A working example of the code in this exercise can be found on GitHub.

The Function

I'll be implementing the ZAVERAGESCORE method for this exercise. The command will accept one parameter, the key for the sorted set. The method will return the average of the scores for all members of the sorted set stored at key.

The method isn't all that difficult overall, and not entirely useful, but should act as a good starting point for our foray into extending Redis.

Why not use Lua?

Well that wouldn't be much fun, would it?

The 2.6 release of Redis came with built-in Lua scripting support. This support has satisfied the vast majority of custom operations and should most definitely be the first solution explored when a custom operation is needed.

However, some complex operations can definitely benefit from a straight C implementation. To implement our example method, a Lua script would have to call a ZRANGE key 0 -1 WITHSCORES command to retrieve all of the members with their scores, requiring a potentially large result set to be created, and only then could the results be iterated upon to calculate the average score. In our exercise, we can simply traverse the sorted set and iteratively calculate the average score as we go, utilizing a constant memory space.

Modify the Command Table

Redis uses a command table to directly map an external command to an internal function. The entire command table is defined as a single struct at line 115 of src/redis.c. As a peripheral function, the command table includes fields for statistics that are updated at runtime.

We can define our custom operation by adding the following to the bottom of the command table:

src/redis.c
{"zaveragescore",zaveragescoreCommand,2,"r",0,NULL,1,1,1,0,0}

The members of the struct are as follows:

  • name: The string name of the function. This is the command used by external clients to invoke the method.
  • function: Pointer to the function that implements the method. We'll declare/define this shortly.
  • arity: The number of arguments to the method, including the method's name.
  • sflags: Command flags. See the entire list of available flags.
  • flags: Bitmask flags. Redis computes these after startup; must be 0.
  • get_keys_proc: Optional function for processing arguments. Generally NULL.
  • first_key_index: Index of the first argument that is a key. Normally 1.
  • last_key_index: Index of the last argument that is a key. Normally 1.
  • key_step: Step interval for obtaining keys from the first to the last key. Normally 1.
  • microseconds: Total microseconds this command has spent executing since last Redis start.
  • calls: Total number of times this command has been called since last Redis start.

For the majority of cases, you will only need to worry about the name, function, and arity fields, while paying attention to the sflags fields for when you are writing commands that write to Redis.

View source of the modified file in this step.

Declare the Function

The Redis codebase declares the functions that implement the external commands starting at line 1063 of src/redis.h. We can declare our custom zaveragescoreCommand function that we previously used in the command table by adding the following at the end of the command prototype declarations:

src/redis.h
void zaveragescoreCommand(redisClient *c);

All functions that implement an external command follow the common signature of returning void and accepting a redisClient pointer.

View source of the modified file in this step.

Define the Function

Now that we have the initial declarations out of the way, all we have left to do is implement the method! We will be adding our method to the bottom of the src/t_zset.c file, which defines all of the internal and external functions used for sorted sets.

We'll start off by declaring some variables used locally in the function and finding the sorted set at the desired key.

src/t_zset.c
void zaveragescoreCommand(redisClient *c) {
    robj *key = c->argv[1];
    robj *zobj;
    double average;
    int count;

    /* Fetch the object */
    if ((zobj = lookupKeyReadOrReply(c,key,shared.nullbulk)) == NULL ||
        checkType(c,zobj,REDIS_ZSET)) return;

    average = 0;
We extract the key for the sorted set from c->argv[1], as the key is the second parameter to the method (the first being the method name itself). We then lookup the key and ensure the retrieved object is a sorted set with lookupKeyReadOrReply and checkType, respectively. If either of these calls fail, nil is returned to the client. Now that we have the sorted set, we should be able to just iterate over the elements to calculate the average score, correct? Well, yes and no. Sorted sets are actually internally represented in Redis by two different data structures, depending on the size of the sorted set: [ziplists](https://github.com/antirez/redis/blob/unstable/src/ziplist.c), a Redis-specific data structure for storing small sorted sets, and [skip lists](http://en.wikipedia.org/wiki/Skip_list) for larger sorted sets. Since we have two possible encodings, we need to handle iterating over both. We check for the encoding using the following control:
src/t_zset.c
if (zobj->encoding == REDIS_ENCODING_ZIPLIST) {
    /* Ziplist score averaging code */
} else if (zobj->encoding == REDIS_ENCODING_SKIPLIST) {
    /* Skip list score averaging code */
} else {
    redisPanic("Unknown sorted set encoding");
}
This ensures the sorted set is at least encoded either as a ziplist or a skip list, else something went Terribly Wrong. Now all we need to do is fill in the averaging code. For Ziplists...
src/t_zset.c
unsigned char *zl = zobj->ptr;
unsigned char *eptr, *sptr;

eptr = ziplistIndex(zl,0);
redisAssertWithInfo(c,zobj,eptr != NULL);
sptr = ziplistNext(zl,eptr);
redisAssertWithInfo(c,zobj,sptr != NULL);

if (eptr != NULL) {
    average = zzlGetScore(sptr);
    zzlNext(zl,&eptr,&sptr);
    count = 2;
    while(eptr != NULL) {
        average = ((average/count)*(count-1)) + (zzlGetScore(sptr)/count);
        count++;
        zzlNext(zl,&eptr,&sptr);
    }
}
And for skip lists...
src/t_zset.c
zset *zs = zobj->ptr;
zskiplist *zsl = zs->zsl;
zskiplistNode *ln;

ln = zsl->header->level[0].forward;
if (ln != NULL) {
    average = ln->score;
    ln = ln->level[0].forward;
    count = 2;
    while(ln != NULL) {
        average = ((average/count)*(count-1)) + (ln->score/count);
        count++;
        ln = ln->level[0].forward;
    }
}
Each of these blocks iterates over the sorted set and calculates the average as it goes. If the sorted set is empty, the average is simply returned as 0. The return the average to the client, we finish our method with the following:
src/t_zset.c
addReplyDouble(c,average);
And that's it! The full source of the modified t_zset.c can be found here.

Making Sure it Works

Compile and start up your Redis modification using the following in your Redis source root:
> make
> src/redis-server

In another console window, start up a redis-cli instance and test it out!

> redis-cli
redis 127.0.0.1:6379> zaveragescore test
(nil)
redis 127.0.0.1:6379> zadd test 1 test1
(integer) 1
redis 127.0.0.1:6379> zadd test 2 test2
(integer) 1
redis 127.0.0.1:6379> zadd test 3 test3
(integer) 1
redis 127.0.0.1:6379> zaveragescore taco
"2"
redis 127.0.0.1:6379> zadd test 1 1
(integer) 1
redis 127.0.0.1:6379> zadd test 1 2
(integer) 1
redis 127.0.0.1:6379> zaveragescore test
"1.6000000000000001"

Sigh... floating points.

Moving Forward

The intent of this exercise was to lay the foundation for more extensive future Redis modifications, such as adding custom datatypes or different persistence strategies, which are definitely more complex. However, the majority of the Redis code base is relatively simple to understand, and easy to get started with without much environment overhead.

See More in the Hacking Redis Series