A Coder is a Poet

前文 libco 分析（上）：协程的实现 中我们介绍了 libco 使用汇编代码实现 协程上下文管理和切换的原理。今天我们继续介绍 libco 管理协程的逻辑，包括如何对 read，write 等接口进行非侵入式改造以及 libco 的共享栈原理。

在继续下文之前想说明一点，相比于同是微信开源的 phxrpc，libco 整个代码的编码质量不算很高，代码风格比较杂乱，格式以及命名也没有严格遵循要求，并且缺乏功能上的注释。在代码中先后出现像函数 poll，co_poll，co_poll_inner，co_eventloop 这种看起来很难区分功能的命名。但是我们在学习的过程中可以去其糟粕，取其精华，学习好的设计思想以及编程思路就可以了。

如何使用 libco

我们首先以 libco 提供的例子 example_echosvr.cpp 来介绍应用程序如何使用 libco 来编写服务端程序。 在 example_echosvr.cpp 的 main 函数中，主要执行如下几步：

1. 创建 socket，监听在本机的 1024 端口，并设置为非阻塞；
2. 主线程使用函数 readwrite_coroutine 创建多个读写协程，调用 co_resume 启动协程运行直到其挂起。这里我们忽略掉无关的多进程 fork 的过程；
3. 主线程继续创建 socket 接收协程 accpet_co，同样调用 co_resume 启动协程直到其挂起；
4. 主线程调用函数 co_eventloop 实现事件的监听和协程的循环切换；

最近越来越感觉到坚持写 Blog 不是一件容易的事情，先前立下的每周至少更新一篇的目标也没有完成；leveldb 的系列也一直拖着没有继续，这个要自我反省一下。

这段时间工作之余在慢慢地看 perfbook ，个人感觉收获颇多。尽管书中很多内容涉及到了底层体系结构，操作系统和编译系统，在平时的工作中极少会使用到；但是书中所提出的各种设计思想和思考问题的方式，给我带来了很多启发，也为后续学习很多新东西打下了基础。举个例子，最近百度开源了其内部使用的 rpc 框架 brpc，今天扫描了一下其中 bvar 的实现，发现完全就是 perfbook 中 counting 所使用的 data ownership 设计思想，如果有相应的模式在脑海里，理解起来非常容易。

有关 perfbook 中更多细节，以后再慢慢道来。今天这篇文章所关注的主题 – Memory reordering 以及 Memory barrier 也由 perfbook 和 leveldb 中引出，与 lock-free algorithm 息息相关。尽管这个主题涉及到 Cache coherence 协议，CPU 体系结构，Sequential consistency 概念等问题，看起来非常底层，但是一旦深入理解，对于后续编程和学习必定大有帮助。

这段时间看的东西有些杂，先是花了一个星期重新把 golang 的语法回顾了一遍，思考了一下 golang 与 C++ 不同的设计哲学；然后又陆陆续续地看了一些 lock-free 相关的论文以及与之相关的多线程内存模型，总体而言，这些内容在脑海在都还未成体系，因此都先暂时按下不表，今天先花点时间来记录一个简单的应用层 ARQ 协议 – KCP。

KCP 简介

KCP 是一个快速可靠协议，能以比 TCP 浪费 10%-20% 的带宽的代价，换取平均延迟降低 30%-40%，且最大延迟降低三倍的传输效果。KCP 主要利用了如下思想来加快数据在网络中的传输：

1. 相比于 TCP，KCP 启动快速模式后 超时 RTO 更新不再 x2，而是 x1.5，避免 RTO 快速膨胀。
2. TCP 丢包时会全部重传从丢的那个包开始以后的数据，KCP 是选择性重传，只重传真正丢失的数据包。
3. TCP 为了充分利用带宽，延迟发送 ACK（NODELAY 都没用），这样超时计算会算出较大 RTT 时间，延长了丢包时的判断过程。KCP 的 ACK 是否延迟发送可以调节。
4. ARQ 模型响应有两种，UNA（此编号前所有包已收到，如TCP）和 ACK（该编号包已收到），光用 UNA 将导致全部重传，光用 ACK 则丢失成本太高，以往协议都是二选其一，而 KCP 协议中，除去单独的 ACK 包外，所有包都有 UNA 信息。
5. KCP 正常模式同 TCP 一样使用公平退让法则，即发送窗口大小由：发送缓存大小、接收端剩余接收缓存大小、丢包退让及慢启动这四要素决定。但传送及时性要求很高的小数据时，可选择通过配置跳过后两步，仅用前两项来控制发送频率。

