陈硕 (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 来实现你的高性能服务器。
(待续)