决战八股文之巅

SQL

长宽表转换

# 长表转宽表
with t1 as (
  select
    id,
    str_to_map(concat_ws(',', collect_set(concat_ws(':', k, v)))) as m
  from t_narrow_dim
  group by id
)
select 
  id,
  m['name'] as name,
  m['age'] as age, 
  ...
from t1;

# 宽表转长表
with t1 as (
  select 
    id, 
    map('name', name, 'age', age, ..) as m
  from t_wide_dim
)
select 
  id, 
  explode(t1.m) as (k, v)
from t1;

开窗

页面停留时间

MACD

UDF

Java

类加载

  • 类加载过程
    1. 加载，将 .class 文件读取到方法区（元空间）
    2. 链接，主要处理符号引用，比如对其他类的引用
    3. 初始化，执行构造方法，分为 <init> 与 <clinit>，
      • <init> 是类的构造函数，<clinit> 是初始化静态变量与静态代码块
      • ClassLoader.loadClass 是不会执行 <clinit>
      • Class.forName 会执行 <clinit>，因此它是 SQL Driver 加载的常见写法
  • 类加载器（从上到下）
    • Boot. Classloader(rt.jar)、Ext. Classloader、App. Classloader
  • 双亲委派
    • 一种安全保护机制，防止核心的 Java 类被篡改，所有类加载请求都往上提交。
    • 上向下破坏：Thread#getContextClassLoader。
      可以理解，越上层的类加载器能加载的类越少，如何让运行在上层类加载器的线程获取到动态的自定义或者 App. 加载器呢？Thread#setContextClassLoader 提供可注入的地方。
    • 下向上破坏：热更新。
      在 App. 加载器之下再创建子加载器，检测到版本变更时，让新的线程用新的子加载器加载，得到不同线程运行相同类名但不同代码的形式。

多线程

  1. 背景 — JVM 内存模型规范（JMM 规范）
    JMM 规范主要规定 volatile 与 final 修饰的共享变量在多线程编程下的可见性与有序性。
    • 可见性，使用 LOCK# 指令前缀，修改强制写回主存，并作废其他核心寄存器缓存
    • 有序性，使用内存屏障禁止指令重排序
  2. 背景 — JVM 内存结构
    • 堆（JDK 8 后，常量池迁移至堆中）
    • JVM 栈帧（局部变量表、操作数栈、方法返回地址等等）
    • 本地方法栈帧（JNI 不与 JVM 的共用）
    • 元空间（方法区）
  3. 其他 — 线程池，ThreadPoolExecutor 的参数

IO

  • ByteBuf/ByteBuffer

G1 GC

  • 背景 — GC Root
    • 由 Boot. 加载器加载的类，及类的静态变量。
    • 栈帧中的局部变量表。
    • 存活的 Java 线程。
    • JNI 引用的对象。
    • 等等（比如 Busy Monitor，MAT 中会具体表明）。
  • 背景 — 三色标记
    三色代表着三种集合，主要用于辅助问题分析，
    • 白色代表辣鸡
    • 黑色代表有效对象，且该对象引用的子对象集合已经被染色
    • 灰色代表该对象引用的子对象集合暂未完全染色，最终将转为黑色
  • 背景 — 分区
    • 对堆进行分区，一般固定 2K 个 Regions，每个区最少 1M 最多 32M
    • 当堆大小超过 2K * 32M 时候，向上扩张 Region 数。
  • 背景 — Collection Set
    CSet 记录当次 G1 GC 需要回收的 Regions，相当于 GC 的工作目标。
  • 背景 — Card Table 与 Remember Set
    1. Card Table 是位图结构，每一位（也称为 Card Page）代表着 512B 的堆空间，主要是用来标记在 Concurrent Mark 阶段时，若存在黑色对象引用变更，将把对象在 Card Table 的 Page 标记为 Dirty，在未来 Remark 阶段，重新分析 Dirty 对象引用链路，重新染色。
    2. Remember Set 是 HashMap<Region, List<Card Page>> 结构，每一个 Region 都持有一个 RSet 结构，其代表其他 Regions 对当前 Region 的引用关系，通过 RSet，即便不用扫描所有 Region，也可以知道当前 Region 的对象有哪些被引用（即 Point-into 的信息）。
  • YGC
    • YGC 触发在 Eden 区写满。通过 GC Root 进行搜索，把检索到处于新生代的对象，复制到 Survive 区，对于超过 15 次的 YGC 中存活，则复制到 Old 区。
    • 由于 YGC 是需要过滤掉老年代中对新生代的引用，实际是使用 GC Root + RSet 平铺结构辅助搜索，就可以避免对单纯基于 GC Root 时需要对老年代 Region 的内部复杂检索。
  • Mixed GC
    • 与 YGC 的 标记复制 算法不一样，Mixed GC 对老年代采用 标记清理 算法，分为 4 步，
      • initial Mark，STAB + 展开与标记 GC Root 的第一层对象
      • concurrent Mark，并行标记其余对象
      • Remark，对于 concurrent Mark 过程中变更的对象引用重新标记
      • Clean-up，清理
    • 与 YGC 相似，Mixed GC 也需要过滤不关联的 Old 区（也就是不在 CSet 的），同样的，利用 RSet 结构可以忽略掉不关联的 Old 区细节。
  • 深入 — 三色标记异常情况分析与 STAB 作用
    • STAB（Snapshot-At-the-Beginning）机制：
      通过 Hook 在对象引用变更时，既保留原始引用关系，也保留变更后的引用关系。
    • 这里面太复杂了，暂时没有时间展开研究了。
  • 其他 — 建议阅读美团技术团队的关于 G1 的文章3，写得真的很飘逸，但句句都是重点。
  • 其他 — 默认新生代占 1/3，老年代占 2/3，Eden 区与 Survive 区占比 8:1:1，因此 Eden 区约占 26.66%。

