本文为一次组内技术分享的文档，关注如下内容：

• 字符串对象的编码与转换
• 各种对象在编码上的实现
• Redis 命令解析执行的部分过程
• 优化内存使用&内存回收

对象的类型与编码

Redis 中，键值对的键和值都分别保存为一个对象。对象的数据结构如下所示：

typedef struct redisObject {
    // 类型，半字节
    unsigned type:4;
     
    // 编码，半字节
    unsigned encoding:4;
     
    // 指向底层实现数据结构的指针
    void *ptr;
     
    // 3 字节，（使用 LFU 算法时：低 8 位表示频率，高 16 位表示时间；LRU 算法时：全部表示 LRU 时钟）
    unsigned lru:LRU_BITS;
 
    // 4字节，引用计数
    int refcount;
 
    // 8字节（64位）
    void *ptr;
}

类型

对象的类型有如下几种

通过 TYPE key 指令看到的输出为值对象的类型，而不是键对象的类型

对象编码

编码可以通过 OBJECT ENCODING 指令查看

字符串对象

可以表示为数字时

• 如果未启用最大内存配置，且满足可以使用的共享对象的数据范围 [0, 10000) 时，返回共享对象的指针，并更新引用计数。共享对象只在这种情况下会尝试使用。
• 不能使用共享内存时，进行编码转换

object.c 代码节选

len = sdslen(s);
if (len <= 20 && string2l(s,len,&value)) {
    // 启用了最大内存（maxmemory）配置时，会避免使用共享对象的方式
    // 因为这样不是每个对象都有独立的空间，不利于 LRU 回收
    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 {
        // 不能使用共享对象时，修改 RAW 编码为 INT
        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) {
            decrRefCount(o);
            return createStringObjectFromLongLongForValue(value);
        }
    }
}

shs.h 代码节选

struct __attribute__ ((__packed__)) sdshdr8 { // __attribute__ ((__packed__)) 禁用编译器对齐，按实际大小存储
    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[]; // flexible array member，柔性数组成员，不占用空间，由 struct 的 size 决定其地址
};

简单动态字符串的情况

• 字符串长度小于 44（39，32）时，redisObject 一个对象最大 64byte 的空间内，存储对象和简单动态字符串对象，此时采用 embstr 编码，此时的内存申请和释放仅需要进行一次，而且空间上连续。
• 如果长度大于 44，则编码为 raw

object.c 代码节选

// 字符串（SDS）长度小于 44 时，使用 embstr 编码
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;
}
 
// 使用 raw 时，把为 SDS 申请空间时多申请的部分释放掉
trimStringObjectIfNeeded(o);

字符串操作 & 编码转换

OBJECT ENCODING 指令可以得到对象的编码，有如下指令：

SET k1 3
OBJECT ENCODING k1 （→ int）
 
APPEND k1 "2"
GET k1 （→ 32）
OBJECT ENCODING k1 （返回值为raw）
 
 
SET k2 3s
OBJECT ENCODING k2 （→ embstr）
 
APPEND k2 "s"
GET k2 （→ 3s）
OBJECT ENCODING k2 （返回值为raw）

现象解释

A string object with encoding OBJ_ENCODING_EMBSTR, that is an object where the sds string is actually an unmodifiable string allocated in the same chunk as the object itself.

大意是说 embstr 编码将 redisObject 和 sds 存在同一内存块中。因此，如果对 embstr 进行修改，则涉及到两个对象在同一个内存块中的内存重分配，所以直接降级为 raw。

sds 的编码通常不会回退（int → embstr → raw）。但在数学运算时，也会有如下现象，与通常的编程常识相符：

127.0.0.1:6379> set k3 9223372036854775807
OK
127.0.0.1:6379> object encoding k3
"int"
127.0.0.1:6379> incr k3
(error) ERR increment or decrement would overflow（超出 long 范围的无法 incr）
 
127.0.0.1:6379> set k5 0.1
OK
127.0.0.1:6379> get k5
"0.1"
127.0.0.1:6379> incrbyfloat k5 0.2
"0.30000000000000004"    （在进行浮点运算时，同样遵循 IEEE 754 标准，不运算则不影响）
 
127.0.0.1:6379> set k6 1
OK
127.0.0.1:6379> append k6 2
(integer) 2
127.0.0.1:6379> object encoding k6
"raw"
127.0.0.1:6379> incr k6
(integer) 13
127.0.0.1:6379> object encoding k6
"int"  （不会因为 k6 变成 raw 了就没办法进行运算，在 incr 运算后，编码会回退为 int）

应用

• 尽量存储短字符串，无论是键还是值（长度在 44 以内）
• 能只用数字实现的情况，尽量避免拼字符串。但没必要进行过度的拆分，键也是对象，也要占用空间。
• 避免使用 redis 进行字符串运算（如拼接），这样可以减少内存重分配的开销

列表对象

编码与实现

在 Redis 3.2 之前，redis 默认采用 ziplist 实现，存的东西大了、多了都会转成 linkedlist。

之后，采用 quicklist 实现，quicklist 是一个 ziplist 和 linkedlist 的混合实现，综合了二者的优势

• 各节点间形成双端链表结构。
• 节点内部的多个 entry 采用与 ziplist 形式相同的存储方式，存储在一个连续空间内，减少了碎片导致的损耗。另外还采用了 LZF 进行再次压缩。

quicklist.h 代码节选

// quicklist 结构
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all listpacks */
    unsigned long len;          /* number of quicklistNodes */
    // ... 其他信息
} quicklist;
 
