关于redis:Redis核心原理与实践字符串实现原理

Redis 是一个键值对数据库（key-value DB），上面是一个简略的 Redis 的命令：

> SET msg "hello wolrd"

该命令将键“msg”、值“hello wolrd”这两个字符串保留到 Redis 数据库中。
本章剖析 Redis 如何在内存中保留这些字符串。

redisObject

Redis 中的数据对象 server.h/redisObject 是 Redis 对外部存储的数据定义的形象类型，在深入分析 Redis 数据类型前，咱们先理解 redisObject，它的定义如下：

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

• type：数据类型。
• encoding：编码格局，即存储数据应用的数据结构。同一个类型的数据，Redis 会依据数据量、占用内存等状况应用不同的编码，最大限度地节俭内存。
• refcount，援用计数，为了节俭内存，Redis 会在多处援用同一个 redisObject。
• ptr：指向理论的数据结构，如 sds，真正的数据存储在该数据结构中。
• lru：24 位，LRU 工夫戳或 LFU 计数。

redisObject 负责装载 Redis 中的所有键和值。redisObject.ptr 指向真正存储数据的数据结构，redisObject .refcount、redisObject.lru 等属性则用于治理数据（数据共享、数据过期等）。

提醒：type、encoding、lru 应用了 C 语言中的位段定义，这 3 个属性应用同一个 unsigned int 的不同 bit 位。这样能够最大限度地节俭内存。

Redis 定义了以下数据类型和编码，如表 1 - 1 所示。

本书第 1 局部会对表 1 - 1 中前五种数据类型进行剖析，最初两种数据类型会在第 5 局部进行剖析。如果读者当初对表 1 - 1 中内容感到纳闷，则能够先带着疑难持续浏览本书。

sds

咱们晓得，C 语言中将空字符结尾的字符数组作为字符串，而 Redis 对此做了扩大，定义了字符串类型 sds（Simple Dynamic String）。
Redis 键都是字符串类型，Redis 中最简略的值类型也是字符串类型，
字符串类型的 Redis 值可用于很多场景，如缓存 HTML 片段、记录用户登录信息等。

定义

提醒：本节代码如无非凡阐明，均在 sds.h/sds.c 中。
对于不同长度的字符串，Redis 定义了不同的 sds 构造体：

typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; 
    char buf[];};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 
    uint8_t alloc;
    unsigned char flags;
    char buf[];};
...

Redis 还定义了 sdshdr16、sdshdr32、sdshdr64 构造体。为了版面整洁，这里不展现 sdshdr16、sdshdr32、sdshdr64 构造体的代码，它们与 sdshdr8 构造体基本相同，只是 len、alloc 属性应用了 uint16_t、uint32、uint64_t 类型。Redis 定义不同 sdshdr 构造体是为了针对不同长度的字符串，应用适合的 len、alloc 属性类型，最大限度地节俭内存。

• len：已应用字节长度，即字符串长度。sdshdr5 可寄存的字符串长度小于 32（25），sdshdr8 可寄存的字符串长度小于 256（28），以此类推。因为该属性记录了字符串长度，所以 sds 能够在常数工夫内获取字符串长度。Redis 限度了字符串的最大长度不能超过 512MB。
• alloc：已申请字节长度，即 sds 总长度。alloc-len 为 sds 中的可用（闲暇）空间。
• flag：低 3 位代表 sdshdr 的类型，高 5 位只在 sdshdr5 中应用，示意字符串的长度，所以 sdshdr5 中没有 len 属性。另外，因为 Redis 对 sdshdr5 的定义是常量字符串，不反对扩容，所以不存在 alloc 属性。
• buf：字符串内容，sds 遵循 C 语言字符串的标准，保留一个空字符作为 buf 的结尾，并且不计入 len、alloc 属性。这样能够间接应用 C 语言 strcmp、strcpy 等函数间接操作 sds。

