redis中常见数据结构

• redis中常见数据结构
  • SDS(简单动态字符串)
  • 链表
  • 字典
    • rehash（重新散列）
    • 扩容
    • 渐进rehash
  • 跳跃表
    • 为什么Redis使用跳跃表而不用平衡树？
  • 整数集合
    • 升级
  • 压缩列表
    • 连续更新

SDS(简单动态字符串)

SDS结构：

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

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

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

比起C字符串，SDS优点：

• 常数复杂度获取字符串长度
• 杜绝缓冲区溢出
• 减少修改字符串长度时所需的内存重分配次数
• 二进制安全
• 兼容部分C字符串函数

链表

Redis列表键的底层之一就是链表

除了列表键之外，发布与订阅、慢查询、监视器等功能也用到了链表

//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;

总结一下redis链表特性：

双端、无环、带长度记录

多态：使用 void* 指针来保存节点值， 可以通过 dup 、 free 、 match 为节点值设置类型特定函数， 可以保存不同类型的值。

字典

Redis的字典使用哈希表作为底层实现

redis用字典作为哈希键的底层实现。

redis一个哈希表节点存放一个键值对

rehash（重新散列）

随着我们不断的操作，哈希表保存的键值可能会增多或者减少，为了让哈希表的负载因子维持在合理的范围内，有时需要对哈希表进行合理的扩展或者收缩。 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

步骤：

1）为ht[1]分配合理空间

2）将ht[0]中的数据rehash到ht[1]上。

3）释放ht[0]，将ht[1]设置为ht[0]，ht[1]创建空表，为下次做准备。

负载因子=哈希表已保存节点数量 / 哈希表大小

扩容

当以下条件中的任意一个被满足时， 程序会自动开始对哈希表执行扩展操作：

服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1 ；
服务器目前正在执行BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5 ；

收缩

当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作

渐进rehash

数据量特别大时，rehash可能对服务器造成影响。为了避免，服务器不是一次性rehash的，而是分多次。渐进式rehash采用的是一种分而治之的方式，将rehash的操作分摊在每一个的访问中，避免集中式rehash而带来的庞大计算量。

需要注意：rehash过程中，每一次删除、查找、更新是在两个表进行的。而新增加的键值对会一律保存在ht[1]里，不对ht[0]进行操作。

跳跃表

​ 跳跃表是有序集合键的底层实现之一。如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

​ Redis第1层链表不是一个单向链表，而是一个双向链表。这是为了方便以倒序方式获取一个范围内的元素。

​ Redis层数最高为32

​ 在同一个跳跃表，多个节点可以包含相同的分数，但每个成员对象必须是唯一的

​ 跳跃表节点按照分值大小进行排序，当分值相同时，节点按照成员大小进行排序

为什么Redis使用跳跃表而不用平衡树？

• 跳表区间查找效率更高，在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。

• 平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。

• 从内存占用上来说，skiplist比平衡树更灵活一些。skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。

• 从算法实现难度上来比较，skiplist比平衡树要简单得多。

  
  

一句话总结为什么Redis要用跳表来实现zset：内存使用更少，简单易维护，性能不比搜索树差

整数集合

​ 整数集合是集合键的底层实现之一。当一个集合只包含整数值元素，并且这个元素的数量不多时，Redis就会使用整数聚合作为集合键的底层实现。

 每个intset.h/intset结构表示一个整数集合：
    typedef struct intset {
      //编码方式
      uint32_t encoding
      //集合包含的元素数量
      uint_32_t length
      //保存元素的数组
      int8_t contents[];

     }intset;

​ 整数集合的每个元素都是comtents数组中的一个数组项，各个项在数组中按值的大小从小到大有序排列，并且数组中不包含任何重复项

升级

​ 每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现在所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。

升级整数集合并添加新元素共分为三步进行:
 1）根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
 2）将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素防止到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
 3）将新元素添加到底层数组里面。

升级的好处：

​ 整数几个的升级策略有两个好处，一个市提升整数集合的灵活性，另一个是尽可能地节约内存。

• 因为整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随时地将int16_t、int32_t或者int64_t类型的整数添加到集合中，而不必担心出现类型错误，这种做法非常灵活。

• 整数集合可以确保升级操作只会在有需要的时候进行，这可以尽量节省内存。

  redis不能降级

压缩列表

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

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

节点结构图：

• 节点的 previous_entry_length属性以字节为单位,记录了压缩列表中前一个节点的长度。 previous_entry_length属性的长度可以是1字节或者5字节。

  如果前一节点的长度小于254字节,那么 previous_entry_length属性的长度为1字节，前一节点的长度就保存在这一个字节里面。

  如果前一节点的长度大于等于254字节,那么 previous_entry_length属性的长度为5字节:其中属性的第一字节会被设置为0xFE(十进制值254),而之后的四个字节则用于保存前一节点的长度.

连续更新

详情看redis-设计与实现57页

　　由于压缩列表的'previous_entry_length'属性可能是1字节或5字节，若在一个压缩列表中，有多个连续的、长度介于250字节到253字节之间的节点，则添加新节点或删除节点都有可能会引发多个节点的连续多次空间扩展，这种现象称之为“连锁更新”。
因为连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作， 而每次空间重分配的最坏复杂度为O(N)， 所以连锁更新的最坏复杂度为O(N^2)。但“连锁更新”发生的概率是很低的，所以不必担心其会影响压缩列表的性能。

重点：

• 节点的encoding属性记录了节点的content属性所保存数据的类型以及长度

• 节点的content属性负责保存节点的值,节点值可以是一个字节数组或者整数,值的类型和长度由节点的encoding属性决定。

• 压缩列表是Redis为节约内存自己设计的一种顺序型数据结构。

• 压缩列表被用作列表键和哈希键的底层实现之一。

• 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值。

• 添加新节点到压缩列表,或者从压缩列表中删除节点,可能会引发连锁更新操作,但这种操作出现的几率并不高。

参考 《Redis设计与实现》