Impala:新一代开源大数据分析引擎

原文发表在《程序员》杂志2013年第8期,略有删改。

/ 耿益锋 陈冠诚

 大数据处理是云计算中非常重要的问题,自Google公司提出MapReduce分布式处理框架以来,以Hadoop为代表的开源软件受到越来越多公司的重视和青睐。以Hadoop为基础,之后的HBase,Hive,Pig等系统如雨后春笋般的加入了Hadoop的生态系统中。今天我们就来谈谈Hadoop系统中的一个新成员 – Impala。

Impala架构分析

Impala是Cloudera公司主导开发的新型查询系统,它提供SQL语义,能够查询存储在Hadoop的HDFS和HBase中的PB级大数据。已有的Hive系统虽然也提供了SQL语义,但是由于Hive底层执行使用的是MapReduce引擎,仍然是一个批处理过程,难以满足查询的交互性;相比之下,Impala的最大特点也是最大卖点就是它的快速。那么Impala如何实现大数据的快速查询呢?在回答这个问题之前,我们需要先介绍Google的Dremel系统[1],因为Impala最开始就是参照Dremel系统进行设计的。

 Dremel是Google的交互式数据分析系统,它构建于Google的GFS(Google File System)等系统之上,支撑了Google的数据分析服务BigQuery等诸多服务。Dremel的技术亮点主要有两个:一个是实现了嵌套型数据的列存储;二是使用了多层查询树,使得任务可以在数千个节点上的并行执行和聚合结果。列存储在关系型数据库中并不陌生,它可以减少查询时处理的数据量,有效的提升查询效率。Dremel的列存储的不同之处在于它针对的并不是传统的关系数据,而是针对嵌套结构的数据。Dremel可以将一条条的嵌套结构的记录转换成列存储形式,查询时根据查询条件读取需要的列,然后进行条件过滤,输出时再将列组装成嵌套结构的记录输出,记录的正向和反向转换都通过高效的状态机实现。另一方面,Dremel的多层查询树则借鉴了分布式搜索引擎的设计,查询树的根节点负责接收查询,并将查询分发到下一层节点,底层节点负责具体的数据读取和查询执行,然后将结果返回上层节点。关于Dremel技术实现上的更多信息,读者可以参阅[9]。

 Impala其实就是Hadoop的Dremel,Impala使用的列存储格式是Parquet。Parquet实现了Dremel中的列存储,未来还将支持Hive并添加字典编码,游程编码等功能。Impala的系统架构如图一所示。Impala使用了Hive 的SQL接口(包括SELECT,INSERT,Join等操作),但目前只实现了Hive的SQL语义的子集(例如尚未对UDF提供支持),表的元数据信息存储在Hive的Metastore中。StateStore是Impala的一个子服务,用来监控集群中各个节点的健康状况,提供节点注册,错误检测等功能。Impala在每个节点运行了一个后台服务impalad,impalad用来响应外部请求,并完成实际的查询处理。Impalad主要包含Query Planner,Query Coordinator和Query Exec Engine三个模块。QueryPalnner接收来自SQL APP和 ODBC的查询,然后将查询转换为许多子查询,Query Coordinator将这些子查询分发到各个节点上,由各个节点上的Query Exec Engine负责子查询的执行,最后返回子查询的结果,这些中间结果经过聚集之后最终返回给用户。

 图1

图1. Impala的系统架构图 [2]

在Cloudera的测试中,Impala的查询效率相比Hive,有数量级的提升。从技术角度上来看,Impala之所以能有好的性能,主要有如下几方面的原因:

 1) Impala不需要把中间结果写入磁盘,省掉了大量的I/O开销。

2) 省掉了MapReduce作业启动的开销。MapReduce启动task的速度是很慢的(默认每个心跳间隔是3秒钟),Impala直接通过相应的服务进程来进行作业调度,速度快了很多。

3) Impala完全抛弃了MapReduce这个不太适合做SQL查询的范式,而是像Dremel一样借鉴了MPP并行数据库的思想,从新另起炉灶,因此可以做更多的查询优化,从而能省掉不必要的shuffle,sort等开销;

4) 通过使用LLVM来统一编译运行时代码,避免了为支持通用编译而带来的不必要开销;

5) 用C++实现,做了很多有针对性的硬件优化,例如使用SSE指令;

6) 使用了支持Data locality的I/O调度机制,尽可能的将数据和计算分配在同一台机器上进行,减少了网络开销;

虽然Impala是参照Dremel来实现,但是Impala也有一些自己的特色,例如Impala不仅仅支持Parquet格式,同时也可以直接处理文本,SequenceFile等Hadoop中常用的文件格式。另外一个更关键的地方在于,Impala是开源的,再加上Cloudera在Hadoop领域的领导地位,其生态圈有很大可能会在将来快速成长。可以预见在不久的未来,Impala很可能像之前的Hadoop和Hive一样在大数据处理领域大展拳脚。Cloudera自己也说期待未来Impala能完全取代Hive。当然,用户从Hive上迁移到Impala上来是需要时间的,而且Impala也只是刚刚发布1.0版,虽然号称已经可以稳定的在生产环境上运行,但相信仍然有很多可改进的空间[7]。需要说明的是,Impala并不是用来取代已有的MapReduce系统,而是作为MapReduce的一个强力补充,总的来说Impala适合用来处理输出数据适中或比较小的查询,而对于大数据量的批处理任务,MapReduce依然是更好的选择。另外一个花边消息是,Cloudera里负责Impala的架构师Marcel Komacker就曾在Google负责过F1系统的查询引擎开发,可见Google确实为大数据的流行出钱出力J

Impala与Shark,Drill等的比较

