

# Java 基础

## 知识体系

## Questions

### 1. `HashMap` 1.8与1.7的区别

|                |          1.7          |          1.8          |
| :------------: | :-------------------: | :-------------------: |
|    底层结构    |       数组+链表       |   数组+链表/红黑树    |
|    插入方式    |        头插法         |        尾插法         |
|   计算hash值   | 4次位运算+5次异或运算 | 1次位运算+1次异或运算 |
|   扩容、插入   |     先扩容再插入      |     先插入再扩容      |
| 扩容后位置计算 |       重新hash        | 原位置或原位置+旧容量 |

#### (1) 扩容因子默认为什么是0.75

如果扩容因子过高，空间利用率提高但是哈希冲突概率增加；如果扩容因子过低，会造成频繁扩容，哈希冲突概率降低，但是空间利用率变低。选择0.75是基于泊松分布，是时间和空间成本上寻求的一种折中选择

#### (2)为什么链表长度为8要转化为红黑树

首先和`hashcode`碰撞次数的泊松分布有关，主要是为了寻找一种时间和空间的平衡。在负载因子0.75（HashMap默认）的情况下，单个`hash`槽内元素个数为8的概率小于百万分之一，将7作为一个分水岭，等于7时不做转换，大于等于8才转红黑树，小于等于6才转链表。链表中元素个数为8时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了8，是根据概率统计而选择的。红黑树中的`TreeNode`是链表中的`Node`所占空间的2倍，虽然红黑树的查找效率为$O(logN)$，要优于链表的$O(N)$，但是当链表长度比较小的时候，即使全部遍历，时间复杂度也不会太高。所以，要寻找一种时间和空间的平衡，即在链表长度达到一个阈值之后再转换为红黑树

### 2. `String` 、`StringBuffer` 、`StringBuilder` 的区别

|               | 是否可变 | 线程是否安全 | 性能 |
| :-----------: | :------: | :----------: | :--: |
|    String     |  不可变  |     安全     |  低  |
| StringBuilder |   可变   |    不安全    |  高  |
| StringBuffer  |   可变   |     安全     | 较高 |

### 3.强引用、软引用、弱引用、虚引用的区别

* **强引用**：如果一个对象具有强引用，垃圾回收器绝不会回收它。当内存空间不足时，JVM 宁愿抛出OOM错误，使程序异常终止；

* **软引用**：如果内存空间足够，垃圾回收器就不会回收它。如果内存空间不足了，就会回收这些对象的内存，只要垃圾回收器没有回收它，该对象就可以被程序使用

* **弱引用**：只具有弱引用的对象拥有更短暂的生命周期。在垃圾回收器线程扫描它所管辖的内存区域的过程中，一旦发现了只具有弱引用的对象，不管当前内存空间足够与否，都会回收它的内存

* **虚引用**：在任何时候都可能被垃圾回收器回收

### 4.`==`和 `equals` 区别

* ==：如果是基本数据类型，比较的是值，如果是引用数据类型，比较的是地址
* `equals`：继承自 `Object` 类，具体实现时可以覆盖父类的实现。如果没有复写，则和 == 一样，比较地址；如果复写了则根据复写的判断方式

### 5.`Object` 类的 `hashCode` 方法的作用

`hashCode `的哈希码主要作用是给散列表快速确定索引的，通过哈希码先判断对象是否有可能相同（因为相同的对象哈希码也一定相同），再去用 equals() 做进一步的比较，这样可以大大减少使用 `equals()`比较的次数

# Java并发

## 知识体系

## Questions

### 1.线性池了解吗？参数有哪些？任务到达线程池的过程？线程池的大小如何设置？

#### 线程池参数

|           参数           |                             作用                             |
| :----------------------: | :----------------------------------------------------------: |
|       corePoolSize       |                        核心线程池大小                        |
|     maximumPoolSize      |                        最大线程池大小                        |
|      keepAliveTime       | 线程池中超过 corePoolSize 数目的空闲线程最大存活时间；可以allowCoreThreadTimeOut(true) 使得核心线程有效时间 |
|         TimeUnit         |                    keepAliveTime 时间单位                    |
|        workQueue         |                         阻塞任务队列                         |
|      threadFactory       |                         新建线程工厂                         |
| RejectedExecutionHandler | 拒绝策略。当提交任务数超过 maxmumPoolSize+workQueue 之和时，任务会交给RejectedExecutionHandler 来处理 |

#### 线程处理任务过程

* 当线程池小于 `corePoolSize`，新提交任务将创建一个新线程执行任务，即使此时线程池中存在空闲线程
* 当线程池达到 `corePoolSize` 时，新提交任务将被放入 `workQueue ` 中，等待线程池中任务调度执行
* 当 `workQueue` 已满，且 `maximumPoolSize` 大于 `corePoolSize` 时，新提交任务会创建新线程执行任务
* 当提交任务数超过 `maximumPoolSize` 时，新提交任务由 `RejectedExecutionHandler` 处理
* 当线程池中超过 `corePoolSize` 线程，空闲时间达到 `keepAliveTime` 时，关闭空闲线程 

#### 线程池的大小设置

* `CPU` 密集型
  * `CPU` 密集的意思是该任务需要大量的运算，而没有阻塞，`CPU` 一直全速运行
  * `CPU` 密集型任务尽可能的少的线程数量，一般为 `CPU` 核数 +1 个线程的线程池

* `IO` 密集型
  * 由于 `IO` 密集型任务线程并不是一直在执行任务，可以多分配一点线程数，如 `CPU * 2`
  * 也可以使用公式：`CPU` 核数 / (1 - 阻塞系数)；其中阻塞系数在 0.8 ～ 0.9 之间

