Java技能图谱

Java

多线程、JUC

happens-before原则

程序顺序规则：一个线程中的某个操作happens-before于后续的操作（如果调转前后的操作后不会改变程序结构，那么这写操作仍可被指令重排）
监视器锁规则：解锁操作前的操作happens-before于之后的上锁操作（及其上锁后的操作）（一般认为的synchronized锁范围内变量的可见性是通过这条规则实现的）
volatile变量规则：volatile变量的写操作happens-before于后续对这个变量的读操作（即保证了volatile关键字修饰变量的可见性）
传递性：A happens-before B，B happens-before C ，那么A happens-before C
start()规则：执行Thread.start()前的操作happends-before 于start()启动的线程中执行的操作（即被启动的线程中可以看到启动前的操作）
join()规则：A线程中执行B.join()，那么B线程中的操作happens-before于join()返回后的操作
程序中断规则：对线程interrupt()方法的调用happens-before后续被中断线程中的检测操作
finalize规则：对象的初始化操作happens-before finalize中的操作

volatile的实现原理

volatile可以实现内存的可见性和防止指令重排序。

通过内存屏障技术实现的。

为了实现volatile的内存语义，编译器在生成字节码时，会在指令序列中插入内存屏障指令，内存屏障效果有：

禁止volatile 修饰变量指令的重排序
写入数据强制刷新到主存
读取数据强制从主存读取

锁

sychronized原理与对象锁

sychronized能实现有序性和可见性，但不能防止指令重排（所以单例模式中即使使用了双重锁检查，也需要使用volatile关键词（new 操作分三步，如果指令重排了可能会先把对象指向空的内存区域，导致其他线程使用异常））

https://juejin.im/post/5ae6dc04f265da0ba351d3ff

锁状态：锁可以升级但不能降级
- 无锁状态
- 偏向锁状态：记录第一个获得锁对象的id，如果之后该线程尝试获得锁，就直接放行；如果其他线程尝试获取锁，则判断对象头中记录（持有锁）的线程是否存活，如果不存活则设置为无锁状态，如果存活则判断线程中的锁记录决定撤销锁/偏向到当前线程/升级锁状态
- 轻量级锁状态：线程通过CAS将锁对象中的Markword替换成当前对象头中MarkWord，替换成功则执行同步块，如果替换失败，说明存在锁竞争，则自旋，自旋获取仍失败时，修改标记位为重量级锁；执行完同步块需要释放锁的线程同样适用CAS修改Markword，此时发现锁被升级，需要释放锁并唤醒其他等待锁的线程
- 重量级锁状态：在代码块前后增加monitorenter和monitorexit

AQS

https://juejin.im/post/5aeb07ab6fb9a07ac36350c8

公平锁与非公平锁的差别是公平锁在请求锁时判断AQS中当前节点是否有前驱节点，如果有，说明有更早的线程在等待锁

ReentrantLock

https://juejin.im/post/5aeb0a8b518825673a2066f0

ReentrantReadWriteLock

https://juejin.im/post/5aeb0e016fb9a07ab7740d90

读锁是共享锁，写锁是独占锁
读写锁个数保存方式：读锁和写锁保存在AQS的同一个status字段中，读锁个数保存在高16位，写锁保存在低16位

StampedLock

包含三个概念：写锁、乐观读、读锁。其中读锁和写锁等同于ReentrantReadWriteLock，乐观读相当于数据库中的乐观锁，在读完后判断版本号（stamp）是否过期，如果过期了，就升级为读锁。在多读少写的场景下，性能更胜于ReentrantReadWriteLock。该锁的非可中断方法对中断的响应有bug，会导致CPU100%，如果有响应中断的需求，需要使用可响应中断的方式获取锁。

多线程面试题总结

http://www.cnblogs.com/xrq730/p/5060921.html

线程池

如果当前运行的线程少于corePoolSize，则会创建新的线程来执行新的任务；
如果运行的线程个数等于或者大于corePoolSize，则会将提交的任务存放到阻塞队列workQueue中；
如果当前workQueue队列已满的话，则会创建新的线程来执行任务；
如果线程个数已经超过了maximumPoolSize，则会使用饱和策略RejectedExecutionHandler来进行处理。

线程池拒绝策略

直接丢弃任务
丢弃队列中最老的任务
抛出异常
由调用线程同步执行

线程数

学术论

计算密集型：CPU数+1
非计算密集型：CPU数*(1+IO时间/CPU时间)

经验论

超时时间：TP90+平均值即允许一次重试
线程数：目标QPS*RT

工具类

CyclicBarrier

CountDownLatch

集合

普通集合

ArrayList

并发环境下出问题的原因：add和remove等方式使用i++或i–方式移动数组指针，由于其为非原子操作，导致数据出错

HashMap

死循环原因：在多线程环境下resize导致形成环形链表，get操作时将死循环
HashMap扩容每次都是按原大小两倍扩容的原因：https://segmentfault.com/q/1010000020673403/a-1020000020676787
1. 寻找某个key所在桶时，原本通过hash%(length-1)的操作，可以简化为hash&(length-1)，按位与操作效率远高于模操作
2. 在rehash过程中，oldTable[i]中的元素只可能分配在newTable[i]或newTable[i+oldCap]，而且只有oldTable[i]中的元素有可能分配到这两个位置。如果不按两倍扩容，则每个元素都需要rehash且随机插入到新的位置中。

JUC中集合

ConcurrentHashMap

put
- 首先对于每一个放入的值，首先利用spread方法对key的hashcode进行一次hash计算，由此来确定这个值在 table中的位置；
- 如果当前table数组还未初始化，先将table数组进行初始化操作；
- 如果这个位置是null的，那么使用CAS操作直接放入；
- 如果这个位置存在结点，说明发生了hash碰撞，首先判断这个节点的类型。如果该节点fh==MOVED(代表forwardingNode,数组正在进行扩容)的话，说明正在进行扩容；
- 如果是链表节点（fh>0）,则得到的结点就是hash值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到key相同的节点，则只需要覆盖该结点的value值即可。否则依次向后遍历，直到链表尾插入这个结点；
- 如果这个节点的类型是TreeBin的话，直接调用红黑树的插入方法进行插入新的节点；
- 插入完节点之后再次检查链表长度，如果长度大于8，就把这个链表转换成红黑树；
- 对当前容量大小进行检查，如果超过了临界值（实际大小*加载因子）就需要扩容。
get
- 先获取hash值，找到对应的节点
- 通过节点的hash值判断当前是链表还是树，当节点的hash小于0时表示为树节点
- 通过对应的数据结构进行查找

CopyOnWriteList

跟读写锁比的优点：读操作完全无锁
缺点：数据无法立即可见；占用双倍内存

ThreadLocal

内存泄漏问题：因为ThreadLocalMap中的key是弱引用而value不是，当map中的key被gc时，value无法被访问到，但是通过可达性分析却能关联到value，导致内存泄漏
解决方案，ThreadLocal在get，set，remove时均会进行清理

ArrayBlockingQueue与LinkedBlockingQueue的差别

ArrayBlockingQueue只用了一个锁，而LinkedBlockingQueue将添加与移除的锁分开，提高了吞吐
LinkedBlockingQueue可以是无界队列，但是ArrayBlockingQueue必须有界

