Redis Source Code

11/6/2019 - 2:29 AM

Rendered
Source

`sds.h` 和 `sds.c`	Redis 的动态字符串实现。
`adlist.h` 和 `adlist.c`	Redis 的双端链表实现。
`dict.h` 和 `dict.c`	Redis 的字典实现。
`redis.h` 中的 `zskiplist` 结构和 `zskiplistNode` 结构，以及 `t_zset.c` 中所有以 `zsl` 开头的函数，比如 `zslCreate` 、 `zslInsert` 、 `zslDeleteNode` ，等等。	Redis 的跳跃表实现。
`hyperloglog.c` 中的 `hllhdr` 结构，以及所有以 `hll` 开头的函数。	Redis 的 HyperLogLog 实现


`intset.h` 和 `intset.c`	整数集合（intset）数据结构。
`ziplist.h` 和 `ziplist.c`	压缩列表（zip list）数据结构。

`object.c`	Redis 的对象（类型）系统实现。
`t_string.c`	字符串键的实现。
`t_list.c`	列表键的实现。
`t_hash.c`	散列键的实现。
`t_set.c`	集合键的实现。
`t_zset.c` 中除 `zsl` 开头的函数之外的所有函数。	有序集合键的实现。
`hyperloglog.c` 中所有以 `pf` 开头的函数。	HyperLogLog 键的实现

`redis.h` 文件中的 `redisDb` 结构，以及 `db.c` 文件。	Redis 的数据库实现。
`notify.c`	Redis 的数据库通知功能实现代码。
`rdb.h` 和 `rdb.c`	Redis 的 RDB 持久化实现代码。
`aof.c`	Redis 的 AOF 持久化实现代码。

`redis.h` 文件的 `pubsubPattern` 结构，以及 `pubsub.c` 文件。	发布与订阅功能的实现。
`redis.h` 文件的 `multiState` 结构以及 `multiCmd` 结构， `multi.c` 文件。	事务功能的实现。
`sort.c`	`SORT` 命令的实现。
`bitops.c`	`GETBIT` 、 `SETBIT` 等二进制位操作命令的实现。

`ae.c` ，以及任意一个 `ae_*.c` 文件（取决于你所使用的多路复用库）。	Redis 的事件处理器实现（基于 Reactor 模式）。
`networking.c`	Redis 的网络连接库，负责发送命令回复和接受命令请求，同时也负责创建/销毁客户端，以及通信协议分析等工作。
`redis.h` 和 `redis.c` 中和单机 Redis 服务器有关的部分。	单机 Redis 服务器的实现

文件	内容
`scripting.c`	Lua 脚本功能的实现。
`slowlog.c`	慢查询功能的实现。
`monitor.c`	监视器功能的实现

文件	内容
`replication.c`	复制功能的实现代码。
`sentinel.c`	Redis Sentinel 的实现代码。
`cluster.c`	Redis 集群的实现代码。

sds.md

Rendered
Source

title : Simple Dynamic String tags : redis date : 2019-11-5

Sds(Simple Dynamic String) 是redis底层所使用的字符串

1.1 用途

实现字符串对象
替代 char* 类型

1.2 结构

sds如下所示，只是普通的char指针

typedef char *sds

而redis 使用[sds header(sdshdr) + char *]的形式来存放一个字符串

sdshdr存放的是字符串的相关信息, 一共有5种不同的类型

LSB : 最低有效位

MSB : 最高有效位

typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb 表示类型, 5 msb 表示长度 0-31 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

之所以有5种，是为了能让不同长度的字符串可以使用不同大小的header。这样，短字符串就能使用较小的header，从而节省内存, 这点我们可以从每一种header中的 len 的类型可以看出

在每一个 sdshdr[n] 中，最后一个成员是一个柔性数组(flexible array)buf，该数组相当于一个标志，并不占用该结构体的空间，在某些编译器下，柔性数组的使用方式是声明一个长度为0的数组 a[0]

在sdshdr的声明中，有个编译选项 __attribute__ ((__packed__)) 在加入该选项之后，结构体就不会进行对齐，而是紧凑压缩，结构体的大小等于内部成员的大小之和

1.3 相关的宏

#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

SDS_HDR_VAR(T,s) : 声明一个sdshdr的结构体指针sh，指向s所在的sdshdr
SDS_HDR(T,s): 获得s所在的sdshdr，不声明变量
SDS_TYPE_5_LEN(f) : 获得sdshdr5的长度，sdshdr5的长度在flags里面，flags有8位，前3位作为类型，后5位作为长度，详情见sdshdr 的注释

1.4 相关操作

1.4.1 获取sds的长度

由于flag的前三位是sds的长度, 因此，首先要获得sdshdr的flags，s[-1]获得的正是flags，随后将flags与SDSTYPEMASK进行按位与操作，获得flags的前三位，得到该sdshdr的类型

之所以进行按位与操作，是因为sdshdr5的特殊性

之后，根据不同的sdstype使用SDS_HDR来进行相应的sdshdr获取(主要是不同的type，len和alloc的类型不同，因此需要进行不同距离的指针偏移)

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

1.4.2 获得sds的容量

由于预分配策略，除了sdstype5外的其他sds的容量并不等于当前长度，alloc > len，因此要使用sdsalloc获取sds的实际容量，操作与sdslen差不多

static inline size_t sdsalloc(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}

1.4.3 其他类似的函数

static inline size_t sdsavail(const sds s) //获取剩余长度，用alloc - len
static inline void sdssetlen(sds s, size_t newlen) //重新设置长度
static inline void sdsinclen(sds s, size_t inc) //增加长度
static inline void sdssetalloc(sds s, size_t newlen) //重新设置容量