开源组织Apache也发起了名为Drill的项目来实现Hadoop上的Dremel,目前该项目正在开发当中,相关的文档和代码还不多,可以说暂时还未对Impala构成足够的威胁[10]。从Quora上的问答来看,Cloudera有7-8名工程师全职在Impala项目上,而相比之下Drill目前的动作稍显迟钝。具体来说,截止到2012年10月底,Drill的代码库里实现了query parser, plan parser,及能对JSON格式的数据进行扫描的plan evaluator;而Impala同期已经有了一个比较完毕的分布式query execution引擎,并对HDFS和HBase上的数据读入,错误检测,INSERT的数据修改,LLVM动态翻译等都提供了支持。当然,Drill作为Apache的项目,从一开始就避免了某个vendor的一家独大,而且对所有Hadoop流行的发行版都会做相应的支持,不像Impala只支持Cloudera自己的发行版CDH。从长远来看,谁会占据上风还真不一定[10]。

除此之外,加州伯克利大学AMPLab也开发了名为Shark的大数据分析系统。在今天6月份的《程序员》上有一篇专门分析与Shark相关的Spark系统的文章,感兴趣的读者朋友可以参考。从长远目标来看,Shark想成为一个既支持大数据SQL查询,又能支持高级数据分析任务的一体化数据处理系统。从技术实现的角度上来看,Shark基于Scala语言的算子推导实现了良好的容错机制,因此对失败了的长任务和短任务都能从上一个“快照点”进行快速恢复。相比之下,Impala由于缺失足够强大的容错机制,其上运行的任务一旦失败就必须“从头来过”,这样的设计必然会在性能上有所缺失。而且Shark是把内存当作第一类的存储介质来做的系统设计,所以在处理速度上也会有一些优势[11]。实际上,AMPLab最近对Hive,Impala,Shark及Amazon采用的商业MPP数据库Redshift进行了一次对比试验,在Scan Query,Aggregation Query和Join Query三种类型的任务中对它们进行了比较。图2就是AMPLab报告中Aggregation Query的性能对比。在图中我们可以看到,商业版本的Redshift的性能是最好的, Impala和Shark则各有胜负,且两者都比Hive的性能高出了一大截。更多相关的实验结果读者朋友可以参考[12]。

图2

图2. Redshift,Impala,Shark与Hive的Aggregation Query性能对比 [12]

以笔者愚见,其实对大数据分析的项目来说,技术往往不是最关键的。例如Hadoop中的MapReduce和HDFS都是源于Google,原创性较少。事实上,开源项目的生态圈,社区,发展速度等,往往在很大程度上会影响Impala和Shark等开源大数据分析系统的发展。就像Cloudera一开始就决定会把Impala开源,以期望利用开源社区的力量来推广这个产品;Shark也是一开始就开源了出来,更不用说Apache的Drill更是如此。说到底还是谁的生态系统更强的问题。技术上一时的领先并不足以保证项目的最终成功。虽然最后那一款产品会成为事实上的标准还很难说,但是,我们唯一可以确定并坚信的一点是,大数据分析将随着新技术的不断推陈出新而不断普及开来,这对用户永远都是一件幸事。举个例子,如果读者注意过下一代Hadoop(YARN)的发展的话就会发现,其实YARN已经支持MapReduce之外的计算范式(例如Shark,Impala等),因此将来Hadoop将可能作为一个兼容并包的大平台存在,在其上提供各种各样的数据处理技术,有应对秒量级查询的,有应对大数据批处理的,各种功能应有尽有,满足用户各方面的需求。

未来展望

其实除了Impala,Shark,Drill这样的开源方案外,像Oracle,EMC等传统厂商也没在坐以待毙等着自己的市场被开源软件侵吞。像EMC就推出了HAWQ系统,并号称其性能比之Impala快上十几倍,而前面提到的Amazon的Redshift也提供了比Impala更好的性能。虽然说开源软件因为其强大的成本优势而拥有极其强大的力量,但是传统数据库厂商仍会尝试推出性能、稳定性、维护服务等指标上更加强大的产品与之进行差异化竞争,并同时参与开源社区、借力开源软件来丰富自己的产品线、提升自己的竞争力,并通过更多的高附加值服务来满足某些消费者需求。毕竟,这些厂商往往已在并行数据库等传统领域积累了大量的技术和经验,这些底蕴还是非常深厚的。甚至现在还有像NuoDB(一个创业公司)这样号称即支持ACID,又有Scalability的NewSQL系统出来。总的来看,未来的大数据分析技术将会变得越来越成熟、越来越便宜、越来越易用;相应的,用户将会更容易更方便地从自己的大数据中挖掘出有价值的商业信息。

参考资料

[1]http://research.google.com/pubs/pub36632.html

[2]http://blog.cloudera.com/blog/2012/10/cloudera-impala-real-time-queries-in-apache-hadoop-for-real/

[3]http://www.slideshare.net/cloudera/data-science-on-hadoop

[4] Impala重点问题列表:http://yuntai.1kapp.com/?p=1089

[5] Hive原理与不足:http://www.ccplat.com/?p=1035

[6] Impala/Hive现状分析与前景展望:http://yanbohappy.sinaapp.com/?p=220

[7] What’s next for Cloudera Impala: http://blog.cloudera.com/blog/2012/12/whats-next-for-cloudera-impala/

[8] MapReduce:一个巨大的倒退:http://t.cn/zQLFnWs

[9] Google Dremel 原理 — 如何能3秒分析1PB:http://www.yankay.com/google-dremel-rationale/

[10] Isn’t Cloudera Impala doing the same job as Apache Drill incubator project? http://www.quora.com/Cloudera-Impala/Isnt-Cloudera-Impala-doing-the-same-job-as-Apache-Drill-incubator-project

[11] Shark:https://github.com/amplab/shark/wiki

[12] Big Data Benchmark: https://amplab.cs.berkeley.edu/benchmark/

[13] Impala wiki:http://dirlt.com/impala.html

[14]How does Impala compare to Shark: http://www.quora.com/Apache-Hadoop/How-does-Impala-compare-to-Shark

[15] EMC讲解Hawq SQL性能:左手Hive右手Impala: http://stor-age.zdnet.com.cn/stor-age/2013/0308/2147607.shtml

作者简介

耿益锋,清华大学计算机系博士研究生,主要研究方向包括大数据处理和云计算中新应用和新场景下分布式系统的设计和优化。

陈冠诚,IBM中国研究院研究员,主要技术方向为大规模分布式系统中的软硬件协同设计。个人博客为并行实验室(www.parallellabs.com),新浪微博@冠诚

