1~5. Java基础

• https://www.jianshu.com/p/ace3782209cc

6. Kafka

• Kafka基础教程
• Kafka offset管理
• Kafka Consumer Group和Consumer Rebalance机制
• Kafka 读写原理与存储结构
• Kafka消息送达语义详解
• Kafka事务特性详解
• Kafka常见问题精选
• Kafka架构设计

7. 操作系统

• IO多路复用模型
• https://cloud.tencent.com/developer/article/1165632

7.1 进程，线程和协程

进程是操作系统分配资源（CPU，内存等）的基本单位。它是程序执行时的一个实例。而线程是程序执行时的最小单位，一个进程可以包含多个线程，这些线程共享进程的所有资源，但又独自拥有自己的堆栈和局部变量。

• 进程是资源分配的最小单位，而线程是程序执行时的最小单元
• 每个进程拥有自己独立的地址空间，每启动一个进程，系统就会为它分配地址空间（建立数据表来维护代码段、堆栈段和数据段），这种操作非常昂贵。而线程则共享进程的地址空间，因此CPU切换一个线程的花费远比进程要小很多，同时创建一个线程的开销也比进程要小很多。
• 线程间的通信更加容易，同一个进程中的线程可以通过共享全局变量，静态变量等方式通信。而进程间通信则需要使用IPC。

而协程是属于线程的。协程程序是在线程里面跑的，因此没有线程的上下文切换消耗。协程的调度切换是用户(程序员)手动切换的，因此更加灵活，因此又叫用户空间线程。由于协程是用户调度的，所以不会出现执行一半的代码片段被强制中断了，因此无需原子操作锁。

7.2 进程间通信

进程通信就是两个进程之间进行数据交换。下面是常用的进程间通信的方式：

• 管道（pipe）
  管道是一种最古老也是最基本的系统IPC形式，所有的Linux系统都提供此种通信机制。管道有两个口，一个入水口一个出水口。pipe系统调用会返回两个文件描述符，一个文件描述符用来写一个用来读。如上图所示，两个file结构指向同一个inode，对应管道在内存种所获得的一片区域。这里稍微要注意的一点是，尽管我们平时的应用都是一个管道对应一个写进程一个读进程，但是管道本身是支持多个进程进行读写的，他们只要对相同的描述符进行操作，加之系统的互斥进程就可以实现多进程的通信。这里也可以看出管道是半双工的，没有一个文件描述符可以用来进行读and写，如果想在两进程间进行全双工操作就开两条管道吧。
• 信号量（semophore ）
  信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
• 消息队列（message queue）
  通过int msgget(key_t, key, int msgflg)和int msgsend(int msgid, const void *msg_ptr, size_t msg_sz, int msgflg)函数来进行消息的读和写。消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
• 信号（signal）
  信号是在软件层次上对中断机制的一种模拟，在原理上，一个进程收到一个信号与处理器收到一个中断请求可以说是一样的。信号是异步的，一个进程不必通过任何操作来等待信号的到达，事实上，进程也不知道信号到底什么时候到达。信号是进程间通信机制中唯一的异步通信机制，可以看作是异步通知，通知接收信号的进程有哪些事情发生了。
• 共享内存（shared memory）
  共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
• 套接字（socket）
  套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。

7.3 select，poll和epoll

select，poll，epoll都是IO多路复用的机制。I/O多路复用就通过一种机制，可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。但select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。

select流程如下：
（1）从用户空间拷贝fd_set到内核空间
（2）遍历所有fd，调用其对应的poll方法
（3）poll方法返回时会返回一个描述读写操作是否就绪的mask掩码
（4）如果遍历完所有的fd，还没有返回一个可读写的mask掩码，则调用select的进程（也就是current）进入睡眠（睡眠时间为schedule_timeout）。当设备驱动发生自身资源可读写后，会唤醒其等待队列上睡眠的进程。
（5）如果超过一定的超时时间（schedule_timeout指定），还是没人唤醒，则调用select的进程会重新被唤醒获得CPU，进而重新遍历fd，判断有没有就绪的fd。
（6）把fd_set从内核空间拷贝到用户空间。

select的几大缺点：
（1）每次调用select，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多时会很大
（2）同时每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大
（3）select支持的文件描述符数量太小了，默认是1024

poll的实现和select非常相似，只是描述fd集合的方式不同，poll使用pollfd结构而不是select的fd_set结构，其他的都差不多。

select和poll都只提供了一个函数——select或者poll函数。而epoll提供了三个函数，epoll_create,epoll_ctl和epoll_wait，epoll_create是创建一个epoll句柄；epoll_ctl是注册要监听的事件类型；epoll_wait则是等待事件的产生。

对于第一个缺点，epoll的解决方案在epoll_ctl函数中。每次注册新的事件到epoll句柄中时（在epoll_ctl中指定EPOLL_CTL_ADD），会把所有的fd拷贝进内核，而不是在epoll_wait的时候重复拷贝。epoll保证了每个fd在整个过程中只会拷贝一次。

对于第二个缺点，epoll的解决方案不像select或poll一样每次都把current轮流加入fd对应的设备等待队列中，而只在epoll_ctl时把current挂一遍（这一遍必不可少）并为每个fd指定一个回调函数，当设备就绪，唤醒等待队列上的等待者时，就会调用这个回调函数，而这个回调函数会把就绪的fd加入一个就绪链表）。epoll_wait的工作实际上就是在这个就绪链表中查看有没有就绪的fd。

总结：
（1）select，poll实现需要自己不断轮询所有fd集合，直到设备就绪，期间可能要睡眠和唤醒多次交替。而epoll其实也需要调用epoll_wait不断轮询就绪链表，期间也可能多次睡眠和唤醒交替。但是它是设备就绪时，调用回调函数，把就绪fd放入就绪链表中，并唤醒在epoll_wait中进入睡眠的进程。虽然都要睡眠和交替，但是select和poll在“醒着”的时候要遍历整个fd集合，而epoll在“醒着”的时候只要判断一下就绪链表是否为空就行了，这节省了大量的CPU时间。这就是回调机制带来的性能提升。

（2）select，poll每次调用都要把fd集合从用户态往内核态拷贝一次，并且要把current往设备等待队列中挂一次，而epoll只要一次拷贝，而且把current往等待队列上挂也只挂一次（在epoll_wait的开始，注意这里的等待队列并不是设备等待队列，只是一个epoll内部定义的等待队列）。这也能节省不少的开销。

7.4 同步IO和异步IO

同步IO分为同步阻塞IO和同步非阻塞IO。Java中BIO是同步阻塞IO，NIO是同步非阻塞IO。同步阻塞IO在内核数据未准备好时，IO线程会直接阻塞直到内核数据准备完成。而同步非阻塞IO在内核数据未准备好时，read请求也能立即返回（此时IO线程可以做其他事或者不断轮询判断内核数据是否准备好）。

为了解决IO线程在用户空间不断轮询的问题，因此提出了IO多路复用的机制。通过向selector注册多个channel，能够实现没有数据准备好时阻塞，数据准备好时返回对应channel。从而实现了单线程处理多个socket连接。Java NIO即采用了IO多路复用机制，它的底层依赖于内核的epoll函数来实现。

而异步IO于同步IO的区别在于，异步IO完全没有阻塞的过程。即使是同步非阻塞IO，也存在着从内核拷贝准备好的数据到用户空间的过程，这一个拷贝过程仍然是阻塞的。而异步IO在一开始注册好了一个回调函数，内核准备好数据后直接将数据拷贝进了用户空间并调用回调函数。因此异步IO不存在阻塞过程。Java中AIO是一种异步IO。

IO分类.PNG

7.5 进程，僵尸进程和孤儿进程

一个进程都由另一个称之为父进程的进程启动，被父进程启动的进程叫做子进程。Linux系统启动时候，它将运行一个名为init的进程，该进程是系统运行的第一个进程，它的进程号为1，它负责管理其它进程，可以把它看做是操作系统进程管理器，它是其它所有进程的祖先进程。系统中的进程要么是由init进程启动，要么是由init进程启动的其他进程启动。

Linux创建进程的函数有：system，exec和fork。

system函数调用“/bin/sh -c command”执行特定的命令，阻塞当前进程直到command命令执行完毕。system()会调用fork()产生子进程，由子进程来调用“/bin/sh -c command”来执行参数string字符串所代表的命令，此命令执行完后随即返回原调用的进程。使用System函数并非启动其他进程的理想手段，因为它必须用一个shell来启动需要的程序。

exec是一个函数组，包括execl，execlp等6个函数。exec函数可以把当前进程替换为一个新进程（仅仅是替换，PID不变），新进程由path或file参数指定。新进程的PID、PPID和nice值与原来的完全一样，exec只是用另一个新程序替换了当前进程的正文、数据、堆和栈段。 事实上，这里发生的一切其实就是， 当进程调用一种exec函数时，该进程完全由新进程替换。

fork函数操作系统会复制一个与父进程完全相同的子进程，虽说是父子关系，但是在操作系统看来，他们更像兄弟关系。这2个进程共享代码空间，但是数据空间是互相独立的，子进程数据空间中的内容是父进程的完整拷贝，指令指针也完全相同，子进程拥有父进程当前运行到的位置，并将从fork调用处执行，就像原进程一样。

僵尸进程

当一个子进程结束运行时，并非马上就消失掉，而是留下一个称为僵尸进程(Zombie)的数据结构，等待父进程处理。

在Linux进程的状态中，僵尸进程是非常特殊的一种，它已经放弃了几乎所有内存空间，没有任何可执行代码，也不能被调度，仅仅在进程列表中保留一个位置，直到父进程通过wait / waitpid 函数来取得子进程的终止状态时才释放。如果它的父进程没安装SIGCHLD信号处理函数调用wait或waitpid()等待子进程结束，又没有显式忽略该信号，那么它就一直保持僵尸状态。如果这时父进程结束了，那么init进程自动会接手这个子进程，为它"收尸"，它还是能被清除的。

孤儿进程

一个父进程退出，而它的一个或多个子进程还在运行，那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。

僵尸进程和孤儿进程的区别：

• 僵尸进程：当前进程运行结束父进程未结束且父进程没有调用wait来清理子进程。如果大量的产生僵死进程，将因为没有可用的进程号而导致系统不能产生新的进程。
• 孤儿进程：当前进程结束且父进程在它之前结束，这时子进程被“托孤”于init进程。孤儿进程无危害。

