Interpreting the Data:Parallel Analysis with Sawzall（3）

12 性能
虽然Sawzall是解释执行的，但是这不是影响性能的主要因素。大部分Sawzall程序都只会带来很少一点的处理开销和I/O开销，而大部分的CPU时间都用于各种run-time的操作，比如分析protocol buffer等等。

不过，为了比较单CPU的Sawzall和其他解释语言的解释执行性能，我们写了一些小的测试程序。第一个是计算Mandelbrot的值，来测试基本的算术和循环性能。第二个测试函数用递归函数来计算头35个菲波纳契级数。我们在一个2.8G x86台式机上执行的测试。表1是测试结果，显示了Sawzall远比Python,Ruby或者Perl快，起码这些benchmarks上要快。另一方面，在这些测试上，Sawzall比解释执行的Java慢1.6倍，比编译执行的Java慢21倍，比C++编译的慢51倍。


Sawzall
Python
Ruby
Perl

Mandelbrot runtime

factor
12.09s

1.00
45.42s

3.75
73.59s

6.09
38.68s

3.20

Fibonacci runtime

factor
11.73s

1.00
38.12s

3.24
47.18s

4.02
75.73s

6.46


表1：Microbenchmarks.第一个Mandelbrotset计算：500x500图像，每点最多500次叠代。第二个用递归函数计算头35个菲波纳契级数。





这个系统的性能关键并非是单个机器上的性能，而是这个性能在处理大数据量时，增加机器的时候性能增加曲线。我们使用了一个450GB的压缩后的查询log数据，并且在其上运行一个Sawzall程序来统计某一个词出现的频率。这个程序的核心代码是类似这样的：

result: table sum[key: string][month: int][day: int] of int;

static keywords: array of string =

       {      "hitchhiker", "benedict", "vytorin",

              "itanium", "aardvark" };



querywords: array of string = words_from_query();

month: int = month_of_query();

day: int = day_of_query();



when (i: each int; j: some int; querywords[i] == keywords[j])

       emit result[keywords[j]][month][day] <- 1;



我们在50到600台2.4G Xeon服务器上执行了这个测试程序。测试的时间结果在图5体现了。在600台机器的时候，汇聚器大概可以每秒处理1.06G压缩后的数据，或者3.2G未压缩的数据。如果这个性能扩展能力是比较完美的，那么随着机器的增加处理性能能近似线形增长，这就是说，每增加一台机器，都能增加一台机器的完整处理性能。在我们的测试中，增加1台机器的效率增加大约是相当于增加0.98台机器。




图5：当增加机器的时候性能变化曲线。实线是花费的时间，虚线是机器的工作时间产出。从50到600台机器的一个区间内，单机的性能产出仅仅下降了30%。



为什么需要一个新语言？
为什么我们需要在MapReduce之上增加一个新的语言？MapReduce已经很高效了；还少什么吗？为什么需要一个全新的语言？为什么不在MapReduce之上使用现成的语言比如Python？

这里给出了构造一个特殊目的语言的常见原因。为某一个问题领域构造特定的符号描述有助于程序清晰化，并且更紧凑，更有效率。在语言内嵌聚合器（包括在运行时刻内嵌聚合器）意味着程序员可以不用自己实现一个，这点不像使用MapReduce需要自己实现。同样的，它也更符合大规模并发处理超大数据集时候的处理思路，并且根据这个处理思路写出一流的程序。同样的，对协议栈buffer的支持，并且提供了平台相关的类型支持，在较低层面上简化了程序开发。总的来说，Sawzall程序要比基于MapReduce的C++小上10~20倍，并且更容易书写。

定制语言还有其他优势包括了增加平台相关的特性，定制的调试和模型界面，等等。

不过，制作这个Sawzall的原始动机完全不同：并行，拆分聚合器，并且提供不需要对记录内部作分析就可以最大程度的对记录进行并行处理。它也提供了一个分布式处理的模式，激励用户从另外的思维角度考察并行问题。在现成的语言中比如Awk[12],Python[1],用户可能要用这个语言书写聚合器，这就可能比较难以做到并行化处理。甚至就算在这些语言中提供了清晰的聚合器接口和函数库，经验老到的用户还有可能要实现他们自己的内容，用以大幅度提高处理性能。

Sawzall采用的模式已经被证明非常有效。虽然对于少数问题来说，这样的模式还不能有效处理，但是大部分海量数据的处理来说都已经很适用了，并且可以简单用程序实现，这就使得Sawzall成为google中很受欢迎的语言。

这个语言对用户编程方面的限制也带来额外的一些好处。因为用户程序的数据流是强类型化的，它很容易用来提供记录中的单独字段的访问控制。就是说，系统可以自动并且安全的在用户程序外增加一层，这个层本身也是由Sawzall实现的，它用来隐藏敏感信息。例如，产品工程师可以在不被授权业务信息的情况下，访问性能和监控信息数据。这个会在单独的论文中阐述。



