做分布式RocksDB的組，4.30號(hào)的時(shí)候同學(xué)跟我說已經(jīng)看不到“分布式kv”這個(gè)崗了，也許是因?yàn)榛軑徣笨诓淮蟀?，這就是我們的基架呀！真是基基又架架呀！

4.24 一面

面試官比較和藹

• 誒那個(gè)LSMKV是不是你們大二下的課程設(shè)計(jì)呀？是的
• 常規(guī)介紹：鍵值分離的內(nèi)存層和持久層，內(nèi)存層跳表；布隆過濾器篩除真陰性，漏掉假陽性；Compaction的實(shí)現(xiàn)和GC簡(jiǎn)單介紹
• 問：鍵值分離的GC如何實(shí)現(xiàn)？常規(guī)介紹，查找前面的(key, v_offset, value)的key是否是最新的（通過v_offset是否是當(dāng)前體系中最新的記錄），如果是重新插入，否則忽略；然后解釋了一下fallocate(PUNCH_HOLE)的機(jī)制，即在數(shù)據(jù)塊層面釋放被打洞的完整數(shù)據(jù)塊，置零部分被打洞的數(shù)據(jù)塊（的被打洞部分），在cpp接口層面認(rèn)為文件“大小”這個(gè)元數(shù)據(jù)不變，但是在被打洞區(qū)域查詢值都將返回0
• 問：GC打洞會(huì)導(dǎo)致讀放大（應(yīng)該指的就是定期垃圾回收會(huì)導(dǎo)致某些讀操作被中途阻塞），有什么方法區(qū)減小讀放大的影響嗎？回答的是開一個(gè)線程去后臺(tái)GC，類似shadow copy的策略，先初始化并寫入要寫入的鍵值對(duì)，然后再打洞（應(yīng)該有點(diǎn)bug，需要再推敲一下回答）
• 追問：能不能從GC的角度優(yōu)化？比如GC數(shù)據(jù)分布比較連續(xù)，空洞較少？我們當(dāng)時(shí)就是連續(xù)空洞，連續(xù)有效數(shù)據(jù)，因?yàn)榭斩炊际菑念^打的，回收是插入到尾部的
• 追問：那你這種方式雖然空洞連續(xù)，但是因?yàn)橐粋€(gè)一個(gè)查，所以還是有讀寫放大，你有沒有了解業(yè)界針對(duì)GC的取舍？確實(shí)不了解，學(xué)習(xí)項(xiàng)目和業(yè)界還是有差距
• 問：KV分離式是什么時(shí)候分離的？flush到磁盤的時(shí)候分離
• 追問：memtable為什么不鍵值分離呢？回答跳表支持順序訪問，分不分離好像問題不大，直接掃一遍；
• 追問：某個(gè)什么risky(RocksDB??)論文里寫的是在WAL的時(shí)候就鍵值分離了，在內(nèi)存層就類似持久層的內(nèi)存分離方法分離了？這我確實(shí)不了解
• 問：你現(xiàn)在的方案有啥可優(yōu)化的點(diǎn)嗎？
• 寫放大：compaction帶來的阻塞，使用immutable memtable話術(shù)進(jìn)行忽悠，用immutable后臺(tái)寫，從類似shadow copy機(jī)制進(jìn)行寫，而讀則是讀原來的SSTable，等到真正需要修改指針指向的時(shí)候再加鎖回退之類的
• 讀放大：自己實(shí)現(xiàn)的LRU緩存，要讀某個(gè)文件的時(shí)候先讀緩存沒被追問
• 開始問科研項(xiàng)目，不方便介紹
• 做題，非常尷尬："aaba"查找所有可拆分的子串配對(duì)情況["a", "a", "b", "a"] ["aa", "b", "a"] ["aba", "a"]，不會(huì)做，說了個(gè)方法太復(fù)雜了，回溯問題其實(shí)蠻簡(jiǎn)單的，還是不會(huì)就換了道更簡(jiǎn)單的
• 計(jì)算二叉樹中所有左葉子結(jié)點(diǎn)的和；還是他么沒思路，后面他提示了一會(huì)兒才寫出個(gè)偽代碼，這次真的是寫代碼寫的第二差的一次（最差的是拼多多二面，連根毛都沒寫出來），后面還被提示沒加遞歸終止條件！
• 反問：是轉(zhuǎn)正實(shí)習(xí)嗎？是問業(yè)務(wù)，kv分布存儲(chǔ)應(yīng)用場(chǎng)景，他說有很多，訂單、模型、etc.

第二天約二面

4.28 滴滴二面

