前言

文章内容来自redis设计与实现，记录笔记，方面以后复习。

1 简单字符串

redis 自己构建了一种名为简单动态字符串sds的抽象类型，并将sds用作redis的默认字符串类型。

set msg "hello"

• 键值对的键是字符串对象，实现是保存字符串“msg”的sds
• 键值的值是字符串对象，是保存字符串“hello”的msg

SDS的定义

struct sdshdr{
    //记录已使用的字节的数量
    int len;
    // 记录数组中未使用的字节数量
    int free;
    //字节数组，用于保存字符串
    char buf[]; 
};

1.2 sds与c字符串的区别

1.2.1 常数复杂度获取字符串长度

由于c字符串并不记录自身的长度信息，所以获取c字符串长度信息，需要进行遍历 复杂度为o（N）,而sds在len属性中记录了sds长度本身，所以获取仅为o（1）

1.2.2 杜绝缓冲区溢出

c字符串未分配足够的空间时，数据进行修改时将会发生溢出，而sds进行修改时，将会检查 free属性的大小（代表剩余空间），不足的化将会额外申请。

1.2.3 减少内存重分配现象

在sds中，buf数组的长度不一定是字符数量加一，数组里面可以包含未使用的字节，而这些字节数量由sds的free属性记录，通过未使用空间sds实现了空间预分配与惰性空间释放两种优化策略。

空间预分配

空间预分配用于优化sds的字符串增长操作，当需要对sds进行空间扩展时，程序不仅仅会为sds分配修改所必须要的空间，还会为sds分配额外未使用空间。

• 如果对sds进行修改后，sds长度（属性len）小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS的len属性值将和free属性值相同。

• 如果进行修改后，SDS长度大于等于1MB，那么程序会分配1MB未使用空间。

  通过空间预分配，redis可以减少连续执行字符串增长操作所需的内存重分配

惰性空间释放

惰性空间释放用于优化sds字符串缩短操作，当sds需要缩短字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性，将这些字节的数量记录起来。

1.2.4 二进制安全

c字符串中的字符必须符合某种编码（ASCII），不能保存图片，音频等这样的二进制数据在读取时必须按照格式进行读取。

SDS的API都是二进制安全的，所有SDS都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制。

1.3 总结

sds具有以下优点F1a;

• 常数复杂度获取字符串长度
• 杜绝缓冲区溢出
• 减少修改字符串长度时所需要的内存重分配次数
• 二进制安全
• 兼容部分c字符串函数

2 链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式。

redis 链表实现

tyPEdef struct list{
    //表头指针
    listNode *head;
    //表尾指针
    listNode *tail;
    //链表所包含的节点数量
    unsigned long len;
    //节点值 复制函数
    void *(*dup) (void *ptr);
    //节点值 释放函数
    void （*free）(void *ptr);
    //节点值 对比函数
    int (*match)(void *ptr,void *key);
}list;

• dup 函数用于复制链表节点所保存的值
• free 函数用于释放链表节点所保存的值
• match 函数用于对比链表节点所保存的值和另一个输入值是否相等

redis 链表实现特性：

• 双端：带有PRev和next指针
• 无环：表头节点的prev指针和表尾节点的next指针都指向NULL
• 带表头指针和表尾指针：获取链表头尾节点复杂度为o（1）
• 带链表长度计数器：获取链表中节点数量的复杂度为O（1）
• 多态：可以通过dup，free，;match三个属性为节点值设置类型特定函数

3 字典

字典是符号表，是一种用于保存键值对的抽象数据结构。字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点保存了字典中的一个键值对。

哈希表的实现

typedef struct dictht{
    //哈希表数组redis设计与实现
    dictEntry **table;
    
    //哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码,用于计算索引值
    unsigned long sizemask;
    
    // 该哈希表已有节点的数量
    unsigned long used;
    
}dictht;

• size 属性记录了哈希表的大小
• used 属性则记录了哈希表目前已有节点的数量
• sizemask 属性的值总是等于size-1

哈希表节点的实现

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

• key 属性保存键值对中的键

• v 属性保存键值对中的值

• next 属性指向另一个哈希表节点的指针，此指针将多个哈希值相同的键值对链接在一起，解决键冲突的问题。

字典的实现

typedef struct dict{
    //  类型特定函数
    dictType *type;
    
    //私有数据
    void *privata;
    
    // 哈希表
    dictht ht[2];
    
    //rehash 索引
    int rehashidx;
    
    
}dict;

• type 属性是一个指向dictType结构的指针，dictType结构保存了用于操作特定类型键值对的函数
• privdata 属性保存了需要传给那些类型特定函数的可选参数
• ht 属性是一个包含两个项的数组，每一个项中都是哈希表，字典只使用ht[0]哈希表，ht[1]哈希表只会在对 h[0]rehash时才使用
• rehashidx 记录了rehash目前的进度，没有则为-1;

typedef struct dictType{
    // 计算哈希值函数
    unsigned int (*hashFunction) (const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privata,const void *key);
    //复制值的函数
    void *(*valDup)(void *privata,const void *obj);
    //对比键的函数
    int （*keyCompare）(void *privata,const void *key1,const void *key2);
    //销毁键的函数
    void (*keyDestructor)(void *privata,void *key);
    //销毁值的函数
    void (*valDestructor)(void *privata,void *obj);
    
}dictType;

3.2 哈希算法

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

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

//使用哈希表的sizemask属性和哈希值，计算出索引值
index=hash & dict->ht[x].sizemask;

3.3 解决键冲突

redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成单向链表，被分配到同一个索引上的多个节点可以用这个单向链表链接起来，这就解决了键冲突。

3.4 rehash

哈希表保存的键值对会逐渐地增多或减少，为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多，或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展或收缩可以通过重新散列操作来完成，redis对hash表执行rehash的步骤：

1 为字典的ht[1]哈希表分配空间，空间的大小取决于要执行的操作。

• 如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于 ht[0].used*2的2的n次方幂
• 如果执行的是 收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂

2 将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，并将键值对放到ht[1]哈希表

3 当ht[0] 为空表后，释放ht[0],将ht[1]设置为ht[0] ,并为ht[1]新创建一个空白哈希表。

---

3.5哈希表的扩展与收缩

哈希表负载因子 = 哈希表已保存节点数量 / 哈希表大小

• 服务器没有执行BGSAVE命令，并且哈希表的负载因子大于等于1 执行扩展操作

• 当哈希表的负载因子 小于0.1 时，执行收缩操作。

3.6 渐进式rehash

为了避免rehash对服务器性能造成影响，服务器不是一次将ht[0]里面所有键值对全部rehash到ht[1],而是分多次，渐进式将里面键值对rehash到ht[1],

1 为ht[1] 分配空间

2 在字典中维持一个索引计数器变量 rehashidx ,并将它的值设置为0,表示rehash开始

3 在rehash进行间，每次对字典进行添加，删除，查找,更新操作时，程序除了执行指定的操作外**，还会顺带将ht[0] 哈希表在rehashidx 索引上的所有键值对rehash到ht[1],rehash 工作完成后，将其属性值加一**

4 当所有键值对都被rehash到ht[1],程序将rehashidx属性值设为-1,rehash更新完成

4 跳跃表

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点。

跳跃表实现了有序集合键(zset)。

4.1 跳跃表的实现

redis 跳跃表是由zskiplistNode，zskipList。

zskiplistNode用于表示跳跃表节点，而zskiplist则用于保存跳跃表节点相关信息。

• header：指向跳跃表的表头节点

• tail：指向跳跃表表尾节点

• level: 记录跳跃表，层数最大的节点层数

• length: 记录跳跃表的长度，也就是跳跃表包含节点的数量

