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这本书作为基础的,在下文中如果没有特别指明,所提书中内容均指该书。

继续阅读:

字符串匹配的后缀算法

字符串匹配问题是算法领域的经典问题,C/C++中常用的 strstr函数就是这个问题的定义:

const char* strstr( const char* str, const char* target );
char* strstr( char* str, const char* target );

Finds the first occurrence of the byte string target in the byte string pointed to by str. The terminating null characters are not compared.

在目标字符串 str中寻找是否存在子串 target,字符串 str的长度为\(n\), target的长度为\(m\)。这个问题最为人所熟知的算法应该是KMP(Knuth-Morris-Pratt)算法,其时间复杂度为\(O(n)\),想法非常酷。

但是,Can we do better?

继续阅读:

Strict Aliasing,神坑?

先来看一段代码:

你觉得程序的输出是什么样的呢?

继续阅读:

探索C++虚函数在g++中的实现

本文是我在追查一个诡异core问题的过程中收获的一点心得,把公司项目相关的背景和特定条件去掉后,仅取其中通用的C++虚函数实现部分知识记录于此。

在开始之前,原谅我先借用一张图黑一下C++:

“无敌”的C++

“无敌”的C++

如果你也在写C++,请一定小心…至少,你要先有所了解:当你在写虚函数的时候,g++在写什么?

继续阅读:

TCP Maximum Segment Size (MSS)

这篇是一个小小的查缺补漏,还记得大三网络实验最后助教检查实验问过这个问题:“MSS是干什么的?”,当时背了个定义蒙混过去了,没有仔细理解,现在又遇到了,补上~

MSS是什么?

下图中看到的是TCP连接发送和接收的过程示意图,最大报文段长度(MSS)的作用是限制在TCP层产生的报文段的最大长度(当然要在滑动窗口允许的前提下)。

TCP发送接收过程图

TCP发送接收过程图

比如如果MSS为1000个字节,每个TCP报文的最大长度为1020字节(附加20字节TCP头部),之后传递到IP层加装20字节IP头部封装成为IP报文利用链路层发送。

继续阅读:

关于Linux环境C/C++网络框架的一点思考

最近又看了一个网络框架的源码,和之前看过的比起来,应该说是各有特色,互有所长。在这个全民写框架的时代,可能是因为框架(Framework)听起来逼格比较高,所以大家都乐于去写一个自己的“框架”,那么,一个合格的网络框架究竟应该是什么样的?我们又该从何下手?

什么是网络框架

网络框架,顾名思义,是给网络应用程序使用的框架,本文中指代在Linux环境下使用C/C++编写的网络服务器框架。用户在使用框架时应该能够做到在对底层网络完全不了解或者所知很少的情况下,轻松实现自己所需要的后台网络服务应用。

原材料

听上去似乎很神奇,但实际上网络框架所要完成的只有一件事情——封装。网络框架所做的事情就是将Linux提供的底层网络API进行封装,向用户提供一套没有网络细节的接口。

继续阅读: