深入浅出Redis-redis底层数据结构

Redis 是一个基于键值对（key-value）的分布式存储系统，与Memcached类似，却优于Memcached的一个高性能的key-value数据库。

在《Redis设计与实现》这样描述：

Redis 数据库里面的每个键值对（key-value）都是由对象（object）组成的：

　　数据库键总是一个字符串对象（string object）;

　　数据库的值则可以是字符串对象、列表对象（list）、哈希对象（hash）、集合对象（set）、有序集合（sort set）对象这五种对象中的其中一种。

我们为什么会说Redis 优于Memcached 呢?

因为Redis 的出现，丰富了memcached 中key-value的存储不足，在部分场合可以对关系数据库起到很好的补充作用，而且这些数据类型都支持push/pop、add/remove及取交集并集和差集及更丰富的操作，而且这些操作都是原子性的。

我们今天探讨的并不是Redis 中value 的数据类型，而是他们的具体实现——底层数据类型。

底层数据结构有一下数据类型：

简单动态字符串(SDS simple dynamic string)
链表(linkedlist)
字典(hashtable)
跳跃表(skiplist)
整数集合(intSet)
压缩列表(ziplist)

也就是说，我们所使用的五种数据类型，是由以上6种底层数据类型实现的。

Redis 是一个开源的使用ANSI C语言编写的key-value 数据库.

以下是五种value类型与Redis底层C语言实现的6种底层实现类型的对应关系。

五种value类型	对应底层实现类型
字符串： string	SDS
集合： set	intSet/hashtable
列表： list	ziplist/linkedlist
哈希： hash	ziplist/hashtable
有序集合:zset	ziplist/skiplist

接下来我们会一步一步的探讨这些数据结构有什么特点，以及他们是如何构成我们所使用的value 数据类型。

深入浅出Redis-redis底层数据结构（上）

深入浅出Redis-redis底层数据结构（下）

1 简单动态字符串（simple dynamic string）SDS

Redis中的字符串并不是直接使用的C语言的字符串，而是自定义一个SDS类型，即Redis默认的字符串类型就是SDS。

如下，msg和”hello world”二者都是字符串对象，底层实现都是保存一条SDS类型的数据。

redis>SET msg "hello world"
OK

除了用来保存字符串以外，SDS还被用作缓冲区（buffer）AOF模块中的AOF缓冲区。

1.1 SDS 的定义

/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

len: 用于记录buf 中已经使用的空间长度（下图数据的长度为5）
free: 用于记录buf 中还空余的空间（初次分配空间，一般没有空余，在对字符串修改的时候，会有剩余空间出现）
buf: 字符数组，用于记录我们的字符串（记录Redis）

sds

1.2 sds对比c语言string的优势

在Redis中，不是靠空字符来判断字符串的结束的，而是通过len这个属性。那么，即便是中间出现了空字符对于SDS来说，读取该字符仍然是可以的
获取字符串长度， O(1)
Redis 中SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：

当我们需要对一个SDS 进行修改的时候，redis 会在执行拼接操作之前，预先检查给定SDS 空间是否足够，如果不够，会先拓展SDS 的空间，然后再执行拼接操作

减少修改字符串时带来的内存重分配次数
特殊字符判读结束

2 链表(linkedlist)

当一个列表键包含了数量较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。

多个链表节点组成的双端链表.

2.1 链表的数据结构

每个链表节点使用一个 listNode结构表示（adlist.h/listNode）：

typedef struct listNode{
      struct listNode *prev;
      struct listNode * next;
      void * value;
}

双端链表：多个链表节点组成的双端链表

list_node

2.2 列表list基于链表的定义

数据定义：

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 组成的结构图：

list

链表的特点：

双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是O（N）
无环：表头节点的 prev 指针和表尾节点的next 都指向NULL，对立案表的访问时以NULL为截止
表头和表尾：因为链表带有head指针和tail 指针，程序获取链表头结点和尾节点的时间复杂度为O(1)
长度计数器：链表中存有记录链表长度的属性 len
多态：链表节点使用 void* 指针来保存节点值，并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。

3 字典(hashtable)

Redis中键值对(k-v)的存储和hash类型数据都是用hashtable实现。

如SET msg “hello world”，底层就是存储了一个(“msg”, “hello world”)的hashtable数据。

3.1 hashtable底层定义(哈希表和哈希表节点)

hashtable的底层结构是数组 + 链表的形式；

一个空的字典结构如图所示：

数据是存在dictEntry数组中，然后以链表形式连接。

hash

3.1.1 哈希表定义(数组)

typedef struct dictht {
   //哈希表数组
   dictEntry **table;
   //哈希表大小
   unsigned long size;

   //哈希表大小掩码，用于计算索引值
   unsigned long sizemask;
   //该哈希表已有节点的数量
   unsigned long used;
}

