Redis底层数据结构（详细篇）

一、常见数据结构的底层数据结构

1、动态字符串SDS（Simple Dynamic String）

组成

字符数组存储数据，头部存储字符数量，预分配内存，SDS类型（5个字节已被弃用）。
问题来了：为什么要这样设计呢？为什么不用c语言的字符串呢？
回答

• 1、保证二进制安全 2、无需遍历数组获取长度
  其实c语言没有字符串，是靠字符数组实现的，并且以“ \0 ”作为结束标志，但是如果数据中间存在结束字符会导致读取数据不全的问题，所以引入len变量来保存字符数量，以len作为标准去读取数据，同时无需遍历数组获取长度（len）。
• 3、动态扩容
  
  预分配有啥好处嘛？
  在操作系统中，分配内存需要内核态和用户态的转换，该过程十分损耗性能，所以当大于1m，会分配多1m，防止多次分配带来的性能损耗。

2、IntSet

组成

本质是一个动态有序的整数数组。

encoding表示编码方式，数组中的数据就按照该编码方式存储。

如何保证动态

问题来了：如果数据超过了编码的范围怎么办呢？


回答： 我们通过编码升级，倒叙依次拷贝（防止正序覆盖当前数据），再添加新元素，最后头信息：length+1并且编码修改为对应的编码类型。

如何确保有序呢? 底层如何查找的呢?

本质就是二分查找，找到则不插入返回错误，没找到则插入有序的适当位置。

3、Dict(dictionary)

3.1组成

和java中jdk1.7版本的HashMap底层数据结构十分相似，由三部分组成：hash表（数组），哈希节点（entry）、字典（Dict）

每个Dict有两个hashTable一个用于存储当前数据，一个用于rehash（后续详细介绍）。
每个hashTable（dictHT）存储entry的指针以及hash表大小和entry个数，其中有一个sizemask用于进行hash求索引比如n&sizemask等价于n%size（sizemask+1），&运算速率更加快。
当发生hash碰撞的时候就是key运算后索引相同则使用单向链表，进行前插法添加新元素。

3.2 扩容

3.3 收缩

hashTable默认size为4，怎么收缩都不能低于4。
收缩后的size为大于等于实际entry个数的最小2的n次方（5->8）

3.4 rehash

因为一次新增的数据太多，导致rehash一次性更新到新的hashTable时长太长而影响其他业务性能，所以每次执行增删改查的时候才会去更新一个索引的数据，直到结束为止。

4、ZipList

为什么不使用相同内存存储entry呢？
回答：之所以叫压缩列表，就是因为去除了链表中的指针（一个指针8字节），并且每个entry由实际内容决定，节省了大批内存空间。

在遍历的时候，无需使用链表的指针来获取前一个元素和下一个元素，而是根据previous_enrty_length计算前一个entry的起始地址，通过自身大小计算下一节点地址。

连锁更新问题

如果这个时候插入一个节点并且长度大于254，将会导致pre_enrty_length属性由1字节变成5字节导致后面的该属性全部连锁更新为5字节。
(该情况发生概率很低)

总结特性

• 可以看成一种连续空间的"双向链表" ，首尾操作简单
• 节点之间不通过指针连接，记录上一节点和本节点长度寻址，节省内存
• 如果节点数量过多，导致链表过长，需要逐个遍历，查询效率不高
• 增删大数据时可能发生连续更新问题

5、 QuickList

上面说到ZipList的致命缺点：空间连续，如果数据过多，申请效率会变低，查询效率也下降，如何解决呢？

• 可以通过限制ZipList的长度和entry大小
• 对于大量的数据进行分片，多个ZipList存储
• 多个ZipList进行联系，引入主角：QuickList

5.1 组成

QuickList本质是一个双端链表，但是每个节点指向ZipList，使得ZipList们联系起来。

config get list-max-ziplist-size 

config get list-compress-depth 

5.2 底层源码（结合组成示意图理解）

5.3 特点总结

• 是一个节点为ZipList的双端链表
• 节点采用ZipList，解决了传统链表的内存占用问题（指针）
• 控制了ZipList的大小，解决申请效率的问题
• 中间节点可以进一步压缩，进一步节省内存空间。

