Skip to content

{ Monthly Archives } 二月 2007

MapReduce 超大集群的简单数据处理

MapReduce 超大集群的简单数据处理 关于: MapReduce: Simplified Data Processing on Large Clusters Jeffrey Dean Sanjay Ghemawat jeff@google.com , sanjay@google.com Google , Inc. 排版文件参考: http://www.fulin.org/tech/mapreduce.htm 摘要 MapReduce是一个编程模式,它是与处理/产生海量数据集的实现相关。用户指定一个map函数,通过这个map函数处理key/value(键/值)对,并且产生一系列的中间key/value对,并且使用reduce函数来合并所有的具有相同key值的中间键值对中的值部分。现实生活中的很多任务的实现都是基于这个模式的,正如本文稍后会讲述的那样。 使用这样的函数形式实现的程序可以自动分布到一个由普通机器组成的超大几群上并发执行。run-time系统会解决输入数据的分布细节,跨越机器集群的程序执行调度,处理机器的失效,并且管理机器之间的通讯请求。这样的模式允许程序员可以不需要有什么并发处理或者分布式系统的经验,就可以处理超大的分布式系统得资源。 我们的MapReduce系统的实现运行在一个由普通机器组成的大型集群上,并且有着很高的扩展性:一个典型的MapReduce计算处理通常分布到上千台机器上来处理上TB的数据。程序员会发现这样的系统很容易使用:已经开发出来了上百个MapReduce程序,并且每天在Google的集群上有上千个MapReduce job正在执行。 1 介绍 在过去的5年内,Google的创造者和其他人实现了上百个用于特别计算目的的程序来出来海量的原始数据,比如蠕虫文档,web请求log,等等,用于计算出不同的数据,比如降序索引,不同的图示展示的web文档,蠕虫采集的每个host的page数量摘要,给定日期内最常用的查询等等。绝大部分计算都是概念上很简洁的。不过,输入的数据通常是非常巨大的,并且为了能在合理时间内执行完毕,其上的计算必须分布到上百个或者上千个计算机上去执行。如何并发计算,如何分布数据,如何处理失败等等相关问题合并在一起就会导致原本简单的计算掩埋在为了解决这些问题而引入的很复杂的代码中。 因为这种复杂度,我们设计了一种新的东西来让我们能够方便处理这样的简单计算。这些简单计算原本很简单,但是由于考虑到并发处理细节,容错细节,以及数据分布细节,负载均衡等等细节问题,而导致代码非常复杂。所以我们抽象这些公共的细节到一个lib中。这种抽象是源自Lisp以及其他很多面向功能的语言的map和reduce概念。我们认识到大部分操作都和map操作相关,这些map操作都是运算在输入记录的每个逻辑”record”上,并且map操作为了产生一组中间的key/value键值对,并且接着在所有相同key的中间结果上执行reduce操作,这样就可以合并适当的数据。我们得函数模式是使用用户定义的map和reduce操作,这样可以让我们并发执行大规模的运算,并且使用重新执行的方式作为容错的优先机制。 MapReduce的主要贡献在于提供了一个简单强大的接口,通过这个接口,可以把大尺度的计算自动的并发和分布执行。使用这个接口,可以通过普通PC的巨大集群,来达到极高的性能。 第二节讲述了基本的编程模式,并且给出了一些例子。第三节讲述了一个面向我们基于集群的计算环境的MapReduce的实现。第四节讲述了一些我们建议的精巧编程模式。第五节讲述了在不同任务下我们的MapReduce实现的性能比较。第六节讲述了在Google中的MapReduce应用以及尝试重写了我们产品的索引系统。第七节讲述了相关工作和未来的工作。 2 编程模式 我们的运算处理一组输入的(input)键值对(key/valuepairs),并且产生一组输出的(output)键值对。MapReduce函数库德用户用两个函数来表达这样的计算:Map和Reduce。 Map函数,是用户自定义的的函数,处理输入的键值对,并且产生一组中间的(intermediate)键值对。MapReduce函数库稽核所有相同的中间键值键I的值,并且发送给Reduce函数进行处理。 Reduce函数同样也是用户提供的,它处理中间键值I,以及这个中间键值相关的值集合。这个函数合并这些值,最后形成一个相对较小的值集合。通常一个单次Reduce执行会产生0个或者1个输出值。提供给Reduce函数的中间值是通过一个iterator来提供的。这就让我们可以处理超过内存容量的值列表。 2.1 例子 我们考虑这样一个例子,在很大的文档集合中通机每一个单词出现的次数。我们写出类似如下的伪代码: map(String key, String value): // key: document name // value: document contents for each [...]

