「面試」拿到B站的意向書

此次B站伺服器端開發面試之旅可謂驚險，不過通過對大部分面試題套路的掌握，不出意外還是拿下了，下面我們來看看這些騷題是不是常見的不能再常見的了。這些面試題看了就能面上？當然不是，只是通過這些題讓自己知道所欠缺的是什麼，以及可以去看看哪些資料。

1 作業系統相關

• 自旋鎖和一般鎖的區別是什麼？為什麼要使用自旋鎖？

當一個執行緒在獲取鎖的時候，如果這個鎖已經被其他執行緒獲取，那麼這個執行緒不會破門而入，而是迴圈等待，但是嗷嗷待哺，需要不斷地嗷嗷叫判斷鎖是否被成功獲取，直到獲取到鎖才會退出迴圈。

自旋鎖通常會出現哪些問題?

如果某個執行緒拿著鎖死不放手，其他執行緒沒法拿到這把鎖，只好等待獲取鎖的執行緒進入迴圈等待的狀態，等待不是睡覺，還是會消耗CPU，等待久了就會導致CPU的使用率太高。

那麼自旋鎖和其他鎖到底有啥不同？

從執行緒狀態來看，自旋鎖的狀態是執行-執行-執行。而非自旋鎖的狀態是執行—阻塞—執行，所以自旋鎖會更高效。

不管是什麼鎖，都是為了實現保護共用資源而提出的一種鎖機制，都是為了對某項資源的互斥使用。對於互斥鎖而言，如果資源已經被佔用，那麼資源的申請者只會進入睡眠的狀態。而自旋鎖不會引起呼叫者睡眠，而是一直迴圈在那裡檢視該自旋鎖的保持著是否已經釋放了鎖。

那麼在Java中如何去實現一個自旋鎖

public class SpinLock {
    private AtomicReference<Thread> cas = new AtomicReference<Thread>();
    public void lock() {
        Thread current = Thread.currentThread();
        // 利用CAS
        while (!cas.compareAndSet(null, current)) {
            // DO 
        }
    }
    public void unlock() {
        Thread current = Thread.currentThread();
        cas.compareAndSet(current, null);
    }
}

上段程式碼中，方法lock利用的CAS，當執行緒A獲取鎖的時候，成功獲取不會進入while迴圈。如果此時執行緒A沒有釋放鎖，當執行緒B來獲取鎖的時候，由於不滿足CAS，就會進入whilei迴圈，不斷判斷是否滿足CAS，直到執行緒A呼叫unlock釋放。

自旋鎖有哪些優點？

1. 因為執行在使用者態，沒有上下文的執行緒狀態切換，執行緒一直處於active，減少了不必要的上下文切換，從而執行速度較快
2. 因為非自旋鎖在沒有獲取鎖的情況下會進入阻塞狀態，從而進入核心態，此時就需要執行緒的上下文切換，因為阻塞後進入核心排程狀態，會導致使用者態和核心態之間的切換，影響鎖的效能。

• 瞭解哪些I/O模型?select是阻塞IO嗎？

首先將IO模型給安排一遍，然後把自己很熟悉的IO模型詳細說一波並介紹出應用場景，這個裝的X就算比較完美，具體的非常詳細的在下一篇文章，這裡簡要說一波。這一部分在上一篇詳細闡述過

阻塞IO

我們知道在呼叫某個函數的時候無非就是兩種情況，要麼馬上返回，然後根據返回值進行接下來的業務處理。當在使用阻塞IO的時候，應用程式會被無情的掛起，等待核心完成操作，因為此時的核心可能將CPU時間切換到了其他需要的程序中，在我們的應用程式看來感覺被卡主(阻塞)了。

非阻塞IO

當使用非阻塞函數的時候，和阻塞IO類比，核心會立即返回，返回後獲得足夠的CPU時間繼續做其他的事情。

IO複用模型

當使用fgets等待標準輸入的時候，如果此時通訊端有資料但不能讀出。IO多路複用意味著可以將標準輸入、通訊端等都當做IO的一路，任何一路IO有事件發生，都將通知相應的應用程式去處理相應的IO事件，在我們看來就反覆同時可以處理多個事情。這就是IO複用。

訊號驅動IO

在訊號驅動式 I/O 模型中，應用程式使用套介面進行訊號驅動 I/O，並安裝一個訊號處理常式，程序繼續執行並不阻塞。當資料準備好時，程序會收到一個 SIGIO 訊號，可以在訊號處理常式中呼叫 I/O 操作函數處理資料。

非同步IO

用程式告知核心啟動某個操作，並讓核心在整個操作（包括將資料從核心拷貝到應用程式的緩衝區）完成後通知應用程式。那麼和訊號驅動有啥不一樣?

