redis数据对象和底层数据结构

1. 基础对象

Redis中的key一定是字符串，value可以是string、list、hash、set、sortset这几种常用的。

类型	作用	底层数据结构
string	简单的key-value	SDS
list	有序列表，可做简单队列	ziplist, linkedlist 【quicklist】
hash	哈希表，存储结构化数据	ziplist, hashtable
set	无序列表(去重)，提供一系列的交集、并集、差集的命令	intset, hashtable
sortset	有序集合映射，排行榜，和时间相关的排序	ziplist, zskiplist

Redis3.0 和 Redis7.0 对比

1.1 string

1. 应用场景：缓存对象、常规计数、分布式锁、共享 session 信息等。

2. String 类型的底层的数据结构实现主要是 SDS（简单动态字符串）。

• SDS 不仅可以保存文本数据，还可以保存二进制数据。
• SDS 获取字符串长度的时间复杂度是 O(1)。
• SDS API 是安全的，拼接字符串不会造成缓冲区溢出。

1.2 list

1. 应用场景：消息队列（但是有两个问题：1. 生产者需要自行实现全局唯一 ID；2. 不能以消费组形式消费数据）等。

2. List 类型的底层数据结构是由双向链表或压缩列表实现的：

• 如果列表的元素个数小于 512 个（默认值，可由 list-max-ziplist-entries 配置），列表每个元素的值都小于 64 字节（默认值，可由 list-max-ziplist-value 配置），Redis 会使用压缩列表作为 List 类型的底层数据结构；
• 如果列表的元素不满足上面的条件，Redis 会使用双向链表作为 List 类型的底层数据结构；

3. 但是在 Redis 3.2 版本之后，List 数据类型底层数据结构就只由 quicklist 实现了，替代了双向链表和压缩列表。

1.3 hash

1. 应用场景：缓存对象、购物车等。

2. Hash 类型的底层数据结构是由压缩列表或哈希表实现的：

   • 如果哈希类型元素个数小于 512 个（默认值，可由 hash-max-ziplist-entries 配置），所有值小于 64 字节（默认值，可由 hash-max-ziplist-value 配置）的话，Redis 会使用压缩列表作为 Hash 类型的底层数据结构；

   • 如果哈希类型元素不满足上面条件，Redis 会使用哈希表作为 Hash 类型的底层数据结构。

3. 在 Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了。

1.4 set

1. 应用场景：聚合计算（并集、交集、差集）场景，比如点赞、共同关注、抽奖活动等。
2. Set 类型的底层数据结构是由哈希表或整数集合实现的：
   • 如果集合中的元素都是整数且元素个数小于 512 （默认值，set-maxintset-entries配置）个，Redis 会使用整数集合作为 Set 类型的底层数据结构；
   • 如果集合中的元素不满足上面条件，则 Redis 使用哈希表作为 Set 类型的底层数据结构。

1.5 zset

redis 127.0.0.1:6379> ZADD runoobkey 1 redis
(integer) 1
redis 127.0.0.1:6379> ZADD runoobkey 2 mongodb
(integer) 1
redis 127.0.0.1:6379> ZADD runoobkey 3 mysql
(integer) 1
redis 127.0.0.1:6379> ZADD runoobkey 3 mysql
(integer) 0
redis 127.0.0.1:6379> ZADD runoobkey 4 mysql
(integer) 0
redis 127.0.0.1:6379> ZRANGE runoobkey 0 10 WITHSCORES

1) "redis"
2) "1"
3) "mongodb"
4) "2"
5) "mysql"
6) "4"

1. 应用场景：排序场景，比如排行榜、电话和姓名排序等。
2. Zset 类型的底层数据结构是由压缩列表或跳表实现的：
   • 如果有序集合的元素个数小于 128 个，并且每个元素的值小于 64 字节时，Redis 会使用压缩列表作为 Zset 类型的底层数据结构；
   • 如果有序集合的元素不满足上面的条件，Redis 会使用跳表作为 Zset 类型的底层数据结构；
3. 在 Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了。
4. skiplist能够达到插入的时间复杂度为O(logn)，根据成员查分值的时间复杂度为O(1)

在score相同的情况下怎么办？

1. 在score相同的情况下，redis使用字典排序。

2. 将时间戳作为成员名的一部分，在应用层，你可以解析成员名并去掉时间戳，得到原始的成员名。

   1) "userid_1627384956000"
   2) "userid_1627384958000"
   3) "userid_1627384960000"

3. 将时间戳作为分数的一部分。整数是socre，小数是时间戳。

2.底层数据结构

2.1 简单动态字符串 - SDS

• 常数复杂度获取字符串长度

  由于 len 属性的存在，我们获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)。

• 杜绝缓冲区溢出

• 减少修改字符串的内存重新分配次数

  由于len属性和alloc属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略。

• 二进制安全
• 兼容部分 C 字符串函数

2.2 压缩列表 - ZipList

Ziplist 是内存紧凑型列表，节省内存空间、提升内存使用率。适用列表数量较少，元素size较小的场景。

1. 连续存储：Ziplist中的元素是连续存储的，不像普通的双向链表那样使用指针进行连接。这样可以减少指针的使用，从而节省内存。