14 工具
虽然Sawzall仅仅发布了18个月，他已经成为了google应用最广泛的语言之一。在我们的源码控制系统内已经有上千个Sawzall程序（虽然，天生这些程序就是短小精干的）。

Sawzall工具的一个衡量指标就是它所处理的数据量。我们监控了2005年3月的使用情况。在3月份，在一个有1500个XeonCPU的工作队列集群上，启动了32580个Sawzall job，平均每个使用220台机器。在这些作业中，产生了18636个失败（应用失败，网络失败，系统crash等等），导致重新运行作业的一部分。所有作业读取了大约3.2x10^15字节的数据（2.8PB），写了9.9x10^12字节（9.3TB）（显示了”数据合并”有些作用）。平均作业处理大概100GB数据，这些作业总共大约等于一个机器整整工作一个世纪的工作。



15 相关工作
传统的数据处理方式通常是通过关系数据库保存数据，并且通过SQL查询来进行查询。我们的系统有比较大的不同。首先，数据集通常过于巨大，不能放在关系型数据库里；而且文件直接在各个存储节点进行处理，而不用导入一个数据库服务器。同样的，我们的系统也没有预先设定的table或者索引；我们用构造一个特别的table和索引来进行这样的相关计算。

Sawzall和SQL完全不同，把高效的处理单个记录分析结果的聚合器接口结合到传统的过程语言。SQL有很高效的数据库join操作，但是Sawzall却不行。但是另一方面来说，Sawzall可以在上千台机器上运行处理超大数据集。

Brook[3]是另一个数据处理语言，特别适合图像处理。虽然在不同的应用领域，就像Sawzall一样，它也是基于一次处理一个元素的计算模式，来进行并行处理，并且通过一个聚合器内核来合并（reduce）输出。

另外一种处理大数据的方式是通过数据流的模式。这样的系统是处理数据流的输入，他们的操作是基于输入记录的顺序。比如，Aurora[4]就是一个流模式处理系统，支持单向数据流输入的数据集处理。就像Sawzall预定义的聚合器，Aurora提供了一个很小的，固定操作功能集合，两者都是通过用户定义的函数来体现的。这些操作功能可以构造很多有意思的查询。同Sawzall不同的是，部分Aurora操作功能是基于输入值得连续的序列，或者输入值得一个数据窗。Aurora只保存被处理的有限的一部分数据，并且不是为了查询超大的归档库设计的。虽然对Aurora来说，增加新的查询很容易，但是他们只能在最近的数据上进行操作。Aurora和Sawzall不同，Aurora是通过精心设计的运行时刻系统和查询优化器来保证性能，而Sawzall是通过强力的并行处理能力来保证性能。

另一种流模式处理系统是Hancock[7]，对流模式的处理方式进行了扩展，提供了对每个查询的中间状态作保存。这个和Sawzall就完全不同，Sawzall完全不考虑每个输入记录的处理后的状态。Hancock和Aurora一样，专注于依靠提高单进程处理效率，而不是依靠大规模并行处理来提高性能。

16 展望
成百台机器并行处理的生产力是非常大的。因为Sawzall是一个大小适度的语言，用它写的程序通常比较小，并且是绑定I/O的。因此，虽然他是一个解释语言，实现上效率也足够了。但是，有些超大的，或者超复杂的分析可能需要编译成为机器码。那么编译器需要每台机器上执行一次，然后就可以用这些高速的二进制代码处理每条输入记录了。

有时候，程序在处理记录的时候需要查询外部数据库。虽然我们已经提供了对一些小型数据库的支持，比如什么IP地址信息之类的，我们的系统还是可以用一个接口来操作一个外部数据库。因为Sawzall对每条记录来说是单独处理的，所以当进行外部数据库操作的时候，系统会暂时停顿，当操作完成，继续处理记录。在这个处理过程中，当然有并行处理的可能。

有时候，我们对数据的分析需要多次处理，无论多次Sawzall处理或者从其他系统的处理而导致的多次Sawzall处理，比如从一个传统数据库来的，或者一个其他语言写的程序来的；由于Sawzall并不直接支持”chaining”(链式处理)，所以，这些多重处理的程序很难在Sawzall中展示。所以，对这个进行语言方面的扩展，可以使得将来能够简单的表达对数据进行多次处理，就如同聚合器的扩展允许直接输出到外部系统一样。

某些分析需要联合从不同的输入源的数据进行分析，通常这些数据是在一次Sawzall处理或者两次Sawzall处理之后进行联合分析。Sawzall是支持这样的联合的，但是通常要求额外的链接步骤。如果有更直接的join支持会简化这样的设计。