### 2.`Java`乐观锁机制，`CAS`思想？缺点？是否原子性？

#### `Java`乐观锁机制

乐观锁体现的是悲观锁的反面。它是一种积极的思想，它总是认为数据是不会被修改的，所以是不会对数据上锁的。但是乐观锁在更新的时候会去判断数据是否被更新过。乐观锁的实现方案一般有两种（版本号机制和 `CAS`）。乐观锁适用于读多写少的场景，这样可以提高系统的并发量。在 `Java` 中 `java.util.concurrent.atomic`下的原子变量类就是使用了乐观锁的一种实现方式 `CAS` 实现的。

乐观锁，大多是基于数据版本 (`Version`)记录机制实现。即为数据增加一个版本标识，在基于数据库表的版本解决方案中，一般是通过为数据库表增加一个 `“version”` 字段来 实现。 读取出数据时，将此版本号一同读出，之后更新时，对此版本号加一。此时，将提 交数据的版本数据与数据库表对应记录的当前版本信息进行比对，如果提交的数据 版本号大于数据库表当前版本号，则予以更新，否则认为是过期数据。

#### `CAS`思想

`CAS` 就是 `compare and swap`（比较交换），是一种很出名的无锁的算法，就是可以不使用锁机制实现线程间的同步。使用CAS线程是不会被阻塞的，所以又称为非阻塞同步。`CAS` 算法涉及到三个操作：需要读写内存值 `V`； 进行比较的值 `A`； 准备写入的值 `B`。当且仅当 `V` 的值等于 `A` 的值等于 `V` 的值的时候，才用 `B` 的值去更新 `V` 的值，否则不会执行任何操作（比较和替换是一个原子操作 `A` 和 `V` 比较，`V` 和 `B` 替换），一般情况下是一个自旋操作，即不断重试。缺点：高并发的情况下，很容易发生并发冲突，如果 `CAS` 一直失败，那么就会一直重试，浪费 `CPU` 资源。

#### 原子性

功能限制 `CAS` 是能保证单个变量的操作是原子性的，在 `Java` 中要配合使用 `volatile` 关键字来保证线程的安全；当涉及到多个变量的时候 `CAS` 无能为力；除此之外 `CAS` 实现需要硬件层面的支持，在 `Java` 的普通用户中无法直接使用，只能借助 `atomic` 包下的原子类实现，灵活性受到了限制。

### 3.`ReenTrantLock` 使用方法？底层实现？和 `synchronized` 区别？

由于 `ReentrantLock` 是 `java.util.concurrent` 包下提供的一套互斥锁，相比 `Synchronized`，`ReentrantLock`类提供了一些高级功能，主要有以下三项：

* 等待可中断，持有锁的线程长期不释放的时候，正在等待的线程可以选择放弃等待，这相当于 `Synchronized` 来说可以避免出现死锁的情况。通过 `lock.lockInterruptibly()`来实现这个机制
* 公平锁，多个线程等待同一个锁时，必须按照申请锁的时间顺序获得锁，`Synchronized` 锁非公平锁，`ReentrantLock` 默认的构造函数是创建的非公平锁，可以通过参数 `true` 设为公平锁，但公平锁表现的性能不是很好
* 锁绑定多个条件，一个 `ReentrantLock` 对象可以同时绑定对个对象。`ReenTrantLock` 提供了一个 `Condition`（条件）类，用来实现分组唤醒需要唤醒的线程们，而不是像 `synchronized` 要么随机唤醒一个线程要么唤醒全部线程

#### 使用方法

 基于 `API` 层面的互斥锁，需要 `lock()` 和 `unlock()` 方法配合 `try/finally` 语句块来完成

#### 底层实现

` ReenTrantLock` 的实现是一种自旋锁，通过循环调用 `CAS` 操作来实现加锁。它的性能比较好也是因为避免了使线程进入内核态的阻塞状态。想尽办法避免线程进入内核的阻塞状态是我们去分析和理解锁设计的关键钥匙

#### `ReenTrantLock`和`synchronized` 的区别

 1、**底层实现**上来说，`synchronized` 是 `JVM` 层面的锁，是 `Java` 关键字，通过 `monitor` 对象来完成（`monitorenter与monitorexit`），对象只有在同步块或同步方法中才能调用 `wait/notify` 方法；`ReentrantLock` 是从 `jdk1.5` 以来（`java.util.concurrent.locks.Lock`）提供的 `API` 层面的锁。`synchronized` 的实现涉及到锁的升级，具体为无锁、偏向锁、自旋锁、向OS申请重量级锁；`ReentrantLock` 实现则是通过利用 `CAS` （`CompareAndSwap`）自旋机制保证线程操作的原子性和 `volatile` 保证数据可见性以实现锁的功能

 2、**是否可手动释放：`**synchronized` 不需要用户去手动释放锁，`synchronized` 代码执行完后系统会自动让线程释放对锁的占用； `ReentrantLock` 则需要用户去手动释放锁，如果没有手动释放锁，就可能导致死锁现象。一般通过`lock()` 和 `unlock()` 方法配合 `try/finally` 语句块来完成，使用释放更加灵活

 3、**是否可中断** `synchronized` 是不可中断类型的锁，除非加锁的代码中出现异常或正常执行完成； `ReentrantLock` 则可以中断，可通过 `trylock(long timeout,TimeUnit unit)` 设置超时方法或者将 `lockInterruptibly()` 放到代码块中，调用 `interrupt` 方法进行中断。

4、**是否公平锁 **`synchronized` 为非公平锁 `ReentrantLock` 则即可以选公平锁也可以选非公平锁，通过构造方法`new ReentrantLock` 时传入 `boolean` 值进行选择，为空默认 `false` 非公平锁，`true` 为公平锁

