大家好，我是小林。

分享一篇騰訊春招二面面經，崗位是C++后端，考察的內容是C++、Redis、網絡。

c++

shared_ptr的原理

答：內部的共享數據和引用計數實現

補充：

shared_ptr多個指針指向相同的對象。shared_ptr使用引用計數，每一個shared_ptr的拷貝都指向相同的內存。每使用他一次，內部的引用計數加1，每析構一次，內部的引用計數減1，減為0時，自動刪除所指向的堆內存。shared_ptr內部的引用計數是線程安全的，但是對象的讀取需要加鎖。

shared_ptr的一個最大的陷阱是循環引用，循環引用會導致堆內存無法正確釋放，導致內存泄漏，可以通過 weak_ptr 來解決這個問題。

多線程怎么保證引用計數的安全的

答：引用計數這個變量是std::atomic，操作時自帶鎖

常見的鎖有哪些

答：讀寫鎖、互斥鎖這些，再就是一些鎖思想，比如樂觀鎖、悲觀鎖、自旋鎖

valotile關鍵字的用處

答：避免編譯器額外優化

Redis

微博上的熱度排行榜用什么數據結構

答：Zset，講了講zrangebyscore

補充：

Zset 類型（Sorted Set，有序集合） 可以根據元素的權重來排序，我們可以自己來決定每個元素的權重值。比如說，我們可以根據元素插入 Sorted Set 的時間確定權重值，先插入的元素權重小，后插入的元素權重大。

在面對需要展示最新列表、排行榜等場景時，如果數據更新頻繁或者需要分頁顯示，可以優先考慮使用 Sorted Set。

有序集合比較典型的使用場景就是排行榜。例如學生成績的排名榜、游戲積分排行榜、視頻播放排名、電商系統中商品的銷量排名等。

我們以博文點贊排名為例，小林發表了五篇博文，分別獲得贊為 200、40、100、50、150。

# arcticle:1 文章獲得了200個贊
> ZADD user:xiaolin:ranking 200 arcticle:1
(integer) 1
# arcticle:2 文章獲得了40個贊
> ZADD user:xiaolin:ranking 40 arcticle:2
(integer) 1
# arcticle:3 文章獲得了100個贊
> ZADD user:xiaolin:ranking 100 arcticle:3
(integer) 1
# arcticle:4 文章獲得了50個贊
> ZADD user:xiaolin:ranking 50 arcticle:4
(integer) 1
# arcticle:5 文章獲得了150個贊
> ZADD user:xiaolin:ranking 150 arcticle:5
(integer) 1

文章 arcticle:4 新增一個贊，可以使用 ZINCRBY 命令（為有序集合key中元素member的分值加上increment）：

> ZINCRBY user:xiaolin:ranking 1 arcticle:4
"51"

查看某篇文章的贊數，可以使用 ZSCORE 命令（返回有序集合key中元素個數）：

> ZSCORE user:xiaolin:ranking arcticle:4
"50"

獲取小林文章贊數最多的 3 篇文章，可以使用 ZREVRANGE 命令（倒序獲取有序集合 key 從start下標到stop下標的元素）：

# WITHSCORES 表示把 score 也顯示出來
> ZREVRANGE user:xiaolin:ranking 0 2 WITHSCORES
1) "arcticle:1"
2) "200"
3) "arcticle:5"
4) "150"
5) "arcticle:3"
6) "100"

獲取小林 100 贊到 200 贊的文章，可以使用 ZRANGEBYSCORE 命令（返回有序集合中指定分數區間內的成員，分數由低到高排序）：

> ZRANGEBYSCORE user:xiaolin:ranking 100 200 WITHSCORES
1) "arcticle:3"
2) "100"
3) "arcticle:5"
4) "150"
5) "arcticle:1"
6) "200"

rehash的過程講一下

答：新舊表雙寫，逐漸遷移

補充：

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

漸進式 rehash 步驟如下：

• 給「哈希表 2」 分配空間，一般會比「哈希表 1」 大 2 倍；
• 在 rehash 進行期間，每次哈希表元素進行新增、刪除、查找或者更新操作時，Redis 除了會執行對應的操作之外，還會順序將「哈希表 1 」中索引位置上的所有 key-value 遷移到「哈希表 2」 上；
• 隨著處理客戶端發起的哈希表操作請求數量越多，最終在某個時間點會把「哈希表 1 」的所有 key-value 遷移到「哈希表 2」，從而完成 rehash 操作。

這樣就巧妙地把一次性大量數據遷移工作的開銷，分攤到了多次處理請求的過程中，避免了一次性 rehash 的耗時操作。