• 算法題：給兩個(gè)字符串，找出它們的最大子串，如a="abcd" b="bcde"的最大子串為"bcd"
• 二維dp問題，算法設(shè)計(jì)課講過的思路
• 面試官：你是不是做過這題？“我刷不一定有刷過，但是算法課上講過”
• 10min完成
• 開始八股了，這次項(xiàng)目問得很少，可能是一面項(xiàng)目問爆了，兩個(gè)極端
• free的時(shí)候如何知道這個(gè)要釋放的內(nèi)存大??？先扯了ics malloc lab相關(guān)的多級(jí)鏈表，被打斷說這不是一個(gè)東西
• 然后說malloc的時(shí)候會(huì)給這塊區(qū)域分配一塊空間存“是否釋放”、“大小”等元數(shù)據(jù)，他點(diǎn)了點(diǎn)頭
• 解釋智能指針
• shared_ptr構(gòu)建在棧上的對(duì)象，析構(gòu)的時(shí)候會(huì)自動(dòng)進(jìn)行減引用計(jì)數(shù)/回收資源的操作指向一個(gè)結(jié)構(gòu)體，結(jié)構(gòu)體包括強(qiáng)引用計(jì)數(shù)（幾個(gè)shared_ptr）和弱引用計(jì)數(shù)（幾個(gè)weak_ptr），以及指向真正對(duì)象的指針
• 強(qiáng)引用計(jì)數(shù)為0會(huì)銷毀真正對(duì)象的指針，且不會(huì)再被shared_ptr指向，弱引用計(jì)數(shù)為0且強(qiáng)引用計(jì)數(shù)為0會(huì)銷毀結(jié)構(gòu)體
• 面試官點(diǎn)了點(diǎn)頭
• 大概講下B樹和B+樹的區(qū)別吧？
• 不記得了，稍微講了下B+樹，比如非葉子節(jié)點(diǎn)和葉子結(jié)點(diǎn)，葉子結(jié)點(diǎn)會(huì)用鏈表連起來B樹真忘了
• 你覺得要讓你存一個(gè)B+樹你要怎么存在磁盤上？
• 這個(gè)沒有背過標(biāo)準(zhǔn)答案，臨時(shí)想了想：頂層的非葉子節(jié)點(diǎn)存在一個(gè)塊內(nèi)，非頂層的葉子結(jié)點(diǎn)相鄰子樹且空間和磁盤物理塊大小差不多的話就可以存在一個(gè)塊內(nèi)，方便索引的順序查找與遍歷，避免頻繁隨機(jī)讀取各個(gè)物理塊
• 追問：那么這個(gè)樹的節(jié)點(diǎn)具體怎么存呢？比如如何區(qū)分左右子節(jié)點(diǎn)，如何區(qū)分空節(jié)點(diǎn)？
• 用類似數(shù)組構(gòu)建堆的思路來區(qū)分左右子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)存(len, val)元組，空節(jié)點(diǎn)存(len=0)表示空（面試官說也可以，估計(jì)不是標(biāo)答，但是是看臨場(chǎng)思路吧）
• 線程間同步的鎖有什么？
• std::mutex、std::atomic、std::condition_variable、sem_t
• 吟唱八股：互斥鎖、原子變量、條件變量、信號(hào)量
• 問std::mutex的實(shí)現(xiàn) 原子地設(shè)置標(biāo)記位，然后底層可能是CAS、FAA這種操作，拿到鎖就繼續(xù)，沒拿到就掛起
• 追問：如果沒有std::mutex而是叫你自己實(shí)現(xiàn)，你要如何實(shí)現(xiàn)
• std::atomic + spin_lock + sleep；后面說還可以用條件變量，被提示條件變量是基于互斥鎖的，且spin_locksleep也不是很好
• 我不懂如何主動(dòng)掛起一個(gè)線程的系統(tǒng)調(diào)用接口，就說了下需要掛起接口，讓線程進(jìn)入RUNNABLE隊(duì)列中
• 解釋死鎖
• 八股：互斥，持有并等待、構(gòu)成環(huán)
• 如何在運(yùn)行中程序檢測(cè)死鎖？
• 先回答了基于散列表的圖，被提示再想想
• 不對(duì)稱的節(jié)點(diǎn)（鎖節(jié)點(diǎn)和線程節(jié)點(diǎn)），不能用單一的散列表構(gòu)成有向圖，回答維護(hù)兩個(gè)散列表（鎖->線程，線程->鎖）表示指向關(guān)系，再dfs
• 問了多線程場(chǎng)景下的通用并發(fā)策略，沒有給具體例子
• 細(xì)粒度鎖
• OCC
• MVCC
• TCP三揮四握，以及一些細(xì)節(jié)
• 為什么TCP上還需要HTTP？ 回答TCP不能完成用戶程序自身定義的各類通信協(xié)議，比如TCP無法既集成HTTP又集成WebSocket
• 科研項(xiàng)目，不方便透露
• 問主從備份策略：冷備份、暖備份、熱備份
• 基數(shù)樹如何存在磁盤上：想故技重施（B+樹），但是其實(shí)不行，因?yàn)榛鶖?shù)樹不是扁平結(jié)構(gòu)而是稀疏瘦長(zhǎng)的，會(huì)帶來元數(shù)據(jù)的payload，未回答出來
• 叫我寫跳表，但是就幾分鐘了，大二下寫的，說可以給你看gitee

說起來有點(diǎn)好笑，4.28剛好是字節(jié)hr面的時(shí)候，我當(dāng)時(shí)問了下學(xué)長(zhǎng)說字節(jié)hr面就是走個(gè)流程，然后幾個(gè)小時(shí)后面滴滴，完全沒準(zhǔn)備，以為字節(jié)穩(wěn)了；后面是字節(jié)hr面掛了，樂

4.29 oc

5.8 offer