博文

目前显示的是 2015的博文

当心Intel® Management Engine埋下openssl的雷

Intel的电脑经常会默认安装一个叫做Intel® Management Engine的软件。这个东西会导致严重的安全漏洞,甚至让很多程序无法运行。举个例子,我今天自己在windows下编译了一个curl然后运行,发现出错了。报告curl.exe - Ordinal Not Found
The ordinal 385 could not be located in the dynamic link library C:\os\curl-7.43.0\builds\libcurl-vc14-x64-release-static-ssl-dll-zlib-dll-sspi\bin\curl.exe. 后来我用depends.exe发现,它引用了c:\program files (x86)\intel\icls client\LIBEAY32.DLL这个文件。而icls client是Intel® Management Engine的一部分,它安装后会把自己加到PATH环境变量中,它还带了两个openssl的dll。这种软件几百年都不会更新一次,想想去年openssl的heart bleed bug。 所以,赶紧,我建议,卸载这个破软件了事。

Reduce, Broadcast and AllReduce

图片
在做机器学习的时候,经常要做这样一个操作:每台机器计算出一个vector,然后把这些vector汇总加起来,再广播回去传统模式如下面这组图所示:总体来说,它可以分为两步:Reduce。 即map-reduce中的那个reduce。 Broadcast。 把reduce的结果broadcast到所有节点。直接以这样两步走的方式解决此问题会很低效。如果vector长度很大,那么负责汇聚的那个节点,就会成为性能瓶颈。树状模式于是就有了基于tree的map-reduce来解决这个问题。这种方式被广泛用在了Vowpal Wabbit和spark中。broadcast的过程与reduce的过程类似,我就不画了。下面举个例子分析下它需要花多少时间。 假设我们有75台机器,采用5叉树的方式来汇聚。那么需要5层。 第一层75台机器。 第二层15台机器。 第三层3台机器。 第四层1台机器。假设每个Vector的大小是1GB,而带宽是10Gb/s,那么reduce阶段至少需要(5+5+3)*8/10=10秒才能传输完。采用上一种方案,reduce需要75*1*8/10=60秒。相比之下有很大的改进。All to All 模式All to All的模式是每台机器和每台机器都得建立一个连接。初始状态是这样:value1value2value3value4机器11321机器22545机器381097机器46236然后,第i行的数据都汇总到第i%n台机器上。(n为机器数)
如下表所示。红色的代表新修改的值。value1value2value3value4机器117321机器222045机器3810187机器462319然后broadcast出去value1value2value3value4机器117201819机器217201819机器317201819机器417201819然后还是按上面的例子算下时间。可以发现,网络开销和机器数量无关。每台机器都需要传输大约2GB*(1-1/n)的数据出去,接收1GB * (1-1/n)的数据进来。所以,大约2秒就可以完成。汇总比较一下:所需时间传统方法60秒*2Tree10秒*2All to All2秒结合实际Yahoo的vowpal wabbit是率先把tree allreduce与hadoop结合起来。spark在reduce阶段提供了tree的…

L1-regularized logistic regression

图片
先挖个坑吧,以后慢慢填。刚读到台大几个学生写的一篇关于L1-regularized logistic regression(L1LR)综述性的论文:“A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification”。使我很受益,他们把各种思路和方法都罗列了出来,使得我可以按图索骥,一一尝试。不至于自己独自瞎忙活。所以我先挖个坑,逐渐的慢慢更新。关于问题的背景请参考我的Logistic Regression笔记。我认为L1-regularized logistic regression的核心是如何对一个非平滑(non-smooth)的非线性凸函数求最小值的问题。这在数学上是一个很广的topic,够写厚厚一本书了。我在此试图以L1LR为例探一探路。关于subgradient与BFGS的关系,在这篇A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning 论文中讲的比较好。Boyd的插值法http://stanford.edu/~boyd/l1_logreg/论文: An Interior-Point Method for Large-Scale `1-Regularized Logistic RegressionGlmnet论文: Regularization paths for generalized linear models via coordinate descent . Jerome H. Friedman, Trevor Hastie, and Robert Tibshirani. Journal of Statistical Software, 33(1):1–22, 2010.L-BFGS-B这是一个比较经典的算法了,也可以用在这个问题上。OWLQN论文: OrthantWise Limited-memory Quasi-Newton "Scalable Training of L1-Regularized Log-Linear Models(2007)" 视频:

Scalable…

java处理大数组真是让人头疼

