【面经】米哈游数据开发一面二面面经

声明：问题从网上搜集，自己补充了答案，不保证准确。

欢迎点击此处关注公众号，每天分享大数据面经。

一面

1.自我介绍

2.MapReduce 的作业过程

见之前的文章。
MapReduce 原理

2.1 Map Task

在这里插入图片描述

Read 阶段：MapTask 通过 InputFormat 获得的 RecordReader，从输入 InputSplit 中解析出一个个 key/value。

Map 阶段：该节点主要是将解析出的 key/value 交给用户编写 map() 函数处理，并产生一系列新的 key/value。

Collect 收集阶段：在用户编写 map() 函数中，当数据处理完成后，一般会调用 OutputCollector.collect() 输出结果。在该函数内部，它会将生成的 key/value 分区（调用 Partitioner），并写入一个环形内存缓冲区中。

Spill 阶段：即“溢写”，当环形缓冲区满后，MapReduce 会将数据写到本地磁盘上，生成一个临时文件。需要注意的是，将数据写入本地磁盘之前，先要对数据进行一次本地排序，并在必要时对数据进行合并、压缩等操作。溢写阶段详情：

步骤 1：利用快速排序算法对缓存区内的数据进行排序，排序方式是，先按照分区编号 Partition 进行排序，然后按照 key 进行排序。这样，经过排序后，数据以分区为单位聚集在一起，且同一分区内所有数据按照 key 有序。
步骤 2：按照分区编号由小到大依次将每个分区中的数据写入任务工作目录下的临时文件 output /spillN.out（N表示当前溢写次数）中。如果用户设置了 Combiner，则写入文件之前，对每个分区中的数据进行一次聚集操作。
步骤 3：将分区数据的元信息写到内存索引数据结构 SpillRecord 中，其中每个分区的元信息包括在临时文件中的偏移量、压缩前数据大小和压缩后数据大小。如果当前内存索引大小超过 1MB，则将内存索引写到文件 output /spillN.out.index 中。
Merge 阶段：当所有数据处理完成后，MapTask 对所有临时文件进行一次合并，以确保最终只会生成一个数据文件。

当所有数据处理完后，MapTask 会将所有临时文件合并成一个大文件，并保存到文件 output/file.out 中，同时生成相应的索引文件 output/file.out.index。
在进行文件合并过程中，MapTask 以分区为单位进行合并。对于某个分区，它将采用多轮递归合并的方式。每轮合并 mapreduce. task.io.sort.factor（默认10）个文件，并将产生的文件重新加入待合并列表中，对文件排序后，重复以上过程，直到最终得到一个大文件。
让每个 MapTask 最终只生成一个数据文件，可避免同时打开大量文件和同时读取大量小文件产生的随机读取带来的开销。

2.2 Shuffle

在这里插入图片描述

Map 方法之后，Reduce 方法之前的数据处理过程称之为 Shuffle。

MapTask 收集 map() 方法输出的 kv 对，放到内存缓冲区中。
Shuffle 中的缓冲区大小会影响到 MapReduce 程序的执行效率，原则上说，缓冲区越大，磁盘 io 的次数越少，执行速度就越快。
环形缓冲区使用率达到阈值会进行快速排序。
从内存缓冲区不断溢出本地磁盘文件，可能会溢出多个文件。
数据处理完成后会对磁盘上所有文件进行归并排序。
多个溢出文件会被合并成大的溢出文件。
在溢出过程及合并的过程中，都要调用 Partitioner 进行分区和针对 key 进行排序。
默认分区是根据 key 的 hashCode 对 ReduceTask 的个数取模得到的。用户无法控制哪个 key 存储到哪个分区。
可以自定义 Partitioner，控制分区代码逻辑。
ReduceTask 根据自己的分区号，去各个 MapTask 机器上取相应的结果分区数据。
ReduceTask 会抓取到同一个分区的来自不同 MapTask 的结果文件，ReduceTask 会将这些文件再进行合并（归并排序）。
合并成大文件后，Shuffle 的过程也就结束了，后面进入 ReduceTask 的逻辑运算过程（从文件中取出一个一个的键值对 Group，调用用户自定义的 reduce() 方法）。

2.3 Reduce Task

在这里插入图片描述

Copy 阶段：ReduceTask 从各个 MapTask 上远程拷贝一片数据，并针对某一片数据，如果其大小超过一定阈值，则写到磁盘上，否则直接放到内存中。

Merge 阶段：在远程拷贝数据的同时，ReduceTask 启动了两个后台线程对内存和磁盘上的文件进行合并，以防止内存使用过多或磁盘上文件过多。

Sort 阶段：按照 MapReduce 语义，用户编写 reduce() 函数输入数据是按 key 进行聚集的一组数据。为了将 key相同的数据聚在一起，Hadoop 采用了基于排序的策略。由于各个 MapTask 已经实现对自己的处理结果进行了局部排序，因此，ReduceTask 只需对所有数据进行一次归并排序即可。

