redis 底层数据结构
概述
Redis 6 和 Redis 7 之间对比：
Redis6 和 Redis7 最大的区别就在于 Redis7 已经用 listpack 替代了 ziplist.
以下是基于 Redis 7基础分析。
RedisObject
Redis是⼀个<k,v>型的数据库，其中key通常都是string类型的字符串对象，⽽value在底层就统⼀是redisObject对象。Redis中的任意数据类型都会被封装为⼀个RedisObject，也叫做Redis对象， redisObject结构，实际上就是Redis内部抽象出来的⼀个封装所有底层数据结构的统⼀对象。这就类似于Java的⾯向对象的设计⽅式。
这⾥⾯⼏个核⼼字段意义如下：
- type：Redis的上层数据类型。⽐如string,hash,set等，可以使⽤指令type key查看。
127.0.0.1:6379> set userid 1594
OK
127.0.0.1:6379> type userid
string
- encoding： Redis内部的数据类型。可以使⽤指令 object encoding key查看。
127.0.0.1:6379> set userid 1594
OK
127.0.0.1:6379> object encoding userid
"int"
- lru：当内存超限时会采⽤LRU算法清除内存中的对象。关于LRU与LFU，在redis.conf中有描述
# LRU means Least Recently Used
# LFU means Least Frequently Used
- refcount：表示对象的引⽤次数。可以使⽤OBJECT REFCOUNT key 指令查看。
- ptr：这是⼀个指针，指向真正底层的数据结构。encoding只是⼀个类型描述。实际数据是保存在ptr指向的具体结构⾥。
encoding 底层编码方式如下:
| 编码方式 | 说明 |
| 0BJ_ENCODING_RAW | raw编码动态字符串 |
| OBJ_ENCODING_INT | long类型的整数的字符串 |
| OBJ_ENCODING_HT | hash表(字典dict) |
| OBJ_ENCODING_ZIPMAP | 已废弃 |
| OBJ_ENCODING_LINKEDLIST | 双端链表 (已废弃) |
| 0BJ_ENCODING_ZIPLIST | 压缩列表(7.0 已废弃) |
| OBJ_ENCODING_INTSET | 整数集合 |
| OBJ_ENCODING_SKIPLIST | 跳表 |
| 0BJ_ENCODING_EMBSTR | embstr的动态字符串 |
| 0BJ_ENCODING_QUICKLIST | 快速列表 |
| 0BJ_ENCODING_STREAM | Stream流 |
| OBJ_ENCODING_LISTPACK | 紧凑列表 |
String 数据结构
SDS
- 获取字符串⻓度的需要通过运算
- ⾮⼆进制安全
- 不可修改
127.0.0.1:6379> set name hi
OK那么Redis将在底层创建两个SDS，其中一个是包含“name”的SDS，另一个是包含“hi”的SDS。
Redis是C语言实现的，其中SDS是一个结构体，源码如下：
例如，一个包含字符串“name”的sds结构如下：
SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的SDS：
假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间：
如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；
如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。
优点：
- 获取字符串长度的时间复杂度为O(1)
- 支持动态扩容
- 减少内存分配次数
- 二进制安全
String底层结构之int
如果存储的字符串是整数值，并且⼤⼩在LONG_MAX范围内，则会采⽤INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。
String底层结构之embstr
如果存储的SDS⻓度⼩于44字节，则会采⽤EMBSTR编码，此时object head与SDS是⼀段连续空间。申请内存时只需要调⽤⼀次内存分配函数，效率更⾼。
String底层结构之Raw
Hash 数据结构
127.0.0.1:6379> config get has*
3) "hash-max-listpack-value"
4) "64"
7) "hash-max-listpack-entries"
8) "512"
Hash数据结构之 listpack
listpack(紧凑列表)可以理解为一个替代版本的ziplist，由于ziplist中有着致命的缺陷-连锁更新，在极端条件下会有着极差的性能，导致整个redis响应变慢。因此在redis5中引入了新的数据结构listpack，作为ziplist的替代版。listpack在6以后已经作为t_hash的基础底层结构。
和 ziplist 列表项类似，listpack 列表项也包含了元数据信息和数据本身。不过，为了避免 ziplist 引起的连锁更新问题，listpack 中的每个列表项不再像 ziplist 列表项那样，保存其前一个列表项的长度，它只会包含三个方面内容：
- 当前元素的编码类型（entry-encoding）
- 元素数据 (entry-content)
- 编码类型和元素数据这两部分的长度 (entry-length)
Hash数据结构之 hashtable
在Redis中hashtable就是字典dict，Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）。
代码
结构图
- 计算新hash表的realsize，即第⼀个⼤于等于dict.ht[0].used的2n
- 按照新的realsize申请内存空间，创建dictht，并赋值给dict.ht[1]
- 设置rehashidx= 0，标示开始rehash
- 将dict.ht[0]中的每⼀个dictEntry都rehash到dict.ht[1]每次执⾏新增、查询、修改、删除操作时，都检查⼀下dict.rehashidx是否⼤于 -1，如果是则将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]初始化为空哈希表
- 将rehashidx赋值为-1，代表rehash结束
- 在rehash过程中，新增操作，则直接写⼊ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执⾏。这样可以确保h[0]的数据只减不增，随着 rehash最终为空
RedisObject
List 数据结构
- - 5：每个quicklist节点上的listpack大小不能超过64Kb（1kb=1024 bytes，即64*1024 bytes）
- -4：每个quicklist节点上的listpack大小不能超过32Kb（1kb=1024 bytes，即32*1024 bytes）
- -3：每个quicklist节点上的listpack大小不能超过16Kb（1kb=1024 bytes，即16*1024 bytes）
- -2：默认值，每个quicklist节点上的listpack大小不能超过8Kb（1kb=1024 bytes，即8*1024 bytes）
- -1：每个quicklist节点上的listpack大小不能超过4Kb（1kb=1024 bytes，即4*1024 bytes）
127.0.0.1:6379> config get lis*
3) "list-compress-depth"
4) "0"
5) "list-max-listpack-size"
6) "-2"
List 数据结构之 listpack
同Hash数据结构之 listpack 一样，参考上文。
List 数据结构之 quicklist
listpack 虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。但是我们要存储大量数据，超出了listpack最佳的上限，那怎么办？
Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个 listpack。我们就可以将数据存到多个 listpack中。
总结：
QuickList的特点：
- 是一个节点为listpack的双端链表
- 节点采用listpack，解决了传统链表的内存占用问题
- 控制了listpack大小，解决连续内存空间申请效率问题
- 中间节点可以压缩，进一步节省了内存
Set 数据结构
- 如果set的数据都是不超过64位的数字(⼀个long数字).就使⽤intset存储 IntSet 。
- 如果set的数据不是数字，并且数据的数量没有大于128且数据⼤⼩小于64，就⽤listpack存储。
- 如果数据的数量大于128或数据⼤⼩小于64，就改为使⽤hashtable存储。
127.0.0.1:6379> config get set*
3) "set-max-listpack-value"
4) "64"
5) "set-max-listpack-entries"
6) "128"
7) "set-max-intset-entries"
8) "512"
Set 数据结构之 IntSet
结构如下：
其中的encoding包含三种模式，表示存储的整数大小不同：
为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：
总结：
Intset可以看做是特殊的整数数组，具备一些特点：
- Redis会确保Intset中的元素唯一、有序
- 具备类型升级机制，可以节省内存空间
- 底层采用二分查找方式来查询
Set 数据结构之 listpask
同Hash数据结构之 listpack 一样，参考上文。
Set 数据结构之 hashtable
ZSet 数据结构
- 如果set 数据的数量没有大于128且数据⼤⼩小于64，就⽤listpack存储。
- 如果数据的数量大于128或数据⼤⼩小于64，就改为使⽤skiplist 存储。
127.0.0.1:6379> config get zset*
1) "zset-max-listpack-entries"
2) "128"
7) "zset-max-listpack-value"
8) "64"
ZSet 数据结构之 listpask
同Hash数据结构之 listpack 一样，参考上文。
ZSet 数据结构之 skiplist
原文地址：https://blog.csdn.net/weixin_46203834/article/details/143889038
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！