在進行漸進式 rehash 的過程中，會有兩個哈希表，所以在漸進式 rehash 進行期間，哈希表元素的刪除、查找、更新等操作都會在這兩個哈希表進行。

比如，查找一個 key 的值的話，先會在「哈希表 1」 里面進行查找，如果沒找到，就會繼續到哈希表 2 里面進行找到。

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

遷移過程中老表是什么時候釋放，怎么知道老表可以釋放了

答：通過數據長度

補充：

每個 hash table 都有存著一個 used 字段，每次單步 rehash 完成的時候，最后都會檢查老表即  ht[0].used 是否變成了 0，變成 0 后，就說明老的哈希表里已經沒有數據了，此時就會去 free 掉老表，交換老表新表的指針，rehashidx 置為 -1，然后就完成了整個 rehash。

網絡

不同地區的用戶的請求怎么打到附近的地區呢？

答：講了CDN

補充：

CDN 將內容資源分發到位于多個地理位置機房中的服務器上，這樣我們在訪問內容資源的時候，不用訪問源服務器。而是直接訪問離我們最近的 CDN 節點 ，這樣一來就省去了長途跋涉的時間成本，從而實現了網絡加速。

找到離用戶最近的 CDN 節點是由 CDN 的全局負載均衡器（*Global Sever Load Balance，GSLB*）負責的。

那 GSLB 是在什么時候起作用的呢？在回答這個問題前，我們先來看看在沒有 CDN 的情況下，訪問域名時發生的事情。

在沒有 CDN 的情況下，當我們訪問域名時，DNS 服務器最終會返回源服務器的地址。

比如，當我們在瀏覽器輸入 www.xiaolin.com 域名后，在本地 host 文件找不到域名時，客戶端就會訪問本地 DNS 服務器。

這時候:

• 如果本地 DNS 服務器有緩存該網站的地址，則直接返回網站的地址；
• 如果沒有就通過遞歸查詢的方式，先請求根 DNS，根 DNS 返回頂級 DNS（.com）的地址；再請求 .com 頂級 DNS 得到 xiaolin.com 的域名服務器地址，再從 xiaolin.com 的域名服務器中查詢到 www.xiaolin.com 對應的 IP 地址，然后返回這個 IP 地址，同時本地 DNS 緩存該 IP 地址，這樣下一次的解析同一個域名就不需要做 DNS 的迭代查詢了。

但加入 CDN 后就不一樣了。

會在 xiaolin.com 這個 DNS 服務器上，設置一個 CNAME 別名，指向另外一個域名 www.xiaolin.cdn.com，返回給本地 DNS 服務器。

接著繼續解析該域名，這個時候訪問的就是 xiaolin.cdn.com 這臺 CDN 專用的 DNS 服務器，在這個服務器上，又會設置一個 CNAME，指向另外一個域名，這次指向的就是 CDN 的 GSLB。

接著，本地 DNS 服務器去請求 CDN 的 GSLB 的域名，GSLB 就會為用戶選擇一臺合適的 CDN 節點提供服務，選擇的依據主要有以下幾點：

• 看用戶的 IP 地址，查表得知地理位置，找相對最近的 CDN 節點；
• 看用戶所在的運營商網絡，找相同網絡的 CDN 節點；
• 看用戶請求 URL，判斷哪一臺服務器上有用戶所請求的資源；
• 查詢 CDN 節點的負載情況，找負載較輕的節點；

GSLB 會基于以上的條件進行綜合分析后，找出一臺最合適的 CDN 節點，并返回該 CDN 節點的 IP 地址給本地 DNS 服務器，然后本地 DNS 服務器緩存該 IP 地址，并將 IP 返回給客戶端，客戶端去訪問這個 CDN 節點，下載資源。

TCP的close_wait在哪端，如果我們場景中出現了大量的close_wait，你覺得要怎么排查

答：被動方，代碼邏輯有問題，沒close

補充：

CLOSE_WAIT 狀態是「被動關閉方」才會有的狀態，而且如果「被動關閉方」沒有調用 close 函數關閉連接，那么就無法發出 FIN 報文，從而無法使得 CLOSE_WAIT 狀態的連接轉變為 LAST_ACK 狀態。

所以，當服務端出現大量 CLOSE_WAIT 狀態的連接的時候，說明服務端的程序沒有調用 close 函數關閉連接。

那什么情況會導致服務端的程序沒有調用 close 函數關閉連接？這時候通常需要排查代碼。

我們先來分析一個普通的 TCP 服務端的流程：

1. 創建服務端 socket，bind 綁定端口、listen 監聽端口
2. 將服務端 socket 注冊到 epoll
3. epoll_wait 等待連接到來，連接到來時，調用 accpet 獲取已連接的 socket
4. 將已連接的 socket 注冊到 epoll
5. epoll_wait 等待事件發生
6. 對方連接關閉時，我方調用 close

