被误用的“一致性”

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

无辜的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进行封装,向用户提供一套没有网络细节的接口。

继续阅读:

Hello, SciPy!

“学而时习之,不亦乐乎”,利用放假几天时间,简单复习了一下之前学习的Machine Learning课程,并且用刚上手没两天的SciPy重新完成了大部分Ng的课后作业,SciPy真的非常好用~

SciPy

SciPy

上图是SciPy官方网站对SciPy的介绍,SciPy并不是单个开源项目,而是一组开源项目共同构成的Python科学计算生态系统,一个非常值得一看的系列Tutorial在这里

下面是重写后的课后练习的notebooks:

  1. Linear regression
  2. Logistic Regression
  3. Multi-class Classification
  4. Learning curve(Bias v.s. Variance)
  5. SVM
  6. K-Means & PCA

神经网络相关的实验还没有重写,sklearn没有提供监督学习的神经网络组件,需要用pylearn2来做,有时间补上。