• 层：节点中每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。

• 后退指针：节点中用bw字样标记后退指针，用于在程序从表尾向表头遍历时使用。

• 分值：节点中所保存的分值，在跳跃表中，节点按各自所保存的分值从小到大排列

• 成员对象：各个节点中的o1等是节点所保存的成员对象

4.2 跳跃表节点

typedef struct zskiplistNode{
    // 后退指针
    struct zskiplistNode *backward;
    
    //分值
    double score;
    
    //成员对象
    robj *obj
        
    // 层
    struct zskipliatLevelP{
        // 前进指针
        struct zskiplistNode *forward;
        
        // 跨度
        unsigned int span;
        
        
    }level[];    
        
    
}zskiplistNode;

• 层 ： 跳跃表节点的level数组包含多个元素，每个元素指向其他节点，程序通过这些层加快访问其他节点的速度。

• 前进指针：用于从表头访问表尾

• 跨度：用于记录两个节点之间的距离

• 后退指针：用于从表尾向表头方向访问节点，每次只能后退至前一个节点。

• 分值和成员

  节点的分值（score）是double 类型数据。跳跃表中的所有节点都按分值大小来排序。

​

​ 节点的成员对象是一个指针，指向保存sds值的字符串对象。

4.3 重点

• 跳跃表是有序集合的底层实现之一
• redis的跳跃表是由 zskipList 和zskipListNode结构组成的
• 跳跃表节点的层高为1到 32 之间的随机数
• 每个节点可以包含相同的分值，但是成员对象必须是唯一的
• 节点按照分值大小排序，当分值相同时，安照对象大小进行排序

5 整数集合

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

5.1 整数集合的实现

整数集合是redis用于保存数值的数据结构，可以保存类型 int16_t,int32_t,int64_t的整数值，并且保证集合中不会出现重复元素。

typedef struct intset{
    // 编码方式
    uint32_t encoding;
    //集合中包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents;
    
} intset;

• contents 是整数集合中的底层实现，各个数组中按值的大小从小到大排列，并且无重复。

• length 属性记录了整数集合包含的元素数量

• contents属性声明为 int8_t类型的数组，但实际上数组并不保存int8_t 的值，contents数组真正类型是取决于encoding的值

  • encoding 值为intset_enc_int16 则contents是int16_t 类型的数组（- 32768,32767）

  • encoding 的值为 intset_enc_int32 则contents是int32_t类型的数组（-2147483648,2147483647）

  • encoding 的值为 intset_enc_int64 则contents是int64_t类型的数组（-922372 036 854 775 808，-922372 036 854 775 807）

5.2 升级

每当我们要将一个新元素添加到整数集合中，并且新元素的类型都比整数集合现有所有元素类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到集合里面。

• 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
• 将底层数组现有的元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素上时，需要维持数组有序性质不变。
• 将新元素添加到底层数组里面。

由于每次升级都需要对底层数组中所有元素进行类型转换，所以向整数集合添加新元素的@R_523_1304@为o（N）

​ 升级好处

提高整数集合的灵活性，尽可能节约内存

• 为了避免类型错误，不会将两种不同的类型放到一个数据结构中

• 节约内存：让一个数组可以同时保存int16_t,int32_t,int64_t类型数据，最简单做法是使用int64_t 类型，会导致浪费内存的情况

5.3 降级

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

5.4 重点

• 整数集合是集合键的底层实现之一
• 整数集合的底层实现为数组，这个数组是以有序，无重复的方式保存了集合元素。
• 升级带来操作上的灵活性，并可能的节约了内存
• 整数集合只支持升级操作，不支持降级操作

6压缩列表

压缩列表是列表键和哈希键的底层实现，当一个列表键只包含少量列表项，并且每个列表项要么是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表来实现。

6.1 压缩列表的构成

压缩列表是redis为了节约内存而开发的，是由一系列的特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或一个整数值。

属性	类型	长度	用途
zlbytes	uint32_t	4字节	记录整个压缩列表占用的内存字节数
zltail	uint32_t	4字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节
zllen	uint16_t	2字节	记录了压缩列表包含的节点数量：当属性值小于uint16_max时，这个属性值就是压缩列表包含的节点，等于则需要遍历
entryx	列表节点	不定	压缩列表包含的各个节点
zlend	uint8_t	1字节	特殊值0xFF，用于标记压缩列表的末端

6.2 压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值，其中，字节数组可以是以下三种长度。

• 长度小于等于63字节的字节数组
• 长度小于等于16383 字节的字节数组
• 长度小于等于 4294967295字节的字节数组

整数值则可以是以下六种长度之一

• 4 位长，0-12 之间的无符号整数
• 1 字节长的有符号整数
• 3 字节长的有符号整数
• int16_t 类型整数
• int32_t 类型整数
• int64_t 类型整数

每个压缩列表节点都由 previous_entry_length,encoding,content三个部分组成

6.2.1 previous_entry_length

节点的previous_entry_length属性是以字节为单位，记录了压缩列表中前一个节点的长度。previous_entry_length 长度可以是1字节或者5字节。

• 如果前一节点的长度小于254节点，那么previous_entry_length 属性的长度为1字节

• 如果前一节点长度大于大等于254节点，那么previous_entry_length属性则为5字节

因为previous_entry_length 属性记录了前一个节点的长度，所以指针可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址

6.2.2 encoding

节点的encoding属性记录了节点的content属性所保存的数据类型以及长度。

• 一字节，两字节或者五字节长，值的最高位为00,01,或者10的是字节数组编码这种编码表示节点的content属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录。
• 一字节长，值的最高位以11开头的整数编码：这种编码表示节点的content属性保存着整数值，整数值的类型和长度由其他位记录

6.2.3 content

节点的content属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型由encoding属性决定。

6.3 连锁更新

• 由于previous_entry_length 的属性记录了前一个节点的长度： 前一节点长度小于254节点，则其属性需要用 1 字节长的空间来保存这个长度值

• 如果前一节点长度大于等于254节点，则需要5字节来保存

  当在一个压缩列表中，有多个连续的，长度介于250字节到253字节之间的节点，当新加的前一节点，导致后一节点的previous_entry_length 更新增加，导致总字节大小增加，引起连锁更新会导致后面的节点也更新。

除了添加新节点会导致连锁更新外，删除节点也可能会引发连锁更新。

由于连锁更新在最坏的情况下需要对压缩列表执行N次 空间重分配操作，而每次空间重分配最坏的复杂度为o（N），所以连锁更新的最坏复杂度为o（N2）

要注意的是

• 首先，压缩列表里要恰好有多个连续的，长度介于250字节至253字节之间的更新才有可能被引发
• 其此出现连锁更新，只要被更新的节点数量不多，就不会对性能造成影响

6.4 重点

• 压缩列表是一种节约内存而开发的顺序型数据结构
• 压缩列表被用作列表键和哈希键的底层实现
• 压缩列表可以包含多个节点，每个节点都可以保存

一个字节数组或者整数值

• 添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率不高

7 对象

redis 并没有使用这些数据结构来实现按键值对数据库，而是基于这些数据结构创造了一个对象系统。

这个系统包含字符串对象，列表对象，哈希对象，集合对象和有序集合对象这五种类型的对象。

• 可以根据不同类型的对象，redis可以在执行命令之前，根据对象的类型来判断对象是否可以执行给定的指令
• redis的对象系统还实现了基于引用计数技术的内存回收机制
• redis对象带有访问时间记录信息

7.1 对象的类型与编码

redis使用对象来表示数据库中的键和值，每次当我们在redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）

redis的每个对象都由一个redisObject结构表示

