自己动手写网络爬虫(二)

Wyh_D_Void 贡献于2011-05-23

作者 Administrator  创建于2010-07-13 00:54:00   修改者kandy  修改于2010-09-13 08:01:00字数51181

文档摘要:随着互联网技术的发展以及风起云涌的云计算浪潮。爬虫技术也逐渐向着分布式方向发展。比如,Google的爬虫就是使用成千上万台小型机和微机进行合作,完成分布式抓取工作的。分布式技术不仅可以解决IT运营的成本,还可以解决爬虫效率问题,尤其是当今云计算的热潮,更把分布式推向了极致。设计分布式爬虫,把抓取任务分布到不同的节点主要是为了抓取性能与可扩展性,也可以使用物理分布的爬虫系统,让每个爬虫节点抓取靠近它的网站。例如,北京的爬虫节点抓取北京的网站,上海的爬虫节点抓取上海的网站,电信网络中的爬虫节点抓取托管在电信的网站,联通网络中的爬虫节点抓取托管在联通的网站。
关键词:

分布式爬虫 分布式爬虫 第2章 分布式爬虫 随着互联网技术的发展以及风起云涌的云计算浪潮。爬虫技术也逐渐向着分布式方向发展。比如,Google的爬虫就是使用成千上万台小型机和微机进行合作,完成分布式抓取工作的。分布式技术不仅可以解决IT运营的成本,还可以解决爬虫效率问题,尤其是当今云计算的热潮,更把分布式推向了极致。 2.1 设计分布式爬虫 把抓取任务分布到不同的节点主要是为了抓取性能与可扩展性,也可以使用物理分布的爬虫系统,让每个爬虫节点抓取靠近它的网站。例如,北京的爬虫节点抓取北京的网站,上海的爬虫节点抓取上海的网站,电信网络中的爬虫节点抓取托管在电信的网站,联通网络中的爬虫节点抓取托管在联通的网站。 分布式爬虫 分布式爬虫 2.1.1 分布式与云计算 分布式技术是一种基于网络的计算机处理技术,与集中式相对应。近些年来,由于个人计算机的性能得到极大地提高及其使用的普及,使得将处理任务分布到网络上的所有计算机成为可能。分布式计算是和集中式计算相对立的概念,分布式计算的数据可以分布在很大区域。 在分布式网络中,数据的存储和处理都是在本地工作站上进行的。数据输出可以打印,也可以保存在软盘上。通过网络能得到更快、更便捷的数据访问。因为每台计算机都能够存储和处理数据,所以不要求服务器的功能十分强大,其价格也就不必过于昂贵。这种类型的网络可以适应用户的各种需要,同时允许他们共享网络的数据、资源和服务。在分布式网络中使用的计算机既能够作为独立的系统使用,也可以把它们连接在一起得到更强的网络功能。 分布式计算的优点是可以快速访问、多用户使用。每台计算机可以访问系统内其他计算机的信息文件,系统设计上具有更大的灵活性。既可为独立计算机的地区用户的特殊需求服务,也可为联网的企业需求服务,实现系统内不同计算机之间的通信。每台计算机都可以拥有和保持所需要的最大数据和文件,减少了数据传输的成本和风险。为分散地区和中心办公室双方提供更迅速的信息通信和处理方式,为每个分散的数据库提供作用域,数据存储于许多存储单元中,但任何用户都可以进行全局访问,使故障的不利影响最小化,以较低的成本来满足企业的特定要求。 云计算(Cloud Computing)是分布式处理(Distributed Computing)、并行处理(Parallel Computing)和网格计算(Grid Computing)的发展,或者说是这些计算机科学概念的商业实现。 云计算的基本原理是,通过使计算任务分布在大量的分布式计算机上,而非本地计算机或远程服务器中,企业数据中心的运行将与互联网更相似。这使得企业能够将资源切换到需要的应用上,根据需求访问计算机和存储系统。 这可是一种革命性的举措,打个比方,就好比是从古老的单台发电机模式转向了电厂集中供电的模式。它意味着计算能力也可以作为一种商品进行流通,就像煤气、水电一样,取用方便,费用低廉。最大的不同在于,它是通过互联网进行传输的。 云计算的蓝图已经呼之欲出:在未来,只需要一台笔记本或者一部手机,就可以通过网络服务来实现我们需要的一切,甚至包括超级计算这样的任务。从这个角度而言,最终用户才是云计算的真正拥有者。   云计算的应用包含这样一种思想,把力量联合起来,给其中的每一个成员使用。 目前,PC依然是我们日常工作生活中的核心工具——我们用PC处理文档、存储资料,用电子邮件或U盘与他人分享信息。如果PC硬盘坏了,我们会因为资料丢失而束手无策。   而在“云计算”时代,“云”会替我们做存储和计算的工作。“云”就是计算机群,每一群都包括几十万台、甚至上百万台计算机。“云”的好处还在于,其中的计算机可以随时更新,保证“云”长生不老。Google就有好几个这样的“云”,其他IT巨头,如微软、雅虎、亚马逊(Amazon)也有或正在建设这样的 分布式爬虫 分布式爬虫 “云”。   届时,我们只需要一台能上网的电脑,不需关心存储或计算发生在哪朵“云”上,但一旦有需要,我们可以在任何地点用任何设备,如电脑、手机等,快速地计算和找到这些资料。我们再也不用担心资料会丢失了。 云计算是虚拟化(Virtualization)、效用计算(Utility Computing)、IaaS(基础设施即服务)、PaaS(平台即服务)、SaaS(软件即服务)等概念混合演进并跃升的结果。云计算的特点如下: (1) 超大规模。Google云计算已经拥有100多万台服务器, Amazon、IBM、微软、Yahoo等的“云”均拥有几十万台服务器。企业私有云一般拥有数百至上千台服务器。“云”能赋予用户前所未有的计算能力。 (2) 虚拟化。云计算支持用户在任意位置、使用各种终端获取应用服务。所请求的资源来自“云”,而不是固定的、有形的实体。应用在“云”中某处运行,但实际上用户无需了解、也不用担心应用运行的具体位置。只需要一台笔记本或者一部手机,就可以通过网络服务来实现我们需要的一切,甚至包括超级计算这样的任务。 (3) 高可靠性。“云”使用了数据多副本容错、计算节点同构可互换等措施来保障服务的高可靠性,使用云计算比使用本地计算机可靠。 (4) 通用性。云计算不针对特定的应用,在“云”的支撑下可以构造出千变万化的应用,同一个“云”可以同时支撑不同的应用运行。 (5) 高可扩展性。“云”的规模可以动态伸缩,满足应用和用户规模增长的需要。 (6) 按需服务。“云”是一个庞大的资源池,可以按需购买;云可以象自来水、电、煤气那样计费。 (7) 极其廉价。由于“云”的特殊容错措施可以采用极其廉价的节点来构成云,“云”的自动化集中式管理使得大量企业无需负担日益高昂的数据中心管理成本,“云”的通用性使资源的利用率较之传统系统大幅提升,因此用户可以充分享受“云”的低成本优势,经常只要花费几百美元、几天时间就能完成以前需要数万美元、数月时间才能完成的任务。 2.1.2 分布式与云计算技术在爬虫中的应用——浅析Google的云计算架构 分布式与云计算深刻地影响着搜索引擎的发展。与其说是云计算影响了搜索引擎,不如说是搜索引擎的发展产生了云计算的概念。Google正是由于在云计算领域的领先,才能多年在搜索领域保持霸主的地位。本节以Google的架构为例,看一下云计算是如何应用在爬虫之中的。 Google的三大核心技术构成了实现云计算服务的基础:GFS(Google文件系统)、MapReduce(分布式计算系统)和BigTable(分布式存储系统)。 GFS位于这三项技术的最底层,负责许多服务器、机器数据的存储工作。它将一个“大体积数据(通常在百兆甚至千兆级别)分隔成固定大小的数据块放到两到三个服务器上。这样做的目的是当一个服务器发生故障时,可以将数据迅速地从另外一个服务器上恢复过来。在存储层面,机器故障的处理由Google文件系统来完成。 分布式爬虫 分布式爬虫 MapReduce (分布式计算系统)是Google开发的编程工具,用于1TB数据的大规模数据集并行运算。这项技术的意义在于,实现跨越大量数据结点分割任务,使得某项任务可以被同时分拆在多台机器上执行。例如把一项搜索任务拆分成一两百个小的子任务,经并行处理后,将运算结果在后台合并,最后把最终结果返回到客户端。 BigTable (分布式存储系统)作为 Google的一种对于半结构化数据进行分布存储与访问的接口或服务,它是建立在GFS和MapReduce之上的结构化分布式存储系统,可以帮助Google最大限度地利用已有的数据存储能力和计算能力,在提供服务时降低运行成本。 2.2 分布式存储 分布式存储是网络爬虫中的一个重要问题,抓取下来的URL要存放在分布式环境中。在云计算热潮风起云涌的今天,存储云的概念也被炒得沸沸扬扬。因此,如何在分布式网络环境中存储数据,也是分布式爬虫的重要课题。 2.2.1 从Ralation_DB到key/value存储 前几年,key/value这个词还是和hash表联系在一起的。而现在,程序员看见key/value这个词时,马上联想到的就是 BigTable、SimpleDB和云计算。当下,key/value存储(或者叫key/value Database、云存储等)是个非常时髦的词汇,越来越多的开发人员(特别是互联网企业)开始关注和尝试key/value的存储形式。 key/value形式的存储并不是凭空想象出来的。有两个原因导致了key/value存储方式的崛起。 1. 大规模的互联网应用 对于Google和eBay这样的互联网企业,每时每刻都有无数的用户在使用它们提供的互联网服务,这些服务带来的就是大量的数据吞吐量。同一时间,会并发出成千上万的连接对数据库进行操作。在这种情况下,单台服务器或者几台服务器远远不能满足这些数据处理的需求,简单的升级服务器性能的方式也不行,所以唯一可以采用的办法就是使用集群了。使用集群的方法有很多种,但大致分为两类:一类仍然采用关系数据库管理系统(RDBMS),然后通过对数据库的垂直和水平切割将整个数据库部署到一个集群上,这种方法的优点在于可以采用RDBMS这种熟悉的技术,但缺点在于它是针对特定应用的。由于应用的不同,切割的方法是不一样的。关于数据库的垂直和水平切割的具体细节可以查看相关资料。 还有一类就是Google所采用的方法,抛弃RDBMS,采用key/value形式的存储,这样可以极大地增强系统的可扩展性(scalability),如果要处理的数据量持续增大,多加机器就可以了。事实上,key/value的存储就是由于BigTable等相关论文的发表慢慢进入人们的视野的。 分布式爬虫 分布式爬虫 2. 云存储 如果说上一个问题还有可以替代的解决方案(切割数据库)的话,那么对于云存储来说,也许key/value的存储就是唯一的解决方案了。云存储简单点说就是构建一个大型的存储平台给别人用,这也就意味着在这上面运行的应用其实是不可控的。如果其中某个客户的应用随着用户的增长而不断增长时,云存储供应商是没有办法通过数据库的切割来达到扩展的,因为这个数据是客户的,供应商不了解这个数据自然就没法作出切割。在这种情况下,key/value的存储就是唯一的选择了,因为这种条件下的可扩展性必须是自动完成的,不能有人工干预。这也是为什么目前几乎所有的云存储都是key/value形式的,例如Amazon的smipleDB,底层实现就是key/value,还有Google的 GoogleAppEngine,采用的是BigTable的存储形式。 key/value存储与RDBMS相比,一个很大的区别就是它没有模式的概念。在RDBMS 中,模式所代表的其实就是对数据的约束,包括数据之间的关系(relationship)和数据的完整性(integrity),比如 RDBMS中对于某个数据属性会要求它的数据类型是确定的(整数或者字符串等),数据的范围也是确定的(0~255),而这些在key/value存储中都没有。在key/value存储中,对于某个key,value可以是任意的数据类型。 在所有的RDBMS中,都是采用SQL语言对数据进行访问。一方面,SQL对于数据的查询功能非常强大;另一方面,由于所有的RDBMS都支持SQL查询,所以可移植性很强。而在key/value 存储中,对于数据的操作使用的都是自定义的一些API,而且支持的查询也比较简单。 正如前面反复提及的,key/value存储最大的特点就是它的可扩展性(scalability),这也是它最大的优势。所谓的可扩展性,其实包括两方面内容。一方面,是指key/value存储可以支持极大的数据存储。它的分布式的架构决定了只要有更多的机器,就能够保证存储更多的数据。另一方面,是指它可以支持数量很多的并发的查询。对于RDBMS,一般几百个并发的查询就可以让它很吃力了,而一个key/value存储,可以很轻松地支持上千个并发查询。 key/value存储的缺陷主要有两点: l 由于key/value存储中没有schema,所以它是不提供数据之间的关系和数据的完备性的,所有的这些东西都落到了应用程序一端,其实也就是开发人员的头上。这无疑加重了开发人员的负担。 l 在RDBMS中,需要设定各表之间的关系,这其实是一个数据建模的过程(data modeling process)。当数据建模完成后,这个数据库对于应用程序就是独立的了,这就意味着其他程序可以在不改变数据模型的前提下使用相同的数据集。但在key/value存储中,由于没有这样一个数据模型,不同的应用程序需要重复进行这个过程。 l key/value存储最大的一个缺点在于它的接口是不熟悉的。这阻碍了开发人员可以快速而顺利地用上它。当然,现在有种做法,就是在key/value存储上再加上一个类SQL语句的抽象接口层,从而使得开发人员可以用他们熟悉的方式(SQL)来操作key/value存储。但由于RDBMS和key/value存储的底层实现有着很大的不同,这种抽象接口层或多或少还是受到了限制。 分布式爬虫 分布式爬虫 2.2.2 Consistent Hash算法 分布式存储常常会涉及负载平衡的问题,由于有多个存储介质,分布在不同的结点上。因此,当一个对象被保存的时候,它究竟应该保存在哪个存储介质上呢(存储介质可以是数据库、Berkeley DB等,甚至可以是内存数据结构)?这就是负载均衡的问题,如图2.1所示。 图2.1 负载均衡示意图 面对云计算的热潮,如何很好地分布存储数据,是一个非常重要的话题。在分布式网络爬虫中,抓取的页面非常多(通常是数十亿级别),因此,分布式存储就非常有意义。那么,如果抓取下来一个页面,究竟要存放到哪个数据库中呢?这就涉及负载均衡的问题。 如果你有 N 个数据存储服务器,那么如何将一个对象(object)映射到 N 个服务器上呢?你很可能会采用类似下面的通用方法计算对象的hash值,然后均匀地映射到N个服务器: hash(object)%N 一切都运行正常,但是要考虑以下两种情况; (1) 一个服务器m挂掉了(在实际应用中必须要考虑这种情况),则所有映射到服务器m 的对象都会失效。怎么办,需要把服务器m移除,这时候服务器为N-1台,映射公式变成了hash(object)%(N-1)。 (2) 由于访问加重,需要添加服务器,这时候服务器是 N+1 台,映射公式变成了 hash(object)%(N+1)。 在上面两种情况下,突然之间几乎所有的服务器都失效了(请看下面单调性的解释)。对于服务器而言,这是一场灾难。 分布式爬虫 分布式爬虫 再来考虑第三个问题,由于硬件能力越来越强,你可能会想让后面添加的节点多干点活,显然上面的 hash 算法也做不到。 有什么方法可以改变这个状况呢,这就要用到Consistent Hashing算法。 hash 算法的一个衡量指标是单调性(Monotonicity),定义如下: 单调性是指如果已经有一些内容通过哈希分配到了相应的缓冲中,而又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。 上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。 Consistent Hashing 是一种 hash 算法,简单地说,在移除/添加一个服务器时,它能够尽可能小地改变已存在的 key 映射关系,尽可能地满足单调性的要求。下面就按照 5 个步骤简单讲讲 Consistent Hashing 算法的基本原理。 步骤一:环形hash空间。 考虑通常的 hash 算法都是将 value 映射到一个 32 位的 key 值,即0~232-1的数值空间。我们可以将这个空间想象成一个首( 0 )尾(232-1)相接的圆环,如图 2.2 所示。 步骤二:把对象映射到hash空间。 接下来考虑4个对象object1~object4,通过hash函数计算出的hash值key在环上的分布如图 2.2 所示。 hash(object1) = key1; … hash(object4) = key4; 图2.2 环形hash空间 步骤三:把服务器映射到hash空间。 Consistent Hashing 的基本思想就是将对象和服务器都映射到同一个 hash 数值空间,并且使用相同的 hash 算法。 假设当前有 A、B和C共3台服务器,那么其映射结果将如图2.3所示,它们在 hash 空间中,以对应的 hash 值排列。 hash(服务器 A) = key A; … hash(服务器 C) = key C; 分布式爬虫 分布式爬虫 图 2.3 4个对象的key值分布 步骤四:把对象映射到服务器。 现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是如何将对象映射到 cache 上面。 在这个环形空间中,如果沿着顺时针方向从对象的 key 值出发,直到遇见一个服务器,那么就将该对象存储在这个服务器上,因为对象和服务器的 hash 值是固定的,因此这个服务器必然是唯一和确定的。这样不就找到了对象和服务器的映射方法了吗? 依然继续上面的例子(见图2.4),那么根据上面的方法,对象 object1 将被存储到服务器A 上,object2 和 object3 对应到服务器C,object4 对应到服务器B。 图2.4 服务器对象的key值表示 步骤五:考察服务器的变动。 前面讲过,通过 hash 算法然后求余的方法带来的最大问题就在于不能满足单调性,当服务器有所变动时,服务器会失效,进而对后台服务器造成巨大的冲击,现在就来分析Consistent Hashing 算法。 (1) 移除服务器。 考虑假设服务器B 挂掉了,根据上面讲到的映射方法,这时受影响的将只是那些沿 cache B 分布式爬虫 分布式爬虫 逆时针遍历直到下一个服务器(服务器C )之间的对象,也即是本来映射到服务器B上的那些对象。 因此这里仅需要变动对象object4,将其重新映射到服务器C上即可,如图2.5所示。 (2) 添加服务器。 再考虑添加一台新的服务器D 的情况,假设在这个环形 hash 空间中,服务器D被映射在对象 object2 和 object3 之间。这时受影响的仅是那些沿 cache D 逆时针遍历直到下一个服务器(服务器B )之间的对象,将这些对象重新映射到服务器D上即可。 因此这里仅需要变动对象 object2,将其重新映射到服务器D上,如图2.6所示。 考量 hash 算法的另一个指标是平衡性(Balance),定义如下: 平衡性是指哈希的结果能够尽可能分布到所有的缓冲中,这样可以使所有的缓冲空间都得到利用。 hash 算法并不能保证绝对的平衡,如果服务器较少,对象并不能被均匀地映射到服务器上,比如在上面的例子中,仅部署服务器A和服务器C的情况下,在4个对象中, 服务器A仅存储了object1,而服务器C则存储了object2、object3和object4,分布是很不均衡的。 图2.5 服务器B被移除后的映射 图2.6 添加服务器D后的映射关系 为了解决这种情况,Consistent Hashing 引入了“虚拟节点”的概念,它可以如下定义: “虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一个实际节点对应若干个“虚拟节点”,这个对应个数也称为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。 仍以仅部署服务器 A 和 服务器C 的情况为例,在图2.5 中我们已经看到,服务器分布并不均匀。现在我们引入虚拟节点,并设置“复制个数”为2,这就意味着一共会存在4个“虚拟节点”,服务器A1和服务器A2代表服务器A;服务器C1和服务器C2代表服务器C,假设一种比较理想的情况如图2.7所示。 分布式爬虫 分布式爬虫 图2.7 引入“虚拟节点”后的映射关系 此时,对象到“虚拟节点”的映射关系为: objec1->服务器A2;objec2->服务器A1;objec3->服务器C1;objec4->服务器C2。 因此对象 object1 和 object2 都被映射到服务器 A 上,而 object3 和 object4 映射到服务器C上,平衡性有了很大提高。 引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询对象所在 cache 时的映射关系如图2.8所示。 图2.8 查询对象所在的cache “虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 服务器 A 的 IP 地址为 202.168.14.241。 引入“虚拟节点”前,计算服务器A 的 hash 值: Hash("202.168.14.241"); 引入“虚拟节点”后,计算“虚拟节点”服务器A1 和服务器A2 的 hash 值: hash("202.168.14.241#1");  // cache A1 hash("202.168.14.241#2");  // cache A2 分布式爬虫 分布式爬虫 2.2.3 Consistent Hash代码实现 上一节,讲述了Consistent Hash算法的原理。本节,我们实现一个简单的Consistent Hash算法。 public class ConsistentHash { private final HashFunction hashFunction;//hash算法 private final int numberOfReplicas;//虚拟节点数目 private final SortedMap circle = new TreeMap(); public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection nodes //物理节点) { this.hashFunction = hashFunction; this.numberOfReplicas = numberOfReplicas; for (T node : nodes) { add(node); } } public void add(T node) { for (int i = 0; i < numberOfReplicas; i++) { circle.put(hashFunction.hash(node.toString() + i), node); } } public void remove(T node) { for (int i = 0; i < numberOfReplicas; i++) { circle.remove(hashFunction.hash(node.toString() + i)); } } public T get(Object key) {//关键算法 if (circle.isEmpty()) { return null; } //计算hash值 int hash = hashFunction.hash(key); //如果不包括这个hash值 if (!circle.containsKey(hash)) { SortedMap tailMap = circle.tailMap(hash); hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); } return circle.get(hash); } 本节内容详细讲述了有关分布式和云计算存储的相关问题,下面几节,我们将讲述Google的分布式和云计算技术以及它们在网络爬虫中的应用。 分布式爬虫 分布式爬虫 2.3 Google的成功之道——GFS Google之所以能成功,很大程度上是应用了GFS+BigTable+MapReduce的架构。由于这种架构,使得Google在当前风起云涌的云计算热潮中始终保持领先地位。Google的爬虫也是采用GFS作为存储网页的底层数据结构。为何GFS能如此受Google的青睐?本节将为你揭示这个谜团。 2.3.1 GFS详解 GFS(Google File System)是Google自己研发的一个适用于大规模分布式数据处理相关应用的、可扩展的分布式文件系统。它基于普通的不算昂贵的硬件设备,实现了容错的设计,并且为大量客户端提供了极高的聚合处理性能。GFS正好与Google的存储要求相匹配,因此在Google内部广泛用作存储平台,适用于Google的服务产生和处理数据应用的要求,以及Google的海量数据的要求。Google最大的集群通过上千个计算机的数千个硬盘,提供了数百TB的存储,并且这些数据被数百个客户端并行操作。Google之所以要研发自己的分布式文件系统,是因为在分布式存储环境中,常常会产生以下一些问题。 1. 在分布式存储中,经常会出现节点失效的情况 因为在分布式存储中,文件系统包含了几百个或者几千个廉价的普通机器,而且这些机器要被巨大数量的客户端访问。节点失效可能是由于程序的bug,操作系统的bug,人工操作的失误,以及硬盘坏掉,内存、网络、插板的损坏,电源的坏掉等原因造成的。因此,持续监视,错误检测,容错处理,自动恢复必须集成到这个文件系统的设计中。 2. 分布式存储的文件都是非常巨大的 GB数量级的文件是常事。每一个文件都包含了很多应用程序对象,比如Web文档等。搜索引擎的数据量是迅速增长的,它通常包含数十亿数据对象。如果使用一般的文件系统,就需要管理数十亿个KB数量级大小的文件。而且,每次I/O只能读出几个字节也不能满足搜索引擎吞吐量的要求。因此,Google决定设计自己的文件系统,重新规定每次I/O的块的大小。 3. 对于搜索引擎的业务而言,大部分文件都只会在文件尾新增加数据,而少见修改已 有数据的 对一个文件的随机写操作在实际上几乎是不存在的。一旦写完,文件就是只读的,并且一般都是顺序读取。比如,在网络爬虫中,把网页抓取下来之后不会做修改,而只是简单地存储,作为搜索结果的快照。在实际的系统中,许多数据都有这样的特性。有些数据可能组成很大的数据仓库,并且数据分析程序从头扫描到尾。有些可能是运行应用而不断地产生数据流。对于这些巨型文件的访问模式来说,增加模式是最重要的,所以我们首要优化性能的就是它。 分布式爬虫 分布式爬虫 4. 与应用一起设计的文件系统API对于增加整个系统的弹性和适用性有很大的好处 为了满足以上几点需要,Google遵照下面几条原则设计了它的分布式文件系统(GFS): (1) 系统建立在大量廉价的普通计算机上,这些计算机经常出故障。则必须对这些计算机进行持续检测,并且在系统的基础上进行检查、容错,以及从故障中进行恢复。 (2) 系统存储了大量的超大文件。数GB的文件经常出现并且应当对大文件进行有效的管理。同时必须支持小型文件,但是不必为小型文件进行特别的优化。 (3) 一般的工作都是由两类读取组成:大的流式读取和小规模的随机读取。在大的流式读取中,每个读操作通常一次就要读取几百字节以上的数据,每次读取1MB或者以上的数据也很常见。因此,在大的流式读取中,对于同一个客户端来说,往往会发起连续的读取操作顺序读取一个文件。而小规模的随机读取通常在文件的不同位置,每次读取几字节数据。对于性能有过特别考虑的应用通常会做批处理并且对它们读取的内容进行排序,这样可以使得它们的读取始终是单向顺序读取,而不需要往回读取数据。 (4) 通常基于GFS的操作都有很多超大的、顺序写入的文件操作。通常写入操作的数据量和读入的数据量相当。一旦完成写入,文件就很少会更改。应支持文件的随机小规模写入,但是不需要为此做特别的优化。 5. 系统必须非常有效地支持多个客户端并行添加同一个文件 GFC文件经常使用生产者/消费者队列模式,或者以多路合并模式进行操作。好几百个运行在不同机器上的生产者,将会并行增加一个文件。 6. 高性能的稳定带宽的网络要比低延时更加重要 GFS目标应用程序一般会大量操作处理比较大块的数据。 基于以上几点考虑,GFS采用了如图2.9所示的架构。 图2.9 Google File System架构 如图2.9所示,GFS集群由一个主服务器(master)和多个块服务器(chunkserver)组成,GFS集群会有很多客户端访问。每一个节点都是一个普通的Linux计算机,运行的是一个用户级别的服务器进程。 分布式爬虫 分布式爬虫 在GFS下,每个文件都被拆成固定大小的块(chunk)。每一个块都由主服务器根据块创建的时间产生一个全局唯一的以后不会改变的64位的块处理(chunk handle)标志。块服务器在本地磁盘上用Linux文件系统保存这些块,并且根据块处理标志和字节区间,通过Linux文件系统读写这些块的数据。出于可靠性的考虑,每一个块都会在不同的块处理器上保存备份。 主服务器负责管理所有的文件系统的元数据,包括命名空间、访问控制信息、文件到块的映射关系、当前块的位置等信息。主服务器也同样控制系统级别的活动,比如块的分配管理,孤点块的垃圾回收机制、块服务器之间的块镜像管理。 连接到各个应用系统的GFS客户端代码包含了文件系统的API,并且会和主服务器及块服务器进行通信处理,代表应用程序进行读写数据的操作。客户端和主服务器进行元数据的操作,但是所有的数据相关的通信是直接和块服务器进行的。 由于在流式读取中,每次都要读取非常多的文件内容,并且读取动作是顺序读取,因此,在客户端没有设计缓存。没有设计缓存系统使得客户端以及整个系统都大大简化了(少了缓存的同步机制)。块服务器不需要缓存文件数据,因为块文件就像本地文件一样被保存,所以Linux的缓存已经把常用的数据缓存到了内存里。 下面简单介绍图2.9中的读取操作分段。首先,客户端把应用要读取的文件名和偏移量,根据固定的块大小,转换为文件的块索引。然后向主服务器发送这个包含了文件名和块索引的请求。主服务器返回相关的块处理标志以及对应的位置。客户端缓存这些信息,把文件名和块索引作为缓存的关键索引字。 于是这个客户端就向对应位置的块服务器发起请求,通常这个块服务器是离这个客户端最近的一个。请求给定了块处理标志以及需要在所请求的块内读取的字节区间。在这个块内,再次操作数据将不用再通过客户端-主服务器的交互,除非这个客户端本身的缓存信息过期了,或者这个文件重新打开了。实际上,客户端通常都会在请求中附加向主服务器询问多个块的信息,主服务器会立刻给这个客户端回应这些块的信息。这个附加信息是通过几个几乎没有任何代价的客户端-主服务器的交互完成的。 块的大小是设计的关键参数。Google选择的块大小为64MB,远远大于典型的文件系统的块大小。每一个块的实例(复制品)都是作为在主服务器上的Linux文件格式存放的,并且只有当需要的情况下才会增长。滞后分配空间的机制可以通过文件内部分段来避免空间浪费,对于这样大的块大小来说,内部分段可能是一个最大的缺陷了。 选择一个很大的块可以提供一些重要的好处。首先,它减少了客户端和主服务器的交互,因为在同一个块内的读写操作只需要客户端初始询问一次主服务器关于块的位置信息就可以了。对主服务器访问的减少可以显著提高系统性能,因为使用GFS的应用大部分是顺序读写超大文件的。即使是对小范围的随机读,客户端也可以很容易地缓存许多大的数据文件的位置信息。其次,由于是使用一个大的块,客户端可以在一个块上完成更多的操作,它可以通过维持一个到主服务器的TCP持久连接来减少网络管理量。第三,它减少了元数据在主服务器上的大小,使得Google应用程序可以把元数据保存在内存中。 下面简单介绍图2.9中的主服务器: 主服务器节点保存了三个主要的数据类型:文件和块的命名空间,文件到块的映射关 分布式爬虫 分布式爬虫 系,每一个块的副本的位置。所有的元数据都保存在主服务器的内存里。头两个类型(namepspaces和文件到块的映射)同时也保存在主服务器本地磁盘的日志中。通过日志,在主服务器宕机的时候,我们可以简单、可靠地恢复主服务器的状态。主服务器并不持久化保存块位置信息。相反,它在启动的时候以及主服务器加入集群的时候,向每一个主服务器询问它的块信息。 因为元数据都是在内存保存的,所以在主服务器上操作很快。另外主服务器也很容易定时扫描后台所有的内部状态。定时扫描内部状态可以用来实现块的垃圾回收,当主服务器失效的时候重新复制,还可以作为服务器之间的块镜像,在执行负载均衡和磁盘空间均衡任务时使用。 因为我们采用内存保存元数据的方式,如果需要支持更大的文件系统,我们可以简单、可靠、高效、灵活地通过增加主服务器的内存来实现。 主服务器并不持久化保存块服务器上的块记录。它只是在启动的时候简单地从块服务器取得这些信息。主服务器可以在启动之后一直保持自己的这些信息是最新的,因为它控制所有的块的位置。 上文提到的主服务器的日志信息保存了关键的元数据变化历史记录,它是GFS的核心。不仅仅因为它是唯一持久化的元数据记录,而且也是因为日志记录也是作为逻辑时间基线,定义了并行操作的顺序。块以及文件,都是用它们创建时刻的逻辑时间基线来作为唯一的并且永远唯一的标志。 由于日志记录是极关键的,因此必须可靠保存,在元数据改变并且持久化之前,对于客户端来说都是不可见的(也就是说保证原子性)。否则,就算是在块服务器完好的情况下,也可能会丢失整个文件系统,或者最近的客户端操作。因此,把这个文件保存在多个不同的主机上,并且只有当刷新这个相关的日志记录到本地和远程磁盘之后,才会给客户端操作应答。主服务器可以每次刷新一批日志记录,以减少刷新和复制这个日志导致的系统吞吐量。 主服务器通过自己的日志记录进行自身文件系统状态的反演。为了减少启动时间,我们必须尽量减少操作日志的大小。主服务器在日志增长超过某一个大小的时候,执行检查点动作,这样可以使下次启动的时候从本地硬盘读出这个最新的检查点,然后反演有限记录数。检查点是一个类似B-树的格式,可以直接映射到内存,而不需要额外的分析。这更进一步加快了恢复的速度,提高了可用性。 对于主服务器的恢复,只需要最新的检查点以及后续的日志文件。旧的检查点及其日志文件可以删掉了,但我们还是要保存几个检查点以及日志文件,用来防止发生比较大的故障。 GFS是一个松散的一致性检查的模型,通过简单高效的实现,来支持高度分布式计算的应用。下面详细讲解GFS的一致性模型。 文件名字空间的改变(如文件的创建)是原子操作,由主服务器来专门处理。名字空间的锁定保证了操作的原子性以及正确性,主服务器的操作日志定义了这些操作的全局顺序。 什么是文件区,文件区就是在文件中的一小块内容。 不论对文件进行何种操作,文件区所处的状态都包括三种:一般成功、并发成功和失败。表2.1列出了这些结果。当所有的客户端看到的都是相同的数据的时候,并且与这些客户端从哪个数据的副本读取无关的时候,这个文件区是一致性的。当一个更改操作成功完成,而且没有并发写冲突时,那么受影响的区就是确定的(并且潜在一致性):所有客户端都可以看到这个变化是什么。并发成功操作使得文件区是不确定的,但是是一致性的:所有客户端都看到了相同的数据,但是并不能确定到底什么变化发生了。通常,这种变化由好多个变动混合片断组成。一个失败的改变会使得一个文件区不一致(因此也不确定):不同的用户可能在不同时间看到不同的数据。 分布式爬虫 分布式爬虫 如果表2.1中数据更改可能是写一个记录或者是一个记录增加。写操作会导致一个应用指定的文件位置的数据写入动作。记录增加会导致数据(记录)增加,这个增加即使是在并发操作中也至少是一个原子操作,但是在并发记录增加中,GFS选择一个偏移量增加(与之对应的是,一个“普通”增加操作是类似写到当前文件最底部的一个操作)。我们把偏移量返回给客户端,并且标志包含这个记录的确定的区域的开始位置。另外,GFS可以在这些记录之间增加填充,或者仅仅是记录的重复。这些确定区间之间的填充或者记录的重复是不一致的,并且通常是因为用户记录数据比较小造成的。 表2.1 文件区所处状态 写 记 录 增加记录 一般成功 定义 定义 并发成功 一致定义 失败 非一致 在一系列成功的改动之后,改动后的文件区是确定的,并且包含了最后一个改动所写入的数据。GFS通过对所有的数据副本,按照相同顺序对块进行提交数据的改动来保证这样的一致性,并且采用块的版本号码控制机制来检查是否有过期的块改动,这种检查通常在主服务器宕机的情况下使用。 另外,由于客户端会缓存这个块的位置,因此可能会在信息刷新之前读到这个过期的数据副本。这个故障潜在发生的区间受块位置缓存的有效期限制,并且也受到下次重新打开文件的限制,重新打开文件会把这个文件所有的块相关的缓存信息全部丢弃而重新设置。此外,由于多数文件都只是追加数据,过期的数据副本通常返回一个较早的块尾部(也就是说这种模式下,过期的块返回的仅仅是说,这个块它以为是最后一个块,其实不是),而不是返回一个过期的数据。 2.3.2 开源GFS——HDFS Google的文件系统究竟是如何写的,我们不得而知。但是根据Google发表的论文以及GFS的相关资料,可以知道apache下有一个开源实现——HDFS。这一小节,我们来介绍HDFS的架构与设计。HDFS的架构如图2.10所示。 根据GFS中主服务器/块服务器的设计,HDFS采用了主服务器/从属服务器架构。一个HDFS集群是由一个名称节点和一定数目的数据节点组成的。名称节点是一个中心服务器,负责管理文件系统的 分布式爬虫 分布式爬虫 名称空间和客户端对文件的访问。数据节点在集群中一般是一个节点一个,负责管理节点上附带的存储。在内部,一个文件会分成一个或多个块,这些块存储在数据节点集合里。名称节点执行文件系统的名称空间操作,例如打开、关闭、重命名文件和目录,同时决定块到具体数据节点的映射。数据节点在名称节点的指挥下进行块的创建、删除和复制。名称节点和数据节点都是设计成可以运行在普通的、廉价的机器上。HDFS采用Java语言开发,因此可以部署在不同的操作系统平台上。一个典型的部署场景是一台机器运行一个单独的名称节点,集群中的其他机器各自运行一个数据节点实例。这个架构并不排除一台机器上运行多个数据节点,不过这比较少见。 图2.10 HDFS架构 名称节点运行在单一节点上大大简化了系统的架构。名称节点负责保管和管理所有的HDFS元数据,而用户与数据节点的通信就不需要通过名称节点(也就是说文件数据直接在数据节点上读写)。 HDFS支持传统的层次型文件组织,与大多数其他文件系统类似,用户可以创建目录,并在其中创建、删除、移动和重命名文件。名称节点维护文件系统的名称空间,任何对文件系统的名称空间和文件属性的修改都将被名称节点记录下来。用户可以设置HDFS保存的文件的副本数目,文件副本的数目称为文件的复制因子,这个信息也是由名称节点保存。 HDFS被设计成在一个大集群中可靠地存储海量文件的系统。它将每个文件存储成块序列,除了最后一个块,所有的块大小都是相同的。文件的所有块都会被复制。每个文件的块大小和复制因子都是可配置的。复制因子可以在文件创建的时候配置,而且以后也可以改变。HDFS中的文件是单用户写模式,并且严格要求在任何时候都只能有一个用户写入。名称节点全权管理块的复制,它周期性地从集群中的每个数据节点接收心跳包和一个数据块报告(Blockreport)。心跳包的接收表示该数据节点正常工作,而数据块报告包括该数据节点上所有的块组成的列表。 名称节点存储HDFS的元数据。对于任何修改文件元数据的操作,名称节点都用一个名为Editlog的事务日志记录下来。例如,在HDFS中创建一个文件,名称节点就会在Editlog中插入一条记录来表示;同样,修改文件的复制因子也会在Editlog中插入一条记录。名称节点 分布式爬虫 分布式爬虫 在本地OS的文件系统中存储这个Editlog。整个文件系统的名称空间,包括块到文件的映射、文件的属性,都存储在名为FsImage的文件中,这个文件也放在名称节点所在系统的文件系统中。 名称节点在内存中保存着整个文件系统的名称空间和文件块的映像。这个关键的元数据设计得很紧凑,一个带有4GB内存的名称节点足以支撑海量的文件和目录。当名称节点启动时,它从硬盘中读取Editlog和FsImage,将Editlog中的所有事务作用在内存中的FsImage,并将这个新版本的FsImage从内存中创新到硬盘上。这个过程称为检查点(checkpoint)。在当前实现中,检查点只在名称节点启动时发生。 所有的HDFS通信协议都是构建在TCP/IP协议上的。客户端通过一个可配置的端口连接到名称节点,通过各个端协议组件(Client Protocol)与名称节点交互。而数据节点是使用数据节点协议组件(Datanode Protocol)与名称节点交互。 使用HDFS的应用都是处理大数据集合的。这些应用都是写数据一次,而读是一次到多次,并且读的速度要满足流式读。HDFS支持文件的一次写入多次读取。一个典型的块大小是64MB,因而,文件总是按照64MB大小切分成块,每个块存储于不同的数据节点中。 客户端创建文件的请求其实并没有立即发给名称节点,事实上,HDFS客户端会将文件数据缓存到本地的一个临时文件。应用的写操作被透明地重定向到这个临时文件。当这个临时文件累积的数据超过一个块的大小(默认为64MB),客户端才会联系名称节点。名称节点将文件名插入文件系统的层次结构中,并且给它分配一个数据块,然后返回数据节点的标识符和目标数据块给客户端。客户端将本地临时文件刷新到指定的数据节点上。当文件关闭时,在临时文件中剩余的没有刷新的数据也会传输到指定的数据节点,然后客户端告诉名称节点文件已经关闭。此时名称节点才将文件创建操作提交到持久存储。如果名称节点在文件关闭前挂了,则该文件将丢失。 当某个客户端向HDFS文件写数据的时候,一开始是写入本地临时文件,假设该文件的复制因子设置为3,那么客户端会从名称节点获取一张数据节点列表来存放副本。然后客户端开始向第一个数据节点传输数据,第一个数据节点一小部分一小部分(4kb)地接收数据,将每个部分写入本地仓库,并且同时将该部分传输到第二个数据节点。第二个数据节点也是这样边收边传,一小部分一小部分地收,存储在本地仓库,同时传给第三个数据节点,第三个数据节点就仅仅是接收并存储了。这就是流水线式的复制。 HDFS给应用提供了多种访问方式,可以通过DFSShell命令行与HDFS数据进行交互,也可以通过Java API调用,还可以通过C语言的封装API访问,并且提供了浏览器访问的方式。 最后,通过一个简单的小例子,展示一下如何使用Java访问HDFS。 import java.io.InputStream; import java.net.URL; import org.apache.hadoop.fs.FsUrlStreamHandlerFactory; import org.apache.hadoop.io.IOUtils; public class DataReadByURL { static{ 分布式爬虫 分布式爬虫 URL.setURLStreamHandlerFactory(new FsUrlStreamHandlerFactory()); } public static void main(String[] args) throws Exception{ InputStream in = null; try{ in = new URL("hdfs://127.0.0.1:9000/data/mydata").openStream(); IOUtils.copyBytes(in,System.out,2048,false); }finally{ IOUtils.closeStream(in); } } } 上面讨论了利用HDFS的URL方式读取HDFS内文件内容的方法,下面讨论如何使用HDFS中的API读取HDFS内的文件。 HDFS主要通过FileSystem类来完成对文件的打开操作。和Java使用java.io.File来表示文件不同,HDFS文件系统中的文件是通过Hadoop的Path类来表示的。 FileSystem通过静态方法 get(Configuration conf)获得FileSystem的实例。通过FileSystem的open()、seek()等方法可以实现对HDFS的访问,具体的方法如下所示: public FSDataInputStream open(Path f) throws IOException public abstract FSDataInputStream open(Path f, int bufferSize) throws IOException; 下面来看一个通过HDFS的API访问文件系统的例子: import org.apache.hadoop.fs.*; import org.apache.hadoop.conf.*; import org.apache.hadoop.io.*; public class HDFSCatWithAPI { public static void main(String[] args) throws Exception{ // 指定Configuration Configuration conf = new Configuration(); //定义一个DataInputStream FSDataInputStream in = null; try{ //得到文件系统的实例 FileSystem fs = FileSystem.get(conf); //通过FileSystem的open方法打开一个指定的文件 in = fs.open(new Path("hdfs://localhost:9000/user/myname/input/fixFontsPath.sh")); //将InputStream中的内容通过IOUtils的copyBytes方法复制到System.out中 IOUtils.copyBytes(in,System.out,4096,false); //seek到position 1 in.seek(1); //执行一边复制一边输出工作 分布式爬虫 分布式爬虫 IOUtils.copyBytes(in,System.out,4096,false); }finally{ IOUtils.closeStream(in); } } } 输出如下: #!/bin/sh # Licensed to the Apache Software Foundation (ASF) under one or more # contributor license agreements.  See the NOTICE file distributed with # this work for additional information regarding copyright ownership. # The ASF licenses this file to You under the Apache License, Version  ...(中间内容略去) EOF !/bin/sh # Licensed to the Apache Software Foundation (ASF) under one or more # contributor license agreements.  See the NOTICE file distributed with # this work for additional information regarding copyright ownership. # The ASF licenses this file to You under the Apache License, Version   ...(中间内容略去) EOF 2.4 Google网页存储秘诀——BigTable 在前面的章节里,提到过分布式系统通常都采用key/value的形式存储数据。比如爬虫抓取页面后,页面的存储就是采用key/value形式。针对这一特点,Google在GFS文件系统的基础上,设计了一种名为BigTable的key/value型分布式数据库系统。应用程序通常都不会直接操作GFS文件系统,而直接操作它的上一级存储结构——BigTable。这正如一般文件系统和关系数据库的道理一样。这一节,我们将详细讲述BigTable的相关知识。 2.4.1 详解BigTable Bigtable(下文中简称BT)是用来存储大规模结构化数据的,它最多可以存储250个字节,分布在几千个普通的服务器上。Google的很多项目都使用BT存储数据,包括网页查询、Google 地图和Google金融。这些应用对BT的要求各不相同:数据大小(从URL到网页到卫星图像)不同,反应速度不同(从后端的大批处理到实时数据服务)。对于不同的项目需求,BT都提供了灵活高效的服务。 分布式爬虫 分布式爬虫 设计BT的目标是建立一个可以广泛应用的、高度扩缩的、高可靠性和高可用性的分布式数据库系统。现在,Google至少有60多个产品和应用都采用BT作为存储结构。下面我们从几个方面介绍BT。 1. BT与关系数据库 BT在很多地方和关系数据库类似:它采用了许多关系数据库的实现策略。但和它们不同的是,BT采用了不同的用户接口。BT不支持完全的关系数据模型,而是为客户提供了简单的数据模型,让客户来动态控制数据的分布和格式(就是只存储字符串,格式由客户来解释),这样能大幅度地提高访问速度。数据的下标是行和列的名字,数据本身可以是任意字符串。BT的数据是字符串,没有具体的类型。客户会把各种结构化或者半结构化的数据(比如说日期串)序列化成字符串。最后,可以使用配置文件来控制数据是放在内存里还是在硬盘上。 2. BT逻辑存储结构 BT的本质是一个稀疏的、分布式的、长期存储的、多维度的和排序的Map。Map的key是行关键字(Row)、列关键字(Column)和时间戳(Timestamp)。Value是一个普通的bytes数组。如下所示: (row:string, column:string,time:int64)->string 图2.11是BT存储网页的底层数据结构示意图(webtable)。其中,每个网页的内容与相关信息作为一行,无论它有多少列。 如图2.11所示,以反转的URL作为Row,列关键字是“contents”、“anchor:my.look.ca”和“anchor:cnnsi.com”,时间戳是t3, t5, t6, t8, t9等。如果要查询t5时间URL为www.cnn.com的页面内容,可以使用{com.cnn.www,contents,t5}作为key去BT中查询相应的value。 图2.11 BT存储示意图 表中的行(Row)可以是任意长度的字符串(目前最多支持64KB,多数情况下10~100个字节就足够了)。在同一行下的每一个读写操作都是原子操作(不管读写这一行里多少个不同列),这使得在对同一行进行并发操作时,用户对于系统行为更容易理解和掌控。 BT通过行关键字在字典中的顺序来维护数据。一张表可以动态划分成多个连续“子表”(tablet)。这些“子表”由一些连续行组成,它是数据分布和负载均衡的单位。这使得读取较少的连续行比较有效率,通常只需要少量机器之间的通信即可。用户可以利用这个属性来选择行关键字,从而达到较好的数据访问 分布式爬虫 分布式爬虫 “局部性”。举例来说,在webtable中,通过反转URL中主机名的方式,可以把同一个域名下的网页组织成连续行。具体而言,可以把站点maps.google.com/index.html中的数据存放在关键字com.google.maps/index.html所对应的数据中。这种存放方式可以让基于主机和基于域名的分析更加有效。 一组列关键字组成了“列族”(column famliy),这是访问控制的基本单位。同一列族下存放的所有数据通常都是同一类型的。“列族”必须先创建,然后才能在其中的“列关键字”下存放数据。“列族”创建后,其中任何一个“列关键字”都可使用。 “列关键字”用如下语法命名:“列族”:限定词。“列族”名必须是看得懂的字符串,而限定词可以是任意字符串。比如,webtable可以有个“列族”叫language,存放撰写网页的语言。我们在language“列族”中只用一个“列关键字”,用来存放网页的语言标识符。该表的另一个有用的“列族”是anchor。“列族”的每一个“列关键字”代表一个锚链接,访问控制、磁盘使用统计和内存使用统计,均可在“列族”这个层面进行。在图2.11的例子中,可以使用这些功能来管理不同应用:有的应用添加新的基本数据,有的读取基本数据并创建引申的“列族”,有的则只能浏览数据(甚至可能因为隐私权的原因不能浏览所有数据)。 BT表中的每一个表项都可以包含同一数据的多个版本,由时间戳来索引。BT的时间戳是64位整型,表示准确到毫秒的“实时”。需要避免冲突的应用程序必须自己产生具有唯一性的时间戳。不同版本的表项内容按时间戳倒序排列,即最新的排在前面。在图2.11中,“contents:”列存放一个网页被抓取的时间戳。 BT使用Google分布式文件系统(GFS)来存储日志和数据文件。一个BT集群通常在一个共享的机器池中工作,池中的机器还运行着其他分布式应用,BT和其他程序共享机器(BT的瓶颈是I/O内存,可以和CPU要求高的程序并存)。BT依赖集群管理系统来安排工作,在共享的机器上管理资源,处理失效机器并监视机器状态。 3. BT内部存储格式——SSTable BT内部采用SSTable格式存储数据。SSTable提供了一个从关键字到值的映射,关键字和值都可以是任意字符串,如图2.12所示。 图2.12 SSTable示意图 在SSTable格式中,映射是排序的、存储的(不会因为掉电而丢失)、不可更改的。并且可以进行如下操作: (1) 通过关键字查询相关的值。 (2) 根据给出的关键字范围遍历所有的关键字和值。 SSTable内部包含一列数据块,通常每个块的大小是64KB,但是大小是可以配置的。 分布式爬虫 分布式爬虫 SSTable中块索引(index)大小是16 位。块索引(存储在SSTable的最后)用来定位数据块。当打开SSTable的时候,块索引被读入内存。每次查找都可以用一次硬盘搜索完成,首先在内存中的索引里进行二分查找,获得数据块的位置,然后根据位置信息直接到硬盘读取数据块。最佳情况是:整个SSTable可以被放在内存里,这样一来就不必访问硬盘了。 4. BT的锁 BT还依赖一个高度可用的分布式数据锁服务(Chubby)。一个Chubby 由5个“活跃”的备份构成,其中一个被这些备份选成主备份,并且处理请求。这个服务只有在大多数备份都是“活跃”的并且互相通信的时候,才是“活跃”的。当有机器失效的时候,Chubby使用一定的算法来保证备份的一致性。Chubby提供了一个名字空间,里面包括目录和一系列文件。每个目录或者文件可以当成一个锁来用,读写文件操作都是原子操作。Chubby客户端的程序库提供了对Chubby文件的一致性缓存。每个Chubby客户维护一个和Chubby通信的会话。如果客户不能在一定时间内更新自己的会话,会话就失效了。当一个会话失效时,其拥有的锁和打开的文件句柄都失效。Chubby客户可以在文件和目录上登记回调函数,以获得改变或者会话过期的通知。 BT使用锁服务来完成以下几个任务: (1) 保证任何时间最多只有一个活跃的主备份。 (2) 存储BT数据的启动位置。 (3) 发现“子表”服务器,并处理tablet服务器失效的情况。 (4) 存储BT数据的“模式”信息(每张表的列信息)。 (5) 存储访问权限列表。在Chubby中,存储了BT的访问权限,如果Chubby不能访问,那么由于获取不到访问权限,因此BT就也不能访问了。 5. BT的主要组成部件 BT主要由三个构件组成: (1) 一个客户端的链接库。 (2) 一个主服务器。 (3) 许多“子表”服务器。“子表”服务器可以动态地从群组中被添加和删除,以适应流量的改变。 主服务器的作用是给“子表”服务器分配“子表”、探测“子表”服务器的增加和缩减、平衡“子表”服务器负载,以及回收GFS系统中文件的碎片。此外,它还可以创建模式表。 一个“子表”服务器管理许多子表(一般每个“子表”服务器可以管理10到1000个子表)。“子表”服务器处理它所管理的“子表”的读写请求,还可以将那些变得很大的“子表”分割。 像许多单主机的分布式存储系统一样,客户端数据不是通过主服务器来传输的:客户端要读写时直接与“子表”服务器通信。因为BT客户端并不依赖主服务器来请求“子表”本地信息,大多数客户端从不与主服务器通信。因此,实际上主机的负载往往很小。 分布式爬虫 分布式爬虫 一个BT群组可以存储大量的表。每一个表有许多“子表”,并且每个“子表”包含一行上所有相关的数据。最初,每个表只包含一个子表。随着表的增长,自动分成了许多的“子表”,每个子表的默认大小为100~200MB。 BT用三层体系的B+树来存储子表的地址信息,如图2.13所示。 图2.13 BT的B+树的体系结构 第一层是一个存储在Chubby中的文件,它包含“根子表”(root tablet)的地址。如图2.13所示,“根子表”包含一些“元数据表”(MetaData tablets)的地址信息。这些“元数据表”包含用户“子表”的地址信息。“根子表”是“元数据表”中的第一个“子表”,但它从不会被分割。 客户端缓存“子表”地址。如果客户端发现缓存的地址信息是错误的,那么它会递归地提升“子表”地址等级。如果客户端缓存是空的,寻址算法需要三个网络往返过程,包括一次从Chubby的读取。如果客户端缓存是过期的,那么寻址算法可能要用6个往返过程。尽管“子表”地址缓存在内存里,不需要GFS访问,但还是可以通过客户端预提取“子表地址”进一步降低性能损耗。 “子表”一次被分配给一个子表服务器。主服务器跟踪“活跃”的“子表”服务器集合以及当前“子表”对“子表服务器”的分配状况。当一个“子表”还没有被分配,并且有一个“子表”服务器是可用的,主机就通过传输一个“子表”装载请求到“子表”服务器来分配“子表”。 BT使用Chubby来跟踪“子表”服务器。当“子表”服务器启动时,它在一个特别的Chubby目录中创建一个文件,并且获得一个互斥锁。主机通过监听这个目录(服务器目录)来发现“子表”服务器。如果“子表”服务器丢失了自己的互斥锁,就会停止为它的“子表”服务。 主机负责探测何时“子表”服务器不再为它的“子表”服务,以便可以尽快地分配那些“子表”。为了达到这个目的,主机会周期性地询问每个“子表”服务器的锁的状态。如果一个“子表”服务器报告它丢失了锁,主机会尝试在服务器的文件中获取一把互斥锁。如果主机能获得这把锁,则表示Chubby是可用的并且“子表”服务器已经失效。因此主机通过删除“子表”服务器的服务文件来确保它不会再工作。一旦服务文件被删除,主机可以把先前分配给这台服务器的所有“子表”移到未分配的“子表”集合中。 “子表”的持久化状态存储在GFS文件里,如图2.14所示。 分布式爬虫 分布式爬虫 图2.14 子表持久化 每次更新“子表”前都要更新“子表”的重做日志(redo log)。并且最近更新的内容(已经提交的但还没有写入到磁盘的内容)会存放在内存中,称为memtable。之前的更新(已经提交的并且固化在磁盘的内容)会被持久化到一系列的SSTable中。 当一个写操作请求过来时,“子表”服务器会先写日志,当提交的时候,就把这些更新写入memtable中。之后等系统不繁忙的时候,就写入SSTable中(这个过程和Oracle数据库写操作基本一致)。 如果请求是读操作,则可以根据当前的memtable和SSTable中的内容进行合并,然后对请求返回结果。因为memtable和SSTable有相同的结构,因此,合并是一个非常快的操作。 2.4.2 开源BigTable——HBase Google提出“云计算”理论之后,很多团队都开始根据这一理论,开发自己的云计算存储模型。其中,HBase是一个比较成功的实例。本小节就讲述HBase的相关知识。 HBase是一个Apache开源项目,它的目标是提供一个在Hadoop分布式环境中运行的类似于BT的存储系统。正如同Google将BT架设在自己的分布式存储系统GFS中一样,HBase是基于HDFS的。 在HBase中,数据在逻辑上被组织成为表、行和列。客户可以使用类似于iterator的接口来遍历行数据,同时也可以通过行值来获取列值。同一个行对应多个不同版本的列值。 1. 数据模型 HBase使用的数据模型和BT类似。应用程序将数据行存储在“打上标签”的表中。一个数据行包含一个排好序的行键值和任意长度的列值。 列名的格式为“:

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 20 金币 [ 分享文档获得金币 ] 26 人已下载

下载文档