Reduce 阶段：reduce() 函数将计算结果写到 HDFS 上。

2.4 Combiner

Combiner 是 Mapper 和 Reducer 之外的一种组件，其父类是 Reducer。

Combiner 和 Reducer 的区别是 Combiner 运行在每一个 MapTask 所在的节点。
作用是进行局部汇总，减少网络的传输量。

3.OutputFormat

数据输出的接口。实现类包括：

TextOutputFormat。
SequenceOutputFormat。
自定义 OutputFormat。

4.Join

4.1 Reduce Join

合并操作在 Reduce 阶段完成，Reduce 端处理压力大，Map 端运算负载低，资源利用率不高，容易发生数据倾斜。

4.2 Map Join

适用于一张小表，一张大表。

3.MySQL 的事务实现

这里简答说一下怎么回答。毕竟是面试题，不可能回答到所有细节，所以需要回答到关键词，然后串联起来，比较通顺即可。总结如下就是：

事务的原子性是通过 undo log 来实现的。
事务的持久性性是通过 redo log 来实现的。
事务的隔离性是通过（读写锁 + MVCC）来实现的。
一致性是通过原子性，持久性，隔离性来实现的。

这是结论。抛出结论后，可以简单阐述原因：

（1）事务有四个特性：

原子性（Atomicity）：语句要么全执行，要么全不执行，是事务最核心的特性，事务本身就是以原子性来定义的。实现主要基于 undo log 日志。
持久性（Durability）：保证事务提交后不会因为宕机等原因导致数据丢失。实现主要基于 redo log 日志。
隔离性（Isolation）：保证事务执行尽可能不受其他事务影响。InnoDB 默认的隔离级别是 RR，RR 的实现主要基于锁机制、数据的隐藏列、undo log 和类next-key lock 机制。
一致性（Consistency）：事务追求的最终目标，一致性的实现既需要数据库层面的保障，也需要应用层面的保障。

（2）要实现上面的特性，需要用到下面的技术：

redo log 与 undo log 介绍
MySQL 锁技术以及 MVCC 基础

a。undo log：回滚日志，用于记录数据被修改前的信息。在发生错误时回滚之前的操作，需要将之前的操作都记录下来，然后在发生错误时才可以回滚。保证了未提交事务的原子性。

b。redo log：重做日志，用来记录已成功提交事务的修改信息，并且会把 redo log 持久化到磁盘，系统重启之后在读取 redo log 恢复最新数据。redo log 用来恢复数据，用于保障已提交事务的持久化特性。

c。MySQL 锁技术：通过读写锁，可以做到读读可以并行，但是不能做到写读，写写并行。事务的隔离性就是根据读写锁来实现的。

共享锁(shared lock)，又叫做"读锁"，读锁是可以共享的，或者说多个读请求可以共享一把锁读数据，不会造成阻塞。
排他锁(exclusive lock)，又叫做"写锁"，写锁会排斥其他所有获取锁的请求，一直阻塞，直到写入完成释放锁。

d。MVCC 基础：MVCC (MultiVersion Concurrency Control) 叫做多版本并发控制。通过在每行记录的后面保存两个隐藏的列来实现的。这两个列，一个保存了行的创建时间，一个保存了行的过期时间，当然存储的并不是实际的时间值，而是系统版本号。MVCC 在 MySQL 中的实现依赖的是 undo log 与 read view。

undo log：undo log 中记录某行数据的多个版本的数据。
read view：用来判断当前版本数据的可见性。

4.MySQL 的数据结构

问题不太清晰。如果是指数据类型，那么应该是数字类型、字符串类型、日期时间类型、二进制类型、空间数据类型。

如果是存储引擎的数据结构，那应该是 B+Tree。MySQL 将所有的数据都放到了叶子节点中，而根节点和非叶子节点中放的都是冗余的索引 Key，树高度只有 3，就是说我们只需要三次磁盘的 io 就可以完成查找，还可以将根节点放到磁盘中，这样就只需要两次，速度也是相当于快。非叶子节点存储索引和下一个子节点的地址，叶子结点存储所有的索引和数据。

5.MySQL 索引加在哪里

索引的优势：提高查询效率（降低 IO 使用率），降低 CPU 使用率。

索引的分类：单值索引，唯一索引，联合索引，主键索引。

索引要加对才能提高速度。这里举一个例子：

大学选认课老师，需要创建一个关系对应表，有三个字段 id、student_id、teacher_id，想要查询某个老师和某个学生是否存在师生关系。

select * from tb where student_id='S123’ and teacher_id='T123'

（1）student_id 和 teacher_id 各自单独建立索引

