面经 - 达坦科技 Python开发实习生一面挂 240220

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

岗位背景

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

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

面试过程

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

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

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

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

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

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

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

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

总而言之，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 持有同一锁的概率是 $\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 把所有能引申的问题个人感觉都在这篇文章整理的差不多了，感觉要提前一下数据库八股的优先级，毕竟这个项目在我的整个简历中放到了很显眼的位置。