1.数据结构与内部编码

1.1 五种基本数据结构

Redis的key均为字符串，value有五种基本数据结构类型，分别为string、list、set、zset、hash。

1.2 数据结构和内部编码

以下为Redis3.0的数据结构和内部编码结构

最新版本的数据结构和内部编码，主要是去掉了ziplist（压缩表），新增了quicklist。

二.内部编码

2.1.压缩列表

2.1.1 压缩列表的结构设计

2.1.1.1 压缩列表构成

Redis使用字节数组实现压缩列表，字节数逻辑划分为多段，如下图：

• zlbytes：用于表示整个字节数组的长度，上图所示的字节数组有23个字节。
• zltail：用户表示最后一个节点距离压缩列表起始地址的距离，为了便于快速找到最后一个节点。上图所示，最后一个节点2距离起始地址的距离是15字节。
• zlen：表示压缩列表一共有几个节点，上图所示，一共有2个节点。

2.1.1.2 节点主要构成

节点主要由previous_entry_length、encoding、content三部分组成。

节点的三个组成部分使用的字节数并不固定，数据越长使用的字节越多，数据越少使用的字节越少，从而达到节约内存的目的。

• previous_entry_length：如果前一个节点的长度<254字节，则previous_entry_length使用用一个字节表示，前一个字节的长度>=254字节，则previous_entry_length变为五个字节。
• encoding：记录了content部分所保存的数据类型及长度。

以下补一个关于C语言数字类型的说明

content：保存节点的数据值。

2.1.2 压缩列表实现列表功能

2.1.2.1 压缩列表示例

以下是一个含有3个节点的压缩列表，3个节点内容分别为10000，1000000，money，以下简单介绍一个LPUSH、RPUSH的操作过程。

LPUSH

1、压缩列表前十位是固定的，LPUSH是从左侧插入。

2、新节点插入后，第2个节点的previous_entry_length需要做一下更新。

3、更新全局变量zlbytes和ztail。

RPUSH

1、利用zltail找到尾节点。

2、在尾节点后面插入新节点。

3、更新全局变量zlbytes和ztail。

2.1.2.2 连续更新问题

previous_entry_length记录着前驱节点的长度，前驱节点发生变化，可能会引起previous_entry_length的变化。

1、前驱节点长度由小于254变成大于等于254时，previous_entry_length就会由1个字节变成5个字节。

2、前驱节点长度由大于等于254变成小于254时，previous_entry_length就会由5个字节变成1个字节。

以下展示一个连续更新的场景：

1、如图，节点1的前驱节点为空，因此previous_entry_length为1个字节。节点2前的节点1是253位，因此节点2中的previous_entry_length也是1个字节。

2、插入一个节点为1000个字节的新节点。

3、因为前驱节点长度从0变成1000，长度已经超过了1个字节可能表达的范围（0-253），节点1的previous_entry_length就会变成5个节点。

4、因为节点1的长度由253变成了257，长度已经超过了1个字节可能表达的范围（0-253），节点2的previous_entry_length就会变成5个结点。

2.2.字典

2.2.1 哈希结构

Redis字典是使用哈希表作为底层实现，每个哈希表节点存储字典的一个键值对。

dict结构

• ht：哈希表。
• rehashindex：-1时表示hash没有进行扩容，> -1 表示正在扩容。

dictht结构：

• table：哈希表数组。
• size：哈希表大小。
• sizemask：哈希表掩码，用于计算哈希值。大小等于size-1。
• used：哈希表已有节点数量。

2.2.2 rehash

扩容触发条件

（负载因子 = ht[0].used / ht[0].size）

• 哈希表负载因子>=1 && <5，并且当前没有执行BGSAVE或BGREWRITEAOF命令。
• 哈希表负载因子 > 5。

扩容过程

如果hash表中元素达到百万甚至千万，

渐进式扩容

• 为ht[1]分配空间，ht[1]的空间是ht[0]的2倍。
• rehashidx设置为0，扩容正式开始。
• 扩容器件增删改查同时在ht[0]和ht[1]上进行，同时将ht[0]上的元素rehash到ht[1]，同时rehashidx++。
• 随着rehash不断进行，dt[0]最终为空。将rehashidx设置为-1。释放ht[0]，将ht[1]设置为ht[0]。

若有收获，就点个赞吧