[大数据]Redis(一). 内部数据结构

Redis(一). 内部数据结构

不同于其他key-value 数据库，Redis支持很多数据结构，并且在这些数据结构上面提供许多强大的API,这些API 是由Redis内部高效数据结构和对应的函数支持；简而言之就是我们使用的Redis命令是由Redis内部的数据结构和对应的函数支持；

1.简单动态字符串Sds

1.1 应用

Sds：Simple Dynamic String，Redis底层使用的字符串，并不是C字符串默认的 char*；

char* 类型的功能单一，大多数情况下都能满足要求，但是，它并不能高效地支持长度计算和追加（append）这两种操作：长度计算O(n)，每次追加append都是需要重新分配内存

1.2 实现

sds 的简单实现就是

typedef char *sds;
struct sdshdr {
// buf 已占用长度
int len;
// buf 剩余可用长度
int free;
// 实际保存字符串数据的地方
char buf[];
};

正常表示字符串nihao的对象就是

struct sdshdr {
  len = 5;
  free = 0;
  buf = "nihao\0";
};

O(1)计算长度， free 字段用于追加的优化，

示例：

set testkey nihao

struct sdshdr {
  len = 5;
  free = 0;
  buf = "nihao\0";
};

append testkey nihaonihao

struct sdshdr {
  len = 15;
  free = 15;
  buf = "nihaonihaonihao\0";
};

执行 APPEND 之后，Redis 为 buf 创建了多于所需空间一倍的大小

append testkey sssss

struct sdshdr {
  len = 20;
  free = 10;
  buf = "nihaonihaonihao\0";
};

追加内容的长度不超过 free 属性的值，那么就不需要对 buf 进行内存重分配

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
.......

    /* Return ASAP if there is enough space left. */追加内容的长度不超过 free 属性的值，那么就不需要对 buf 进行内存重分配
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    # 计算新字符串的总长度
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    # 如果新字符串的总长度小于 SDS_MAX_PREALLOC
    # 那么为字符串分配 2 倍于所需长度的空间
    # 否则就分配所需长度加上 SDS_MAX_PREALLOC 数量的空间
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    }
......
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    # 分配内存
    sdssetalloc(s, usable);
    return s;
}

SDS_MAX_PREALLOC 最大为1024*1024 = 1M , 如果重新分配大小就扩大一倍，如果本次扩大的字符串是大于1M 就多分配1M,free = 1M，

不会浪费内存，只有使用append 命令的字符串才会有这样的策略；

1.3 总结

总结：Redis 使用Sds ,不是C的char* ； 优点是Sds 有较高效的长度计算，高效追加，二进制安全，缺点是可能会浪费一些内存，而且这些内存不会主动释放；

2.双端链表

常用的数据结构，类似数组，但是比数组的函数更丰富

2.1 应用

RPUSH 、LPOP 或 LLEN 等命令时，程序在底层操作就是双端链表；客户端使用的Lists 除此之外
? 事务模块使用双端链表来按顺序保存输入的命令；
? 服务器模块使用双端链表来保存多个客户端；
? 订阅/发送模块使用双端链表来保存订阅模式的多个客户端；
? 事件模块使用双端链表来保存时间事件（time event）；

2.2 实现

Redis 列表使用两种数据结构作为底层实现：

1. 双端链表

2. 压缩列表

主要是有两个数据结构构成 ListNode 和 List

节点ListNode

typedef struct listNode {
// 前驱节点
struct listNode *prev;
// 后继节点
struct listNode *next;
// 值 void * 表示节点保存的数据对数据类型不做限制
void *value;
} listNode;

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;

2.3 总结

总结：

Redis 自己实现了链表

链表的两个数据结构的定义上，可以得到的性能特征

• 双向遍历
• 插入头部和尾部都是O(1)
• 计算长度的复杂度O(1)

3.字典

字典 又名映射map ，由一集键值对（key-value pairs）组成

3.1 应用

1. 实现数据库键空间（key space）； 比如

   ## 清除键空间 所有键值对
   FLUSHDB 
   ## 获取键空间 所有键值对
   DBSIZE
   ## 设置一个字符串键到键空间
   set key value
   

2. 用作 Hash 类型键的其中一种底层实现

   实现是字典+ 压缩列表 (类似于Java的HashMap)

127.0.0.1:6379[2]> hset fam lp lhh
(integer) 1
127.0.0.1:6379[2]> hset fam lg sff
(integer) 1
127.0.0.1:6379[2]> hgetall fam
1) "lp"
2) "lhh"
3) "lg"
4) "sff"
127.0.0.1:6379[2]>

3.2 实现

实现方法有多种

• 最简单的就是链表和数组，限制条件就是元素个数不多；
• 兼顾高效和简单性，可以使用哈希表
• 追求稳定的性能可以使用平衡树

Redis 选择了高效且实现简单的哈希表作为字典的底层实现

字典实现

/*
* 字典
** 每个字典使用两个哈希表，用于实现渐进式 rehash
*/
typedef struct dict {
// 特定于类型的处理函数
dictType *type;
// 类型处理函数的私有数据
void *privdata;
// 哈希表（2 个） ，0 号哈希表（ht[0]）是字典主要使用的哈希表，而 1 号哈希表（ht[1]）则只有在程序对 0 号哈希表进行 rehash 时才使用
dictht ht[2];
// 记录 rehash 进度的标志，值为-1 表示 rehash 未进行
int rehashidx;
// 当前正在运作的安全迭代器数量
int iterators;
} dict

字典所使用的哈希表实现 dictht

