Redis 01_Redis数据类型和编码

一、redisObject介绍

Tip: Redis对象机制详解 https://pdai.tech/md/db/nosql-redis/db-redis-x-redis-object.html

1.1 redisObject数据结构及功能介绍

在 Redis 的命令中，用于对键进行处理的命令占了很大一部分，而对于键所保存的值的类型（键的类型），键能执行的命令又各不相同。如：LPUSH 和 LLEN 只能用于列表键, 而 SADD 和 SRANDMEMBER 只能用于集合键, 等等; 另外一些命令, 比如 DEL、TTL 和 TYPE, 可以用于任何类型的键；但是要正确实现这些命令, 必须为不同类型的键设置不同的处理方式: 比如说, 删除一个列表键和删除一个字符串键的操作过程就不太一样。

以上的描述说明, Redis 必须让每个键都带有类型信息, 使得程序可以检查键的类型, 并为它选择合适的处理方式。比如说，集合类型就可以由字典和整数集合两种不同的数据结构实现，但是，当用户执行 ZADD 命令时，应该不必关心集合使用的是什么编码，只要 Redis 能按照 ZADD 命令的指示，将新元素添加到集合就可以了。这说明, 操作数据类型的命令除了要对键的类型进行检查之外, 还需要根据数据类型的不同编码进行多态处理。

为了解决以上问题，Redis并没有直接使用这些数据结构来实现key-value数据库，而是基于这些数据结构构建了一个对象系统。包括字符串对象、列表对象、哈希对象、集合对象和有序集合对象五种类型的对象。每种对象都使用了至少一种底层数据结构。

Tips: Redis 底层用到的主要的数据结构，如：sds、list、dict、ziplist、skiplist、inset等。具体等将在本文第二章节进行介绍。

通过对对象的区分，Redis可以在执行命令前判断该对象是否能够执行该条命令。为对象设置不同的数据结构实现，只要是为了提高效率。

这个对象系统的主要功能包括:

redisObject 对象为所有类型的value提供了统一的封装
- 基于 redisObject 对象的类型检查
- 基于 redisObject 对象的显式多态函数
为对象的淘汰策略保存相关信息
对 redisObject 进行分配、共享和销毁的机制
实现引用计数及内存自动释放功能

Redis使用对象来表示数据中的key和value，每当在Redis数据库中创建一个新的键值对时，至少会创建两个对象，一个作用语key，另一个作用于value。

举个例子：set msg "hello world" 表示分别创建了一个字符串对象保存 “msg”，另一个字符串对象保存 “hello world”。

redis使用对象机制（redisObject）来实现类型判断、命令多态和基于引用次数的垃圾回收； redis会预分配一些常用的数据对象，并通过共享这些对象来减少内存占用，和避免频繁的为小对象分配内存。

Redis中的每个对象由 redisObject 结构体来描述，对象的类型、编码、内存回收、共享对象都需要redisObject的支持，redisObject 结构体定义如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


#define LRU_BITS 24

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU_BITS: 24；LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;  // 指向实际数据（底层数据结构，如sds、ziplist、inset等等）的指针
} robj;

各个属性解析如下：

type 占4个比特位，表示对象的类型，在Redis 中可以使用 type keyname 查看 key对象的类型，它的值可能是以下常量中的一个：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


/* A redis object, that is a type able to hold a string / list / set */

/* The actual Redis Object */
#define OBJ_STRING 0    /* String object. */
#define OBJ_LIST 1      /* List object. */
#define OBJ_SET 2       /* Set object. */
#define OBJ_ZSET 3      /* Sorted set object. */
#define OBJ_HASH 4      /* Hash object. */

/* The "module" object type is a special one that signals that the object
 * is one directly managed by a Redis module. In this case the value points
 * to a moduleValue struct, which contains the object value (which is only
 * handled by the module itself) and the RedisModuleType struct which lists
 * function pointers in order to serialize, deserialize, AOF-rewrite and
 * free the object.
 *
 * Inside the RDB file, module types are encoded as OBJ_MODULE followed
 * by a 64 bit module type ID, which has a 54 bits module-specific signature
 * in order to dispatch the loading to the right module, plus a 10 bits
 * encoding version. */
#define OBJ_MODULE 5    /* Module object. */
#define OBJ_STREAM 6    /* Stream object. */

encoding 占4个比特位，表示对象使用哪种编码，在Redis 中可以使用 object encoding keyname 查看 key对象的编码类型，它的值可能是以下常量中的一个：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// https://github.com/redis/redis/blob/6.0/src/server.h#L615
#define OBJ_ENCODING_RAW 0        // Raw representation, 简单动态字符串，用于保存键值对的键和配置文件中的参数。
#define OBJ_ENCODING_INT 1        // Encoded as integer, 用于优化小整数的内存使用。
#define OBJ_ENCODING_HT 2         // Encoded as hash table, 用于存储普通哈希对象的字段和值。
#define OBJ_ENCODING_ZIPMAP 3     // Encoded as zipmap, 这是一种特殊类型的哈希表，用于优化小哈希对象的内存使用；版本2.6后不再使用.
#define OBJ_ENCODING_LINKEDLIST 4 // No longer used: old list encoding, 双端链表，用于存储列表键；旧版本2.x中String的底层之一.
#define OBJ_ENCODING_ZIPLIST 5    // Encoded as ziplist,list/hash/zset encoding, 用于优化小列表或者小哈希对象的内存使用。
#define OBJ_ENCODING_INTSET 6     // Encoded as intset, 用于优化只包含整数元素的集合的内存使用。
#define OBJ_ENCODING_SKIPLIST 7   // Encoded as skiplist, 跳跃表和字典，用于存储有序集合键。
#define OBJ_ENCODING_EMBSTR 8     // Embedded sds string encoding, 对于长度小于44字节的字符串，Redis选择使用此特殊的编码方式。
#define OBJ_ENCODING_QUICKLIST 9  // Encoded as linked list of listpacks, 对于列表对象（list object）的一种编码方式。quicklist是ziplist和双向链表的混合体。
#define OBJ_ENCODING_STREAM 10    // Encoded as a radix tree of listpacks
#define OBJ_ENCODING_LISTPACK 11  // Encoded as a listpack 

