第2章  简单动态字符串sds

使用SDS(simple dymastic string)简单动态字符串的抽象类型，用作默认字符串

使用sds保存db中的字符串值，还被用来做缓冲区，AOF模块的AOF缓冲区，客户端状态中的输入输出缓冲区。

type sdshdr struct {
    // 记录buf数组中已使用的字节数量，等于sds所保存字符串的长度
    len int
    // 记录buf数组中未使用字节的数量
    free int
    // 字节数组
    buf []byte
}

sds用未使用空间的优化策略：

空间预分配

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

// todo 额外未使用空间计算公式

惰性空间释放

用来优化sds的字符串缩短操作，当sds的api需要缩短sds保存的字符串时，程序并不立即使用内存重新分配来挥手缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，以等待将来使用。

二进制安全

sds的api都是二进制安全的，所有sds api都会以处理二进制的方式来处理sds存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、假设，数据在写入时是什么样的，被读取时就是什么样的。

与C字符串的比较

 

第3章 链表

列表键：当一个列表键包含了数量比较多的元素，或者列表中包含的元素都是比较长的字符串时，redi时就会使用链表作为列表键的底层实现。

应用

发布与订阅

慢查询

监视器

链表的数据结构

type ListNode struct {
    // 前置节点
    pre *ListNode
    // 后置节点
    next *ListNode 
    // 节点的值
    value interface{}
}

 

第4章 字典

又称为符号表、关联数组、映射，保存键值对的数据结构

使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

键冲突

当有两个或者以上数量的键被分配到了哈希表数组的同一个索引上面时，就称这些键发生了冲突。

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

rehash(重新散列)

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

扩展或收缩哈希表可以通过rehash(重新散列)操作来完成。rehash步骤如下：

//todo

哈希表的扩展与收缩

当以下条件的任意一个满足，程序会自动开始对哈希表执行扩展操作：

1.服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1.

2.服务器目前正在执行bgsave或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5

当哈希表的负载因子小于0.1，程序自动开始对哈希表进行收缩。

第5章 跳跃表

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

redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串，redis就会使用跳跃表作为有序集合键的底层实现。

第6章 整数集合intset

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

可以保存类型未int16_t，int32_t，int64_t的整数值，并且保证集合中不会出现重复元素。

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

contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项(item)，各个项在数组中按值的大小从小到大有序的排列，并且数组中不包含任何重复项。

虽然contents是int8_t类型，但是contents数组的真正类型取决于encoding的值。

如果encoding是INTSET_ENC_INT16，那么contents就是一个int16_t类型的数组，数组里的每个项都是int16_t类型的整数值。

如果encoding是INSET_ENC_INT32,那么contents数组是int32_t类型的。

如果encoding是INTSET_ENC_INT64，那么contents是int64_t类型的数组。

length记录了整数集合包含的元素数量，即contents数组的长度。

升级

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

升级整数集合并添加新元素的步骤：

1.根据新元素列席，扩展整数集合底层数组的空间大小，并为新元素分配空间。

2.将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确位上，并且在放置元素过程中，需要继续维持底层数组的有序性质不变。

3.将新元素添加到底层数组里面。

 

 

升级的好处

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

节约内存

要让一个数组可以同时保存int16_t，int32_t，int64_t三种类型的值，最简单的做法是使用int64_t作为底层实现。

但是如果只存储int16_t和int32_t的数据会浪费内存。

如果一直向整数集合添加int16_t类型的值，那么底层contents就会一直是int16_t类型，只有在要将int32_t或者int64_t添加到集合，才会对数组进行升级。

降级

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

第7章 压缩列表

是列表键和哈希键的底层实现之一。是为了节约内存而开发的。由一系列特殊编码的连续内存块组成的顺序型的数据结构。一个压缩列表可以包含多个节点entry，每个节点可以保存一个字节数组或者一个整数值。

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

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

压缩列表的构成

压缩列表节点组成：

previous_entry_length

以字节为单位，记录了压缩列表中前一个节点的长度，取值为1或者5。程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。

如果前一节点的长度小于254字节，那么previous_entry_length属性的长度为1字节：前一字节的长度就保存在这个字节里面。

如果前一字节的长度大于等于254字节，那么previous_entry_length属性的长度为5字节，其中属性的第一字节会被设置为0xFE(十进制254)，而之后的4个字节则用来保存前一节点的长度。

encoding

记录了几点的content属性所保存数据的类型及长度：

1.一字节、两字节或者五字节长，值的最高位为00，01或者10的是字节数组编码，这种编码表示节点的content属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录。

2.一字节，值的最高位以11开头的整数编码，这种编码表示节点的content属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录。

content

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

连锁更新

添加新节点，删除节点都会引发连锁更新。

