C++实现成员函数检查

最近看到一段代码,感觉非常trick,但也非常有意思,写出来记录一下。

背景是这样的,有一个模板函数 copy_assign ,其作用非常简单,就是将第二参数“拷贝”给第一个参数,但是为了对能够进行深拷贝的类型进行深拷贝,希望的行为是这样的:

如果T有成员函数int assign(const T &),则调用dest.assign(src),并以assign函数的返回值作为返回值;
如果T没有成员函数int assign(const T &),则调用dest=src,并返回0。

函数的原型如下:

并且为了降低运行时开销,我们希望这一切是在编译期确定的,所以我们需要在编译期就能够确定类型T是否有assign成员函数,并且根据结果指定对应的行为。

继续阅读:

并发编程牛刀小试:SeqLock

Sequential lock,简称seq lock,是一种有点特殊的“读写锁”,Linux内核从2.6版本开始引入,是一种非常简单轻量保护共享数据读写的方法。

基本原理


Sequential lock的原理非常简单,其核心就是通过维护一个序号(sequence)来避免读者(Reader)读到错误的数据,而写者(Writer)在加锁和解锁的过程中递增序号,多个写者之间需要借助于额外的互斥锁来保证互斥关系。

具体来讲,序号初始化为0,读者和写者的流程如下:

  • 写者开始修改临界区中的数据时,首先获取写者间互斥锁,然后递增序号(奇数),开始修改数据,修改数据完成后会再次递增序号(偶数),然后释放写者间互斥锁。
  • 对读者来说,在修改数据的过程中读者可能会读到错误的数据,但读者在读数据前后会分别获取一次序号,对两次获取的序号进行比较,如果不相同则说明在读取过程中有写者进入了临界区,需要重试;如果序号相同但是是奇数,说明读者开始读取到结束读取的这段时间写者占有了临界区,同样也需要重试。
SeqLock时序示意

SeqLock时序示意

看个例子就明白了,如上图所示,是不是非常简洁明了。

继续阅读:

Hazard Pointer

上一篇文章中实现了一个lock-free的队列,但是有一个问题:内存无法被安全的回收。那么,这次就来把这缺失的一环补上:hazard pointer,一种lock-free对象的内存回收机制。

hazard pointer

hazard pointer

PS:因为hazard pointer完整代码略有些长,不适合贴在文章内部,完整代码可以在这里找到。

继续阅读:

无锁队列的一种实现

队列作为最常用的基础数据结构之一,相信大家都已经非常非常熟悉了,这里省略关于队列的介绍。在平时开发中队列的出现频率非常非常高,因此我们也会很关心队列的性能问题。当并发访问队列时,队列的性能往往受到同步手段的制约,最简单的方式是使用互斥锁对整个队列加锁,但其并发性能却惨不忍睹。

因此,有了各式各样的无锁队列实现,本文介绍其中的一种实现。还是老样子,实现基于x86体系结构,Linux环境。

继续阅读:

用户态同步之自旋锁

最近花了一些时间研究如何在用户态实现自旋锁,这里简单的总结一下。本文的所有代码以及配套的测试用代码都可以在我的github上找到。

问题在哪


首先明确问题,我们需要一种用户态实现的线程同步机制,正确性当然是最重要的。本文的目的是实现正确的自旋锁(自旋锁比较简单轻量,但了解了原理后实现互斥锁并不困难,自行维护等待关系并通过 futex 对线程执行挂起、唤醒操作就可以了)。

概念上这个问题很简单啊,是不是我们只要用一个线程共享的变量做互斥,然后在线程获得和释放锁时修改这个变量就行了?比如像下面这样:

然而事情没这么简单,因为对这个变量的操作不是原子的,所以会导致这个锁无法正确的运行(即使在单核环境也如此),因此我们需要利用硬件提供的原子操作来实现锁(FYI. 一种不需要原子操作的锁实现方法见前文中提到过的Dekker算法,非常漂亮,但通用性不足)。

除此之外,另一个问题是多核争用的性能问题,这一点我会在后文中提到。

另外由于在用户态实现锁对硬件体系结构提供的一致性保证非常相关,所以必须注明,本文中所有实现针对于x86体系结构(也就是acquire-release语义),不具备可移植性

继续阅读:

多核并发编程中的cache line对齐问题

先看一段代码:

这段代码的逻辑很简单,开多个线程并行执行一个不断对全局变量取反的操作,你觉得最后的结果会是什么呢?

继续阅读:

Sequential Consistency,Cache-Coherence及Memory barrier

如今多核CPU在服务器中已经是标配,如何更好的发挥多核CPU进行并行计算相信是每个后端开发都会遇到的难题。这篇文章主要是梳理一下我最近学习的一些关于C++多线程编程的知识。

并发 VS 并行


