当然，大部分场景几乎不要用Lock-Free和Wait-Free的算法，一个是因为不需要那么极尽变态地压榨性能。另一个是这两种算法其实很复杂，即使写出来了，从形式化的手段也难以证明算法的正确性。对于越复杂的数据结构越是如此。比如Lock-Free的数据结构目前在boost C++中常见的有Queue, Ring Buffer，Stack这些简单的数据结构。但是如果你搜网络上的论文，就很难见到有Lock-Free的树型数据结构。其一是太复杂了，即使实现并证明正确，但是实测性能可能也没加锁的树形数据结构高。如果这样就舍本逐末了。
title: 多核编程的相关理论及实践 date: 2018-04-13 12:01:23 tags:
多核编程
前言
在开篇之前，我想说点文体风格，由于阅读brpc的文档给了我巨大的收获，所以文体的风格会以问答的方式展开。顺便给出原理解释，还有感受下戈君大神在文档中浸淫多年的软件基础设施工程实践心得体会。我文字理解驾驭不了的地方会选择性地摘抄文档内容。
正文
1. 如何针对写多读少的场景设计一个多线程计数器？
大部分RPC框架，或者其他中间件或多或少都需要有这样的需求，因为这些中间件基本都是主打高性能的，高效利用多核多线程。既然是高性能，都需要为它设计计数器，目的是为了方 便统计各种服务的调用次数，还有其他性能参数（QPS,平均延时），以达到监控服务，调优服务的最终目的。 本着最直观的理解，写下了如下最简单的计数器代码:
以上代码是正确的，global_count在多线程调用的累加下不会出错。但是由于多线程高频率修改global_count，性能可能没你想象的好，因为造成了大量的Race Condition。这时候锁的性能造成了瓶颈。你不得不想方设法的绕开锁的限制。
这里有一点值得注意，C++提供的std::mutex在大部分不压榨性能的场景足够用了，造成std::mutex性能低下的两点，一个是std::mutex的粒度过大，也就是临界区过大限制了并发度。另一个就是频繁的访问导致锁争用，上下文切换非常频繁。
那么如何解决计数器遇到的这个问题呢？ 其实最直观的就是避免共享，避免锁争用。用thread local技术来避免减少大量的Cache Bouncing，该技术原理是每个线程修改（写）global_count只维持线程自己的一个变量累加的副本。等到有线程读global_count的时候，就把各个线程的变量副本的结果合并起来，这个速度就会显得慢了，不过因为是写多读少的场景，所以没有问题。
2. Cache Bouncing是为何物？
为了以较低的成本大幅提高性能，现代CPU都有cache。cpu cache已经发展到了三级缓存结构，基本上现在买的个人电脑都是L3结构。其中L1和L2 cache为每个核独有，L3则所有核共享。为了保证所有的核看到正确的内存数据，一个核在写入自己的L1 cache后，CPU会执行Cache一致性算法把对应的Cache Line(一般是64字节)同步到其他核的Cache中。这个过程并不很快，是微秒级的，相比之下写入L1 cache只需要若干纳秒。当很多线程在频繁修改某个共享字段变量时，这个字段所在的Cache Line被不停地同步到不同的核上，就像在核间弹来弹去，这个现象就叫做Cache Bouncing。由于实现cache一致性往往有硬件锁，Cache Bouncing是一种隐式的的全局竞争。
当然Cache一致性算法有多种，其中一种听到的最多的叫MESI协议。
3. CAS原子指令为什么会这么难？
多核多线程编程常用锁避免多个线程在修改同一个数据时产生race condition。当锁成为性能瓶颈时，我们又总想试着绕开它，而不可避免地接触了原子指令（用于实现Lock-Free和Wait-Free等数据结构和算法）。但在实践中，用CAS原子指令写出正确的代码是一件非常困难的事，各种概念接踵而来，琢磨不透的race condition、ABA problem、memory barrier很烧脑。（Memory Barrier又叫内存栅栏，内存屏障）。
顾名思义，原子指令是对软件不可再分的指令，比如x.fetch_add(n)指原子地给x加上n，这个指令对软件要么没做，要么完成，不会观察到中间状态。常见的原子指令有：
你已经可以不用显式加锁用这些指令做原子计数，比如多个线程同时累加一个原子变量，以统计这些线程对一些资源的操作次数。但是，这可能会有两个问题：
4. 什么情况下多核之间的Cache Line会频繁同步导致Cache Bouncing？
一个核心写入自己的L1 cache是极快的(4 cycles, ~2ns)，但当另一个核心读或写同一处内存时，它得确认看到其他核心中对应的cache line。对于软件来说，这个过程是原子的，不能在中间穿插其他代码，只能等待CPU完成一致性同步，这个复杂的硬件算法使得原子操作会变得很慢，竞争激烈时fetch_add会耗费数百纳秒左右。访问被多个线程频繁共享的内存往往是比较慢的。比如像一些场景临界区看着很小，但保护它的spin lock性能不佳，因为spin lock使用的exchange, fetch_add等指令必须等待最新的cache line，看上去只有几条指令，花费若干微秒并不奇怪。
要提高性能，就要避免让CPU频繁同步cache line。这不单和原子指令本身的性能有关，还会影响到程序的整体性能。最有效的解决方法很直白：尽量避免共享。（比如用之前提到过的Thread Local）。
一个相关的编程陷阱是False Sharing：对那些不怎么被修改甚至只读变量的访问，由于同一个cache line中的其他变量被频繁修改，而不得不经常等待cache line同步而显著变慢了(也就是被别的变量拉低的性能)。多线程中的变量尽量按访问规律排列，频繁被其他线程修改的变量要放在独立的Cache Line中。要让一个变量或结构体按Cache Line对齐。
5. 基于CAS原语的原子指令编写的Lock-Free和Wait-Free数据结构和算法性能一定更高吗？
诚然，原子指令基于CAS原语的控制并发的粒度会更小，但是由此带来了更大的复杂性。它能为服务赋予两个重要的概念Lock-Free和Wait-Free。
当然前者的意思不言自明了，就是无锁编程（算法），后者是无等待编程（算法）。有的人说，那好了，采用Lock-Free的算法，不用加锁了，显然更快了。Wait-Free那更加快了，都不用等待了。当然理论上是这么一回事，但是工程实践上又是一回事。无锁编程采用底层的CAS原语其实上的是硬件粒度的锁，理论上是更加快，因为一些实时系统的关键部分和一些关键的数据结构为了压榨性能，确实是用Lock-Free的算法和Wait-Free算法编写的。但是，值得注意的事情是：
lock-free和wait-free必须处理更多更复杂的race condition和ABA problem，完成相同目的的代码比用锁更复杂。代码越多，反而比用小粒度的std::mutex耗时长。
使用mutex的算法变相带“后退”效果。后退(backoff)指出现竞争时尝试另一个途径以临时避免竞争，mutex出现竞争时会使调用者睡眠，使拿到锁的那个线程可以很快地独占完成一系列流程，总体吞吐可能反而高了。
mutex导致低性能往往是因为临界区过大（限制了并发度），或竞争过于激烈（上下文切换开销变得突出）。lock-free/wait-free算法的价值在于其保证了一个或所有线程始终在做有用的事，而不是绝对的高性能。但在一种情况下lock-free和wait-free算法的性能多半更高：就是算法本身可以用少量的CAS原子指令实现。实现锁也是要用原子指令的，当算法本身用一两条指令就能完成的时候，相比额外用锁肯定是更快了。
当然，大部分场景几乎不要用Lock-Free和Wait-Free的算法，一个是因为不需要那么极尽变态地压榨性能。另一个是这两种算法其实很复杂，即使写出来了，从形式化的手段也难以证明算法的正确性。对于越复杂的数据结构越是如此。比如Lock-Free的数据结构目前在boost C++中常见的有Queue, Ring Buffer，Stack这些简单的数据结构。但是如果你搜网络上的论文，就很难见到有Lock-Free的树型数据结构。其一是太复杂了，即使实现并证明正确，但是实测性能可能也没加锁的树形数据结构高。如果这样就舍本逐末了。
6.协程是什么？它为什么不能利用多核？
协程是一种用户态的线程，由用户态的调度器来调度，因为其非常轻量，可以用来部分代替线程从而实现所谓的高并发（看场景），而且由于协程不对应内核中的线程概念，所以用户可以一瞬间创建出成千上万个协程，而不消耗太多性能，它们之前切换可以非常快（100ns-200ns），受缓存一致性的影响很小。但是呢，平常我们所说的协程并不能利用CPU多核，因为是它相当于是N：1的线程库，就是N个协程只跑在一个内核线程上，一个内核线程只会在一个核上运行。
还有一个缺点就是，因为协程无法高效利用多核，代码必须非阻塞，否则所有协程都会被block住，对开发者要求比较苛刻。协程的这种特点使其非常适合写运行时间基本能确定的IO服务器，比如http server，在一些精心调试的场景中，可以达到非常高的吞吐量（实时大流量）。协程的这个特点与Event Loop的单线程异步是类似的，一个callback函数如果需要等待比较长的时间，那么整个Event Loop就被block住了，其他事件得不到及时响应。
所以可以看到了，Node.js之类的适配上协程确实可以达到高并发，高吞吐，这句话本身没问题。但是这是有场景的，Node.js适合处理IO数据密集型实时应用系统，比如Web消息实时推送（知乎的问答提示），Web可视化数据实时展示。Node非常适合如下情况：在响应客户端之前，你预计可能有很高的流量，但所需的服务器端逻辑和处理不一定很多（服务端不能有复杂计算，复杂业务逻辑，复杂事务处理）。
当然有懂一点的人可能会说，可以开启多个Node.js进程（Cluster模块）来以多个内核线程达到利用多核的目的，当然至于这样是不是很方便，很高效就是另一个话题了。但是据我所知，主流大型互联网公司基础框架想高效的利用多核都不会选择这种方案。
7. Go语言中的GoRoutine是协程吗？为什么它却能利用多核？
不是，因为GoRoutine是可以利用多核的，它实质上就是个M:N的线程库（一般M会远大于N），M个GoRoutine对应N个内核线程（当然，这个特性是以语言内建特性的方式暴露出来的，而不是标准库的形式，所以写起来会更自然些）。一个RoRoutine因复杂的计算或者同步阻塞IO等待而block住也不会影响其他GoRoutine。
Goroutine调度器的实现由一种关键的技术：Work-Stealing调度算法。这一种算法的目的是想让GoRoutine更快地被调度到更多的CPU核心上。
8. 单线程Reactor和多线程Reactor模型有什么不同？
以libevent, libev等event-loop库为典型。这个模型一般由一个event dispatcher等待各类事件，待事件发生后原地调用对应的event handler，全部调用完后等待更多事件，故为"loop"。这个模型的实质是把多段逻辑按事件触发顺序交织在一个系统线程中。一个event-loop只能使用一个核，故此类程序要么是IO-bound，要么是每个handler有确定的较短的运行时间（比如http server)，否则一个耗时漫长的回调就会卡住整个程序，产生高延时。在实践中这类程序不适合多开发者参与，一个人写了阻塞代码可能就会拖慢其他代码的响应。由于event handler不会同时运行，不太会产生复杂的race condition，一般不需要加锁。此类程序主要靠部署更多进程增加扩展性。Redis就是这么干的。
以boost::asio为典型。一般由一个或多个线程分别运行event dispatcher，待事件发生后把event handler交给一个worker线程执行。 这个模型是单线程reactor的自然扩展，叫多线程Reactor，可以利用多核。由于共用地址空间使得线程间交互变得廉价，worker thread间一般会更及时地均衡负载，而多进程一般依赖更前端的服务（Nginx）来分割流量，一个设计良好的多线程reactor程序往往能比同一台机器上的多个单线程reactor进程更均匀地使用不同核心。不过由于cache一致性的限制，多线程reactor并不能获得线性于核心数的性能，在特定的场景中，粗糙的多线程reactor实现跑在24核上甚至没有精致的单线程reactor实现跑在1个核上快。由于多线程reactor包含多个worker线程，单个event handler阻塞未必会延缓其他handler，所以event handler未必得非阻塞，除非所有的worker线程都被阻塞才会影响到整体进展。事实上，大部分RPC框架都使用了这个模型，且回调中常有阻塞部分，比如同步等待访问下游的RPC返回。
9. N：1线程库和M:N线程库又有什么区别？
之前提到过，平常所说的协程（Coroutine）相当于是一个N：1的线程库。但是这么说并不代表N：1的线程库就是协程，它有另外的名字叫纤程（Fiber）。以GNU Pth, StateThreads等为典型，一般是把N个用户线程映射入一个系统内核线程。同时只运行一个用户线程，调用阻塞函数时才会切换至其他用户线程（有调度器，所以跟Event Loop这点细节上又不大一样）。N:1线程库与单线程reactor在能力上是等价的，但事件回调被替换为了上下文(栈,寄存器,signals)，运行回调变成了跳转至上下文。和event loop库一样，单个N:1线程库无法充分发挥多核性能，只适合一些特定的程序。只有一个系统线程对CPU cache较为友好，加上舍弃对signal mask的支持的话，用户线程间的上下文切换可以很快(100~200ns)。N:1线程库的性能一般和event loop库差不多，扩展性也主要靠多进程。
M:N线程库也只是一种实现思想思路，Goroutine就是这样的实现。即把M个用户线程映射入N个系统内核线程。M:N线程库可以决定一段代码何时开始在哪运行，并何时结束，相比多线程reactor在调度上具备更多的灵活度。但实现全功能的M:N线程库是困难的，它一直是个活跃的研究话题。我们这里说的M:N线程库特别针对编写网络服务，在这一前提下一些需求可以简化，比如没有时间片抢占，没有(完备的)优先级等。M:N线程库可以在用户态也可以在内核中实现，用户态的实现以新语言为主，比如GHC threads和goroutine，这些语言可以围绕线程库设计全新的关键字并拦截所有相关的API。而在现有语言中的实现往往得修改内核，比如Windows UMS和google SwicthTo(虽然是1:1，但基于它可以实现M:N的效果)。相比N:1线程库，M:N线程库在使用上更类似于系统内核线程，需要用锁或消息传递（消息总线，Actor模型，Vert.x，Akka库等代表）保证代码的线程安全。