知识点汇总 | northern

先是聊项目，从项目的架构设计到部署流程。
Java容器有哪些？哪些是同步容器,哪些是并发容器？

容器分两个大类，Collection和Map。Collection又分List、Set、Queue、Vector几个大类，Map有HashMap、TreeMap、LinkedHashMap、HashTable，其中，Vector、HashTable是同步容器。

并发容器一般在juc包下，有ConcurrentHashMap、CopyOnWriteArrayList等。

ps:

List: ArrayList、LinkedList

Set: HashSet、LinkedHashSet、TreeSet

Queue: LinkedList、PriorityQueue

引申：几个容器的主要方法的操作流程，容器体系结构

ArrayList和LinkedList的插入和访问的时间复杂度？

ArrayList：插入O(n) 访问O(1)

LinkedList：插入O(1) 访问O(n)

Java反射原理，注解原理？

反射原理：在运行状态下，对于任何一个类，都能够知道这个类的所有属性和方法；对于任意一个对象，都能调用它的任意方法和属性，并能改变它的属性。总结来说，反射把Java类中的各个成分映射成为一个个Java对象，并且可以进行操作。

注解原理：注解的本质是一个继承了Annotation接口的接口。

解析一个类或者方法的注解有两种形式，一是编译期扫描，如@Override，编译器会检查方法是否真的重写了父类的某个方法；二是运行期发射，虚拟机规范定义了一系列和注解相关的属性表，字段、属性或类上有注解时（被注解修饰了），会写相应信息进字节码文件，Class类中提供了一些接口用于获取注解或判断是否被某个注解修饰。

延伸阅读：JAVA 注解的基本原理

ps: Java类执行的过程/类加载过程（2-6）/类的生命周期（2-8） – tbc 更准确的说法

编译：Java文件编译成.class字节码文件
加载：类加载器通过全限定名，将字节码加载进JVM，存储在方法区，将其转换为一个与目标类型对应的Class对象实例
验证：格式（.class文件规范）验证和语义（final不能继承等）验证？
准备：静态变量赋初值与内存空间，final修饰的内存空间直接赋原值（？），不是开发人员赋的初值
解析：符号引用转换为直接引用，分配地址（?）
初始化：先初始化父类，再初始化自身；静态变量赋值，静态代码块执行。
使用
卸载

新生代分为几个区？使用什么算法进行垃圾回收？为什么使用这个算法？

新生代有三个区，一个较大的Eden区，两个小的Survivor区。

使用复制算法。（也有标记过程，标记-复制）

一方面，针对算法本身，相对于标记-清除算法，不会有内存碎片的问题；相对于标记-整理算法，处理效率高很多（在整理时，还未进行对象清理，移动存活对象时需要将存活对象插入到待清理对象之前，有大量的移动操作，时间复杂度很高）。

复制算法主要问题在于内存利用率，而HotSpot的Eden和Survivor的默认比例是8:1，保证内存利用率达到了90%，所以影响也不是太大。

另一方面，新生代minor gc比较频繁，对gc效率有比较高的要求；对象生命周期比较短，小的survivor空间即可容纳大部分情况下的存活对象。

引申：jvm的几个知识点，算法，判断对象存活，GC roots有哪些，内存分配与回收策略，类加载机制

HashMap在什么情况下会扩容，或者有哪些操作会导致扩容？

java8中
1. 放入新值（putValue–put/putMapEntries）后，元素个数size大于阈值threshold，会触发扩容。
2. 链表树化时，如果表长table.length小于64，会用扩容代替树化。
3. put值前，如果表长为0，会触发扩容

HashMap put方法的执行过程？【见46】
1. 如果table为空，或长度为0，初始化。默认loadFactor为0.75，默认capacity为16（capacity是table的长度），threshold一般为capacity*loadFactor。
2. 通过hash定位槽，如果槽为空，构造新节点赋值给槽
3. 若槽不为空，则在槽的链表或树中找到key相同的节点，替换节点值为新值；或是没有key相同的节点，就在树中或链表尾部加入新节点；若链表加入新节点后长度达到8（槽不算，aka槽下原有7个节点），则进行红黑树转化
4. 如果是新加入节点，modCount、元素个数size自增1，如果元素个数超过阈值，则进行扩容

7.1 Java8扩容的执行过程？

1. 计算新容量newCap和新阈值newThr（ps: 当容量已到最大值时，不再扩容；2倍扩容；）
 2. 创建新的数组，赋值给table
 3. 将键值对重新映射到新数组上
      1. 如果无链表，直接根据`hash&(newCap-1)`定位
      2. 如果是树节点，委托红黑树来拆分和重新映射
      3. 为链表，根据`hash&oldCap`的值分成0、1两组，映射到j和j+oldCap（0低位，1高位）（**链表顺序不变**）

HashMap检测到hash冲突后，将元素插入在链表的末尾还是开头？

Java8是加载链表末尾

Java7是开头

头插法会改变链表中元素原本的顺序，在并发情况下可能会产生链表成环的问题。

Java7到Java8的改变HashMap为何从头插入改为尾插入

java7的问题老生常谈，HashMap的死循环

1.8还采用了红黑树，讲讲红黑树的特性，为什么人家一定要用红黑树而不是AVL、B树之类的？

插入、删除、查找的最坏时间复杂度都为 O(logn)。

红黑树特性：
1. 每个节点要么是黑色，要么是红色
2. 根节点是黑色的
3. 每个叶节点是黑色的（Java实现中，叶子节点是null，遍历时看不到黑色的叶子节点，反而每个叶子节点是红色的）
4. 如果一个节点是红色的，那么它的两个子节点是黑色的（意味着可以有连续的黑色节点，但不能有连续的红色节点。若给定N个黑色节点，最短路径情况是连续N个黑色，树高为N-1；最长路径情况是红黑相间，树高为2N-2）
5. 对任一节点，从节点到它每个叶子节点的路径包含相同数量的黑色节点（最主要特性，插入、删除要调整以遵守这个规则）
面试旧敌之红黑树（直白介绍深入理解）

为什么用红黑树？

红黑树的统计性能（理解为增删查平均性能）优于AVL树。

AVL：名字来源发明者G. M. Adelson-Velsky和E. M. Landis。本质是平衡二叉搜索树（查找树），任何节点的左右子树高度差不超过1，是高度平衡的二叉查找树。

B树：重温数据结构：理解 B 树、B+ 树特点及使用场景平衡二叉树节点最多有两个子树，而 B 树每个节点可以有多个子树，M 阶 B 树表示该树每个节点最多有 M 个子树

AVL树高度平衡，查找效率高，但维护这个平衡的成本比较大，插入、删除要做的调整比较耗时。

红黑树的插入、删除、查找各种操作的性能比较平衡。

B树和B+树多用于数据存储在磁盘上的场景，比较矮胖，一次读取较多数据，减少IO。节点内是有序列表。列表的插入、删除成本比较高，如果是链表形式，则查找效率比较低（不能用二分查找提高查询效率）。

【自己的理解：B树节点内是有序列表，通过二分查找提高效率】

为什么STL和linux都使用红黑树作为平衡树的实现？ - Acjx的回答 - 知乎 https://www.zhihu.com/question/20545708/answer/58717264

https和http区别，有没有用过其他安全传输手段？

区别：
1. http明文传输，安全性低；HTTPS数据加密传输，安全性高
2. 使用https协议需要到CA（Certificate Authority，数字证书认证机构）申请证书
3. http的响应速度比HTTPS快，因为HTTPS除了http三次握手的包，还要加上ssl的交互–具体是？
4. 端口不同，http80端口，https443端口
5. https本质是构建在ssl/tls之上的http协议
HTTP 与 HTTPS 的区别

其他安全传输手段：SSH

SSH 协议原理、组成、认证方式和过程

延伸

https的特性：加密保证安全性防窃听、认证防伪装、完整性防篡改

加密方式：混合加密，用非对称加密传输对称秘钥，用对称秘钥进行要传输的数据的加解密

认证：使用证书来对通信双方认证。

完整性：ssl提供报文摘要功能来进行完整性保护。

http也可以通过md5验证完整性，但数据篡改后也可重新生成md5，因为是明文的。https是通过ssl的报文摘要来保证完整性的，结合了加密与认证，即使加密后数据被篡改，也很难再生成报文摘要，因为不知道明文是什么。

线程池的工作原理，几个重要参数，然后给了具体几个参数分析线程池会怎么做，最后问阻塞队列的作用是什么？

线程池解决两个问题：
1. 由于减少了每个任务的调度开销，通常在执行大量异步任务时提供优秀的性能。
2. 提供了管理、调控资源的方式

Executors工厂方法：

1. newFixedThreadPool 固定size的线程池。为了满足资源管理的需求，需要限制当前线程数量的场景。适用于负载比较重的服务器。
   1. corePoolSize == maximumPoolSize
   2. keepAliveTimes = 0
   3. LinkedBlockingQueue  队列大小Integer.MAX_VALUE，等价于无界
   4. 当线程池中线程数达到corePoolSize后，新任务将在队列中等待
   5. 由于使用无界队列，运行中的线程池不会拒绝任务
2. newSingleThreadExecotor 单个线程的线程池。需要保证顺序执行任务的场景，并且在任意时间点不会有多个线程是活动的。
   1. corePoolSize = maximumPoolSize  = 1
   2. keepAliveTimes = 0
   3. LinkedBlockingQueue
   4. 如果当前线程池无线程，就创建一个线程来运行任务
   5. 当线程数达到1后，新的任务都加入到队列中
3. newCachedThreadPool 大小无界的线程池（自动资源回收？），适用于有很多短期异步执行任务的小程序，或者是负载比较轻的服务器。
   1. corePoolSize = 0, maximumPoolSize = Integer.MAX_VALUE
   2. keepAliveTimes = 60s
   3. SynchronousQueue 是一个没有容量的阻塞队列，一个插入操作必须等待另一个线程对应的移除操作
   4. 提交任务时如果有空闲线程，就空闲线程取到这个任务执行；否则创建一个线程来执行任务
   5. 适用于将主线程的任务传递给空闲线程执行



重要参数：

1. core and maximum pool sizes 
   1. corePoolSize 核心最大线程：新任务加入时，如果运行线程个数小于核心线程数，即使有其他工作线程是空闲的，也会创建新线程 -- 线程池预热
   2. maximumPoolSize 线程池最大线程：阻塞队列满时，如果运行线程数小于maximumPoolSize，才可创建新线程运行任务
   3. corePoolSize=maximumPoolSize时，等价于newFixedThreadPool
   4. maximumPoolSize=本质上无限的数（比如Integer.MAX_VALUE），等价于newCachedThreadPool ？
   5. 一般只在构造时设置这两个参数，但也可以通过两个set方法改变
   6. **这两个参数会自动调整么？**
2. On-demand construction
   1. 默认情况下，只有任务提交时才会创建线程（包括核心线程）
   2. 也可以通过prestartCoreThread或者prestartAllCoreTheads来预先创建线程。比如构建了一个阻塞队列不为空的线程池时，会想要这么做（预先创建线程）。
3. Creating new threads
   1. 默认使用defaultThreadFactory来创建线程，相同的线程组ThreadGroup、优先级priority和非守护线程状态non-daemon status.
   2. 也可以使用自定义的threadFactory，自定义线程名称、线程组、优先级等。
   3. threadFactory创建线程失败的什么东西没看懂
4. Keep-alive times
   1. keepAliveTime 如果线程数多于核心线程数，超过这个时间的空闲线程将会被停掉（指销毁掉？）
5. queuing
   1. 入队规则
