Redis

redis 工作模型、redis 持久化、redis 过期淘汰机制、redis 分布式集群的常见形式、分布式锁、缓存击穿、缓存雪崩、缓存一致性问题

推荐书籍:《Redis 设计与实现》

推荐文章:

Redis-复制

Redis 高可用-Sentinel

Redis-Cluster

常见问题

  • redis 性能为什么高?

基于内存、数据结构简单、单线程、使用多路I/O复用模型,非阻塞IO、使用底层模型不同,Redis 直接自己构建了VM 机制。

  • 单线程的 redis 如何利用多核 cpu 机器?

开启多个实例

  • redis 的缓存淘汰策略?

定时删除、惰性删除、定期删除

  • redis 如何持久化数据?

RDB、AOF

  • redis 有哪几种数据结构?

SDS、双向链表、字典、跳跃表、整数集合、压缩列表

  • redis 集群有哪几种形式?

  • 有海量 key 和 value 都比较小的数据,在 redis 中如何存储才更省内存?

使用 google protobuf 等紧凑序列化手段 + 压缩(gzip 等)

  • 如何保证 redis 和 DB 中的数据一致性?

使用消息队列更新缓存, 消费端保证只有一个线程顺序消费消息即可

  • 如何解决缓存穿透和缓存雪崩?

缓存穿透、缓存击穿、缓存雪崩区别和解决方案

  • 如何用 redis 实现分布式锁?

语法级别

redis 默认端口号 6379

通用操作
del
del key
scan
SCAN cursor [MATCH pattern] [COUNT count]

The default COUNT value is 10.

举个例子

127.0.0.1:6379> scan 0 match * count 20
1) "15"
2)  1) "febs.cache.user.mrbird"
    2) "febs.cache.user.root"
    3) "febs.cache.user.scott"
    4) "febs.cache.user.config.12"
    5) "febs.cache.user.role.jack"
    6) "febs.cache.user.role.mrbird"
    7) "list"
    8) "febs.cache.user.role.scott"
    9) "febs.cache.user.permission.jack"
   10) "febs.cache.user.config.2"
   11) "febs.cache.user.permission.mrbird"
   12) "*2\r"
   13) "febs.cache.user.jack"
   14) "integers"
   15) "febs.cache.user.permission.root"
   16) "febs.cache.user.config.1"
   17) "febs.cache.user.role.root"
   18) "febs.cache.user.config.13"
   19) "febs.cache.user.permission.scott"
   20) "num"
127.0.0.1:6379> scan 15 match * count 20
1) "0"
2) (empty list or set)

直到游标为 0 表示扫描完毕。

String 操作
GET/SET key value
List 操作

List 通过 LSET/LPUSH/LINDEX/LRANGE 操作, LPUSH 默认是将新元素插入链表头部.

127.0.0.1:6379> LPUSH list 0 100
(integer) 2
127.0.0.1:6379> LINDEX list 1
"0"
127.0.0.1:6379> LSET list 1 12
OK
127.0.0.1:6379> LRANGE list 0 1
1) "100"
2) "12"
Hash 操作

Hash 通过 HGET/HSET 操作获取/设置单个字段的值,通过 HMGET/HMSET/HMDEL 操作获取/设置/多个字段的值。

127.0.0.1:6379> HSET users user1 "zjp" user2 "shiyuan"
(error) ERR wrong number of arguments for 'hset' command
127.0.0.1:6379> HMSET users user1 "zjp" user2 "shiyuan"
OK
127.0.0.1:6379> HMGET users user2
1) "shiyuan"
127.0.0.1:6379> HSET users user3 "drq"
(integer) 1
有序集合(Sorted Set)

Sorted Set 通过 ZADD key score1 member1[score2 member2] 向有序集合添加一个或多个成员,或者更新已存在成员的分数,ZSCORE key member 返回有序集中,成员的分数值

