阿里面试总结

一面：

1. 刚开始面试就是对简历项目一顿撕，PV和UV是怎么计算的，UV怎么进行去重的？不用ES该如何实现去重？

这个项目我还准备了下，结果答的还是不太好,

2. 说说flink,spark streaming,storm的区别？

活题，随便答；

3.

3. spark的调度执行逻辑，stage，宽依赖和窄依赖，容错机制？

容错机制：

窄依赖可以通过血缘关系 来恢复故障RDD，而宽依赖则考虑使用 检查点 的方式恢复。

RDD的容错机制是 如何实现的？

1. 借助这些依赖关系，DAG可以认为这些RDD之间形成了 lineage(血统，血缘关系)，借助lineage ，能保证一个RDD在计算前，它的父RDD已经完成了计算，并实现了RDD的容错。

2. 当某个RDD发生故障需要恢复时，从数据源逐步执行对应的transformation操作来重新生成当前的RDD，这种容错策略 要高于 常用的 检查点 （Check Pointing）策略。

CheckPoint(将RDD持久化到磁盘上):

调度执行逻辑：

依赖关系：

依赖 关系：

1.  窄依赖【Narrow Dependency 】（1:1）：如 map ->flatMap等。

2. 宽依赖【Wide Dependency 】（1：多）：如groupByKey()等。

Shuffle：

存在spark shuffle :

因为具有某种共同的特征的一类数据需要最终汇聚 （aggregate）到一个计算节点进行计算 ，这个数据重新打乱然后汇聚到不同节点的过程就是 shuffle。

老 ：

Hash Base shuffle 产生的临时文件数 = MapTask * ResultTask 。

弊：

会产生过多的临时文件。

新：

SortBasedShuffle： 产生的文件数 = MapTask 数量 。

如果Shuffle 不落地：

①可能会造成内存溢出

②当某分区丢失时，会重新计算所有父分区数据

Stage:

一个DAG会根据RDD之间的依赖关系进行Stage划分，流程是：以Action为基准，向前回溯，遇到宽依赖，就形成一个Stage。遇到窄依赖，则执行流水线优化（将多个连续的窄依赖放到一起执行）

4. HashMap源码，红黑树，阿里的好像都比较爱问HashMap，建议面试前着重准备一下？

答：建议面试前多看看hashmap的put函数和一些阈值；

5. 分布式一致性协议算法有哪些，说说它们？

分布式一致性协议：

2PC：

算法过程：

表决阶段：

【协调者视角】： 协调者 向所有参与者发送一个vote_request消息。

【参与者视角】：当参与者接收到vote_request消息后，向协调者返回vote_commit消息，如果没有准备好，则返回vote_abort消息，告知协调者目前尚无提交事务的可能。

附：协调者状态机：

提交阶段：

【协调者视角】：协调者收到来自各个参与者的表决信息，如果一致认为可以提交，协调者向参与者发送一个global_commit 消息，通知参与者进行本地提交，如果有某个参与者返回的表决信息是 vote_abort消息，则协调者向所有参与者者发送global_abort 消息来取消事务。

【参与者视角】: 每个提交了表决信息的参与者等待协调者行为，如果参与者接收到的是一个 Global_commit消息，那么参与者提交事务，如果接收到的是一个 Global-abort 消息，则参与者取消此次事务。

附：参与者状态机：

算法潜在问题：

从两者的有限状态机可以看出包含 3 个阻塞态：

协调者的wait状态；

参与者的INIT状态；

参与者的READY状态 ；

如果一个协议包含阻塞态，明显是一个脆弱的系统，很有可能因为进程陷入奔溃而导致阻塞态的对象进入长时间的等待；

解决手段：

1， 超时判断机制 ；

可以解决 协调者的 WAIT状态 和 参与者的INIT状态 长时阻塞问题；

2. 参与者互询机制 ；

可以解决参与者的 READY状态；

解释：

1. 如果协调者处于长时间 WAIT 状态，加入超时判断机制后，在一定时间内未收到所有参与者返回的信息，可以假定参与者进程奔溃或者网络通信故障，此时协调者可以安全地 发送 Global-Abort消息取消本地事务。

2. 如果参与者处于 INIT状态，说明协调者处于发送Vote-Request 消息的时间，加入超时判断机制，如果在一定时间内未收到消息，则可以终止本地事务，向协调者发送 vote-Abort 消息；

3. 如果参与者处于READY 状态，引入超时判断机制无法解决问题，此时等待协调者发送的全局表决信息，我们不能粗暴的终止事务会导致数据的不一致，不确定 协调者发送到底是哪种表决信息。

互询机制：孤单的参与者P 询问其它 参与者 Q（此时参与者Q 可能有以下4种状态；）：

1. COMMIT 状态：说明协调者 发送了Global-commit消息，但是孤单的P没有收到，此时我们就可以将P 安全的转换为 COMMIT ；

2. Abort状态 ：也说明协调者发送了global-Abort，此时我们也可以将 P 安全的转换为 Abort状态；

3. INIT状态，说明参与者Q还没有收到协调者的vote-request，但是P已经静茹了READY状态，Q可能在协调者多播放Vote-request消息或者网络故障的时候被 OVER掉了，都会导致这一现象，。证明参与者Q处于INIT状态，协调者未收到所有参与者的反馈不可能进入提交阶段，不可能发送 Global-commit，即使加入超时判断 也只是在一段时间后进入 Abort状态；

READY状态：没辙咯。。所有参与者都处于READY状态，这种情况下，陷入长时阻塞。

2PC 无法解决，3PC 可解决。

3PC：

用来解决 2PC无法解决的长时阻塞的办法；

其核心思想是将2PC 的提交阶段 再次细分为：

预提交阶段；

提交阶段 ；

协调者和参与者对应的状态机：

协调者：

参与者：

raft 向量时钟（vector clock ）:

概述：

生成时间之间偏序关系的算法。

典型应用场景：用来判断分布式环境下，不同事件之间是否存在因果关系；

 Paxos

 简介：

    所有的一致性协议要么Paxos，要么是其变体；

    Paxos算法描述与实现之间有着巨大的鸿沟，，，

    难理解性：

      非协议本身，而是在于什么因素导致使协议以此种方式呈现其正确性证明过程 的；

  知识所需背景：

    副本状态机：

           

      服务器再接收到客户端的指令时会将其添加到 log尾部；

      一致性协议的目的：就是保持各个log副本数据的一致性；

      追求特性：

        1. 安全性：

          状态机从不返回错误的结果，多个提议中只有一个会被选中；

        2. 可用性；

          大多数服务器正常，则保持整个服务可用，2n+1台，只允许n台出错；

        3. “大多数”状态机维护的log数据一致，就可以快速通知客户端操作成功，避免被一些累赘状态机拖累响应速度；

  单Paxos 和 多Paxos：:

    差异：

      单Paxos：

        副本状态机中各个服务器对log中“某个位置”通过协议达成一致，因为某个时刻不同服务器的 相同位置的操作命令是不一样的，目的是将它编程一样的；

      多Paxos：

        副本状态机中各个服务器对log中“多个位置”通过协议达成一致，

        是多个单paxos共同执行的结果；

    并行进程：

      对应副本状态机中 的 “一致性模块”

      承担角色：

        1. 提议者：

          提议者 提出 提议以供投票表决 ；

        2. 接受者：

          接受者 对众多提议进行表决，选出唯一 确定的一个;

        3. 学习者：

          无表决权，但是可以从接受者 知道 哪个提议最终中彩；

        一个并行进程可以承担多种角色；

    非拜占廷模型：

      1. 并发进程可以任意速度执行，失败也可重启；

      2. 信息传输丢失，可以重复发，顺序也可以 任意，但是唯一不可以的是：篡改信息内容；（真实的的分布式计算环境下，会通过内容检测性检测出来 的）；

  算法执行过程：

    执行目的：

      当多个并行进程提出 “提议”后，如何达成一致；

    执行过程：

      阶段1：

        【提议者视角】：

          提议者 选择提议编号 n 并给大多数（半数以上）接受者 Prepare请求，携带编号 n;

        【接受者视角】：

          某个接受者 接收到带有 提议编号n 的Prepare 请求，做判断：

            若 没有响应过 比 提议编号n大的prepare请求，则给响应，并承诺以后不会接收比它小的，   if 接受者响应过 阶段2【接受者视角】（任意编号为n的Accept请求），则将所有响应的Accept请求 提议编号最高的提议内容发给 提议者；

              提议内容包含：提议编号，提议值。

            若 响应过 比 提议编号n大的Prepare请求，那么不会给提议者响应。

      阶段2：

         【提议者视角】：

          if 提议者接收到了大多数 接受者的响应，则向这些接受者 发送 Accept请求：

            Accept请求包含：提议编号n , 提议值V；

          if 阶段1【接受者视角】没有收到任何接受者的Accept内容，则可以任意赋值给 提议V;

          提议值V的选择方式：

            如果返回了编号最高的Accept提议内容，则从这些提议内容里选择最搞的编号的的提议值 赋值 给 V；

        【接受者视角】：

          if 接受者接收到了 任意编号为 n的Accept 请求，则接受者接收此请求，除非在此期间 响应过比编号 n 更高的 Prepare请求；

      阶段3：

        学习者从接受者知道 提议值 ；

          低效率：

            某个接收Accept请求的接受者，通知所有学习者；

            缺点：

              造成大量通信。 假设m个接收者，n的学习者，就需要 m*n 次通信；

          高效率1：

            从学习者中选出一个代表，由它 通知 其它学习者，m+n 次通信；

            不足：

              如果学习者代表发生故障，则其它学习者无法得知 提议值 ；健壮性不足；

          高效率2：

            选出若干学习者代表，由这些代表从接受者获取提议值；（要是它们也全部故障了，艾，一边凉快去吧~）

