計算機基礎知識對程序員來說有多重要？

大家好，我是小林。

之前有很多讀者問我學計算機基礎有啥用？不懂算法、計算機網絡、操作系統這些東西，也可以完成工作上的 CRUD 業務開發，那為什么要花時間去學？

是的，不懂這些，確實不會影響 CRUD 業務開發，對于這類業務開發的工作，難點是在于對業務的理解，但是門檻并不高，找個剛畢業人，讓他花幾個月時間熟悉業務和代碼，他一樣可以上手開發了，也就是說，單純的 CRUD 業開發工作很快就會被體力更好的新人取代的。

另外，在面對一些性能問題，如果沒有計算機基礎，我們是無從下手的，這時候程序員之間的分水嶺就出來了。

今天，我不講虛的東西。

我以如何設計一個「高性能的單機管理主機的心跳服務」的方式，讓大家感受計算基礎之美，這里會涉及到數據結構與算法 + 操作系統 + 計算機組成 + 計算機網絡這些知識。

這里貼一個目錄。

PS：這篇文章會比較長，大家耐心看下去，你會發現原來計算機基礎知識的用處，相信我，你會感觸很深刻，

案例需求

后臺通常是由多臺服務器對外提供服務的，也就是所謂的集群。

如果集群中的某一臺主機宕機了，我們必須要感知到這臺主機宕機了，這樣才做容災處理，比如該宕機的主機的業務遷移到另外一臺主機等等。

那如何感知呢？那就需要心跳服務了。

要求每臺主機都要向一臺主機上報心跳包，這樣我們就能在這臺主機上看到每臺主機的在線情況了。

心跳服務主要做兩件事情：

發現宕機的主機；

發現上線的主機。

看上去感覺很簡單，但是當集群達到十萬，甚至百萬臺的時候，要實現一個可以能管理這樣規模的集群的心跳服務進程，沒點底層知識是無法做到的。

接下來，將從三個維度來設計這個心跳服務：

宕機判斷算法的設計

高并發架構的設計

傳輸層協議的選擇

宕機判斷算法的設計

這個心跳服務最關鍵是判斷宕機的算法。

如果采用暴力遍歷所有主機的方式來找到超時的主機，在面對只有幾百臺主機的場景是沒問題，但是這個算法會隨著主機越多，算法復雜度也會上升，程序的性能也就會急劇下降。

所以，我們應該設計一個可以應對超大集群規模的宕機判斷算法。

我們先來思考下，心跳包應該有什么數據結構來管理？

心跳包里的內容是有主機上報的時間信息的，也就是有時間關系的，那么可以用「雙向鏈表」構成先入先出的隊列，這樣就保存了心跳包的時序關系。

由于采用的數據結構是雙向鏈表，所以隊尾插入和隊頭刪除操作的時間復雜度是 O(1)。

如果有新的心跳包，則將其插入到雙向鏈表的尾部，那么最老的心跳包就是在雙向鏈表的頭部，這樣在尋找宕機的主機時，只要看雙向鏈表頭部最老的心跳包，距現在是否超過 5 秒，如果超過 5秒 則認為該主機宕機，然后將其從雙向鏈表中刪除。

細心的同學肯定發現了個問題，就是如果一個主機的心跳包已經在隊列中，那么下次該主機的心跳包要怎么處理呢？

為了維持隊列里的心跳包是主機最新上報的，所以要先找到該主機舊的心跳包，然后將其刪除，再把新的心跳包插入到雙向鏈表的隊尾。

問題來了，在隊列找到該主機舊的心跳包，由于數據結構是雙向鏈表，所以這個查詢過程的時間復雜度時 O(N)，也就是說隨著隊列里的元素越多，會越影響程序的性能，這一點我們必須優化。

查詢效率最好的數據結構就是「哈希表」了，時間復雜度只有 O(1)，因此我們可以加入這個數據結構來優化。

哈希表的 Key 是主機的 IP 地址，Value 包含主機在雙向鏈表里的節點，這樣我們就可以通過哈希表輕松找到該主機在雙向鏈表中的位置。