Google File System

Google File System 关于: The Google File System Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung Google? {sanjay,hgobioff,shuntak}@google.com 排版文件参考: http://www.fulin.org/tech/gfs.htm 首页版权 Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial [...]

水均益列传

水均益者,皇家宣谕台之杂说使,充任礼部之代言,外藩之宣慰,虽九品以外,然人微言重;乃黄门走卒,却身低位高,宣谕台以内,人称“水主”者是也。 夫水主,皮白发乌,颜容俊俏,每有所出,必西服革履,粉面油头,皱双眉以显深沉,射精光而演独到,踞主持以控三方,出言论而导舆情,以青壮傲视赵公等老朽,通夷语独霸杂说之讲台。放眼天下者不得不垂注乎水主,乃因国朝于外邦之好恶情状,颇多授意水主类也,是以水主名矣。 然则水主体察上意惟恐不周,臧否人物往往过当。初,伊国开战,水主忽铠甲遍体,痛别国人,誓言乎以身犯险,将于狼烟中探访旧友撒达姆氏,惜乎浅尝辄止,仅于边境客栈遥望乎旧友禁宫,寄语乎撒氏勉励以战,当其时也,弱女子闾秋露薇者素面朝天独闯伊国,其见闻亲历战火,举国夸赞,水主大窘,仓皇回朝。 又,米国扫荡暴君,水主召中军参将张公召忠等议论战事,水主导引之,张公妄议之,出言则必称米国将败,出谋则冀望撒氏反攻,然则世事难料,水、张等百无一中,徒惹坊间哗笑,业内蒙羞。然则水主等不以为耻也。 举凡外邦风云变幻,则水主必正襟危坐,张公等谋士必摇唇鼓舌,布达上意每每过当,褒贬人物往往并非,君不见:褒者络绎锒铛,贬者结队上台,坊间讥为水氏铁律者谓:挺则败,嘲则胜,竟屡试不爽也。 论者曰:水氏,传声而已矣,斥之或者过当?余则谓:传声者,五音而已,水氏之传,八音也,多则失其原本,遗笑外邦事小,误引民情事大,则水氏之可斥,然也。 张艺谋列传 张氏艺谋,陕西人氏,国朝影戏之名导,奉圣乐舞之班头者也。初,张氏怀才于黄土,蛰伏于渭水,不遇于旧都,乃天地间一介匹夫而已矣。 当是时也,国朝厄运之强弩,邓公拨乱以反正,张氏乃振而起,投考京师影戏教习坊,得高贤传之以摄影术,赖名伶授之以鼓惑功,外邦经典适时泽润,国朝苛禁渐次以松,是以张氏等辈饿极而饱食,囚久而放弛,学成文武艺,效于帝王家,乃以“第五代”伶者自命也。 夫张氏,环眼豹头,虎步狼行,沉毅果决,腹藏珠玑者也。国朝千载之糟粕良莠,黄土百代之兴亡更迭,张氏颇多浸淫,尤喜玩味乎男女之隐情,品咂乎贫贱之苟且,则“黄土地”小试搏名之牛刀,“红高粱”惊爆壮士之野合,“红灯笼”狎玩小妾之隐伤,“秋菊女”状告胯下之奇案,诸如此类,良莠之作迭出,举国叹息,童叟瞠目,西夷击掌,友邦惊诧,于是张氏名矣。 女优者巩,张氏之头牌名伶者也,演而优则媚,张氏笑纳之,进则鹊巢鸠占,张氏乃绝发妻以迎,遂演成江湖艳案。虽然,乃因梨园常态,无损乎名伶艳影,好事者反谓之美谈者也。 张氏之大作屡出,声名日隆,乃以国朝首席之名号觊觎友邦之影戏桂冠者也,于是乎粪土金银千万,“英雄”布“十面埋伏”之阵,意者取奥斯卡如探囊取物耳,未料竟尔铩羽;司礼监收张氏于门下,张氏欣然从命,乃奉命于雅典献短裙大腿之舞,怎奈徒惹士子讥嘲,大臣侧目。则张氏于国朝,竟有鸡肋之叹也。 论者曰:张氏,大才也,虽江河日下,其煌煌扛鼎之作未可遽灭耳。余则谓:然也,然则特立独行,虽才尽犹荣也,自得乎御用,虽大才,其未可久也,况可久荣者乎?

