Learning From Redis #4 / Reference Counting

Reference counting is a programming technique to track the reference of an object/memory allocation. It’s used to automatically free memory that has no longer references across the runtime.

Redis uses the above technique to automatically manage the deallocation of it’s internal object which stores any kind of data.

As we can see below the redisObject structure defined, contains a member refcount which stores the reference count of the object.

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

redis/server.h at unstable · redis/redis

As Redis core processing layer is single threaded, the refcount variable gets incremented/decremented by 1 directly on each reference/dereference respectively without any lock and once the value reaches to 0, the object is freed from memory.

I’ve removed some of the code and added some comments for easier understanding.

void decrRefCount(robj *o) {
    if (o->refcount == 1) { // if previous value of refcount is 1, the object will have no more references and can be freed.
        ...
        zfree(o);
    } else {
        if (o->refcount <= 0) serverPanic("decrRefCount against refcount <= 0"); // this should never happen, there is a bug in the system hence exit.
        if (o->refcount != OBJ_SHARED_REFCOUNT) o->refcount--; // reduce the reference count, if it's no maintained as a global object (which lives throughout the life of the program).
    }
}

The actual code can be found here:

redis/object.c at unstable · redis/redis

The above implementation of reference counting in Redis is a very simple example. There is no scenario for nested object inside redisObject to have recursively increment/decrement the refcount.

Reference counting is very simple to implement however has some drawbacks.

1. Additional memory overhead Each object needs to have an additional integer variable which increases the memory footprint.
2. Cyclic Structures Reference counting doesn’t work with cyclic structure and will cause memory leak as it would leave disjointed memory object in the heap.

If you want to read/learn more, here are some other interesting observations from Redis.

Learnings from Redis # 3