这种情况下，不管 MySQL 选用了哪个索引字段用来查询，都会一次查询出多个记录然后逐一遍历。比如查询中使用了 student_id 列的索引，那么就会查询出 S123 和多个教师编号的对应关系，然后再一条条遍历找到教师编号 T123。

（2）student_id 和 teacher_id 的联合索引

这种索引的切合度最好，MySQL 会直接选用这个索引。而且联合索引会在相同的 student_id 下将 teacher_id 排好序。使定位学生和教师的关联关系更加高效。

总结：索引加在经常查找的查询中 where 过滤条件的字段上。

6.HDFS 的一个节点读两个节点写，读到什么写到什么

没理解问题想问什么。可以看之前的文章。

7.因为我有两个项目涉及到爬虫，就问了几个爬虫的

8. Java 类加载

类加载机制：java 虚拟机将编译后的 class 文件加载到内存中，进行校验、转换、解析和初始化，到最终的使用。这就是 java 类加载机制。包括加载（Loading）、验证（Verification）、准备（Preparation）、解析（Resolution）、初始化（Initialization）、使用（Using）、卸载（Unloading）等阶段。

重点是类加载器，系统提供的 3 种类加载器如下：

1）启动类加载器（Bootstrap ClassLoader）：负责将存放在 <JAVA_HOME>\lib 目录中，或者被 -Xbootclasspath 参数所指定的路径中的，并且是虚拟机识别的类库加载到虚拟机内存中。（注：仅按照文件名识别，如 rt。jar，名字不符合的类库即使放在lib目录中也不会被加载）。

2）扩展类加载器（Extension ClassLoader）：负责加载 <JAVA_HOME>\lib\ext 目录中的，或被 java。ext。dirs 系统变量所指定的路径中的所有类库，开发者可以直接使用扩展类加载器。

3）应用程序类加载器（Application ClassLoader）：负责加载用户路径（ClassPath）上所指定的类库，开发者可以直接使用这个类加载器，一般情况下该类加载是程序中默认的类加载器。

类加载器的执行顺序采用双亲委派模型：如果一个类加载器收到类加载的请求，他首先不会自己去尝试加载这个类，而是把请求委派给父类加载器去完成，每一层次的类加载器都是这样，因此所有的加载请求最终都应该传送到底层的启动类加载器中，只有当父类加载器反馈自己无法完成这个加载请求时（在它的加载路径下没有找到所需加载的Class），子类加载器才会尝试去加载。

好处：

1）避免重复加载同一个类；

2）防止用户任意修改 java 中的类。

9. Java 多线程的生命周期

1。新建状态(new)

Thread t = new Thread();

2。可运行状态(runnable)

分成两种状态，ready 和 running。分别表示就绪状态和运行状态。

就绪状态:线程对象调用 start 方法之后，等待 JVM 的调度(此时该线程并没有运行)。
运行状态:线程对象获得 JVM 调度，如果存在多个 CPU，那么允许多个线程并行运行。

3。阻塞状态(blocked)

正在运行的线程因为某些原因放弃CPU，暂时停止运行，就会进入阻塞状态。此时JVM不会给线程分配CPU，直到线程重新进入就绪状态，才有机会转到运行状态。阻塞状态只能先进入就绪状态，不能直接进入运行状态。阻塞状态的两种情况:

当 A 线程处于运行过程时，试图获取同步锁时，却被 B 线程获取。此时 JVM 把当前 A 线程存到对象的锁池中，A 线程进入阻塞状态。
当线程处于运行过程时，发出了 IO 请求时，此时进入阻塞状态。

4。等待状态(waiting)：等待状态只能被其他线程唤醒

此时使用的无参数的 wait 方法，当线程处于运行过程时，调用了 wait() 方法，此时 JVM 把当前线程存在对象等待池中。

5。计时等待状态(timed waiting)：使用了带参数的wait方法或者sleep方法

当线程处于运行过程时，调用了 wait(long time) 方法，此时 JVM 把当前线程存在对象等待池中。
当前线程执行了 sleep(long time) 方法。

6。终止状态(terminated)

通常称为死亡状态，表示线程终止。

正常执行完 run 方法而退出(正常死亡)。
遇到异常而退出。

10. MapReduce 怎么做矩阵乘法

例如两个矩阵 A 和 B 相乘得到 C，实际上是 A 的行和 B 的列相乘。关键之处是设计 key，让参与运算的值传递到同一个 Reducer 中。分析：

a11 会被 c11、c12、…、c1m 用到，即 Map 阶段 A 的元素要分成 m 个 <key, value> 对；
b11 会被 c11、c21、…、cn1 用到，即 Map 阶段 B 的元素要分成 n 个 <key, value> 对；
c11 的计算会用到 a11、a12、… 和 b11、b21、…，即 a11、a12、… 和 b11、b21、… 的 key 应该相同才会被分到同一个 Reducer。