因为连锁更新在最坏情况下需要对压缩表执行N次空间重新分配，而每次空间重新分配的最坏复杂度为O(N)，所以连锁更新的最坏复杂度为O(N^2)。

尽管连锁更新复杂度高，但是造成性能问题的几率很低：

1.压缩列表里恰好有多个连续的、长度介于250字节至253字节之间的节点，连锁更新才有可能被引发，在实际中这种情况并不多见。

2.即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响。

第8章 对象

redis对象系统：字符串对象，列表对象，哈希对象，集合对象，有序集合对象

redis在执行命令之前，根据对象类型来判断一个对象是否可以执行给定的命令，可以针对不同的使用场景，为对象设置多种不同的数据结构实现。

redis对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象占用的内存就自动被释放；

还通过引用计数技术实现了对象的共享机制，可以在适当条件下，通过让多个数据库共享同一个对象来节约内存。

redis的对象带有访问时间记录信息，该信息可以用于计算数据库键的空转时长，在服务器启用了maxmemory功能情况下，空转时长较大的那些键可能会优先被服务器删除。

对象的类型和编码

redis使用对象来表示数据库中的键和值，每次当在redis数据库中虚拟键一个键值对时，至少会创建两个对象，一个对象用作键值对的键(键对象)，另一个对象用作键值对的值(值对象)。

redis键总是一个字符串对象，而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象中的其中一种。

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

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

类型

编码和底层实现

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

字符串对象

字符串对象的编码可以是int，raw，embstr

字符串命令的实现

列表对象

列表对象的编码可以是ziplist或者linkedlist

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

linkedlist编码的列表对象使用双端链表作为底层实现，每个双端链表节点都保存了一个字符串对象，每个字符串对象都保存了一个列表元素。

列表命令实现

哈希对象

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

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

1.保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后

2.先添加到哈希对象中的键值对会被放在压缩列表的表头方向，而后添加的会被放在压缩列表的表尾方向。

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

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

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

当哈希对象同时满足以下两个条件时，哈希对象使用ziplist编码(否则其他的都使用hashtable编码)：

1.哈希对象保存的所有键值对的键和值的字符串长度都小于64字节

2.哈希对象保存的键值对的数量小于512

哈希命令实现

集合对象

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

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

hashtable编码集合对象使用字典作为底层实现，字典的每个键都是字符串对象，每个字符串对象都包含了一个集合元素，而字典的值全部都设置为NULL。

编码的转换

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

1.集合对象保存的所有元素都是整数值

2.集合对象保存的元素数量不超过512

集合命令实现

有序集合对象

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

ziplist编码的压缩列表使用压缩列表作为底层实现，每个集合元素使用两个紧在一起的压缩列表节点来保存，第一个节点保存元素的成员(member)，第二个元素保存元素的分值(score)。

压缩列表内的集合元素按照分值从小到达排序，分值较小的元素被放置在靠近表头的方向，分值较大的元素放置在靠近表尾的方向。

skiplist编码的有序集合使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表

typedef struct zset {
    // 跳跃表，按分值从小到大保存了集合元素，每个跳跃表节点都保存了一个集合元素，跳跃表节点的object属性保存了元素的成员，而跳跃表节点的score保存元素的分值
    zskiplist *zsl;
    // 字典，为有序集合创建了一个从成员到分值的映射，字典中的每个键值都保存了一个集合元素，键保存了元素成员，字典的值保存了元素的分值
    dict *dict;
}zset;

有序集合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。

虽然zset结构同时使用跳跃表和字典来保存有序集合，但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存元素不会产生任何重复成员或分值，也不会因此浪费额外内存。

有序集合为什么要同时使用字典和跳跃表实现？

编码的转换

当有序集合对象同时保存以下两个条件，对象使用ziplist编码：

1.有序集合保存的元素数量小于128个

2.有序集合保存的所有元素成员的长度都小于64字节

命令实现

类型检查与命令多态

1.可以对任意类型的键执行，比如DEL，EXPIRE，RENAME，TYPE，OBJECT命令

2.只能对特定类型的键执行：

    字符串：SET，GET，APPEND，STRLEN

    哈希键：HDEL，HSET，HGET，HLEN

   列表键: RPUSH，LPOP，LINSERT，LLEN

   集合键：SADD，SPOP，SINTER，SCARD

  有序集合键：ZADD，ZCARD，ZRANK,ZSCORE

类型检查的实现

通过redisObject结构的type类型实现：

1.在执行一个类型特定命令之前，服务器会先检查输入数据库键的值对象是否为执行命令所需的类型，如果是的话，服务器就对键执行指定的命令。

2.否则，服务器将拒绝执行命令，并向客户端返回一个类型错误。

多态命令的实现：

内存回收