希腊字母

α.Α.alpha       β.Β.beta       γ.Γ.gamma       δ.Δ.delta ε.Ε.epsilon     ζ.Ζ.zeta       η.Η.eta         θ.Θ.theta ι.Ι.iota        κ.Κ.kappa      λ.Λ.lambda      μ.Μ.mu ν.Ν.nu          ξ.Ξ.xi         ο.Ο.omicron     π.Π.pi ρ.Ρ.rho         σ.Σ.sigma      τ.Τ.tau         υ.Υ.upsilon φ.Φ.phi         χ.Χ.chi        ψ.Ψ.psi         ω.Ω.omega

高级扫描技术及原理介绍

Scan,是一切入侵的基础,对主机的探测工具非常多,比如大名鼎鼎的nmap。我这里没有什么新鲜技术,都是一些老东西老话题,即使参考的Phrack文档也甚至是96年的老文档,我只是拾人牙慧而已。 最基本的探测就是Ping,不过现在连基本的个人防火墙都对Ping做了限制,这个也太基本了。如果透过防火墙,如何获得最理想的目标图,也是很多人整天思考的问题。 一、高级ICMP扫描技术 Ping就是利用ICMP协议走的,我们在这里主要是利用ICMP协议最基本的用途:报错,根据网络协议,如果按照协议出现了错误,那么接收端将产生一个ICMP的错误报文。这些错误报文并不是主动发送的,而是由于错误,根据协议自动产生。 当IP数据报出现checksum和版本的错误的时候,目标主机将抛弃这个数据报,如果是checksum出现错误,那么路由器就直接丢弃这个数据报了。有些主机比如AIX、HP-UX等,是不会发送ICMP的Unreachable数据报的。 我们利用下面这些特性: 1、向目标主机发送一个只有IP头的IP数据包,目标将返回Destination Unreachable的ICMP错误报文。 2、向目标主机发送一个坏IP数据报,比如,不正确的IP头长度,目标主机将返回Parameter Problem的ICMP错误报文。 3、当数据包分片但是,却没有给接收端足够的分片,接收端分片组装超时会发送分片组装超时的ICMP数据报。 向目标主机发送一个IP数据报,但是协议项是错误的,比如协议项不可用,那么目标将返回Destination Unreachable的ICMP报文,但是如果是在目标主机前有一个防火墙或者一个其他的过滤装置,可能过滤掉提出的要求,从而接收不到任何回应。可以使用一个非常大的协议数字来作为IP头部的协议内容,而且这个协议数字至少在今天还没有被使用,应该主机一定会返回Unreachable,如果没有Unreachable的ICMP数据报返回错误提示,那么就说明被防火墙或者其他设备过滤了,我们也可以用这个办法来探测是否有防火墙或者其他过滤设备存在。 利用IP的协议项来探测主机正在使用哪些协议,我们可以把IP头的协议项改变,因为是8位的,有256种可能。通过目标返回的ICMP错误报文,来作判断哪些协议在使用。如果返回Destination Unreachable,那么主机是没有使用这个协议的,相反,如果什么都没有返回的话,主机可能使用这个协议,但是也可能是防火墙等过滤掉了。NMAP的IP Protocol scan也就是利用这个原理。 利用IP分片造成组装超时ICMP错误消息,同样可以来达到我们的探测目的。当主机接收到丢失分片的数据报,并且在一定时间内没有接收到丢失的数据报,就会丢弃整个包,并且发送ICMP分片组装超时错误给原发送端。我们可以利用这个特性制造分片的数据包,然后等待ICMP组装超时错误消息。可以对UDP分片,也可以对TCP甚至ICMP数据包进行分片,只要不让目标主机获得完整的数据包就行了,当然,对于UDP这种非连接的不可靠协议来说,如果我们没有接收到超时错误的ICMP返回报,也有可能时由于线路或者其他问题在传输过程中丢失了。 我们能够利用上面这些特性来得到防火墙的ACL(access list),甚至用这些特性来获得整个网络拓扑结构。如果我们不能从目标得到Unreachable报文或者分片组装超时错误报文,可以作下面的判断: 1、防火墙过滤了我们发送的协议类型 2、防火墙过滤了我们指定的端口 3、防火墙阻塞ICMP的Destination Unreachable或者Protocol Unreachable错误消息。 4、防火墙对我们指定的主机进行了ICMP错误报文的阻塞。 二、高级TCP扫描技术 最基本的利用TCP扫描就是使用connect(),这个很容易实现,如果目标主机能够connect,就说明一个相应的端口打开。不过,这也是最原始和最先被防护工具拒绝的一种。 在高级的TCP扫描技术中主要利用TCP连接的三次握手特性来进行,也就是所谓的半开扫描。这些办法可以绕过一些防火墙,而得到防火墙后面的主机信息。当然,是在不被欺骗的情况下的。下面这些方法还有一个好处就是比较难于被记录,有的办法即使在用netstat命令上也根本显示不出来。 SYN 向远端主机某端口发送一个只有SYN标志位的TCP数据报,如果主机反馈一个SYN || ACK数据包,那么,这个主机正在监听该端口,如果反馈的是RST数据包,说明,主机没有监听该端口。在X-Scanner 上就有SYN的选择项。 ACK 发送一个只有ACK标志的TCP数据报给主机,如果主机反馈一个TCP RST数据报来,那么这个主机是存在的。 FIN 对某端口发送一个TCP FIN数据报给远端主机。如果主机没有任何反馈,那么这个主机是存在的,而且正在监听这个端口;主机反馈一个TCP RST回来,那么说明该主机是存在的,但是没有监听这个端口。 NULL 即发送一个没有任何标志位的TCP包,根据RFC793,如果目标主机的相应端口是关闭的话,应该发送回一个RST数据包。 FIN+URG+PUSH 向目标主机发送一个Fin、URG和PUSH分组,根据RFC793,如果目标主机的相应端口是关闭的,那么应该返回一个RST标志。 三、高级UDP扫描技术 在UDP实现的扫描中,多是了利用和ICMP进行的组合进行,这在ICMP中以及提及了。还有一些特殊的就是UDP回馈,比如SQL SERVER,对其1434端口发送‘x02’或者‘x03’就能够探测得到其连接端口。 下面这段程序就是一个TCP探测的例子,当然,并没有做得完美,因为没有接收部分,而在WIN2000下实际就是一个选择性的SNIFFER,呵呵,大家可以使用其他的SNIFFER来实现同样的目的。也可以改变下面的程序只发送IP包,利用ICMP特性来实现探测。 #include <stdio.h> #include <winsock2.h> #include <ws2tcpip.h> [...]

