1.分布式缓存
1.1高并发下的分布式缓存
我们先从最开始的来说，我们现在一般都是B/S架构，一般都是中间挂一个服务器，后面有一个数据库。如下图：
如果客户端的访问量很大的话，那对于后端的服务来说就有一定压力了，压力主要有两个环节；一个环节是关于服务器，一个环节是我们数据库；当我们的并发量增加时，最先达到瓶颈的是我们数据库，这就会导致客户端的访问速度，访问效率降低，这时该如何解决呢？这个时候我们就需要加缓存层；
我们可以把经常访问的数据 称之为热点数据，存放在缓存中，当我们去数据库拿数据的时候，先去缓存中找一下，找到了直接返回，没找到再去数据库中查找；这时可以阻挡一部分接触数据库的请求
如果热点数据很大，一台redis缓存存放不了，这时我们可以采用多台redis机器，这就牵扯到了redis集群，这就是我们说的分布式缓存；
1.2redis集群模式
1.2.1 主从备份模式
有一台master，它的下面会挂一群slave；
如果客户端去读数据，是找的这些slave；如果客户端去写数据，找的是master，写完之后master会将数据同步给slave
思考一个问题，如果使用了这种集群模式，对于上面说到的问题可以解决吗？搭建这样的集群模式最终所能存储的数据是由单台机器的容量所决定的。
哨兵模式：哨兵是当主节点挂了之后，需要监控将从切换为主，其他的从节点跟随新的主节点。
所以搭建这样的集群模式是解决不了海量的热点数据存储的一个问题；所以我们有了下面这种模式的集群；
1.2.2切片模式的集群
我们可以把海量的热点数据进行一个切片，切成一块一块的，每一块存放在一台redis上；
cluster模式:分治，分片的，每一个节点存放的是一部分数据，单个节点挂掉会损失一部分数据。解决的是容量，压力问题。
那么我们有什么办法将这些数据均匀的分布在这三台机器上 ？有一个切片规则，可以计算下数据key的hash值； 比如上面的三台机器，我们可以hash(key) % 3 = [0,1,2]它的计算结果在 0，1，2之间，这样就可以把大量的热点数据均匀的存放在三台redis机器上；
但是这样的切片规则是有问题的，什么问题？不利于集群的扩展， 当我们增加一台redis时，这时我们切片规则需要改变并且原本三台上的部分数据需要根据切片规则迁移到新增加的redis机器上
我们来看一下一个优秀的切片规则
1.2.2.1一致性Hash算法
假设我们现在有一个环，这个环叫做Hash环，我们准备三台redis机器，Hash环的作用是决定哪些数据存放在哪个redis机器上。
每一台redis机器都有他的Ip和编号，我们通过给他的IP和编号做Hash运算，计算结果作为在这个环上的位置。
接下来我们对每一条数据也进行这样的计算，每一条数据都会落在这个环上，接下来我们把这些数据在环上沿着顺时针去找，首先找到哪台服务器就放在哪个机器上面
一致性Hash算法的好处是对集群的扩展非常有利，假设我们新增了一台redis4机器，那么只需要将图中redis2和redis4之间线段里的数据（之前存放在redis3）迁移到redis4即可，只需要redis3和redis4发生数据迁移就行，其他的机器不需要动；但这个算法会有一个问题，数据倾斜问题，当redis机器较少或环长度过大时，机器间可能会离的过近，此时我们看下图：
此时可以看出只有少部分数据存放在redis2中，大量数据都存放在redis1中。为了解决这个问题，我们提出了虚拟节点的概念；
1.2.2.2 虚拟节点
我们可以把每一台redis服务虚拟成多个点（redisA1，redisA2。。。），再把虚拟出来的点分布在Hash环上，数据落在虚拟的点但实际落在它对应真实的服务器上，如下图：
1.3缓存击穿，穿透，雪蹦
1.3.1缓存穿透
假设我们现在以id=-1的请求去请求获取数据，这时数据库里没有，缓存里更没有；当有大量不存在的请求过来时，这些请求在缓存中查找不到，便会去数据库中查找，这时就有可能把数据库压垮！！
如何解决呢？？
我们可以在缓存与数据库之间搞个过滤器，假设我们每次都是通过ID去查询的，过滤器中保存数据库所有的主键ID；当请求过来之后，首先判断过滤器中是否存在这个ID，不存在的话直接过滤掉请求；
但是上面的方案会存在一个问题，当我们数据库数据越来越大时，过滤器所占用的内存也会随之增大，过滤效率就会降低，客户端请求的链路时间也会越长，客户体验会不好；这时就引出了一个算法-布隆算法
1.3.1.1布隆算法
我们可以使用布隆算法来降低过滤器对内存的占用；布隆算法主要通过错误率来换取空间的占用；
算法的原理
它有一个二进制码数组，假设他的长度是10；此时传入ID=100，它会根据Hash函数得到它在二进制数组中的位置，通过这个hash函数计算的结果集会在二进制数组长度之间。
此时第二位上的1代表id=100的这个数据存在；
那么错误率是怎么出现的呢？
假设id=1000的数据，通过hash函数计算得到位置也是二进制数组的第二位上，此时二进制数组的第二位的1就代表了ID=100和ID=1000这两条数据存在。
以我们上面举的这个例子，我们发现错误率很高，那这个错误率是怎么产生的呢？？是由于我们Hash碰撞的概率太高了，Hash碰撞的概率与我们的二进制数组长度有关系，越长Hash函数计算的结果范围越大越不容易碰撞。还有一种减少Hash碰撞概率的办法，那就是增加多个不同的Hash函数进行运算，比如上面ID=100的数据传入三个Hash函数，最后得出的位置是0，3，7；那也就是说这二进制数组0，3，7三个位置都是1的情况下才代表了ID=100的这条数据
以上面长度10的二进制数组为例，通过一个Hash函数落到相同位置的概率是1/10，那通过三个Hash函数落到相同位置的概率就是1/10 * 1/10 * 1/10 = 1/1000，Hash碰撞的概率极大的降低了。
1.3.1.2 布隆算法的题
假设有两个文件，每个文件里100亿个url，最高效率的找出这两个文件的交集，并给出精准算法和模糊算法。
精准算法：
定义一个共用的Hash函数算法规则将每个文件可以分成1000个小文件，那么相同的url经过相同的Hash函数之后一定会落在同一个小文件中，最后只要挨个比较两边的小文件里面的url是否相等；
缺点：要经过两次的磁盘IO，第一次遍历每个大文件进行拆分，第二次把对应的小文件进行遍历；
模糊算法-布隆算法
跟上面逻辑一样，定义一个二进制数组，对比每个文件里的url经过hash函数之后是否落在同一位置，是就判断为相同；
只需要一次磁盘IO；
1.3.2缓存雪蹦
redis集群集体宕机， 那所有去redis里请求数据的都会打到数据库上，那一刻数据库可能就撑不住，这种一般很低概率发生；一般都是缓存里的数据都设置了同一有效时间，此时有效期一到redis会把他们删除，此时请求这些数据都会请求到数据库，数据库可能也会宕机；这种情况让redis里的数据陆续失效就可以了而不是同时失效。
2.分布式锁
2.1锁是什么？
2.1.1单机锁
假设有两个线程，他们都需要对堆中一个对象进行修改，同时修改可能导致数据错误问题，此时我们可以用一个第三方的锁标示，让一个线程获取锁后再进行数据的操作，在锁未释放的时候其他线程要先获取锁才能操作数据。
2.1.2分布式锁
当有两台数据时，如果他们访问的数据都在各自的堆里面，其实是不需要分布式锁的；在高并发场景下，要访问数据往往在第三方服务第三方机器里，此时线程不能将各自堆里的对象作为锁标识，因为各自堆里的对象都是独立的，此时我们就需要引入第三方的锁标识，这个锁就叫做分布式锁；
2.1.3有了分布式锁之后还需要JVM锁吗？
在分布式锁的情况下，能保证多机多线程访问资源的一致性，这个时候还需要单个机器里的JVM锁吗？
答案是需要的！ 那为什么单机内部还需要一把锁？当没有JVM锁，此时两个机器四个线程去争抢一把分布式锁，此时是四个线程一起争抢资源，倘若两个线程先在单机的JVM内部争抢一把锁，抢到了再去抢占分布式锁，此时便只有两个线程去抢占一把分布式锁，减少了网络的IO，起到了过滤的作用
所以分布式锁肯定是要比JVM锁慢的，那为什么还需要使用分布式锁呢，它主要解决了并发量的问题。
2.2两大类分布式锁
2.2.1类cas自旋式分布式锁-redis，mysql
2.2.1.1 单机锁 cas所存在问题
-
ABA问题。因为CAS需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A 就会变成1A-2B－3A。
从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。 -
循环时间长开销大。自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。如果JVM能支持处理器提供的pause指令那么效率会有一定的提升，pause指令有两个作用，第一它可以延迟流水线执行指令（de-pipeline）,使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突（memory order violation）而引起CPU流水线被清空（CPU pipeline flush），从而提高CPU的执行效率。
-
只能保证一个共享变量的原子操作。当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。
我们来了解下锁升级过程：
当我们使用JVM锁时，它会产生自旋然后再系统调用 。当一个线程没有抢到锁，当别的线程释放锁之后，这个线程后续如何进行？答案是当线程处于自旋时，它就一直处于运行状态，此时该线程会等待cpu处理，当等待时间过长时，它会让出cpu，自己变为阻塞状态。那后续如何唤醒？是自己醒还是被唤醒，当别的线程释放了锁时，内核会将这个线程切换为运行太态，等着内核调度的时候，调度到这个线程时就可以运行了。
2.1.1.2redis分布式锁
redis几个特征：单线程，对业务的处理是串行的。
当C1，C2两个线程去redis抢占锁时，各自调用本地方法setnx+timeout，key存在则表示抢锁失败，key不存在则抢占锁。这时会出现几个问题：
一：如果C1在抢占锁时运行一段时间挂了，此时还没有释放锁，这时C2的整个业务便处于死锁状态，所以才有会一个加入锁过期时间，即便挂了锁也会到期自动释放。
二:当C1抢到锁之后，C2会通过IO做自旋操作，不断去发送setnx指令询问是否释放掉锁，释放则抢占锁执行接下来逻辑。如果有很多客户端发送请求去抢占锁，但每次只有一个能抢到锁且一直自旋发送请求，很多都是无效请求。 这种的解决方案是开发发布订阅，阻塞队列加超时检测。
三：当C1抢到锁之后，由于某些原因导致C1的执行时间超过了过期时间，此时C2遍抢占到锁，可以加一个监控线程，这个线程会监控抢占到这把锁的线程，如果过期时间到了该线程还没有执行完，监控线程会增加这把锁的过期时间。
2.1.1.3redlock
redlock使用多机的方式，redlock不是redis实现的，是客户端实现的算法。如何实现呢？
现在有C1，C2，C3几个线程，再准备A1，A2，A3这几台redis机器，然后每一个线程都会和这几台redis机器有IO的连接 。假设C1线程首先到达这几台redis，这几台redis会给这一个线程返回，也就是说这个线程的锁是这几个节点 返回的。那如果是C1先到达A1，A2但C2先到达A3，此时这几个redis节点还会给C1返回锁吗？答案是会的，只要过半就可以获得锁， 这就可以解决redis单点故障的问题，即使挂了，只要过半就给你返回锁。
此时会有个问题，当C1抢到了A1，C2抢到了A2，C3抢到了A3，此时任何一个线程都没有过半，此时就会进行随机重试，有可能需要抢好几轮才能过半抢到。 这个算法也会有上面出现的几个问题，挂了，运行时间超过过期时间，且需要解决这几个问题还会比一般的锁复杂。
2.2.2event事件通知锁的变化-zk，etcd
相比于自旋式的锁，哪种性能更好点呢？
在单机环境下是自旋式的好点，cas自旋时cpu指令级上的，它并不产生系统调用；但event事件通知是需要通过IO的，通过IO就会产生系统调用，当抢锁方过多时，对于持锁方它需要发送多次的网络IO。
2.2.2.1 zookeeper
zk集群有一个leader和多个salve，主从模型 ，当需要查询的时候这个时候可以访问任何一个从节点，但是 对于增删改来说，leader会做一个两阶段提交
什么是两阶段提交
当需要做增删改操作时，leader会 通知从节点把操作写到自己的日志里，返回一个确认OK ，当leader收到各个节点返回的确认就位的信息，过半通过后leader告诉各个节点把操作日志进行提交，提交成功后在告诉leader完成提交，之后完成。
leader挂了之后怎么办？
这时各个从节点会进行一个选举过程，这个过程主要是各个节点之间互相发消息并带着自己数据的Id以及自己的serviceId，优先看谁的数据最新，其次看谁的 serviceId更大，谁最大便会把这个节点标识为自己的leader 。
zk里有一个session和watch的概念，这个session在每一个节点中都会保存起来，当客户端链接任何一个节点时，该节点突然挂掉时，客户端可以 通过session连接其他的节点而不受挂掉的影响；
对于客户端，客户端可以在zk上建立一个持久化的节点，也就是说不管客户端连没连接该节点数据一直都会在；还有一种是临时节点，这种节点会绑定session，在确定还没有断开连接时，该节点数据会在，当断开链接后session开始计时，当session过期后会删除该节点数据。
watch监控回调
假设你在zk上创建了一个节点，这个节点是一把锁，当该节点锁被操作时比如删除修改，这时zk会callback给客户端执行回调函数，
zk主从模型的好处
假设现在几个线程同时进行加锁操作，这几个线程肯定需要经过leader，此时leader肯定是按照消息的顺序去创建节点锁， 假设一个线程已经创建了节点锁，那其他线程来创建时发现该锁已被创建 ，则会直接返回给其他线程创建失败，此时zk会给该节点设置一个观察点当该锁被操作时zk就会给客户端去执行他的回调函数，可以在里面继续抢锁。