因此，

key 应该设计为 key = (i, k)，其中 i 来自 aij，k 来自 bjk；
A 的 value 设计为 value = (‘a’, j, aij)；
B 的 value 设计为 value = (‘b’, j, bjk)。

在 Shuffle 阶段，相同 key 的 value 会被加入到同一个列表中，形成 <key, list(value)> 对，传递给 Reducer，这个由 Hadoop 自动完成。接下来我们所要做的，就是把 list(value) 解析出来，来自 A 的元素，单独放在一个数组中，来自 B 的元素，放在另一个数组中，然后，我们计算两个数组（各自看成一个向量）的点积，即可算出。

11.Hadoop1.0 和 2.0 和 3.0 的区别

1.x 和 2.x：

Hadoop 2.0 新增了 HDFS HA 机制，HA 增加了standbynamenode 进行热备份，解决了 1.0 的单点故障问题。
Hadoop 2.0 新增了 HDFS federation，解决了 HDFS 水平可扩展能力。
Hadoop 2.0相比于Hadoop 1.0 新增了 YARN 框架。

2.x 和 3.x：

Java运行环境升级为1.8；
HDFS 支持纠删码：纠删码相比于副本机制节省了一半以上的存储空间，普通副本机制需要3倍存储空间而这种机制只需1.4倍即可。
YARN时间线服务
支持多余 2 个以上的 NameNode：3.0 支持单 active namenod e+ 多 standby namenode 部署方式进一步提升了可用性。
MapReduce 本地优化，性能提升了30%。

12.HDFS HA 怎么实现热备份，这种方式有什么问题

HDFS HA 功能通过配置 Active/Standby 两个 NameNodes 实现在集群中对 NameNode 的热备来。

元数据管理方式需要改变。
- 内存中各自保存一份元数据；
- Edits 日志只有 Active 状态的 NameNode 节点可以做写操作；
- 所有的 NameNode 都可以读取 Edits；
- 共享的 Edits 放在一个共享存储中管理（qjourna l和 NFS 两个主流实现）。
需要一个状态管理功能模块。
- 实现了一个 zkfailover，常驻在每一个 namenode 所在的节点，每一个 zkfailover 负责监控自己所在 NameNode 节点，利用 zk 进行状态标识；
- 当需要进行状态切换时，由 zkfailover 来负责切换，切换时需要防止 brain split 现象的发生。
必须保证两个 NameNode 之间能够 ssh 无密码登录。
隔离（Fence），即同一时刻仅仅有一个 NameNode 对外提供服务

13.系统 CPU 占用98%了，你咋办

看是否真的是计算密集型任务太多。kill 掉一些任务。

14.进程之间怎么通信

管道：所谓的管道，就是内核里面的一串缓存，从管道的一端写入的数据，实际上是缓存在内核中的，另一端读取，也就是从内核中读取这段数据。另外，管道传输的数据是无格式的流且大小受限。先进先出，单向的，效率低，不适合进程间频繁地交换数据。

对于匿名管道，它的通信范围是存在父子关系的进程；
对于命名管道，它可以在不相关的进程间也能相互通信。

消息队列：消息队列是保存在内核中的消息链表，A 进程要给 B 进程发送消息，A 进程把数据放在对应的消息队列后就可以正常返回了，B 进程需要的时候再去读取数据就可以了。消息队列不适合比较大数据的传输。消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销。

共享内存：共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。不需要拷贝来拷贝去，大大提高了进程间通信的速度。

信号量：信号量其实是一个整型的计数器，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。通过 PV 操作防止多个进程同时修改同一个共享内存。

信号：上面说的进程间通信，都是常规状态下的工作模式。对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。信号是进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程，一旦有信号产生，我们就有下面这几种，用户进程对信号的处理方式。

执行默认操作；
捕捉信号；
忽略信号。

Socket：用于跨网络与不同主机上的进程之间通信。

二面

1.自我介绍

2.爬虫网络出问题咋办

3.Spark 的 OOM 可能是因为什么

看一下 Spark 的内存模型。

Storage 内存是存储 broadcast，cache，persist 数据的地方。

Other 内存是程序执行时预留给自己的内存。

OOM 的问题通常出现在 execution 这块内存中，因为 storage 这块内存在存放数据满了之后，会直接丢弃内存中旧的数据，对性能有影响但是不会有 OOM 的问题。

Spark 中的 OOM 问题不外乎以下三种情况：