127.0.0.1:6379> ZADD fruit-price 10.0 apple 7 banana
(integer) 2
127.0.0.1:6379>  ZSCORE fruit-price apple
"10"
127.0.0.1:6379> ZCARD fruit-price
(integer) 2
127.0.0.1:6379> ZRANGE fruit-price 0 5 WITHSCORES
1) "banana"
2) "7"
3) "apple"
4) "10"

数据结构与对象

简单动态字符串 SDS(simple dynamic string)

redis 存储字符串使用的是自定义 SDS 结构体, 而不是 c 语言中的 char 数组,这带来了很多方便,因为 SDS 本质上是封装了 char 数组的一个结构, 同时也弥补了 char 数组关于越界及其他的一些问题。参考源码文件 sds.h

struct sdshdr {

    // buf 中已占用空间的长度
    // SDS 实际存储的字符串长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间,用于保存字符串
    char buf[];
};

SDS 使用 N+1 个长度的数组存储 N 个字符, 最后一个字符是 c 语言字符串的结束符号 '\0'.

使用 SDS 是有好处的,比如可以在

常数时间 O(1) 获取字符长度 len

/*
 * 返回 sds 实际保存的字符串的长度
 *
 * T = O(1)
 */
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

杜绝缓冲区溢出

(会检查 SDS 中数据空间大小是否>=新字符的长度)

sds sdscatlen(sds s, const void *t, size_t len) {

    struct sdshdr *sh;

    // 原有字符串长度
    size_t curlen = sdslen(s);

    // 扩展 sds 空间
    // T = O(N)
    // 会检查 free 是否大于新增的部分的数组的长度
    s = sdsMakeRoomFor(s,len);

    // 内存不足?直接返回
    if (s == NULL) return NULL;
    //...
}

减少修改字符串带来的内存重分配次数

程序执行的字符串操作有两种,一种是增长字符串操作,比如拼接操作,另一种则是缩短字符串操作,比如截断操作。

对于增长字符串操作, redis 会使用空间预分配的手段,具体如下

空间预分配

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

sds sdsMakeRoomFor(sds s, size_t addlen) {

    struct sdshdr *sh, *newsh;

    // 获取 s 目前的空余空间长度
    size_t free = sdsavail(s);

    size_t len, newlen;

    // s 目前的空余空间已经足够,无须再进行扩展,直接返回
    if (free >= addlen) return s;

    // 获取 s 目前已占用空间的长度
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));

    // s 最少需要的长度
    newlen = (len+addlen);

    // 根据新长度,为 s 分配新空间所需的大小
    if (newlen < SDS_MAX_PREALLOC)
        // 如果新长度小于 SDS_MAX_PREALLOC 
        // 那么为它分配两倍于所需长度的空间
        newlen *= 2;
    else
        // 否则,分配长度为目前长度加上 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
    // T = O(N)
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

    // 内存不足,分配失败,返回
    if (newsh == NULL) return NULL;

    // 更新 sds 的空余长度
    newsh->free = newlen - len;

    // 返回 sds
    return newsh->buf;
}

SDS_MAX_PREALLOC = 1024 * 1024, 也就是 1M,

  1. 如果修改后 SDS 长度没有超过 1M, 那么 SDS 将分配和 len 属性大小一样的 free 空间,SDS 中 buff 长度为实际数组的两倍 + 1 个字节('\0')
  2. 如果修改后 SDS 长度超过 1M, 那么 SDS 将分配额外的 1M 的 free 空间,SDS 中 buff 长度为实际数组+ 1M+ 1 个字节('\0')
惰性空间释放

惰性空间释放用于优化 SDS 操作字符串的缩短操作:当 SDS 的 API 需要对 SDS 进行缩短时,程序不会立即使用内存重分配来回收缩短后多出来的字节,而是使用 free 属性将这些字节的数量纪录下来,等待将来使用。

