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跟微策略合作的情况。

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 .

Intel Nehalem微处理器架构 by Glenn Hinton (Intel Fellow)

Intel的Nehalem是一个空前成功的设计。做架构最重要的本事就是学会做折衷(Tradeoff)。 Nehalem的Lead Architect Glenn Hinton在Stanford ee380这门课上详细讲解了Nehalem设计时的几个关键选择,特此分享给大家。

Intel的Nehalem是一个空前成功的设计。做架构最重要的本事就是学会做折衷(Tradeoff)。 Nehalem的Lead Architect Glenn Hinton在Stanford ee380这门课上详细讲解了Nehalem设计时的几个关键选择,特此分享给大家。

Intel’s Nehalem family of CPUs span from large multi-socket 32 core/64 thread systems to ultra small form factor laptops. What were some of the key tradeoffs in architecting and developing the Nehalem family of CPUs? What pipeline should it use? Should it optimize for servers? For desktops? For Laptops? There are lots of tradeoffs here. This talk will discuss some of the tradeoffs and results.

课程视频地址:http://ee380.stanford.edu/cgi-bin/videologger.php?target=100217-ee380-300.asx

Stanford ee380往年课程汇总:http://www.stanford.edu/class/ee380/

X-RIME: 基于Hadoop的开源大规模社交网络分析工具