3.1.2 哈希表节点（dictEntry）

typeof struct dictEntry{
   //键
   void *key;
   //值
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;

}

hash_node

在数据结构中，我们清楚key 是唯一的，但是我们存入里面的key 并不是直接的字符串，而是一个hash 值，通过hash 算法，将字符串转换成对应的hash 值，
然后在dictEntry 中找到对应的位置。

这时候我们会发现一个问题，如果出现hash 值相同的情况怎么办？Redis 采用了链地址法：

当k1 和k0 的hash 值相同时，将k1中的next 指向k0 想成一个链表。

注意如图，key是唯一的，不存在重复，只是两个key的hash值可能重复，所以数组索引可能一直，此时使用链地址法存放。

3 redis hash结构

hashtable

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privedata;
    // 哈希表
    dictht  ht[2];
    // rehash 索引
    in trehashidx;

}

4 跳跃表(skiplist)

总结

跳跃表是有序集合的底层实现之一
主要有zskiplist 和zskiplistNode两个结构组成
每个跳跃表节点的层高都是1至32之间的随机数
在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的对象必须是唯一的
节点按照分值的大小从大到小排序，如果分值相同，则按成员对象大小排序

4.1 什么是跳跃表？

漫画:什么是跳跃表？

redis(五)跳跃表

skiplist1

skiplist2

如图，是跳跃表的存储结构，总结几点：

1 skiplist结构：

  1. 提取极限： 同一层只有两个节点时，就没有比较的意义了
  2. 每一层节点数是前一层的一般，所以添加节点时会判断是否提取(抛硬币)

2 如何插入？

新节点和各层索引节点逐一比较，确定原链表的插入位置。O（logN）

3 如何删除？

删除每一层的该节点即可，如果某一层只剩下该节点，那就干掉整个一层。

4 新节点是否提升为上一级索引?

利用抛硬币的随机方式，决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币，结果为“负”则停止。O（logN）

因为跳跃表删除和添加的节点是不可预测的，很难用一种有效的算法保证跳跃表的索引部分始终均匀。
随机抛硬币的方法虽然不能保证索引绝对均匀分布，却可以让大体趋于均匀。

5 skiplist和平衡树

skiplist的有点事维护平衡的成本比较低，完全是依靠随机。
二叉查找树在多次插入删除后，需要Rebalance来重新来调整结构平衡。

4.2 redis skiplist实现

Redis中使用跳跃表结构的有两个：

有序集合zset 和在集群节点中用作内部数据结构。

4.2.1 跳跃表的数据结构定义

如下图，Redis 的跳跃表主要由两部分组成：zskiplist（链表）和zskiplistNode（节点）

skiplist

Redis的跳跃表实现与传统跳跃表定义有三点不同：

允许重复分数；
排序不止根据分数，还可能根据成员对象（当分数相同时）；
有一个前继指针，因此在第1层，就形成了一个双向链表，从而可以方便的从表尾向表头遍历，用于zrevrange命令的实现。

1 zskiplist

typedef struct zskiplist {
     //表头节点和表尾节点
     structz skiplistNode *header,*tail;

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

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

}zskiplist;

- header ：指向跳跃表的表头节点。
- tail ：指向跳跃表的表尾节点。
- level ：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
- length ：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

2 zskiplistNode

typedef struct zskiplistNode{
　　//分值
    double score;

　　//成员对象
    robj *obj;

　　//层
    struct zskiplistLevel{
　　　　//前进指针
        struct zskiplistNode *forward;
　　　　//跨度
        unsigned int span;
    } level[];

　　//后退指针
    struct zskiplistNode *backward;
}

4.2.2 zskiplistNode属性成员解析

1、分值(double score)和成员对象(robj obj)：(zset的value值)

    obj是该结点的成员对象指针，score是该对象的分值，是一个浮点数,跳跃表中的所有结点，都是根据score从小到大来排序的。
    成员对象obj指向一个字符串，这个字符串对象保存着一个SDS值.
    同一个跳跃表中，各个结点保存的成员对象必须是唯一的,分值可以相同。

2、节点之间关联结构实现：

  1 zskiplistLevel level[] 数组:

    如下图：
    level数组对应的是该节点的层次信息，是一个数组，因为一个节点可能对应多个层次(翻硬币)，很容易理解。

    1、前进指针： level[i].forward，表示该节点所在层次的下一个节点.
          如下图节点5在L1/L2/L3三层分布，
          则节点5的level[1].forward是none，level[2].forward指向7，level[3].forward指向6
　　2、跨度：level[i].span 用于记录forward节点和当前节点的距离
          如5的level[3].forward指向6，span是1；level[2].forward指向7，span是2；

  如上图：
　2、后退指针：backward 节点中用 BW 字样标记节点的后退指针，它指向位于当前节点的前一个节点。
              这个并不是层次的，而是相邻查询。

