关于后端:Redis基础剖析基础数据结构及其用法

这是一个系列的文章，打算把 Redis 的 根底数据结构 、 高级数据结构 、 长久化的形式 以及 高可用的形式 都讲一遍，公众号会比其余的平台提前更新，感兴趣的能够提前关注，「SH 的全栈笔记」，上面开始注释。

如果你是一个有教训的后端或者服务器开发，那么肯定据说过 Redis，其全称叫 Remote Dictionary Server。是由 C 语言编写的基于 Key-Value 的存储系统。说直白点就是一个 内存数据库，既然是内存数据库就会遇到如果服务器意外宕机造成的数据不统一的问题。

这跟很多游戏服务器也是一样的，感兴趣的能够参考我之前的文章游戏服务器和 Web 服务器的区别。其数据首先会流向内存，基于疾速的内存读写来实现高性能，而后定期将内存的数据中的数据落地。Redis 其实也是这么个流程，基于疾速的内存读写操作，单机的 Redis 甚至可能扛住 10 万的 QPS。

Redis 除了高性能之外，还领有丰盛的数据结构，反对大多数的业务场景。这也是其为什么如此受欢迎的起因之一，上面咱们就来看一看 Redis 有哪些 根底数据类型，以及他们底层都是怎么实现的。

其根底数据类型有String、List、Hash、Set、Sorted Set，这些都是罕用的根底数据类型，能够看到十分丰盛，简直可能满足大部分的需要了。其实还有一些高级数据结构，咱们在这章里临时先不提，只聊根底的数据结构。

String 能够说是最根底的数据结构了，用法上能够间接和 Java 中的 String 挂钩，你能够把 String 类型用于存储某个标记位，某个计数器，甚至狠一点，序列化之后的 JSON 字符串都行，其单个 key 限度为 512M。其常见的命令为get、set、incr、decr、mget。

get 获取某个 key，如果 key 不存在会返回空指针
set 给 key 赋值，将 key 设置为指定的值，如果该 key 之前曾经有值了，那么将被新的值给笼罩
incr 给以后的 key 的值 +1，如果 key 不存在则会先给 key 调用 set 赋值为 0，再调用incr。当然如果该 key 的类型不能做加法运算，例如字符串，就会抛出谬误
decr 给以后 key 的值 -1，其余的同上
mget 同 get，只是一次性返回多条数据，不存在的 key 将会返回空指针

可能大多数的人只是到用一用的境地，这也无可非议，然而如果是作为一个对技术有谋求的开发，或者说你有想近大厂的想法，肯定要有刨根问底的精力。只有当你真正晓得一个货色的底层原理时，你遇到问题时能力提供给你更多的思路去解决问题。接下来咱们就来聊一下 Redis 中 String 底层是如何实现的。

咱们晓得 Redis 是用 C 语言写的，然而 Redis 却没有间接应用，而是本人实现了一个叫 SDS（Simple Dynamic String）的构造来实现字符串，构造如下。

struct sdshdr {
  // 记录 buf 中已应用的字节数量
  int len;
  // 记录 buf 中未应用的字节数量
  int free;
  // 字节数组，用于保留字符串
  char buf[];}

为什么 Redis 要本人实现 SDS 而不是间接用 C 的字符串呢？次要是因为以下几点。

缩小获取字符串长度开销 C 语言中获取字符串的长度须要遍历整个字符串，直到遇到完结标记位\0，工夫复杂度为 O(n)，而 SDS 间接保护了长度的变量，取长度的工夫复杂度为 O(1)
防止缓冲区溢出 C 语言中如果往一个字节数组中塞入超过其容量的字节，那么就会造成 缓冲区溢出 ，而 SDS 通过保护free 变量解决了这个问题。向 buf 数组中写入数据时，会先判断残余的空间是否足够塞入新数据，如果不够，SDS 就会 重新分配 缓冲区，加大之前的缓冲区。且加大的长度等于新增的数据的长度
空间预调配 & 空间惰性开释 C 语言中，每次批改字符串都会重新分配内存空间，如果对字符串批改了 n 次，那么必然会呈现 n 次内存重新分配。而 SDS 因为冗余了一部分空间，优化了这个问题，将必然重新分配 n 次变为最多调配 n 次，而数据从 buf 中移除的时候，闲暇进去的内存也不会马上被回收，避免新写入数据而造成内存重新分配
保障二进制平安 C 语言中，字符串遇到\0 会被截断，而 SDS 不会因为数据中呈现了 \0 而截断字符串，换句话说，不会因为一些非凡的字符影响理论的运算后果

能够联合上面的图来了解 SDS。

总结一下就是下面列表的四个小标题，为了缩小获取字符串长度开销、防止缓冲区溢出、空间预调配 & 空间惰性开释和保障二进制平安。