map 执行中内存溢出：在单个 map 中产生了大量的对象导致的。解决方法是通过减少每个 task 的大小来减少 Executor 内存中的数量，具体做法是在调用 map 操作前先调用 repartition 方法，增大分区数来减少每个分区的大小，再传入 map 中进行操作。
shuffle 后内存溢出：shuffle 后，shuffle 会产生数据倾斜，少数的 key 内存非常的大，它们都在同一个 Executor 中计算，导致运算量加大甚至会产生 OOM。
driver 内存溢出：可能有如下三种情况。前两种情况发生在 executor 中，最后情况发生在 driver 中。
- 用户在 Driver 端口生成大对象, 比如创建了一个大的集合数据结构。解决思路：考虑将该大对象转化成 Executor 端加载。例如调用 sc.textFile/ sc.hadoopFile 等。如若无法避免, 自我评估该大对象占用的内存, 相应增加 driver-memory 的值。
- 从 Executor 端收集数据回 Driver 端。解决思路：本身不建议将大的数据从 Executor 端 collect 回来。建议将 Driver 端对 collect 回来的数据所做的操作，转化成 Executor 端 RDD 操作。如若无法避免, 自我评 collect 需要的内存, 相应增加 driver-memory 的值。
- Spark 本身框架的数据消耗。解决思路：考虑缩小大 numPartitions 的 Stage 的 partition 个数, 例如从 HDFS load 的 partitions 一般自动计算, 但是后续用户的操作中做了过滤等操作已经大大减少数据量, 此时可以缩小 Parititions。通过参数 spark.ui.retainedStages（默认 1000）/ spark.ui.retainedJobs（默认 1000）控制。实在没法避免, 相应增加内存。

4.Spark的宽窄算子

窄依赖举例：map。

宽依赖举例：groupByKey。

5.spark 的 groupByKe y和 reduceByKey 区别

从 shuffle 的角度：reduceByKey 和 groupByKey 都存在 shuffle 的操作，但是 reduceByKey 可以在 shuffle 前对分区内相同 key 的数据进行预聚合（combine）功能，这样会减少落盘的数据量，而 groupByKey 只是进行分组，不存在数据量减少的问题，reduceByKey 性能比较高。

从功能的角度：reduceByKey 其实包含分组和聚合的功能。groupByKey 只能分组，不能聚合，所以在分组聚合的场合下，推荐使用 reduceByKey，如果仅仅是分组而不需要聚合。那么还是只能使用 groupByKey。

6.Spark 和 mr 的 shuffle 有啥区别

可以看下面两篇文章。

Shuffle 过程本质上都是将 Map 端获得的数据使用分区器进行划分，并将数据发送给对应的 Reducer 的过程。

区别：

从逻辑角度来讲，Shuffle 过程就是一个 GroupByKey 的过程，两者没有本质区别。只是 MapReduce 为了方便 GroupBy 存在于不同 partition 中的 key/value records，就提前对 key 进行排序。Spark 认为很多应用不需要对 key 排序，就默认没有在 GroupBy 的过程中对 key 排序。
从数据流角度讲，两者有差别。MapReduce 只能从一个 Map Stage shuffle 数据，Spark 可以从多个 Map Stages shuffle 数据。

7.java 的 GC 算法，CMS 和 G1

GC 算法：

引用计数法 应用于：微软的COM/ActionScrip3/Python等
- 如果对象没有被引用，就会被回收，缺点：需要维护一个引用计算器
复制算法 年轻代中使用的是Minor GC，这种GC算法采用的是复制算法(Copying)
- 效率高，缺点：需要内存容量大，比较耗内存
- 使用在占空间比较小、刷新次数多的新生区
标记清除 老年代一般是由标记清除或者是标记清除与标记整理的混合实现
- 效率比较低，会差生碎片。
标记压缩 老年代一般是由标记清除或者是标记清除与标记整理的混合实现
- 效率低速度慢，需要移动对象，但不会产生碎片。
标记清除压缩标记清除-标记压缩的集合，多次GC后才Compact
- 使用于占空间大刷新次数少的养老区，是3 4的集合体

GMS 和 G1：

CMS（Concurrent Mark Sweep）收集器是一种以获取最短回收停顿时间为目标的收集器，基于并发“标记清理”实现,在标记清理过程中不会导致用户线程无法定位引用对象。仅作用于老年代收集。

初始标记（CMS initial mark）：独占CPU，stop-the-world, 仅标记GCroots能直接关联的对象,速度比较快；
并发标记（CMS concurrent mark）:可以和用户线程并发执行，通过GCRoots Tracing 标记所有可达对象；
重新标记（CMS remark）：独占CPU，stop-the-world, 对并发标记阶段用户线程运行产生的垃圾对象进行标记修正,以及更新逃逸对象；
并发清理（CMS concurrent sweep）：可以和用户线程并发执行，清理在重复标记中被标记为可回收的对象。

G1 收集器弱化了 CMS 原有的分代模型（分代可以是不连续的空间），将堆内存划分成一个个Region 1MB~32MB，默认 2048 个分区），这么做的目的是在进行收集时不必在全堆范围内进行。它主要特点在于达到可控的停顿时间，用户可以指定收集操作在多长时间内完成，即 G1提供了接近实时的收集特性。它的步骤如下：

