只放一个图片做网站,关键词在线下载,wordpress视频优化,北京网页设计师培训班目录 一、动态字符串
二、intset
三、Dict
1. 简介
2. Dict的扩容
3. Dict的rehash
4. 知识小结
四、ZipList
1. 简介
2. ZipListEntry
3. Encoding编码
五、ZipList的连锁更新问题
六、QuickList
七、SkipList
八、RedisObject
1. 什么是 redisObject
2. Redi…目录 一、动态字符串
二、intset
三、Dict
1. 简介
2. Dict的扩容
3. Dict的rehash
4. 知识小结
四、ZipList
1. 简介
2. ZipListEntry
3. Encoding编码
五、ZipList的连锁更新问题
六、QuickList
七、SkipList
八、RedisObject
1. 什么是 redisObject
2. Redis的编码方式
3. 五种数据结构
九、String
十、List
十一、Redis数据结构-Set结构
十二、ZSET
十三、Hash 一、动态字符串
我们都知道 Redis 中保存的 Key 是字符串value 往往是字符串或者字符串的集合。
可见字符串是 Redis 中最常用的一种数据结构。
不过 Redis 没有直接使用 C 语言中的字符串因为 C 语言字符串存在很多问题
获取字符串长度的需要通过运算
非二进制安全
不可修改
Redis 构建了一种新的字符串结构称为简单动态字符串 Simple Dynamic String 简称 SDS。
例如我们执行命令 那么 Redis 将在底层创建两个 SDS其中一个是包含 “name” 的 SDS另一个是包含“虎哥”的 SDS。
Redis 是 C 语言实现的其中 SDS 是一个结构体源码如下 例如一个包含字符串 “name” 的 sds 结构如下 SDS 之所以叫做动态字符串是因为它具备动态扩容的能力例如一个内容为 “hi” 的 SDS 假如我们要给 SDS 追加一段字符串 “,Amy” 这里首先会申请新内存空间
如果新字符串小于 1M则新空间为扩展后字符串长度的两倍 1
如果新字符串大于 1M则新空间为扩展后字符串长度 1M1。称为内存预分配。 二、intset
IntSet 是 Redis 中 set 集合的一种实现方式基于整数数组来实现并且具备长度可变、有序等特征。
结构如下 其中的 encoding 包含三种模式表示存储的整数大小不同 为了方便查找Redis 会将 intset 中所有的整数按照升序依次保存在 contents 数组中结构如图 现在数组中每个数字都在 int16_t 的范围内因此采用的编码方式是 INTSET_ENC_INT16部分占用的字节大
小为
encoding4 字节
length4 字节
contents2 字节 * 3 6 字节 我们向该其中添加一个数字50000这个数字超出了 int16_t 的范围intset 会自动升级编码方式到合适的大
小。
以当前案例来说流程如下
升级编码为 INTSET_ENC_INT32, 每个整数占 4 字节并按照新的编码方式及元素个数扩容数组倒序依次将数组中的元素拷贝到扩容后的正确位置将待添加的元素放入数组末尾最后将 inset 的 encoding 属性改为 INTSET_ENC_INT32将 length 属性改为 4 源码如下 综合所述
Intset 可以看做是特殊的整数数组具备一些特点
Redis 会确保 Intset 中的元素唯一、有序具备类型升级机制可以节省内存底层采用二分查找方式来查询
三、Dict
1. 简介
我们知道 Redis 是一个键值型 Key-Value Pair 的数据库我们可以根据键实现快速的增删改查。
而键与值的映射关系正是通过 Dict 来实现的。
Dict 由三部分组成分别是哈希表 DictHashTable 、哈希节点 DictEntry 、字典 Dict 当我们向 Dict 添加键值对时Redis 首先根据 key 计算出 hash 值 h
然后利用 h sizemask 来计算元素应该存储到数组中的哪个索引位置。
我们存储 k1v1假设 k1 的哈希值 h 1则 13 1
因此 k1v1 要存储到数组角标 1 位置。 Dict 由三部分组成分别是哈希表 DictHashTable 、哈希节点 DictEntry 、字典 Dict 2. Dict的扩容
Dict 中的 HashTable 就是数组结合单向链表的实现当集合中元素较多时必然导致哈希冲突增多
链表过长则查询效率会大大降低。
Dict 在每次新增键值对时都会检查负载因子 LoadFactor used/size 满足以下两种情况时会触发哈希表
扩容
哈希表的 LoadFactor 1并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程
哈希表的 LoadFactor 5 3. 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标示开始将 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 最终为空
整个过程可以描述成 4. 知识小结
Dict的结构
类似 java 的 HashTable底层是数组加链表来解决哈希冲突Dict 包含两个哈希表ht[0] 平常用ht[1] 用来 rehash
Dict 的伸缩
当 LoadFactor 大于 5 或者 LoadFactor 大于 1 并且没有子进程任务时Dict 扩当 LoadFactor 小于 0.1 时Dict扩容大小为第一个大于等于 used 1 的 2^n收缩大小为第一个大于等于 used 的 2^nDict 采用渐进式 rehash每次访问 Dict 时执行一次 rehashrehash 时 ht[0] 只减不增新增操作只在 ht[1] 执行其它操作在两个哈希表
四、ZipList
1. 简介
ZipList 是一种特殊的“双端链表” 由一系列特殊编码的连续内存块组成。
可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。 属性 类型 长度 用途 zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数 zltail uint32_t 4 字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节通过这个偏移量可以确定表尾节点的地址。 zllen uint16_t 2 字节 记录了压缩列表包含的节点数量。 最大值为UINT16_MAX 65534如果超过这个值此处会记录为65535但节点的真实数量需要遍历整个压缩列表才能计算得出。 entry 列表节点 不定 压缩列表包含的各个节点节点的长度由节点保存的内容决定。 zlend uint8_t 1 字节 特殊值 0xFF 十进制 255 用于标记压缩列表的末端。
2. ZipListEntry
ZipList 中的 Entry 并不像普通链表那样记录前后节点的指针因为记录两个指针要占用 16 个字节浪费内存。
而是采用了下面的结构 previous_entry_length前一节点的长度占 1 个或 5 个字节。
如果前一节点的长度小于254字节则采用1个字节来保存这个长度值如果前一节点的长度大于254字节则采用5个字节来保存这个长度值第一个字节为 0xfe后四个字节才是真实长度数据
encoding编码属性记录 content 的数据类型字符串还是整数以及长度占用 1 个、2 个或 5 个字节contents负责保存节点的数据可以是字符串或整数
ZipList 中所有存储长度的数值均采用小端字节序即低位字节在前高位字节在后。
例如数值 0x1234采用小端字节序后实际存储值为0x3412
3. Encoding编码
ZipListEntry 中的 encoding 编码分为字符串和整数两种
字符串如果 encoding 是以 “00”、“01” 或者 “10” 开头则证明 content 是字符串 编码 编码长度 字符串大小 |00pppppp| 1 bytes 63 bytes |01pppppp|qqqqqqqq| 2 bytes 16383 bytes |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| 5 bytes 4294967295 bytes
例如我们要保存字符串“ab” 和 “bc” ZipListEntry 中的 encoding 编码分为字符串和整数两种
整数如果 encoding 是以 “11” 开始则证明 content 是整数且 encoding 固定只占用1个字节 编码 编码长度 整数类型 11000000 1 int16_t2 bytes 11010000 1 int32_t4 bytes 11100000 1 int64_t8 bytes 11110000 1 24位有符整数(3 bytes) 11111110 1 8位有符整数(1 bytes) 1111xxxx 1 直接在xxxx位置保存数值范围从0001~1101减1后结果为实际值 五、ZipList的连锁更新问题
ZipList 的每个 Entry 都包含 previous_entry_length 来记录上一个节点的大小长度是 1 个或 5 个字节
如果前一节点的长度小于 254 字节则采用 1 个字节来保存这个长度值
如果前一节点的长度大于等于 254 字节则采用 5 个字节来保存这个长度值第一个字节为 0xfe后四个字节才
是真实长度数据
现在假设我们有 N 个连续的、长度为 250~253 字节之间的 entry因此 entry 的 previous_entry_length 属
性用 1 个字节即可表示
如图所示 ZipList 这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新 Cascade Update 。
新增、删除都可能导致连锁更新的发生。
综合所述
压缩列表的可以看做一种连续内存空间的双向链表列表的节点之间不是通过指针连接而是记录上一节点和本节点长度来寻址内存占用较如果列表数据过多导致链表过长可能影响查询性能增或删较大数据时有可能发生连续更新问题
六、QuickList
问题1ZipList 虽然节省内存但申请内存必须是连续空间如果内存占用较多申请内存效率很低。怎么办
答为了缓解这个问题我们必须限制 ZipList 的长度和 entry 大小。
问题2但是我们要存储大量数据超出了 ZipList 最佳的上限该怎么办
答我们可以创建多个 ZipList 来分片存储数据。
问题3数据拆分后比较分散不方便管理和查找这多个 ZipList 如何建立联系
答Redis 在 3.2 版本引入了新的数据结构 QuickList它是一个双端链表只不过链表中的每个节点都是一个
ZipList。 为了避免 QuickList 中的每个 ZipList 中 entry 过多Redis 提供了一个配置项list-max-ziplist-size 来限制。
如果值为正则代表 ZipList 的允许的 entry 个数的最大值
如果值为负则代表 ZipList 的最大内存大小分 5 种情况
-1每个 ZipList 的内存占用不能超过 4kb-2每个 ZipList的 内存占用不能超过 8kb-3每个 ZipList 的内存占用不能超过 16kb-4每个 ZipList 的内存占用不能超过 32kb-5每个 ZipList 的内存占用不能超过 64kb
其默认值为 -2 以下是 QuickList 的和 QuickListNode 的结构源码 我们接下来用一段流程图来描述当前的这个结构 综合所述
QuickList 是一个节点为 ZipList 的双端链表节点采用 ZipList解决了传统链表的内存占用控制了 ZipList 大小解决连续内存空间申请效率中间节点可以压缩进一步节省了内存
七、SkipList
SkipList跳表首先是链表但与传统链表相比有几点差异
元素按照升序排列存储
节点可能包含多个指针指针跨度不同。 SkipList跳表首先是链表但与传统链表相比有几点差异
元素按照升序排列存储
节点可能包含多个指针指针跨度不同。 SkipList跳表首先是链表但与传统链表相比有几点差异
元素按照升序排列存储
节点可能包含多个指针指针跨度不同。 综合所述
跳跃表是一个双向链表每个节点都包含 score 和 ele 值节点按照 score 值排序score 值一样则按照 ele 字典每个节点都可以包含多层指针层数是 1 到 32 之间的随机不同层指针到下一个节点的跨度不同层级越高跨度越大增删改查效率与红黑树基本一致实现却更简单
八、RedisObject
Redis 中的任意数据类型的键和值都会被封装为一个 RedisObject也叫做 Redis 对象源码如下
1. 什么是 redisObject
从 Redis 的使用者的角度来看⼀个 Redis 节点包含多个 database非 cluster 模式下默认是 16 个cluster 模
式下只能是 1 个而一个 database 维护了从 key space 到 object space 的映射关系。这个映射关系的 key
是 string 类型⽽ value 可以是多种数据类型
比如string , list , hash、set、sorted set 等。
我们可以看到key 的类型固定是 string而 value 可能的类型是多个。
⽽从 Redis 内部实现的⾓度来看database 内的这个映射关系是用⼀个 dict 来维护的。
dict 的 key 固定用⼀种数据结构来表达就够了这就是动态字符串 sds。而 value 则比较复杂为了在同⼀个
dict 内能够存储不同类型的 value这就需要⼀个通⽤的数据结构这个通用的数据结构就是 robj全名是
redisObject。 2. Redis的编码方式
Redis 中会根据存储的数据类型不同选择不同的编码方式共包含 11 种不同类型 编号 编码方式 说明 0 OBJ_ENCODING_RAW raw编码动态字符串 1 OBJ_ENCODING_INT long类型的整数的字符串 2 OBJ_ENCODING_HT hash表字典dict 3 OBJ_ENCODING_ZIPMAP 已废弃 4 OBJ_ENCODING_LINKEDLIST 双端链表 5 OBJ_ENCODING_ZIPLIST 压缩列表 6 OBJ_ENCODING_INTSET 整数集合 7 OBJ_ENCODING_SKIPLIST 跳表 8 OBJ_ENCODING_EMBSTR embstr的动态字符串 9 OBJ_ENCODING_QUICKLIST 快速列表 10 OBJ_ENCODING_STREAM Stream流
3. 五种数据结构
Redis 中会根据存储的数据类型不同选择不同的编码方式。每种数据类型的使用的编码方式如下 数据类型 编码方式 OBJ_STRING int、embstr、raw OBJ_LIST LinkedList和ZipList(3.2以前)、QuickList3.2以后 OBJ_SET intset、HT OBJ_ZSET ZipList、HT、SkipList OBJ_HASH ZipList、HT
九、String
String 是 Redis 中最常见的数据存储类型
其基本编码方式是 RAW基于简单动态字符串 SDS 实现存储上限为 512mb。
如果存储的 SDS 长度小于 44 字节则会采用 EMBSTR 编码此时 object head 与 SDS 是一段连续空间。申请
内存时只需要调用一次内存分配函数效率更高。
底层实现⽅式动态字符串 sds 或者 long
String 的内部存储结构⼀般是 sds Simple Dynamic String 可以动态扩展内存但是如果⼀个 String 类型
的 value 的值是数字那么 Redis 内部会把它转成 long 类型来存储从⽽减少内存的使用。 如果存储的字符串是整数值并且大小在 LONG_MAX 范围内则会采用 INT 编码直接将数据保存在
RedisObject 的 ptr 指针位置刚好 8 字节不再需要 SDS 了。 确切地说String 在 Redis 中是⽤⼀个 robj 来表示的。
用来表示 String 的 robj 可能编码成 3 种内部表⽰OBJ_ENCODING_RAWOBJ_ENCODING_EMBSTR
OBJ_ENCODING_INT。
其中前两种编码使⽤的是 sds 来存储最后⼀种 OBJ_ENCODING_INT 编码直接把 string 存成了 long 型。
在对 string 进行 incr, decr 等操作的时候如果它内部是 OBJ_ENCODING_INT 编码那么可以直接行加减操
作如果它内部是OBJ_ENCODING_RAW 或 OBJ_ENCODING_EMBSTR 编码那么 Redis 会先试图把 sds 存储
的字符串转成 long 型如果能转成功再进行加减操作。
对⼀个内部表示成 long 型的 string 执行 append , setbit , getrange 这些命令针对的仍然是 string 的值即
⼗进制表示的字符串而不是针对内部表⽰的 long 型进⾏操作。
比如字符串 ”32”如果按照字符数组来解释它包含两个字符它们的 ASCII 码分别是 0x33 和 0x32 。当我
们执行命令 setbit key 70 的时候相当于把字符 0x33 变成了 0x32这样字符串的值就变成了 ”22”。
⽽如果将字符串 ”32” 按照内部的 64 位 long 型来解释那么它是 0x0000000000000020在这个基础上执
⾏ setbit 位操作结果就完全不对了。
因此在这些命令的实现中会把 long 型先转成字符串再进行相应的操作。
十、List
Redis 的 List 类型可以从首、尾操作列表中的元素 哪一个数据结构能满足上述特征
LinkedList 普通链表可以从双端访问内存占用较高内存碎片较多ZipList 压缩列表可以从双端访问内存占用低存储上限低QuickListLinkedList ZipList可以从双端访问内存占用较低包含多个 ZipList存储上限高
Redis的List结构类似一个双端链表可以从首、尾操作列表中的元素
在 3.2 版本之前Redis 采用 ZipList 和 LinkedList 来实现 List当元素数量小于 512 并且元素大小小于 64 字节
时采用 ZipList 编码超过则采用 LinkedList 编码。
在 3.2 版本之后Redis 统一采用 QuickList 来实现 List 十一、Redis数据结构-Set结构
Set 是 Redis 中的单列集合满足下列特点
不保证有序保证元素求交集、并集、差集 可以看出Set 对查询元素的效率要求非常高思考一下什么样的数据结构可以满足
HashTable也就是 Redis 中的 Dict不过 Dict 是双列集合可以存键、值对
Set 是 Redis 中的集合不一定确保元素有序可以满足元素唯一、查询效率要求极高。
为了查询效率和唯一性set 采用 HT 编码 Dict 。Dict 中的 key 用来存储元素value 统一为 null。
当存储的所有数据都是整数并且元素数量不超过 set-max-intset-entries 时Set 会采用 IntSet 编码以节省
内存 结构如下 十二、ZSET
ZSet 也就是 SortedSet其中每一个元素都需要指定一个 score 值和 member 值
可以根据 score 值排序member 必须可以根据 member 查询分数 因此zset 底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。
之前学习的哪种编码结构可以满足
SkipList可以排序并且可以同时存储 score 和 ele 值 member HTDict可以键值存储并且可以根据 key 找 value 当元素数量不多时HT 和 SkipList 的优势不明显而且更耗内存。
因此 zset 还会采用 ZipList 结构来节省内存不过需要同时满足两个条件
元素数量小于 zset_max_ziplist_entries默认值 128每个元素都小于 zset_max_ziplist_value字节默认值 64
ziplist 本身没有排序功能而且没有键值对的概念因此需要有 zset 通过编码实现
ZipList 是连续内存因此 score 和 element 是紧挨在一起的两个 entry element 在前score 在后score 越小越接近队首score 越大越接近队尾按照 score 值升序排列 十三、Hash
Hash 结构与 Redis 中的 Zset 非常类似
都是键值存储都需求根据键获取值键必须唯一
区别如下
zset 的键是 member值是 scorehash 的键和值都是任意值zset 要根据 score 排序hash 则无需排序
底层实现方式压缩列表 ziplist 或者字典 dict
当 Hash 中数据项比较少的情况下Hash 底层才⽤压缩列表 ziplist 进⾏存储数据随着数据的增加底层的 ziplist 就可能会转成 dict
具体配置如下
hash-max-ziplist-entries 512hash-max-ziplist-value 64
当满足上面两个条件其中之⼀的时候Redis 就使⽤ dict 字典来实现 hash。
Redis 的 hash 之所以这样设计是因为当 ziplist 变得很⼤的时候它有如下几个缺点
每次插⼊或修改引发的 realloc 操作会有更⼤的概率造成内存拷贝从而降低性能。⼀旦发生内存拷贝内存拷贝的成本也相应增加因为要拷贝更⼤的⼀块数据。当 ziplist 数据项过多的时候在它上⾯查找指定的数据项就会性能变得很低因为 ziplist 上的查找需要进行
遍历。
总之ziplist 本来就设计为各个数据项挨在⼀起组成连续的内存空间这种结构并不擅长做修改操作。
⼀旦数据发⽣改动就会引发内存 realloc可能导致内存拷贝。
hash 结构如下 zset 集合如下 因此Hash 底层采用的编码与 Zset 也基本一致只需要把排序有关的 SkipList 去掉即可
Hash 结构默认采用 ZipList 编码用以节省内存。 ZipList 中相邻的两个 entry 分别保存 field 和 value
当数据量较大时Hash 结构会转为 HT 编码也就是 Dict触发条件有两个
ZipList 中的元素数量超过了 hash-max-ziplist-entries默认 512ZipList 中的任意 entry 大小超过了 hash-max-ziplist-value默认 64 字节
