A Coder is a Poet

Kaiyuan Blog

C++ 模板特性之 SFINAE

最近在看 Facebook 开源的 C++ 组件库 folly 的源码,不仅收获了很多 Modern C++ 的编程技巧(e.g. type_traits,meta-programming),也了解了很多高效数据结构的设计思想(e.g. FBString,Atomic Data Structures)。不得不说,folly 与 Leveldb 一样具有很高的源码质量,尽管采用了较多的高级特性及平台相关特性,但是阅读起来并不会因代码风格而吃力。今天这篇文章,我们来介绍一下在 folly 中被大量使用的现代 C++ 模板特性 – Substitution failure is not an error (SFINAE)

在开始今天的主题之前,先思考一下如下两个通常可能会遇到的问题:

  1. 如何在编译期间判断某个类型 T 是否是 class 类型或者判断某个 class T 是否有指定的成员变量或成员函数?
  2. 如何在函数编译期间根据特定的条件来选择启用或禁用特定的重载?
继续阅读 >>

分布式系统一致性

Linearizability vs. Sequential consistency

说到『一致性』这个词,你首先想到了什么?

图1:CAP 定理趣图

是 ACID 中的 consistency? 还是 Raft 或者 Paxos 中的 consensus? 是 MESI cache 一致性协议中的 coherence? 亦或是 CAP Theory 中的 consistency?

继续阅读 >>

Lock-free 编程:A Case Study(下)

Hazard Pointer

在上文 Lock-free 编程:A case study(上) 中,我们介绍了如何通过 CAS2 操作实现一个无锁的支持并发访问的 Map。尽管 CAS2 帮助我们达到了 Lock-free 的要求,但不管怎么说,最终的实现在不太「优雅」的同时也不具有较好的性能。为了更进一步完善我们的 Lock-free Map,今天我们来介绍一些更高级的技术。

回忆一下前文中我们在通过 C++ 实现 Lock-free 的过程中面临的最主要的问题:什么时候释放旧的 map 指针 pOld。抛开使用 CAS2 实现的引用计数的方案,我们也可以简单粗暴一点,直接在『一段时间以后』去 delete 掉 pOld。然而,『一段时间』是一个很奇妙的说法,究竟多长时间才可以被定义为『一段时间呢』呢?显而易见的是,如果这个时间太长会导致内存释放不够及时,产生大量的内存垃圾;而如果这段时间被定义的太短,又可能在删除的时刻还有读线程仍持有这个旧的 Map,从而使读线程产生异常。那么,我们如何来定义『最适当』的删除时间呢?

继续阅读 >>

Lock-free 编程:A Case Study(上)

基于 CAS 的无锁数据结构

在并行和分布式编程领域,Lock-free 是一个非常复杂也非常具有挑战性的话题。前面的文章 Memory reordering 浅析 中,我们提到了一个与 Lock-free 息息相关的概念–内存屏障。今天我们通过一个由浅入深的编程范例来具体介绍 lock-free 数据结构和算法思想,包括 Hazard PointerRead-Copy Update 的基本概念。这篇文章的初衷都来源于对 Andrei Alexandrescu 的文章 Lock-Free Data Structures 的扩展和理解。

Lock-free vs. Wait-free

从直观上理解,lock-free 数据结构即不使用任何锁的数据结构,Lock-free 编程则指利用一组特定的原子操作来控制多个线程对于同一数据的并发访问。相比于基于锁的算法而言,Lock-free 算法具有明显的特征:某个线程在执行数据访问时挂起不会阻碍其他的线程继续执行。这意味着在任意时刻,多个 lock-free 线程可以同时访问同一数据而不产生数据竞争或者损坏。

继续阅读 >>

libco 分析(下):协程的管理

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

在继续下文之前想说明一点,相比于同是微信开源的 phxrpc,libco 整个代码的编码质量不算很高,代码风格比较杂乱,格式以及命名也没有严格遵循要求,并且缺乏功能上的注释。在代码中先后出现像函数 pollco_pollco_poll_innerco_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 实现事件的监听和协程的循环切换;
继续阅读 >>

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

继续阅读 >>