有自信了，再战阿里！

MySQL

MySQL的事务的几个特性你知道吗？

知道的，事务有四大特性：

原子性（Atomicity）：一个事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节，而且事务在执行过程中发生错误，会被回滚到事务开始前的状态，就像这个事务从来没有执行过一样，就好比买一件商品，购买成功时，则给商家付了钱，商品到手；购买失败时，则商品在商家手中，消费者的钱也没花出去。
一致性（Consistency）：是指事务操作前和操作后，数据满足完整性约束，数据库保持一致性状态。比如，用户 A 和用户 B 在银行分别有 800 元和 600 元，总共 1400 元，用户 A 给用户 B 转账 200 元，分为两个步骤，从 A 的账户扣除 200 元和对 B 的账户增加 200 元。一致性就是要求上述步骤操作后，最后的结果是用户 A 还有 600 元，用户 B 有 800 元，总共 1400 元，而不会出现用户 A 扣除了 200 元，但用户 B 未增加的情况（该情况，用户 A 和 B 均为 600 元，总共 1200 元）。
隔离性（Isolation）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致，因为多个事务同时使用相同的数据时，不会相互干扰，每个事务都有一个完整的数据空间，对其他并发事务是隔离的。也就是说，消费者购买商品这个事务，是不影响其他消费者购买的。
持久性（Durability）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

这些事务的这四个特性是怎么实现的？

持久性是通过 redo log （重做日志）来保证的；
原子性是通过 undo log（回滚日志）来保证的；
隔离性是通过 MVCC（多版本并发控制）或锁机制来保证的；
一致性则是通过持久性+原子性+隔离性来保证；

多个MySQL中事务一起执行的时候会发生什么问题吗？

可能出现脏读、不可重复读、幻读的问题。

脏读：如果一个事务「读到」了另一个「未提交事务修改过的数据」，就意味着发生了「脏读」现象。
不可重复读：在一个事务内多次读取同一个数据，如果出现前后两次读到的数据不一样的情况，就意味着发生了「不可重复读」现象。
幻读：在一个事务内多次查询某个符合查询条件的「记录数量」，如果出现前后两次查询到的记录数量不一样的情况，就意味着发生了「幻读」现象。

这三个现象的严重性排序如下：

MySQL隔离级别如下：

读未提交，指一个事务还没提交时，它做的变更就能被其他事务看到，可能发生脏读、不可重复读和幻读现象。
读提交，指一个事务提交之后，它做的变更才能被其他事务看到，可能发生不可重复读和幻读现象，但是不可能发生脏读现象；
可重复读，指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，MySQL InnoDB 引擎的默认隔离级别；可能发生幻读现象，但是不可能脏读和不可重复读现象；
串行化；会对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行；脏读、不可重复读和幻读现象都不可能会发生。

MySQL中除了间隙锁还有什么锁？

行级锁的类型主要有三类：

Record Lock，记录锁，也就是仅仅把一条记录锁上；
Gap Lock，间隙锁，锁定一个范围，但是不包含记录本身；
Next-Key Lock：Record Lock + Gap Lock 的组合，锁定一个范围，并且锁定记录本身。

Record Lock 称为记录锁，锁住的是一条记录。而且记录锁是有 S 锁和 X 锁之分的：

当一个事务对一条记录加了 S 型记录锁后，其他事务也可以继续对该记录加 S 型记录锁（S 型与 S 锁兼容），但是不可以对该记录加 X 型记录锁（S 型与 X 锁不兼容）;
当一个事务对一条记录加了 X 型记录锁后，其他事务既不可以对该记录加 S 型记录锁（S 型与 X 锁不兼容），也不可以对该记录加 X 型记录锁（X 型与 X 锁不兼容）。

举个例子，当一个事务执行了下面这条语句：

mysql > begin;
mysql > select * from t_test where id = 1 for update;

就是对 t_test 表中主键 id 为 1 的这条记录加上 X 型的记录锁，这样其他事务就无法对这条记录进行修改了。

当事务执行 commit 后，事务过程中生成的锁都会被释放。

Gap Lock 称为间隙锁，只存在于可重复读隔离级别，目的是为了解决可重复读隔离级别下幻读的现象。