Lucene研究之二——系统结构分析初步

转载自 http://www.jalorsoft.com/holen/holen_lucene_02.html 作者:陈光(holen@263.net) 时间:2004-08-26 本文主要讨论Lucene的系统结构,希望对其结构的初步分析,更深入的了解Lucene的运作机制,从而实现对Lucene的功能扩展。 1. Lucene的包结构 如上图所示,Lucene源码中共包括7个子包,每个包完成特定的功能: Lucene包结构功能表 包名 功能 org.apache.lucene.analysis 语言分析器,主要用于的切词,支持中文主要是扩展此类 org.apache.lucene.document 索引存储时的文档结构管理,类似于关系型数据库的表结构 org.apache.lucene.index 索引管理,包括索引建立、删除等 org.apache.lucene.queryParser 查询分析器,实现查询关键词间的运算,如与、或、非等 org.apache.lucene.search 检索管理,根据查询条件,检索得到结果 org.apache.lucene.store 数据存储管理,主要包括一些底层的I/O操作 org.apache.lucene.util 一些公用类 2. Lucene的主要逻辑图 Lucene功能强大,但从根本上说,主要包括两块:一是文本内容经切词后索引入库;二是根据查询条件返回结果。 以下是上述两大功能的逻辑图: 查询逻辑 按先后顺序,查询逻辑可分为如下几步: 1.  查询者输入查询条件 条件之间可以通过特定运算符进行运算,比如查询希望查询到与“中国”和“北京”相关的记录,但不希望结果中包括“海淀区中关村”,于是输入条件为“中国+北京-海淀区中关村”; 2.  查询条件被传达到查询分析器中,分析器将将对“中国+北京-海淀区中关村”进行分析,首先分析器解析字符串的连接符,即这里的加号和减号,然后对每个词进行切词,一般最小的词元是两个汉字,则中国和北京两个词不必再切分,但对海淀区中关村需要切分,假设根据切词算法,把该词切分为“海淀区”和“中关村”两部分,则最后得到的查询条件可以表示为:“中国” AND “北京” AND NOT(“海淀区” AND “中关村”)。 3.  查询器根据这个条件遍历索引树,得到查询结果,并返回结果集,返回的结果集类似于JDBC中的ResultSet。 4.  将返回的结果集显示在查询结果页面,当点击某一条内容时,可以链接到原始网页,也可以打开全文检索库中存储的网页内容。 这就是查询的逻辑过程,需要说明的是,Lucene默认只支持英文,为了便于说明问题,以上查询过程采用中文举例,事实上,当Lucene被扩充支持中文后就是这么一个查询过程。 入库逻辑 入库将把内容加载到全文检索库中,按顺序,入库逻辑包括如下过程: 1.  入库者定义到库中文档的结构,比如需要把网站内容加载到全文检索库,让用户通过“站内检索”搜索到相关的网页内容。入库文档结构与关系型数据库中的表结构类似,每个入库的文档由多个字段构成,假设这里需要入库的网站内容包括如下字段:文章标题、作者、发布时间、原文链接、正文内容(一般作为网页快照)。 2.  包含N个字段的文档(DOCUMENT)在真正入库前需要经过切词(或分词)索引,切词的规则由语言分析器(ANALYZER)完成。 3.  切分后的“单词”被注册到索引树上,供查询时用,另外也需要也其它不需要索引的内容入库,所有这些是文件操作均由STORAGE完成。 [...]