提醒：sdshdr 构造体中的 buf 数组并没有指定数组长度，它是 C99 标准定义的柔性数组—构造体中最初一个属性能够被定义为一个大小可变的数组（该属性前必须有其余属性）。应用 sizeof 函数计算蕴含柔性数组的构造体大小，返回后果不包含柔性数组占用的内存。
另外，__attribute__((__packed__))关键字能够勾销构造体内的字节对齐以节俭内存。

操作剖析

接下来看一下 sds 构建函数：

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    // [1]
    char type = sdsReqType(initlen);
    // [2]
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    // [3]
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1);
    ...
    // [4]
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    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;
        }
        ...
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    // [5]
    return s;
}

参数阐明：

• init、initlen：字符串内容、长度。

【1】依据字符串长度，判断对应的 sdshdr 类型。
【2】长度为 0 的字符串后续通常须要扩容，不应该应用 sdshdr5，所以这里转换为 sdshdr8。
【3】sdsHdrSize 函数负责查问 sdshdr 构造体的长度，s_malloc 函数负责申请内存空间，申请的内存空间长度为 hdrlen+initlen+1，其中 hdrlen 为 sdshdr 构造体长度（不蕴含 buf 属性），initlen 为字符串内容长度，最初一个字节用于寄存空字符“\0”。s_malloc 与 C 语言的 malloc 函数的作用雷同，负责调配指定大小的内存空间。
【4】给 sdshdr 属性赋值。
SDS_HDR_VAR 是一个宏，负责将 sh 指针转化为对应的 sdshdr 构造体指针。
【5】留神，sds 实际上就是 char* 的别名，这里返回的 s 指针指向 sdshdr.buf 属性，即字符串内容。Redis 通过该指针能够间接读 / 写字符串数据。

构建一个内容为“hello wolrd”的 sds，其构造如图 1 - 1 所示。

sds 的扩容机制是一个很重要的性能。

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

    if (avail >= addlen) return s;
    // [2]
    len = sdslen(s);
    
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // [3]
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    // [4]    
    type = sdsReqType(newlen);
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    // [5]
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {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);
    }
    // [6]
    sdssetalloc(s, newlen);
    return s;
}

参数阐明：
addlen：要求扩容后可用长度（alloc-len）大于该参数。
【1】获取以后可用空间长度。如果以后可用空间长度满足要求，则间接返回。
【2】sdslen 负责获取字符串长度，因为 sds.len 中记录了字符串长度，该操作复杂度为 O(1)。这里 len 变量为原 sds 字符串长度，newlen 变量为新 sds 长度。sh 指向原 sds 的 sdshdr 构造体。
【3】预调配比参数要求多的内存空间，防止每次扩容都要进行内存拷贝操作。新 sds 长度如果小于 SDS_MAX_PREALLOC（默认为 1024×1024，单位为字节），则新 sds 长度主动扩容为 2 倍。否则，新 sds 长度主动减少 SDS_MAX_PREALLOC。
【4】sdsReqType(newlen)负责计算新的 sdshdr 类型。留神，扩容后的类型不应用 sdshdr5，该类型不反对扩容操作。
【5】如果扩容后 sds 还是同一类型，则应用 s_realloc 函数申请内存。否则，因为 sds 构造曾经变动，必须挪动整个 sds，间接调配新的内存空间，并将原来的字符串内容复制到新的内存空间。s_realloc 与 C 语言 realloc 函数的作用雷同，负责为给定指针重新分配给定大小的内存空间。它会尝试在给定指针原地址空间上重新分配，如原地址空间无奈满足要求，则调配新内存空间并复制内容。
【6】更新 sdshdr.alloc 属性。

对下面“hello wolrd”的 sds 调用 sdsMakeRoomFor(sds,64)，则生成的 sds 如图 1 - 2 所示。