JVM

GC

内存划分

程序计数器
Java堆
虚拟机栈：执行方法时，创建一个『栈帧』，主要用来存放方法中的局部变量，线程隔离
本地方法栈：同虚拟机栈，差别在于虚拟机栈服务对象是Java方法，而本地方法栈服务的是native方法。
方法区（也称永久代，在Java8中取消了这个分区，其中的内容进入了Java堆，称为metadata）
- 类信息、类变量、方法信息、字段信息
- 运行时常量池
  - 符号应用
    - 方法名称
    - 字段名称
    - 类全限定名等
  - 字面量
    - 字符串
    - 常量
    - 基本类型

GCROOT

虚拟机栈中的对象
本地方法栈中的对象
方法区中的静态属性引用的对象
方法区中的常量引用的对象
synchronize持有的对象

GC算法

标记—清理
标记—复制
标记—整理
分代收集算法

对象什么时候进入老年代

大对象，在分配时可直接进入老年代，或年轻代可用内存不足时，通过担保机制进入老年代
年龄达到阈值（默认15）
Survivor空间中相同年龄的所有对象大小的总和大于Survivor空间的一半，大于这些年龄的对象可以进入老年代

三色标记法

https://juejin.im/post/5e5283abf265da573d61a311

类加载

过程

装载：查找和导入Class文件
链接
1. 校验：校验Class文件的合法性
2. 准备：给类的静态变量分配空间
3. 解析：将符号引用转成直接引用
初始化：对类的静态变量、静态代码块进行初始化执行操作

类加载器

BootstrapClassloader
ExtensionClassLoader
AppClassLoader

双亲委托加载机制：类加载器遇到一个加载需求时，会将其委托给父加载器进行加载，如果父加载器没有加载，再由当前类加载器进行加载。方便在加载一些基础类如Object类时，不同子类加载器均加载了该类而导致各种问题（不同类加载器加载了同一个class，也视为不同类型）

垃圾收集器

CMS

过程：

初始标记(STW)：可达性分析，标记根节点直接关联的对象
并发标记：从上个阶段对象出发，并发标记整个堆对象，参考三色标记法
重新标记(STW)：并发标记阶段有一些对象会修改引用关系，例如出现对象消失，需要通过增量更新方式，将删除引用记录的操作记录下来，在该步重新扫描
并发清理：将标记为垃圾的内存区域进行清除，因为只清除垃圾对象，所以是可以与用户线程并行执行

CMS缺点：

由于多个步骤与用户线程并行，所以在CPU核数较少的机器上，还是会对用户线程有明显的性能影响
无法处理浮动垃圾，所以无法在内存完全使用完才进行垃圾回收，必须预留部分内存。
前面提到CMS是标记-清除算法，所以容易造成内存碎片，在分配大内存时可能遇到有足够剩余内存但没有足够连续内存区域而导致提前FullGC的情况。CMS提供了在没有连续内存时开启内存整理的开关，但是由于需要移动内存，所以在CMS上这个步骤必须STW。

G1

G1将堆分为固定大小的region（1-32M），每个region可以被标记为年轻代或老年代，GC时以region为单位进行处理
同一时刻只有一个region的内存处于可分配，各个线程申请自己的buffer进行内存分配，使用完成后通过CAS继续申请，但这种方式会导致内存碎片。
每个region会有一个remember set，用来记录该region引用的外部对象，避免gc时扫描其他region的所有对象。在修改引用指针时，通过写屏障将该操作进行拦截，按需写入remember set

当使用大内存服务器时建议使用该回收器，通过-XX:MaxGCPauseMillis可以设置每次GC停顿的最长时间，来防止需要回收大量垃圾时STW太长导致业务异常

初始标记(STW)：可达性分析，标记根节点直接关联的对象
并发标记：从上个阶段对象出发，并发标记整个堆对象，参考三色标记法
最终标记(STW)：通过原始快照处理少量的并发标记阶段变化的引用关系
筛选回收(STW)：根据设定的停顿时长，选择收益最大的一个或多个region进行回收（因为回收过程需要移动存活的对象，所以这一步是需要STW）

Shenandoah

过程：

初始标记(STW)
并发标记
最终标记(STW)：SATB
并发清理：清理一个存活对象都没有的region
并发回收：Shenandoah并发整理通过转发指针来实现，在每个对象上标记其需要转发的位置，在没有重分配时，转发指针指向自身，当进行重分配时，转发指针指向重分配后的地址。转发指针需要使用读前屏障来实现，所以会影响GC时的吞吐，导致GC时长变长。
引用更新

ZGC

https://juejin.im/entry/5b86a276f265da435c4402d4

JDK11引入的新垃圾收集器，可以回收超大堆（达到数T）并保证10ms以内的停顿。

与标记对象的传统算法相比，ZGC在指针上做标记，在访问指针时加入Load Barrier（读屏障），比如当对象正被GC移动，指针上的颜色就会不对，这个屏障就会先把指针更新为有效地址再返回，也就是，永远只有单个对象读取时有概率被减速，而不存在为了保持应用与GC一致而粗暴整体的Stop The World。

ZGC只有非常短暂的STW，例如根节点扫描时，但是根节点的数量是有限的，不会随着堆的大小而变化。
跟G1一样把堆分为了不同region，但是可以动态决定region大小（可以是N*2M），能更好处理大对象
通过染色指针来实现并发整理算法，通过占用指针中的4个bit来标记当前引用对象是否处于重分配状态，当读屏障拦截到染色指针时，会进行自愈过程，即查询记录并将指针指向新的地址，所以只会影响重分配内存后的第一次访问。并且由于染色指针的映射关系不记录在对象本身，所以原内存可以立刻被用来使用。

过程：

初始标记(STW)
并发标记
最终标记(STW)：SATB
并发重分配：把需要重分配的对象复制到新的region上，再维护一张转发表，将原指针染色
并发重映射：修改重分配的旧指针映射，但是指针在被访问时会自愈，所以这一步会在下一次gc并发标记阶段同步进行

CMS 与 G1 优劣对比

G1优势：可以设置GC停顿时间；通过标记-整理/复制算法实现，没有内存碎片；

CMS优势：只需要维护老年代到年轻代的Remember Set，但G1每个region无论是什么代都需要维护一份Remember Set，内存占用更高；都使用了读后屏障维护Remember Set，但是CMS的RSet更轻量级，性能消耗更小；G1通过原始快照方式来处理并发标记时的指针变化问题，CMS使用增量标记方式，性能消耗更小。

NIO

https://segmentfault.com/a/1190000006824196?utm_source=tuicool&utm_medium=referral

https://zhuanlan.zhihu.com/p/23488863

框架

Spring

IOC

IOC容器启动过程——AbstractApplicationContext.refresh()

https://javadoop.com/post/spring-ioc

prepareRefresh() 准备工作，设置启动状态，处理配置文件占位符等
obtainFreshBeanFactory() 将需要的Bean解析成BeanDefinition并注册到BeanFactory中

refreshBeanFactory 刷新BeanFactory
- 销毁旧的BeanFactory
- 创建一个DefaultListableBeanFactory，applicationContext持有该BeanFactory来实现后续的操作。
- 设置是否允许Bean覆盖和循环引用
- 加载Bean定义（BeanDefinition）
  - 创建XmlBeanDefinitionReader，用来读取配置XML文件
  - 解析XML文件
  - 解析标签，此处只整理了bean标签
    - beanName默认使用id，如果id不存在则使用name中的第一个，如果name也没有设置，则用类名+#0
    - 创建BeanDefinition
    - 将bean标签中的属性赋值到BeanDefinition中
    - 注册BeanDefinition
      - 注册
        
        通过beanName查找是否已经注册过
        
        如果注册过，判断是否允许覆盖，如果不允许，则抛出异常，允许则直接覆盖
        
        没有注册，则维护beanName和bean关联的map
      - 别名注册：维护别名与beanName的map，通过别名获取时，通过此map快速找到beanName，然后再查找对应bean
返回BeanFactory

prepareBeanFactory(beanFactory) 准备BeanFactory

设置类加载器
设置默认BeanExpressionResolver
添加ApplicationContextAwareProcessor，此processor很常用，主要用来获取applicationContext
设置几个在自动注入时先忽略的几个接口
添加ApplicationListenerDetector，这个processor用来在初始化ApplicationListener的子类时，将其添加到监听列表中
手动注册一些bean

postProcessBeanFactory(beanFactory) 在注册了所有Bean之后，PostBeanProcessor注册前预留的拓展点（模板方法）

AnnotationConfigServletWebServerApplicationContext（SpringBoot默认web环境时使用）在此处去扫描basePackages包下的bean并注册

invokeBeanFactoryPostProcessors(beanFactory) 调用所有的BeanFactoryPostProcessors.postProcessBeanFactory
registerBeanPostProcessors(beanFactory) 注册ProcessBeanProcessor
initMessageSource() 处理国际化资源
initApplicationEventMulticaster() 初始化事件广播
onRefresh() 初始化bean之前的预留的拓展点（模板方法）
registerListeners() 检查和注册事件监听器
finishBeanFactoryInitialization(beanFactory) 初始化所有的非懒加载单例

合并父bean中的配置
如果是FactoryBean，在beanName前增加&
getBean(String beanName)
- 处理别名，如果传入的是别名，则获取其真实的beanName
- 判断bean是否已存在，如果存在，则直接返回（如果是FactoryBean，就返回其创建的bean）
- 初始化当前bean依赖（depend-on）的bean，递归调用getBean方法
- createBean()
  - 检查需要创建的bean的Class已经被加载
  - 准备方法覆盖（lookup-method和replace-method）
  - 执行InstantiationAwareBeanPostProcessor#postProcessBeforeInstantiation，给某些BeanPostProcessors执行的机会来返回bean的代理，如AOP(并非所有AOP均在此处实现)
  - doCreateBean()
    - 创建实例（createBeanInstance）
      - 检查类的访问权限
      - 判断构造参数类型，调用对应的构造参数
        
        如果没有使用方法覆盖，则直接通过反射调用构造参数
        
        如果进行了方法覆盖，则使用CGLIB动态生成子类来实现方法覆盖
      - 返回bean的包装类型BeanWrapper
    - Bean的装配，因为上一步只创建了实例，其中的属性没有赋值（populateBean）
      - 调用InstantiationAwareBeanPostProcessor的postProcessAfterInstantiation方法
      - 根据自动注入的方式（byName/byType）调用方法，获取所有需要注入的属性（调用getBean方法）
      - 调用InstantiationAwareBeanPostProcessor的postProcessProperties方法(@ Autowire之类的注解在此处通过AutowiredAnnotationBeanPostProcessor注入)
      - 将获取到的属性设置到bean中
    - 初始化bean（initializeBean）
      - 三类aware回调：BeanNameAware,BeanClassLoaderAware,BeanFactoryAware
      - 调用BeanPostProcessor.postProcessBeforeInitialization
      - 判断bean是否实现了InitializingBean接口，如果是，调用其afterPropertiesSet方法
      - 如果配置了init-method，则调用对应方法
      - 调用BeanPostProcessor.postProcessAfterInitialization

finishRefresh() 广播初始化完成事件

AOP

https://javadoop.com/post/spring-aop-source

SpringMVC

SpringCloud

Eureka

https://www.infoq.cn/article/jlDJQ*3wtN2PcqTDyokh

运行过程

服务启动后向Eureka注册，Eureka Server会将注册信息向其他Eureka Server进行同步，当服务消费者要调用服务提供者，则向服务注册中心获取服务提供者地址，然后会将服务提供者地址缓存在本地，下次再调用时，则直接从本地缓存中取，完成一次调用。
当服务注册中心Eureka Server检测到服务提供者因为宕机、网络原因不可用时，则在服务注册中心将服务置为DOWN状态，并把当前服务提供者状态向订阅者发布，订阅过的服务消费者更新本地缓存。
服务提供者在启动后，周期性（默认30秒）向Eureka Server发送心跳，以证明当前服务是可用状态。Eureka Server在一定的时间（默认90秒）未收到客户端的心跳，则认为服务宕机，注销该实例。

Eureka保护机制

如果在一定时间内超过85%的节点没有正常心跳，那么Eureka认为客户端与注册中心的网络出现故障，Eureka进入保护模式，不再剔除任何服务哪怕长时间没有收到其心跳；该阶段仍接受新服务的注册和查询，但不会同步到其他节点上；当网络稳定后再将新注册信息同步到其他节点中。

Spring中的各类BeanPostProcessor

Spring支持的扩展接口

Spring 如何解决循环依赖

BeanFactory getBean源码分析

创建Bean的时候，每次创建完对象实例(对象A)，在进行参数设置之前，会将当前对象（还没有赋值完毕的Bean，也称为早期引用）先缓存起来；在参数赋值时，需要创建其依赖的对象，如果这个依赖的对象(对象B)正好依赖了当前需要被赋值的Bean，其可以从缓存中获取到其早期依赖，那么这个被依赖的对象(对象B)就能顺利初始化完成，随后对象A也可以被顺利初始化完成。

根据上述原理，一般情况下的依赖都可以解决循环依赖的问题，但是前提是只有创建完对象实例后才会被缓存，所以如果在调用构造方法时循环依赖，会导致无法创建实例，也就无法得到缓存起来的早期引用了。

BeanFactory 和 ApplicationContext

BeanFactory实现了IOC容器最基本的功能，其定义了一系列getBean接口，通过这个方法可以获取容器所管理的Bean。ApplicationContext继承了BeanFactory，在BeanFactory的基础上扩展了一些功能，例如国际化、资源访问、事件发布等。其也是Spring框架的基础，提供了各种扩展能力。

ApplicationContext中getBean接口的实现都是委托给内置的BeanFactory对象，例如使用最多的DefaultListableBeanFactory。

RocketMQ

https://juejin.im/post/5de3c8026fb9a07194761641

http://www.itpub.net/2019/11/27/4449/

https://itzones.cn/categories/rocketMQ/

架构组成

NameServer：NameServer集群相当于精简版zooKeeper，用来注册topic与broker信息。NameServer之间不进行通讯，只与broker维持心跳，即broker定时上报其所负责的topic数据。
Broker：负责消息存储，消息收发