Lucene研究之一——起源、现状及初步应用

转载自 http://www.jalorsoft.com/holen/holen_lucene_01.html 本文是Lucene研究文集的首篇,主要介绍了Lucene的起源、发展、现状,以及Luence的初步应用,可以作为了解和学习Lucene的入门资料。 1. 起源与发展 Lucene是一个高性能、纯Java的全文检索引擎,而且免费、开源。Lucene几乎适合于任何需要全文检索的应用,尤其是跨平台的应用。 Lucene的作者Doug Cutting是一个资深的全文检索专家,刚开始,Doug Cutting将Lucene发表在自己的主页上,2000年3月将其转移到sourceforge,于2001年10捐献给Apache,作为Jakarta的一个子工程。 2.使用现状 经过多年的发展,Lucene在全文检索领域已经有了很多的成功案例,并积累了良好的声誉。 基于Lucene的全文检索产品(Lucene本身只是一个组件,而非一个完整的应用)和应用Lucene的项目在世界各地已经非常之多,比较知名的有: l         Eclipse:主流Java开发工具,其帮助文档采用Lucene作为检索引擎 l         Jive:知名论坛系统,其检索功能基于Lucene l         Ifinder:出自德国的网站检索系统,基于Lucene(http://ifinder.intrafind.org/) l         MIT DSpace Federation:一个文档管理系统(http://www.dspace.org/) 国内外采用Lucene作为网站全文检索引擎的也很多,比较知名的有: l         http://www.blogchina.com/weblucene/ l         http://www.ioffer.com/ l         http://search.soufun.com/ l         http://www.taminn.com/ (更多案例,请参见http://wiki.apache.org/jakarta-lucene/PoweredBy) 在所有这些案例中,开源应用占了很大一部分,但更多的还是商化业产品和网站。毫不夸张的说,Lucene的出现,极大的推动了全文检索技术在各个行业或领域中的深层次应用。 3.初步应用 前面提到,Lucene本身只是一个组件,而非一个完整的应用,所以若想让Lucene跑起来,还得在Lucene基础上进行必要的二次开发。 下载与安装 首先,你需要到Lucene的官方网站http://jakarta.apache.org/lucene/ 去下载一份拷贝,最新版是1.4。下载后将得到一个名为lucene-1.4-final.zip的压缩文件,将其解压,里面有一个名为lucene-1.4-final.jar的文件,这就是Lucene组件包了,若需要在项目使用Lucene,只需要把lucene-1.4-final.jar置于类路径下即可,至于解压后的其他文件都是参考用的。 接下来,我用Eclipse建立一个工程,实现基于Lucene的建库、记录加载和记录查询等功能。 如上图所示,这是开发完成后的工程,其中有三个源文件CreateDataBase.java,InsertRecords.java,QueryRecords.java,分别实现建库、入库、检索的功能。 以下是对这三个源文件的分析。 建库源码及说明 CreateDataBase.java package com.holen.part1; import java.io.File; import org.apache.lucene.analysis.standard.StandardAnalyzer; import org.apache.lucene.index.IndexWriter; /** * @author Holen [...]