初始标记（Initial Marking）：标记一下GC Roots能直接关联到的对象，伴随着一次普通的Young GC发生，并修改NTAMS（Next Top at Mark Start）的值，让下一阶段用户程序并发运行时，能在正确可用的Region中创建新对象，此阶段是stop-the-world操作。
根区间扫描，标记所有幸存者区间的对象引用，扫描 Survivor到老年代的引用，该阶段必须在下一次Young GC 发生前结束。
并发标记（Concurrent Marking）：是从GC Roots开始堆中对象进行可达性分析，找出存活的对象，这阶段耗时较长，但可与用户程序并发执行，该阶段可以被Young GC中断。
最终标记（Final Marking）：是为了修正并发标记期间因用户程序继续运作而导致标记产生变动的那一部分标记记录，虚拟机将这段时间对象变化记录在线程Remembered Set Logs里面，最终标记阶段需要把Remembered Set Logs的数据合并到Remembered Set中，此阶段是stop-the-world操作，使用snapshot-at-the-beginning (SATB) 算法。
筛选回收（Live Data Counting and Evacuation）：首先对各个Region的回收价值和成本进行排序，根据用户所期望的GC停顿时间来制定回收计划,回收没有存活对象的Region并加入可用Region队列。这个阶段也可以做到与用户程序一起并发执行，但是因为只回收一部分Region，时间是用户可控制的，而且停顿用户线程将大幅提高收集效率。

7.如果我要分配一个对象，这个对象已经超过了一个 region 的大小，这时会发生什么情况

Region 中有一种特殊的 Humongous Region，专门用来存储大对象。G1 收集器规定只要对象的大小超过了 Region 大小的一般就会被认为是巨型对象。每个 Region 的大小可以通过 -XX:G1HeapRegionSize 来调整(1MB-32MB，且为 2 的 N 次幂)。G1 收集器通常把 Humongous Region 看做老年代的一部分。对象划分的规则：

对象大小小于一半 Region，直接存储到标记为 Eden 的 Region；
对象大小大于一半 Region 但是小于一个 Region，存储到标记为 Humongous 的 Region 中；
对象大小超过一个 Region 大小，存储到标记为 Humongous 的多个连续 Region 中。

8.MySQL 的两个引擎的区别，聚簇索引和非聚簇索引

MyISAM：

用途：访问的速度快，以 SELECT、INSERT 为主的应用
索引：B tree，FullText，R-tree
锁：表锁
事务：不支持事务
其他：不支持外键。每个 MyISAM 在磁盘上存储成三个文件。第一个文件的名字以表的名字开始，扩展名指出文件类型。 .frm文件存储表定义。数据文件的扩展名为 .MYD (MYData)。索引文件的扩展名是 .MYI (MYIndex)。

InnoDB：

用途：大部分情况下选择 InnoDB，除非需要用到某些 InnoDB不具备的特性，并且没有其他办法可以替代，否则都应该优先选择 InnoDB 引擎。
索引：B+ tree，hash(引擎自适应，无法人为干预)，FullText(5.6开始)
锁：行锁
事务：支持
其他：对比 MyISAM 的存储引擎，InnoDB 写的处理效率差一些，并且会占用更多的磁盘空间以保存数据和索引。InnoDB 所有的表都保存在同一个数据文件中，InnoDB 表的大小只受限于操作系统文件的大小限制。MyISAM 只缓存索引，不缓存真实数据；InnoDB 不仅缓存索引还要缓存真实数据，对内存要求较高，而且内存大小对性能有决定性的影响。

聚簇索引和非聚集索引：

聚集索引的顺序就是数据的物理存储顺序。它会根据聚集索引键的顺序来存储表中的数据，即对表的数据按索引键的顺序进行排序，然后重新存储到磁盘上。因为数据在物理存放时只能有一种排列方式，所以一个表只能有一个聚集索引。
非聚集索引：索引顺序与物理存储顺序不同。非聚集索引的使用场合为：查询所获数据量较少时；某字段中的数据的唯一性比较高时。
例：比如字典中，用‘拼音’查汉字，就是聚集索引。因为正文中字都是按照拼音排序的。而用‘偏旁部首’查汉字，就是非聚集索引，因为正文中的字并不是按照偏旁部首排序的，我们通过检字表得到正文中的字在索引中的映射，然后通过映射找到所需要的字。

9.事务的性质，一致性指的是，分布式事务

事务有四个特性：

原子性（Atomicity）：事务的最小执行的执行的单位，不允许分割。事务的原子性确保动作要么全部成功，要么全部不成功。
持久性（Durability）：一个事务被提交之后。他对数据库的改变是持久的，即使是数据库发生故障也不应该对其收到影响。
隔离性（Isolation）：并发访问数据库时，一个用户的事务不被其他事务所干扰，各并发事务之间数据库是独立的。
一致性（Consistency）：执行事务前后，数据保持一致性，多个事务对同一数据读取的结果是相同的。