• 講講select和epoll的區別？

這裡一樣的套路，先說出兩者的用途，然後兩者的優缺點。

select的缺點

• select返回的是含有整個控制程式碼的陣列，應用程式需要遍歷整個陣列才能發現哪些控制程式碼發生了事件
• select的觸發方式是水平觸發，應用程式如果沒有完成對一個已經就緒的檔案描述符進行IO操作，那麼之後每次select呼叫還是會將這些檔案描述符通知程序
• 核心 / 使用者空間記憶體拷貝問題，select每次都會改變核心中的控制程式碼資料結構集，因而每次select呼叫時都需要從使用者空間向核心空間複製所有的控制程式碼資料結構，產生巨大的開銷
• 單個程序能夠監視的檔案描述符的數量存在最大限制，通常是1024，當然可以更改數量

epoll實現

epoll在核心中會維護一個紅黑樹和一個雙向連結串列，紅黑樹存放通過epoll_ctl方法向epoll物件中新增進來的事件，所以不需要每次呼叫epoll_wait都全量複製所有的事件結構。雙向連結串列存放就緒的事件，所有新增到epoll中的事件都會與裝置(網路卡)驅動程式建立回撥關係，也就是說，當相應的事件發生時會呼叫這個回撥方法，這個回撥方法在核心中叫ep_poll_callback,它會將發生的事件新增到rdlist雙連結串列中。呼叫epoll_wait就會直接返回連結串列中的就緒事件，效率高。

• select適合少量活躍連線，一般幾千。

• epoll適合大量不太活躍的連線。

• 樂觀鎖和悲觀鎖瞭解嗎？

這個問題延伸的問題會很多，比如執行緒安全，CAS原理，優缺點等。

啥是悲觀和樂觀，咋們面試的時候不得樂觀一些。想給面試來一波官方解釋，然後大白話解釋一波就差不多了。

官方：悲觀鎖是總是假設最壞的情況，每次那資料都認為別人會修改它，所以每次去那資料都要上鎖，這樣別人去拿這個資料就會阻塞。樂觀鎖就不一樣了，總是覺得一切都是最好的安排，每次拿資料都認為別人不會修改，所以也就不上鎖，但是在更新的時候會判斷這個期間別人有沒有更新這個資料。

• 什麼是快取穿透？如何避免？什麼是快取雪崩？何如避免？

快取穿透

一般來說，快取系統會通過key去快取查詢，如果不存在對應的value，就應該去後端系統查詢（比如DB）。這個時候如果一些惡意的請求到來，就會故意查詢不存在的key,當某一時刻的請求量很大，就會對後端系統造成很大的壓力。這就叫做快取穿透。

如何避免？

對查詢結果為空的情況也進行快取，快取時間設定短一點，或者該key對應的資料insert了之後清除快取。對一定不存在的key進行過濾。可以把所有的可能存在的key放到一個大的Bitmap中，查詢時通過該bitmap過濾。

快取雪崩

當快取伺服器重新啟動或者大量快取集中在某一個時間段失效，這樣在失效的時候，會給後端系統帶來很大壓力。導致系統崩潰。

如何避免？

在快取失效後，通過加鎖或者佇列來控制讀資料庫寫快取的執行緒數量。比如對某個key只允許一個執行緒查詢資料和寫快取，其他執行緒等待。

做二級快取，A1為原始快取，A2為拷貝快取，A1失效時，可以存取A2，A1快取失效時間設定為短期，A2設定為長期。

不同的key，設定不同的過期時間，讓快取失效的時間點儘量均勻。

2 redis相關

如果是後端/伺服器端面試的同學，怎麼說都的去找一本redis書來看看，其出現的概率只有那麼大了，切記切記。看看B站問了哪幾個問題。

• redis的淘汰刪除策略瞭解嗎？

能說不了解嗎，就算是沒有聽說過，咋們也可以來一句：「不好意思面試官，這一塊還不怎麼深入，但是從字面意思來理解巴拉巴拉」，不至於一臉懵逼。下面我們看看redis的快取策略

Redis中通過maxmemory引數來設定記憶體的使用上限，如果Redis所使用記憶體超過設定的最大值，那麼會根據組態檔中的策略選取要刪除的key來刪除，從而留出新的鍵值空間。主要的六種淘汰key策略

1. volatile-lru

在鍵空間中設定過期時間，移除哪些最近最少使用的key，佔著茅坑不拉屎的key

2. allkeys-lru

移除最近最少使用的key

3. volatile-random

在鍵空間中設定過期時間，隨機移除一個key

4. allkeys-random

隨機移除一個key

5. noeviction

