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 中分配的内存空间的长度。容量减去长度就代表还有多少空闲空间可用。

存储结构如下

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

共享对象池

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

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

1. 共享字符串对象：

   • Redis 中的字符串常量，如空字符串和整数的字符串表示，是被共享的。这意味着如果多个键存储相同的字符串值，它们实际上引用的是同一个共享字符串对象，而不是每个键都有一份独立的拷贝。

2. 整数对象池：

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

3. 共享哈希表和集合对象：

   • Redis 中的哈希表和集合对象也可以被共享。当一个数据结构为空时，Redis 会使用共享的空对象，而不是为每个空数据结构创建新对象。

4. 对象引用计数：

   • 每个共享对象都有一个引用计数，表示有多少个键引用了该对象。当引用计数为零时，对象可以被释放。引用计数机制确保了共享对象在不再被引用时可以被安全地释放。

5. 内存管理：

   • 共享对象池有助于减少内存碎片，因为相同的数据结构在内存中只有一份拷贝。这对于大规模的 Redis 部署来说是一个重要的优势。

6. 提高性能：

   • 共享对象池减少了频繁创建和销毁相同数据结构的开销，从而提高了 Redis 的性能。它还有助于减小内存占用，使得 Redis 更加高效。

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

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

embstr 与 raw

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

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

散列类型

散列（Hash）类型的内部编码方式有两种主要形式，分别是 ziplist和 hashtable。

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-entries和 hash-max-ziplist-value值将导致更多的散列使用 ziplist编码，减小内存开销，但可能牺牲一些性能。较大的值则可能提高性能，但会增加内存占用。

ziplist

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

ziplist 的字段描述

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

元素的字段描述

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

列表类型

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

REDIS_ENCODING_ZIPLIST 在列表类型的具体表现与散列类型相同，同样可以通过配置项 list-max-ziplist-entries 和 list-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

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

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

跳表的主要特点：

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

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

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

---