Muduo 網絡程式設計示例之八：用 Timing wheel 踢掉空閑連接配接Timing wheel 原理代碼實作與改進

Muduo 網絡程式設計示例之八：Timing wheel 踢掉空閑連接配接

陳碩 (giantchen_AT_gmail)

這是《Muduo 網絡程式設計示例》系列的第八篇文章，原計劃講檔案傳輸，這裡插入一點計劃之外的内容。

本文介紹如何使用 timing wheel 來踢掉空閑的連接配接，一個連接配接如果若幹秒沒有收到資料，就認為是空閑連接配接。

在嚴肅的網絡程式中，應用層的心跳協定是必不可少的。應該用心跳消息來判斷對方程序是否能正常工作，“踢掉空閑連接配接”隻是一時權宜之計。我這裡想順便講講 shared_ptr 和 weak_ptr 的用法。

如果一個連接配接連續幾秒鐘（後文以 8s 為例）内沒有收到資料，就把它斷開，為此有兩種簡單粗暴的做法：

每個連接配接儲存“最後收到資料的時間 lastReceiveTime”，然後用一個定時器，每秒鐘周遊一遍所有連接配接，斷開那些 (now - connection.lastReceiveTime) > 8s 的 connection。這種做法全局隻有一個 repeated timer，不過每次 timeout 都要檢查全部連接配接，如果連接配接數目比較大（幾千上萬），這一步可能會比較費時。

每個連接配接設定一個 one-shot timer，逾時定為 8s，在逾時的時候就斷開本連接配接。當然，每次收到資料要去更新 timer。這種做法需要很多個 one-shot timer，會頻繁地更新 timers。如果連接配接數目比較大，可能對 reactor 的 timer queue 造成壓力。

使用 timing wheel 能避免上述兩種做法的缺點。timing wheel 可以翻譯為“時間輪盤”或“刻度盤”，本文保留英文。

連接配接逾時不需要精确定時，隻要大緻 8 秒鐘逾時斷開就行，多一秒少一秒關系不大。處理連接配接逾時可以用一個簡單的資料結構：8 個桶組成的循環隊列。第一個桶放下一秒将要逾時的連接配接，第二個放下 2 秒将要逾時的連接配接。每個連接配接一收到資料就把自己放到第 8 個桶，然後在每秒鐘的 callback 裡把第一個桶裡的連接配接斷開，把這個空桶挪到隊尾。這樣大緻可以做到 8 秒鐘沒有資料就逾時斷開連接配接。更重要的是，每次不用檢查全部的 connection，隻要檢查第一個桶裡的 connections，相當于把任務分散了。

《Hashed and hierarchical timing wheels: efficient data structures for implementing a timer facility》這篇論文詳細比較了實作定時器的各種資料結構，并提出了階層化的 timing wheel 與 hash timing wheel 等新結構。針對本文要解決的問題的特點，我們不需要實作一個通用的定時器，隻用實作 simple timing wheel 即可。

Simple timing wheel 的基本結構是一個循環隊列，還有一個指向隊尾的指針 (tail)，這個指針每秒鐘移動一格，就像鐘表上的時針，timing wheel 由此得名。

以下是某一時刻 timing wheel 的狀态，格子裡的數字是倒計時（與通常的 timing wheel 相反），表示這個格子（桶子）中的連接配接的剩餘壽命。

一秒鐘以後，tail 指針移動一格，原來四點鐘方向的格子被清空，其中的連接配接已被斷開。

假設在某個時刻，conn 1 到達，把它放到目前格子中，它的剩餘壽命是 7 秒。此後 conn 1 上沒有收到資料。

1 秒鐘之後，tail 指向下一個格子，conn 1 的剩餘壽命是 6 秒。

又過了幾秒鐘，tail 指向 conn 1 之前的那個格子，conn 1 即将被斷開。

下一秒，tail 重新指向 conn 1 原來所在的格子，清空其中的資料，斷開 conn 1 連接配接。

如果在斷開 conn 1 之前收到資料，就把它移到目前的格子裡。

收到資料，conn 1 的壽命延長為 7 秒。

時間繼續前進，conn 1 壽命遞減，不過它已經比第一種情況長壽了。

timing wheel 中的每個格子是個 hash set，可以容納不止一個連接配接。

比如一開始，conn 1 到達。

随後，conn 2 到達，這時候 tail 還沒有移動，兩個連接配接位于同一個格子中，具有相同的剩餘壽命。（下圖中畫成連結清單，代碼中是哈希表。）

幾秒鐘之後，conn 1 收到資料，而 conn 2 一直沒有收到資料，那麼 conn 1 被移到目前的格子中。這時 conn 1 的壽命比 conn 2 長。

在具體實作中，格子裡放的不是連接配接，而是一個特制的 Entry struct，每個 Entry 包含 TcpConnection 的 weak_ptr。Entry 的析構函數會判斷連接配接是否還存在（用 weak_ptr），如果還存在則斷開連接配接。

資料結構：

在實作中，為了簡單起見，我們不會真的把一個連接配接從一個格子移到另一個格子，而是采用引用計數的辦法，用 shared_ptr 來管理 Entry。如果從連接配接收到資料，就把對應的 EntryPtr 放到這個格子裡，這樣它的引用計數就遞增了。當 Entry 的引用計數遞減到零，說明它沒有在任何一個格子裡出現，那麼連接配接逾時，Entry 的析構函數會斷開連接配接。

Timing wheel 用 boost::circular_buffer 實作，其中每個 Bucket 元素是個 hash set of EntryPtr。

在構造函數中，注冊每秒鐘的回調（EventLoop::runEvery() 注冊 EchoServer::onTimer() ），然後把 timing wheel 設為适當的大小。

其中 EchoServer::onTimer() 的實作隻有一行：往隊尾添加一個空的 Bucket，這樣 circular_buffer 會自動彈出隊首的 Bucket，并析構之。在析構 Bucket 的時候，會依次析構其中的 EntryPtr 對象，這樣 Entry 的引用計數就不用我們去操心，C++ 的值語意會幫我們搞定一切。

在連接配接建立時，建立一個 Entry 對象，把它放到 timing wheel 的隊尾。另外，我們還需要把 Entry 的弱引用儲存到 TcpConnection 的 context 裡，因為在收到資料的時候還要用到 Entry。（思考題：如果 TcpConnection::setContext 儲存的是強引用 EntryPtr，會出現什麼情況？）

在收到消息時，從 TcpConnection 的 context 中取出 Entry 的弱引用，把它提升為強引用 EntryPtr，然後放到目前的 timing wheel 隊尾。（思考題，為什麼要把 Entry 作為 TcpConnection 的 context 儲存，如果這裡再建立一個新的 Entry 會有什麼後果？）

然後呢？沒有然後了，程式已經完成了我們想要的功能。（完整的代碼會列印 circular_buffer 變化的情況，運作一下即可了解。）

希望本文有助于您了解 shared_ptr 和 weak_ptr。

在現在的實作中，每次收到消息都會往隊尾添加 EntryPtr （當然，hash set 會幫我們去重。）一個簡單的改進措施是，在 TcpConnection 裡儲存“最後一次往隊尾添加引用時的 tail 位置”，然後先檢查 tail 是否變化，若無變化則不重複添加 EntryPtr。這樣或許能提高效率。

以上改進留作練習。

    本文轉自 陳碩  部落格園部落格，原文連結http://www.cnblogs.com/Solstice/archive/2011/05/04/2036983.html：，如需轉載請自行聯系原作者