更激进的系统模式可以完全消除这种批处理的模式。在激进的模式下，一个任务比如性能检测任务，这个Sawzall程序会持续的处理输入数据，并且聚合器跟进这个数据流。聚合器本身在一些在线服务器上运行，并且可以在任何时候来查询任何table或者table 条目的值。这种模式和流式数据库[4][7]比较类似，事实上这个也是基于数据流模式考虑的。不过，在研究这种模式以前，由Dean和Ghemawat构造的MapReduce库由于已经非常有效了，所以这样的模式还没有实现过。也许有一天我们会回到这样的模式下。



17 结束语
随着问题的增大，就需要有新的解决方案。为了更有效的解决海量数据集的大规模并发分析计算，就需要进一步限制编程模式来确保高并发能力。并且还要求不影响这样的并发模式下的展示/应用/扩展能力。

我们的觉得方法是引入了一个全新的语言叫做Sawzall。这种语言通过强制程序员每次考虑一条记录的方式来实现这样的编程模式，并且提供了一组强力的接口，这些接口属于常用的数据处理和数据合并聚合器。为了能方便写出能并发运行在上千台计算机上执行的简洁有效的程序，学一下这个新的语言还是很超值的。并且尤其重要的是，用户不用学习并发编程，本语言和底层架构解决了全部的并发细节。

虽然看起来在一个高效环境下使用解释语言有点夸张，但是我们发现CPU时间并不是瓶颈，语言明确指出，绝大部分程序都是小型的程序，并且大量的时间都耗费在I/O上以及run-time的本地代码。此外，解释语言所带来的扩展性是比较强大的，在语言级别和在多机分布式计算上的表达都是容易证明扩展能力。

也许对我们系统的终极测试就是扩展能力。我们发现随着机器的增加，性能增长是近似线性增长的。对于海量数据来说，能通过增加机器设备就能取得极高的处理性能。



18 致谢
Geeta Chaudhry写了第一个强大的Sawzall程序，并且给出了超强建议。Amit Pate,Paul Haahr，Greg Rae作为最早的用户给与了很多帮助。Paul Haahr创建了PageRank 例子。Dick Sites， Ren’ee French对于图示有贡献。此外Dan Bentley,Dave Hanson,John Lamping,Dick Sites,Tom Szymanski, Deborah A. Wallach 对本论文也有贡献。



19 参考资料
[1] David M. Beazley, Python Essential Reference, New Riders, Indianapolis, 2000.

[2] Jon Bentley, Programming Pearls, CACM August 1986 v 29 n 8 pp. 711-721.

[3] Ian Buck et al., Brook for GPUs: Stream Computing on Graphics Hardware, Proc. SIGGRAPH,Los Angeles, 2004.

[4] Don Carney et al., Monitoring Streams – A New Class of Data Management Applications, Brown Computer Science Technical Report TR-CS-02-04. At
http://www.cs.brown.edu/research/aurora/aurora tr.pdf.

[5] M. Charikar, K. Chen, and M. Farach-Colton, Finding frequent items in data streams, Proc 29th Intl. Colloq. on Automata, Languages and Programming, 2002.

[6] W. F. Clocksin and C. S. Mellish, Programming in Prolog, Springer, 1994.

[7] Cortes et al., Hancock: A Language for Extracting Signatures from Data Streams, Proc. Sixth International Conference on Knowledge Discovery and Data Mining, Boston, 2000, pp. 9-17.

[8] Jeffrey Dean and Sanjay Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, Proc 6th Symposium on Operating Systems Design and Implementation, San Francisco, 2004, pages 137-149.

[9] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, The Google File System, Proc. 19th Symposium on Operating System Principles, Lake George, New York, 2003, pp. 29-43.

[10] M. Greenwald and S. Khanna, Space-efficient online computation of quantile summaries, Proc. SIGMOD, Santa Barbara, CA, May 2001, pp. 58-66.

[11] David R. Hanson, Fast allocation and deallocation of memory based on object lifetimes. Software–Practice and Experience, 20(1):512, January 1990.

[12] Brian Kernighan, Peter Weinberger, and Alfred Aho, The AWK Programming Language, Addison-Wesley, Massachusetts, 1988.

[13] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd, The pagerank citation algorithm: bringing order to the web, Proc. of the Seventh conference on the World Wide Web, Brisbane, Australia, April 1998.

[14] Martin Rinard et al., Enhancing Server Reliability Through Failure-Oblivious Computing, Proc. Sixth Symposium on Operating Systems Design and Implementation, San Francisco, 2004, pp. 303-316.

[15] Douglas Thain, Todd Tannenbaum, and Miron Livny, Distributed computing in practice: The Condor experience, Concurrency and Computation: Practice and Experience, 2004.



20 译者


崮山路上走9遍2005-8-5于大连完稿

BLOG: sharp838.mblogger.cn

EMAIL: [e-mail]；[e-mail]



所有的版权归于原作者。



本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/zhujt1981/archive/2008/04/04/2249940.aspx