随着互联网的快速发展,涌现出了一大批以Facebook,Twitter,人人,微博等为代表的新型社交网站。这些网站用户数量的迅速增长使得海量的用户数据不断被产生出来,而如何有效地对这些海量的用户数据进行社交网络分析(Social Network Analysis)正成为一个越来越热门的问题。本文向大家介绍由IBM中国研究院和北京邮电大学合作开发的X-RIME开源库(http://xrime.sourceforge.net/),一个基于Hadoop的开源社交网络分析工具。

其实早在90年代初就已经有许多企业和研究机构对社交网络进行过相关研究。然而随着互联网用户的急速的增长,今日的社交网站所需处理的数据已经不是传统的解决方案所能够应对的了。例如,传统的社会网络分析算法和工具往往都是单机形式的,在面对大规模数据集的时候往往会出现存储和处理能力不足等方面问题,再加上原始输入数据和社会网络的内部表示大都属于无结构或者半结构化数据,传统关系数据库并不擅长处理此类数据,使得利用传统的社会网络分析算法和工具对大规模数据集进行处理变得更加困难。另一方面,随着Hadoop的日益流行,许多中小互联网企业可以通过搭建Hadoop集群来方便地进行大规模数据处理。然而,Hadoop并不直接提供社交网络分析的算法库,因此实施海量社交网络分析仍存在较高门槛。基于这些需求,我们设计并实现了X-RIME。

X-RIME是一个基于Hadoop的开源社会网络分析工具。依赖于Hadoop提供的大规模数据并行处理能力,X-RIME实现了对十几中网络分析算法的并行化,提供了一整套用于对大规模社会网络进行分析处理的解决方案。通过使用X-RIME,用户可以方便快捷地对海量社会网络数据进行分析,从这些海量社会网络数据中获取更深层次的有用信息,从而进一步挖掘商业价值,支持商业决策以及发现新的业务增长点。

阅读全文>>

文 / 陈冠诚,史巨伟,杨博(IBM中国研究院),杨寅(人民搜索)

随着互联网的快速发展,涌现出了一大批以Facebook,Twitter,人人,微博等为代表的新型社交网站。这些网站用户数量的迅速增长使得海量的用户数据不断被产生出来,而如何有效地对这些海量的用户数据进行社交网络分析(Social Network Analysis)正成为一个越来越热门的问题。本文向大家介绍由IBM中国研究院和北京邮电大学合作开发的X-RIME开源库(http://xrime.sourceforge.net/),一个基于Hadoop的开源社交网络分析工具。

其实早在90年代初就已经有许多企业和研究机构对社交网络进行过相关研究。然而随着互联网用户的急速的增长,今日的社交网站所需处理的数据已经不是传统的解决方案所能够应对的了。例如,传统的社会网络分析算法和工具往往都是单机形式的,在面对大规模数据集的时候往往会出现存储和处理能力不足等方面问题,再加上原始输入数据和社会网络的内部表示大都属于无结构或者半结构化数据,传统关系数据库并不擅长处理此类数据,使得利用传统的社会网络分析算法和工具对大规模数据集进行处理变得更加困难。另一方面,随着Hadoop的日益流行,许多中小互联网企业可以通过搭建Hadoop集群来方便地进行大规模数据处理。然而,Hadoop并不直接提供社交网络分析的算法库,因此实施海量社交网络分析仍存在较高门槛。基于这些需求,我们设计并实现了X-RIME。

X-RIME是一个基于Hadoop的开源社会网络分析工具。依赖于Hadoop提供的大规模数据并行处理能力,X-RIME实现了对十几中网络分析算法的并行化,提供了一整套用于对大规模社会网络进行分析处理的解决方案。通过使用X-RIME,用户可以方便快捷地对海量社会网络数据进行分析,从这些海量社会网络数据中获取更深层次的有用信息,从而进一步挖掘商业价值,支持商业决策以及发现新的业务增长点。

1. X-RIME架构介绍

 

 

图一描述了X-RIME的整体架构,它主要由四层组成:HDFS,X-RIME数据模型,X-RIME算法库以及基于社交网络分析的商业智能分析应用。

X-RIME整体架构
图1. X-RIME整体架构

X-RIME算法库是X-RIME的核心组成部分,他基于Map/Reduce实现了十余种分布式社交网络处理算法。

X-RIME最底层采用了HDFS来存储海量数据。像很多其他基于Hadoop的数据分析解决方案一样,X-RIME也采用了HDFS来构建底层的海量数据存储设施。整个X-RIME算法库的所有的输入文件、中间结果和最终结果都会存储在HDFS上。

处于倒数第二层的X-RIME数据模型层实现了社交网络数据的“数据结构”。我们知道,社交网络的基础模型是图论中的图模型。在这个模型中,社会网络的个体被视为图中的节点,个体之间的关联被视为图中的边。 X-RIME数据模型层包括了近20 种数据结构,主要包括基于Hadoop 的对社会网络中的点、边等抽象概念的具体数据结构表示。在后面一节我们会详细介绍该数据模型的设计原则。

在X-RIME数据模型层之上的是X-RIME核心算法库(它运行在Hadoop的MapReduce框架之上)。在算法库中,我们通过map()/reduce()函数对的形式实现了十余种常见的社交网络分析算法。这些算法通过将多个Hadoop Job按算法工作流程组合在一起来共同完成相应的任务。这些算法都被相同的接口封装起来,这些接口一般包括四种参数:(1)输入文件在HDFS中的路径,它保存了与X-RIME数据模型相兼容的输入文件;(2)输出文件在HDFS中的路径,它用以保存最终的分析结果;(3)MAP/REDUCE的相关参数,例如Mapper数或者Reducer数等;(4)社交网络分析算法相关参数,例如迭代次数等。

图一中最顶层是基于社交网络分析的商业智能分析应用。它通过调用X-RIME核心算法库来实现对社交网络的数据分析。如果需要的话,用户还能将它与已有的数据仓库解决方案集成(例如JAQL,Mahout等),从而提供一个更加完整、高效的综合商业智能分析解决方案。

2. X-RIME 数据模型的设计原则

 

 

X-RIME 的设计目标是用来专门做大规模数据集社会网络分析的工具,因此我们对X-RIME 数据模型进行设计时必须考虑以下两点原则:X-RIME 需要处理大规模数据集;X-RIME 分析的对象是社会网络。X-RIME 处理大规模数据集的能力主要依赖于Hadoop的大规模并行处理能力,因此只要X-RIME 中所有的数据结构都是基于HADOOP 的海量数据集接口即可。这里我们重点分析X-RIME分析的对象即社会网络的特点。之前的分析中已经提到社会网络的基础模型是图论中的图模型,在这个模型里,社会网络中的个体被视为图里的结点v ,结点的集合为V ;个体之间的关联被视为图里面的边e,边的集合是E = {e (u, v) | u∈V, v∈V},因此整个模型就可以看作是G = (V, E)。基于此我们对X-RIME 的数据模型做了如下考量:

2.1 采用邻接矩阵还是邻接表

稀疏图和稠密图的邻接表与邻接矩阵形式
图2. 稀疏图和稠密图的邻接表与邻接矩阵形式

如图 2 所示,要表示一个图G = (V, E),有两种标准的方法,即邻接矩阵和邻接表。一般认为当|E|远小于|V|2的图属于稀疏图,反之则认为是稠密图。使用邻接矩阵表示法的优点在于可以很快判断两个给定结点是否存在连接边,缺点在于当要表示的图是稠密图的时候有大量的空间会被浪费。邻接表表示方式的优点在于节省空间,缺点在于判断两个给定结点是否存在连接表需要遍历其中某个结点的邻接表,效率较低。基于以下两点考虑,我们采用了邻接表的方式表示X-RIME 中的图结构:

(1)社交网络一般属于稀疏图结构,因此使用邻接表表示可以节省大量空间,提高空间利用率。
(2)X-RIME 中大部分算法不需要快速判断两个给定结点是否存在连接边。

2.2 边的表现形式

在邻接表中,结点之间的关系需要使用边来承载,边的形式可以有多种,如有向边,无向边,自环边(自己指向自己)等。考虑到在社会网络中,上述几种边都有可能存在,在不同的应用场景中有不同需求,因此我们需要有灵活的数据结构来支持上述各种不同形式的边。此外还有一种情况需要考虑,当有向边用{from, to}来表示时,传统的邻接表表示法只是将这条边信息记录在from 端,但是在社会网络分析中,我们可能存在某种场景需要同时将这条边信息记录在to 端,X-RIME 的设计中考虑了这种应用场景。

2.3 额外的承载信息

社会网络中结点和边需要存储额外信息
图3. 社会网络中结点和边需要存储额外信息

X-RIME 需要处理的社会网络图与传统的简单图不一样,它是个体以及个体之间复杂关系的一种抽象。如图3 所示,在社会网络中,结点自身往往需要存储一些额外的信息,例如当图中的结点表示人的时候,可能需要额外记录这个人的性别、年龄、家庭地址等信息;结点之间的关系(边)往往也需要存储一些额外的信息,例如当图中的边表示两个人是好朋友的时候,可能需要额外记录这条边的强度(好友关系的强烈程度)、边的类型(关系类型,如家人、朋友、同学等)、好友间的物理距离等。基于上述考虑,X-RIME 的设计中必须考虑为结点和边提供额外的信息存储功能。

2.4 比较器

在社会网络中,个体和边需要进行某种程度的对比。例如在好友关系网中,人们可能希望比较得出哪些人是自己最好的朋友,人们同样可能希望比较得出自己在好友心目中的重要程度等。映射到X-RIME 中,大量的运算的确需要对结点以及边进行比较。这种比较可以是简单的数值比较(例如边的权值比较)也可以是复杂的逻辑比较(例如综合边的关系类型,边的强度,结点之间的物理距离等进行比较)。X-RIME 的设计中必须考虑数据类型之间的比较,需要设计各种比较器。

2.5 效率问题

X-RIME 需要处理的是大规模海量数据,如果我们对输入数据的读写处理只是简单地根据原始的文本文件格式进行读写,势必影响效率,因为这样多了一个中间转换过程,需要读入内存再根据特定的数据结构格式进行转换。Hadoop 提供的序列化IO 接口为我们提供了一个有效的方法来提高读写效率。在读取输入数据之前,我们需要预先对原始文本进行转换,通过Hadoop 序列化IO 接口的序列化功能将其转换成二进制镜像文件形式,这样每次X-RIME 读取被序列化产生的二进制文件的时候可以直接通过Hadoop 序列化IO 接口的反序列化功能将镜像文件装载到内存里,输出的时候直接通过Hadoop IO 的序列化功能进行输出,效率大大提高。两种读写方式的示意图如图4 所示。

两种输入输出方式(左:较为低效的传统方式,右:高效的序列化方式)
图4. 两种输入输出方式(左:较为低效的传统方式,右:高效的序列化方式)

3. X-RIME使用介绍

 

 

使用X-RIME大致可以分为四步。第一步:获取原始数据,例如使用爬虫获取原始网站数据。第二步:对数据进行预处理以转化成X-RIME数据模型所支持的格式。这个步骤与用户提供的具体数据格式相关,因而通常由X-RIME用户自己实现。第三步:调用X-RIME算法库对这些数据进行社交网络分析。第四步:对X-RIME的输出结果进行整合,生成易于理解的文档。

下面我们来介绍下使用X-RIME对某BBS中一个分论坛进行弱连通分支(Weakly Connected Components,后面简称WCC)算法分析的结果。在BBS中,每一个帖子的发起者A是一个节点,而如果另一个用户B回复了这个帖子,我们说这两个用户间形成了一个关系,即B指向了A。

弱连通分布
图5. 弱连通分布

图5中的蓝红紫三条线分别代表该BBS中MilitaryView版, Circuit版和Career_POST版的WCC分布情况。从图中我们可以看到,MilitaryView版和Circuit版中大部分的用户的WCC值都很高。这说明这两个版块中的大部分用户彼此都直接或者间接的联系在一起。相反的,Career_POST版中大部分的用户彼此间的联系都非常松散。其实这个结果非常易于理解,因为MilitaryView和Circuit版是专门的版块,在这个版块的用户大都是基于相同的兴趣而产生的发帖、回帖行为,因此彼此间的互动更频繁、联系更紧密;相对的,Career_POST版主要被用于发布和浏览招聘信息,因此用户的回帖行为不多,用户间的关联性不强。

4. 总结

 

 

X-RIME作为基于Hadoop的开源工具,为大家提供了一种方便快捷地进行大规模社交网络分析的新选择。如果您对X-RIME有什么新的需求或者建议,欢迎您直接与我们联系:chengc@cn.ibm.com。

参考文献

 

 

[1] X-RIME Homepage: http://xrime.sourceforge.net/

[2] Wei Xue, JuWei Shi, Bo Yang. X-RIME: Cloud-Based Large Scale Social Network Analysis. Proceedings of 2010 IEEE International Conference on Services Computing.

[3] Kai Shuang, Yin Yang, Bin Cai, Zhe Xiang. X-RIME: HADOOP-BASED LARGE-SCALE SOCIAL NETWORK ANALYSIS. Proceedings of IC-BNMT2010.

[4] 杨寅.大规模社会网络分析数据模型的设计与实现. 中国科技论文在线.

Facebook的Realtime Hadoop及其应用

在今年的SIGMOD‘11上,Facebook又发了一篇新paper(点此下载),讲述了它们在提高Hadoop实时性上的工作及其应用。简单来讲,他们的项目需求主要有:

1. Elasticity(伸缩性)
2. High write throughput(高写吞吐量)
3. Efficient and low-latency strong consistency semantics within a data center(单个data center内高性能、低延迟的强一致性)
4. Efficient random reads from disk(disk的高性能随机读)
5. High Availability and Disaster Recovery(高可靠性、灾后恢复能力)
6. Fault Isolation(错误隔离)
7. Atomic read-modify-write primitives(read-modify-write原子操作)
8. Range Scans(范围扫描)

阅读全文>>

在今年的SIGMOD‘11上,Facebook又发了一篇新paper(点此下载),讲述了它们在提高Hadoop实时性上的工作及其应用。简单来讲,他们的项目需求主要有:

1. Elasticity(伸缩性)
2. High write throughput(高写吞吐量)
3. Efficient and low-latency strong consistency semantics within a data center(单个data center内高性能、低延迟的强一致性)
4. Efficient random reads from disk(disk的高性能随机读)
5. High Availability and Disaster Recovery(高可靠性、灾后恢复能力)
6. Fault Isolation(错误隔离)
7. Atomic read-modify-write primitives(read-modify-write原子操作)
8. Range Scans(范围扫描)

最终他们选择了Hadoop和HBase作为解决方案的基石,因为HBase已经满足了上述需求中的大部分。与此同时,他们还做了如下三点改进以满足实时性需求:
1. File Appends
2. Name Node的高可靠性优化 (AvatarNode)
3. HBase的读性能的优化

文章还列举了三个基于此方案的应用:Facebook Message,Facebook Insight,Facebook Metric Systems,大家可以着重看看这三个应用的特点及需求是怎样被这个方案满足的。

在现在这个时代,只有大公司才有如此大的数据来做新东西,难怪Facebook,Google的paper被大量追捧了。

参考资料:
[1] Facebook’s New Realtime Analytics System: HBase To Process 20 Billion Events Per Day
[2] Real Time Analytics for Big Data: An Alternative Approach

下面是这篇文章的slides:

Jeff Dean关于Google系统架构的讲座

上个月Jeff Dean在Standford的Computer Systems Colloquium (EE380)这门讨论课上详细讲了讲Google的系统架构发展过程,因为这是份很新的资料,所以特意把它的Slide下下来与大家分享一下。这门课是Standford的讲座课程,每一节课都由不同的顶级工程师/科学家/投资人前来讲授IT行业的最新动向,非常非常有料,绝对值得深挖。这门课的每节课都是带视频的,Jeff Dean的这个讲座的录像在这里

阅读全文>>

上个月Jeff Dean在Standford的Computer Systems Colloquium (EE380)这门讨论课上详细讲了讲Google的系统架构发展过程,因为这是份很新的资料,所以特意把它的Slide下下来与大家分享一下。这门课是Standford的讲座课程,每一节课都由不同的顶级工程师/科学家/投资人前来讲授IT行业的最新动向,非常非常有料,绝对值得深挖。这门课的每节课都是带视频的,Jeff Dean的这个讲座的录像在这里。想要下载该视频的同学可以去这里(要会功夫,你懂的)。

这个讲座的主要内容包括:
• Evolution of various systems at Google
– computing hardware
– core search systems
– infrastructure software

• Techniques for building large-scale systems
– decomposition into services
– design patterns for performance & reliability

个人的一点小感想:Jeff Dean在Google的这几年能面临这么多有意思的挑战,编程模型,可靠性,伸缩性,运行时环境等等等等,真是羡煞旁人。随着Google业务的扩展,整个系统的设计也面临各种各样新的挑战。只有有了扎实的基本功,在面对没有现成解决方案的新问题时才能游刃有余,做工程是如此,做研究更是如此。

可能有些同学会因为这是个英语的讲座而头疼。我觉得大家可以坚持看,哪个单词看不懂的就查字典,刚开始可能痛苦点,但是只要坚持下去,积少成多,你就会发现自己的英语慢慢就上来了,至少看这些英文slides是没问题了。

Building Software Systems at Google and Lessons Learned

另外还有几个关于Jeff Dean的Google架构的博文:
Jeff Dean 在WSDM 2009上面的演讲 Keynote 和视频终于出来了
来自Jeff Dean的分布式系统设计模式(更新版)
Jeff Dean的Stanford演讲

我还发现了Jeff另外一个在09年做的类似主题的讲座,内容稍有重复,但是可以算是一个补充,例如这个里面包括了BigTable等内容。

Enjoy!