从图 1 - 2 中能够看到，应用 len 记录字符串长度后，字符串中能够寄存空字符。Redis 字符串反对二进制平安，能够将用户的输出存储为没有任何特定格局意义的原始数据流，因而 Redis 字符串能够存储任何数据，比方图片数据流或序列化对象。C 语言字符串将空字符作为字符串结尾的特定标记字符，它不是二进制平安的。
sds 罕用函数如表 1 - 2 所示。

编码

字符串类型一共有 3 种编码：

• OBJ_ENCODING_EMBSTR：长度小于或等于 OBJ_ENCODING_EMBSTR_SIZE_LIMIT（44 字节）的字符串。
  在该编码中，redisObject、sds 构造寄存在一块间断内存块中，如图 1 - 3 所示。
  

OBJ_ENCODING_EMBSTR 编码是 Redis 针对短字符串的优化，有如下长处：

(1)内存申请和开释都只须要调用一次内存操作函数。(2)redisObject、sdshdr 构造保留在一块间断的内存中，缩小了内存碎片。

• OBJ_ENCODING_RAW：长度大于 OBJ_ENCODING_EMBSTR_SIZE_LIMIT 的字符串，在该编码中，redisObject、sds 构造寄存在两个不间断的内存块中。
• OBJ_ENCODING_INT：将数值型字符串转换为整型，能够大幅升高数据占用的内存空间，如字符串“123456789012”须要占用 12 字节，在 Redis 中，会将它转化为 long long 类型，只占用 8 字节。

咱们向 Redis 发送一个申请后，Redis 会解析申请报文，并将命令、参数转化为 redisObjec。
object.c/createStringObject 函数负责实现该操作：

robj *createStringObject(const char *ptr, size_t len) {if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

能够看到，这里依据字符串长度，将 encoding 转化为 OBJ_ENCODING_RAW 或 OBJ_ENCODING_EMBSTR 的 redisObject。

将参数转换为 redisObject 后，Redis 再将 redisObject 存入数据库，例如：

> SET Introduction "Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker."

Redis 会将键“Introduction”、值“Redis…”转换为两个 redisObject，再将 redisObject 存入数据库，后果如图 1 - 4 所示。

Redis 中的键都是字符串类型，并应用 OBJ_ENCODING_RAW、OBJ_ENCODING_ EMBSTR 编码，而 Redis 还会尝试将字符串类型的值转换为 OBJ_ENCODING_INT 编码。object.c/tryObjectEncoding 函数实现该操作：

robj *tryObjectEncoding(robj *o) {
    long value;
    sds s = o->ptr;
    size_t len;
    ...
    // [1]
     if (o->refcount > 1) return o;

    len = sdslen(s);
    // [2]
    if (len <= 20 && string2l(s,len,&value)) {// [3]
        if ((server.maxmemory == 0 ||
            !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) &&
            value >= 0 &&
            value < OBJ_SHARED_INTEGERS)
        {decrRefCount(o);
            incrRefCount(shared.integers[value]);
            return shared.integers[value];
        } else {// [4]
            if (o->encoding == OBJ_ENCODING_RAW) {sdsfree(o->ptr);
                o->encoding = OBJ_ENCODING_INT;
                o->ptr = (void*) value;
                return o;
            } else if (o->encoding == OBJ_ENCODING_EMBSTR) {// [5]
                decrRefCount(o);
                return createStringObjectFromLongLongForValue(value);
            }
        }
    }

    // [6]
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
        robj *emb;

        if (o->encoding == OBJ_ENCODING_EMBSTR) return o;
        emb = createEmbeddedStringObject(s,sdslen(s));
        decrRefCount(o);
        return emb;
    }

    // [7]
    trimStringObjectIfNeeded(o);

    return o;
}

