xingliuhua
文章 标签 分类
xingliuhua

目录

Redis学习-redis底层数据结构

xingliuhua 收录于 笔记
   约 4310 字   预计阅读 9 分钟 

动态字符串

redis是C语言编写，但是字符串并不是简单地的C字符串。它是SDS（simple dynamic string）。

/*  
 * 保存字符串对象的结构  
 */  
struct sdshdr {  
      
    // buf 中已占用空间的长度  
    int len;  
  
    // buf 中剩余可用空间的长度  
    int free;  
  
    // 数据空间  
    char buf[];  
};

pic1.png 1、len 变量，用于记录buf 中已经使用的空间长度（这里指出Redis 的长度为5）

2、free 变量，用于记录buf 中还空余的空间（初次分配空间，一般没有空余，在对字符串修改的时候，会有剩余空间出现）

3、buf 字符数组，用于记录我们的字符串（记录Redis）

SDS 与 C 字符串的区别

获取字符串长度（SDS O（1）/C 字符串 O(n)）

传统的C 字符串 使用长度为N+1 的字符串数组来表示长度为N 的字符串，所以为了获取一个长度为C字符串的长度，必须遍历整个字符串。

和C 字符串不同，SDS 的数据结构中，有专门用于保存字符串长度的变量，我们可以通过获取len 属性的值，直接知道字符串长度。

杜绝缓冲区溢出

C 字符串 不记录字符串长度，除了获取的时候复杂度高以外，还容易导致缓冲区溢出。

假设程序中有两个在内存中紧邻着的 字符串 s1 和 s2，其中s1 保存了字符串“redis”，二s2 则保存了字符串“MongoDb”

如果我们现在将s1 的内容修改为redis cluster，但是又忘了重新为s1 分配足够的空间，这时候就会出现以下问题： 原本s2 中的内容已经被S1的内容给占领了，s2 现在为 cluster，而不是“Mongodb”。

Redis 中SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：

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

减少修改字符串时带来的内存重分配次数　　　

预分配内存，提前申请空间。 　　 C语言字符串在进行字符串的扩充和收缩的时候，都会面临着内存空间的重新分配问题。

  1. 字符串拼接会产生字符串的内存空间的扩充，在拼接的过程中，原来的字符串的大小很可能小于拼接后的字符串的大小，那么这样的话，就会导致一旦忘记申请分配空间，就会导致内存的溢出。

  2. 字符串在进行收缩的时候，内存空间会相应的收缩，而如果在进行字符串的切割的时候，没有对内存的空间进行一个重新分配，那么这部分多出来的空间就成为了内存泄露。

举个例子：我们需要对下面的SDS进行拓展，则需要进行空间的拓展，这时候redis 会将SDS的长度修改为13字节，并且将未使用空间同样修改为13字节 。这样下次扩展字符串的时候可能就不需要申请了，因为上一次多申请了13个。

惰性空间释放

我们在观察SDS 的结构的时候可以看到里面的free 属性，是用于记录空余空间的。我们除了在拓展字符串的时候会使用到free 来进行记录空余空间以外，在对字符串进行收缩的时候，我们也可以使用free 属性来进行记录剩余空间，这样做的好处就是避免下次对字符串进行再次修改的时候，需要对字符串的空间进行拓展。

然而，我们并不是说不能释放SDS 中空余的空间，SDS 提供了相应的API，让我们可以在有需要的时候，自行释放SDS 的空余空间。

通过惰性空间释放，SDS 避免了缩短字符串时所需的内存重分配操作，并未将来可能有的增长操作提供了优化

二进制安全

C 字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存想图片，音频，视频，压缩文件这样的二进制数据。

但是在Redis中，不是靠空字符来判断字符串的结束的，而是通过len这个属性。那么，即便是中间出现了空字符对于SDS来说，读取该字符仍然是可以的。

总结

SDS相比C字符串好处多多。

  • 获取字符串长度不用再遍历。
  • 字符串变长会校验空间，不会溢出。
  • 扩容的时候会多申请空间，减少内存分配次数。
  • 可以保持二进制数据。图片、视频、空格都不怕了。

链表

redis的list是一个双向链表。

链表的特性

  • 双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是O（N）

  • 无环：表头节点的 prev 指针和表尾节点的next 都指向NULL，对立案表的访问时以NULL为截止

  • 表头和表尾：因为链表带有head指针和tail 指针，程序获取链表头结点和尾节点的时间复杂度为O(1)

  • 长度计数器：链表中存有记录链表长度的属性 len

  • 多态：链表节点使用 void* 指针来保存节点值，并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。

字典

在字典中，一个键（key）可以和一个值（value）进行关联，字典中的每个键都是独一无二的。在C语言中，并没有这种数据结构，但是Redis 中构建了自己的字典实现。

SET msg “hello world”

创建这样的键值对（“msg”，“hello world”）在数据库中就是以字典的形式存储.

如果出现hash 值相同的情况怎么办？Redis 采用了链地址法： pic2.png

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

Rehash

rehash就是扩容和缩容。

加载因子（load factor） = ht[0].used / ht[0].size 也就是所有的元素个数 / 桶的个数

扩容：

  • 没有执行BGSAVE和BGREWRITEAOF指令的情况下，哈希表的加载因子大于等于1。
  • 正在执行BGSAVE和BGREWRITEAOF指令的情况下，哈希表的加载因子大于等于5。

