Redis数据结构及对象（上）

Redis对象及底层数据结构

redis一共有五大常用的对象，用type命令即可查看当前键对应的对象类型，分别是string（字符串）、hash（哈希）、list（列表）、set（集合）、zset（有序集合），但是这些只是对外的数据结构，实际上每一个对象都有两到三种不同底层数据结构实现，可以通过object encoding命令查看键值对应的底层数据结构实现，

下表即为每种对象所对应的底层数据结构实现。

类型	编码	底层数据结构
string	int	整数值
string	raw	简单动态字符串
string	embstr	用embstr编码的简单动态字符串
hash	ziplist	压缩列表
hash	hashtable	字典
list	ziplist	压缩列表
list	linkedlist	双端列表
set	intset	整数集合
set	hashtable	字典
zset	ziplist	压缩列表
zset	skiplist	跳表和字典

简单动态字符串（SDS）

定义

redis并没有使用C字符串，而是使用了名为简单动态字符串（SDS）的结构，SDS的定义如下：

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;

    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];
};

len:记录字符串长度，大小为4个字节
free: 记录buf[]中未被使用字节数量，大小为4个字节
buf[]: 保存字符串，大小为字符串大小+1，因为buf[]最后一个字节保存'\0' 所以sds的总大小为 = 4 + 4 + size(str) + 1

SDS的作用

那么redis为什么要使用看起来更占空间的SDS结构呢？主要有以下几个原因：

O(1)复杂度获得string的长度 相比于C字符串需要遍历string才能获得长度(复杂度O(N))，SDS直接查询len的数值即可。
防止缓冲区溢出 当修改C字符串时，如果没有分配够足够的内存，很容易造成缓冲区溢出。而使用SDS结构，当修改字符串时，会自动检测当前内存是否足够，如果内存不够，则会扩展SDS的空间，从而避免了缓冲区溢出。
减少修改字符串带来的频繁的内存分配 每次增长或缩短C字符串，都需要重新分配内存，而redis经常被用在数据修改频繁的场合，所以SDS采用了两种策略从而避免了频繁的内存分配。 ①空间预分配如上文所述，SDS会自动分配内存，如果修改后字符串内存占用小于1MB，则会分配同样大小的未使用内存空间。（eg len: 20kb free: 10kb→ len: 40kb free 40kb），如果大于1MB，则分配1MB未使用内存空间。如此一来就可以避免因为字符串增长带来的频繁空间分配。 ②惰性删除当缩短字符串时，SDS并没有释放掉相应的内存，而是保留下来，用free记录未使用的空间，为以后的增长字符串做准备。
二进制安全 SDS会以处理二进制数据的形式存取buf中的内容，从而让SDS不仅可以保存任意编码的文本信息，还可以保存诸如图片、视频、压缩文件等二进制数据。

双端列表

定义

双端列表作为一种常用的数据结构，当一个list的长度超过512时，那么redis将使用双端列表作为底层数据结构。下面是一个列表节点的定义：

typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

多个列表节点串联起来便可实现双端列表。

typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 链表所包含的节点数量
    unsigned long len;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);

} list;

可以看到双端列表是一个无环双端带表头表尾节点的链表。

字典

定义

散列表（Hash table，也叫哈希表），是根据键而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

当hashtable的类型无法满足ziplist的条件时（元素类型小于512且所有值都小于64字节时），redis会使用字典作为hashtable的底层数据结构实现。redis的字典（dict）中维护了两个哈希表（table），而每个哈希表包含了多个哈希表节点（entry）。下面分别来介绍这三个对象。

哈希表节点

typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

key：键值对中的键。
v: 键值对中的值，可以看到值可以为一个指针，或者是一个uint64整数或者int64整数。
next：是为了用链地址法解决hash冲突。

哈希表

typedef struct dictht {

   // 哈希表数组
   dictEntry **table;

   // 哈希表大小
   unsigned long size;

   // 哈希表大小掩码，用于计算索引值
   // 总是等于 size - 1
   unsigned long sizemask;

   // 该哈希表已有节点的数量
   unsigned long used;

} dictht;

table：是一个保存着指向所有节点指针的数组。
size: 记录了table数组的大小。
sizemask: 用于和hash值一起计算索引值（index = hash & sizemask ）

字典