数据存储

文件分类

commitLog：消息元数据存储文件，每个broker中所有元数据存储到其中。单个文件最大1G，该broker中的所有topic共用此文件，所有的元数据顺序写入，写入性能高
config：配置信息文件，包括一些Group，Topic以及Consumer消费offset等信息。
consumeQueue：消费队列文件，每个队列一个文件，相当于commitLog的索引。消费者按序consumeQueue文件，再通过每一条记录中的offset去commitLog中读取元数据。

写入过程

客户端发送消息给broker时，broker将所有topic的数据写入同一个commitLog文件，在多个topic情况下顺序写入性能仍很高（对比kafka每个topic一个文件）。写入完成后，定时任务会不断扫描commitLog中的数据，将其写入到对应的consumerQueue中。

读取过程

客户端读取对应的consumeQueue文件，此过程为顺序读取可以利用操作系统PageCache，性能较高。通过读取到的记录中对应的元数据offset，可以在commitLog文件中找到对应的元数据。

性能问题

在读取过程中，在通过offset读consumeQueue文件时会出现随机读，没有办法很好命中缓存，所以性能较差，主要通过Java文件映射（mmap）的方式，可以将文件直接映射到用户态内存地址，读写文件相当于是内存读写操作，将带来良好的性能。这种方式比较消耗内存，所以在主从模式下，当master机器内存占用超过40%时，读请求将会转发给salve节点。

高可用（HA）

集群模式

单master模式：一台宕机，整个服务不可用
单master多slave模式：master宕机时不可写入，可以从slave读取
多master模式：单个master宕机时，该机器上面的数据不可读，如果Topic分布在多台master上，那么其余的master可以读写
多master多salve模式：某个master宕机，只会导致该master不可写入，可以从salve读取；如果Topic分布在多台master上，那么其余的master可以读写

主从模式

数据备份：保证一组broker上数据的冗余，当master宕机不可恢复时保证数据不丢失（或很少丢失）
高可用：当master宕机，客户端可以连接salve节点进行消费；生产者也可以连接topic对应的其他broker节点进行发送
高性能：当master有消息堆积时（内存使用超过40%）会将读请求转发到salve节点，减轻master节点的压力

刷盘策略

异步刷盘：发送消息时将数据写入内存，等待异步线程进行刷盘操作，有小概率宕机丢数据的可能性，但性能更高。
同步刷盘：主线程会等待刷盘任务完成，如果刷盘失败，则认为消息发送失败，保证数据一致性。

延时消息实现方案

http://www.itpub.net/2020/01/07/5010/

快速失败

为了防止某台master出现消息堆积而导致大量消息超时，RocketMQ使用了快速失败机制。通过一个定时任务，每隔10ms扫描队列中第一个节点，如果排队时间超过200ms（可配置），就会把等待时间超过该值的任务全部返回失败。而客户端将会捕获失败而进行重试，可以在其他master机器上进行重试。

Tomcat

Netty

https://www.javadoop.com/post/netty-part-1

Hystrix

Hystrix技术解析

信号量模式与线程池模式的区别

信号量模式将接受请求与请求下游接口放在同一个线程中执行，即请求下游接口时不创建新的线程执行，没创建线程与上下文切换带来的开销，只通过maxConcurrentRequests参数限制最大并发数。

线程池模式将请求下游接口放到线程池中执行，可以异步执行多个下游接口。

数据库

Redis

https://juejin.im/post/5dc3a9fbf265da4d3c072eab

集群模式

主从模式、哨兵模式、集群模式

https://juejin.im/post/5b7d226a6fb9a01a1e01ff64

哨兵模式架构

主节点的下线过程

所有哨兵节点每秒PING一次所有的主、从节点及其他哨兵节点。
如果一个节点超过一定时间没有相应PING，则会认为该节点主观下线
如果是主节点主观下线，则所有哨兵节点需要每秒检查一次该主节点是否的确进入主观下线状态
当一个哨兵节点认为主节点主观下线并不意味着主节点真的故障了，如果有足够数量的哨兵节点均认为该主节点是主观下线状态，则将该主节点标记为客观下线；如果没有足够数量的哨兵节点认可主节点主观下线，主节点的客观下线状态将被移除，当主节点响应了某个哨兵节点PING指令时，那么该哨兵节点对主节点的主观下线状态也会被移除。
哨兵节点向所有从服务器发送INFO指令，选出新的主服务器
将其余从节点执行新的主节点，并进行数据复制

选举新主节点

选举Sentinel(哨兵) Leader

当需要选举主节点时，需要选举一个哨兵（Sentinel）节点为Leader。每个哨兵节点会要求其他哨兵节点选举自己为Leader，如果被请求的节点没有参与过选举，则将同意其请求，即发起请求的节点票数+1；否则不同意其请求，票数不变。

如果某个哨兵节点的得票数大于一半，则其成为Leader。如果没有超过一半的节点，则重新选举。

Sentinel Leader决定主节点

过滤所有的故障节点
选择slave-priority最大的节点作为主节点，如果不存在则继续
选择复制偏移量最大（即已从旧主节点同步数据最多的）的节点为主节点，如果不存在则继续
选择runid（在节点启动时分配的随机id）最小的节点为主节点

Redis Cluster 架构

https://mp.weixin.qq.com/s/zjwiOkRFvQDpKfeFL1-dUQ

一个redis集群包含2^14=16384个哈希槽，集群中的每个节点会分配到一部分槽，如下图

集群使用公式 CRC16(key) % 16384 来计算每次请求的键 key 属于哪个槽，再通过槽对应节点配置，就可以找到key所对应的数据应该请求哪一个节点。

这种方式很方便进行扩容和缩容，例如：

如果用户将新节点 D 添加到集群中，那么集群只需要将节点 A 、B、C 中的某些槽移动到节点 D 就可以了。
与此类似，如果用户要从集群中移除节点 A ，那么集群只需要将节点 A 中的所有哈希槽移动到节点 B 和节点 C ，然后再移除节点 A 就可以了。

槽迁移过程

例如A节点的X槽迁移到B节点

向节点 A 发送命令 CLUSTER SETSLOT X MIGRATING B，此时A节点X槽状态设置为**MIGRATING**
向节点 B 发送命令 CLUSTER SETSLOT X IMPORTING A，此时B节点X槽状态设置为**IMPORTING**
A节点中所有key开始迁移至B节点，迁移过程是原子性的，也就是一个key要么还在A节点中，要么已经迁移至B节点中，不会同时存在
此时有客户端请求属于X槽的key，如果是已存在的key，则由A处理；否则返回ASK指令，客户端将使用ASKING指令重新请求B节点；这能保证A节点中key数量只减不增，B节点key只增不减
当所有key都迁移完成，A、B节点清除迁移状态，B节点发送UPDATE指令给所有节点，通知其更新槽对应的节点信息，后续的X槽指令将全部被重定向（MOVED指令）到B节点

分布式锁

https://juejin.im/post/5e6df710e51d4526fc74b4ec

单点模式

通过原子命令加锁并设置失效时间，例如：SET key random_value NX PX 30000
设置值时，需要设置一个随机值，通过lua脚本进行原子性解锁，保证上锁和解锁是同一个客户端