Q:重新设置长度/容量为什么不需要重新分配空间？
A:因为这些函数的功能只是修改某个属性，真正对内存空间进行修改的是调用它们的函数

1.4.4 核心操作

使用现有字符串创建新的字符串，其步骤可以概括为

根据长度获取相应的sds hdr
进行内存分配，初始化sds hdr结构体
拷贝数据

该函数的使用方式为 mystring = sdsnewlen("abc", 3);

该函数使用 sdsReqType 获取现有字符串 init 的 sdstype , 该函数利用字符串的长度进行类型的选择

然后利用 sdsHdrSize 获取相应 sds hdr的长度(也就是 sizeof(sds hdr type))

接着调用 s_malloc(zmalloc) 为整个 sds(sds hdr + char *) 分配内存

在 zmalloc 中，先调用 malloc 进行内存的分配，如果分配失败则中断程序，如果分配成功则精确地更新 used_memory 变量维护实际分配的内存大小

为什么要说精确的呢？因为 malloc会在分配内存的时候进行内存对齐，因此我们可能分配到的内存会比我们想要的内存大那么一些，因此需要对多出来的部分进行一个计算然后才能更细全局的已分配内存大小

void *zmalloc(size_t size) {
    void *ptr = malloc(size+PREFIX_SIZE); //尝试分配内存

    if (!ptr) zmalloc_oom_handler(size); //oom(out of memory) 错误, 打印错误，程序终止

    /*
    #define update_zmalloc_stat_alloc(__n) do { \
    size_t _n = (__n); \
    if (_n&(sizeof(long)-1)) _n += sizeof(long)-(_n&(sizeof(long)-1)); \
    atomicIncr(used_memory,__n); \
    } while(0)
    */

    //下面更新used_memory变量
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_alloc(zmalloc_size(ptr)); 
        return ptr;
#else
    *((size_t*)ptr) = size;
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    return (char*)ptr+PREFIX_SIZE;
#endif
}

接下来检查 sds，如果 sds 不是空指针而且不等于 SDS_NOINIT ，那么就将所分配的空间进行清零

然后根据init 的 sds hdr 类型填充所分配的空间的 sds hdr 部分，最后拷贝 init 所指向的字符串

/* Create a new sds string with the content specified by the 'init' pointer
 * and 'initlen'.
 * If NULL is used for 'init' the string is initialized with zero bytes.
 * If SDS_NOINIT is used, the buffer is left uninitialized;
 *
 * The string is always null-termined (all the sds strings are, always) so
 * even if you create an sds string with:
 *
 * mystring = sdsnewlen("abc",3);
 *
 * You can print the string with printf() as there is an implicit \0 at the
 * end of the string. However the string is binary safe and can contain
 * \0 characters in the middle, as the length is stored in the sds header. */
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1); //实际调用的是zmalloc

    //检查init
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;

    //获取sds hdr位置
    s = (char*)sh+hdrlen;

    //获取flags的地址，为sds type 5的flags填充作准备
    fp = ((unsigned char*)s)-1;

    //往sdshdr中写入字符串的相关信息
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    //复制字符串
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

扩容

扩容的话其实需要注意的就是 sdshdr 类型在扩容之后的改变

如果 sdshdr 没有改变，那么就使用 realloc 直接修改内存大小

如果改变了，那么就重新设置新的 sdshdr

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* Return ASAP if there is enough space left. */
    //剩余空间足够，不扩容
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    //进行预分配
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */

     // 因为type5不支持剩余长度，因此使用type8
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

回收 sds 中的未使用空间

既然是回收空间，那么修改的地方就是 sdshdr

/* Reallocate the sds string so that it has no free space at the end. The
 * contained string remains not altered, but next concatenation operations
 * will require a reallocation.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
    size_t len = sdslen(s);
    //获得剩余的长度
    size_t avail = sdsavail(s);
    //获得sdshdr的位置
    sh = (char*)s-oldhdrlen;

    /* Return ASAP if there is no space left. */
    if (avail == 0) return s;

    /* Check what would be the minimum SDS header that is just good enough to
     * fit this string. */
    //以字符串的真实长度为参数，获取该长度所对应的sdshdr
    type = sdsReqType(len);
    hdrlen = sdsHdrSize(type);

    /* If the type is the same, or at least a large enough type is still
     * required, we just realloc(), letting the allocator to do the copy
     * only if really needed. Otherwise if the change is huge, we manually
     * reallocate the string to use the different header type. */
     //由于原先的长度>=新的长度，那么原先的hdr也是完全够用的
     //那么就检查新的sdshdr类型是否太小，比如比SDS_TYPE8还小，如果太小那么就没有必要使用那么大的sdshdr，而是重新分配
    if (oldtype==type || type > SDS_TYPE_8) {
        newsh = s_realloc(sh, oldhdrlen+len+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+oldhdrlen;
    } else {
        newsh = s_malloc(hdrlen+len+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    //单纯地只是设置容量大小
    sdssetalloc(s, len);
    return s;
}

思考

整个sds hdr结构以及对应的操作，都是围绕严格控制数据大小这个主题展开的

其表现为

压缩结构体，禁止字节对齐
使用不同长度的int类型来存放长度
当数据的大小改变之后，对其使用的sds hdr结构进行降级

从此可以看出，在对数据大小进行优化时，类型长度是非常重要的，切勿随意地使用

Cacher is the code snippet organizer for pro developers

We empower you and your team to get more done, faster