typedef struct redisObject{
    // 类型
    unsigned type:4;
    
    // 编码
    unsigned encoding:4
        
    // 指向底层实现数据结构的指针    
    void *ptr;
      
}

7.1.1 类型

对象的type 属性记录了对象的类型，是以下常量中的一个。

类型常量	对象的名称
REDIS_STRING	字符串对象
REDIS_LIST	列表对象
REDIS_HASH	哈希对象
REDIS_SET	集合对象
REDIS_ZSET	有序集合对象

对于数据库中保存的键值对来说，键总是一个字符串对象，而值则可以是其他对象，可以TYPE 命令来获取数据库键对应的值对象的类型。

# 键为字符串对象，值为字符串对象
127.0.0.1:6379> set  msg "hello"
OK
127.0.0.1:6379> type msg
string
# 键为字符串对象，值为列表对象
127.0.0.1:6379> rpush numbers 1 3 5
(integer) 3
127.0.0.1:6379> type numbers
list

7.1.2 编码和底层实现

对象的ptr 指针，指向对象的底层实现数据结构，而这些数据结构由对象的encoding属性决定。

encoding 属性记录了对象所使用的编码，也就是说这个对象使用了什么数据结构作为对象的底层实现。

编码常量	编码所对应的底层数据结构
REDIS_ENCODING_INT	long类型的整数
REDIS_ENCODING_EMBSTR	embstr 编码的简单动态字符串
REDIS_ENCODING_RAW	简单动态字符串
REDIS_ENCODING_HT	字典
REDIS_ENCODING_LINKEDLIST	双端链表
REDIS_ENCODING_ZIPLIST	压缩列表
REDIS_ENCODING_INTSET	整数集合
REDIS_ENCODING_SKIPLIST	跳跃表和字典

不同类型和编码的对象

类型	编码	对象
REDIS_STRING	REDIS_ENCODING_INT	使用整数值实现字符串对象
REDIS_STRING	REDIS_ENCODING_EMBSTR	使用embstr编码的简单动态字符串对象
REDIS_STRING	REDIS_ENCODING_RAW	使用简单字符串实现的字符串对象
REDIS_LIST	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的列表对象
REDIS_LIST	REDIS_ENCODING_LINKEDLIST	使用双端链表实现的列表对象
REDIS_HASH	REDIS_ENCODING_ZIPLIST	使用列表实现的哈希对象
REDIS_HASH	REDIS_ENCODING_HT	使用字典实现的哈希对象
REDIS_SET	REDIS_ENCODING_INSET	使用整数集合实现的集合对象
REDIS_SET	REDIS_ENCODING_HT	使用字典实现的集合对象
REDIS_ZSET	REDIS_ENCODING_ZIPLIST	使用压缩列表实现的有序集合对象
REDIS_ZSET	REDIS_ENCODING_SKIPLIST	使用跳跃表和字典实现的有序集合对象

使用OBJECT ENCODING 查看一个数据库键的值对象的编码

127.0.0.1:6379> object encoding msg
"embstr"

通过 encoding 属性，来设定对象所使用的编码，而不是为特定类型的对象关联一种的固定的编码，极大地提升了redis的灵活性和效率，因为redis可以根据不同的使用场景来为一个对象设置编码，从而优化对象在某一场景的效率。

redis 使用 压缩列表作为列表对象的底层实现

• 因为压缩列表比双端链表可以更快的被载入缓存中
• 随着列表对象包含的元素越来越多，使用压缩列表的保存元素的优势减少，对象就会将底层实现从压缩列表转向功能更强，适合保存大量元素的双端链表上面。

7.2 字符串对象

字符串对象可以是 int，raw，或者embstr。

如果一个字符串对象保存的是整数值，并且这个整数值可以用long 来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面并将字符串对象编码设置为int。

如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于39字节，那么字符串对象将使用一个简单动态字符串SDS来保存这个字符串值，并将编码设置为raw.

