1 缓存数据库的结构分析

1.1 使用的数据结构和数据类型对象

• 动态字符串

动态字符串结构体是SDS定义，由源码sds.h/sdshdr结构表示一个SDS值。

其c实现了包括减少修改字符串带来的内存分配次数，空间预分配方案，惰性空间释放方案，兼容部分C字符串函数，避免缓冲区溢出等。

• 链表
  链表提供了高效的节点重排能力，以及顺序性的节点访问方式，可以通过增删节点灵活调整链表长度。
  reids的数据结构 列表 底层实现之一是链表。

redis的链表实现有以下特点：

    无环双端链表，带有表头指针和表尾指针。 通过list结构的head指针和tail指针。
    多态支持，链表节点使用 void* 指针保存节点值，可以通过list结构的dup，free，match三个属性为节点值设置类型特定函数，以保持不同数据类型。

• 字典

保存键值对的抽象数据结构，又被称之为 symbol table，关联数组 associative array，映射 map
字典每个键唯一，但是值可以为空或相同。

redis使用 murmurHash 算法作为底层实现，这个算法在2008年出现，即使输入的键有规律，算法仍能给出一个很好的随机分布特点。
有兴趣的可以搜索它。

每个哈希表节点都有一个next指针，多个哈希标节点可以使用next指针构成一个单向链表，被分配到同一索引的多个节点可以用这个单向链表链接。

扩展和收缩hash表可以通过执行 rehash重新散列完成。

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

跳跃表效率可以和平衡树对比，但是实现更为简单，所以有不少程序使用跳跃表代替平衡树。
比如一个有序集，会员信息

    ZRANGE member-price 0 2 WITH-SCORES
    ZCARD member-price

member-price 有序集合的全部数据都保存在一个跳跃表，每个表节点都保存一个成员的信息。

与链表和字典不同，redis缓存数据库有两个地方使用这个结构，一个是有序集合键，另一个是集群节点的内部数据结构。

它由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息，比如表头，表尾节点，长度。Node保存跳跃表节点。

每个跳跃表节点层高都是1到32个随机数。在同一个跳跃表，多个节点可以包括相同分值。每个节点成员对象必须唯一。

跳跃表节点按分值大小进行排序。 节点按成员对象大小排序。

• 整数集合
  redis缓存集合键的底层实现是 整数集合 inset。当一个集合包括集合元素不多时，Redis就使用整数集合作为集合键底层实现。

如果集合只包括2个整数元素，这个集合键底层实现就是 整数集合。

    127.0.0.1:6379> SADD numb 1 2
    (integer) 2 
    127.0.0.1:6379> OBJECT ENCODING numb
    "intset"

整数集合可以保存整数值的抽象数据结构，int16_t, int32_t, int64_t,并保存集合元素不重复

每当我们需要把一个新元素添加到整数集，并且新元素类型比整数集合全部元素都长，整数集合需要升级，然后添加。

升级过程就是一般的三个升级步骤：

    1， 分配新空间； 
    2，底层数组元素全部转换为新元素相同类型，放置到新空间正确位置，维护相对顺序；
    3，新元素添加到新空间。

整数集合支持升级操作，但是不支持降级操作。

• 压缩列表

ziplist 时列表键和哈希键的底层实现。 当一个列表键只包括少量项目，并且每个列表项要么小整数型，要么就是长度比较短的字符串，

那么Redis就使用压缩列表做列表键底层实现。

    HMSET peoples "name" "jack" "age" 59 "job" "programmer"
    OK
    127.0.0.1:6379> OBJECT ENCODING peoples
    "ziplist"

当一个哈希键只包括少量键值对，并且键值对时小整数或短字符串，redis就使用压缩列表做哈希键底层。

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

<= 63 自己的字节数组 2^6 -1
<= 16383 字节的字节数组 2^14 - 1
<= 4294967295 的字节数组 2^32 -1

整数值可以是以下6个长度之一

4字节  0~12之间的无符号整型
1字节  有符号整型
3字节 有符号整型
int16_t 类型整型
int32_t 
int64_t

每个压缩列表ziplist 由 previous_entry_length, encoding, content 三个部分组成。
它们分别记录压缩列表

previous_entry_length 前一个节点长度（属性长度1或5字节），

encoding 节点的content属性所保存数据的类型和长度，

content 保存节点值

压缩列表是一种节省内存的顺序型数据结构。 常被用作列表键和哈希键的底层实现。
它可以包括多个节点，每个节点保存一个字节数组或整数值。

添加新节点到压缩列表，或者从压缩列表删除节点，可能引发连锁更新，但是几率不高。

• 数据类型对象系统

Reids使用以上这些数据结构时，使用的一个独特的对象系统，这个系统包含字符串对象，列表对象，哈希对象，结合对象。有序集合对象这些。

根据对象指令，redis判断是否符合执行条件，并且基于引用计数的方式回收内存 和 对象共享，以方便在适当条件下，通过让多个数据库键共享一个对象节省内存。

    127.0.0.1:6379> RPUSH zst 1 2 3 1999 "hello" "world"
    (integer) 6
    127.0.0.1:6379> OBJECT ENCODING zst
    "quicklist"

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

可以查看它们的类型：

字符串类型对象 REDIS_STRING

    SET infos "hello world"
    TYPE infos
    string

哈希类型对象 REDIS_STRING

    HMSET peoples "name" "jack" "age" 59 "job" "programmer"
    TYPE peoples
    hash  

列表对象 REDIS_LIST

    RPUSH rst 1 2 3 1999 "hello" "world"
    TYPE rst
    list

集合对象 REDIS_SET

    SADD numb 1 2 apple banana    
    TYPE numb
    set

有序集合对象 REDIS_ZSET

    ZADD price 8.5 apple 10.1 banana 9.8 cherry 
    TYPE price
    zset

未定义

    TYPE nothing
    none

2 数据库

• 数据库的实现

服务器持久化存储数据库的方法，
redis缓存将全部数据库保持在 服务器状态 redis.h/redisServer 结构的db数组中。

db数组每个项都是一个 redis.h/redisDb 结构。

在redis初始化时，程序根据服务器状态 dbnum属性决定创建多少数据库。
默认为16个，并且用户没有指定使用哪一个时，默认使用数据库0.

• 键空间：

db数组每个项都是一个 redis.h/redisDb 结构，这个字典被称之为键空间。

键空间的键也就是redis数据库的键。 值可以是字符串对象，列表对象，哈希表对象，集合对象，有序集对象任意一个Redis对象。

在redis数据库中添加一个键，也就是在健空间字典添加一个键。 从redis数据库删除一个键，也就是从键空间删除一个键。

• 键生存周期，过期策略

    指令：
  
    EXPIRE 
    PEXPIRE
  

在某个时间点过期

    EXPIREAT
    PEXPIREAT

本质上都在底层执行 PEXPIREAT 指令。

数据库接收客户端的秒或毫秒精度的键设置生存时间，TTL。
在经过指定秒数或毫秒之后，服务器就自动删除生存时间0的键。

TTL，PTLL指令接受一个带有生存时间或者过期时间的键，返回这个键的剩余生存时间，
也就是返回距离这个键被服务器自动删除还有多长时间。

SET key value
EXPIRE key 1000
TTL key

在底层的expires字典保存了数据库中全部键的过期时间。 也被称之为过期字典

过期字典键是一个指针，这个指针指向键空间某个键对象也就是某个数据库键。
过期字典值是一个 long long 类型整数，这个整数保存了键所指向的数据库键过期时间，毫秒精度的unix时间戳。

取消过期时间

        127.0.0.1:6379> set name jack
        OK
        127.0.0.1:6379> pexpire name 10000000
        (integer) 1
        127.0.0.1:6379> get name
        "jack"
        127.0.0.1:6379> ttl name
        (integer) 9996
        127.0.0.1:6379> ttl name
        (integer) 9993
        127.0.0.1:6379> PERSIST name
        (integer) 1
        127.0.0.1:6379> ttl name
        (integer) -1
        127.0.0.1:6379> get name
        "jack"

确定过期键状态

通过过期字典，程序可以用以下步骤检查一个给定键是否过期：

1 检查给定键是否存在过期字典，如果是，则取得过期时间
2 检查Unix时间戳是否大于键过期时间，如果是，键已过期，否则，键未过期。

• 过期键删除策略
  缓存清理过期键的方式有三种

    1，定时删除
    用户最友好的方式，但是对CPU时间不友好。
    设置过期时间的同时，创建一个定时器 timer，让定时器在键的过期时间去临时，立即对键执行删除操作。
    使用大量定时器，是不现实的。
    2，惰性删除
    放任键过期不管，但是每次从键空间获取键，都检查是否过期，没有过期就返回改键。否则就删除。
    对CPU友好，只有程序取出键时才对键进行检查和删除。
    如果永远不使用该键，那么内存将被永远占用。
    3，被动定期删除 
    每隔一段时间，程序对数据库进行一次检查，删除其中过期键，算法决定删除多少过期键，以及检查多少数据库。
  

一般场景配合定时删除和惰性删除，就可以匹配大多数场景。

• 持久化 RDB 与 AOF

在执行SAVE指令或BGSAVE指令后，redis将创建一个新的RDB文件。
程序对数据库的键进行检查，已经过期的不会被保存。 因此，数据库中包含过期键不会造成持久存储的影响。

服务启动时，加载RDB文件，如果服务为主服务，那么载入RDB文件时，程序会文件保存的键进行检查，没有过期的键被加载。

如果服务器是备机，在载入RDB文件时，将载入全部键，并且从主服务同步键的状态。

当过期键被惰性删除或定期删除后，程序向AOF文件追加 append 一条 DEL指令，显式记录该键已经被删除。
如果客户端通过 GET 类似的指令访问过期键 name，

1 服务器从数据库删除 name
2 追加一条 DEL name 到 AOF文件
3 向执行GET指令的客户端返回空回复。

数据库包括过期键，不会对AOF及其重写造成影响。
如果服务器为复制服务器，那么键的删除操作由主服务器控制。

• 事件处理

文件事件，
redis基于Reactor模式开发了字节的网络事件处理器，这个处理器被称之为文件事件处理器 file event handler

    1 文件事件处理器使用 I/O 多路复用同时监听多个套接字，并根据套件字目前执行的认为为套接字关联不同事件处理。

    2 当被监听的套接字准备好执行链接应答 accept，读取 read， 写入 write， close 关闭时，与操作相对的文件事件将产生。

此时文件事件处理器就会调用套接字之前关联的事件处理器处理这些事件。

单线程redis服务，通过多路复用的方式高性能监听文件事件，可以很好地与redis服务器中其他同样单线程模块对接。保持简单性。

套接字                                               事件处理器
    socket1                                        -->   命令请求处理器
    socket2  --> I/O多路复用程序  --> 文件事件调度器 -->   指令回复处理器
    socket3  -->                                   -->   连接应答处理器
    socket4                                         

文件事件对套接字操作的抽象，每当一个套接字准备好执行连接应答 accpet，写入，读取，关闭时，就此时文件事件。

尽管多个事件可能并发产生，但是IO多路复用总是将产生的套接字放入一个队列，再处理这个队列：有序，同步地，每次一个套接字
当处理完上一个后，再处理下一个。

一个完整的客户端与服务器通信处理过程如下：
1 服务器 AE_READ-ABLE 事件处于监听状态下，而该事件所对应的处理器为连接应答处理器。

2 这是一个redis客户端向服务器发起连接，监听套接字将产生AE_READABLE事件，触发连接应答处理器执行。

处理器将应答客户端的连接请求，并将客户端套接字 AE_READ-ABLE 事件与命令请求处理器关联。

