A Coder is a Poet

Kaiyuan Blog

Memory Reordering 浅析

最近越来越感觉到坚持写 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 概念等问题,看起来非常底层,但是一旦深入理解,对于后续编程和学习必定大有帮助。

继续阅读 >>

KCP: 快速可靠的ARQ协议

这段时间看的东西有些杂,先是花了一个星期重新把 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 笔记六:Memtable 实现

回顾一下在第一篇关于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_ 来决定内存释放。

继续阅读 >>

libco 分析(上):协程的实现

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

在前面的文章 动态链接之 Hook 系统函数 中我们提到过腾讯开源的一套用于支撑微信后端海量并发的 C++ 协程库 libco。相比于其他的 C++ 协程实现,libco 通过仅有的几个函数接口 co_createco_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++ 引入了输入输出流。C++ 的输入输出系统中提供了两个基类,分别是 ios_baseios。基于这两个基类实现了我们常用的标准输入输出流 istreamostream。同时,基于这两个流,C++ 提供了另外两种类型:文件输入输出流 fstream 以及字符串输入输出流 stringstream。这些类之间的继承关系可以用下图来说明:

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

继续阅读 >>

leveldb 笔记五:LRUCache的实现

leveldb 利用 cache 来通过一个 key 快速地检索到 value 值,其在 include/leveldb/cache.h 中定义了 cache 应该实现的接口。leveldb 要求 cache 实现内部的同步,从而可以让外部的线程并发地访问。像前面介绍的运行时环境 Env 一样,外部的使用者可以根据接口自定义其 cache 的实现。同时,leveldb 也提供了默认的基于 LRU(Least-Recently-Used) 的 cache。

我们首先看一下 cache 的定义,其在类定义的时候声明了一个 Rep 结构,并在类中定义了一个指向 Rep 的指针 rep_

class Cache {
private:
    struct Rep;
    Rep* rep_;
    ...
}

在后面的学习中我们可以看到,在 table_builder 的定义中,作者也采用了这种方式。可能有很多人不明白作者为什么采用这种方式来定义类成员。事实上,这正是 Scott Meyers 在 Effective C++ 条款 31 所提到的

继续阅读 >>