當記憶體使用達到閥值的時候，所有引起申請記憶體的命令會報錯；

ok，現在知道了需要淘汰哪些key，那我們如何去淘汰這些key

1. 定時刪除

很簡單，設定一個鬧鐘，鬧鐘響了就刪除即可。這種方式對於記憶體來說還是比較友好，記憶體不需要啥額外的操作，直接通過定時器就可保證儘快的刪除。對於CPU來說就有點麻煩了，如果過期鍵比較多，那麼定時器也就多，這刪除操作就會佔用太多的CPU資源

2. 惰性刪除

每次從鍵空間獲取鍵的時候檢查鍵的過期時間，如果過期了，刪除完事。

3. 定期刪除

每隔一段時間就去資料庫檢查，刪除過期的鍵

這種方案是定時刪除和惰性刪除的中和方法，既通過限制刪除操作執行的時長來減少對CPU時間的影響，也能減少記憶體的浪費。但是難點在於間隔時長需要根據業務情況而定。

3 mysql

• mysql中使用的鎖有哪些？什麼時候使用行鎖，什麼時候會使用表鎖？

InnoDB中的行鎖是通過索引上的索引項實現，主要特點是，只有通過索引條件檢索資料，InnoDB才會使用行級鎖，否則InnoDB將使用表鎖。

這裡注意，在Mysql中，行級鎖不是鎖記錄而是鎖索引。索引又分為主鍵索引和非主鍵索引兩種。如果在一條語句中操作了非主鍵索引，Mysql會鎖定該非主鍵索引，再鎖定相關的主鍵索引。

• 瞭解過間隙鎖嗎？間隙鎖的加鎖範圍是怎麼確定的？
• 瞭解B+樹嗎？B+樹什麼時候會出現結點分裂？

這個回答在上一篇的B+樹已經詳細說了。這裡簡述一下

1. 將已滿結點進行分裂，將已滿節點後M/2節點生成一個新節點，將新節點的第一個元素指向父節點。
2. 父節點出現已滿，將父節點繼續分裂。
3. 一直分裂，如果根節點已滿，則需要分類根節點，此時樹的高度增加。

• 事務還沒執行完資料庫掛了，重新啟動的時候會發生什麼？
• undo紀錄檔和redo紀錄檔分別是幹嘛的？

redo log重做紀錄檔是InnDB儲存引擎層的，用來保證事務安全。在事務提交之前，每個修改操作都會記錄變更後的資料，儲存的是物理紀錄檔-資料，防止發生故障的時間點，有髒頁未寫入磁碟，在重新啟動mysql的時候，根據redo log進行重做從而達到事務的永續性

undo log回滾紀錄檔儲存了事務發生之前的資料的一個版本，可以用於回滾，同時也提供多版本並行控制下的讀。

• 簡單講講資料庫的MVCC的實現原理？

細說太多了，幾個大寫字母代表啥，這幾個大寫字母又是如何關聯起來完事。細問再深究

• mysql的binlog紀錄檔什麼時候會使用？

首先應該知道binlog是一個二進位制檔案，記錄所有增刪改操作，節點之間的複製都會依靠binlog來完成。從底層原理來說，binlog有三個模式

1. 模式1–row模式

每一行的資料被修改就會記錄在紀錄檔中，然後在slave段對相同的資料進行修改。比如說"update xx where id in(1,2,3,4,5)"，使用此模式就會記錄5條記錄

2. 模式2–statement模式

修改資料的sql會記錄到master的binlog中。slave在複製的時候sql thread會解析成和原來maseter端執行過的相同的sql在此執行

3. 模式3–mixed模式

mixed模式即混合模式，Mysql會根據執行的每一條具體sql區分對待記錄的紀錄檔形式。那麼binlog的主從同步流程到底是咋樣的

流程簡述：

Master執行完增刪改操作後都會記錄binlog紀錄檔,當需要同步的時候會主動通知slave節點，slave收到通知後使用IO THREAD主動去master讀取binlog寫入relay紀錄檔(中轉紀錄檔),然後使 SQL THREAD完成對relay紀錄檔的解析然後入庫操作,完成同步。

4 基本資料結構

• 使用LRU時，如果短時間內會出現大量只會使用一次的資料，可能導致之前大量高頻使用的快取被刪除，請問有什麼解決辦法?
• 瞭解過迴圈連結串列嗎？他的長度怎麼計算？

他的主要特點是連結串列中的最後一個節點的指標域指向頭結點，整個連結串列形成一個環。***這裡*迴圈連結串列判斷連結串列結束的標誌是，判斷尾節點是不是指向頭結點

• 哪種資料結構可以支援快速插入，刪除，查詢等操作？