假设，表中有一个范围 id 为（3，5）间隙锁，那么其他事务就无法插入 id = 4 这条记录了，这样就有效的防止幻读现象的发生。

间隙锁虽然存在 X 型间隙锁和 S 型间隙锁，但是并没有什么区别，间隙锁之间是兼容的，即两个事务可以同时持有包含共同间隙范围的间隙锁，并不存在互斥关系，因为间隙锁的目的是防止插入幻影记录而提出的。

Next-Key Lock 称为临键锁，是 Record Lock + Gap Lock 的组合，锁定一个范围，并且锁定记录本身。

假设，表中有一个范围 id 为（3，5] 的 next-key lock，那么其他事务即不能插入 id = 4 记录，也不能修改 id = 5 这条记录。

所以，next-key lock 即能保护该记录，又能阻止其他事务将新纪录插入到被保护记录前面的间隙中。

说一个MySQL死锁的案例

t_order 表里现在已经有了 6 条记录，其中 id 字段为主键索引，order_no 字段普通索引，也就是非唯一索引：

有两事务，一个事务要插入订单 1007 ，另外一个事务要插入订单 1008，因为需要对订单做幂等性校验，所以两个事务先要查询该订单是否存在，不存在才插入记录，过程如下：

可以看到，两个事务都陷入了等待状态，原因：

T1: 事务 a 在执行 select id from t_order where order_no = 1007 for update，会在二级索引（INDEX_NAME : index_order）上加的是 X 型的 next-key 锁，锁范围是(1006, +∞]。
T2: 事务 b 在执行 select id from t_order where order_no = 1008 for update，会在二级索引（INDEX_NAME : index_order）上加的是 X 型的 next-key 锁，锁范围是(1006, +∞]。
T3：事务 a 往事务 A next-key 锁的范围 (1006, +∞] 里插入 id = 1007 的记录就会被锁住：因为当我们执行以下插入语句时，会在插入间隙上获取插入意向锁，而插入意向锁与间隙锁是冲突的，所以当其它事务持有该间隙的间隙锁时，需要等待其它事务释放间隙锁之后，才能获取到插入意向锁
T4：事务 b 往事务 a next-key 锁的范围 (1006, +∞] 里插入 id = 1008 的记录就会被锁住，原因也是一样，申请插入意向锁的时候阻塞了。

案例中的事务 A 和事务 B 在执行完后 select ... for update 语句后，都持有范围为(1006,+∞]的next-key 锁，而接下来的插入操作为了获取到插入意向锁，都在等待对方事务的间隙锁释放，于是就造成了循环等待，导致死锁。

MySQL分库分表之后怎么确保每个表的id都是唯一的？

可以使用雪花算法算法来生成分布式 id，它会生成一个 64 bit 的整数，可以保证不同进程主键的不重复性，以及相同进程主键的有序性。

雪花算法

在同一个进程中，它首先是通过时间位保证不重复，如果时间相同则是通过序列位保证。同时由于时间位是单调递增的，且各个服务器如果大体做了时间同步，那么生成的主键在分布式环境可以认为是总体有序的，这就保证了对索引字段的插入的高效性。

但是雪花算法有缺点，雪花算法是强依赖于时间的，而如果机器时间发生回拨，有可能会生成重复的 ID。可以用美团提供的分布式 ID 解决方案 Leaf，他是不依赖时间戳的，

Redis

Redis数据结构有了解吗？底层实现？

Redis 常见的有五种数据类型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。

Redis 五种数据类型的应用场景：

String 类型的应用场景：缓存对象、常规计数、分布式锁、共享 session 信息等。
List 类型的应用场景：消息队列（但是有两个问题：1. 生产者需要自行实现全局唯一 ID；2. 不能以消费组形式消费数据）等。
Hash 类型：缓存对象、购物车等。
Set 类型：聚合计算（并集、交集、差集）场景，比如点赞、共同关注、抽奖活动等。
Zset 类型：排序场景，比如排行榜、电话和姓名排序等。

各个数据结构的底层实现：

