您的位置: 首页  >  文章  >  redis数据结构(redis为什么那么快的原因之一)

redis数据结构(redis为什么那么快的原因之一)

分类: 文章 • 2025-05-21 12:33:28

redis之所以快，也与它设计的数据结构有关。
参考自《redis设计与实现》

1字符串String

简单动态字符串SDS[Simple Dynamic String]

结构：

  1. int len;//SDS所保存的字符串长度//buf数组中已使用字节的数量
  2. int free;//buf数组中未使用的字节数量
  3. char buf[]//保存字符串

遵循C字符串以’\0’空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性

SDS与C字符串的区别
常熟复杂度获取字符串长度

C字符串不记录本身的长度信息，需要遍历，复杂度为O（N）

SDS在len属性中记录了字符串的长度

杜绝缓冲区溢出

C语言的strcat添加src字符串到dest字符串末尾，假定用户在执行这个函数时，已经为dest分配了足够的内存。如果该假设不成立，会导致缓冲区溢出（字符串后面的内存会被修改）

修改SDS时，API先检查SDS的空间是否满足修改所需的要求，如果不满足扩容（空间分配原则：当len小于IMB（1024*1024）时增加字符串分配空间大小为原来的2倍，当len大于等于1M时每次分配 额外多分配1M的空间）。

减少修改字符串时带来的内存重分配次数

C语言的字符串在strcat时，先使用内存重分配操作，扩展字符串空间再拼接（否则缓冲区

溢出）。在trim的截断操作时，程序通过内存重分配来释放字符串不再使用的那部分空间（否则内存泄漏）。

Redis作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串的长度都需要执行一次内存重分配的话，光执行内存重分配过程会很耗时。

通过使用未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略

  1. 空间预分配（减少连续执行字符串增长操作所需的内存重分配）

    如果修改后长度小于1MB（1024*1024），那么程序分配和len属性同样大小的free空间，即len等于free

    如果修改后SDS的长度大于等于1MB，free将为1MB

  2. 惰性空间释放

    sdstrim缩减字符串后只是修改字符串中的字符并修改free

二进制安全

C语言字符串中的字符必须符合某种编码（如ASCII），并且除了字符串的末尾之外，字符串里不能包含空字符，否则会被误认为是字符串结尾。这些限制使得只能保存文本数据，不能保存图片、音频、视频、压缩文件等二进制数据。

SDS的API都是二进制安全的，程序不会对buf的数据做任何限制、过滤或者假设，数据写入是什么样子读取什么样子。

使用SDS的buf属性成为字节数组，不是保存字符，而是二进制数据。通过len的属性的值来判断是否结束。

可以使用一部分<string.h>库中的函数

2链表

结点结构：先驱、后继、值

list结构：

  1. 头、尾、长度、
  2. dump函数用于复制链表节点保存的值、free函数用于释放链表节点保存的值、match函数用于比较节点保存的值和输入值是否相同

特性：双端、无环、带长度计数器、多态（通过dump、free、match函数）

3字典、映射（map）、关联数组

dictht（哈希表）结构：哈希表数组、哈希表大小、sizemask哈希表大小掩码用于计算索引值总是等于size-1、used 该哈希表已有节点数量

哈希表节点dictEntry结构：键、值、指向下一个节点

字典结构：type类型特定函数、privadata私有函数、哈希表数组ht（长度2）、rehashidx
索引当rehash不在进行时值为-1
type和privadata是针对不同类型的键值对，为创建多态字典设置
ht是一个包含两个项的数组，数组的每个项都是哈希表，一般情况只用ht[0]，只会在ht[0]进行rehash时使用ht[1]

哈希算法

键的hash值&sizemask计算索引值（也需要数组的长度的2的n次方）

解决键值冲突

链地址法、头插

rehash

哈希表保存的键值对太多或太少时，程序需对哈希表的长度进行扩展或收缩

步骤：

  1. 为字典ht[1]哈希表分配空间，如果是扩展操作ht[1]大小为ht[0].used*2直到大于等于used的2的n次方，如果是收缩，那么ht[1]大小为第一个大于等于ht[0].used的2的n次方冪
  2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面，rehash指重新计算键的哈希值和索引值，然后放在ht[1]的指定位置
  3. 当ht[0]的所有键值都迁移到ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]常见一个空白哈希表

何时自动扩展：
1.服务器没有执行BGSAVE或BGREWRITEAOF命令，并且哈希表的负载因子大于等于1、
2.正在执行前两个且负载因子大于等于5

何时收缩：扩展因子小于0.1

负载因子=ht[0].used/ht[0].size

渐进式rehash

分而治之

4跳跃表skiplist

一种有序的数据结构，通过每个节点中维持多个指向其他节点的指针从而达到快速访问节点的目的
平均logn最坏n复杂度的节点查找，还可通过顺序性操作批量处理节点
大部分情况效率媲美平衡树，并且实现更简单

链表的查询效率为O(n)，链表加多级索引可以增加查询效率，就是跳跃表