Impala与Stinger对比

Tez和Impala现在竞争非常激烈,前者走的是基于DAG的精细化管理,后者是基于MPP的技术架构重头开始造了一个C++版本的SQL引擎。截止到2013年7月,Hortonworks的Stinger(Hive 0.11 + Tez)还是比Impala慢不少,毕竟Impala的动作更早一些。Hortonworks跟Cloudera这场硬仗干的真是激烈啊。

与大家分享三个演讲(墙外),一个是Impala与Stinger的对比,一个是Stinger的核心-Tez的介绍,一个是Impala跟微策略合作的情况。

Git快速学习指南

写在前面的话

学习是一个永无止境的过程,举个例子,学习“学习的方法”是一个不断迭代的过程:随着个人经历、周围环境的变化,我们的学习方法也需要作相应的改变。在学生时代,如果想要学习新知识,最常做的很可能是买一本这个领域的经典著作,然后啃下去。这种方法优点是学的扎实,对概念的来龙去脉能理解的比较深刻,缺点嘛也很明显,费时费力,需要很多一大段的、不被打扰的时间,学生时代最适合这种方法。

工作之后,因为惯性使然,我还经常继续使用这种方法,结果因为很难抽出大块时间深入学习某项知识,所以收效甚微。这样一个痛点,作为爱折腾点新东西的人,当然是要想办法从“方法论”上做改进。痛定思痛,仔细思考后,我决定拿Git的学习过程做一个实验,来摸索一个适合(已上班的)程序员的学习方法的最佳实践。

对Git这样的工具,最终目的一定是用到实际项目中去。所以大致原则是:不要太深入理论(知道Git是个分布式版本控制系统就OK),然后找一个能直接上手的教程,learn by doing。

具体步骤

1)先在Code shool上了一节Try Git,交互式的网页教程,直接边看文字教材边在网页terminal里面敲命令,基本学完之后堆Git最基本的几个命令比较熟了。
2)gitimmersion.googol.im的教程,目前正在学习中,内容比Try Git全面,作为进一步提高用,一步一步跟着做就行。
3)优才网的Git视频教程,目前还没开始练。

most popular antidepressant with least side effects To be continued.

与Google拼音的工程师聊聊中文滑行输入

前一阵子Google拼音输入法加入了中文滑行输入功能,我因为去年和同事一起发过一个输入法的专利,对输入法的创新比较感兴趣,所以第一时间体验了一番。于是就有了与Google负责拼音输入法的@秃秃哥 同学的一番对话。

http://www.weibo.com/2149547674/zBlOmd9kJ#_rnd1372946523209

@冠诚:装了,但感觉輸中文还是没有九宫格好用 输入法的极致是实现盲打 我觉得目前的实现离这个目标还是差很多的 倒是flskey这个盲打输入法比较有意思 谷歌工程师可以参考下 合格的工程师一定会看到我这条评论的 呵呵 加油 争取变改进型创新为革命型 毕竟改变用户长久的九宫格习惯需要更大的力量

can i take ciprofloxacin for ear infection 果然@秃秃哥 同学开始回复我这个微博,我俩就此开始交互:

@秃秃哥:谷歌全键盘的智能纠错已经可以支持一定程度的盲打了,你不妨试试。

@冠诚:回复@秃秃哥九宫格也可以盲打啊,跟九宫格比,滑行盲打的准确度能提升一倍吗?如果不能的话,凭什么去吸引那么多的用户去改变输入习惯?滑行之所以能在英文输入上火起来,是因为老外不幸的没有九宫格。[嘻嘻]

@冠诚:回复@秃秃哥九宫格的键比滑行要大很多,所以它实现盲打很容易。如果稍微观察下现在的年轻人,他们九宫格打字应该很快的。尤其是在手机上。平板上滑行的发展空间会更大些。但是你去搜下各种论坛,很多人还在求平板上的九宫格。说白了,还是要先找用户的痛点,再去考虑算法技术实现等。

秃秃哥:回复@冠诚:谷歌拼音在平板上的九宫格你有没有试过啊?给点建议呗。

冠诚:回复@秃秃哥:你说的是平板上的滑行输入吧? 手上只有ipad sorry 啊。其实,我觉得吧,要有一个能在中文盲打效率上比九宫格好两倍以上才能让用户改变输入习惯,而且这个改变还要很长时间,例如从年轻的刚入网的用户开始培养比较容易。那么这个问题就变成,九宫格在平板上有多弱?能被提升两倍吗?

秃秃哥:回复@冠诚:不是滑行啊。我是说谷歌拼音在平板上的九宫格键盘是特殊设计的布局。

秃秃哥:回复@冠诚:我们并不是要改变用户的使用习惯啊。九宫格用户还应该继续使用九宫格。滑行输入是给全键盘用户准备的。全键盘用户比九宫格用户还是多的。另外,我们的九宫格键盘也是优化了的。

冠诚:回复@秃秃哥:那就要做市场调研,看看不用九宫格做中文输入法的用户有多少,然后在看看滑行中文比非九宫格的中文输入快到两倍没?如果有市场,有提升,那就有机会。先把这帮人转到滑行上来,再去跟九宫格死磕。

秃秃哥:回复@冠诚:哎呀,哪儿那么麻烦呀。九宫格和全键盘两个用户群其实重叠很小的,他们之间是很难转换的。我们的目标就是让他们都可以快速舒服的输入。

冠诚:回复@秃秃哥:恩,我是想从创造新business角度来考虑输入法创新的,可能跟你不太一样。所以我才那么关注效率的成倍提升和用户习惯。就像当年的搜狗拼音一样的质变。这样影响力才大。只是量产的话可能竞争壁垒比较低一点,影响力也小一些。可能输入法确实坑小一些,用户的使用习惯也千差万别。

此时@xcv58_ 同学也开始加入:

@xcv58_:回复@冠诚:想创造新的Business 就应该思考如何让人们离开输入法也能交流。