分布式事务：

分布式事务指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于不同的分布式系统的不同节点之上,且属于不同的应用，分布式事务需要保证这些操作要么全部成功，要么全部失败。本质上来说，分布式事务就是为了保证不同数据库的数据一致性。

10.两阶段提交和三阶段提交

问题：在分布式系统中，为了保证数据的高可用，通常会将数据保留多个副本(replica)，这些副本会放置在不同的物理的机器上。在数据有多份副本的情况下，如果网络、服务器或者软件出现故障，会导致部分副本写入成功，部分副本写入失败。这就造成各个副本之间的数据不一致，数据内容冲突，造成事实上的数据不一致。

解决：增加一个协调机制来解决数据不一致问题。两阶段提交和三阶段提交都是通过引入一个协调者来进行协调。

两阶段提交：

请求阶段：事务协调者通知每个参与者准备提交或取消事务，然后进入表决过程，参与者要么在本地执行事务，写本地的 redo 和 undo 日志，但不提交，到达一种"万事俱备，只欠东风"的状态。请求阶段，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。
提交阶段：在该阶段，写调整将基于第一个阶段的投票结果进行决策: 提交或取消。当且仅当所有的参与者同意提交事务，协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行响应的操作。
解决了哪些问题：在正常的情况下，如果第一阶段某些参与者出现问题，那么其他所有参与者都能够知道事务失败了，可以执行取消操作，数据保持了一致性。如果所有的参与者都能够执行成功，那么在提交阶段，所有事务提交，数据也是一致的。
还有哪些问题：
- 阻塞：在请求和提交阶段都是阻塞的，多个参与者都要进行决策，阻塞时间边长，如果出现网络问题，长时间等待阻塞。
- 单点故障：协调者的作用非常重要，协调者挂了，参与者长期阻塞。
- 不一致：如果协调者在提交阶段中间挂了，某些参与者收到了提交命令，某些参与者没有收到，还是会出现数据不一致情况。

三阶段提交：三阶段提交协议在协调者和参与者中都引入超时机制，并且把两阶段提交协议的第一个阶段分成了两步: 询问，然后再锁资源，最后真正提交。

canCommit 阶段：协调者向参与者发送 commit 请求，参与者如果可以提交就返回 yes 响应，否则返回 no 响应。
preCommit 阶段：协调者根据参与者 canCommit 阶段的响应来决定是否可以继续事务的 preCommit 操作。根据响应情况，有下面两种可能：
- 协调者从所有参与者得到的反馈都是yes：那么进行事务的预执行，协调者向所有参与者发送 preCommit 请求，并进入 prepared 阶段。参与者接收到 preCommit 请求后会执行事务操作，并将 undo 和 redo 信息记录到事务日志中。如果一个参与者成功地执行了事务操作，则返回 ACK 响应，同时开始等待最终指令。
- 协调者从所有参与者得到的反馈有一个是 No 或是等待超时之后协调者都没收到响应：那么就要中断事务，协调者向所有的参与者发送 abort 请求。参与者在收到来自协调者的 abort 请求，或超时后仍未收到协调者请求，执行事务中断。
doCommit 阶段：协调者根据参与者 preCommit 阶段的响应来决定是否可以继续事务的 doCommit 操作。根据响应情况，有下面两种可能：
- 协调者从参与者得到了 ACK 的反馈：协调者接收到参与者发送的 ACK 响应，那么它将从预提交状态进入到提交状态，并向所有参与者发送 doCommit 请求。参与者接收到 doCommit 请求后，执行正式的事务提交，并在完成事务提交之后释放所有事务资源，并向协调者发送 haveCommitted 的 ACK 响应。协调者收到这个 ACK 响应之后，完成任务。
- 协调者从参与者没有得到 ACK 的反馈, 也可能是接收者发送的不是 ACK 响应，也可能是响应超时：执行事务中断。
解决了哪些问题：
- 减少阻塞；
- 如果第一个阶段，参与者挂了，或者协调者挂了，最终数据都是一致的，因为超时机制，也不会一直等待。
还有哪些问题：如果进入 PreCommit 后，Coordinator 发出的是 abort 请求，假设只有一个 Cohort 收到并进行了 abort 操作，而其他对于系统状态未知的 Cohort 会根据 3PC 选择继续 Commit，此时系统状态发生不一致性。

11.排序算法的时间复杂度

12.快排什么情况下最差，基本有序时用什么

快排的运行时间依赖于划分是否平衡。在分解时每次选择的主元素都是最大或最小元素时最差，比如在基本有序时，每次选择最左边的元素为主元素。