127.0.0.1:6379> set msg "sheng ming de zhen di zai yu yun dong , shi jian shi jian yan zhen li de wei yi biao zhun"
OK
127.0.0.1:6379> strlen msg
(integer) 89

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

• embstr 编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次
• 释放embstr 编码的字符串对象只需要调用一次内存释放函数，而释放raw编码的字符串对象需要调用两次内存释放函数。
• 由于embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比raw编码的字符串对象，能够更好地利用缓存带来的优势。

long double l类型的浮点数在redis中也是作为字符串值来保存的，我们要保存一个浮点数到字符串对象，那么程序会先将这个浮点数转换成字符串值，然后在保存转换所得的字符串。在有需要的是程序会将保存在字符串对象里面的字符串转换为浮点数值，执行操作，然后在执行操作的浮点数值转换为字符串值。

7.2.1 编码的转换

int 编码的字符串对象和 embstr编码的字符串对象在条件满足的情况下，会被转换成为raw编码的字符串对象。

对于int编码的字符串对象来说，我们向对象执行了一些命令，使得这个对象保存的不再是整数值，而是一个字符串值，那么字符串对象编码将从 int 变为 raw。

7.3 列表对象

列表对象的编码方式可以是 ziplist，或者是linkedlist.

ziplist 编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点保存了一个列表元素。

另一方面，linkedlist编码的列表对象使用双端链表作为底层实现，每个双端链表节点（node）都保存了一个字符串对象，而每个字符串对象都保存了一个列表对象。

注意：linkedlist编码对象在底层结构中包含了多个字符串对象，字符串对象是redis 五种类型的对象中的唯一一种会被其他对象嵌套的

7.3.1 编码转换

当列表对象同时满足以下两个条件时，列表对象使用ziplist编码表示：

• 列表对象保存的所有字符串元素的长度都小于64字节，

• 列表对象保存的元素数量小于512个;不能满足这两个条件的列表对象需要使用linkedLIst 编码。

7.4 哈希对象

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

ziplist 编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会将保存了键的压缩列表节点推入到压缩列表表尾，然后在将保存了值的压缩列表节点推入到压缩列表表尾。

• 保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后。
• 先添加到哈希对象中的键值对会被放在压缩列表的表头方向，而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

另一个，hashtable的编码对象使用字典作为底层实现，哈希对象中非每个键值对都使用一个字典键值对来保存。

• 字典的每个键都是一个字符串对象，对象中保存了键值对的键
• 字典的每个值都是一个字符串对象，对象中保存了键值对的值

7.5 集合对象

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

int set 编码的集合对象使用整数集合作为底层实现，集合对象包含所有的元素都被保存在整数集合里面。

另一方面，hashtable的属性集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部被设为null

7.5.1编码转换

当集合对象同时满足以下两个条件时，对象使用intset编码

• 集合对象保存的所有元素都是整数值
• 集合对象保存的元素数量不超过512个

7.6 有序集合对象

有序集合的编码是ziplist或者skiplist。

ziplist编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，而第二个元素则保存分值

skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典表和跳跃表。zset结构中的zsl跳跃表按分值大小保存了所有的集合元素，除此之外zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素。

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

7.6.1 为什么使用跳表和字典来实现zset

有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现。因为在性能上会比单独使用的要高。

• 如果只使用字典表来实现有序集合，查找的复杂度虽然为o（1），但是字典是以无序的方式进行排序的，所以在进行范围型操作时，会对此进行排序而完成此排序需要o（NLOGN）时间复杂度，以及额外的o（N）内存空间保存值。

• 另一方面，如果只使用跳跃表来实现，执行范围操作优点会被保留，但是根据成员查找分值这一操作的复杂度则会为o（logN）

为了让有序集合的查找和范围型操作尽可能快地执行，redis采用了字典和跳跃表两种数据结构来实现有序集合。

7.6.2 编码的转换