### 4.介绍一下 `Java` 的内存模型

`Java` 内存模型（`Java Memory Model，JMM`）就是一种符合内存模型规范的，屏蔽了各种硬件和操作系统的访问差异的，保证了 `Java` 程序在各种平台下对内存的访问都能保证效果一致的机制及规范。`JMM` 是一种规范，是解决由于多线程通过共享内存进行通信时，存在的本地内存数据不一致、编译器会对代码指令重排序、处理器会对代码乱序执行等带来的问题。目的是保证并发编程场景中的原子性、可见性和有序性。所以，`Java` 内存模型，除了定义了一套规范，还提供了一系列原语，封装了底层实现后，供开发者直接使用。我们前面提到，并发编程要解决**原子性、有序性和一致性**的问题。

* **原子性：** 在 `Java` 中，为了保证原子性，提供了两个高级的字节码指令 `Monitorenter` 和 `Monitorexit`。这两个字节码，在 `Java` 中对应的关键字就是 `Synchronized`。因此，在 `Java` 中可以使用 `Synchronized` 来保证方法和代码块内的操作是原子性的
* **可见性：**` Java` 内存模型是通过在变量修改后将新值同步回主内存，在变量读取前从主内存刷新变量值的这种依赖主内存作为传递媒介的方式来实现的。`Java` 中的 `Volatile` 关键字修饰的变量在被修改后可以立即同步到主内存。被其修饰的变量在每次使用之前都从主内存刷新。因此，可以使用 `Volatile` 来保证多线程操作时变量的可见性。除了 `Volatile`，`Java` 中的 `Synchronized` 和 `Final` 两个关键字也可以实现可见性。只不过实现方式不同
* **有序性：**在 `Java` 中，可以使用 `Synchronized` 和 `Volatile` 来保证多线程之间操作的有序性。区别：`Volatile` 禁止指令重排。`Synchronized` 保证同一时刻只允许一条线程操作

### 5.`volatile` 作用？底层实现？单例模式中 `volatile` 的作用？

#### 作用

保证数据的“可见性”：被 `volatile` 修饰的变量能够保证每个线程能够获取该变量的最新值，从而避免出现数据脏读的现象。 禁止指令重排：在多线程操作情况下，指令重排会导致计算结果不一致。

#### 底层实现

观察加入 `volatile` 关键字和没有加入 `volatile` 关键字时所生成的汇编代码发现，加入 `volatile` 关键字时，会多出一个 `lock` 前缀指令， `lock` 前缀指令实际上相当于一个内存屏障（也成内存栅栏），内存屏障会提供3个功能：

* 它确保指令重排序时不会把其后面的指令排到内存屏障之前的位置，也不会把前面的指令排到内存屏障的后面；即在执行到内存屏障这句指令时，在它前面的操作已经全部完成
* 它会强制将对缓存的修改操作立即写入主存
* 如果是写操作，它会导致其他 `CPU` 中对应的缓存行无效

#### 单例模式中 `volatile` 的作用

防止代码读取到 `instance` 不为 `null` 时，`instance` 引用的对象有可能还没有完成初始化

```java
class Singleton{
    private volatile static Singleton instance = null;   //禁止指令重排
    private Singleton() {        
    }
    public static Singleton getInstance() {
        if(instance==null) {
            synchronized (Singleton.class) {
                if(instance==null)
                    instance = new Singleton();
            }
        }
        return instance;
    }
}
```

### 6.`ThreadLocal` 原理

### 7.`CAS` 和 `ABA` 问题

### 8.原子类的实现原理

### 9.说一下 `CurrentHashMap` 如何实现线程安全的

# JVM

## 知识体系

## Questions

### 1.`JVM` 内存划分

### 2.`GC` 垃圾收集器

### 3.垃圾收集算法，为什么新生代用标记-复制老年代用标记-整理

### 4.类加载流程

### 5.双亲委派机制，怎么样会打破双亲委派模型

### 6.`JVM` 1.7 和 1.8 的区别



# 数据库

## 知识体系

## Questions

###  1.`MySQL`的引擎了解吗？默认的是哪个？`InnoDB `和 `myISAM` 的区别？

`myISAM`:  支持表锁，适合读密集的场景，不支持外键，不支持事务，索引与数据在不同的文件，非聚簇索引

`InnoDB`:支持行、表锁，默认为行锁，适合并发场景，支持外键，支持事务，索引与数据同一文件，聚簇索引

### 2.介绍 `MVCC`

`MVCC` 是一种多版本并发控制机制，在大多数情况下代替行级锁，使用 `MVCC`，能降低其系统开销。`MVCC` 是通过保存数据在某个时间点的快照来实现的.。不同存储引擎的 `MVCC` 实现是不同的，典型的有乐观并发控制和悲观并发控制。`InnoDB` 的 `MVCC` 是通过在每行记录后面保存两个隐藏的列来实现的，这两个列，分别保存了这个行的创建时间，一个保存的是行的删除时间。这里存储的并不是实际的时间值，而是系统版本号(可以理解为事务的 `ID`)，每开始一个新的事务，系统版本号就会自动递增，事务开始时刻的系统版本号会作为事务的 `ID`。`InnoDB` 只会查找版本早于当前事务版本的数据行(也就是行的系统版本号小于或等于事务的系统版本号)，这样可以确保事务读取的行，要么是在事务开始前已经存在的，要么是事务自身插入或者修改过的。

### 3.`MySQL` 中一条 `SQL` 语句的执行过程

以查询语句为例

```mysql
select * from tb_student  A where A.age='18' and A.name='张三';
```