這樣，每當收到心跳包時，先判斷其在不在哈希表里。

如果不存在哈希表里，說明是新主機上線，先將其插入到雙向鏈表的尾部，然后將該主機的 IP 作為 Key，主機在雙向鏈表的節點作為 Value 插入到哈希表。

如果存在哈希表里，說明主機已經上線過，先通過查詢哈希表，找到該主機在雙向鏈表里舊的心跳包的節點，然后就可以通過該節點將其從雙向鏈表中刪除，最后將新的心跳包插入到雙向鏈表的隊尾，同時更新哈希表。

可以看到，上面這些操作全都是 O(1)，不管集群規模多大，時間復雜度都不會增加，但是代價就是內存占用會越多，這個就是以空間換時間的方式。

有個細節的問題，不知道大家發現了沒有，就是為什么隊列的數據結構采用雙向鏈表，而不是單向鏈表？

因為雙向鏈表比單向鏈表多了個 pre 的指針，可以通過其找到上一個節點，那么在刪除中間節點的時候，就可以直接刪除，而如果是單向鏈表在刪除中間的時候，我們得先通過遍歷找到需被刪除節點的上一個節點，才能完成刪除操作，這里中間多了個遍歷操作。

既然引入哈希表，那我們在判斷出有主機宕機了（檢查雙向鏈表隊頭的主機是否超時），除了要將其從雙向鏈表中刪除，也要從哈希表中刪除。

要將主機從哈希表刪除，首先我們要知道主機的 IP，因為這是哈希表的 Key。

雙向鏈表存儲的內容必須包含主機的 IP 信息，那為了更快查詢到主機的 IP，雙向鏈表存儲的內容可以是一個鍵值對（Key-Value），其 Key 就是主機的 IP，Value 就是主機的信息。

這樣，在發現雙向鏈表中頭部的節點超時了，由于節點的內容是鍵值對，于是就能快速地從該節點獲取主機的 IP ，知道了主機的 IP 信息，就能把哈希表中該主機信息刪除。

至此，就設計出了一個高性能的宕機判斷算法，主要用了數據結構：哈希表 + 雙向鏈表，通過這個組合，查詢 + 刪除 + 插入操作的時間復雜度都是 O(1)，以空間換時間的思想，這就是數據結構與算法之美！

熟悉算法的同學應該感受出來了，上面這個算法就是類 LRU 算法，用于淘汰最近最久使用的元素的場景，該算法應用范圍很廣的，操作系統、Redis、MySQL 都有使用該算法。

在很多大廠面試的時候，經常會考察 LRU 算法，甚至會要求手寫出來，后面我在寫一篇 LRU 算法實現的文章。

高并發架構的設計

設計完高效的宕機判斷算法后，我們來設計個能充分利用服務器資源的架構，以應對高并發的場景。

首先第一個問題，選用單線程還是多線程模式？

選用單線程的話，意味著程序只能利用一個 CPU 的算力，如果 CPU 是一顆 1GHZ 主頻的 CPU，意味著一秒鐘只有 10 億個時鐘周期可以工作，如果要讓心跳服務程序每秒接收到 100 萬心跳包，那么就要求它必須在 1000 個時時鐘周期內處理完一個心跳包。

這是無法做到的，因為一個匯編指令的執行需要多個時鐘周期，更何況高級語言的一條語句是由多個匯編指令構成的，而且這個 1000 個時鐘周期還要包含內核從網卡上讀取報文，以及協議棧的報文分析。

因此，采用單線程模式會出現算力不足的情況，意味著在百萬級的心跳場景下，容易出現內核緩沖區的數據無法被即使取出而導致溢出的現象，然后就會出現大量的丟包。

所以，我們要選擇多進程或者多線程的模式，來充分利用多核的 CPU 資源。多進程的優勢是進程間互不干擾，但是內存不共享，進程間通信比較麻煩，因此采用多線程模式開發會更好一些，多線程間可以共享數據。