6、SkipList

上面聊了这么多链表，其实都没看到怎么去解决快速查找中间节点的问题，这里引入的SkipList就优化了链表中元素查找效率。

它和其他传统链表不同：1、元素按升序排列（也是方便后续的查找）

根据score值进行排序

2、节点可能包含多个指针，跨度不一样（加速查找效率，跳表的来源）

上源码：是个双向链表，每个节点值是SDS，整个排序考score，然后就是前后指针，由于增序，所以多级指针体现在forword（向后），跨度不一所以使用数组存储。

示意图

特点总结：

• 双向链表，每个节点都含score和ele值
• 节点按score排序，score值相同则按 ele字典排序（字符串）
• 每个节点可包含多级指针，1-32之间
• 指针层级越高，跨度越大
• 增删修改效率和红黑树 基本一致，实现却简单

最后：redis的对象（redisObject）

逐层分析

1、type

就是我们熟悉的5中常见类型string 、hash、list、set和zset（4个bit）

2、encoding

就是五种类型在数据量不同的情况下不同的编码方式（4个bit）

3、lru（最后一次使用时间）

便于统计使用情况，用于统计空闲时间。（24bit）

4、refcount

引用计数器，便于淘汰和回收。

5、ptr（指针）

指向真正的数据。

其实这里就可以发现： 如果我们一直使用string类型去存储大量数据，会浪费很多对象的头内存，我们可以将其使用集合去存储进行内存的优化。

二、常见数据结构

1、String

使用的编码格式有三种 RAW EMBSTR INT

• 基本的编码方式是raw，基于SDS（动态字符串），存储上限为512mb。
• 如果存储的SDS长度小于等于44字节，则采用EMBSTR 编码，此时redisobj head和SDS是一段连续空间。申请内存时只需要调用一次内存分配函数（设计到内核态和用户态的切换），效率更高。
• 如果存储的字符串是整数，并且大小在LONG_max范围内，则采用INT编码，直接使用pre指针位置（刚好8字节），不需要SDS。
  

2、LIST

• 在3.2版本之前，Redis采用ZipList和Linklist来实现List，当元素小于512并且元素大小小于64字节时采用ZipList编码，超过采用Linklist。
• 3.2之后，统一使用QuickList来实现。
  具体QuickList请看上述中的详解。

3、Set（无序唯一）

• 为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null。
• 当存储的数据都是整数的时候，并且元素数量不超过set-max-intset-entries时，set采用IntSet编码，以节省空间。
  如图 当元素为{5，10，20}这时候 sadd s1 m1 会将编码方式由intset转为dict。

4、ZSet（SortedSet）

其中的每一个元素都需要指定一个score值和member值：

• 根据score值排序
• member值唯一（set都是这样的）
• 根据member查询score
  so：底层数据结构必须满足 键值存储，键唯一，可排序
• dict 满足键值存储和根据key找value
• skipList 满足可排序，可以存储score和member
  其实底层就是综合了他们的优点来满足需求，二者都要，一共两份数据（空间换时间）。
  示意图：
  
  key存ele ，value存score实现ele找score ，但是根据score排序。

大家可以看到当元素少的时候其实性价比不高，内存消耗比较大，所以：
当元素不多的时候，底层会采用zipList实现存储。
什么叫不多？界限是啥？ 同时满足以下两个条件（一般都是个数，内存大小）

• 元素小于128（默认）可以调节。
• 每个元素小于64字节

学了zipList知道其实他本身不具备 键值存储，键唯一，可排序三个特点如何实现呢？

• zipList是连续空间，因此score和ele紧挨着一起的两个enrty，ele在前。
• score越小越接近队首，按score升序排列。
  

5、Hash

其实学了zset，发现二者很相似，只不过hash不需要保证有序，所以立马知道，其底层就是dict，但是当数据量不多则使用zipList。
hash默认是使用zipList编码，节省空间，相邻两个entry存的就是key 和value。
当数据量大时则转为HT（dict）编码，触发条件有两个：

• 元素数量超过512（默认，可调节）
• 大小超过64字节（默认，可调节）
  
  以上则是Redis底层主要的数据结构。