這段時間分享了很多校招的面經(jīng)，有很多讀者說想看社招的，其實(shí)社招面試是基于你的工作項(xiàng)目來展開問的，比如你項(xiàng)目用了 xxx 技術(shù)，那么面試就會追問你項(xiàng)目是怎么用 xxx 技術(shù)的，遇到什么難點(diǎn)和挑戰(zhàn)，然后再考察一下這個 xxx 技術(shù)的原理。

今天就分享一位快手社招面經(jīng)，崗位是后端開發(fā)，問題都是基于項(xiàng)目涉及的技術(shù)棧去展開聊的，同時最后也會有算法題。

項(xiàng)目

• 自我介紹+項(xiàng)目介紹
• 就你負(fù)責(zé)比較多的項(xiàng)目詳細(xì)說說，項(xiàng)目背景，data模型，流程，難點(diǎn)和挑戰(zhàn)
• 講講項(xiàng)目后端用到的技術(shù)棧，比如mq，rpc，緩存啥的
• 消息隊列用過嗎，業(yè)務(wù)場景？
• 怎么保證消息的有序性？

Redis

Redis有哪些數(shù)據(jù)類型

回答：String，list，map，set，Zset，stream，hyperloglog。。。

（打斷）追問：map怎么擴(kuò)容，擴(kuò)容時會影響緩存嗎

回答：底層有兩個dict，一個dict負(fù)責(zé)請求，到達(dá)負(fù)載比例進(jìn)行擴(kuò)容，漸進(jìn)式擴(kuò)容，一部分一部分轉(zhuǎn)移到新的dict

追問：擴(kuò)容時訪問key怎么處理?

回答：先從舊dict獲取key，查不到的話，然后從新的dict獲取key

小林補(bǔ)充：

進(jìn)行 rehash 的時候，需要用上 2 個哈希表了。

在正常服務(wù)請求階段，插入的數(shù)據(jù)，都會寫入到「哈希表 1」，此時的「哈希表 2 」 并沒有被分配空間。

隨著數(shù)據(jù)逐步增多，觸發(fā)了 rehash 操作，這個過程分為三步：

• 給「哈希表 2」 分配空間，一般會比「哈希表 1」 大 2 倍；
• 將「哈希表 1 」的數(shù)據(jù)遷移到「哈希表 2」 中；
• 遷移完成后，「哈希表 1 」的空間會被釋放，并把「哈希表 2」 設(shè)置為「哈希表 1」，然后在「哈希表 2」 新創(chuàng)建一個空白的哈希表，為下次 rehash 做準(zhǔn)備。

為了方便你理解，我把 rehash 這三個過程畫在了下面這張圖：

這個過程看起來簡單，但是其實(shí)第二步很有問題，如果「哈希表 1 」的數(shù)據(jù)量非常大，那么在遷移至「哈希表 2 」的時候，因?yàn)闀婕按罅康臄?shù)據(jù)拷貝，此時可能會對 Redis 造成阻塞，無法服務(wù)其他請求。

為了避免 rehash 在數(shù)據(jù)遷移過程中，因拷貝數(shù)據(jù)的耗時，影響 Redis 性能的情況，所以 Redis 采用了漸進(jìn)式 rehash，也就是將數(shù)據(jù)的遷移的工作不再是一次性遷移完成，而是分多次遷移。

漸進(jìn)式 rehash 步驟如下：

• 給「哈希表 2」 分配空間；
• 在 rehash 進(jìn)行期間，每次哈希表元素進(jìn)行新增、刪除、查找或者更新操作時，Redis 除了會執(zhí)行對應(yīng)的操作之外，還會順序?qū)ⅰ腹１?1 」中索引位置上的所有 key-value 遷移到「哈希表 2」 上；
• 隨著處理客戶端發(fā)起的哈希表操作請求數(shù)量越多，最終在某個時間點(diǎn)會把「哈希表 1 」的所有 key-value 遷移到「哈希表 2」，從而完成 rehash 操作。

這樣就巧妙地把一次性大量數(shù)據(jù)遷移工作的開銷，分?jǐn)偟搅硕啻翁幚碚埱蟮倪^程中，避免了一次性 rehash 的耗時操作。

在進(jìn)行漸進(jìn)式 rehash 的過程中，會有兩個哈希表，所以在漸進(jìn)式 rehash 進(jìn)行期間，哈希表元素的刪除、查找、更新等操作都會在這兩個哈希表進(jìn)行。比如，查找一個 key 的值的話，先會在「哈希表 1」 里面進(jìn)行查找，如果沒找到，就會繼續(xù)到哈希表 2 里面進(jìn)行找到。

另外，在漸進(jìn)式 rehash 進(jìn)行期間，新增一個 key-value 時，會被保存到「哈希表 2 」里面，而「哈希表 1」 則不再進(jìn)行任何添加操作，這樣保證了「哈希表 1 」的 key-value 數(shù)量只會減少，隨著 rehash 操作的完成，最終「哈希表 1 」就會變成空表。

