Archive for category 技术点滴

ES-Hadoop 5.0 发布,支持 Storm 1.x.x

ElasticSearch-Hadoop 终于在上个月发布了 5.0 正式版,一个重大改变是支持了 Storm 1.x.x,而不再支持 Storm 0.9。工作的项目从两年前就开始使用 ES-Hadoop 将 Storm 输出的数据写入 ES,今年5月将 Storm 到 1.0 后,却发现 ES-Hadoop 不支持 Storm 1.0。自己动手丰衣足食,向官方提交了支持 Storm 1.0 的 pull request,现在随着 5.0 一起发布了😀

es-hadoop

囧,这个标题一开始写错了,所以 Release Notes 里也跟着错了。

https://www.elastic.co/guide/en/elasticsearch/hadoop/5.0/release-notes.html

https://github.com/elastic/elasticsearch-hadoop/pull/769

2 Comments

stormpy内存泄露问题分析

我们的项目中用到了storm,自9月26日起,我们的storm集群频繁出现集群宕掉甚至宕机的问题。

1、现象

storm集群的supervisor机器出现内存泄露,cpu打满,zk集群宕掉,storm nimbus宕掉的情况,严重的甚至出现服务器宕机。我们使用的是storm-0.9.2。

storm-cpu-mem

2、分析过程

2.1、定位出现问题的topology

通过修改python程序名称(我们使用了multilang)的方法,首先定位到出现mem增长的topology是oop,并且是python进程的mem、cpu占用很严重。

2.2、查看日志和增加内存主动回收代码

日志中并没有太多直接能表明mem和cpu增长的异常信息,通过搜索得知有人通过增加主动内存回收代码“解决”了问题,于是我们尝试相同的方法。然而这个方法并没有最终解决问题,反而造成了cpu消耗更多。比较有用的信息是pipe broken这个报错,表明可能是stdin或者stdout的问题。

2.3、转机

9月29日晚,借酒消愁。酒桌上我们再次讨论了这个问题,各自说了直觉中导致问题最可能的原因。我们提到了死循环中某个数据结构不断增长,提到了Java和python通信机制问题。

9月30日storm再次出现内存泄漏的问题,然而此次出现问题的topology是ssn,并且得知运行在线下的pts这个topology也曾出现过这个问题。我们意识到这是一个三个topology共有的问题,它们共有的部分是最可能有问题的——storm multilang python的官方库,storm.py——并且这部分代码中是有死循环的。

在猜想的同时,我们一边重新分析日志,希望能找到可能遗漏的线索,同时进行着另一些“尝试”。

2.4、出现曙光

十一期间storm再次出现问题,我们仍然没有找到问题的原因,之前的所有“尝试”都失败了。我们仍然严重怀疑问题出在storm.py。10月9日上午,我们查看了最新的storm.py代码,并同我们当前使用的storm.py进行diff,最新的代码发现有了不少改动,增加了一些异常处理等代码。我们把新代码上到了线下集群,期望它能有好的表现。下午,新topology抛出了和先前相同的异常,但是这次storm集群mem并没有出现泄漏,到这里我们更相信是storm.py出了问题,只是我们还没分析出内存泄漏点。

10月9日晚上,我们梳理了storm-0.9.3到storm-0.9.5的release log,将其修复的相关bug择了出来,对最有可能的STORM-351做了标记。

2.5、确定问题

10月10日上午,我们首先查看了STORM-351multilang python process fall into endless loop),在这个bug描述的提示下,内存泄漏问题的原因被我们找到了

stormpy

问题出现在readMsg()这个方法。Java进程退出后,python进程依然存在,此时sys.stdin关闭了。readline()返回NULL,line被赋值为空,不满足line == “end”的条件,循环没有退出,msg增加了一个字节”\n”,然后进入了死循环。msg不断增加,导致了内存泄漏。死循环同时导致了cpu被打满。

我们在测试中复现了这个现象。

2.6、其他问题解释

zk集群宕掉是因为zk和storm混布,内存被打满后,zk也挂掉,nimbus挂掉是因为zk挂掉了。

3、解决方案

STORM-351这个bug已经在storm-0.9.3中修复了,使用新的storm.py,并使用storm-0.9.3.jar或更新的jar包编译topology即可。

,

2 Comments

流量突降,升级rsyslog失败?

机房syslog日志服务器使用的rsyslog还在用v5,版本太低,需要升级到v8。

