redis的5种数据类型以及其底层实现

redis 是KV(key-value pair)存储，不管是K还是V，底层都是对象（object 组成）的，其中K是一个字符串对象(string object)，V 分别有我们常听说的5种数据类型，分别是字符串(String)、列表(List)、哈希(Hash)、集合(Set)、有序集合(Zset)。不过是K还是V，底层都是用 redisObject 数据结构表示，如下：

struct redisObject {
    unsigned type:4;//4 bit
    unsigned encoding:4;//4 bit
    //24 bit=3byte
    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;//4byte
    void *ptr;//8type
};

其中 type 表示对象的类型，分别有 REDIS_STRING(字符串)，REDIS_LIST(列表)，REDIS_HASH(哈希)，REDIS_SET(集合对象)，REDIS_ZSET(有序集合)；

encoding 字段表示底层的编码实现，因为每种数据类型其实底层实现数据结构至少有2种，根据不同的条件选择不同的数据结构，而且会根据条件的变化升级或者更换数据结构，最终的目的是尽可能压缩存储和提升效率。具体每个数据类型的编码以及数据结构下面会详解。

ptr: 指向的是底层实现的数据结构

5种数据类型对应的底层编码结构如下图：

<center>图1</center>

字符串(String)

如上图1所示，数据类型为String的底层编码有3种：INT，EMBSTR，RAW。

• 当 value的值是整数时，采用INT编码。

• 当 value 非整数时，小于等于44字节时，采用 EMBSTR 编码，大于44字节时采用RAW编码，如下：

  localhost:6379> set test "01234567890123456789012345678901234567890123"
  OK
  localhost:6379> OBJECT ENCODING test
  "embstr"
  localhost:6379> set test "012345678901234567890123456789012345678901234"
  OK
  localhost:6379> OBJECT ENCODING test
  "raw"
  

• EMBSTR 编码 VS RAW编码

• EMBSTR 编码 和 RAW 编码底层实现都是 redisObject 结构 + SDS 结构

• 小于等于44字节用 EMBSTR编码，对比RAW有什么优势：

  1. 其实EMBSTR和RAW编码都是 redisObject 结构 + SDS 结构，只是 embstr 编码只需要1次内存分配（redisObject和SDS结构是连续的内存），而 RAW 编码需要分别为redisObject和 SDS 进行分配，内存一般不连续，对比EMBSTR，RAW多一次内存分配
  2. 内存释放时，EMBSTR 比 RAW 少一次调用内存释放函数
  3. EMBSTR 编码分配的内存的连续的，可以更好利用CPU缓存提升性能。

• 为啥是44字节

  答：因为内存分配函数最大1次分配是64字节，除开redisObject 占用16字节、SDS 结构3个字节、字符串结尾字符\0的1个字节，剩余最大：64-16-3-1=44字节。

SDS

SDS：simple dynamic string，redis 采用这个数据结构来代替 C 字符串（使用N+1的字符数组表示长度为N的字符串，最后一个字符是空字符'\0') ，SDS的结构图如下：

sds

<center>图2</center>

len: 字符串长度。可通过 O(1) 复杂度获取字符串长度，不像C 字符串需要遍历所有原素、时间复杂度 O(N) 来获取

alloc: 分配给字符串的空间。用于扩容判断，当 alloc - len 的空间不满足新字符串空间要求，进行扩容，扩容策略如上图。

flags: SDS的类型，redis 3.2版本后，定义了 5 种不同的类型结构，为了根据最小适用原则选择更节省内存的结构,如下:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    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[];
};

buf[]: 字符数组，用于存储实际数据。对比 C字符串，该数组可以存储任意字符，不像 C 字符串限制不能存储 '\0' 字符。

总结 redis 在很多场景使用 SDS 代替 C 字符串来表示字符串的原因：

1. SDS 获取字符串长度是O(1)，C字符串是 O(N)，性能更高
2. SDS API 更加安全。C 字符串在字符串拼接时，需依赖程序员确保空间足够，如果空间不足又忘记分配，就会出现缓冲区溢出，而 SDS 通过将确保空间足够封装到API里面（由 redis内部判断是否需要扩容），不需程序员管理，更加安全。
3. 在修改字符串时， SDS 的内存重分配次数少于 C 字符串。因为SDS使用空间预分配（分配多余的空间）和惰性空间释放（字符长度缩短时，并不释放无用字符占用的空间，后续使用直接替代即可）来减少内存重新分配，提升效率，有点空间换时间意思。
4. 存储的数据类型更广。C 字符串只适合存储文本数据，不能存储图片、音视频等二进制数据，而 SDS 可以。

列表(List)

Redis 3.2版本之前，List 的编码有2种：分别是 ZIPLIST（压缩列表） 和 LINKEDLIST(双向链表)。当 LIST 中每个字符串长度都小于64字节并且列表的元素个数小于512个时，采用 ZIPLIST 编码，否则采用 LINKEDLIST 编码。

