之前看了《Redis 设计与实现》这本书, 对 Redis 的认识加深了一些, 便做了一些总结, 同时也记录下自己的一些想法.
这节先介绍 Redis 提供的基本结构, 主要分为底层的基本结构和以对象形式包装的 Object 结构.
1.SDS
C 字符串在 Redis 中主要用于无须对字符串值进行修改的地方, 对于需要修改字符串的场景, 则使用 SDS(简单动态字符串).
SDS 的结构如下示:
其中 buff 是字符串缓冲区, 用于存放字符串, len 为 buf 数组中已使用字节的数量, free 为 buf 数组中未使用字节的数量. 注意, buff 中存放的是二进制数据, 使用 len 属性来判断字符串是否结束, 保留'\0'符号是为了兼容部分 C 函数.
同 C 字符串相比, 由于 SDS 记录了相关的使用情况, 因而能够以常数复杂度获取字符串长度, 并且能够杜绝缓冲区溢出. 同时, 通过使用空间预分配和惰性空间释放两种策略, 能够减少修改字符串时带来的内存重分配次数.
所谓空间预分配是指, 当对 SDS 进行修改的时候, 并且需要对 SDS 空间进行扩展的时候, 程序不仅会为 SDS 分配修改所需要的空间, 还会为 SDS 分配额外的未使用空间. 其分配策略是如下定义的: 如果对 SDS 修改后的长度小于 1MB, 那么程序分配和 len 属性同样大小的未使用空间; 如果对 SDS 修改后的长度大于等于 1MB, 那么程序会分配 1MB 的未使用空间. 通过空间预分配策略, Redis 可以减少连续执行字符串增长操作所需要的内存重分配次数.
所谓惰性空间释放, 就是当需要缩短 SDS 保存的字符串的时候, 程序并不立即使用内存重新分配来回收缩短后多出来的字节, 而是使用 free 属性将这些字节的数量记录下来, 并等将来使用.
SDS 的行为同 Java 中的 StringBuilder 类似.
2.list
list 结构是个标准的无环双向链表实现, 结构如下:
具体过程不再讲解, 网上对该结构的讲解比较多.
3.dict
dict 结构是个标准的字典实现, 使用链地址法解决冲突. Dict 的结构如下:
其中 ht 是一个长度为 2 的数组, 一般情况下只使用了 ht[0],ht[1] 用于 rehash 过程. rehashidx 记录了 rehash 的过程,-1 表示没有在进行. Redis 采用渐进式 rehash 的方式来 rehash, 防止在数量庞大时导致服务器在一段时间内停止服务.
渐进式 rehash 的主要过程为: 为 dict 的 ht[1] 哈希表分配空间, 可以是扩容, 也可以是缩容; 将保存在 ht[0] 中的所有键值对重新计算索引值, rehash 到 ht[1] 上; 迁移完成后释放 ht[0], 将 ht[1] 设置为 ht[0], 并在 ht[1] 新创建一个空白哈希表, 为下一次 rehash 做准备.
4.jump List
跳表是有序集合的底层实现之一.
关于跳表的细节, 可以看下面的介绍
Redis 使用跳表不用红黑树的原因在于:
在插入, 删除, 查找以及迭代输出有序序列这几个操作上, 跳表跟红黑树的时间复杂度是一样的, 但是在按区间查找数据的操作上, 跳表的效率比红黑树更高.
跳表较红黑树更好实现, 意味着可读性好, 不易出错.
跳表更加灵活, 可以通过改变索引结构来平衡执行效率和内存消耗之间的关系
5.intset
当一个集合只包含整数值元素, 并且这个集合的元素数量不多时, Redis 就会使用整数集合作为集合的底层实现. 下面是 intset 的结构
其中 content 用于存储整数集合的值, length 为 content 的长度, encoding 为 content 中存储的整数的类型, 可以为 int_16,int_32 和 int_64.
当需要新增元素到 intset 里时, Redis 会保证元素是有序的. 如果 content 长度不够或者新增的类型同 encoding 的类型不同, 还会触发 intset 的升级. 升级过程包括重新分配 content 大小 (以新的 encoding 类型为准), 必要时提升 encoding 的类型, 移动元素的位置, 最后修改 length 属性.
注意, intset 不支持降级操作, 一旦对数组进行了升级, 编码就会一直保持升级后的状态.
6.zipList
当一个列表键只包含少量列表项, 并且每个列表项要么就是小整数, 要么就是长度比较短的字符串, 那么就会使用压缩列表来做列表键的底层实现.
压缩列表的结构如下:
每个 zipList 节点的组成部分如下:
每个节点保存一个字节数据或者一个整数值, 其中字节数组和整数值都允许保存不同的长度, 由 encoding 属性决定. previous_entry_length 属性则记录了前一个节点的长度, 使用 1 个字节或者 5 个字节来存储, 在新节点加入时可能引起连锁更新.
7.object
Redis 以对象的形式来存储键值, 提供了字符串对象, 列表对象, 哈希对象, 集合对象和有序集合对象 5 种类型. 并使用引用计数来管理对象的回收.
对象结构的主要属性包括 type,encoding 和 ptr 属性.
其中 type 属性记录了对象的类型, 这个属性的值包括:
类型常量 | 对象的名称 |
---|---|
REDIS_STRING | 字符串对象 |
REDIS_LIST | 列表对象 |
REDIS_HASH | 哈希对象 |
REDIS_SET | 集合对象 |
REDIS_ZSET | 有序集合对象 |
encoding 记录了对象使用了什么数据结构的对象底层实现, 这个属性的值包括:
编码常量 | 编码所对应的底层数据结构 |
---|---|
REDIS_ENCODING_INT | long 类型的整数 |
REDIS_ENCODING_EMBSTR | embstr 编码的简单动态字符串 |
REDIS_ENCODING_RAW | 简单动态字符串 |
REDIS_ENCODING_HT | 字典 |
REDIS_ENCODING_LINKEDLIST | 双端链表 |
REDIS_ENCODING_ZIPLIST | 压缩列表 |
REDIS_ENCODING_INTSET | 整数集合 |
REDIS_ENCODING_SKIPLIST | 跳跃表和字典 |
1.REDIS_STRING
字符串对象的编码可以为 INT,EMBSTR 或者 RAW. 当字符串对象保存的是整数, 且该整数能够用 long 来表示, 则使用 int 存储整数值; 当保存的是一个字符串, 且长度小于 39 字节, 则使用 embstr 编码, 大于 39 字节则使用 raw 编码. 关于两者的区别, 可以看下面的说明 http://redisbook.com/preview/object/string.html . 而 embstr 要以 39 个字节来划分的原因可以看这个说明
2.REDIS_LIST
列表对象的编码可以为 ZIPLIST 或者 LINKEDLIST.
当列表对象可以同时满足以下两个条件时, 列表对象使用 ziplist 编码:
列表对象保存的所有字符串元素的长度都小于 64 字节;
列表对象保存的元素数量小于 512 个
若不满足则使用 linkedlist 编码, 该条件可以通过配置文件的配置项 list-max-ziplist-value 和 list-max-ziplist-entries 进行修改.
3.REDIS_HASH
哈希对象的编码可以为 ZIPLIST 或者 HASHTABLE
当哈希对象可以同时满足以下两个条件时, 哈希对象使用 ziplist 编码:
哈希对象保存的所有键值对的键和值的字符串当度都小于 64 字节;
哈希对象保存的键值对数量小于 512 个
若不满足则使用 hashtable 编码, 该条件可以通过配置文件的配置项 hash-max-ziplist-value 和 hash-max-ziplist-entries 进行修改.
4.REDIS_SET
集合对象的编码可以为 INTSET 或者 HASHTABLE
当集合对象可以同时满足以下两个条件时, 使用 intset 编码:
集合对象保存的所有元素都是整数值;
集合对象保存的元素数量不超过 512 个
若不满足则使用 hashtable 编码, 该条件可以通过配置文件的配置项 set-max-intset-entries 进行修改.
5.REDIS_ZSET
有序集合的编码可以为 ZIPLIST 或者 SKIPLIST
当有序集合对象同时满足以下两个条件时, 使用 ziplist
有序集合保存的元素数量小于 128 个;
有序集合保存的所有元素成员的长度都小于 64 字节;
若不满足则使用 skiplist 编码, 该条件可以通过配置文件的配置项 zset-max-ziplist-entries 和 zset-max-ziplist-values 进行修改.
个人公众号: 啊驼
来源: https://www.cnblogs.com/cxyAtuo/p/11562361.html