可能導致服務端沒有調用 close 函數的原因，如下。

第一個原因：第 2 步沒有做，沒有將服務端 socket 注冊到 epoll，這樣有新連接到來時，服務端沒辦法感知這個事件，也就無法獲取到已連接的 socket，那服務端自然就沒機會對 socket 調用 close 函數了。

不過這種原因發生的概率比較小，這種屬于明顯的代碼邏輯 bug，在前期 read view 階段就能發現的了。

第二個原因：第 3 步沒有做，有新連接到來時沒有調用 accpet 獲取該連接的 socket，導致當有大量的客戶端主動斷開了連接，而服務端沒機會對這些 socket 調用 close 函數，從而導致服務端出現大量 CLOSE_WAIT 狀態的連接。

發生這種情況可能是因為服務端在執行 accpet 函數之前，代碼卡在某一個邏輯或者提前拋出了異常。

第三個原因：第 4 步沒有做，通過 accpet 獲取已連接的 socket 后，沒有將其注冊到 epoll，導致后續收到 FIN 報文的時候，服務端沒辦法感知這個事件，那服務端就沒機會調用 close 函數了。

發生這種情況可能是因為服務端在將已連接的 socket 注冊到 epoll 之前，代碼卡在某一個邏輯或者提前拋出了異常。之前看到過別人解決 close_wait 問題的實踐文章，感興趣的可以看看：一次 Netty 代碼不健壯導致的大量 CLOSE_WAIT 連接原因分析

第四個原因：第 6 步沒有做，當發現客戶端關閉連接后，服務端沒有執行 close 函數，可能是因為代碼漏處理，或者是在執行 close 函數之前，代碼卡在某一個邏輯，比如發生死鎖等等。

可以發現，當服務端出現大量 CLOSE_WAIT 狀態的連接的時候，通常都是代碼的問題，這時候我們需要針對具體的代碼一步一步的進行排查和定位，主要分析的方向就是服務端為什么沒有調用 close。

TCP粘包問題怎么解決

• 答：特殊標記
• 追問：打斷，如果使用特殊標記解決會遇到什么問題
• 答：正文轉義字符

補充：

1、固定長度的消息

這種是最簡單方法，即每個用戶消息都是固定長度的，比如規定一個消息的長度是 64 個字節，當接收方接滿 64 個字節，就認為這個內容是一個完整且有效的消息。

但是這種方式靈活性不高，實際中很少用。

2、特殊字符作為邊界

我們可以在兩個用戶消息之間插入一個特殊的字符串，這樣接收方在接收數據時，讀到了這個特殊字符，就把認為已經讀完一個完整的消息。

HTTP 是一個非常好的例子。

HTTP 通過設置回車符、換行符作為 HTTP 報文協議的邊界。

有一點要注意，這個作為邊界點的特殊字符，如果剛好消息內容里有這個特殊字符，我們要對這個字符轉義，避免被接收方當作消息的邊界點而解析到無效的數據。

3、自定義消息結構

我們可以自定義一個消息結構，由包頭和數據組成，其中包頭包是固定大小的，而且包頭里有一個字段來說明緊隨其后的數據有多大。

比如這個消息結構體，首先 4 個字節大小的變量來表示數據長度，真正的數據則在后面。

struct { 
    u_int32_t message_length; 
    char message_data[]; 
} message;

當接收方接收到包頭的大小（比如 4 個字節）后，就解析包頭的內容，于是就可以知道數據的長度，然后接下來就繼續讀取數據，直到讀滿數據的長度，就可以組裝成一個完整到用戶消息來處理了。

protobuf了解嗎

答：不了解

補充：

Protobuf 是用于數據序列化和反序列化的格式，類似于 json。但它們有以下幾點區別：

• 數據大?。篜rotobuf是一種二進制格式，相對于JSON來說，數據大小更小，序列化和反序列化的效率更高，因此在網絡傳輸和存儲方面具有一定的優勢。
• 性能：由于Protobuf是二進制格式，相對于JSON來說，解析速度更快，占用的CPU和內存資源更少，因此在高并發場景下，性能更優。
• 可讀性：JSON是一種文本格式，可讀性更好，易于調試和排查問題。而Protobuf是一種二進制格式，可讀性較差。

Protobuf適用于高性能、大數據量、高并發等場景，而JSON適用于數據交換、易讀性要求高的場景。

說一下代碼里使用異步的思路

答：舉了個客戶端異步connect，使用select檢測結果的例子

順勢問select/epoll的區別

答：常規八股回答

補充：