sds sdstrim(sds s, const char *cset) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    char *start, *end, *sp, *ep;
    size_t len;

    // 设置和记录指针
    sp = start = s;
    ep = end = s+sdslen(s)-1;

    // 修剪, T = O(N^2)
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > start && strchr(cset, *ep)) ep--;

    // 计算 trim 完毕之后剩余的字符串长度
    len = (sp > ep) ? 0 : ((ep-sp)+1);

    // 如果有需要,前移字符串内容
    // T = O(N)
    if (sh->buf != sp) memmove(sh->buf, sp, len);

    // 添加终结符
    sh->buf[len] = '\0';

    // 更新属性
    sh->free = sh->free+(sh->len-len);
    sh->len = len;

    // 返回修剪后的 sds
    return s;
}

二进制安全

c 语言中的字符必须符合某种编码(比如 ASCII), 但 Redis 保证 SDS 的 API 操作是二进制安全的, buff 存储的不是字符,而是存储二进制数据。

链表

链表键的实现之一就是链表,Redis 中使用自定义的双向链表来表示, 参考源码文件 adlist.h

/*
 * 双端链表节点
 */
typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;
/*
 * 双端链表结构
 */
typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);

    // 链表所包含的节点数量
    unsigned long len;

} list;

redis 实现的链表具有如下特征:

  1. 双端:链表节点带有 prev 和 next 指针,获取某个节点的前置节点和后置节点的复杂度为 O(1).
  2. 无环:表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL, 对链表的访问以 NULL 为终点.
  3. 带表头和表尾指针:通过 list 结构的 head 指针和 tail 指针,获取链表表头和链表表尾只需 O(1) 时间.
  4. 带链表长度计数器:程序使用 list 结构的 len 属性实现获取链表长度只需 O(1) 时间.
  5. 多态:链表节点使用 void * 指针来保存节点值,并且通过 dup、free、match 三个属性为节点值设置类型特定函数,所以链表可以保存各种不同类型的值.

字典

Redis 数据库底层就是用字典实现数据库的增、删、改、查操作,字典还是哈希键的底层实现之一。

数据结构

哈希表

Redis 的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,而每个哈希表节点都存储字典中的一个键值对。参考源码文件 dict.h

/*
 * 哈希表
 *
 * 每个字典都使用两个哈希表,从而实现渐进式 rehash 。
 */
typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

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

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

} dictht;

table 属性中的每一个元素都是指向 dictEntry 结构的指针,每个 dictEntry 结构都保存一个键值对。

哈希表节点
/*
 * 哈希表节点
 */
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];

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

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;

type 属性和 privdata 属性是针对不同类型的键值对,为创建多态字典而设置。

ht 属性是一个哈希表数组,正常情况下字典只使用 ht[0], ht[1] 只有在对 ht[0] 进行 rehash 时才使用。

Hash 算法

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    /* Expand the hash table if needed */
    // 单步 rehash
    // T = O(N)
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;

    /* Compute the key hash value */
    // 计算 key 的哈希值
    h = dictHashKey(d, key);
    // T = O(1)
    for (table = 0; table <= 1; table++) {

        // 计算索引值
        idx = h & d->ht[table].sizemask;

        /* Search if this slot does not already contain the given key */
        // 查找 key 是否存在
        // T = O(1)
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }

        // 如果运行到这里时,说明 0 号哈希表中所有节点都不包含 key
        // 如果这时 rehahs 正在进行,那么继续对 1 号哈希表进行 rehash
        if (!dictIsRehashing(d)) break;
    }
    // 返回索引值
    return idx;
}    

可见 hash 是根据键的 hash 值 & sizemask 拿到对应链表的索引。键冲突时采用链地址法。

到此为止, Redis 的字典实现和 JDK1.7 中的 HashMap 如出一辙,稍微有点区别的在扩容时。

rehash

扩展和收缩都可以通过 rehash 来完成,Redis 对字典的 rehash 如下:

  1. 为字典 ht[1] 哈希表分配空间,分配的空间大小取决于要执行的操作,以及 ht[0] 中当前包含的键值对数量。
    • 如果执行的是扩展操作,那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n
    • 如果执行的是收缩操作,那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n
  2. 将 ht[0] 哈希表的元素 rehash 到 ht[1] 哈希表
  3. 当 ht[0] 哈希表的元素前移到 ht[1] 后,释放 ht[0], 将 ht[1] 设置为 ht[0], 并为 ht[1] 新建一个空表。