lru 占 24 个比特位，记录该对象最后一次被访问的时间。千万别以为这只能在LRU淘汰策略中才用，LFU也是复用的个字段。当使用LRU时，它保存的上次读写的24位unix时间戳(秒级)；使用LFU时，24位会被分为两个部分，16位的分钟级时间戳和8位特殊计数器。使用object idletime keyname查看键的空间时间，单位：秒：
- 空转时长：当前时间减去键的值对象的lru时间，就是该键的空转时长。Object idletime 命令可以打印出给定键的空转时长
- 如果服务器打开了maxmemory(最大内存限制，一般为机器内存的一半)选项，并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru，那么当服务器占用的内存数超过了maxmemory选项所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。
refcount 对象的引用计数，类似于shared_ptr 智能指针的引用计数，当refcount为0时，释放该对象。在Redis 中可以使用 object refcount keyname 查看对象的引用计数。
ptr 是一个指针，指向对象具体的底层实现的数据结构，这个底层数据结构由 type 和 encoding 属性决定。举个例子，如果一个 redisObject 的 type 属性为 OBJ_LIST ，encoding 属性为 OBJ_ENCODING_QUICKLIST ，那么这个对象就是一个Redis 列表（List），它的值保存在一个 quickList 的数据结构内，而 ptr 指针就指向quicklist的对象；

下图展示了redisObject 、Redis 所有数据类型、Redis 所有编码方式以及底层数据结构之间的关系： Redis对象编码与底层映射

1.2 Redis 命令的处理过程简介（redisObject结构各字段使用范例）

Redis中操作key的命令大致可以分为两类：一种是可以操作任何类型的key，如：del、type、object等命令；另外一种是针对特定类型的key只能使用特定的命令，如：LLEN命令只能用来获取列表对象的长度。

1、类型检查（type字段） 比如对于 LLEN命令，Redis服务器在执行命令之前会先检查输入的 key 对应的的 value 对象是否为列表类型，即检查该 value 对象的 type类型是不是 OBJ_LIST，如果是才会执行LLEN命令。否则就拒绝执行命令并返回操作类型错误。

2、多态命令的实现（encoding） Redis除了会根据value对象的类型来判断对应key能否执行执行命令外，还会根据value对象的 编码方式（encoding字段） 选择正确的方式来执行命令。比如：列表对象的编码方式有quicklist 和 ziplist两种，Redis服务器除了判断对应value对象的类型为列表对象外，还要根据具体的编码选择正确的LLEN执行。

借用面向对象的术语来说，可以认为LLEN命令是多态的。只要执行LLEN命令的列表键，无论value对象的编码是哪种方式，LLEN命令都可以正常执行。实际上del、type等也是多态命令。它们和LLEN的区别在于，前者是基于类型的多态，后者是基于编码的多态。

当执行一个处理数据类型命令的时候，redis执行以下步骤：

根据给定的 key，在数据库字典中查找和 key 相对应的 redisObject，如果没找到，就返回NULL；
检查 redisObject 的 type 属性和执行命令所需的类型是否相符，如果不相符，返回类型错误；
根据 redisObject 的 encoding 属性所指定的编码，选择合适的操作函数来处理底层的数据结构；
返回数据结构的操作结果作为命令的返回值；

比如执行 LPOP 命令：

1.3 Redis 内存回收和共享对象（refcount）

C语言不具备自动回收功能，Redis就通过引用计数实现了自己的内存回收机制。具体是由redisObject结构中的refcount字段记录。对象的引用计数会随着对象的使用状态而不断变化。

创建一个新对象时，refcount会被初始化为1；当对象被另一个新程序使用时 refcount加1；不被一个程序使用时减1；当refcount==0时，该对象所占的空间会被回收。

Tips: 在Redis 中可以使用 object refcount keyname 查看对象的引用计数。

1

127.0.0.1:6379

Redis一般会把一些常见的值放到一个共享对象中，这样可使程序避免了重复分配的麻烦，也节约了一些CPU时间。

redis预分配的值对象如下：

各种命令的返回值，比如成功时返回的OK，错误时返回的ERROR，命令入队事务时返回的QUEUE，等等
包括 0 在内，小于 REDIS_SHARED_INTEGERS 的所有整数（REDIS_SHARED_INTEGERS的默认值是10000）

Tips：共享对象只能被字典和双向链表这类能带有指针的数据结构使用。像整数集合和压缩列表这些只能保存字符串、整数等自勉之的内存

为什么redis不共享列表对象、哈希对象、集合对象、有序集合对象，只共享字符串对象？

列表对象、哈希对象、集合对象、有序集合对象，本身可以包含字符串对象，复杂度较高。
如果共享对象是保存字符串对象，那么验证操作的复杂度为O(1)
如果共享对象是保存字符串值的字符串对象，那么验证操作的复杂度为O(N)
如果共享对象是包含多个值的对象，其中值本身又是字符串对象，即其它对象中嵌套了字符串对象，比如列表对象、哈希对象，那么验证操作的复杂度将会是O(N的平方)

如果对复杂度较高的对象创建共享对象，需要消耗很大的CPU，用这种消耗去换取内存空间，是不合适的

1.4 引用计数以及对象的消毁

redisObject 中有 refcount 属性，是对象的引用计数，显然计数0那么就是可以回收。

每个redisObject结构都带有一个refcount属性，指示这个对象被引用了多少次；
当新创建一个对象时，它的refcount属性被设置为1；
当对一个对象进行共享时，redis将这个对象的refcount加一；
当使用完一个对象后，或者消除对一个对象的引用之后，程序将对象的refcount减一；
当对象的refcount降至0 时，这个RedisObject结构，以及它引用的数据结构的内存都会被释放。

1.5 Redis 不同对象编码规则

Redis 不同对象编码规则如下图所示：