大于等于3.2 版本后，结合 ZIPLIST 和 LINKELIST的优缺点，诞生了 快速列表（QUICKLIST），其实就是 ZIPLIST + LINKEDLIST 结合体。

ZIPLIST（压缩列表）

ZIPLIST(压缩列表)的结构图如下：

ziplist

<center>图3</center>

ziplist主要属性

zlbtyes: 整个列表占用字节数

zltail_offset: 最后一个元素的偏移量，为了支持反向遍历

zlength: 元素个数。

entry列表： 存储具体数据的节点

zlend: 结束标识。

entry主要属性

prelen: 前一个节点长度，以1个字节或者5个字节，根据上个节点的长度是否超过254字节来选择

encoding: 记录content的类型和长度，通过前面2bit记录content类型，后面的bit记录长度。具体：前面2bit是 00、01或10时，表示字节数组编码（content保存字节数组），剩余其他bit表示content长度；前面bit是11，表示整数编码，content存的是整数，剩余的其他bit表示整数的类型和长度。

content: 存储实际的内容，可以是字节数组或者整数，类型有encoding决定

ZIPLIST的优缺点

优点

1. 内存空间连续、数据结构紧凑（对比 LINKEDLIST 没有前后指针的占用），占用内存更小，内存使用率更高
2. 内存空间连续，遍历时可以利用CPU缓存，遍历效率更高

缺点：

1. 新增和修改时，会重新分配内存，还有可能引起 级联更新问题 （因为更新一个元素，导致后续元素都需要进行更新。如果上个自己小于254字节，prelen会用一个字节表示，否则5字节，如果某个小于254字节的entry修改后大于等于254字节，那么下个entry节点的prelen属性从1个字节扩展到5个字节，而且如果扩展后又变成超过254字节，那么后面的节点也要进行更新，最极端情况是每个节点都是接近254字节，修改头部某一个导致超过254，导致后面所有字节都需要进行更新，不过这种概率很低），所以不太合适存储过多元素。针对ziplist的缺点，后续的版本后引入了listpack（紧凑列表）来解决ziplist的级联更新问题。

LINKEDLIST（双向链表）

LINKEDLIST 其实就是一个双向链表，如下图

linkedlist

<center>图4</center>

优点

1. 获取头尾节点时间复杂度O(1)
2. 获取上个和下个节点时间复杂度O(1)

缺点：

1. 每个节点内存不连续，不能很好利用CPU缓存
2. 每个节点都需要存储上个和下个节点的指针，占用内存相对ZIPLIST多

QUICKLIST（快速列表）

redis 3.2 版本后，结合 ZIPLIST 和 LINKEDLIST 的优缺点，设计出了 QUICKLIST。

如下图

quicklist

<center>图5</center>

如图所示，其实整体还是 LINKEDLIST, 只是每个节点的VALUE底层不再是SDS，而是ZIPLIST。可以利用上ziplist的优点，同时，由于每个节点存储的ziplist长度相对全部用ziplist存储要短，级联更新的问题会得到改善。

哈希(Hash)

哈希的编码实现有2种，一个是ZIPLIST或LISTPACK（redis 7版本用这个替代ziplist），一个是HT(哈希表)。

ZIPLIST编码结构上面已经讲解了，不过在这里使用2个相邻的entry来存储kv，前面一个存储k，后面一个存储v. 如下图：

hash_ziplist

LISTPACK(压缩列表)

listpack

如上图，对比ziplist，大部分几乎完全一样，主要有下面几点不同：

1. LISTPACK 去掉了 ztail_offset字段

2. entry结果不在存储上个节点长度，而且通过lenth存储本节点的长度，这个是解决级联更新的关键点。具体原因：ziplist出现级联更新主要是因为存放上个节点的 prelen 字段可能是1字节或者5字节，如果上个节点变成超过254字节，会影响到当前节点的 prelen 字段从1字节改成5字节，后续的节点也会出现类似的级联更新。而listpack的设计去掉了这个字段，而且通过lenth存储本字节长度，所以不会影响后续的节点，也就不会出现级联更新的问题。

3. encoding的设计更加复杂和紧凑，以节省内存。主要是利用前面的几bit表示编码类型，剩余的bit表示content数据字段的长度或者存储实际的数值（比如整数，避免使用content存储，以节省内存）。下面是几个例子：

   • 0xxxxxxx 表示非负小整数，可以表示 0~127。前面0表示编码，剩余的几bit表示content数据的长度
   • 11110001 aaaaaaaa bbbbbbbb 表示 2 字节有符号整数。前一个字节表示编码类型，后面存储实际的整数，content为空

HT编码（HASHTABLE、哈希表）

其实跟java的hashmap类似，主要是数组+链表（数组的每个元素）组成，不过考虑扩容时性能，使用2个hashtable来是实现渐进式rehash。

hashtable

如上图，HT主要属性如下：

1. table: 一个dictEntry数组，每个数组元素是一个链表。添加kv时，会对key进行hash得到数组下标，如果没有元素直接插入，如果有存在的元素，则通过链表进行串联起来。
2. size: dictEntry数组长度
3. sizemark：哈希表大小掩码，用于计算数组下标
4. used: 哈希表key的个数