8. Docker

Docker是一个软件，它通过容器技术能够实现快速部署和运行应用。一个容器是Docker中的一个管理单元，它其中包含了应用所必须的运行环境，因此应用能够快速的在容器中启动和运行，并且能够毫无成本的迁移到其他安装了Docker的物理机器上。

• Docker网络模型
• Dockerfile RUN，CMD，ENTRYPOINT命令区别
• Docker数据存储总结
• Doker Git Book

9. Kubernetes

• Kubernetes从入门到实践
  
• Kubernetes Git Book

10. 限流

10.1 令牌桶算法

令牌桶算法的原理是，系统以固定的速率往令牌桶中放入令牌；当请求进来时，则从桶中取走令牌；当桶中令牌为空时，触发限流。下面是一个简易的令牌桶实现：

public class RateLimiter {
    private int capacity;
    private int rate;
    private long lastTimestamp;
    private int token;

    public RateLimiter(int permitsPerSecond) {
        this.capacity = permitsPerSecond; //令牌桶容量
        this.rate = permitsPerSecond / 1000;  //每毫秒产生rate个令牌
    }

    public synchronized boolean tryAcquire(int permits) {
        long now = System.currentTimeMillis();
        int newToken = (int) ((now - lastTimestamp) * rate);
        if (newToken > 0) {
            token = Math.min(capacity, token + newToken);
            lastTimestamp = now;
        }
        if (token >= permits) {
            token -= permits;
            return true;
        }
        return false;
    }
}

11. Cassandra

• Cassandra 读机制
• Cassandra 写机制
• Cassandra 删除机制
• Cassandra架构
• Cassandra副本机制
• Cassandra组件

12. Redis

12.1 缓存的作用和可能的问题

缓存的优势主要有两个：高性能和高并发。由于缓存存储在内存中，因此查询速度远远快于数据库查询。另外，单机Mysql的并发量在2000QPS左右，而Redis单机并发量通常在几万的级别，因此天然支持高并发。

使用缓存可能带来的问题包括：

• 缓存雪崩，缓存穿透和缓存击穿
• 缓存与数据库的一致性问题
• 缓存并发竞争

缓存雪崩

缓存雪崩，指的是大量缓存在一段时间内集体失效。这样的话，短时间内大量请求会直接打到数据库。

解决方案：针对这种情况，可以在缓存的生存时间后面再加上一个随机数，这样的话就不至于同一时刻集体过期。实际上，因为大量缓存失效意味着这些缓存在同一时刻被设置的，而这种情况不多见。

缓存穿透

缓存穿透是指大量请求同时访问数据中不存在的数据。由于数据库中不存在，因此这些请求每次访问都会跳过缓存直接访问数据库。

解决方案：服务只要从数据库中没查到，就写一个默认值到缓存里，并设置一个过期时间。这样的话，下次有相同的key 来访问的时候，在缓存失效之前，都可以直接从缓存中取数据。

缓存击穿

缓存击穿是指在热点数据过期的瞬间，大量请求直接打到数据库，从而造成数据库无法支撑的现象。

解决方案：可以将热点数据设置为永远不过期；或者基于 redis or zookeeper 实现互斥锁，等待第一个请求构建完缓存之后，再释放锁，进而其它请求才能通过该 key 访问数据。

缓存双写一致性

Cache Aside Pattern

最经典的缓存+数据库读写的模式，就是 Cache Aside Pattern。

• 读的时候，先读缓存，缓存没有的话，就读数据库，然后取出数据后放入缓存，同时返回响应。
• 更新的时候，先更新数据库，然后再删除缓存。

下面是一些常见的保证缓存一致性的方案：

1. 先写数据库，再更新缓存（弃用）

这个方案主要缺点有两个：
（1）有可能更新缓存的代价很高。比如可能更新了某个表的一个字段，然后其对应的缓存，是需要查询另外两个表的数据并进行运算，才能计算出缓存最新的值的。
（2）可能缓存并不会被频繁访问。如果你频繁修改一个缓存涉及的多个表，缓存也频繁更新。那么对于一个读请求很小，写请求很多的缓存来说，那么代价就很高。

2. 先删除缓存，再更新数据库

可能的不一致性：A删除了缓存后，再更新数据库之前，B访问了该数据。由于没有缓存，因此B直接读取数据库，查询到了旧值，并写入了缓存。此后A再更新了数据库数据。这就造成了数据的不一致性。

解决方案：采用延时双删策略

public void write(String key,Object data){
        redis.delKey(key);
        db.updateData(data);
        Thread.sleep(1000);
        redis.delKey(key);
}

在更新数据库后，再进行一次Redis key的延迟删除。这个具体的延时时长取决于业务的读耗时，可以设置成读耗时+几十毫秒。这样能够确保删除读操作带来的脏数据。

采用这种延时双删策略，吞吐量降低怎么办？
可以将第二次删除作为异步的。例如重起一个线程，进行异步删除。

3. 先更新数据库，再删除缓存

可能的不一致性：缓存刚好失效，A读取数据库得到旧值。B更新数据库后，B删除缓存。A将旧值写入缓存。

