数字马力面经和答案解析！社招岗

2023-11-15 08:52:28 浏览数 (1)

面试背景：社招、2 年开发工作经验。面试时间是今年 7.3 号，工作地点是长沙，面试总时长 50 分钟。

面试题目：

  1. ZooKeeper 原理？
  2. ZooKeeper 怎么做的崩溃恢复？
  3. 什么是 Zab 协议？
  4. HashMap 底层实现？
  5. ConcurrentHashMap 原理？以及为什么要这样改进？
  6. 深挖 CAS？乐观锁？和 ABA 问题？
  7. 手写括号算法匹配？

公司介绍

数字马力，是蚂蚁集团旗下全资子公司，专注于提供数字科技、智能技术的产品、解决方案和服务，助力企业持续升级数字化能力。

据小道消息称数字马力是给蚂蚁公司做内包的公司，成立于 2021 年 12 月。

薪资待遇：13 薪 年终奖（0-3 个月）。

答案解析

1.ZooKeeper 问题

答案解析：其实前三个问题的答案是一样的，所以我猜测，应该是应聘者没回答上来要点，所以面试官在刻意引导应聘者。

因为，ZooKeeper 实现的核心原理就是 Zab 协议，而 Zab 协议里面又包含了崩溃修复的具体流程。

2.什么是 Zab 协议？

答：ZAB （Zookeeper Atomic Broadcast，ZooKeeper 原子消息广播协议），它被用于实现分布式系统中的数据一致性和可靠性。

ZAB 协议总共包含以下两部分内容：

  1. ZAB 协议通过两阶段提交的方式来确保分布式系统的一致性。这两阶段分别是：准备阶段和提交阶段。在准备阶段，一个节点（称为 Leader）向其他节点（称为 Follower）发送提案，Follower 接受并确认提案。在提交阶段，Leader 将提案发送给所有节点，并等待多数节点的确认。一旦多数节点发送确认消息，Leader 就可以将提案确定为最终结果，然后通知所有节点进行更新。
  2. ZAB 协议还包括了崩溃恢复机制，当 Leader 节点崩溃时，系统会选择一个新的 Leader 来取代原先的 Leader 节点。新的 Leader 通过比对已完成的事务日志和未完成的临时提案来进行恢复。

所以，ZAB 协议通过原子广播的方式，在分布式系统中实现了一致性和可靠性，保证了数据的一致性和正确性。

3.ZooKeeper 如何进行崩溃修复？

答：在说崩溃修复之前，我们需要先了解一些前置内容。

在 ZooKeeper 中有三种节点类型，它们分别是：

  1. Leader（主节点）：能够处理读写请求，也同时负责同步写事务请求给其他节点且需要保证事务的顺序性，是整个集群的老大。
  2. Follower（跟随者）：只负责处理读请求，无权写，因此收到写请求需要转发给 Leader 处理，待 Leader 写完后再同步给 Follower。如果 Leader 挂了，那么 Follower 是有资格参与竞选的。
  3. Observer（观察者）：和 Follower 一样，唯一不同的是，不参与 Leader 的选举，可以利用不参与 Leader 选举的特性用来线性扩展读的 QPS。

也就是说，所有写操作会先到 Leader 节点，然后 Leader 节点在通过 2PC（两阶段提交：预提交、ACK、确认提交等流程）来进行数据同步，当写入成功过半就认为信息写入成功。而跟随者和观察者是为了增加读性能的，只不过跟随者还可以通过竞选主节点来保证集群的稳定性。