6. 说说一致性哈希算法？

一致性哈希算法：

背景概述：

分布式哈希表（DHT） 是 P2P网络 和 分布式存储中常见的一种技术 ，是哈希表的分布式扩展，每台机器只负责承载部分数据，如何通过哈希方式对数据进行 增删改查等数据操作的技术。

而"一致性哈希" 就是DHT其中的一种实现方式。

算法概述：

“一致性哈希”算法 将 （哈希数值空间） 按照（大小）组成一个首尾相接的环状序列。

对于每台机器，可以根据其 （IP） 和 （端口号）经过 （哈希函数 ）映射到 哈希数值空间内。

每台机器就是环状序列的不同节点。

注：假设 N 代表机器，i代表哈希空间对应的数值。

而每台机器负责存储落在一段有序哈希空间内的数据，比如N 14存储 经过哈希后落在6~14范围内的数据。

同时每个机器节点 记录环中的前趋节点和后继节点的位置，使之成为一个真正的有向环。

路由问题（快速找到数据问题）：

低效率解决办法：

沿着有向环顺序查找，接收到查询请求的节点，获得查询的主键的哈希值    ( j) 之后，判断是否在自身管理范围内，否的话就交给后继节点进行处理。

直到 某个节点 Nx, x是>=j的最小编号节点。

这样，最多遍历所有的节点也能找到 对应的结果。

高效率解决办法：

为了加快查找速度，在每个节点配置路由表，路由表存储 m 条路由信息（m 为哈希空间的二进制数值比特位长度）。

其中i 项 （0<=i<=m-1）路由信息表示距离上一个节点的2**i的距离的哈希空间内的节点。

图演示：

算法执行过程描述：

输入：

从机器节点 N(i)发起初始查询请求，查询主键Key对应的键值，其中H(key)=j ;

输出：

Ni给出Key对应的键值value,或者返回键值不存在的信息 。

过程：

假设当前所在初始节点为Nc,他的后继节点为Ns,要查找的初始节点为Ni，N(i)=j。

1. 判断 c<=j<=s,

2. 如果为True，结束查找，说明key如果存在，一定在Nc的后继节点Ns上，所以Nc发送消息给Ns,要它查找key的值value,Ns将查询结果返回给 Ni。