测试通过后先选了一个小机房进行升级,过程一切顺利,结果也正常。流量图很漂亮,两台syslog日志服务器做负载均衡,红线是升级了的服务器的流量。日志收发都正常。

 

今天下午继续升级,有三个机房没有负载均衡,单独拿出来处理。安装部署也没问题,该检查流量了。结果一看,IN流量掉了一截。没有负载均衡,按理应该升级瞬间流量掉为0,升级完成流量又恢复升级前的水平。等了一段时间,IN流量仍然没有恢复,进一步查看OUT流量也掉了一截,而且几乎降为0了,升级过的机房都表现成这样。

 

不应该啊,昨天晚上测的好好的,而且今天操作步骤又和昨天晚上一样,操作系统内核完全一样,为啥会出现这种情况!于是检查rsyslog进程和配置,都没有错。检查rsyslog接收日志情况,能接收日志,检查某一种日志的接收情况,没有数据丢失。去下游检查转发出去的某种日志,依然没有丢失。这时候IN和OUT流量依然没有恢复升级前水平,我认为升级失败了,于是回滚。回滚后IN和OUT流量恢复了。

至此有个问题不解:

为什么OUT流量陡降几乎为0了,去下游检查转发出去的某种日志却没有丢失的情况?这太矛盾了。

NO GHOST ONLINE!

以前从来没关注过OUT流量,为什么升级前OUT流量这么大?OUT流量主要就是转发到下游的日志,而且我确定这种日志非常少,绝不可能达到20Mbps。而且为什么升级后OUT流量陡降,回滚后立即复原?那一定是别的流量被干掉了,因为转发到下游的日志没有丢。

上机器抓包,发现出去的包绝大多数是dns请求,这是因为rsyslog配置了域名解析,所以升级后OUT流量被干掉的是dns流量!立马想到前些日子在读Rainer博客时读到的rsyslog v5的dns cache机制问题

Up until and including version 5 rsyslog does actually not implement a real DNS cache.
Starting with 6.3.1, I have now implemented a real, full-blown cache system which will resolve the issues with that use case.

v5的dns cache并不是一个真正的cache,所以仍然有大量的dns请求。然而从6.3.1开始,rsyslog实现了完整的dns cache,dns请求自然就少了。

这篇博客还提到v5的dns cache工作地很好,几乎没有用户抱怨。唯一不同的是udp流量,如果模板配置了域名解析而且有大量机器发送日志的话,就会有大量dns请求。——呵呵,no real pain.

They seem to work surprisingly well, as almost no real pain was reported by users in regard to this system. The big exception is UDP traffic, if combined with template options that require host resolution and a larger number of different hosts sendin messages.

这种问题只会在大流量时表现地很明显,所以昨天晚上升级的小流量机房没出现这个问题。其实再仔细看看那个流量图,小流量机房升级过后IN的流量也没有恢复到升级前的水平,只是差得不多,被忽略了。

那么IN的流量为什么也下降了呢?因为接收的dns应答包少了。

好吧,所以说升级没有失败,周一继续升完剩余的机房。

唔 = –

No Comments

vim7代码自动补全AutoComplPop