6. rejected tasks 四个拒绝策略 RejectedExecutionHandler
   1. ThreadPoolExecutor.AbortPolicy 抛出RejectedExecutionException
   2. CallerRunsPolicy 调用者自身来执行
   3. DiscardPolicy 丢弃任务，任务不会被执行
   4. DiscardOldestPolicy work queue的首个任务将会被丢弃，重试添加当前任务（可能再次失败，自旋执行）
7. hook methods
   1. beforeExecute afterExecute 可用来设置运行环境，重新初始化本地线程，获取统计数据，添加日志。
   2. terminated executor终止时提供的钩子方法
8. queue maintenance getQueue可用于监控和调试当前work queue，其他用途不建议。remove和purge可用于大量任务取消时候的存储清理。
9. reclamation （清除？）一个在程序中无引用、并且无剩余线程的线程池，即使无显式shutdown关闭，也可以被清除回收。可以通过这些方式设置线程池的线程在无使用时（最终）销毁：设置keep-alivet times；使用小的核心线程数比如0，或者设置allowCoreThreadTimeOut。



ScheduledThreadPoolExcutor

延迟运行命令，或周期执行命令



LinkedBlockingQueue和DelayQueue的实现原理

1. LinkedBlockingQueue 就是生产者消费者的实现
   1. 应用了ReentrantLock（putLock & tackLock）和lock的Condition（notEmpty & notFull）
2. DelayQueue
   1. 应用了PriorityQueue，时间小的在队头
   2. ReentrantLock（lock）和Condition（available）



FutureTask是用AQS实现的 get=acquireShared，run/cancel后=release

Linux怎么查看系统负载情况？
1. uptime
2. w
3. top
查看linux系统负载情况

请详细描述springmvc处理请求全流程？
1. 通用的流程：
  1. 客户端提交请求到DispatcherServlet
  2. DispatcherServlet寻找Handler（HandlerExecutionChain）(包括handler , common interceptors和MappedInterceptor)
  3. DispatcherServlet调用controller
  4. controller调用业务逻辑，返回ModelAndView
  5. DispatcherServlet寻找ViewResolver，找到对应视图
  6. 渲染视图显示到客户端

2. restful的一些细节（上述2、3、4过程的细化，restful的mav一般是空的）：

   1. getHandler取到一个HandlerExecutionChain mappedHandler，包含URL对应的controller方法HandlerMethod，和一些interceptors
   2. HandlerMethod取到对应的handlerAdapter，数据绑定就再这个ha中做的
   3. mappedHandler执行拦截器的preHandle
   4. handlerAdapter执行controller方法，包含请求前的数据绑定（数据转换），和请求后的数据转换（转换后将数据按需要的格式写入response）
   5. mappedHandler执行拦截器的postHandle
   6. 以上过程如果有抛出异常，由全局异常处理器来处理
   7. mappedHandler触发拦截器的afterCompletion
   8. 讲一讲AtomicInteger，为什么要用CAS而不是synchronized？

查询中哪些情况不会使用索引？
1. 使用or
2. like以”%xx”开始匹配
3. 联合（复合）索引，不符合最左匹配
4. 索引列数据类型隐形转换，比如列是字符串，但用数值来查询就用不上索引
5. 在where子句中，对索引列有数学运算、或者使用函数，用不了索引
6. MySQL估计全表扫描比查询索引快时（比如数据量非常少）

