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 10encoding：表示 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 结构体包含了三个字段：
buf：指向字符串的实际内容。字符串以空字符’\0’结尾，buf 的长度可以通过sdslen获取，不包括结尾的’\0’。len：表示字符串的长度，即不包括结尾的’\0’的字符个数。free：表示字符串的容量，即 buf 中分配的内存空间的长度。容量减去长度就代表还有多少空闲空间可用。
存储结构如下
而当键值内容可以用一个 64 位有符号整数表示时，redis 会将键值转为 long 类型来存储，比如 SET key 123，存储结构就变为下图，与之前相比大大节省了存储空间。
共享对象池
redisObject 的 refcount 字段存储了引用次数，即一个键值可以被多个键引用。
在 Redis 中，共享对象池用于管理和复用一些常用的数据结构对象，以减少内存碎片和提高性能。这些共享对象通常是一些常量字符串、整数对象等，它们在 Redis 内部会被频繁使用。
- 共享字符串对象：
- Redis 中的字符串常量，如空字符串和整数的字符串表示，是被共享的。这意味着如果多个键存储相同的字符串值，它们实际上引用的是同一个共享字符串对象，而不是每个键都有一份独立的拷贝。
- 整数对象池：
- Redis 为小整数（通常范围在[-10000, 10000]）维护一个整数对象池。当存储整数值时，Redis 尽量使用已存在的整数对象，而不是创建新的对象。这减少了内存占用和提高了性能。比如
SET key 123，可以直接引用共享对象而不需要创建新的 redisObject 了。
- Redis 为小整数（通常范围在[-10000, 10000]）维护一个整数对象池。当存储整数值时，Redis 尽量使用已存在的整数对象，而不是创建新的对象。这减少了内存占用和提高了性能。比如
- 共享哈希表和集合对象：
- Redis 中的哈希表和集合对象也可以被共享。当一个数据结构为空时，Redis 会使用共享的空对象，而不是为每个空数据结构创建新对象。
- 对象引用计数：
- 每个共享对象都有一个引用计数，表示有多少个键引用了该对象。当引用计数为零时，对象可以被释放。引用计数机制确保了共享对象在不再被引用时可以被安全地释放。
- 内存管理：
- 共享对象池有助于减少内存碎片，因为相同的数据结构在内存中只有一份拷贝。这对于大规模的 Redis 部署来说是一个重要的优势。
- 提高性能：
- 共享对象池减少了频繁创建和销毁相同数据结构的开销，从而提高了 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。
hash-max-ziplist-entries：
- 这个配置项定义了一个散列类型（hash）使用
ziplist编码的最大键值对数量阈值。
hash-max-ziplist-entries 512hash-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 编码的最大节点数量和最大值的阈值。
list-max-ziplist-entries：
- 这个配置项定义了一个列表使用
ziplist编码的最大节点数量的阈值。
list-max-ziplist-entries 512list-max-ziplist-value：
- 这个配置项定义了一个列表使用
ziplist编码的最大值的阈值。
list-max-ziplist-value 64quicklist
为了兼顾压缩列表和双向循环列表的优点，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编码方式的时机可以通过以下两个配置项来定义：
zset-max-ziplist-entries：
- 这个配置项定义了一个有序集合使用
ziplist编码的最大成员数量的阈值。
zset-max-ziplist-entries 128zset-max-ziplist-value：
- 这个配置项定义了一个有序集合使用
ziplist编码的最大值的阈值。
zset-max-ziplist-value 64具体规则不再赘述。
当超过阈值时，有序集合使用 REDIS_ENCODING_SKIPLIST 编码方式，这时，有序集合的底层数据结构采用了跳表（Skip List）和散列表（Hash Table）的组合。散列表用来存储元素值与元素分数的映射，跳表用来存储元素的分数以及其到元素值的映射以实现排序功能。redis 对跳表的实现进行了几点修改：1、允许跳表中的元素（分数）相同；2、位每个跳表节点增加了指向前一节点的指针，支持倒序查找。
skiplist
跳表的关键思想是通过建立多层次的索引来减少查找的时间复杂度。最底层的链表是原始数据，每个节点都有一个指针指向下一个节点。上层的链表是下层链表的子集，每个节点都有一个指针指向下层链表中相同位置的节点。这些上层链表提供了一种快速跳跃的方式，在查找时可以快速定位到目标元素的大致位置，然后在更细节的层次进行查找。
跳表就是多层链表，每一层链表都是有序的，最下面一层是原始链表，包含所有数据，从下往上节点个数逐渐减少，如下图所示。
跳表的主要特点：
- 层级结构：
- 跳表的节点分布在多个层级上，最底层包含所有节点。每一层级都是一个有序链表，层级越高，节点越稀疏。
- 索引层：
- 跳表的每个节点都包含多个指针，指向下一层的相同节点。这样形成的多级指针构成了索引层。
- 顶层的节点指针直接指向最右侧的节点，底层的节点指针连接整个链表。
- 加速查找：
- 通过层级结构，跳表允许快速的查找操作。在查找元素时，可以从最顶层开始，按照顺序逐层向下跳跃，直到找到目标元素或者确定目标元素不在跳表中。
- 插入和删除：
- 在插入和删除操作时，需要更新各层的指针，以保持跳表的有序性和层级结构。
- 这通常涉及到更新节点之间的指针，确保插入或删除的节点被正确连接到各层中。
- 平均时间复杂度：
- 对于有序集合的查找、插入和删除操作，跳表的平均时间复杂度是 O(log n)，其中 n 是元素数量。
- 跳表的性能与平衡树结构相当，但其实现更为简单。
采用此种编码方式时，元素值是用 redisObject 存储的，所以可以用字符串类型键值的优化方法优化元素值，而元素的分数使用 double 类型存储的。
------本页内容已结束，喜欢请分享------