无问芯穹-分布式存储实习-一面面经

10.29  处女面，估计是凉经，太紧张了

1. 自我介绍

2. 问两个项目的来源（一个 bitcask kv 存储，一个 orm 框架）
kv 存储是自己读论文做的，然后加了一些优化，orm 是极客兔兔的

3. slice 的底层原理（结构体定义，扩容机制）
从结构体字段开始讲的，然后扩容机制讲了 1.18 版本以前和 1.18 之后分别怎么实现的，修改实现的原因，以及触发扩容后底层数组指针改变等等

4. 所以触发扩容前后底层数组地址是不一样的是吗（是）

5. go map 哈希冲突怎么解决的
说了解决哈希冲突的两种方法（拉链法，开放寻址法），然后讲 go 使用的是拉链法

6. 两种解决办法分别怎么实现的

7. go map 是有序的吗
不是，为了避免开发者认为 map 有序，底层实现上做了处理，导致每次遍历的顺序不一样

8. go gc（三色标记法，混合写屏障）
从追踪回收算法里的标记-清除开始讲，然后引到三色标记（比标记-清除算法多一个标记中断过程），讲标记的含义，三色标记的流程，然后讲用三色标记是为了解决 stw 时间过长的问题，但是单纯的三色标记还没办法解决这个问题，然后引导到屏障技术，讲插入屏障和删除屏障，最后引导到混合写屏障

9. 讲一下 chan 的底层原理吧，这个日常使用应该经常用到
还是从结构体定义开始讲，主要底层循环队列 buf，以及 sendq （发送者 goroutine 队列）和 recvq（接收者 goroutine 队列），以及管道传输操作的本质操作

10. 你觉得 chan 的使用中应该注意什么
缓冲区的使用，然后讲了有缓冲和无缓冲的区别

11. mysql 和 redis 相关
问了俩问题，没准备到，之前看的过去太久想不起来了

12. 介绍一下你的 kv 存储项目吧
bitcask 存储引擎，引入了内存缓存，用跳表做内存索引和内存缓存的数据结构，对键构造 BloomFliter 减少对磁盘和内存缓存的读取，对热点数据用 lru 置换优化，内存缓存的批量刷盘，wal 保证奔溃一致性...

13. 如果内存缓存批量刷盘的时候写入了新数据，导致 lru 置换淘汰数据要写入内存缓存怎么办
刷盘的时候会短暂中指接收 lru 淘汰的数据，计入下一次缓存

14. 你的意思是会短暂的堵塞是吗
是，堵塞期间会先用等待队列接收

15. 也就是说用户感知下其实是插入成功了但是实际是在等待队列是吗
对，简单解释了一下

16. 如果插入数据的情况是覆盖写而不是新数据呢
讲了这一块的处理（最朴素的处理，很低效）

17. （开始拷打，指出了项目的一个问题）那我有一个疑问，如果这个时候断电了，你队列里的数据会丢失吗
（写的时候没意识到这个问题）会丢失的...

18. 那你 wal 预写日志的时机是哪
老实讲了，在等待队列出队到内存缓存接收之间

19. 也就是说确实保证了一定的数据一致性但实际极端情况下还是会有丢失情况对吧
（老实了）短暂沉默，然后：对...

20. 看你使用了跳表做基本数据结构，介绍一下原理
从定义，多级链表，概率讲，然后说各个操作的基本过程，最后分析时间复杂度

21. b 树 / b+ 树
不太熟

22. 项目里用了布隆过滤器，怎么实现快速查询的
讲了原理，二进制向量，哈希映射函数，多次计算哈希，插入/查询过程

23. 手撕：链表删除倒数第 n 个节点

24. 介绍思路，分析时间复杂度

结束...#面经#