Kafka

  • Kafka 消费回压
    • 我们消费模型是单线程消费，多线程异步处理（Vert.x）
      因此设计为，
      • 定义 Msg = Pair<ConsumerRecord, completed 标记>；
      • 消费时先进入 Map<PartitionId, PriorityBlockingQueue<Msg>> 结构；
        （依 Msg 的 ConsumerRecord$offset 排序）
      • 处理业务模块；
      • 当业务处理完成，标记已完成状态（completed=true）；
      • 当需要提交 Offsets 时，按分区分别处理，按顺序先 Drop 掉队列中处理完成的消息，得到第一个未提交的 Offset，这就是该分区可提交的 Offset。
    • 回压，实现原理就是计算上面队列的存量数据，当存量大于阈值，则消费速率减半（也就是阻塞消费线程），当持续时间内，存量小于阈值，则消费四倍增大，直至等于阈值。
  • 控制 Kafka 的传输速率
    • 客户端，配置 ZK 中 Client/User Entity，Broker 计算批的流量的延时，以延迟响应。
    • Broker 端，通常限制分区重分配时的复制速率，可以直接 reassign 命令中指定，其配置的是 ZK 中 Broker&Topic Entity，缺点是会影响正常生产消费。
# 对于匿名生产者消费者（未配置 client.id）速率限制为 20MB/s
kafka-configs.sh --alter \
  --add-config 'producer_byte_rate=20971520,consumer_byte_rate=20971520' \ 
  --entity-type clients \
  --entity-default

# 对于分区重分配的复制速率限制为 100M/s
kafka-reassign-partitions.sh  \
  --reassignment-json-file reassignment-json-file.json \
  --execute \
  --throttle 104857600

# 上面等价于下面组合命令
# Leader 副本是数据源（代表着旧副本），Follow（代表着新副本）从 Leader 中获取
kafka-configs.sh --alter \
  --add-config 'leader.replication.throttled.rate=104857600,follower.replication.throttled.rate=104857600' \
  --entity-type brokers \
  --entity-name 1
kafka-configs.sh --alter \
  --add-config "leader.replication.throttled.replicas='0:0,0:1,1:1,1:0',follower.replication.throttled.replicas='1:2,0:2'" \
  --entity-type topics \
  --entity-name user_location

Spark

基本关系

  • 一个 App 对应一个 SparkContext，由 SparkSession 创建
  • App 内有多个 Jobs，每触发一次 sc#runJob 就会产生一个 Job
  • Job 内有多个 Stages，Stage 是由 DAGScheduler 通过宽窄依赖划分，对应 Shuffle 过程
  • Stage 内也有多个 Tasks，组成 TaskSet，由 TaskScheduler 把任务分发到 Executors