疑问：为啥使用2个hashtable来实现？

答：如果使用一个hashtable实现，在扩容时，需针对所有数据进行迁移，耗时较大，如果数据量比较大，影响响应命令的耗时，因此设计2个hashtable时，可以某个下标的链表，无需要迁移所有元素，可以更快响应，减少阻塞。具体迁移步骤大概如下（ht[0]的容量到达扩容条件时）：

1. 为 ht[1] 分配空间

2. 维护一个索引计数变量 rehashidx，初始为0，在rehash时，将ht[0]在 rehashidx 索引上的所有数据rehash到 ht[1]，迁移完 rehashidx += 1。同时，rehash期间，添加元素只会在ht[1]添加，保证待迁移的数据只会越来越少。

3. 迁移完成后，释放 ht[0] 空间，并且将 ht[1] 替换为 ht[0]

hashtable扩容条件：

1. 服务器没有执行BGSAVE和BGREWRITEAOF命令，并且哈希表负载因子大于等于1
2. 服务器正在执行BGSAVE和BGREWRITEAOF命令，负载因子大于等于5

负载因子：已保存的数据/哈希表大小(ht[0].used/ht[0].size)

PS: 如果迁移中时，没有后续命令触发剩余的元素迁移，会一直处于迁移状态吗？redis通过定时任务来对迁移中的字典进行迁移，保证不然字典长时间处于迁移中状态。

集合(Set)

Set 的编码有2种：INTSET 和 HASHTABLE(HT)。当集合中所有的元素都是整数，并且个数不超过512时，采用 INTSET 编码，否则采用 HASHTABLE(HT) 编码（上面已经讲解过，这里不再展开）。

INTSET编码

intset

如上图，特别说明的是encoding字段，它会根据目前元素的最大值选择最小的编码类型，以节省内存。如果有新的最大值，当前的编码类型不满足时，会进行升级，但是升级后不再支持降级。

有序集合(ZSet)

Zset和set都是不能存储重复值的集合，不过Zset通过score属性来对元素进行排序，可以根据score进行范围查询等操作，非常适用排行榜等场景。

Zset的编码实现有2种：SKIPLIST(跳跃列表)+ HT(哈希表) 结合、ZIPLIST(压缩列表，6版本之前)或LISTPACT(6版本之后) 。当有序集合的元素个数小于128，每个元素都小于64字节时，采用ZIPLIST编码，否则采用 ZIPLIST(压缩列表)+ HT(哈希表) 结合的编码。LISTPACK编码上面已经讲解过，不做讲解。

ZIPLIST的编码跟上面讲的一样，不过一个zset元素+分值用2个entry节点进行存储，其中一个存储元素值，另外一个存储分值score，并且按照score从小到达大进行排序。

zset_ziplist

SKIPLIST(跳跃列表)

结构图如下：

skiplist

源码结构( tag 6.2.8)：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

从结构图和源码可知，每个kv对应 zskiplistNode 结构，其实 sds 存储集合元素，score 表示分数，backward 指向后向一个节点，通过这个可以反向遍历，zskiplistLevel 数组，存储多层的指向前向节点的指针以及跨度span（用于计算节点的排名）。

查找过程： 从 header的最高层开始遍历，找到最后一个比目标节点小的节点，然后从这个节点降一层再开始遍历，找到最后一个比目标节点小的节点，按次类推，直到降到最底层，遍历找到目标节点。遍历期间经过的节点称为［搜索路径］。插入节点时，也是根据这个搜索路径来进行插入的，但是插入的节点面临一个问题就是层数多少合适？redis 采用的是随机算法。

插入过程： 通过上面的查找过程得到[搜索路径]，然后根据随机算法算出层数，再将搜索路径上的节点跟这个新节点通过前后指针串起来。

计算层数的随机算法： 如下面源码所示，生成一个范围 0~1的随机数，如果小于0.25，那么层数加1，继续循环，不满足则退出循环，并且不超过最大层数32

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
//#define ZSKIPLIST_P 0.25 
//#define ZSKIPLIST_MAXLEVEL 32

删除过程： 根据查找过程得到的【搜索路径】，然后将删除节点有关联的相关节点重新处理一下前后指针即可，注意更新一下 最高层数 level

更新过程： 如果更新的score和value 带来位置的改变，通过先删除节点，再插入来调整位置

排序规则： 先根据score从小到达排序，如果score相等，通过value进行字典排序（字符串比较排序）。

元素排名： 通过搜索路径经过的所有节点的跨度 span 进行叠加

如上面的源码zset数据结构，还包含了dict（字典）的数据结构，主要是为了根据元素找score可以O(1)的时间复杂度实现，如果使用跳跃列表则需要O(logN)的复杂度，有点利用空间换时间的设计，通过冗余加上dict，提升查询元素score的性能。

本文由mdnice多平台发布