字节大数据架构 2 面

节二面

1 面试官：请简单的自我介绍一下？
面试官，您好！我叫 xxx , xxxx 年 x 月毕业于 xxx 学校，xx 学历，目前就职于 xxx 公司 xxx 部门，职位为：大数据开发工程师，主要从事于 xxx 组件、平台的开发工作。
工作以来，我先后参加了 xxx 项目、xxx 项目以及 xxx 项目，积累了丰富的项目经验，同时，这 x 个项目都得到了领导的一致好评。
我对 Flink 组件有着浓厚的兴趣，工作之余经常钻研技术、例如：Flink 四大基石、Flink 内核应用提交流程、Flink 调度策略等。
入职 x 年，曾荣获优秀员工，以上是我的自我介绍，请面试官提问。
2 面试官：flink 内核,你做了哪些工作？
(1) client 层源码修改， 扩展了 flink run 命令参数，修改多个类，并重新编译，使其应用提交流程满足公司的业务需求。
具体修改如下：
1. CliFrontendParser 类 添加如下内容

2. CliFrontend 类 添加如下内容


3. 修改 SecurityUtils 类

(2) ranger 鉴权源码修改。自定义实现 flink range 鉴权插件，使其通过 sql 提交应用时满足 ranger 鉴权操作。(代码过长，就不放啦)
(3) JobStatusListener 监听 Job 状态变更的源码修改。原生的 flink 只提供了一个固定实现，我扩展了 flink 的源码，让用户可以通过 execution.job-status-listeners 参数来指定自己的 listener，任务管理模块接口用它来监听 job 状态并将新的状态发回 webserver。
部分代码如下：

3 面试官：JobManager 和 TaskManager 之间如何通信？主要用到哪些类？
这个问题可谓是考察的非常细致了，看你对底层源码是否了解
Flink 内部节点之间的通信是利用 Akka，比如 JobManager 和 TaskManager 之间的通信。而 operator 之间的数据传输是利用 Netty。
Flink 整个通信框架的组件主要由 RpcEndpoint、RpcService、RpcServer、AkkaInvocationHandler、AkkaRpcActor 等构成。
1. RpcEndpoint 定义了一个 Actor 的 路 径 ；
2. RpcService 提供了启动 RpcServer 、执行代码体等方 法 ；
3. RpcServer/AkkaInvocationHandler 提供了与 Actor 通信的接口；
4. AkkaRpcActor 为 Flink 封装的 Actor。
4 面试官：使用 Akka 通信是同步还是异步？通信方式有几种？
在 Flink 应用中，Flink 尝试使用异步消息和通过 Futures（用来获取异步的响应）来处理响应。
Akka 异步通信方式包含两种：tell 和 ask。
1. tell 方式
当使用 tell 方式时，表示仅仅使用异步方式给某个 Actor 发送消息，无需等待 Actor 的响应结果，并且也不会阻塞后续代码的运行，如：
helloActor.tell(“hello helloActor”, ActorRef.noSender());
其中：第一个参数为消息，它可以是任何可序列化的数据或对象，第二个参数表示发送 者，通常来讲是另外一个 Actor 的引用， ActorRef.noSender()表示无发送者（实际上是一个叫做 deadLetters 的 Actor）。
2. ask 方式
当我们需要从 Actor 获取响应结果时，可使用 ask 方法，ask 方法会将返回结果包装在 scala.concurrent.Future 中，然后通过异步回调获取返回结果。

5 面试官：flink sql 了解吗，介绍一下 flink sql 的完整执行流程？
该问题在一面中已经被考察过，由于大数据架构岗位的职责要求第二点 打造流批一体的 SQL 层，要求了解 SQL 原理等，所以重复考察 SQL 也是可以理解的。
详细答案请查看一面：字节跳动大数据架构 1 面面经（超详细答案总结）

6 面试官：Left join 的底层实现原理了解吗？
具体实现原理：请看文章：
http://t.zoukankan.com/ljygz-p-15434413.html
7 面试官：谓词下推在什么时候可以做过滤下推?
谓词下推的含义：
将外层查询块的 WHERE 子句中的谓词移入所包含的较低层查询块（例如视图），从而能够提早进行数据过滤以及有可能更好地利用索引。
举个例子：
当有两张表 join 时，先对两张表 join, 然后进行过滤操作。此时可以先 filter 条件，先将 两张表无用数据过滤掉，然后再进行 join 操作。
8 面试官：ok，我现在给你两张表，你求一下所有 100 分成绩的学生，先用正常 sql 写一下，然后再用谓词下推的方式写一下
现在有两张表 student，Grade，求所有 100 分成绩的学生，
正常 sql ：
SELECT FROM Student t , Grade gwhere t.S_id = g.S_id
AND g.grade = 100
谓词下推方式：
SELECT FROM Student RIGHT JOIN t1 (SELECT FROM Grade WHERE grade = 100) t2ON t1.S_id = t2.S_id
9 面试官：谓词下推的原理图会吗？在电脑屏幕上画一下
我靠， SQL 写完还不行，还得画一下图，我也是醉了……
原理图如下：