/*
* 哈希表
*/
typedef struct dictht {
// 哈希表节点指针数组（俗称桶，bucket）数组的每个元素都是一个指向 dictEntry 结构的指针 ，dictEntry 保存着一个键值对，以及一个指向另一个 dictEntry 结构的指针
dictEntry **table;
// 指针数组的大小
unsigned long size;
// 指针数组的长度掩码，用于计算索引值
unsigned long sizemask;
// 哈希表现有的节点数量
unsigned long used;
} dictht;

/*
* 哈希表节点
*/
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 链往后继节点
struct dictEntry *next;
} dictEntry

结构图

dictht 使用链地址法来处理键碰撞：当多个不同的键拥有相同的哈希值时，哈希表用一个链表将这些键连接起来。(HashMap 其中的一个bucket 储存entry小于8时也是用链表保存的，可以参考理解)

哈希算法

MurmurHash2 32 bit 算法 主要使用这个

3.3 字典的各个步骤

3.3.1 创建

字典的数据结构中ht[2] 中 每个元素的table 还都没有为 table 属性分配任何空间；ht[0] 分配空间是第一次添加键值对，ht[1] 是指向rehash 的时候

3.3.2 添加键值对

添加前 假设是空白字典如 3.3.1 中所示

• ht[0] 分配空间是第一次添加键值对

• 发生了键碰撞，那么程序需要处理碰撞；

• 满足了 rehash 条件，那么需要启动相应的 rehash 程序

  哈希表的性能依赖于它的大小：size（总个数）属性节点的数量：used (bucket 在使用的个数)属性之间的比率 1：1 最好 直接hash 就得到了

比例变大了之后hash 就变成了链表 ，查询优势下降；定位到bucket 后还需要遍历一遍链表中的键值对

所以每次在添加键值对之前，先判断是否满足rehash 条件 ， ratio = used / size 满足以下任何一个条件的话，rehash 过程就会被激活(注意 激活不是执行)

• 自然 rehash ：ratio >= 1 ，且变量 dict_can_resize（系统后台线程执行持久化任务的时候 AOF BGSAVE 等，会暂时为false，避免内存碰撞touch,完成或变成TRUE） 为真。
• 强制rehash ： ratio大于变量dict_force_resize_ratio （目前版本中，dict_force_resize_ratio 的值为 5 ）。

3.3.3 Rehash 执行过程

字典的 rehash 操作实际上就是执行以下任务，主要是 增大了哈希表的大小：

1. 创建一个比 ht[0]->table 更大的 ht[1]->table (大小至少为 ht[0]->used 的两倍) ；
2. 将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ；
3. 将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0] ；

3.3.4 渐进式 rehash

注意：对于触发了rehash 的

rehash 是分多此，渐进式的完成的，渐进式 rehash 主要由 _dictRehashStep 和 dictRehashMilliseconds 两个函数进行
? _dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash ，每次执行一次添加、查找、删除操作；

? dictRehashMilliseconds 则由 Redis 服务器常规任务程序（server cron job）执行，用于对数据库字典进行主动 rehash ，可以在指定的毫秒数内，对字典进行 rehash；

注：在rehash过程中，两个哈希表都在用，查询，删除等都是在两个哈希表中进行；新增在ht[1] 中

3.3.5 字典的收缩

rehash 中不仅可以扩容，也可以收缩；它执行以下步骤：

1. 创建一个比 ht[0]->table 小的 ht[1]->table ；
2. 将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ；
3. 将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0] ；

当字典的填充率低于 10% 时，程序就可以对这个字典进行收缩操作了。字典收缩和字典扩展的一个区别是：
? 字典的扩展操作是自动触发的（不管是自动扩展还是强制扩展）删除的时候调用函数判断；
? 而字典的收缩操作则是由程序手动执行

3.4 总结

• Redis 中的数据库和哈希键都基于字典来实现
• 只有在 rehash 进行时，才会同时使用 0 号和 1 号哈希表。
• 哈希表使用链地址法来解决键冲突的问题
• 哈希表的 rehash 是分多次、渐进式地进行的
• rehash 中不仅可以扩容，也可以收缩

4. 跳跃表

? 表头（head）：负责维护跳跃表的节点指针。
? 跳跃表节点：保存着元素值，以及多个层。
? 层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
? 表尾：全部由 NULL 组成，表示跳跃表的末尾。

4.1 实现

在查找的时候，遵循以下步骤：(最该层开始 ，左边大 右边小，不断下层，不断缩小区间，最后定位)

1. 从最高层开始寻找
2. 找到该层大于要寻找的key的第一个元素的前一个元素
3. 向下移到下一层
4. 每一层最左边为无穷小，最右边为无穷大

Redis 基于 William Pugh 论文中描述的跳跃表进行了以下修改，时间复杂度O(lg n)

1. 允许重复的 score 值：多个不同的 member 的 score 值可以相同。
2. 进行对比操作时，不仅要检查 score 值，还要检查 member ：当 score 值可以重复时，单靠 score 值无法判断一个元素的身份，所以需要连 member 域都一并检查才行。
3. 每个节点都带有一个高度为 1 层的后退指针，用于从表尾方向向表头方向迭代：当执行ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时，就会用到

这个属性

typedef struct zskiplist {
// 头节点，尾节点
struct zskiplistNode *header, *tail;
// 节点数量
unsigned long length;
// 目前表内节点的最大层数
int level;
} zskiplist;

zskiplistNode

typedef struct zskiplistNode {
// member 对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
    struct zskiplistNode *forward;
// 这个层跨越的节点数量
unsigned int span;
} level[];
} zskiplistNode;

4.2 应用

唯一作用，就是实现有序集数据类型 sorted set 有序集的 score 值和 member 域的指针作为元素;score 值为索引，对有序集元素进行排序

4.3 总结

• 随机化数据结构
• Redis 的唯一作用就是作为有序集类型
• Redis 基于 William Pugh 论文中描述的跳跃表进行了修改