多線程體現在「分發線程是多線程和工作線程是多線程」，決定了多線程開發模式后，我們還需要解決五個問題。

我們應該使用多路復用技術來服務多個客戶端，而且是要使用 epoll。

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

而 epoll 的方式即使監聽的 Socket 數量越多的時候，效率不會大幅度降低，能夠同時監聽的 Socket 的數目也非常的多了。

多路復用更詳細的介紹，可以看之前這篇文章：這次答應我，一舉拿下 I/O 多路復用！

在收到心跳包后，我們應該要將心跳包均勻分發到不同的工作線程上處理。

分發的規則可以用哈希函數，這樣在接收到心跳包后，解析出主機的 IP 地址，然后通過哈希函數分發給工作線程處理。

于是每個工作線程只會處理特定主機的心跳包，多個工作線程間互不干擾，不用在多個工作線程間加鎖，從而實現了無鎖編程。

分發線程和工作線程之間可以加個消息隊列，形成「生產者 - 消費者」模型。

分發線程負責將接收到的心跳包加入到隊列里，工作線程負責從隊列取出心跳包做進一步的處理。

除此之外，還需要做如下兩點。

第一點，工作線程一般是多于分發線程，給每一個工作線程都創建獨立的緩沖隊列。

第二點，緩沖隊列是會被分發線程和工作線程同時操作，所以在操作該隊列要加鎖，為了避免線程獲取鎖失而主動放棄 CPU，可以選擇自旋鎖，因為自旋鎖在獲取鎖失敗后，CPU 還在執行該線程，只不過 CPU 在空轉，效率比互斥鎖高。

更多關于鎖的講解可以看這篇：「互斥鎖、自旋鎖、讀寫鎖、悲觀鎖、樂觀鎖的應用場景」

現代 CPU 都是多核心的，線程可能在不同 CPU 核心來回切換執行，這對 CPU Cache 不是有利的，雖然 L3 Cache 是多核心之間共享的，但是 L1 和 L2 Cache 都是每個核心獨有的。

如果一個線程在不同核心來回切換，各個核心的緩存命中率就會受到影響，相反如果線程都在同一個核心上執行，那么其數據的 L1 和 L2 Cache 的緩存命中率可以得到有效提高，緩存命中率高就意味著 CPU 可以減少訪問 內存的頻率。

當有多個同時執行「計算密集型」的線程，為了防止因為切換到不同的核心，而導致緩存命中率下降的問題，我們可以把線程綁定在某一個 CPU 核心上，這樣性能可以得到非常可觀的提升。

在 Linux 上提供了 sched_setaffinity 方法，來實現將線程綁定到某個 CPU 核心這一功能。

更多關于 CPU Cache 的介紹，可以看這篇：「如何寫出讓 CPU 跑得更快的代碼？」

Linux 默認的內存分配器是 PtMalloc2，它有一個缺點在申請小內存和多線程的情況下，申請內存的效率并不高。

后來，Google 開發的 TCMalloc 內存分配器就解決這個問題，它在多線程下分配小內存的速度要快很多，所以對于心跳服務應當改用 TCMalloc 申請內存。

我暫時就想到這么多了，這里每一個點都跟「計算機組成和操作系統」知識密切相關。

傳輸層協議的選擇

心跳包的傳輸層協議應該是選 TCP 和 UDP 呢？

對于傳輸層協議的選擇，我們要看心跳包的長度大小。

如果長度小于 MTU，那么可以選擇 UDP 協議，因為 UDP 協議沒那么復雜，而且心跳包也不是一定要完全可靠傳輸，如果中途發生丟包，下一次心跳包能收到就行。

如果長度大于 MTU，就要選擇 TCP 了，因為 UDP 在傳送大于 1500 字節的報文，IP 協議就會把報文拆包后再發到網絡中，并在接收方組裝回原來的報文，然而，IP 協議并不擅長做這件事，拆包組包的效率很低。