10 面试官：flink 状态了解吗？包含几种划分方式
state 一般指一个具体的 Task/Operator 的状态，主要是用来保存中间的 计算结果 或者 缓存数据。
state 按照 Flink 管理还是用户管理分为：RowState(原始状态）和 Managedstate(托管状态)
1. RowState 由用户自行管理，只支持 字节 数组，所有状态都要转换为二进制字节数组才可以。
2. ManagedState 由 Flink RunTime 管理，支持多种数据结构，如 Map List 等
State 按照 key 划分，可以分为 KeyedState,OperatorState.
keyedState 只能用在 keyStream 上，并且每一个 key 对应一个 state 对象，keyedState 保存在 StateBackend 中，通过 RuntimeContext 访问，实现 Rich Function 接口，支持多种数据结构，如 ListState、MapState、AggregatingState 等
OperatorState 可以用于所有算子，但整个算子只对应一个 state，实现 CheckpointedFunction 或者 ListCheckpointed 接口，目前只支持 ListState 数据结构。
11 面试官: ok，那介绍一下 keyState 扩缩容的原理
所谓扩缩容，在
Flink
中就是指改变算子的并行度。Flink 是不支持动态改变并行度的，必须先停止作业，修改并行度之后再从 Savepoint 恢复。如果没有状态，那么不管
scale-in
还是
scale-out
都非常简单，只要做好数据流的重新分配就行。
举个例子， 假如原先 map 算子的并行度为 2，现在任务暂停了，我们把算子并行度改为 3 或者 改为 1 ，这时通过指定
savepoint
，重新恢复 job 任务。如下图的例子所示。

但对于有状态数据，如果并行度改变之后，HDFS 里的状态数据将经历状态下载、状态重建，被重新分配给各个
sub-Task
，如下图所示：原理图如下图所示：

12 面试官: 状态是如何重建的 ?
对于有状态数据，由于并行度从 2 变成 3。
最开始 Flink 中的 key 是按照 hash(key) % parallelism 的规则分配到各个 Sub-Task 上去的，那么我们可以在扩容完成后，根据新分配的 key 集合从 HDFS 直接取回对应的
Keyed State
数据。如下图所示：并行度从 从 2 增加到 3 后，Keyed State 中各个 key 的状态重建原理图。

但因为上述在 Checkpoint 发生时，状态数据是顺序写入文件系统的。从上图可以看出，当状态重建时，存在两个问题：
1. 状态随机读取，效率低下
；
2. 缩放之后各 Sub-Task 处理的 key 有可能大多都不是缩放之前的那些 key
基于这两个问题，引出了 KeyGroup。
Key Group
是 Keyed State 分配的原子单位，且 Flink 作业内 ，Key Group 的数量与最大并行度相同，也就是说 Key Group 的索引位于 [0, maxParallelism - 1]的区间内。每个 Sub-Task 都会处理一个到多个 Key Group，在源码中，以
KeyGroupRange
数据结构来表示。
KeyGroupRange 由两部分组成，
startKeyGroup
和
endKeyGroup
，实际上指的是 Key Group 的索引，左闭右开区间。
当并行度从 2 改为 3 时，KeyGroupRange 对应的原理图如下：

13 面试官: 状态重建时，调用的源码了解吗 ?
在并行度更改后，需要对原先的状态进行重建，状态重建的代码实现主要位于
RocksDBIncrementalRestoreOperation #
restoreWithRescaling(Collection restoreStateHandles)
，
参数 restoreStateHandles 表示与该 task 实例所负责的 keygroup 有交叉的 state。

下面以上图对 restoreStateHandles 做一个具象解释，假设有个 task 的并行度是 2，对应的 task 实例为 task-0,1，之后将其并行度调整到 3，对应的 task 实例为 new-task-0,1,2。图中的条形长度表示 task 实例所负责的 keygroup 范围。
1. new-task 0
的 keygroup 只与 task0 有交叉，重建 new-task-0 的状态时，restoreStateHandles 中只包含 task-0 的 checkpoint 数据。
2. new-task-1
的 keygroup 只与 task-0,1 都有交叉，重建 new-task-1 的状态时，restoreStateHandles 中需要包含 task-0,1 的 checkpoint 数据。
3. new-task 2
的 keygroup 只与 task1 有交叉，重建 new-task-2 的状态时，restoreStateHandles 中只包含 task-1 的 checkpoint 数据。
上述原理 对应到 源码 RocksDBIncrementalRestoreOperation#restoreWithRescaling 中的含义就是
1. 直接从 StateBackend 创建 DB
2. 对这个 StateBackend 进行剪枝，删除不需要的 keygroup。
我们知道 new-task-1 的 keygroup 只与 task-0,1 都有交叉，重建 new-task-1 的状态时，restoreStateHandles 中需要包含 task-0,1 的 checkpoint 数据。所以在对 StateBackend 进行剪枝时，就是找到 StateHandle 与目标 keygroup 非重叠的部分，然后调用 *deleteRange 方法，将其删除。图解表示如下：

算法

14 面试官: 写一个算法吧，之字形打印二叉树。
该题为 Leetcode 103. 二叉树的锯齿形层序遍历 的原题，
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

解题思路：
对树进行逐层遍历，用队列维护当前层的所有元素，当队列不为空的时候，求得当前队列的长度 size，每次从队列中取出 size 个元素进行拓展，然后进行下一次迭代。
为了满足题目要求的返回值为「先从左往右，再从右往左」交替输出的锯齿形，我们可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。
双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展，但是对当前层节点的存储我们维护一个变量 isOrderLeft 记录是从左至右还是从右至左的：
· 如果从左至右，我们每次将被遍历到的元素插入至双端队列的末尾。
· 如果从右至左，我们每次将被遍历到的元素插入至双端队列的头部。
当遍历结束的时候我们就得到了答案数组。
代码如下：

复杂度分析:
时间复杂度：O(N)
，其中 N 为二叉树的节点数。每个节点会且仅会被遍历一次。
空间复杂度：O(N)
。我们需要维护存储节点的队列和存储节点值的双端队列，空间复杂度为 O(N)。