上面的这种情况概率非常小，因为数据库的读操作往往比写操作快很多，因此基本不可能出现A读完数据后，要等待B更新完数据后再写旧值到缓存。

另外，针对方案2和方案3，都可能会存在删除缓存失败的情况，这样缓存中的数据就是脏数据了。在这种情况下，可以通过将要删除的key发送给消息队列，consumer通过消费删除消息执行Redis key的删除，删除失败则不断重试。另外，还有一种和业务逻辑解耦的方式：通过订阅Mysql的binglog，然后订阅程序提取出所需要的数据以及key，发送给消息队列，Consumer负责消费消息然后进行Redis数据的删除，删除失败则不断重试。

另外，通过给缓存设置过期时间，能够确保最基本的最终一致性。

如果必须保证强一致性的话，那么可以通过内部队列的方式，将读写请求串行化。下面是基本思想：

更新数据的时候，根据数据的唯一标识，将操作路由之后，发送到一个 jvm 内部队列中。读取数据的时候，如果发现数据不在缓存中，那么将重新执行“读取数据+更新缓存”的操作，根据唯一标识路由之后，也发送到同一个 jvm 内部队列中。

一个队列对应一个工作线程，每个工作线程串行拿到对应的操作，然后一条一条的执行。这样的话，一个数据变更的操作，先删除缓存，然后再去更新数据库，但是还没完成更新。此时如果一个读请求过来，没有读到缓存，那么可以先将缓存更新的请求发送到队列中，此时会在队列中积压，然后同步等待缓存更新完成。

这里有一个优化点，一个队列中，其实多个更新缓存请求串在一起是没意义的，因此可以做过滤，如果发现队列中已经有一个更新缓存的请求了，那么就不用再放个更新请求操作进去了，直接等待前面的更新操作请求完成即可。

另外，考虑到读请求可能积压时间过长，因此可以设置一个读超时时间，一旦到达这个超时时间仍然没有出队列，则直接访问数据库返回读取到的值。

缓存并发竞争

缓存并发竞争是指多客户端同时并发写一个 key，可能本来应该先到的数据后到了，导致数据错误。解决方案如下：

1. 使用Redis或Zookeeper构建分布式锁，所有针对同一个key的读写操作都必须获得锁
2. 对value增加一个时间戳，set时先判断当前value的时间戳是否早于自己的时间戳，如果早于才执行set

高可用缓存

Redis缓存宕机了，有可能造成大量请求直接打到数据库，从而造成服务不可用。解决方案：

1. 事前：构建Redis高可用集群，避免Redis全盘宕机
2. 事中：使用服务的本地ehcache缓存，Hystrix限流/降级，避免系统崩溃
3. 事后：Redis 持久化，一旦重启，自动从磁盘上加载数据，从而快速恢复缓存数据

12.2 Redis构建分布式锁

对于单机Redis，构建分布式锁依赖于setNX命令。下面是构建一个锁的命令：

SET resource_name random_value NX PX 30000

• NX参数表示key不存在的时候才会设置成功
• PX参数表示过期时间。

释放锁的时候，使用lua脚本进行CAS操作。

-- 删除锁的时候，找到 key 对应的 value，跟自己传过去的 value 做比较，如果是一样的才删除。
if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

为什么要用 random_value 随机值呢？因为如果某个客户端获取到了锁，但是阻塞了很长时间才执行完。此时可能已经自动释放锁了，因此别的客户端已经获取到了这个锁，要是你这个时候直接删除 key 的话那么其他客户端获得的锁就被删除了，所以得用随机值加上面的 lua 脚本来保证原子性的释放锁。

在分布式场景下，可以使用RedLock算法：

这个场景是假设有一个 redis cluster，有 5 个 redis master 实例。然后执行如下步骤获取一把锁：

1. 获取当前时间戳，单位是毫秒；
2. 跟上面类似，轮流尝试在每个 master 节点上创建锁，过期时间较短，一般就几十毫秒；
3. 尝试在大多数节点上建立一个锁，比如 5 个节点就要求是 3 个节点 n / 2 + 1；
4. 客户端计算建立好锁的时间，如果建立锁的时间小于超时时间，就算建立成功了；
5. 要是锁建立失败了，那么就依次之前建立过的锁删除；
6. 只要别人建立了一把分布式锁，你就得不断轮询去尝试获取锁。

12.3 Redis的线程模型

redis 内部使用文件事件处理器 file event handler，这个文件事件处理器是单线程的，所以 redis 才叫做单线程的模型。它采用 IO 多路复用机制同时监听多个 socket，将产生事件的 socket 压入内存队列中，事件分派器根据 socket 上的事件类型来选择对应的事件处理器进行处理。

12.4 Redis内部数据结构的实现

• Redis基本数据类型和使用场景

Hash

存储Hash数据时，Redis内部使用两种数据结构：ziplist和hashtable。

ziplist是一个经过特殊编码的双向链表，它的设计目标就是为了提高存储效率。ziplist可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。它能以O(1)的时间复杂度在表的两端提供push和pop操作。

实际上，ziplist充分体现了Redis对于存储效率的追求。一个普通的双向链表，链表中每一项都占用独立的一块内存，各项之间用地址指针（或引用）连接起来。这种方式会带来大量的内存碎片，而且地址指针也会占用额外的内存。而ziplist却是将表中每一项存放在前后连续的地址空间内，一个ziplist整体占用一大块内存。它是一个表（list），但其实不是一个链表（linked list）。

