这是第一次面试,自我安慰为,面得不好是意料之中吧。

岗位背景

达坦科技,北京小公司,线上实习。找 Rust 分布式存储开发,应该是缺人,牛客私聊我有 Python 线上实习。

个人简历主 C++,也涉及一半 Python 内容。

面试过程

首先是本来以为面试官会要求打开屏幕共享,结果面试官全程不露脸,也不要求屏幕共享,我开了摄像头也没开。

整个流程非常快,当天 HR 微信联系。

下午和 HR 聊了分布式和 Rust,我说我都不懂,HR 提供了意见:MIT6.824Rust 官方教程。总体感觉 HR 很友好(但个人并没有 Rust 发展计划,我只能嗯嗯嗯好好好)。

晚上 CTO 约面(下文称面试官),约了第二天下午。整个微信联系过程都很礼貌,面试过程也很礼貌,不过给我挂了,当然聊得过程中也感觉到会被挂了。

面试官只问了一个问题,CMU15445。和我聊整个项目的实现和中间拓展的问题,估计面试官对数据库还是比较拿手,它说他还有很多关于数据库的拓展问题,但我没办法继续回答下去。其中主要问题如下:

问题 解答情况
大概介绍简历上两个项目。 Python 项目是 Python 课作业,bustubCMU15445 公开课项目,没具体介绍。
Copy-on-Write Trie 的整体实现流程。 个人认为我的表述还算清晰。解释了 Copy-on-Write 但解释有问题,给自己埋坑。
追问:多线程同时修改根节点会发生什么? 发现我的对我的并发过程回忆是错误的,我当时说写不需要任何加锁。
LRU 是怎么实现的,什么是 LRU-K 回答很结巴,没有做过很好的梳理。面试官也不懂 LRU-K,我讲得他很蒙。
追问:LRU-K 的优势? 即为什么要 LRU-K 完全不清楚,面试官两次追问,不得已开始瞎编。
(我提到 LRU-K 中 Pin 和 Unpin,面试官觉得应该时间花太多(因为我前面结巴),没有追问)
BPM 里有用到什么吗? 我直接回答没什么东西,简单的调度逻辑,并发给全部上锁,很快过这个话题。
可拓展哈希表为什么要三层分页? 分页少并发效率低,容量小;分页多索引速度慢,虽然容量大。当时说分页多并发性会提升是有错误的。
(我提到没完成整个项目) (我真是老实)
你为什么没完成整个项目?中间遇到什么问题? 在 2023fall 中发生新的接口变动,我无法找到变动的接口,该新项目也无法在网络找到参考。然后 balabala 被追问了具体什么变动。
追问:你完成的部分分别是数据库的哪些方面? 回答 “存储”,先讲到哈希表存储实际数据,BPM 管理缓存池;Trie 涉及字符串存储,但实际在项目中起到检验 C++ 功底的看门员。其中我提到哈希表和 B+ 树。
追问:比较哈希表和 B+ 树。 这部分我自认为回答的还算可以。其中我提到哈希表无法做区间索引。
追问:那么哈希表的区间索引是怎么做的? 不知道。。。又给自己埋坑。
(反问)

梳理上述问题

多线程同时修改 Copy-on-Write Trie 的根会发生什么?

当时的回答是完全错误的,后面被质疑我说记不清了。

多线程同时修改 Copy-on-Write Trie 时首先获取写锁,在整个修改过程中持有写锁。在修改根时会持有 “根” 锁,根锁在修改完根时立即释放。读取时需要获取根锁,读取根后立即释放,不需要申请读锁。

为什么需要持有根锁? 读操作从根开始索引,因此读操作应该从何处开始应该被保护。换言之,根锁保护的不是根,而是指向根的变量。

Copy-on-Write 的优势体现在哪里? Copy-on-Write 保证了每个节点在创建后就不会被修改,这里不考虑根锁的开销,这样做读操作不再需要持有任何锁,它与写操作可以并行。换言之,传统的读写锁策略保证读与读之间是互容的,其余操作都是互斥的;而在 Copy-on-Write 中,​它又允许读与写操作之间是互容的。 在整个 Copy-on-Write Trie 中只有写操作之间和获取根是串行的。

传统的读写锁版本需要持有根锁吗? 不需要,根的保护可以被包含在整个读写锁版本中。事实上,Copy-on-Write 中的根锁可以是读写锁,但我采用的是互斥锁,两者产生的性能差异不大。

LRU 是怎么实现的?LRU-K 是什么?

不再回答这个问题,当时回答这个问题很结巴。不过在回答问题的过程中算是梳理明白了。但回答追问。

