likes
comments
collection
share

Redis 学习笔记-数据结构

作者站长头像
站长
· 阅读数 10

本文为极客时间《Redis 核心技术与实战》的学习笔记。

为什么要用Redis?

Redis 学习笔记-数据结构

从整个互联网的业务场景来看，读操作远远大于写操作是最普遍的情况。使用Redis作为缓存可以很好的解决这种业务场景，代价是：增加了代码量，引入了数据一致性问题。想要得到一些，总是要失去一些。与Redis带来的性能上的巨大提升，这些问题显得就没那么重要了。

使用Redis时主要有两个思路：

  1. 把Redis作为缓存使用；
  2. 把Redis作为存储使用；

这两者的区别在于，对于数据的持久性要求不同。通常情况下，我们会选择缓存来使用，这也是绝大多数业务场景的需要。

Redis的数据结构

Redis 学习笔记-数据结构

基础数据结构

简单的讲，Redis 的数据结构有五个常用类型：String（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Sorted Set（有序集合）。 在具体的使用场景中：

  1. String最常用的数据结构。常用，容易被滥用；存储少量数据时会导致内容浪费
  2. List用得很少，常见业务场景里几乎用不到列表。
  3. Set用的也很少，评论或者订阅关系的场景能用。
  4. Hash和Sorted Set是用的比较多的数据结构。Sorted Set稍微加工下可以用在很多场景下。比如：加权评论，弹幕等。

底层数据结构

Redis 学习笔记-数据结构

除了String的底层是简单字符串SDS结构，其他类型底层都有两种数据结构支持。Redis的配置列表中有一块配置信息是专门用来设置具体使用哪一个数据结构。比如：对于Hash而言，其底层会选择哈希表和压缩链表这两种数据结构。在配置文件中：

  • hash-max-ziplist-entries：表示用压缩列表保存时哈希集合中的最大元素个数。
  • hash-max-ziplist-value：表示用压缩列表保存时哈希集合中单个元素的最大长度。

对于一个Key，一旦超过其中一个阈值，Redis就会从压缩链表切换到哈希表，并且这个过程不可逆。一旦切到了哈希表，后续不会再切换回来。

问题：为什么Redis会有这种操作？

  1. Redis是一个内存级别的存储系统。对于计算机而言，内存的容量是比较昂贵的，不容易扩展的。我们的系统在使用内存的过程中，需要慎重再慎重，节约再节约。
  2. 归根结底，Redis的数据结构设计都是在尽可能的实现存储和效率上的一种平衡。简而言之，在时间可以接受的前提下尽量降低内存的开销。

Redis中常见的底层结构够：SDS，双向链表，哈希表，压缩链表，整数数组，跳表。其中SDS，压缩链表和跳表，需要展开一下。

SDS

SDS全称：简单动态字符串（Simple Dynamic String，SDS），是String类型的底层结构。C语言原生的字符串是非常难用的，Redis使用SDS代替了原生的字符串。相比较而言，它具有以下几个优势：

  1. 可以动态调整大小，避免内存浪费。
  2. 记录了字符串的长度，在执行len()方法时会效率极高，为O(1)。
  3. 二进制安全。SDS可以存储二进制数据，而不仅仅局限于字符数据。它不会因为字符串中包含null字符而提前终止。这是SDS最重要的特点。

SDS的整体数据结构比较简单，包括：

  1. buf：字节数组，保存实际数据。为了表示字节数组的结束，Redis 会自动在数组最后加一个“\0”，这就会额外占用 1 个字节的开销。
  2. len：占 4 个字节，表示 buf 的已用长度。
  3. alloc：也占个 4 字节，表示 buf 的实际分配长度，一般大于 len。

采用类似思想的还有：GO的切片。

问题延伸，为什么String类型容易浪费内存？

这个问题需要从三个角度来回答：

  1. SDS本身的数据结构需要额外的9个字节来存储结构信息。
  2. Redis的数据结构是层层嵌套的，每一层都需要额外的字节来存储信息。
  3. Redis使用的内存分配库jemalloc在分配内存是会多分配一些内存，避免频繁的内存分配。

详细而言： 第一点，我们上面已经讲过了。第二点参考下图：

Redis 学习笔记-数据结构

第三点，假如我们申请的内存为N个字节，那么jemalloc会分配 A（A大于N，小于N的2的幂次数） 个字节。

另外，SDS会分成三种分配方式：

  1. int，RedisObject会和SDS结合，不再多分配空间。
  2. embstr，当字符串小于44字节时，RedisObject会和SDS一起分配一块连续的内存。
  3. raw，当字符串大于44字节时，RedisObject会和SDS会分开存储，然后用指针相连。

压缩链表

