Redis原理篇——数据结构

动态字符串SDS

一.动态字符串SDS
我们都知道Redis中保存的Key是字符串，value往往是字符串或者字符串集合。可见字符串时Redis中最常用的一种数据结构。
不过Redis没有直接使用c语言中的字符串，因为c语言字符串存在很多问题：

• 获取字符串长度需要通过运算
• 非二进制安全
• 不可修改
  Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String）,简称SDS。
  
  例如：一个包含字符串“name”的sds结构如下：
  
  可以看到sds的这种结构的优势，因为已经指定了长度，所以就不需要进行运算去计算字符串的长度，直接通过len 就可以知道字符串的长度，虽然上图中也有字符串结束标志，但是并不是通过它来计算字符串的长度。

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的SDS:

加入我们要给SDS追加一段字符串“,Amy”,这里首先会申请新内存空间：

• 如果新字符串小于1M,则新空间为扩展后字符串长度的两倍+1；
• 如果新字符串大于1M,则新空间为扩展后字符串长度+1M+1;
  我们将这种内存分配的方式称为内存预分配
  
  SDS的优点：
• 获取字符串长度的时间复杂度为O(1)
• 支持动态扩容
• 减少内存分配次数
• 二进制安全

IntSet

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变，有序等特征。
结构如下：

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

上图中，数组中的每个数字都在int_16的范围内，因此采用的编码方式为INSERT_ENC_INIT16，每部分占用的字符大小为：

• encoding:4字节
• length:4字节
• contents:2字节*3=6字节
  
  底层源码
  
  intset可以看做是特殊的整数数组，具备一些特点：
• Redis会确保intset的元素唯一，有序
• 具备类型升级机制，可以节省内存空间
• 底层采用二分查找方式来查询

Dict

我们知道Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值得映射关系正式通过Dict来实现的。Dict由三部分组成，分别是：哈希表、哈希节点、字典

当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h）,然后利用h&sizemark来计算元素应该存储到数组中的哪个索引位置。假设k1的哈希值h=1,则1&3=1,因此k1=v1要存储到数组角标1位置。

dict结构如下：


Dict的扩容
Dict中的HashTable就是数组结合单项链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。
Dict在每次新增键值对时都会检查负载因子(LoadFactor = used/size),满足以下两种情况会触发哈希扩容：

• 哈希表的 LoadFactor>=1.并且服务器没有执行bgsive或者bgrewriteaof等后台进程；
• 哈希表的LoadFactor>5；
  
  Dict收缩
  Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当loadfactor<0.1时，会做哈希表收缩：
  
  Dict的rehash
  Dict的rehash并不是一次性完成的。试想一下，如果Dict中包含数百万的entry,要在一次rehash完成，极有可能导致主线程阻塞。因此Dict的rehash是分多次、渐进式的完成，因此称为渐进式rehash。流程如下：
  ①计算新的hash表的size,值取决于当前要做的是扩容还是收缩：
     - 如果是扩容，则新的size为第一个大于等于dict.ht[0].used+1的2的n次方
     - 如果是收缩，则新的size为第一个大于等于dict.ht[0].used的2的n次方（不得小于4）
  ②按照新的size申请内存空间，创建dictht,并赋值给dict.ht[1]
  ③设置dict.rehashidx = 0,表示开始rehash
  ④每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]并且将rehashidx++。直到dict.ht[0]所有的数据都rehash到dict.ht[1]中
  ⑤将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]内存
  ⑥将rehashidx赋值为-1，代表rehash结束
  ⑦在rehash过程中，新增操作，则直接写入ht[1],查询、修改、删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保dict.ht[0]的数据只减不增，随着rehash最终为空。

压缩列表（ZipList）

ZipList是一种特殊的“双端链表”，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作，并且该操作的时间复杂度为O(1)。

ZipListEntry
ZipList中的entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占16字节，浪费内存。而是采用了下面的结构：

Encoding编码
ZipListEntry中的encoding编码分为字符串和整数两种：

• 字符串：如果encoding是以“00”，“01”，“10”开头，则证明content是字符串
  
  例如，我们要保存字符串：“ab”和"bc"
  
• 整数：如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节
  
  例如，一个ZipList中包含两个整数数值：“2”和“5”
  
  ZipList的连锁更新问题
  ZipList的每个entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节：
• 如果前一个节点长度小于254字节，则采用1个字节来包存这个长度
• 如果前一个节点长度大于等于254字节，则采用5个字节来保存这个长度值，第一个字节为oxfe,后四个字节才是真是长度数据

现在，假设我们有N个连续的、长度为250-253字节之间的entry,因此entry的previous_entry_length属性用1个字节即可表示，如图所示：

ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新。新增、删除都可能导致连锁更新的发生。

QuickList

QuickList结构图：

QuickList的特点：

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

跳表（SkipList）

SkipList首先是链表，但与传统链表相比有几点差异：

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同
  
  
  
  SkipList的特点：
• 跳表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject,也叫做Redis对象


Redis会根据存储的数据类型不同，选择不同的编码方式，每种数据类型使用的编码方式如下：