3. 如果为False，Nc查找其对应 的路由表，找到小于j的最大节点Nh(如果所有节点都>j,则选择 m-1项为Nh),Nc项Nh发送信息，要它帮忙查找，此时Nh为新的Nc节点，接下来重复步骤2,3即可。

插入新节点N（new）问题：

概述：

新加入的N（new）节点必须与有向环中的任意一个节点 Nx产生联系，通过上面的路由算法找到H（N(new)）的对应哈希值new,可以找到它的后继节点为Ns,假设前趋节点为Np。

算法过程：

要将N（new）节点 加入，需要后续步骤。

非并发环境：

1，改变Np，Nnew,Ns对应已经发生变化的前趋节点和后继节点，以体现新的网络架构。

2. 迁移Ns节点上哈希值小于 new的数据到N（new）节点上。

并发环境：

1，将N(new)的后继节点指为Ns,前继节点置位空值Null。

2. 稳定性检测，并非为新节点加入而设置的，而是所有节点周期性自动完成。     通过稳定性检测可以完成前趋和 后继节点的数据迁移。

稳定性检测：

1. Nc向Ns询问他的前趋节点Np,一般这样直接到步骤4。

2. 如果Nc是介于 Np和Ns之间，Nc记录Np为其后继节点。

3. 令Nx为Nc的后继节点，Nx可能是Np,亦可能是Ns，取决于步骤2。   如果Nx的前趋节点为Null或者Nc位于Nx和它的前趋节点之间，那么Nc给Nx发送消息告诉 Nx，Nc就是它的前趋节点，Nx将前趋节点设置为 Nc。

4. Nx把哈希值小于c的数据迁移到Nc上。

新加入节点之后 ，原先的路由表还需要更新，因此每个节点还需要周期性检查路由表。

节点 离开：

正常离开：可以通知前趋节点和后继节点做一些更新工作，迁移数据 等。

异常离开：往往是机器故障导致的，可以采用机器节点数据多副本的方式。

潜在问题：

1. 机器节点映射到环状结构的位置是随机的呃，所以可能导致机器负载不均衡。

2. 机器异质性问题：（机器有高配和低配的），有可能出现低配高负载的情况.

可以引入“虚拟节点”，将一个物理节点虚拟化成若干个虚拟节点，分别映射到环状结构的不同问题，一方面可以导致更加的负载均衡，也可以兼顾到 机器异质性问题 。

7. 说一下布隆过滤器（Bloom Filter）？（自问知道的比较清楚，说了一点，我等他往更深层问呢，结果他直接就下一个问题了，早知道我就自己说完了。[是谁说阿里考官问知识点直到不会为止的，出来我要跟你理论理论]）

场景：快速 从海量数据中找出某个成员是否属于这个集合：

BF （Bloom Filter） 布隆过滤器：

特长：

二进制向量数据结构，空间效率极高。

因为 BF 使用位数组和哈希函数来表征集合，并不需要存储集合数据本身内容，所以其空间利用率非常高。

基本思想：

长度为 m 的位数组来存储集合信息。

k 个相互独立的哈希函数将数据映射到数组空间；

对于集合S中的某个成员a，分别使用k个哈希函数对其进行计算，如果 H i（a）=x(1<=i<=k,1<=x<=m),则将位数组的第x 位置为1，

查询：

当查询某个成员a是否在集合S中出现时，使用相同的k个哈希函数计算，如果其对应位置全部为1，则a属于集合S,只要有一个位置为0，则a 不属于集合S。

误判率及相关计算：

使用场景：

运行发生一定误判的场景，而在要求 100%精确判断的场景下不适合使用。

为什么会发生误判：

假如此时再查询X3这个元素是否属于集合，通过3个哈希函数计算后的位置数为 2,7,11 ,而这时这3个位置都为1，BF会认为X3属于集合，这样岂不是误判了。

漏判：

会发生误判但一定不会发生漏判，因为整个过程不存在将 1 改为 0的情况。

影响误判率的因素：

1. 集合大小 n 。

因为集合n越大，其它条件固定的情况下，位数组中就会有更多比例的位置被设成1，误判率就会增大。