hash 表的收缩与扩展

负载因子 load_factor = ht[0].used / ht[0].size, 满足下列条件时程序会自动进行扩展与收缩

  1. 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且哈希表的负载因子 load_factor >= 1
  2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且哈希表的负载因子 load_factor >= 5
  3. 哈希表的负载因子 load_factor < 0.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 完成。
  5. 补充:渐进式 rehash 期间,字典的删除、修改、查询会在两个哈希表中执行,比如查找,会先去 ht[0] 查找, 找不到再去 ht[1] 查找;新添加到字典的键值对只会被保存到 ht[1], 以保证 ht[0] 的元素数量只减不增,最后为空表。

rehash 代码, 添加前 rehash, 并且使用添加元素到新链表表头的方式, 了解 JDK1.7 HashMap 的话下面代码应该很熟悉。

/* 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.
 *
 * 执行 N 步渐进式 rehash 。
 *
 * 返回 1 表示仍有键需要从 0 号哈希表移动到 1 号哈希表,
 * 返回 0 则表示所有键都已经迁移完毕。
 *
 * 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.
 *
 * 注意,每步 rehash 都是以一个哈希表索引(桶)作为单位的,
 * 一个桶里可能会有多个节点,
 * 被 rehash 的桶里的所有节点都会被移动到新哈希表。
 *
 * T = O(N)
 */
int dictRehash(dict *d, int n) {

    // 只可以在 rehash 进行中时执行
    if (!dictIsRehashing(d)) return 0;

    // 进行 N 步迁移
    // T = O(N)
    while(n--) {
        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */
        // 如果 0 号哈希表为空,那么表示 rehash 执行完毕
        // T = O(1)
        if (d->ht[0].used == 0) {
            // 释放 0 号哈希表
            zfree(d->ht[0].table);
            // 将原来的 1 号哈希表设置为新的 0 号哈希表
            d->ht[0] = d->ht[1];
            // 重置旧的 1 号哈希表
            _dictReset(&d->ht[1]);
            // 关闭 rehash 标识
            d->rehashidx = -1;
            // 返回 0 ,向调用者表示 rehash 已经完成
            return 0;
        }

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        // 确保 rehashidx 没有越界
        assert(d->ht[0].size > (unsigned)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 */
        // 将链表中的所有节点迁移到新哈希表
        // T = O(1)
        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;
        // 更新 rehash 索引
        d->rehashidx++;
    }

    return 1;
}

跳跃表

跳跃表是一种有序的数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。查找复杂度平均 O(logN), 最坏 O(N)

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

跳跃表的实现

Redis 的跳跃表定义在 redis.h/zskiplistNode 和 redis.h/zskiplist, 而具体实现在 t_zset.c 可以看到

/*
 * 跳跃表
 */
typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

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

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

} zskiplist;

header、tail 属性:跳跃表的表头节点和表尾节点

level 属性:记录目前跳跃表内,层数最大的那个节点的层数(表头结点不算)

length 属性:目前跳跃表中节点的数量

/* 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;

各个节点的层是怎么创建的呢?每个节点的层的数量是随机在 1-32 之间生成的一个数

来看下 t_zset.c

/*
 * 创建并返回一个新的跳跃表
 *
 * T = O(1)
 */
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    // 分配空间
    zsl = zmalloc(sizeof(*zsl));

    // 设置高度和起始层数
    zsl->level = 1;
    zsl->length = 0;

    // 初始化表头节点
    // T = O(1)
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);// ZSKIPLIST_MAXLEVEL = 32
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;

    // 设置表尾
    zsl->tail = NULL;

    return zsl;
}

创建头结点并进行相关的初始化

我们来看下 zslInsert 操作