了解了这些之后，我们再来看 ZooKeeper 崩溃修复的流程（也就是当主节点崩溃后的流程），咱们先假设 ZooKeeper 集群有两个节点，ServerA 和 ServerB，它的崩溃修复的选举流程如下：

  1. 各自投票：
    1. ServerA 先投票给自己，投票信息包含节点 sid 和 zxid，sid 就是 myid（集群 ID，启动集群时必须设置的 ID，是在配置文件当中配置死的，整个集群内唯一），zxid 是事务 id，自增（每次写入操作时生成）。假设 ServerA 将票投给自己，那么投票信息就为 (1,1)。
    2. ServerB 也投票给自己，假设 ServerB 的 sid 为 2 ，那么此时 ServerB 投票信息为 (2,1)。
  2. 投票广播：
    1. 接下来 ServerA 和 ServerB 分别将自己的投票信息广播给集群中其他节点。也就是 ServerA 将（1,1） 广播给 ServerB， ServerB 将（2,1）广播给 ServerA。
    2. ServerA 收到 ServerB 的投票信息后，检查下 ServerB 的状态是否是本轮投票，以及是否是 LOOKING 寻主的状态。 反之，ServerB 收到 ServerA 的投票信息后也是一样的。
  3. 投票对比：优先对比 zxid，其次对比 sid。ServerA 会将自己的投票和 ServerB 的投票进行对比，先对比 zxid 发现 zxid 一样，然后对比 sid，发现 ServerB 的 sid 大于 ServerA 的 sid，所以此时 ServerA 就会更改投票信息为 (2,1)，然后将投票信息再次发送出去。而 ServerB 不需要更新投票信息，但是下一轮还需要再次将投票发出去。
  4. 统计投票：每一轮投票都会统计每台节点的投票信息，判断是否有过半的节点收到了相同的投票信息，如果过半，则将投票过半的节点升级为 Leader。ServerA 和 ServerB 收到的投票信息都为 (2,1)，且数量来说，大于一半节点的数量，所以将 ServerB 选出来作为 Leader。
  5. 更新节点状态：ServerA 作为 Follower，更新状态为 FOLLOWING，ServerB 作为 Leader。

以上就是 ZooKeeper 崩溃修复的选举流程，当然 ZooKeeper 集群启动的选主投票也是类似的。当完成选择流程之后，我们的 ZooKeeper 集群也就完成了崩溃修复了。

4.HashMap 底层实现？

答：HashMap 底层实现在 JDK1.7 和 JDK1.8 是不一样的，在 JDK1.7 中，HashMap 使用的是数组 链表实现的，而 JDK1.8 中使用的是数组 链表或红黑树实现的。 HashMap 在 JDK1.7 中的实现如下图所示：

HashMap 在 JDK1.8 中的实现如下图所示：

HashMap 中每个元素称之为一个哈希桶（bucket），哈希桶包含的内容有以下 4 项：

  • hash值
  • key
  • value
  • next（下一个节点）

默认情况下，在 JDK 1.8 版本中，HashMap 使用的是数组加链表的形式存储的，而当数组的长度大于 64，并且链表的长度大于 8 时，就会将链表升级为红黑树，以增加 HashMap 查询时的性能。

5.ConcurrentHashMap 原理？为什么要这样改进？

答：ConcurrentHashMap 在不同的 JDK 版本中实现也是不一样的，在 JDK1.7 中它使用的是数组加链表的形式实现的，而数组又分为：大数组 Segment 和小数组 HashEntry。大数组 Segment 可以理解为 MySQL 中的数据库，而每个数据库（Segment）中又有很多张表 HashEntry，每个 HashEntry 中又有多条数据，这些数据是用链表连接的，如下图所示：

而在 JDK 1.7 中，ConcurrentHashMap 是通过在 Segment 加锁来保证其安全性的，所以我们把它称之为分段锁或片段锁，如下图所示：

它的实现源码如下：

从上面源码可以看出，JDK 1.7 时，ConcurrentHashMap 主要是用 Lock 进行加锁来实现线程安全的。

而在 JDK 1.8 中，它是使用了数组 链表/红黑树的方式优化了 ConcurrentHashMap 的实现，具体实现结构如下：

链表升级为红黑树的规则：当链表长度大于 8，并且数组的长度大于 64 时，链表就会升级为红黑树的结构。

PS：ConcurrentHashMap 在 JDK1.8 虽然保留了 Segment 的定义，但这仅仅是为了保证序列化时的兼容性，不再有任何结构上的用处了。

在 JDK1.8 中 ConcurrentHashMap 使用的是 CAS volatile 或 synchronized 的方式来保证线程安全的，它的核心实现源码如下：

从上述源码可以看出，在 JDK1.8 中，添加元素时首先会判断容器是否为空，如果为空则使用 volatile 加 CAS 来初始化。如果容器不为空则根据存储的元素计算该位置是否为空，如果为空则利用 CAS 设置该节点；如果不为空则使用 synchronize 加锁，遍历桶中的数据，替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