ziplist是一个双向链表，当Hash对象满足以下条件时，Redis会使用ziplist存储：

1. 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节
2. 哈希对象保存的键值对数量小于 512 个

当不满足以上两种情况时，Hash对象会被存储在hashtable中。

Sorted Set

存储Sorted Set时，Redis内部使用两种数据结构：zset ziplist和skiplist（跳表）。

ziplist是一个双向链表，当Sorted Set对象满足以下条件时，Redis会使用zset ziplist存储：

1. Set中元素的 member 长度小于服务器属性 server.zset_max_ziplist_value 的值（默认为 64 ）。
2. Set的大小小于服务器属性 server.zset_max_ziplist_entries 的值（默认为 128 ）。

zset ziplist插入新元素时，会根据score进行的插入排序，因此zset ziplist总是升序的。

当不满足以上条件时，Sorted Set对象会被存储在dict和skiplist中。dict是一个hash桶，用于在O(1)时间内查找集合元素。skiplist（跳表）效率和平衡树媲美（但实现比平衡树简单很多），用于O(logN)时间内根据score进行定位，通常用于ZRANGE，ZRANK等命令。

关于跳表的数据结构，请参考：https://lotabout.me/2018/skip-list/

12.5 RDB和AOF

• Redis高级特性

12.6 Redis过期策略

• Redis高级特性

12.7 Redis高可用

Redis高可用可以分为两个部分，主从架构和哨兵。

主从架构

主从架构.PNG

Redis主从架构，Master负责写请求，Slave负责读请求，然后通过Redis的主从复制实现主从一致性。

当启动一个 slave node 的时候，它会发送一个 PSYNC 命令给 master node。如果这是 slave node 初次连接到 master node，那么会触发一次 full resynchronization 全量复制。此时 master 会启动一个后台线程，开始生成一份 RDB 快照文件，同时还会将从客户端 client 新收到的所有写命令缓存在内存中。RDB 文件生成完毕后， master 会将这个 RDB 发送给 slave，slave 会先写入本地磁盘，然后再从本地磁盘加载到内存中，接着 master 会将内存中缓存的写命令发送到 slave，slave 也会同步这些数据。slave node 如果跟 master node 有网络故障，断开了连接，会自动重连，连接之后 master node 仅会复制给 slave 部分缺少的数据。

之后，master 每次接收到写命令之后，先在内部写入数据，然后异步发送给 slave node。

另外，slave 不会过期 key，只会等待 master 过期 key。如果 master 过期了一个 key，或者通过 LRU 淘汰了一个 key，那么会模拟一条 del 命令发送给 slave。

哨兵

哨兵（sentinel）是Redis集群中的一个重要组件，它的主要作用如下：

• 集群监控：负责监控 redis master 和 slave 进程是否正常工作。
• 消息通知：如果某个 redis 实例有故障，那么哨兵负责发送消息作为报警通知给管理员。
• 故障转移：如果 master node 挂掉了，会自动转移到 slave node 上。
• 配置中心：如果故障转移发生了，通知 client 客户端新的 master 地址。

故障转移时，判断一个 master node 是否宕机了，需要大部分的哨兵都同意才行，涉及到了分布式选举的问题。哨兵至少需要 3 个实例，来保证自己的健壮性。哨兵 + redis 主从的部署架构，是不保证数据零丢失的，只能保证 redis 集群的高可用性。

每次一个哨兵要做主备切换，首先需要quorum个哨兵认为master宕机了（哨兵会定时向master和slave发送心跳），然后选举出一个哨兵来做切换，此时这个选举出来的哨兵还需要得到majority个哨兵的认同，才能正式执行切换。

哨兵互相之间的发现，是通过 redis 的 pub/sub 系统实现的，每个哨兵都会往 sentinel:hello 这个 channel 里发送一个消息，这时候所有其他哨兵都可以消费到这个消息，并感知到其他的哨兵的存在。

更多关于哨兵的原理，请参考：https://github.com/doocs/advanced-java/blob/master/docs/high-concurrency/redis-sentinel.md

12.8 Redis集群和gossip协议

• https://github.com/doocs/advanced-java/blob/master/docs/high-concurrency/redis-cluster.md

12.9 Redis热点key问题

所谓热key问题就是，突然有几十万的请求去访问redis上的某个特定key。那么，这样会造成流量过于集中，达到物理网卡上限，从而导致这台redis的服务器宕机。

12.9.1 怎么发现热点key

1. 凭借业务经验，进行预估哪些是热key
其实这个方法还是挺有可行性的。比如某商品在做秒杀，那这个商品的key就可以判断出是热key。缺点很明显，并非所有业务都能预估出哪些key是热key。

2. 在客户端进行收集
这个方式就是在操作redis之前，加入一行代码进行数据统计。那么这个数据统计的方式有很多种，也可以是给外部的通讯系统发送一个通知信息。缺点就是对客户端代码造成入侵。

3. 在Proxy层做收集
有些集群架构是下面这样的，Proxy可以是Twemproxy，是统一的入口。可以在Proxy层做收集上报，这种方案对业务侵入最小，但是缺点很明显，并非所有的redis集群架构都有proxy。