提到并发编程,有很多不同的编程模型,如多进程、多线程、协程,还可以结合使用I/O多路复用技术来进行异步并发编程,由此产生了很多不同类型的并发编程技巧来解决各类场景下的问题。

其中,协程模型也称为“用户态线程”,在用户态对程序流进行切换,避免了系统上下文切换的开销,属于并发而不是并行的(协程也可以和多进程、多线程模型结合,此处不做探讨),多进程和多线程的编程模型是真正并行的,即多个程序流是真正同时运行的,因此可以更好的利用多核优势,由于多线程之间共用进程地址空间,所以多线程模型相对多进程模型而言可以减少一些进程间的通信开销。

多线程同步


然而,凡事有利必有弊,共用进程地址空间带来了性能上的提高必然也会产生一些复杂的问题,及引入了线程间同步的问题。多个线程如果不加保护的访问共享的变量,必然会引发严重问题,这些在线程间共享的变量被称为“临界区”,最为经典的例子就是多个线程同时对单变量执行递增操作,相信诸位都已经听到耳朵起茧,就不再展开了。

在多线程编程中,常用的同步方式是使用pthread库中提供的线程同步手段(暂不考虑C++11中提供的线程库),如互斥锁、自旋锁、信号量、条件变量等等,但这些方法不是本文的主要内容,因此也不做展开,有兴趣的同学可以自行阅读《UNIX环境高级编程》中关于多线程同步的章节。

PS:在Linux内核中由于内核线程共用内核地址空间,所以内核线程之间也需要使用线程同步机制进行保护,Linux内核中所使用的几种常见同步机制分析见我之前的文章

继续阅读:

被误用的“一致性”

想必每个接触过分布式系统的同学都没少看到过“一致性”这个词,但是我最近有一个越来越强烈的感觉:“一致性”这个词已经被严重的误用了,以至于当我看到这个词的时候,我甚至得花些功夫去思考这到底指的是哪个“一致性”,更严重的是,当别人在谈到“一致性”的时候,实际上他们在谈的完全是另一种东西。

无辜的Paxos


故事的起因来源于Paxos(没错,又是这货),网上对于Paxos的文献太多,而且质量参差不齐,在绝大多数的中文文档中,你都可以看到这样的描述:“Paxos是一个分布式强一致性协议”,不瞒你说,每次看到这样的表述的时候,我的内心是崩溃的…且听我慢慢道来。

问题的由来很大一部分原因在于英文对中文的翻译,因此我们必须将术语还原到英文进行讨论,『一致性』对应的英文名词应该是Consistency没错了,然后我们在Lamport大神的原始论文《Paxos Made Simple》中搜索关键词,你会发现:

"Consistency" Not Found

“Consistency” Not Found

没错,论文中一次都没有提到过Consistency,也就是说,Paxos和『一致性』根本半毛钱关系都没有啊!那Paxos究竟是什么呢?论文中写的很明确——”The Consensus Algorithm”。

PS:本文中所有使用中文“一致”均指Consistency,“共识”为Consensus。

继续阅读:

分布式共识(Consensus):Viewstamped Replication、Raft以及Paxos

从上篇文章到现在,已经有半年多的时间没有写过什么了,时间真是匆匆而过,感觉从上次写博客到现在似乎也就是一眨眼的功夫。

回顾我这大半年,完全可以用四个字概括:“不务正业”,先是跟着曼昆的书学习了微观、宏观经济学的基础知识,恶补了一下个人理财的基础理论(很有意思,但依然挡不住我买的基金嗷嗷跌),然后又入坑了摄影(其实就是买个微单瞎拍瞎修)。至于个人的技术提升方面就显得捉襟见肘了,先是跟着斯坦福CS145、CS245两门课程复习了一下数据库方面的知识,然后就在分布式系统的泥沼中挣扎到了现在…可能唯一一件值得纪念的事情就是去年年底抱大牛大腿参加某司举办的hackathon,过程中学到了一点Golang的皮毛,最后搞了个apple watch耍(队友大牛依然表示对结果不太满意…),另外出于对tby大牛的仰慕,又补习了一下前端开发技能,然并卵,已经又忘光了…

一不小心写了一大段流水账,回归主题。之前花了大概两个多月时间从头琢磨分布式系统,研一时候修这门课完全是白学了,本来学的就不好,两年过去基本也不剩什么了。翻了两本最出名的教材,看了一些高校的课程安排和slides,总算感觉自己有点“上道”了~

这篇文章主要总结一下我个人认为是整个分布式系统中最为重要的问题(没有之一):分布式共识(Consensus)

达成共识

达成共识

PS:我在学习过程中是以《分布式系统:概念与设计》1这本书作为基础的,在下文中如果没有特别指明,所提书中内容均指该书。

继续阅读: