/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    int len; // buf 中已占用空间的长度  
    int free; // buf 中剩余可用空间的长度
    char buf[];  // 数据空间
};

/*
 * 双端链表节点
 */
typedef struct listNode { 
    struct listNode *prev;  // 前置节点   
    struct listNode *next; // 后置节点
    void *value; // 节点的值
} listNode;

/*
 * 双端链表结构
 */
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;

redis的链表特性如下：
　　1）双向：每个listNode节点带有prev和next指针，可以找到前一个节点和后一个节点，具有双向性。
　　2）无环：list链表的head节点的prev和tail节点的next指针都是指向null。
　　3）带表头指针和尾指针：即上述的head和tail，获取头指针和尾指针的时间复杂度O(1)。
　　4）带链表长度计数器；即list的len属性，记录节点个数，因此获取节点个数的时间复杂度O(1)。
　　5）多态:链表使用void*指针来保存节点的值，可以通过list的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存不同类型的值。

/*
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
typedef struct dictht   
    dictEntry **table; // 哈希表数组
    unsigned long size;  // 哈希表大小；也是table数组大小
    unsigned long sizemask; // 哈希表大小掩码，用于计算索引值；总是等于 size - 1
    unsigned long used; // 该哈希表已有节点的数量
} dictht;

/*
 * 哈希表节点
 */
typedef struct dictEntry {
    void *key;   // 键
    union {      // 值
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;  // 指向下个哈希表节点，形成链表;指向另一个哈希表节点的指针，该指针将多个哈希值相同的键值对连接在一起，避免因为哈希值相同导致的冲突。
} dictEntry;

/*
 * 字典
 */
typedef struct dict {
    dictType *type; // 类型特定函数（不懂）
    void *privdata; // 私有数据（不懂）
    dictht ht[2]; // 哈希表,其中h{0}为平时使用的，h[1]为rehash使用的；
    int rehashidx; // rehash 索引；当 rehash 不在进行时，值为 -1（rehashing not in progress if rehashidx == -1）
    int iterators; // // 目前正在运行的安全迭代器的数量；（number of iterators currently running）（不懂）
} dict;

要将新的键值对加到字典，程序要先对键进行哈希算法，算出哈希值和索引值，再根据索引值，把包含新键值对的哈希表节点放到哈希表数组指定的索引上。redis实现哈希的代码是：
　　hash =dict->type->hashFunction(key);
　　index = hash& dict->ht[x].sizemask;
算出来的结果中，index的值是多少，则key会落在table里面的第index个位置（第一个位置index是0）。
其中，redis的hashFunction，采用的是murmurhash2算法：即使加入的键是有规律的，算法仍能给出一种很好的随机分布性，并且算法的计算速度也非常快。

上图最左边的就是zskiplist结构，该结构包含以下属性：
1 header：指向跳跃表的表头表头节点。
2 tail：指向跳跃表的表尾节点。
3 level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
4 length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

位于zskiplist结构右方的四个zskiplistNode结构，该结构包含一下属性：
1 层（level）：节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L2代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的举例。在上图中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
2 后退指针：节点中用BW（backward）字样标记节点的后退指针，他指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
3 分值（score）：各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排量。
4 成员对象（obj）：各个节点中o1、o2和o3是节点所保存的成员对象。

注意：表头节点和其他节点的构造是一样的；表头节点也有后退指针、分值和成员对象，不过表头节点的这些属性不会被用到，所以图中省略了。

/* ZSETs use a specialized version of Skiplists */
/*
 * 跳跃表节点
 */
typedef struct zskiplistNode {
    robj *obj; // 成员对象
    double score;    // 分值
    struct zskiplistNode *backward; // 后退指针
    // 层
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned int span; // 跨度
    } level[];
} zskiplistNode;

跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通这些层来加快访问其他节点的速度，一般来说，层数越多，访问其他节点的速度就越快。

每次创建一个新的跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”。下图就是带有不同层高的节点。

每个层都有一个指向表尾方向的前进指针，用于从表头向表尾方向访问节点。下图用虚线表示出了程序从表头向表尾方向，遍历跳跃表中所有节点的路径：

       a 迭代程序首先访问跳跃表的第一个节点（表头），然后从第四层的前进指针移动到表中的第二个节点。
       b 在第二个节点时，程序沿着第二层的前进指针移动到表中第三个节点。
       c 在第三个节点时，程序同样沿着第二层的前进指针移动到表中的第四个节点。
       d 当程序再次沿着第四个节点的前进指针移动式，他碰到一个null，程序知道这时已经到达了跳跃表的表尾，于是结束这次遍历。

层的跨度用于记录两个节点之间的距离：
a 两个节点之间的跨度越大，他们相距得就越远。
b 指向null的所有前进指针的跨度都为0，因为他们没有连向任何节点。
       初看上去，很容易以为跨度和遍历操作有关，但实际上并不是这样，遍历操作只使用前进指针就可以完成了，宽度实际上是用来计算排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。
       举个例子，下图用虚线标记了在跳跃表中查找分值为3.0、成员对象为o3的节点时，沿途经历的层：查找的过程只经过了一个层，并且层的跨度为3，所以目标节点在跳跃表中的排位为3。

 再举个例子，下图用虚线标记了在跳跃表中查找分值为2.0、成员对象为o2的节点时，沿途经历的层：在查找节点的过程中，程序经过了两个跨度为1的节点，因此可以计算出，目标节点在跳跃表中的排位为2。