redis proxy.PNG

4. 使用redis monitor命令
下面是使用用redis monitor命令的例子：

//获取10万条命令
List<String> keyList = redis.monitor(100000);
//存入到字典中，分别是key和对应的次数
AtomicLongMap<String> ATOMIC_LONG_MAP = AtomicLongMap.create(); 
//统计
for (String command : commandList) {
    ATOMIC_LONG_MAP.incrementAndGet(key);
}
//后续统计和分析热点key
statHotKey(ATOMIC_LONG_MAP);

这种方案的缺点是，高并发条件下会有造成redis 内存爆掉的隐患。

5. 使用redis hot-keys参数
redis 4.0.3提供了redis-cli的热点key发现功能，执行redis-cli时加上–hotkeys选项即可。但是该参数在执行的时候，如果key比较多，执行起来比较慢。下面使用hot-keys命令的例子：

$./redis-cli --hotkeys

# Scanning the entire keyspace to find hot keys as well as
# average sizes per key type.  You can use -i 0.1 to sleep 0.1 sec
# per 100 SCAN commands (not usually needed).

[00.00%] Hot key 'counter:000000000002' found so far with counter 87
[00.00%] Hot key 'key:000000000001' found so far with counter 254
[00.00%] Hot key 'mylist' found so far with counter 107
[00.00%] Hot key 'key:000000000000' found so far with counter 254
[45.45%] Hot key 'counter:000000000001' found so far with counter 87
[45.45%] Hot key 'key:000000000002' found so far with counter 254
[45.45%] Hot key 'myset' found so far with counter 64
[45.45%] Hot key 'counter:000000000000' found so far with counter 93

-------- summary -------

Sampled 22 keys in the keyspace!
hot key found with counter: 254    keyname: key:000000000001
hot key found with counter: 254    keyname: key:000000000000
hot key found with counter: 254    keyname: key:000000000002
hot key found with counter: 107    keyname: mylist
hot key found with counter: 93    keyname: counter:000000000000
hot key found with counter: 87    keyname: counter:000000000002
hot key found with counter: 87    keyname: counter:000000000001
hot key found with counter: 64    keyname: myset

要使用--hot-keys参数，必须将maxmemory-policy参数设置为volatile-lfu或allkeys-lfu。

Redis 4.0新增了allkey-lfu和volatile-lfu两种数据逐出策略。lru策略是淘汰最近一段时间没有用到的key，而lfu则是淘汰最近一段时间使用次数最少的数据。

6. 抓包评估
Redis客户端使用TCP协议与服务端进行交互，通信协议采用的是RESP。自己写程序监听端口，按照RESP协议规则解析数据，进行分析。缺点就是开发成本高，维护困难，有丢包可能性。

12.9.2 发现热点key后如何解决

发现热点key后，解决方案主要有两种：利用二级缓存和分散热点key。

1. 利用二级缓存
比如利用ehcache，甚至一个HashMap都可以。在你发现热key以后，把热key加载到系统的JVM中。针对这种热key请求，会直接从jvm中取，而不会走到redis层。

缺点：1. 需要额外保证Redis和服务器端热点Key的数据一致性。2. 如果对可能成为 hot key 的 key 都进行本地缓存，那么本地缓存是否会过大，从而影响应用程序本身所需的内存空间。

2. 备份热点Key
这种解决方案很简单，就是将热点key进行分散。每一次读热点key时，都加上一个随机数（随机数可以在0-集群机器数量间随机）进行读取，不存在则追加这个热点key和随机数组成的key。这样其实相当于将热点key备份了多份。下面是一个简单实现：

const M = N * 2
//生成随机数
random = GenRandom(0, M)
//构造备份新key
bakHotKey = hotKey + “_” + random
data = redis.GET(bakHotKey)
if data == NULL {
    data = GetFromDB()
    redis.SET(bakHotKey, expireTime + GenRandom(0,5))
}

缺点：由于热点key备份了多份，因此增加了保证数据一致性的复杂度。

12.10 BitMap和HyperLogLog

BitMap API如下：

• SETBIT key offset value给一个指定key的值的第offset位赋值为value。value只能为0或1。
• GETBIT key offset获取指定key的值的第offset位的值。
• bitcount key [start, end] 统计 key 上位为1的个数。

通过bitmap，我们可以用最少的内存处理以下问题：

• 统计网站活跃用户数量（将uid位置为1，然后调用bitcount返回）
• 统计用户在线状态

通过BITOP operation destkey key [key ...]命令能够实现对多个bitmap的运算操作。其中operation支持 AND 、 OR 、 NOT 、 XOR 4种操作。

而HyperLogLog目的是做基数统计，故不是集合，不会保存元数据，只记录数量而不是数值，存在一定误差。HyperLogLog API如下：

• PFADD key element [element …]给指定key添加元素
• PFCOUNT key [key …] 返回指定key的基数
• PFMERGE destkey sourcekey [sourcekey …] 合并多个HyperLogLog

redis> PFADD  databases  "Redis"  "MongoDB"  "MySQL"
(integer) 1

redis> PFCOUNT  databases
(integer) 3