LRU-K 相对于 LRU 的优势体现在哪里?

参考这篇论文:The LRU-K page replacement algorithm for database disk buffering (acm.org) 这篇论文是 1993 年 LRU-K 最早被提出时的论文。我们以两个例子、两个测评来体现 LRU-K 的优势:

  • 案例一:在一个 B+ 树索引中,假设这个 B+ 树深度为 22,它有 11 个根节点,100100 个叶子节点,1000010000 个数据节点。在这个案例中,一次简单的索引操作,有 1100\frac{1}{100} 的概率命中某个叶子节点,110000\frac{1}{10000} 的概率命中某个数据节点。这个频率差异是巨大的,而在传统的 LRU 中并未考虑这个因素,而 LRU-K 则适当的引入了频率这个概念。
  • 案例二:存在两个用户,一个用户需要进行一次扫描操作,而另一个用户进行正常的随机访问操作。扫描操作其实很简单,例如遍历一张数据表等,但其带来的后果却是灾难的。扫描操作会快速引用大量页面,这对于传统 LRU 而言将迅速驱逐所有随机访问页面,但是扫描操作引用的页面几乎在之后很长一段时间内不再被引用,而随机访问页面才是真正需要被缓存的,这几乎使传统的 LRU 失效。对于这个问题 LRU-2 就能很好的解决。
  • 测评一:双池测评,在 Pool1 中每个页面被访问的概率为 1100\frac{1}{100},在 Pool2 中每个页面被访问的概率为 110000\frac{1}{10000}。这实际是对案例一的测评,数据显示 LRU-KBPM 较小时,会带来大约两倍的命中率提升。
  • 测评二:Zipfian 测评,Zipfian 是一种概率分布模型,它指出 rank i 的页面被访问的概率是 1ilogba\frac{1}{i^{\log_ba}},其中 a, ba,~b 是常数。这实际是对概率阶梯分布的强化,数据显示 LRU-KBPM 较小时,会带来大约 15%15\% 的命中率提升。

既然考虑频率为什么不采用 LFU?

  • LFU 只考虑频率,而实际最近访问时间依然是一个重要因素。
  • LFU 过渡考虑频率,带来的开销巨大,它是这么做的:考虑最近 TT 秒内,页面访问的次数。这将记录最近 TT 分钟内的所有访问,如果页面访问次数非常频繁,带来的开销就是极其巨大的。

总而言之,LFU 适合访问频率低的场景,LRU 适合高速访问场景。

可拓展哈希表为什么要三层分页?

三层分页中,分为 Header Page / Directory Page / Bucket Page,其中前两层分页用于索引,第三层分页用于实际存储键值对,它们的大小都不超过页大小。

为什么要分页? 如果不分页,那么哈希表就不具备可拓展性,那么可以分为两种情况:

  • 所有的数据被存放在一个页中,一个页大小通常是固定的,例如 4096B,这个空间只能存储数百个键值对,这显然无法满足需求。
  • 如果使用直接索引的方式,即通过哈希值可以直接计算页号,这样的操作不具备可拓展性。页号指向的实际磁盘空间由 BPM 管理,以及分配的页号是否实际占用磁盘,也是由 BPM 管理的。如果 BPM 在分配页号时实际分配磁盘,那么后果是灾难性,它将占用巨大的存储空间;如果不是,那么仍然取决于 BPM 如何管理磁盘,事实上我们并没有在 BPM 中支持这个功能;如果这个功能确实在 BPM 中被支持,那么二层分页可以被这样支持,但是如果需要使用三级分页依然遇到问题。

为什么二级分页不行? 准确来说,不是二级分页不行,而是二级分页不好。首先,三级分页相比二级分页有更大的存储空间,如果页大小是 4096B,那么三级分页大概可以存储 1e9 的数据规模,而二级分页大概为 1e6 的数据规模。另外,三级分页相对于二级分页有更多并发性能提升空间,因为在下级分页可以释放上级分页持有的锁;但分页过多会产生页面命中不集中的问题,这需要 Grow/Shrink 机制来实现。