我们把上述流程简化一下，我们可以简单的认为在 JDK1.8 中，ConcurrentHashMap 是在头节点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。而且 JDK1.8 使用的是红黑树优化了之前的固定链表，那么当数据量比较大的时候，查询性能也得到了很大的提升，从之前的 O(n) 优化到了 O(logn) 的时间复杂度，具体加锁示意图如下：

6.乐观锁？CAS？ABA 问题？

答：乐观锁是一种并发控制机制，它的核心思想是假设在大多数情况下，并发操作之间不会产生冲突，因此不需要使用显式的锁进行串行化处理，而是只在提交操作时检查是否发生了冲突。

所以乐观锁是一种实现锁的策略，而这种策略的实现主要是依靠 CAS 机制。

CAS 是 Compare and Swap（比较并交换）的缩写，是一种并发算法，常用于实现乐观锁。

CAS 操作包含三个参数：一个内存位置（通常是一段数据的地址）、期望的值和新的值。CAS 操作的执行过程如下：

  1. 首先，将内存位置的当前值与期望的值进行比较。
  2. 如果相等，说明内存位置的值没有改变，就使用新的值替换原来的值，然后返回 true，表示替换成功。
  3. 如果不相等，说明内存位置的值发生了改变，可能有其他线程修改了该值，那么 CAS 操作失败并返回 false。

然而，需要注意的是，CAS 操作并不能解决所有并发问题，因为它仍然存在 ABA 问题。

ABA 问题是指在并发环境下，一个变量从初始值 A 经过一系列操作变为 B，然后再回到 A。这样，观察变量的线程可能无法察觉到中间的操作，从而引发一些意外的问题。

具体来说，假设线程 T1 从初始值 A 开始，使用 CAS 将变量的值从 A 替换为 B，然后又将 B 替换为 A。与此同时，线程 T2 在 T1 操作之前读取了变量的值 A，然后在 T1 操作之后读取了相同的值 A，发现两次读取的值相同，认为变量没有发生变化。

为了解决 ABA 问题，常用的方法是使用带有版本号或时间戳的 CAS 操作。

具体操作如下：

  1. 在变量中引入一个版本号或时间戳。
  2. 在执行 CAS 操作时，除了比较变量的值外，还要比较版本号或时间戳。
  3. 如果变量的值和版本号都匹配，则可以执行 CAS 操作。

通过引入版本号或时间戳，可以在比较变量值时同时检测到变量的变化历史。即使变量的值回到了 A，但是版本号或时间戳已经被改变，从而避免了 ABA 问题。

7.括号算法匹配？

题目详见：https://leetcode.cn/problems/valid-parentheses/

算法实现原理

  • 栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
  • 建立哈希表构建左右括号对应关系：key 左括号，value 右括号；这样查询 222 个括号是否对应只需 O(1) 时间复杂度；建立栈 stack，遍历字符串 s 并按照算法流程一一判断。

算法实现流程

  • 如果是左括号，则入栈 push；
  • 否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号不对应，则提前返回 false。

实现代码如下：

代码语言：javascript复制
class Solution {
    private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
        put('{','}'); put('[',']'); put('(',')'); put('?','?');
    }};
    public boolean isValid(String s) {
        if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
        LinkedList<Character> stack = new LinkedList<Character>() {{ add('?'); }};
        for(Character c : s.toCharArray()){
            if(map.containsKey(c)) stack.addLast(c);
            else if(map.get(stack.removeLast()) != c) return false;
        }
        return stack.size() == 1;
    }
}

小结

数字马力这次面试的整体难度不大，但可以看的出来，面试官个人是比较熟悉 ZooKeeper 的，所以一开始就问了 ZooKeeper 的问题，如果应聘者刚开始的这些问题回答不好的话，后续凉的概率还是很大的。

因此，应聘者需要注意一下，你写在简历上的技能，除了你真的会用以外，你还要在面试的时候能回答上来才行，不然你写在简历上，就是自己坑自己。

参考&鸣谢

力扣作者：Krahets

本文已收录到我的面试小站 www.javacn.site，其中包含的内容有：Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、设计模式、消息队列等模块。

变量 并发 集群 链表 数组

0 人点赞