二、Redis 底层数据结构详解

Tips: Redis底层数据结构详解 https://pdai.tech/md/db/nosql-redis/db-redis-x-redis-ds.html

2.1 Redis 底层数据结构类型简介

Redis 5种基础数据类型为字符串(string)、列表(list)、哈希(hash)、集合(set)、有序集合(zset)；这些基础类型的底层是如何实现的呢？

Redis的每种对象都由对象结构(redisObject) 与对应编码的数据结构组合而成。

Redis 底层数据结构类型分为如下几类：

简单动态字符串 - SDS(全称Simple Dynamic Strings)
压缩列表 - ZipList
快表 - QuickList
字典/哈希表 - Dict
整数集 - IntSet
跳表 - ZSkipList

2.2 简单动态字符串 - sds

Redis 是用 C语言写的，但是对于Redis的字符串，却不是 C 语言中的字符串（即以空字符’\0’结尾的字符数组），它是Redis自己构建的一种名为 简单动态字符串SDS(全称Simple Dynamic Strings) 的抽象类型，并将 SDS 作为 Redis的默认字符串表示。

SDS 是一类用于存储二进制数据的结构体类型，具有动态扩容的特点，其实现位于src/sds.h与src/sds.c中。

SDS的总体概览:

Redis 3.0 及之前版本，SDS 的结构定义如下：

1
2
3
4
5


struct sdshdr {  
      unsigned int len;   // 记录 buf 数组中已使用字节的数量，等于 SDS 所保存字符串的长度
      unsigned int free;  // 记录 buf 数据中未使用的字节数量
      char     buf[];     // 字节数组，用于保存字符串，字符串末尾（索引为len）总是包含一个空字符（'\0'），以兼容 C 语言的字符串函数
};

Redis 3.2 版本开始，SDS 的结构定义如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

通过上面代码可以看到，SDS有五种不同的头部，其中sdshdr5实际并未使用到，所以实际上有四种不同的头部，分别如下:

其中：

len 保存了字符串的长度
alloc 分别以 uint8, uint16, uint32, uint64 表示 SDS 除头部（len、alloc 和 flags）与末尾的 \0 外，剩余的字节数。
flags 始终为一字节，以低三位标示着头部的类型，高5位未使用
buf[] 数组用来保存字符串的每个元素，最后一个元素的下一个字符为 \0

使用 SDS（而不使用C语言字符串）实现的好处：

常数复杂度获取字符串长度
- 由于 len 属性的存在，获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)。而对于 C 语言，获取字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。通过 strlen key 命令可以获取 key 的字符串长度。
杜绝缓冲区溢出
- 在 C 语言中使用 strcat 函数来进行两个字符串的拼接，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。而对于 SDS 数据类型，在进行字符修改的时候，会首先根据记录的 len 属性检查内存空间是否满足需求，如果不满足，会进行相应的空间扩展，然后在进行修改操作，所以不会出现缓冲区溢出。
减少修改字符串的内存重新分配次数
- C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。
- 而对于SDS，由于len属性和alloc属性的存在，对于修改字符串SDS实现了 空间预分配 和 惰性空间释放 两种策略：
  1. 空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。
  2. 惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 alloc 属性将这些字节的数量记录下来，等待后续使用。（当然SDS也提供了相应的API，当有需要时，也可以手动释放这些未使用的空间。）
二进制安全
- 因为C字符串以空字符作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括空字符串，因此C字符串无法正确存取；而所有 SDS 的API 都是以处理二进制的方式来处理 buf 里面的元素，并且 SDS 不是以空字符串来判断是否结束，而是以 len 属性表示的长度来判断字符串是否结束。
兼容部分 C 字符串函数
- 虽然 SDS 是二进制安全的，但是一样遵从每个字符串都是以空字符串结尾的惯例，这样可以重用 C 语言库<string.h> 中的一部分函数。

Redis SDS空间预分配补进一步理解 当执行追加（append）操作时，比如现在给 key='Hello World' 的字符串后追加 ’ again!‘后，这时 len=18，alloc由0变成了18，此时的buf=‘Hello World again!\0………………..’(.表示空格)，也就是buf的内存空间是18+18+1=37个字节，其中 ‘\0’ 占1个字节，Redis给字符串多分配了18个字节的预分配空间，所以下次还有append追加的时候，如果预分配空间足够，就无须在进行空间分配了。

在Redis当前版本中，为字符串申请内存空间是，当新字符串的长度小于1M时，Redis会分配它们所需大小一倍的空间，当大于1M的时候，就为它们额外多分配1M的空间。

执行过 APPEND 命令的字符串会带有额外的预分配空间，这些预分配空间不会被释放，除非该字符串所对应的键被删除，或者等到关闭 Redis 之后，再次 启动时重新载入的字符串对象将不会有预分配空间。因为执行 APPEND 命令的字符串键数量通常并不多，占用内存的体积通常也不大，所以这一般并不算什么问题。另一方面，如果执行 APPEND 操作的键很多，而字符串的体积又很大的话，那可能就需要修改 Redis 服务器，让它定时释放一些字符串键的预分配空间，从而更有效地使用内存。

SDS小结： redis的字符串表示为sds，而不是C字符串（以\0结尾的char*），它是Redis 底层所使用的字符串表示，它被用在几乎所有的 Redis 模块中。可以看如下对比：一般来说，SDS 除了保存数据库中的字符串值以外，SDS 还可以作为缓冲区（buffer）：包括 AOF 模块中的AOF缓冲区以及客户端状态中的输入缓冲区。

2.3 压缩列表 - ZipList

压缩列表（ziplist） 是为了提高存储效率而设计的一种特殊编码的双向链表。它可以存储字符串或者整数，存储整数时是采用整数的二进制而不是字符串形式存储。它能在O(1)的时间复杂度下完成 list两端的 push 和 pop 操作。但是因为每次操作都需要重新分配 ziplist的内存，所以实际复杂度和 ziplist的内存使用量相关。

ziplist结构

1
2
3
4
5
6


