阿里面试总结
作者：来^_^
链接：https://www.nowcoder.com/discuss/226834?source_id=discuss_experience_nctrack&channel=-1
来源：牛客网
一面：
- 刚开始面试就是对简历项目一顿撕，PV和UV是怎么计算的，UV怎么进行去重的？不用ES该如何实现去重？
这个项目我还准备了下，结果答的还是不太好,
- 说说flink,spark streaming,storm的区别？
活题，随便答；
- spark的调度执行逻辑，stage，宽依赖和窄依赖，容错机制？
容错机制：
窄依赖可以通过血缘关系 来恢复故障RDD，而宽依赖则考虑使用 检查点 的方式恢复。
RDD的容错机制是 如何实现的？
借助这些依赖关系，DAG可以认为这些RDD之间形成了 lineage(血统，血缘关系)，借助lineage ，能保证一个RDD在计算前，它的父RDD已经完成了计算，并实现了RDD的容错。
当某个RDD发生故障需要恢复时，从数据源逐步执行对应的transformation操作来重新生成当前的RDD，这种容错策略 要高于 常用的 检查点 （Check Pointing）策略。
CheckPoint(将RDD持久化到磁盘上):
调度执行逻辑：
依赖关系：
依赖 关系：
窄依赖【Narrow Dependency 】（1:1）：如 map ->flatMap等。
宽依赖【Wide Dependency 】（1：多）：如groupByKey()等。
Shuffle：
存在spark shuffle :
因为具有某种共同的特征的一类数据需要最终汇聚 （aggregate）到一个计算节点进行计算 ，这个数据重新打乱然后汇聚到不同节点的过程就是 shuffle。
老 ：
Hash Base shuffle 产生的临时文件数 = MapTask * ResultTask 。
弊：
会产生过多的临时文件。
新：
SortBasedShuffle： 产生的文件数 = MapTask 数量 。
如果Shuffle 不落地：
①可能会造成内存溢出
②当某分区丢失时，会重新计算所有父分区数据
Stage:
一个DAG会根据RDD之间的依赖关系进行Stage划分，流程是：以Action为基准，向前回溯，遇到宽依赖，就形成一个Stage。遇到窄依赖，则执行流水线优化（将多个连续的窄依赖放到一起执行）
- HashMap源码，红黑树，阿里的好像都比较爱问HashMap，建议面试前着重准备一下？
答：建议面试前多看看hashmap的put函数和一些阈值；
- 分布式一致性协议算法有哪些，说说它们？
分布式一致性协议：
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状态 长时阻塞问题；
- 参与者互询机制 ；
可以解决参与者的 READY状态；
解释：
如果协调者处于长时间 WAIT 状态，加入超时判断机制后，在一定时间内未收到所有参与者返回的信息，可以假定参与者进程奔溃或者网络通信故障，此时协调者可以安全地 发送 Global-Abort消息取消本地事务。
如果参与者处于 INIT状态，说明协调者处于发送Vote-Request 消息的时间，加入超时判断机制，如果在一定时间内未收到消息，则可以终止本地事务，向协调者发送 vote-Abort 消息；
如果参与者处于READY 状态，引入超时判断机制无法解决问题，此时等待协调者发送的全局表决信息，我们不能粗暴的终止事务会导致数据的不一致，不确定 协调者发送到底是哪种表决信息。
互询机制：孤单的参与者P 询问其它 参与者 Q（此时参与者Q 可能有以下4种状态；）：
COMMIT 状态：说明协调者 发送了Global-commit消息，但是孤单的P没有收到，此时我们就可以将P 安全的转换为 COMMIT ；
Abort状态 ：也说明协调者发送了global-Abort，此时我们也可以将 P 安全的转换为 Abort状态；
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算法描述与实现之间有着巨大的鸿沟，，，难理解性：非协议本身，而是在于什么因素导致使协议以此种方式呈现其正确性证明过程 的；
知识所需背景：
副本状态机：图演示：<br />服务器再接收到客户端的指令时会将其添加到 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：选出若干学习者代表，由这些代表从接受者获取提议值；（要是它们也全部故障了，艾，一边凉快去吧~）
- 说说一致性哈希算法？
一致性哈希算法：
背景概述：
分布式哈希表（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。
判断 c<=j<=s,
如果为True，结束查找，说明key如果存在，一定在Nc的后继节点Ns上，所以Nc发送消息给Ns,要它查找key的值value,Ns将查询结果返回给 Ni。
如果为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对应已经发生变化的前趋节点和后继节点，以体现新的网络架构。
- 迁移Ns节点上哈希值小于 new的数据到N（new）节点上。
并发环境：
1，将N(new)的后继节点指为Ns,前继节点置位空值Null。
- 稳定性检测，并非为新节点加入而设置的，而是所有节点周期性自动完成。 通过稳定性检测可以完成前趋和 后继节点的数据迁移。
稳定性检测：
Nc向Ns询问他的前趋节点Np,一般这样直接到步骤4。
如果Nc是介于 Np和Ns之间，Nc记录Np为其后继节点。
令Nx为Nc的后继节点，Nx可能是Np,亦可能是Ns，取决于步骤2。 如果Nx的前趋节点为Null或者Nc位于Nx和它的前趋节点之间，那么Nc给Nx发送消息告诉 Nx，Nc就是它的前趋节点，Nx将前趋节点设置为 Nc。
Nx把哈希值小于c的数据迁移到Nc上。
新加入节点之后 ，原先的路由表还需要更新，因此每个节点还需要周期性检查路由表。
节点 离开：
正常离开：可以通知前趋节点和后继节点做一些更新工作，迁移数据 等。
异常离开：往往是机器故障导致的，可以采用机器节点数据多副本的方式。
潜在问题：
机器节点映射到环状结构的位置是随机的呃，所以可能导致机器负载不均衡。
机器异质性问题：（机器有高配和低配的），有可能出现低配高负载的情况.
可以引入“虚拟节点”，将一个物理节点虚拟化成若干个虚拟节点，分别映射到环状结构的不同问题，一方面可以导致更加的负载均衡，也可以兼顾到 机器异质性问题 。
- 说一下布隆过滤器（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的情况。
影响误判率的因素：
- 集合大小 n 。
因为集合n越大，其它条件固定的情况下，位数组中就会有更多比例的位置被设成1，误判率就会增大。
- 哈希函数的个数k。
个数越多，位数组中更多比例的位置被设置为1，即增大了 误判率。
但在查询时，显然个数越多的时候误判率会越低。
- 位数组的大小 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 即可。
改进的代价：
位数组大小倍数增加。
另外存在计数溢出的可能，因为比特位表达能力仍然有限，计数很大的时候存在计数溢出的问题。
- public,private,default,protected 中default(包内)和protected谁的范围更大？
答：default,protected是包内可访问；
- 静态变量和静态代码块的执行顺序？
答：静态变量先于静态代码块执行，整个执行顺序是：
附：父类静态变量初始化—-》父类静态代码块———-》子类静态变量初始化———》子类静态语句块————》父类变量初始化—————》 父类代码块—————》父类构造函数 ———》子类变量初始化————》子类语句块—————》子类构造函数；
- Mysql问的比较少，只问了索引的数据结构？
答：索引的数据结构：
1.生成索引，建立二叉查找树
2.生成索引，建立B-Tree
3.生成索引，建立B+-Tree
4.生成索引，建立Hash，基于InnoDB和MyISAM的Mysql不显示支持哈希
- 位图数据结构，BitMap,少量主流数据库使用，如Oracle，mysql不支持，
- volatile和synchronized关键字？
Synchronized 与volatile 关键字的区别？
概念上的区别：执行控制 和 内存可见；
执行控制：控制代码执行顺序以及是否可以并发 ；
Synchronized 解决执行控制问题，它会其它线程获取当前对象的监控锁，使得当前对象中被Synchronized关键字保护的代码块无法被并发执行，并且Synchronized 还会创建一个内存屏障，保证了所有CPU操作结果都会直接刷到主存中去，从而保证了可见性。
内存可见：控制的是线程执行结果在内存中对其它线程的可见性，根据Java内存模型的实现，Java线程在具体执行时，会先拷贝主存中的数据 到线程本地（CPU缓存），操作完成后再把结果从线程刷到主存中；
volatile 解决了内存可见，所有对volatile关键字的读写都会直接刷到主存中去，保证了变量的可见性，适用于对变量可见性有要求而对读取顺序没有要求的场景。
两者区别：
volatile 不会造成线程的阻塞，Synchronized 会造成线程的阻塞。
volatile仅能使用在变量级别，Synchronized 可以使用在变量，方法，类级别上。
volatile 标记的变量不会被编译器优化，Synchronized标记的变量会被编译器优化。
Volatile 仅能保证变量的修改可见性，不能保证原子性，而Synchronized 可以保证变量修改的可见性和原子性。
Volatile本质告诉JVM 当前变量在寄存器（工作内存）中的值是不确定的，需要从主存中去读取 ，Synchronized则是锁定当前变量，只有当前线程可以访问该变量，其它线程不可以。
12.高并发问了一点，ArrayBlockingQueue和LinkedBlockingQueue?
13.最后还问了一个IPV4相关的场景，设计算法和数据结构，晚上面的，脑子有点闷，没想明白？
若有收获，就点个赞吧
0 人点赞