为什么用它

Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时, Redis就会使用跳跃表来作为有序集合健的底层实现。

​ 这里我们需要思考一个问题——为什么元素数量比较多或者成员是比较长的字符串的时候Redis要使用跳跃表来实现？

​ 从上面我们可以知道，跳跃表在链表的基础上增加了多级索引以提升查找的效率，但其是一个空间换时间的方案，必然会带来一个问题——索引是占内存的。原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值值和几个指针，并不需要存储对象，因此当节点本身比较大或者元素数量比较多的时候，其优势必然会被放大，而缺点则可以忽略。

结构

redis数据结构(redis为什么那么快的原因之一)

ps:这个跳跃表中存储了3个节点元素、其中左边是dummy空节点。

zskiplistList

结构：header指向跳跃表的表头节点、tail指向跳跃表的表尾节点、level记录层数最大的那个节点的层数(表头节点的层数不计算在内)、length跳跃表目前节点数目(表头节点不计算在内)

zskiplistNode

结构：

  1. level层节点中用L1、L2、L3等字样标记节点的各个层，每个层带有两个属性分别是前进指针和跨度。前进指针用于访问位于表尾方向的其他节点（从表头向表尾方向访问节点），而跨度记录了前进指针指向节点和当前节点的距离。这是个数组第n层的数组长度为n，存有n个level结构。
  2. backward后退指针：指向位于当前节点的前一个节点，在从表尾的遍历时使用
  3. score分值：double类型，在跳跃表中，节点按各自所保存的分值从小到大排序
  4. obj成员对象：指针，指向一个字符串对象，字符串对象保存着一个SDS

表头节点和其他节点的构造是一样的，但是后退指针、分值和成员函数这些属性不会被用到

跨度：用于记录两个节点间的距离，跨度越大相距越短，指向NULL的所有前进指针的跨度为0，跨度是计算排位(rank)的：查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分值相同的节点将将按照成员对象在字典序中的大小进行排序，

5整数集合

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

实现

  1. uint32_t encoding编码方式 INTSET_ENC_INT16
  2. uint32_t length元素数量 整数集合包含的元素数量，也是contents数组的长度
  3. int8_t contents[]保存元素的数组

contents数组中按值从小到大排序，且数组中不包含重复项

升级

好处：提升整数集合的灵活性(C语言是静态语言，避免类型错误一般不会将两个不同类型的值放在同一个数据结构里)、节约内存

不支持降级操作

6压缩列表

是列表键和哈希键的底层实现之一。列表项要么是小整数值，要么是长度比较短的字符串会使用压缩列表。在一块连续的内存中。使用压缩列表的好处除了节约内存之外，还有减少内存碎片的作用，我把这种行为叫做"合并存储"，也就是将很多小的数据块存储在一个比较大的内存区域。

压缩列表的构成

为了节约内存而开发的，是一系列特殊编码的连续内存块组成的顺序形数据结构。一个压缩节点可以保存一个字节数组或者一个整数值。

  1. zlbytes记录整个压缩列表占用的内存字节数，在对压缩列表进行内存重分配，或者计算zlend的位置时使用
  2. zltail记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过它可以确定表尾节点地址
  3. zllen记录压缩列表包含的节点数量，等于UINT16_MAX时，真实数目需要遍历
  4. entryX压缩列表包含的各个节点
  5. zlend特殊值0xFF，用于标记压缩列表的末端

节点的构成

  1. previous_entry_length 上一个节点的长度，单位为字节。通过它可以计算出前一个节点的起始地址。可以实现表尾到表头遍历
  2. encoding 节点content属性保存数据的类型以及长度。
  3. content 可以是小整数也可以是短字符串

连锁更新

特殊情况(由于previous_entry_length既可以是1字节也可以是5字节)下产生的连续多次空间扩展操作

情况不多见，更新节点数目不多对性能也不会造成影响

7对象

创建一个键值对时会创建两个对象分别储存键和值称为redisObject。它有三个属性

  1. type STRING(字符串对象)、LIST(列表对象)、HASH(哈希对象)、集合对象、有序集合对象
    对于redis数据库而言，键总是一个字符串对象，而值可以是各种
  2. encoding 决定ptr指向对象的底层实现数据结构，如REDIS_ENCODING_INTlong类型的整数\EMBSTR embstr编码的简单动态字符串(SDS)\RAW简单动态字符串\HT字典\LINKEDLIST双端链表\ZIPLIST压缩列表\INTSET整数集合\SKIPLIST跳跃表和字典
  3. ptr指向底层数据结构的指针

还有一个int refcount引用计数用于垃圾回收

还有一个unsigned lru属性记录对象最后一次被程序访问的时间

字符串对象

字符串对象的编码可以是int、raw或者embstr

  1. int编码：如果字符串对象保存的是整数，并且这个整数可以用long类型表示
  2. raw编码：如果字符串对象保存的是一个字符串，并且字符串长度大于32字节那么使用SDS保存，并且编码设置为raw
  3. embstr编码：如果字符串对象保存的是一个字符串，并且长度小于等于32字节，使用embstr编码。

