滴滴分布式kv

做分布式RocksDB的组，4.30号的时候同学跟我说已经看不到“分布式kv”这个岗了，也许是因为基架岗缺口不大吧，这就是我们的基架呀！真是基基又架架呀！

4.24 一面

面试官比较和蔼

• 诶那个LSMKV是不是你们大二下的课程设计呀？是的
• 常规介绍：键值分离的内存层和持久层，内存层跳表；布隆过滤器筛除真阴性，漏掉假阳性；Compaction的实现和GC简单介绍
• 问：键值分离的GC如何实现？常规介绍，查找前面的(key, v_offset, value)的key是否是最新的（通过v_offset是否是当前体系中最新的记录），如果是重新插入，否则忽略；然后解释了一下fallocate(PUNCH_HOLE)的机制，即在数据块层面释放被打洞的完整数据块，置零部分被打洞的数据块（的被打洞部分），在cpp接口层面认为文件“大小”这个元数据不变，但是在被打洞区域查询值都将返回0
• 问：GC打洞会导致读放大（应该指的就是定期垃圾回收会导致某些读操作被中途阻塞），有什么方法区减小读放大的影响吗？回答的是开一个线程去后台GC，类似shadow copy的策略，先初始化并写入要写入的键值对，然后再打洞（应该有点bug，需要再推敲一下回答）
• 追问：能不能从GC的角度优化？比如GC数据分布比较连续，空洞较少？我们当时就是连续空洞，连续有效数据，因为空洞都是从头打的，回收是插入到尾部的
• 追问：那你这种方式虽然空洞连续，但是因为要一个一个查，所以还是有读写放大，你有没有了解业界针对GC的取舍？确实不了解，学习项目和业界还是有差距
• 问：KV分离式是什么时候分离的？flush到磁盘的时候分离
• 追问：memtable为什么不键值分离呢？回答跳表支持顺序访问，分不分离好像问题不大，直接扫一遍；
• 追问：某个什么risky(RocksDB??)论文里写的是在WAL的时候就键值分离了，在内存层就类似持久层的内存分离方法分离了？这我确实不了解
• 问：你现在的方案有啥可优化的点吗？
• 写放大：compaction带来的阻塞，使用immutable memtable话术进行忽悠，用immutable后台写，从类似shadow copy机制进行写，而读则是读原来的SSTable，等到真正需要修改指针指向的时候再加锁回退之类的
• 读放大：自己实现的LRU缓存，要读某个文件的时候先读缓存没被追问
• 开始问科研项目，不方便介绍
• 做题，非常尴尬："aaba"查找所有可拆分的子串配对情况["a", "a", "b", "a"] ["aa", "b", "a"] ["aba", "a"]，不会做，说了个方法太复杂了，回溯问题其实蛮简单的，还是不会就换了道更简单的
• 计算二叉树中所有左叶子结点的和；还是他么没思路，后面他提示了一会儿才写出个伪代码，这次真的是写代码写的第二差的一次（最差的是拼多多二面，连根毛都没写出来），后面还被提示没加递归终止条件！
• 反问：是转正实习吗？是问业务，kv分布存储应用场景，他说有很多，订单、模型、etc.

第二天约二面

4.28 滴滴二面

• 算法题：给两个字符串，找出它们的最大子串，如a="abcd" b="bcde"的最大子串为"bcd"
• 二维dp问题，算法设计课讲过的思路
• 面试官：你是不是做过这题？“我刷不一定有刷过，但是算法课上讲过”
• 10min完成
• 开始八股了，这次项目问得很少，可能是一面项目问爆了，两个极端
• free的时候如何知道这个要释放的内存大小？先扯了ics malloc lab相关的多级链表，被打断说这不是一个东西
• 然后说malloc的时候会给这块区域分配一块空间存“是否释放”、“大小”等元数据，他点了点头
• 解释智能指针
• shared_ptr构建在栈上的对象，析构的时候会自动进行减引用计数/回收资源的操作指向一个结构体，结构体包括强引用计数（几个shared_ptr）和弱引用计数（几个weak_ptr），以及指向真正对象的指针
• 强引用计数为0会销毁真正对象的指针，且不会再被shared_ptr指向，弱引用计数为0且强引用计数为0会销毁结构体
• 面试官点了点头
• 大概讲下B树和B+树的区别吧？
• 不记得了，稍微讲了下B+树，比如非叶子节点和叶子结点，叶子结点会用链表连起来B树真忘了
• 你觉得要让你存一个B+树你要怎么存在磁盘上？
• 这个没有背过标准答案，临时想了想：顶层的非叶子节点存在一个块内，非顶层的叶子结点相邻子树且空间和磁盘物理块大小差不多的话就可以存在一个块内，方便索引的顺序查找与遍历，避免频繁随机读取各个物理块
• 追问：那么这个树的节点具体怎么存呢？比如如何区分左右子节点，如何区分空节点？
• 用类似数组构建堆的思路来区分左右子节点，每个节点存(len, val)元组，空节点存(len=0)表示空（面试官说也可以，估计不是标答，但是是看临场思路吧）
• 线程间同步的锁有什么？
• std::mutex、std::atomic、std::condition_variable、sem_t
• 吟唱八股：互斥锁、原子变量、条件变量、信号量
• 问std::mutex的实现 原子地设置标记位，然后底层可能是CAS、FAA这种操作，拿到锁就继续，没拿到就挂起
• 追问：如果没有std::mutex而是叫你自己实现，你要如何实现
• std::atomic + spin_lock + sleep；后面说还可以用条件变量，被提示条件变量是基于互斥锁的，且spin_locksleep也不是很好
• 我不懂如何主动挂起一个线程的系统调用接口，就说了下需要挂起接口，让线程进入RUNNABLE队列中
• 解释死锁
• 八股：互斥，持有并等待、构成环
• 如何在运行中程序检测死锁？
• 先回答了基于散列表的图，被提示再想想
• 不对称的节点（锁节点和线程节点），不能用单一的散列表构成有向图，回答维护两个散列表（锁->线程，线程->锁）表示指向关系，再dfs
• 问了多线程场景下的通用并发策略，没有给具体例子
• 细粒度锁
• OCC
• MVCC
• TCP三挥四握，以及一些细节
• 为什么TCP上还需要HTTP？ 回答TCP不能完成用户程序自身定义的各类通信协议，比如TCP无法既集成HTTP又集成WebSocket
• 科研项目，不方便透露
• 问主从备份策略：冷备份、暖备份、热备份
• 基数树如何存在磁盘上：想故技重施（B+树），但是其实不行，因为基数树不是扁平结构而是稀疏瘦长的，会带来元数据的payload，未回答出来
• 叫我写跳表，但是就几分钟了，大二下写的，说可以给你看gitee

说起来有点好笑，4.28刚好是字节hr面的时候，我当时问了下学长说字节hr面就是走个流程，然后几个小时后面滴滴，完全没准备，以为字节稳了；后面是字节hr面挂了，乐

4.29 oc

5.8 offer