3 客户端向服务器发一条指令执行，客户端将产生 AE_READABLE事件，引发命令请求处理器执行。

4 执行命令产生响应的回复，服务器将客户端套接字 AE_WRITABLE事件与命令回复处理器关联。 当客户端尝试读取指令回复时。

触发命令回复处理器执行，当命令恢复处理器将命令回复全部写入到套接字后，服务器就会解除客户端套接字的 AE_WRITABLE事件与回复处理器的关联。

时间事件

定时事件，让一个程序在指定时间后执行一次，比如，让程序X在当前事件在30毫秒后执行一次。

周期性事件，比如每隔30秒执行一次。

时间事件由三部分组成：

id： 服务器为事件事件创建的全局唯一ID 标识号。 ID号按从小到大顺序递增，新事件的ID号总是大一些。

when： 毫秒精度的UNIX时间戳，记录了时间事件到达arrive的事件

timeProc： 时间事件处理器，一个函数。 当事件事件到达，服务就调用相关处理器处理事件。

周期性事件更加通用。

时间事件在底层被存入一个无序链表，每当时间执行器运行，它就遍历整个链表，查找已到达时间的事件，并调用相关事件处理器。

比如serverCron函数的应用，持续运行的Redis服务需要定期对自身资源和状态进行检测和调整，从而确保服务器可以长期，稳定运行。

这些定期操作由 redis.c/serverCron负责执行

1，更新服务器各类统计信息，比如时间，内存占用，数据库占用
2，清理数据库过期键值对
3，关闭和清理连接失效客户端
4，尝试进行AOF或RDB持久化操作
5，负责主服务与从服务的同步操作
6，如果是集群，对集群进行定期同步和连接测试

redis服务器以周期性事件方式运行serverCron函数，
在服务器运行期间，每隔一段时间（由配置的hz控制），serverCron就执行一次，直到服务器关闭。

默认情况下，"hz "被设置为10。提高该值将在Redis 空闲时使用更多的 CPU Redis 处于空闲状态，但同时也会使 Redis 在以下情况下反应更迅速有许多键同时到期，超时可能被处理得更精确。

范围在1到500之间，但是超过100的值通常不是个好主意。

大多数用户应该使用默认的10，并将其提高到只有在需要非常低的延迟的环境下才可以提高到100。

• 服务器的调度执行方式

数据库添加，删除，查看，更新操作的实现方法。

由于存在文件事件和时间事件，决定何时分类处理它们将很重要。

事件的调度和执行由 ae.c/aeProcessEvents负责。它主要由以下步骤：

1， 获取到达时间离当前时间最接近的时间事件
2， 计算最接近的时间事件距离达到还有多少毫秒
3，如果事件已达到时间，那么 remaind_ms 的值可能为负，设置为0
4，根据 remaind_ms 的值，创建timeval结构
5， 阻塞并等待文件事件产生，最大阻塞事件由传入的timeval结构决定
6，如果remaind_ms 值为0，那么 aeApiPoll 调用之后马上返回，不阻塞
7，处理全部已产生的文件事件
8，处理全部已到时间点的时间事件

redis服务是一个事件驱动程序，分为文件事件和时间事件。
文件事件基于Reactor模式实现的网络通信程序。

文件事件是对接套接字操作的抽象： 每次套接字变为可应答 acceptable，可写 writable，可读 readable 相关事件就产生。

文件事件分为读/写两类（AE_READABLE, AE_WRITEABLE）.

时间事件分为定时事件和周期性事件，服务器一般只执行serverCron函数这一个时间事件，并且是周期性的，通常会晚毫秒级执行时间。

文件事件和时间事件为合作关系，服务器轮流处理，不会进行抢占。

服务器启动到可以处理客户端数据需要进行以下步骤：

1 初始化服务器状态
2 载入服务器配置
3 初始化服务器数据结构
4 还原数据库状态
5 执行事件循环。