Grow/Shrink 机制如何解决命中率下降问题? 通过在一些级别的页中增加 Grow/Shrink 机制可以很好的提高命中率,在我们的三级分页中,只在 Directory 页使用了 Grow/Shrink 机制,Header 没有使用。

  • 实现原理: 事实上在这个机制下,这个 Directory 页下的所有索引都指向相同的 Bucket,当这个 Bucket 满时,它会进行 Grow,这需要重新计算哈希值来将原本桶中的键值对分到两个桶中。而在一个桶为空时,它将尝试进行 Shrink,这将导致两个桶合并,而 Directory 中的索引也会重新指向相同的桶。但这个过程会带来并发效率的降低。
  • 为什么解决了问题? 这样做使用了更少的桶,准确来说,在刚开始一个 Directory 下只管理了一个 Bucket,在数据量少时这样一个 Bucket 就已经足够了。桶的数量会随着数据规模的增长而增长,而桶的数量对于页的数量是起到决定性作用的。
  • 为什么并发效率降低了?为什么不给 Header 使用 Grow/Shrink 机制? Grow/Shrink 机制减少了页的数量,但与此同时,我们发现 Grow 操作需要同时持有三个页的锁(一个 Directory、两个 Bucket,当然我们也可以先完成所有 Directory 内的操作然后释放它)。总之它会更长时间的占用更高级别的公共资源,并发效率就会下降。也正是因为占用高级别公共资源对并发效率影响巨大,因此对 Header 添加 Grow/Shrink 机制可能带来负面效果;如果对 Header 添加这个机制,那么每次索引都一定花费额外的时间保证该机制的工作,重点是这个过程是持锁的,而在 Directory 持有同一锁的概率是 11000\frac{1}{1000}
  • 为什么维护 `Grow/Shrink` 的数据保存在 `Directory` 中,而非各个 `Bucket` 中? 这个操作在进行 Shrink 的时候,检测到一个桶空,就无需去打开另非空桶去修改它的值,这减少了换页的可能性。

为什么不采用更多级分页?

使用更多级分页的唯一理由是希望存储更大规模是数据,因为多级索引或带来额外的索引开销。如果确实需要增加级数,那么我依然建议在第一级不使用 Grow/Shrink 机制,而在后面的中间所有的分级中使用这一机制,这样可以很好的权衡并发效率和页的命中率。

哈希索引如何进行范围查找?

哈希索引无法进行范围查找。对于哈希索引,进行范围查找必须扫描表。

对比 B+ 树索引和哈希索引。

  • 哈希索引具有更好的性能和并发效率。
    • 修改性能方面:哈希索引进行的维护操作更加简单,因此具有更好的性能。
    • 查找性能方面:哈希索引直接计算哈希值,并逐级索引即可;而 B+ 树需要在节点中遍历或二分。
    • 并发效率方面:B+ 树为保证并发安全,必须持有整条链路的锁,而哈希索引则可以提前释放锁。B+ 树索引的优势在于,B+ 树索引可以进行区间查找,无需排序等。
  • B+ 树在区间索引、排序、分组方面表现远优于哈希索引。
    • 哈希索引只支持快速的等值查找,在区间索引方面,与没有适用索引几乎别无二致。
    • B+ 树具有顺序性,在区间索引方面与等值查找效率相仿。

为什么 B+ 树索引更常用? 前面讲到在等值查找和修改方面,哈希索引的性能优于 B+ 树,但这个优势是有限的,是一个常数倍的优势。而在区间索引方面,这个差异在时间复杂度上是天差地别的。最后,区间索引是数据库中十分常见的操作,这个操作必须被重要考虑。

面试评价

面试官真的非常友好,当面给出了面评。会后还在微信发了简单面评。

再次感谢你参加今天的面试,根据面试结果我们觉得你不太适合我们现在的项目需求。

基于面试情况,我建议你能够坚持将之前的 CMU 项目做完,并且对已经完成的部分进行深入探索和研究,会达到事半功倍的效果。

会议最有趣的部分是,面试官快结束时说 “感觉你现在像在盲人摸象”。不过不得不说确实是这样的,整个项目过程中我没有去参考太多理论资料。

自我反思

对于简历内容的把握程度非常重要,准备面试还就要围绕简历内容展开。寒假快要结束了,整个寒假基本是在学习和整理 C++,导致 CMU15445 的代码还有拓展原理都忘光了基本。

然后是岗位匹配度的问题,这家是 Rust 厂,当时简历海投属这家回应最快。当时聊起来它们是线上实习,然后 HR 说可以给我配 Python 的工作,当时想虽然我是想做 C++ 的,但是 remote 还是很香的吧,我也是运气真的好吧,先面试了再说。最后庆幸的是,这是我第一次面试,岗位确实也不匹配,失败很正常,要是第一面就是大厂那痛失一次机会啊。

整个寒假基本都在学习 C++,但缺少对简历其他方面的整理,现在 C++ 学的差不多了,然后 CMU15445 把所有能引申的问题个人感觉都在这篇文章整理的差不多了,感觉要提前一下数据库八股的优先级,毕竟这个项目在我的整个简历中放到了很显眼的位置。

准备面试应该是以简历为中心,拓展深度广度的学习过程。