/*
 * 创建一个成员为 obj ,分值为 score 的新节点,
 * 并将这个新节点插入到跳跃表 zsl 中。
 * 
 * 函数的返回值为新节点。
 *
 * T_wrost = O(N^2), T_avg = O(N log N)
 */
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    redisAssert(!isnan(score));

    // 在各个层查找节点的插入位置
    // T_wrost = O(N^2), T_avg = O(N log N)
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {

        /* store rank that is crossed to reach the insert position */
        // 如果 i 不是 zsl->level-1 层
        // 那么 i 层的起始 rank 值为 i+1 层的 rank 值
        // 各个层的 rank 值一层层累积
        // 最终 rank[0] 的值加一就是新节点的前置节点的排位
        // rank[0] 会在后面成为计算 span 值和 rank 值的基础
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];

        // 沿着前进指针遍历跳跃表
        // T_wrost = O(N^2), T_avg = O(N log N)
        while (x->level[i].forward &&
            (x->level[i].forward->score < score ||
                // 比对分值
                (x->level[i].forward->score == score &&
                // 比对成员, T = O(N)
                compareStringObjects(x->level[i].forward->obj,obj) < 0))) {

            // 记录沿途跨越了多少个节点
            rank[i] += x->level[i].span;

            // 移动至下一指针
            x = x->level[i].forward;
        }
        // 记录将要和新节点相连接的节点
        update[i] = x;
    }

    /* we assume the key is not already inside, since we allow duplicated
     * scores, and the re-insertion of score and redis object should never
     * happen since the caller of zslInsert() should test in the hash table
     * if the element is already inside or not. 
     *
     * zslInsert() 的调用者会确保同分值且同成员的元素不会出现,
     * 所以这里不需要进一步进行检查,可以直接创建新元素。
     */

    // 获取一个随机值作为新节点的层数
    // T = O(N)
    level = zslRandomLevel();

    // 如果新节点的层数比表中其他节点的层数都要大
    // 那么初始化表头节点中未使用的层,并将它们记录到 update 数组中
    // 将来也指向新节点
    if (level > zsl->level) {

        // 初始化未使用层
        // T = O(1)
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }

        // 更新表中节点最大层数
        zsl->level = level;
    }

    // 创建新节点
    x = zslCreateNode(level,score,obj);

    // 将前面记录的指针指向新节点,并做相应的设置
    // T = O(1)
    for (i = 0; i < level; i++) {

        // 设置新节点的 forward 指针
        x->level[i].forward = update[i]->level[i].forward;

        // 将沿途记录的各个节点的 forward 指针指向新节点
        update[i]->level[i].forward = x;

        /* update span covered by update[i] as x is inserted here */
        // 计算新节点跨越的节点数量
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);

        // 更新新节点插入之后,沿途节点的 span 值
        // 其中的 +1 计算的是新节点
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    /* increment span for untouched levels */
    // 未接触的节点的 span 值也需要增一,这些节点直接从表头指向新节点
    // T = O(1)
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }

    // 设置新节点的后退指针
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;

    // 跳跃表的节点计数增一
    zsl->length++;

    return x;
}

整数集合

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

127.0.0.1:6379> SADD numbers 1 3  5 7 9
(integer) 5
127.0.0.1:6379> OBJECT ENCODING numbers
"intset"

源码在 intset.h

typedef struct intset {

    // 编码方式
    uint32_t encoding;

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

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

} intset;

contents 数组是整数集合的底层实现:整数集合的每一项都是 contents 中的一个数组项,各个项按值大小从小到大有序排列,并且不包含任何重复项。

虽然 intset 将 contents 数组声明为 int8_t 类型数组, 但实际上 contents 数组并不保存任何 int8_t 类型的值,它的真正类型取决于 encoding 属性的值。

  • encoding 属性值为 INSERT_INC_INT16, 那么 contents 就是一个 int16_t 类型的数组。
  • encoding 属性值为 INSERT_INC_INT32, 那么 contents 就是一个 int32_t 类型的数组。
  • encoding 属性值为 INSERT_INC_INT64, 那么 contents 就是一个 int64_t 类型的数组。

升级

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

