Ring Buffer 的应用
这是一篇命题作文，源于今天在微薄上的一系列讨（好吧，也可以说是吵架）。其实方案没有太多好坏，就看你信不信这样做能好一些或坏一些。那么，整理成 blog 写出，也就是供大家开拓思路了。
我理解的需求来源于网络服务提供程序的一个普遍场景：一个服务器程序可能会收到多个客户端的网络数据流，在每个数据流上实际上有多个独立的数据包，只有一个数据包接收完整了才能做进一步的处理。如果在一个网络连接上数据包并不完整，就需要暂时缓存住尚未接收完的数据包。
问题是：如何管理这些缓冲区比较简洁明了，且性能高效。
其实这个有许多解决方案，比如为每个网络连接开一个单独的固定长度的 buffer 。或是用 memory pool 等改善内存使用率以及动态内存分配释放，等等。今天在微薄上吵架也正是在于这些方案细节上，到底好与不好，性能到底如何。既然单开一篇 blog 了，我不像再谈任何有争议的细节，仅仅说说，用 Ring Buffer 如何解决这个问题。
具体点说，我倾向于用 C 语言来做这种偏底层、业务简单的模块。为了减低工作量，可以使用一些成熟的库，比如 libev 等。
类似的库多半提供的是一种回调机制的框架，设置好对应的 IO 异步请求的 callback 函数，然后启动框架的主循环，每个 socket （或别的句柄）可读写时，回调注册好的函数。
把这件事情做的干净漂亮的关键点之一在于数据缓冲区的管理。
拿到需求后，我们应该适当估算我们的程序需要解决多大的数据吞吐量。比如，我们可以假设，一个逻辑完整的数据包在 TCP 连接上，可能最长大约会经过一两秒时间，通过 1 到 10 个包发送过来。整个系统每秒会处理 100M 字节（千兆网）的数据流，那么大约在 10 秒内，处理的数据量大约就在 1G 。
根据对实际业务的估算，这个值可能不到 1G ，128M 就够，也可能多达几个 G 。没关系。我们只是估算出，大致在这个范围内，一个独立的逻辑包一定存在于整个数据流的截段中。我指的数据流是服务程序从网卡上读到的所有数据。
就以 1G 为例，那么这个服务程序只需要开单个这么大的 buffer 就足够了，不必再有任何的动态内存管理。
我们把所有的数据，不论它来至哪个 TCP 连接，都以循环队列的方式，无差别的循序置入这个 buffer。放置的时候，以每次 IO 可读时可以读入的最大字节长度为限。一旦放不下，就折返到 buffer 头部。
buffer 里大概的数据结构是这样的：
[数据长度 连接号 下一块的位置 数据] [数据长度 连接号 下一块的位置 数据] [数据长度 连接号 下一块的位置 数据] ...
另外，内存里开一张 hash 表，记下连接号到数据块的映射关系。如果不想用 hash 表的话，也可以在 buffer 中直接记下连接对象在内存中的地址。
每当一个连接可读的时候，无论读到多少字节，都向这个 buffer 后面追加。并且用链表将其和历史上曾经读过的数据连起来。
同时，可以分析一个逻辑包是否完成。如果没有完成，则继续下面的工作。完成了的话，则利用已有的链表，将分离的数据块拼合在一块连续的内存上。之后，如何处理这个逻辑包，就不在是这个层次上的工作了。
对于处理掉的数据块，可以做一个记号表示废弃即可。我的做法是对数据长度段取反，这样 buffer 在循环使用时，可以判断出下面的内存空间是否可以安全使用。
处理完一个逻辑包后，有可能最后一块数据被切分出去。我的做法时调整这个块，前半块标记为废弃数据块，后半块为待处理数据块。
理论上，如果你的估算没有错且留有余量的话，每次新到来的数据包都能在 buffer 中找到储存它们的空间。因为根据估算，消费速度是要大于生产速度的。不然整个系统都跑不下去。
但如果碰到例外怎么办? 比如有个客户端半个逻辑包发来以后，迟迟不发下半个包。最简单的做法是，碰到 ring buffer 回卷后，碰到那些未废弃的数据块（尚未处理掉），索引到对应的连接，直接 close 掉连接，把没有处理的数据扔掉即可。因为在互联网上，连接本来就是不稳定的。你的协议原本就要处理主动断开连接的情况。无非是根据 ring buffer 的大小和当时的负载情况，设置了一个超时而已。
有兴趣的同学，可以用这个思路实现一下几年前我提到的连接服务器 。代码量应该不大。
另，在更高层的应用上，同样可以使用类似的策略。即循环使用一个 ring buffer 。当 buffer 回转时碰到有对象占用 buffer 拦路时，杀掉对象。对于一些对象比较复杂占用的数据段不固定，对象生命期很短的应用，ring buffer 都有参考价值。例如 3d engine 中的粒子系统。对于要个别需要长期生存的对象，还可以定期复制自己，重新压入 ring buffer 的方式来延长生命期。
使用 ring buffer 的优势是内存使用率很高，不会造成内存碎片，几乎没有浪费（比如传统动态内存分配需要的 cookie）。业务处理的同一时间，访问的内存数据段集中。可以更好的适应不同系统，取得较高的性能。内存的物理布局简单单一，不太容易发生内存越界、悬空指针等 bug ，出了问题也容易在内存级别分析调试。做出来的系统容易保持健壮。
2 月 3 日 补充:
读了几位同学的反馈，发现在几个地方没讲清楚，造成许多疑惑。
一、从 ring buffer 里切分出去的数据块是可以任意合并或再切分的。数据块头上的数据块长度正是为了找到下一块的位置，可以把邻接的两个被标记（废弃）的块合成一个；为了可以任意切分，这里数值上制定的长度和实际占用的长度可能略微不等。实际占用的长度是 4 字节对齐的，而记录的长度则是真实值。比如，记录长度为 6 ，那么在推算下一块位置的时候，需要先圆整到 8 。这样做的话，可以让数据块长度至少为 4 。我们用 4 字节记录长度信息的话，就足够了。更细节的位置还有，我们需要利用连接号域做一个标记，比如空出一个不存在的连接号，表示这个块废弃且无关联连接。实际上，ring buffer 初始化时，就是把整个空间初始化为一个块，并打上可用（废弃）标记。使用的时候就从这个块中一分为二，取其一而用。
经过网友提醒, 这里还需要多设置一个单字节的 offset 域, 记录未处理的数据块头部偏移。
二、ring buffer 中切分出去的块的分配过程是顺序依次进行的，回收的次序则是随机的。初看起来这会导致使用一段时间后，buffer 里有很多空洞。但是， ring buffer 不是一个 memory pool ，并不做复杂的内存块管理工作。如果你想那样做的话，不如直接使用 malloc/free 。也不用为预测的数据量留大一个数量级的空间。ring buffer 在使用时，留足了空间和时间，当 buffer 回转，头指针继续从低地址位移动时，那些先前分配出去的数据块应该都被打上废弃标记了。我们要做的只是根据需要，把这些连续废弃块合成我们需要的程度。万一碰到中间有个别继续被占用的数据块怎么办？那就是上文中提到的，根据连接号强行回收的工作了。
Comments
Posted by: wsq | (23) July 28, 2014 01:38 PM
Posted by: tearshark | (22) March 12, 2012 04:30 PM
Posted by: 忠义哥 | (21) February 25, 2012 12:36 AM
Posted by: jessc | (20) February 13, 2012 11:16 PM
Posted by: punkydog | (19) February 9, 2012 01:54 PM
Posted by: zhanzenghui | (18) February 7, 2012 08:52 PM
Posted by: Holimion | (17) February 6, 2012 10:53 AM
Posted by: 老突发 | (16) February 6, 2012 10:10 AM
Posted by: 老突发 | (15) February 6, 2012 10:02 AM
Posted by: 老突发 | (14) February 6, 2012 09:50 AM
Posted by: Scott | (13) February 4, 2012 05:10 PM
Posted by: 冷锋 | (12) February 3, 2012 03:38 PM
Posted by: 老赵 | (11) February 3, 2012 03:35 PM
Posted by: haxixi_keli | (10) February 3, 2012 12:47 PM
Posted by: guaniu | (9) February 3, 2012 11:12 AM
Posted by: Cloud | (8) February 3, 2012 10:34 AM
Posted by: Anonymous | (7) February 3, 2012 10:05 AM
Posted by: grep | (6) February 3, 2012 08:57 AM
Posted by: pizi | (5) February 3, 2012 01:08 AM
Posted by: pizi | (4) February 3, 2012 01:06 AM
Posted by: hoterran | (3) February 2, 2012 10:48 PM
Posted by: landy | (2) February 2, 2012 10:37 PM
Posted by: 刘金雨 | (1) February 2, 2012 10:34 PM