思考這個問題的時候，我們不凡複習下不錯的二分查詢，它依賴陣列隨機存取的特性，其查詢時間複雜度為O(log n)。如果我們將元素放入連結串列中，二分查詢還好使嗎？這就是今天和大家分享的跳錶

理解跳錶

假設使用單連結串列儲存n個元素，其中元素有序如下圖所示

從連結串列中查詢一個元素，自然從頭開始遍歷找到需要查詢的元素，此時的時間複雜度為O(n)。那採用什麼方法可以提高查詢的效率呢？問就是加索引，如何加，我們從這部分資料中抽取幾個元素出來作為單獨的一個連結串列，如下圖所示]

假設此時咋們查詢元素16，首先一級索引處尋找，當找到元素14的時候，下一個節點的值為18，意味著我們尋找的數在這兩個數的中間。此時直接從14節點指標下移到下面的原始連結串列中，繼續遍歷，正好下一個元素就是我們尋找的16。好了，我們小結一下，如果從原始連結串列中尋找元素16，需要遍歷比較8次，如果通過索引連結串列尋找我們只需要5次即可。

我們繼續查詢元素16，此時比較次數變為4次。這樣看來，加一層索引查詢的次數就變少，如果有n個元素到底有多少索引？

假設我們按照每兩個結點就抽出一個結點作為上一層的索引節點，第一層所以節點個數n/2，第二層為n/4,第x級索引的結點個數是第x-1級索引的結點個數的1/2，那第x級索引結點的個數就是n/(2^{x)。假設索引有y級，我們可以得到n/(2}y)=2，從而求得y=log2n-1。

這麼多索引是不是就很浪費記憶體嘞？

假設原始連結串列大小為n，那第一級索引大約有 n/2 個結點，第二級索引大約有 n/4 個結點，以此類推，每上升一級就減少一半，直到剩下 2 個結點。如果我們把每層索引的結點數寫出來，就是一個等比數列。這幾級索引的結點總和就是 n/2+n/4+n/8…+8+4+2=n-2 。所以，跳錶的空間複雜度是 O(n) 。那還能不能降低一些呢。機智的你應該就考慮到假設每三個結點抽取一個節點作為索引連結串列的節點。

跳錶與二叉查詢樹

兩者其查詢的時間複雜度均為O(logn) ，那跳錶還有哪些優勢？

先看二叉查詢樹，

這種結構會導致二叉查詢樹的查詢效率變為 O(n),。

跳錶與紅黑樹

說實話，紅黑樹確實比較複雜，面試的時候讓你寫紅黑樹，你就給他大嘴巴子？

紅黑樹需要通過左右旋的方式去維持樹大小平衡。而跳錶是通過隨機函數來維護前面提到的 「 平衡性 」 。當我們往跳錶中插入資料的時候，我們可以選擇同時將這個資料插入到部分索引層中。如何選擇加入哪些索引層呢？
我們通過一個隨機函數，來決定將這個結點插入到哪幾級索引中，比如隨機函數生成了值 K ，那我們就將這個結點新增到第一級到第 K 級這 K 級索引中。當我們往跳錶中插入資料的時候，我們可以選擇同時將這個資料插入到部分索引層中。

小結

Redis中的有序集合採用了跳錶的方式來實現，其實還採用了雜湊表等資料結構進行融合。它在插入，刪除等都有比較快的速度，雖然紅黑樹也可以做到，但是紅黑樹對於按照區間查詢資料這個操作，跳錶可以做到 O(logn) 的時間複雜度定位區間的起點，然後在原始連結串列中順序往後遍歷就可以了

• 平時愛看技術部落格嗎？分享一篇最近的技術部落格？平時上B站嗎？

看的技術部落格多了，這就是嘮嗑。比如說，看看小賤一天天BB的文章，哈哈哈哈哈

面試官：我擦，尼瑪說的這個我都關注了，難怪我問啥你都能說個一二三。

5 總結

請記下以下幾點:

• 公司招你去是幹活了，不會因為你怎麼怎麼的而降低對你的要求標準。
• 工具上面寫程式碼和手撕程式碼完全不一樣。
• 珍惜每一次面試機會並學會覆盤。
• 對於應屆生主要考察的還是計算機基礎知識的掌握，專案要求沒有那麼高，是自己做的就使勁摳細節，做測試，只有這樣，才知道會遇到什麼問題，遇到什麼難點，如何解決的。從而可以侃侃而談了。
• 非科班也不要怕，怕了你就輸了！一定要多嘗試。

---

我是小藍，一個專為大家分享面試經驗的藍人。如果覺得文章不錯或者對你有點幫助，感謝分享給你的朋友，也可在下方給小藍贊，這對小藍非常重要，謝謝你們，下期再會。