跳表結(jié)構(gòu)了解嗎

回答：第一層是雙向鏈表，會有多層來作為鏈表的索引。

追問：和二叉樹有什么區(qū)別，從時間復(fù)雜度和空間復(fù)雜度分析

回答：二叉查找樹的時間復(fù)雜度是O(logn)，空間復(fù)雜度是O(n)；跳表的時間復(fù)雜度是O(log_{k}n)，k為跳表索引步長，空間復(fù)雜度是O(n)

MySQL

MySQL事務(wù)用過嗎，應(yīng)用場景是什么

自己學(xué)習(xí)的demo里用過，場景：銀行轉(zhuǎn)賬

追問：假如是跨行轉(zhuǎn)賬怎么解決事務(wù)

回答：我想一想。。。

小林補(bǔ)充：用分布式事務(wù)

（打斷）追問：跨行先不說，先說不跨行，先說說單庫事務(wù)，事務(wù)的4個基本特性

回答：原子性，一致性，隔離性，持久性

追問：一致性指的是什么

回答：一致性指的是事務(wù)提交前后數(shù)據(jù)庫狀態(tài)一致，是原子性，隔離性和持久性的整合

追問：隔離級別有哪幾種

回答：讀未提交，讀已提交，可重復(fù)讀，序列化

追問：可重復(fù)讀是是什么意思，怎么實(shí)現(xiàn)的

同一個事務(wù)中多次讀取結(jié)果一致。通過Read View + MVCC實(shí)現(xiàn)，在事務(wù)開始時創(chuàng)建一個Read View，之后都用這個Read View。

追問：可重復(fù)讀具體實(shí)現(xiàn)細(xì)節(jié)

回答：Read View的結(jié)構(gòu)包含（1）當(dāng)前事務(wù)id，（2）active事務(wù)id列表，（3）最小active事務(wù)id記為min_txn_id，（4）next事務(wù)id記為max_txn_id。如果record對應(yīng)的事務(wù)id，小于最小active事務(wù)id，直接讀；否則讀取最小active事務(wù)id之前版本的數(shù)據(jù)（這塊的邏輯答得有問題，用語言表達(dá)時有點(diǎn)混亂，可以私下多練習(xí)練習(xí)表達(dá)）

小林補(bǔ)充：

我們需要了解兩個知識：

• Read View 中四個字段作用；
• 聚簇索引記錄中兩個跟事務(wù)有關(guān)的隱藏列；

那 Read View 到底是個什么東西？

Read View 有四個重要的字段：

• m_ids ：指的是在創(chuàng)建 Read View 時，當(dāng)前數(shù)據(jù)庫中「活躍事務(wù)」的事務(wù) id 列表，注意是一個列表，“活躍事務(wù)”指的就是，啟動了但還沒提交的事務(wù)。
• min_trx_id ：指的是在創(chuàng)建 Read View 時，當(dāng)前數(shù)據(jù)庫中「活躍事務(wù)」中事務(wù) id 最小的事務(wù)，也就是 m_ids 的最小值。
• max_trx_id ：這個并不是 m_ids 的最大值，而是創(chuàng)建 Read View 時當(dāng)前數(shù)據(jù)庫中應(yīng)該給下一個事務(wù)的 id 值，也就是全局事務(wù)中最大的事務(wù) id 值 + 1；
• creator_trx_id ：指的是創(chuàng)建該 Read View 的事務(wù)的事務(wù) id。

知道了 Read View 的字段，我們還需要了解聚簇索引記錄中的兩個隱藏列。

假設(shè)在賬戶余額表插入一條小林余額為 100 萬的記錄，然后我把這兩個隱藏列也畫出來，該記錄的整個示意圖如下：

對于使用 InnoDB 存儲引擎的數(shù)據(jù)庫表，它的聚簇索引記錄中都包含下面兩個隱藏列：

• trx_id，當(dāng)一個事務(wù)對某條聚簇索引記錄進(jìn)行改動時，就會把該事務(wù)的事務(wù) id 記錄在 trx_id 隱藏列里；
• roll_pointer，每次對某條聚簇索引記錄進(jìn)行改動時，都會把舊版本的記錄寫入到 undo 日志中，然后這個隱藏列是個指針，指向每一個舊版本記錄，于是就可以通過它找到修改前的記錄。

在創(chuàng)建 Read View 后，我們可以將記錄中的 trx_id 劃分這三種情況：

一個事務(wù)去訪問記錄的時候，除了自己的更新記錄總是可見之外，還有這幾種情況：

• 如果記錄的 trx_id 值小于 Read View 中的 min_trx_id 值，表示這個版本的記錄是在創(chuàng)建 Read View 前已經(jīng)提交的事務(wù)生成的，所以該版本的記錄對當(dāng)前事務(wù)可見。