// src/ziplist.c
/*
The general layout of the ziplist is as follows:
 *
 * <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
*/

整个ziplist在内存中的存储格式如下：

zlbytes 字段的类型是 uint32_t, 这个字段中存储的是整个ziplist所占用的内存的字节数；
zltail 字段的类型是 uint32_t, 它指的是ziplist中最后一个entry的偏移量，用于快速定位最后一个entry, 以快速完成pop等操作；
zllen 字段的类型是 uint16_t, 它指的是整个ziplit中entry的数量，这个值只占2bytes（16位）: 如果ziplist中entry的数目小于65535(2的16次方), 那么该字段中存储的就是实际entry的值. 若等于或超过65535, 那么该字段的值固定为65535, 但实际数量需要一个个entry的去遍历所有entry才能得到；
zlend 是一个终止字节，其值为全F, 即0xff，ziplist保证任何情况下, 一个entry的首字节都不会是255；

Entry结构：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


// src/ziplist.c
/*
* ZIPLIST ENTRIES
 * ===============
 *
 * Every entry in the ziplist is prefixed by metadata that contains two pieces
 * of information. First, the length of the previous entry is stored to be
 * able to traverse the list from back to front. Second, the entry encoding is
 * provided. It represents the entry type, integer or string, and in the case
 * of strings it also represents the length of the string payload.
 * So a complete entry is stored like this:
 *
 * <prevlen> <encoding> <entry-data>
 *
 * Sometimes the encoding represents the entry itself, like for small integers
 * as we'll see later. In such a case the <entry-data> part is missing, and we
 * could have just:
 *
 * <prevlen> <encoding>
 *
 * The length of the previous entry, <prevlen>, is encoded in the following way:
 * If this length is smaller than 254 bytes, it will only consume a single
 * byte representing the length as an unsinged 8 bit integer. When the length
 * is greater than or equal to 254, it will consume 5 bytes. The first byte is
 * set to 254 (FE) to indicate a larger value is following. The remaining 4
 * bytes take the length of the previous entry as value.
 *
 * So practically an entry is encoded in the following way:
 *
 * <prevlen from 0 to 253> <encoding> <entry> // 长度小于254结构
 *
 * Or alternatively if the previous entry length is greater than 253 bytes
 * the following encoding is used:
 *
 * <0xFE,4 bytes unsigned little endian prevlen> <encoding> <entry> //长度大于等于254
 *
*/

第一种情况：一般结构 <prevlen> <encoding> <entry-data>

prevlen：前一个entry的大小，编码方式见下文；
encoding：不同的情况下值不同，用于表示当前entry的类型和长度；
entry-data：真正用于存储entry表示的数据；

第二种情况：在entry中存储的是int类型时，encoding 和 entry-data 会合并在encoding中表示，此时没有entry-data字段；

redis中，在存储数据时，会先尝试将string转换成int存储，节省空间；此时entry结构：<prevlen> <encoding>
prevlen编码
- 当前一个元素长度小于254（255用于zlend）的时候，prevlen长度为1个字节，值即为前一个entry的长度，如果前一个entry的长度大于等于254的时候，prevlen用5个字节表示，第一字节设置为254，后面4个字节存储一个小端的无符号整型，表示前一个entry的长度；

1
2


<prevlen from 0 to 253> <encoding> <entry>      //长度小于254结构
0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>   //长度大于等于254

encoding编码
- encoding的长度和值根据保存的是int还是string，还有数据的长度而定；
- 前两位用来表示类型，当为 ‘11’ 时，表示entry存储的是int类型，其它表示存储的是string；
- 存储string时：
  1. |00pppppp| ：此时encoding长度为1个字节，该字节的后六位表示entry中存储的string长度，因为是6位，所以entry中存储的string长度不能超过63；
  2. |01pppppp|qqqqqqqq| 此时encoding长度为两个字节；此时encoding的后14位用来存储string长度，长度不能超过16383；
  3. |10000000|qqqqqqqq|rrrrrrrr|ssssssss|ttttttt| 此时encoding长度为5个字节，后面的4个字节用来表示encoding中存储的字符串长度，长度不能超过2^32 - 1;
- 存储int时：
  1. |11000000| encoding为3个字节，后2个字节表示一个int16；
  2. |11010000| encoding为5个字节，后4个字节表示一个int32；
  3. |11100000| encoding 为9个字节，后8字节表示一个int64；
  4. |11110000| encoding为4个字节，后3个字节表示一个有符号整型；
  5. |11111110| encoding为2字节，后1个字节表示一个有符号整型；
  6. |1111xxxx| encoding长度就只有1个字节，xxxx表示一个0 - 12的整数值；
  7. |11111111| 还记得zlend么？

源码中数据结构支撑：以看到为了操作上的简易实际还增加了几个属性

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


/* We use this function to receive information about a ziplist entry.
 * Note that this is not how the data is actually encoded, is just what we
 * get filled by a function in order to operate more easily. */
typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;

prevrawlensize 表示 previous_entry_length字段的长度
prevrawlen 表示 previous_entry_length字段存储的内容
lensize 表示 encoding字段的长度
len 表示数据内容长度
headersize 表示当前元素的首部长度，即previous_entry_length字段长度与encoding字段长度之和
encoding 表示数据类型
p 表示当前元素首地址

ZipList特别省内存:

Tips: 理解了上面的Entry结构，就能真正理解ZipList为什么是特别节省内存的数据结构。

ziplist节省内存是相对于普通的list来说的，如果是普通的数组，那么它每个元素占用的内存是一样的且取决于最大的那个元素（很明显它是需要预留空间的）；
所以ziplist在设计时就很容易想到要尽量让每个元素按照实际的内容大小存储，所以增加encoding字段，针对不同的encoding来细化存储大小；
这时候还需要解决的一个问题是遍历元素时如何定位下一个元素呢？在普通数组中每个元素定长，所以不需要考虑这个问题；但是ziplist中每个data占据的内存不一样，所以为了解决遍历，需要增加记录上一个元素的length，所以增加了prelen字段。