集群模式

在集群模式下，如果在master节点上获取了锁，但是数据还没来得及同步到到slave节点主节点就挂了，故障转移后，从新的master节点将可以获取到一个新的锁，出现了一把锁被两个线程持有的问题。

RedLock

上锁：在集群模式下，即有N个节点的情况下，通过一个统一key+随机值的方式，向N个节点获取锁。只要有N/2+1个节点加锁成功，则视为获取锁成功，否则需要进行解锁。

解锁：依次向每个节点发起解锁操作，即便这个节点上没有上锁成功。

风险点：当某个节点上锁成功，但是故障重启后，可能会丢失数据从而导致其他客户端可以重复上锁成功。例如三个节点中有两个加锁成功一个加锁失败，加锁成功数大于等于N/2+1，所以视为上锁成功。此时加锁成功的一个节点故障重启并丢失了数据，此时如果有客户端申请加锁，将可以获取锁成功。

持久化策略

https://zackku.com/redis-rdb-aof/

RDB

定时把数据的快照保存到文件中，由于是某个时间点的快照，所以可能会丢数据，但是持久化和加载性能更高，文件数据更小。

AOF

将每次的操作记录写入到缓冲区，根据策略（每次刷盘、每秒刷盘、等操作系统自动刷盘）将记录追加到文件上。

由于记录每次操作，日志文件冗余，加载速度会很慢，所以可以开启日志重写，例如将多次INCR操作合并成一次SET操作。

AOF相对于RDB可靠性更高，但是默认刷盘策略为一秒一次，仍不能保证数据绝对安全；AOF记录的是操作日志，所以可读性更高，即使文件被部分破坏，也容易恢复到某个数据节点；但是存储的文件更大，写入和加载性能效率低于RDB

数据结构

Redis	底层数据结构	备注
string	当存储值为整数时，使用int 当存储值为字符串且小于32字节，使用embstr，即优化后的`SDS` 当存储值为字符串且大于32字节，使用raw，即SDS	`SDS`为包装后的char数组浮点数也通过char数组，需要计算时转成浮点数计算，计算完转成char数组保存 SDS中最大只能保存512M数据
list	3.2版本前&数据较少时，使用ziplist 3.2版本前&数据较多时，使用linkedlist 3.2版本后，使用quicklist	`ziplist` `linkedlist` `quicklist`
hash	`hashtable`	`hashtable`
set	当所有元素为整数&个数小于512时，使用`intset` 其他情况，使用`hashtable`	`intset`
zset	当元素较少时，使用ziplist + `hashtable` 当元素较多时，使用`skiplist` + `hashtable`	`skiplist` 使用`skiplist` + `hashtable`是为了利用查询时`hashtable`O(1)时间复杂度和排序时`skiplist`O(logn)时间复杂度的优势

内存淘汰策略

noeviction(默认策略)：对于写请求不再提供服务，直接返回错误（DEL请求和部分特殊请求除外）
allkeys-lru：从所有key中使用LRU算法进行淘汰
volatile-lru：从设置了过期时间的key中使用LRU算法进行淘汰
allkeys-random：从所有key中随机淘汰数据
volatile-random：从设置了过期时间的key中随机淘汰
volatile-ttl：在设置了过期时间的key中，根据key的过期时间进行淘汰，越早过期的越优先被淘汰

其他数据结构

bitset

可以操作一个值中的二级制位，可以用来实现布隆过滤器

geo

可以存储位置，并通过目标位置的距离查询指定距离范围内的数据，例如实现附近的人。

HyperLogLog

适合用来统计一个集合中不重复的元素个数，但不要求数据完全准确的情况，例如访问UV等。

一亿个统计数据约只占12M内存。

MySQL

https://draveness.me/mysql-innodb

MySQL索引背后的数据结构及算法原理（包含B树和B+树原理）http://blog.codinglabs.org/articles/theory-of-mysql-index.html

锁

MySQL加锁分析

锁的种类

互斥锁、共享锁、意向互斥锁、意象共享锁
什么是意象锁

如果没有意向锁，当已经有人使用行锁对表中的某一行进行修改时，如果另外一个请求要对全表进行修改，那么就需要对所有的行是否被锁定进行扫描，在这种情况下，效率是非常低的；不过，在引入意向锁之后，当有人使用行锁对表中的某一行进行修改之前，会先为表添加意向互斥锁（IX），再为行记录添加互斥锁（X），在这时如果有人尝试对全表进行修改就不需要判断表中的每一行数据是否被加锁了，只需要通过等待意向互斥锁被释放就可以了。

锁的算法

Record Lock

如果where 条件中包含主键索引或其他索引作为过滤条件，那么将在B+树中找到对应记录并上锁，即为Record Lock；
如果没有索引，那么只能进行锁表。

Gap Lock

当where条件中存在范围条件时（必须有索引，否则仍为表锁），例如where id between 10 and 20，将会上Gap Lock。

Next-Key Lock

Next-Key Lock算法，锁定的不是单个值，而是一个范围（GAP）。上面索引值有1，3，5，8，11，其记录的GAP的区间如下：是一个左开右闭的空间

