Redis 内部编码与优化方式

Redis 内部编码与优化方式

前言

redis 为每种数据类型都提供了多种内部编码方式,以散列类型为例,通过散列表实现散列类型,此时查找和赋值操作时间复杂度为 O(1),但是当键中元素很少时,O(1)的性能并不会比 O(n)有明显的性能提高。所以此时 redis 会使用一种比较紧凑但是性能稍差的内部编码方式,内部编码方式对于开发者来说是透明的,当键中元素变多时,redis 就会自动调整内部编码方式,转换为散列表。

查看一个键的内部编码方式可以使用 OBJECT ENCODING

127.0.0.1:6379> HSET Person name Jack age 21
(integer) 2
127.0.0.1:6379> OBJECT ENCODING Person
"ziplist"
127.0.0.1:6379> SET key value
OK
127.0.0.1:6379> OBJECT ENCODING key
"embstr"

redis 的每个键值都是用一个 redisObject 结构体存储的,如下

typedef struct RedisObject {
    unsigned type:4; // 数据类型
    unsigned encoding:4; // 内部编码方式
    unsigned lru:LRU_BITS; // LRU信息,用于缓存淘汰策略
    int refcount; // 引用计数
    void *ptr; // 指向实际的数据
} robj;

各个字段的释义

  • type:表示 RedisObject 所存储数据的类型。例如,字符串类型的值对应的 type 为 REDIS_STRING,哈希类型的值对应的 type 为 REDIS_HASH,以此类推。

    // RedisObject结构中type字段的取值
    #define REDIS_STRING 0
    #define REDIS_LIST 1
    #define REDIS_HASH 2
    #define REDIS_SET 3
    #define REDIS_ZSET 4
    #define REDIS_HASHMAP 5
    #define REDIS_MODULE_VALUE 6
    #define REDIS_MODULE_HASH 7
    #define REDIS_MODULE_LIST 8
    #define REDIS_MODULE_SET 9
    #define REDIS_MODULE_ZSET 10
  • encoding:表示 RedisObject 实际数据的内部编码方式。不同的数据类型有不同的编码方式,如字符串可以有 int 编码、embstr 编码和 raw 编码等。

    // RedisObject结构中encoding字段的取值
    #define REDIS_ENCODING_RAW 0         /* Raw encoding */
    #define REDIS_ENCODING_INT 1         /* Encoded as integer */
    #define REDIS_ENCODING_HT 2          /* Encoded as hash table */
    #define REDIS_ENCODING_ZIPMAP 3      /* Encoded as zipmap */
    #define REDIS_ENCODING_LINKEDLIST 4  /* Encoded as regular linked list */
    #define REDIS_ENCODING_ZIPLIST 5     /* Encoded as ziplist */
    #define REDIS_ENCODING_INTSET 6      /* Encoded as intset */
    #define REDIS_ENCODING_SKIPLIST 7    /* Encoded as skiplist */
    #define REDIS_ENCODING_EMBSTR 8      /* Embedded sds string encoding */
    #define REDIS_ENCODING_QUICKLIST 9   /* Encoded as linked list of ziplists */
    #define REDIS_ENCODING_STREAM 10     /* Encoded as a radix tree of listpacks */
  • lru:用于实现 Least Recently Used(LRU)算法的信息,用于过期策略。LRU 信息记录了最后一次访问该对象的时间,用于判断对象是否过期。

  • refcount:引用计数,用于管理对象的生命周期。当对象被引用时,引用计数会增加;当对象不再被引用时,引用计数会减少。当引用计数为 0 时,对象会被释放。

  • ptr:指向实际数据的指针。根据不同的数据类型和编码方式,指针可能指向不同的数据结构。

各个数据类型可能采用的内部编码方式以及执行 OBJECT ENCODING命令的结果如下表所示

内部编码(encoding) 释义 OBJECT ENCODING 命令结果
REDIS_ENCODING_RAW 原始编码,将字符串以字节数组形式存储 “raw”
REDIS_ENCODING_INT 整数编码,将字符串转换为整数并以整数形式存储 “int”
REDIS_ENCODING_HT 哈希表编码,用于表示哈希类型的值 “hashtable”
REDIS_ENCODING_ZIPMAP 压缩哈希编码,使用紧凑的字节数组存储键值对 “zipmap”
REDIS_ENCODING_LINKEDLIST 链表编码,用双向链表存储列表类型的值 “linkedlist”
REDIS_ENCODING_ZIPLIST 压缩列表编码,使用紧凑的字节数组存储列表类型的值 “ziplist”
REDIS_ENCODING_INTSET 整数集合编码,用于表示集合类型的值,采用有序整数数组存储 “intset”
REDIS_ENCODING_SKIPLIST 跳跃表编码,用于表示有序集合类型的值,使用跳跃表和哈希表 “skiplist”
REDIS_ENCODING_EMBSTR 嵌入式字符串编码,适用于长度较短的字符串,将字符串和长度信息连续存储在一起 “embstr”
REDIS_ENCODING_QUICKLIST 快速列表编码,使用一种特殊的数据结构快速地存储和操作列表类型的值 “quicklist”
REDIS_ENCODING_STREAM 流编码,使用基于有序整数数组的基数树数据结构存储流类型的值 “stream”