ziplist的缺点：

ziplist 也不预留内存空间，并且在移除结点后，也是立即缩容，这代表每次写操作都会进行内存分配操作；
结点如果扩容，导致结点占用的内存增长，并且超过254字节的话，可能会导致链式反应: 其后一个结点的 entry.prevlen 需要从一字节扩容至五字节，最坏情况下，第一个结点的扩容，会导致整个ziplist表中的后续所有结点的 entry.prevlen 字段扩容，虽然这个内存重分配的操作依然只会发生一次，但代码中的时间复杂度是O(N)级别, 因为链式扩容只能一步一步的计算，但这种情况的概率十分的小，一般情况下链式扩容能连锁反映五六次就很不幸了，之所以说这是一个严重问题，是因为，这样的坏场景下，其实时间复杂度并不高：依次计算每个entry新的空间占用，也就是O(N), 总体占用计算出来后, 只执行一次内存重分配, 与对应的memmove操作。

2.4 快表 - QuickList

快表（quicklist） 这个结构是Redis在3.2版本后新加的, 之前的版本是list(即linkedlist)，用于String数据类型中。

它是一种以ziplist为结点的双端链表结构，宏观上，quicklist是一个链表，微观上，链表中的每个结点都是一个ziplist。

quicklist结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


// Redis 6.0 源码中quicklist相关的结构
/* Node, quicklist, and Iterator are the only data structures used currently. */

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 10 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
 * 'sz' is byte length of 'compressed' field.
 * 'compressed' is LZF data with total (compressed) length 'sz'
 * NOTE: uncompressed length is stored in quicklistNode->sz.
 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

/* Bookmarks are padded with realloc at the end of of the quicklist struct.
 * They should only be used for very big lists if thousands of nodes were the
 * excess memory usage is negligible, and there's a real need to iterate on them
 * in portions.
 * When not used, they don't add any memory overhead, but when used and then
 * deleted, some overhead remains (to avoid resonance).
 * The number of bookmarks used should be kept to minimum since it also adds
 * overhead on node deletion (searching for a bookmark to update). */
typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;


/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
 * 'count' is the number of total entries.
 * 'len' is the number of quicklist nodes.
 * 'compress' is: -1 if compression disabled, otherwise it's the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * 'fill' is the user-requested (or default) fill factor.
 * 'bookmakrs are an optional feature that is used by realloc this struct,
 *      so that they don't consume memory when not used. */
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistIter {
    const quicklist *quicklist;
    quicklistNode *current;
    unsigned char *zi;
    long offset; /* offset in current ziplist */
    int direction;
} quicklistIter;

typedef struct quicklistEntry {
    const quicklist *quicklist;
    quicklistNode *node;
    unsigned char *zi;
    unsigned char *value;
    long long longval;
    unsigned int sz;
    int offset;
} quicklistEntry;

这里定义了6个结构体:

quicklistNode, 宏观上, quicklist是一个链表, 这个结构描述的就是链表中的结点. 它通过zl字段持有底层的ziplist. 简单来讲, 它描述了一个ziplist实例
quicklistLZF, ziplist是一段连续的内存, 用LZ4算法压缩后, 就可以包装成一个quicklistLZF结构. 是否压缩quicklist中的每个ziplist实例是一个可配置项. 若这个配置项是开启的, 那么quicklistNode.zl字段指向的就不是一个ziplist实例, 而是一个压缩后的quicklistLZF实例
quicklistBookmark, 在quicklist尾部增加的一个书签，它只有在大量节点的多余内存使用量可以忽略不计的情况且确实需要分批迭代它们，才会被使用。当不使用它们时，它们不会增加任何内存开销。
quicklist. 这就是一个双链表的定义. head, tail分别指向头尾指针. len代表链表中的结点. count指的是整个quicklist中的所有ziplist中的entry的数目. fill字段影响着每个链表结点中ziplist的最大占用空间, compress影响着是否要对每个ziplist以LZ4算法进行进一步压缩以更节省内存空间.
quicklistIter是一个迭代器
quicklistEntry是对ziplist中的entry概念的封装. quicklist作为一个封装良好的数据结构, 不希望使用者感知到其内部的实现, 所以需要把ziplist.entry的概念重新包装一下.

quicklist的内存布局图如下所示:

quicklist更多额外信息:

quicklist.fill的值影响着每个链表结点中, ziplist的长度
- 当数值为负数时, 代表以字节数限制单个ziplist的最大长度. 具体为:
- -1 不超过 4kb
- -2 不超过 8kb
- -3 不超过 16kb
- -4 不超过 32kb
- -5 不超过 64kb
- 当数值为正数时, 代表以entry数目限制单个ziplist的长度. 值即为数目. 由于该字段仅占16位, 所以以entry数目限制ziplist的容量时, 最大值为2^15个
quicklist.compress的值影响着quicklistNode.zl字段指向的是原生的ziplist, 还是经过压缩包装后的quicklistLZF
- 0 表示不压缩, zl字段直接指向ziplist
- 1 表示quicklist的链表头尾结点不压缩, 其余结点的zl字段指向的是经过压缩后的quicklistLZF
- 2 表示quicklist的链表头两个, 与末两个结点不压缩, 其余结点的zl字段指向的是经过压缩后的quicklistLZF
- 以此类推, 最大值为2^16
quicklistNode.encoding字段, 以指示本链表结点所持有的ziplist是否经过了压缩. 1代表未压缩, 持有的是原生的ziplist, 2代表压缩过
quicklistNode.container字段指示的是每个链表结点所持有的数据类型是什么. 默认的实现是ziplist, 对应的该字段的值是2, 目前Redis没有提供其它实现. 所以实际上, 该字段的值恒为2
quicklistNode.recompress字段指示的是当前结点所持有的ziplist是否经过了解压. 如果该字段为1即代表之前被解压过, 且需要在下一次操作时重新压缩.

quicklist的具体实现代码篇幅很长, 这里就不贴代码片断了, 从内存布局上也能看出来, 由于每个结点持有的ziplist是有上限长度的, 所以在与操作时要考虑的分支情况比较多。