基本有序时选择直接插入排序。

冒泡排序也可以考虑，设置一个标志位，没有发生移动就提前结束排序。

13.两个栈怎么实现一个队列

14.1000 个几 G 的文件，怎么在 16G 机子上排序

先对每个文件排序，得到 1000 个局部有序的文件 file1，file2，…，file1000，存放在磁盘。
多路归并：将每一个小文件的第一个数取出，即每一个小文件里的最小数，对这些数进行排序（可以维护一个 size 为 1000 的小根堆），将这些数里的最小数字 numi 写入大文件第一行，该数字来自 filei。
将 filei 的下一个数字读入继续第 2 步的操作。重复直到全部排好序。

15.满二叉树和完全二叉树的区别

满二叉树：指深度为 k 且有 2^k-1 个结点的二叉树。即最后一层全为叶子结点，其它层都是非叶子结点。

完全二叉树：当二叉树的深度为 h 时，它的 h 层节点必须都是连续靠左并不可隔开的(满二叉树也符合)，并且 1～h-1 层的结点数都达到最大个数（即 1~h-1 层为一个满二叉树）。

16.Hive 接触过吗

17.synchronized 和 lock 的区别

区别如下：

异常是否释放锁：synchronized 在发生异常时候会自动释放占有的锁，因此不会出现死锁；而 lock 发生异常时候，不会主动释放占有的锁，必须手动 unlock 来释放锁，可能引起死锁的发生。（所以最好将同步代码块用 try catch 包起来，finally 中写入 unlock，避免死锁的发生。）
是否响应中断：lock 等待锁过程中可以用 interrupt 来中断等待，而 synchronized 只能等待锁的释放，不能响应中断；
是否知道获取锁：Lock 可以通过 trylock 来知道有没有获取锁，而 synchronized 不能；
Lock 可以提高多个线程进行读操作的效率。（可以通过 readwritelock 实现读写分离）
在性能上来说，如果竞争资源不激烈，两者的性能是差不多的，而当竞争资源非常激烈时（即有大量线程同时竞争），此时 Lock 的性能要远远优于 synchronized。所以说，在具体使用时要根据适当情况选择。
synchronized 使用 Object 对象本身的 wait 、notify、notifyAll 调度机制，而 Lock 可以使用 Condition 进行线程之间的调度。

性能区别：

synchronized 是托管给 JVM 执行的。
- 在 Java1.5 中，synchronize 是性能低效的。因为这是一个重量级操作，需要调用操作接口，导致有可能加锁消耗的系统时间比加锁以外的操作还多。相比之下使用 Java 提供的 Lock 对象，性能更高一些。
- 但是到了 Java1.6，发生了变化。synchronize 在语义上很清晰，可以进行很多优化，有适应自旋，锁消除，锁粗化，轻量级锁，偏向锁等等。导致在 Java1.6 上 synchronize 的性能并不比 Lock 差。官方也表示，他们也更支持 synchronize，在未来的版本中还有优化余地。
而 lock 是 java 写的控制锁的代码。

18.lock 的底层实现

synchronized 原始采用的是 CPU 悲观锁机制，即线程获得的是独占锁。独占锁意味着其他线程只能依靠阻塞来等待线程释放锁。而在 CPU 转换线程阻塞时会引起线程上下文切换，当有很多线程竞争锁的时候，会引起 CPU 频繁的上下文切换导致效率很低。

而 Lock 用的是乐观锁方式。所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。乐观锁实现的机制就是 CAS 操作（Compare and Swap）。我们可以进一步研究 ReentrantLock 的源代码，会发现其中比较重要的获得锁的一个方法是 compareAndSetState。这里其实就是调用的CPU提供的特殊指令。现代的 CPU 提供了指令，可以自动更新共享数据，而且能够检测到其他线程的干扰，而 compareAndSet() 就用这些代替了锁定。这个算法称作非阻塞算法，意思是一个线程的失败或者挂起不应该影响其他线程的失败或挂起的算法。

19.notify 和 notifyAll 的区别

notify() 和 notifyAll() 都是 Object 对象用于通知处在等待该对象的线程的方法。两者的最大区别在于：

notifyAll 使所有原来在该对象上等待被 notify 的所有线程统统退出 wait 的状态，变成等待该对象上的锁，一旦该对象被解锁，他们就会去竞争。
notify 则文明得多，它只是选择一个 wait 状态线程进行通知，并使它获得该对象上的锁，但不惊动其他同样在等待被该对象 notify 的线程们，当第一个线程运行完毕以后释放对象上的锁此时如果该对象没有再次使用 notify 语句，则即便该对象已经空闲，其他 wait 状态等待的线程由于没有得到该对象的通知，继续处在 wait 状态，直到这个对象发出一个 notify 或 notifyAll，它们等待的是被notify 或 notifyAll，而不是锁。