所以，TCP 協議就選擇自己做拆包組包的事情，當心跳包的長度大于 MSS 時就會在 TCP 層拆包，且保證 TCP 層拆包的報文長度不會 MTU。

選擇了 TCP 協議后，我們還要解決一些事情，因為 TCP 協議是復雜的。

首先，要讓服務器能支持更多的 TCP 連接，TCP 連接是通過四元組唯一確認的，也就是**「 源 IP、目的 IP、源端口、目的端口 」**。

那么當服務器 IP 地址（目的 IP）和監聽端口（目標端口）固定時，變化的只有源 IP（2^32） 和源端口（2^16），因此理論上服務器最大能連接 2^(32+16) 個客戶端。

這只是理論值，實際上服務器的資源肯定達不到那么多連接。Linux 系統一切皆文件，所以 TCP 連接也是文件，那么服務器要增大下面這兩個地方的最大文件句柄數：

通過 ulimit 命令增大單進程允許最大文件句柄數；

通過 /proc/sys/fs/file-nr 增大系統允許最大文件句柄數。

另外， TCP 協議的默認內核參數并不適應高并發的場景，所以我們還得在下面這四個方向通過調整內核參數來優化 TCP 協議：

三次握手過程需要優化；

四次揮手過程需要優化：

TCP 緩沖區要根據網絡帶寬時延積設置；

擁塞控制算法需要優化；

前三個的優化的思路，我在之前的文章寫過，詳見：「面試官：換人！他連 TCP 這幾個參數都不懂」

這里簡單說一下優化擁塞控制算法的思路。

傳統的擁塞控制分為四個部分：慢啟動、擁塞避免、快速重傳、快速恢復，如下圖：

當 TCP 連接建立成功后，擁塞控制算法就會發生作用，首先進入慢啟動階段。決定連接此時網速的是初始擁塞窗口，默認值是 10 MSS。

在帶寬時延積較大的網絡中，應當調高初始擁塞窗口，比如 20 MSS 或 30 MSS，Linux 上可以通過 route ip change 命令修改它。

傳統的擁塞控制算法是基于丟包作為判斷擁塞的依據。不過實際上，網絡剛出現擁塞時并不會丟包，而真的出現丟包時，擁塞已經非常嚴重了，比如像理由器里都有緩沖隊列應對突發流量：

上圖中三種情況：

當緩沖隊列為空時，傳輸速度最快；

當緩沖隊列開始有報文擠壓，那么網速就開始變慢了，也就是網絡延時變高了；

當緩沖隊列溢出時，就出現了丟包現象。

傳統的擁塞控制算法就是在第三步這個時間點進入擁塞避免階段，顯然已經很晚了。

其實進行擁塞控制的最佳時間點，是緩沖隊列剛出現積壓的時刻，也就是第二步。

Google 推出的 BBR 算法是以測量帶寬、時延來確定擁塞的擁塞控制算法，能提高網絡環境的質量，減少網絡延遲和降低丟包率。

Linux 4.9 版本之后都支持 BBR 算法，開啟 BBR 算法的方式：

net.ipv4.tcp_congestion_control=bbr

這里的每一個知識都涉及到了計算機網絡，這就是計算機網絡之美！

總結

掌握好數據結構與算法，才能設計出高效的宕機判斷算法，本文我們采用哈希表 + 雙向鏈表實現了類 LRU 算法。

掌握好計算組成 + 操作系統，才能設計出高性能的架構，本文我們采用多線程模式來充分利用 CPU 資源，還需要考慮 IO 多路服用的選擇，鎖的選擇，消息隊列的引入，內存分配器的選擇等等。

掌握好計算機網絡，才能選擇契合場景的傳輸協議，如果心跳包長度大于 MTU，那么選擇 TCP 更有利，但是 TCP 是個復雜的協議，在高并發的場景下，還需要對 TCP 的每一個階段需要優化。如果如果心跳包長度小于 MTU，且不要求可靠傳輸時，UDP 協議是更好的選擇。

怎么樣？

是不是感動到了計算機基礎之美。

任務調度 開發者

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。