quicklist有自己的优点, 也有缺点, 对于使用者来说, 其使用体验类似于线性数据结构, list作为最传统的双链表, 结点通过指针持有数据, 指针字段会耗费大量内存. ziplist解决了耗费内存这个问题. 但引入了新的问题: 每次写操作整个ziplist的内存都需要重分配. quicklist在两者之间做了一个平衡. 并且使用者可以通过自定义quicklist.fill, 根据实际业务情况, 经验主义调参.

2.5 字典/哈希表 - Dict

Tips: 字典本质上就是哈希表, 这个在很多语言中都有。

Redis中字典的数据结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// 哈希表结构定义：
typedef struct dictht{
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值
    //总是等于 size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
 
}dictht

哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，dictEntry 结构定义如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


typedef struct dictEntry{
     //键
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
 
     //指向下一个哈希表节点，形成链表
     struct dictEntry *next;
}dictEntry

key 用来保存键，val 属性用来保存值，值可以是一个指针，也可以是uint64_t整数，也可以是int64_t整数。

注意这里还有一个指向下一个哈希表节点的指针，我们知道哈希表最大的问题是存在哈希冲突，如何解决哈希冲突，有开放地址法和链地址法。这里采用的便是链地址法，通过next这个指针可以将多个哈希值相同的键值对连接在一起，用来解决哈希冲突。

一些要点

哈希算法：Redis计算哈希值和索引值方法如下：

1
2
3
4
5


// 1、使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

// 2、使用哈希表的sizemask属性和第一步得到的哈希值，计算索引值
index = hash & dict->ht[x].sizemask;

解决哈希冲突：这个问题上面介绍了，方法是链地址法。通过字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点
扩容和收缩：当哈希表保存的键值对太多或者太少时，就要通过 rerehash(重新散列）来对哈希表进行相应的扩展或者收缩。具体步骤：
- 1、如果执行扩展操作，会基于原哈希表创建一个大小等于 ht[0].used*2n 的哈希表（也就是每次扩展都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表）。相反如果执行的是收缩操作，每次收缩是根据已使用空间缩小一倍创建一个新的哈希表。
- 2、重新利用上面的哈希算法，计算索引值，然后将键值对放到新的哈希表位置上。
- 3、所有键值对都迁徙完毕后，释放原哈希表的内存空间。
触发扩容的条件：
- 1、服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。
- 2、服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。
- 3、负载因子 = 哈希表已保存节点数量 / 哈希表大小。

渐近式 rehash 渐近式 rehash 是指扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。如果保存在Redis中的键值对只有几个几十个，那么 rehash 操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成Redis一段时间内不能进行别的操作。所以Redis采用渐进式 rehash,这样在进行渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行增加操作，一定是在新的哈希表上进行的。

2.6 整数集 - IntSet

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

intset结构

1
2
3
4
5


typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

encoding 表示编码方式，取值有三个：INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64
length 代表其中存储的整数的个数
contents 指向实际存储数值的连续内存区域, 就是一个数组；整数集合的每个元素都是 contents 数组的一个数组项（item），各个项在数组中按值得大小从小到大有序排序，且数组中不包含任何重复项。（虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组，但实际上 contents 数组并不保存任何 int8_t 类型的值，contents 数组的真正类型取决于 encoding 属性的值）

整数集合的升级 当在一个int16类型的整数集合中插入一个int32类型的值，整个集合的所有元素都会转换成32类型。整个过程有三步：

根据新元素的类型（比如int32），扩展整数集合底层数组的空间大小，并为新元素分配空间。
将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
最后改变encoding的值，length+1。

如果删除掉刚加入的int32类型时，是不会做一个降级操作。主要还是减少开销的权衡。

2.7 跳表 - ZSkipList

跳跃表 结构在 Redis 中的运用场景只有一个，那就是作为有序列表 (Zset) 的使用。跳跃表的性能可以保证在查找，删除，添加等操作的时候在对数期望时间内完成，这个性能是可以和平衡树来相比较的，而且在实现方面比平衡树要优雅，这就是跳跃表的长处。跳跃表的缺点就是需要的存储空间比较大，属于利用空间来换取时间的数据结构。

跳跃表设计要解决的问题 对于一个单链表来讲，即便链表中存储的数据是有序的，如果要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。比如下图查找12，需要7次查找

如果给链表增加如下两级索引，那么它搜索次数就变成了3次

Redis跳跃表的设计 Redis跳跃表并没有在单独的类（比如skplist.c)中定义，而是其定义在server.h中, 如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

其内存布局如下图:

zskiplist的核心设计要点

头节点不持有任何数据, 且其level[]的长度为32
每个结点
- ele字段，持有数据，是sds类型
- score字段, 其标示着结点的得分, 结点之间凭借得分来判断先后顺序, 跳跃表中的结点按结点的得分升序排列.
- backward指针, 这是原版跳跃表中所没有的. 该指针指向结点的前一个紧邻结点.
- level字段, 用以记录所有结点(除过头节点外)；每个结点中最多持有32个zskiplistLevel结构. 实际数量在结点创建时, 按幂次定律随机生成(不超过32). 每个zskiplistLevel中有两个字段
  - forward字段指向比自己得分高的某个结点(不一定是紧邻的), 并且, 若当前zskiplistLevel实例在level[]中的索引为X, 则其forward字段指向的结点, 其level[]字段的容量至少是X+1. 这也是上图中, 为什么forward指针总是画的水平的原因.
  - span字段代表forward字段指向的结点, 距离当前结点的距离. 紧邻的两个结点之间的距离定义为1.

为什么不用平衡树或者哈希表替换跳跃表？简而言之就是实现简单且达到了类似效果。

Tips: https://news.ycombinator.com/item?id=1171423

skiplist与平衡树、哈希表的比较 来源于：https://www.jianshu.com/p/8ac45fd01548

skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。

在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。

平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。

从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。

查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。