embstr是专门用于短字符串的一种优化编码方式，这种编码和raw编码一样都使用redisObject和sdshdr结构表示字符串对象。但是raw编码会调用两次内存分配分别创建redisObject和sdshdr结构而embstr编码使用一次内存分配函数来分配一块连续的空间。

embstr比raw的优势：创建所需内存次数从两次变到一次、内存释放次数从两次变到一次、embstr字符串对象的数据在一块连续的内存里面，更能利用缓存带来的优势。

小数是以字符串形式保存的

列表对象

列表对象的编码可以是ziplist或者linkedlist

编码转换

满足下列两个条件时，列表对象使用ziplist编码(这两个条件的上限值可以通过配置文件修改)：

  1. 列表对象保存的所有字符串元素的长度都小于64字节
  2. 列表对象保存的元素数量小于512个

哈希对象

哈希对象的编码可以是ziplist或者hashtable

  1. ziplist：

    当有新的键值对进来时，先把保存了键的压缩列表节点压入尾，随后把保存了值的压缩列表节点压入尾。因此保存了一对键值的两个节点是挨在一起的，并且先添加的在表头方向

  2. hashtable：

    使用字典作为底层实现。哈希对象中的每个键值对都使用一个字典键值对来保存。且字典的键和值都是字符串对象

编码转换

满足下列两个条件时，哈希对象使用ziplist编码(这两个条件的上限值可以通过配置文件修改)：

  1. 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
  2. 哈希对象保存的键值对数量小于512个

集合对象

集合对象的编码可以是intset或者hashtable

  1. intset：

    暂时无

  2. hashtable：

    hashtable编码的集合使用字典作为底层实现，字典的每个键都是一个字符串对象，而字典的值全部被设置为NULL。

编码转换

满足下列两个条件时，集合对象使用intset编码(这两个条件的上限值可以通过配置文件修改)：

  1. 集合对象保存的都是整数值
  2. 集合对象保存的元素数量不超过512个

有序集合对象

Redis 有序集合和集合一样也是 string 类型元素的集合,且不允许重复的成员。
不同的是每个元素都会关联一个 double 类型的分数。redis 正是通过分数来为集合中的成员进行从小到大的排序。
有序集合的成员是唯一的,但分数(score)却可以重复。

有序集合对象的编码可以是ziplist或者skiplist

  1. ziplist：

    第一个节点保存元素的成员，第二个元素则保存元素的分值，且按照分值排序

  2. skiplist：

    zset结构作为底层实现，一个zset结构同时包含一个字典+一个跳跃表。

    跳跃表的一个节点保存一个集合元素：跳跃表节点的object属性保存了元素的成员，而跳跃表节点的score属性则保存了元素的分值。可以通过跳跃表的api实现ZRANK、ZRANGE等命令

    字典为有序集合创建了一个成员到分值的映射，字典的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值保存了元素的分值(score)。通过字典，可以用O(1)复杂度查找给定成员的分值，ZSCORE命令就是根据这一特性实现的。

    有序集合的每个元素的成员都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。

    虽然zset结构同时使用跳跃表和字典来保存有序集合元素，但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以不会产生任何重复成员或者分值，也不会因此浪费内存。

    为什么要同时使用两种？因为跳跃表good at ZRANK、ZRANGE，而字典good at 根据成员查找分值

编码转换

满足下列两个条件时，有序集合对象使用ziplist编码(这两个条件的上限值可以通过配置文件修改)：

  1. 有序集合保存的元素数量小于128个
  2. 有序集合保存的所有元素成员的长度都小于64字节

内存回收

C语言并不具备自动回收内存的功能，所以redis在自己的对象系统中构建了一个引用计数技术实现的内存回收机制，可以通过追踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。

redisObject中还有一个int refCount引用计数。

  1. 在创建一个新对象时，引用计数被初始化为1
  2. 被一个新程序使用时，引用计数加一
  3. 不再被一个新程序使用时，引用计数减一
  4. 对象的引用计数变为0时，对象所占用的内存会被释放

对象共享

引用计数属性还带有对象共享的作用。可以节约内存

举例子：假设键A创建了一个包含整数值100的字符串对象作为值对象，如果键B也要创建一个同样保存了整数值100的字符串对象作为值对象，那么服务器就让键A和键B共享同一个字符串。

共享的步骤：

  1. 将数据库键的值指针指向一个现有的值对象
  2. 将被共享的值对象的引用计数增加1

目前来说，redis会在初始化服务器时创建一万个字符串对象，从0到9999的所有整数，所以set A 100 ，OBJECT REFCOUNT A的结果是2

redis只对包含整数值的字符串对象进行共享，因为如果验证整数值字符串的复杂度是O(1)，而验证字符串对象的复杂度就是O(N)，验证共享对象的复杂度将会是O(N的平方)。尽管可以节约更多空间，但是会消耗更多的CPU时间。

对象的空转时长

redisObject中lru属性记录了对象最后一次被命令程序访问的时间

相关推荐