回顾一下在第一篇关于leveldb的目录中所介绍的内容，leveldb 最重要结构之一即是存储在内存中的 Memtable 和 Immutable Memtable。leveldb 每次在写入一个 Key/Value 对时，首先将该操作追加到 log 中，然后再将其写入到内存的 Memtable 中。如果 Memtable 的内存占用超过指定值，则 Leveldb 就自动将其转换为 Immutable Memtable，并自动生成新的 Memtable。Immutable Memtable 会被后台线程转储到磁盘中，构成磁盘上的 SSTable 结构。

MemTable 结构定义在文件 memtable.h 中，其成员变量如下：

class MemTable {
private:
    typedef SkipList<const char*, KeyComparator> Table;
    
    Table table_;
    Arena arena_;
    KeyComparator comparator_;
    int refs_;
    ...
}

leveldb 中的 MemTable 基于跳表 SkipList 来实现对于键值对的有序管理，通过内存管理器 Arena 来为插入的 key/value 对申请内存，并通过记录引用数量 refs_ 来决定内存释放。

“Subroutines are special cases of … coroutines.” — Donald Knuth

在前面的文章 动态链接之 Hook 系统函数 中我们提到过腾讯开源的一套用于支撑微信后端海量并发的 C++ 协程库 libco。相比于其他的 C++ 协程实现，libco 通过仅有的几个函数接口 co_create，co_resume 以及 co_yield 配合 co_poll，来支持同步或者异步的写法，从而实现对现有逻辑非侵入式的异步化改造。今天我们来详细分析一下 libco c++ 协程的实现。

（ps：写这个系列文章之前，我也没想到以后竟然会变成半个 libco 的使用者和维护者，当然这篇文章现在看来还是有一些问题的，后面再来纠正）

C/C++ 协程

首先需要声明的是，这里不打算花时间来介绍什么是协程，以及协程和线程有什么不同。如果对此有任何疑问，可以自行 google。与 Python 不同，C/C++ 语言本身是不能天然支持协程的。现有的 C++ 协程库均基于两种方案：利用汇编代码控制协程上下文的切换，以及利用操作系统提供的 API 来实现协程上下文切换。典型的例如：

• libco，Boost.context：基于汇编代码的上下文切换
• phxrpc：基于 ucontext/Boost.context 的上下文切换
• libmill：基于 setjump/longjump 的协程切换

一般而言，基于汇编的上下文切换要比采用系统调用的切换更加高效，这也是为什么 phxrpc 在使用 Boost.context 时要比使用 ucontext 性能更好的原因。关于 phxrpc 和 libmill 具体的协程实现方式，以后有时间再详细介绍。

为了提供更灵活的输入输出控制，并让其支持更多的类型和格式，C++ 引入了输入输出流。C++ 的输入输出系统中提供了两个基类，分别是 ios_base 和 ios。基于这两个基类实现了我们常用的标准输入输出流 istream 和 ostream。同时，基于这两个流，C++ 提供了另外两种类型：文件输入输出流 fstream 以及字符串输入输出流 stringstream。这些类之间的继承关系可以用下图来说明：

对于大多数 c++ 程序而言，使用系统提供的输入输出框架已经足够了。但是，对于想要根据需求改变流表现的使用者来说，了解如何定制流的过程至关重要。例如，你可能希望在你的项目中像标准输入输出一样来读取 tcp socket，或者希望像标准输入输出一样来封装一个对于 FILE* 的读取和写入，再或者你希望利用输入输出流的方式来操纵内存中的数据，这些都可以通过定制自己的流来实现。