从算法实现难度上来比较，skiplist比平衡树要简单得多。#

三、Redis对象与编码(底层结构)对应关系详解

3.1 数据类型（Type）和编码（Encoding）简介

Redis支持五种主要的数据类型：字符串(String)、列表(List)、集合(Set)、有序集合(Sorted Set) 和哈希(Hash)。

每种数据类型都有对应的编码方式，数据类型与编码方式总览如下：

数据类型	编码方式
字符串	int、embstr、raw
列表	ziplist、linkedlist、quicklist
集合	intset、hashtable
有序集合	ziplist、skiplist
哈希表	ziplist、hashtable

在Redis中，数据类型（Type）和编码（Encoding）是非常重要的概念。

要查看Redis某个key的内部编码，可以使用Redis自带的命令：OBJECT ENCODING key。

其中，key是你想要查询的键名。例如，如果你想要查询名为mykey的键的内部编码，可以执行以下命令：

1

127.0.0.1:6379> object encoding mykey  // 查看某个Redis键值的编码

3.2 字符串(Strings)对象

字符串(Strings) 是Redis中最基本的数据类型，通常用于存储文本或二进制数据，不仅所有key都是字符串类型，其它几种数据类型构成的元素也是字符串。字符串的长度不能超过512M。

在Redis中 字符串(Strings) 类型对象的编码可以是 int，raw 或者 embstr，具体的编码方式是根据数据的内容和大小来动态选择的，以最大程度地节省内存和提高性能：

EMBSTR（embstr-encoded string 嵌套字符串编码）：用于存储较短(redis3.2版本之前是小于等于39字节，之后是小于等于44字节)的字符串，但与RAW不同的是，EMBSTR的编码方式将字符串长度也一并存储在编码结构中，以节省内存。
RAW 大字符串：这是最常见的字符串编码方式，它用于存储较长（redis3.2版本之前是大于39字节，之后是大于44字节）的字符串，长度不超过字符串编码结构的限制（512M）。这种编码方式不会对字符串进行压缩，因此在存储较大的字符串时效率高。
INT（整数编码）：当一个字符串可以被解释为整数时，Redis会将其编码为整数，以节省内存。整数编码分为以下几种子编码方式：
- int16_t：16位整数编码，存储16位以内的整数。
- int32_t：32位整数编码，存储32位以内的整数。
- int64_t：64位整数编码，存储64位以内的整数。

Tips: INT（整数编码） 编码方式的优点是存储空间小，操作效率高。缺点是只能存储整数，不支持字符串操作。

RAW和EMBSTR共享编码：在某些情况下，Redis会使用一种特殊的编码方式，该方式可以共享RAW和EMBSTR编码方式的优点。这意味着它既可以存储较短的字符串，又可以高效地存储较大的字符串。

字符串对象支持三种编码方式: RAW, INT, EMBSTR, 三种方式的内存布局分别如下:

其实 embstr 编码是专门用来保存短字符串的一种优化编码，raw 和 embstr 的区别： embstr与raw都使用redisObject和sds保存数据，区别在于，embstr的使用只分配一次内存空间（因此redisObject和sds是连续的），而raw需要分配两次内存空间（分别为redisObject和sds分配空间）。

因此与raw相比，embstr的好处在于创建时少分配一次空间，删除时少释放一次空间，以及对象的所有数据连在一起，寻找方便。而embstr的坏处也很明显，如果字符串的长度增加需要重新分配内存时，整个redisObject和sds都需要重新分配空间，因此redis中的embstr实现为只读。

编码的转换 Redis中对于浮点数类型也是作为字符串保存的，在需要的时候再将其转换成浮点数类型。

当 int 编码保存的值不再是整数，或大小超过了long的范围时，自动转化为raw。

对于 embstr 编码，由于 Redis 没有对其编写任何的修改程序（embstr 是只读的），在对embstr对象进行修改时，都会先转化为raw再进行修改，因此，只要是修改embstr对象，修改后的对象一定是raw的，无论是否达到了44个字节。

SDS（简单动态字符串）：SDS是一种用于表示字符串的数据结构，它具有动态大小，可以在不需要重新分配内存的情况下进行扩展，这种编码方式用于存储较大的字符串，以节省内存和提高性能。

3.3 列表(Lists)对象

列表(Lists) 是一系列有序(插入顺序排序)的字符串集合，可以添加、修改和删除元素，它的底层实际上是个链表结构。在Redis中 列表(Lists) 有三种编码方式：

ziplist：在Redis3.2版本之前，当List列表中每个字符串的长度都(小于64字节)并且List列表中(元素数量小于512个)时，List对象使用ziplist编码，其它情况使用linkedlist编码。ziplist是一种紧凑的、压缩的列表结构，可以节省内存，适用于小型列表。
linkedlist：在Redis 3.2版本是 list 的一种编码结构，支持任意大小的列表，但其内存占用会随着列表长度的增加而增加。
quicklist：Redis 3.2版本引入，替代了 ziplist 和 linkedlist 成为list 的编码方式，quicklist是一种由多个ziplist组成的列表结构，既能保证性能，又能节省内存，适用于大型列表。

列表对象（quicklist编码）的内存布局如下图所示:

3.4 哈希(Hashes)对象

哈希(Hashes) 是一系列键值对集合，每个键关联一个值。在Redis中 哈希(Hashes) 支持两种编码方式：

ziplist：保存的所有键值的字符串长度小于64字节，并且键值对数量小于512个，Redis会采用ziplist编码方式存储。ziplist编码方式的优点是存储空间小，操作效率高。缺点是不支持快速的键查找操作。
hashtable：除上述条件之外，Redis会采用hashtable编码方式存储。hashtable(也称 dict)编码方式的优点是支持快速的键查找操作，缺点是存储空间相对较大，操作效率相对较低。

**哈希(Hashes)**两种编码内存布局分别如下: 上图中不严谨的地方有:

ziplist中每个entry, 除了键与值本身的二进制数据, 还包括其它字段, 图中没有画出来
dict底层可能持有两个dictht实例
没有画出dict的哈希冲突

