Redis原理（上）

Redis原理

1-Redis数据结构

1-1.动态字符串(Simple Dynamic String)

Redis中保存的Key是字符串，value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。

不过Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：

0. 非二进制安全
1. 不可修改
2. 获取字符串长度的需要通过运算

Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String） ，简称SDS

arduino

复制代码

set name bobochang

如上命令 Redis将在底层创建两个SDS，其中一个是包含“name”的SDS，另一个是包含“bobochang”的SDS。

Redis是C语言实现的，其中SDS是一个结构体，源码如下：

例如，一个包含字符串“name”的sds结构如下：

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

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

如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；

如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。

动态字符串 SDS 优点：

• 获取字符串长度的时间复杂度O(1)
• 支持动态扩容
• 减少内存分配次数
• 确保二进制安全

1-2.InSet

IntSet是Redis中set集合的一种实现方式，

基于整数数组来实现，并且具备长度可变、有序等特征。

结构如下：

其中的encoding包含三种模式，表示存储的整数大小不同：

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

现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为： encoding：4字节 length：4字节 contents：2字节 * 3 = 6字节

我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。 以当前案例来说流程如下：

• 升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组
• 倒序依次将数组中的元素拷贝到扩容后的正确位置
• 将待添加的元素放入数组末尾
• 最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

Intset数据结构优点：

• Redis会确保Intset中元素的唯一、有序
• 具备类型升级机制，可以节省内存空间
• 底层采用二分查找方式来查询

1-3.Dict

Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。

而键与值的映射关系正是通过Dict来实现的。

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），

然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置。

如：我们存储k1=v1，假设k1的哈希值h =1，则1&3 =1，因此k1=v1要存储到数组角标1位置。

1-3-1.Dict的扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：

0. 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
1. 哈希表的 LoadFactor > 5 ；

1-3-2.Dict的rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。

因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。过程是这样的：

• 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：

• 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
• 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）

• 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
  
• 设置dict.rehashidx = 0，标示开始rehash
  
• 将dict.ht[0]中的每一个dictEntry都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]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空
  

整个过程画成图例：

Dict字典数据结构优点：

• Dict的结构：

• 类似java的HashTable，底层是数组加链表来解决哈希冲突
• Dict包含两个哈希表，ht[0]平常用，ht[1]用来rehash，常为null

• Dict的扩容与收缩：

• 当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时，Dict扩容
• 当LoadFactor小于0.1时，Dict收缩
• 扩容大小为第一个大于等于used + 1的2^n
• 收缩大小为第一个大于等于used 的2^n
• Dict采用渐进式rehash，每次访问Dict时执行一次rehash
• rehash时ht[0]只减不增，新增操作只在ht[1]执行，其它操作在两个哈希表

1-4.ZipList

ZipList 是一种特殊的“双端链表” ，由一系列特殊编码的连续内存块组成。

可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。

1-4-1.ZipListEntry

ZipList 中的Entry并不像普通链表那样记录前后节点的指针，

因为记录两个指针要占用16个字节，浪费内存。

而是采用了下面的结构：

• previous_entry_length：前一节点的长度，占1个或5个字节。

• 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
• 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

• encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
  
• contents：负责保存节点的数据，可以是字符串或整数
  

1-4-2.Encoding编码

ZipListEntry中的encoding编码分为字符串和整数两种： 字符串：如果encoding是以“00”、“01”或者“10”开头，则证明content是字符串

例如，我们要保存字符串：“ab”和 “bc”

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

• 整数：如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节

例如，我们要保存数字 2 和数字5