Redis 数据结构底层原理

内部编码：raw、int、embstr、hashtable、ziplist、linkedlist、inset、skiplist

总体数据结构

语音理解 (opens new window)

redisDB结构的expires字典保存了数据库中所有键的过期时间，我们称这个字典为过期字典：

• 过期字典的键是一个指针，这个指针指向键空间中的某个键对象
• 过期字典的值是一个long long类型的整数，这个整数保存了键所指向的数据库键的过期时间

/* Redis数据库结构体 */
typedef struct redisDb {
    // 数据库键空间，存放着所有的键值对（键为key，值为相应的类型对象）
    dict *dict;                 
    // 键的过期时间
    dict *expires;              
    // 处于阻塞状态的键和相应的client（主要用于List类型的阻塞操作）
    dict *blocking_keys;       
    // 准备好数据可以解除阻塞状态的键和相应的client
    dict *ready_keys;           
    // 被watch命令监控的key和相应client
    dict *watched_keys;         
    // 数据库ID标识
    int id;
    // 数据库内所有键的平均TTL（平均过期时间）
    long long avg_ttl;         
} redisDb;

/** 字典数据结构 **/
typedef struct dict {
    // 哈希表的类型，不同类型包括不同的哈希函数，比较函数，键值的内存释放函数
    dictType *type;
    // 存储一些额外的数据，一般用不到
    void *privdata;
    // 两个hashtable，另外一个扩容时用
    dictht ht[2];
    // rehash使用
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

/** hashtable **/
typedef struct dictht {
    // hashtable
    dictEntry **table;
    // 哈希表的大小
    unsigned long size;
    // size - 1
    unsigned long sizemask;
    // 数据长度
    unsigned long used;
} dictht;

// hashtable存放的元素
typedef struct dictEntry {
    // 指向key的指针，肯定时指向一个SDS
    void *key;
    union {
    void *val;
    uint64_t u64;
    int64_t s64;
    } v;
    // hash冲突使用拉链法，指向下一个元素
    struct dictEntry *next;
} dictEntry;

typedef struct redisObject {
	unsigned type:4; // 4 bit
    unsigned encoding:4; // 4 bit
    unsigned lru:LRU_BITS; // 内存淘汰策略 24 bit
    int refcount; // 引用计算法 4 byte
    void *ptr； // 指向真正的数据内存空间 8 byte
    // 总空间： 4bit + 4 bit + 24 bit + 4 byte + 8 byte = 16byte
}

unsigned lru:LRU_BITS：对象最后一次被访问的时间

string

redis中所有的key都是String类型，redis底层是C语言实现的

ASCII码：一个英文字母（不分大小写）占一个字节的空间，一个中文汉字占两个字节的空间

UTF-8编码：一个英文字符等于一个字节，一个中文（含繁体）等于三个字节

Unicode编码：一个英文等于两个字节，一个中文（含繁体）等于两个字节

C中字符串的定义：

char[] data = 'guojia'
# C语言中，会默认给字符串末尾增加一个'\0'，一个字节
# 假如有的字符串中就包含'\0'怎么办？

redis是通过加了个sds的结构解决\0的问题，很好奇其他中间件如何解决的，每个都需要自己解决，是不是太麻烦了

二进制安全

为了解决上面的问题，redis重新定义了一个数据结构sdshdr(sds：simple dynamic string)：

// redis 3.0
struct sdshdr {
    // 记录buf数组中已使用字节的数量，即SDS所保存字符串的长度
    unsigned int len;
    // 记录buf数据中未使用的字节数量
    unsigned int free;
    // 字节数组，用于保存字符串
    char buf[];
};

内存预分配

需要修改某个key的value，如果增加的长度超过free，就需要对原数组进行扩容了；redis扩容的规则：

• （len + addlen）* 2，例如：当前数组长度是6，free=0，要修改成12个字节的新字符串，扩容后长度 = （6 + （12 - 6）） * 2 = 24
• 当value的长度超过1M（即1024个字节），每次扩容都是 + 1M

扩容之后的长度要比需要的长度大，称之为内存预分配

兼容部分C字符串函数

虽然SDS的API是二进制安全的，但还是像C字符串一样以空字符结尾，目的是为了让保存文本数据的SDS可以重用一部分C字符串的函数

C字符串与SDS对比

程序中有两个在内存中紧邻着的字符串 s1 和 s2，其中s1保存了字符串“redis”，s2 则保存了字符“MongoDb”；现在将s1 的内容修改为redis cluster，但是又忘了重新为s1 分配足够的空间，这时候就会出现以下问题：原本s2中的内容已经被S1的内容给占领了，s2现在为 cluster，而不是“Mongodb”，这就是缓冲区溢出

SDS升级

redis 3.2之前的数据结构，len和free都是int类型，int要占用4个字节；并且一般我们字符串的长度没有4个字节这么长，所以很浪费空间；3.2对SDS进行了升级：

// 3.2
/* 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 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[];
};

3.2版本及之后，会根据字符串的长度来选择对应的数据结构：

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)  // 32
        return SDS_TYPE_5;
    if (string_size < 1<<8)  // 256
        return SDS_TYPE_8;
    if (string_size < 1<<16)   // 65536 64k
        return SDS_TYPE_16;
    if (string_size < 1ll<<32)  // 4294967296 4G
        return SDS_TYPE_32;
    return SDS_TYPE_64;
}

sdshdr5的数据结构如下：

flags占用8bit，前3bit表示数据结构的类型，例如000表示sdshdr5，后5bit表示buf的字节数（长度），2^5 - 1 = 31，最好能表示31个字节的字符串；free：31 - len；如果字符串长度超过31，就要用sdshdr8表示：

flags占用8bit，前3bit表示数据结构的类型，例如001表示sdshdr8，后5bit未使用；len表示buf的字节数，allo表示分配的字节数；最长能表示的字符串长度 = 2^8 - 1 = 255

---

推测： sdshdr5申请的时候就会分配31个字节，然后31 - len就能求出free sdshdr8及更大的结构不会一下就分满，所以需要alloc记录分配的内存，alloc - len = free

内部编码

typedef struct redisObject {
	unsigned type:4; // 4 bit
    unsigned encoding:4; // 4 bit
    unsigned lru:LRU_BITS; // 内存淘汰策略 24 bit
    int refcount; // 引用计算法 4 byte
    void *ptr； // 指向真正的数据内存空间 8 byte
    // 总空间： 4bit + 4 bit + 24 bit + 4 byte + 8 byte = 16byte
}

embstr

一个redisObject一共是16byte，操作系统通常一下会读取一行数据（缓存行），一般缓存行是64byte；所以一次内存读取64 - redisObject（16byte)）= 48byte，会多读出来48byte的数据；如果我们的数据小于48byte，直接和redisObject放在一起就可以一次读出来；48byte的字符串使用sdshdr8，这个数据结构本身占用3个字节（len + alloc + flags），再加上会在字符串末尾自动加上\0（1byte），48 - 4 = 44（byte），如果key字符串长度小于等于44，就可以使用embstr

int

C语言long类型就是8byte存储的，如果value是一个数值，就直接把value存在ptr的位置就好了，不用再重写申请内存空间了；不过如果value超过long的最大值就不行了

raw

value长度大于44，使用raw

list

ziplist

• zlbytes：32bit，4个字节，记录ziplist占用的内存字节数；也就是说一个ziplist最大可以包含2^32 - 1个字节，接近4GB
• zltail：32bit，4个字节，记录最后一个entry在ziplist中的偏移字节数；方便从尾部遍历
• zlen：16bit，2个字节，记录ziplist中entry的个数，一个ziplist最多存放2^16 -1 = 65535个entry
• zlend：8bit，1个字节，固定值255，标志ziplist的尾巴；当从 --->（左往右遍历）到最后一个entry，再往下判断prevrawlen的时候发现是255就表示ziplist已结束（再往下判断第一个字节是不是255，如果是表示ziplist结束，所以prevrawlen的第一个字节，最大只能254，如果prevrawlen值也能是255，从左往右就无法判断结束了）；这也是prevrawlen最大只能是254的原因；当从右完整遍历_（<---）_的时候，判断前一个元素的长度为0就代表ziplist结束了
• entry：list的值
  • prevrawlen：记录前一个元素的长度，为了从右往左遍历_（<---）_
  • len：当前entry的长度
  • data：当前entry的value

（每个entry的大小都不一样，不能实现随机读取）

len字段的用法： （这里len是变长的，就是为了节约len的长度）

序号	字段	说明
1	00xxxxxx	剩余的6个bit用来表示长度，最大长度2^6 - 1个byte
2	01xxxxxx xxxxxxxx	前两个高位bit是01，len字段占用2byte，剩余14bit表示长度，最大长度2^14 - 1个byte
3	10xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx	前两个高位bit是10，len字段占用4bit，剩余32bit表示长度，最大长度2^32 - 1个byte
4	11000000	前两个高位bit是11，值为OXC0，len字段占1byte，后面的data为2byte的int16类型
5	11010000	前两个高位bit是1101，值为OXD0，len字段占1byte，后面的data为4byte的int32类型
6	...	...

linkedlist

3.2之前，list底层的编码是ziplist和linkedlist实现的；当list对象中元素的长度比较小或者数量比较少的时候，采用ziplist来存储，当list对象中元素的长度比较大或者数量比较多的时候，则会转而使用双向列表linkedlist来存储

quicklist

3.2之后，一个list底层可以有多个ziplist，ziplist由quicklist关联起来；可以定义每个ziplist的大小，超过就分裂

quicklist	quicklistNode	list-max-ziplist-size

• 管理quicklistNode组成的双向链表
• head：指向双向链表的头节点
• tail：指向双向链表的尾节点
• count：元素总个数
• length：quicklistNode节点数 |
• 每个ziplist由一个quicklickNode管理
• zl：指向ziplist的指针
• count：ziplist元素的个数
• prev：指向前一个quicklistNode
• next：指向后一个quicklistNode |
• 当取正值的时候，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成5的时候，表示每个quicklist节点的ziplist最多包含5个数据项
• 当取负值的时候，表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时，它只能取-1到-5这五个值，每个值含义如下：
  • -5：每个ziplist大小不能超多64kb
  • -4：不能超过32kb
  • ... |

hash

当数据量比较小，或者单个元素比较小时，底层用ziplist存储（fied和name为一个entry），数据大小和元素阈值可以通过参数控制：

// ziplist元素个数超过512，改为hashtable
hash-max-ziplist-entries 512
// 单个元素超过64byte时，改为hashtable
hash-max-ziplist-value 64

set

下面两个条件任意满足一个时，底层是hashtable:

• 元素个数大于set-max-intset-entries
• 元素无法用整型表示

否则使用inset

inset

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

typedef struct intset {
    uint32_t encoding; // 编码。
    uint32_t length;   // 数组长度。
    int8_t contents[]; // 整数值数值。
} intset;

根据插入数值大小，决定contents数组的encoding格式。编码格式分别有int16_t，int32_t，int64_t。以最大的数值为准，如果最大的数值是int64_t那么数组的每个元素都是int64_t，contents还是一个有序的数组；优点是统一简单，提高数组查找效率——源码实现是通过二分法查找。如果数组不同数值用不同的编码存储，就很难用二分法查找了（这也是为什么使用inset的原因），只能使用hashtable来提高查询效率； 但是这样做一方面提高了查找效率，另一方面也会导致内存浪费，如果所有数据中，只有一个数据是int64_t，其它数据都是int16_t，整个数组都以int64_t存储，显然会造成内存浪费

zset

底层数据结构为hashtable + 跳表；当数据量比较少是，用ziplist

// 元素个数超过128，使用跳表
zset-max-ziplist-entries 128
// 单个元素大小超过64byte，使用跳表
zset-max-ziplist-value 64

skiplist

想快速找到上图链表中的 10 这个元素，只能从头开始遍历链表，直到找到我们需要找的元素。查找路径：1、3、4、5、7、8、9、10。这样的查找效率很低，平均时间复杂度很高O(n)；那有没有办法提高链表的查找速度呢？如下图所示，我们从链表中每两个元素抽出来，加一级索引，一级索引指向了原始链表，即：通过一级索引 7 的down指针可以找到原始链表的 7 。那现在怎么查找 10 这个元素呢

先在索引找 1、4、7、9，遍历到一级索引的 9 时，发现 9 的后继节点是 13，比 10 大，于是不往后找了，而是通过 9 找到原始链表的 9，然后再往后遍历找到了我们要找的 10，遍历结束。有没有发现，加了一级索引后，查找路径：1、4、7、9、10，查找节点需要遍历的元素相对少了，我们不需要对 10 之前的所有数据都遍历，查找的效率提升了；那如果加二级索引呢？如下图所示，查找路径：1、7、9、10。是不是找 10 的效率更高了？这就是跳表的思想，用“空间换时间”，通过给链表建立索引，提高了查找的效率

跳表查询、插入、删除的时间复杂度为O(log n)

为什么选择跳表而不是红黑树

按照区间来查找数据这个操作，红黑树的效率没有跳表高。按照区间查找数据时，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，非常高效；对于树而言，要取同一层级的元素还是比较复杂的

跳表的随机层数

1.6.1 每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找；这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的 2:1 的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点重新进行调整

skiplist 为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是 为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是 3，那么就把它链入到第 1 层到第 3 层这三层链表中。为了表达清楚，下图展示了如何通过一步步的插入操作从而形成一个 skiplist 的过程：

参考：

1. Redis从入门到高可用分布式实践 (opens new window)
2. Redis从入门到高可用分布式实践(sentinel和Cluster) (opens new window)
3. Redis6.0底层源码设计原理与核心数据结构详解 (opens new window)
4. Redis中有哪些数据结构及底层实现原理 (opens new window)