redis对象系统中的引用技术实现内存回收机制，程序跟踪对象的引用技术信息，在适当的时候自动释放对象并进行内存回收。

每个对象的引用技术信息由redisObject结构的refcount记录。

typedef struct redisObject {
    // ....
    // 引用计数
    int refcount;
} robj;

对象的引用基数信息会随着对象的使用状态而不断变化：

1.在创建一个新对象的时候，引用基数的值会被初始化为1

2.当对象被一个新程序使用时，它的引用计数值会被递增1

3.当对象不再被程序使用时，引用计数减1

4.当对象的引用计数值为0时，对象所占用的内存被释放

对象共享

对象的引用计数属性除了用来内存回收，还带有对象共享属性。

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

对象的空转时长

redisObject的lru属性，记录了对象最后一次被命令程序访问的时间

typedef struct redisObject {
    // ...
    // 对象最后一次被程序访问的时间
    unsigned lru:22;
    // ...
}

OBJECT IDLETIME可以打印出给定键的空转时长： 当前时间 -  键的值对象的lru时间

键的空转时长除了可以用object ieletime打印出来，还可以方便内存回收。

如果服务器打开了maxmemory选项，并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru，那么当服务器占用的内存数超过了maxmemory选项设置的上限值时，空转时长较高的会优先被服务器释放，从而回收内存。

第9章 数据库

服务器中的数据库

将所有数据都保存在服务器状态redis.h/redisServer结构的db数组中。db数组的每个项都是一个redis.h/redisDb结构，每个redisDb结构代表一个数据库。

struct redisServer {
    // ...
    // 一个数组，保存着服务器中的所有数据库
    redisDb *db;
    // 服务器的数据库数量:在初始化服务器时，程序根据服务器状态的dbnum属性决定应该创建多少数据库.值由服务器配置的database选项决定，默认值为16，即redis服务器默认会创建16个数据库。
    int dbnum;
    // ...
}

切换数据库

默认，redis客户端的目标数据库为0号数据库，但客户端可以执行select来切换目标数据库。

在服务器内部，客户端状态redisClient结构的db属性记录客户端当前的目标数据库，是一个指向redisDb结构的指针。

typedef struct redisClient {
    // ...
    // 记录客户端当前正在使用的数据库。指针指向redisServer.db数组中的其中一个元素，而被指向的元素就是客户端的目标数据库。
    redisDb *db;
    // ...
} redisClient;

通过修改redisClient.db的指针，让它指向服务器中的不同数据库，从而实现切换目标数据库的功能，即select命令实现的原理。

数据库创建空间

typedef struct redisDb {
    // ...
    // 数据库键空间，保存着数据库中的所有键值对
    dict *dict;
    // ...
}

键空间和用户所见的数据库是直接对应的：

1.键空间的键即数据库的键，每个键都是一个字符串对象

2.键空间的值即数据库的值，每个值可以是字符串对象、列表对象、哈希表对象、集合对象和有序集合对象中的任意一种redis对象

添加新键

添加一个新键值到数据库，即将一个新键值对添加到键空间的字典里面，其中键位字符串，而值则为任意中类型的redis对象。

删除键

删除数据库中的一个键，实际上是在键空间删除键对应的键值对对象。

更新键

对键空间里面的键对应的值对象进行更新。

读写键时的维护操作

1.在读取一个键之后(读操作和写操作都要对键进行读取)，服务器会根据键是否存在来更新服务器的键空间命中(hit)次数或不命中(miss)次数。这两个值可以早INFO stats命令的keyspace_hits和keyspace_misses查看。

2.在读取一个键之后，服务器会更新键的LRU(最后一次使用)时间。

3.如果服务器在读取一个键发现该键已经过期，那么服务器会先删除这个过期键，然后才执行剩下的其他操作。

4.如果客户端有使用WATCH命令监视某个键，那么服务器在对被监视的键进行修改之后会将这个键标记为脏(dirty)，从而让事务程序注意到这个键已经被修改过。

5.服务器每次修改一个键后，都会对脏(dirty)键计数器的值增1，这个计数器会触发服务器的持久化以及复制操作。

6.如果服务器开启了数据库通知功能，那么在键进行修改之后，服务器将按配置发生相应的数据库通知。

设置键的生存时间或过期时间

expire或者pexpire命令设置键的生存时间，在经过指定的时间后，服务器会自动删除生存时间为0的键。

expirate或者pexpirate设置键的过期时间，过期时间到了服务器自动从数据库删除这个键。

设置过期时间

保存过期时间

typedef struct redisDb {
    // ...
    // 过期字典，保存着键的过期时间。指向键空间的某个键对象，是一个long long类型的整数，保存了键所指向的数据库键的过期时间
    dict *expires;
    // ...
}redisDb;

移除过期时间

persist， pexpireat