• 如果記錄的 trx_id 值大于等于 Read View 中的 max_trx_id 值，表示這個版本的記錄是在創(chuàng)建 Read View 后才啟動的事務(wù)生成的，所以該版本的記錄對當(dāng)前事務(wù)不可見。

• 如果記錄的 trx_id 值在 Read View 的

  min_trx_id
  

  和

  max_trx_id
  

  之間，需要判斷 trx_id 是否在 m_ids 列表中：

  • 如果記錄的 trx_id 在 m_ids 列表中，表示生成該版本記錄的活躍事務(wù)依然活躍著（還沒提交事務(wù)），所以該版本的記錄對當(dāng)前事務(wù)不可見。
  • 如果記錄的 trx_id 不在 m_ids列表中，表示生成該版本記錄的活躍事務(wù)已經(jīng)被提交，所以該版本的記錄對當(dāng)前事務(wù)可見。

MySQL binlog，redolog和undolog的區(qū)別

回答：從這三種log的功能進(jìn)行分析，undolog用來做事務(wù)回滾；redolog用來處理mysql宕機(jī)（或進(jìn)程掛掉）時的數(shù)據(jù)恢復(fù)；binlog記錄所有的數(shù)據(jù)修改操作，可以用來做全量的數(shù)據(jù)恢復(fù)，主從復(fù)制（后一點(diǎn)當(dāng)時沒答出來）。

小林補(bǔ)充：

1. binlog（二進(jìn)制日志）：記錄所有對MySQL數(shù)據(jù)庫的修改操作，包括插入、更新和刪除等。binlog主要用于數(shù)據(jù)恢復(fù)到指定時間點(diǎn)或者指定事務(wù)。可以使用mysqlbinlog命令將binlog文件解析成SQL語句，從而恢復(fù)MySQL數(shù)據(jù)庫的狀態(tài)。

2. redolog（重做日志）：記錄所有對MySQL數(shù)據(jù)庫的修改操作，但是只記錄了物理操作，比如頁的修改。redolog主要用于MySQL的崩潰恢復(fù)，即在MySQL崩潰后，通過重做日志，將數(shù)據(jù)庫恢復(fù)到最近一次提交的狀態(tài)。可以使用 Forcing InnoDB Recovery 來進(jìn)行崩潰恢復(fù)。

3. undolog（回滾日志）：用于記錄事務(wù)的回滾操作，即在事務(wù)執(zhí)行過程中，如果發(fā)生了回滾，會將回滾操作記錄到undolog中。undolog主要用于 MySQL 的回滾操作，比如使用ROLLBACK語句回滾事務(wù)。undolog是InnoDB存儲引擎的特有日志，不同于其他存儲引擎。

追問：binlog和redolog做數(shù)據(jù)恢復(fù)的區(qū)別

回答：redolog有大小限制，數(shù)據(jù)可能被覆蓋，用來處理緊急數(shù)據(jù)庫故障；binlog是全量操作日志，可以進(jìn)行做全量的數(shù)據(jù)恢復(fù)。

小林補(bǔ)充：

binlog和redolog都是用于MySQL數(shù)據(jù)庫的日志。它們都可以用于數(shù)據(jù)恢復(fù)，但是它們的使用場景和恢復(fù)方法有所不同。

binlog是MySQL的二進(jìn)制日志，它記錄了所有對MySQL數(shù)據(jù)庫的修改操作，包括插入、更新和刪除等。binlog可以用于恢復(fù)MySQL數(shù)據(jù)庫到指定的時間點(diǎn)或者指定的事務(wù)。具體來說，可以使用mysqlbinlog命令將binlog文件解析成SQL語句，然后再執(zhí)行這些SQL語句，從而恢復(fù)MySQL數(shù)據(jù)庫的狀態(tài)。

redolog是MySQL的重做日志，它記錄了所有對MySQL數(shù)據(jù)庫的修改操作，但是只記錄了物理操作，比如頁的修改。redolog可以用于恢復(fù)MySQL數(shù)據(jù)庫的崩潰恢復(fù)，即在MySQL崩潰后，通過重做日志，將數(shù)據(jù)庫恢復(fù)到最近一次提交的狀態(tài)。具體來說，可以使用innodb_recovery命令來進(jìn)行崩潰恢復(fù)，該命令會根據(jù)重做日志來恢復(fù)數(shù)據(jù)庫。

因此，binlog和redolog都可以用于數(shù)據(jù)恢復(fù)，但是它們的使用場景和恢復(fù)方法有所不同。binlog主要用于數(shù)據(jù)恢復(fù)到指定時間點(diǎn)或者指定事務(wù)，而redolog主要用于MySQL的崩潰恢復(fù)。

算法

• 合并兩個有序數(shù)組

面試總結(jié)

感覺

不足之處

有些地方的表達(dá)邏輯不夠清晰，代碼得多寫。