redis> PFADD  databases  "Redis"    # Redis 已经存在，不必对估计数量进行更新
(integer) 0

redis> PFCOUNT  databases    # 元素估计数量没有变化
(integer) 3

redis> PFADD  databases  "PostgreSQL"    # 添加一个不存在的元素
(integer) 1

redis> PFCOUNT  databases    # 估计数量增一
4

应用场景：

• 基数不大，数据量不大就用不上，会有点大材小用浪费空间
• 有局限性，就是只能统计基数数量，而没办法去知道具体的内容是什么
• 和bitmap相比，属于两种特定统计情况，简单来说，HyperLogLog 去重比 bitmap 方便很多
• 一般可以bitmap和hyperloglog配合使用，bitmap标识哪些用户活跃，hyperloglog计数

12.11 Redis构建乐观锁

https://my.oschina.net/itommy/blog/1790641

13. 分布式相关

13.1 CAP理论

• CAP
• 2PC，3PC和TCC

13.2 全局唯一ID算法

TDDL算法

1. 在数据库中创建 sequence 表，用于记录当前已被占用的id最大值。
2. 每台客户端主机取一个id区间（比如 1000~2000, 即max_id + step）缓存在本地，并更新 sequence 表中的id最大值记录。
3. 客户端主机之间取不同的id区间，用完再取，使用乐观锁机制控制并发。

Snowflake算法

将64位ID分割为4部分：

1. 最高位不使用
2. 41位存储时间戳。需要注意的是此处的 41 位时间戳并非存储当前时间的时间戳，而是存储时间戳的差值（当前时间戳 - 起始时间戳），这里的起始时间戳一般是ID生成器开始使用的时间戳，由程序来指定。
3. 10位存储机器标志。包括5位数据标识位和5位机器标识位，这10位决定了分布式系统中最多可以部署 1 << 10 = 1024 s个节点。超过这个数量，生成的ID就有可能会冲突。
4. 12位毫秒内的序列。这 12 位计数支持每个节点每毫秒（同一台机器，同一时刻）最多生成 1 << 12 = 4096个ID。

13.3 分布式事务

• 常见分布式事务解决方案

14. 数据库

14.1 主从复制

随着系统中业务访问量的增大，如果是单机部署数据库，就会导致I/O访问频率过高。有了主从复制，增加多个数据存储节点，将负载分布在多个从节点上，降低单机磁盘I/O访问的频率，提高单个机器的I/O性能。

读写分离，简单来说就是一个主库，挂多个从库，然后我们就单单只是写主库，然后主库会自动把数据给同步到从库上去。

主从复制过程中，主库将变更写入 binlog 日志，然后主库的IO线程负责将新的变更发送给从库，从库有一个 IO 线程将主库的binglog拷贝到自己本地，写入一个 relay 中继日志中。接着从库中有一个 SQL 线程会从中继日志读取 binlog。

Mysql主从复制模式分为三种：异步模式，半同步模式和全同步模式。

• 异步模式（默认）：主库将事务 Binlog 事件写入到 Binlog 文件中，此时主库只会通知一下IO线程发送这些新的 Binlog，然后主库就会继续处理提交操作，而此时不会保证这些 Binlog 传到任何一个从库节点上。
• 半同步模式：是介于全同步复制与全异步复制之间的一种，主库只需要等待至少一个从库节点收到并且 Flush Binlog 到 Relay Log 文件即可，主库不需要等待所有从库给主库反馈。同时，这里只是一个收到的反馈，而不是已经完全完成并且提交的反馈，如此，节省了很多时间。
• 全同步模式：指当主库执行完一个事务，所有的从库都执行了该事务才返回给客户端。因为需要等待所有从库执行完该事务才能返回，所以全同步复制的性能必然会收到严重的影响。

binlog记录格式也分为三种：基于SQL语句的复制（statement-based replication，SBR），基于行的复制（row-based replication，RBR)，混合模式复制（mixed-based replication,MBR)。对应的binlog文件的格式也有三种：STATEMENT,ROW,MIXED。

14.2 分库分表

水平拆分是把一个表的数据给弄到多个库的多个表里去，但是每个库的表结构都一样，只不过每个库表放的数据是不同的，所有库表的数据加起来就是全部数据。水平拆分的意义，就是将数据均匀放更多的库里，然后用多个库来扛更高的并发，还有就是用多个库的存储容量来进行扩容。

垂直拆分的意思，就是把一个有很多字段的表给拆分成多个表，或者是多个库上去。每个库表的结构都不一样，每个库表都包含部分字段。一般来说，会将较少的访问频率很高的字段放到一个表里去，然后将较多的访问频率很低的字段放到另外一个表里去。因为数据库是有缓存的，你访问频率高的行字段越少，就可以在缓存里缓存更多的行，性能就越好。这个一般在表层面做的较多一些。

分库分表方案

• https://www.shiyanlou.com/library/advanced-java/docs/high-concurrency/database-shard-dynamic-expand
• https://tech.meituan.com/2016/11/18/dianping-order-db-sharding.html

平滑迁移

采用双倍扩容策略。扩容前每个节点的数据，有一半要迁移至一个新增节点中，对应关系比较简单，并且无需停止应用服务器。具体操作如下(假设已有 2 个节点 A/B，要双倍扩容至 A/A2/B/B2 这 4 个节点)：

