REDIS数据结构与对象

卢亚光

REDIS 数据结构与对象 375 前言Redis 是一种非关系类型数据库，以（k, v）的形式储存数据信息。由于读写速度很快，常被应用于缓存方向。Redis 使用对象来代表数据库中的键和值。Redis 有 5 种数据对象，分别是字符串对象（ String 对象）、列表对象（ List ）、哈希对象（ Hash ）、集合对象、以及有序集合对象（Sorted Set）五种。其 key 值的形式都是使用的字符串形式，value 的形式可以是上面五种对象中的任意一种。Redis 对象内存结构如图1所示:这里 type 代表对象的种类。encoding 代表这个对象的编码形式。ptr 代表着指向储存数据的指针，针对不同的数据对象，有着不同的编码形式，其底层的数据结构也是不尽相同的。下图为 Redis 数据对象编码方式与数据结构的对应关系。1、字符串对象Redis 的键对象都是字符串对象。并且值也可以使用字符串对象创建。根据编码形式的不同，分为 int 编码，raw 编码以及 embstr 三种编码形式。1.1 int编码当 Redis 的对象中的值储存整数值时，其使用的便是 int 编码。其数据直接储存在内存当中，无需特殊的数据结构储存数据。1.2 raw编码Raw 编码底层的数据结构使用的是 SDS（简单动态字符串）结构。Redis 底层是用 c 语言实现的。但是在实现字符串对象的数据结构时，并没有使用简单的字符串的数据结构形式。而是使用 SDS 的结构进行储存。相比较普通字符串，SDS 对象结构如下所示/*   * 保存字符串对象的结构   */  struct sdshdr {            // buf 中已占用空间的长度      int len;        // buf 中剩余可用空间的长度      int free;        // 数据空间      char buf[];  };这里 len 用来记录数据空间已经使用的长度，free 表示数据空间剩余的长度。buf 用来表示储存数据的数据空间。由此对象可知，SDS 结构的好处有：1、获取对象长度的时间负杂度为 O(1)。2、减少更改字符串时内存的重新分配次数 。SDS 在进行更改操作时，会进行预检查，查看剩余空间是否足够，如不够的话，会进行扩展，然后进行字段的拼接或者其它操作。并且由于含有 len 字段以及 free 字段。在进行内存的重新分配，一般来说。进行 n 次字符串的增长会进行n次的扩容，这里使用 SDS 扩容的次数哦可以小于 n 次。3、能够保存特殊的字符。普通字符串由于需要判断字符串截止位置，会以第一个出现空字符的位置认为是字符串的截止位置。所以只能用来保存文本数据，这里 SDS 记录的字符串的使用长度 len，因此就算数据中含有空字符，仍然是可以储存的。1.3 embstr 编码同 raw 一样，embstr 编码底层储存数据的结构也是 SDS 形式。但是两者储存字符串的长度不同，并且内存的分配策略也有所不同，对于 embstr 使用于储存小于32字节的字符串值，分配一个连续的空间用来储存 redisObject 结构与数据结构，如下图所示：而对于 raw 来说，需要进行两次内存分配，创建对象时需要为 redisObject 以及 SDS 分别分配一块儿内存，两者使用 ptr 进行链接这里，当 int 编码加入非整数字符或者 embstr 的编码长度增加超过 32 字节时，会转换为 raw 编码。2、列表对象列表对象有两种数据储存的结构，其中 zipList 编码的底层数据结构是压缩列表，而 linklist 编码使用饿底层数据结构为链表。2.1 zipList 编码使用压缩列表的前提条件：一是所有字符串长度都小于 64 字节，二是元素数量小于 512，这两个条件可以在 Redis 的配置文件中修改， list-max-ziplist-value 选项和 list-max-ziplist-entries 选项。压缩列表是 Redis 为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型( sequential )数据结构。一个压缩列表可以包含任意多个节点( entry ),每个节点可以保存一个字节数组或者一个整数值，如下图。示例：这里列表总长为 0x5c(80)，初始节点与末尾节点的偏移量为 0x3c(60).当我们知道初始节点的地址 p 时，就可以计算出末尾节点的地址为 p+60。2.2 linkedlist 编码当 Redis 需要储存的对象不满足压缩列表所要求的对象时，此时使用 linkedlist 编码形式储存对象，linkedlist 底层使用的是双端链表。每个节点都会储存一个字符串对象，而每个字符串对象中都储存了一个列表元素，如图所示图1.7 linkedlist 对象结构双端列表是由多个链表节点构成，节点含有指向前方的指针 prev 以及指向后方的节点 next图8 双端链表对象结构对外提供节点值的复制，释放以及对比函数来设置类型特定的函数。使用列表对象适用于做简单的消息队列功能；最新消息排行等功能。3、哈希对象3.1 zipList 编码当每一个对象的大小都比较小并且整体的个数不大的情况下，可以使用压缩列表的方式来实现 Redis 的 hash 对象的储存如下图所示：整体组成结构和上边列表相似，只不过压缩列表相邻位置以 key-value 形式来储存对象3.2 hashtable 编码hashtable 编码方式底层使用字典的方式进行储存数据，其中 hash 表使用 dict 结构定义typedef struct dictht {   //哈希表数组   dictEntry **table;   //哈希表大小   unsigned long size;   //哈希表大小掩码，用于计算索引值   unsigned long sizemask;   //该哈希表已有节点的数量   unsigned long used;}其中 table 指向 dictEntry 数组，数组中储存的 key 以及 value 的值，但是我们存入时并不是简单的将 key 存入对应的位置。这里会通过 hash 算法将字符串转换为对应的 hash 值，然后储存的 dictentry 对应的位置上。这里，如果两个 key 的 hash 值相同时，这里会以链表的形式将两个 key 值链接起来，如下图所示：hash表节点解决hash冲突3.2 rehash 操作当 hash 表保存的键值对不断增加或者减少，为了让哈希表的负载因子维持在一个合理的范围之内，这时候就需要通过 rehash 操作完成这里，当 hash 表里的内容超过负载因子之后，会进行 rehash 操作，对 hash 表进行扩展，扩展规则：1、ht(1) 的大小是超过 h(0) 大小的第一个 2^n 次幂。就比如现在 h(0) 是 4 时,大于 4 的第一个 2^n 为 8,这时候 h(1) 的大小就会扩容成 8.2、此时将 h(0) 的数据转移到 h(1) ,对应位置重新通过 hash 值进行计算3、最后将 h(0) 释放，h(1) 设置成为 h(0), 为 h(1) 分配一个空白的 hash 表4、集合对象4.1 Intset当需要储存的底层储存对象都是整数，并且整体个数小于 512 （此值可以通过修改Redis配置文件中的 et-max-intset-entries 修改）时，此时使用的是 intset 编码，ptr 指向整数集合当中4.2 hashTable集合对象也可以使用 hashtable 的结构进行储存，与前面 hash 对象不同的是，这里只是使用了键来保存集合对象，key 值指向 null.5、有序集合对象5.1 ziplist当有序集合对象需要储存的数据所有元素长度小于 64 字节，并且元素个数小于 128 个时，使用压缩列表来储存有序集合对象，这里两个相邻的数据分别储存元素值以及对应的分值，分支小的靠近表头，分支大的靠近表尾，这样的储存形式保证了数据的有序性。5.2 skiplistskiplist 编码方式是将字典的编码方式与跳跃表的方式相结合，字典在上面已经提到了，有点是查询的负责度为 O(1) ，但是保证不了有序，这里就要引入跳跃表来实现集合的顺序性。跳跃表拥有指向头部以及尾部的指针，以及元素个数的 length 和表示最高层高的 level。下面代表一个节点的数据结构typedef struct zskiplistNode{   //每一层带有两个属性 前进指针 跨度  struct zskiplistLevel{          //前进指针    struct zskiplistNode *forward;           //跨度    unsigned int span;  }     level[];    //后退指针 BW  struct zskiplistNode *backward;    //分值  double score; //成员对象  robj *obj;}从结构来看，跳表有着前进指针以及后退指针，并且针对前进指针有着对应的跨度。节点对象包含分值，节点按照分支的大小从小向大排序。这里使用两种结构来保存数据，这里分值和成员都是共享的，指针指向统一地址，因此不会占用内存。总结Redis 提供了多种数据类型用来支持不同的业务场景，比如微博粉丝的关注列表、排行榜等。不同的数据类型适用于不同的场景。本文讲解了 Redis 的数据对象以及其底层实现的数据结构。感受一下 Redis 对于内存以及查询速度进行的设计以及优化形式。参考文献《Redis设计与实现(第二版)》