Today i spoted on twitter this:

@antirez: “The Redis community is composed of 99% of people that, really, know their stuff, know the Redis internals and behaviour, and are * great *.”

@shanley: “@antirez I’ve never met a technical community where 99% of them were familiar with the internals of anything. Did you mean 9%?”

This sparked in my mind very quick review of the topics that we talk about in work and i realised that we talk about a lot about internals of redis and a bit about riak but this is different story :).

Spike

I just wanted to write a short post about first thing i ever picked when i was looking into internals of Redis. It is List :D i love lists.

So what i did was opening again github and picking up list header file to re-read.

https://github.com/antirez/redis/blob/d310fbedabd3101505b694f5c25a2e48480a3c2b/src/adlist.h

First thing that you notice is that code is simple and whole thing is implemented in 93 lines of header and 341 lines .c file. (with license etc lol).

Structure of List

In general List is just degenerated Tree. In Redis structure of it is simple. Whole description of the list is simply

1
2
3
4
5
6
7
8
9
10
11
12
13
14

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

this knowledge lets us count how much space this will take on the heap and compare it with eg. set if we really need to. (list is imho most memory effective structure)

List iterator is important so its also worth having a peek at even if this is just internal implementation.

1
2
3
4

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

with this we can take a peek into .c file and check how you get iterator.

1
2
3
4
5
6
7
8
9
10
11

listIter *listGetIterator(list *list, int direction){
    listIter *iter;

    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

And see that even if AL_START_HEAD is defined as 0 and AL_START_TAIL as 1 if we will use direction of 5 (lol) we will get tail :D I know that i’m bikesheding now.

Even without going any deeper you have a feeling how this works. Double linked list with (void) value. First thing i thought today was (this was stupid) “Wow why this is (void ) and not (char ) this would let compiler better type check it while compilation” but antirez wrote to me “@jakuboboza hint: grep listCreate .c” and that was the hint i needed. (void *) is more generic but list is used in many places in redis internals and i did not thought about it (lol)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

λ grep listCreate *.c
adlist.c:list *listCreate(void)
adlist.c:    if ((copy = listCreate()) == NULL)
aof.c:    server.aof_rewrite_buf_blocks = listCreate();
aof.c:    c->reply = listCreate();
aof.c:    c->watched_keys = listCreate();
bio.c:        bio_jobs[j] = listCreate();
multi.c:        clients = listCreate();
networking.c:    c->reply = listCreate();
networking.c:    c->io_keys = listCreate();
networking.c:    c->watched_keys = listCreate();
networking.c:    c->pubsub_patterns = listCreate();
object.c:    list *l = listCreate();
pubsub.c:            clients = listCreate();
redis-benchmark.c:    config.clients = listCreate();
redis.c:    server.clients = listCreate();
redis.c:    server.clients_to_close = listCreate();
redis.c:    server.slaves = listCreate();
redis.c:    server.monitors = listCreate();
redis.c:    server.unblocked_clients = listCreate();
redis.c:    server.ready_keys = listCreate();
redis.c:    server.pubsub_patterns = listCreate();
sentinel.c:    sentinel.scripts_queue = listCreate();
slowlog.c:    server.slowlog = listCreate();
sort.c:    operations = listCreate();
t_list.c:        list *l = listCreate();
t_list.c:            l = listCreate();
t_list.c:        server.ready_keys = listCreate();
ziplist.c:            ref = listCreate();

A lot of places :) lol.

In adlist.c we can also check how the list is created

1
2
3
4
5
6
7
8
9
10
11
12
13

list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

This is just academic example :D I love it. This code is easy to understand and just pleasure to read.

why to even bother talking about internals ?

It is important to talk about them because if you read in documentation that

1
2
3

lpush is O(1)
rpush is O(1)
lpop is O(1)

you really want to check this out to get better understanding how stuff works under the hood. Even if this is trivial example.

It is worth talking about internals of tools that you use, you learn a lot and i think its truth what antirez said, this community is great!

Next

Thing to view is suggested by antires Dict!

antirez: “@jakuboboza it’s definitely a very simple implementation! Probably our most “on steroids” implementation of data structures is dict.c”

^_____^