redis基本数据结构

image.png-214kB

1
2
3
4
5
6
7
1. 字符串:redis没有直接使用C语言传统的字符串表示,而是自己实现的叫做简单动态字符串SDS的抽象类型。C语言的字符串不记录自身的长度信息,而SDS则保存了长度信息,这样将获取字符串长度的时间由O(N)降低到了O(1),同时可以避免缓冲区溢出和减少修改字符串长度时所需的内存重分配次数。
2. 链表linkedlist:redis链表是一个双向无环链表结构,很多发布订阅、慢查询、监视器功能都是使用到了链表来实现,每个链表的节点由一个listNode结构来表示,每个节点都有指向前置节点和后置节点的指针,同时表头节点的前置和后置节点都指向NULL。
3. 字典hashtable:用于保存键值对的抽象数据结构。redis使用hash表作为底层实现,每个字典带有两个hash表,供平时使用和rehash时使用,hash表使用链地址法来解决键冲突,被分配到同一个索引位置的多个键值对会形成一个单向链表,在对hash表进行扩容或者缩容的时候,为了服务的可用性,rehash的过程不是一次性完成的,而是渐进式的。
4. 跳跃表skiplist:跳跃表是有序集合的底层实现之一,redis中在实现有序集合键和集群节点的内部结构中都是用到了跳跃表。redis跳跃表由zskiplist和zskiplistNode组成,zskiplist用于保存跳跃表信息(表头、表尾节点、长度等),zskiplistNode用于表示表跳跃节点,每个跳跃表的层高都是1-32的随机数,在同一个跳跃表中,多个节点可以包含相同的分值,但是每个节点的成员对象必须是唯一的,节点按照分值大小排序,如果分值相同,则按照成员对象的大小排序。
5. 整数集合intset:用于保存整数值的集合抽象数据结构,不会出现重复元素,底层实现为数组。
6. 压缩列表ziplist:压缩列表是为节约内存而开发的顺序性数据结构,他可以包含多个节点,每个节点可以保存一个字节数组或者整数值。(新版本已被替换)
7. listpack:  redis5之后替换ziplist

sds

简单动态字符串 结构:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
//最长 2^8-1 长度的 sdshdr
struct __attribute__ ((__packed__)) sdshdr8 {
    //len 表示已使用长度
    uint8_t len; /* used */
    //buf分配的总长度, 也就是数组的总大小, 剩余大小 = alloc - len
    uint8_t alloc; /* excluding the header and null terminator */
    //低3位保存类型标志
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    //字符数组
    char buf[];
};
- 参考: https://zhuanlan.zhihu.com/p/388427900
- todo 需要恶补下C语言的结构体的内存存放结构

list

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//链表结构体
typedef struct list {
    //链表首节点
    listNode *head;
    //链表尾节点
    listNode *tail;
    //结构体的函数相当于多态, 由具体的对象提供对应的函数实现
    //链表复制指定节点的value的值, 值如果是结构体, 则需要对应的函数来拷贝
    void *(*dup)(void *ptr);
    //链表释放指定节点的value的内存的函数, 值如果是结构体, 则需要对应的函数释放内存
    void (*free)(void *ptr);
    //值的比较函数, 相当于 java 的equals, 用于比较结构体是否相等
    int (*match)(void *ptr, void *key);
    //链表长度
    unsigned long len;
} list;

//链表节点的结构体
typedef struct listNode {
    //前一个节点的引用
    struct listNode *prev;
    //下一个节点的引用
    struct listNode *next;
    //当前节点的值, 相当于 Object 类型
    void *value;
} listNode;

- 参考文档 https://zhuanlan.zhihu.com/p/388630205

dict

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//hash表结构体
typedef struct dictht {
    //hash表的指针数组, dictEntry * 表示hash节点的指针, 再加一个 *, 也就是dictEntry ** 表示数组的首地址
    dictEntry **table;
    //hash数组大小, 一般为 2^n
    unsigned long size;
    //hash数组长度掩码, sizemask =  size - 1
    unsigned long sizemask;
    //hash表的kv对的个数
    unsigned long used;
} dictht;

//hash表的节点
typedef struct dictEntry {
    //节点的key
    void *key;
    //节点的值 v , v 可以是指针, 也可以是uint64整数, 也可以是int64整数, 还可以是浮点数
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //下一个节点
    struct dictEntry *next;
} dictEntry;

//字典的结构体
typedef struct dict {
    //字典类型的指针
    dictType *type;
    //携带的私有数据
    void *privdata;
    //hash字典的数组, 长度为2, 主要是用于渐进式hash时使用
    dictht ht[2];
    //rehash下一个要迁移的桶索引, rehash 不进行时为 -1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // pauserehash > 0 表示 rehash 是暂停的. 安全的迭代需要停止
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

压缩列表 - 过时,redis新版本中逐渐替换掉了

image.png-67.4kB

1
2
3
压缩列表实际上类似于⼀个数组,数组中的每⼀个元素都对应保存⼀个数据。和数组不同的是,压缩列表在表头有三个字段zlbytes、zltail和zllen,分别表⽰列表⻓度、列表尾的偏移量和列表中的entry个数;压缩列表在表尾还有⼀个zlend,表⽰列表结束。

在压缩列表中,如果我们要查找定位第⼀个元素和最后⼀个元素,可以通过表头三个字段的⻓度直接定位,复杂度是O(1)。⽽查找其他元素时,就没有这么⾼效了,只能逐个查找,此时的复杂度就是O(N)了。

listpack 紧凑列表

listpack 为何能替换掉ziplist ziplist存在的问题: ziplist 设计出的紧凑型数据块可以有效利用内存,但在更新上,由于每一个 entry 都保留了前一个 entry 的 prevlen 长度,因此在插入或者更新时可能会出现连锁更新,这是一个影响效率的大问题。

  • 参考文档:https://juejin.cn/post/7093530299866284045

跳表

image.png-618.1kB

1
有序链表只能逐⼀查找元素,导致操作起来⾮常缓慢,于是就出现了跳表。具体来说,跳表在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {

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

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

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

} zskiplist;

redis全局设计

image.png-601.5kB

1
2
3
4
5
Redis使⽤了⼀个哈希表来保存所有键值对。一个哈希表,其实就是一个数组,数组的每个元素称为一个哈希桶,一个哈希表由多个哈希桶组成,一个哈希桶保存了键值对数据

即使值是集合等类型,哈希桶会存储具体集合的值的指针,而不是存储集合本身。

哈希桶中的entry元素中保存了*key和*value指针。分别指向了实际的键和值,这 样⼀来,即使值是⼀个集合,也可以通过*value指针被查找到。

哈希会冲突

image.png-496kB

1
写大量的数据,哈希冲突的概率虽然不会特别大(取决于哈希桶的数量),但不可避免。如果两个key计算出来,对应的是同一个哈希桶。redis采用拉链法的方式来解决哈希冲突,冲突的哈希桶用指针连接,通过*next指针指向下一个哈希桶。

rehash

1
2
3
4
5
6
哈希冲突明显,会导致寻找速度变慢。redis的策略是采用rehash操作,增加现有的哈希桶数量,让更多的桶之间分散保存,减少冲突

为了使rehash操作更⾼效,Redis默认使⽤了两个全局哈希表:哈希表1和哈希表2。⼀开始,当你刚插⼊数据时,默认使⽤哈希表1,此时的哈希表2并没有被分配空间。随着数据逐步增多,Redis开始执⾏ rehash,这个过程分为三步: 
1. 给哈希表2分配更⼤的空间,例如是当前哈希表1⼤⼩的两倍;
2. 把哈希表1中的数据重新映射并拷⻉到哈希表2中;
3. 释放哈希表1的空间。

渐进式rehash

image.png-353.8kB

1
在第⼆步拷⻉数据时,Redis仍然正常处理客⼾端请求,每处理⼀个请求时,从哈希表1中的第⼀个索引位置开始,顺带着将这个索引位置上的所有entries拷⻉到哈希表2中;等处理下⼀个请求时,再顺带拷⻉哈希表1中的下⼀个索引位置的entries。在渐进式 rehash 执行期间,新添加的数据会直接写入到哈希表2中,哈希表1只提供读取,不在进行写入操作,以保证哈希表1只减不增

渐进式rehash算法 todo

为了兼容scan命令,rehash的哈希算法非常巧妙,

rehash的时机

  • 服务的计划任务(databasesCron)中,会处理扩容缩容,键过期,rehash等。在没有其他进程处理db磁盘操作时,每1ms执行一次
  • 每次请求读写的时候,如果该db在rehash中,会将该key对应的entry写到新的hash表中

redis支持哪些数据类型

1
2
3
4
5
字符串对象string:int整数、embstr编码的简单动态字符串、raw简单动态字符串
列表对象list:ziplist、linkedlist
哈希对象hash:ziplist、hashtable
集合对象set:intset、hashtable
有序集合对象zset:ziplist、skiplist

redis为什么那么快

1
2
3
4
5
redis的速度非常的快,单机的redis就可以支撑每秒10几万的并发,相对于mysql来说,性能是mysql的几十倍。速度快的原因主要有几点:
- 完全基于内存操作
- C语言实现,优化过的数据结构,基于几种基础的数据结构,redis做了大量的优化,性能极高
- 使用单线程,无上下文的切换成本,避免多线程开发的并发控制问题
- 基于非阻塞的IO多路复用机制

redis6.0的多线程

1
2
3
4
5
Redis是单线程,主要是指Redis的的⽹络IO和键值对读写是由 ⼀个线程来完成的,这也是Redis对外提供键值存储服务的主要流程,但Redis的其他功能,⽐如持久化、 异步删除、集群数据同步等,其实是由额外的线程执⾏的。

redis使用多线程并非是完全摒弃单线程,redis还是使用单线程模型来处理客户端的请求,只是使用多线程来处理数据的读写和协议解析,执行命令还是使用单线程。

这样做的目的是因为redis的性能瓶颈在于网络IO而非CPU,使用多线程能提升IO读写的效率,从而整体提高redis的性能。

多路复用 todo

image.png-368.7kB

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
一个网络请求需要监听客⼾端请求(bind/listen),和客⼾端建⽴连 接(accept),从socket中读取请求(recv),解析客⼾端发送请求(parse),根据请求类型读取键值数据(get),最后给客⼾端返回结果,即向socket中写回数据(send)。

在这⾥的⽹络IO操作中,有潜在的阻塞点,分别是accept()和recv()。当Redis监听到⼀个客⼾端有连接请求,但⼀直未能成功建⽴起连接时,会阻塞在accept()函数这⾥,导致其他客⼾端⽆法和Redis建⽴连接。类似的,当Redis通过recv()从⼀个客⼾端读取数据时,如果数据⼀直没有到达,Redis也会⼀直阻塞在 recv()。

socket⽹络模型本⾝⽀持⾮阻塞模式。

针对监听套接字,我们可以设置⾮阻塞模式:当Redis调⽤accept()但⼀直未有连接请求到达时,Redis线程 可以返回处理其他操作,⽽不⽤⼀直等待。但是,你要注意的是,调⽤accept()时,已经存在监听套接字了。

虽然Redis线程可以不⽤继续等待,但是总得有机制继续在监听套接字上等待后续连接请求,并在有请求时 通知Redis。

Linux中的IO多路复⽤机制是指⼀个线程处理多个IO流,就是我们经常听到的select/epoll机制。简单来说,在Redis只运⾏单线程的情况下,该机制允许内核中,同时存在多个监听套接字和已连接套接字。内核会⼀直监听这些套接字上的连接请求或数据请求。⼀旦有请求到达,就会交给Redis线程处理,这就实现了⼀个 Redis线程处理多个IO流的效果。

redis持久化机制

1
redis为数据持久化提供了两种方式,一种是AOF(append only file),用于记录每次操作命令的记录,一种是RDB,用于存储当前的内存快照

AOF

  • 三种持久化写回策略
1
2
3
always ##aof_buf内容写入并同步到AOF文件
everysec ##将aof_buf中内容写入到AOF文件,如果上次同步AOF文件时间距离现在超过1秒,则再次对AOF文件进行同步
no ##将aof_buf内容写入AOF文件,但是并不对AOF文件进行同步,同步时间由操作系统决定
  • 问题
1
AOF不是完美的,因为redis是单线程的,在执行完命令写回AOF文件的时候,会阻塞下一个操作。因此为了达到性能与可靠性的权衡,一般会默认选择everysec
  • 重写机制
1
2
3
4
5
6
7
8
因为每次操作的命令都会追加到AOF文件中,这会导致AOF文件异常的大。AOF重写机制就是在重写时,Redis根据数据库的现状创建⼀个新的AOF⽂件,也就是说,读取数据库中的所有键值对,然后对每⼀个键值对⽤⼀条命令记录它的写⼊。重写机制具有“多变⼀”功能。所谓的“多变⼀”,也就是说,旧⽇志⽂件中的多条命令,在重写后的新⽇志中变成了⼀条命令。

和AOF⽇志由主线程写回不同,重写过程是由后台线程bgrewriteaof来完成的,这也是为了避免阻塞主线 程,导致数据库性能下降。 我把重写的过程总结为“⼀个拷⻉,两处⽇志”。

“⼀个拷⻉”就是指,每次执⾏重写时,主线程fork出后台的bgrewriteaof⼦进程。此时,fork会把主线程的内存拷⻉⼀份给bgrewriteaof⼦进程,这⾥⾯就包含了数据库的最新数据。然后,bgrewriteaof⼦进程就可以在不影响主线程的情况下,逐⼀把拷⻉的数据写成操作,记⼊重写⽇志。

“两处⽇志”⼜是什么呢?
因为主线程未阻塞,仍然可以处理新来的操作。此时,如果有写操作,第⼀处⽇志就是指正在使⽤的AOF⽇ 志,Redis会把这个操作写到它的缓冲区。这样⼀来,即使宕机了,这个AOF⽇志的操作仍然是⻬全的,可 以⽤于恢复。 ⽽第⼆处⽇志,就是指新的AOF重写⽇志。这个操作也会被写到重写⽇志的缓冲区。这样,重写⽇志也不会 丢失最新的操作。等到拷⻉数据的所有操作记录重写完成后,重写⽇志记录的这些最新操作也会写⼊新的 AOF⽂件,以保证数据库最新状态的记录。此时,我们就可以⽤新的AOF⽂件替代旧⽂件了。

RDB

1
2
3
4
5
6
7
8
RDB持久化可以手动执行也可以根据配置定期执行,它的作用是将某个时间点上的数据库状态保存到RDB文件中,RDB文件是一个压缩的二进制文件,通过它可以还原某个时刻数据库的状态。由于RDB文件是保存在硬盘上的,所以即使redis崩溃或者退出,只要RDB文件存在,就可以用它来恢复还原数据库的状态。
可以通过SAVE或者BGSAVE来生成RDB文件。
SAVE命令会阻塞redis进程,直到RDB文件生成完毕,在进程阻塞期间,redis不能处理任何命令请求,这显然是不合适的。
BGSAVE则是会fork出一个子进程,然后由子进程去负责生成RDB文件,父进程还可以继续处理命令请求,不会阻塞进程。

因为在存取快照要保证某一点的数据不能动,但写操作不能动就又阻塞了主线程,这时候就需要采用写时复制技术 (Copy-On-Write,COW),在执⾏快照的同时,正常处理写操作。如果主线程要修改⼀块数据(例如图中的键值对C),那么,这块数据就会被复制⼀份,⽣成 该数据的副本。然后,bgsave⼦进程会把这个副本数据写⼊RDB⽂件,⽽在这个过程中,主线程仍然可以 直接修改原来的数据。

对于RDB,更新频率也是个问题,也不能时时取快照,因此服务器宕机时,可能还是会让数据丢失

防止数据不丢失

1
将AOF(append only file)与RDB混合使用,AOF记录两次快照间的日志

缓存相关问题

image.png-1304.2kB

缓存击穿

1
2
3
4
5
6
7
缓存击穿的概念就是单个key并发访问过高,过期时导致所有请求直接打到db上.缓存击穿 的情况,经常发⽣在热点数据过期失效时


解决方案:
1. 加锁更新,比如请求查询A,发现缓存中没有,对A这个key加锁,同时去数据库查询数据,写入缓存,再返回给用户,这样后面的请求就可以从缓存中拿到数据了。
2. 将过期时间组合写在value中,通过异步的方式不断的刷新过期时间,防止此类现象。
3. 对于访问特别频繁的热点数据, 不设置过期时间

缓存雪崩

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
当某一时刻发生大规模的缓存失效的情况,比如你的缓存服务宕机了,会有大量的请求进来直接打到DB上,这样可能导致整个系统的崩溃,称为雪崩。

第⼀个原因是:缓存中有⼤量数据同时过期,导致⼤量请求⽆法得到处理
第二个原因是:redis缓存服务器宕机

针对雪崩几个解决方案:
1. 针对不同key设置不同的过期时间,避免同时过期
2. 限流,如果redis宕机,可以限流,避免同时刻大量请求打崩DB
3. 集群方案,事先预防
4. 二级缓存,同热key的方案。

缓存穿透

1
2
3
4
5
6
7
8
9
缓存穿透是指查询不存在缓存中的数据,每次请求都会打到DB,就像缓存不存在一样。

产生条件:
1.业务层误操作:缓存中的数据和数据库中的数据被误删除了,所以缓存和数据库中都没有数据; 
2.恶意攻击:专⻔访问数据库中没有的数据。

解决方案:
1.缓存空值或缺省值
2.加一层布隆过滤器。布隆过滤器的原理是在你存入数据的时候,会通过散列函数将它映射为一个位数组中的K个点,同时把他们置为1
布隆过滤器
1
2
3
4
5
6
7
布隆过滤器由⼀个初值都为0的bit数组和N个哈希函数组成,可以⽤来快速判断某个数据是否存在。当我们想标记某个数据存在时(例如,数据已被写⼊数据库),布隆过滤器会通过三个操作完成标记: 

⾸先,使⽤N个哈希函数,分别计算这个数据的哈希值,得到N个哈希值。

然后,我们把这N个哈希值对bit数组的⻓度取模,得到每个哈希值在数组中的对应位置。 最后,我们把对应位置的bit位设置为1,这就完成了在布隆过滤器中标记数据的操作。

如果数据不存在(例如,数据库⾥没有写⼊数据),我们也就没有⽤布隆过滤器标记过数据,那么,bit数 组对应bit位的值仍然为0。

image.png-384.6kB

Redis的过期策略

惰性删除

1
惰性删除指的是当我们查询key的时候才对key进行检测,如果已经达到过期时间,则删除。显然,他有一个缺点就是如果这些过期的key没有被访问,那么他就一直无法被删除,而且一直占用内存。

定期删除

1
指的是redis每隔一段时间对数据库做一次检查,删除里面的过期key。由于不可能对所有key去做轮询来删除,所以redis会每次随机取一些key去做检查和删除。

定期+惰性都未删除

1
2
3
4
5
6
7
假设redis每次定期随机查询key的时候没有删掉,这些key也没有做查询的话,就会导致这些key一直保存在redis里面无法被删除,这时候就会走到redis的内存淘汰机制。
volatile-lru:从已设置过期时间的key中,移出最近最少使用的key进行淘汰
volatile-ttl:从已设置过期时间的key中,移出将要过期的key
volatile-random:从已设置过期时间的key中随机选择key淘汰
allkeys-lru:从key中选择最近最少使用的进行淘汰
allkeys-random:从key中随机选择key进行淘汰
noeviction:当内存达到阈值的时候,新写入操作报错

redis高可用

主从库模式

1
2
读操作:主从库都可以
写操作:只在主库写,然后同步给从库

主从同步步骤 image.png-848.6kB

1
2
3
4
5
6
7
slave 启动主从复制配置:replicaof serverip
slave发送psync命令到master,psync runId(主库的实例id) -1(offset,第一次初始化为-1)
master主库收到psync命令后,会⽤FULLRESYNC响应命令带上两个参数:主库runID和主库⽬前的复制进度offset,返回给从库。从库收到响应后,会记录下这两个参数。
master收到psync之后,执行bgsave,生成RDB全量文件
master把slave的写命令记录到repl_buffer缓存中
bgsave执行完毕之后,发送RDB文件到slave,slave执行
master发送repl_buffer中的写命令到slave,slave执行

如果有很多从库,建议主-从-从模式,由中间的从库作多副本同步的工作 如果主从库连接断连,主库会将断连后的增量数据保存在为repl_backlog_buffer,等恢复了再将增量的数据同步给主库.主从库都会维护一个读写的offset位置master_repl_offset,slave_repl_offset,如果断连的话就根据位置比对,将这之间的命令重新发送给slave

哨兵模式

基于主从方案的缺点还是很明显的,假设master宕机,那么就不能写入数据,那么slave也就失去了作用,整个架构就不可用了,除非你手动切换,主要原因就是因为没有自动故障转移机制。而哨兵(sentinel)的功能比单纯的主从架构全面的多了,它具备自动故障转移、集群监控、消息通知等功能。

  • 哨兵的作用
  • image.png-318.7kB
1
2
3
4
5
6
7
哨兵其实就是⼀个运⾏在特殊模式下的Redis进程,主从库实例运⾏的同时,它也在运⾏。哨兵主要负责的 就是三个任务:监控、选主(选择主库)和通知。

监控是指哨兵进程在运⾏时,周期性地给所有的主从库发送PING命令,检测它们是否仍然 在线运⾏。如果从库没有在规定时间内响应哨兵的PING命令,哨兵就会把它标记为“下线状态”;同样, 如果主库也没有在规定时间内响应哨兵的PING命令,哨兵就会判定主库下线

主库挂了以后,哨兵就需要从很多个从库⾥,按照⼀定的规 则选择⼀个从库实例,把它作为新的主库。

在执⾏通知任务时,哨兵会把新主库的连接信息发给其他从库,让 它们执⾏replicaof命令,和新主库建⽴连接,并进⾏数据复制。同时,哨兵会把新主库的连接信息通知给客 ⼾端,让它们把请求操作发到新主库上。
  • 哨兵的误判
1
单节点的哨兵容易产生误着,在此降低误判率,在实际应⽤时,哨兵机制通常采⽤多实例的⽅式进⾏部署,多个哨兵实例通过“少数服从 多数”的原则,来判断主库是否客观下线。⼀般来说,我们可以部署三个哨兵,如果有两个哨兵认定主 库“主观下线”,就可以开始切换过程。当然,如果你希望进⼀步提升判断准确率,也可以再适当增加哨兵个数,⽐如说使⽤五个哨兵。
  • 哨兵的通信机制
1
2
3
1. 基于pub/sub机制的哨兵集群组成过程;
2. 基于INFO命令的从库列表,这可以帮助哨兵和从库建⽴连接;
3. 基于哨兵⾃⾝的pub/sub功能,这实现了客⼾端和哨兵之间的事件通知。
  • 哨兵的工作过程
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
1.初始化sentinel,将普通的redis代码替换成sentinel专用代码
2.初始化masters字典和服务器信息,服务器信息主要保存ip:port,并记录实例的地址和ID
3.创建和master的两个连接,命令连接和订阅连接,并且订阅sentinel:hello频道
4.每隔10秒向master发送info命令,获取master和它下面所有slave的当前信息
5.当发现master有新的slave之后,sentinel和新的slave同样建立两个连接,同时每个10秒发送info命令,更新master信息
6.sentinel每隔1秒向所有服务器发送ping命令,如果某台服务器在配置的响应时间内连续返回无效回复,将会被标记为下线状态
7.选举出领头sentinel,领头sentinel需要半数以上的sentinel同意
领头sentinel从已下线的的master所有slave中挑选一个,将其转换为master
8.让所有的slave改为从新的master复制数据
9.将原来的master设置为新的master的从服务器,当原来master重新回复连接时,就变成了新master的从服务器

sentinel会每隔1秒向所有实例(包括主从服务器和其他sentinel)发送ping命令,并且根据回复判断是否已经下线,这种方式叫做主观下线。当判断为主观下线时,就会向其他监视的sentinel询问,如果超过半数的投票认为已经是下线状态,则会标记为客观下线状态,同时触发故障转移。

redis集群

切片集群

1
2
3
4
5
Redis Cluster⽅案采⽤哈希槽(Hash Slot,接下来我会直接称之为Slot),来处理数据和实例 之间的映射关系。在Redis Cluster⽅案中,⼀个切⽚集群共有16384个哈希槽,这些哈希槽类似于数据分 区,每个键值对都会根据它的key,被映射到⼀个哈希槽中

具体的映射过程分为两⼤步:⾸先根据键值对的key,按照CRC16算法计算⼀个16 bit的值;然后,再⽤这 个16bit值对16384取模,得到0~16383范围内的模数,每个模数代表⼀个相应编号的哈希槽。

我们在部署Redis Cluster⽅案时,可以使⽤cluster create命令创建集群,此时,Redis会⾃动把这些槽平均 分布在集群实例上。例如,如果集群中有N个实例,那么,每个实例上的槽个数为16384/N个。
  • 客⼾端如何定位数据?
1
集群的实例增减,或者是为了实现负载均衡⽽进⾏的数据重新分布,会导致哈希槽和实例的映射关系发⽣变化,客⼾端发送请求时,会收到命令执⾏报错信息。了解了MOVED和ASK命令,你就不会为这类报 错⽽头疼了。
  • 故障转移
1
如果节点A向节点B发送ping消息,节点B没有在规定的时间内响应pong,那么节点A会标记节点B为pfail疑似下线状态,同时把B的状态通过消息的形式发送给其他节点,如果超过半数以上的节点都标记B为pfail状态,B就会被标记为fail下线状态,此时将会发生故障转移,优先从复制数据较多的从节点选择一个成为主节点,并且接管下线节点的slot,整个过程和哨兵非常类似,都是基于Raft协议做选举。

redis事务

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
redis通过MULTI、EXEC、WATCH等命令来实现事务机制,事务执行过程将一系列多个命令按照顺序一次性执行,并且在执行期间,事务不会被中断,也不会去执行客户端的其他请求,直到所有命令执行完毕。事务的执行过程如下:

1.服务端收到客户端请求,事务以MULTI开始
2.如果客户端正处于事务状态,则会把事务放入队列同时返回给客户端QUEUED,反之则直接执行这个命令
3.当收到客户端EXEC命令时,WATCH命令监视整个事务中的key是否有被修改,如果有则返回空回复到客户端表示失败,否则redis会遍历整个事务队列,执行队列中保存的所有命令,最后返回结果给客户端

WATCH的机制本身是一个CAS的机制,被监视的key会被保存到一个链表中,如果某个key被修改,那么REDIS_DIRTY_CAS标志将会被打开,这时服务器会拒绝执行事务。

事务是具有ACID特性的一组操作,redis的事务支持一致性与隔离性,持久性取决于redis的配置,原子性不一定能够保证。

当事务中使⽤的命令有逻辑性错误,原⼦性得不到保证,在其它情况下,事务都可以原⼦性执⾏。
Redis 事务不支持检查那些程序员自己逻辑错误。例如对 String 类型的数据库键执行对 HashMap 类型的操作!

使用watch机制来保证隔离性,当检测到有数据更改时,放弃事务的执行。

redis的原子操作

1
2
3
4
5
在大并发情况下,虽然redis是单线程的,但是有些需要分步执行或者需要读取后再操作的,比如读取原先的库存,再减1,或者设置原先的库存的超时时间等,当我们需要对读取的数据做更多判断,或者是我们对数据的修改不是简单的增减时,就得使用另外的方式

一般可以使用两种方式来保证原子性
1.redis内部的实现方式,redis对值的加减可以使用INCR与decr,设置过期时间可以使用SETNX等。
2.将代码封装成lua脚本

redis实现分布式锁

1
2
3
4
5
6
7
8
在基于单个Redis实例实现分布式锁时,对于加锁操作,我们需要满⾜三个条件。 
1. 加锁包括了读取锁变量、检查锁变量值和设置锁变量值三个操作,但需要以原⼦操作的⽅式完成,所 以,我们使⽤SET命令带上NX选项来实现加锁;
2. 锁变量需要设置过期时间,以免客⼾端拿到锁后发⽣异常,导致锁⼀直⽆法释放,所以,我们在SET命令 执⾏时加上EX/PX选项,设置其过期时间;
3. 锁变量的值需要能区分来⾃不同客⼾端的加锁操作,以免在释放锁时,出现误释放操作,所以,我们使⽤SET命令设置锁变量值时,每个客⼾端设置的值是⼀个唯⼀值,⽤于标识客⼾端。

多节点redis实现可以参照redlock

https://www.redis.com.cn/topics/distlock.html

redis的io多路复用

1
2

采用epool的方式 

redis zset为什么使用skiplist而不用红黑树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
跳表在区间查询的时候效率是高于红黑树的,跳表进行查找O(logn)的时间复杂度定位到区间的起点,然后在原始链表往后遍历就可以了 ,其他插入和单个条件查询,更新两者的复杂度都是相同的O(logn)

跳表的代码实现相对于红黑树更容易实现

跳表更加灵活,他可以通过改变索引构建策略,有效平衡执行效率和内存消耗。(红黑树的平衡是通过左旋转和有旋转来进行平衡)


1)在做范围查找的时候,平衡树比skiplist操作要复杂。在平衡树上,我们找到指定范围的小值之后,还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造,这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单,只需要在找到小值之后,对第1层链表进行若干步的遍历就可以实现。
2)平衡树的插入和删除操作可能引发子树的调整,逻辑复杂,而skiplist的插入和删除只需要修改相邻节点的指针,操作简单又快速。
3)从内存占用上来说,skiplist比平衡树更灵活一些。一般来说,平衡树每个节点包含2个指针(分别指向左右子树),而skiplist每个节点包含的指针数目平均为1/(1-p),具体取决于参数p的大小。如果像Redis里的实现一样,取p=1/4,那么平均每个节点包含1.33个指针,比平衡树更有优势。
4)查找单个key,skiplist和平衡树的时间复杂度都为O(log n),大体相当;而哈希表在保持较低的哈希值冲突概率的前提下,查找时间复杂度接近O(1),性能更高一些。所以我们平常使用的各种Map或dictionary结构,大都是基于哈希表实现的。
5)从算法实现难度上来比较,skiplist比平衡树要简单得多。