redis源码分析

redis数据结构

sds

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

相比C字符串，SDS具有以下优势:

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

二进制安全: 二进制数据在写入时是怎么样的，读取时就是怎么样，那么就是二进制安全的

list

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;

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

• redis链表结构实现为双向无环链表
• 每个链表使用一个list结构来表示，这个结构带有表头、表尾节点指针以及链表长度等信息
• 通过为链表设置不同的类型特定函数，redis的链表可以用于保存各种不同类型的值

dict

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。

字典在Redis中的应用相当广泛，比如Redis的数据库就是使用字典来作为底层实现的，除了用来表示数据库之外，字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。

字典底层通过hashtable实现，dict->dictht->*dictentry

实现

哈希表

typedef struct dictht {

    // 哈希表数组 数组每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对
    dictEntry **table;  

    // 哈希表大小,大小为2^n
    unsigned long size;         

    //哈希表大小掩码，用于计算索引值
    //总是等于size-1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

哈希表节点

typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;

    // 将多个哈希值相同的键值对连接在一起，用来解决键冲突问题
    struct dictEntry *next;
} dictEntry;

字典

typedef struct dict {

    // 类型特定函数 保存了一簇用于操作特定类型键值对的函数，redis为用途不同的字典设置了不同类型特定函数
    dictType *type;

    // 私有数据 保存了需要传递给特定函数的可选参数
    void *privdata;

    // 哈希表 ht[1]rehash时使用
    dictht ht[2];

    // rehash索引
    //当rehash不在进行时，值为-1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);   //键的复制函数
    void *(*valDup)(void *privdata, const void *obj);   //值的复制函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);  //键的比较大小函数
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

字典操作

新增

向字典添加新的键值对时，需要通过_dictKeyIndex函数获取索引值，然后根据索引值将包含新键值对的哈希表节点(entry)放到哈希表数组的指定索引上
获取索引具体过程如下:

1. 根据键计算出哈希值(dictHashKey)
2. 接着与掩码求与得到索引值

static int dictAdd(dict *ht, void *key, void *val) {
    int index;
    dictEntry *entry;

    /* Get the index of the new element, or -1 if
     * the element already exists. */
     // 获取key在哈希表数组中的索引值
    if ((index = _dictKeyIndex(ht, key)) == -1)
        return DICT_ERR;

    /* Allocates the memory and stores key */
    // 生成哈希表节点，通过拉链法解决哈希冲突
    entry = malloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;

    /* Set the hash entry fields. */
    dictSetHashKey(ht, entry, key);
    dictSetHashVal(ht, entry, val);
    ht->used++;
    return DICT_OK;
}

//获取key所对应的索引值
static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    /* Compute the key hash value */
    //获取哈希值,dictHashKey定义如下`#define dictHashKey(d, key) (d)->type->hashFunction(key)`
    h = dictHashKey(d, key);                    
    for (table = 0; table <= 1; table++) {
        // 与哈希表的掩码按位与求得索引值。
        // 哈希表长度size为2^n,sizemask=size-1,得知掩码二进制表示的低位是连续为1，求与运算可以得到不大于sizemask的索引值
        idx = h & d->ht[table].sizemask;        
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

解决键冲突

链地址法

dict扩容

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
负载因子 = 哈希表节点数/哈希表大小,代码实现上就是ht[0].used/ht[0].size

执行起来包括两部分，存储扩容和数据rehash

存储扩容

扩容时机

dict新加元素时

扩容条件

满足以下任一条件即可扩容:

• 负载因子>=1 并且 “允许扩容开关”为打开状态
• 负载因子>=强制扩容阈值(目前为5)

扩容后哈希表大小变为当前哈希表节点数的2倍（ht[0].used*2），然后开始进入rehash的步骤

允许扩容开关在子进程存在时会关闭，子进程出现有两种可能，1是rdb子进程，2是aof子进程
通过扩容条件可以发现，redis官方是不建议在子进程存在情况下进行dict扩容的，为什么？
默认情况fork后父子进程共用同一份内存，根据COW特性，当内存数据有变化时会对变化的内存段会发生复制，而dict扩容恰恰会让整个dict发生变化，于是会产生大量的内存复制，导致内存使用量上涨。出于对内存使用量的考虑，redis官方尽可能减少在子进程存在情况下的dict扩容

//如果有必要的话，对哈希表进行扩容
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

rehash

在dict的属性rehashidx被设置为非-1后，dict正式进入rehash流程，rehash的目的是将将ht[0]中所有键值对rehash到ht[1]中。
在对对象增删改查时都会进行rehash状态检查，如果处于rehash状态则进行1次rehash操作，这种非一次性集中完成而是分多次渐进式完成的hash操作，我们称之为渐进式rehash。

为什么不一次性rehash完？
一次性将全部键值对rehash到ht[1]可能会导致服务一段时间内不可用。

以下是哈希表渐进式rehash的详细步骤：
1）为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
2）在字典中维持一个索引偏移量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
3）在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx位置索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值+1。
4）随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。

rehash源码如下:

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table. */
 // 执行N次渐进式rehash操作,渐进式rehash时n为传参为1
int dictRehash(dict *d, int n) {
    if (!dictIsRehashing(d)) return 0;

    while(n--) {
        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */
        if (d->ht[0].used == 0) {
            zfree(d->ht[0].table);
            d->ht[0] = d->ht[1];
            _dictReset(&d->ht[1]);
            d->rehashidx = -1;
            return 0;
        }

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }
    return 1;
}

定时rehash

redis本身db也是使用dict实现的，对于db本身也存在rehash的情况，在serverCron->databasesCron->incrementallyRehash实现了面向db键空间的定时辅助 rehash逻辑，db会在定时任务中抽出1毫秒来进行rehash db工作

参考资料

美团针对Redis Rehash机制的探索和实践

zskiplist

zskiplist->zskiplistNode
跳跃表是一种有序的数据结构，支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。
大部分情况下效率可与平衡树相媲美，实现比平衡树要更为简单。
可以方便地实现快速查找及范围查找。

基本操作: 遍历/查找/反向遍历

实现细节:

• 表头节点没有存储对象
• 每个跳跃表节点层高是1得到32之间的随机数
• 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
  初看上去，很容易以为跨度和遍历操作有关，但实际上并不是这样，遍历操作只使用前进指针就可以完成了，跨度实际上是用来计算排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

实现

typedef struct zskiplistNode {

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

} zskiplistNode;

typedef struct zskiplist {

    // 表头节点和表尾节点
    structz skiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

https://www.cnblogs.com/thrillerz/p/4505550.html

整数集合(intset)

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

intset是集合键的底层实现之一

实现

typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

升级

每次向整形几何添加新元素都可能引起升级，而每次升级都需要对底层数组中已有的所有元素进行类型转换，所以像整数集合添加新元素的时间复杂度为O(N)

升级的好处

• 提升灵活性
  C语言是静态类型语言，为了避免类型错误 ，通常不会讲两种不同类型的值方在同一个数据结构中，但是整数集合可以通过自动升级底层数组来适应新元素，所以我们可以把int16_t、int32_t等整数添加到集合中，而不必担心出现类型错误。
• 节约内存

压缩列表ziplist

压缩列表是列表键和哈希键的底层实现之一。
>

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

压缩列表是redis为了节约内存而开发的顺序性数据结构。
一个压缩列表包含任意个节点，每个节点保存一个字节数组或一个整数值。
添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

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

previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度
压缩列表的从表尾向表头遍历操作就是使用这一原理实现的

对象

上面我们介绍了sds、双端链表、字典、压缩列表、整数集合等数据结构，Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统。
这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这5种类型的对象。每种对象都至少用到一种前面介绍的数据结构。这样的好处是我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率

对象的类型与编码

redis数据库每个键值对的键和值都是一个对象

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

typedef struct redisObject {
    unsigned type:4;        //类型表示对象类型，即字符串、列表、哈希、集合、有序集合五种
    unsigned encoding:4;    //编码记录了对象所使用的编码，即这个对象使用了什么数据结构作为底层实现
    void *ptr;              //指向底层实现数据结构的指针
    // ...
} robj;

每种类型的对象都至少使用了两种不同的编码:

通过object encoding key可以查看一个数据库键的值对象的编码

字符串对象

字符串对象的编码可以是int、raw或者embstr。

编码转换

int、embstr编码的对象在一定条件下会转换为raw编码的对象

• 如果int编码的字符串对象保存的不再是整数值而是一个字符串，那么就会转换为raw
• redis没有为embstr编码编写任何修改api，所以当修改embstr编码对象时必须先将其转为raw格式，然后再执行修改命令

列表对象

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

哈希对象

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

集合对象

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

有序集合对象

有序集合的编码可以是ziplist或者skiplist。
跳表编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表

typedef struct zset {
    zskiplist *zsl;     //跳跃表   快速范围查找，保障了平均O(logN)的查询速度
    dict *dict;         //字典 保存值与value的关联关系，所以可以O(1)的形式(score)获取分数
} zset;

虽然zset同时使用跳表和字典来保存有序集合元素，但两者通过指针来共享相同元素的成员和分值，所以不会产生重复成员或分值，也不会因此浪费内存

为什么使用跳跃表而不是二叉平衡树呢？

• 二叉平衡树实现相较跳跃表更加复杂

内存回收

redis对象系统还实现了基于引用计数计数的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放，另外redis还通过引用计数计数实现了对象共享机制，这一机制在适当条件下，通过让多个数据库键共享同一个对象来节约内存

typedef struct redisObject {
    // ...

    // 引用计数
    int refcount;

    // ...
} robj;

redis引用计数信息会随着对象的使用状态而不断变化:

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

对象共享

除了实现引用计数内存回收外，对象的引用计数属性还带有对象共享的作用
redis在初始化服务器时，会创建一万个字符串对象，这些对象包含了从0到9999的所有整数值，当服务器需要用到值0到9999的字符串对象时，服务器就会使用这些共享对象，而不是创建新对象

查看值对象的引用计数
object refcount key

对象的空转时长

空转时长通过当前时间减去对象的lru时间计算得来
当服务器打开maxmemory选项且内存回收算法为lru时，如果服务器内存超过maxmemory，空转时长较长的键会优先被服务器释放

typedef struct redisObject {

    // ...

    unsigned lru:22;    //记录对象最后一次被程序访问的时间

    // ...

} robj;

打印给定键的空转时长
OBJECT IDLETIME key

单机数据库的实现

数据库

struct redisServer {
    // ...
    redisDb *db;    // 一个数组，保存着服务器中的所有数据库
    int dbnum;      // 服务器的数据库数量 默认情况下为16
    long long dirty;// Changes to DB from the last save
    time_t lastsave;// 上一次执行保存的时间
    sds aof_buf;    // AOF缓冲区
    // ...
};

切换数据库

每个redis客户端都有自己的目标数据库，可以通过select命令切换目标数据库
下图客户端执行命令SELECT 2，目标数据库改为2号数据库，此时客户端状态和服务器状态之间的关系如下图

数据库键空间

Redis是一个键值对数据库服务器，服务器中的每个数据库都由一个redis.h/redisDb结构表示，其中redisDb的dict字典中保存了数据库中的所有键值对，我们将这个字典称为键空间

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

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

• 键空间的键就是数据库的键，每个键都是一个字符串对象
• 键空间的值也就是数据库的值，每个值都是字符串对象、列表对象等其中的一种对象

示例

读写键空间时的维护工作

使用redis对数据库进行读写操作时，服务器还会执行一些额外的维护操作，比如

• 读取一个键(读操作和写操作都要对键进行读取)，服务器会根据键是否存在来更新服务器的键空间命中(hit次数或键空间不命中(miss)次数，这两个值可以在info stats的keyspace_hits属性和keyspace_misses属性中查看
• 读取一个键后，服务器会更新键的LRU时间(redisObject对象的lru字段)
• 如果读取一个键时发现已过期，那么服务器会先删除这个过期键，然后才执行余下的其他操作
• 如果客户端使用watch命令监视了某个键，那么服务器在对被监视的键修改后，会将这个键标记为脏(dirty),从而让事务处理程序注意到这个键已经被修改过(见7.事务)
• 服务器每次修改一个键后，都会对脏(dirty)键计数器值增1，这个计数器会触发服务器的持久化以及复制操作
• 如果服务器开启了数据库通知功能，那么在对键进行修改之后，服务器将按配置发送响应的数据库通知

键的过期时间

可以通过EXPIRE、PEXPIRE、EXPIREAT、PEXPIREAT命令对键设置过期时间，其中EXPIRE、PEXPIRE、EXPIREAT三个命令都是使用PEXPIREAT实现的
PERSIST命令可以移除一个键的过期时间
TTL PTTL返回剩余过期时间

保存过期时间

redisDb结构的expires字典保存了数据库中所有键的过期时间，我们称之为过期字典
过期字典的键是一个指针，这个指针指向键空间里中的某个键对象

typedef struct redisDb {
    ...
    // 过期字典，保存着键的过期时间
    dict *expires;
    ...
} redisDb;

过期键的删除策略

redis服务器使用惰性删除和定期删除两种策略

• 惰性删除: 在取出键时才对键进行过期检查
• 定期删除: 每隔一段时间执行一次删除过期键操作。每次从expires字典中随机检查一部分键的过期时间，并删除其中的过期键，全局变量current_db会记录检查进度，每次执行时会接着上一次的进度进行处理

  过期删除逻辑见activeExpireCycle函数
  对于”记录检查进度”举个例子,本次过期键检查到db10,下次检查会从db11开始遍历，当所有的db都被执行后，current_db重置为0，然后再次开始新一轮的检查。
  current_db源码中声明为一个静态局部变量，所以不会每次初始化，达到记录上次遍历位置的效果

AOF、RDB和复制功能对过期键的处理

保存RDB文件

通过SAVE或BGSAVE生成RDB文件时，会对数据库的键进行检查，过期键不会被保存到新建的rdb文件中

载入RDB文件

• 如果服务器以主服务器模式运行，那么在载入RDB文件时，程序会对文件中保存的键进行检查，过期键会被忽略
• 如果服务器以从服务器模式运行，RDB文件中所有键(无论是否过期)，都会被载入到数据库中

AOF文件写入

如果数据库某个键已经过期但是还没有被清理，那么AOF不会因为这个过期键产生任何影响
当过期键被清理之后，程序会向AOF文件追加一条DEL命令，来显式记录该键已被删除

AOF重写

重写过程中，程序会对数据库中的键进行检查，已过期键不会被保存到重写后的AOF文件中

复制

复制模式下，从服务器的过期键删除动作由主服务器控制:

• 主服务器删除一个过期键后，会显式地向从服务器发送一个DEL命令
• 从服务器在执行客户端读命令时，即使碰到过期键也不会将过期键删除，而是继续像处理未过期的键一样来处理过期键(继续返回给客户端，Redis 3.2中，从节点在读取数据时，增加了对数据是否过期的判断：如果该数据已过期，则不返回给客户端)
• 从服务器只有在接收到主服务器发来的DEL命令之后，才会删除过期键

RDB持久化

RDB文件是一个经过压缩的二进制文件
RDB文件用于保存和还原Redis服务器所有数据库中的所有键值对数据。

RDB文件的创建与载入

有两个命令可以用于生成RDS文件，SAVE/BGSAVE

• SAVE命令会阻塞Redis服务器进程，直到RDB文件创建完毕为止，在服务器进程阻塞期间，服务器不能处理任何命令请求
• BGSAVE会派生出一个子进程，然后由子进程负责创建RDB文件，父进程继续处理请求

RDB的载入工作是在服务器启动时自动执行的，服务器在载入RDB文件期间，会一直处于阻塞状态，直至载入工作完成
PS: 服务器优先使用AOF持久化，只有在AOF关闭时，服务器才会使用RDB文件来还原数据库状态

自动间隔性保存

redis允许用户设置save选项，让服务器每隔一段时间执行一次bgsave命令

满足以下三个条件中任意一个，bgsave命令就会被执行
save 900 1          900秒内对数据库进行了至少一次修改
save 300 10         300秒内对数据库进行了至少10次修改
save 60 10000       60秒内对数据库进行了至少10000次修改

bgsave定期保存实现

// ServerCron中
// server.dirty 服务器上次保存后的修改计数
// server.lastsave 服务器上次save时间
// sp->changes 对应 save 900 1 中的1
// sp->seconds 对应 save 900 1 中的900
if (server.dirty >= sp->changes &&
    server.unixtime-server.lastsave > sp->seconds &&
    (server.unixtime-server.lastbgsave_try >
        CONFIG_BGSAVE_RETRY_DELAY ||
        server.lastbgsave_status == C_OK))
{
    ...
    rdbSaveInfo rsi, *rsiptr;
    rsiptr = rdbPopulateSaveInfo(&rsi);
    rdbSaveBackground(server.rdb_filename,rsiptr);
    break;
}

dirty计数器和lastsave属性

dirty计数器记录距离上一次成功执行SAVE命令或者BGSAVE命令之后，服务器对数据库状态进行了多少次修改(写入、删除、更新)
lastsave属性是一个UNIX时间戳，记录服务器上次成功执行SAVE/BGSAVE命令的时间

struct redisServer {
    ...
    // 修改计数器
    long long dirty;

    // 上一次执行保存的时间
    time_t lastsave;
    ...
};

检查保存条件是否满足

Redis的服务器周期性操作函数serverCron默认每隔100毫秒就会执行一次，该函数用于对正在运行的服务器进行维护，其中一项工作就是检查save选项设置的保存条件是否已经满足，如果满足就执行BGSAVE

RDB文件结构

REDIS: 文件开头是五个字符”REDIS”,用来判别是不是RDB文件
db_version: 4字节整数，记录RDB文件的版本号
databases: 包含另个或任意多个数据库及各数据库中的键值对数据
EOF: 常量长度为1字节，标志着RDB文件正文内容的结束
check_sum: 校验和，用来检查RDB文件是否有损坏

AOF持久化

AOF文件通过保存所有修改数据的写命令请求来记录服务器的数据库状态
AOF文件中的所有命令都以redis命令请求协议格式保存

AOF持久化的实现

AOF持久化实现可以分为命令追加(append)、文件写入、文件同步(sync)三个步骤

命令追加

AOF开启时，服务器执行一个写命令后，会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区的末尾

struct redisServer {
    ...
    // AOF缓冲区
    sds aof_buf;
    ...
};

写入同步

Redis服务器进程就是一个事件循环(loop),这个循环的文件事件负责接收客户端命令请求以及向客户端发送命令回复，而时间事件则负责像serverCron函数这样需要定时运行的函数

在每次事件循环结尾，都会调用flushAppendOnlyFile,考虑是否需要将aof_buf缓冲区中的内容写入到AOF文件中，这个过程的伪代码为

def eventLoop():

    while True:

        # 处理文件事件，接收命令请求以及发送命令回复
        # 处理命令请求时可能会有新内容被追加到 aof_buf 缓冲区中
        processFileEvents()

        # 处理时间事件
        processTimeEvents()

        # 考虑是否要将 aof_buf 中的内容写入和保存到 AOF 文件里面 其行为受服务器配置appendfsync的值决定always/everysec/no
        flushAppendOnlyFile()

flushAppendOnlyFile函数的行为由服务器配置的appendfsync选项的值来决定

always      将aof_buf缓冲区中的内容同步到aof文件中，最多丢失一个事件循环中所产生的命令数据
everysec    每秒同步一次，这个同步操作是由一个专门的线程负责执行的
no

为提高文件写入效率，现在操作系统中当用户调用write函数写文件时，其实是有缓冲区的，缓冲区被填满或超过指定时限后，才真正将缓冲区数据写磁盘。
这种情况虽然提高了效率，但是给写入数据带来了安全问题，因为如果计算机停机，那么保存在内存缓冲区里的写入数据就会丢失。为此，操作系统提供了fsync和fdatasynv两个同步函数，他们可以强制操作系统将缓冲区的数据写入到硬盘里，从而确保写入数据的安全性
当appendfsync为always时，会强制进行fsync/fdatasynv
当appendfsync为everysec时，会开启专门的线程执行aof任务

if (server.aof_fsync == AOF_FSYNC_ALWAYS) {
    /* redis_fsync is defined as fdatasync() for Linux in order to avoid
        * flushing metadata. */
    latencyStartMonitor(latency);
    //强制fsync
    redis_fsync(server.aof_fd); /* Let's try to get this data on the disk */
    latencyEndMonitor(latency);
    latencyAddSampleIfNeeded("aof-fsync-always",latency);
    server.aof_fsync_offset = server.aof_current_size;
    server.aof_last_fsync = server.unixtime;
} else if ((server.aof_fsync == AOF_FSYNC_EVERYSEC &&
    server.unixtime > server.aof_last_fsync)) {
    if (!sync_in_progress) {
        // 开启专门线程处理aof
        aof_background_fsync(server.aof_fd);
        server.aof_fsync_offset = server.aof_current_size;
    }
    server.aof_last_fsync = server.unixtime;
}

AOF文件的载入与还原

创建一个不带网络连接的伪客户端，循环执行AOF文件中读取到的命令

AOF重写

为解决AOF文件体积膨胀的问题，redis提供了rewrite功能

AOF文件重写实现

AOF重写主要是解决AOF文件越来越大的问题，但实际上AOF文件重写并不需要对现有的AOF文件进行任何读取、分析或写入操作，这个功能是通过读取服务器当前的数据库状态来实现的
原理: 从数据库中读取键现在的值，然后用一条命令去记录键值对，代替之间记录这个键值对的多条命令，这就是AOF重写功能的实现原理

AOF后台重写

redis为避免AOF重写阻塞服务，将AOF重写程序放到子进程里执行。

AOF重写期间，服务器进程还需要继续处理命令请求，而新的命令可能对现有的数据库进行修改，从而使得服务器当前数据库状态和重写后的AOF文件锁保存的数据库状态不一致。

为解决这种数据不一致问题，Redis服务器设置了一个AOF重写缓冲区，这个缓冲区在服务器创建子进程之后开始使用，当Redis服务器执行完一个写命令之后，它会同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区。

当子进程完成AOF重写工作之后，它会向父进程发送一个信号，父进程在接收到该信号后，会调用一个信号处理函数，并执行以下工作:

• 1.将AOF重写缓冲区中的所有内容写入到新AOF文件中，这时新AOF文件所保存的数据库状态和服务器当前的数据库状态一致
• 2.对新的AOF文件进行改名，原子的(atomic)覆盖现有的AOF文件，完成新旧两个AOF文件的替换

整个AOF后台重写过程中，只有信号处理函数执行时会堵服务器进程造成阻塞，这将AOF重写对服务器性能造成的影响降到了最低。

// serverCron中aof重写逻辑，如果条件允许，则开启后台进程进行重写
if (!hasActiveChildProcess() &&
    server.aof_rewrite_scheduled)
{
    rewriteAppendOnlyFileBackground();
}

// 子进程结束后aof缓冲区内容8
void backgroundRewriteDoneHandler(int exitcode, int bysignal) {
    ...
    snprintf(tmpfile,256,"temp-rewriteaof-bg-%d.aof",
        (int)server.aof_child_pid);
    newfd = open(tmpfile,O_WRONLY|O_APPEND);
    if (newfd == -1) {
        redisLog(REDIS_WARNING,
            "Unable to open the temporary AOF produced by the child: %s", strerror(errno));
        goto cleanup;
    }

    if (aofRewriteBufferWrite(newfd) == -1) {
        redisLog(REDIS_WARNING,
            "Error trying to flush the parent diff to the rewritten AOF: %s", strerror(errno));
        close(newfd);
        goto cleanup;
    }
    ...
}

事件

redis服务器是一个事件驱动程序，服务器需要处理以下两类事件

• 文件事件(file event): Redis服务器通过套接字与客户端进行连接，而文件事件就是服务器对套接字的抽象。服务器与客户端的通信会产生相应的文件事件，而服务器则通过监听并处理这些事件来完成一系列网络通信操作
• 时间事件(time event): Redis服务器中的一些操作(比如serverCron)需要在给定的时间点执行，而时间事件就是服务器对这类定时操作的抽象

文件事件

redis基于reactor模式开发了自己的网络事件处理器: 这个处理器被称为文件事件处理器(file event handler)

• 文件事件处理器使用I/O多路复用程序来同时监听多个套接字，并根据套接字目前执行的任务来为套接字关联不同的事件处理器
• 当被监听的套接字准备好执行accept、read、write、close等操作时，与操作相对应的文件事件就会产生，这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件

redis线程模型

I/O复用程序

I/O多路复用程序会将所有产生的事件的套接字都放到一个队列里，然后通过这个队列，以有序、同步、每次一个套接字的方式向文件事件分派器传送套接字。当上一个套接字产生的事件被处理完毕之后（该套接字为事件所关联的事件处理器执行完毕），I/O多路复用程序才会继续向文件事件分派器传送下一个套接字

文件事件的处理器

redis为文件事件编写了多个处理器，这些事件处理器分别用于实现不同的网络通信需求

• 为了对连接服务器的各个客户端进行应答，服务器要为监听套接字关联连接应答处理器
• 为了接受客户端传来的命令请求，服务器要为客户端套接字关联命令请求处理器
• 为了向客户端返回命令的执行结果，服务器要为客户端关联命令回复处理器
• 当主服务器和从服务器进行复制时，主从服务器都需要关联特别为复制功能编写的复制处理器

时间事件

redis时间事件分为以下两类:

• 定时事件: 让一段程序在指定的时间后执行一次
• 周期性事件: 让一段程序每隔指定时间就执行一次

实现

服务器将所有时间事件放到一个无序链表中，每当时间事件执行器运行时，它就遍历整个链表，查找所有已到达的时间事件，并调用响应的事件处理器

时间事件应用实例: serverCron

持续运行的redis服务器需要定期对自身资源和状态进行检查和调整，这些定期操作由redis.c/serverCron函数负责执行，它的主要工作包括

• 更新服务器各类统计信息，比如时间，内存占用,数据库占用等
• 清理数据库中的过期键值对
• 尝试进行AOF或RDB持久化操作
• 如果服务器是主服务器，那么对从服务器进行定期同步
• 如果处于集群模式，对集群进行定期同步和连接测试

2.8版本前100ms一次，在2.8及以后版本，用户可以通过修改hz选项来调整serverCron每秒执行次数

服务器

服务器从启动到能够处理客户端命令请求需要执行以下步骤:
1.初始化服务器状态
2.载入服务器配置
3.初始化服务器数据结构
4.还原数据库状态
5.执行事件循环

多机数据库的实现

复制

旧版复制功能实现(2.8之前)

redis复制分为同步和传播两部分

• 同步(sync)用于将从服务器数据更新至主服务器当前所处的数据库状态
• 命令传播操作用于主服务器的数据库状态被修改，导致从服务器的状态不一致时，让主从服务器的数据库重新回到一致性状态。

同步

1. 从服务器向主服务器发送sync命令
2. 收到sync命令的主服务器执行bgsave命令，在后台生成一个rdb文件，并使用一个缓冲区记录从现在开始执行的所有写命令
3. 当主服务器的bgsave命令执行完毕后，主服务器将basave命令生成的rdb文件发送给从服务器，从服务器接收并载入这个rdb文件，将自己的数据库状态更新至主服务器执行bgsave命令时的数据库状态。
4. 主服务器将记录在缓冲区里面的所有写命令发送给从服务器，从服务器执行这些命令，将自己的数据状态更新至主服务器数据库当前所处的状态

传播

当主服务器执行写命令后主从不再一致，这时主服务器将自己执行的写命令发送给从服务器，当从服务器执行了相同的写命令后，主从再次一致。

旧版复制的缺陷

从服务器对主服务器可以分为初次复制和断线后重复制两种
对于初次来说，旧版复制功能能够很好地完成任务，但对于断线后重复值来说，旧版功能太过低效(重新sync)

2.8之后

在2.8版本之前，如果从服务器断开后重连，从服务器会向主服务器发送sync命令全量同步，这回带来很大问题

1. 主服务器需要执行bgsave来生成rdb文件，这会占用大量的cpu、内存及磁盘IO资源
2. 主服务器需要将自身生成的rdb文件发送给从服务器，这会占用主服务器大量的网络带宽
3. 从服务器载入rdb文件期间会因阻塞无法提供服务

于是在2.8开始，redis开始用PSYNC替代SYNC，PSYNC分为完整重同步和部分重同步，其中完整重同步与SYNC相同，而部分重同步则用于处理断线重连的情况，当从服务器断线重连时，如果条件允许，主服务器可以将从服务器连接断开期间执行的写命令发送给从服务器，从服务器只需要接收并执行这些命令，就可以重新与主服务器一致

部分重同步的实现

部分冲同步功能由一下三个部分构成

• 主服务器的复制偏移量和从服务器的复制偏移量
• 主服务器的复制积压缓冲区
• 服务器运行id

复制偏移量

执行复制的双方分别维护一个复制偏移量
通过对比主从服务器的复制偏移量，程序可以很容易的知道主从服务器是否处于一致状态。

复制积压缓冲区

复制积压缓冲区是一个固定长度的先进先出队列，默认1M。

当主服务器进行命令传播时，它不仅会将命令发送给所有从服务器，还会将写命令入队到复制积压缓冲区里面。因此复制积压缓冲区里保存着一部分最近传播的写命令，并且复制积压缓冲区会为队列中的每个字节记录相应的复制偏移量

复制积压缓冲区的构造

当从重新连接主时会通过PSYNC将自己的复制偏移量发送给主，主会根据这个偏移量决定对从执行何种同步操作:

• 如果offset偏移量后的数据还在复制积压缓冲区中，那么主对从执行部分重同步操作
• 如果offset偏移量后数据已不在复制积压缓冲区中，那么主对从执行完整重同步操作

服务器运行ID

实现部分重同步还需要用到服务器运行id(run id)，每个redis服务器都有自己的运行id，该id在服务器启动时自动生成

1. 当从服务器对主服务器进行初次复制时，主服务器会将自己的运行ID传送给从服务器,从服务器会主服务器的运行id保存起来
2. 从断线重新连接上一个主时，从服务器会发送之前保存的的主运行id
3. 如果保存的主运行id与当前连接主服务器的运行id相同，那么说明断线之前复制的就是当前连接的服务器，主服务器可以尝试部分重同步操作；相反，说明之前主服务器发生了变化，只能执行完整重同步

复制的实现

当完成了同步之后，主从服务器就会进入命令传播阶段，这时主服务器只要一直将自己执行的写命令发送给从服务器，而从服务器只要一直接收并执行主服务器发来的写命令，就可以保证主从服务器一直保持一致了

心跳检测

在命令传播阶段，从服务器默认会以每秒一次的频率，向主服务器发送命令REPLCONF ACK <replication_offset>,发送的作用有3个

• 检测主从服务器的网络连接
• 检测命令丢失
  • 主服务器传播给从服务器的写命令半路丢失，从服务向主服务器发送REPLCONF ACK命令时，主服务器将发觉从服务器复制偏移量少于自己的复制偏移量，将这些数据重新发送给从服务器

哨兵(sentinel)

介绍

sentinel是redis的高可用方案，为主从模式集群提供故障转移能力

故障转移流程

实现

sentinel是一个运行在特殊模式下的redis服务器

检查主观下线状态

默认情况下，sentinel会以一秒一次的频率向所有与它创建了命令连接的实例发送PING命令，并通过实例返回的PING命令回复来判断实例是否在线
配置文件中的down-after-milliseconds选项指定了sentinel判断实例进入主观下线所需的时间长度

检查客观下线状态

当sentinel将一个主服务器判断为主观下线后，为确认主服务器是否真的下线了，会向同样监视这一主服务器的其他sentinel询问，看它们是否也认为主服务器已进入下线状态。当sentinel从其他sentinel接收到足够多的已下线判断之后，sentinel就会将从服务器判定为客观下线，并对主服务器执行故障转移

集群

待合并文档

redis集群是redis提供的分布式数据库方案，通过分片来进行数据共享，并提供复制和故障转移功能

节点

一个节点就是一个运行在集群模式下的redis服务器

槽

集群整个数据库被分为16384个槽，数据库每个键都属于这16384个槽的其中一个，集群的每个节点可以处理0个或最多16384个槽

当16384个槽中有任何一个没有被节点接收处理，那么集群处于下线状态fail，其他情况为ok

记录节点槽指派信息

clusterNode 结构的slots属性和numslot属性记录了当前节点负责处理哪些槽

struct clusterNode{
    ...
    unsigned char slots[16384/8];   //slots属性是一个二进制位数组，这个数组的长度是16384/8=2048个字节，共包含16384个二进制位
    int numslots;
    ...
}

clusterState 结构存储了集群状态

typedef struct clusterState {
  // ...
  // 存储节点和槽的对应关系
  clusterNode *slots[16384];
  // ...
} clusterState;

命令请求

节点在接到一个命令请求时，会先检查这个命令请求要处理的键所在的槽是否由自己负责，如果不是的话，节点向客户端返回一个MOVED错误，MOVED错误携带的信息可以指引客户端转向正在负责相关槽的节点

如果节点A正在迁移节点B，那么当节点A没能在自己的数据库找到命令指定的数据库键时，节点A会向客户端返回一个ASK错误，指引客户端到节点B继续查找指定的数据库键

MOVED表示槽的负责权已经从一个节点转移到另一个节点，ASK错误只是两个节点迁移槽过程中的一种临时措施

重新分片

redis集群重新分片可以将任意数量已经指派给某个节点的槽改为指派给另一个节点，并且相关槽所属的键值对也会从源节点被移动到目标节点

重新分片可以在线操作，在重新分片过程中，集群不需要下线，并且源节点和目标节点都可以继续处理命令请求

重新分片的实现原理

MOVED错误

MOVED错误代表槽的负责权已经从一个节点转移到了另一个节点 (非临时，仅第一次访问该slot时发生)

ASK错误

ASK错误只是两个节点在迁移槽过程中使用的一种 临时措施: 在客户端收到关于槽i的ASK操作之后，客户端只会在接下来的一次命令请求中将关于槽i的命令请求发送至ASK操作所指示的节点，但这种转向不会对客户端今后发送关于槽i的命令请求产生任何影响，客户端仍然会将关于槽i的命令请求发送至目前负责处理槽i的节点，除非ASK错误再次发生 (临时的，中间状态时，每次都会发生)

复制和故障转移

redis集群中的节点分为主节点和从节点，其中主节点用于处理槽，从节点用于冗余主节点

故障检测

与哨兵类似流程类似

集群每个节点会定期向其他节点发送ping信息，如果在规定时间内没有返回pong消息，那么发送ping消息的节点就会将接受ping消息的节点标记为疑似下线(probalbe fail,PFAIL)

如果一个集群里，半数以上主节点都将某个主节点x报为疑似下线，那么这个主节点x将被标记为已下线(FAIL)，同时将x标记为已下线的节点会向集群广播一条关于主节点x的FAIL消息，所有收到这条FAIL消息的节点都会立即将主节点x标记为已下线

故障转移

当一个从节点发现自己正在复制的主节点进入下线状态时，从节点将开始对下线主节点进行故障转移

1. 下线主节点n0的所有从节点中选中其中一个n1(选举)
2. n1节点执行SLAVEOF NO ONE,成为新的主节点
3. 新主节点n1节点会撤销所有对n0节点的槽指派，并将这些槽全部指派给自己
4. 新的主节点n1向集群广播一条PONG消息，这条PONG消息可以让集群中的其他结点立即知道这个节点已经由从节点变成主节点，并且这个主节点已经接管了原本由已下线节点负责处理的槽
5. 新的主节点开始接收和自己负责的槽有关的命令操作

事务

事务提供了一种将多个命令打包，然后一次性有序执行的机制，实现上是将多个命令入队到服务端事务队列中，然后按照先进先出的顺序执行。

带有WATCH命令的事务会将客户端和被监视的键在数据库中的watched_keys字典中进行关联，当键被修改时，程序会将所有监视被修改键的客户端的REDIS_DIRTY_CAS标志打开

只有在客户端的REDIS_DIRTY_CAS标志未被打开时，服务器才会 执行客户端提交的事务，否则的话，服务器将拒绝执行客户端提交的事务

redis事务总是具有ACID中的原子性、一致性、和隔离性，当服务器运行在AOF持久化模式下，并且appendfsync选项的值为always时，事务也具有持久性

事务队列

WATCH命令的实现

WATCH命令是一个乐观锁，他可以在EXEC前监视任意数量的数据库键，并在EXEC时，检查被监视的键是否至少有一个已经被修改过了，如果是的话，服务器将拒绝执行事务，并向客户端返回代表事务执行失败的空回复

慢查询日志

配置项

slowlog-log-slower-than选项指定执行时间超过多少微秒的命令请求会被记录到日志上。
slowlog-max-len选项置顶服务器最多保存多少条慢查询日志

SLOWLOG GET

FAQ

1.Redis高性能的原因

• IO模型
• 无锁
• 多种数据结构，不同场景通过使用不同数据结构提升查询修改时间复杂度
• 大量缓存
  • 全局的当前时间缓存server.ustime/server.mstime/server.unixtime
  • 全局共享变量

2.multi与pipeline的区别

• pipeline使用客户端缓冲区，multi使用服务端缓冲区
• 请求次数不同，pipeline请求一次，multi请求多次
• multi/exec可以保证原子性，pipeline不保证原子性