??xml version="1.0" encoding="utf-8" standalone="yes"?>
选择题:
1.两个长度各ؓN的有序数l进行合qӞ求可能的最多的比较ơ数Q(2n-1Q?br>2.两个长度为N的有序数l,要求在这两个数组中排WN的元素,最的旉复杂度? Q?O(logn)Q类g分搜索)
3.逆L兰表辑ּ求|Q竟然画了很久的后缀表达式没d来,真杯兗。直接求值就行了Q?br>4.一个关于二叉树的问题,大意是要在二叉树查找某个元素Q求选项l出的查扑ֺ列哪个不可能出现Q(考察二叉树的性质Q?br>5.excell的列表示如AB...Z, AA AB ....ZZ, AAA AAB .... ZZZ, 求DEF的十q制|?6q制的|直接计算Q?br>6.函数指针数组的写法问题。?br>7.虚函数问题,大意是基cd义了一个保护成员,构造函数初始化?Q还定义了一个虚函数Q基cL成?-Q而子cd重定义了虚函敎ͼ成?+Q主函数里,new了一个子cd象,然后定义一个基cL针指向此对象Q又定义了一个基cd用指向此基类指针指向的对象,然后分别调用了虚函数Q要求基cd义的成员的倹{?br>8.l出一D늨序,要求输出|直接计算。程序里计算字符数组 char a[]={'a','b','c'}的长度采用sizeof(a)/sizeof(a[0])的方法?br>9.指出l出选项中不可能存储在栈中的是。。。(全局静态变量,攑֜静态区中)
10.l出char *p="hello world", char a[]="byebye",strncpy(p,a,6),问这个程序运行后p的结果是什么?(q里*p是一个字W串帔RQ不能对它的元素q行修改Q所以程序在q行时会出错)
主观题编E题Q?br>大意是给Z个数l,q个数组每个元素都不同,q且可能是升序的Q或者是升序+旋{后的l果Q例?,2,3,4,5,或?4,5,1,2,3 或?3,4,5,1,2{等Q?br>然后l一个数Q要扑ևq个数在所l数l中的烦引值或者返?1Q要求复杂度必须于o(n)?br>相对比较单吧Q首先是判断是否是从左到x升序的,若是Q则用二分查找,复杂度ؓo(logn),如果不是Q则Ҏ要找的gW一个值比较的l果Q在左半部分或右半部分查找这个数Q易知,查找ơ数肯定于nQ因而复杂度W合要求?br>W二个小题是要给Z些测试数据ƈ加以说明?br>正式扑ַ的第一场面试,不是很顺利,Ҏ记录Q攒下RP, ^.^
Ҏ1Q可以估计每个文件安的大ؓ50G×64=320GQ远q大于内存限制的4G。所以不可能其完全加蝲到内存中处理。考虑采取分而治之的Ҏ?/p>
s 遍历文gaQ对每个url求取Q然后根据所取得的值将url分别存储?a name=baidusnap0>1000个小文gQ记?a >
Q中。这h个小文g的大Uؓ300M?/p>
s 遍历文gbQ采取和a相同的方式将url分别存储?strong style="BACKGROUND-COLOR: #ffff66; COLOR: black">100
0各小文gQ记?a >s 求每对小文g中相同的urlӞ可以把其中一个小文g的url存储到hash_set中。然后遍历另一个小文g的每个urlQ看其是否在刚才构徏的hash_set中,如果是,那么是共同的urlQ存到文仉面就可以了?/p>
Ҏ2Q如果允许有一定的错误率,可以使用Bloom filterQ?G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射340亿bitQ然后挨个读取另外一个文件的urlQ检查是否与Bloom filterQ如果是Q那么该url应该是共同的urlQ注意会有一定的错误率)?/p>
2. ?0个文Ӟ每个文g1GQ每个文件的每一行存攄都是用户的queryQ每个文件的query都可能重复。要求你按照query的频度排序?/strong>
Ҏ1Q?/p>
s 序d10个文Ӟ按照hash(query)%10的结果将query写入到另?0个文ӞCؓQ中。这h生成的文件每个的大小大约?GQ假设hash函数是随机的Q?/p>
s 找一台内存在2G左右的机器,依次?a >用hash_map(query, query_count)来统计每个query出现的次数。利用快??归ƈ排序按照出现ơ数q行排序。将排序好的query和对应的query_cout输出到文件中。这样得C10个排好序的文ӞCؓ
Q?/p>
s ?a >q?0个文件进行归q排序(内排序与外排序相l合Q?/p>
Ҏ2Q?/p>
一般query的总量是有限的Q只是重复的ơ数比较多而已Q可能对于所有的queryQ一ơ性就可以加入到内存了。这P我们可以采用trie?hash_map{直接来l计每个query出现的次敎ͼ然后按出现次数做快??归ƈ排序可以了?/p>
Ҏ3Q?/p>
与方?cMQ但在做完hashQ分成多个文件后Q可以交l多个文件来处理Q采用分布式的架构来处理Q比如MapReduceQ,最后再q行合ƈ?/p>
3. 有一?G大小的一个文Ӟ里面每一行是一个词Q词的大不过16字节Q内存限制大是1M。返回频数最高的100个词?/strong>
Ҏ1Q顺序读文g中,对于每个词xQ取Q然后按照该值存?000个小文gQ记?a >
Q中。这h个文件大概是200k左右。如果其中的有的文g过?M大小Q还可以按照cM?strong style="BACKGROUND-COLOR: #880000; COLOR: white">Ҏl箋往下分Q知道分解得到的文件的大小都不过1M。对每个文Ӟl计每个文g中出现的词以及相应的频率Q可以采用trie?hash_map{)Qƈ取出出现频率最大的100个词Q可以用?strong style="BACKGROUND-COLOR: #ffff66; COLOR: black">100个结点的最堆Q,q把100词及相应的频率存入文Ӟq样又得C5000个文件。下一步就是把q?000个文件进行归qӞcM与归q排序)的过E了?/p>
4. 量日志数据Q提取出某日讉K癑ֺơ数最多的那个IP?/strong>
Ҏ1Q首先是q一天,q且是访问百度的日志中的IP取出来,逐个写入C个大文g中。注意到IP?2位的Q最多有个IP。同样可以采用映的ҎQ比如模1000Q把整个大文件映ؓ1000个小文gQ再扑և每个文中出现频率最大的IPQ可以采用hash_mapq行频率l计Q然后再扑և频率最大的几个Q及相应的频率。然后再在这1000个最大的IP中,扑և那个频率最大的IPQ即为所求?/p>
5. ?.5亿个整数中找Z重复的整敎ͼ内存不以容U2.5亿个整数?/strong>
Ҏ1Q采?-BitmapQ每个数分配2bitQ?0表示不存在,01表示出现一ơ,10表示多次Q?1无意义)q行Q共需内存内存Q还可以接受。然后扫描这2.5亿个整数Q查看Bitmap中相对应位,如果?0?1Q?1?0Q?0保持不变。所描完事后Q查看bitmapQ把对应位是01的整数输出即可?/p>
Ҏ2Q也可采用上题类似的ҎQ进行划分小文g?strong style="BACKGROUND-COLOR: #880000; COLOR: white">Ҏ。然后在文件中扑և不重复的整数Qƈ排序。然后再q行归ƈQ注意去除重复的元素?/p>
6. 量数据分布?strong style="BACKGROUND-COLOR: #ffff66; COLOR: black">100台电脑中Q想个办法高校统计出q批数据的TOP10?/strong>
Ҏ1Q?/p>
s 在每台电脑上求出TOP10Q可以采用包?0个元素的堆完成(TOP10,用最大堆QTOP10大,用最堆Q。比如求TOP10大,我们首先取前10个元素调整成最堆Q如果发玎ͼ然后扫描后面的数据,q与堆顶元素比较Q如果比堆顶元素大,那么用该元素替换堆顶Q然后再调整为最堆。最后堆中的元素是TOP10大?/p>
s 求出每台电脑上的TOP10后,然后把这100台电脑上的TOP10l合hQ共1000个数据,再利用上面类似的Ҏ求出TOP10可以了?/p>
7. 怎么在v量数据中扑և重复ơ数最多的一个?
Ҏ1Q先做hashQ然后求模映ؓ文Ӟ求出每个文件中重复ơ数最多的一个,q记录重复次数。然后找Z一步求出的数据中重复次数最多的一个就是所求(具体参考前面的题)?/p>
8. 上千万或上亿数据Q有重复Q,l计其中出现ơ数最多的钱N个数据?/strong>
Ҏ1Q上千万或上亿的数据Q现在的机器的内存应该能存下。所以考虑采用hash_map/搜烦二叉?U黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了,可以用第6题提到的堆机制完成?/p>
9. 1000万字W串Q其中有些是重复的,需要把重复的全部去掉,保留没有重复的字W串。请怎么设计和实玎ͼ
Ҏ1Q这题用trie树比较合适,hash_map也应该能行?/p>
10. 一个文本文Ӟ大约有一万行Q每行一个词Q要求统计出其中最频繁出现的前10个词Q请l出思想Q给出时间复杂度分析?/strong>
Ҏ1Q这题是考虑旉效率。用trie树统计每个词出现的次敎ͼ旉复杂度是O(n*le)Qle表示单词的^准长度)。然后是扑և出现最频繁的前10个词Q可以用堆来实现Q前面的题中已经讲到了,旉复杂度是O(n*lg10)。所以ȝ旉复杂度,是O(n*le)与O(n*lg10)中较大的哪一个?/p>
11. 一个文本文Ӟ扑և?0个经常出现的词,但这ơ文件比较长Q说是上亿行或十亿行QM无法一ơ读入内存,问最优解?/strong>
Ҏ1Q首先根据用hashq求模,文件分解ؓ多个文Ӟ对于单个文g利用上题?strong style="BACKGROUND-COLOR: #880000; COLOR: white">Ҏ求出每个文g件中10个最常出现的词。然后再q行归ƈ处理Q找出最l的10个最常出现的词?/p>
12. 100w个数中找出最大的100个数?/strong>
Ҏ1Q在前面的题中,我们已经提到了,用一个含100个元素的最堆完成。复杂度为O(100w*lg100)?/p>
Ҏ2Q采用快速排序的思想Q每ơ分割之后只考虑比u大的一部分Q知道比轴大的一部分在比100多的时候,采用传统排序法排序Q取?strong style="BACKGROUND-COLOR: #ffff66; COLOR: black">100个。复杂度为O(100w*100)?/p>
Ҏ3Q采用局部淘汰法。选取?strong style="BACKGROUND-COLOR: #ffff66; COLOR: black">100个元素,q排序,Cؓ序列L。然后一ơ扫描剩余的元素xQ与排好序的100个元素中最的元素比,如果比这个最的要大Q那么把q个最的元素删除Qƈ把x利用插入排序的思想Q插入到序列L中。依ơ@环,知道扫描了所有的元素。复杂度为O(100w*100)?/p>
13. L热门查询Q?/strong>
搜烦引擎会通过日志文g把用hơ检索用的所有检索串都记录下来,每个查询串的长度?-255字节。假讄前有一千万个记录,q些查询串的重复L较高Q虽然L?千万Q但是如果去除重复和Q不过3百万个。一个查询串的重复度高Q说明查询它的用戯多,也就热门。请你统计最热门?0个查询串Q要求用的内存不能过1G?/p>
(1) hqC解决q个问题的思\Q?/p>
(2) LZ要的处理程Q算法,以及法的复杂度?/p>
Ҏ1Q采用trie树,关键字域存该查询串出现的ơ数Q没有出Cؓ0。最后用10个元素的最推来对出现频率q行排序?/p>
14. 一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数q对它们操作。如何找?a >个数中的中数Q?/strong>
Ҏ1Q先大体估计一下这些数的范_比如q里假设q些数都?2位无W号整数Q共?a >个)。我们把0?a >
的整数划分ؓN个范围段Q每个段包含
个整数。比如,W一个段??a >
Q第二段?a >
?a >
Q?#8230;Q第N个段?a >
?a >
。然后,扫描每个机器上的N个数Q把属于W一个区D늚数放到第一个机器上Q属于第二个区段的数攑ֈW二个机器上Q?#8230;Q属于第N个区D늚数放到第N个机器上。注意这个过E每个机器上存储的数应该是O(N)的。下面我们依ơ统计每个机器上数的个数Q一ơ篏加,直到扑ֈWk个机器,在该机器上篏加的数大于或{于
Q而在Wk-1个机器上的篏加数于
Qƈ把这个数Cؓx。那么我们要扄中位数在Wk个机器中Q排在第
位。然后我们对Wk个机器的数排序,q找出第
个数Q即为所求的中位数。复杂度?a >
的?/p>
Ҏ2Q先Ҏ台机器上的数q行排序。排好序后,我们采用归ƈ排序的思想Q将qN个机器上的数归ƈh得到最l的排序。找到第个便是所求。复杂度?a >
的?/p>
15. 最大间隙问?/strong>
l定n个实?a >Q求着n个实数在实u上向?个数之间的最大差|要求U性的旉法?/p>
Ҏ1Q最先想到的Ҏ是先对qn个数据进行排序,然后一遍扫描即可确定相ȝ最大间隙。但?strong style="BACKGROUND-COLOR: #880000; COLOR: white">Ҏ不能满U性时间的要求。故采取如下ҎQ?/p>
s 扑ֈn个数据中最大和最数据max和min?/p>
s 用n-2个点{分区间[min, max]Q即[min, max]{分为n-1个区_前闭后开区间Q,这些区间看作桶Q编号ؓQ且?a >
的上界和桶i+1的下届相同,x个桶的大相同。每个桶的大ؓQ?a >
。实际上Q这些桶的边界构成了一个等差数列(首项为minQ公差ؓ
Q,且认为将min攑օW一个桶Q将max攑օWn-1个桶?/p>
s n个数攑օn-1个桶中:每个元?a >分配到某个桶Q编号ؓindexQ,其中
Qƈ求出分到每个桶的最大最数据?/p>
s 最大间隙:除最大最数据max和min以外的n-2个数据放入n-1个桶中,由抽屉原理可知至有一个桶是空的,又因为每个桶的大相同,所以最大间隙不会在同一桶中出现Q一定是某个桶的上界和气候某个桶的下界之间隙Q且该量{之间的Ӟ即便好在该连个便好之间的Ӟ一定是I桶。也是_最大间隙在桶i的上界和桶j的下界之间?a >。一遍扫描即可完成?/p>
16. 多个集合合q成没有交集的集合:l定一个字W串的集合,格式如:。要求将其中交集不ؓI的集合合ƈQ要求合q完成的集合之间无交集,例如上例应输?a >
?/strong>
(1) hqC解决q个问题的思\Q?/p>
(2) l出主要?strong style="BACKGROUND-COLOR: #ff66ff; COLOR: black">处理程Q算法,以及法的复杂度Q?/p>
(3) hq可能的改进?/p>
Ҏ1Q采用ƈ查集。首先所有的字符串都在单独的q查集中。然后依扫描每个集合Q顺序合q将两个盔R元素合ƈ。例如,对于Q首先查看aaa和bbb是否在同一个ƈ查集中,如果不在Q那么把它们所在的q查集合qӞ然后再看bbb和ccc是否在同一个ƈ查集中,如果不在Q那么也把它们所在的q查集合q。接下来再扫描其他的集合Q当所有的集合都扫描完了,q查集代表的集合便是所求。复杂度应该是O(NlgN)的。改q的话,首先可以记录每个节点的根l点Q改q查询。合q的时候,可以把大的和的q行合,q样也减复杂度?/p>
17. 最大子序列与最大子矩阵问题
数组的最大子序列问题Q给定一个数l,其中元素有正Q也有负Q找出其中一个连l子序列Q和最大?/p>
Ҏ1Q这个问题可以动态规划的思想解决。设表示以第i个元?a >
l尾的最大子序列Q那么显?a >
。基于这一点可以很快用代码实现?/p>
最大子矩阵问题Q给定一个矩阵(二维数组Q,其中数据有大有小Q请找一个子矩阵Q得子矩阵的和最大,q输个和?/p>
Ҏ1Q可以采用与最大子序列cM的思想来解冟뀂如果我们确定了选择Wi列和Wj列之间的元素Q那么在q个范围内,其实是一个最大子序列问题。如何确定第i列和Wj列可以词用暴搜的Ҏq行?/p>
1. 安装增强功能?Guest Additions)
安装?u>ubuntu后,q行Ubuntuq登录。然后在VirtualBox的菜单里选择"讑֤(Devices)" -> "安装增强功能?Install Guest Additions)"?/p>
你会发现在Ubuntu桌面上多Z个光盘图标,q张光盘默认被自动加载到了文件夹/media/cdom0。进入命令行l端Q输入:
cd /media/cdom0
sudo ./VboxLinuxAdditions.run
开始安装工具包。安装完毕后会提C重启Ubuntu?/p>
2. 讄׃n文g?/p>
重启完成后点?讑֤(Devices)" -> ׃n文g?Shared Folders)菜单Q添加一个共享文件夹Q选项固定和时是指该文gҎ否是持久的。共享名可以d一个自己喜Ƣ的Q比?gongxiang"Q尽量用英文名U?/p>
3. 挂蝲׃n文g?/p>
重新q入虚拟UbuntuQ在命o行终端下输入Q?/p>
sudo mkdir /mnt/shared
sudo mount -t vboxsf gongxiang /mnt/shared
其中"gongxiang"是之前创建的׃n文g夹的名字。OKQ现在Ubuntu和主机可以互传文件了?/p>
假如您不x一ơ都手动挂蝲Q可以在/etc/fstab中添加一?/p>
gongxiang /mnt/shared vboxsf rw,gid=100,uid=1000,auto 0 0
q样p够自动挂载了?/p>
4. 卸蝲的话使用下面的命令:
sudo umount -f /mnt/shared
注意Q?/p>
׃n文g夹的名称千万不要和挂载点的名U相同。比如,上面的挂载点?mnt/sharedQ如果共享文件夹的名字也是shared的话Q在挂蝲的时候就会出现如下的错误信息(?a >http://www.virtualbox.org/ticket/2265)Q?/p>
/sbin/mount.vboxsf: mounting failed with the error: Protocol error
原因分析可以看Tips on running Sun Virtualbox的Shared Folder on a Linux Guest节?/p>
1、副本的存放Q副本的存放?/span>HDFS可靠性和性能的关键?/span>HDFS采用一U称?/span>rack-aware的策略来改进数据的可靠性、有效性和|络带宽的利用。这个策略实现的短期目标是验证在生环境下的表现Q观察它的行为,构徏试和研I的基础Q以便实现更先进的策略。庞大的HDFS实例一般运行在多个机架的计机形成的集上Q不同机枉的两台机器的通讯需要通过交换机,昄通常情况下,同一个机架内的两个节炚w的带宽会比不同机枉的两台机器的带宽大?/span>
通过一个称?/span>Rack Awareness的过E,Namenode军_了每?/span>Datanode所属的rack id。一个简单但没有优化的策略就是将副本存放在单独的机架上。这样可以防止整个机Ӟ非副本存放)失效的情况,q且允许L据的时候可以从多个机架d。这个简单策略设|可以将副本分布在集中Q有利于lgp|情况下的负蝲均衡。但是,q个单策略加大了写的代hQ因Z个写操作需要传?/span>block到多个机架?/span>
在大多数情况下,replication因子?/span>3Q?/span>HDFS的存攄略是一个副本存攑֜本地机架上的节点Q一个副本放在同一机架上的另一个节点,最后一个副本放在不同机架上的一个节炏V机架的错误q远比节点的错误,q个{略不会影响到数据的可靠性和有效性。三分之一的副本在一个节点上Q三分之二在一个机架上Q其他保存在剩下的机架中Q这一{略改进了写的性能?/span>
2、副本的选择Qؓ了降低整体的带宽消耗和dgӞHDFS会尽量让readerLq的副本。如果在reader的同一个机架上有一个副本,那么p该副本。如果一?/span>HDFS集群跨越多个数据中心Q那?/span>reader也将首先试L地数据中心的副本?/span>
3?/span>SafeMode
Namenode启动后会q入一个称?/span>SafeMode的特D状态,处在q个状态的Namenode是不会进行数据块的复制的?/span>Namenode从所有的 Datanode接收心蟩包和Blockreport?/span>Blockreport包括了某?/span>Datanode所有的数据块列表。每?/span>block都有指定的最数目的副本。当Namenode确认某?/span>Datanode的数据块副本的最数目,那么?/span>Datanode׃被认为是安全的;如果一定百分比Q这个参数可配置Q的数据块检确认是安全的,那么Namenode退?/span>SafeMode状态,接下来它会确定还有哪些数据块的副本没有达到指定数目,q将q些block复制到其?/span>Datanode?/span>
五、文件系l元数据的持久化
Namenode存储HDFS的元数据。对于Q何对文g元数据生修改的操作Q?/span>Namenode都用一个称?/span>Editlog的事务日志记录下来。例如,?/span>HDFS中创Z个文ӞNamenode׃?/span>Editlog中插入一条记录来表示Q同P修改文g?/span>replication因子也将往 Editlog插入一条记录?/span>Namenode在本?/span>OS的文件系l中存储q个Editlog。整个文件系l的namespaceQ包?/span>block到文件的映射、文件的属性,都存储在UCؓFsImage的文件中Q这个文件也是放?/span>Namenode所在系l的文gpȝ上?/span>
Namenode在内存中保存着整个文gpȝnamespace和文?/span>Blockmap的映像。这个关键的元数据设计得很紧凑,因而一个带?/span>4G内存?Namenode_支撑量的文件和目录。当Namenode启动Ӟ它从盘中读?/span>Editlog?/span>FsImageQ将所?/span>Editlog中的事务作用Q?/span>apply)在内存中?/span>FsImage Qƈ这个新版本?/span>FsImage从内存中flush到硬盘上,然后?/span>truncateq个旧的EditlogQ因个旧?/span>Editlog的事务都已经作用?/span>FsImage上了。这个过E称?/span>checkpoint。在当前实现中,checkpoint只发生在Namenode启动Ӟ在不久的来我们实现支持周期性的checkpoint?/span>
Datanodeq不知道关于文g的Q何东西,除了文件中的数据保存在本地的文件系l上。它把每?/span>HDFS数据块存储在本地文gpȝ上隔ȝ文g中?Datanodeq不在同一个目录创建所有的文gQ相反,它用启发式地Ҏ来确定每个目录的最x件数目,q且在适当的时候创建子目录。在同一个目录创建所有的文g不是最优的选择Q因为本地文件系l可能无法高效地在单一目录中支持大量的文g。当一?/span>Datanode启动Ӟ它扫描本地文件系l,对这些本地文件生相应的一个所?/span>HDFS数据块的列表Q然后发送报告到NamenodeQ这个报告就?/span>Blockreport?/span>
六、通讯协议
所有的HDFS通讯协议都是构徏?/span>TCP/IP协议上。客L通过一个可配置的端口连接到NamenodeQ通过ClientProtocol?Namenode交互。?/span>Datanode是?/span>DatanodeProtocol?/span>Namenode交互。从ClientProtocol?Datanodeprotocol抽象Z个远E调?/span>(RPCQ,在设计上Q?/span>Namenode不会d发vRPCQ而是是响应来自客L?Datanode ?/span>RPCh?/span>
七、健壮?/span>
HDFS的主要目标就是实现在p|情况下的数据存储可靠性。常见的三种p|Q?/span>Namenode failures, Datanode failures和网l分Ԍnetwork partitions)?/span>
1、硬盘数据错误、心x和重新复制
每个Datanode节点都向Namenode周期性地发送心跛_。网l切割可能导致一部分Datanode?/span>Namenode失去联系?Namenode通过心蟩包的~失到q一情况Qƈ这?/span>Datanode标记?/span>deadQ不会将新的IOh发给它们。寄存在dead Datanode上的M数据不再有效?/span>Datanode的死亡可能引起一?/span>block的副本数目低于指定|Namenode不断地跟t需要复制的 blockQ在M需要的情况下启动复制。在下列情况可能需要重新复Ӟ某个Datanode节点失效Q某个副本遭到损坏,Datanode上的盘错误Q或者文件的replication因子增大?/span>
2、集均?/span>
HDFS支持数据的均衡计划,如果某个Datanode节点上的I闲I间低于特定的界点Q那么就会启动一个计划自动地数据从一?/span>Datanode搬移到空闲的Datanode。当Ҏ个文件的hH然增加Q那么也可能启动一个计划创文g新的副本Qƈ分布到集中以满_用的要求。这些均衡计划目前还没有实现?/span>
3、数据完整?/span>
从某?/span>Datanode获取的数据块有可能是损坏的,q个损坏可能是由?/span>Datanode的存储设备错误、网l错误或者Y?/span>bug造成的?/span>HDFS客户端Y件实CHDFS文g内容的校验和。当某个客户端创Z个新?/span>HDFS文gQ会计算q个文g每个block的校验和Qƈ作ؓ一个单独的隐藏文g保存q些校验和在同一?/span>HDFS namespace下。当客户端检索文件内容,它会认?/span>Datanode获取的数据跟相应的校验和文g中的校验和是否匹配,如果不匹配,客户端可以选择从其?/span>Datanode获取?/span>block的副本?/span>
4、元数据盘错误
FsImage?/span>Editlog?/span>HDFS的核心数据结构。这些文件如果损坏了Q整?/span>HDFS实例都将失效。因而,Namenode可以配置成支持维护多?/span>FsImage?/span>Editlog的拷贝。Q何对FsImage或?/span>Editlog的修改,都将同步到它们的副本上。这个同步操作可能会降低 Namenode每秒能支持处理的namespace事务。这个代h可以接受的,因ؓHDFS是数据密集的Q而非元数据密集。当Namenode重启的时候,它L选取最q的一致的FsImage?/span>Editlog使用?/span>
Namenode?/span>HDFS是单点存在,如果Namenode所在的机器错误Q手工的q预是必ȝ。目前,在另一台机器上重启因故障而停止服务的Namenodeq个功能q没实现?/span>
5、快?/span>
快照支持某个旉的数据拷贝,?/span>HDFS数据损坏的时候,可以恢复到过M个已知正的旉炏V?/span>HDFS目前q不支持快照功能?/span>
八、数据组l?/span>
1、数据块
兼容HDFS的应用都是处理大数据集合的。这些应用都是写数据一ơ,d是一ơ到多次Qƈ且读的速度要满x式读?/span>HDFS支持文g?/span>write- once-read-many语义。一个典型的block大小?/span>64MBQ因而,文gL按照64M切分?/span>chunkQ每?/span>chunk存储于不同的 Datanode
2、步?/span>
某个客户端创建文件的h其实q没有立卛_l?/span>NamenodeQ事实上Q?/span>HDFS客户端会文件数据缓存到本地的一个时文件。应用的写被透明地重定向到这个时文件。当q个临时文g累积的数据超q一?/span>block的大(默认64M)Q客L才会联系Namenode?/span>Namenode文件名插入文gpȝ的层ơ结构中Qƈ且分配一个数据块l它Q然后返?/span>Datanode的标识符和目标数据块l客L。客L本C时文?/span>flush到指定的 Datanode上。当文g关闭Ӟ在时文件中剩余的没?/span>flush的数据也会传输到指定?/span>DatanodeQ然后客L告诉Namenode文g已经关闭。此?/span>Namenode才将文g创徏操作提交到持久存储。如?/span>Namenode在文件关闭前挂了Q该文g丢失?/span>
上述Ҏ是对通过?/span>HDFS上运行的目标应用认真考虑的结果。如果不采用客户端缓存,׃|络速度和网l堵塞会对吞估量造成比较大的影响?/span>
3、流水线复制
当某个客L?/span>HDFS文g写数据的时候,一开始是写入本地临时文gQ假设该文g?/span>replication因子讄?/span>3Q那么客L会从Namenode 获取一?/span>Datanode列表来存攑։本。然后客L开始向W一?/span>Datanode传输数据Q第一?/span>Datanode一部分一部分(4kb)地接收数据,每个部分写入本C库,q且同时传输该部分到W二?/span>Datanode节点。第二个Datanode也是q样Q边收边传,一部分一部分地Ӟ存储在本C库,同时传给W三?/span>DatanodeQ第三个Datanode׃仅是接收q存储了。这是水U式的复制?/span>
九、可讉K?/span>
HDFSl应用提供了多种讉K方式Q可以通过DFSShell通过命o行与HDFS数据q行交互Q可以通过java API调用Q也可以通过C语言的封?/span>API讉KQƈ且提供了览器访问的方式。正在开发通过WebDav协议讉K的方式。具体用参考文档?/span>
十、空间的回收
1、文件的删除和恢?/span>
用户或者应用删除某个文Ӟq个文gq没有立MHDFS中删除。相反,HDFS这个文仉命名Qƈ转移?/span>/trash目录。当文gq在/trash目录Ӟ该文件可以被q速地恢复。文件在/trash中保存的旉是可配置的,当超q这个时_Namenode׃该文g?/span>namespace中删除。文件的删除Q也释攑օ联该文g的数据块。注意到Q在文g被用户删除和HDFSI闲I间的增加之间会有一个等待时间gq?/span>
当被删除的文件还保留?/span>/trash目录中的时候,如果用户x复这个文Ӟ可以索浏?/span>/trash目录q检索该文g?/span>/trash目录仅仅保存被删除文件的最q一ơ拷贝?/span>/trash目录与其他文件目录没有什么不同,除了一点:HDFS在该目录上应用了一个特D的{略来自动删除文Ӟ目前的默认策略是删除保留过6时的文Ӟq个{略以后会定义成可配|的接口?/span>
2?/span>Replication因子的减?/span>
当某个文件的replication因子减小Q?/span>Namenode会选择要删除的q剩的副本。下ơ心x就该信息传递给DatanodeQ?Datanode׃U除相应?/span>blockq攄_同样Q在调用setReplicationҎ和集中的空闲空间增加之间会有一个时间gq?/span>
参考资料:
HDFS Java API: http://hadoop.apache.org/core/docs/current/api/
HDFS source code: http://hadoop.apache.org/core/version_control.html
先决条g
请先认Hadoop被正安装、配|和正常q行中。更多信息见Q?/p>
Hadoop快速入门对初次使用者?
Hadoop集群搭徏对大规模分布式集?
概述
Hadoop Map/Reduce是一个用简易的软g框架Q基于它写出来的应用E序能够q行在由上千个商用机器组成的大型集群上,q以一U可靠容错的方式q行处理上TU别的数据集?/p>
一个Map/Reduce 作业QjobQ?通常会把输入的数据集切分q独立的数据块,?mapdQtaskQ以完全q行的方式处理它们。框架会对map的输出先q行排序Q?然后把结果输入给reduced。通常作业的输入和输出都会被存储在文gpȝ中?整个框架负责d的调度和监控Q以及重新执行已l失败的d?/p>
通常QMap/Reduce框架和分布式文gpȝ是运行在一l相同的节点上的Q也是_计算节点和存储节炚w常在一赗这U配|允许框架在那些已经存好数据的节点上高效地调度Q务,q可以整个集群的网l带宽被非常高效地利用?/p>
Map/Reduce框架׃个单独的master JobTracker 和每个集节点一个slave TaskTracker共同l成。master负责调度构成一个作业的所有Q务,q些d分布在不同的slave上,master监控它们的执行,重新执行已经p|的Q务。而slave仅负责执行由master指派的Q务?/p>
应用E序臛_应该指明输入/输出的位|(路径Q,q过实现合适的接口或抽象类提供map和reduce函数。再加上其他作业的参敎ͼ构成了作业配置Qjob configurationQ。然后,Hadoop?job client提交作业Qjar?可执行程序等Q和配置信息lJobTrackerQ后者负责分发这些Y件和配置信息lslave、调度Q务ƈ监控它们的执行,同时提供状态和诊断信息ljob-client?/p>
虽然Hadoop框架是用JavaTM实现的,但Map/Reduce应用E序则不一定要?Java来写 ?/p>
Hadoop Streaming是一U运行作业的实用工具Q它允许用户创徏和运行Q何可执行E序 Q例如:Shell工具Q来做ؓmapper和reducer?
Hadoop Pipes是一个与SWIG兼容的C++ API Q没有基于JNITM技术)Q它也可用于实现Map/Reduce应用E序?
输入与输?br>Map/Reduce框架q{?lt;key, value> 键值对上,也就是说Q?框架把作业的输入看ؓ是一l?lt;key, value> 键值对Q同样也产出一l?<key, value> 键值对做ؓ作业的输出,q两l键值对的类型可能不同?/p>
框架需要对key和value的类(classes)q行序列化操作, 因此Q这些类需要实?Writable接口?另外Qؓ了方便框架执行排序操作,keycdd?WritableComparable接口?/p>
一个Map/Reduce 作业的输入和输出cd如下所C:
(input) <k1, v1> -> map -> <k2, v2> -> combine -> <k2, v2> -> reduce -> <k3, v3> (output)
例子QWordCount v1.0
在深入细节之前,让我们先看一个Map/Reduce的应用示例,以便对它们的工作方式有一个初步的认识?/p>
WordCount是一个简单的应用Q它可以计算出指定数据集中每一个单词出现的ơ数?/p>
q个应用适用?单机模式Q?伪分布式模式 ?完全分布式模?三种Hadoop安装方式?/p>
源代?br> WordCount.java
1. package org.myorg;
2.
3. import java.io.IOException;
4. import java.util.*;
5.
6. import org.apache.hadoop.fs.Path;
7. import org.apache.hadoop.conf.*;
8. import org.apache.hadoop.io.*;
9. import org.apache.hadoop.mapred.*;
10. import org.apache.hadoop.util.*;
11.
12. public class WordCount {
13.
14. public static class Map extends MapReduceBase implements Mapper<LongWritable, Text, Text, IntWritable> {
15. private final static IntWritable one = new IntWritable(1);
16. private Text word = new Text();
17.
18. public void map(LongWritable key, Text value, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {
19. String line = value.toString();
20. StringTokenizer tokenizer = new StringTokenizer(line);
21. while (tokenizer.hasMoreTokens()) {
22. word.set(tokenizer.nextToken());
23. output.collect(word, one);
24. }
25. }
26. }
27.
28. public static class Reduce extends MapReduceBase implements Reducer<Text, IntWritable, Text, IntWritable> {
29. public void reduce(Text key, Iterator<IntWritable> values, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {
30. int sum = 0;
31. while (values.hasNext()) {
32. sum += values.next().get();
33. }
34. output.collect(key, new IntWritable(sum));
35. }
36. }
37.
38. public static void main(String[] args) throws Exception {
39. JobConf conf = new JobConf(WordCount.class);
40. conf.setJobName("wordcount");
41.
42. conf.setOutputKeyClass(Text.class);
43. conf.setOutputValueClass(IntWritable.class);
44.
45. conf.setMapperClass(Map.class);
46. conf.setCombinerClass(Reduce.class);
47. conf.setReducerClass(Reduce.class);
48.
49. conf.setInputFormat(TextInputFormat.class);
50. conf.setOutputFormat(TextOutputFormat.class);
51.
52. FileInputFormat.setInputPaths(conf, new Path(args[0]));
53. FileOutputFormat.setOutputPath(conf, new Path(args[1]));
54.
55. JobClient.runJob(conf);
57. }
58. }
59.
用法
假设环境变量HADOOP_HOME对应安装时的根目录,HADOOP_VERSION对应Hadoop的当前安装版本,~译WordCount.java来创建jar包,可如下操作:
$ mkdir wordcount_classes
$ javac -classpath ${HADOOP_HOME}/hadoop-${HADOOP_VERSION}-core.jar -d wordcount_classes WordCount.java
$ jar -cvf /usr/joe/wordcount.jar -C wordcount_classes/ .
假设Q?/p>
/usr/joe/wordcount/input - 是HDFS中的输入路径
/usr/joe/wordcount/output - 是HDFS中的输出路径
用示例文本文件做入:
$ bin/hadoop dfs -ls /usr/joe/wordcount/input/
/usr/joe/wordcount/input/file01
/usr/joe/wordcount/input/file02
$ bin/hadoop dfs -cat /usr/joe/wordcount/input/file01
Hello World Bye World
$ bin/hadoop dfs -cat /usr/joe/wordcount/input/file02
Hello Hadoop Goodbye Hadoop
q行应用E序Q?/p>
$ bin/hadoop jar /usr/joe/wordcount.jar org.myorg.WordCount /usr/joe/wordcount/input /usr/joe/wordcount/output
输出是:
$ bin/hadoop dfs -cat /usr/joe/wordcount/output/part-00000
Bye 1
Goodbye 1
Hadoop 2
Hello 2
World 2
应用E序能够使用-files选项来指定一个由逗号分隔的\径列表,q些路径是task的当前工作目录。用选项-libjars可以向map和reduce的classpath中添加jar包。?archives选项E序可以传递档案文件做为参敎ͼq些档案文g会被解压q且在task的当前工作目录下会创Z个指向解压生成的目录的符号链接(以压~包的名字命名)?有关命o行选项的更多细节请参?Commands manual?/p>
使用-libjars?filesq行wordcount例子Q?br>hadoop jar hadoop-examples.jar wordcount -files cachefile.txt -libjars mylib.jar input output
解释
WordCount应用E序非常直截了当?/p>
Mapper(14-26?中的mapҎ(18-25?通过指定?TextInputFormat(49?一ơ处理一行。然后,它通过StringTokenizer 以空gؓ分隔W将一行切分ؓ若干tokensQ之后,输出< <word>, 1> 形式的键值对?/p>
对于CZ中的W一个输入,map输出是:
< Hello, 1>
< World, 1>
< Bye, 1>
< World, 1>
W二个输入,map输出是:
< Hello, 1>
< Hadoop, 1>
< Goodbye, 1>
< Hadoop, 1>
关于l成一个指定作业的map数目的确定,以及如何以更_的方式去控制q些mapQ我们将在教E的后箋部分学习到更多的内容?/p>
WordCountq指定了一个combiner (46?。因此,每次mapq行之后Q会对输出按照keyq行排序Q然后把输出传递给本地的combinerQ按照作业的配置与Reducer一PQ进行本地聚合?/p>
W一个map的输出是Q?br>< Bye, 1>
< Hello, 1>
< World, 2>
W二个map的输出是Q?br>< Goodbye, 1>
< Hadoop, 2>
< Hello, 1>
Reducer(28-36?中的reduceҎ(29-35? 仅是每个keyQ本例中是单词Q出现的ơ数求和?/p>
因此q个作业的输出就是:
< Bye, 1>
< Goodbye, 1>
< Hadoop, 2>
< Hello, 2>
< World, 2>
代码中的runҎ中指定了作业的几个方面, 例如Q通过命o行传递过来的输入/输出路径、key/value的类型、输?输出的格式等{JobConf中的配置信息。随后程序调用了JobClient.runJob(55?来提交作业ƈ且监控它的执行?/p>
我们在本教E的后箋部分学习更多的关于JobConfQ?JobClientQ?Tool和其他接口及c?class)?/p>
Map/Reduce - 用户界面
q部分文档ؓ用户会面的Map/Reduce框架中的各个环节提供了适当的细节。这应该会帮助用hl粒度地d现、配|和调优作业。然而,h意每个类/接口的javadoc文档提供最全面的文档;本文只是惌v到指南的作用?/p>
我们会先看看Mapper和Reducer接口。应用程序通常会通过提供map和reduceҎ来实现它们?/p>
然后Q我们会讨论其他的核心接口,其中包括Q?JobConfQJobClientQPartitionerQ?OutputCollectorQReporterQ?InputFormatQOutputFormat{等?/p>
最后,我们通过讨论框架中一些有用的功能点(例如QDistributedCacheQ?IsolationRunner{等Q来收尾?/p>
核心功能描述
应用E序通常会通过提供map和reduce来实?Mapper和Reducer接口Q它们组成作业的核心?/p>
Mapper
Mapper输入键值对(key/value pair)映射Cl中间格式的键值对集合?/p>
Map是一cd输入记录集{换ؓ中间格式记录集的独立d?q种转换的中间格式记录集不需要与输入记录集的cd一致。一个给定的输入键值对可以映射?个或多个输出键值对?/p>
Hadoop Map/Reduce框架为每一个InputSplit产生一个mapdQ而每个InputSplit是由该作业的InputFormat产生的?/p>
概括地说Q对Mapper的实现者需要重?JobConfigurable.configure(JobConf)ҎQ这个方法需要传递一个JobConf参数Q目的是完成Mapper的初始化工作。然后,框架个Q务的InputSplit中每个键值对调用一?map(WritableComparable, Writable, OutputCollector, Reporter)操作。应用程序可以通过重写Closeable.close()Ҏ来执行相应的清理工作?/p>
输出键值对不需要与输入键值对的类型一致。一个给定的输入键值对可以映射?个或多个输出键值对。通过调用 OutputCollector.collect(WritableComparable,Writable)可以攉输出的键值对?/p>
应用E序可以使用Reporter报告q度Q设定应用别的状态消息,更新CountersQ计数器Q,或者仅是表明自p行正常?/p>
框架随后会把与一个特定key兌的所有中间过E的|valueQ分成组Q然后把它们传给Reducer以出最l的l果。用户可以通过 JobConf.setOutputKeyComparatorClass(Class)来指定具体负责分l的 Comparator?/p>
Mapper的输排序后,p划分l每个Reducer。分块的L目和一个作业的reduced的数目是一L。用户可以通过实现自定义的 Partitioner来控制哪个key被分配给哪个 Reducer?/p>
用户可选择通过 JobConf.setCombinerClass(Class)指定一个combinerQ它负责对中间过E的输出q行本地的聚集,q会有助于降低从Mapper?Reducer数据传输量?/p>
q些被排好序的中间过E的输出l果保存的格式是(key-len, key, value-len, value)Q应用程序可以通过JobConf控制对这些中间结果是否进行压~以及怎么压羃Q用哪U?CompressionCodec?/p>
需要多个MapQ?br>Map的数目通常是由输入数据的大决定的Q一般就是所有输入文件的dQblockQ数?/p>
Map正常的ƈ行规模大致是每个节点QnodeQ大U?0?00个mapQ对于CPU 消耗较的mapd可以讑ֈ300个左叟뀂由于每个Q务初始化需要一定的旉Q因此,比较合理的情冉|map执行的时间至超q?分钟?/p>
q样Q如果你输入10TB的数据,每个块(blockQ的大小?28MBQ你需要大U?2,000个map来完成Q务,除非使用 setNumMapTasks(int)Q注意:q里仅仅是对框架q行了一个提C?hint)Q实际决定因素见q里Q将q个数D|得更高?/p>
Reducer
Reducer与一个key兌的一l中间数值集归约QreduceQؓ一个更的数值集?/p>
用户可以通过 JobConf.setNumReduceTasks(int)讑֮一个作业中reduced的数目?/p>
概括地说Q对Reducer的实现者需要重?JobConfigurable.configure(JobConf)ҎQ这个方法需要传递一个JobConf参数Q目的是完成Reducer的初始化工作。然后,框架为成l的输入数据中的每个<key, (list of values)>对调用一?reduce(WritableComparable, Iterator, OutputCollector, Reporter)Ҏ。之后,应用E序可以通过重写Closeable.close()来执行相应的清理工作?/p>
Reducer?个主要阶D:shuffle、sort和reduce?/p>
Shuffle
Reducer的输入就是Mapper已经排好序的输出。在q个阶段Q框枉过HTTP为每个Reducer获得所有Mapper输出中与之相关的分块?/p>
Sort
q个阶段Q框架将按照key的值对Reducer的输入进行分l?Q因Z同mapper的输Z可能会有相同的keyQ?/p>
Shuffle和Sort两个阶段是同时进行的Qmap的输Z是一边被取回一边被合ƈ的?/p>
Secondary Sort
如果需要中间过E对key的分l规则和reduce前对key的分l规则不同,那么可以通过 JobConf.setOutputValueGroupingComparator(Class)来指定一个Comparator。再加上 JobConf.setOutputKeyComparatorClass(Class)可用于控制中间过E的key如何被分l,所以结合两者可以实现按值的二次排序?/p>
Reduce
在这个阶D,框架为已分组的输入数据中的每?<key, (list of values)>对调用一?reduce(WritableComparable, Iterator, OutputCollector, Reporter)Ҏ?/p>
Reduced的输出通常是通过调用 OutputCollector.collect(WritableComparable, Writable)写入 文gpȝ的?/p>
应用E序可以使用Reporter报告q度Q设定应用程序别的状态消息,更新CountersQ计数器Q,或者仅是表明自p行正常?/p>
Reducer的输出是没有排序的?/p>
需要多个ReduceQ?br>Reduce的数目徏议是0.95?.75乘以 (<no. of nodes> * mapred.tasktracker.reduce.tasks.maximum)?/p>
?.95Q所有reduce可以在maps一完成时就立刻启动Q开始传输map的输出结果。用1.75Q速度快的节点可以在完成第一轮reduced后,可以开始第二轮Q这样可以得到比较好的负载均衡的效果?/p>
增加reduce的数目会增加整个框架的开销Q但可以改善负蝲均衡Q降低由于执行失败带来的负面影响?/p>
上述比例因子比整体数目稍一些是Zl框架中的推性Q务(speculative-tasksQ?或失败的d预留一些reduce的资源?/p>
无Reducer
如果没有归约要进行,那么讄reduced的数目ؓ零是合法的?/p>
q种情况下,mapd的输Z直接被写入由 setOutputPath(Path)指定的输\径。框架在把它们写入FileSystem之前没有对它们进行排序?/p>
Partitioner
Partitioner用于划分键值空_key spaceQ?/p>
Partitioner负责控制map输出l果key的分剌ӀKeyQ或者一个key子集Q被用于产生分区Q通常使用的是Hash函数。分区的数目与一个作业的reduced的数目是一L。因此,它控制将中间q程的keyQ也是q条记录Q应该发送给m个reduced中的哪一个来q行reduce操作?/p>
HashPartitioner是默认的 Partitioner?/p>
Reporter
Reporter是用于Map/Reduce应用E序报告q度Q设定应用别的状态消息, 更新CountersQ计数器Q的机制?/p>
Mapper和Reducer的实现可以利用Reporter 来报告进度,或者仅是表明自p行正常。在那种应用E序需要花很长旉处理个别键值对的场景中Q这U机制是很关键的Q因为框架可能会以ؓq个d时了,从而将它强行杀歅R另一个避免这U情况发生的方式是,配|参数mapred.task.timeout讄Z个够高的|或者干脆设|ؓӞ则没有超旉制了Q?/p>
应用E序可以用Reporter来更新CounterQ计数器Q?/p>
OutputCollector
OutputCollector是一个Map/Reduce框架提供的用于收?Mapper或Reducer输出数据的通用机制 Q包括中间输出结果和作业的输出结果)?/p>
Hadoop Map/Reduce框架附带了一个包含许多实用型的mapper、reducer和partitioner 的类库?/p>
作业配置
JobConf代表一个Map/Reduce作业的配|?/p>
JobConf是用户向Hadoop框架描述一个Map/Reduce作业如何执行的主要接口。框架会按照JobConf描述的信息忠实地d试完成这个作业,然而:
一些参数可能会被管理者标Cؓ finalQ这意味它们不能被更攏V?
一些作业的参数可以被直截了当地q行讄Q例如: setNumReduceTasks(int)Q,而另一些参数则与框架或者作业的其他参数之间微妙地相互媄响,q且讄h比较复杂Q例如: setNumMapTasks(int)Q?
通常QJobConf会指明Mapper、Combiner(如果有的??Partitioner、Reducer、InputFormat?OutputFormat的具体实现。JobConfq能指定一l输入文?(setInputPaths(JobConf, Path...) /addInputPath(JobConf, Path)) ?setInputPaths(JobConf, String) /addInputPaths(JobConf, String)) 以及输出文g应该写在哪儿 (setOutputPath(Path))?/p>
JobConf可选择地对作业讄一些高U选项Q例如:讄ComparatorQ?攑ֈDistributedCache上的文gQ中间结果或者作业输出结果是否需要压~以及怎么压羃Q?利用用户提供的脚?setMapDebugScript(String)/setReduceDebugScript(String)) q行调试Q作业是否允讔R防性(speculativeQQ务的执行 (setMapSpeculativeExecution(boolean))/(setReduceSpeculativeExecution(boolean)) Q每个Q务最大的试ơ数 (setMaxMapAttempts(int)/setMaxReduceAttempts(int)) Q一个作业能容忍的Q务失败的癑ֈ?(setMaxMapTaskFailuresPercent(int)/setMaxReduceTaskFailuresPercent(int)) Q等{?/p>
当然Q用戯使用 set(String, String)/get(String, String) 来设|或者取得应用程序需要的L参数。然而,DistributedCache的用是面向大规模只L据的?/p>
d的执行和环境
TaskTracker是在一个单独的jvm上以子进E的形式执行 Mapper/ReducerdQTaskQ的?/p>
子Q务会l承父TaskTracker的环境。用户可以通过JobConf中的 mapred.child.java.opts配置参数来设定子jvm上的附加选项Q例如: 通过-Djava.library.path=<> 一个非标准路径设ؓq行时的链接用以搜烦׃n库,{等。如果mapred.child.java.opts包含一个符号@taskid@Q?它会被替换成map/reduce的taskid的倹{?/p>
下面是一个包含多个参数和替换的例子,其中包括Q记录jvm GC日志Q?JVM JMX代理E序以无密码的方式启动,q样它就能连接到jconsole上,从而可以查看子q程的内存和U程Q得到线E的dumpQ还把子jvm的最大堆寸讄?12MBQ?qؓ子jvm的java.library.pathd了一个附加\径?/p>
<property>
<name>mapred.child.java.opts</name>
<value>
-Xmx512M -Djava.library.path=/home/mycompany/lib -verbose:gc -Xloggc:/tmp/@taskid@.gc
-Dcom.sun.management.jmxremote.authenticate=false -Dcom.sun.management.jmxremote.ssl=false
</value>
</property>
用户或管理员也可以用mapred.child.ulimit讑֮q行的子d的最大虚拟内存。mapred.child.ulimit的gQKB)为单位,q且必须大于或等?Xmx参数传给JavaVM的|否则VM会无法启动?/p>
注意Qmapred.child.java.opts只用于设|task tracker启动的子d。ؓ守护q程讄内存选项h?cluster_setup.html
${mapred.local.dir}/taskTracker/是task tracker的本地目录, 用于创徏本地~存和job。它可以指定多个目录Q跨多个磁盘)Q文件会半随机的保存到本地\径下的某个目录。当job启动Ӟtask trackerҎ配置文档创徏本地job目录Q目录结构如以下所C:
${mapred.local.dir}/taskTracker/archive/ :分布式缓存。这个目录保存本地的分布式缓存。因此本地分布式~存是在所有task和job间共享的?
${mapred.local.dir}/taskTracker/jobcache/$jobid/ : 本地job目录?
${mapred.local.dir}/taskTracker/jobcache/$jobid/work/: job指定的共享目录。各个Q务可以用这个空间做为暂存空_用于它们之间׃n文g。这个目录通过job.local.dir 参数暴露l用戗这个\径可以通过API JobConf.getJobLocalDir()来访问。它也可以被做ؓpȝ属性获得。因此,用户Q比如运行streamingQ可以调用System.getProperty("job.local.dir")获得该目录?
${mapred.local.dir}/taskTracker/jobcache/$jobid/jars/: 存放jar包的路径Q用于存放作业的jar文g和展开的jar。job.jar是应用程序的jar文gQ它会被自动分发到各台机器,在task启动前会被自动展开。用api JobConf.getJar() 函数可以得到job.jar的位|。用JobConf.getJar().getParent()可以讉K存放展开的jar包的目录?
${mapred.local.dir}/taskTracker/jobcache/$jobid/job.xmlQ?一个job.xml文gQ本地的通用的作业配|文件?
${mapred.local.dir}/taskTracker/jobcache/$jobid/$taskidQ?每个d有一个目录task-idQ它里面有如下的目录l构Q?
${mapred.local.dir}/taskTracker/jobcache/$jobid/$taskid/job.xmlQ?一个job.xml文gQ本地化的Q务作业配|文件。Q务本地化是指task讑֮特定的属性倹{这些g在下面具体说明?
${mapred.local.dir}/taskTracker/jobcache/$jobid/$taskid/output 一个存放中间过E的输出文g的目录。它保存了由framwork产生的时map reduce数据Q比如map的输出文件等?
${mapred.local.dir}/taskTracker/jobcache/$jobid/$taskid/workQ?task的当前工作目录?
${mapred.local.dir}/taskTracker/jobcache/$jobid/$taskid/work/tmpQ?task的时目录。(用户可以讑֮属性mapred.child.tmp 来ؓmap和reduce task讑֮临时目录。缺省值是./tmp。如果这个g是绝对\径, 它会把task的工作\径加到该路径前面作ؓtask的时文件\径。如果这个值是l对路径则直接用这个倹{?如果指定的目录不存在Q会自动创徏该目录。之后,按照选项 -Djava.io.tmpdir='临时文g的绝对\?执行java子Q务?pipes和streaming的时文件\径是通过环境变量TMPDIR='the absolute path of the tmp dir'讑֮的)?如果mapred.child.tmp?/tmp|q个目录会被创徏?
下面的属性是为每个task执行时用的本地参数Q它们保存在本地化的d作业配置文g里:
名称 cd 描述
mapred.job.id String job id
mapred.jar String job目录下job.jar的位|?
job.local.dir String job指定的共享存储空?
mapred.tip.id String task id
mapred.task.id String task试id
mapred.task.is.map boolean 是否是map task
mapred.task.partition int task在job中的id
map.input.file String mapd的文件名
map.input.start long map输入的数据块的v始位|偏U?
map.input.length long map输入的数据块的字节数
mapred.work.output.dir String task临时输出目录
task的标准输出和错误输出会被读到TaskTracker中,q且记录?${HADOOP_LOG_DIR}/userlogs
DistributedCache 可用于map或reduce task中分发jar包和本地库。子jvmL?当前工作目录 加到 java.library.path ?LD_LIBRARY_PATH?因此Q可以通过 System.loadLibrary?System.load装蝲~存的库。有关用分布式~存加蝲׃n库的l节请参?native_libraries.html
作业的提交与监控
JobClient是用h交的作业与JobTracker交互的主要接口?/p>
JobClient 提供提交作业Q追t进E,讉K子Q务的日志记录Q获得Map/Reduce集群状态信息等功能?/p>
作业提交q程包括Q?/p>
查作业输入输出样式细?
Z业计InputSplit倹{?
如果需要的话,Z业的DistributedCache建立必须的统计信息?
拯作业的jar包和配置文g到FileSystem上的Map/Reducepȝ目录下?
提交作业到JobTrackerq且监控它的状态?
作业的历史文件记录到指定目录?_logs/history/"子目录下。这个指定目录由hadoop.job.history.user.location讑֮Q默认是作业输出的目录。因此默认情况下Q文件会存放在mapred.output.dir/_logs/history目录下。用户可以设|hadoop.job.history.user.location为none来停止日志记录?/p>
用户使用下面的命令可以看到在指定目录下的历史日志记录的摘要?
$ bin/hadoop job -history output-dir
q个命o会打印出作业的细节,以及p|的和被杀ȝdl节?br>要查看有关作业的更多l节例如成功的Q务、每个Q务尝试的ơ数Qtask attemptQ等Q可以用下面的命o
$ bin/hadoop job -history all output-dir
用户可以使用 OutputLogFilter 从输出目录列表中{选日志文件?/p>
一般情况,用户利用JobConf创徏应用E序q|作业属性, 然后?JobClient 提交作业q监视它的进E?/p>
作业的控?br>有时候,用一个单独的Map/Reduce作业q不能完成一个复杂的dQ用户也许要链接多个Map/Reduce作业才行。这是容易实现的Q因Z业通常输出到分布式文gpȝ上的Q所以可以把q个作业的输ZZ一个作业的输入实现串联?/p>
然而,q也意味着Q确保每一作业完成(成功或失?的责d直接落在了客戯n上。在q种情况下,可以用的控制作业的选项有:
runJob(JobConf)Q提交作业,仅当作业完成时返回?
submitJob(JobConf)Q只提交作业Q之后需要你轮询它返回的 RunningJob句柄的状态,q根据情况调度?
JobConf.setJobEndNotificationURI(String)Q设|一个作业完成通知Q可避免轮询?
作业的输?br>InputFormat 为Map/Reduce作业描述输入的细节规范?/p>
Map/Reduce框架Ҏ作业的InputFormat来:
查作业输入的有效性?
把输入文件切分成多个逻辑InputSplit实例Q?q把每一实例分别分发l一?Mapper?
提供RecordReader的实玎ͼq个RecordReader从逻辑InputSplit中获得输入记录, q些记录由Mapper处理?
Z文g的InputFormat实现Q通常?FileInputFormat的子c) 默认行ؓ是按照输入文件的字节大小Q把输入数据切分成逻辑分块Qlogical InputSplit Q?其中输入文g所在的FileSystem的数据块寸是分块大的上限。下限可以设|mapred.min.split.size 的倹{?/p>
考虑到边界情况,对于很多应用E序来说Q很明显按照文g大小q行逻辑分割是不能满需求的?在这U情况下Q应用程序需要实C个RecordReader来处理记录的边界qؓ每个d提供一个逻辑分块的面向记录的视图?/p>
TextInputFormat 是默认的InputFormat?/p>
如果一个作业的Inputformat是TextInputFormatQ?q且框架到输入文g的后~?gz?lzoQ就会用对应的CompressionCodec自动解压~这些文件?但是需要注意,上述带后~的压~文件不会被切分Qƈ且整个压~文件会分给一个mapper来处理?/p>
InputSplit
InputSplit 是一个单独的Mapper要处理的数据块?/p>
一般的InputSplit 是字节样式输入,然后由RecordReader处理q{化成记录样式?/p>
FileSplit 是默认的InputSplit?它把 map.input.file 讑֮入文件的路径Q输入文件是逻辑分块文g?/p>
RecordReader
RecordReader 从InputSlitd<key, value>寏V?/p>
一般的QRecordReader 把由InputSplit 提供的字节样式的输入文gQ{化成由Mapper处理的记录样式的文g?因此RecordReader负责处理记录的边界情况和把数据表C成keys/values对Ş式?/p>
作业的输?br>OutputFormat 描述Map/Reduce作业的输出样式?/p>
Map/Reduce框架Ҏ作业的OutputFormat来:
验作业的输出Q例如检查输\径是否已l存在?
提供一个RecordWriter的实玎ͼ用来输出作业l果?输出文g保存在FileSystem上?
TextOutputFormat是默认的 OutputFormat?/p>
d的Side-Effect File
在一些应用程序中Q子d需要生一些side-fileQ这些文件与作业实际输出l果的文件不同?/p>
在这U情况下Q同一个Mapper或者Reducer的两个实例(比如预防性Q务)同时打开或者写 FileSystem上的同一文g׃产生冲突。因此应用程序在写文件的时候需要ؓ每次d试Q不仅仅是每ơQ务,每个d可以试执行很多ơ)选取一个独一无二的文件名(使用attemptidQ例如task_200709221812_0001_m_000000_0)?/p>
Z避免冲突QMap/Reduce框架为每ơ尝试执行Q务都建立和维护一个特D的 ${mapred.output.dir}/_temporary/_${taskid}子目录,q个目录位于本次试执行d输出l果所在的FileSystem上,可以通过 ${mapred.work.output.dir}来访问这个子目录?对于成功完成的Q务尝试,只有${mapred.output.dir}/_temporary/_${taskid}下的文g会移动到${mapred.output.dir}。当Ӟ框架会丢弃那些失败的d试的子目录。这U处理过E对于应用程序来说是完全透明的?/p>
在Q务执行期_应用E序在写文g时可以利用这个特性,比如 通过 FileOutputFormat.getWorkOutputPath()获得${mapred.work.output.dir}目录Q?q在其下创徏Ld执行时所需的side-fileQ框架在d试成功时会马上Udq些文gQ因此不需要在E序内ؓ每次d试选取一个独一无二的名字?/p>
注意Q在每次d试执行期间Q?{mapred.work.output.dir} 的值实际上?${mapred.output.dir}/_temporary/_{$taskid}Q这个值是Map/Reduce框架创徏的?所以用这个特性的Ҏ是,?FileOutputFormat.getWorkOutputPath() 路径下创建side-file卛_?/p>
对于只用map不用reduce的作业,q个l论也成立。这U情况下Qmap的输出结果直接生成到HDFS上?/p>
RecordWriter
RecordWriter 生成<key, value> 对到输出文g?/p>
RecordWriter的实现把作业的输出结果写?FileSystem?/p>
其他有用的特?br>Counters
Counters 是多个由Map/Reduce框架或者应用程序定义的全局计数器?每一个Counter可以是Q何一U?Enumcd。同一特定Enumcd的Counter可以汇集C个组Q其cd为Counters.Group?/p>
应用E序可以定义L(Enumcd)的Countersq且可以通过 map 或?reduceҎ中的 Reporter.incrCounter(Enum, long)或?Reporter.incrCounter(String, String, long) 更新。之后框架会汇总这些全局counters?/p>
DistributedCache
DistributedCache 可将具体应用相关的、大寸的、只ȝ文g有效地分布放|?/p>
DistributedCache 是Map/Reduce框架提供的功能,能够~存应用E序所需的文?Q包括文本,档案文gQjar文g{)?/p>
应用E序在JobConf中通过url(hdfs://)指定需要被~存的文件?DistributedCache假定由hdfs://格式url指定的文件已l在 FileSystem上了?/p>
Map-Redcue框架在作业所有Q务执行之前会把必要的文g拯到slave节点上?它运行高效是因ؓ每个作业的文件只拯一ơƈ且ؓ那些没有文档的slave节点~存文档?/p>
DistributedCache Ҏ~存文档修改的时间戳q行q踪?在作业执行期_当前应用E序或者外部程序不能修改缓存文件?/p>
distributedCache可以分发单的只读数据或文本文Ӟ也可以分发复杂类型的文g例如归档文g和jar文g。归档文?zip,tar,tgz和tar.gz文g)在slave节点上会被解档(un-archivedQ?q些文g可以讄执行权限?/p>
用户可以通过讄mapred.cache.{files|archives}来分发文件?如果要分发多个文Ӟ可以使用逗号分隔文g所在\径。也可以利用API来设|该属性: DistributedCache.addCacheFile(URI,conf)/ DistributedCache.addCacheArchive(URI,conf) and DistributedCache.setCacheFiles(URIs,conf)/ DistributedCache.setCacheArchives(URIs,conf) 其中URI的Ş式是 hdfs://host:port/absolute-path#link-name 在StreamingE序中,可以通过命o行选项 -cacheFile/-cacheArchive 分发文g?/p>
用户可以通过 DistributedCache.createSymlink(Configuration)Ҏ让DistributedCache 在当前工作目录下创徏到缓存文件的W号链接?或者通过讄配置文g属性mapred.create.symlink为yes?分布式缓存会截取URI的片D作为链接的名字?例如QURI?hdfs://namenode:port/lib.so.1#lib.soQ?则在task当前工作目录会有名ؓlib.so的链接, 它会链接分布式缓存中的lib.so.1?/p>
DistributedCache可在map/reduced中作?一U基软g分发机制使用。它可以被用于分发jar包和本地库(native librariesQ?DistributedCache.addArchiveToClassPath(Path, Configuration)?DistributedCache.addFileToClassPath(Path, Configuration) API能够被用?~存文g和jar包,q把它们加入子jvm的classpath。也可以通过讄配置文档里的属?mapred.job.classpath.{files|archives}辑ֈ相同的效果。缓存文件可用于分发和装载本地库?/p>
Tool
Tool 接口支持处理常用的Hadoop命o行选项?/p>
Tool 是Map/Reduce工具或应用的标准。应用程序应只处理其定制参数Q?要把标准命o行选项通过 ToolRunner.run(Tool, String[]) 委托l?GenericOptionsParser处理?/p>
Hadoop命o行的常用选项有:
-conf <configuration file>
-D <property=value>
-fs <local|namenode:port>
-jt <local|jobtracker:port>
IsolationRunner
IsolationRunner 是帮助调试Map/ReduceE序的工兗?/p>
使用IsolationRunner的方法是Q首先设|?keep.failed.tasks.files属性ؓtrue Q同时参考keep.tasks.files.patternQ?/p>
然后Q登录到dq行p|的节点上Q进?TaskTracker的本地\径运?IsolationRunnerQ?br>$ cd <local path>/taskTracker/${taskid}/work
$ bin/hadoop org.apache.hadoop.mapred.IsolationRunner ../job.xml
IsolationRunner会把p|的Q务放在单独的一个能够调试的jvm上运行,q且采用和之前完全一L输入数据?/p>
Profiling
Profiling是一个工P它用内|的java profiler工具q行分析获得(2-3?map或reduce样例q行分析报告?/p>
用户可以通过讄属性mapred.task.profile指定pȝ是否采集profiler信息?利用api JobConf.setProfileEnabled(boolean)可以修改属性倹{如果设为trueQ?则开启profiling功能。profiler信息保存在用h志目录下。缺省情况,profiling功能是关闭的?/p>
如果用户讑֮使用profiling功能Q可以用配|文档里的属?mapred.task.profile.{maps|reduces} 讄要profile map/reduce task的范围。设|该属性值的api?JobConf.setProfileTaskRange(boolean,String)?范围的缺省值是0-2?/p>
用户可以通过讑֮配置文档里的属性mapred.task.profile.params 来指定profiler配置参数。修改属性要使用api JobConf.setProfileParams(String)。当q行taskӞ如果字符串包?s?它会被替换成profileing的输出文件名。这些参C在命令行里传递到子JVM中。缺省的profiling 参数?-agentlib:hprof=cpu=samples,heap=sites,force=n,thread=y,verbose=n,file=%s?/p>
调试
Map/Reduce框架能够q行用户提供的用于调试的脚本E序?当map/reducedp|Ӟ用户可以通过q行脚本在Q务日志(例如d的标准输出、标准错误、系l日志以及作业配|文Ӟ上做后箋处理工作。用h供的调试脚本E序的标准输出和标准错误会输Zؓ诊断文g。如果需要的话这些输出结果也可以打印在用L面上?/p>
在接下来的章节,我们讨论如何与作业一h交调试脚本。ؓ了提交调试脚本, 首先要把q个脚本分发出去Q而且q要在配|文仉讄?/p>
如何分发脚本文gQ?br>用户要用 DistributedCache 机制来分发和链接脚本文g
如何提交脚本Q?br>一个快速提交调试脚本的Ҏ是分别ؓ需要调试的mapd和reduced讄 "mapred.map.task.debug.script" ?"mapred.reduce.task.debug.script" 属性的倹{这些属性也可以通过 JobConf.setMapDebugScript(String) ?JobConf.setReduceDebugScript(String) API来设|。对于streamingQ?可以分别为需要调试的mapd和reduced使用命o行选项-mapdebug ?-reducedegug来提交调试脚本?/p>
脚本的参数是d的标准输出、标准错误、系l日志以及作业配|文件。在q行map/reducep|的节点上q行调试命o是:
$script $stdout $stderr $syslog $jobconf
Pipes E序ҎW五个参数获得c++E序名?因此调试pipesE序的命令是
$script $stdout $stderr $syslog $jobconf $program
默认行ؓ
对于pipesQ默认的脚本会用gdb处理core dumpQ?打印 stack traceq且l出正在q行U程的信息?/p>
JobControl
JobControl是一个工P它封装了一lMap/Reduce作业以及他们之间的依赖关pR?/p>
数据压羃
Hadoop Map/Reduce框架为应用程序的写入文g操作提供压羃工具Q这些工具可以ؓmap输出的中间数据和作业最l输出数据(例如reduce的输出)提供支持。它q附带了一?CompressionCodec的实玎ͼ比如实现?zlib和lzo压羃法?Hadoop同样支持gzip文g格式?/p>
考虑到性能问题QzlibQ以及Javacd的缺失(lzoQ等因素QHadoop也ؓ上述压羃解压法提供本地库的实现。更多的l节请参?q里?/p>
中间输出
应用E序可以通过 JobConf.setCompressMapOutput(boolean)api控制map输出的中间结果,q且可以通过 JobConf.setMapOutputCompressorClass(Class)api指定 CompressionCodec?/p>
作业输出
应用E序可以通过 FileOutputFormat.setCompressOutput(JobConf, boolean) api控制输出是否需要压~ƈ且可以?FileOutputFormat.setOutputCompressorClass(JobConf, Class)api指定CompressionCodec?/p>
如果作业输出要保存成 SequenceFileOutputFormat格式Q需要?SequenceFileOutputFormat.setOutputCompressionType(JobConf, SequenceFile.CompressionType)apiQ来讑֮ SequenceFile.CompressionType (i.e.RECORD / BLOCK - 默认是RECORD)?/p>
例子QWordCount v2.0
q里是一个更全面的WordCount例子Q它使用了我们已l讨的很多Map/Reduce框架提供的功能?/p>
q行q个例子需要HDFS的某些功能,特别?DistributedCache相关功能。因此这个例子只能运行在 伪分布式 或?完全分布式模式的 Hadoop上?/p>
源代?br> WordCount.java
1. package org.myorg;
2.
3. import java.io.*;
4. import java.util.*;
5.
6. import org.apache.hadoop.fs.Path;
7. import org.apache.hadoop.filecache.DistributedCache;
8. import org.apache.hadoop.conf.*;
9. import org.apache.hadoop.io.*;
10. import org.apache.hadoop.mapred.*;
11. import org.apache.hadoop.util.*;
12.
13. public class WordCount extends Configured implements Tool {
14.
15. public static class Map extends MapReduceBase implements Mapper<LongWritable, Text, Text, IntWritable> {
16.
17. static enum Counters { INPUT_WORDS }
18.
19. private final static IntWritable one = new IntWritable(1);
20. private Text word = new Text();
21.
22. private boolean caseSensitive = true;
23. private Set<String> patternsToSkip = new HashSet<String>();
24.
25. private long numRecords = 0;
26. private String inputFile;
27.
28. public void configure(JobConf job) {
29. caseSensitive = job.getBoolean("wordcount.case.sensitive", true);
30. inputFile = job.get("map.input.file");
31.
32. if (job.getBoolean("wordcount.skip.patterns", false)) {
33. Path[] patternsFiles = new Path[0];
34. try {
35. patternsFiles = DistributedCache.getLocalCacheFiles(job);
36. } catch (IOException ioe) {
37. System.err.println("Caught exception while getting cached files: " + StringUtils.stringifyException(ioe));
38. }
39. for (Path patternsFile : patternsFiles) {
40. parseSkipFile(patternsFile);
41. }
42. }
43. }
44.
45. private void parseSkipFile(Path patternsFile) {
46. try {
47. BufferedReader fis = new BufferedReader(new FileReader(patternsFile.toString()));
48. String pattern = null;
49. while ((pattern = fis.readLine()) != null) {
50. patternsToSkip.add(pattern);
51. }
52. } catch (IOException ioe) {
53. System.err.println("Caught exception while parsing the cached file '" + patternsFile + "' : " + StringUtils.stringifyException(ioe));
54. }
55. }
56.
57. public void map(LongWritable key, Text value, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {
58. String line = (caseSensitive) ? value.toString() : value.toString().toLowerCase();
59.
60. for (String pattern : patternsToSkip) {
61. line = line.replaceAll(pattern, "");
62. }
63.
64. StringTokenizer tokenizer = new StringTokenizer(line);
65. while (tokenizer.hasMoreTokens()) {
66. word.set(tokenizer.nextToken());
67. output.collect(word, one);
68. reporter.incrCounter(Counters.INPUT_WORDS, 1);
69. }
70.
71. if ((++numRecords % 100) == 0) {
72. reporter.setStatus("Finished processing " + numRecords + " records " + "from the input file: " + inputFile);
73. }
74. }
75. }
76.
77. public static class Reduce extends MapReduceBase implements Reducer<Text, IntWritable, Text, IntWritable> {
78. public void reduce(Text key, Iterator<IntWritable> values, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {
79. int sum = 0;
80. while (values.hasNext()) {
81. sum += values.next().get();
82. }
83. output.collect(key, new IntWritable(sum));
84. }
85. }
86.
87. public int run(String[] args) throws Exception {
88. JobConf conf = new JobConf(getConf(), WordCount.class);
89. conf.setJobName("wordcount");
90.
91. conf.setOutputKeyClass(Text.class);
92. conf.setOutputValueClass(IntWritable.class);
93.
94. conf.setMapperClass(Map.class);
95. conf.setCombinerClass(Reduce.class);
96. conf.setReducerClass(Reduce.class);
97.
98. conf.setInputFormat(TextInputFormat.class);
99. conf.setOutputFormat(TextOutputFormat.class);
100.
101. List<String> other_args = new ArrayList<String>();
102. for (int i=0; i < args.length; ++i) {
103. if ("-skip".equals(args[i])) {
104. DistributedCache.addCacheFile(new Path(args[++i]).toUri(), conf);
105. conf.setBoolean("wordcount.skip.patterns", true);
106. } else {
107. other_args.add(args[i]);
108. }
109. }
110.
111. FileInputFormat.setInputPaths(conf, new Path(other_args.get(0)));
112. FileOutputFormat.setOutputPath(conf, new Path(other_args.get(1)));
113.
114. JobClient.runJob(conf);
115. return 0;
116. }
117.
118. public static void main(String[] args) throws Exception {
119. int res = ToolRunner.run(new Configuration(), new WordCount(), args);
120. System.exit(res);
121. }
122. }
123.
q行样例
输入样例Q?/p>
$ bin/hadoop dfs -ls /usr/joe/wordcount/input/
/usr/joe/wordcount/input/file01
/usr/joe/wordcount/input/file02
$ bin/hadoop dfs -cat /usr/joe/wordcount/input/file01
Hello World, Bye World!
$ bin/hadoop dfs -cat /usr/joe/wordcount/input/file02
Hello Hadoop, Goodbye to hadoop.
q行E序Q?/p>
$ bin/hadoop jar /usr/joe/wordcount.jar org.myorg.WordCount /usr/joe/wordcount/input /usr/joe/wordcount/output
输出Q?/p>
$ bin/hadoop dfs -cat /usr/joe/wordcount/output/part-00000
Bye 1
Goodbye 1
Hadoop, 1
Hello 2
World! 1
World, 1
hadoop. 1
to 1
注意此时的输入与W一个版本的不同Q输出的l果也有不同?/p>
现在通过DistributedCache插入一个模式文Ӟ文g中保存了要被忽略的单词模式?/p>
$ hadoop dfs -cat /user/joe/wordcount/patterns.txt
\.
\,
\!
to
再运行一ơ,q次使用更多的选项Q?/p>
$ bin/hadoop jar /usr/joe/wordcount.jar org.myorg.WordCount -Dwordcount.case.sensitive=true /usr/joe/wordcount/input /usr/joe/wordcount/output -skip /user/joe/wordcount/patterns.txt
应该得到q样的输出:
$ bin/hadoop dfs -cat /usr/joe/wordcount/output/part-00000
Bye 1
Goodbye 1
Hadoop 1
Hello 2
World 2
hadoop 1
再运行一ơ,q一ơ关闭大写敏感性(case-sensitivityQ:
$ bin/hadoop jar /usr/joe/wordcount.jar org.myorg.WordCount -Dwordcount.case.sensitive=false /usr/joe/wordcount/input /usr/joe/wordcount/output -skip /user/joe/wordcount/patterns.txt
输出Q?/p>
$ bin/hadoop dfs -cat /usr/joe/wordcount/output/part-00000
bye 1
goodbye 1
hadoop 2
hello 2
world 2
E序要点
通过使用一些Map/Reduce框架提供的功能,WordCount的第二个版本在原始版本基上有了如下的改进Q?/p>
展示了应用程序如何在Mapper (和Reducer)中通过configureҎ 修改配置参数(28-43??
展示了作业如何用DistributedCache 来分发只L据?q里允许用户指定单词的模式,在计数时忽略那些W合模式的单?104??
展示Tool接口和GenericOptionsParser处理Hadoop命o行选项的功?(87-116, 119??
展示了应用程序如何用Counters(68?Q如何通过传递给mapQ和reduceQ?Ҏ的Reporter实例来设|应用程序的状态信?72??
Java和JNI是Sun Microsystems, Inc.在美国和其它国家的注册商标?/p>
本文来自CSDN博客Q{载请标明出处Q?a >http://blog.csdn.net/superxgl/archive/2010/01/11/5171929.aspx
一?span>
hive ?/span>hive 是一个基?/span> hadoop 的开源数据仓库工P用于存储和处理v量结构化数据?/span> 它把量数据存储?/span> hadoop 文gpȝQ而不是数据库Q但提供了一套类数据库的数据存储和处理机Ӟq?/span> HQL Q类 SQL Q语a对这些数据进行自动化理和处理。我们可以把 hive 中v量结构化数据看成一个个的表Q而实际上q些数据是分布式存储?/span> HDFS 中的?/span> Hive l过对语句进行解析和转换Q最l生成一pdZ hadoop ?/span> map/reduce dQ通过执行q些d完成数据处理?/span>
Hive 诞生?/span> facebook 的日志分析需求,面对量的结构化数据Q?/span> hive 以较低的成本完成了以往需要大规模数据库才能完成的dQƈ且学习门槛相对较低,应用开发灵z而高效?/span>
Hive ?/span> 2009.4.29 发布W一个官方稳定版 0.3.0 至今Q不q一q的旉Q正在慢慢完善,|上能找到的相关资料相当,其中文资料更少Q本文结合业务对 hive 的应用做了一些探索,q把q些l验做一个ȝQ所谓前车之_希望读者能走一些弯路?/span>
Hive 的官?/span> wiki 请参考这?/span> :
http://wiki.apache.org/hadoop/Hive
官方主页在这里:
http://hadoop.apache.org/hive/
hive-0.5.0 源码包和二进制发布包的下载地址
http://labs.renren.com/apache-mirror/hadoop/hive/hive-0.5.0/
二?span>
部v׃ Hive 是基?/span> hadoop 的工P所?/span> hive 的部|需要一个正常运行的 hadoop 环境。以下介l?/span> hive 的简单部|和应用?/span>
部v环境Q?/span>
操作pȝQ?/span> Red Hat Enterprise Linux AS release 4 (Nahant Update 7)
Hadoop Q?/span> hadoop-0.20.2 Q正常运?/span>
部v步骤如下Q?/span>
1?/span> 下蝲最新版本发布包 hive-0.5.0-dev.tar.gz Q传?/span> hadoop ?/span> namenode 节点上,解压得到 hive 目录。假设\径ؓQ?/span> /opt/hadoop/hive-0.5.0-bin
2?/span> 讄环境变量 HIVE_HOME Q指?/span> hive 根目?/span> /opt/hadoop/hive-0.5.0-bin 。由?/span> hadoop 已运行,查环境变?/span> JAVA_HOME ?/span> HADOOP_HOME 是否正确有效?/span>
3?/span> 切换?/span> $HIVE_HOME 目录Q?/span> hive 配置默认卛_Q运?/span> bin/hive 卛_启动 hive Q如果正常启动,会出现“ hive> ”提示W?/span>
4?/span> 在命令提C符中输?#8220; show tables; ”Q如果正常运行,说明已部|成功,可供使用?/span>
常见问题Q?/span>
1?/span> 执行“ show tables; ”命o提示“ FAILED: Error in metadata: java.lang.IllegalArgumentException: URI: does not have a scheme ”Q这是由?/span> hive 找不到存攑օ数据库的数据库而导致的Q修?/span> conf/ hive-default.xml 配置文g中的 hive.metastore.local ?/span> true 卛_。由?/span> hive 把结构化数据的元数据信息攑֜W三Ҏ据库Q此处设|ؓ true Q?/span> hive 在本地创徏 derby 数据库用于存攑օ数据。当然如果有需要也可以采用 mysql {第三方数据库存攑օ数据Q不q这?/span> hive.metastore.local 的配|值应?/span> false ?/span>
2?/span> 如果你已有一?/span> nutch1.0 pȝ正在跑,而你不想单独再去部v一?/span> hadoop 环境Q你可以直接使用 nutch1.0 自带?/span> hadoop 环境Q但q样的部|会D hive 不能正常q行Q提C找不到某些Ҏ。这是由?/span> nutch1.0 使用?/span> commons-lang-2.1.jar q个包,?/span> hive 需要的?/span> commons-lang-2.4.jar Q下载一?/span> 2.4 版本的包替换?/span> 2.1 卛_Q?/span> nutch ?/span> hive 都能正常q行?/span>
三?span> 应用场景
本文主要讲述使用 hive 的实践,业务不是关键Q简要介l业务场景,本次的Q务是Ҏ索日志数据进行统计分析?/span>
集团搜烦刚上U不久,日志量ƈ不大 。这些日志分布在 5 台前端机Q按时保存Qƈ以小时ؓ周期定时上一时产生的数据同步到日志分析机,l计数据要求按小时更新。这些统计项Q包括关键词搜烦?/span> pv Q类别访问量Q每U访问量 tps {等?/span>
Z hive Q我们将q些数据按天为单位徏表,每天一个表Q后台脚本根据时间戳每时同步q来?/span> 5 台前端机的日志数据合q成一个日志文Ӟ导入 hive pȝQ每时同步的日志数据被q加到当天数据表中,导入完成后,当天各项l计将被重新计ƈ输出l计l果?/span>
以上需求若直接Z hadoop 开发,需要自行管理数据,针对多个l计需求开发不同的 map/reduce q算dQ对合ƈ、排序等多项操作q行定制QƈQ务运行状态,工作量ƈ不小。但使用 hive Q从导入到分析、排序、去重、结果输出,q些操作都可以运?/span> hql 语句来解冻I一条语句经q处理被解析成几个Q务来q行Q即使是关键词访问量增量q种需要同时访问多天数据的较ؓ复杂的需求也能通过表关联这L语句自动完成Q节省了大量工作量?/span>
四?span> Hive 实战
初次使用 hive Q应该说上手q是挺快的?/span> Hive 提供的类 SQL 语句?/span> mysql 语句极ؓ怼Q语法上有大量相同的地方Q这l我们上手带来了很大的方便,但是要得心应手地写好q些语句Q还需要对 hive 有较好的了解Q才能结?/span> hive 特色写出_֦的语句?/span>
关于 hive 语言的详l语法可参考官?/span> wiki 的语a手册 :
http://wiki.apache.org/hadoop/Hive/LanguageManual
虽然语法风格为我们提供了便利Q但初次使用遇到的问题还是不的Q下面针对业务场景谈谈我们遇到的问题Q和?/span> hive 功能的定制?/span>
1?/span> 分隔W问?/span>
首先遇到的是日志数据的分隔符问题Q我们的日志数据的大致格式如下:
2010-05-24 00:00:02@$_$@QQ2010@$_$@all@$_$@NOKIA_1681C@$_$@1@$_$@10@$_$@@$_$@-1@$_$@10@$_$@application@$_$@1
从格式可见其分隔W是“ @$_$@ ”Q这是ؓ了尽可能防止日志正文出现与分隔符相同的字W而导致数据淆。本?/span> hive支持在徏表的时候指定自定义分隔W的Q但l过多次试发现只支持单个字W的自定义分隔符Q像“ @$_$@ ”q样的分隔符是不能被支持的,但是我们可以通过对分隔符的定制解册个问题, hive 的内部分隔符?#8220; \001 ”Q只要把分隔W替换成“\001 ”卛_?/span>
l过探烦我们发现有两条途径解决q个问题?/span>
a) 自定?/span> outputformat ?/span> inputformat ?/span>
Hive ?/span> outputformat/inputformat ?/span> hadoop ?/span> outputformat/inputformat 相当cMQ?/span> inputformat 负责把输入数据进行格式化Q然后提供给 hive Q?/span> outputformat 负责?/span> hive 输出的数据重新格式化成目标格式再输出到文Ӟq种Ҏ式进行定制的方式较ؓ底层Q对其进行定制也相对单,重写 InputFormat ?/span> RecordReader cM?/span> next Ҏ卛_Q示例代码如下:
public boolean next(LongWritable key, BytesWritable value)
throws IOException {
while ( reader .next(key, text ) ) {
String strReplace = text .toString().toLowerCase().replace( "@$_$@" , "\001" );
Text txtReplace = new Text();
txtReplace.set(strReplace );
value.set(txtReplace.getBytes(), 0, txtReplace.getLength());
return true ;
}
return false ;
}
重写 HiveIgnoreKeyTextOutputFormat ?/span> RecordWriter 中的 write ҎQ示例代码如下:
public void write (Writable w) throws IOException {
String strReplace = ((Text)w).toString().replace( "\001" , "@$_$@" );
Text txtReplace = new Text();
txtReplace.set(strReplace);
byte [] output = txtReplace.getBytes();
bytesWritable .set(output, 0, output. length );
writer .write( bytesWritable );
}
自定?/span> outputformat/inputformat 后,在徏表时需要指?/span> outputformat/inputformat Q如下示例:
stored as INPUTFORMAT 'com.aspire.search.loganalysis.hive.SearchLogInputFormat' OUTPUTFORMAT 'com.aspire.search.loganalysis.hive.SearchLogOutputFormat'
b) 通过 SerDe(serialize/deserialize) Q在数据序列化和反序列化时格式化数据?/span>
q种方式E微复杂一点,Ҏ据的控制能力也要׃些,它用正则表辑ּ来匹配和处理数据Q性能也会有所影响。但它的优点是可以自定义表属性信?/span> SERDEPROPERTIES Q在 SerDe 中通过q些属性信息可以有更多的定制行为?/span>
2?/span> 数据导入导出
a) 多版本日志格式的兼容
׃ hive 的应用场景主要是处理h据(只读不写Q,因此它只支持扚w导入和导出数据,q不支持单条数据的写入或更新Q所以如果要导入的数据存在某些不太规范的行,则需要我们定制一些扩展功能对其进行处理?/span>
我们需要处理的日志数据存在多个版本Q各个版本每个字D늚数据内容存在一些差异,可能版本 A 日志数据的第二个列是搜烦关键字,但版?/span> B 的第二列却是搜烦的终端类型,如果q两个版本的日志直接导入 hive 中,很明显数据将会乱,l计l果也不会正。我们的d是要使多个版本的日志数据能在 hive 数据仓库中共存,且表?/span> input/output 操作能够最l映到正确的日志版本的正确字段?/span>
q里我们不关心这部分J琐的工作,只关心技术实现的关键点,q个功能该在哪里实现才能?/span> hive 认得q些不同格式的数据呢Q经q多方尝试,在中间Q何环节做q个版本适配都将D复杂化,最l这个工作还是在 inputformat/outputformat 中完成最Z雅,毕竟 inputformat 是源_ outputformat 是最l归ѝ具体来_是在前面提到?/span> inputformat ?/span> next Ҏ中和?/span> outputformat ?/span> write Ҏ中完成这个适配工作?/span>
b) Hive 操作本地数据
一开始,L把本地数据先传到 HDFS Q再?/span> hive 操作 hdfs 上的数据Q然后再把数据从 HDFS 上传回本地数据。后来发现大可不必如此, hive 语句都提供了“ local ”关键字,支持直接从本地导入数据到 hive Q也能从 hive 直接导出数据到本圎ͼ不过其内部计时当然是用 HDFS 上的数据Q只是自动ؓ我们完成导入导出而已?/span>
3?/span> 数据处理
日志数据的统计处理在q里反倒没有什么特别之处,是一?/span> SQL 语句而已Q也没有什么高q技巧,不过q是列D一些语句示例,以示 hive 处理数据的方便之处,q展C?/span> hive 的一些用法?/span>
a) ?/span> hive d用户定制功能Q自定义功能都位?/span> hive_contrib.jar 包中
add jar /opt/hadoop/hive-0.5.0-bin/lib/hive_contrib.jar;
b) l计每个关键词的搜烦量,q按搜烦量降序排列,然后把结果存入表 keyword_20100603 ?/span>
create table keyword_20100603 as select keyword,count(keyword) as count from searchlog_20100603 group by keyword order by count desc;
c) l计每类用户l端的搜索量Qƈ按搜索量降序排列Q然后把l果存入?/span> device_20100603 ?/span>
create table device_20100603 as select device,count(device) as count from searchlog_20100603 group by device order by count desc;
d) 创徏?/span> time_20100603 Q用自定义?/span> INPUTFORMAT ?/span> OUTPUTFORMAT Qƈ指定表数据的真实存放位置?/span> '/LogAnalysis/results/time_20100603' Q?/span> HDFS 路径Q,而不是放?/span> hive 自己的数据目录中
create external table if not exists time_20100603(time string, count int) stored as INPUTFORMAT 'com.aspire.search.loganalysis.hive.XmlResultInputFormat' OUTPUTFORMAT 'com.aspire.search.loganalysis.hive.XmlResultOutputFormat' LOCATION '/LogAnalysis/results/time_20100603';
e) l计每秒讉K?/span> TPS Q按讉K量降序排列,q把l果输出到表 time_20100603 中,q个表我们在上面刚刚定义q,其真实位|在 '/LogAnalysis/results/time_20100603' Qƈ且由?/span> XmlResultOutputFormat 的格式化Q文件内Ҏ XML 格式?/span>
insert overwrite table time_20100603 select time,count(time) as count from searchlog_20100603 group by time order by count desc;
f) 计算每个搜烦h响应旉的最大|最值和q_?/span>
insert overwrite table response_20100603 select max(responsetime) as max,min(responsetime) as min,avg(responsetime) as avg from searchlog_20100603;
g) 创徏一个表用于存放今天与昨天的关键词搜索量和增量及其增量比率,表数据位?/span> '/LogAnalysis/results/keyword_20100604_20100603' Q内容将?/span> XML 格式?/span>
create external table if not exists keyword_20100604_20100603(keyword string, count int, increment int, incrementrate double) stored as INPUTFORMAT 'com.aspire.search.loganalysis.hive.XmlResultInputFormat' OUTPUTFORMAT 'com.aspire.search.loganalysis.hive.XmlResultOutputFormat' LOCATION '/LogAnalysis/results/keyword_20100604_20100603';
h) 讄表的属性,以便 XmlResultInputFormat ?/span> XmlResultOutputFormat 能根?/span> output.resulttype 的不同内容输Z同格式的 XML 文g?/span>
alter table keyword_20100604_20100603 set tblproperties ('output.resulttype'='keyword');
i) 兌今天关键词统计结果表Q?/span> keyword_20100604 Q与昨天关键词统计结果表Q?/span> keyword_20100603 Q,l计今天与昨天同时出现的关键词的搜烦ơ数Q今天相Ҏ天的增量和增量比率,q按增量比率降序排列Q结果输出到刚刚定义?/span> keyword_20100604_20100603 表中Q其数据文g内容ؓ XML 格式?/span>
insert overwrite table keyword_20100604_20100603 select cur.keyword, cur.count, cur.count-yes.count as increment, (cur.count-yes.count)/yes.count as incrementrate from keyword_20100604 cur join keyword_20100603 yes on (cur.keyword = yes.keyword) order by incrementrate desc;
j)
4?/span> 用户自定义函?/span> UDF
部分l计l果需要以 CSV 的格式输出,对于q类文g体全是有效内容的文gQ不需要像 XML 一样包?/span> version Q?/span> encoding {信息的文g_最适合?/span> UDF(user define function) 了?/span>
UDF 函数可直接应用于 select 语句Q对查询l构做格式化处理之后Q再输出内容。自定义 UDF 需要?/span> org.apache.hadoop.hive.ql.exec.UDF Qƈ实现 evaluate 函数Q?/span> Evaluate 函数支持重蝲Q还支持可变参数。我们实C一个支持可变字W串参数?/span> UDF Q支持把 select 得出的Q意个数的不同cd数据转换为字W串后,?/span> CSV 格式输出Q由于代码较单,q里l出源码CZQ?/span>
public String evaluate(String... strs) {
StringBuilder sb = new StringBuilder();
for ( int i = 0; i < strs. length ; i++) {
sb.append(ConvertCSVField(strs[i])).append( ',' );
}
sb.deleteCharAt(sb.length()-1);
return sb.toString();
}
需要注意的是,要?/span> UDF 功能Q除了实现自定义 UDF 外,q需要加入包?/span> UDF 的包Q示例:
add jar /opt/hadoop/hive-0.5.0-bin/lib/hive_contrib.jar;
然后创徏临时ҎQ示例:
CREATE TEMPORARY FUNCTION Result2CSv AS ‘com.aspire.search.loganalysis.hive. Result2CSv';
使用完毕q要 drop ҎQ示例:
DROP TEMPORARY FUNCTION Result2CSv;
5?/span> 输出 XML 格式的统计结?/span>
前面看到部分日志l计l果输出C个表中,借助 XmlResultInputFormat ?/span> XmlResultOutputFormat 格式化成 XML 文gQ考虑到创个表只是Z得到 XML 格式的输出数据,我们只需实现 XmlResultOutputFormat 卛_Q如果还要支?/span> select 查询Q则我们q需要实?/span> XmlResultInputFormat Q这里我们只介绍 XmlResultOutputFormat ?/span>
前面介绍q,定制 XmlResultOutputFormat 我们只需重写 write 卛_Q这个方法将会把 hive 的以 ’\001’ 分隔的多字段数据格式化ؓ我们需要的 XML 格式Q被化的CZ代码如下Q?/span>
public void write(Writable w) throws IOException {
String[] strFields = ((Text) w).toString().split( "\001" );
StringBuffer sbXml = new StringBuffer();
if ( strResultType .equals( "keyword" )) {
sbXml.append( "<record><keyword>" ).append(strFields[0]).append(
"</keyword><count>" ).append(strFields[1]).append( "</count><increment>" ).append(strFields[2]).append(
"</increment><rate>" ).append(strFields[3]).append(
"</rate></result>" );
}
Text txtXml = new Text();
byte [] strBytes = sbXml.toString().getBytes( "utf-8" );
txtXml.set(strBytes, 0, strBytes. length );
byte [] output = txtXml.getBytes();
bytesWritable .set(output, 0, output. length );
writer .write( bytesWritable );
}
其中?/span> strResultType .equals( "keyword" ) 指定关键词统计结果,q个属性来自以下语句对l果cd的指定,通过q个属性我们还可以用同一?/span> outputformat 输出多种cd的结果?/span>
alter table keyword_20100604_20100603 set tblproperties ('output.resulttype'='keyword');
仔细看看 write 函数的实C可发玎ͼ其实q里只输Z XML 文g的正文,?/span> XML 的文件头和结束标{֜哪里输出呢?所q我们采用的是基?/span> outputformat 的实玎ͼ我们可以在构造函数输?/span> version Q?/span> encoding {文件头信息Q在 close() Ҏ中输出结束标{?/span>
q也是我们ؓ什么不使用 UDF 来输出结果的原因Q自定义 UDF 函数不能输出文g头和文g,对于 XML 格式的数据无法输出完整格式,只能输出 CSV q类所有行都是有效数据的文件?/span>
五?span> ȝ
Hive 是一个可扩展性极强的数据仓库工具Q借助?/span> hadoop 分布式存储计^台和 hive ?/span> SQL 语句的理解能力,我们所要做的大部分工作是输入和输出数据的适配Q恰恰这两部?/span> IO 格式是千变万化的Q我们只需要定制我们自q输入输出适配器, hiveؓ我们透明化存储和处理q些数据Q大大简化我们的工作。本文的重心也正在于此,q部分工作相信每一个做数据分析的朋友都会面对的Q希望对您有益?/span>
本文介绍了一ơ相当简单的Z hive 的日志统计实战,?/span> hive 的运用还处于一个相对较的层面Q目前尚能满需求。对于一些较复杂的数据分析Q务,以上所介绍的经验很可能是不够用的,甚至?/span> hive 做不到的Q?/span> hive q有很多q阶功能Q限于篇q本文未能涉及,待日后结合具体Q务再详细阐述?/span>
如您Ҏ文有M或指教,误论,谢谢?/span>