好久没写博客了:(

在公司机器上coding,只能是用vim了。一直感觉用着不爽,十分怀念VS下的Visual Assistant的代码自动补全。前几天新的项目又要开始coding,想着被称作“神器”的vim怎么会不能代码自动补全。Google一番,原来vim7就已经支持代码补全了,但还是用着不爽,因为需要按ctrl-n/ctrl-p,或者ctrl-x ctrl-o才会调出补全,而不是像Visual Assistant是边写边自动弹出的。继续折腾,就发现了标题中的自动补全插件AutoComplPop,呵,装上以后就跟VA差不多了!

安装方法:

1、下载AutoComplPop程序,是一个zip压缩包,主页点这里
2、解压缩,得到三个目录,autoload、doc和plugin;
3、复制三个目录下的文件到$VIMRUNTIME或$HOME/.vim同名目录下。

OK!享受vim代码自动补全吧!

问题:

1、虽然ACP的项目主页上说vim7.0就可以,但我试了下,7.0会报错,原因不详。在vim7.3下可以使用。
2、如果遇到 vim报错omnifunc未设置,可增加下面的代码到vimrc。

autocmd FileType python set omnifunc=pythoncomplete#Complete
autocmd FileType javascript set omnifunc=javascriptcomplete#CompleteJS
autocmd FileType html set omnifunc=htmlcomplete#CompleteTags
autocmd FileType css set omnifunc=csscomplete#CompleteCSS
autocmd FileType xml set omnifunc=xmlcomplete#CompleteTags
autocmd FileType php set omnifunc=phpcomplete#CompletePHP
autocmd FileType c set omnifunc=ccomplete#Complete

3、颜色啥的问题,自己配吧。

参考:

1、用Vim编程——配置与技巧
2、配置基于Vim的Python编程环境
3、[ Vim plugin ] AutoComplPop 安裝方式

3 Comments

编程珠玑,字字珠玑

Programming Pearls跌跌撞撞,连滚带爬地但还算仔细地读完了这本书,感觉身心愉悦、神清气爽,决定还要再度几遍。

首先,这本书的书名好,中文译名更好——《编程珠玑》,正如本书的风格,篇幅精悍短小,行文流畅优美,十五章的正文如十五颗熠熠生辉的珍珠,阐释着编程之道,没有一句话多余,也不必再增,果然字字珠玑。译者显然比我功力深许多,要是我,恐怕就直接译成珍珠了——过于直白,顿失优雅。

概览全书,共分15章,短的仅四五页,长的不过数十页,一本书薄薄200来页,似有K&R《C程序设计语言》一书风格。前十章介绍程序设计的基本原则和基本技能技术,后五章给出运用这些原则、技术的实际应用,“效率”是贯穿全书的主题。每一章开始提出有关本章主题的若干个问题,接下来详细分析,给出解决方案,章末还有总结和拓展习题。语言风格绝非教科书式的“周吴郑王”,更像是在讲故事,如作者在第一版跋中自问自答所述,“本书的章节侧重的是故事情节而不是定理和表格”。源码大多以接近C/C++伪代码写成,也有部分C/C++代码,这样将主要的注意力集中在算法和数据结构上,而不是规范的声明、接口,有些甚至略去了错误检查机制。边栏和深入阅读大大拓宽了读者的视野。

我觉得有必要按章来总结一下这本书。

第一章
开篇提出“怎样给一个磁盘的文件排序”的问题,阐述了正确定义和理解问题的重要性,这是程序设计的第一步。这一章回答了为什么要自己设计数据结构自己设计程序,而不用系统提供的功能。事实上,系统为我们提供了许多有用的程序功能,但是有时候因为一些原因,我们不能使用,更多的时候是因为效率问题,我们需要自己设计。

第二章
通过三个问题揭示算法给程序员带来的好处,一个精妙的算法在时空效率上给程序带来的好处。1.在海量数据中寻找缺失的某个数字;2.字符串的循环左移; 3.寻找“变位词”集合。在本书中第一次正式讲到了二分搜索和排序。

第三章
数据视图决定了我们在程序中应该采用什么样的数据结构,好的数据结构可以简化代码。

第四章
这是非常重要的一章,本章仔仔细细地讨论了二分搜索,从最初用伪代码表示二分搜索的思想,一点一点扩充完善代码,最终形成非常接近C代码的伪代码。后半部分使用程序验证技术讨论了上述代码的正确性,逻辑缜密。

第五章
将第四章的二分搜索的伪代码用C语言实现,使用断言对所实现的程序进行了测试,并介绍了一些测试和程序计时的方法。 第五章的第一条习题讨论了本书的编程风格。

第六章
讨论了程序性能分析,以一个实例讲述了在计算机系统的若干个设计层面上提高程序执行效率的方法,然后给出了系统化观点的总结。

第七章
这一章是有趣的估算。开篇讲述了一些估算的基本技巧,然后介绍了程序性能的估计等问题。

第八章
这一章可以看作是第二章的进一步讲解,突出了算法设计在程序设计中的重要地位。本章的问题是“求和最大的连续子序列”,这是今年淘宝实习生招聘研发类的一道笔试题。对这个问题,本章给出了4种不同的算法,从一个显而易见的算法开始,逐步优化,降低时间复杂度,最终得出最优算法,过程非常详细。

第九章
这一章讲的是代码调优。前半部分讲了四个问题的代码调优。1.整数取模;2.函数、宏和内联代码;3.顺序搜索;4.计算球面距离。后半部分对二分搜索进行了细致的代码调优,书中称之为“大手术”。

第十章
讨论了如何节省空间。前半部分以实例介绍了稀疏疏结构,后半部分给出了数据空间技术和代码空间技术,使用这些技术以节省存储空间和代码空间。

第十一章
这一章详细介绍了插入排序和快速排序,同样从最初简陋的代码逐步优化算法,并使用部分第九章介绍的代码调优技术对代码进行优化。

第十二章
讨论一个有趣的问题——生成随机数。本章给出了三种不同的解决方案。

第十三章
本章介绍了5种表示集合的重要数据结构——数组、链表、二叉搜索树、箱和位向量。对每一种数据结构的实现都做了详细的讲解,并对其性能进行了分析,同时提出了一些优化的方法。

第十四章
介绍了两个重要的数据结构——堆和优先级队列。后半部分介绍了堆排序。

第十五章
这一章围绕字符串进行了一些讨论,统计一本书中每个单词出现的次数,查找字符串中最长的重复子字符串以及随机生成文本,主要涉及的数据结构是散列表和“后缀数组”(字符指针数组)。章末再次讨论了关于使用库组件还是定制组件的问题,一些库组件通用性强,但效率不如定制的专用组件高;有些库组件是非常高效的。

最后说说我觉得这本书不足的地方。本书把习题提示和习题答案分开了,我觉得没有必要,这反而给读者带来了阅读困难,实际上某些习题提示已经非常接近最终答案了,而某些习题答案只是给出了提示性的语言,所以两部分合并起来为好,也方便阅读。本书一些章节的标题起的不好,这似乎和一个我非常赞赏的书名很矛盾,比如第十三章,章标题是“搜索”,而主要内容将的却是几种数据结构,虽然这章开始交代了本章内容有一个搜索问题引发,可我怎么也看不出那是一个搜索问题。前面有些章节的标题也不够好,看不出本章的内容到底是什么。个人见解,仅供参考。

2 Comments

关于字符串“循环左移”算法的讨论

问题:有一个长度为n的字符串,对其循环左移i位,就像这样,有字符串“abcdefg”,对其循环左移3位得到“defgabc”。使用什么样的算法实现?

这个问题是腾讯C/C++研发实习生的一个面试题。

我要说明一下,在这里我只是关注算法。在实现中,不考虑错误检测或者异常处理,也不考虑特殊的情况,比如i<0就是循环右移啊,i>n需要取模啊等等;也不计算每种算法实现都需要步骤的时间开销,比如字符串的初始化,事实上,为了简化代码,我就直接使用了string类型而不是char[ ],再比如求字符串的长度,就直接调用了字符串处理函数等等。做这么多简化,为的就是能更侧重算法本身。下面来看几种实现算法。

一、使用一个字节的额外空间开销

这种算法要经历i趟,每一趟把str[0]赋值给临时变量char t,剩余的字符向左移动一位,即str[k]=str[k+1],移动完成后把临时变量t赋值给str[n-1]。

//code in C++
string rotateLeft_1(string str,int i)
{
	char t;
	int strlen;
	strlen = str.length();
	for (int j=0;j<i;j++)
	{
		t = str[0];
		for (int k=0;k<strlen;k++)
		{
			str[k] = str[k+1];
		}
		str[strlen-1] = t;
	}
	return str;
}

这个算法虽然空间开销小,但是时间开销可大了去了,两层的嵌套循环,效率太低。有没有效率高一点的算法呢——废话,当然有!

二、使用n个字节的额外空间开销

减小时间开销的一个基本思想是以空间换时间。这个算法使用一个新的长度为n的字符串(字符数组)保存原始字符串的副本,然后对原始字符串的每个元素重新赋值。

//code in C++
string rotateLeft_2(string str,int i)
{
	int strlen;
	strlen = str.length();
	string t = new char[strlen];
	for (int j=0;j<strlen;j++)
	{
		t[j] = str[j];
	}
	for (j=0;j<strlen;j++)
	{
		str[j] = t[(j+i)%strlen];
	}
	return str;
}

这种算法要比第一种时间开销小,但是似乎空间上的开销过大了。

三、使用i个字节的额外空间开销

显而易见,上面的算法远非最佳算法,所以算法有在时空上取得双赢的改进的可能。第三种算法将字符串的前i个元素复制到一个临时字符串(字符数组)中,将原始字符串余下的n-i个元素左移i个位置,最后将最初的i个元素从临时字符串(字符数组)中复制到余下的位置。

//code in C++
string rotateLeft_3(string str,int i)
{
	string t = new char[i];
	int strlen = str.length();
	for (int j=0;j<i;j++)
	{
		t[j] = str[j];
	}
	for (j=i;j<strlen;j++)
	{
		str[j-i] = str[j];
	}
	for (j=strlen-i;j<strlen;j++)
	{
		str[j] = t[j-strlen+i];
	}
	return str;
}

这种算法看上去和第二种没太大差别,但无论从时间开销还是空间开销上来讲,都要比第二种好。原因在于虽然原始字符串中的每个位置都要发生变化,但没有必要花费n个字节的内存开销保存原始字符串的副本,只需保存前i个位置的元素。不过总觉得这种算法还不够好-_-!

四、使用一个字节额外空间开销的“杂技”算法

同样是使用一个字节的额外空间开销,但这种“有点像精巧的杂技动作”的算法的时间开销比第一种要小很多。首先把str[0]存到一个临时变量char t中,然后移动str[i]到str[0],str[2i]到str[i],……,直到遇到str[0](str的下标对n取模),将t赋值给刚才移动的最后一个位置。str中的每个元素都要进行移动,如果没有移动完,就从str[1]开始再次移动,直到所有的元素都已经移动了。

//code in C++
string rotateLeft_4(string str,int i)
{
	int strlen = str.length();
	char t;
	int count = 0;    //统计移动次数
	int j,k = 0;      //k初始化为0,从str[0]开始
	while (1)
	{
		t = str[k];         //开始的元素保存到临时变量t中
		j = (k+i) % strlen;
		while(j != k)       //开始移动,直到遇到开始的元素
		{
			str[(j-i+strlen) % strlen] = str[j];
			count++;    //移动次数统计量+1
			j = (j+i) % strlen;
		}
		str[(k-i+strlen) % strlen] = t;    //临时变量t中保存的值赋值给刚才移动的最后一个位置
		count++;
		if (count<strlen)    //判断是否所有元素都已经移动
		{
			k++;         //没有移动所有元素,再次从str[k+1]开始
		}
		else
		{
			break;       //所有元素都已经移动,跳出循环
		}
	}
	return str;
}

这个算法看起来就比较复杂,难怪说是“有点像精巧的杂技动作”,实现起来也要格外小心。

五、“翻手”算法

来看一个有趣的实现字符串循环左移的算法。在具体讲这种算法之前,先来看看线性代数里的转置。(AB)T等于什么?等于BTAT。那么(ATBTT等于什么?等于(BTT(ATT,即BA。

啊哈!我们用三个步骤就可以完成这个字符串的循环左移了。对于字符串来讲,转置在这里就是逆置。把原始字符串分成ab两部分,a是前i个元素,b是后n-i个元素,首先对a求逆,得到a-1b,然后对b求逆得到a-1b-1,然后对整体求逆得到(a-1b-1-1=ba。

下面这张图形象地说明了这种算法,这里是将一个长度为10的字符串循环左移5位。

//code in C++
string reverse(string str,int m,int n)
{
	char temp;
	while(m<n)
	{
		temp = str[m];
		str[m] = str[n];
		str[n] = temp;
		m++;
		n--;
	}
	return str;
}
string rotateLeft_5(string str,int i)
{
	int strlen = str.length();
	str = reverse(str,0,i-1);
	str = reverse(str,i,strlen-1);
	str = reverse(str,0,strlen-1);
	return str;
}

我写的代码有些丑陋。“翻手”算法的时空效率是比较高的。

另外来看一下使用python实现的算法。用python来处理字符串非常方便,尤其是分片,简直就是神器啊。(这里就不讨论时空效率了)

#code in python
#! /usr/bin/python
str = raw_input("Please input the string and i\n")
i = input()
str = (str[i-1::-1]+str[:i-1:-1])[::-1]
print str

这里将分片操作的最后一个参数置为-1,用作置逆。但这是不是多此一举呢?既然都有分片操作了,直接分片连接就行了,这似乎就没有设计算法的味道了。

#code in python
#! /usr/bin/python
str = raw_input("Please input the string and i\n")
i = input()
str = str[i:]+str[:i]
print str

上面五个算法里我认为最漂亮的是第五个算法,算法思想简洁优美,实现起来也不复杂,并且效率高,空间开销也小。

,

4 Comments