大家好，我是小林。
昨天有位關注我一年的讀者找我，他去年關注我後，開始自學 CS，主要是計算機基礎這一塊。
他從那時起，就日復一日的學習，並在 Github 有做筆記的習慣，你看他的提交記錄，每天都有，一天都沒拉下，就這樣堅持了一年。
這個一年沒有間斷過的堅持，我是真的被震撼到，雖然我也經常肝文章，但是我也做不到每天都是學習的狀態，總會想偷懶幾天，畢竟學習真的是反人性的哈哈。
這裡先給大家分享些計算機必讀書籍，獲取方式：計算機必讀書籍（含下載方式），包含資料結構與演算法、作業系統、計算機網路、資料庫、Linux 這些。
這位讀者去年的時候，也只是會用 python 輸出 hello world 初學者，而如今能開始啃 Redis 原始碼了，並且還記錄了學習 Redis 資料結構的原始碼筆記。
我也跟他討論了我學計算基礎的感受，他也有相同的感受，看來是同道中人。
之前有很多讀者問我學計算機基礎有啥用？不懂演算法、計算機網路、作業系統這些東西，也可以完成工作上的 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 核心來回切換執行，這對 CPU Cache 不是有利的，雖然 L3 Cache 是多核心之間共享的，但是 L1 和 L2 Cache 都是每個核心獨有的。
如果一個執行緒在不同核心來回切換，各個核心的快取命中率就會受到影響，相反如果執行緒都在同一個核心上執行，那麼其資料的 L1 和 L2 Cache 的快取命中率可以得到有效提高，快取命中率高就意味著 CPU 可以減少訪問 記憶體的頻率。
當有多個同時執行「計算密集型」的執行緒，為了防止因為切換到不同的核心，而導致快取命中率下降的問題，我們可以把執行緒繫結在某一個 CPU 核心上，這樣效能可以得到非常可觀的提升。
在 Linux 上提供了 sched_setaffinity 方法，來實現將執行緒繫結到某個 CPU 核心這一功能。
更多關於 CPU Cache 的介紹，可以看這篇：「如何寫出讓 CPU 跑得更快的程式碼？」
第五個記憶體分配器
Linux 預設的記憶體分配器是 PtMalloc2，它有一個缺點在申請小記憶體和多執行緒的情況下，申請記憶體的效率並不高。
後來，Google 開發的 TCMalloc 記憶體分配器就解決這個問題，它在多執行緒下分配小記憶體的速度要快很多，所以對於心跳服務應當改用 TCMalloc 申請記憶體。
下圖是 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
1
這裡的每一個知識都涉及到了計算機網路，這就是計算機網路之美！
總結
掌握好資料結構與演算法，才能設計出高效的宕機判斷演算法，本文我們採用雜湊表 + 雙向連結串列實現了類 LRU 演算法。
掌握好計算組成 + 作業系統，才能設計出高效能的架構，本文我們採用多執行緒模式來充分利用 CPU 資源，還需要考慮 IO 多路服用的選擇，鎖的選擇，訊息佇列的引入，記憶體分配器的選擇等等。
掌握好計算機網路，才能選擇契合場景的傳輸協議，如果心跳包長度大於 MTU，那麼選擇 TCP 更有利，但是 TCP 是個複雜的協議，在高併發的場景下，還需要對 TCP 的每一個階段需要最佳化。如果如果心跳包長度小於 MTU，且不要求可靠傳輸時，UDP 協議是更好的選擇。
怎麼樣？
是不是感動到了計算機基礎之美。
————————————————
智慧校園數字化校園全國招商加盟代理155 5541 3633