升级分为三步:

  1. 根据新元素类型,扩展整数集合底层数组的空间大小,并为新元素分配空间。
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确位置上,而且在放置新元素时,继续维持底层数组有序性不变
  3. 将新元素添加到底层数组中

可以看下升级代码

降级

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

压缩列表

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么是整数值,要么是比较短的字符串,那么 Redis 会使用压缩列表作为列表键的底层实现.

127.0.0.1:6379> RPUSH lst 1 3 5 10086 "hello word"
(integer) 5
127.0.0.1:6379> OBJECT ENCODING lst
"ziplist"

另外,当一个哈希键只包含少量列表项,并且每个键值对的键和值要么是整数值,要么是比较短的字符串,那么 Redis 会使用压缩列表作为哈希键的底层实现.

127.0.0.1:6379> HMSET profile "name" "Jack" "age" 28 "job" "Programmer"
OK
127.0.0.1:6379> OBJECT ENCODING profile
"ziplist"

压缩列表的构成

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

压缩列表由下面几项构成

  • zlbytes: uint32_t 类型, 占 4 个字节,记录整个压缩列表占用的内存字节数:在内存重分配或者计算 zlend 时使用
  • zltail: uint32_t 类型, 占 4 个字节,记录压缩列表表尾节点距离压缩列表的起始地址有多少个字节
  • zllen: uint16_t 类型, 占 2 个字节, 记录压缩列表包含的节点数量,当属性值小于 UINT16_MAX(65535) 时表示压缩列表的节点数量; 当等于 UINT16_MAX 时, 节点数量需要遍历压缩列表才能计算出来。
  • entryX: 列表节点,长度不定,保存压缩列表包含的各个节点
  • zlend: uint8_t 类型, 占 1 个字节, 值为 0xFF, 用于标记压缩列表的末端

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值,每个压缩列表节点都由 previous_entry_length,encoding ,content 三个部分组成。

previous_entry_length

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

  • 如果前一个节点的长度小于 254 字节,那么 previous_entry_length 属性为 1 个字节:保存前一个节点的长度
  • 如果前一个节点的长度大于等于 254 字节,那么 previous_entry_length 属性为 5 个字节:其中属性的第一个字节被设置为 0xFE(254),之后 4 个字节保存前一个节点的长度
encoding

节点的 encoding 属性记录了节点保存的 content 的类型以及长度:

a、b、c 等表示二进制数据, - 表示留空

字节数组编码如下

编码 编码长度 content 属性保存的值
00bbbbbb 1 个字节 长度小于等于 2^7-1 个字节的字节数组
01bbbbbb cccccccc 2 个字节 长度小于等于 2^14-1个字节的字节数组
10------ aaaaaaaa bbbbbbbb cccccccc dddddddd 5 个字节 长度小于等于 2^32-1 个字节的字节数组

整数编码如下

编码 编码长度 content 属性保存的值
11000000 1 个字节 int16_t 类型的整数
11010000 1 个字节 int32_t 类型的整数
11100000 1 个字节 int64_t 类型的整数
11110000 1 个字节 24 位有符号整数
11111110 1 个字节 8 位有符号整数
1111aaaa 1 个字节 使用这一编码的节点没有 content 属性,因为编码本身的aaaa四位已经保存了介于0-12之间的值,所以无需 content 属性
content

content 存储的内容由 encoding 决定。

连锁更新

节点的 previous_entry_length 属性记录了前一个节点的长度,如果有多个连续的长度在 250 左右的节点,对它们中的一个节点更新可能会触发其他节点更新,因为 previous_entry_length 超过 254 就要占用 5 个字节,不过实际中这种情况很少发生,因此不用担心性能问题。

对象

Redis 主要包含 SDS、双向链表、字典、压缩列表、跳跃表、整数集合等数据结构。

Redis 并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统,这个系统包含字符串对象、列表对象、哈希对象、集合对象、集合对象和有序集合对象。

对象类型及编码

Redis 使用

Redis 使用

开启 redis 服务器