List 也是一个应用频率很高的数据结构，其设计到的命令太多了，就不像 String 那样一个一个演示了，感兴趣的大家能够去搜一搜。命令有 lpush、lpushx、rpush、rpushx、lpop、rpop、lindex、linsert、lrange、llen、lrem、lset、ltrim、rpoplpush、brpoplpush、blpop、brpop，其都是对数组中的元素的操作。

List 的用处我认为次要集中在以下两个方面。

当作一般列表存储数据（相似于 Java 的 ArrayList）

用做异步队列

一般列表这个天然不用多说，其中寄存的必然业务中须要的数据，上面来着重聊一下 异步队列。

啥玩意，List 还能当成队列来玩？

List 除了能被用做队列，还能当作栈来应用。在下面介绍了很多操作 List 命令，当咱们用 rpush/lpop 组合命令的时候，实际上就是在应用一个队列，而当咱们用 rpush/rpop 命令组合的时候，就是在应用一个栈。lpush/rpop 和 lpush/lpop 是同理的。

假如咱们用的是 rpush 来生产音讯，当咱们的程序须要生产音讯的时候，就应用 lpop 从异步队列 中生产音讯。然而如果采纳这种形式，当队列为空时，你可能须要不停的去询问队列中是否有数据，这样会造成机器的 CPU 资源的节约。

所以你能够采取让以后线程 Sleep 一段时间，这样确实能够节俭一部分 CPU 资源。然而你可能就须要去思考 Sleep 的工夫，距离太短，CPU上下文切换可能也是一笔不小的开销，距离太长，那么可能造成这条音讯被提早生产（不过都用异步队列了，应该能够疏忽这个问题）。

除了 Sleep，还有没有其余的形式？

有，答案是blpop。当咱们应用 blpop 去生产时，如果以后队列是空的，那么此时线程会阻塞住，直到上面两种 condition。

达到设置的 timeout 工夫
队列中有音讯能够被生产

比起 Sleep 一段时间，实时性会好一点；比起轮询，对 CPU 资源更加敌对。

在 Redis3.2 之前，Redis 采纳的是 ZipList（压缩列表）或者 LinkedList（链表）。当 List 中的元素同时满足 每个元素的小于 64 字节 和List 元素个数小于 512 个 时，存储的形式为ZipList。凡是有一个条件没满足就会转换为LinkedList。

而在 3.2 之后，其实现变成了 QuickList（疾速列表）。LinkedList 因为是较为根底的货色，此处就不赘述了。

ZipList 采纳间断的内存紧凑存储，不像链表那样须要有额定的空间来存储前驱节点和后续节点的指针。依照其存储的区域划分，大抵能够分为三个局部，每个局部也有本人的划分，其具体的构造如下。

header ziplist 的头部信息
- zlbytes 标识 ziplist 所占用的内存字节数
- zltail 到 ziplist 尾节点的偏移量
- zllen ziplist 中的存储的节点数量
entries 存储理论节点的信息
- pre_entry_length 记录了前一个节点的长度，通过这个值能够疾速的跳转到上一个节点
- encoding 顾名思义，存储量元素的编码格局
- length 所存储数据的长度
- content 保留节点的内容
end 标识 ziplist 的开端

如果采纳链表的存储形式，链表中的元素由指针相连，这样的形式可能会造成肯定的 内存碎片。而指针也会占用额定的存储空间。而 ZipList 不会存在这些状况，ZipList 占用的是一段间断的内存空间。

然而相应地，ZipList 的批改操作效率较为低下，插入和删除的操作会设计到频繁的内存空间申请和开释（有点相似于 ArrayList 从新扩容），且查问效率同样会受影响，实质上 ZipList 查问元素就是遍历链表。

在 3.2 版本之后，list的实现就换成了 QuickList。QuickList 将 list 分成了多个节点，每一个节点采纳 ZipList 存储数据。

其用法就跟 Java 中的 HashMap 中一样，都是往 map 中去丢键值对。

根底的命令如下：

hset 在 hash 中设置键值对
hget 获 hash 中的某个 key 值
hdel 删除 hash 中某个键
hlen 统计 hash 中元素的个数
hmget 批量的获取 hash 中的键的值
hmset 批量的设置 hash 中的键和值
hexists 判断 hash 中某个 key 是否存在
hkeys 返回 hash 中的所有键（不蕴含值）
hvals 返回 hash 中的所有值（不蕴含键）
hgetall 获取所有的键值对，蕴含了键和值

其实大多数状况下的应用跟 HashMap 是差不多的，没有什么较为非凡的中央。

hash 的底层实现也是有两种，ZipList 和 HashTable。但具体采纳哪一种与 Redis 的版本无关，而与以后 hash 中所存的元素无关。首先当咱们创立一个 hash 的时候，采纳的 ZipList 进行存储。随着 hash 中的元素增多，达到了 Redis 设定的阈值，就会转换为 HashTable。