字符串类型

存储结构优化

redis 使用一个 sdshdr 类型的结构存储字符串,redisObject 的 ptr 字段指向的就是该变量的地址。

sdshdr 是用于表示简单动态字符串(Simple Dynamic String)的结构体。它的定义如下:

typedef struct sdshdr {
    // buf指向字符串的实际内容
    // 在buf中存储的字符串以空字符'\0'结尾
    // buf的长度可以通过sdslen获取,不包括结尾的'\0'
    char *buf;
    // 字符串长度
    // 不包括结尾的'\0'
    int len;
    // 字符串的容量
    // 等于buf中分配的内存空间的长度
    int free;
} sdshdr;

sdshdr 结构体包含了三个字段:

  1. buf:指向字符串的实际内容。字符串以空字符’\0’结尾,buf 的长度可以通过 sdslen获取,不包括结尾的’\0’。
  2. len:表示字符串的长度,即不包括结尾的’\0’的字符个数。
  3. free:表示字符串的容量,即 buf 中分配的内存空间的长度。容量减去长度就代表还有多少空闲空间可用。

存储结构如下

image-20240110221810418

而当键值内容可以用一个 64 位有符号整数表示时,redis 会将键值转为 long 类型来存储,比如 SET key 123,存储结构就变为下图,与之前相比大大节省了存储空间。

image-20240110221940019

共享对象池

redisObject 的 refcount 字段存储了引用次数,即一个键值可以被多个键引用。

在 Redis 中,共享对象池用于管理和复用一些常用的数据结构对象,以减少内存碎片和提高性能。这些共享对象通常是一些常量字符串、整数对象等,它们在 Redis 内部会被频繁使用。

Redis 为小整数(通常范围在[-10000, 10000])维护一个整数对象池。当存储整数值时,Redis 尽量使用已存在的整数对象,而不是创建新的对象。这减少了内存占用和提高了性能。比如 SET key 123,可以直接引用共享对象而不需要创建新的 redisObject 了。

共享对象的引用次数在 Redis 内部管理,开发者在使用 Redis 时通常不需要直接操作这些引用次数。引用次数的增加和减少是由 Redis 内部的引用计数机制自动处理的,确保共享对象在不再被引用时能够被正确释放和回收内存。

当配置了 maxmemory 来限制 redis 最大可用内存时,redis 不会使用共享对象,因为对于每一个键值都需要 redisObject 来记录其 lru 信息。

为什么没有字符串对象池

共享对象池中一个关键操作是判断对象是否相等。

Redis中只有整数类型的对象池,是因为整数的比较算法的时间复杂度是O(1),也只保留了10000个整数为了防止对象池的过度浪费。

相对而言,字符串的比较算法的时间复杂度是O(n),特别是长字符串的比较更加消耗性能。

而且,整数类型被重复使用的概率很大,字符串被重复使用的概率相比就会小很多很多,所以在Redis中只用整数类型的对象共享池。

作者:黑马程序员
链接:https://www.zhihu.com/question/615359314/answer/3169551903
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

embstr 与 raw

在 redis3.0 版本中,引入了 REDIS_ENCODING_EMBSTR 字符串编码方式,该编码方式与 REDIS_ENCODING_RAW 类似,都是使用 sdshdr 结构实现的,区别是 embstr 使用连续的内存块来存储 redisObject 和 sdshdr,这样分配和释放 embstr 内存都只需要一次操作,但是当 embstr 中的字符串值长度超过预先分配的空间时,需要重新分配内存块来扩展空间。而 raw 则可以根据需要动态地分配和释放内存空间。因此在存储长度较短的字符串情况下性能优于 raw。

embstr 适用于长度较短的字符串,可以节省内存空间并提高性能。而 raw 适用于长度较长的字符串,可以动态地分配和释放内存空间。

散列类型

散列(Hash)类型的内部编码方式有两种主要形式,分别是 ziplisthashtable

REDIS_ENCODING_HT 编码即散列表,可以实现 O(1)时间复杂度的查找和赋值操作,其字段和值也是用 redisObject 存储的,所以优化方式与字符串类型相同。