typedef struct dict {

   // 类型特定函数
   dictType *type;

   // 私有数据
   void *privdata;

   // 哈希表
   dictht ht[2];

   // rehash 索引
   // 当 rehash 不在进行时，值为 -1
   int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。
字典内部有两个哈希表，这样做的目的是为rehash做准备。

hash算法

当在哈希表中存取数据时，首先需要用hash算法算出键值对中的键所对应的hash值，然后再根据根据table数组的大小取模，计算出对应的索引值，再继续接下来的操作。redis使用了MurmurHash2 算法来计算键的哈希值，又使用了快速幂取模算法降低了取模的复杂度。整个过程如下:

hash = dict->type->hashFunction(k0);
index = hash & dict->ht[0].sizemask;

当hash冲突发生时则采用链地址法解决hash冲突。

rehash

当哈希表保存的键值对越来越多时，哈希表的负载因子（load factor = used / size）越来越大，原本O(1)复杂度的查找也会渐渐趋向于O(N)，为了保证哈希表的负载因子在一定的范围之内。redis需要动态的调整table数组的大小，其中最重要的便是rehash过程。rehash分以下的几个步骤：

为字典的 ht[1] 哈希表分配空间，需要注意的是新的size必须是2^n，这主要是为了配合快速幂取模算法。
将ht[0]上的键值对rehash到ht[1]上，即重新计算ht[0]上所有键值对的hash值和索引值，然后分配到ht[1]上，当原来的哈希表数据量很大时可能会引起线程的阻塞，所以redis采用渐进式的rehash方式。
ht[0]表释放，原子性的替换ht[1]至ht[0]，并创建一个空的哈希表分配至ht[1]

渐进式rehash

redis的rehash过程并不是一次性集中rehash，而是分批间隔式的，在dict中的rehashidx便是为此服务。相较于一次性的rehash，渐进式的rehash多了下面这些步骤:

开始rehash时，将rehashidx置为0。
当完成了一次rehash后，将rehashidx自增1，直到遍历完所有的table数组。
在rehash过程中，如果有对字典进行增加，则只增加ht[1]，如果是查找，则先查找ht[0]，如果找不到则去查找ht[1]，而如果是删除和更新，则ht[0]和ht[1]同步操作。
完成所有rehash后，将rehashidx置为-1。

这是比较典型的分而治之的思想，将一次性集中作业分散，降低了系统的风险。

跳跃表

定义

跳表的的查找复杂度为平均O(logN)/最坏O(N)。在很多场合下作为替代平衡树的数据结构，在redis中，如果有序集合的属性不满足ziplist的要求，则将跳表作为有序集合的底层实现。

上图即为一个完整的跳表，其中有几点比较重要，这个跳表一共有三个节点再加上一个头节点，最高有五层。一个跳跃表包含了两种对象，一个是跳跃表节点，一个是跳跃表。

跳跃表节点

typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

backward：后退指针，和双端列表一样，指向上一个节点。
score：分值，有序列表的排序依据。
obj：成员对象，实际上为一个SDS，在有序集合中分值可以重复，但成员对象不能重复。
level：层，跳表的关键所在，在条表中每一层包含了1到n个节点，在有序的情况下，可以快速遍历数组。
forward：下一个节点的对象，这里的下一个代表是第一个或者是第n个。
span: 下一个节点和现在节点的距离。

跳跃表

typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

跳跃表中保存了头尾节点，方便遍历，还保存了节点的数量，可以在O(1) 复杂度内返回跳跃表的长度。

整数集合

定义

当集合的值全为整数且集合的长度不超过512时，redis采用整数集合作为集合的底层数据结构。

typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

encoding：整数集合中元素的编码方式

INTSET_ENC_INT16 ， contents 就是一个 int16_t 类型的数组（最小值为 -32,768 ，最大值为 32,767 ）。 INTSET_ENC_INT32 ， contents 就是一个 int32_t 类型的数组（最小值为 -2,147,483,648 ，最大值为 2,147,483,647 ）。 INTSET_ENC_INT64 ， contents 就是一个 int64_t 类型的数组（最小值为 -9,223,372,036,854,775,808 ，最大值为 9,223,372,036,854,775,807 ）。

length：数量
contents：集合元素虽然contents看起来是int8_t，但是它的具体内容的存取还是按encoding的方式完成。

升级

redis采用多种编码的方式，主要还是为了省内存。当集合中加入了不符合当前集合编码的数字时，数组集合会自动更新至能匹配到的编码，值得注意的是，这种升级是不可逆的，只能由小往大，不能降级。如此一来，就能够在存放小数据时，剩下很大的空间，而且也不必为编码不匹配的事情而烦恼了。

压缩列表

压缩列表是redis又一个为了节省内存所做的优化，是list/hash/zset的底层数据结构之一，当数据值不大且数量较低时，redis都会使用压缩列表。

zlbytes：记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算 zlend 的位置时使用。
zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen：记录了压缩列表包含的节点数量：当这个属性的值小于 UINT16_MAX （65535）时，这个属性的值就是压缩列表包含节点的数量；当这个值等于 UINT16_MAX 时，节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX：压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend：特殊值 0xFF （十进制 255 ），用于标记。压缩列表的末端。

压缩列表和双端列表有些类似，不过一个用指针衔接起来，一个则是用数组和长度衔接起来。下面来看一看压缩列表节点的定义：

prevrawlen：前置节点的长度，相当于双端列表中的前置指针，通过它可以计算出前置节点的地址。
coding: 和正数集合类似，是为了表明content中是何种数据
content: 数据

总结

本文对于redis常见的数据结构及其底层实现进行了分析和梳理，希望能够理清这些底层数据结构对于redis高性能的作用和影响。