冠诚:回复@xcv58_:是的,所以新business是语音输入,甚至智能助手,贴心小秘书,能直接自动理解你的意图,google now啥的路数。未来就是直接”一个眼神,我就懂了你”。更极客点那就直接读懂脑电波。

秃秃哥:回复@冠诚:输入法领域用户习惯是非常难以改变的。你看看qwerty那么低效的键盘,还不是活了快一个世纪了。那么多创新的高效的键盘设计,没一个能取代的了的。我们的创新就是要在不对用户习惯做彻底变革的前提下一小步一小步的提升输入效率,降低学习难度。全键盘拼音滑行输入就是一个有益的尝试。

冠诚:回复@秃秃哥:完全同意,而且确实帮到了全键盘用户。[呵呵]

然后,@触宝 同学也来凑了这条微博的热闹:

触宝:亲也可以试试触宝输入法哇,不仅支持中文的简全拼和整句滑行输入外,同时支持英文滑行输入哇~

buy doxycycline online UK – 分割线 –

总结:微博果然是了解用户需求,与用户交流并收集反馈的好工具。

仰望星空 脚踏实地

最近连续跟IBM的一位VP和一位Fellow有过交流,对“仰望星空,脚踏实地”有了一些新的体会,特在此分享。

仰望星空

讲的是你做事情的vision,或者是说你的动机。作为一名研究员来讲,最兴奋最幸福的事情莫过于对社会产生巨大的影响。IBM Fellow Chieko Asakawa(浅川智惠子)是无障碍设计领域的杰出研究人员,她领导了IBM于1997年专为盲人设计的语音浏览器Homepage Reader等一系列产品,而浅川院士本身就是一位盲人。在1997年互联网还没有很普及的时候,根据自己的需求研发了这样一款产品,不得不佩服她敏锐的技术触觉。但是最关键的是她长期以来对技术的vision。她的目标很简单:利用计算技术帮助盲人(及其他残障人士)更好地接触数字信息和社会环境,她说这是她的dream。跟那位VP的聊天中谈到技术项目的评估第一步往往要看它的vision是什么。其实不管是研究还是开发,第一步往往是要讲清楚你要做的这件事情的vision是什么,通过你要做的事情你改变了什么?你解决了什么问题?这件事情能不能使听众一听就觉得很买账?可以说vision好不好直接决定两件事情: http://premiumflooringsolutions.co.uk/?p=buy-50-mg-luvox-tablets-cheap 你自己是不是很兴奋的要去做这件事情 以及你能从你的听众那里得到多少支持(可以是你的老板,你的投资人)。IBM CRL领导过两个IBM Research全球的研究项目:Wireless Network Cloud(无线网络云)和Internet of Things(物联网),一个是用软件来实现传统硬件基站的功能,一个是将物理世界和数字世界连接起来。Facebook,Google,Apple,Cloud Computing,Software Defined Network,Mobile,Big Data,Social,Virtualization这些名词背后你都能找到一个很鼓舞人的vision。想vision的时候一个重要原则就是make a difference。这件事情为什么只有在IBM能干成?为什么别人干不了?你有啥资源和优势是别人不可能达到的?你的技术背景是否足够强大?关系人脉如何?你干的这事情是“锦上添花”还是“雪中送炭”?锦上添花的事情意义就很小了,没啥做的必要。雪中送炭就是一个从无到有的过程,干成了得到的满足感肯定是无以伦比的,而且影响力也会很大。一句俗话就是:“心有多大,舞台就有多大”。郭去疾受World is flat的启发去做兰亭集市就是一个例子。Coursera正在改变教育的普及度,改变就放生在你身边。要敢于Think Big。除此之外,另一个原则就是understanding how the world works。这个话题可以讲的很深,但关键一点就是说你如果想预测未来什么是重要的,你可以从历史中学习那些重要的事情到底是怎么变得那么重要的?

脚踏实地

讲的是执行。要做好一件事情,一定要坚持。你必须一步一步,从小事做起,积跬步以至千里,而走完这个千里可能需要十年甚至三十年时间。在中国,很普遍的一件事情是你的目标很容易动摇,很容易被社会的现实因素所动摇,例如房子,例如钱。不得不说取得巨大成功的人还是很有些理想主义的dreamer,例如马云,例如扎克伯格。浅川在IBM工作了28年评上IBM Fellow,我导师Per Stenstrom 20年才评上ACM/IEEE Fellow,高德纳写Tex断断续续用了10年,VMware在成长为今天这个规模之前蛰伏了好几年,DARPA资助的众多研究项目周期长达十年,成为了一个领域的专家需要10000个小时的训练,等等。小步快跑,快速修正,不断迭代,错了就改,失败了就再来,反复锤炼。顶级会议的论文要花大量工作,反复修改才会被录取(CRL最近中的一篇ISCA是六个人近一年的工作);顶级研究项目会遇到众多困难 和挑战。让人惊叹的成就大都是一路风雨走过来的。深入深入在深入,多想想你做这件事情怎样才能make a difference?你要做的很平庸,那你不就是个随便都可以被替代的人了么,干嘛非得让你来做?你创造了什么别人创造不了的价值?多想想这些问题,耐得住寂寞,好好干。国人在执行层面一般都很强大,但是vision比外国人确实弱不少。

最后分享下我的一点心得:

想到一个问题: 不应该在意结果,而应该注重过程,因为正是在过程中你才得到了快乐,得到了体验。与过程相比,结果是好是坏其实远不那么重要。太关注结果,很容易失去活着的意义,因为等你历经艰辛得到那个结果的时候,你却什么都没得到。结果导向很容易让自己生活的不快乐,也不能让身边的人快乐。结果只是一些点,得到了也就过去了,而过程才是真正需要我们仔细享受的,因为它才是用我们的生命中最宝贵的时间换来的。想起一个终极问题:人活着为了什么?现在我的答案是:“为了尽情的体会生命的美好”

记一次诡异的Debug经历

Debug需要有刨根问底和百折不挠的精神。曙光往往在你被折磨的体无完肤之时出现,顿时你觉得整个世界都是光明的。