REDIS_ENCODING_ZIPLIST 底层使用 ziplist 存储数据,在配置文件中可以定义使用 REDIS_ENCODING_ZIPLIST 方式编码的时机。满足下面这两个条件,Redis 就会选择使用 ziplist编码方式,否则使用 hashtable

  1. hash-max-ziplist-entries:

    • 这个配置项定义了一个散列类型(hash)使用 ziplist编码的最大键值对数量阈值。
    hash-max-ziplist-entries 512
  2. hash-max-ziplist-value:

    • 这个配置项定义了一个散列类型使用 ziplist编码的最大值的阈值。
    hash-max-ziplist-value 64

通过调整这两个配置项,可以根据的实际使用场景和性能需求来设定阈值。较小的 hash-max-ziplist-entrieshash-max-ziplist-value值将导致更多的散列使用 ziplist编码,减小内存开销,但可能牺牲一些性能。较大的值则可能提高性能,但会增加内存占用。

ziplist

REDIS_ENCODING_ZIPLIST 是一种紧凑的编码格式,使用压缩列表存储键值,压缩列表是一种紧凑的、连续存储的字节数组,可以在一定程度上节省内存空间。查找和插入的时间复杂度都是 O(n),所以适用于元素较少的情况。内存结构如下图,存储方式是元素 1 存储字段 1,元素 2 存储值 1,以此类推。

ziplist 的字段描述

  • zlbytes:压缩列表的总字节数。该字段表示整个压缩列表所占用的内存空间大小。
  • zltail:压缩列表尾部的偏移量。该字段表示压缩列表中最后一个字节的索引位置。通过这个偏移量,可以快速定位到压缩列表的尾部。
  • zllen:压缩列表中的字段数量。该字段表示压缩列表中键值对的个数。

元素的字段描述

  • 前一个元素的大小(PrevEntrySize):该字段用于记录前一个元素(键值对)的字节数。它的作用是在遍历压缩列表时,可以通过该字段的值来快速定位到前一个元素的起始位置。如果前一个元素的大小为 0,则表示当前元素是第一个元素。
  • 当前元素的编码类型(EncodingType):该字段表示当前元素的编码方式,用于标识当前元素是字符串、整数还是其他类型。不同的编码类型有不同的编码方式和存储结构。
  • 当前元素的大小(EntrySize):该字段记录了当前元素的字节数。它表示当前元素的内容占用的字节数,包括键的长度、键的内容、值的长度和值的内容。
  • 当前元素的内容(EntryContent):该字段存储了当前元素的实际内容,包括键的内容和值的内容。具体的内容格式和编码方式取决于当前元素的编码类型。

image-20240110225443593

列表类型

列表类型内部编码方式可能是 REDIS_ENCODING_LINKEDLIST 和 REDIS_ENCODING_ZIPLIST。REDIS_ENCODING_LINKEDLIST 即双向链表,链表中每个元素都是用 redisObject 存储的,因此此种编码方式下的优化与字符串类型的键值相同。

REDIS_ENCODING_ZIPLIST 在列表类型的具体表现与散列类型相同,同样可以通过配置项 list-max-ziplist-entrieslist-max-ziplist-value 进行配置使用 REDIS_ENCODING_ZIPLIST 编码的时机。这两个配置项分别定义了列表使用 ziplist 编码的最大节点数量和最大值的阈值。

  1. list-max-ziplist-entries:

    • 这个配置项定义了一个列表使用 ziplist 编码的最大节点数量的阈值。
    list-max-ziplist-entries 512
  2. list-max-ziplist-value:

    • 这个配置项定义了一个列表使用 ziplist 编码的最大值的阈值。
    list-max-ziplist-value 64

quicklist

为了兼顾压缩列表和双向循环列表的优点,Redis 引入了 REDIS_ENCODING_QUICKLIST 编码方式。

quicklist 将大的列表分割成多个小的压缩列表节点,每个节点都是一个压缩列表或双向循环列表。这种方式可以在保持内存紧凑性的同时,减少对整个列表的遍历和操作的时间复杂度。

1、Quicklist 将大的列表划分成多个节点。每个节点都是一个独立的数据结构,可以单独进行操作。这样就将列表的操作范围缩小到了节点级别,而不需要遍历整个列表。通过维护每个节点的元素数量和索引范围,可以根据索引快速定位到需要的节点。这样在进行遍历或操作时,可以直接定位到包含目标元素的节点,而不需要遍历其他节点。

2、Quicklist 可以根据列表的动态变化进行优化和切换。当列表较小或元素较小时,可以使用压缩列表节点,以节省内存。而当列表较长或元素较大时,可以使用双向循环列表节点,以提高插入和删除操作的性能。Quicklist 的混合编码方式允许根据实际情况选择合适的节点类型。

集合类型

集合类型的内部编码方式可能是 REDIS_ENCODING_HT 和 REDIS_ENCODING_INTSET。

