做分布式RocksDB的組，4.30號的時候同學(xué)跟我說已經(jīng)看不到“分布式kv”這個崗了，也許是因為基架崗缺口不大吧，這就是我們的基架呀！真是基基又架架呀！

4.24 一面

面試官比較和藹

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

第二天約二面

4.28 滴滴二面

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

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

4.29 oc

5.8 offer