2. 紧凑存储：Ziplist通过使用紧凑的存储格式，可以节省内存空间。它将不同长度的字符串和整数存储在一起，使用特定的编码方式进行压缩，从而减少了存储空间的占用。

3. 快速访问：由于Ziplist使用连续存储，可以通过偏移量（offset）快速访问到指定位置的元素，而无需像普通链表那样遍历。

2.3 快表 - QuickList

quicklist这个结构是Redis在3.2版本后新加的, 之前的版本是list(即linkedlist)， 用于String数据类型中。

它是一种以ziplist为结点的双端链表结构。 宏观上, quicklist是一个链表, 微观上, 链表中的每个结点都是一个ziplist。

2.4 哈希表 - HashTable

1. 解决哈希冲突

链地址法。通过字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点。

2. 扩容和收缩

当哈希表保存的键值对太多或者太少时，就要通过 rerehash(重新散列）来对哈希表进行相应的扩展或者收缩。

• 第一个ht[0] 长度为4，将ht[1]哈希表的大小设置为8。

• 将ht[0]包含的四个键值对都rehash到ht[1]，下标会变。

• 释放ht[0]，并将ht[1]设置为ht[0]，然后为ht[1]分配一个空白哈希表。（4个变成了8个）

3. 触发扩容的条件

负载因子 = 哈希表已保存节点数量 / 哈希表大小。一个大小为512，包含256个键值对的哈希表来说， 256 / 512 = 0.5

1. 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。

2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。

3. 另一方面，当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。

4. 渐近式 rehash

如果保存在Redis中的键值对只有几个几十个，那么 rehash 操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成Redis一段时间内不能进行别的操作。

渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

Redis采用渐进式 rehash，在渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行增加操作，一定是在新的哈希表上进行的。

2.5 整数集 - IntSet

整数集合（intset）是集合类型的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。

2.6 跳表 - ZSkipList

1. 跳跃表是一种平衡的数据结构：与平衡二叉搜索树相比，跳跃表的插入、删除和查找操作的平均时间复杂度都是O(log n)，其中n是元素的数量。
2. 跳跃表是一种有序数据结构：跳跃表中的元素是有序排列的，使得查找操作可以通过跳跃的方式快速定位到目标元素。
3. 跳跃表通过多级索引实现快速查找：跳跃表中的每一层都是原始链表的一个子集，每一级索引的元素数量逐渐减少。通过在不同级别之间跳跃，可以快速定位到目标元素。
4. 跳跃表支持高效的插入和删除操作：相比平衡二叉搜索树，跳跃表的插入和删除操作更加简单高效，不需要进行平衡操作，只需要更新索引层的指针即可。
5. 跳跃表相对简单易实现：相比其他平衡数据结构如红黑树等，跳跃表的实现相对简单，容易理解和实现。
6. 跳跃表相对于其他数据结构，可能会占用更多的内存空间来存储额外的索引层。

为什么Redis选择使用跳表而不是红黑树来实现有序集合?

Redis 中的有序集合(zset) 支持的操作：插入一个元素，删除一个元素，查找一个元素，有序输出所有元素，按照范围区间查找元素。

1. 按照区间来查找数据这个操作，红黑树的效率没有跳表高。按照区间查找数据时，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。
2. 跳表实现起来简单。

3. 新的数据对象

3.1 Bitmap （位存储）

2.2 版新增，二值状态统计的场景，比如签到、判断用户登陆状态、连续签到用户总数等；

Bitmap 即位图数据结构，都是操作二进制位来进行记录，只有0 和 1 两个状态。

两个状态的，都可以使用 Bitmaps！如果存储一年的打卡状态需要多少内存呢？ 365 天 = 365 bit 1字节 = 8bit 46 个字节左右！

3.2 HyperLogLogs（基数统计)

2.8 版新增，海量数据基数统计的场景，比如百万级网页 UV 计数等；

比如数据集 {1, 3, 5, 7, 5, 7, 8}， 那么这个数据集的基数集为 {1, 3, 5 ,7, 8}, 基数(不重复元素)为5。 基数估计就是在误差可接受的范围内，快速计算基数。

3.3 geospatial (地理位置)

3.2 版新增，存储地理位置信息的场景，比如滴滴叫车；

geo底层的实现原理实际上就是Zset。这个功能可以推算地理位置的信息: 两地之间的距离, 方圆几里的人。

3.4 Stream

5.0 版新增，消息队列，相比于基于 List 类型实现的消息队列，有这两个特有的特性：自动生成全局唯一消息ID，支持以消费组形式消费数据。

4. 头脑风暴

• 压缩链表的规律，每个元素都小于64字节。或者元素个数小于512个，zset是128个。

5. 参考资料

• https://github.com/ZhongFuCheng3y/3y#tvredis
• https://pdai.tech/md/db/nosql-redis/db-redis-x-rdb-aof.html
• https://segmentfault.com/a/1190000039208726
• https://www.pdai.tech/md/db/nosql-redis/db-redis-x-redis-ds.html
• https://www.jianshu.com/p/9d8296562806