select 和 poll 的缺陷在于，當客戶端越多，也就是 Socket 集合越大，Socket 集合的遍歷和拷貝會帶來很大的開銷，因此也很難應對 C10K。

epoll 是解決 C10K 問題的利器，通過兩個方面解決了 select/poll 的問題。

• epoll 在內核里使用「紅黑樹」來關注進程所有待檢測的 Socket，紅黑樹是個高效的數據結構，增刪改一般時間復雜度是 O(logn)，通過對這棵黑紅樹的管理，不需要像 select/poll 在每次操作時都傳入整個 Socket 集合，減少了內核和用戶空間大量的數據拷貝和內存分配。
• epoll 使用事件驅動的機制，內核里維護了一個「鏈表」來記錄就緒事件，只將有事件發生的 Socket 集合傳遞給應用程序，不需要像 select/poll 那樣輪詢掃描整個集合（包含有和無事件的 Socket ），大大提高了檢測的效率。

IO特別密集時epoll效率還高嗎

答：可以考慮select/poll，這種情況輪詢也很高效，且結構簡單。

補充：

可以先解釋io特別密集時為什么 epoll 效率不高。原因是：

• 連接密集（短連接特別多），使用epoll的話，每一次連接需要發生epoll_wait->accpet->epoll_ctl調用，而使用select只需要select->accpet，減少了一次系統調用。
• 讀寫密集的話，如果收到數據，我們需要響應數據的話，使用epoll的情況下， read 完后也需要epoll_ctl 加入寫事件，相比select多了一次系統調用

講一講ET模式

答：常規八股回答

補充：

epoll 支持兩種事件觸發模式，分別是邊緣觸發（edge-triggered，ET）和水平觸發（level-triggered，LT）。

這兩個術語還挺抽象的，其實它們的區別還是很好理解的。

• 使用邊緣觸發模式時，當被監控的 Socket 描述符上有可讀事件發生時，服務器端只會從 epoll_wait 中蘇醒一次，即使進程沒有調用 read 函數從內核讀取數據，也依然只蘇醒一次，因此我們程序要保證一次性將內核緩沖區的數據讀取完；
• 使用水平觸發模式時，當被監控的 Socket 上有可讀事件發生時，服務器端不斷地從 epoll_wait 中蘇醒，直到內核緩沖區數據被 read 函數讀完才結束，目的是告訴我們有數據需要讀?。?/li>

舉個例子，你的快遞被放到了一個快遞箱里，如果快遞箱只會通過短信通知你一次，即使你一直沒有去取，它也不會再發送第二條短信提醒你，這個方式就是邊緣觸發；如果快遞箱發現你的快遞沒有被取出，它就會不停地發短信通知你，直到你取出了快遞，它才消停，這個就是水平觸發的方式。

這就是兩者的區別，水平觸發的意思是只要滿足事件的條件，比如內核中有數據需要讀，就一直不斷地把這個事件傳遞給用戶；而邊緣觸發的意思是只有第一次滿足條件的時候才觸發，之后就不會再傳遞同樣的事件了。

如果使用水平觸發模式，當內核通知文件描述符可讀寫時，接下來還可以繼續去檢測它的狀態，看它是否依然可讀或可寫。所以在收到通知后，沒必要一次執行盡可能多的讀寫操作。

如果使用邊緣觸發模式，I/O 事件發生時只會通知一次，而且我們不知道到底能讀寫多少數據，所以在收到通知后應盡可能地讀寫數據，以免錯失讀寫的機會。因此，我們會循環從文件描述符讀寫數據，那么如果文件描述符是阻塞的，沒有數據可讀寫時，進程會阻塞在讀寫函數那里，程序就沒辦法繼續往下執行。所以，邊緣觸發模式一般和非阻塞 I/O 搭配使用，程序會一直執行 I/O 操作，直到系統調用（如 read 和 write）返回錯誤，錯誤類型為 EAGAIN 或 EWOULDBLOCK。

一般來說，邊緣觸發的效率比水平觸發的效率要高，因為邊緣觸發可以減少 epoll_wait 的系統調用次數，系統調用也是有一定的開銷的的，畢竟也存在上下文的切換。

對于一個后端服務怎么提升性能

• 回答：講了存儲層面的使用中間緩存、網絡框架設計優化
• 追問：提示長連接短連接
• 追問：怎么避免拷貝呢，不同的層面說說
• 回答：C++移動語義、零拷貝
• 追問：零拷貝的使用場景
• 追問：kafka了解嗎
• 回答：不了解
• 追問：建議關注一下kafka，很快很好用

算法

手撕：合并兩個有序鏈表

感受

基礎問題大部分還好，面試官最后評價還不錯。