* 先检查该语句是否有权限，如果没有权限，直接返回错误信息，如果有权限，在 `MySQL8.0` 版本以前，会先查询缓存，以这条 `sql` 语句为 `key` 在内存中查询是否有结果，如果有直接缓存，如果没有，执行下一步
* 通过分析器进行词法分析，提取 `sql` 语句的关键元素，比如提取上面这个语句是查询 `select`，提取需要查询的表名为 `tb_student`,需要查询所有的列，查询条件是这个表的 `id='1'`。然后判断这个 `sql` 语句是否有语法错误，比如关键词是否正确等等，如果检查没问题就执行下一步
* 接下来就是优化器进行确定执行方案，上面的 `sql` 语句，可以有两种执行方案： a.先查询学生表中姓名为“张三”的学生，然后判断是否年龄是18。 b.先找出学生中年龄18岁的学生，然后再查询姓名为“张三”的学生。 那么优化器根据自己的优化算法进行选择执行效率最好的一个方案（优化器认为，有时候不一定最好）。那么确认了执行计划后就准备开始执行了
* 进行权限校验，如果没有权限就会返回错误信息，如果有权限就会调用数据库引擎接口，返回引擎的执行结果

### 4.如何查看 `sql` 语句的执行计划？用哪个关键字？使用这个关键字可以得到哪些信息？

用关键字 `explain` 来查看执行计划