需要注意的是: 当采用HT编码, 即使用dict作为哈希对象的底层数据结构时, 键与值均是以sds的形式存储的。

举例说明 当使用ziplist，也就是压缩列表作为底层实现时，新增的键值对是保存到压缩列表的表尾。比如执行以下命令：

1
2
3


hset profile name "Tom"
hset profile age 25
hset profile career "Programmer"

如果使用ziplist，profile 存储如下：

当使用 hashtable 编码时，上面命令存储如下： hashtable 编码的哈希表对象底层使用字典数据结构，哈希对象中的每个键值对都使用一个字典键值对。

在前面介绍压缩列表时，介绍过压缩列表是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，相对于字典数据结构，压缩列表用于元素个数少、元素长度小的场景。其优势在于集中存储，节省空间。

编码转换 当同时满足下面两个条件时，使用ziplist（压缩列表）编码：

列表保存元素个数小于512个；
每个元素长度小于64字节；

不能满足这两个条件的时候使用 hashtable 编码。以上两个条件也可以通过Redis配置文件 zset-max-ziplist-entries 选项和 zset-max-ziplist-value 进行修改。

3.5 集合(Sets)对象

集合(Sets) 是是 string 类型（整数也会转换成string类型进行存储）的无序集合，支持添加、删除和查询元素。在Redis中 集合(Sets) 支持两种编码方式：

intset：当集合中的元素都是整数时，Redis会采用intset编码方式存储。intset编码方式的优点是存储空间小，操作效率高。
hashtable：当集合中的元素包含字符串时，Redis会采用hashtable编码方式存储。当使用hashtable（dict）作为集合对象的底层实现时, 是将数据全部存储于dict的键中, 值字段闲置不用，hashtable编码方式的优点是可以存储任意类型的元素，支持字符串操作。缺点是存储空间相对较大，操作效率相对较低。

集合对象的内存布局如下图所示: 举例说明

1

SADD numbers 1 3 5

1

SADD Dfruits "apple" "banana" "cherry"

编码转换 当集合同时满足以下两个条件时，使用 intset 编码：

集合对象中所有元素都是整数；
集合对象所有元素数量不超过512；

不能满足这两个条件的就使用 hashtable 编码。第二个条件可以通过配置文件的 set-max-intset-entries 进行配置。

3.6 有序集合(Sorted Sets)对象

有序集合(Sorted Sets) 是一系列有序的字符串集合，和上面的集合对象相比，有序集合对象是有序的。与列表使用索引下标作为排序依据不同，有序集合为每个元素设置一个分数（score）作为排序依据。

在Redis中 有序集合(Sorted Sets) 底层实现依然有两种, 一种是使用ziplist作为底层实现, 另外一种比较特殊, 底层使用了两种数据结构: dict与skiplist. 前者对应的编码值宏为ZIPLIST, 后者对应的编码值宏为SKIPLIST：

ziplist：使用ziplist来实现在序集合很容易理解, 只需要在ziplist这个数据结构的基础上做好排序与去重就可以了，当集合中元素个数少于128个，并且每个元素的大小小于64字节时，使用此编码方式。这是因为ziplist在处理较小数据时，内存效率更高，性能更优。
skiplist 与 dict结合：skiplist是一种跳跃表结构，支持快速查询和排序。Redis中实现的这个跳跃表似乎天然就是为了实现有序集合对象而实现的，适用于大型有序集合。

编码为ZIPLIST时, 有序集合的内存布局如下: 编码为SKIPLIST时, 有序集合的内存布局如下: 为什么还要辅助一个dict实例呢? 说明：其实有序集合单独使用字典或跳跃表其中一种数据结构都可以实现，但是这里使用两种数据结构组合起来，原因是假如单独使用字典，虽然能以 O(1) 的时间复杂度查找成员的分值，但是因为字典是以无序的方式来保存集合元素，所以每次进行范围操作的时候都要进行排序；假如单独使用跳跃表来实现，虽然能执行范围操作，但是查找操作有 O(1)的复杂度变为了O(logN)。因此Redis使用了两种数据结构来共同实现有序集合。

举例说明

1

ZADD price 8.5 apple 5.0 banana 6.0 cherry

编码转换 当有序集合对象同时满足以下两个条件时，对象使用 ziplist 编码：

保存的元素数量小于128；
保存的所有元素长度都小于64字节。

不能满足上面两个条件的使用 skiplist 编码。以上两个条件也可以通过Redis配置文件 zset-max-ziplist-entries 选项和 zset-max-ziplist-value 进行修改。

四、Type与Encoding底层原理

4.1 编码转换

Redis中的每个键值对都有一个类型标识，表示该键值对的数据类型。当对一个键进行操作时，Redis会根据该键当前的编码方式以及操作所需的编码方式，对键值对进行编码转换。例如，当向一个字符串中追加内容时，如果该字符串当前的编码方式为raw，但是新的内容可以使用embstr编码方式存储，那么Redis会将该字符串的编码方式从raw转换为embstr。

4.2 数据结构

除了编码方式外，Redis还使用了许多经典的数据结构来实现各种数据类型。

例如，Redis的列表和哈希表都是采用链表结构实现的。而有序集合则采用了跳跃表(Skip List)这种高效的数据结构。

这些数据结构都经过了精心设计和优化，以满足各种场景下的应用需求。例如，链表结构适合频繁地添加和删除元素，而跳跃表结构则适合排序和查找。

本文介绍了Redis支持的五种主要数据类型以及相应的编码方式。Redis的数据类型和编码方式是为了在不同的场景下达到最佳的性能和内存占用。理解这些类型和编码机制，对于深化我们对Redis的认识，优化其性能，以及发挥其最大潜力是至关重要的。

虽然每个项目的需求和应用可能会有所不同，但通过精心选择和使用合适的类型和编码，都可以充分利用Redis为应用带来的高效，快速和可靠。

总之，Redis的类型和编码是其核心功能的基石，理解这些可以更好地使用Redis，解决实际问题。