[MYSQL 索引类型、什么情况下用不上索引、什么情况下不推荐使用索引](https://blog.csdn.net/kaka1121/article/details/53395628)

[MySQL性能优化的最佳21条经验](https://www.cnblogs.com/hongfei/archive/2012/10/19/2731342.html) -- 没大用

[mysql explain执行计划详解](https://blog.csdn.net/kaka1121/article/details/53394426) -- 有错字之类的

type: const 命中唯一索引或主键的时候

数据库索引，底层是怎样实现的，为什么要用B+树索引？

MySQL底层使用B+树实现的。

MyISAM引擎，B+树主索引、辅助索引叶节点是数据记录的地址，称为非聚集索引（与InnoDB区分）

InnoDB的主键索引是聚集索引，叶节点存的完整的数据记录；辅助索引，叶节点存的是主键的值。

为什么用B+树索引？

1. 数据文件比较大，一般存储在磁盘上

2. 索引的组织结构要尽量减少查找过程中磁盘IO次数。

3. 数据库系统利用磁盘预读原理，将一个节点的大小设为一个页的大小，则只需要一次IO就可以将一个节点的数据都读入



B+树只有叶子节点存放数据，非叶子节点作为索引，这样树出度大，树高小，一般3层，查询目标数据的io次数比较少，效率高。

使用节点大小正好等于磁盘一页大小的B+树，可以减少io操作次数，提高查询效率。



从数组、哈希表、二叉树等数据结构的对比来回答，见下面这篇文章

[MySQL为什么不用数组、哈希表、二叉树等数据结构作为索引呢](https://juejin.im/post/5e920646e51d4546f5790713)

[orderby底层执行过程](https://juejin.im/post/5e945b9651882573b7537c2a)

Mysql主从同步的实现原理？

原理：在主库上记录二进制日志，在备库重放日志的方式实现异步数据复制。

复制有三个步骤：
1. 主库记录二进制日志，每次准备提交事务（完成数据库更新）前先记录二进制日志（记录日志完后，再执行数据库更新）
2. 备库将主库的二进制文件复制到本地的中继日志中。
  1. 备库会启动一个工作线程，称为IO工作线程，负责和主库建立一个普通的客户端连接
  2. 如果该进程追赶上了主库，它将进入睡眠状态，直到主库有新的事件产生，会被唤醒，将接收到的事件记录到中继日志中
3. 备库的SQL线程读取中继日志并在备库执行
  1. 中继日志一般在系统缓存中，开销低，也可以根据配置选项来决定是否写入自己的二进制日志中

常见复制架构：

1. 一主多从

2. 主主

3. 环型复制

   ![wKioL1YKPpuzRxapAAKMyc9n3zQ218.jpg](../../image/wKioL1YKPpuzRxapAAKMyc9n3zQ218.jpg)







[MySQL复制详解](https://blog.51cto.com/amyhehe/1699168)

MySQL是怎么用B+树？

innodb引擎用B+树当索引，索引文件同时是数据文件。聚集索引，也就是主键索引，叶节点存储的完整行数据；辅助索引，也称为非聚集索引，叶节点存对应行记录的主键。

MyISAM引擎也是用B+树当索引，为非聚集索引，索引不是数据文件，叶节点存的是行记录的地址。

谈谈数据库乐观锁与悲观锁？
1. 悲观锁，认为操作会发生冲突，提前加锁，直到自己操作结束再释放锁。
2. MySQL的显式锁定写锁 select .. for update & 读锁 select .. lock in share mode
3. 乐观锁，认为不会发生冲突，在提交更新的时候会判断一下期间数据有没有被修改。类似于CAS操作，常用方式有版本号、时间戳。

有使用过哪些NoSQL数据库？MongoDB和Redis适用哪些场景？

工程中用过Redis，主要是小部分数据的缓存其他不太了解

NoSql not only sql 非关系型数据库

[memcache、redis、mongoDB 如何选择？](https://zhuanlan.zhihu.com/p/32940868)

~~描述分布式事务之TCC服务设计？~~
1. 不了解
2. TCC分布式事务 try - confirm - cancel

~~Redis和memcache有什么区别？Redis为什么比memcache有优势？~~

~~同19~~
~~考虑redis的时候，有没有考虑容量？大概数据量会有多少？~~

没有，公司维护的Redis组件 – redis & nosql 需要再深入一点呀

谈谈分布式锁、以及分布式全局唯一ID的实现比较？

分布式锁
1. 为什么需要分布式锁？
  1. 效率：避免不同节点重复相同的工作，这些工作会浪费资源。比如针对一个操作发多封邮件。
  2. 正确性：避免破坏正确性的发生，比如多个节点操作了同一条数据，其中一个操作结果被覆盖了，造成数据丢失。
2. 常见实现方式
  1. 数据库
    1. 表的一行数据表示一个资源，select..for update来加锁，可同时存节点信息，支持重入。
    2. 理解简单，但需要自己实现，以及维护超时、事务和异常处理等，性能局限于数据库，性能相对比较低，不适合高并发场景。
  2. zookeeper
    1. curator封装 – 具体怎么用还没看过呢
    2. Zk 排他锁和共享锁有区别。排他锁，利用zk有序节点，序号最小的节点表示获取到锁，其他未获取到锁的节点监听自己的前一个节点。（共享锁，能获取到资源都算？回家再看看。）还有个读写锁，一个节点获取读锁，只要序号小于他的都为读锁，就表示获取到读锁；一个节点获取写锁，需要自己的序号最小，才表示获取到写锁。可重入锁之类的，zk节点写值吧，原理和Java的reentrantLock类似，获取多少次，state自加多少次，解锁再一次次自减，直到state为0表示完全释放。
    3. （文章里说zk分布式锁和数据库mysql差不多。。真的么）
  3. redis setNX
    1. 自己参照一篇文章实现的比较简单，主要利用setNX，不支持重入，非公平。有超时释放，有加锁身份，解锁原子性
    2. 下面的文章里介绍的Redission。不太了解，加锁原子性lua脚本，用了hset，hashmap的结构，key是资源，value是锁定次数，可重入。。还有公平锁的实现。。。
  分布式锁

分布式全局唯一ID/分布式ID生成器 实现方式

1. uuid

   1. 缺点：长，占用空间大，间接导致数据库性能下降
   2. 缺点：不是有序的，导致索引在写的时候有过多的随机写

2. 数据库自增主键

   1. 缺点：完全依赖于数据库，有性能瓶颈
   2. 缺点：不易扩展

3. snowflake Twitter，Scala实现的...

   1. 雪花算法，带有时间戳的全局唯一ID生成算法

   2. 固定ID格式：

      1
2
3
41位的时间戳（精确到毫秒，41位的长度可使用69年）
10位的机器ID（10位长度最多支持1024个服务器节点部署）
12位的计数序列号（12位支持每节点每毫秒最多生成4096个序列号）

~~集群监控的时候，重点需要关注哪些技术指标？这些指标如何优化？~~
1. 系统指标：cpu使用率、内存使用率、机器连通性、系统负载（cpu.load）
2. 网络指标：网络流入速度、网络流出速度、网络流入包数、网络流出包数、TCP连接数、TCP Active Opens（主动打开数）、IP接收包数、IP丢包数、TCP接收包数、TCP发送包数、TCP包传输错误数、TCP重传数
3. 磁盘指标：磁盘使用率、iNode使用率、磁盘繁忙占比、磁盘读速度、磁盘写速度、磁盘读次数、磁盘写次数
4. 容器指标？：线程数[容器指标]/平均到每核、进程数[容器指标]/平均到每核….
监控知识体系

小米监控
从千万的数据到亿级的数据，会面临哪些技术挑战？你的技术解决思路？

https://zhuanlan.zhihu.com/p/51081227
最常见的数据库，如MySql、Oracle等，都采用行式存储，比较适合OLTP。如果用MySql等行数据库来实现OLAP，一般都会碰到两个瓶颈：
1. 数据量瓶颈：mysql比较适合的数据量级是百万级，再多的话，查询和写入性能会明显下降。因此，一般会采用分库分表的方式，把数据规模控制在百万级。
2. 查询效率瓶颈：mysql对于常用的条件查询，需要单独建立索引或组合索引。非索引字段的查询需要扫描全表，性能下降明显。
分表

垂直业务拆分=分库+微服务（可分库基础上再分表）

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

最近两年遇到的最大的挫折，从挫折中学到了什么？

胃炎？失眠？

生病要看病，不要自己琢磨；看病也是要厚脸皮的，多问；运动，保持良好生活习惯。

– 这么回答..太坑了吧

最近有没有学习过新技术？

zookeeper

kafka

json:Gson/jackson/fastjson

设计模式：尽量在工作中合适地应用

docker简单使用

简单说一下面向对象的特征以及六大原则

特征：
1. 封装：把客观事物封装成抽象的类
2. 抽象继承！：（实现继承or接口继承）让某个类型的对象获得另一个类型的对象的属性和方法
3. 多态：一个类实例的相同方法在不同情形有不同的表现形式。（编译多态与运行时多态）一般指运行时多态..?
  
  多态存在的必要条件：继承、重写、父类引用指向子类对象
原则：
1. 单一职责：一个类的功能要单一，不能包罗万象
2. 开放封闭：一个模块，在扩展性方面应该是开发的，在更改性方面是封闭的
3. 里氏替换：子类应当可以替换父类，并出现在父类能够出现的任何地方
4. 依赖倒置：高层次的模块不应该依赖于低层次的模块，他们都应该依赖于抽象；抽象不应该依赖于具体实现，具体实现应该依赖于抽象。
5. 接口分离：模块间要通过抽象接口隔离开，而不是通过具体的类强耦合起来，即面向接口编程。
6. 迪米特原则：一个类对自己依赖的类知道的越少越好。类间解耦，低耦合、高内聚。

谈谈final、finally、finalize的区别

final
1. 修饰类、方法或变量
2. 修饰类：表明类不能被继承
3. 方法：禁止在子类中被覆盖（private方法会隐式被指定为final）
4. 变量：
  1. 基本数据类型的变量：数值在初始化后不能更改
  2. 引用类型的变量：初始化后不能再指向另一个对象（指向的地址不可变）

finally：

一般与try catch一起使用，无论程序抛出异常或正常执行，finally块的内容一定会被执行。

最常用的地方：通过try-catch-finally来进行类似资源释放、保证解锁等动作。



finalize

Object的protected方法，子类可以覆盖该方法以实现资源清理工作，GC在回收对象之前调用该方法。

日常开发中基本不用，也不推荐使用。Java9中被标记为deprecated! -- 不想多说

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

Java中==、equals与hashCode的区别和联系

https://juejin.im/entry/59b3897b5188257e733c24eb – 后面写的比较乱

https://juejin.im/post/5a4379d4f265da432003874c – equals与hashCode

Java数据类型
1. 8种基本数据类型
  1. （整型）数值类型 byte short int long 1.2.4.8
  2. （浮点）数值类型 float double 4.8
  3. 字符型 char 2 存储 Unicode 码，用单引号赋值。
  4. 布尔类型 boolean 1
2. 3种引用类型：类、接口、数组

==

比较两个数据是否相等，基本类型比较数值是否相等，引用类型比较地址是否相等。



equals()方法

Object类型定义的，比较二者==

1
2
3
4
//object的equals方法
public boolean equals(Object obj) {
    return (this == obj);
}


想自定义对象逻辑“相等”（值相等、或内容相等）的含义时，重写equals方法。

重写equals准则：

> **自反性**：对于任何非空引用值 x，x.equals(x) 都应返回 true。

> **对称性**：对于任何非空引用值 x 和 y，当且仅当 y.equals(x) 返回 true 时，x.equals(y) 才应返回 true。

> **传递性**：对于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true， 并且 y.equals(z) 返回 true，那么 x.equals(z) 应返回 true。

> **一致性**：对于任何非空引用值 x 和 y，多次调用 x.equals(y) 始终返回 true 或始终返回 false， 前提是对象上 equals 比较中所用的信息没有被修改。

> **非空性**：对于任何非空引用值 x，x.equals(null) 都应返回 false。



一般只判断同类型的对象

主要不要违反了对称性、传递性



hashCode()方法

1
public native int hashCode();


equals的对象hashcode一定相等，hashcode相同的对象不一定equals

为什么对象的hashcode会相同？

hashcode的实现取决于jvm，比较典型的一种是基于内存地址进行哈希计算，也有基于伪随机的实现。

哈希计算会存在哈希碰撞。

https://juejin.im/entry/597937cdf265da3e114cd300

谈谈Java容器ArrayList、LinkedList、HashMap、HashSet的理解，以及应用场景

| | ArrayList | LinkedList | HashMap | HashSet |
| ————– | —————– | —————– | ———– | —————– |
| 数据结构 | （可变）数组 | （双向）链表 | 数组+红黑树 | 底层实现是HashMap |
| 插入时间复杂度 | o(n) | o(1) | | |
| 删除时间复杂度 | o(n) | o(1) | | |
| 访问时间复杂度 | o(1) 支持随机访问 | o(n) 不支持随机.. | | |
| 应用场景 | 经常访问 | 经常修改 | 映射..？ | 去重 |

谈谈线程的基本状态，其中的wait() sleep() yield()方法的区别。

线程的基本状态

新建、运行（运行中、就绪）、等待、超时等待、阻塞、终止

wait()

Object的方法，在某个对象上等待，等待这个对象将它唤醒，释放锁。运行->等待/超时等待

sleep()

Thread的静态方法，当前线程睡眠，不释放锁。运行->超时等待

yield()

Thread的方法，让出当前cpu。还是运行这个大状态，从运行中变成就绪状态。

JVM性能调优的监控工具了解那些？

jps jstack jmap

jps [option]

输出Java进程信息

1
2
3

jps -ml
111957 org.apache.catalina.startup.Bootstrap -config /export/Domains/testenv.jd.local/server1/conf/server.xml start
136044 sun.tools.jps.Jps -ml

jstack [option] pid

输出某个进行内的线程栈信息

1
2
3

jstack 111957 | grep 1b6d0
"System_Clock" #307 daemon prio=5 os_prio=0 tid=0x00007f71b53f3800 nid=0x1b6d0 runnabl
e [0x00007f72606d9000]

1
2

-l long listings，会打印出额外的锁信息，在发生死锁时可以用<strong>jstack -l pid</strong>来观察锁持有情况  
-m mixed mode，不仅会输出Java堆栈信息，还会输出C/C++堆栈信息（比如Native方法）

jmap [option] pid

输出某个进程内的堆信息：JVM版本、使用的GC算法、堆配置、堆内存使用情况

jmap -heap 111957
Attaching to process ID 111957, please wait...
Debugger attached successfully.
Server compiler detected.
JVM version is 25.20-b23

using thread-local object allocation.
Parallel GC with 43 thread(s)

Heap Configuration:
   MinHeapFreeRatio         = 0
   MaxHeapFreeRatio         = 100
   MaxHeapSize              = 2147483648 (2048.0MB)
   NewSize                  = 357564416 (341.0MB)
   MaxNewSize               = 715653120 (682.5MB)
   OldSize                  = 716177408 (683.0MB)
   NewRatio                 = 2
   SurvivorRatio            = 8
   MetaspaceSize            = 21807104 (20.796875MB)
   CompressedClassSpaceSize = 1073741824 (1024.0MB)
   MaxMetaspaceSize         = 17592186044415 MB
   G1HeapRegionSize         = 0 (0.0MB)

Heap Usage:
PS Young Generation
Eden Space:
   capacity = 353370112 (337.0MB)
   used     = 28186432 (26.88067626953125MB)
   free     = 325183680 (310.11932373046875MB)
   7.976461801047849% used
From Space:
   capacity = 2097152 (2.0MB)
   used     = 1736768 (1.65631103515625MB)
   free     = 360384 (0.34368896484375MB)
   82.8155517578125% used
To Space:
   capacity = 2097152 (2.0MB)
   used     = 0 (0.0MB)
   free     = 2097152 (2.0MB)
   0.0% used
PS Old Generation
   capacity = 869793792 (829.5MB)
   used     = 160875768 (153.42308807373047MB)
   free     = 708918024 (676.0769119262695MB)
   18.495851485681793% used

36932 interned Strings occupying 3347024 bytes.

输出堆内存中对象个数、大小统计直方图

1	jmap -histo:live 111957 \| less

B  byte  
C  char  
D  double  
F  float  
I  int  
J  long  
Z  boolean  
[  数组，如[I表示int[]  
[L+类名 其他对象

dump出堆信息，再使用jhat或其他工具分析

1
2
3

jmap -dump:format=b,file=dump.dat 111957
jhat -port 8888 dump.dat
# 浏览器输入 ip:port可访问

jstat [ generalOption | outputOptions vmid [interval[s|ms] [count]] ]

jvm统计信息

vmid是Java虚拟机ID，在Linux/Unix系统上一般就是进程ID。interval是采样时间间隔。count是采样数目。

jstat -gc 111957 250 6 # gc信息
 S0C    S1C    S0U    S1U      EC       EU        OC         OU       MC     MU    CCS
C   CCSU   YGC     YGCT    FGC    FGCT     GCT
2048.0 2048.0  0.0    0.0   345088.0 148448.5 1397248.0   119834.5  80640.0 78303.8 84
48.0 7919.0    133    8.230   5     11.160   19.390
2048.0 2048.0  0.0    0.0   345088.0 148457.6 1397248.0   119834.5  80640.0 78303.8 84
48.0 7919.0    133    8.230   5     11.160   19.390
2048.0 2048.0  0.0    0.0   345088.0 148457.6 1397248.0   119834.5  80640.0 78303.8 84
48.0 7919.0    133    8.230   5     11.160   19.390
2048.0 2048.0  0.0    0.0   345088.0 150425.8 1397248.0   119834.5  80640.0 78303.8 84
48.0 7919.0    133    8.230   5     11.160   19.390
2048.0 2048.0  0.0    0.0   345088.0 150425.8 1397248.0   119834.5  80640.0 78303.8 84
48.0 7919.0    133    8.230   5     11.160   19.390
2048.0 2048.0  0.0    0.0   345088.0 150427.8 1397248.0   119834.5  80640.0 78303.8 84
48.0 7919.0    133    8.230   5     11.160   19.390

S0C、S1C、S0U、S1U：Survivor 0/1区容量（Capacity）和使用量（Used）  
EC、EU：Eden区容量和使用量  
OC、OU：年老代容量和使用量  
PC、PU：永久代容量和使用量  
YGC、YGT：年轻代GC次数和GC耗时  
FGC、FGCT：Full GC次数和Full GC耗时  
GCT：GC总耗时

简单谈谈JVM内存模型，以及volatile关键字

运行时数据区域包括堆、方法区（包括运行时常量池）、Java虚拟机栈、本地方法栈、程序计数器、直接内存。
1. 堆：所有对象在这里分配内存【所有线程共享】
2. 方法区：存放已被加载的类信息、常量、静态变量、即时编译器编译后的代码等信息【所有线程共享】
3. Java虚拟机栈：生命周期与线程相同，描述的是Java方法执行时候的内存模型，每个方法被执行的时候都会创建一个栈帧，存储局部变量表、操作数栈、常量池引用（动态链接）、方法出口等信息。【线程私有】
4. 本地方法栈：与虚拟机栈类似，只不过方法是本地方法【线程私有】
5. 程序计数器：记录正在执行的虚拟机字节码指令的地址（如果是本地方法则为空）【线程私有】
6. 直接内存：JDK1.4引入NIO，可以使用native函数库分配堆外内存，然后通过堆内的DirectByteBuffer作为这部分内存的引用、进行操作。可以提高性能，避免堆外内存和堆内内存的来回拷贝。

**Java内存模型 JMM**

**Java memory model**

用来屏蔽不同硬件和操作系统的内存访问差异，实现Java在各平台上一致的内存访问效果。

JMM规定，所有变量都存在主内存中（类似于操作系统的普通内存）；每个线程有自己的工作内存（=CPU的寄存器或高速缓存），保存了该线程使用的变量的主内存副本拷贝。线程只能操作工作内存。

存在缓存不一致问题。



<img src="../../image/image-20200514161253557.png" alt="image-20200514161253557" style="zoom:30%;" />



**主内存与工作内存交互操作**

<img src="../../image/image-20200514163326711.png" alt="image-20200514163326711" style="zoom:50%;" />

**内存模型三大特性**

1. 原子性：上述8个操作是原子的（double&long等64位变量的操作，JVM允许非原子），一系列操作合起来其实是非原子的

2. 可见性：指一个线程修改了共享变量的值，其他线程可以立即得知这个修改。JMM是通过变量修改后将新值同步到主内存（并使其他工作内存中的这个变量副本无效）、在变量读取前从主内存刷新变量值来实现的。

3. 有序性：从本线程来看，所有操作都是有序的；从线程外看，操作是无序的，因为发生了指令重排。JMM允许编译器和处理器进程指令重排，重排不会影响到单线程的执行结果，但会影响多线程的执行正确性。

   volatile关键字通过添加内存屏障的方式来禁止指令重排（重排序时不能把屏障后的指令重排到屏障前）



**先行发生原则**

1. 单一线程原则：在一个线程内，在程序前面的操作先行发生于后面的操作。
2. 管程锁定原则：一个 unlock 操作先行发生于后面对同一个锁的 lock 操作。
3. volatile变量规则：对一个 volatile 变量的写操作先行发生于后面对这个变量的读操作。
4. 线程启动规则：Thread 对象的 start() 方法调用先行发生于此线程的每一个动作。
5. 线程加入规则：Thread 对象的结束先行发生于 join() 方法返回。
6. 线程中断规则：对线程 interrupt() 方法的调用先行发生于被中断线程的代码检测到中断事件的发生。
7. 对象终结规则：一个对象的初始化完成(构造函数执行结束)先行发生于它的 finalize() 方法的开始。
8. 传递性：如果操作 A 先行发生于操作 B，操作 B 先行发生于操作 C，那么操作 A 先行发生于操作 C。



[volatile关键字](https://juejin.im/post/5a2b53b7f265da432a7b821c#heading-0)

**volatile关键字**

1. 保证了不同线程对该变量操作的内存可见性
2. 禁止指令重排序，保证（volatile读写）有序性

垃圾收集器与内存分配策略【祥见JVM的几个大知识点】

垃圾收集器

内存分配策略

Minor GC 和 Full GC
1. Minor GC:回收新生代，因为新生代对象存活时间很短，因此 Minor GC 会频繁执行，执行的速度一般也会比较快。
2. Full GC:回收老年代和新生代，老年代对象其存活时间长，因此 Full GC 很少执行，执行速度会比 Minor GC 慢很多。

分配策略

1. 对象优先在 Eden 分配

   大多数情况下，对象在新生代 Eden 上分配，当 Eden 空间不够时，发起 Minor GC。 

2. 大对象直接进入老年代

   大对象是指需要连续内存空间的对象，最典型的大对象是那种很长的字符串以及数组。

   经常出现大对象会提前触发垃圾收集以获取足够的连续空间分配给大对象。

   -XX:PretenureSizeThreshold，大于此值的对象直接在老年代分配，避免在 Eden 和 Survivor 之间的大量内存复制。

3. 长期存活的对象进入老年代

   为对象定义年龄计数器，对象在 Eden 出生并经过 Minor GC 依然存活，将移动到 Survivor 中，年龄就增加 1 岁， 增加到一定年龄则移动到老年代中。

   -XX:MaxTenuringThreshold 用来定义年龄的阈值。

4. 动态对象年龄判定

   虚拟机并不是永远要求对象的年龄必须达到 MaxTenuringThreshold 才能晋升老年代，如果在 Survivor 中相同年龄 所有对象大小的总和大于 Survivor 空间的一半，则年龄大于或等于该年龄的对象可以直接进入老年代，无需等到 MaxTenuringThreshold 中要求的年龄。

5. 空间分配担保

   在发生 Minor GC 之前，虚拟机先检查老年代最大可用的连续空间是否大于新生代所有对象总空间，如果条件成立的话，那么 Minor GC 可以确认是安全的。

   如果不成立的话虚拟机会查看 HandlePromotionFailure 的值是否允许担保失败，如果允许那么就会继续检查老年代 最大可用的连续空间是否大于历次晋升到老年代对象的平均大小，如果大于，将尝试着进行一次 Minor GC;如果小 于，或者 HandlePromotionFailure 的值不允许冒险，那么就要进行一次 Full GC。



**Full GC 的触发条件**

对于 Minor GC，其触发条件非常简单，当 Eden 空间满时，就将触发一次 Minor GC。而 Full GC 则相对复杂，有以下条件:

1. 调用 System.gc()
    只是建议虚拟机执行 Full GC，但是虚拟机不一定真正去执行。不建议使用这种方式，而是让虚拟机管理内存。 

2. 老年代空间不足

   老年代空间不足的常见场景为前文所讲的大对象直接进入老年代、长期存活的对象进入老年代等。

   为了避免以上原因引起的 Full GC，应当尽量不要创建过大的对象以及数组。除此之外，可以通过 -Xmn 虚拟机参数 调大新生代的大小，让对象尽量在新生代被回收掉，不进入老年代。还可以通过 -XX:MaxTenuringThreshold 调大对 象进入老年代的年龄，让对象在新生代多存活一段时间。

3. 空间分配担保失败
    使用复制算法的 Minor GC 需要老年代的内存空间作担保，如果担保失败会执行一次 Full GC。

4. JDK 1.7 及以前的永久代空间不足

   在 JDK 1.7 及以前，HotSpot 虚拟机中的方法区是用永久代实现的，永久代中存放的为一些 Class 的信息、常量、静 态变量等数据。

   当系统中要加载的类、反射的类和调用的方法较多时，永久代可能会被占满，在未配置为采用 CMS GC 的情况下也 会执行 Full GC。如果经过 Full GC 仍然回收不了，那么虚拟机会抛出 java.lang.OutOfMemoryError。

   为避免以上原因引起的 Full GC，可采用的方法为增大永久代空间或转为使用 CMS GC。

5. Concurrent Mode Failure

   执行 CMS GC 的过程中同时有对象要放入老年代，而此时老年代空间不足(可能是 GC 过程中浮动垃圾过多导致暂时 性的空间不足)，便会报 Concurrent Mode Failure 错误，并触发 Full GC。

垃圾收集算法【见Java虚拟机】
1. 标记-清除
2. 标记-整理
3. 复制
4. 分代收集
  1. 新生代：复制算法
  2. 老年代：标记-清除 or 标记整理

**虚拟机的几大问题**

1. 运行时数据区域
2. 垃圾收集
   1. 对象可达
   2. 引用类型
   3. GC Roots
   4. 算法
   5. 收集器
3. 内存分配与回收策略（回收主要是老年代的触发条件）
4. 类加载机制

MySQL几种常用的存储引擎区别

InnoDB与MyISAM比较典型的几个区别：
1. innodb支持事务、MVCC快照读、行级锁粒度、hash索引、聚集索引、支持外键
2. myisam支持全文索引、空间索引、数据压缩
3. innodb存储成本高、内存成本高、插入速度低，myisam反过来

来源：MySQL技术内幕

 <img src="../../image/image-20200515154754678.png" alt="image-20200515154754678" style="zoom:50%;" />

数据库的隔离级别
1. 未提交读 read uncommited
2. 读提交 rc read commited
3. 可重复读rr repeatable read
4. 可串行化 serializable

5亿整数的大文件，怎么排？

内存估算

假设每个数最多64位，8字节

5,0000,0000x8 ~ 500MBx8 = 4000MB ~ 4G

假设5亿数不重复

内存装的下：

直接快排，得算好久吧..



[5亿个整数排序](https://juejin.im/post/5e435f236fb9a07cbc268994)

内存装不下：

1. 读文件，数取模%4000存入4000个小文件，每个文件约1M
2. 读每个小文件，快排
3. 多路归并排序输出



[海量数据处理思路](https://juejin.im/entry/5a27cb796fb9a045104a5e8c)

1. 分治/hash映射 + hash统计 + 堆/快排/归并排序
   1. hash分成n个小文件，满足内存要求：好处是，可以让相同的数或字符串进入同一个小文件
   2. 小文件排序或统计，或没有本步骤，输出另一份小文件
   3. 最终要求
      1. 全排序：使用多路归并
      2. 找top k：直接小顶堆（找最大top k）or大顶堆；或者每个小文件先找top k，再对比n个top k
      3. 找两文件不同：两两小文件set对比

2. 数据结构
   1. bitmap 可用于整数去重等
   2. [trie树](https://juejin.im/post/5c2c096251882579717db3d2) 名字来源retrieval

~~Java内存模型~~【重复】
~~full gc怎么触发？~~【见35】
~~gc算法~~【见36】
~~JVM回收策略~~【内存分配和回收策略，见Java虚拟机】
ClassLoader原理和应用
1. ClassLoader的作用
  1. 加载class字节码文件到jvm
  2. 确认每个类应由那个类加载器加载，这也影响到两个类是否相等的判断，影响的方法有equals()、isAssignableFrom()、isInstance()以及instanceof关键字
2. 加载的类存放在哪里？
  
  jdk8之前在方法区，8之后在元数据区。
3. 什么时候触发类加载？
  1. 隐式加载
    1. 遇到new、getstatic、putstatic、invokestatic4条字节码指令时
    2. 对类进行反射调用时
    3. 当初始化一个类时，如果父类还没初始化，优先加载父类并初始化
    4. 虚拟机启动时，需指定一个包含main函数的主类，优先加载并初始化这个主类
  2. 显式加载
    1. 通过ClassLoader的loadClass方法
    2. 通过Class.forName
    3. 通过ClassLoader的findClass方法
4. 有哪些类加载器ClassLoader？
  1. Bootstrap ClassLoader：加载JVM自身工作需要的类，由JVM自己实现。加载JAVA_HOME/jre/lib下的文件
  2. ExtClassLoader：是JVM的一部分，由sun.misc.Launcher$ExtClassLoader实现，会加载JAVA_HOME/jre/lib/ext下的文件，或由System.getProperty("java.ext.dirs")指定的目录下的文件
  3. AppClassLoader：应用类加载器，由sun.misn.Launcher$AppClassLoader实现，加载System.getProperty("java.class.path")目录下的文件，也就是classpath路径。
5. 双亲委派模型
  1. 原理：当一个类加载器收到类加载请求时，如果存在父类加载器，会先由父类加载器进行加载，当父类加载器找不到这个类时（根据类的全限定名称。找不到是由于，每个类有自己的加载路径。），当前类加载器才会尝试自己去加载。
  2. 为什么使用双亲委派模型？它可以解决什么问题？
    
    双亲委派模型能够保证类在内存中的唯一性。
    
    假如没有双亲委派模型，用户自己写了个全限定名为java.lang.Object的类，并用自己的类加载器去加载，同时BootstrapClassLoader加载了rt.jar包中的jdk本身的java.lang.Object，这样内存中就存在两份Object类了，会出现很多问题，例如根据全限定名无法定位到具体的类。

高吞吐量的话用哪种gc算法

高吞吐量，如果指cpu多用于用户程序，需要停顿时间比较短的收集器，新生代在服务端一般用Parallel Scavenge，算法也是复制算法。

复制算法的性能比较高。

HashMap
1. 查找
  1. 根据hash定位槽
  2. 在槽中查找给定key（hash相等、key相等），找到直接返回，否则最后返回null
    1. 若槽节点key相等，返回槽节点
    2. 若槽节点为树节点，委托给树查找
    3. 遍历链表查找

2. 遍历

   从`index = 0, table[index]`开始，找到一个不为null的槽，遍历链表



3. 插入

   1. 如果table为空，或长度为0，初始化。（默认loadFactor为0.75，默认capacity为16（capacity是table的长度），threshold一般为capacity*loadFactor。）

   2. 通过hash定位槽，如果槽为空，构造新节点赋值给槽

   3. 若槽不为空，则在槽的链表或树中找到key相同的节点，替换节点值为新值；或是没有key相同的节点，就在树中或链表尾部加入新节点；若链表加入新节点后长度达到8（槽不算，aka槽下原有7个节点），则进行红黑树转化

   4. 如果是新加入节点，modCount、元素个数size自增1，如果元素个数超过阈值，则进行扩容



4. 扩容

    1. 计算新容量newCap和新阈值newThr（ps: 当容量已到最大值时，不再扩容；2倍扩容；）

    2. 创建新的数组，赋值给table

    3. 将键值对重新映射到新数组上

        1. 如果无链表，直接根据`hash&(newCap-1)`定位

        2. 如果是树节点，委托红黑树来拆分和重新映射

        3. 为链表，根据`hash&oldCap`的值分成0、1两组，映射到j和j+oldCap（0低位，1高位）（**链表顺序不变**）



 5. 删除

    1. 定位到槽

    2. 找到删除节点

    3. 删除节点，并修复链表或红黑树



6. 链表树化

   1. 链表树化有两个条件，不满足采用扩容，满足再扩容
   2. 树化时，将Node节点替换为TreeNode，保留next信息
   3. 替换后，再从head开始，进行红黑树化（标记红黑节点、父子节点，如果root节点不是first节点，再修正next和prev？）【链表转成红黑树后，原链表的顺序仍然会被引用仍被保留了（红黑树的根节点会被移动到链表的第一位）】

   在扩容过程中，树化要满足两个条件：

   1. 链表长度大于等于 TREEIFY_THRESHOLD 8 

   2. 桶数组容量大于等于 MIN_TREEIFY_CAPACITY 64



7. 红黑树拆分（扩容时候）

   红黑树中保留了next引用，拆分原理和链表相似

   1. 根据hash拆分成两组（这时候会生成新的next关系）

   2. 各组内根据情况，链化或者重新红黑树化



8. 红黑树链化

   将TreeNode替换为Node

ConcurrentHashMap

相比较HashMap，主要是增加了写操作时候的同步处理。扩容迁移时，多个线程帮助迁移。

1. 为什么要用synchronized代替ReentrantLock？

   1. 优化后的synchronized性能与ReentrantLock差不多，基于JVM也保证synchronized在各平台上的使用一致。

   2. 锁粒度降低了；在大量数据操作下，基于api的ReentrantLock会有更大的内存开销。



2. sizeCtl

   1. 默认为0

   2. 当table为null时，持有一个initial table size用于初始化

   3. 当sizeCtl<0时

      1. -1表示正在初始化

      2. 非-1的负数

         1
2
3
（sizeCtl的低16位-1）表示有多少个线程参与扩容迁移
 sizeCtl的高16位
-(1 + the number of active resizing threads)

sizeCtl>0时，(n << 1) - (n >>> 1) = 0.75n （表示阈值，超过阈值需要扩容）

插入
1. 计算hash
2. 循环执行
  1. 如果数组为空，初始化initTable
    1. 如果hash定位到的槽为空，CAS替换为新节点，退出循环
    2. 如果槽不为空，节点hash为-1，说明正在迁移，helpTransfer
    3. 槽不为空，且不在迁移，那么，对头节点加锁，链表或红黑树形式插入或更新节点
3. addCount

迁移

transfer的第二个参数为空的时候，触发扩容，创建nextTable，在addCount和tryPresize中有这样的调用。

addCount是size不精确情况下，可能触发扩容；tryPresize是已知精确size的情况下做扩容。
1. 计算步长stride
  1. 如果nextTab未创建，则创建之，并赋给nextTable
  2. 循环迁移
    1. 分配迁移区间i和bound（i从前往后，bound = i - stride + 1`，总之就是stride）
    2. 如果区间已达边界，将sc减1，表示本线程退出迁移。如果是最后一个迁移线程，标记finish和advance为true，进入下一循环recheck；非最后线程，直接退出方法。
    3. 如果finish为true，table = nextTab; sizeCtl = (n << 1) - (n >>> 1);，退出
    4. 若未达边界，且槽为空，CAS槽为fwd，进入下一循环
    5. 槽不为空，且槽已经是fwd，进入下一循环
    6. 最后一种情形，进行迁移
      1. 为链表，根据节点hash二进制第k位为0或1分成两组（n=2^k），1连接到高位槽上
      2. 为红黑树，分组同链表，分好的组根据节点个数判断是否链化或新生成红黑树

volatile的底层如何实现，怎么就能保住可见性了？

见【34 JMM与volatile】

有参与过开源的项目吗？

米有！

~~线程池原理，拒绝策略，核心线程数~~ 见【11】
1亿个手机号码，判断重复

不允许有误差的：
1. hash到n个小文件中
2. 每个文件做统计
3. 个数大于1的是重复的

允许有误差的：

布隆过滤器

线程之间的交互方式有哪些？有没有线程交互的封装类？

线程之间的协作
1. join() 在线程中调用另一个线程的join()方法，会将本线程挂起，直到目标线程结束
2. wait() notify() notifyAll()
  1. 调用 wait() 使得线程等待某个条件满足，线程在等待时会被挂起，当其他线程的运行使得这个条件满足时，其它线程会调用 notify() 或者 notifyAll() 来唤醒挂起的线程。
  2. 属于Object（不是Thread）
3. await() signal() signalAll()
  1. java.util.concurrent 类库中提供了 Condition 类来实现线程之间的协调，可以在 Condition 上调用 await() 方法使线程等待，其它线程调用Condition的 signal() 或 signalAll() 方法唤醒等待的线程。

线程交互的封装类

CountDownLatch

用来控制一个线程等待多个线程。
维护了一个计数器 cnt，每次调用 countDown() 方法会让计数器的值减 1，减到 0 的时候，那些因为调用 await() 方法而在等待的线程就会被唤醒。

 public class CountdownLatchExample {
    public static void main(String[] args) throws InterruptedException {
        final int totalThread = 10;
        CountDownLatch countDownLatch = new CountDownLatch(totalThread);
        ExecutorService executorService = Executors.newCachedThreadPool();
        for (int i = 0; i < totalThread; i++) {
            executorService.execute(() -> {
                System.out.print("run..");
                countDownLatch.countDown();
}); }
        countDownLatch.await();
        System.out.println("end");
        executorService.shutdown();
} }

run..run..run..run..run..run..run..run..run..run..end

等待所有run结束

CyclicBarrier

用来控制多个线程互相等待，只有当多个线程都到达时，这些线程才会继续执行。
和 CountdownLatch 相似，都是通过维护计数器来实现的。线程执行 await() 方法之后计数器会减 1，并进行等待，直到计数器为 0，所有调用 await() 方法而在等待的线程才能继续执行。
CyclicBarrier 和 CountdownLatch 的一个区别是，CyclicBarrier 的计数器通过调用 reset() 方法可以循环使用，所以它才叫做循环屏障。

public class CyclicBarrierExample {
    public static void main(String[] args) {
        final int totalThread = 10;
        CyclicBarrier cyclicBarrier = new CyclicBarrier(totalThread);
        ExecutorService executorService = Executors.newCachedThreadPool();
        for (int i = 0; i < totalThread; i++) {
            executorService.execute(() -> {
                System.out.print("before..");
                try {
                    cyclicBarrier.await();
                } catch (InterruptedException | BrokenBarrierException e) {
                    e.printStackTrace();
                }
                System.out.print("after..");
            });
}
        executorService.shutdown();
    }
}

before..before..before..before..before..before..before..before..before..before..after..after..after..after..after..after..after..after..after..after..

等待所有before结束

3. Semaphore

   1. Semaphore 类似于操作系统中的信号量，可以控制对互斥资源的访问线程数。

   2. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class SemaphoreExample {
    public static void main(String[] args) {
        final int clientCount = 3;
        final int totalRequestCount = 10;
        Semaphore semaphore = new Semaphore(clientCount);
        ExecutorService executorService = Executors.newCachedThreadPool();
        for (int i = 0; i < totalRequestCount; i++) {
            executorService.execute(()->{
                try {
                    semaphore.acquire();
                    System.out.print(semaphore.availablePermits() + " ");
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    semaphore.release();
                }
}); }
        executorService.shutdown();
    }
}
1 0 1 1 1 2 2 2 0 1


      有限个资源

两次点击，怎么防止重复下订单？

两次点击的场景
1. 没有刷新和前端控制，同一个按钮点了两次
2. 网络问题以为失败（其实成功了）又提交了一次
3. rpc等重试服务
4. 刷新前后各点一次（或者表单刷新又提交了一次）
5. 点了后退按钮，再前进
处理方案：
1. 前端
  1. 弹出确认界面，或disable入口并倒计时等
2. 后端
  1. 约定【所谓重复订单，需要定义这是相同的订单】，需要和客户端配合实现
    1. 比如支付可以用订单ID作判断
    2. 如果是下单，可以用uuid或服务端先生成一个全局唯一的订单ID，客户端如果未接收到下单成功的响应，多次重试都用这一个订单ID来提交。（如果是刷新，需要客户端去服务端请求最新购物车数据，已成功下单的商品已被移除；如果是未刷新页面的重试，则使用同一个订单ID；或者提示用户刷新、提示是否重试）
  2. 后端的去重判断方式 https://www.cnblogs.com/jett010/articles/9056567.html – 本质上分布式锁的应用
    1. 基于数据库中对应订单ID的状态做判断，ID已存在（下单），或者状态已变更（修改订单，比如取消、退款等）。如果查询和更新是分开的两个操作，会存在时间差，比如查询完后状态被别的线程修改了，可以用加数据库锁的方式解决这个问题（悲观锁或乐观锁）
    2. 利用数据库唯一性索引，性能比较低
    3. Redis分布式锁，key是订单ID，要点是加锁和解锁的原子性
    4. ps redis的计数器是原子操作 https://redis.io/commands/incr

~~数据库表设计，索引~~ 【explain分析也看看】
Redis的缓存淘汰策略、更新策略
1. 过期策略
  1. 定期删除：默认每隔100ms随机抽取一些设置了过期时间的key，检查是否过期，如果过期就删除（因为全表扫描非常耗时、耗性能，所以是随机，也因此要配合惰性删除）
  2. 惰性删除：在客户端要获取某个key时，判断key是否设置过期以及是否过期，如果过期先删除
2. 内存淘汰策略
  
  Redis在使用内存达到某个阈值（通过maxmemory配置)的时候，就会触发内存淘汰机制，选取一些key来删除。
  1
  2
  # maxmemory <bytes> 配置内存阈值
  # maxmemory-policy noeviction
  1. noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。默认策略
  2. allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。
  3. allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。
  4. volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。
  5. volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。
  6. volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。
  如何选取合适的策略？比较推荐的是两种lru策略。根据自己的业务需求。如果你使用Redis只是作为缓存，不作为DB持久化，那推荐选择allkeys-lru；如果你使用Redis同时用于缓存和数据持久化，那推荐选择volatile-lru。
  
  redis过期策略和内存淘汰策略
  
  java实现LRU

dubbo、netty、RPC介绍原理

https://juejin.im/post/5e215783f265da3e097e9679
1. RPC
  1. remote procedure call 远程过程调用，是一种进程间的通信方式，是一种技术思想，而不是规范
  2. 一次完整的rpc调用流程。RPC的目标是把2-8封装起来，对用户透明。
    
    (1):服务消费方(client)以本地调用方式调用服务。
    
    (2):client stub接收到调用后负责将方法、参数等组装成能够进行网络传输的消息体。
    
    (3):client stub找到服务地址，并将消息发送到服务端。
    
    (4):server stub收到消息后进行解码。
    
    (5):server stub根据解码结果调用本地的服务。
    
    (6):本地服务执行并将结果返回给server stub。
    
    (7):server stub将返回结果打包成消息并发送至消费方。
    
    (9):client stub接收到消息，并进行解码。
    
    (9):服务消费方得到最终结果。
  3. 决定rpc效率的两个重要因素：通信效率，序列化和反序列化效率
  4. 常见rpc框架：dubbo、gRPC、Thrift、HSF（high speed service framework）

2. netty [理解netty](https://juejin.im/post/5bdaf8ea6fb9a0227b02275a)

   1. netty是一个异步事件驱动的网络应用程序框架，是基于NIO的多路复用模型实现的。

   2. 传统HTTP服务

      【HTTP服务器之所以称为HTTP服务器，是因为编码解码协议是HTTP协议，如果协议是Redis协议，那它就成了Redis服务器，如果协议是WebSocket，那它就成了WebSocket服务器，等等。 使用Netty可以定制编解码协议，实现自己的特定协议的服务器。】

      1. 创建一个ServerSocket，监听并绑定一个端口
      2. 一系列客户端来请求这个端口
      3. 服务器使用Accept，获得一个来自客户端的Socket连接对象
      4. 启动一个新线程处理连接
         1. 读Socket，得到字节流
         2. 解码协议，得到HTTP请求对象
         3. 处理HTTP请求，得到一个结果，封装成一个HTTPResponse对象
         4. 编码协议，将结果序列化字节流写入Socket，发给客户端
      5. 循环步骤3

   3. NIO

      1. 不是Java独有的概念，NIO代表IO多路复用。

      2. 由操作系统提供的功能，早期select，后期linux-epoll/max-kqueue。一般就说是epoll（没人用mac当服务器）

      3. Netty基于Java NIO进行了封装，提供易于操作的使用模式和接口。

      4. BIO (Blocking IO)，如何理解blocking

         1. 服务端监听时，accept是阻塞的，只有新连接来了，accept才会返回，主线程才能继续
         2. 读写Socket时，read是阻塞的，只有请求消息来了（需要读完吗？），read才能返回，子线程才能继续处理
         3. 读写Socket时，write是阻塞的，只有客户端把消息接收了（客户端把消息接收了是什么表现？），write才能返回，子线程才能继续

      5. NIO利用**事件机制**（=事件驱动机制）实现非阻塞。【可以用一个线程把Accept，读写操作，请求处理的逻辑全干了。如果什么事都没得做，它也不会死循环，它会将线程休眠起来，直到下一个事件来了再继续干活，这样的一个线程称之为NIO线程。】

         伪代码

         1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while true {
    events = takeEvents(fds)  // 获取事件，如果没有事件，线程就休眠
    for event in events {
        if event.isAcceptable {
            doAccept() // 新链接来了
        } elif event.isReadable {
            request = doRead() // 读消息
            if request.isComplete() {
                doProcess()
            }
        } elif event.isWriteable {
            doWrite()  // 写消息
        }
    }
}


   4. Reactor（基于事件驱动）线程模型

      【netty可以基于以下模型灵活配置，比较常见的是用第三种。】

      【在Netty里面，Accept连接可以使用单独的线程池去处理，读写操作又是另外的线程池来处理。】

      【Accept连接和读写操作也可以使用同一个线程池来进行处理。请求处理逻辑既可以使用单独的线程池进行处理，也可以跟读写线程放在一块处理。】

      【线程池中的每一个线程都是NIO线程。用户可以根据实际情况进行组装，构造出满足系统需求的高性能并发模型。】

      1. Reactor单线程模型。一个NIO线程+一个accept线程。reactor线程负责分发，read、decode等操作都由其他线程处理。就和上面的伪代码差不多。

         ![image-20200523181425912](../../image/image-20200523181425912.png)

      2. Reactor多线程模型。相比上一种，【其他线程】由线程池来托管。

         ![image-20200523181750089](../../image/image-20200523181750089.png)

      3. Reactor主从模型。多个acceptor的NIO线程池用于接收客户端的连接。

         ![image-20200523181851749](../../image/image-20200523181851749.png)

   5. TCP粘包拆包

      1. 现象

         1. 假设使用netty在客户端重复写100次数据"你好，我的名字是xxx!"给服务端，用ByteBuf存放这个数据
         2. 服务端接收后输出，一般存在三种情况
            1. 完整的一个字符串
            2. 字符串多了
            3. 字符串少了

      2. 原因：尽管client按照ByteBuf为单位发送数据，server按照ByteBuf读取，但操作系统底层是tcp协议，按照字节发送和接收数据，在netty应用层，重新拼装成的ByteBuf与客户端发送过来的ByteBuf可能不是对等的。

         因此，我们**需要自定义协议来封装和解封应用层的数据包**。

      3. netty中定义好的拆包器

         1. 固定长度的拆包器 FixedLengthFrameDecoder
         2. 行拆包器 LineBasedFrameDecoder
         3. 分隔符拆包器 DelimiterBasedFrameDecoder （行拆包器的通用版本，可自定义分隔符）
         4. 长度域拆包器 LengthFieldBasedFrameDecoder （最通用，在协议中包含长度域字段）

   6. 零拷贝

      1. 传统方式的拷贝

         `File.read(bytes)`
         `Socket.send(bytes)`

         需要四次数据拷贝和四次上下文切换

         1. 数据从磁盘读取到内核的read buffer

         2. 数据从内核缓冲区拷贝到用户缓冲区

         3. 数据从用户缓冲区拷贝到内核的socket buffer

         4. 数据从内核的socket buffer拷贝到网卡接口（硬件）的缓冲区

      2. 零拷贝的概念

         1. 上面的第二步和第三步是没有必要的，通过java的FileChannel.transferTo方法，可以避免上面两次多余的拷贝（需要操作系统支持）

         2. 调用transferTo,数据从文件由DMA引擎拷贝到内核read buffer

            接着DMA从内核read buffer将数据拷贝到网卡接口buffer

            上面的两次操作都不需要CPU参与，达到了零拷贝。

      3. Netty中的零拷贝

         体现在三个方面：

         1. bytefuffer

            Netty发送和接收消息主要使用bytebuffer，bytebuffer使用直接内存（DirectMemory）直接进行Socket读写。

            原因：如果使用传统的堆内存进行Socket读写，JVM会将堆内存buffer拷贝一份到直接内存中然后再写入socket，多了一次缓冲区的内存拷贝。DirectMemory中可以直接通过DMA发送到网卡接口

         2. Composite Buffers

            传统的ByteBuffer，如果需要将两个ByteBuffer中的数据组合到一起，需要先创建一个size=size1+size2大小的新的数组，再将两个数组中的数据拷贝到新的数组中。

            使用Netty提供的组合ByteBuf，就可以避免这样的操作。CompositeByteBuf并没有真正将多个Buffer组合起来，而是保存了它们的引用，从而避免了数据的拷贝，实现了零拷贝。

         3. 对FileChannel.transferTo的使用

            Netty中使用了FileChannel的transferTo方法，该方法依赖于操作系统实现零拷贝。



3. dubbo

   1. 简介与特性：dubbo是一款高性能、轻量级的开元Java RPC框架，提供三大核心能力：**面向接口的远程方法调用**、**智能容错和负载均衡**、**服务自动注册和发现**。

      1. 【以下几点是官网上的特性介绍...】
      2. 面向接口的远程方法调用：提供高性能的基于代理的远程调用能力，服务以接口为粒度，为开发者屏蔽远程调用底层细节。
      3. 智能负载均衡：内置多种负载均衡策略（有哪些？），感知下游节点的健康状况，显著减少调用延迟，提高系统吞吐量。
      4. 服务自动注册于发现：支持多种注册中心服务（有哪些？），服务实例上下线实时感知（具体实现是什么？）。
      5. 高度可扩展能力：遵循微内核+插件的设计原则，所有核心能力如Protocol、Transport、Serialization被设计为可扩展点，平等的对待内置实现和第三方实现。（SPI设计模式？）
      6. 运行期流量调度：内置条件、脚本等路由策略，通过配置不同的路由规则，实现灰度发布、同机房优先等功能。
      7. 可视化的服务治理与运维：提供丰富服务治理、运维工具：随时查看服务元数据、服务健康状态以及调用统计，实时下发路由策略、调度配置参数。

   2. dubbo架构

      <img src="../../image/image-20200523161523850.png" alt="image-20200523161523850" style="zoom:30%;" />

      <img src="../../image/image-20200523161846866.png" alt="image-20200523161846866" style="zoom:50%;" />

      以上两张图说明dubbo执行流程：

      1. dubbo容器启动后，provider将自己提供的服务注册到注册中心（注册中心便知道有哪些服务上线了）
      2. consumer启动后，从注册中心订阅需要的服务。
      3. 注册中心以长连接的方式向consumer发送服务变更通知。
      4. consumer同步调用provider的服务（如果服务有多个节点，可通过负载均衡算法选择一个节点进行调用）
      5. consumer和provider会定期将调用信息（调用时间、调用服务信息）发送给监控中心
      6. Dubbo容器启动、服务生产者注册自己的服务、服务消费者从注册中心中订阅服务是在Dubbo应用启动时完成的；consumer调用provider是同步过程；注册中心向consumer发送服务变更通知是异步的；consumer和provider向监控中心发送信息是异步的。

      调用链整体展开：

      ![image-20200523162137463](../../image/image-20200523162137463.png)

      下面这张图看起来有点复杂了..

      ![image-20200523162039246](../../image/image-20200523162039246.png)

   3. Dubbo配置的覆盖关系 (1):方法级优先、接口级次之，全局配置优先级最低。 (2):如果级别一样，则消费者优先，提供方次之。

   4. dobbo高可用
      1. 注册中心Zookeeper宕机，还可以消费Dubbo暴露的服务。
      2. Dubbo的监控中心宕机，不会影响Dubbo的正常使用，只是丢失了部分采样数据。
      3. 数据库宕机后，注册中心仍然可以通过缓存提供服务列表查询，但是不能注册新的服务。
      4. 注册中心集群的任意一个节点宕机，将自动切换到另外一台。
      5. 注册中心全部宕机，服务提供者和消费者可以通过本地缓存通讯。
      6. 服务提供者无状态，任意一台宕机后，不影响使用。 
      7. 服务提供者全部宕机，服务消费者应用将无法使用，并且会无限次重连等待服务提供者恢复。

   5. 负载均衡策略

      1. 【默认为随机】

      2. 基于**权重的随机**负载均衡：Random LoadBalance，比如orderService想要远程调用userService，而userService分别在三台机器上，我们可以给每台机器设置权重，比如三台机器的权重依次为100、200、50，则总权重为350，则选择第一台的概率就是100/350.

      3. 基于**权重的轮询**负载均衡：RoundRobin LoadBalance（可以理解为按照权重占比进行轮询。占比少的，当权重比较低时就不会再去权重低的机器上请求。如果某台机器性能一般，但权重占比高，就很可能卡在这里）

      4. 最少活跃数负载均衡：LeastActive LoadBalance，比如三台服务器上一次处理请求所花费的时间分别为100ms、1000ms、300ms，则这一次请求回去上一次处理请求时间最短的机器，所以这次一号服务器处理这次请求。

      5. 一致性Hash负载均衡：ConsistentHash LoadBalance

         原文：https://blog.csdn.net/revivedsun/java/article/details/71022871

         一致性Hash负载均衡涉及到两个主要的配置参数为hash.arguments 与hash.nodes。

         hash.arguments ： 当进行调用时候根据调用方法的哪几个参数生成key，并根据key来通过一致性hash算法来选择调用结点。例如调用方法invoke(String s1,String s2); 若hash.arguments为1(默认值)，则仅取invoke的参数1（s1）来生成hashCode。

         hash.nodes： 为结点的副本数。

         1
2
3
4
5
缺省只对第一个参数Hash，如果要修改，请配置
<dubbo:parameter key="hash.arguments" value="0,1" />

缺省用160份虚拟节点，如果要修改，请配置
<dubbo:parameter key="hash.nodes" value="320" />


      6. 降级服务

         当服务器压力剧增的情况下，根据实际业务及流量，对一些服务和页面有策略地不处理或者换种简单的方式处理，从而释放服务器资源以保证核心交易正常或高效运行。

         1. mock=force:return+null:表示消费方对该服务的方法都返回null值，不发起远程调用。用来屏蔽不重要的服务不可用时对调用方的影响，可以直接在Dubbo客户端(localhost:7001)对服务消费者设置，屏蔽掉即可。

         2. mock=fall:return+null:表示消费方对该服务的方法调用在失败后，再返回null，不抛出异常。用来容忍不重要服务不稳定时对调用方的影响，可以直接在Dubbo客户端(localhost:7001)对服务消费者设置，容错掉即可。

      7. 集群容错

         1. Failover Cluster:失败自动切换，当出现失败，重试其他服务器。通常用于读操作，但重试会带来更长延迟。可通过retries=n来设置重试次数。
         2. Failfast Cluster:快速失败，只发起一次调用，失败立即报错。通常用于非幂等性的写操作，比如新增操作。

         3. Forking Cluster:并行调用多个服务器，只要一个成功即返回。通常用于实时性要求较高的读操作，但需要浪费更多的服务资源。通过过fork=n设置最大并行数。

         4. Broadcast Cluster:广播调用所有提供者，逐个调用，任意一台报错则报错，通常用于通知所有服务提供者更新缓存或日志等本地资源信息。

限流算法

缓存：提升系统访问速度和增大系统处理容量

降级：当服务器压力剧增的情况下，根据当前业务情况对一些服务和页面有策略地降级，以此释放服务器资源以保证核心任务的正常运行

限流：限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理

限流算法：
1. 固定窗口法
  1. 实现：固定时间内限定个数，比如限定每分钟100个请求
  2. 缺点：无法应对两个时间边界内的突发流量。比如在计数器清零的前一秒和后一秒都进来100个请求，那么系统短时间内就收到了两倍（200个）请求，有可能超负荷。
  3. 原因：统计精度不够
2. 滑动窗口法
  1. 实现：简单来说就是随着时间的推移，时间窗口也会持续移动，有一个计数器不断维护着窗口内的请求数量，这样就可以保证任意时间段内，都不会超过最大允许的请求数。例如当前时间窗口是0s~60s，请求数是40，10s后时间窗口就变成了10s~70s，请求数是60。
  2. 可以用Redis有序集合实现..
  4. 缺点：还是不能解决细粒度请求过于集中的问题，比如限制一分钟60个请求，但在59s时发送了60个请求过来。
3. 漏桶算法
  1. 算法思想：与令牌桶算法有点相反。不限制流入速率，但以固定的速度将水流出。如果流入速度太大会导致水满溢出，溢出的请求被丢弃。
  2. 实现一：基于queue。queue的大小表示桶的大小，queue满了请求会被拒绝；另维护一个定时器，根据设定的出水速度去queue中取一个任务，比如限定一秒钟5个请求，就200ms去取一个任务，取到就执行，取不到就轮空。
  3. 实现二：基于meter，计数器。【…写的不是很清楚，看起来和固定窗口法很像了，没有体现固定的出水，只表示时间粒度比较细】
4. 令牌桶法
  1. 算法思路：以固定的速率生成令牌，把令牌放到固定容量的桶里，超过桶容量的令牌则丢弃。每来一个请求获取一次令牌，只有获得令牌的请求才能放行，没有获得令牌的请求丢弃。
  2. 【令牌是匀速生成的，如果请求超高频，则完全被限制成令牌的生成速率；如果请求突发，也最多只允许令牌数的上限。】
  3. Guava RateLimiter
5. 令牌桶与漏桶的比较
  1. 漏桶能够强行限制数据的传输速率
  2. 令牌桶限制数据的平均传输速率，允许某种程度的突发传输
  3. 【看起来比较喜欢令牌桶】

zk挂了怎么办？ todo
1. 指zk集群挂了其中一台机器？ – 集群自己可以处理
  1. 挂的是master
  2. 挂的是follower
  3. 挂的是..
2. 集群全挂了？—那就是全挂了啊趁早加入监控和降级策略

分布式锁的实现方式，zk实现和Redis实现的比较

实现方式：CAP的应用
1. MySQL唯一索引
  1. 实现：锁名称建立唯一索引，先插入数据的线程获得锁
  2. 缺点：完全依赖数据库的可用性（单点问题，无主从切换）和性能
2. Redis
  1. 实现：setnx key value expire_time
  2. 优缺点：为解决无主从切换的问题，可以使用Redis集群，或者sentinel哨兵模型。当master节点出现故障，哨兵从slave中选取节点称为新master节点。文章说，Redis集群的复制是AP模式，可能存在数据不一致，导致存在两个线程获得到锁的情况。（一个线程在原master获得锁，另一个线程在新master获得锁）
  3. 对数据一致性非常敏感的场景，建议使用CP模型（比如zk）
3. zk
  1. 实现：
    1. 线程向zk的锁目录，申请创建有序的临时节点
    2. 如果建成的节点序号最小，表明获得到锁
    3. 如果序号非最小，监听自己的前一个节点
    4. 删除节点表示释放锁；当获取锁的客户端异常、无心跳，临时节点会被删除，也表示释放锁
  2. 优缺点：CP模式，zk的分布式锁比Redis的可靠，但Redis的性能更高。要根据自己的业务场景，再选型。

秒杀场景设计，应付突然的爆发流量

一个秒杀系统的设计思考

两个核心问题：并发读、并发写

对应到架构设计，就是高可用、一致性和高性能的要求

1. 高性能：涉及高读和高写。

   核心理念：高读->尽量“少读”或“读少”，高写->数据拆分

   1. 动静分离：将页面拆分，静态部分做CDN缓存（秒级失效，若干CDN节点），动态部分异步请求。

      数据拆分、静态缓存、数据整合（指动态数据、静态数据怎么整合在一起，一种服务端将动态数据插入到静态页面，另一种前端异步调用）

   2. 热点优化

      1. 热点操作：零点刷新、零点下单、零点加购物车等，属于用户行为不好改变，但可以做一些限制，比如用户频繁刷新页面时进行提示阻断。

      2. 热点数据：

         1. 热点识别：分为**静态热点**（可以提前预测的。大促前夕，可以根据大促的行业特点、活动商家等纬度信息分析出热点商品，或者通过卖家报名的方式提前筛选；另外，还可以通过技术手段提前预测，例如对买家每天访问的商品进行大数据计算，然后统计出 TOP N 的商品，即可视为热点商品）和**动态热点**（无法提前预测的。比如直播临时做了个广告可能导致一件商品短期内被大量购买）。

            动态热点的识别实现思路：1. **异步采集交易链路各个环节的热点key信息**，比如nginx采集访问url或agent采集热点日志（一些中间件本身已具备热点发现能力），提前识别潜在的热点数据。2. **聚合分析热点数据，达到一定规则的热点数据，通过订阅分发推送到链路系统**，各系统根据自身需求决定如何处理热点数据，或限流或缓存，从而实现热点保护

            最好做到秒级实时，这样动态发现才有意义。实际上也是对核心节点的数据采集和分析能力提出了较高的要求。

         2. 热点隔离：将热点数据隔离出来，不影响非热点数据的访问。 -- 【我怎么觉得参与秒杀的商品都可以直接作为热点呢？？】

            1. 业务隔离。秒杀作为一种营销活动，卖家需要单独报名，从技术上来说，系统可以提前对已知热点做缓存预热 -- 【静态热点吧..】
            2. 系统隔离。系统隔离是运行时隔离，通过分组部署和另外 99% 进行分离，另外秒杀也可以申请单独的域名，入口层就让请求落到不同的集群中 -- 【也是静态热点吧..】
            3. 热点数据，可以启用单独的缓存集群或者DB服务组，从而更好的实现横向或纵向能力扩展 -- 【可以是动态的，假如一个商品被动态标记为热点后】

         3. 热点优化：对这1%的数据做针对性的优化

            1. 缓存：热点缓存是最为有效的办法。
            2. 限流：流量限制更多是一种保护机制。--属于有损服务。

   3. 系统优化：提升硬件水平、调优JVM性能、代码层面优化

      1. 代码层面优化：1. **减少序列化**（减少RPC调用，一种可行的方案是将多个关联性较强的应用进行 “合并部署”，从而减少不同应用之间的 RPC 调用（微服务设计规范））2. **直接输出流数据**（只要涉及字符串的I/O操作，无论是磁盘 I/O 还是网络 I/O，都比较耗费 CPU 资源，因为字符需要转换成字节，而这个转换又必须查表编码。所以对于常用数据，比如静态字符串，推荐提前编码成字节并缓存，具体到代码层面就是通过 OutputStream() 类函数从而减少数据的编码转换；另外，热点方法toString()不要直接调用ReflectionToString实现，推荐直接硬编码，并且只打印DO的基础要素和核心要素-- 这整段不是很懂，toString懂啊哈哈）3. **裁剪日志异常堆栈**，超大流量下频繁地输出完整堆栈，会加剧系统当前负载（可以通过日志配置文件控制异常堆栈输出的深度）4. **去组件框架**：极致优化要求下，可以去掉一些组件框架，比如去掉传统的 MVC 框架，直接使用 Servlet 处理请求。这样可以绕过一大堆复杂且用处不大的处理逻辑，节省毫秒级的时间，当然，需要合理评估你对框架的依赖程度


2. 一致性：秒杀场景下的一致性问题，主要是库存扣减的准确性问题

   1. 减库存的方式：

  1. 下单减库存（用户体验好，但存在恶意下单不付款的问题）

      2. 付款减库存（用户体验差，很多人下单成功但有人不能付款）

      3. **预扣库存**：缓解了以上两种方式的问题。预扣库存实际就是“下单减库存”和 “付款减库存”两种方式的结合，将两次操作进行了前后关联，下单时预扣库存，付款时释放库存。

         劣势：并没有彻底解决以上问题。比如针对恶意下单的场景，虽然可以把有效付款时间设置为 10 分钟，但恶意买家完全可以在 10 分钟之后再次下单。

         实际业界也多用这种方式，下单后一般都有个 “有效付款时间”，超过该时间订单自动释放，是典型的预扣库存方案。

      4. 恶意下单的解决方案主要还是结合安全和反作弊措施来制止。比如，识别频繁下单不付款的买家并进行打标，这样可以在打标买家下单时不减库存；再比如为大促商品设置单人最大购买件数，一人最多只能买 N 件商品；又或者对重复下单不付款的行为进行次数限制阻断等

      5. 超卖分为两种：1. 商家可以补货的，允许超卖；2. 不允许超卖，限定库存字段不能为负数：1）一是在通过事务来判断，即保证减后库存不能为负，否则就回滚；2）直接设置数据库字段类型为无符号整数，这样一旦库存为负就会在执行 SQL 时报错

   2. 一致性性能的优化

      1. 高并发读：“分层校验”。即在读链路时，不做一致性校验，只做不影响性能的检查（如用户是否具有秒杀资格、商品状态是否正常、用户答题是否正确、秒杀是否已经结束、是否非法请求等），**在写链路的时候，才对库存做一致性检查，在数据层保证最终准确性。**

         不同层次尽可能过滤掉无效请求，只在“漏斗” 最末端进行有效处理，从而缩短系统瓶颈的影响路径。

      2. 高并发写

         1. 更换DB选型：换用缓存系统（带有持久化功能的缓存，如Redis，适合减库存操作逻辑单一的，无事务要求的）

         2. 优化DB性能：库存数据落地到数据库实现其实是一行存储（MySQL），因此会有大量线程来竞争 InnoDB 行锁。但并发越高，等待线程就会越多，TPS 下降，RT 上升，吞吐量会受到严重影响。

            两种方法：

            1. 应用层排队。加入分布式锁，控制集群对同一行记录进行操作的并发度，也能控制单个商品占用数据库连接的数量
            2. 数据层排队。（应用层排队是有损性能的，数据层排队是最为理想的。）业界中，阿里的数据库团队开发了针对InnoDB 层上的补丁程序（patch），可以基于DB层对单行记录做并发排队，从而实现秒杀场景下的定制优化。另外阿里的数据库团队还做了很多其他方面的优化，如 COMMIT_ON_SUCCESS 和 ROLLBACK_ON_FAIL 的补丁程序，通过在 SQL 里加入提示（hint），实现事务不需要等待实时提交，而是在数据执行完最后一条 SQL 后，直接根据 TARGET_AFFECT_ROW 的结果进行提交或回滚，减少网络等待的时间（毫秒级）。目前阿里已将包含这些补丁程序的 MySQL 开源：AliSQL。

3. 高可用

   1. 流量削峰

      1. 答题：通过提升购买的复杂度，达到两个目的：防止作弊&延缓请求。本质是通过在入口层削减流量，从而让系统更好地支撑瞬时峰值。
      2. 排队：最为常见消息队列，通过把同步的直接调用转换成异步的间接推送，缓冲瞬时流量。（弊端：请求积压、用户体验）（排队本质是在业务层将一步操作转变成两步操作，从而起到缓冲的作用，但鉴于此种方式的弊端，最终还是要基于业务量级和秒杀场景做出妥协和平衡。）
      3. 过滤：过滤的核心目的是通过减少无效请求的数据IO 保障有效请求的IO性能。
         1. 读限流：对读请求做限流保护，将超出系统承载能力的请求过滤掉
         2. 读缓存：对读请求做数据缓存，将重复的请求过滤掉
         3. 写限流：对写请求做限流保护，将超出系统承载能力的请求过滤掉
         4. 写校验：对写请求做一致性校验，只保留最终的有效数据

   2. Plan B

      1. 架构阶段：考虑系统的可扩展性和容错性，避免出现单点问题。例如多地单元化部署，即使某个IDC甚至地市出现故障，仍不会影响系统运转

         编码阶段：保证代码的健壮性，例如RPC调用时，设置合理的超时退出机制，防止被其他系统拖垮，同时也要对无法预料的返回错误进行默认的处理

         测试阶段：保证CI的覆盖度以及Sonar的容错率，对基础质量进行二次校验，并定期产出整体质量的趋势报告

         发布阶段：系统部署最容易暴露错误，因此要有前置的checklist模版、中置的上下游周知机制以及后置的回滚机制

         运行阶段：系统多数时间处于运行态，最重要的是运行时的实时监控，及时发现问题、准确报警并能提供详细数据，以便排查问题

         故障发生：首要目标是及时止损，防止影响面扩大，然后定位原因、解决问题，最后恢复服务

      2. 预防：建立常态压测体系，定期对服务进行单点压测以及全链路压测，摸排水位

         管控：做好线上运行的降级、限流和熔断保护。需要注意的是，无论是限流、降级还是熔断，对业务都是有损的，所以在进行操作前，一定要和上下游业务确认好再进行。就拿限流来说，哪些业务可以限、什么情况下限、限流时间多长、什么情况下进行恢复，都要和业务方反复确认

         监控：建立性能基线，记录性能的变化趋势；建立报警体系，发现问题及时预警

         恢复：遇到故障能够及时止损，并提供快速的数据订正工具，不一定要好，但一定要有
         在系统建设的整个生命周期中，每个环节中都可能犯错，甚至有些环节犯的错，后面是无法弥补的或者成本极高的。所以高可用是一个系统工程，必须放到整个生命周期中进行全面考虑。同时，考虑到服务的增长性，高可用更需要长期规划并进行体系化建设。

![image-20200525191748562](../../image/image-20200525191748562.png)

分布式数据一致性

https://juejin.im/post/5ce7b325e51d45772a49ac9d
1. 数据不一致性的情形
  1. 主库、从库和缓存的数据一致性：相同数据冗余。为保证数据库的高可用和高性能，会采用主从（备）架构并引入缓存。数据不一致存在于数据冗余的时间窗口内。
  2. 多副本数据之间的数据一致性：相同数据副本。一份数据有多个副本存储到不同节点上，客户端可以访问任一节点进行读写。常用协议包括Paxos、ZAB、Raft、Quorum、Gossip等。
  3. 分布式服务之间的数据一致性：微服务架构下，不同服务操作不同的库表，要求库表间要保持一致（等价于分布式事务） – 【感觉题目问的是这个】
2. 对CAP理论的理解 https://www.zhihu.com/question/54105974/answer/139037688
  
  C代表一致性，A代表可用性（在一定时间内，用户的请求都会得到应答），P代表分区容忍性。
  
  一个分布式系统里面，节点组成的网络本来应该是连通的。然而可能因为一些故障，使得有些节点之间不连通了，整个网络就分成了几块区域。数据就散布在了这些不连通的区域中。这就叫分区。
  
  当你一个数据项只在一个节点中保存，那么分区出现后，和这个节点不连通的部分就访问不到这个数据了。这时分区就是无法容忍的。
  
  提高分区容忍性的办法就是一个数据项复制到多个节点上，那么出现分区之后，这一数据项就可能分布到各个区里。容忍性就提高了。
  
  然而，要把数据复制到多个节点，就会带来一致性的问题，就是多个节点上面的数据可能是不一致的。要保证一致，每次写操作就都要等待全部节点写成功，而这等待又会带来可用性的问题。
  
  总的来说就是，数据存在的节点越多，分区容忍性越高，但要复制更新的数据就越多，一致性就越难保证。为了保证一致性，更新所有节点数据所需要的时间就越长，可用性就会降低。

3. 理解数据库本地事务  [分布式事务](https://juejin.im/post/5b5a0bf9f265da0f6523913b)

   1. ACID
      1. 原子性 atomicity：一个事务(transaction)中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。
      2. 一致性 consistency：事务的执行前后，是从一个一致性状态转移到另一个一致性状态。【是通过原子性和隔离性保证的。】
      3. 隔离性 isolation：事务并发执行时，每个事务有各自完整的数据空间。有不同的隔离级别，大部分通过锁实现。
      4. 持久性 durability：事务只要成功执行，对数据库所做的更新会永久保存下来。
   2. 隔离级别
   3. innodb实现原理：主要通过锁和日志来保证ACID
      1. 通过锁机制和mvcc实现隔离性
      2. redo log（重做日志）实现持久性
      3. undo log实现原子性和一致性【可以回滚】

4. 分布式事务 -- **主要是要保证原子性**

   1. 分布式事务

      指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于不同的分布式系统的不同节点之上。

      一次大操作由不同的小操作组成，小操作分布在不同的服务器上，且属于不同的应用，**分布式服务需要保证这些小操作要么全部成功，要么全部失败**。

   2. 分布式事务的场景

      1. Service多个节点 -- 指微服务等，比如一个交易平台，订单、库存、余额等在不同的服务下，一次交易需要原子性得更新。
      2. resource多个节点 -- 指分库分表了，比如转账双方的余额在不同的表里，一次转账双方都要正确更新。

   3. 理论

      1. CAP
      2. BASE

   4. 解决方案

      1. 2PC
         1. 第一阶段：预提交，并反映是否可以提交。【事务管理器要求每个涉及到事务的数据库预提交(precommit)此操作，并反映是否可以提交.】
         2. 第二阶段：提交，或者回滚。【事务协调器要求每个数据库提交数据，或者回滚数据。】
         3. 优点：实现成本低
         4. 缺点：单点问题（事务管理器单点，可能引起资源管理器一直阻塞），同步阻塞（precommit后，资源管理器一直处于阻塞中，直到提交、释放资源），可能存在数据不一致（比如协调者发出了commit通知，但只有部分参与者收到通知并执行了commit，其余参与者则没收到通知处于阻塞状态，就产生不一致了）
      2. TCC
         1. try - confirm - cancel
         2. 协调者变成多点，引入进群
         3. 引入超时，超时后进行补偿，并且不会锁定整个资源，缓解同步阻塞
         4. 数据一致性：通过补偿机制，由业务活动管理器控制一致性
      3. 本地消息表：核心是将需要分布式处理的任务通过消息日志的方式来异步执行。消息日志可以存储到本地文本、数据库或消息队列，再通过业务规则自动或人工发起重试。
      4. MQ事务
      5. SAGA
      6. seata

数据库隔离级别
1. 读未提交
2. 读提交
3. 可重复读
4. 可串行化
一致性哈希

一致性哈希算法
1. 求出各节点的哈希值，将其配置到0~2^32的圆（continuum）上
2. 用同样方法求出存储数据的哈希值，映射到相同的圆上
3. 从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个节点上。如果超过2^32仍然找不到节点，就保存到第一个节点上
4. 【如果添加一个节点node5，只会影响该节点的逆时针方向的第一个节点node4会受到影响（原来在node4上的数据要重新分配一些到node5上）】
5. 一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性
6. 在服务节点太少时，容易因节点分部不均匀而造成数据倾斜问题，可引入虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射。

消息队列原理介绍
1. 作用
  1. 解耦
  2. 异步
  3. 削峰/限流
~~注解的原理~~ 【见4】
~~数据库原理~~，数据库中间件，索引优化
1. 索引优化
  1. 如果MySQL评估使用索引比全表扫描还慢，则不会使用索引
  2. 前导模糊查询（like ‘%xx’）不会使用索引，可以优化为非前导模糊查询（like ‘xx%’）
  3. 数据类型出现隐式转换的时候不会命中索引，特别是当列类型是字符串，一定要将字符常量值用引号引起来
  4. 复合索引，要满足最左匹配原则
  5. union、in、or 都能够命中索引，建议使用 in
    
    查询的CPU消耗：or (id=1 or id=2)> in (id in (1,2)) >union(id = 1 union id = 2)
  6. 用or分割开的条件，如果or前的条件中列有索引，而后面的列中没有索引，那么涉及到的索引都不会被用到
    
    因为or后面的条件列中没有索引，那么后面的查询肯定要走全表扫描，在存在全表扫描的情况下，就没有必要多一次索引扫描增加IO访问。
  7. 负向条件查询不能使用索引，可以优化为 in 查询
    
    负向条件有：!=、<>、not in、not exists、not like 等。
  8. 范围条件查询可以命中索引
    
    范围条件有：<、<=、>、>=、between等（返回数据的比例超过30%，会不使用索引）
  9. 查询条件（带有计算函数）执行计算不会命中索引
  10. 利用覆盖索引进行查询，避免回表
  11. 建议索引的列设置为非null
  12. 更新十分频繁的字段上不宜建立索引
  13. 区分度不大的字段上不宜建立索引
  14. 业务上具有唯一特性的字段，建议建立唯一索引
  15. 多表关联时，关联字段建议有索引
  16. 创建索引时避免以下错误观念
    1. 索引越多越好，认为一个查询就需要建一个索引。
    2. 宁缺勿滥，认为索引会消耗空间、严重拖慢更新和新增速度。
    3. 抵制唯一索引，认为业务的唯一性一律需要在应用层通过“先查后插”方式解决。
    4. 过早优化，在不了解系统的情况下就开始优化。