![](https://i.loli.net/2021/07/01/xPIajcdQrysEJON.png)

![](https://i.loli.net/2021/07/01/k8TmrSEaK4M1lpc.png)

### 5.聚簇索引和非聚簇索引的区别，非聚簇索引是如何查询的？

聚簇索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的就是整张表的行记录数据，也将聚集索引的叶子节点称为数据页。这个特性决定了索引组织表中数据也是索引的一部分，每张表只能拥有一个聚簇索引。`InnoDB` 通过主键聚集数据，如果没有定义主键，`InnoDB` 会选择非空的唯一索引代替。如果没有这样的索引，`InnoDB` 会隐式的定义一个主键来作为聚簇索引。

在聚簇索引之上创建的索引称之为辅助索引，辅助索引访问数据总是需要二次查找。辅助索引叶子节点存储的不再是行的物理位置，而是主键值。通过辅助索引首先找到的是主键值，再通过主键值找到数据行的数据页，再通过数据页中的 `Page Directory`找到数据行。`InnoDB` 辅助索引的叶子节点并不包含行记录的全部数据，叶子节点除了包含键值外，还包含了相应行数据的聚簇索引键。辅助索引的存在不影响数据在聚簇索引中的组织，所以一张表可以有多个辅助索引。在 `InnoDB` 中有时也称辅助索引为二级索引。

二级索引需要两次索引查找， 二级索引中保存的“行指针”的本质：不是物理地址的指针，而是行的主键值。所以通过二级索引查找行，引擎需要找到二级索引的子节点获得对应主键值，然后根据该值去聚簇索引找到对应行。 出现重复工作：两次B-Tree查找，而非一次。对于InnoDB，自适应哈希索引能够减少这样重复。

###  6.`MySQL`的 `ACID`，分别解释一下

**原⼦性：** 事务是最⼩的执⾏单位，不允许分割。事务的原⼦性确保动作要么全部完成，要么全不执行

**一致性：** 执⾏事务前后，数据保持⼀致，多个事务对同⼀个数据读取的结果是相同的

 **隔离性：** 并发访问数据库时，⼀个⽤户的事务不被其他事务所⼲扰，各并发事务之间数据库是独⽴的

 **持久性：** ⼀个事务被提交之后。它对数据库中数据的改变是持久的，即使数据库发⽣故障也不应该对其有任何影响

### 7.数据库索引的实现原理

`MySQL` 中默认的引擎为 `InnoDB`，`innoDB` 的索引使用的是 `B+` 树实现

**`B+` 树对比 `B树` 的好处**

* `IO` 次数少：`B+` 树的中间结点只存放索引，数据都存在叶结点中，因此中间结点可以存更多的数据，让索引树更加矮胖

* 范围查询效率更高：`B` 树需要中序遍历整个树，`B+` 树只需要遍历叶结点中的链表

* 查询效率更加稳定：每次查询都需要从根结点到叶结点，路径长度相同，所以每次查询的效率都差不多

**使用 `B` 树索引和哈希索引的比较**

哈希索引能以 `O(1)` 时间进行查找，但是只支持精确查找，无法用于部分查找和范围查找，无法用于排序与分组；`B` 树索引支持大于小于等于查找，范围查找。哈希索引遇到大量哈希值相等的情况后查找效率会降低。哈希索引不支持数据的排序

### 8.联合索引，最左前缀匹配规则

联合索引又叫复合索引。两个或更多个列上的索引被称作复合索引。对于复合索引：`MySQL` 从左到右的使用索引中的字段，一个查询可以只使用索引中的一部份，但只能是最左侧部分。当最左侧字段是常量引用时，索引就十分有效

**优点：**

* 避免回表

* 两个单列查询返回行较多，同时查返回行较少，联合索引更高效

**如何设计：**

* 等值查询中，查询条件a返回的条目比较多，查询条件b返回的条目比较多，而同时查询a、b返回的条目比较少，那么适合建立联合索引

* 对于有等值查询的列和范围查询的列，等值查询的列建在前、范围查询的列建在后比较实用

* 如果联合索引列的前置列与索引单列一致，那么单列查询可以用到索引，这样就避免了再建单列索引，因此联合索引的前置列应尽量与单列一致

**最左前缀匹配原则：**在MySQL建立联合索引时会遵守最左前缀匹配原则，即最左优先，在检索数据时从联合索引的最左边开始匹配

### 9.索引怎么优化

* `like` 语句的前导模糊查询不能使用索引
* **联合索引最左前缀原则**
* 不能使用索引中范围条件右边的列(范围列可以用到索引)，范围列之后列的索引全失效
* 不要在索引列上面做任何操作(计算、函数)，否则会导致索引失效而转向全表扫描
* 使用短索引，如果对长字符串列进行索引，应该指定一个前缀长度，这样能够节省大量索引空间
* 常查询数据建立索引或者组合索引，不要建立无意义的索引

### 10.事物隔离级别

- 读未提交（read uncommitted，RU） 一个事务还没提交，它的变更就能被其它事务看到
- 读已提交（read committed，RC） 一个事务提交后，其变更才会被其他事务看到
- 可重复读（repeatable read，RR） 一个事务执行过程中看到的数据，和该事务在启动时看到的数据一致。 自然未提交的变更对其他事务也是不可见的。一个事务启动时，能够看到所有已提交的事务结果。但之后的该事务执行期间，其他事务的更新对它就不可见了
- 串行化（serializable） 对同行记录，“写”加“写锁”，“读”加“读锁”。出现读写锁冲突时，后访问的事务必须等前一个事务执行完成

### 11.`binlog`、`redo log`、`undo log`

#### `binlog`

`binlog`用于记录数据库执行的写入性操作(不包括查询)信息，以二进制的形式保存在磁盘中。`binlog`是`mysql`的逻辑日志，并且由`Server`层进行记录，使用任何存储引擎的`mysql`数据库都会记录`binlog`日志

**使用场景：**

1. **主从复制**：在`Master`端开启`binlog`，然后将`binlog`发送到各个`Slave`端，`Slave`端重放`binlog`从而达到主从数据一致
2. **数据恢复**：通过使用`mysqlbinlog`工具来恢复数据

#### `redo log`

`redo log`包括两部分：一个是内存中的日志缓冲(`redo log buffer`)，另一个是磁盘上的日志文件(`redo log file`)。`mysql`每执行一条`DML`语句，先将记录写入`redo log buffer`，后续某个时间点再一次性将多个操作记录写到`redo log file`。这种**先写日志，再写磁盘**的技术就是`MySQL`里经常说到的`WAL(Write-Ahead Logging)` 技术

**区别**

|          | redo log                                                     | binlog                                                       |
| -------- | ------------------------------------------------------------ | ------------------------------------------------------------ |
| 文件大小 | `redo log`的大小是固定的。                                   | `binlog`可通过配置参数`max_binlog_size`设置每个`binlog`文件的大小。 |
| 实现方式 | `redo log`是`InnoDB`引擎层实现的，并不是所有引擎都有。       | `binlog`是`Server`层实现的，所有引擎都可以使用 `binlog`日志  |
| 记录方式 | redo log 采用循环写的方式记录，当写到结尾时，会回到开头循环写日志。 | binlog 通过追加的方式记录，当文件大小大于给定值后，后续的日志会记录到新的文件上 |
| 适用场景 | `redo log`适用于崩溃恢复(crash-safe)                         | `binlog`适用于主从复制和数据恢复                             |

#### `undo log`

`undo log` 主要有两个作用：`回滚`和`多版本控制(MVCC)` 。在数据修改的时候，不仅记录了 `redo log`，还记录 `undo log`，如果因为某些原因导致事务失败或回滚了，可以用 `undo log` 进行回滚（保证了原子性） 。`undo log` 主要存储的是`逻辑日志`，用来回滚的`相反操作日志`。比如我们要 `insert` 一条数据了，那 `undo log` 会记录的一条对应的 `delete` 日志。我们要 `update` 一条记录时，它会记录一条对应相反的 `update` 记录。因为 `undo log` 存储着修改之前的数据，相当于一个前版本，``MVCC` 实现的是读写不阻塞，读的时候只要返回前一个版本的数据就行了

# Spring

## 知识体系

## Questions

### 1.`Sping IOC AOP` 的实现原理

### 2.`Spring` 事务的实现原理

### 3.`bean` 的生命周期


# Redis

## 知识体系

## Questions

### 1.基于 `redis` 的分布式锁是如何实现的

![](https://i.loli.net/2021/07/01/WwxOC1ULHkAdIfF.png)

**实现思想**：获取锁的时候，使用 `setnc` 加锁，并使用 `expire` 命令为锁添加一个超时时间，超过该时间则自动释放锁，锁的 `value` 值为一个随机生成的 `UUID`，通过此在释放锁的时候进行判断；获取锁的时候还设置一个获取的超时时间，若超过这个时间则放弃获取锁；释放锁的时候，通过 `UUID` 判断是不是该锁，若是该锁，则执行 `delete` 进行锁释放。因为 `redis` 是单线程的，这样的话，如果4个请求打过来的话，只有一个请求能获得锁，获得锁即为 `key` 设置一个值，如果这个 `key` 存在就设置失败，也就是只有一个请求可以设置成功，这个请求处理完之后，会把这个 `key` 释放掉，那么剩下等着的3个请求一定会有一个请求重新对这个 `key` 设置一个值再次获得锁，依次类推。这样即当不同机子上的请求打过来的时候能够保证某一时刻只能有一个请求去消费资源，间接地形成一种加锁的机制。

#### `Redisson` 实现 `Redis` 分布式锁

* 加锁机制：客户端1面对分布式集群下，首先根据 `hash` 节点选择一台机器，发送一段 `lua` 脚本（保证复杂业务的原子性），将 `key `加锁（如果 `key `不存在就进行加锁）、设置过期时间、客户端 `id`

* 锁互斥机制：如果客户端2执行同样的lua脚本，代码中则会判断该锁 `key` 已存在，紧接着判断锁 `key` 的 `hash` 数据结构中是否包含客户端2的 `id`，如果不包含则会获得一个返回的数字，代表这个锁 `key` 的剩余生存时间，紧接着客户端2会进入 `while` 循环不断尝试加锁

* `watch dog` 自动延期机制：客户端1加锁有默认生存时间，如果想继续持有，可以在加锁成功时启动一个 `watch dog`看门狗（后台线程），每10秒检查一下，如果客户端1还持有锁 `key`，就会不断的延长锁 `key` 的生存时间。**(是对1中如何设置有效期的优化)**

* 可重入加锁机制： `hash` 数据结构中的客户端 `id` 加锁次数+1**(是对锁只能加一次，不可重入的优化)** 

* 释放锁机制：每次对数据结构中的加锁次数-1，当加锁次数为0，说明该客户端不持有锁，此时会从 `redis` 里删除这个 `key` ，另外的客户端可以尝试完成加锁。

**缺点**：如果采用这种方案，对某个 `redis master` 实例，写入 `mylock` 这种锁的 `value`，此时异步复制给对应的 `master slave` 实例，这个过程中一旦 `redis master` 宕机，`redis slave` 就变成了 `redis master` 会导致客户端2尝试加锁时，在新的`redis master `上完成了加锁，而客户端1也以为自己成功加了锁。导致多个客户端对一个分布式锁完成了加锁，导致各种脏数据产生。【`redis` 主从架构的主从异步复制导致 `redis` 分布式锁的最大缺陷】

### 2.跳表数据结构，`redis` 中哪里用到了跳表

跳跃表（[skiplist](http://en.wikipedia.org/wiki/Skip_list)）是一种随机化的数据， 由 William Pugh 在论文[《Skip lists: a probabilistic alternative to balanced trees》](http://www.cl.cam.ac.uk/teaching/0506/Algorithms/skiplists.pdf)中提出， 跳跃表以有序的方式在层次化的链表中保存元素， 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳跃表的实现要简单直观得多

![ilBuYTAOrxfEdSm](https://i.loli.net/2021/08/21/ilBuYTAOrxfEdSm.jpg)

跳跃表主要由以下部分构成：

- 表头（head）：负责维护跳跃表的节点指针
- 跳跃表节点：保存着元素值，以及多个层
- 层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次
- 表尾：全部由 `NULL` 组成，表示跳跃表的末尾

`redis` 数据类型 `zset` 实现有序集合，底层使用的数据结构是跳表

### 3.出现缓存雪崩、击穿、穿透的情况及解决方法

#### 缓存雪崩

**缓存雪崩**指缓存同一时间大面积的失效，所以，后面的请求都会落到数据库上，造成数据库短时间内承受大量请求而崩掉。

**解决方案：**

- **Redis 高可用**，主从+哨兵，`Redis cluster`，避免全盘崩溃
- 本地 ehcache 缓存 + hystrix **限流&降级**，避免 `MySQL` 被打死
- 缓存数据的**过期时间设置随机**，防止同一时间大量数据过期现象发生
- **逻辑上永不过期**给每一个缓存数据增加相应的**缓存标记**，缓存标记失效则更新数据缓存
- **多级缓存**，失效时通过二级更新一级，由第三方插件更新二级缓存

#### **缓存穿透**

**缓存穿透**是指缓存和数据库中都没有的数据，导致所有的请求都落到数据库上，造成数据库短时间内承受大量请求而崩掉。

**解决方案：**

* **接口层增加校验**，如用户鉴权校验，id 做基础校验，id<=0 的直接拦截
* 从缓存取不到的数据，在数据库中也没有取到，这时也可以将**key-value 对写为 key-null**，缓存有效时间可以设置短点，如30秒。这样可以防止攻击用户反复用同一个id暴力攻击
* 采用**布隆过滤器**，将所有可能存在的数据哈希到一个足够大的 `bitmap` 中，一个一定不存在的数据会被这个 `bitmap` 拦截掉，从而避免了对底层存储系统的查询压力

#### **缓存击穿**

由于并发用户特别多，同时读缓存没读到数据，又同时去数据库去取数据，引起数据库压力瞬间增大，造成过大压力。和缓存雪崩不同的是，缓存击穿指并发查同一条数据，缓存雪崩是不同数据都过期了，很多数据都查不到从而查数据库

**解决方案：**

* 设置**热点数据永远不过期**，异步线程处理
* 加**写回操作加互斥锁**，查询失败默认值快速返回
* 缓存预热

​		系统上线后，将相关**可预期（例如排行榜）**热点数据直接加载到缓存

​		写一个缓存刷新页面，手动操作热点数据**（例如广告推广）**上下线

### 4.持久化策略

#### `RDB`

`RDB` 持久化是指在指定时间间隔内将内存中的数据集快照写入磁盘。实际上 `fork` 子线程，先将数据集写入临时文件，写入成功后，在替换之前的文件，用二进制压缩文件，`RDB` 是 `Redis` 默认的持久化方式，会在对应目录下生产一个`dump.rdb` 文件，重启会通过加载 `dump.rdb` 文件恢复数据

**优点**

- `RDB` 会生成多个数据文件，每个文件都代表了某时刻 `redis` 中的所有数据，这种方式非常适合做**冷备**，可将这种完整数据文件发送到云服务器存储，比如 `ODPS` 分布式存储，以预定好的备份策略来定期备份 `redis` 中的数据
- `RDB` 对 `Redis` 对外提供的读写服务，影响非常小，可让 `redis` 保持高性能，因为 `redis` 主进程只要 `fork` 一个子进程，让子进程执行 `RDB`
- 相对于 `AOF`，直接基于 `RDB` 文件重启和恢复 `redis`进程，更加快速

**缺点**

- `fork` 耗内存，`copy-on-write` 策略 `RDB `每次在 `fork` 子进程来执行 `RDB` 快照数据文件生成的时候，如果数据文件特别大，可能会导致对客户端提供的服务暂停数毫秒，或者甚至数秒
- 不可控，容易丢失数据 一般 `RDB` 每隔5分钟，或者更长时间生成一次，若过程中 `redis` 宕机，就会丢失最近未持久化的数据

#### `AOF`

`AOF`持久化是以日志的形式记录记录每一个增删操作然后追加到文件中。`AOF`的出现是为了弥补`RDB`备份的不足（数据不一致性）

**AOF的备份策略**

- `appendfsync always`：每次有数据修改发生时都会同步
- `appendfsync everysec`：每秒同步一次
- `appendsync no`：让操作系统决定何时进行同步

**优点**

- 更好避免数据丢失 一般`AOF`每隔1s，通过子进程执行一次`fsync`，最多丢1s数据
- `append-only`模式追加写 所以没有任何磁盘寻址的开销，写入性能高，且文件不易破损，即使文件尾部破损，也易修复
- 日志文件即使过大，出现后台重写操作，也不会影响客户端的读写 因为在`rewrite log`时，会压缩其中的指令，创建出一份需要恢复数据的最小日志。在创建新日志时，旧日志文件还是照常写入。当新的`merge`后的日志文件准备好时，再交换新旧日志文件即可

**缺点**

- 对于同一份数据，`AOF`日志一般比`RDB`快照更大，恢复慢
- `AOF`开启后，写`QPS`会比`RDB`的低，因为`AOF`一般会配置成每s `fsync`一次日志文件，当然，每s一次`fsync`，性能也还是很高的

### 5.主从复制原理

主从复制，是指将一台`redis`服务器的数据，复制到其他的`redis`服务器。前者称为主节点(`master`)，后者称为从节点(`slave`)。数据的复制是单向的，只能由主节点到从节点

**作用**

* 数据冗余：主从复制实现了数据的热备份，是持久化之外的一种数据冗余方式
* 故障恢复：当主节点出现问题时，可以由从节点提供服务，实现快速的故障恢复；实际上是一种服务的冗余
* 负载均衡：在主从复制的基础上，配合读写分离，可以由主节点提供写服务，由从节点提供读服务（即写`redis`数据时应用连接主节点，读`redis`数据时应用连接从节点），分担服务器负载；尤其是在写少读多的场景下，通过多个从节点分担读负载，可以大大提高`redis`服务器的并发量
* 高可用基石：除了上述作用以外，主从复制还是哨兵和集群能够实施的基础，因此说主从复制是`redis`高可用的基础

**原理**

* 通过从服务器发送到`PSYNC`命令给主服务器

* 如果是首次连接，触发一次**全量复制**。此时主节点会启动一个后台线程，生成 `RDB` 快照文件

* 主节点会将这个 `RDB` 发送给从节点，`slave` 会先写入本地磁盘，再从本地磁盘加载到内存中

* `master`会将此过程中的写命令写入缓存，从节点**实时同步**这些数据

* 如果网络断开了连接，自动重连后主节点通过命令传播**增量复制**给从节点部分缺少的数据

### 6.数据库缓存一致性

#### **先更新数据库，再更新缓存**

**线程安全**：同时有请求A和请求B进行更新操作

> 1. 线程A更新了数据库
> 2. 线程B更新了数据库
> 3. 线程B更新了缓存
> 4. 线程A更新了缓存

这就出现请求A更新缓存应该比请求B更新缓存早才对，但是因为网络等原因，B却比A更早更新了缓存。这就导致了脏数据，因此不考虑

**业务场景**：（1）如果你是一个写数据库场景比较多，而读数据场景比较少的业务需求，采用这种方案就会导致，数据压根还没读到，缓存就被频繁的更新，浪费性能；（2）如果你写入数据库的值，并不是直接写入缓存的，而是要经过一系列复杂的计算再写入缓存。那么，每次写入数据库后，都再次计算写入缓存的值，无疑是浪费性能的。显然，删除缓存更为适合

#### **先删除缓存，再更新数据库**

> 1. 请求A进行写操作，删除缓存
> 2. 请求B查询发现缓存不存在
> 3. 请求B去数据库查询得到旧值
> 4. 请求B将旧值写入缓存
> 5. 请求A将新值写入数据库

上述情况就会导致不一致的情形出现。而且，如果不采用给缓存设置过期时间策略，该数据永远都是脏数据。 

#### **先更新数据库，再删除缓存**

> 1. 请求缓存刚好失效
> 2. 请求A查询数据库，得一个旧值
> 3. 请求B将新值写入数据库
> 4. 请求B删除缓存
> 5. 请求A将查到的旧值写入缓存

这样就出现脏数据了，然而，实际上出现的概率可能非常低，因为这个条件需要发生在读缓存时缓存失效，而且并发着有一个写操作。而实际上数据库的写操作会比读操作慢得多，而且还要锁表，而读操作必需在写操作前进入数据库操作，而又要晚于写操作删除缓存，所有的这些条件都具备的概率基本并不大，但是还是会有出现的概率。并且假如**第一步写数据库成功，第二步删除缓存失败，这样也导致脏数据**

#### **延时双删**

> 1. 先删除(淘汰)缓存
> 2. 再写数据库（这两步和原来一样）
> 3. 休眠1秒，再次删除(淘汰)缓存

或者

> 1. 先写数据库
> 2. 再删除(淘汰)缓存（这两步和原来一样）
> 3. 休眠1秒，再次删除(淘汰)缓存

这个1秒应该看你的业务场景，应该自行评估自己的项目的读数据业务逻辑的耗时，然后写数据的休眠时间则在读数据业务逻辑的耗时基础上，加几百ms即可，这么做确保读请求结束，写请求可以删除读请求造成的缓存脏数据

**为了性能更快，可以把第二次删除缓存可以做成异步的，这样不会阻塞请求了，如果再严谨点，防止第二次删除缓存失败，这个异步删除缓存可以加上重试机制，失败一直重试，直到成功**

**方案一**

> 1. 更新数据库数据
> 2. 缓存因为种种问题删除失败
> 3. 将需要删除的key发送至消息队列
> 4. 自己消费消息，获得需要删除的key
> 5. 继续重试删除操作，直到成功

![9rzmXuUeYCcOGQp](https://i.loli.net/2021/08/23/9rzmXuUeYCcOGQp.jpg)

该方案有一个缺点，对业务线代码造成大量的侵入，于是有了方案二，启动一个订阅程序去订阅数据库的Binlog，获得需要操作的数据。在应用程序中，另起一段程序，获得这个订阅程序传来的信息，进行删除缓存操作

**方案二**

> 1. 更新数据库数据
> 2. 数据库会将操作信息写入binlog日志当中
> 3. 订阅程序提取出所需要的数据以及key
> 4. 另起一段非业务代码，获得该信息
> 5. 尝试删除缓存操作，发现删除失败
> 6. 将这些信息发送至消息队列
> 7. 重新从消息队列中获得该数据，重试操作

![WcMTS4zq9A7E8sD](https://i.loli.net/2021/08/23/WcMTS4zq9A7E8sD.jpg)

### 7.`redis` 的内存淘汰策略

![](https://tva1.sinaimg.cn/large/008i3skNly1gtbx2jwtfnj61ct0l9dhm02.jpg)

* `volatile-ttl` 在筛选时会针对设置了过期时间的键值对，根据过期时间的先后进行删除，越早过期的越先被删除
* `volatiile-random` 在筛选时对设置了过期时间的键值对进行随机删除
* `volatile-lru` 使用 `lru` 算法筛选设置了过期时间的键值对
* `volatile-lfu` 使用 `lfu` 算法筛选设置了过期时间的键值对

* 优先使用 `allkeys-lru` 可以充分利用 `lru` 这一经典算法的优势，把最近最常访问的数据留在缓存中，提升应用的访问性能
* 如果业务中有置顶的需求，可以使用 `volatile-lru` 策略同时不给这些置顶数据设置过期时间

### 8.`redis` 的 `key` 的过期策略

* **定时过期**：每个设置过期时间的`key`都需要创建一个定时器，到过期时间就会立即清除。该策略可以立即清除过期的数据，对内存很友好；但是会占用大量的`CPU`资源去处理过期的数据，从而影响缓存的响应时间和吞吐量

* **惰性过期**：只有当访问一个`key`时，才会判断该`key`是否已过期，过期则清除。该策略可以最大化地节省`CPU`资源，却对内存非常不友好。极端情况可能出现大量的过期`key`没有再次被访问，从而不会被清除，占用大量内存

* **定期过期**：每隔一定的时间，会扫描一定数量的数据库的`expires`字典中一定数量的`key`，并清除其中已过期的`key`。该策略是前两者的一个折中方案。通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以在不同情况下使得CPU和内存资源达到最优的平衡效果

### 9.`redis` 是单线程的吗，为什么这么快

**单线程**

- 没有了多线程上下文切换的性能损耗
- 没有了访问共享资源加锁的性能损耗
- 开发和调试非常友好，可维护性高

**纯内存操作**

`redis`是一个内存数据库，它的数据都存储在内存中，这意味着我们读写数据都是在内存中完成，这个速度是非常快的。`redis`是一个KV内存数据库，它内部构建了一个哈希表，根据指定的`KEY`访问时，只需要`O(1)`的时间复杂度就可以找到对应的数据。同时，`redis`提供了丰富的数据类型，并使用高效的操作方式进行操作，这些操作都在内存中进行，并不会大量消耗`CPU`资源，所以速度极快

**IO 多路复用技术**

`redis` 服务采用 `Reactor` 的方式来实现文件事件处理器（每一个网络连接其实都对应一个文件描述符）。文件事件处理器使用 I/O 多路复用模块同时监听多个 FD，当 `accept`、`read`、`write` 和 `close` 文件事件产生时，文件事件处理器就会回调 FD 绑定的事件处理器。虽然整个文件事件处理器是在单线程上运行的，但是通过 I/O 多路复用模块的引入，实现了同时对多个 FD 读写的监控，提高了网络通信模型的性能，同时也可以保证整个 `redis` 服务实现的简单





### 参考

* https://blog.csdn.net/Liu_Wd/article/details/108052428
* https://zhuanlan.zhihu.com/p/366972218
* https://houbb.github.io/2019/01/02/db-index-07-combine-index
* https://juejin.cn/post/6860252224930070536
* https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
* https://www.jianshu.com/p/53f0b27dc7e1
* https://sourcegraph.com/github.com/Wasabi1234/Java-Interview-Tutorial/-/blob/%E6%95%B0%E6%8D%AE%E5%AD%98%E5%82%A8/Redis/Redis%E6%8C%81%E4%B9%85%E5%8C%96.md
* https://www.cnblogs.com/kismetv/p/9236731.html
* https://java.isture.com/redis/question/Redis%E4%BF%9D%E8%AF%81%E7%BC%93%E5%AD%98%E4%B8%8E%E6%95%B0%E6%8D%AE%E5%BA%93%E5%8F%8C%E5%86%99%E6%97%B6%E7%9A%84%E6%95%B0%E6%8D%AE%E4%B8%80%E8%87%B4%E6%80%A7.html
* https://www.jianshu.com/p/8aa619933ebb