当集合中所有元素都是整数且元素的个数小于配置文件中的 set-max-intset-entries指定值时,会使用 REDIS_ENCODING_INTSET 存储集合,否则使用 REDIS_ENCODING_HT。

以下是 Redis 中整数集合的结构体定义:

typedef struct intset {
    uint32_t encoding;   // 编码方式,表示整数集合的类型
    uint32_t length;     // 集合中元素的数量
    int8_t contents[];   // 存储元素的数组
} intset;

REDIS_ENCODING_INTSET 提供了高效的查找操作,因为整数集合是有序的,可以使用二分查找算法,找操作的时间复杂度是 O(log n)。

但由于整数集合中的元素是有序的,插入和删除元素需要移动其他元素的位置来保持有序性。这可能涉及到元素的搬移操作,因此插入和删除元素的时间复杂度为 O(N),所以当集合元素过多时性能较差。尽管插入和删除的时间复杂度较高,但由于整数集合通常用于静态数据集,元素的插入和删除操作较少,因此影响整体性能的程度较小。

当新增的元素不是整数或者超过了 set-max-intset-entries阈值时,redis 会将存储结构转为 REDIS_ENCODING_HT。

注意,一旦转换成 REDIS_ENCODING_HT,之后该列表即使满足使用 REDIS_ENCODING_INTSET 条件,也不会回滚使用 REDIS_ENCODING_INTSET 编码方式。

有序集合

有序集合类型的内部编码方式可能是 REDIS_ENCODING_SKIPLIST 和 REDIS_ENCODING_ZIPLIST。使用 ziplist 时,有序集合的存储方式按照元素 1 的值、元素 1 的分数、元素 2 的值、元素 2 的分数顺序排序。

同理,有序集合(Sorted Set)的使用 ziplist编码方式的时机可以通过以下两个配置项来定义:

  1. zset-max-ziplist-entries:

    • 这个配置项定义了一个有序集合使用 ziplist编码的最大成员数量的阈值。
    zset-max-ziplist-entries 128
  2. zset-max-ziplist-value:

    • 这个配置项定义了一个有序集合使用 ziplist编码的最大值的阈值。
    zset-max-ziplist-value 64

具体规则不再赘述。

当超过阈值时,有序集合使用 REDIS_ENCODING_SKIPLIST 编码方式,这时,有序集合的底层数据结构采用了跳表(Skip List)和散列表(Hash Table)的组合。散列表用来存储元素值与元素分数的映射,跳表用来存储元素的分数以及其到元素值的映射以实现排序功能。redis 对跳表的实现进行了几点修改:1、允许跳表中的元素(分数)相同;2、位每个跳表节点增加了指向前一节点的指针,支持倒序查找。

skiplist

跳表的关键思想是通过建立多层次的索引来减少查找的时间复杂度。最底层的链表是原始数据,每个节点都有一个指针指向下一个节点。上层的链表是下层链表的子集,每个节点都有一个指针指向下层链表中相同位置的节点。这些上层链表提供了一种快速跳跃的方式,在查找时可以快速定位到目标元素的大致位置,然后在更细节的层次进行查找。

跳表就是多层链表,每一层链表都是有序的,最下面一层是原始链表,包含所有数据,从下往上节点个数逐渐减少,如下图所示。

image-20240110233538893

跳表的主要特点:

  1. 层级结构:
    • 跳表的节点分布在多个层级上,最底层包含所有节点。每一层级都是一个有序链表,层级越高,节点越稀疏。
  2. 索引层:
    • 跳表的每个节点都包含多个指针,指向下一层的相同节点。这样形成的多级指针构成了索引层。
    • 顶层的节点指针直接指向最右侧的节点,底层的节点指针连接整个链表。
  3. 加速查找:
    • 通过层级结构,跳表允许快速的查找操作。在查找元素时,可以从最顶层开始,按照顺序逐层向下跳跃,直到找到目标元素或者确定目标元素不在跳表中。
  4. 插入和删除:
    • 在插入和删除操作时,需要更新各层的指针,以保持跳表的有序性和层级结构。
    • 这通常涉及到更新节点之间的指针,确保插入或删除的节点被正确连接到各层中。
  5. 平均时间复杂度:
    • 对于有序集合的查找、插入和删除操作,跳表的平均时间复杂度是 O(log n),其中 n 是元素数量。
    • 跳表的性能与平衡树结构相当,但其实现更为简单。

采用此种编码方式时,元素值是用 redisObject 存储的,所以可以用字符串类型键值的优化方法优化元素值,而元素的分数使用 double 类型存储的。

------本页内容已结束,喜欢请分享------

文章作者
能不能吃完饭再说
隐私政策
PrivacyPolicy
用户协议
UseGenerator
许可协议
NC-SA 4.0


© 版权声明
THE END
喜欢就支持一下吧
点赞22赞赏 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片