其设定的阈值如下：

存储的某个键或者值长度大于默认值（64）
ZipList 中存储的元素数量大于默认值（512）

ZipList 下面咱们专门简略剖析了一下，了解这个设定应该也比拟容易。当 ZipList 中的元素过多的时候，其查问的效率就会变得低下。而 HashTable 的底层设计其实和 Java 中的 HashMap 差不多，都是通过拉链法解决哈希抵触。具体的能够参考从根底的应用来深挖 HashMap 这篇文章。

Set 的概念能够与 Java 中的 Set 划等号，用于存储一个不蕴含反复元素的汇合。

其次要的命令如下，key 代表 redis 中的 Set，member 代表汇合中的元素。

sadd sadd key member [...] 将一个或者多个元素退出到汇合中，如果有曾经存在的元素会疏忽掉。
srem srem key member [...]将一个或者多个元素从汇合中移除，不存在的元素会被疏忽掉
smembers smembers key返回汇合中的所有成员
sismember dismember key member判断 member 在 key 中是否存在，如果存在则返回 1，如果不存在则返回 0
scard scard key返回汇合 key 中的元素的数量
smove move source destination member将元素从 source 汇合挪动到 destination 汇合。如果 source 中不蕴含 member，则不会执行任何操作，当且仅当存在才会从汇合中移出。如果 destination 曾经存在元素则不会对 destination 做任何操作。该命令是原子操作。
spop spop key随机删除并返回汇合中的一个元素
srandmember srandmember key与 spop 一样，只不过不会将元素删除，能够了解为从汇合中随机出一个元素来。
sinter 求一个或者多个汇合的交加
sinterstore sinterstore destination key [...]与 sinter 相似，然而会将得出的后果存到 destination 中。
sunion 求一个或者多个汇合的并集
sunionstore sunionstore destination key [...]
sdiff 求一个或者多个汇合的差集
sdiffstore sdiffstore destination key [...]与 sdiff 相似，然而会将得出的后果存到 destination 中。

咱们晓得 Java 中的 Set 有多种实现。在 Redis 中也是，有 IntSet 和HashTable两种实现，首先初始化的时候应用的是IntSet，而满足如下的条件时，就会转换成HashTable。

当汇合中保留的所有元素都是整数时
汇合对象保留的元素数量不超过 512

下面曾经简略的介绍了 HashTable 了，所以这里只聊聊 IntSet。

intset 底层是一个数组，既然数据结构是数组，那么存储数据就能够是有序的，这也使得 intset 的底层查问是通过二分查找来实现。其构造如下。

struct intset {
  // 编码方式
  uint32_t encoding;
  // 汇合蕴含元素的数量
  uint32_t length;
  // 存储元素的数组
  int8_t contents[];}

与 ZipList 相似，IntSet 也是应用的一连串的内存空间，然而不同的是 ZipList 能够存储二进制的内容，而 IntSet 只能存储整数；且 ZipList 存储是无序的，IntSet 则是有序的，这样一来，元素个数雷同的前提下，IntSet 的查问效率会更高。

其与 Set 的性能大抵相似，只不过在此基础上，能够给每一个元素赋予一个权重。你能够了解为 Java 的 TreeSet。与 List、Hash、Set 一样，其底层的实现也有两种，别离是ZipList 和SkipList（跳表）。

初始化 Sorted Set 的时候，会采纳 ZipList 作为其实现，其实很好了解，这个时候元素的数量很少，采纳 ZipList 进行紧凑的存储会更加的节俭空间。当期达到如下的条件时，就会转换为 SkipList：

其保留的元素数量的个数小于 128 个
其保留的所有元素长度小于 64 字节

上面的命令中，key 代表 zset 的名字；4 代表 score，也就是权重；而 member 就是 zset 中的 key 的名称。

zadd zadd key 4 member用于减少元素
zcard zcard key用于获取 zset 中的元素的数量
zrem zrem key member [...]删除 zset 中一个或者多个 key
zincrby zincrby key 1 member给 key 的权重值加上 score 的值（也就是 1）
zscore zscore key member用于获取指定 key 的权重值
zrange zrange key 0 -1获取 zset 中所有的元素，zrange key 0 -1 withscores获取所有元素和权重，withscores参数的作用是决定是否将权重值也一起返回。其返回的元素依照 从小到大 排序，如果元素具备雷同的权重，则会依照字典序排序。
zrevrange zrevrange key 0 -1 withscores，其与 zrange 相似，只不过 zrevrange 依照 从大到小 排序。
zrangebyscore zrangebyscore key 1 5，返回 key 中权重在区间 (1, 5] 范畴内元素。当然也能够应用 withscores 来将权重值一并返回。其元素依照 从小到大 排序。1 代表 min，5 代表 max，他们也能够别离是 -inf 和inf，当你不晓得 key 中的 score 区间时，就能够应用这个。还有一个相似于 SQL 中的 limit 的可选参数，在此就不赘述。