String 类型的底层的数据结构实现主要是 SDS（简单动态字符串）
List 类型的底层数据结构是由双向链表或压缩列表实现的
Hash 类型的底层数据结构是由压缩列表或哈希表实现的
Set 类型的底层数据结构是由哈希表或整数集合实现的：
Zset 类型的底层数据结构是由压缩列表或跳表实现的：

Redis是单线程的吗？

Redis 单线程指的是「接收客户端请求->解析请求 ->进行数据读写等操作->发送数据给客户端」这个过程是由一个线程（主线程）来完成的，这也是我们常说 Redis 是单线程的原因。

但是，Redis 程序并不是单线程的，Redis 在启动的时候，是会启动后台线程（BIO）的：

Redis 在 2.6 版本，会启动 2 个后台线程，分别处理关闭文件、AOF 刷盘这两个任务；
Redis 在 4.0 版本之后，新增了一个新的后台线程，用来异步释放 Redis 内存，也就是 lazyfree 线程。例如执行 unlink key / flushdb async / flushall async 等命令，会把这些删除操作交给后台线程来执行，好处是不会导致 Redis 主线程卡顿。因此，当我们要删除一个大 key 的时候，不要使用 del 命令删除，因为 del 是在主线程处理的，这样会导致 Redis 主线程卡顿，因此我们应该使用 unlink 命令来异步删除大key。

之所以 Redis 为「关闭文件、AOF 刷盘、释放内存」这些任务创建单独的线程来处理，是因为这些任务的操作都是很耗时的，如果把这些任务都放在主线程来处理，那么 Redis 主线程就很容易发生阻塞，这样就无法处理后续的请求了。

后台线程相当于一个消费者，生产者把耗时任务丢到任务队列中，消费者（BIO）不停轮询这个队列，拿出任务就去执行对应的方法即可。

关闭文件、AOF 刷盘、释放内存这三个任务都有各自的任务队列：

BIO_CLOSE_FILE，关闭文件任务队列：当队列有任务后，后台线程会调用 close(fd) ，将文件关闭；
BIO_AOF_FSYNC，AOF刷盘任务队列：当 AOF 日志配置成 everysec 选项后，主线程会把 AOF 写日志操作封装成一个任务，也放到队列中。当发现队列有任务后，后台线程会调用 fsync(fd)，将 AOF 文件刷盘，
BIO_LAZY_FREE，lazy free 任务队列：当队列有任务后，后台线程会 free(obj) 释放对象 / free(dict) 删除数据库所有对象 / free(skiplist) 释放跳表对象；

Java

Java中有哪些常用的容器呢？

List是有序的Collection，使用此接口能够精确的控制每个元素的插入位置，用户能根据索引访问List中元素。常用的实现List的类有LinkedList，ArrayList，Vector，Stack。

ArrayList是容量可变的非线程安全列表，其底层使用数组实现。当几何扩容时，会创建更大的数组，并把原数组复制到新数组。ArrayList支持对元素的快速随机访问，但插入与删除速度很慢。
LinkedList本质是一个双向链表，与ArrayList相比，，其插入和删除速度更快，但随机访问速度更慢。

Set不允许存在重复的元素，与List不同，set中的元素是无序的。常用的实现有HashSet，LinkedHashSet和TreeSet。

HashSet通过HashMap实现，HashMap的Key即HashSet存储的元素，所有Key都是用相同的Value，一个名为PRESENT的Object类型常量。使用Key保证元素唯一性，但不保证有序性。由于HashSet是HashMap实现的，因此线程不安全。
LinkedHashSet继承自HashSet，通过LinkedHashMap实现，使用双向链表维护元素插入顺序。
TreeSet通过TreeMap实现的，添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序。

Map 是一个键值对集合，存储键、值和之间的映射。Key 无序，唯一；value 不要求有序，允许重复。Map 没有继承于 Collection 接口，从 Map 集合中检索元素时，只要给出键对象，就会返回对应的值对象。主要实现有TreeMap、HashMap、HashTable、LinkedHashMap、ConcurrentHashMap

HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突），JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
HashTable：数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap：红黑树（自平衡的排序二叉树）
ConcurrentHashMap：Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后CAS锁）

HashMap是线程不安全的，那有什么线程安全的办法吗？

HashMap不是线程安全的，Hashtable和ConcurrentHashMap 都是线程安全的。

