陳碩 (giantchen_AT_gmail)
Blog.csdn.net/Solstice t.sina.com.cn/giantchen
Muduo 全系列文章列表： http://blog.csdn.net/Solstice/category/779646.aspx
本文介紹 Muduo 中輸入輸出緩沖區的設計與實現。
本文中 buffer 指一般的應用層緩沖區、緩沖技術，Buffer 特指 muduo::net::Buffer class。
本文前兩節的內容已事先發表在 muduo 英文博客 http://muduo.chenshuo.com/2011/04/essentials-of-non-blocking-tcp-network.html 。
Muduo 的 IO 模型
UNPv1 第 6.2 節總結了 Unix/Linux 上的五種 IO 模型：阻塞(blocking)、非阻塞(non-blocking)、IO 復用(IO multiplexing)、信號驅動(signal-driven)、異步(asynchronous)。這些都是單線程下的 IO 模型。
C10k 問題的頁面介紹了五種 IO 策略，把線程也納入考量。（現在 C10k 已經不是什么問題，C100k 也不是大問題，C1000k 才算得上挑戰）。
在這個多核時代，線程是不可避免的。那么服務端網絡編程該如何選擇線程模型呢？我贊同 libev 作者的觀點：one loop per thread is usually a good model。之前我也不止一次表述過這個觀點，見《多線程服務器的常用編程模型》《多線程服務器的適用場合》。
如果采用 one loop per thread 的模型，多線程服務端編程的問題就簡化為如何設計一個高效且易于使用的 event loop，然后每個線程 run 一個 event loop 就行了（當然、同步和互斥是不可或缺的）。在“高效”這方面已經有了很多成熟的范例（libev、libevent、memcached、varnish、lighttpd、nginx），在“易于使用”方面我希望 muduo 能有所作為。（muduo 可算是用現代 C++ 實現了 Reactor 模式，比起原始的 Reactor 來說要好用得多。）
event loop 是 non-blocking 網絡編程的核心，在現實生活中，non-blocking 幾乎總是和 IO-multiplexing 一起使用，原因有兩點：
- 沒有人真的會用輪詢 (busy-pooling) 來檢查某個 non-blocking IO 操作是否完成，這樣太浪費 CPU cycles。
- IO-multiplex 一般不能和 blocking IO 用在一起，因為 blocking IO 中 read()/write()/accept()/connect() 都有可能阻塞當前線程，這樣線程就沒辦法處理其他 socket 上的 IO 事件了。見 UNPv1 第 16.6 節“nonblocking accept”的例子。
所以，當我提到 non-blocking 的時候，實際上指的是 non-blocking + IO-muleiplexing，單用其中任何一個是不現實的。另外，本文所有的“連接”均指 TCP 連接，socket 和 connection 在文中可互換使用。
當然，non-blocking 編程比 blocking 難得多，見陳碩在《Muduo 網絡編程示例之零：前言》中“TCP 網絡編程本質論”一節列舉的難點。基于 event loop 的網絡編程跟直接用 C/C++ 編寫單線程 Windows 程序頗為相像：程序不能阻塞，否則窗口就失去響應了；在 event handler 中，程序要盡快交出控制權，返回窗口的事件循環。
為什么 non-blocking 網絡編程中應用層 buffer 是必須的？
Non-blocking IO 的核心思想是避免阻塞在 read() 或 write() 或其他 IO 系統調用上，這樣可以最大限度地復用 thread-of-control，讓一個線程能服務于多個 socket 連接。IO 線程只能阻塞在 IO-multiplexing 函數上，如 select()/poll()/epoll_wait()。這樣一來，應用層的緩沖是必須的，每個 TCP socket 都要有 stateful 的 input buffer 和 output buffer。
TcpConnection 必須要有 output buffer
考慮一個常見場景：程序想通過 TCP 連接發送 100k 字節的數據，但是在 write() 調用中，操作系統只接受了 80k 字節（受 TCP advertised window 的控制，細節見 TCPv1），你肯定不想在原地等待，因為不知道會等多久（取決于對方什么時候接受數據，然后滑動 TCP 窗口）。程序應該盡快交出控制權，返回 event loop。在這種情況下，剩余的 20k 字節數據怎么辦？
對于應用程序而言，它只管生成數據，它不應該關心到底數據是一次性發送還是分成幾次發送，這些應該由網絡庫來操心，程序只要調用 TcpConnection::send() 就行了，網絡庫會負責到底。網絡庫應該接管這剩余的 20k 字節數據，把它保存在該 TCP connection 的 output buffer 里，然后注冊 POLLOUT 事件，一旦 socket 變得可寫就立刻發送數據。當然，這第二次 write() 也不一定能完全寫入 20k 字節，如果還有剩余，網絡庫應該繼續關注 POLLOUT 事件；如果寫完了 20k 字節，網絡庫應該停止關注 POLLOUT，以免造成 busy loop。（Muduo EventLoop 采用的是 epoll level trigger，這么做的具體原因我以后再說。）
如果程序又寫入了 50k 字節，而這時候 output buffer 里還有待發送的 20k 數據，那么網絡庫不應該直接調用 write()，而應該把這 50k 數據 append 在那 20k 數據之后，等 socket 變得可寫的時候再一并寫入。
如果 output buffer 里還有待發送的數據，而程序又想關閉連接（對程序而言，調用 TcpConnection::send() 之后他就認為數據遲早會發出去），那么這時候網絡庫不能立刻關閉連接，而要等數據發送完畢，見我在《為什么 muduo 的 shutdown() 沒有直接關閉 TCP 連接？》一文中的講解。
綜上，要讓程序在 write 操作上不阻塞，網絡庫必須要給每個 tcp connection 配置 output buffer。
TcpConnection 必須要有 input buffer
TCP 是一個無邊界的字節流協議，接收方必須要處理“收到的數據尚不構成一條完整的消息”和“一次收到兩條消息的數據”等等情況。一個常見的場景是，發送方 send 了兩條 10k 字節的消息（共 20k），接收方收到數據的情況可能是：
- 一次性收到 20k 數據
- 分兩次收到，第一次 5k，第二次 15k
- 分兩次收到，第一次 15k，第二次 5k
- 分兩次收到，第一次 10k，第二次 10k
- 分三次收到，第一次 6k，第二次 8k，第三次 6k
- 其他任何可能
網絡庫在處理“socket 可讀”事件的時候，必須一次性把 socket 里的數據讀完（從操作系統 buffer 搬到應用層 buffer），否則會反復觸發 POLLIN 事件，造成 busy-loop。（Again, Muduo EventLoop 采用的是 epoll level trigger，這么做的具體原因我以后再說。）
那么網絡庫必然要應對“數據不完整”的情況，收到的數據先放到 input buffer 里，等構成一條完整的消息再通知程序的業務邏輯。這通常是 codec 的職責，見陳碩《Muduo 網絡編程示例之二：Boost.Asio 的聊天服務器》一文中的“TCP 分包”的論述與代碼。
所以，在 tcp 網絡編程中，網絡庫必須要給每個 tcp connection 配置 input buffer。
所有 muduo 中的 IO 都是帶緩沖的 IO (buffered IO)，你不會自己去 read() 或 write() 某個 socket，只會操作 TcpConnection 的 input buffer 和 output buffer。更確切的說，是在 onMessage() 回調里讀取 input buffer；調用 TcpConnection::send() 來間接操作 output buffer，一般不會直接操作 output buffer。
btw, muduo 的 onMessage() 的原型如下，它既可以是 free function，也可以是 member function，反正 muduo TcpConnection 只認 boost::function<>。
void onMessage(const TcpConnectionPtr& conn, Buffer* buf, Timestamp receiveTime);
對于網絡程序來說，一個簡單的驗收測試是：輸入數據每次收到一個字節（200 字節的輸入數據會分 200 次收到，每次間隔 10 ms），程序的功能不受影響。對于 Muduo 程序，通?？梢杂?codec 來分離“消息接收”與“消息處理”，見陳碩《在 muduo 中實現 protobuf 編解碼器與消息分發器》一文中對“編解碼器 codec”的介紹。
如果某個網絡庫只提供相當于 char buf[8192] 的緩沖，或者根本不提供緩沖區，而僅僅通知程序“某 socket 可讀/某 socket 可寫”，要程序自己操心 IO buffering，這樣的網絡庫用起來就很不方便了。（我有所指，你懂得。）
Buffer 的要求
http://code.google.com/p/muduo/source/browse/trunk/muduo/net/Buffer.h
Muduo Buffer 的設計考慮了常見的網絡編程需求，我試圖在易用性和性能之間找一個平衡點，目前這個平衡點更偏向于易用性。
Muduo Buffer 的設計要點：
- 對外表現為一塊連續的內存(char*, len)，以方便客戶代碼的編寫。
- 其 size() 可以自動增長，以適應不同大小的消息。它不是一個 fixed size array (即 char buf[8192])。
- 內部以 vector of char 來保存數據，并提供相應的訪問函數。
Buffer 其實像是一個 queue，從末尾寫入數據，從頭部讀出數據。
誰會用 Buffer？誰寫誰讀？根據前文分析，TcpConnection 會有兩個 Buffer 成員，input buffer 與 output buffer。
- input buffer，TcpConnection 會從 socket 讀取數據，然后寫入 input buffer（其實這一步是用 Buffer::readFd() 完成的）；客戶代碼從 input buffer 讀取數據。
- output buffer，客戶代碼會把數據寫入 output buffer（其實這一步是用 TcpConnection::send() 完成的）；TcpConnection 從 output buffer 讀取數據并寫入 socket。
其實，input 和 output 是針對客戶代碼而言，客戶代碼從 input 讀，往 output 寫。TcpConnection 的讀寫正好相反。
以下是 muduo::net::Buffer 的類圖。請注意，為了后面畫圖方便，這個類圖跟實際代碼略有出入，但不影響我要表達的觀點。
這里不介紹每個成員函數的作用，留給《Muduo 網絡編程示例》系列。下文會仔細介紹 readIndex 和 writeIndex 的作用。
Buffer::readFd()
我在《Muduo 網絡編程示例之零：前言》中寫道
- 在非阻塞網絡編程中，如何設計并使用緩沖區？一方面我們希望減少系統調用，一次讀的數據越多越劃算，那么似乎應該準備一個大的緩沖區。另一方面，我們系統減少內存占用。如果有 10k 個連接，每個連接一建立就分配 64k 的讀緩沖的話，將占用 640M 內存，而大多數時候這些緩沖區的使用率很低。muduo 用 readv 結合棧上空間巧妙地解決了這個問題。
具體做法是，在棧上準備一個 65536 字節的 stackbuf，然后利用 readv() 來讀取數據，iovec 有兩塊，第一塊指向 muduo Buffer 中的 writable 字節，另一塊指向棧上的 stackbuf。這樣如果讀入的數據不多，那么全部都讀到 Buffer 中去了；如果長度超過 Buffer 的 writable 字節數，就會讀到棧上的 stackbuf 里，然后程序再把 stackbuf 里的數據 append 到 Buffer 中。
代碼見 http://code.google.com/p/muduo/source/browse/trunk/muduo/net/Buffer.cc#36
這么做利用了臨時棧上空間，避免開巨大 Buffer 造成的內存浪費，也避免反復調用 read() 的系統開銷（通常一次 readv() 系統調用就能讀完全部數據）。
這算是一個小小的創新吧。
線程安全？
muduo::net::Buffer 不是線程安全的，這么做是有意的，原因如下：
- 對于 input buffer，onMessage() 回調始終發生在該 TcpConnection 所屬的那個 IO 線程，應用程序應該在 onMessage() 完成對 input buffer 的操作，并且不要把 input buffer 暴露給其他線程。這樣所有對 input buffer 的操作都在同一個線程，Buffer class 不必是線程安全的。
- 對于 output buffer，應用程序不會直接操作它，而是調用 TcpConnection::send() 來發送數據，后者是線程安全的。
如果 TcpConnection::send() 調用發生在該 TcpConnection 所屬的那個 IO 線程，那么它會轉而調用 TcpConnection::sendInLoop()，sendInLoop() 會在當前線程（也就是 IO 線程）操作 output buffer；如果 TcpConnection::send() 調用發生在別的線程，它不會在當前線程調用 sendInLoop() ，而是通過 EventLoop::runInLoop() 把 sendInLoop() 函數調用轉移到 IO 線程（聽上去頗為神奇？），這樣 sendInLoop() 還是會在 IO 線程操作 output buffer，不會有線程安全問題。當然，跨線程的函數轉移調用涉及函數參數的跨線程傳遞，一種簡單的做法是把數據拷一份，絕對安全（不明白的同學請閱讀代碼）。
另一種更為高效做法是用 swap()。這就是為什么 TcpConnection::send() 的某個重載以 Buffer* 為參數，而不是 const Buffer&，這樣可以避免拷貝，而用 Buffer::swap() 實現高效的線程間數據轉移。（最后這點，僅為設想，暫未實現。目前仍然以數據拷貝方式在線程間傳遞，略微有些性能損失。）
Muduo Buffer 的數據結構
Buffer 的內部是一個 vector of char，它是一塊連續的內存。此外，Buffer 有兩個 data members，指向該 vector 中的元素。這兩個 indices 的類型是 int，不是 char*，目的是應對迭代器失效。muduo Buffer 的設計參考了 Netty 的 ChannelBuffer 和 libevent 1.4.x 的 evbuffer。不過，其 prependable 可算是一點“微創新”。
Muduo Buffer 的數據結構如下：
圖 1
兩個 indices 把 vector 的內容分為三塊：prependable、readable、writable，各塊的大小是（公式一）：
prependable = readIndex
readable = writeIndex - readIndex
writable = size() - writeIndex
（prependable 的作用留到后面討論。）
readIndex 和 writeIndex 滿足以下不變式(invariant):
0 ≤ readIndex ≤ writeIndex ≤ data.size()
Muduo Buffer 里有兩個常數 kCheapPrepend 和 kInitialSize，定義了 prependable 的初始大小和 writable 的初始大小。（readable 的初始大小為 0。）在初始化之后，Buffer 的數據結構如下：括號里的數字是該變量或常量的值。
圖 2
根據以上（公式一）可算出各塊的大小，剛剛初始化的 Buffer 里沒有 payload 數據，所以 readable == 0。
Muduo Buffer 的操作
1. 基本的 read-write cycle
Buffer 初始化后的情況見圖 1，如果有人向 Buffer 寫入了 200 字節，那么其布局是：
圖 3
圖 3 中 writeIndex 向后移動了 200 字節，readIndex 保持不變，readable 和 writable 的值也有變化。
如果有人從 Buffer read() & retrieve() （下稱“讀入”）了 50 字節，結果見圖 4。與上圖相比，readIndex 向后移動 50 字節，writeIndex 保持不變，readable 和 writable 的值也有變化（這句話往后從略）。
圖 4
然后又寫入了 200 字節，writeIndex 向后移動了 200 字節，readIndex 保持不變，見圖 5。
圖 5
接下來，一次性讀入 350 字節，請注意，由于全部數據讀完了，readIndex 和 writeIndex 返回原位以備新一輪使用，見圖 6，這和圖 2 是一樣的。
圖 6
以上過程可以看作是發送方發送了兩條消息，長度分別為 50 字節和 350 字節，接收方分兩次收到數據，每次 200 字節，然后進行分包，再分兩次回調客戶代碼。
自動增長
Muduo Buffer 不是固定長度的，它可以自動增長，這是使用 vector 的直接好處。
假設當前的狀態如圖 7 所示。（這和前面圖 5 是一樣的。）
圖 7
客戶代碼一次性寫入 1000 字節，而當前可寫的字節數只有 624，那么 buffer 會自動增長以容納全部數據，得到的結果是圖 8。注意 readIndex 返回到了前面，以保持 prependable 等于 kCheapPrependable。由于 vector 重新分配了內存，原來指向它元素的指針會失效，這就是為什么 readIndex 和 writeIndex 是整數下標而不是指針。
圖 8
然后讀入 350 字節，readIndex 前移，見圖 9。
圖 9
最后，讀完剩下的 1000 字節，readIndex 和 writeIndex 返回 kCheapPrependable，見圖 10。
圖 10
注意 buffer 并沒有縮小大小，下次寫入 1350 字節就不會重新分配內存了。換句話說，Muduo Buffer 的 size() 是自適應的，它一開始的初始值是 1k，如果程序里邊經常收發 10k 的數據，那么用幾次之后它的 size() 會自動增長到 10k，然后就保持不變。這樣一方面避免浪費內存（有的程序可能只需要 4k 的緩沖），另一方面避免反復分配內存。當然，客戶代碼可以手動 shrink() buffer size()。
size() 與 capacity()
使用 vector 的另一個好處是它的 capcity() 機制減少了內存分配的次數。比方說程序反復寫入 1 字節，muduo Buffer 不會每次都分配內存，vector 的 capacity() 以指數方式增長，讓 push_back() 的平均復雜度是常數。比方說經過第一次增長，size() 剛好滿足寫入的需求，如圖 11。但這個時候 vector 的 capacity() 已經大于 size()，在接下來寫入 capacity()-size() 字節的數據時，都不會重新分配內存，見圖 12。
圖 11
圖 12
細心的讀者可能會發現用 capacity() 也不是完美的，它有優化的余地。具體來說，vector::resize() 會初始化(memset/bzero)內存，而我們不需要它初始化，因為反正立刻就要填入數據。比如，在圖 12 的基礎上寫入 200 字節，由于 capacity() 足夠大，不會重新分配內存，這是好事；但是 vector::resize() 會先把那 200 字節設為 0 （圖 13），然后 muduo buffer 再填入數據（圖 14）。這么做稍微有點浪費，不過我不打算優化它，除非它確實造成了性能瓶頸。（精通 STL 的讀者可能會說用 vector::append() 以避免浪費，但是 writeIndex 和 size() 不一定是對齊的，會有別的麻煩。）
圖 13
圖 14
google protobuf 中有一個 STLStringResizeUninitialized 函數，干的就是這個事情。
內部騰挪
有時候，經過若干次讀寫，readIndex 移到了比較靠后的位置，留下了巨大的 prependable 空間，見圖 14。
圖 14
這時候，如果我們想寫入 300 字節，而 writable 只有 200 字節，怎么辦？muduo Buffer 在這種情況下不會重新分配內存，而是先把已有的數據移到前面去，騰出 writable 空間，見圖 15。
圖 15
然后，就可以寫入 300 字節了，見圖 16。
圖 16
這么做的原因是，如果重新分配內存，反正也是要把數據拷到新分配的內存區域，代價只會更大。
prepend
前面說 muduo Buffer 有個小小的創新（或許不是創新，我記得在哪兒看到過類似的做法，忘了出處），即提供 prependable 空間，讓程序能以很低的代價在數據前面添加幾個字節。
比方說，程序以固定的4個字節表示消息的長度（即《Muduo 網絡編程示例之二：Boost.Asio 的聊天服務器》中的 LengthHeaderCodec），我要序列化一個消息，但是不知道它有多長，那么我可以一直 append() 直到序列化完成（圖 17，寫入了 200 字節），然后再在序列化數據的前面添加消息的長度（圖 18，把 200 這個數 prepend 到首部）。
圖 17
圖 18
通過預留 kCheapPrependable 空間，可以簡化客戶代碼，一個簡單的空間換時間思路。
其他設計方案
這里簡單談談其他可能的應用層 buffer 設計方案。
不用 vector<char>？
如果有 STL 潔癖，那么可以自己管理內存，以 4 個指針為 buffer 的成員，數據結構見圖 19。
圖 19
說實話我不覺得這種方案比 vector 好。代碼變復雜，性能也未見得有 noticeable 的改觀。
如果放棄“連續性”要求，可以用 circular buffer，這樣可以減少一點內存拷貝（沒有“內部騰挪”）。
Zero copy ?
如果對性能有極高的要求，受不了 copy() 與 resize()，那么可以考慮實現分段連續的 zero copy buffer 再配合 gather scatter IO，數據結構如圖 20，這是 libevent 2.0.x 的設計方案。TCPv2介紹的 BSD TCP/IP 實現中的 mbuf 也是類似的方案，Linux 的 sk_buff 估計也差不多。細節有出入，但基本思路都是不要求數據在內存中連續，而是用鏈表把數據塊鏈接到一起。
圖 20
當然，高性能的代價是代碼變得晦澀難讀，buffer 不再是連續的，parse 消息會稍微麻煩。如果你的程序只處理 protobuf Message，這不是問題，因為 protobuf 有 ZeroCopyInputStream 接口，只要實現這個接口，parsing 的事情就交給 protobuf Message 去操心了。
性能是不是問題？看跟誰比
看到這里，有的讀者可能會嘀咕，muduo Buffer 有那么多可以優化的地方，其性能會不會太低？對此，我的回應是“可以優化，不一定值得優化。”
Muduo 的設計目標是用于開發公司內部的分布式程序。換句話說，它是用來寫專用的 Sudoku server 或者游戲服務器，不是用來寫通用的 httpd 或 ftpd 或 www proxy。前者通常有業務邏輯，后者更強調高并發與高吞吐。
以 Sudoku 為例，假設求解一個 Sudoku 問題需要 0.2ms，服務器有 8 個核，那么理想情況下每秒最多能求解 40,000 個問題。每次 Sudoku 請求的數據大小低于 100 字節（一個 9x9 的數獨只要 81 字節，加上 header 也可以控制在 100 bytes 以下），就是說 100 x 40000 = 4 MB per second 的吞吐量就足以讓服務器的 CPU 飽和。在這種情況下，去優化 Buffer 的內存拷貝次數似乎沒有意義。
再舉一個例子，目前最常用的千兆以太網的裸吞吐量是 125MB/s，扣除以太網 header、IP header、TCP header之后，應用層的吞吐率大約在 115 MB/s 上下。而現在服務器上最常用的 DDR2/DDR3 內存的帶寬至少是 4GB/s，比千兆以太網高 40 倍以上。就是說，對于幾 k 或幾十 k 大小的數據，在內存里邊拷幾次根本不是問題，因為受以太網延遲和帶寬的限制，跟這個程序通信的其他機器上的程序不會覺察到性能差異。
最后舉一個例子，如果你實現的服務程序要跟數據庫打交道，那么瓶頸常常在 DB 上，優化服務程序本身不見得能提高性能（從 DB 讀一次數據往往就抵消了你做的全部 low-level 優化），這時不如把精力投入在 DB 調優上。
專用服務程序與通用服務程序的另外一點區別是 benchmark 的對象不同。如果你打算寫一個 httpd，自然有人會拿來和目前最好的 nginx 對比，立馬就能比出性能高低。然而，如果你寫一個實現公司內部業務的服務程序（比如分布式存儲或者搜索或者微博或者短網址），由于市面上沒有同等功能的開源實現，你不需要在優化上投入全部精力，只要一版做得比一版好就行。先正確實現所需的功能，投入生產應用，然后再根據真實的負載情況來做優化，這恐怕比在編碼階段就盲目調優要更 effective 一些。
Muduo 的設計目標之一是吞吐量能讓千兆以太網飽和，也就是每秒收發 120 兆字節的數據。這個很容易就達到，不用任何特別的努力。
如果確實在內存帶寬方面遇到問題，說明你做的應用實在太 critical，或許應該考慮放到 Linux kernel 里邊去，而不是在用戶態嘗試各種優化。畢竟只有把程序做到 kernel 里才能真正實現 zero copy，否則，核心態和用戶態之間始終是有一次內存拷貝的。如果放到 kernel 里還不能滿足需求，那么要么自己寫新的 kernel，或者直接用 FPGA 或 ASIC 操作 network adapter 來實現你的高性能服務器。
(待續)