最近有两次难忘的Debug经历。一次是由于系统重装了OS,某些系统配置变化了,导致Hadoop上的Terasort跑不通。问题的表面现象表现为,该节点/home所挂载的磁盘在Terasort运行时出现大量I/O操作,而不是hadoop真正写data的分区/data,从而极大影响性能。本来如果正常的话,该节点的/home分区是不会出现I/O的。用iotop等工具只能看到Hadoop的JVM对/home分区造成了巨大的I/O操作,但是究竟为何这些JVM会对/home而不是/data做大量操作?这到底是哪个配置的错误造成的?牵涉到这种reasoning的debug,好像还没有很好的工具能帮上忙。最后解决这个bug是通过不断调整Terasort的参数,不断试错发现的:在一次关闭JVM Huge Page后的测试时Terasort就能正常运行,从而锁定HugePage的相关设定,最后发现是因为重装系统后该用户名的group id变了,所以被allocate的HugePage并不能被该用户的JVM所使用,从而导致内存不足进而产生大量swap,才会出现/home目录大量I/O的情形。

第二次是在集群上测试是发现一台节点CPU会有很异常的WAIT时间。用sysbench进行file I/O测试能复现这个bug。既然CPU有wait,那么很可能是disk有问题。用nmon分析了该机器的磁盘组的lvm数据后发现/dev/sdb设备有故障,会出现只有这个设备I/O busy而其它LVM里面的磁盘却空闲的情形。之后把该磁盘从LVM中删除,重做RAID 0,搞定了这个bug。

下一代大数据分析技术

原文发表于《程序员》杂志2013年第2期.

文 / 陈冠诚

随着以Hadoop为代表的大数据分析技术的普及,大数据的商业价值得到深入挖掘,并开始在互联网、零售、医疗、物联网等多个行业里成为商业变革的主导力量。Facebook最近就发布了名为Graph Search的新型社交搜索产品,基于海量的社交关系网络及“Likes”行为数据,为用户提供个性化的社交搜索服务,该产品被认为将是Google搜索业务的重要竞争对手。在电子商务领域,淘宝的数据魔方就是一个基于大数据分析的典型产品。数据魔方基于淘宝所掌握的大量消费数据提供各种各样的分析服务,例如展示消费者的购物习惯,地域分布,年龄分布,热销排名等,为淘宝卖家提供了非常有价值的分析数据。然而,这些现有的大数据分析技术处理的主要对象仍集中于文本数据,例如社交图谱,搜索关键字,商品数目,店铺、商品浏览记录,成交、收藏、评价记录等等,却没有涵盖一类非常重要的数据:多媒体。

实际上,多媒体数据的数据不仅规模远远超过文本数据,其商业价值也毫不逊色。以全球流量最大的网站Youtube为例,它在07年一年所消耗的网络带宽就等同于整个互联网在2000年的全部流量。另一方面,多媒体数据的来源也是异常丰富。仅以手机为例,手机的摄像头、麦克风可以产生丰富的图像、视频、语音数据。除此之外,社会中的各种监控摄像设备、医疗图像设备、物联网传感设备、卫星图像等都能产生大量的图像、视频数据。而多媒体相对于文本数据更有其得天独厚的优势:丰富的多媒体数据对人的感官刺激远胜过纯文本数据。以新浪微博为例,微博中被大量关注和转发的微博大都含有图片、视频等链接;相反,纯文字的微博受关注的程度还是会差不少。同样,微信以语音作为主要的信息载体,一举与纯文本的短信形成差异化竞争优势,再加上产品的社交因素而一炮走红,现在大家经常能在街上看见与手机上的微信好友对话的用户。在零售行业,基于图像的大数据分析也将打开一片新的市场。例如在一个大型的购物中心,我们可以对人流的视频数据进行分析,从而对消费者的购物习惯、逛街顺序等信息进行充分挖掘,从而有针对性地设计相应的促销方案、货架摆放规律等等。在安防行业,基于对视频数据的实时分析,我们可以监控潜在的安全隐患(例如检测出消防通道被占用需要及时清理),大大提升安全措施的响应时间。可以预见,基于多媒体数据的大数据分析将对互联网、零售、安防、生物医药等在内的众多领域发挥重要的作用。

在笔者看来,基于多媒体数据的大数据分析主要的技术难点就在于数据量和算法复杂度大大增加。Google在2012年有一项曾引起广泛关注的研究成果:他们使用了一千台电脑的一点六万颗处理器核组建了一个机器学习神经网络,花了三天时间用来自Youtube中截取的1000万幅图像来训练该神经网络,从而使得该网络可以自主学习并形成了“猫”这个概念,最终成功地识别出猫的图像。从这个例子中我们可以看到,要对海量图像、视频进行分析所需要的机器规模确实对计算资源和软件算法提出了极大挑战。好在视频、图像、语音处理并不是一个什么崭新的领域,这些方向都有很多的技术积累。笔者认为,真正的挑战可能在于如何将现有的多媒体处理技术扩展到大规模数据上去,毕竟对小规模数据有效的算法可能在处理超大规模的数据时会遇到从未有过的挑战。但是笔者也相信,基于多媒体数据的分析技术也一定会在未来得到蓬勃发展,并为用户创造新的价值。

多核与异步并行

我们在设计多线程程序时往往有很多性能指标,例如低延迟(latency),高吞吐量(throughput),高响应度(responsiveness)等。随着多核处理器上CPU核数的日益增加,如何高效地利用这些计算资源以满足这些设计目标变得越来越重要。这次向大家介绍的异步并行就是一种帮助实现低延迟、高吞吐量和高响应度的并行编程技术。

原文发表于《程序员》杂志2012年第9期,文字略有修改。

我们在设计多线程程序时往往有很多性能指标,例如低延迟(latency),高吞吐量(throughput),高响应度(responsiveness)等。随着多核处理器上CPU核数的日益增加,如何高效地利用这些计算资源以满足这些设计目标变得越来越重要。这次向大家介绍的异步并行就是一种帮助实现低延迟、高吞吐量和高响应度的并行编程技术。