Hashtable和Collections.synchronizedMap返回的装饰器类SynchronizedMap都是通过synchronized关键字来保证多线程操作的线程安全，但使用synchronized会有一个问题，就是锁的粒度太大，同时只能有一个线程进行操作，导致并发度低下，影响了操作的性能。

比如：Hashtable的get和put方法，都使用了关键字synchronized修饰，这就意味着当一个线程调用put方法添加元素时，其它线程不能再同时执行put添加元素，也不能调用get方法获取数据。

为了解决synchronized并发度低的问题，ConcurrentHashMap使用了cas+synchronized解决共享遍历操作原子性问题，使用volatile保障共享变量的内存可见性问题。

Java的线程池有哪些？

ScheduledThreadPool：可以设置定期的执行任务，它支持定时或周期性执行任务，比如每隔 10 秒钟执行一次任务，我通过这个实现类设置定期执行任务的策略。
FixedThreadPool：它的核心线程数和最大线程数是一样的，所以可以把它看作是固定线程数的线程池，它的特点是线程池中的线程数除了初始阶段需要从 0 开始增加外，之后的线程数量就是固定的，就算任务数超过线程数，线程池也不会再创建更多的线程来处理任务，而是会把超出线程处理能力的任务放到任务队列中进行等待。而且就算任务队列满了，到了本该继续增加线程数的时候，由于它的最大线程数和核心线程数是一样的，所以也无法再增加新的线程了。
CachedThreadPool：可以称作可缓存线程池，它的特点在于线程数是几乎可以无限增加的（实际最大可以达到 Integer.MAX_VALUE，为 2^31-1，这个数非常大，所以基本不可能达到），而当线程闲置时还可以对线程进行回收。也就是说该线程池的线程数量不是固定不变的，当然它也有一个用于存储提交任务的队列，但这个队列是 SynchronousQueue，队列的容量为0，实际不存储任何任务，它只负责对任务进行中转和传递，所以效率比较高。
SingleThreadExecutor：它会使用唯一的线程去执行任务，原理和 FixedThreadPool 是一样的，只不过这里线程只有一个，如果线程在执行任务的过程中发生异常，线程池也会重新创建一个线程来执行后续的任务。这种线程池由于只有一个线程，所以非常适合用于所有任务都需要按被提交的顺序依次执行的场景，而前几种线程池不一定能够保障任务的执行顺序等于被提交的顺序，因为它们是多线程并行执行的。
SingleThreadScheduledExecutor：它实际和 ScheduledThreadPool 线程池非常相似，它只是 ScheduledThreadPool 的一个特例，内部只有一个线程。

Java的线程池中有哪几种拒绝策略？能自定义拒绝策略吗？

当线程池的任务队列满了之后，线程池会执行指定的拒绝策略来应对，常用的四种拒绝策略包括：CallerRunsPolicy、AbortPolicy、DiscardPolicy、DiscardOldestPolicy，此外，还可以通过实现RejectedExecutionHandler接口来自定义拒绝策略。

四种预置的拒绝策略：

CallerRunsPolicy，使用线程池的调用者所在的线程去执行被拒绝的任务，除非线程池被停止或者线程池的任务队列已有空缺。
AbortPolicy，直接抛出一个任务被线程池拒绝的异常。
DiscardPolicy，不做任何处理，静默拒绝提交的任务。
DiscardOldestPolicy，抛弃最老的任务，然后执行该任务。
自定义拒绝策略，通过实现接口可以自定义任务拒绝策略。

Spring生命周期说一下

Spring框架中的Bean生命周期可以分为以下几个阶段：

实例化：在这个阶段，Spring容器根据配置或者注解等方式创建Bean的实例。可以通过构造函数实例化或者工厂方法实例化。
属性赋值：在实例化后，Spring容器会为Bean的属性注入值，可以通过setter方法注入或者字段注入。
初始化：在属性赋值完成后，Spring容器会调用Bean的初始化方法进行一些额外的初始化操作。可以通过实现InitializingBean接口或者在配置文件中指定初始化方法。
使用：初始化完成后，Bean可以被正常使用，可以调用其方法进行业务逻辑处理。
销毁：当容器关闭或者手动销毁Bean时，Spring容器会调用Bean的销毁方法进行资源释放等清理操作。可以通过实现DisposableBean接口或者在配置文件中指定销毁方法。