（-∞,1]，(1,3]，(3,5]，(5,8]，(8,11]，(11,+∞）

Next-Key Lock是Record Lock和Gap Lock的组合，即锁住范围的同时锁住区间，在RR(REPEATABLE-READ)隔离级别下, SELECT ... FOR UPDATE使用Next-Key Lock, 即Record Lock + Gap Lock.

在一些场景下Next-Key Lock会退化

场景	退化成的锁类型
使用`unique index`精确匹配(=), 且记录存在	Record Lock
使用`unique index`精确匹配(=), 且记录不存在	Gap Lock
使用`unique index`范围匹配(<和>)	`Record Lock` + `Gap Lock` 且锁上界不锁下界

Gap Lock 与 Next-Key Lock

官方文档：https://docs.oracle.com/cd/E17952_01/mysql-5.0-en/innodb-record-level-locks.html

带翻译版：https://cloud.tencent.com/developer/article/1447138

死锁

在多个SQL以不同顺序申请锁时，可能会产生死锁，例如:

使用索引A（非主键）进行更新时，如果恰巧有其他sql通过主键更新A字段时，将有可能死锁。因为通过非主键更新时，会先将A（辅助索引）上锁，再找到其主键上锁；通过主键更新时，会先对主键上锁，如果发现需要更新的字段为辅助索引（如A索引）时，再将辅助索引上锁，此时就会导致死锁。

单表理想性能计算

希望btree的高度h<=3，即最多通过两次IO可以查询所有数据（根节点常驻内存）
InnoDB中主键默认为64位即8b，索引为6b，合计一条记录需要14b，MySQL中一个节点占用一页，一页大小为16k，所以每个节点最多16kb/14b=1170条记录
h=3时，索引占用前两层，所以一共1170*1170条内页索引（不包含叶子节点的节点数）
假设每条记录为1k，所以叶子节点中每一个节点约为16条记录，合计1170*1170*16约等于两千万，此时单表占用空间约为1170*1170*16/1024/1024≈20G
坊间传的MySQL数据量达到两千万后性能下降的原因大致是这样的，但是是按每条记录1k计算的，所以仅供参考，如果单行记录远小于这个值的，不会受两千万数量的影响
例如辅助索引，叶子节点存储的数据域是主键（InnoDB），所以每一行占用的空间为16b（key 8b，主键8b），那么每个叶子节点最多容纳16k/16b=1000个节点，此时整棵树最多可容纳1170*1170*1000约等于13亿行
所以可以认为，当表数据量小于20G且行数不大于13亿时，一般不会出现太大性能瓶颈

索引（InnoDB）

聚集索引：存放着一条行记录的全部信息
辅助索引：包含索引列和一个用于查找对应行记录的『书签』

回表

如果在辅助索引中（例如(user_id,user_name)），不包含所要查询的字段，例如 select user_name,sex from tb_user where user_id = xxx语句中，需要查询user_name和sex，但是在该索引中不包含sex字段，所以需要通过辅助索引找到主键，再通过聚集索引找到完整数据才能获取到sex字段，这个过程即为回表 。

索引覆盖

上文回表可以看出，回表操作需要额外通过主键索引找到完整数据的过程，比不回表的操作多了一次IO，所以可以尽量避免此类消耗。例如将常用的查询字段放入索引中，若索引中的字段涵盖了要查询的所有字段，即为索引覆盖。不过会增大索引的空间造成浪费，通过空间换时间，需要根据业务场景选择。

索引下推

索引下推可以在范围查询或like查询情况下，减少回表操作。

例如有a,b两个字段，建立 (a,b) 联合索引，执行 select * where a > 0 and b >0

正常情况下，只能用到a字段的索引，因为B+树中只能通过前缀匹配范围查询。通过筛选 a>0条件后，进行回表操作，再筛选出 b>0的记录

可以发现，这种方式回表的数据较多，其实可以做一次优化，在筛选完a>0后，再进行一次b>0筛选，这样回表的数据就少多了，这种优化方式成为索引下推，MySQL中默认开启。

索引优化策略

最左前缀匹配
不要使用函数
用区分度大的字段作为索引
减少回表操作，请求量大的SQL可以考虑进行索引覆盖
尽量减少使用排序，如果要使用，尽量保证走索引；如果不走索引尽量保证在内存中排序；尽量使用LIMIT，因为LIMIT能尽可能保证进行内存排序而不是文件排序，参见LIMIT优化

排序

MySQL排序原理与案例分析

计划任务中出现Using filesort表示需要额外排序，但不一定是文件排序，也有可能是内存排序

排序过程

查询出满足where条件的记录
对于每条记录，将主键+排序key取出，放入sort buffer，例如(id+key)
如果sort buffer能存放下所有的记录，则在内存中使用快速排序；如果放不下，就需要放入文件中，使用归并排序
排序完后，如果需要limit则进行过滤；如果需要回表，则执行回表
将数据返回给客户端

LIMIT优化

例如Order by limit M,N，虽然所有元素都要参与排序，但是在sort buffer中只需要能放下N+M个元素即可在内存中使用堆排序，而不需要进行文件排序，减少IO提高性能。

事务特性 ACID

原子性(Atomicity)：事务是一个不可再分割的工作单元
一致性(Consistency)：事务不能破坏关系数据的完整性以及业务逻辑上的一致性
隔离性(Isolation)：事务之间是隔离的，一个事务不应该影响其它事务运行效果
持久性(Durability)：事务完成以后，该事务所对数据库所作的更改便持久的保存在数据库之中，并不会被回滚

事务隔离级别

此处注意甄别数据库规范与InnoDB具体实现之间的差异，此处指InnoDB的具体实现

未提交读(READ UNCOMMIT)：存在脏读问题
提交读(READ COMMIT)：解决脏读问题，存在不可重复读和幻读问题
重复读(REPEATABLE READ)：解决不可重复读问题和幻读，通过MVCC解决不可重复读，通过gap lock解决幻读
串行(SERIALIZABLE)：从MVCC退化到基于锁的并发控制

不可重复读和幻读

不可重复读是指在一个事务中，已加锁的记录第二次读取时与之前的内容不同，但数量不变，即可能被update

幻读是指在一个事务中，已加锁的数据第二次读取时结果集数量不同，即可能被insert或delete。官方链接：https://dev.mysql.com/doc/refman/8.0/en/innodb-next-key-locking.html

https://www.cnblogs.com/itcomputer/articles/5133254.html

MVCC

https://chenjiayang.me/2019/06/22/mysql-innodb-mvcc/

https://www.cnblogs.com/naci/p/3753644.html?utm_source=tuicool&utm_medium=referra

MVCC (Multiversion Concurrency Control) 中文全程叫多版本并发控制，是现代数据库（包括 MySQL、Oracle、PostgreSQL 等）引擎实现中常用的处理读写冲突的手段，目的在于提高数据库高并发场景下的吞吐性能。用来实现InnoDB中的RC和RR级别。

实现原理

在每一行数据中，增加了两个隐藏字段，分别是DATA_TRX_ID和DATA_ROLL_PTR，DATA_TRX_ID表示更新这条记录的事务id，事务id为每次开启事务时分配的id，保证先开启事务的事务id小于后开启的事务。DATA_ROLL_PTR为指向指向undo log中该行之前版本的指针。

在每次更新，把需要更新的行数据原样拷贝到undo log中；再修改表中改行的值，并把DATA_TRX_ID的值设置为当前修改事务id、DATA_ROLL_PTR设置为undo log行所在的地址；

插入操作仅需要把新插入的行中DATA_TRX_ID设置为当前事务id即可；

删除操作与更新操作的差别为需要修改需要删除行的删除标记为已删除；

ReadView

在执行select操作时，将当前系统中所有的活跃事务id拷贝到一个列表中，生成一个ReadView。其中的事务id称为m_ids。

在RC中，每一个select均会生成一个ReadView；RR中，只在每个事务的第一次select生成ReadView。

如果被访问版本的 trx_id 小于 m_ids 中的最小值，说明生成该版本的事务在 ReadView 生成前就已经提交了，所以该版本可以被当前事务访问。
如果被访问版本的 trx_id 大于 m_ids 列表中的最大值，说明生成该版本的事务在生成 ReadView 后才生成，所以该版本不可以被当前事务访问。需要根据 Undo Log 链找到前一个版本，然后根据该版本的 DB_TRX_ID 重新判断可见性。
如果被访问版本的 trx_id 属性值在 m_ids 列表中最大值和最小值之间（包含），那就需要判断一下 trx_id 的值是不是在 m_ids 列表中。如果在，说明创建 ReadView 时生成该版本所属事务还是活跃的，因此该版本不可以被访问，需要查找 Undo Log 链得到上一个版本，然后根据该版本的 DB_TRX_ID 再从头计算一次可见性；如果不在，说明创建 ReadView 时生成该版本的事务已经被提交，该版本可以被访问。
此时经过一系列判断我们已经得到了这条记录相对 ReadView 来说的可见结果。此时，如果这条记录的 delete_flag 为 true，说明这条记录已被删除，不返回。否则说明此记录可以安全返回给客户端。

主从复制与读写分离

原理

数据写操作走主库，读操作走从库，实现读写分离。所有写操作记录写入binlog，从库通过一个IO线程将主库binlog同步至本地，再将内容写入relay log。从库中的SQL 线程将读取relay log将其顺序执行，实现数据变更从主库同步到从库的过程。

数据延迟

主库与从库间的数据延迟的可能原因

binlog从主库同步到从库是异步的，外加需要同步完成后再重新执行binlog，天然存在延迟
主库的写操作是可以并发的，但是从库在同步时的变更操作是单线程的
主库执行完变更后宕机，binlog没来得及同步到从库

解决（缓解）方案

半同步复制：主库在提交完事务后，不直接返回给客户端，而是等待至少一个从库接受并写入到relay log后才返回。保障了数据的安全性，但是会导致用户请求的延迟。
并行复制：从库可以开启多个线程读取relay log中不同库的日志，实现库级别的并行
在特殊业务场景下，读操作直连主库，保证数据的可见性。

ZooKeeper

Zookeeper的ZAB协议

ZK的缺陷

阿里为什么不用 ZooKeeper 做服务发现

ZK追求CP而不是AP，导致脑裂时，该机房的ZK处于不可以状态，导致通过ZK实现的服务发现的集群在该机房的机器虽然网络畅通，但不可调用。
注册中心不应该因为自身的问题而影响服务之间本身的可连通性。即服务应该仅在上下线、扩缩容等必要时才依赖注册中心，当ZK宕机时，不应该影响已启动业务之间的互相调用。
由于ZK写操作不可扩展，无法通过增加节点解决写压力，如果微服务过多，外加每个服务都要进行健康检查，ZK将会不堪重负。即使通过业务隔离划分多个ZK集群，但不能保证不同业务之间永远不会互相调用。
一般的服务健康检查都是依赖ZK对TCP长链接的活性检查，但这种方式不够灵活，TCP活跃不代表服务健康

总结：ZK适合在不需要高TPS支持的业务场景下处理分布式锁、分布式选主、主备切换等；如果在高TPS链路上、大规模数据存取、服务发现、健康检查等方便并不适合。

HBase设计原理

https://www.cnblogs.com/laoqing/p/12091471.html

https://segmentfault.com/a/1190000019959411

架构组成

HMaster：负责Region的分配；表结构创建修改等操作；通过ZK监听管理RegionServer
RegionServer：管理Region，每个RegionServer可管理1000个Region；处理Region的读写请求；切分过大的Region
Region：Table中的数据根据rowKey的范围被水平分割存放在多个Region上

读写过程

基本概念

MetaTable：HBase中的一张特殊的表，用来存放RowKey与RegionServer的关系
WAL：Write Ahead Log 是HDFS中的一个文件，也称为HLog。同一个RegionServer共用同一个WAL文件，所有写操作信息会被优先写入WAL文件
BlockCache：读缓存
MemStore：写缓存，写操作被写入MemStore后即视为写入成功，后续根据一定策略进行刷盘（flush如HDFS）（类似与操作系统中的PageCache）。每个Column Family都会对应一个MemStore
HFile：在HDFS中存储的数据，以KV方式存储，相同的数据会有多个版本共存

写操作

新数据被写入WAL
新数据写入MemStore
写入成功

由于WAL文件写入采用append方式，所以为顺序写入，性能很高。在成功写入WAL后再写入MemStore保证机器宕机掉电导致MemStore中数据丢失，也可以通过WAL文件恢复丢失数据。

当MemStore中积累一定数据后，每个MemStore会往HDFS上写入一个新的HFile，当一个MemStore满了，内存中的所有MemStore都会被flush到HDFS中

压缩（Compaction）

每次MemStore刷盘操作都会生成新的HFile，过多HFile会导致读性能问题，需要通过压缩来解决

Minor Compaction：选取一些小的HFile将其合并成较大的HFile，这个过程不会处理已经删除或失效的数据。
Major Compaction：将单个Region中的所有HFile合并成一个大的HFile（每个Column Family仍为独立的HFile），由于Major Compaction对机器的IO等影响较大，所以一般在低峰期计划执行。

分裂

一张表刚开始只有一个region，当数据变多变大时，它会分裂成两个region，各自包含原来的一半数据。出于负载均衡考虑，HMaster会将新生成的region迁移到其他HRegionServer中，此时的迁移只是逻辑上的，也就是说只是把新的region交给其他HRegionServer管理，但数据仍在原处，所以此时HRegionServer需要访问不在本地（本机）的数据而影响性能。等到下一次Major Compaction可以将数据移到HRegionServer附近存储解决问题。

读操作

客户端从ZK处查询MetaTable所在的HRegionServer
查询对应HRegionServer获取MetaTable，根据MetaTable确定RowKey所在HRegionServer
访问HRegionServer查询数据

在查询HRegionServer的具体查询过程如下：

从BlockCache中查询
从MemStore中查询
查询HFile，由于查询HFile涉及到磁盘IO会影响性能，所以会通过BlockCache中的索引和布隆过滤器进行查询优化。

由于每一个RowKey存在多个历史版本，所以一次读操作可能需要查询多次，而每个版本数据可能会在不同HFile上，会影响性能，这被称为读放大。

故障恢复

当某个RegionServer宕机时，该节点与ZK的链接会断开，此时HMaster将会监听到此事件，HMaster开始自动进行故障恢复：

把原来由该RegionServer管理的region分配给其他健康的RegionServer
有些数据还在MemStore中并没有刷盘，此时需要将WAL日志按Region进行切分
每个Region执行日志回放进行数据恢复

优缺点

优点

数据在单机上过大时，将自动进行分裂而实现负载均衡，可以通过水平扩展存储海量数据
使用HDFS作为底层数据存储，保障数据安全性
使用WAL进行数据恢复保证高可用
离线计算友好

缺点

故障恢复很慢
Major Compaction会占用大量I/O资源
不支持二级索引

MongoDB/ElasticSearch设计原理

常用设计模式

细数JDK里的设计模式 http://blog.jobbole.com/62314/
模板方法
工厂

网络

TCP/IP 四层协议

网络访问层
网络层：IP、ARP
传输层：TCP、UDP
应用层：HTTP、FTP、SMTP

连接

https://zhuanlan.zhihu.com/p/86426969

三次握手

三次握手是指服务器与客户端建立一个TCP链接一共需要通讯三次，目的是为了互相确认彼此的接受和发送能力均正常。

次序	发包方向	发送信息	能力确认	是否可携带数据
第一次	客户端->服务端	SYN=1,seq=x	客户端发送能力正常	否
第二次	服务端->客户端	SYN=1,ACK=1,ack=x+1,seq=y	服务端发送能力、接受能力正常	否
第三次	客户端->服务端	ACK=1,ack=y+1,seq=x+1	客户端接受能力正常	是

半连接队列和全连接队列

服务器端在收到客户端发来的第一次SYN报文后，会处于SYN_RCVD状态，服务器会将这种状态的连接放入队列中，称为半连接队列。在这个队列中的连接如果等待一段时间没有收到客户端的确认包，将会进行重传直到达到最大重传次数，然后会被从半连接队列中移除。

针对这种机制，有可能受到SYN攻击，即客户端发起大量SYN请求，导致半连接队列被占满并且不断进行重试，最终导致网络瘫痪。

完成三次握手的连接，将会放入全连接队列中。

四次挥手

断开连接需要四次通讯，因为断开连接需要连接双方各主动发起一次结束报文，证明发起方不再向对方发送数据了，并且每一次发起对方均需要响应，所以一共有四次通讯。

次序	发包方向	发送信息	当前状态
第一次	客户端->服务端	FIN=1,seq=i	客户端停止发送数据
第二次	服务端->客户端	ACK=1,ack=i+1,seq=j	服务端停止接受数据
第三次	服务端->客户端	FIN=1,ACK=1,ack=i+1,seq=k	服务端停止发送数据
第四次	客户端->服务端	ACK=1,ack=k+1,seq=i+1	客户端等待2MSL后关闭并进入CLOSE 服务端接受后直接进入CLOSE

第四次接受到响应报文后为何需要等待2MSL才能进入CLOSED

MSL（Maximum Segment Lifetime）表示一个报文在网络传输时最大生命周期，如果超过这个时间，就算被接受到，报文也会被丢弃。

第四次挥手时，客户端的ACK报文在传输中可能会丢失，服务器会要求客户端进行重传，如果客户端立即进入CLOSED，将没有能力响应，从而导致服务端无法正常CLOSED。等待2MSL表示服务端已经无需客户端进行重传了，则可以关闭。

HTTP

HTTP1.0 与 HTTP1.1的区别

更多的缓存策略，如If-Unmodified-Since, If-Match, If-None-Match
支持客户端请求部分数据，可以实现断点续传
请求头中增加了host字段
支持长链接和流水线，提高性能

HTTP1.1 与 HTTP2.0的区别

多路复用：降低服务端连接压力，降低传输延迟
首部压缩：避免header中数据重复传输
服务端推送：服务端可以将资源主动推送给客户端，提高加载效率

HTTP 与 HTTPS的区别

HTTP数据传输完全明文，容易被抓包和劫持；HTTPS使用TLS（SSL的新版本）来保证安全传输，数据加密传输。

HTTPS过程：

在握手过程中，客户端向服务端请求证书，服务端返回证书及公钥
客户端收到证书后向证书签发机构验证
客户端生成对称秘钥，用服务端公钥加密后传输给服务端，后续请求通过该秘钥加密通信

数据结构

二叉搜索树
平衡树
平衡查找树——2-3树 https://www.cnblogs.com/yangecnu/p/Introduce-2-3-Search-Tree.html
红黑树（2-3树的二叉实现）：高度为lgN https://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html

源码

HashedWheelTimer

https://www.javadoop.com/post/HashedWheelTimer

将一个轮盘分为512格，每一格跨度100ms。每个任务根据执行时间放入对应的格子里，并计算其轮次。每次循环到下一个格子时，先计算距离当前格子的执行开始时间，如果还没到，则sleep到目标时间，然后按顺序执行这个格子中轮次为0的所有任务，轮次不为0的任务全部自减；如果已经超过这个格子的deadline，即开始时间+100ms，则直接跳过这次执行。

例如1000ms后执行的任务，需要放到(1000/100)%512=10号格子中，轮次为0；513000ms后执行的任务，需要放到(513000/100)%512=10，轮次为1；

可以发现1000ms和513000ms后执行的任务放在了同一个队列中，但是轮次不同，第一次执行当10号格子时，100ms任务轮次为0，正常执行；513000ms任务轮次自减成0，下一次轮到的时候就可以执行了。

如果上一个格子占用了过多时间怎么办

正常情况下，每个格子只有100ms的执行窗口期，但是在执行过程中不会判断是否执行超时，只有全部执行完，走到下一个格子时，会判断是否超过当前格子的deadline。如果超过了，将直接执行当前格子对应的任务。

工作线程为单线程

执行所有任务的线程是单线程的，如果每个格子中的任务执行时间之和超过100ms，后续的所有任务将会受到影响，所以尽量不要提交执行时间很长的任务到HashedWheelTimer中。

算法

缓存淘汰算法

LRU

LRU全称是Least Recently Used，即最近最少使用。当缓存需要清理时，清除最近一段时间没有使用过的数据。

数据结构：双向链表+哈希表

算法复杂度：一般情况下为O(1)，特殊情况下由于哈希碰撞严重，可能会退化为O(N)

通过一个双向链表存储所有的节点，如果某个数据被访问，那么将该节点移动到链表最开始，需要淘汰时，将链表最后一个节点移除。为了方便查询，在哈希表中存储的数据结构为key:(value,point),其中point表示该数据在链表中的指针，方便移动时能快速找到链表中的节点。

LFU

LFU 即Least Frequently Used，最近最少使用。当缓存需要清理时，清除最近使用次数最少的数据。

数据结构：TreeMap + 哈希表 + 双向链表

算法复杂度：一般情况下为O(1)，特殊情况下由于哈希碰撞严重，可能会退化为O(N)

在TreeMap中保存访问次数与访问次数对应的数据，相同的访问次数可能对应多个数据，这些数据通过双向链表进行保存。哈希表中的数据结构为key:(value,point),其中point表示该数据在双向链表中的指针，方便修改访问次数时可以快速在链表中移除该节点并添加到新的链表中。

FIFO

FIFO 即First In First Out，先进先出。当缓存需要清理时，清除最先加入缓存的数据。

数据结构：双向链表 + 哈希表

算法复杂度：一般情况下为O(1)，特殊情况下由于哈希碰撞严重，可能会退化为O(N)

通过双向链表保存数据的加入顺序，新加入的数据添加到队尾，需要清理时，移除队头数据。

架构

分布式系统设计原则：CAP原则

https://www.cnblogs.com/szlbm/p/5588543.html
- C:一致性(Consistency)，A:可用性(Availability)，P:分区容错性(Partition tolerance)
- 分布式系统必须实现分区容错性，所以P必须实现
- CA不能同时满足：因为网络是不可靠的，要实现分区之间数据一致，必须依赖与网络。如果需要强一致性，网络故障时会导致不可用(without A)，如果需要保证可用性，则网络故障时只能用旧值(without C)

分布式事务

https://mp.weixin.qq.com/s/gg4q_53eiHCI3OUWzN7eWg

XA

2PC(two phase commit)的一种实现，分别需要执行预提交(precommit)和提交(commit)两个阶段，需要底层数据库支持。

缺点：

需要事务管理器进行协调，如果事务管理器故障会导致资源阻塞
最终提交前，资源一直被阻塞，性能差
网络问题导致多个服务没有同时提交或同时回滚，导致数据不一致

TCC

https://www.bytesoft.org/

TCC分为三个操作，分别是try、confirm、cancel，其中每一个操作都是完整的本地事务。

try：尝试执行业务检查和准备操作，例如转账前检查余额，并将余额进行冻结。
confirm：如果所有从属业务try操作均成功执行，则依次执行confirm。confirm不允许业务异常，例如冻结金额不足等业务问题。如果执行失败，则将不断重试，所以需要保证幂等。例如将try操作冻结的余额进行扣除。
cancel：如果有任何一个从属业务try失败，则执行所有try成功业务对应的cancel操作。如果执行失败，将不断重试，需要保证幂等。例如将try操作冻结的金额释放。