我在spark中创建了一个长度为10亿,类型为double[]的accumlator。结果,发现函数send不出去,driver无法把这个函数send给worker 15/06/23 04:57:52 ERROR yarn.ApplicationMaster: User class threw exception: java.lang.OutOfMemoryError: Requested array size exceeds VM limit
java.lang.OutOfMemoryError: Requested array size exceeds VM limit
  at java.util.Arrays.copyOf(Arrays.java:2271)
  at java.io.ByteArrayOutputStream.grow(ByteArrayOutputStream.java:113)
  at java.io.ByteArrayOutputStream.ensureCapacity(ByteArrayOutputStream.java:93)
  at java.io.ByteArrayOutputStream.write(ByteArrayOutputStream.java:140)
  at java.io.ObjectOutputStream¥BlockDataOutputStream.drain(ObjectOutputStream.java:1870)
  at java.io.ObjectOutputStream¥BlockDataOutputStream.setBlockDataMode(ObjectOutputStream.java:1779)
  at java.io.ObjectOutputStream.writeObject0(ObjectOutputStream.java:1186)
  at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:347)
  at org.apache.spark.serializer.JavaSerializationStream.writeObject(JavaSerializer…

关于win 10升级的一些....

图片
呃,最近媒体上关于win 10如何免费升级的消息满天飞,我不知道我周围有多少人关心这个,也不知道哪些可以讲哪些不能讲……先放些图吧。这是我在win 8.1上收到的升级通知只有家庭版和专业版才会接到这样的升级通知,企业版不会。它主要有这样两点考虑:企业版有单独的销售策略,企业版并不能免费升级。企业版要想升级到win 10,企业是要因此而花钱的(可能已经以年费的方式掏过了) 企业内不应该允许个人随便升级操作系统。企业应该有自己的版本管理策略,由企业自己决定什么时候升,怎么升。理论来说,只有正版才能升级,盗版不能升级。 因为升级的过程中要连接微软的服务器进行激活。然后高潮来了。360/qq版的win 10是怎么回事。会不会有删不掉的内置应用?
360/qq版的win 10是这两个公司委托微软做的一个特别版。安装文件是微软做的,带有微软的数字签名,装完后里面不会有删不掉的东西。不像Android,定制版总是搞一些卸不掉的应用。盗版能激活吗?
不能。微软并没有提供key给360/qq。安装过程中所连接的激活服务器,依然是微软的服务器。另外,安装360/qq定制版的过程中遇到任何问题,微软不管,由这两家中国公司负责技术支持。所以,在我看来,奇虎和腾讯只是windows的两条推广渠道,而不是销售渠道。win 10并不是完全免费了,它也是有定价的,该卖还是要卖的。对个人用户来说,正版windows的销售渠道只有一个:微软的在线商店。没有代理商、分销商之类的。也没有实物。能买到的就是一个key和一个iso下载链接。一年内免费是说催促大家在一年内赶紧升级。并不是说装了win 10以后还要再掏钱。win 10的一个重大的改变是:会在开始菜单旁边内置cortana。cortana是一个类似于siri/google now的东西。cortana的中文识别做的挺不错的,比siri好。

Spark 1.1中下载jar包时的一个小错误

图片
我在用yarn中跑spark时,总是遇见一个这样的错误:java.io.FileNotFoundException: D:\data\yarnnm\local\usercache\chasun\appcache\application_1434537262045_0033\container_1434537262045_0033_01_000054\netlib-native\_ref-win-x86\_64-1.1-natives.jar (Access is denied)
  at java.io.FileOutputStream.open(Native Method)
  at java.io.FileOutputStream.(FileOutputStream.java:221)
  at org.spark-project.guava.common.io.Files¥FileByteSink.openStream(Files.java:223)
  at org.spark-project.guava.common.io.Files¥FileByteSink.openStream(Files.java:211)
  at org.spark-project.guava.common.io.ByteSource.copyTo(ByteSource.java:203)
  at org.spark-project.guava.common.io.Files.copy(Files.java:436)
  at org.spark-project.guava.common.io.Files.move(Files.java:651)
  at org.apache.spark.util.Utils¥.fetchFile(Utils.scala:437)
  at org.apache.spark.executor.Executor¥¥anonfun¥org¥apache¥spark¥executor¥Executor¥¥updateDependencies¥6.apply(Executor.scala:372)
  at org.apache.spark.executor.Executor¥¥anonfun¥org¥apache¥spark¥…

Rosenbrock Function

图片
Rosenbrock function是最优化课本中经常出现的函数。stanfordnlp的代码中也经常拿它测试各种最优化方法的正确性和性能。Rosenbrock function定义如下:$$ f(x,y)=100(y-x^2)^2+(1-x)^2 $$函数图像如下:它的一阶导数为:$$ \frac {\partial }{\partial y} f (x,y) = -200{x}^{2}+200y $$$$ \frac {\partial }{\partial x}f (x,y) =-400(-{x}^{2}+y)x-2+2x $$它的二阶导数(Hessian Matrix)为:$$ \left[ \begin {array}{cc} 1200{x}^{2}-400y+2 & -400x \\ -400x & 200\end {array} \right] $$当它取极值的时候它的一阶导数等于0。所以由\( \frac {\partial }{\partial y} f (x,y) =0 \) 可得 \( y=x^2 \)。代入\( \frac {\partial }{\partial x} f (x,y) =0 \)的式子中可解得它只有唯一解x=1,y=1。把(1,1)代入Hessian矩阵中得到$$ \left[ \begin {array}{cc} 802&-400 \\ -400&200 \end {array} \right] $$它是正定的。所以f(x,y)在(1,1)这一点取得极小值。等高线图如下:> with(plots); > contourplot(100*(-x^2+y)^2+(1-x)^2, x = -3 .. 3, y = -20 .. 20, contours = 20);当使用牛顿迭代法的时候需要用到Hessian矩阵的逆:> LinearAlgebra:-MatrixInverse( VectorCalculus:-Hessian(100*(-x^2+y)^2+(1-x)^2, [x, y]) );$$ H^{-1} = \left[ \begin {array}{cc} \frac{1}{2(200{x}^{2}-200y+1)}&{\frac {x}{2…

Spark的速度快是以丧失计算结果正确性为代价的

是的,Spark很快。但是它不保证它算出的值是对的,哪怕你要做的只是简单的整数累加。Spark最著名的一篇论文是:《Spark: Cluster Computing with Working Sets》。当你读它的时候你需要明白:文中代码不保证计算结果是正确的。具体来说,它的Logistic Regression的代码在map阶段用到了accumulator。下面解释为什么这么做是错误的。假设有这样一个简单的任务:input file的每一行是100个整数,要求竖着加下来例如:输入1 2 3 4 5 ... 100
1 2 3 4 5 ... 200
1 3 3 4 5 ... 100输出3 7 9 12 15 ... 400很简单,对吧?是个猪都会算。 在hadoop上这个问题可以通过Map reduce来解决。首先把输入文件分成N个大小相等的块。然后每个块输出一行100个整数,如 2 4 6 8 10 ... 200
然后reducer接收每个mapper的输出结果,累加起来得到最终结果。缺点是: 从mapper到reducer是需要DISK-IO及网络传输的。那么需要传输N*100个整数。当输入集的维数很大(每行有上百万个字节)的时候,很浪费。spark很巧妙的引入了accumulator的概念。同一台机器上所有的task的输出,会先在这个机器上进行本地汇总,然后再发给reducer。这样就不再是task数量*维数,而是机器数量*维数。会节省不少。具体来说,在做机器学习的时候,大家很习惯的用accumulator来做这样的计算。accumulator是被很careful设计的。比如,只有master节点能读取accumulator的值,worker节点不能。在“Performance and Scalability of Broadcast in Spark
”一文中,作者写到:“Accumulators can be defined for any type that has an “add” operation and a “zero” value. Due to their “add-only” semantics, they are easy to make fault-tolerant.” 。但真的是这样吗?并不是。accumulator如…

BFGS的笔记

Hessian矩阵:$$ G = \begin{bmatrix} \dfrac{\partial^2 f}{\partial x1^2} & \dfrac{\partial^2 f}{\partial x1,\partial x2} & \cdots & \dfrac{\partial^2 f}{\partial x1,\partial xn} \ \dfrac{\partial^2 f}{\partial x2,\partial x1} & \dfrac{\partial^2 f}{\partial x2^2} & \cdots & \dfrac{\partial^2 f}{\partial x2,\partial xn} \ \vdots & \vdots & \ddots & \vdots \ \dfrac{\partial^2 f}{\partial xn,\partial x1} & \dfrac{\partial^2 f}{\partial xn,\partial x2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix} $$最优化中的Quasi-Newton method是当f的二阶偏导矩阵Hessian matrix难以求出来的时候,用另一个矩阵B来代替Hessian矩阵。主要有两种方法:SR1和BFGS。这两种方法的主要区别是:SR1产生的是rank 1的矩阵,而BFGS产生的是rank 2的矩阵。SR1的全称是symmetric-rank-one。DFP令\( Bk \) 是Hessian矩阵\( Gk\) 的近似。那么BFP计算\( B_k \)的公式是$$ B{k+1} = (I - \frac{yk sk^T}{yk^T sk}Bk\frac{sk yk^T}{yk^T sk} + \frac{yk yk^T}{yk^T sk})$$它的逆矩阵\( Hk = Bk^{-1} \) 的递推公式是$$ H{k+1} = Hk - \frac{Hk yk yk^T Hk}{yk^T Hk yk} + \frac{sk sk^T}{yk^T s_k}$$BFG…

Logistic Regression笔记

图片
Logistic functionLogistic function是指满足这样的函数关系的一条曲线$$ y = \frac{1}{1+e^{-x}} , x \in R $$ 它又常被称为S型曲线。它有一个很好的特性是: \( y' = y(1-y) , max(y)=1 \)因为y的最大值是1,所以我们可以把1-y称作y的不饱和度。所以,y的增长速度和y成正比,和y的不饱和度成反比。举个例子,社会学上经常用Logistic function来估算人口增长。假设y是当前人口基数/环境所能容纳的上限。环境所能容纳的人数上限是固定值。显然人口基数越大,出生的孩子也就越多,人口增长也就越快。但是另一方面,人口越接近饱和,增长速度也就越慢。Logistic RegressionLogistic Regression本质上来讲就是利用极大似然法进行参数估计。Logistic Regression是假设某件事情发生的概率满足Logistic function的形式:$$ P(x) = \frac{1}{1+e^{-w \cdot x}} \quad w,x \in R^n $$其中x是特征向量(比如性别、年龄),在回归分析中被称为自变量。w是这些特征所对应的权重,是待估计参数。Logistic Regression的核心是给出Loss函数以及Loss函数的一阶导数的计算方式。即:对每一行训练数据x,都能计算出一个L(x)和L'(x)。前者是一个标量(实数),后者是一个向量。然后把这两个东西交给SGD、BFGS或CG等最优化方向去求解。LR模型本身是极为简单的,难点在后面如何求最优化的部分。Loss函数及其导数的推导过程如果我们引入随机变量y。用y=1代表该事件发生,y=0代表该事件不发生,那么$$ P(Y=y|x) = P(x)^y(1-P(x))^{1-y} = (\frac{1}{1+e^{-w \cdot x}})^y (1-\frac{1}{1+e^{-w \cdot x}})^{1-y} $$如果用\(x_i,y_i\)代表训练集中的第i行数据,把那么这些样本的联合分布概率为$$ \prod_{i=1}^{n}{P(Y=y_i|x_i)} = \prod_{i=1}{P_i^{y_i}(1-P_i)^{1-y_i}} $$\(P_i\)是\(P(Y…

Android M

图片
刚刚把我的9儿子升级到了Android M

Markdown的选择

我一直在思索用什么格式存储文档比较好。之前一直在用google docs,但是它的格式不公开,上传/下载的时候需要转换格式,转换的时候必然会丢失一些信息。于是后来想,那还是纯本文或者markdown吧。选型但是Markdown方言很多,选哪个好?我考察了以下三个。pandoc. John MacFarlane写的,万能的转换器。对我来说一个缺点是它的是Haskell语言。commonmark. 这是John MacFarlane搞的对markdown进行标准化的一场伟大尝试。他给出了C语言和js的实现,其中C语言的很容易在windows下编译过去,代码简单易懂。可惜,没人买账。GitHub Flavored Markdown. 这个大概是现在事实性的标准了。因为代码都托管在github上,所以写文档的时候自然也就顺着 github 的要求来。我没有找到它的开源实现。但是,atom.io是github公司的,而这个编辑器的markdown实现用的是marked. 我试了下还不错。Ghost markdown. 这是我现在所用的blog engine Ghost的markdown方言。它内部用的是showdownjs 这个库,然后自己写了一些扩展。语法高亮它是自己做了一些简单的字符串替换,生成Html5的code标签格式。但是html5的<code>标签目前没有浏览器去做高亮,所以还是得借助于在前端嵌入highlight.js这样的东西。markedmarked 用起来比较简单,可以传自己的highlight函数进去。比较容易和highlight.js配合。我用的时候比较头疼的是marked的换行功能非常有问题,请参见github上的issue 115. 2年多了,一直没人修。数学公式html header中再加上一行mathjax的js链接,就可以在markdown中支持数学公式了。 不过由于‘\’在markdown中是转义字符,所以写‘\’的时候要连写两个。Othershighlight.js既可以用在服务器端,也可以用在浏览器里。但是我更倾向于在服务器上使用,让client端更瘦一点。

我在Yahoo与ATS 九死一生的故事

图片
去年9月,我去Yahoo后领导交给我的第一件事,就是把Yahoo内部一个过时的、已经End-Of-Life的http server换成Apache Traffic Server(ATS)。这件事情就类似于把某网站的架构从apache+tomcat变成nginx+tomcat一样,可以说非常简单。我只管更改一下安装脚本,剩下的让运维工程师去线上操作就行了。Too easy!! 然而没想到遇坑无数,我悲惨的人生就此开始。详情见下文。100-continue导致响应慢请见这个jira https://issues.apache.org/jira/browse/TS-1125 的Description。调用我们服务的client service是使用C++基于libcurl实现的。而curl默认开启了一个很废柴的功能,就是当post body大于1k的时候,它会在Headers中加上"Expect: 100-Continue"。 当它收到100 continue的response header之后,它才会继续把body post过去。而ATS以及我们后端的App Server默认根本不理解这个东西,于是就导致curl一直卡在那里,等到timeout,然后才post body。解决方法: Yahoo的Feifei Cai在2014年4月提交了一个补丁,使得ATS能够识别"Expect: 100-Continue"。该补丁已经被merge进去了。我只需要在配置文件中打开proxy.config.http.send_100_continue_response,那么ATS就会自动回复100 continue。问题"似乎"解决了。其实如果我们能说服调用方修改下他们的代码,禁用掉curl的这个功能,那么不仅能降低相应延迟(因为能减少一个RTT),而且也没有100 continue的麻烦了。可惜,不能。本地端口耗尽很遗憾的是,ATS与我们的backend(即origin server)之间并不是长连接,每来一个请求就需要建立一个TCP连接,每建立一个TCP连接就需要占用一个端口,于是很快就遇上了本地端口耗尽的问题。 Linux默认的time wait是180秒,也就是说5万个端口只够应对每秒270个HTTP请求。这是一个非常常…

Bye, Yahoo

图片
Yahoo北京研发中心正式关闭了。3月31日是最后一天。所有不relocation到美国的同事,都在30日和31日办完了离职手续。 于是乎,我也要正式开始找工作了。

雅虎北京研发中心正式关闭,我被裁了

如新闻所说,雅虎北京研发中心正式宣布关闭。所以,我也……

DELL R410 C-states引发的严重性能问题

图片
最近刚发现了DELL R410的BIOS缺陷导致的一个严重性能问题。通过更改BIOS设置,这些机器的性能提高了50%。现象我们组有一套流处理系统,它接收事件,处理,再转给下一个。这是一个计算密集型的程序,瓶颈在CPU上。当它发现它的处理速度跟不上的时候,它就开始丢事件。于是我们就增加了机器数量,以期望解决问题。实际结果却是变得更糟了,事件丢失比例大幅增加。原因是publisher的事件分发采用的是roundrobin的策略,新加的这几台机器的性能明显弱于其它机器,于是它们就拼命丢事件。但是,所有这些机器的CPU都是一样的啊。最主要的区别是,旧机器是HP,新机器是DELL的。上面的线是DELL的机器,下面的是HP的。峰值的CPU使用率,DELL的比HP的几乎高一倍。空闲时大约高50%左右。于是我开始调查为什么DELL的机器会比HP的慢。然后在DELL的机器的启动时的dmesg中找到了这样一句话:"p4-clockmod: Warning: EST-capable CPU detected. The acpi-cpufreq module offers voltage scaling in addition to frequency scaling. You should use that instead of p4-clockmod, if possible."并且,DELL机器的/proc/cpuinfo和HP的相比,cpu flags中少了est这个flag。还有一个区别是:根据/proc/cpuinfo中的信息,DELL的机器的CPU始终是满频(2.4G Hz)运行。而HP的机器则是时高时低,空闲的CPU都运行在1.6GHz。DELL机器的cpuinfo我列在了下面:processor15vendor_idGenuineIntelcpu family6model44model nameIntel(R) Xeon(R) CPU E5620 @ 2.40GHzstepping2cpu MHz2394.035cache size12288 KBphysical id0siblings8core id10cpu cores4apicid21initial apicid21fpuyesfpu_exceptionyescpuid level11wpye…

长连接与负载均衡

长连接和负载均衡都是服务器端常用的技术,但是它们碰在一起的时候麻烦就出现了。下面以google的kubernetes举例,说说麻烦在哪里。kubernetes是一个管理docker集群的东西。部署在kubernetes上的每个服务(service)由一个或多个pod组成。每个pod都有一个独立的IP。kubernetes希望利用IP层的负载均衡技术,让每个服务都对应一个独立的IP。这样,当pod发生迁移或者伸缩的时候,对使用它的人是不可见的。我想说的是,这样做是有问题的。假设服务S由podA和podB两个pod组成。客户端使用了固定大小的连接池,到服务S有100个连接。然后突然,podB死掉了。于是对客户端来说,连接池的数量就降低到了50。由于50个连接不够用,所以很快,客户端就向podA新建了50个连接,把总连接数量补到了100。然后podB恢复了。但是对于客户端来说,因为100个连接已经够用了,所以podB收不到任何请求。简单的结论是:假如一个服务由多个副本组成,并且客户端使用了长连接,那么客户端必须知晓副本的数量,否则服务端负载就会不均衡。假如连接本身是无状态的(例如HTTP),那么可以加入一个中间代理来解决负载均衡的问题,从而降低client端的复杂度。所以就kubernetes来说,无论你是用flannel、skydns,还是其它什么策略。只要存在长连接,客户端就必须主动去查kubernetes API来获知pods的真实IP。这个耦合及依赖是必须存在的。

关于Replicated State Machines的一些笔记

当同一个数据存在多个副本的时候,怎么管理它们就成了问题。在Map-Reduce的场景下,数据都是一次写入永不更改,那么问题就变得非常简单,让每一份数据都有多个拷贝,然后处理好分发和读取的细节问题就行了。这些细节问题包括:所有的拷贝不能处于同样的环境下。这样单一环境的故障不至于引起所有拷贝都损坏。具体来说,如果你想容忍整个IDC的停机故障,那么就得让数据有跨IDC的副本。 读取的算法能容忍某些副本是坏的,它能检测数据的完整性,当遇到错误时,从其它副本位置重试 有一个监控程序能有效的检测数据完整性并为损坏的数据创建新的副本在上述场景下,因为数据都是只读的,所以没有一致性问题。这也是为什么Map-Reduce能这么流行这么备受推崇的原因之一。Replicated State Machines用于支持数据可被修改。比如分布式系统中的元数据信息。具体例如,一个分布式系统中,一个目录下有哪些文件。虽然文件本身可以做到一次写入永不修改,但是目录不可能。目录的内容总是动态变化的。Replicated State Machines(后面简称RSM)的最早提出是在图灵奖得主Leslie Lamport的著名论文"Time, clocks, and the ordering of events in a distributed system(1978)"论文中,比较系统性的阐述是在Fred Schneider的论文"Implementing fault-tolerant services using the state machine approach(1990)"中。Fred Schneider现在是Cornell大学计算机系主任。它的基本思想是一个分布式的RSM系统由很多个replica组成,每个replica是一个状态机,它的状态保存在一组状态变量中。状态机的状态通过并且只能通过外部命令(commands)来改变。比如你可以把MySQL服务器想像成一个状态机。它每接收到一条带修改功能的SQL语句(比如update/insert)就会改变它的状态。一组配置好replication的MySQL servers就是典型的RSM。RSM能够工作基于这样的假设:如果一些状态机具有相同的初始状态,并且他们接收到的命令也相同,处理这些命令的顺序也相同…

使用逻辑时钟重述paxos协议

Paxos是一个分布式选举协议,被广泛用在很多分布式系统中,比如Google的Chubby,MegaStore,Linux的Ceph。它的目的是为了让一群机器通过选举的方式达成一个一致性的决议。比如现在有5台MySQL服务器,它们要选举一个Master出来(无人工干预),所有的数据修改请求都发给这个Master,其它的做为Slave,以备在Master死掉后自动顶上去。Paxos协议将参与通信的主体分为两个角色:proposer和acceptor。分别各有多个。分布式选举协议的基本框架是:一个proposer提出一个提案,然后把这个提案发给所有的acceptor。acceptor可以选择接受或者拒绝这个提案。一个提案如果被过半数的acceptor接受,那么此提案被选中(chosen)。一个系统中可以同时有多个proposer提出多个提案,但是最终只能有一个被选中。并且应该至少有一个被选中。选举过程中机器可能crash掉,或者网络中断,机器一会儿死了一会儿活了。但是无论如何,只要死掉的机器数不过半,选举就应正常进行下去。Paxos协议是一个被公认的晦涩难懂的协议。但是今天突然发现,如果按照逻辑时钟的角度去阐述它,它就变得简单清晰了许多。下面介绍如何利用带逻辑时钟的RPC协议来实现Paxos。基于逻辑时钟的RPC协议为了让这套系统能正确运行,我们需要一个精确的时钟。由于操作系统的物理时钟经常是有偏差的,所以我们决定采用一个逻辑时钟。时钟的目的是给系统中发生的每一个事件编排一个序号。逻辑时钟可以利用全局计数器来实现。我们可以找一台机器提供一个全局的计数服务。它只支持一个方法:incrementAndGet()。这个方法的作用是将计数器的值加一,并且返回增加后的值。我们将这个计数器称为globalClock。globalClock的初始值为0。然后,系统中的每个其它机器,都有一个自己的localClock,它的初始值来自globalClock。假设机器和机器之间通过request-response这样的模式通讯。每条网络消息的类型要么是reqeust,要么是response。response又分为两种:OK和Rejected。我们规定无论什么类型的网络消息,都必须带有一个时间戳,时间戳取自这台机器的localClock。我们规定消息的接收方必须执行以下行为:if(mess…

挖了一些关于nodejs的八卦

TimelineNode.js诞生于2009年,它的初始作者是Ryan Dahl。他出生于美国加州San Diego,2009年时居住在德国,是一个自由职业者。在那时他创作了nodejs。在完成nodejs的初始开发并公之于众后,硅谷一家创业公司Joyent找到他并雇佣了他。Joyent给他发工资让他依然以100%的时间做自己原本喜欢做的事情(开发nodejs),一场愉快的交易。当时的CEO是David Young,CTO是Jason Hoffman。Joyent这个公司很难说清楚它到底是做什么的,因为它经历了数次转型和合并。
2011年,Isaac Z. Schlueter开发了nodejs的包管理工具npm,并于2011年11月将之合并到nodejs中。Isaac出生于美国康涅狄格州,曾就读于南康涅狄格州立大学,肄业。据他说他先是在Yahoo工作(2006/01 - 2010/01),然后辞职做了npm,然后受雇于Kakai了几个月(2010/04 - 2010/08),然后加入了Joyent(2010/09 - 2013/12)。据他声称npm恰好是他在换工作的间隙做的,于是版权属于他个人,不属于任何公司。但事实绝非如此,不细说了。
在2012年1月31日,Ryan Dahl公布他将nodejs的领导位置让位于Isaac Schlueter,然后Ryan Dahl就去纽约了,从此从网络上消失了。
2012年5月,Joyent当时的CEO David Young离开Joyent。11月,Henry Wasik接任CEO。
2013年9月,Jason Hoffman从CTO的位置上离职,去了Ericsson。Bryan Cantrill接任CTO。Bryan Cantrill当时刚30岁,加入Joyent 3年半。
2014年1月,负责管理nodejs的Isaac Schlueter离开了Joyent,创办了npm,Inc,并担任CEO。nodejs的管理工作由Timothy J Fontaine接任。而Fontaine刚加入Joyent不到1年。他于2013年2月加入Joyent,4月加入nodejs的核心贡献团队。
2014年6月,Joyent从思科请来了Scott Hammond作为新CEO,代替Henry Wasik。同时,TJ Fontaine 也宣…

Intel CPU的BUG导致reboot起不来

这个BUG是我去年11月撞见的,早该写出来了。因为这个BUG造成的灾难后果远远超出我的想像。当时的现象是某些机器重启后起不来,/var/log/message中有这样的信息:Nov 15 03:46:09 kernel: INFO: task sh:7684 blocked for more than 120 seconds.
Nov 15 03:46:09 kernel: "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
Nov 15 03:46:11 kernel: Call Trace:
Nov 15 03:46:11 kernel: [] ? ext4_file_open+0x0/0x130 [ext4]
Nov 15 03:46:11 kernel: [] schedule_timeout+0x215/0x2e0
Nov 15 03:46:12 kernel: [] ? nameidata_to_filp+0x54/0x70
Nov 15 03:46:12 kernel: [] ? cpumask_next_and+0x29/0x50
Nov 15 03:46:12 kernel: [] wait_for_common+0x123/0x180
Nov 15 03:46:12 kernel: [] ? default_wake_function+0x0/0x20
Nov 15 03:46:13 kernel: [] wait_for_completion+0x1d/0x20
Nov 15 03:46:13 kernel: [] sched_exec+0xdc/0xe0
Nov 15 03:46:13 kernel: [] do_execve+0xe0/0x2c0
Nov 15 03:46:13 kernel: [] sys_execve+0x4a/0x80
Nov 15 03:46:13 kernel: [] stub_execve+0x6a/0xc0 上网一查,发现这是一个已知的BUG, 请见 http://www.intel.com/content/dam/www/public/us/en/documents/specificat…

关于内嵌v8的一些性能测试

我写了个插件把google的javascript引擎v8嵌入到ATS中去,目的是希望以脚本的方式修改http请求。然后我刚刚在网上看见nginx的作者对v8的声讨:http://sysoev.ru/prog/v8.html 说为什么v8不适合嵌入到http server中(比如嵌入到nginx),其中一个理由是,创建一个V8 context需要2ms,那么一个单线程的http server每秒就最多只能处理500个请求,这样的结果简直不可接受。nginx的这篇文章是2010年写的,时过境迁,我刚做了下实验,发现并不属实。创建Context并不慢首先,v8中创建第一个context确实很慢。因为它需要初始化很多global的变量和函数。你想想看启动一个java的vm要多久,相比而下2ms算什么。请看下面这段代码:Isolate::Scope isolate_scope(isolate); HandleScope handle_scope(isolate); MESURE_TIME_BEGIN(create_context1) Local<Context> context = Context::New(isolate); Context::Scope context_scope(context); MESURE_TIME_END(create_context1) MESURE_TIME_BEGIN(create_context2) v8::Local<v8::Context> context2 = v8::Local<v8::Context>::New(isolate, context); Context::Scope context_scope2(context2); MESURE_TIME_END(create_context2) 第二个context是在第一个context的基础上创建的。在我的笔记本上测试:create_context1 time=28440968 nano secondscreate_context2 time=414 nano seconds也就是说创建一个新的context的时间小于1微秒。对于我的场景来说,我是在服务器启动、加载js代码的时候创建第一个co…

故障排查经历:负载高CPU低

今天我们一台服务器出了问题,负载异常高。正常情况下它的负载应该是0.5 -1.5左右,但是今天突然变成了5-6。我上去看,cpu很闲,IO也很少啊。没看出任何异常。为啥呢。后来用ps发现有几个进程始终处于uninterruptible sleep状态$ ps aux|grep power
root 23840 0.0 0.0 0 0 ? D Feb06 0:01 [power_saving/0]
root 23841 0.0 0.0 0 0 ? D Feb06 0:01 [power_saving/1]
root 23844 0.0 0.0 0 0 ? D Feb06 0:00 [power_saving/2]
root 23845 0.0 0.0 0 0 ? D Feb06 0:00 [power_saving/3]它们虽然不占CPU,但是会被记录到load中。恰好有4个进程,恰好比平时的负载大了4。但是它们是从哪来的呢? 我向运维工程师申请了查看/var/log/message的权限,发现Feb 6 01:48:03 xxx kernel: CPU5: Package power limit normal
Feb 6 01:48:03 xxx kernel: CPU17: Package power limit normal
Feb 6 01:48:03 xxx kernel: CPU23: Package power limit normal
Feb 6 01:50:25 xxx kernel: INFO: task kacpi_notify:179 blocked for more than 120 seconds.
Feb 6 01:50:25 xxx kernel: "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
Feb 6 01:50:25 xxx kernel: kacpi_notify D 0000000000000000 0 179 2 0x00000000
Feb 6 01:50:25 xxx kernel: ffff88032aa4db30 0000000000000046 0000000000000001 00000000000000…

排错经历:全局变量被多次析构

我们team有一套C++写的server程序,最近发现它在每次退出的时候会崩溃,core dump文件的栈如下:(gdb) bt
#0 0x0000003ea4e32925 in raise () from /lib64/libc.so.6
#1 0x0000003ea4e34105 in abort () from /lib64/libc.so.6
#2 0x0000003ea4e70837 in __libc_message () from /lib64/libc.so.6
#3 0x0000003ea4e76166 in malloc_printerr () from /lib64/libc.so.6
#4 0x0000003ea729d4c9 in std::basic_string\, std::allocator\ >::~basic_string() ()
from /usr/lib64/libstdc++.so.6
#5 0x0000003ea4e35e22 in exit () from /lib64/libc.so.6
#6 0x0000003ea4e1ed24 in __libc_start_main () from /lib64/libc.so.6
#7 0x0000000000400629 in _start ()下面介绍一下我是如何找到出问题的代码。请注意,因为编译器优化的缘故,这个栈是不完整的。安装完调试符号后,栈应该是这样:(gdb) bt
#0 0x0000003ea4e32925 in raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#1 0x0000003ea4e34105 in abort () at abort.c:92
#2 0x0000003ea4e70837 in __libc_message (do_abort=2, fmt=0x3ea4f58aa0 "*** glibc detected *** %s: %s: 0x%s ***\n")
at ../sysdeps/unix/sysv/linux/libc_fatal.c:198
#3 0x0000003ea4e76166 in …

最近与ATS Event有关的两个问题

ATS的Event真的是很复杂,太多了。最近遇到的两个比较严重的问题,都是因为在某个函数内收到了不该收到的Event。问题1: UnixNetVConnection::mainEvent收到了VC_EVENT_WRITE_COMPLETE这个我已经提了bug report https://issues.apache.org/jira/browse/TS-3289这是在启用了100 continue之后发现的,每次必定core dump.问题2: HttpSM::state_send_server_request_header收到了VC_EVENT_WRITE_READY我启用了某个inception插件,所以HttpSM::state_send_server_request_header这个函数并非是在给origin server发送request的时候调用,而是在inception插件处理了accept请求之后。所以HttpSM::state_send_server_request_header收到的应该只有VC_EVENT_WRITE_COMPLETE事件,不应该有VC_EVENT_WRITE_READY,因为这时候还未发生socket write操作。都先mark在这里,看我什么时候能找到原因。

ATS真是太复杂了

ATS是一个类似于squid的HTTP代理服务器,大约有30多万行C/C++代码,配置选项有数千个,极为复杂。这是一篇没什么意义的吐槽文。History1996年,UC Berkeley的一个教授Eric Brewer和他的学生一起成立了一个公司叫Inktomi。它本来是做搜索引擎的,后来敌不过Google,转而做web server的开发。然后大概在1997、1998年左右,它开发了一个很牛B的HTTP代理服务器,名字大概是叫Inktomi Traffic Server,准备和Cisco的Cache Director竞争,后来也败了。后来2002年,Inktomi被Yahoo以2亿美元收购了,Inktomi的Traffic Server就变成了Yahoo Traffic Server,简称YTS。YTS在Yahoo内部备受重用。根据Yahoo的公开数据,在2009年的时候,YTS已经每天处理170亿次请求,峰值带宽20Gb。在2009年Yahoo把YTS开源,交给Apache软件基金会(Apache Software Foundation,简称ASF)管理,成为该基金会的一个子项目。于是,YTS就被改名为ATS(Apache Traffic Server)。简单说就是:Inktomi Traffic Server(1998) -> Yahoo Traffic Server(2002) -> Apache Traffic Server(2009)这中间还有一个小插曲,在2006年的时候,Websense不知道怎么把Inktomi的Traffic Server拿去了,连名字都没改,直接集成到Websense的企业产品中拿出去卖。还有一个小细节,根据Yahoo的工程师Shih-Yong Wang在COSCUP 2010年会议上的演讲,YTS直到2010年了,都还不支持64位。作为一个cache server,这略微有点悲剧啊。即便在中国国内,那会儿都鲜有内存小于4G的机器上线了。根据公开资料,现在ATS在Yahoo已经有上万个主机节点,峰值带宽100Gb以上。功能单一,缺乏竞争力在我看来,ATS能打败的主力竞争者只有一个:Squid。因为Squid的是一个纯代理服务器,在功能上与ATS有很大重合。ATS不能Serve静态文件。这导致ATS后面得再挂一个ng…