• 新增两个数据库 A2/B2 作为从库，设置主从同步关系为：A=>A2、B=>B2，直至主从数据同步完毕(早期数据可手工同步)
• 调整分片规则并使之生效：
  原 ID%2=0 => A 改为 ID%4=0 => A, ID%4=2 => A2
  原 ID%2=1 => B 改为 ID%4=1 => B, ID%4=3 => B2
• 解除数据库实例的主从同步关系，并使之生效
• 此时，四个节点的数据都已完整，只是有冗余(多存了和自己配对的节点的那部分数据)，择机清除即可(过后随时进行，不影响业务)

更多平滑扩容的内容，请参考：

• https://my.oschina.net/u/1859679/blog/1577049
• https://maxwell.gitbook.io/way-to-architect/shu-ju-ku/mysql/mysqlzhong-de-sharding/fen-ku-fen-biao-hou-de-ping-hua-kuo-rong

14.3 最左前缀匹配原则

mysql建立多列索引（联合索引）有最左前缀的原则，即最左优先，即：

如果有一个2列的索引(col1,col2),则已经对(col1)、(col1,col2)上建立了索引；
如果有一个3列索引(col1,col2,col3)，则已经对(col1)、(col1,col2)、(col1,col2,col3)上建立了索引；

下面是2个例子：

1、b+树的数据项是复合的数据结构，比如(name,age,sex)的时候，b+树是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据；但当(20,F)这样的没有name的数据来的时候，b+树就不知道第一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。

2、比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了， 这个是非常重要的性质，即索引的最左匹配特性。（这种情况无法用到联合索引）

问题1：假如要查 A in () AND B in (), 怎么建索引?

• 只给选择性高的一列建索引，这里因为两个都是范围查询所以另一个是走不到索引的。（这里答的不好，其实也可以建联合索引然后用 （A,B) in ((1,2),(3,4)) 的方式去查）

问题2： 查 A in () AND B in () 时, MySQL 是怎么利用索引的?

• 先走一个非聚簇索引，查询出行数据后再用另一列回表做筛选

14.4 分页

limit 的用法是 limit [offset], [rows]，其中 offset 表示偏移值， rows 表示需要返回的数据行。mysql 的 limit 给分页带来了极大的方便，但数据偏移量一大，limit 的性能就急剧下降。

如果能够确定上一次分页的最大id，那么可以这样优化：

select * from table_name where (id >= 10000) limit 10

否则，可以通过先select主键再子查询的方式来进行：

SQL代码1：平均用时6.6秒 SELECT * FROM `cdb_posts` ORDER BY pid LIMIT 1000000 , 30

SQL代码2：平均用时0.6秒 SELECT * FROM `cdb_posts` WHERE pid >= (SELECT pid FROM  
`cdb_posts` ORDER BY pid LIMIT 1000000 , 1) LIMIT 30

因为要取出所有字段内容，第一种需要跨越大量数据块并取出，而第二种基本通过直接根据索引字段定位后，才取出相应内容，效率自然大大提升。对limit的优化，不是直接使用limit，而是首先获取到offset的id，然后直接使用limit size来获取数据。（这种优化在聚簇索引下可能无效）

14.5 索引

Mysql支持的索引包括B+树索引，哈希索引，全文索引等等。B+树是一个平衡的多叉树。B+树从根节点到叶子节点的搜索效率基本相当，不会出现大幅波动。哈希索引采用一定的哈希算法，把键值换成新的哈希值，检索时不需要类似B+树那样从根节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置。

哈希索引的缺点：

1. 只支持等值查询，不支持范围查询
2. 不支持按照索引值排序
3. 不支持部分索引查询（哈希索引始终是使用索引列的全部内容来计算哈希值）

更多关于索引的内容，请参考：https://www.cnblogs.com/duanxz/p/3799045.html

为什么数据库使用B+树作为索引实现？

1. B+树的磁盘读写代价更低。由于B树的每一个节点都保存了数据，而B+树所有的数据都保存在叶子节点，因此每一次IO B+树读到的关键字信息就更多，因此IO次数相对更少。

2. B+树的范围查询效率更高。由于B树的所有信息分散在整颗树中，因此范围查询需要一遍中序遍历。而B+树的叶子节点保存了所有的数据，并使用链表连接，因此范围查询更加迅速。

更多关于数控索引数据结构的内容，请参考：https://blog.csdn.net/xlgen157387/article/details/79450295

14.6 Mysql事务，锁和MVCC原理

• Mysql事务，锁和MVCC原理

15. RPC框架的设计

• https://zhuanlan.zhihu.com/p/60287858?utm_source=wechat_session&utm_medium=social&utm_oi=61516120326144

16. 大数据查询问题

• https://www.cnblogs.com/RainLa/p/8623840.html
• https://blog.csdn.net/FX677588/article/details/72471357

17. ZooKeeper

• ZooKeeper基础
• ZooKeeper高级特性
• ZooKeeper选举流程

18. Hystrix

• Hystrix基础
• Hystrix高级特性

19. 计算机网络

• HTTP协议
• 计算机网络

20. 应用类问题

• 应用类问题
• 高并发秒杀系统设计
• RPC框架