skiplist1

5 整数集合(intSet)

整数集合是Set的底层实现之一，当一个集合中只包含整数，且这个集合中的元素数量不多时，redis就会使用整数集合intset作为集合的底层实现。

5.1 intSet结构定义

intset将数组定义为int8_t，但实际上数组保存的元素类型取决于encoding

typedef struct intset{
    //编码方式
    uint32_t enconding;

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

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

}

intset2

5.2 升级

问题： intset有默认的enconding方式(intset_enc_int16),如果存储编码方式不同的数据时，就需要使用redis中的升级策略解决

Intset 中升级整数集合并添加新元素共分为三步进行：

根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
将底层数组现有的所有元素都转换成新的编码格式，重新分配空间
将新元素加入到底层数组中

intset

优势：

提升灵活性
节约内存

5.3 总结

整数集合是集合建的底层实现之一
整数集合的底层实现为数组，这个数组以有序，无重复的范式保存集合元素，在有需要时，程序会根据新添加的元素类型改变这个数组的类型
升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存
整数集合只支持升级操作，不支持降级操作

6 压缩列表(ziplist)

ziplist是redis list/hash/zset的实现之一。

6.1 使用场景

list：

当一个list只把含少量元素，并且每个列表元素要么就是小整数，要么就是长度比较短的字符串，那么Redis 就会使用压缩列表来做列表键的底层实现。
hash:

当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。
zset:

1) zset会根据zadd命令添加的第一个元素的长度大小来选择编码方式，满足zset_max_ziplist_entries的值不为0，第一个元素的长度小于server.zset_max_ziplist_value，否则就使用skiplist。　　2) 当待新加的新的字符串长度超过zset_max_ziplist_value（默认值64）时或者ziplist保存的节点数量超过server.zset_max_ziplist_entries（默认值128）时使用skiplist。

6.2 ziplist结构定义

6.2.1 debug object key

可以用过debug object key 来查看redis数据存储使用的数据结构。

> zadd programmings 1.0 go 2.0 python 3.0 java
(integer) 3

> debug object programmings
Value at:0x7fec2de00020 refcount:1 encoding:ziplist serializedlength:36 lru:6022374 lru_seconds_idle:6 > hmset books go fast python slow java fast
OK
> debug object books
Value at:0x7fec2de000c0 refcount:1 encoding:ziplist serializedlength:48 lru:6022478 lru_seconds_idle:1

debug object 输出的 encoding 字段都是 ziplist，这就表示内部采用压缩列表结构进行存储。

6.2.1 结构定义

ziplist

struct ziplist<T> {
    int32 zlbytes; // 整个压缩列表占用字节数
    int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点

    int16 zllength; // 元素个数
    T[] entries; // 元素内容列表，挨个挨个紧凑存储
    int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

struct entry {
   int<var> prevlen; // 前一个 entry 的字节长度

   int<var> encoding; // 元素类型编码
   optional byte[] content; // 元素内容
}

重点记忆：结合图

ztail_offset：用来快速定位到最后一个元素，然后倒着遍历(实现双向遍历)
prevlen: 前一个 entry 的字节长度，当压缩列表倒着遍历时，需要通过这个字段来快速定位到下一个元素的位置。
encoding: Redis 通过这个字段的前缀位来识别具体存储的数据形式.(为了节约存储空间)

6.2.2 操作

1 增加元素

因为 ziplist 都是紧凑存储，没有冗余空间 (对比一下 Redis 的字符串结构)。意味着插入一个新的元素就需要调用 realloc 扩展内存。
取决于内存分配器算法 和 当前的 ziplist 内存大小，realloc 可能会重新分配新的内存空间，
并将之前的内容一次性拷贝到新的地址，也可能在原有的地址上进行扩展，这时就不需要进行旧内容的内存拷贝。

如果 ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist 不适合存储大型字符串，存储的元素也不宜过多。

2 级联更新

前面提到每个 entry 都会有一个 prevlen 字段存储前一个 entry 的长度。如果内容小于 254 字节， prevlen 用 1 字节存储，否则就是 5 字节。
这意味着如果 某个 entry 经过了修改操作从 253 字节变成了 254 字节，那么它的下一个 entry 的 prevlen 字段就要更新，从 1 个字节扩展到 5 个字节;
如果这个 entry 的长度本来也是 253 字节，那么后面 entry 的 prevlen 字段还得继续更 新。

如果 ziplist 里面每个 entry 恰好都存储了 253 字节的内容，那么第一个 entry 内容的修改就会导致后续所有 entry 的级联更新，这就是一个比较耗费计算资源 的操作。

删除中间的某个节点也可能会导致级联更新，读者可以思考一下为什么? 因为prevlen会变

Show Disqus Comments

Redis(8)-深入浅出Redis-redis底层数据结构