节点的后退指针用于从表尾向表头方向访问节点：跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。

节点的分值（score属性）是一个double类型的浮点数，跳跃表中的所有节点都按照分值从小到大来排序。
节点的成员对象是一个指针，他指向一个字符串对象，而字符串对象则保存着一个SDS值。
在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分值相同的节点按照成员对象在字典中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头方向），而成员对象较大的节点则会排在后面（靠近表尾的方向）。
举个例子，在下图所示的跳跃表中，三个跳跃表节点都保存了相同的分值10086.0，但保存成员对象o1的节点却排在保存成员对象o2和o3的节点之前，由顺序可知，三个对象在字典中的排序哦o1<=o2<=o3。

/*
 * 通过使用一个zskiplist结构来持有这些节点，程序可以更方便地对整个跳跃表进行处理，比如快速访问跳跃表的表头节点和表尾节点，或者快速地获取跳跃表节点的数量等信息。
 * header和tail指针分别指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头及诶点和表尾节点的复杂度为O(1)。
 * 通过使用length属性来记录节点的数量，程序可以在O(1)复杂度内返回跳跃表的长度。
 * level属性则用于在O(1)复杂度内获取跳跃表中层高最大的那个节点的层数量，注意表头节点的层高并不计算在内。
 */
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;    // 表头节点和表尾节点
    unsigned long length;    // 表中节点的数量
    int level;    // 表中层数最大的节点的层数
} zskiplist;

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

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

struct redisServer { 
    redisDb *db; // 一个数组，保存着服务器中的所有数据库
    int dbnum; // 服务器的数据库数量，在初始化服务器时，程序会根据服务器状态的dbnum属性来决定应该创建多少个数据库，默认是16
    struct saveparam *saveparams; // 记录了保存条件的数组 它包括time_t seconds int changes秒数和修改次数 
    long long dirty; // 修改计数器
    time_t lastsave; // 上一次保存的时间
    sds aof_buf; // AOF缓冲区
    ...
}
 
typedef struct redisClient { 
    redisDb *db; // 客户端正在使用的数据库
    ...
}
 
typedef struct redisDb { 
    dict *dict; // 数据库键空间，保存着数据库中的所有键值对 key永远是字符串对象，value可以是五大类型
    dict *expires // 过期字典，保存着键的过期时间；key为指向上面那个dict的key，value为过期时间的毫秒时间戳
    ...
}

save命令：会阻塞redis服务器进程，知道RDB文件创建完毕为止，在服务器进程阻塞期间，服务器不能处理任何命令请求；
bgsave命令：会派生出一个子进程，然后由子进程负责创建RDB文件，服务器不能处理任何命令请求；

因为AOF文件的更新频率通常比RDB文件的更新频率高，所以：
1）如果服务器开启了AOF持久化功能，那么服务器会优先使用AOF文件来还原数据库状态；
2）只有在AOF持久化功能处于关闭状态时，服务器才会使用RDB文件来还原数据库状态；

Redis的复制功能分为同步（sync）和命令传播（command propagate）两个操作：
同步操作用于将服务器的数据库状态更新至主服务器当前的数据库状态；
命令传播操作则用于在主服务器的数据库状态被修改，导致主从服务器的数据库状态出现不一致时，让主从服务器的数据库重新回到一致状态；

Redis中，从服务器对主服务器的复制可以分为以下两种情况：
初次复制：从服务器以前没有复制过任何主服务器，或者从服务器当前要复制的主服务器和上一次复制的主服务器不同；
断线后复制：处于命令传播阶段的主从服务器因为网络原因而中断了复制，但从服务器通过自动重新连接连上了主服务器，并继续复制主服务器；

为了解决旧版复制功能在处理断线重复机制情况时的低效问题，Redis从2.8版本开始，使用PSYNC命令代替SYNC命令来执行复制时的同步操作：
完整同步（full resynchronization）：用于处理初次复制的情况，和SYNC命令的执行步骤基本一样，他们都是通过让主服务器创建并发送RDB文件，以及向从服务器发送保存在缓冲区里面的写命令来进行同步；
部分同步（partial resynchronization）：用于处理断线后重复机制，当从服务器在断线后重新连接主服务器时，如果条件允许，主服务器可以将主服务器连接断开期间执行的写命令发送给从服务器，从服务器只要接收并执行这些写命令，就可以将数据更新至主服务器当前所处的状态；

在命令传播阶段，从服务器默认会以每秒一次的频率，向主服务器发送命令：REPLCONF ACK <replication_off>，其中 replication_offset 是从服务器当前的复制偏移量。
发送REPLCONF ACK 命令对于主从服务器有三个作用：
1）检测主从服务器的网络连接状态
2）辅助实现min-slaves选项
3）检测命令丢失：主从服务器的复制偏移量是否一致