让我们先来看这样一个例子。在下面的程序中,我们有一个do_something()的API,这个函数实现了将一个文件写入磁盘的功能,所以改函数比较耗时。在调用这个函数时,最简单的用法是对该函数进行同步调用,即下面程序中caller1()所采用的方式。这种写法带来的问题是,caller1需要阻塞等待do_something()的完成,期间CPU不能做任何其他的计算,从而导致CPU资源的空闲。与此相反,程序中的caller2就采用了异步调用do_something()的方式。这样,caller2在将异步调用do_something的命令发送给worker线程之后,就可以立刻返回并开始执行other_work(),不仅能将other_work()提前完成,更提高了CPU利用率。

int do_something(doc)
{
    return write_document(doc); // 耗时的I/O写操作
}

void caller1(doc) {
   result = do_something(doc); //同步调用do_something()
   other_work(); //这个操作需要等待do_something()的完成
   more_other_work();
}
void caller2() {
   worker.send(do_something_msg());//异步调用do_something()
   other_work(); //这个操作不需要等待do_something()的完成,因此提高了CPU的利用率
   more_other_work();
}

在现代计算机体系结构中,I/O设备的速度远远比不上CPU,我们在做计算时一个基本的设计原则就是在CPU等待I/O请求的同时,用足够多的计算任务将CPU跑满,从而掩盖掉I/O请求造成的延迟。在单核时代,我们使用Multiplexing的方式将I/O任务与计算任务重叠在一起进而提高程序性能,即一个进程如果进入I/O等待,操作系统会将该进程放入等待队列,并调度执行另一个进程的计算任务;多核时代来临之后,CPU上的计算资源变得越来越多,通过使用异步并行技术充分利用CPU的计算资源,提升应用程序的延迟性、吞吐量、响应度也变得越来越普遍。下面让我们通过几个典型应用来对异步并行做更多的介绍。

GUI线程的异步并行设计

GUI线程是采用异步并行设计来提高响应度的一个经典例子。一个GUI程序的典型结构是使用一个循环来处理诸如用户点击了某个按钮、系统产生了一个中断等事件。许多GUI系统还提供了诸如优先级队列等数据结构以保证优先级高的事件能得到及时的相应。下例是一个典型的GUI系统伪代码:

while( message = queue.receive() ) {
  if( it is a "保存文件" request ) {
    save_document(); // 这是一个会产生阻塞的同步调用
  }
  else if( it's a "打印文档" request ) {
    print_document(); // 这是一个会产生阻塞的同步调用
  }
else
  ...
}

这个程序有一个非常常见的性能bug:它对save_document()和print_document()这两个非常耗时的操作采用了同步调用的方式,这与GUI线程应该具备及时响应的设计初衷产生了直接矛盾。GUI线程的设计目标不仅仅是对相应的事件作出正确的响应,更重要的是这些响应必须非常及时。按照上面这个程序的逻辑,很可能会出现如下情况:用户在点击“保存文件”按钮之后,程序需要花费几秒钟才能完成save_document()调用,因此该程序在这几秒钟时间内都不能再对其他任何事件作出响应;而这时如果用户还想要调整窗口大小,这个操作在几秒钟之内都得不到响应,从而破坏用户体验。

一般来说,需要拥有高响应度的线程不应该直接执行可能带来延迟或阻塞的操作。可能带来延迟或阻塞的操作不仅仅包括保存文件、打印文件,还包括请求互斥锁、等待其他线程某个操作的完成等。

我们有三种方式来将耗时的操作从需要保持高响应度的线程中转移出去。下面让我们继续用GUI系统的例子来对这三种方法一一进行介绍,以分析它们各自适用的场景。

方式一:一个专用的工作线程

第一种将耗时操作从GUI线程中转移出去的方式是,使用一个专门的工作线程来异步地处理GUI线程发送的耗时操作请求。如下图所示,GUI线程依次将打印文档(PrintDocument)和保存文档(SaveDocument)两个异步请求发送给工作线程之后就立刻返回,从而继续对用户的其他请求做出及时的相应(例如调整窗口大小、编辑文档等);与此同时,工作线程依次对打印文档和保持文档进行顺序处理,并在并在该异步请求完成到某一进度时(或者该异步请求完成时)向GUI线程发送相应的通知信号。

图1. 使用专门的工作线程来处理GUI线程的异步请求
图1. 使用专门的工作线程来处理GUI线程的异步请求

让我们来看看这种处理方式的代码会长成什么样子:

// 第一种方式:使用一个专门的工作线程来处理GUI线程的异步请求
// GUI线程:
while( message = queue.receive() ) {
   if( it's a "保存文档" request ) {
      worker.send( new save_msg() ); // 发送异步请求
   }
   else if( it's a "保存文档" completion notification ) {
     display(“保存文档成功!”); // 接到异步请求的进度通知
   }
   else if( it's a "打印文档" request ) {
      worker.send( new print_msg() ); //发送异步请求
   }
   else if( it's a "打印文档" progress notification ) {
      if( percent < 100 ) // 接到异步请求的进度通知
         display_print_progress( percent );
      else
         display(“打印完毕!”);
   }
   else
   ...
}