Spring如何解决循环依赖？

Spring 使用三级缓存来解决循环依赖的问题，三级缓存分别是：

singletonObjects： 一级缓存，存储单例对象，Bean 已经实例化，初始化完成。
earlySingletonObjects： 二级缓存，存储 singletonObject，这个 Bean 实例化了，还没有初始化。
singletonFactories： 三级缓存，存储 singletonFactory。

用A<--->B循环依赖配上下面的图来说明

当Spring容器实例化A的时候发现需要B，首先将A放到三级缓存里面去实例B。B实例化的时候需要A，首先B查询一级缓存，发现没有；然后查询二级缓存，知道从三级缓存找到需要的A，然后把A从三级缓存删除并放到二级缓存。此时，B初始化完毕，然后将B放到一级缓存中(此时B中的A依然是创建状态)。此时回来创建A，然后查找B，直接从一级缓存找到B，然后完成A的创建，并将A放到一级缓存中。

Spring 三级缓存只能够解决单例setter注入的循环依赖，而不能解决原型Bean，构造器注入的循环依赖。

系统

linux有几种IO模型？分别说说？

在Linux中一共有5种I/O模型，分别如下:

阻塞 I/O

当程序向kernel发起system call read()时，进程此时阻塞，等待数据就绪(等待kernel读取数据到kernel space)

Process –> systel call –>kernel –> hardware(hard disk)

上面的阻塞并正常情况不会带来太大的资源浪费，因为Kernel从磁盘中读取数据这过程瞬间就能完成。但如果是网络I/O，情况就会变的不同，比如Socket。

上图是blocking I/O发起system call recvfrom()时，进程将一直阻塞等待另一端Socket的数据到来。在这种I/O模型下，我们不得不为每一个Socket都分配一个线程，这会造成很大的资源浪费。

Blocking I/O优缺点都非常明显。优点是简单易用，对于本地I/O而言性能很高。缺点是处理网络I/O时，造成进程阻塞空等，浪费资源。

非阻塞 I/O

非阻塞I/O很容易理解。相对于阻塞I/O在那傻傻的等待，非阻塞I/O隔一段时间就发起system call看数据是否就绪(ready)。

如果数据就绪，就从kernel space复制到user space，操作数据; 如果还没就绪，kernel会立即返回EWOULDBLOCK这个错误。如下图

Non-blocking I/O的优势在于，进程发起I/O操作时，不会因为数据还没就绪而阻塞，这就是”非阻塞”的含义。

但这种I/O模型缺陷过于明显。在本地I/O，kernel读取数据很快，这种模式下多了至少一次system call，而system call是比较消耗cpu的操作。对于Socket而言，大量的system call更是这种模型显得很鸡肋。

I/O 多路复用 (select 、poll、 epoll)

I/O Multiplexing又叫IO多路复用，这是借用了集成电路多路复用中的概念。它优化了非阻塞I/O大量发起system call的问题。

上面介绍的I/O模型都是直接发起I/O操作，而I/O Multiplexing首先向kernel发起system call，传入file descriptor和感兴趣的事件(readable、writable等)让kernel监测，当其中一个或多个fd数据就绪，就会返回结果。程序再发起真正的I/O操作recvfrom读取数据。

在linux中，有3种system call可以让内核监测file descriptors，分别是select、poll、epoll。

信号驱动 I/O (SIGIO)

第一次发起system call不会阻塞进程，kernel的数据就绪后会发送一个signal给进程。进程发起真正的IO操作。

异步 I/O (the POSIX aio_functions)

异步I/O，即I/O操作不会引起进程阻塞。请看上图，发起aio_read请求后，kernel会直接返回。等数据就绪，发送一个signal到process处理数据。

请留意图片细节，程序不需要再次发起读取数据的system call，因为kernel会把数据复制到user space再通知进程处理，整个过程不存在任何阻塞。

其他

Kafka如何保证高可用？
RPC底层实现是怎么样的？
ES搜索引擎底层怎么实现的？

算法

算法题：合并两个有序链表（力扣原题）