Redis基础与高级数据结构

一、Redis基础与高级数据结构
二、Redis基础原理
三、Redis拓展知识

一、string

1. 基本原理：字符数组，动态字符串，预分配冗余空间减少内存频繁分配
2. 扩容原理：长度<1MB时2倍扩容，长度>1MB时一次扩1MB，字符串最大长度512MB
3. 数据结构：
   • struct SDS<T> { T capacity; T len ; byte flags; byte[] content;}
   • 长度特别短embstr结构，长度超过44字节时raw的结构
   • embstr内存上连续一次内存分配，raw内存上不连续二次内存分配，Redis对象头指针指向String内存地址
   • 44字节改变结构：64-Redsi对象头（16字节）-String对象头（3字节）-字符串末尾NULL（1字节）=44字节

二、list

1. 基本结构：ziplist、quicklist（个数大于512或长度超过64）

2. ziplist数据结构：

   zlbytes	zltail_offset	zllengt	entry	...	entry	zlend
   总字节数	最后个元素到第一个的偏移量	元素个数	元素1	...	元素n	列表结束符

   • ziplist是一块连续的空间，元素之间紧挨着储存
   • entry的结构:struct entry{int<var> prevlen; int<var> encoding; optional byte[] content;},prevlen为前一个元素的长度，encodeing为编码类型，用于标识内容类型和长度，如果对于小的整数来说，encoding低位中就保存内容，不用保存在content中
   • entry中的prevlen，当存储的字符串长度小于254字节，使用1字节表示长度，
     大于254个字节，使用5个字节标识长度，ziplist添加和删除节点会引发联机更新的问题
3. quicklist数据结构：
   • 之前采用linklist后由于指针大小和每次内存单独分配，改用quicklist
   • ziplist默认长度为8KB，默认不压缩，可以配置使用LZF算法进行压缩

三、hash

1.基本结构：ziplist、数组+链表（个数大于512或长度超过64）
2.扩容方式：为追求性能采用渐进式rehash策略，同时保留新旧2个hash结构
3.扩容原理：哈希扩容的时候会有卡顿，所有同时保留现有哈希和扩容缩容后的哈希，在原哈希没有找到再另一个哈希再进行查找，在定时任务以及后续的hash操作指令中渐渐的将旧数组的元素迁移到新数组。

四、set

1.数据结构：intset、哈希的特殊结构，所有的value都是NULL（个数大于512）
intset结构，动态调整类型为uint16~uint64的数组

encoding	length	value	value	...	value

五、zset

1.数据结构：ziplist、哈希（存储key-value）+跳跃列表（提供排序）（个数大于512或长度超过64）
2.quicklist数据结构：

• 最多64层，容纳2的64次方个元素
• 插入元素采用随机算法，理论上第一层概率为50%，第二层25%，以此类推，redis中晋升25%，因此跳跃列表会比较扁平
• source值一样的时候会比较value的值
• rank的实现是因为在节点的指针中存放了一跳经过的跨度

---

六、位图

1.基本结构：位数组
2.使用场景：用户的一年签到记录
3.基本操作：

• getbit、setbit、bitcount（指定位置范围）、bitpos（指定范围内）
• bitfield多个位操作set、get、incrby（默认配置会出现折返。也可以设置失败或者饱和截断）

七、HyperLogLog

1.基本结构：稀疏矩阵、HyperLogLog（2的14次方个桶用于调和平均，所以占12KB）
2.使用场景：提供不精确的去重计数方案，标准误差为0.81%，可以统计每天访问系统的UV数据
3.基本操作：pfadd、pfcount、pfmerge（多个pf计数累加）

八、布隆过滤器

1.基本结构：位数组、无偏hash函数

2.使用场景：推荐算法中的是否已经看过该文档、邮件过滤、爬虫记录已经爬过的URL，会有一定误判，但是不存在一定不存在，存在不一定一定存在。
3.基本使用：bf.add、bf.exists 、bf.mexists
4.参数调优：

• 使用bf.reserve设置key、error_rate、inital_size
• error_rate错误率，错误率越低空间越大
• inital_size预计元素个数，超了误判率会变高

九、地理位置GeoHash（了解）

1.算法原理：GeoHash将二维的经纬度数据映射到一维的整数（反向从证书还原有损），所有的坐标都存储在zset中，score是坐标52位整数，所以可以查看附件的元素（实际会复杂一些）

2.基本使用：geoadd、geodist（距离）、geopos（经纬度）、geohash（位置编码）、georadiusbymemeber(位置附近)、georadius(经纬附近)
3.注意事项：

• 集群数据量不建议超过1MB，这样迁移可能会卡顿
• 建议使用单机，Geo数据按照国家、省等进行拆分

---

十、listpack（了解）

1.产生背景：为了取代ziplist，不会有级联更新的问题，每个节点单独存在
2.数据结构：

total_bytes	size	entry	...	entry	end
总字节数	元素个数	元素1	...	元素n	列表结束符

• entry的结构:struct entry{int<var> encoding;optional byte[] content;int<var> length;},length为当前元素的长度，不再是前一个元素长度，由于在entry的末端，所以与ziplist相比可以直接计算最后一个元素的位置，encodeing为编码类型，可以是1~5个字节中的任一长度
• 现在暂时应用于Stream中，并没有完全的替换ziplist的结构

十一、基数树 rax（了解）

1.数据结构：与zset不同的是zset基于score进行排序，rax基于key进行排序（字典序），rax是基数树radix tree的特殊结构，与基数树不同的是节点可以进行压缩存多个字符

2.使用场景：使用在Stream机构中用于存储消息队列