// 工作线程:处理来自GUI线程的异步请求
while( message = workqueue.receive() ) {
   if( it's a "保存文档" request )
      save_document(); // 保存文档并在结束后向GUI线程发送通知
   else if( it's a "打印文档 " request )
      print_document(); // 打印文档并向GUI线程发送进度通知
   else
   ...
}

方式二:每一个异步请求分配一个工作线程

在第一种方法的基础之上,我们可以做一些相应的扩展:对每一个GUi线程的异步请求都分配一个专门的工作线程,而不是只用一个工作线程去处理所有异步请求。这个方式的好处很明显,异步请求被多个线程分别并行处理,因此提升了处理速度。值得注意的是,我们需要及时对这些工作线程进行垃圾回收操作,否则大量线程会造成内存资源的紧张。

图2. 为每个GUI线程的异步请求分配一个工作线程
图2. 为每个GUI线程的异步请求分配一个工作线程

这种模式的代码如下所示。因为对每个异步请求我们都启动一个新的线程,我们可以充分地利用多核的计算资源,更快地完成相应的任务。

// 方式二:每一个异步请求分配一个线程
while( message = queue.receive() ) {
   if( it's a "保存文档" request ) {
      ...  new Thread( [] { save_dcument(); } ); // 启动新线程对异步请求进行处理
   }
   else if( it's a "打印文档" request ) {
      … new Thread( [] { print_document(); } );/ // 启动新线程对异步请求进行处理
   }
   else if( it's a "保存文档" notification ) { ... }
                                      // 同方式一
   else if( it's a "打印文档" progress notification ) { ... }
                                      // 同方式一
   else
      ...
}

方式三:使用线程池来处理异步请求

第三种方式更进了一步:我们可以根据多核硬件资源的多少来启动一个专门的线程池,用线程池来完成GUI线程的异步请求。这种方式的好处在于,我们可以在充分利用多核的硬件资源,以及并行地对异步请求进行高效处理间取得一个很好的平衡。该方式的工作示意图如下所示:

图3. 使用线程池来处理GUI线程的异步请求
图3. 使用线程池来处理GUI线程的异步请求

让我们来看一下这种方式的伪代码。需要注意的是,线程池的具体实现每个语言各有不同,因此下面的代码只供大家参考之用。

// 方式三:使用线程池来处理异步请求
while( message = queue.receive() ) {
if( it's a "保存文档" request ) {
pool.run( [] { save_document(); } ); // 线程池的异步调用
}
else if( it's a "打印文档" request ) {
pool.run( [] { print_document(); } ); //线程池的异步调用
}
else if( it's a "保存文档" notification ) { ... }
// 同前
else if( it's a "打印文档" progress notification ) {  ... }
// 同前
else
...
}

Grand Central Dispatch的异步并行

Grand Central Dispatch(GCD)是苹果于Mac OS X 10.6和iOS4中发布的一项并行编程技术。对使用GCD的程序员来说,只需要将需要被处理的任务块丢到一个全局的任务队列中去就可以了,这个任务队列中的任务会由操作系统自动地分配和调度多个线程来进行并行处理。将需要被处理的任务块插入到任务队列中去有两种方式:同步插入和异步插入。

让我们来看看一个使用GCD异步并行的实例。在下面的程序中,analyzeDocument函数需要完成的功能是对这个文档的字数和段落数进行相关统计。在分析一个很小的文档时,这个函数可能非常快就能执行完毕,因此在主线程中同步调用这个函数也不会有很大的性能问题。但是,如果这个文件非常的大,这个函数可能变得非常耗时,而如果仍然在主线程中同步调用该方法,就可能带来很大的性能延迟,从而影响用户体验。

// 不使用GCD的版本
- (IBAction)analyzeDocument:(NSButton *)sender {
    NSDictionary *stats = [myDoc analyze];
    [myModel setDict:stats];
    [myStatsView setNeedsDisplay:YES];
    [stats release];
}

使用GCD的异步并行机制来优化这个函数非常简单。如下所示,我们只需要在原来的代码基础上,先通过dispatch_get_global_queue来获取全局队列的引用,然后再将任务块通过dispatch_async方法插入该队列即可。任务块的执行会交由操作系统去处理,并在该任务块完成时通知主线程。一般来讲,异步插入的方式拥有更高的性能,因为在插入任务之后dispatch_async可以直接返回,不需要进行额外等待。

//使用GCD异步并行的版本
- (IBAction)analyzeDocument:(NSButton *)sender
{
dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0ul);
dispatch_async(queue, ^{
         NSDictionary *stats = [myDoc analyze];
         [myModel setDict:stats];
         [myStatsView setNeedsDisplay:YES];
         [stats release];
     });
}

总结

本文对多核编程时常用的异步并行技术做了相关介绍。通过使用异步并行技术,我们可以将比较耗时的操作交给其他线程去处理,主线程因此可以去处理其他有意义的计算任务(例如相应用户的其他请求,完成其他计算任务等),从而有效提高系统的延迟性、吞吐率和响应性。

做好失败的准备

这周二晚上收到了SC’12大会的邮件通知,我的论文终于被接收了.在被SC’12录取之前,我这篇文章分别被IPDPS,ICS和SC据过,每一次被拒都得到了非常多有帮助的评审意见,帮助我更好的改进这篇文章.当然,被拒的滋味不好受.我认识的众多好友投顶级会议纷纷一投就中(例如madong的IJCAI, jiayu的NIPS和SIGIR, yang xi的ASPLOS和OOSPLA),我被拒了那么多次咋还没中呢,心里的挫败感多多少少还是有一点.

不过现在回头来看,最大的体会就是:要想做成一件公认的不太容易的事情,你必须做好失败的准备.Per在第一次投稿的时候跟我说,”没事,你投ICS吧,把目标设的高一点好”.现在想来,就是要给自己设定一个超出自己能力的目标,才能激发出自己的潜能:) 当然,既然你给自己设定了一个比较高的目标,你就一定要清楚的认识到,这件事情不是那么容易成功的.你必须把工作做到位,做扎实,过了那个门槛才行.而这个门槛的高度可能需要你付出非常多的努力.具体到SC’12的这篇论文上,因为是系统相关的题目,所以必须要把实验部分做的非常扎实才能让审稿人满意,向我这样的普通人,自然需要努力努力再努力才能成功.

大家都在讲成功,都想要成功,殊不知成功之前大都要经历失败,尤其是在令人瞩目的成功之前,更是如此.比如说,你想成为一名优秀的程序员,可能需要10年的苦工.比如说,你想要在ISCA发一篇有影响力的文章,可能需要做个三四年扎实的工作才行.比如说,你想创办一家成功的公司并上市,可能需要10年的时间并经历千辛万苦.当然,除了努力之外,还有另外一个非常重要的因素,那就是洞察力.如果能发现一个新的热点,自然就能站在浪潮之巅成为风云人物,不过那是另一个故事了,发现问题永远比解决问题要难嘛.

把目标设的高一点,然后朝着那个目标的门槛努力,中间失败了也不要紧,因为每失败一次,离成功就近了一分.

这周二晚上收到了SC’12大会的邮件通知,我的论文终于被接收了.在被SC’12录取之前,我这篇文章分别被IPDPS,ICS和SC据过,每一次被拒都得到了非常多有帮助的评审意见,帮助我更好的改进这篇文章.当然,被拒的滋味不好受.我认识的众多好友投顶级会议纷纷一投就中(例如madong的IJCAI, jiayu的NIPS和SIGIR, yang xi的ASPLOS和OOSPLA),我被拒了那么多次咋还没中呢,心里的挫败感多多少少还是有一点.

不过现在回头来看,最大的体会就是:要想做成一件公认的不太容易的事情,你必须做好失败的准备.Per在第一次投稿的时候跟我说,”没事,你投ICS吧,把目标设的高一点好”.现在想来,就是要给自己设定一个超出自己能力的目标,才能激发出自己的潜能:) 当然,既然你给自己设定了一个比较高的目标,你就一定要清楚的认识到,这件事情不是那么容易成功的.你必须把工作做到位,做扎实,过了那个门槛才行.而这个门槛的高度可能需要你付出非常多的努力.具体到SC’12的这篇论文上,因为是系统相关的题目,所以必须要把实验部分做的非常扎实才能让审稿人满意,像我这样的普通人,自然需要努力努力再努力才能成功.

大家都在讲成功,都想要成功,殊不知成功之前大都要经历失败,尤其是在令人瞩目的成功之前,更是如此.比如说,你想成为一名优秀的程序员,可能需要10年的苦工.比如说,你想要在ISCA发一篇有影响力的文章,可能需要做个三四年扎实的工作才行.比如说,你想创办一家成功的公司并上市,可能需要10年的时间并经历千辛万苦.当然,除了努力之外,还有另外一个非常重要的因素,那就是洞察力.如果能发现一个新的热点,自然就能站在浪潮之巅成为风云人物,不过那是另一个故事了,发现问题永远比解决问题要难嘛.

把目标设的高一点,然后朝着那个目标的门槛努力,中间失败了也不要紧,因为每失败一次,离成功就近了一分.

Facebook技术分享: Social Networking at Scale

在HPCA’12大会上,来自Facebook的Sanjeev Kumar做了题为“Social Networking at Scale”的技术演讲,主要对Facebook在可扩展的软/硬件架构上的挑战做了分析,特地分享给大家。

在HPCA’12大会上,来自Facebook的Sanjeev Kumar做了题为“Social Networking at Scale”的技术演讲,主要对Facebook在可扩展的软/硬件架构上的挑战做了分析,特地分享给大家。

为什么NoSQL和Hadoop该一起使用?

Cloudera和CouchBase最近以“为什么NoSQL和Hadoop该一起使用?”为题做了个主题分享,其中对传统IT架构和Big Data架构做了很好的对比,很值得一看。

Cloudera和CouchBase最近以“为什么NoSQL和Hadoop该一起使用?”为题做了个主题分享,其中对传统IT架构和Big Data架构做了很好的对比,很值得一看。

Understanding System and Architecture for Big Data

简介:IBM Research最近在Big Data领域有很多工作,例如我们组在4月份在10台采用POWER7处理器的P730服务器上成功地用14分钟跑完了1TB数据的排序(7月份又在10台Power7R2上用8分44秒跑完了1TB排序),这项工作已经发表为一篇IBM Research Report,欢迎大家围观,并提出宝贵意见,谢谢。

The use of Big Data underpins critical activities in all sectors of our society. Achieving the full transformative potential of Big Data in this increasingly digital world requires both new data analysis algorithms and a new class of systems to handle the dramatic data growth, the demand to integrate structured and unstructured data analytics, and the increasing computing needs of massive-scale analytics. In this paper, we discuss several Big Data research activities at IBM Research: (1) Big Data benchmarking and methodology; (2) workload optimized systems for Big Data; (3) case study of Big Data workloads on IBM Power systems. In (3), we show that preliminary infrastructure tuning results in sorting 1TB data in 14 minutes on 10 Power 730 machines running IBM InfoSphere BigInsights. Further improvement is expected, among other factors, on the new IBM PowerLinuxTM 7R2 systems.

By: Anne E. Gattiker, Fadi H. Gebara, Ahmed Gheith, H. Peter Hofstee, Damir A. Jamsek, Jian Li, Evan Speight, Ju Wei Shi, Guan Cheng Chen, Peter W. Wong

Published in: RC25281 in 2012

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

下载链接

Questions about this service can be mailed to reports@us.ibm.com .

简介:IBM Research最近在Big Data领域有很多工作,例如我们组在4月份在10台采用POWER7处理器的P730服务器上成功地用14分钟跑完了1TB数据的排序(7月份又在10台Power7R2上用8分44秒跑完了1TB排序),这项工作已经发表为一篇IBM Research Report,欢迎大家围观,并提出宝贵意见,谢谢。

The use of Big Data underpins critical activities in all sectors of our society. Achieving the full transformative potential of Big Data in this increasingly digital world requires both new data analysis algorithms and a new class of systems to handle the dramatic data growth, the demand to integrate structured and unstructured data analytics, and the increasing computing needs of massive-scale analytics. In this paper, we discuss several Big Data research activities at IBM Research: (1) Big Data benchmarking and methodology; (2) workload optimized systems for Big Data; (3) case study of Big Data workloads on IBM Power systems. In (3), we show that preliminary infrastructure tuning results in sorting 1TB data in 14 minutes on 10 Power 730 machines running IBM InfoSphere BigInsights. Further improvement is expected, among other factors, on the new IBM PowerLinuxTM 7R2 systems.

By: Anne E. Gattiker, Fadi H. Gebara, Ahmed Gheith, H. Peter Hofstee, Damir A. Jamsek, Jian Li, Evan Speight, Ju Wei Shi, Guan Cheng Chen, Peter W. Wong

Published in: RC25281 in 2012

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

Download link: http://domino.research.ibm.com/library/cyberdig.nsf/1e4115aea78b6e7c85256b360066f0d4/f085753cf57c8c35852579e90050598f!OpenDocument&Highlight=0,big,data

Questions about this service can be mailed to reports@us.ibm.com .