2. 哈希函数的个数k。

个数越多，位数组中更多比例的位置被设置为1，即增大了 误判率。

但在查询时，显然个数越多的时候误判率会越低。

3. 位数组的大小 m。

位数组大小 m越大，那么在 n和k固定的情况下，位数组中剩余0的比特位就越高，误判率就会减小。

已知 k,n,m 即可计算出对应的误判率。

已知 n,m 最优的哈希函数个数为：

k = n/m * ln2

已知集合大小n,并设定好误判率 p, 问：m的大小如何确定？

m = - n*lnp / (ln2)^2

缺点：

无法删除集合成员，只能增加成员并对其查询。

改进：

计数 BF (Counting Bloom Filter)

思考：为什么基本BF无法实现删除？

答：其基本信息单位是 1 个比特位。所以只能表达两种状态。

计数BF 的  基本信息单元 由多个比特位组成，一般为3到4个。

使用过程：

将集合成员加入 位数组时，根据k个哈希函数进行计算，只需要将原先的数值 +1 即可。

查询集合成员时，只要对应位置的信息单元都不为 0 ,即判定该成员属于集合。

删除成员：只要将对应位置的计数 -1 即可。

改进的代价：

位数组大小倍数增加。

另外存在计数溢出的可能，因为比特位表达能力仍然有限，计数很大的时候存在计数溢出的问题。

8. public,private,default,protected 中default(包内)和protected谁的范围更大？

答：default,protected是包内可访问；

9. 静态变量和静态代码块的执行顺序？

答：静态变量先于静态代码块执行，整个执行顺序是：

附：父类静态变量初始化---》父类静态代码块-------》子类静态变量初始化------》子类静态语句块--------》父类变量初始化----------》 父类代码块----------》父类构造函数 ------》子类变量初始化--------》子类语句块----------》子类构造函数；

10. Mysql问的比较少，只问了索引的数据结构？

答：索引的数据结构：

1.生成索引，建立二叉查找树

2.生成索引，建立B-Tree

3.生成索引，建立B+-Tree

4.生成索引，建立Hash，基于InnoDB和MyISAM的Mysql不显示支持哈希

5. 位图数据结构，BitMap,少量主流数据库使用，如Oracle，mysql不支持，

11. volatile和synchronized关键字？

Synchronized 与volatile 关键字的区别？

概念上的区别：执行控制 和 内存可见；

执行控制：控制代码执行顺序以及是否可以并发 ；

Synchronized 解决执行控制问题，它会其它线程获取当前对象的监控锁，使得当前对象中被Synchronized关键字保护的代码块无法被并发执行，并且Synchronized 还会创建一个内存屏障，保证了所有CPU操作结果都会直接刷到主存中去，从而保证了可见性。

内存可见：控制的是线程执行结果在内存中对其它线程的可见性，根据Java内存模型的实现，Java线程在具体执行时，会先拷贝主存中的数据 到线程本地（CPU缓存），操作完成后再把结果从线程刷到主存中；

volatile 解决了内存可见，所有对volatile关键字的读写都会直接刷到主存中去，保证了变量的可见性，适用于对变量可见性有要求而对读取顺序没有要求的场景。

两者区别：

1. volatile 不会造成线程的阻塞，Synchronized 会造成线程的阻塞。

2. volatile仅能使用在变量级别，Synchronized 可以使用在变量，方法，类级别上。

3. volatile 标记的变量不会被编译器优化，Synchronized标记的变量会被编译器优化。

4. Volatile 仅能保证变量的修改可见性，不能保证原子性，而Synchronized 可以保证变量修改的可见性和原子性。

5. Volatile本质告诉JVM 当前变量在寄存器（工作内存）中的值是不确定的，需要从主存中去读取 ，Synchronized则是锁定当前变量，只有当前线程可以访问该变量，其它线程不可以。

12.高并发问了一点，ArrayBlockingQueue和LinkedBlockingQueue?

13.最后还问了一个IPV4相关的场景，设计算法和数据结构，晚上面的，脑子有点闷，没想明白？