Spark Shuffle 对 Cache&Checkpoint RDD 的影响

相比较 MR Shuffle，Spark 的特点是 Map 端的 combine() 函数会通过 AppendOnlyMap 数据结构进行在线聚合，而不是当 map() 函数完成后，对已落地文件重新读取执行 combine() 函数。

这使得 C&C RDD 的设计变得复杂，因为 Map 端的 Shuffle Write 写出的结果将只适用于当前的算子（Shuffle Write 是执行了特定的 combine() 聚合函数的结果，而不是 RDD 本身的数据）。

  • 对于 Cache RDD，Spark 在执行 combine() 之前对每一条 record 执行 persist()
  • 对于 Checkpoint RDD，Spark 采取不影响正常计算链路，重新计算实现
    （因为 Checkpoint 写 HDFS 的延时可能影响正常计算，而 Cache 只写本地磁盘或内存）

Algorithm

  1. 求最大子矩阵和：枚举横轴两线，通过对列求和，降维到一维数组，在一维数组求子序列的最大和，得到其一维数组的两个端点，也即对应矩阵的两根纵轴。
  2. 数组均分问题：
  3. 二分两数组的中位数：由于中位数 M 是两数组总长度折半，因此二分枚举其中一个数组的位置 P，可得出另一数组的位置 Q = M – P，并使得 B[Q – 1] < A[P] 且 A[P – 1] < B[Q]，然后再分辨 A[P] 或 B[Q] 是中位数。
  4. 两字符串的编辑距离：建立二维 DP，纵轴代表字符串 U，横轴代表字符串 V，可得转移方程，DP[i][j] = min(DP[i – 1][j] + 1, DP[j – 1][i] + 1, DP[i – 1][j – 1] + (U[i] != V[j]))。
  5. 股票买卖含冷冻期：建立两组二维 DP，一组是表示持仓的 held[2][i]，另一组是表示空仓的 folded[2][i]，每组分别有两种状态（共 4 种状态），
    1. 持仓的可能是昨天就持仓，今天维持该状态，也可能是空仓然后今天买入；
    2. 空仓的可能是昨天就空仓，今天也维持该状态，也可能昨天持仓，今天卖出。

Operation System

三次握手，很重要的一点就是同步初始的序列号。

半连接队列与全连接队列，存在于服务端，半连接可以理解已 Acked 客户端序列号，但由于未完整握手成功，未收到来自客户端的 Ack，也就是不知道客户端已 Acked 服务端的序列号；全连接就是收到来自客户端的 Ack，连接从半连接状态转移到全连接状态。

四次挥手，

  • FIN_WAIT_1 对应关闭【客户端写出流】与等同含义的服务端读入流；
  • FIN_WAIT_2 对应关闭【服务端写出流】与等同含义的客户端读入流；
  • 上述两个状态，一来一回，构成四次挥手。

四次挥手结束时，TIME_WAIT 将等待 2x MSL 时间（Maximum Segment Lifetime 最大报文段时间，默认 2 分钟），以应对最后一次客户端发送 ACK FIN 时可能的丢失，一旦丢失且不存在 TIME_WAIT 时间，服务端重试后将收到 RST 信号，误以为客户端异常。

SO_REUSEADDR 参数，是让 TIME_WAIT 状态的 Socket 允许重用（如网关场景），理论上相当于把操作系统应对 ACK FIN 丢失的逻辑下放到用户应用程序上。

Spring Web & Spring Cloud

  • Bean 的作用域有哪些？@Scope 有 Singleton 与 Prototype
  • Bean 的生命周期是？
  • Bean 的线程安全问题？ThreadLocal，事务就是用 ThreadLocal 传递上下文
  • BeanFactory 和 ApplicationContext 有什么区别？
  • 怎么解决循环依赖？延迟注入，具体细节是通过 L1、L2、L3 缓存实现。
    L1 是已经装配完成的 Beans，L2 是实例已创建但未完成装配，L3 则是 Beans 工厂方法。
  • 事务传播规则？父调用的事务传播到子调用（默认），或者创建新的事务，又或者并行调用时，优先执行非事务调用，让事务调用挂起。

参考资料

  1. https://developer.aliyun.com/article/753815
  2. https://tech.meituan.com/2014/09/23/java-memory-reordering.html
  3. https://tech.meituan.com/2016/09/23/g1.html