当同时满足以下两个条件时，对象则会使用ziplist编码。

• 有序集合保存的元素数量小于128
• 有序集合保存的所有元素成元的长度都小于64 字节。

不能满足上两个条件的有序集合对象则使用skiplist编码。

7.7 类型检查与多态命令

rdis 中用于操作键的命令分为两种，其中一种命令可以对任何类型的键执行，比如del，expire，rename，type，object类型

• SET，GET，APPEND，STRLEN 等命令只能对字符串键执行
• HDEL,HSET,HGET,HLEN 等命令只能对哈希键执行
• RPUSH，LPOP，LINSTER，LLEN等命令只能对列表键处理
• SADD，SPOP，SINTER，SCARD 等命令只能对集合键处理
• ZADD，ZCARD，ZRANK，ZSCORE 等命令只能对有序集合键执行

7.7.1 类型检查的实现

类型检查是通过redisObject结构的type属性来进行实现的。

• 在执行一个类型特定命令之前，服务器会先检查输入数据库键的值对象是否为执行命令所需的类型，如果是的话，服务器就对键执行指定的命令。
• 否则服务器将拒绝执行命令，并返回一个类型错误。

7.7.2 多态命令

Redis 除了会根据值对象的类型来判断键是否能够执行指定命令外，还会根据值对象的编码方式，选择正确的命令实现代码来执行命令。

如列表对象有 ziplist和linkedlist两种编码方式可用，在对键执行命令时，服务器会根据键的值对象所使用的编码选择正确的命令。

如执行 llen命令

• 如果列表对象的编码为ziplist，那么说明列表对象的实现为压缩列表，程序会将使用ziplistlen函数来返回列表长度
• 如果列表编码为linkedlist，那么说明列表对象的实现为双端链表，程序将使用listlength函数返回链表长度

我们可以认为llen命令是多态的，无论对象使用的是ziplist编码还是linkedlist编码，命令都可以正常执行

7.8 内存回收

由于c语言不具备内存回收功能，所以redis在自己的对象系统中构建了一个引用计数

typedef    struct  redisObject{

   // 引用计数

int  refount;
  

 

}robj;
    

• 在创建一个新的对象时，引用计数的值会被初始化为1;
• 当对象被一个新程序使用时，它的引用计数值会被增一
• 当对象不再被一个程序使用时，它的引用计数值会被减一
• 当对象的引用计数值为0时，对象所占用的内存空间将会被释放

ps：在redis中引用计数法不会导致循环引用，因为ptr属性只会指向不同编码方式形成的数据结构，而不是对象。

7.9 对象共享

在创建键A与键B 具有相同数值 100 时，此时是让A与B 共享同一个字符串对象。

• 将数据库键的值指针指向一个现有的值对象

• 将被共享的值对象的引用计数增一

  

目前来说，Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从0 到9999的所有整数值，当服务器需要使用到这些对象时，就会使用共享对象而不是新创建对象。

7.9.1 为什么redis 对象不共享包含字符串的对象

在进行共享时，程序需要先检查给定的共享对象和键所想创建的目标对象是否相同，一个共享对象保存的值越复杂，验证所需要的复杂度就越高，消耗的cpu时间也会越多。

• 共享对象是保存整数值的字符串对象，验证操作为o（1）
• 共享对象 是保存字符串值的字符串对象，验证操作的复杂度为o（N）

7.10 重点回顾

• redis 数据库每个键值对的键和值都是一个对象
• redis 共有字符串，列表，哈希，集合，有序集合五种类型对象，每种类型至少有两种或以上的编码方式
• 服务器在执行某些命令时，会先检查给定键的类型能否执行的命令，而检查一个键的类型就是检查键的值对象类型
• Redis 对象系统带有引用计数的实现的内存垃圾回收机制
• redis 会共享值0-9999的字符串对象
• 对象会记录自己最后的一次被访问的时间，这个时间用于计算对象的空转时间。