高并发的一些总结

本文转自公众号"lunewcome"。

有很多“奇技淫巧”的高并发，但基础知识的掌握程度决定了我们所写代码的并发程度，对基础足够了解才能写出并发性能更高的程序，所以本文先总结一些基础，然后再看一些具体例子。这个总结不是从头开始的详细介绍，另外影响并发性能的因素很多，想必这里说的也不是全部。

整数读写的原子性
计算机保证读写整数或指针是原子的，只要地址是按字长对齐的。要注意的是这里的原子性并不是“线程安全”什么的，而仅仅是指不会读到“乱七八糟”的值，比如有10个线程并发地往整数变量a中写0~9，那么只会读到0~9中的某个值而不会是其它任何值。

程序员视角下的缓存
总有人担心写指令是先写到缓存，经过某一段时间后再“刷”新到内存，而在这段时间内其它线程读不到最新值；还有一些文章总结了很多底层的或硬件的东西，比如“write buffer”。其实从程序员的角度看只要记住这两点：
1）利用缓存提高性能，例如避免伪共享，注意缓存行大小
2）不需要在意缓存更新问题，这是由硬件通过MESI协议保证的，我们只要记住一个线程执行完写入指令后，其它线程再从内存读时就能拿到最新值。
注意第二点，可能有人会说“既然如此，为什么多线程并发写一个整数，结果仍然是一个非确定的值”？其它第二点并不等同于线程同步操作，它只是缓存和内存之间的一致性，并不是指多线程写缓存/内存时的一致性/同步。

执行顺序与内存屏障（内存栅）
有两个地方可能“乱序执行”：一是编译器可能优化调整指令顺序，二是为了提高性能现代cpu几乎都是乱序执行（弱内存序），如powerpc和arm，常用的x86（强内存序）也不保证读写完全有序。这是不能用doube-check实现单例模式的原因。为了保证顺序性，在一些关键地方就必须加入内存屏障。屏障的作用就是当它之前的语句全部执行完后，才能执行它后面的语句。这方面也有很多比较底层的文章，但单纯从程序员的角度看，只要理解概念然后就老实用c++11提供的接口吧，原因是：
1）硬件差异大，但并不需要所有人去了解并解决。
2）c++11的封装的是各平台下能实现的最高性能，没必要自己弄一套。

伪共享
缓存失效是指整个缓存行失效，而不是其中的一部分，所以如果多个cpu/核的缓存中保存了同一缓存行，根据MESI协议，当某一个cpu/核写该缓存行时其余cpu/核上的缓存行都将失效。这个描述包含“真共享”和伪共享，当各cpu/核读写同一变量时就是“真共享”，读写不同变量时就是伪共享。“真共享”是我自己造的词，没见别人这么叫过，应该是因为它比伪共享容易察觉的多，不需要多说。伪共享的直接结果就是“cache miss”，这对性能影响很大，所以在关键数据结构上需要格外注意。只有理解了伪共享，才能知道用shard_ptr来回拷贝并非想象的那么高性能，才能知道读写锁不是描述的那么美好，等等。

下面是一些实践总结。

map
c++中的std::map，std::unordered_map都不是线程安全的，在多线程环境下需要加锁。加一把“大锁”当然安全但性能很差。一种简单有效的办法是仿效JAVA中的分段锁：定义多个map，每个都用一个mutex来保护读写。访问时首先判断key落在哪个段，再对该段的mutex加锁，然后就能安全地访问对应的map了。通过这种分段的方式的降低了冲突概率，提高了并发，简单而且性能不差。我在实际中一般用32或64个段，还没有发现有瓶颈问题。
使用原子操作实现map能得到更好的并发性能，但要自己去实现。最好先看看用原子操作实现一个list有多麻烦再决定要不要实现无锁map。

vector（可变长数组）：Append-only
如何实现高并发、线程安全的vector？我实现过这样一样链表式的数组：每个数组都是等长的，写满后就申请一个新的并用指针链接到当前数组后面。这样就形成了一个“链表式的数组”，特点是顺序读写性能好但随机读性能稍差。链接用的指针需要用一个原子操作，保证申请完新数组并适当初始化后再加入到链表中。

RCU（Read，Copy Update）
RCU的概念很早就有，linux内核2.6版本实现了相应接口。它的大致思想是：Read是无锁的但要标记读的开始，写时首先Copy原内容，在拷贝上完成Update操作后替换原内容；待所有的Read都不再引用原内容后，删除原内容。
RCU的关键就在于如何知道所有的Read都不再引用原内容，2.6版本的实现思路是读时开启“禁止抢占”，这样读时就没有上下文切换，所以当写端发现所有cpu都有过一次上下文切换后，就能确定所有Read已经走出了保护区域，不再引用原内容。在更新的版本中，linux实现了分级RCU，能进一步提高并发，适应多cpu环境（成百上千个cpu的机器）。
操作系统要考虑的环境当然比应用程序复杂恶劣的多，而我们是可以用些取巧的办法的：
1）我实际中实现过这样一个双buffer：一个用于读，另一个用于写，读写切换后再等待一段时间才删除切换下来的buffer。这个双buffer能工作的关键是“这段时间”比线上请求的耗时长得多，比如1~10s，而线上请求一般在ms级完成。
2）上面的vector也可以用类似思路实现，即容量时重新申请2倍大的空间，Copy原vector的内容，再切换两个buffer的指针。这样就能有很高的随机读性能，在不触发扩容时写性能也很高（大部分情况如此）。

brpc中的dbd（Doubly-Buffered-Data）
绝妙，是我第一次见到这个神奇操作时的感受，我实在惊叹---真是想知道作者当初如何想到这样巧妙的思路。直到我了解了RCU的实现，我猜测作者可能是受了RCU的启发。和RCU类似，dbd也是适合读多写少的场景，并且也都要等待所有的读完成。dbd也是一个双buffer，和我的双buffer不同的是：
1）定义thread local的mutex，每次读buffer时先获取该锁
2）定义保证顺序写的mutex，写时先获取该锁
3）写操作切换buffer后，逐一去获取1）中所有的thread local的mutex锁，获取后立即释放。好玩的是这一步，请思考下为什么这样就能保证所有读都已经完成？
这和RCU是多么的相像！只不过一个是等待cpu一个是等待线程。
像我同事wonderfu一样，致敬brpc。

thread local
最高的并发就是完全隔离，互不影响，thread local天生如此。实际上不仅brpc的dbd，我们熟知的tcmalloc和jemalloc也都使用了thread local特性，所以让我们记住这高并发最后的利器吧。
最后，还有一项来自数据库的技术：mvcc（Multiversion Concurrency Control），我平时还没有用到，只是提一下就不细说了。

参考：
https://www.kernel.org/doc/Documentation/RCU/whatisRCU.txt
https://www.kernel.org/doc/Documentation/memory-barriers.txt
https://github.com/Apache/incubator-brpc/blob/master/docs/cn/lalb.md