redis-重点
五大基本类型、三种特殊类型
Redis 共有 5 种基本数据类型:String(字符串)、List(列表)、Set(集合)、Hash(散列)、Zset(有序集合),可供用户定义和使用。
除了 5 种基本的数据类型之外,Redis 还支持 3 种特殊的数据类型:Bitmap、HyperLogLog、GEO。
String
最简单的 k-v 形式,v 的字符串是 redis 自己实现的一种数据结构简单动态字符串 SDS,特点是除了可以保存文本数据,还可以保存二进制、整型数据。
由于是最简单的 k-v 形式,用于存储“占位”信息很方便,比如 token、access 等。
而 String 如果是整型的 value,还可以直接使用计算方法,因此需要计数时也很好用。
除此之外,直接存序列化后的对象字符串也可以,比 Hash 省空间。
其底层实现为:SDS。
List
Redis 中的 List,底层是链表的形式存的,Redis 自己实现了一个双向链表(虽然最终不直接使用双向linkedList)用来存 List。
相比起 String 最简单的 k-v 一个对一个的形式,List 则是一个 k 对应多个 v,多个 v 就以双向链表的形式存在。如图:

自带的 LRANGE 很适合分页查询。
但是注意,List 归根结底从来只有一个 k,所以对 List 设置的 ttl 会覆盖整个 v 双向链表。
底层实现:quickList
双向 linkedList,每个节点都维护前驱、后继节点太浪费空间,而且缓存不友好。
quickList 则不再使用一个节点单独维护,而是把一部分连续的元素聚合成列表,列表再独享一个,然后列表之间再组成链表
比如这样:
1 | /===========================================================\ |
这样最大的好处,就是灵活:一个节点要插入、删除、修改,那么只操作其中一个 quickListNode 的 list 即可,其余节点则不需要再操作了。
Hash
Hash 不再是简单的一个 k,而是多个 String 的 k-v 对形式,如图:

可以看到,一个 Hash 内不包含了若干 k-v 对,每个 k-v 对享受独立的 ttl,这是和 List 不同的。
当然,Hash 更适合的是映射一个对象。
底层实现:ListPack+链表
其实 Hash 就和 Java 的 HashMap 差不多,如今 redis 的 Hash 有两种底层实现,分别是 ListPack、HashTable。
ListPack 最简单,它竟然直接把每一对 k-v 同时存到一个线性表里,即 [k0, v0, k1, v1, ..., kn, vn],这种方式适合于少量的 k-v,节省时空消耗,但是不适合量大的情况。
HashTable 和 Java 里的没区别,线性表+链表,先算哈希值存入 Dict,等发生哈希冲突了再转链表。
两种方法会从 ListPakc 到 HashTable 单向切换,k-v 对数超过 512;或者某个 k、v 的字符数超过默认 64 字节时就会发生转变,且不会再降级为 ListPack。
为什么要设置 64 字节?因为 ZipList 本质上是连续分配的线性表,每个格子大小就是 64 字节,如果要存超过 64 字节的元素,要么截断,要么占用下一个格子两个格子一起存一个元素,但是那是不允许的,所以要转成链表,链表的节点大小可以动态分配,才能容纳超过 64 字节的元素。
Set
Set 也是一个 k-v 形式,但是类似于 List、区别于 Hash:Set 也是一个 k 对应多个 v 的形式,v 却是以集合方式存在,如图:

可以看到,相比起 List 每个 v 对应索引,Set 完全不含,因为 Set 不是有序的,而只是用于表达:一群不重复的元素,和所有语言中的 set 概念一样。
Set 可以很轻松地处理需要求交集、并集的场景,比如朋友圈点赞、评论的用户,其他用户看到好友、非好友的时候,展示不同的昵称。
和 List 一样,ttl 覆盖所有元素。
底层实现:Intset + HashTable
和 Hash 一样,数据量小(默认512)的时候,用有序的线性表直接存每个元素。数据量大了之后转 HashTable。
Set 怎么实现去重?数据量小的时候,线性表直接二分查找看有没有一模一样的,这就是为什么要保持有序。
而如果是 HashTable 就简单了,发生哈希冲突时,直接丢弃新来的。
ZSet
ZSet 就是 Sorted Set,是有序的,如图所示:

可以看到,比起 Set 的 v 只含元素,ZSet 的每个元素包含另一个因素:score,按照 score 排序。
但是需要注意,元素不能相同,但 score 可以相同。
应用场景:需要排行的场景。
todo:底层实现:ZipList + SkipList
和其他类型一样,数据量小和数据量大的时候分别用不同的结构,ZipList 和 SkipList。
ZipList 本质上就是一个线性表,根据 score 有序地同时存元素和 score,比如 [v1, 10, v2, 20, v3, 30, ......],当然,最大存储元素为 128,数据量超过时,或者有元素大于 64 个字节时,单向转为 SkipList。
再来看 SkipList,我们直接手写一个跳表。假设有 8 个元素,已经根据 score 有序排列了:
1 | list: A:1 -> B:2 -> C:3 -> D:4 -> E:5 -> F:6 -> G:7 -> H:8 -> null |
二分地建立一节索引:
1 | index1: 2 -> 4 -> 6 -> 8 |
再对 index1 建立二级索引:
1 | index2: 4 -> 8 |
BitMap
位图,用 1、0 表示某种状态,且直接用的二进制,很省空间。
底层是 string 类型你敢信吗,基于 SDS 但是不读取为 string,只关注其中二进制。
场景:例如统计活跃用户、标识用户点赞过等。
HyperLogLog
并非 redis 的显式类型,而是一种算法,redis 只是实现了部分功能。
其形式也是多 k-v 形式的,k 可以视作某种标签,v 则是数量。
HyperLogLog 的真正优势在于空间花销,只需要 12k 的空间就能存储接近2^64个不同元素,但是带来了错误率,有一定的计数误差。
Redis 性能
Redis 为什么快?
纯内存操作;
单线程模型,虽然 redis 服务是单线程,但是实现了多路 I/O 复用,所以既有性能又有安全;
数据类型的底层实现性能异常优秀;
Redis 自有的 RESP (REdis Serialization Protocol) 协议简单高效。
底层
Redis 底层的数据结构性能非常优秀,重点的有 Rehash、SkipList、QuickList 等。
SDS
SDS 本质上是一个包含字符数组的对象,它显式地记录了自己的长度(所以可以实现 O(1) 级别的长度获取);并且遍历时严格按照 for(strlen)而非遇到 ‘\0’ 时结束(这使其二进制安全)。
除此之外,它还在空间分配和释放时作出改进。分配空间时,会尝试分配更多空间,字符数组小于 1mb 时分配两倍空间、大于 1mb 时多分配 1mb,这使得空间不足的问题得到较好解决。而在释放上,SDS 遵循绝不减少空间、只增加空间的策略,除非把我杀掉。
为什么不使用 C 语言写的 char* ?因为恰好不满足 SDS 的四个优点,甚至还有缺陷。比如需要遍历 O(n) 才能得到 strlen、遇到 ‘\0’ 才结束导致二进制不安全、频繁 malloc、容易空间不足导致出问题。
Dict & Rehash
Dict 字典,可以用于维护一个哈希表;Rehash 则赋予哈希表重新分配长度的能力。Set、Hash、ZSet 都用到了 Dict 和 Rehash。
Rehash 这种数据结构有一点有意思,其扩容是渐进式的。什么意思?一张 dict 的长度,如果我们知道它最终会成长为千亿级别,但是仅仅在现在,它的长度还用不到那么高,显然直接给这个 dict 分配千亿长度很蠢,它应该只满足现在的需求,然后慢慢成长。
渐进式扩容,dict0 不够用了,就申请一个 dict0 两杯长度的 dict1,dict0 的元素重新计算哈希值加入 dict1,全部计算完后 dict0 释放,dict1 就是新的 dict0。
[TODO]
单线程模型
Redis 6.0 前
Redis 用 IO 多路复用监听 socket 处理客户端请求,由于全是内存操作,所以性能极为优异;而又因为 Redis 使用一个主要单线程处理所有就绪的 socket,因此甚至不需要担心并行下的锁问题,本质上是极快的串行。
捋一下逻辑,我们假设一个 redis 服务连接了若干个客户端,客户端随时有可能找 redis 读写,但是 redis 主线程只管读写数据,不管连接、请求、收发,这些谁来管?其实是操作系统内核的活。
客户端要和 Redis 建立长连接,向下请求 Linux 内核帮忙,内核查看 redis 连接没有问题,就维护一个Socket 文件描述符(fd),表示已经和 redis 连接好了,有什么事把消息发到 socket 缓冲区,内核通知 redis 就行。所以这个时候,redis 还没有真正开始干活。
当然,redis 知道有客户端和自己连接了也不是什么都不干,它会把这个 socket 加入到自己的文件事件处理器(file event handler),其中不仅通过多路 IO 的方式监听了多个 socket,还能够将每个 socket 的请求精确分配到与之关联的不同处理器。