除了可能对其中的元素增加权重之外，应用 ZSet 还能够实现 提早队列。

提早队列用于寄存提早工作，那什么是提早队列呢？

举个很简略的例子，你在某个电商 APP 中下订单，然而没有付款，此时它会揭示你，「订单如果超过 1 个小时没有领取，将会主动敞开」；再比方在某个流动完结前 1 个小时给用户推送音讯；再比方订单实现后多少天主动确认收货等等。

用人话解释一遍，那就是过会才要干的事件。

那 ZSet 怎么实现这个性能？

其实很简略，就是将工作的执行工夫设置为 ZSet 中的元素权重，而后通过一个后盾线程定时的从 ZSet 中查问出权重最小的元素，而后通过与以后工夫戳判断，如果大于以后工夫戳（也就是该执行了）就将其从 ZSet 中取出。

那，怎么取？

其实我看很多讲 Redis 实现提早队列的博客都没有把这个怎么取讲清楚，到底该用什么命令，传什么参数。咱们应用 zrangebyscore 命令来实现，还记得 -inf 和 inf 吗，其全称是 infinity，别离示意无限小和无限大。

因为咱们并不知道提早队列当中的 score（也就是工作执行工夫）的范畴，所以咱们能够间接应用 -inf 和 inf，残缺命令如下。

zrangescore key -inf inf limt 0 1 withscores

还是有点用，那 ZSet 底层是咋实现的呢？

下面曾经讲过了 ZipList，就不赘述，上面聊聊 SkipList。

SkipList 存在于 zset（Sorted Set）的构造中，如下：

struct zset {
  // 字典
  dict *dict;
  // 跳表
  zskiplist *zsl;
}

而 SkipList 的构造如下：

struct zskiplist {
  // 表头节点和表尾节点
  struct zskiplistNode *header, *tail;
  // 表中节点的数量
  unsigned long length;
  // 表中层数最大的节点的层数
  int level;
}

不晓得大家是否有想过，为什么 Redis 要应用 SkipList 来实现 ZSet，而不必数组呢？

首先 ZSet 如果数组存储的话，因为 ZSet 中存储的元素是有序的，存入的时候须要将元素放入数组中对应的地位。这样就会对数组进行频繁的增删，而频繁的增删在数组中效率并不高，因为波及到数组元素的挪动，如果元素插入的地位是首位，那么前面的所有元素都要被挪动。

所以为了应酬频繁增删的场景，咱们须要应用到链表。然而随着链表的元素增多，同样的会呈现问题，尽管增删的效率晋升了，然而查问的效率变低了，因为查问元素会从头到尾的遍历链表。所有如果有什么办法可能晋升链表的查问效率就好了。

于是跳表就诞生了。基于单链表，从第一个节点开始，每隔一个节点，建设索引。其实也是单链表。只不是两头省略了节点。

例如存在个单链表 1 3 4 5 7 8 9 10 13 16 17 18

形象之后的索引为 1 4 7 9 13 17

如果要查问 16 只须要在索引层遍历到 13，而后依据 13 存储的上层节点（实在链表节点的地址），此时只须要再遍历两个节点就能够找到值为 16 的节点。

所以能够从新给跳表下一个定义，链表加多级索引的构造，就是跳表

在跳表中，查问任意数据的工夫复杂度是 O(logn)。工夫复杂度跟二分查找是一样的。能够换句话说，用单链表实现了 二分查找 。但这也是一种用 空间换工夫 的思路，并不是收费的。

对于 Redis 的根底数据结构和其底层的原理就简略的聊到这里，之后的几篇应该会聊聊 Redis 的高可用和其对应的解决方案，感兴趣的能够继续关注，公众号会比其余的平台都先更新。

往期文章：

大白话聊聊微服务——人人都能看懂的演进过程

简略理解 InnoDB 底层原理

浅谈 JVM 与垃圾回收

深刻理解 ConcurrentHashMap

【简略理解系列】从根底的应用来深挖 HashMap

如果你感觉这篇文章对你有帮忙，还麻烦 点个赞 ， 关个注 ， 分个享 ， 留个言

也能够微信搜寻公众号【SH 的全栈笔记】，当然也能够间接扫描二维码关注

关于后端:Redis基础剖析基础数据结构及其用法

1. 数据类型

2. String

2.1 应用

2.2 原理

2.2.1 构造

2.2.2 长处

3. List

3.1 应用

3.2 原理

3.2.1 ZipList

3.2.2 QuickList

4. Hash

4.1 应用

4.2 原理

5. Set

5.1 应用

5.2 原理

5.2.1 IntSet

6. Sorted Set

6.1 应用

6.2 原理

6.2.1 SkipList

End