// quicklist 节点结构
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;
    size_t sz;             /* entry size in bytes (unsigned long long) */
    unsigned int count : 16;     /* count of items in listpack */
    // ... 其他信息
} quicklistNode;
 
// quicklist 节点上 ziplist 的结构
typedef struct quicklistLZF {
    size_t sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

QuickList 节点结构示意图

应用

• 不要使用版本过低的 redis
• 思想：连续空间、压缩-解压等方式来节省内存（需要牺牲一定算力）

哈希对象

底层采用 ziplist 或 dict 实现，优先采用 ziplist，元素太大太多会变为 dict，其阈值可配，相关参数为 hash-max-ziplist-value 和 hash-max-ziplist-entries。

采用 ziplist 和 hashtable 进行存储时，执行相关指令前者为 O(n) 复杂度，后者为 O(1)，内存中的结构分别如：

集合对象

底层采用 intset 或 dict 实现，条件满足时会优先采用 intset。元素过多或存储了非整数值时，会变成 hashtable，阈值可以通过 set-max-intset-entries 进行配置。

使用 intset 和 hashtable 进行存储时，执行相关指令前者为 O(n) 复杂度，后者为 O(1)，内存结构分别如下：

有序集合对象

元素较少时，底层采用 ziplist 实现（值和分值作为两个紧挨的元素进行存储），当元素过多时过大时，会转换为 skiplist + dict 实现，阈值可以通过 zset-max-ziplist-entries 和 zset-max-ziplist-value 设定。

否则采用 skiplist + dict 进行实现，以获得 skiplist 高效的范围操作性能，以及 dict 高效的查询性能。

采用 ziplist 编码时，通过遍历压缩列表实现相关指令；采用 zset 编码时，范围查询和统计相关指令（如 ZCARD, ZCOUNT）均使用 skiplist，查询（ZSCORE）使用 dict。

类型检查 & 命令多态

redis 对指令的类型检查基于 redisObject 中的 type 进行。

命令多态：redis 的 README 中关于该实现的描述：redis 内有一个全局变量 redisCommandTable（位于 commands.c 中），维护了全部指令的信息，包括指令名、指令的实现方法、指令所需参数及类型等信息。在解析后，这些指令信息会维护在一个 dict 结构中（server.c populateCommandTable 函数）。

解析执行命令时，首先从该 table 中找到要执行的目标指令对象，类型检查后执行目标方法。

redisCommandTable 代码截取：

该文件的代码为自动生成：

generate-command-code.py 代码节选

# 读取各指令的配置文件
for filename in glob.glob('%s/commands/*.json' % srcdir):
    with open(filename,"r") as f:
        d = json.load(f)
        for name, desc in d.items():
            create_command(name, desc) # 将指令写入 command_list
# ...
with open("%s/commands.c" % srcdir,"w") as f:
    # ...
    curr_group = None
    for command in command_list:
        # ... 通过代码写注释
        f.write("{%s},\n" % command.struct_code())
    f.write("{0}\n")
    f.write("};\n")

server.指令配置文件如下所示（以 hget 为例）：

{
    "HGET": {
        "summary": "Get the value of a hash field",
        "complexity": "O(1)",  // 复杂度
        "group": "hash",
        "since": "2.0.0",
        "arity": 3,
        "function": "hgetCommand",
        "command_flags": [
            "READONLY",
            "FAST"
        ],
        // ...
        "arguments": [ // 命令参数
            {
                "name": "key",
                "type": "key",
                "key_spec_index": 0
            },
            {
                "name": "field",
                "type": "string"
            }
        ]
    }
}

内存回收

我们可以在使用 redis 时配置 maxmemory-policy 指定已用内存达到最大时采用的置换算法。此外，redis 会采用引用计数的方式进行内存回收。

对象创建时：(object.c createObject 函数片段)

o->refcount = 1;
 
// LFU：最近最少使用
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
    o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;  // 低 8 位，初始值为5，高 16 位为时间（最小单位为分钟，65536 分钟一循环）
} else {  // LRU: 最近最久未使用
    o->lru = LRU_CLOCK();  // 记录当前 LRU 时钟
}

访问对象时：（db.c 代码片段）

// LFU 频次更新，执行衰减和增加操作（过程十分复杂）
/* Update LFU when an object is accessed.
 * Firstly, decrement the counter if the decrement time is reached.
 * Then logarithmically increment the counter, and update the access time. */
void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);  // 根据一定算法进行“减少”运算
    counter = LFULogIncr(counter);  // 进行“增加”运算
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;  // 还原为 24 位
}
// ...
        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                updateLFU(val);
            } else {
                // LRU 的实现，重置一下时钟
                val->lru = LRU_CLOCK();
            }
        }

可以通过 OBJECT IDLETIME key 指令获得对象的空转时长，即当前时间减去对象的 lru 属性得到的值。

参考文章

知乎 redis中embstr与raw编码方式之间的界限
简书 quick'list VS ziplist
知乎 Redis 为什么用跳表而不用平衡树
掘金 动态字符串（一些操作的源码解读）
思否 动态字符串源码分析（解释了柔性数组成员等特性）
cnblogs 动态字符串数据结构分析
cnblogs Redis数据结构：快速链表
博客 Redis内部数据结构详解(5)——quicklist
cnblogs Redis中的LFU算法
CSDN Redis底层详解 LRU算法
思否 Redis 命令处理声明周期