redis-server redis.windows.conf

开启 redis 客户端

resdis-cli

关闭 redis 服务器

E:\Dev\Redis>redis-cli.bat shutdown
127.0.0.1:6379> shutdown

存储到硬盘

RDB

RDB 的创建与载入

Redis 有两个命令可以生成 RDB 文件, 一个是 SAVE, 另一个是 BASAVE

SAVE 命令会阻塞服务器进程,BGSAVE 会派生子进程创建 RDB

save 策略:100 秒内有 3 次修改则执行

save 100 3

如果服务期开启了 AOF 功能, 服务器会优先使用 AOF 文件恢复数据,因为 AOF 更新频率较快

dbfilename "dump-6001.rdb"

AOF

aof 功能默认是没有开启的,手动修改配置文件

appendonly yes
# appendfsync always
appendfsync everysec
# appendfsync no

appendfsync always 表示每次修改都保存到 AOF 文件, appendfsync everysec 则是每秒保存一次,appendfsync no 则是不保存,由操作系统调度保存

appendfilename "appendonly-6001.aof"

AOF 持久化实现

AOF 持久化功能分为命令追加、文件写入、文件同步三个步骤

  • 命令追加, AOF 功能打开时,服务器执行一个写入命令后会以协议格式将被执行的写命令追加到服务器的 aof_buf 缓冲区

  • 文件写入与同步

服务器在执行文件操作时可能执行写命令,使得一些内容被追加到 aof_buf 缓冲区,每次服务期结束事件循环之前,都要调用 flushAppendOnlyFile 函数,考虑是否将 aof_buf 缓冲区数据写入文件,这依赖于 appendfsync 的值。

AOF 重写

BGREWRITEAOF 通过读取服务器数据,开启子进程重写 AOF,执行 AOF 重写期间数据不一致主要通过设置 AOF 重写缓冲区实现。

AOF 重写时服务器执行几个工作:

  • 执行客户端操作
  • 将执行后的写命令追加到 AOF 缓冲区
  • 将执行后的写命令追加到 AOF 重写缓冲区

AOF 缓冲区缓冲区的内容定是写入和同步到 AOF, 对现有的 AOF 文件的处理工作会如常进行

从创建子进程开始,服务器的所有的写操作都被记录到重写缓冲区中

客户端

客户端

名字

127.0.0.1:6379> CLIENT SETNAME CL1
OK
127.0.0.1:6379> CLIENT list
id=3 addr=127.0.0.1:10773 fd=11 name=CL1 age=2463 idle=0 flags=N db=0 sub=0 psub=0 

multi=-1 qbuf=0 qbuf-free=32768 obl=0 oll=0 omem=0 events=r cmd=client

复制

在 Redis 中,可以使用 SLAVEOF 指令或者设置 slaveof 选项,让一个服务器去复制另一个服务器,称复制的服务器为主服务器,复制别人的服务器称从服务器。

127.0.0.1:6001> SLAVEOF 127.0.0.1 6379
OK

断开复制

127.0.0.1:6001> SLAVEOF no one
OK

旧版复制(2.8 以前)

Redis 2.8 以前版本复制包含同步命令传播

  • 同步操作用于将从服务器状态更新至当前服务器所处的状态
  • 命令传播操作则是用于在主服务器被修改,导致主从服务器状态不一致时,让主从服务器重新一致

同步

从服务器通过向主服务器发送 SYNC 指令完成同步

  1. 从服务器向主服务器发送 SYNC 指令
  2. 收到 SYNC 指令得主服务器执行 BGSAVE 命令,后端生成一个 RDB 文件,并使用缓冲区记录从现在开始所有的写命令
  3. 当主服务器的 BGSAVE 命令执行完毕后,会将 RDB 文件发送给从服务器,从服务器加载这个文件,将自己的状态更新至主服务器当前的状态
  4. 主服务器将记录在缓冲区的所有命令发送给从服务器,从服务器执行这些命令将自己的状态更新至主服务器的状态

命令传播

同步命令完成后,主从数据库的状态达到一致,但是这种一致不是一成不变的,服务器执行客户端命令时会导致主从服务器的状态有不一致。命令传播操作:主服务器会将自己执行的命令发送给从服务器,当从服务器执行命令后,主从服务器的状态又达到一致。

旧版缺陷

初次复制

没什么问题

断线后重新复制:处于命令传播的主从服务器因网络问题导致中断复制,旧版能让主从状态达到一致,但效率低下

新版复制

新版使用 PSYNC 替代旧版的 SYNC 命令, PSYNC 包括完整重同步和部分重同步

完整重同步和旧版的初始复制差不多,部分重同步则是用于主从断线后的复制:当从服务器重新连接时,主服务器会将从服务器断开期间的指令发送给从服务器,从服务器只要接收并执行这些指令,就能完成和主服务器状态一致。

部分重同步

复制偏移量

主从双方维护一个复制偏移量:主服务器每次向从服务器传播 N 个字节时,偏移量加 N;从服务器接收 N 个字节时复制偏移量加 N

复制积压缓冲区

复制积压缓冲区是主服务器维护的一个固定长度的先进先出队列,默认大小 1 M

当主服务器进行传播时,它不仅会将命令传播给从服务器,还会将命令入队到复制积压缓冲区

如果从服务器重连接时偏移量 offset 之后的数据仍然存在于复制挤压缓冲区,则主服务器进行部分重同步,否则进行完整重同步

服务器 ID

PSYNC

  • 如果从服务器没有执行过复制或者 SLAVEOF no one, 那么从服务器向主服务器发送一个 PSYNC 指令,主动请求主服务器进行完整重同步
  • 如果从服务器已经执行过完整重同步,那么从服务器将执行 PSYNC
  • 如果服务器返回 +FULLRESYNC 表示主从服务器进行完整重同步
  • 如果服务器返回 +CONTINUE,表示主从服务器进行部分重同步
  • 如果服务器返回 -ERR, 表示主服务器的版本低于 2.8, 无法识别 PSYNC 指令,从服务器将向主服务器发送 SYNC 指令

Sentinel

sentinel 配置, 一主多从

port 26379
sentinel monitor mymaster 127.0.0.1 6379 2 # mymaster 集群名字 主服务器地址:ip sentinel判断数量
sentinel down-after-milliseconds mymaster 5000
sentinel failover-timeout mymaster 60000
sentinel parallel-syncs mymaster 1 # parallel-syncs 设置在故障转移后可以重新配置为使用新的主副本的副本数。

配置 sentinel,至少三台且保证为奇数,启动 sentinel,

redis-server redis.windows-sentinel.conf --sentinel

Sentinel(哨兵) 是 Redis 高可用的解决方案:由一个或多个 Sentinel 实例组成的 Sentinel 系统可以监视任意多个主服务器,以及这些主服务器属下的从服务器,并在被监视主服务器处于下线状态时,自动将下线服务器的属下的某个从服务器升级为主服务器,然后由新的主服务器代替已下线的主服务器继续处理命令请求。

故障转移

下线主节点后,主节点的一个从节点升级为主节点,sentinel 查看

127.0.0.1:26379> SENTINEL slaves mymaster
1)  1) "name"
    2) "127.0.0.1:6379"
    3) "ip"
    4) "127.0.0.1"
    5) "port"
    6) "6379"
    7) "runid"
    8) ""
    9) "flags"
   10) "s_down,slave"

可以看到 flags:s_down,slave, 主节点下线并降级为从节点,重启旧的主节点后

127.0.0.1:26379> SENTINEL slaves mymaster
1)  1) "name"
    2) "127.0.0.1:6379"
    3) "ip"
    4) "127.0.0.1"
    5) "port"
    6) "6379"
    7) "runid"
    8) "3f1e60bc24fee7fcfed1b158d2e8e4c672fa1424"
    9) "flags"
   10) "slave"

旧的主节点称为新主节点的从节点

集群

发表评论

评论内容
 

评论列表, 共 0 条评论