收缩:

  • 加载因子小于0.1时，程序自动开始对哈希表进行收缩操作。

扩容和收缩的数量

扩容：

  • 第一个大于等于ht[0].used * 2的2^n(2的n次方幂)。

收缩：

  • 第一个大于等于ht[0].used的2^n(2的n次方幂)。

hash的扩容和缩容都不是一下就完成的。而是·渐进式的，这样可以避免暂时的卡住。 甚至在进行期间，每次对哈希表的增删改查操作，除了正常执行之外，还会顺带将ht[0]哈希表相关键值对rehash到ht[1]。

ziplist 压缩列表。

redis的列表键和哈希键的底层实现之一。此数据结构是为了节约内存而开发的。和各种语言的数组类似，它是由连续的内存块组成的，这样一来，由于内存是连续的，就减少了很多内存碎片和指针的内存占用，进而节约了内存。 pic3.png 然后文中的entry的结构是这样的： pic4.png

元素的遍历 先找到列表尾部元素, 然后再根据ziplist节点元素中的previous_entry_length属性，来逐个遍历。

整数集合

整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，可以保存类型为int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素 整数集合是集合（Set）的底层实现之一，如果一个集合只包含整数值元素，且元素数量不多时，会使用整数集合作为底层实现

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

contents数组：整数集合的每个元素在数组中按值的大小从小到大排序，且不包含重复项 length记录整数集合的元素数量，即contents数组长度 encoding决定contents数组的真正类型，如INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64 pic11.png

跳跃表

个人理解有点像mysql索引的B+树，为的就是zset快速查找。

一个普通的单链表查询一个元素的时间复杂度为O(N)，即便该单链表是有序的。使用跳跃表（SkipList）是来解决查找问题的，它是一种有序的数据结构，不属于平衡树结构，也不属于Hash结构，它通过在每个节点维持多个指向其他节点的指针，而达到快速访问节点的目的。

跳跃表是有序集合（Sorted Set）的底层实现之一，如果有序集合包含的元素比较多，或者元素的成员是比较长的字符串时，Redis会使用跳跃表做有序集合的底层实现

跳跃表其实可以把它理解为多层的链表，它有如下的性质

多层的结构组成，每层是一个有序的链表 最底层（level 1）的链表包含所有的元素 跳跃表的查找次数近似于层数，时间复杂度为O(logn)，插入、删除也为 O(logn) 跳跃表是一种随机化的数据结构(通过抛硬币来决定层数)

那么如何来理解跳跃表呢，我们从最底层的包含所有元素的链表开始，给定如下的链表 pic12.png 然后我们每隔一个元素，把它放到上一层的链表当中，这里我把它叫做上浮（注意，科学的办法是抛硬币的方式，来决定元素是否上浮到上一层链表，我这里先简单每隔一个元素上浮到上一层链表，便于理解），操作完成之后的结构如下 pic13.png 查找元素的方法是这样，从上层开始查找，大数向右找到头，小数向左找到头，例如我要查找17，查询的顺序是：13 -> 46 -> 22 -> 17；如果是查找35，则是 13 -> 46 -> 22 -> 46 -> 35；如果是54，则是 13 -> 46 -> 54 pic14.png

跳跃表节点的删除和添加都是不可预测的，很难保证跳表的索引是始终均匀的，抛硬币的方式可以让大体上是趋于均匀的

redis五种数据结构的实现

redis对象 redis中并没有直接使用以上所说的各种数据结构来实现键值数据库，而是基于一种对象，对象底层再间接的引用上文所说的具体的数据结构。

根据对象的类型可以判断一个对象是否可以执行给定的命令，也可针对不同的使用场景，对象设置有多种不同的数据结构实现，从而优化对象在不同场景下的使用效率

pic5.png

字符串

pic6.png 其中：embstr和raw都是由SDS动态字符串构成的。唯一区别是：raw是分配内存的时候，redisobject和 sds 各分配一块内存，而embstr是redisobject和raw在一块儿内存中。

列表

pic7.png

hash

pic8.png

set

pic9.png

zset

第一种使用ziplist。 前提：保存元素数量小于128，并且每个元素长度小于64字节 （这两个参数可以通过zset-max-ziplist-entries 选项和 zset-max-ziplist-value 进行修改）

ziplist原理： 压缩列表（ziplist）是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。 pic10.png

使用字典和跳跃表 使用跳表的时候并不是完全是跳表，是hash表和跳表的组合。

typedef struct zset{
     //跳跃表
     zskiplist *zsl;
     //字典
     dict *dice;
} zset;

字典的键保存元素的值，字典的值则保存元素的分值；跳跃表节点的 object 属性保存元素的值，跳跃表节点的 score 属性保存元素的分值。

为什么不直接用跳跃表？ 假如我们单独使用 字典，虽然能以 O(1) 的时间复杂度查找成员的分值，但是因为字典是以无序的方式来保存集合元素，所以每次进行范围操作的时候都要进行排序；假如我们单独使用跳跃表来实现，虽然能执行范围操作，但是查找操作有 O(1)的复杂度变为了O(logN)。因此Redis使用了两种数据结构来共同实现有序集合。

更新于 2017-04-16
 redis
返回 | 主页