【1】该数据对象被多处援用，不能再进行编码操作，否则会影响其余中央的失常运行。
【2】如果字符串长度小于或等于 20，则调用 string2l 函数尝试将其转换为 long long 类型，如果胜利则返回 1。
在 C 语言中，long long 占用 8 字节，取值范畴是 -9223372036854775808～9223372036854775807，因而最多能保留长度为 19 的字符串转换后的数值，加上正数的符号位，一共 20 位。
上面是字符串能够转换为 OBJ_ENCODING_INT 编码的解决步骤。
【3】首先尝试应用 shared.integers 中的共享数据，防止反复创立雷同数据对象而节约内存。shared 是 Redis 启动时创立的共享数据集，寄存了 Redis 中罕用的共享数据。shared.integers 是一个整数数组，寄存了小数字 0～9999，共享于各个应用场景。
留神：如果配置了 server.maxmemory，并应用了不反对共享数据的淘汰算法（LRU、LFU），那么这里不能应用共享数据，因为这时每个数据中都必须存在一个 redisObjec.lru 属性，这些算法才能够失常工作。
【4】如果不能应用共享数据并且原编码格局为 OBJ_ENCODING_RAW，则将 redisObject.ptr 原来的 sds 类型替换为字符串转换后的数值。
【5】如果不能应用共享数据并且原编码格局为 OBJ_ENCODING_EMBSTR，因为 redisObject、sds 寄存在同一个内存块中，无奈间接替换 redisObject.ptr，所以调用 createString- ObjectFromLongLongForValue 函数创立一个新的 redisObject，编码为 OBJ_ENCODING_INT，redisObject.ptr 指向 long long 类型或 long 类型。
【6】到这里，阐明字符串不能转换为 OBJ_ENCODING_INT 编码，尝试将其转换为 OBJ_ENCODING_EMBSTR 编码。
【7】到这里，阐明字符串只能应用 OBJ_ENCODING_RAW 编码，尝试开释 sds 中残余的可用空间。
字符串类型的实现代码在 t_string.c 中，读者能够查看源码理解更多实现细节。

提醒：server.c/redisCommandTable 定义了每个 Redis 命令与对应的处理函数，读者能够从这里查找感兴趣的命令的处理函数。

struct redisCommand redisCommandTable[] = {
    ...
    {"get",getCommand,2,
     "read-only fast @string",
     0,NULL,1,1,1,0,0,0},

    {"set",setCommand,-3,
     "write use-memory @string",
     0,NULL,1,1,1,0,0,0},
     ...
}

GET 命令的处理函数为 getCommand，SET 命令的处理函数为 setCommand，以此类推。

另外，咱们能够通过 TYPE 命令查看数据对象类型，通过 OBJECT ENCODING 命令查看编码：

> SET msg "hello world"
OK
> TYPE msg
string
> OBJECT ENCODING  msg
"embstr"
> SET Introduction "Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker."
OK
> TYPE Introduction
string
> OBJECT ENCODING  info
"raw"
> SET page 1
OK
> TYPE page
string
> OBJECT ENCODING  page
"int"

总结：

• Redis 中的所有键和值都是 redisObject 变量。
• sds 是 Redis 定义的字符串类型，反对二进制平安、扩容。
• sds 能够在常数工夫内获取字符串长度，并应用预分配内存机制缩小内存拷贝次数。
• Redis 对数据编码的次要目标是最大限度地节俭内存。字符串类型能够应用 OBJ_ENCODING_ RAW、OBJ_ENCODING_EMBSTR、OBJ_ENCODING_INT 编码格局。

本文内容摘自作者新书 《Redis 外围原理与实际》，这本书深刻地剖析了 Redis 罕用个性的外部机制与实现形式，大部分内容源自对 Redis 源码的剖析，并从中总结出设计思路、实现原理。通过浏览本书，读者能够疾速、轻松地理解 Redis 的外部运行机制。
通过该书编辑批准，我会持续在集体技术公众号（binecy）公布书中局部章节内容，作为书的预览内容，欢送大家查阅，谢谢。

京东链接
豆瓣链接