压缩链表的结构如下：

Redis 学习笔记-数据结构

  • zlbytes，表示整个压缩链表占用的字节数。
  • zltail，指向压缩链表中最后一个压缩节点的偏移量。
  • zllen，表示压缩链表中包含的节点数量。
  • zlend，表示压缩链表的结束。
  • entry，用来存储数据的结构。

它的特点，换句话说，它是如何压缩数据降低内存开销的。

  1. 压缩链表的entry存储了元素的内容，长度，编码等，并且每个entry在内存中都是紧密排列的，这样就可以省下指针的内存开销。也就是说，压缩链表相对于双向链表而言，它压缩了指针所占用的开销。
  2. 压缩链表中可以存多个entry，相比String，它省下了大量的dictEntry的内存开销。
  3. 压缩链表的遍历效率并不低，但不适用于频繁插入或删除的场景，这是它的缺陷。压缩链表在插入或者修改数据时可能会导致连锁更新，即前后的entry都需要修改；会触发内存再分配。这都是长耗时操作。因此，当单个元素长度较小，整体内容较小时，Redis才会选择压缩链表作为底层存储结构。

跳表

跳表是少有的一个结构，最常用的场景就是redis的有序集合。它的原理如下：

Redis 学习笔记-数据结构

跳表的核心思想就是：加一层。通过加索引的方式，优化查询效率。整个过程就像在多级索引上跳来跳去，最后定位到元素。当数据量很大时，整个复杂度就O(logN)

需要注意的一个问题： 为什么不采用树或者红黑树，或者像MySQL一样采用B树？ 这个问题本质上问的是跳表和其他数据结构的差别。

这里有大佬的经典回答：news.ycombinator.com/item?id=117…

有两个核心问题：

  1. Redis的定位，也即问题的背景。Redis是一个内存数据库，在时间复杂度差不多的情况下，优先选择内存占用较小（也就是空间复杂度较低）的数据结构，而且相对而言跳表实现起来更简单。
  2. 跳表和树的区别，尤其是数据结构上的区别。 树需要大量的指针来记录节点信息，树越高，开销越大。跳表在这方面要好的多。在插入数据时，跳表可能会调整索引，树需要再平衡，各有特点。Redis在其中取了一个明恒

扩展结构

BitMap

Bitmap 本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型。String 类型是会保存为二进制的字节数组，所以，Redis 就把字节数组的每个 bit 位利用起来，用来表示一个元素的二值状态。你可以把 Bitmap 看作是一个 bit 数组。

Bitmap 常用于二值状态的业务场景，比如：用户是否登录，商品是否存在。

HyperLogLog

HyperLogLog 是一种用于统计基数的数据集合类型，它的最大优势就在于，当集合元素数量非常多时，它计算基数所需的空间总是固定的，而且还很小。日常用的比较少，了解即可。

GEO

GEO 是用于存储和处理地理位置信息的数据结构，跟地理位置相关的业务会用到这个结构。

Streams

Streams 是 Redis 专门为消息队列设计的数据类型，可以解决常见的消息队列问题。但是，我们有专门提供消息队列的组件：kafka，RocketMQ 等。

这里有一个常见问题：如何使用redis实现一个消息队列？实现一个延时消息队列？

全局哈希

存储结构

Redis的会使用一个全局哈希表来存储所有的Key，就像我们早期讲的GO的Map一样，它采用的也是拉链法。

Redis 学习笔记-数据结构

渐进式Rehash

就像我们之前聊过的，Map的装载的数量增加时，性能会下降。为了提高性能，会对Map进行扩容，Redis采用了渐进式Rehash的方式进行扩容：

  1. 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
  2. 渐进式扩容：Redis仍然正常处理客户端请求，每处理一个请求时，从哈希表1中的第一个索引位置开始，顺带着将这个索引位置上的所有entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的entries。整体思路与GoMap一致，其实大多数的Map都会采用渐进式扩容，这样可以保证在扩容的过程中，Map依然可以正常提供服务，只是性能低一点点。毕竟慢一点和不能用是两码事。
  3. 释放哈希表 1 的空间。

常用耗时情况

  1. 单元素操作（增删改查）往往都是非常快的。
  2. 遍历操作，尤其是对大KEY进行遍历操作，是非常非常慢的。绝大多数的数据结构遍历的复杂度都是O(N)，大多数公司的Redis安全生产手册上都不允许遍历元素，尤其是遍历Redis所有的Key。
  3. 获取某个集合里元素的个数，这个操作是效率非常高的。大多数结构中都会存储一个当前集合的总个数，因此不需要遍历统计。比如，压缩链表。

小工具

测算数据占用的内存空间：Redis容量预估-极数云舟