《中国电信——Google核心技术初探》由会员分享，可在线阅读，更多相关《中国电信——Google核心技术初探（106页珍藏版）》请在金锄头文库上搜索。
1、核心技术初探核心技术初探中国电信集团股份有限公司广州研究院中国电信集团股份有限公司广州研究院提纲提纲1由廉价计算机组成的计算群集由廉价计算机组成的计算群集Google的全球性架构的全球性架构2GFSGoogle的文件系统浅析的文件系统浅析3ChubbyGoogle的锁服务的锁服务4bigtableGoogle为结构化数据开发的分布式数据库为结构化数据开发的分布式数据库5map/reduceGoogle的分布式并行编程框架的分布式并行编程框架6sawzallGoogle的并行编程语言的并行编程语言7GAEGoogleApplicationEngine8开源方面的开源方面的Hadoop9判断网页的
2、重要性判断网页的重要性Pagerank算法简介及正确性浅析算法简介及正确性浅析10总结总结Google是什么？是什么？Google 本是数学中的一个名词，它表示一个十分巨大的数： 1后面跟 100个 0（即 10 的100次方）Sergey Brin 和Larry Page 使用Google 作为自己的搜索引擎和公司名的主要原因是希望自己设计的 Web 搜索引擎将来能够支持十分巨大的 Web页面检索Google集群计算机数量的增长集群计算机数量的增长万台2001.30.82006.8452003102008.1080万？90值得注意的值得注意的Google的查询结果的查询结果约有约有427,0
3、00项符合项符合googleclusterieee的查询结果，以下的查询结果，以下是第是第1-10项项（搜索用时（搜索用时0.24秒）秒）查询时间查询时间2008-8-309:00约有约有426,000项符合项符合googleclusterieee的查询结果，以下的查询结果，以下是第是第1-10项项（搜索用时（搜索用时0.27秒）秒）查询时间查询时间2008-8-3015:47Why?WhatwillhappenwhenauserentersaquerytoGoogle?Google的查询服务架构的查询服务架构1、DNS负载均衡（考虑全球各个群集的负载情况）2、群集内部的硬件负载均衡设备制定一
4、个web server3、将query执行拆分成两个主要阶段：（1）index server进行反向索引查询，并输出各关键字对应文档集合的交集（docid的列表，排序）（2）根据docid的列表由docment server计算实际的title、url和摘要http:/ + cluster使用复制技术提升容量及容错使用复制技术提升容量及容错查询行为的特点：只读操作为主、更新操作（写）很少查询行为的特点：只读操作为主、更新操作（写）很少充分利用群集固有的并行计算特性充分利用群集固有的并行计算特性将数据及处理器分割成独立的将数据及处理器分割成独立的shard，这样能够使性能近似线性增加，这样能够使
5、性能近似线性增加强调群集的整体吞吐量而不是单一线程的高性能强调群集的整体吞吐量而不是单一线程的高性能依赖软件可靠性，不使用依赖软件可靠性，不使用RAID使用复制以达到高吞吐量和高可用性使用复制以达到高吞吐量和高可用性性价比为第一考虑，只配置目前性价比最好的性价比为第一考虑，只配置目前性价比最好的cpu使用廉价的普通使用廉价的普通pcGoogle的数据中心的数据中心Tonsofcheapx86boxesPrice/performanceiskingPowerisamajorissue,tooDatasetissplitupovermultiplemachinesIndexserversDocum
6、entserversSpellcheckserversetc.Google典型的硬件配置典型的硬件配置Cheapx86boxes,40-80/rackModestdiskspace/box(250GB?;oneperbox)Intra-racknetworkis100baseTInter-racknetworkis1000baseTTheybuildtheirownserversandswitchesHavemanypatentsoncable/rack/powerinnovations性价比性价比Traditionalbig-ironbox(circa2003)82GHzXeons64GBR
7、AM8TBdisk$758,000USDPrototypicalGOOGrack(circa2003)1762GHzXeons176GBRAM7TBdisk$278,000USD有了分布式架构，有了分布式架构，Google还需要淘汰机器吗？还需要淘汰机器吗？集群中的跨代集群中的跨代cpu，从单一处理器的，从单一处理器的533MHz的的IntelCeleron服务器到双服务器到双1.4GHz的奔腾的奔腾III服务器（服务器（2003年的情况）年的情况）Google的标准是计算每查询成本的标准是计算每查询成本/性能，因此每台机器只使性能，因此每台机器只使用用2-3年年另外一个因素，即使另外一个因素
8、，即使Google开发了大规模并行算法，也需要开发了大规模并行算法，也需要淘汰过久的硬件，使得能够保持相对简单的并行控制淘汰过久的硬件，使得能够保持相对简单的并行控制Google真的要建水电站吗？真的要建水电站吗？商业商业IDC的能耗是的能耗是70-150W每平每平方英尺，方英尺，Google的数据中心达的数据中心达到到400-700W每平方英尺每平方英尺用于冷却的空调系统、用于冷却的空调系统、UPS系系统也需要专门设计统也需要专门设计Google对微处理器的看法对微处理器的看法需要适度的高需要适度的高CPI（性能因子，（性能因子，Clockcyclesperinstruction）指令层没有
9、太多可开发的并行计算潜力指令层没有太多可开发的并行计算潜力对于线程级的并发，微电路层的并行计算架构是有希望的对于线程级的并发，微电路层的并行计算架构是有希望的（按照（按照Google的说法，双核的说法，双核cpu能提高能提高30%的性能）的性能）小结：小结：Google的做法的做法Replication,replication,replicationEachpieceofdataisavailableonmultiplemachinesLiterallydozensofcopiesoftheWebacrosstheirclustersRequestsaresplitupoverthelogic
10、alclustersandhandledinparallelGoogle的逻辑结构图的逻辑结构图Google需要解决海量计算的需求需要解决海量计算的需求more queriesbetter resultsmore dataEveryGoogleserviceseescontinuinggrowthincomputationalneedsMore queriesMore users, happier usersMore dataBigger web, mailbox, blog, etc.Better resultsFind the right information, and find it
11、fasterGoogleTechnologyLayers Computing platform Distributed systems infrastructure Services and Applications Web searchGMailAds systemGoogle MapsCheap PC HardwareLinuxPhysical 的核心组件的核心组件Distributedlockserver:chubby.Distributedstorage:GFS,BigTable.Theworkqueue.Parallelcomputation:MapReduce,Sawzall.GF
12、S:TheGoogleFileSystemReliabledistributedstoragesystemforpetabytescalefilesystems.Datakeptin64-megabyte“chunks”storedondisksspreadacrossthousandsofmachinesEachchunkreplicated,usually3times,ondifferentmachinessothatGFScanrecoverseamlesslyfromdiskormachinefailure.AGFSclusterconsistsofasinglemaster,mult
13、iplechunkservers,andisaccessedbymultipleclients.ClientClientMisc. serversClientReplicasMastersGFS MasterGFS MasterC0C1C2C51 revresknuhCC0C5N revresknuhCC1C3C52 revresknuhCMaster manages metadataData transfers happen directly between clients/chunkserversFiles broken into chunks (typically 64 MB)Chunk
14、s triplicated across three machines for safetySee SOSP03 paper at http:/ 2、文件被分割成固定尺寸的块。在每个块创建的时候，服务器分配给它一个不变的、全球唯一的64位的块句柄对它进行标识。块服务器把块作为linux文件保存在本地硬盘上，并根据指定的块句柄和字节范围来读写块数据。 3、主服务器管理文件系统所有的元数据，包括名称空间，访问控制信息，文件到块的映射信息，以及块当前所在的位置。它还管理系统范围的活动，例如块租用管理，孤儿块的垃圾回收，以及块在块服务器间的移动。主服务器用心跳信息周期地跟每个块服务器通讯，发送指令并收
15、集块服务器状态。 GFS的接口的接口GFS提供了一个类似传统文件系统的接口，虽然它并没有实现类似提供了一个类似传统文件系统的接口，虽然它并没有实现类似POSIX的标准的标准API。文件在目录中按照层次组织，用路径名来标识。我们。文件在目录中按照层次组织，用路径名来标识。我们支持常用的操作，如创建，删除，打开，关闭，读和写文件。支持常用的操作，如创建，删除，打开，关闭，读和写文件。GFS有有快照快照和和记录追加记录追加操作。快照操作可以用很低的成本创建文件或者操作。快照操作可以用很低的成本创建文件或者目录树的拷贝。记录追加操作可以在保证原子性的前提下，允许多个客目录树的拷贝。记录追加操作可以在保
16、证原子性的前提下，允许多个客户端同时在一个文件上追加数据。这对于实现多路结果合并以及户端同时在一个文件上追加数据。这对于实现多路结果合并以及生产者生产者-消费者消费者模型非常有好处，多个客户端可以同时在一个文件上追加数据，模型非常有好处，多个客户端可以同时在一个文件上追加数据，而不需要任何额外的锁定。而不需要任何额外的锁定。采用采用64M的块的优缺点的块的优缺点首先，减少了客户端和主服务器通讯的需求，因为对同一个块的读写，首先，减少了客户端和主服务器通讯的需求，因为对同一个块的读写，只需要一次用于获得块位置信息的与主服务器的通讯。对只需要一次用于获得块位置信息的与主服务器的通讯。对Google
17、非常重非常重视的工作负载来说，这种减少尤其明显，因为视的工作负载来说，这种减少尤其明显，因为Google的应用程序经常连的应用程序经常连续读写巨大的文件。续读写巨大的文件。其次，由于块尺寸很大，所以客户端会对一个给定的块进行许多操作，其次，由于块尺寸很大，所以客户端会对一个给定的块进行许多操作，这样就可以通过跟块服务器保持较长时间的这样就可以通过跟块服务器保持较长时间的TCP连接来减少网络负载。连接来减少网络负载。第三，降低了主服务器需要保存的元数据的尺寸。这就允许把元数据放第三，降低了主服务器需要保存的元数据的尺寸。这就允许把元数据放在内存中在内存中。缺点，对于小文件来说，某个块可能成为访问
18、热点，从而产生性能瓶颈。缺点，对于小文件来说，某个块可能成为访问热点，从而产生性能瓶颈。采用压缩存储采用压缩存储Google采用采用ZLIB压缩算法先对原始压缩算法先对原始Web页面信息进行压缩，然后只存储压缩页面信息进行压缩，然后只存储压缩后的结果。后的结果。ZLIB压缩算法对压缩算法对WEB文档的压缩比为文档的压缩比为3：1因此一个因此一个64MB的大的大文件，实际上包含文件，实际上包含192MB的原始的原始Web文档。文档。synclengthCompressed packetsynclengthCompressed packetPacket的格式docidencodeurllenPag
19、elenurlpage主服务器如何应对失效主服务器如何应对失效主服务器保存三种主要类型的元数据：文件和块的命名空间，文件到块主服务器保存三种主要类型的元数据：文件和块的命名空间，文件到块的映射，以及每个块副本的位置。所有的元数据都保存在主服务器的内的映射，以及每个块副本的位置。所有的元数据都保存在主服务器的内存里。存里。除此之外，前两种类型（命名空间和文件块映射）的元数据，还会用日除此之外，前两种类型（命名空间和文件块映射）的元数据，还会用日志的方式保存在主服务器的硬盘上的操作日志内，并在远程的机器内复志的方式保存在主服务器的硬盘上的操作日志内，并在远程的机器内复制一个副本。使用日志可以简单可
20、靠的更新主服务器的状态，而且不用制一个副本。使用日志可以简单可靠的更新主服务器的状态，而且不用担心服务器崩溃带来的数据不一致的风险。主服务器不会持久化保存块担心服务器崩溃带来的数据不一致的风险。主服务器不会持久化保存块的位置信息。主服务器在自己启动以及块服务器加入集群的时候，询问的位置信息。主服务器在自己启动以及块服务器加入集群的时候，询问块服务器它所包含的块的信息。块服务器它所包含的块的信息。GFS简化的一致性模型简化的一致性模型文件命名空间的修改（例如，文件创建）是原子性的。他们仅受主服务器的控制：文件命名空间的修改（例如，文件创建）是原子性的。他们仅受主服务器的控制：命名空间锁定保证了原
21、子性和正确性命名空间锁定保证了原子性和正确性。主服务器的操作日志定义了这些操作的全局总顺序主服务器的操作日志定义了这些操作的全局总顺序在一系列成功的操作后，被操作的数据范围被保证为已定义的，并且包含最后一在一系列成功的操作后，被操作的数据范围被保证为已定义的，并且包含最后一次操作写入的数据。（次操作写入的数据。（a）GFS对块的多个副本采用一样的顺序进行操作。对块的多个副本采用一样的顺序进行操作。（b）并使用块版本号来检测副本是否因为它所在的块服务器当机而错过了某些）并使用块版本号来检测副本是否因为它所在的块服务器当机而错过了某些操作，而失效了。失效的副本不会再被任何操作涉及，也不会被主服务器
22、作为块操作，而失效了。失效的副本不会再被任何操作涉及，也不会被主服务器作为块位置告知客户端，而会优先被垃圾收集。位置告知客户端，而会优先被垃圾收集。倚靠追加而不是其他的写入、检查点、写操作的自验证、自说明的记录倚靠追加而不是其他的写入、检查点、写操作的自验证、自说明的记录GFS的名称空间管理和锁的名称空间管理和锁每个主服务器操作运行之前都需要获得一系列的锁。例如，如果操作包每个主服务器操作运行之前都需要获得一系列的锁。例如，如果操作包含含/d1/d2/./dn/leaf，首先获得目录，首先获得目录/d1，/d1/d2，.，/d1/d2/./dn的读取锁，以及全路径的读取锁，以及全路径/d1/d
23、2/./dn/leaf的读写锁。的读写锁。因为名称空间可以有许多节点，所以读写锁需要的时候才会被分配，一因为名称空间可以有许多节点，所以读写锁需要的时候才会被分配，一旦不再使用就会被删除。锁的获取依据一个全局一致的顺序来避免死锁：旦不再使用就会被删除。锁的获取依据一个全局一致的顺序来避免死锁：首先由名称空间的层次决定顺序，统一层次内的锁顺序由字典顺序决定。首先由名称空间的层次决定顺序，统一层次内的锁顺序由字典顺序决定。GFS的高可用性的高可用性一个块服务器失效后，有些块的副本数量可能过低，必须被克隆以恢复它们的复一个块服务器失效后，有些块的副本数量可能过低，必须被克隆以恢复它们的复制水平。恢复
24、所有这样的块需要的时间取决于资源的总量。在实验中，停掉集群制水平。恢复所有这样的块需要的时间取决于资源的总量。在实验中，停掉集群B里面的一台块服务器。这个块服务器有里面的一台块服务器。这个块服务器有15000个块，包含个块，包含600GB的数据。为了的数据。为了限制对正在运行的程序的干扰，为一些定期任务提供余地，默认参数限制集群中限制对正在运行的程序的干扰，为一些定期任务提供余地，默认参数限制集群中最多有最多有91个并行的克隆操作（块服务器数量的个并行的克隆操作（块服务器数量的40%），每个克隆操作的速度可以），每个克隆操作的速度可以是是6.25MB（50Mbps）。所有的块会在）。所有的块会
25、在23.2分钟内恢复，复制的速度是分钟内恢复，复制的速度是440MB/s。在另外的实现中，停掉两个块服务器，每个大概有在另外的实现中，停掉两个块服务器，每个大概有16000个块和个块和660GB数据。这数据。这个双倍的失效，造成个双倍的失效，造成266个块只有一个副本。这个块只有一个副本。这266个块被优先复制，在个块被优先复制，在2分钟内分钟内所有都恢复到至少两个副本，这样就把集群推到一个状态，可以容忍另外的块服所有都恢复到至少两个副本，这样就把集群推到一个状态，可以容忍另外的块服务器失效，不会造成数据丢失。务器失效，不会造成数据丢失。ChubbyADistributedlockservic
26、e特点：特点：不是编程框架，也不是单机版上传统的互斥锁，而是一种由不是编程框架，也不是单机版上传统的互斥锁，而是一种由集群系统提供的锁服务集群系统提供的锁服务一个一个chubby的实例称之为一个的实例称之为一个chubbycell，可以为，可以为1万台万台机器提供锁服务机器提供锁服务大部分采用集中式部署，并至少复制一个远程大部分采用集中式部署，并至少复制一个远程cell主要的设计目标：可靠性、可用性、大量用户、易理解的语主要的设计目标：可靠性、可用性、大量用户、易理解的语法法chubbygoogle帝国的基石帝国的基石依赖依赖chubby运行的系统有：运行的系统有：1.GFS-usechubb
27、ylocktoappointaGFSmasterserver2.Bigtable-usechubbyinserveralways:toelectamaster,toallowthemastertodiscovertheserveritcontrol,andtopermitclientstofindthemaster3.GFSandbigtable-usechubbytostoreasmallamountofmeta-data在部署在部署chubby之前，之前，google的分布式系统采用的分布式系统采用adhoc的方法来选举的方法来选举master或者手工指定或者手工指定Chubby的优势：提
28、高可用性，在的优势：提高可用性，在failureover的时候不需要人工干涉的时候不需要人工干涉Chubby采用采用Paxos协议来解决分布式一致性的问题协议来解决分布式一致性的问题为什么是锁服务而不是其它？为什么是锁服务而不是其它？首先，首先，google发现他们的程序员有时候没有按照架构设计者的要求在设计中考虑发现他们的程序员有时候没有按照架构设计者的要求在设计中考虑高可用性，没有使用一致性协议高可用性，没有使用一致性协议其次，很多的其次，很多的google服务需要选举服务需要选举mater或者需要一个机制来在不同的机器间发或者需要一个机制来在不同的机器间发布数据，布数据，chubby的成
29、功在于充当了一个名字服务器并提供一致性的客户端的成功在于充当了一个名字服务器并提供一致性的客户端caching而不是而不是time-basedcaching第三，锁接口更容易被程序员熟悉，部分程序员在分布式环境中常常错误地使用第三，锁接口更容易被程序员熟悉，部分程序员在分布式环境中常常错误地使用锁锁最后，分布式一致性算法使用多数派来作决定，因此需要使用几个副本来获得高最后，分布式一致性算法使用多数派来作决定，因此需要使用几个副本来获得高可用性可用性因此，因此，google的架构师选择了锁服务，而不是一个开发库或者是一致性服务，并的架构师选择了锁服务，而不是一个开发库或者是一致性服务，并且提供小
30、文件存储功能来允许且提供小文件存储功能来允许mater宣告他们自己以及相关参数宣告他们自己以及相关参数chubby锁的特点锁的特点长期锁（长期锁（hoursordays）而不是短期锁（）而不是短期锁（secondsorless）好处：长期锁使得好处：长期锁使得chubbyserver的事务率和的事务率和client的事务率的事务率关系不大，而且可以减少关系不大，而且可以减少server当掉时当掉时client被大量锁定的被大量锁定的风险风险Chubby的系统结构的系统结构典型的场景是典型的场景是5台服台服务器组成一个务器组成一个cell，选择选择mater和数据同和数据同步均采用一致性协步均采
31、用一致性协议议Client applicationChubby libraryClient applicationChubby libraryClient processesRPCs5 server of a chubby cellmasterChubby server放在不同的机架上Chubby锁的形式锁的形式Exportsafilesysteminterface,similartounixDirectorybasedapproach:/ls/foo/wombat/pouchCoarse-grainedlocks,canstoresmallamountofdatainalock5replic
32、as,needamajorityvotetobeactiveGenericoperations:create,read,write,lockCallbacksondatastoredinChubby:File contents changedChild node added, removed, changedLock expired, lock competition, .Chubby master failureChubby的事件的事件filecontentsmodifiedoftenusedtomonitorthelo-cationofaserviceadvertisedviathefil
33、echildnodeadded,removed,ormodifiedusedtoim-plementmirroring.(Inadditiontoallowingnewfilestobediscovered,returningeventsforchildnodesmakesitpossibletomonitorephemeralfileswithoutaffectingtheirreferencecounts.)Chubbymasterfailedoverwarnsclientsthatothereventsmayhavebeenlost,sodatamustberescanned.ahand
34、le(anditslock)hasbecomeinvalidthistypi-callysuggestsacommunicationsproblem.lockacquiredcanbeusedtodeterminewhenapri-maryhasbeenelected.conflictinglockrequestfromanotherclientallowsthecachingoflocks.Caching长期长期caching而不是而不是time-based，由服务器通知客户端，由服务器通知客户端cache无效，客户端自身也有一个租约，修改操作仅在服务无效，客户端自身也有一个租约，修改操作仅
35、在服务期知道所有期知道所有client都将原有的都将原有的cache无效后进行无效后进行Client只有是只有是cache无效的操作，而不是无效的操作，而不是update内容内容虚同步的方法在已经存在多种通信协议的环境中是不合适的虚同步的方法在已经存在多种通信协议的环境中是不合适的SessionandKeepAlivesAclientrequestsanewsessiononfirstcontactingthemasterofaChubbycell.Itendsthesessionexplicitlyeitherwhenitterminates,orifthesessionhasbeenidl
36、e(withnoopenhandlesandnocallsforaminute)每个每个session还有一个关联的还有一个关联的leasetimer，leasetimer本质上是一个本质上是一个Qos承诺承诺（保证（保证chubby锁服务提供响应的最大等待时间），可用于服务器负载平衡（流锁服务提供响应的最大等待时间），可用于服务器负载平衡（流量控制）量控制）Client端的端的leasetimertimeout之后，进入所谓危险期（此时没有断开之后，进入所谓危险期（此时没有断开session），而是进入所谓），而是进入所谓graceperiod（45sbydefault），如果在），如果在g
37、raceperoid能够重新连接上服务器，就继续会话的操作，否则向上层应用返回错误能够重新连接上服务器，就继续会话的操作，否则向上层应用返回错误原则：尽量不原则：尽量不restart，如果断开之后重新连接之后所有原操作均不能执行，如果断开之后重新连接之后所有原操作均不能执行Fail-over过程过程除了延迟，上层应用感觉不到除了延迟，上层应用感觉不到master的变化的变化清除cache，启动grace perios timerChubby的数据库的数据库第一个版本用第一个版本用BerkeleyDB，后来嫌，后来嫌Berkeley的开发人员对的开发人员对分布式复制部分功能的代码更新不够快，自己
38、做了一个类似分布式复制部分功能的代码更新不够快，自己做了一个类似Birrell的简单的的简单的database，实现了原子操作，取消了事务操，实现了原子操作，取消了事务操作作备份备份每几个小时，每个每几个小时，每个chubbycell的的master就写一个自己数据就写一个自己数据库的库的snapshot到另一栋建筑的另一个到另一栋建筑的另一个GFSfileserver中，防中，防止循环依赖止循环依赖滥用的客户端滥用的客户端缺少更激进的缺少更激进的caching，很多程序员喜欢写个循环不停地去，很多程序员喜欢写个循环不停地去retry一个不一个不存在的文件，因此需要惩罚过多使用存在的文件，因此
39、需要惩罚过多使用open()的应用，另外，采用的应用，另外，采用negativecaching（BSD的虚拟文件系统）的方法来解决的虚拟文件系统）的方法来解决缺少缺少quotas，导入一个，导入一个256kBytes的的chubby文件大小限制文件大小限制把把chubby当当Publish/subscribe来用是划不来的，主要是因为来用是划不来的，主要是因为chubby非非常重视对数据的无效操作而不是数据更新操作常重视对数据的无效操作而不是数据更新操作教训教训开发者是很少考虑可用性的开发者是很少考虑可用性的细纹理的锁是不需要的细纹理的锁是不需要的不用不用TCP，而用，而用UDP作为作为RPC
40、s的网络层通信协议（主要是的网络层通信协议（主要是TCP本身的拥塞控制及回退机制让本身的拥塞控制及回退机制让google无法精确控制各种无法精确控制各种timer）BigTableAdistributedstoragesystemformanagingstructureddatathatisdesignedtoscaletoaverylargesize:petabytesofdataacrossthousandsofcommodityservers.BuiltontopofGFS.Usedbymorethan60GoogleproductsandprojectsincludingGoogleE
41、arth,GoogleFinance,Orkut,BigTable:AnExampleforcrawldataAwebcrawlingsystemmightuseBigTablethatstoreswebpages.EachrowkeycouldrepresentaspecificURL,withcolumnsforthepagecontents,thelanguage,thereferencestothatpage,orothermetadata.Therowrangeforatableisdynamicallypartitionedbetweenservers.Rowsarecluster
42、edtogetheronmachinesbykey,sousingURLsaskeyswouldminimizethenumberofmachineswherepagesfromasingledomainarestored.Eachcellistimestampedsotherecouldbemultipleversionsofthesamedatainthetable.Datamodel:abigmap triple for key - lookup, insert, and delete APIArbitrary “columns” on a row-by-row basisColumn
43、family:qualifier. Family is heavyweight, qualifier lightweightColumn-oriented physical store- rows are sparse!Does not support a relational modelNo table-wide integrity constraintsNo multirow transactionsSSTableImmutable,sortedfileofkey-valuepairsChunksofdataplusanindexIndex is of block ranges, not
44、valuesIndex64K block64K block64K blockSSTableTabletContainssomerangeofrowsofthetableBuiltoutofmultipleSSTablesIndex64K block64K block64K blockSSTableIndex64K block64K block64K blockSSTableTabletStart:aardvarkEnd:appleTableMultipletabletsmakeupthetableSSTablescanbesharedTabletsdonotoverlap,SSTablesca
45、noverlapSSTableSSTableSSTableSSTableTabletaardvarkappleTabletapple_two_EboatFindingatabletServersTabletserversmanagetablets,multipletabletsperserver.Eachtabletis100-200megsEach tablet lives at only one serverTablet server splits tablets that get too bigMasterresponsibleforloadbalancingandfaulttolera
46、nceUse Chubby to monitor health of tablet servers, restart failed serversGFS replicates data. Prefer to start tablet server on same machine that the data is already atTablet的操作的操作EditingatableMutationsarelogged,thenappliedtoanin-memoryversionLogfilestoredinGFSSSTableSSTableTabletapple_two_EboatInser
47、tInsertDeleteInsertDeleteInsertMemtableCompactionsMinorcompactionconvertthememtableintoanSSTableReduce memory usage Reduce log traffic on restartMergingcompactionReduce number of SSTablesGood place to apply policy “keep only N versions”MajorcompactionMerging compaction that results in only one SSTab
48、leNo deletion records, only live data性能优化方法：性能优化方法：LocalityGroupsGroupcolumnfamiliestogetherintoanSSTableAvoid mingling data, ie page contents and page metadataCan keep some groups all in memoryCancompresslocalitygroupsBloomFiltersonlocalitygroupsavoidsearchingSSTable其它方面的优化其它方面的优化两阶段压缩模式两阶段压缩模式两层次的
49、两层次的Caching布隆过滤器布隆过滤器单一的单一的commit-log文件文件加速加速Tablet的移动的移动使用不可变的数据使用不可变的数据MicrobenchmarksApplicationatGoogle小结：小结：bigtable的成功之处的成功之处最成功之处，对很多技术的选择、取舍都恰到好处最成功之处，对很多技术的选择、取舍都恰到好处Workqueue:SchedulingmanyjobsonmanymachinesAlargescaletimesharingsystembuiltoutofanarrayofcomputersandtheirram,cpusanddisks.Sc
50、hedulesjobs,allocatesresources,reportsstatus,andcollectstheresults.Similartootherdistributedsystemsdescribedintheliterature,suchasCondor.ThesamemachinesthatserveaschunkserversforaGFScellcanalsocontributeCPUandmemoryresourcestoaworkqueuebecausethecomputationalrequirementsofaGFSstoragecellarenegligibl
51、e.SoamachineAmaycontributetostoragecluster(GFScell)Bandalsotocomputecluster(workqueue)C-thecomputeandstoragecellscan(andwill)overlap.Workqueue:SchedulingmanyjobsonmanymachinesGFS MasterGFSChunkserverJob 0task1 en i hcaMWorkqueueslaveWorkqueuemasterBigmemory job taskGFSChunkserverJob 2taskWorkqueuesl
52、aveBigmemory job taskN en i hcaMMapReduce引言引言MapReduce中最重要的两个词就是中最重要的两个词就是Map（映射）和（映射）和Reduce（规约）。初看（规约）。初看Map/Reduce这两个词，熟悉这两个词，熟悉FunctionLanguage的人一定感觉很熟悉。的人一定感觉很熟悉。FP把把这样的函数称为这样的函数称为”higherorderfunction”（”Highorderfunction”被成为被成为FunctionProgramming的利器之一哦），也就是说，这些函数是编写来被与其的利器之一哦），也就是说，这些函数是编写来被与其它
53、函数相结合（或者说被其它函数调用的）。如果说硬要比的化，可以把它想象它函数相结合（或者说被其它函数调用的）。如果说硬要比的化，可以把它想象成成C里面的里面的CallBack函数，或者函数，或者STL里面的里面的Functor。比如你要对一个。比如你要对一个STL的容的容器进行查找，需要制定每两个元素相比较的器进行查找，需要制定每两个元素相比较的Functor（Comparator），这个），这个Comparator在遍历容器的时候就会被调用。在遍历容器的时候就会被调用。MapReduce引言（二）引言（二）对图像处理程序来说，其实大多数的图像处理操作都是对图像矩阵进行对图像处理程序来说，其实大
54、多数的图像处理操作都是对图像矩阵进行某种运算。这里的运算通常有两种，一种是映射，一种是规约。拿两种某种运算。这里的运算通常有两种，一种是映射，一种是规约。拿两种效果来说，效果来说，”老照片老照片”效果通常是强化照片的效果通常是强化照片的G/B值，然后对每个象素加值，然后对每个象素加一些随机的偏移，这些操作在二维矩阵上的每一个元素都是独立的，是一些随机的偏移，这些操作在二维矩阵上的每一个元素都是独立的，是Map操作。而操作。而”雕刻雕刻”效果需要提取图像边缘，就需要元素之间的运算效果需要提取图像边缘，就需要元素之间的运算了，是一种了，是一种Reduce操作。再举个简单的例子，一个一维矩阵（数组）
55、操作。再举个简单的例子，一个一维矩阵（数组）0,1,2,3,4可以映射为可以映射为0,2,3,6,8（乘（乘2），也可以映射为），也可以映射为1,2,3,4,5（加（加1）。它可以规约为）。它可以规约为0（元素求积）也可以规约为（元素求积）也可以规约为10（元（元素求和）。素求和）。MapReduce引言（三）引言（三）面对复杂问题，古人教导我们要面对复杂问题，古人教导我们要“分而而治之之”，英文中对应的词是，英文中对应的词是”DivideandConquer“。Map/Reduce其实就是其实就是Divide/Conquer的过程，通过把问题的过程，通过把问题Divide，使这些，使这些Di
56、vide后的后的Map运算高度并行，再将运算高度并行，再将Map后的结果后的结果Reduce（根据某一（根据某一个个Key），得到最终的结果。），得到最终的结果。Googler发现这是问题的核心，其它都是共性问题。因此，他们把发现这是问题的核心，其它都是共性问题。因此，他们把MapReduce抽象分离出来。这样，抽象分离出来。这样，Google的程序员可以只关心应用逻辑，关心根据哪些的程序员可以只关心应用逻辑，关心根据哪些Key把问题进行分解，哪些操作是把问题进行分解，哪些操作是Map操作，哪些操作是操作，哪些操作是Reduce操作。其它并行计操作。其它并行计算中的复杂问题诸如分布、工作调度、
57、容错、机器间通信都交给算中的复杂问题诸如分布、工作调度、容错、机器间通信都交给Map/ReduceFramework去做，很大程度上简化了整个编程模型。去做，很大程度上简化了整个编程模型。MapReduce引言（四）引言（四）MapReduce的另一个特点是，的另一个特点是，Map和和Reduce的的输入和输出都是中间临时文件（MapReduce利用利用Google文件系统文件系统GFS来来管理和访问这些文件），而不是不同进程间或者不同机器间管理和访问这些文件），而不是不同进程间或者不同机器间的其它通信方式。这是的其它通信方式。这是Google一贯的风格，化繁为简，返璞一贯的风格，化繁为简，返
58、璞归真。归真。MapReduce引言（五）引言（五）Map的定义：的定义： Map, written by the user, takes an input pair and produces a set of intermediate key/value pairs. The MapReduce library groups together all intermediate values associated with the same intermediate key I and passes them to the Reduce function.Reduce的定义：的定义： The
59、Reduce function, also written by the user, accepts an intermediate key I and a set of values for that key. It merges together these values to form a possibly smaller set of values. Typically just zero or one output value is produced per Reduce invocation. The intermediate values are supplied to the
60、users reduce function via an iterator. This allows us to handle lists of values that are too large to fit in memory.MapReduceAprogrammingmodelandanassociatedimplementationforprocessingandgeneratinglargedatasets.Auserspecifiedmapfunctionprocessesakey/valuepairtogenerateasetofintermediatekey/valuepair
61、s.Auserspecifiedreducefunctionmergesallintermediatevaluesassociatedwiththesameintermediatekey.Programswritteninthisfunctionalstyleareautomaticallyparallelizedandexecutedonalargeclusterofcommoditymachines.MapReduce:RuntimeEnvironmentTheMapReduceruntimeenvironmenttakescareof:Partitioning the input dat
62、a.Scheduling the programs execution across a set of machines.Handling machine failures.Managing required inter-machine communication.Allowsprogrammerswithoutanyexperiencewithparallelanddistributedsystemstoeasilyutilizetheresourcesofalargedistributedcluster.AllattheapplicationlevelbuiltontopofLinux.M
63、apReduce:GrepforSysadminsSupposewewantedadistributedgrepoveralargedataset.cat file | grep “ip address” matches.txtOurinputisreallylarge,sowellneedtoreaditfromadistributedfilesystemanyway.AdistributedgrepwithMapReducewould:Split up the file into individual chunks.Send each small chunk to a different
64、machine.Have each of the machines run the same mapper on their data chunk (grep “ip address” in this case)Collate the matches from the individual worker machines into an output file (the reducer, in this example the Identity function). SystemOptimizationspossible:Data localityNetwork topology optimi
65、zations (rack diversity, etc.)MapReduce:SystemStructureMapReduce:一个例子一个例子例子：在一个文档集合中统计每个单词出现的次数例子：在一个文档集合中统计每个单词出现的次数Map操作的输入是每一篇文档，将输入文档中每一个单词的出现输出到中间文件中去。操作的输入是每一篇文档，将输入文档中每一个单词的出现输出到中间文件中去。map(Stringkey,Stringvalue):/key:documentname/value:documentcontentsforeachwordwinvalue:EmitIntermediate(w,“1
66、);比如我们有两篇文档，内容分别是比如我们有两篇文档，内容分别是A“Iloveprogramming”B“Iamablogger,youarealsoablogger”。B文档经过文档经过Map运算后输出的中间文件将会是：运算后输出的中间文件将会是：I,1am,1a,1blogger,1you,1are,1a,1blogger,1MapReduce:一个例子（二）一个例子（二）Reduce操作的输入是单词和出现次数的序列。用上面的例子来说，就是操作的输入是单词和出现次数的序列。用上面的例子来说，就是(”I”,1,1),(”love”,1),(”programming”,1),(”am”,1),
67、(”a”,1,1)等。然后根据每个单词，算出总的出现次数。等。然后根据每个单词，算出总的出现次数。reduce(Stringkey,Iteratorvalues):/key:aword/values:alistofcountsintresult=0;foreachvinvalues:result+=ParseInt(v);Emit(AsString(result);最后输出的最终结果就会是：最后输出的最终结果就会是：(”I”,2),(”a”,2)MapReduce:一个例子（三）一个例子（三）实际的执行顺序是：实际的执行顺序是：MapReduceLibrary将将Input分成分成M份。这里的
68、份。这里的InputSplitter也可以是多台机器也可以是多台机器并行Split。Master将将M份份Job分给分给Idle状态的状态的M个个worker来处理；来处理；对于输入中的每一个对于输入中的每一个pair进行进行Map操作，将中间结果操作，将中间结果Buffer在在Memory里；里；定期的（或者根据内存状态），将定期的（或者根据内存状态），将Buffer中的中间信息中的中间信息Dump到到本地磁盘上，并且把文件信息传回给磁盘上，并且把文件信息传回给Master（Master需要把这些信息发送给需要把这些信息发送给Reduceworker）。这里最重要的一点是，）。这里最重要的一
69、点是，在写磁盘的时候，需要将中间文件做Partition（比如R个）。拿上面的例子来举例，如果把所有的信息存到一个文件，。拿上面的例子来举例，如果把所有的信息存到一个文件，Reduceworker又会变成瓶颈。我们只需要保证又会变成瓶颈。我们只需要保证相同Key能出现在同一个Partition里面就可以把这个问题分解。里面就可以把这个问题分解。R个个Reduceworker开始工作，从不同的开始工作，从不同的Mapworker的的Partition那里拿到数据（那里拿到数据（read the buffered data from the local disks of the map worke
70、rs），用），用key进行排序（如果内存中放不下需要用到外部排序进行排序（如果内存中放不下需要用到外部排序-externalsort）。很显然，排）。很显然，排序（或者说序（或者说Group）是）是Reduce函数之前必须做的一步。函数之前必须做的一步。这里面很关键的是，每个这里面很关键的是，每个Reduceworker会去从很多会去从很多Mapworker那里拿到那里拿到X(0XR)Partition的中间结果，这样，所有属于这个的中间结果，这样，所有属于这个Key的信息已经都在这个的信息已经都在这个worker上了。上了。Reduceworker遍历中间数据，对每一个唯一遍历中间数据，对每
71、一个唯一Key，执行，执行Reduce函数（参数是这个函数（参数是这个key以及相对应的一系列以及相对应的一系列Value）。）。执行完毕后，唤醒用户程序，返回结果（最后应该有执行完毕后，唤醒用户程序，返回结果（最后应该有R份份Output，每个，每个ReduceWorker一个）。一个）。MapReduce:一个例子（四）一个例子（四）可见，这里的分（可见，这里的分（Divide）体现在两步，分别是将输入分成）体现在两步，分别是将输入分成M份，以及将份，以及将Map的中间结果分成的中间结果分成R份。将输入分开通常很简单，份。将输入分开通常很简单，Map的中间结果通常的中间结果通常用用”has
72、h(key)modR”这个结果作为标准，保证相同的这个结果作为标准，保证相同的Key出现在同一出现在同一个个Partition里面。当然，使用者也可以指定自己的里面。当然，使用者也可以指定自己的PartitionFunction，比如，对于比如，对于UrlKey，如果希望同一个，如果希望同一个Host的的URL出现在同一个出现在同一个Partition，可以用，可以用”hash(Hostname(urlkey)modR”作为作为PartitionFunction。MapReduce:一个例子（五）一个例子（五）对于上面的例子来说，每个文档中都可能会出现成千上万的对于上面的例子来说，每个文档中都
73、可能会出现成千上万的(”the”,1)这样的中间结果，琐碎的中间文件必然导致传这样的中间结果，琐碎的中间文件必然导致传输上的损失。因此，输上的损失。因此，MapReduce还支持用户提供还支持用户提供CombinerFunction。这个函数通常与。这个函数通常与ReduceFunction有相同的实现，有相同的实现，不同点在于不同点在于Reduce函数的输出是最终结果，而函数的输出是最终结果，而Combiner函函数的输出是数的输出是Reduce函数的某一个输入的中间文件。函数的某一个输入的中间文件。海量数据分析：Sawzall并行处理超大的数据集往往会采用一种平面的正则结构，存放于跨越多个
74、计算机的多个磁盘上。这方面的例子包超大的数据集往往会采用一种平面的正则结构，存放于跨越多个计算机的多个磁盘上。这方面的例子包括了电话通话记录，网络日志，括了电话通话记录，网络日志，web文档库等等。文档库等等。只要这些超大数据集不能装在单个关系数据库里边的时候，传统的数据库技术对于研究这些超大数据集只要这些超大数据集不能装在单个关系数据库里边的时候，传统的数据库技术对于研究这些超大数据集来说那就是没有意义的。来说那就是没有意义的。此外，对于这些数据集的分析可以展示成为应用简单的，便于分布式处理的计算方法：比如过滤，聚合，此外，对于这些数据集的分析可以展示成为应用简单的，便于分布式处理的计算方法
75、：比如过滤，聚合，统计抽取，等等。统计抽取，等等。Sawzall是一种自动化分析系统。在过滤阶段，查询请求通过一种全新的编程语言来快速执行，把数据是一种自动化分析系统。在过滤阶段，查询请求通过一种全新的编程语言来快速执行，把数据处理到聚合阶段。无论过滤阶段还是聚合阶段都是分布在上百台甚至上千台计算机上执行的。他们的结处理到聚合阶段。无论过滤阶段还是聚合阶段都是分布在上百台甚至上千台计算机上执行的。他们的结果通过比较并且保存到一个文件。果通过比较并且保存到一个文件。系统的设计系统的设计-包括分成两阶段，以及这种新式的编程语言，聚合器的特性包括分成两阶段，以及这种新式的编程语言，聚合器的特性-都是
76、在数据和计算分布在很多都是在数据和计算分布在很多台机器上的情况下，内嵌使用并行机制的。台机器上的情况下，内嵌使用并行机制的。超大数据集超大数据集平面正则结构平面正则结构跨越多磁盘组及物理机跨越多磁盘组及物理机瓶颈在瓶颈在I/O,而不在而不在CPUs任务拆分及分发任务拆分及分发对数据就近处理对数据就近处理高容错设计高容错设计背景知识背景知识Sawzall总体数据流图总体数据流图SawzallMapReduceWorkqueueGoogle File SystemScheduling softwareSoftware librariesHigh level languageApplication
77、file systemSawzall在在google帝国大厦的位置帝国大厦的位置count:table sum of int;total:table sum of float;sum_of_squares: table sum of float;x:float=input;emitcount1;emittotalx;emitsum_of_squares- x*x;proto “document.proto”max_pagerank_uri:table maximun(1)domain:string of url:stringweight pagerank:int;doc: Document =
78、 input;url:string = doc.url;emit max_pagerank_urldomain(url)- urlweight doc.pagerank;Sawzall程序例子程序例子SimilartoCandPascalType-safescriptinglanguageCodeismuchshorterthanC+Purevaluesemantics,noreferencetypesStaticallytypedNoexceptionprocessingSawzall语言的特点语言的特点SawzallPythonRubyPerlMandelbrotruntimeFactor
79、12.09s1.0045.42s3.7573.59s6.0938.68s3.20FibonacciruntimeFactor11.73s1.0038.12s3.2447.18s4.0275.73s6.46Sawzall的性能的性能ThousandsofmachinesarepowerfulinparallelClusterandlarge-scaledistributedsystemDemo6PLANETLAB某些观点某些观点Sawzall的聚合器的聚合器搜集器搜集器c:tablecollectionofstring;一个简单的输出结果列表，这个结果在列表中是任意顺序的。一个简单的输出结果列表
80、，这个结果在列表中是任意顺序的。采样器采样器s:tablesample(100)ofstring类似搜集器，但是存的是无偏差的输出结构的采样值。这个采样的大小是用参数体现的。类似搜集器，但是存的是无偏差的输出结构的采样值。这个采样的大小是用参数体现的。累加器累加器s:tablesumof(count:int,revenue:float);所有输出结果的合计。这个输出结果必须是算数的或者可以以算术为基础的（也就是可累加的）所有输出结果的合计。这个输出结果必须是算数的或者可以以算术为基础的（也就是可累加的）最大值最大值m:tablemaximum(10)ofstringweightlength:i
81、nt;取得最大权重的值。每一个值都有一个权重，并且最终选择的值是根据最大权重来选择的。这个参数（例子中是取得最大权重的值。每一个值都有一个权重，并且最终选择的值是根据最大权重来选择的。这个参数（例子中是10）规定）规定了需要保留的最终输出的值数量。权重是以明确的了需要保留的最终输出的值数量。权重是以明确的keyword来描述的，并且它的类型（这里是来描述的，并且它的类型（这里是int）是在这里定义的，它）是在这里定义的，它的值是的值是emit语句给出的。对上边例子来说，语句给出的。对上边例子来说，emit语句如下：语句如下：emitm-sweightlen(s);这样将会在结果中放置最长的字符
82、串。这样将会在结果中放置最长的字符串。分位数分位数q:tablequantile(101)ofresponse_in_ms:int;是用输出的值来构造一个每个概率增量分位数的累计概率分布（算法是一个是用输出的值来构造一个每个概率增量分位数的累计概率分布（算法是一个Greenwald和和Khanna的分布式算法的分布式算法10）。这个例子可以用来查看系统的响应变化的分布情况。通过参数）。这个例子可以用来查看系统的响应变化的分布情况。通过参数101，这个参数用来计算百分点。第，这个参数用来计算百分点。第50个元个元素是中间点的响应时间，第素是中间点的响应时间，第99个元素是个元素是99%的响应时间
83、都小于等于第的响应时间都小于等于第99个元素。个元素。最常见最常见c:tabletop(10)oflanguage:string;toptable评估这个值是否最常见（与之对应的，评估这个值是否最常见（与之对应的，maximuntable找到最高权重的值，而不是最常见的值）找到最高权重的值，而不是最常见的值）例如：例如：emitt-language_of_document(input);将会从文档库中建立将会从文档库中建立10个最常见的语言。对于很大的数据集来说，它可能需要花费过大的代价来找到精确的出席频率个最常见的语言。对于很大的数据集来说，它可能需要花费过大的代价来找到精确的出席频率的的o
84、rder，但是可以有很有效的评估算法。，但是可以有很有效的评估算法。toptable是用了是用了Charikar,Chen,Farach-Colton的分布式算法。算法返回的分布式算法。算法返回的最常见的频率是极为接近真实的出现频率。因为它的交换性和结合性也不是完全精确的：改变处理的输入记录先的最常见的频率是极为接近真实的出现频率。因为它的交换性和结合性也不是完全精确的：改变处理的输入记录先后顺序确实会影响到最终的结果。作为弥补措施，在统计元素个数之外，也要统计这些个数的误差。如果这个误差后顺序确实会影响到最终的结果。作为弥补措施，在统计元素个数之外，也要统计这些个数的误差。如果这个误差和元素
85、个数相比比较小，那么结果的正确度就比较高，如果错误相对来说比较大，那么结果就比较差。对于分布不和元素个数相比比较小，那么结果的正确度就比较高，如果错误相对来说比较大，那么结果就比较差。对于分布不均匀的大型数据集来说，均匀的大型数据集来说，toptable工作的很好。但是在少数情况下比如分布均匀的情况下，可能会导致工作的不是工作的很好。但是在少数情况下比如分布均匀的情况下，可能会导致工作的不是很成功。很成功。Sawzall的聚合器（二）的聚合器（二）Sawzall的聚合器（三）的聚合器（三）取唯一取唯一u:tableunique(10000)ofstring;uniquetable是比较特别的。
86、它报告的是提交给他的唯一数据项的估计大小。是比较特别的。它报告的是提交给他的唯一数据项的估计大小。sumtable可以用来计算数可以用来计算数据项的总和个数，但是一个据项的总和个数，但是一个uniquetable会忽略掉重复部分；最终计算输入值集合得大小。会忽略掉重复部分；最终计算输入值集合得大小。uniquetable同样特别无论输入的值是什么类型，它的输出总是一个同样特别无论输入的值是什么类型，它的输出总是一个count。这个参数是给出了内部使用的。这个参数是给出了内部使用的table大小，这个是用来内部作评估是用的内部表；大小，这个是用来内部作评估是用的内部表；10000的参数值会让最终
87、结果有的参数值会让最终结果有95%的概率正负的概率正负2%的误差的误差得到正确的结果（对于得到正确的结果（对于N，标准偏差是大概，标准偏差是大概N*参数参数*(-1/2)）带索引的聚合器聚合器可以是带索引的，这个可以使得每一个索引下标的值都有一个单独的聚合器。这个聚合器可以是带索引的，这个可以使得每一个索引下标的值都有一个单独的聚合器。这个index可以是可以是任意的任意的Sawzall类型，并且可以是一个聚合器的多维的结构下标。类型，并且可以是一个聚合器的多维的结构下标。例如，如果我们检查例如，如果我们检查web服务器的服务器的log，table：tabletop(1000)country:
88、stringhour:intofrequest:string;可以用来找到每一个国家每一个小时的最常用的请求字串。可以用来找到每一个国家每一个小时的最常用的请求字串。例子：例子：proto“querylog.proto”queries_per_degree:tablesumlat:intlon:intofint;log_record:QueryLogProto=input;loc:Location=locationinfo(log_record.ip);emitqueries_per_degreeeint(loc.lat)int(loc.lon)-1;执行结果执行结果为什么需要设计一个新语言？
89、1.为什么需要在为什么需要在MapReduce之上增加一个新语言？之上增加一个新语言？2.MapReduce已经很高效了，还少什么吗？已经很高效了，还少什么吗？3.为什么需要一个全新的语言？为什么不在为什么需要一个全新的语言？为什么不在MapReduce之上使用现成之上使用现成的语言比如的语言比如Python？设计一个新语言的理由1.为某一个问题领域构造特定的符号描述有助于程序清晰化，并且更紧凑，更有效率。为某一个问题领域构造特定的符号描述有助于程序清晰化，并且更紧凑，更有效率。2.在语言内嵌聚合器（包括在运行时刻内嵌聚合器）意味着程序员可以不用自己实现一个，在语言内嵌聚合器（包括在运行时刻内
90、嵌聚合器）意味着程序员可以不用自己实现一个，这点不像使用这点不像使用MapReduce需要自己实现。需要自己实现。3.同样的，它也更符合大规模并发处理超大数据集时候的处理思路，并且根据这个处理思路同样的，它也更符合大规模并发处理超大数据集时候的处理思路，并且根据这个处理思路写出一流的程序。写出一流的程序。4.同样的，对协议栈同样的，对协议栈buffer的支持，并且提供了平台相关的类型支持，在较低层面上简化了的支持，并且提供了平台相关的类型支持，在较低层面上简化了程序开发。总的来说，程序开发。总的来说，Sawzall程序要比基于程序要比基于MapReduce的的C+小上小上1020倍，并且更容倍
91、，并且更容易书写。易书写。5.定制语言还有其他优势包括了增加平台相关的特性，定制的调试和模型界面，等等。定制语言还有其他优势包括了增加平台相关的特性，定制的调试和模型界面，等等。Sawzall的效果的效果Sawzall采用的模式已经被证明非常有效。虽然对于少数问采用的模式已经被证明非常有效。虽然对于少数问题来说，这样的模式还不能有效处理，但是大部分海量数据题来说，这样的模式还不能有效处理，但是大部分海量数据的处理来说都已经很适用了，并且可以简单用程序实现，这的处理来说都已经很适用了，并且可以简单用程序实现，这就使得就使得Sawzall成为成为google中很受欢迎的语言中很受欢迎的语言GAEG
92、oogleApplicationEngineGAE数据存储数据存储API用一种别具特色的机制定义数据模型。一个模型描述了一种实体：用一种别具特色的机制定义数据模型。一个模型描述了一种实体：entity，包括多个，包括多个属性的类型和配置。应用程序利用属性的类型和配置。应用程序利用python类来定义模型，类的类来定义模型，类的attributes描述属性。一种类型的描述属性。一种类型的entity对应了一个模型类的对象实例。实例的对应了一个模型类的对象实例。实例的pythonattributes则对应了属性值。一个则对应了属性值。一个entity可以用类的构造可以用类的构造函数创建，并通过调用
93、函数创建，并通过调用put()方法之后保存到服务器。方法之后保存到服务器。GAE数据存储并不是关系数据库。在提供与传统数据库的相似介面的同时，利用它本身具备了可伸缩性数据存储并不是关系数据库。在提供与传统数据库的相似介面的同时，利用它本身具备了可伸缩性的能力，提供了另外的方法来管理和设计数据库。的能力，提供了另外的方法来管理和设计数据库。GAE的的Query查询接口查询接口TheQueryInterfaceModel或者或者Expando的的all()方法返回查询对象，对应这种表类所有的方法返回查询对象，对应这种表类所有的entity。应用程序通。应用程序通过过Filter()、Order()
94、、ancesitor()来准备查询。来准备查询。classStory(db.Model):title=db.StringProperty()date=db.DateTimeProperty()query=Story.all()query.filter(title=,Foo)query.order(-date)query.ancestor(key)#Thesemethodscanbechainedtogetherononeline.query.filter(title=,Foo).order(-date).ancestor(key)GAE的的GqlQuery查询接口查询接口GqlQuery类构造
95、函数的参数包括查询语句和可选的参数。语句包括数据的种类，条件过滤，排序还有类构造函数的参数包括查询语句和可选的参数。语句包括数据的种类，条件过滤，排序还有祖先条件。还可以包括对结果集的限制以及偏移。祖先条件。还可以包括对结果集的限制以及偏移。#Parameterscanbeboundwithpositionalarguments.query=db.GqlQuery(SELECT*FROMStoryWHEREtitle=:1ANDANCESTORIS:2ORDERBYdateDESC,Foo,key)#Or,parameterscanbeboundwithkeywordarguments.que
96、ry=db.GqlQuery(SELECT*FROMStoryWHEREtitle=:titleANDANCESTORIS:parentORDERBYdateDESC,title=Foo,parent=key)#String,numberandBooleanvaluescanbeliteralvaluesinthestring.query=db.GqlQuery(SELECT*FROMStoryWHEREtitle=FooANDANCESTORIS:parentORDERBYdateDESC,parent=key)开源方面的开源方面的Hadoop Lucene之父Doug Cutting的又一
97、力作，在Hadoop中实现了Google的GFS和MapReduce算法，使Hadoop成为了一个分布式的计算平台Yahoo的的Pig猪猪Yahoo猪年行大礼，在五一期间放出了：猪年行大礼，在五一期间放出了：PIG猪猪。YahooPig是一个运行在是一个运行在Hadoop（DougCutting在在06年年3月份加入了月份加入了Yahoo）上的并行处理架构，有了）上的并行处理架构，有了Pig使使得普通的程序员具有了分析处理得普通的程序员具有了分析处理gigantic数据集的能力数据集的能力YahooPig有如下特点：有如下特点：1、专注于于大量数据集分析；、专注于于大量数据集分析；2、运行在集
98、群的计算架构上，、运行在集群的计算架构上，YahooPig提供了多层抽象，简化并行计算让普通用户提供了多层抽象，简化并行计算让普通用户使用；这些抽象完成自动把用户请求使用；这些抽象完成自动把用户请求queries翻译成有效的并行评估计划，然后在物理集翻译成有效的并行评估计划，然后在物理集群上执行这些计划；群上执行这些计划；3、提供类似、提供类似SQL的操作语法；的操作语法；4、开放源代码；、开放源代码；Pig代码的例子代码的例子a=COGROUPQueryResultsBYurl,PagesBYurl;b=FOREACHaGENERATEFLATTEN(QueryResults.(query,
99、position),FLATTEN(Pages.pagerank);c=GROUPbBYquery;d=FILTERcBYcheckTop5(*);微软的微软的Dryad微软的微软的Dryad集成集成Linq(随着随着.net2.0正式发布正式发布)，新的名，新的名称是：称是：DryadLINQ判断网页的重要性判断网页的重要性Pagerank算法简介及正确性算法简介及正确性浅析浅析PR(A)=(1-d)+d(PR(T1)/C(T1)+.+PR(Tn)/C(Tn)其中：其中：PR(A):页面页面A的网页级别的网页级别,PR(Ti)：页面：页面Ti的网页级别，页面的网页级别，页面Ti链向页面链向页
100、面A，C(Ti)：页面：页面Ti链出的链接数量，链出的链接数量，d：阻尼系数，取值在：阻尼系数，取值在01之间之间.特点：特点：1）这个算法不以站点排序，页面网页级别由一个个独立的页面决定；）这个算法不以站点排序，页面网页级别由一个个独立的页面决定；2）页面的网页级别由链向它的页面的网页级别决定，但每个链入页面的贡献）页面的网页级别由链向它的页面的网页级别决定，但每个链入页面的贡献的值是不同的。如果的值是不同的。如果Ti页面中链出越多，它对当前页面页面中链出越多，它对当前页面A的贡献就越小。的贡献就越小。A的的链入页面越多，其网页级别也越高；链入页面越多，其网页级别也越高；3）阻尼系数的使用，
101、减少了其它页面对）阻尼系数的使用，减少了其它页面对当前页面当前页面A的排序贡献。的排序贡献。所有页面的网页级别之和等于互联网的总页数？所有页面的网页级别之和等于互联网的总页数？1.由方程由方程PR(A)=(1-d)+d(PR(T1)/C(T1)+.+PR(Tn)/C(Tn)定义可知，方程的数量等于定义可知，方程的数量等于页面总数页面总数N，PR(A).PR(N)2.把这把这N个方程相加，左边是个方程相加，左边是PR(A)+.+PR(N)，右边是，右边是(1-d)N+d(PR(Ti)/C(Ti)，3.然后看看然后看看PR(Ti)/C(Ti)每一项的特点，显然每个页面的链出每一项的特点，显然每个页
102、面的链出C(Ti)是固定的，而且页面是固定的，而且页面Ti有有一个链出，就意味着一个链出，就意味着PR(Ti)出现在某个方程的右边一次，因此页面出现在某个方程的右边一次，因此页面Ti有有C(Ti)个链出，个链出，PR(Ti)/C(Ti)中就有中就有C(Ti)个个PR(Ti)/C(Ti)项，加起来刚好就是项，加起来刚好就是PR(Ti)。那么。那么N个方程相加后个方程相加后变成变成PR(A)+.+PR(N)=(1-d)N+d(PR(A)+.+PR(N)），因此，），因此，PR(A)+.+PR(N)=(1-d)N/(1-d)=N，就是说所有页面的网页级别之和等于互联网的总页数。其实这里有一个前提，就
103、是说所有页面的网页级别之和等于互联网的总页数。其实这里有一个前提条件，就是每个页面都必须有出链，如果有页面不具备出链（这样的链接称为悬摆链），条件，就是每个页面都必须有出链，如果有页面不具备出链（这样的链接称为悬摆链），上述结论是不成立的上述结论是不成立的将方程将方程PR(A)=(1-d)+d(PR(T1)/C(T1)+.+PR(Tn)/C(Tn)改写为改写为PR(A)-（d/C(T1)）PR(T1)-.-（d/C(Tn)）PR(Tn)=1-d方程组的左边就是一个矩阵方程组的左边就是一个矩阵1-（d/C(T1)）.-（d/C(Tn)）-（d/C(Ti)）1.1（对角线上为（对角线上为1）对于对
104、于Jacobi迭代，定理：若矩阵迭代，定理：若矩阵A满足下列条件之一，则满足下列条件之一，则Jacobi迭代收敛。迭代收敛。（1）A为行对角占优阵为行对角占优阵（2）A为列对角占优阵为列对角占优阵（3）A满足满足根据前面的分析，矩阵满足第根据前面的分析，矩阵满足第3个条件（计算结果个条件（计算结果=d1）因此，对于任意初值均收敛于方程组的唯一解。（对于互联网上的情况，这个方程组非常庞大，而且采用迭代求解的方法，因此，对于任意初值均收敛于方程组的唯一解。（对于互联网上的情况，这个方程组非常庞大，而且采用迭代求解的方法，这就是这就是google的分布式海量运算的原因）的分布式海量运算的原因）在迭代
105、的过程中，每个网页的网页级别的和是收敛于整个网络的页面数在迭代的过程中，每个网页的网页级别的和是收敛于整个网络的页面数的的？每个页面的平均网页级别是每个页面的平均网页级别是1，实际上的值在（，实际上的值在（1d）和）和(dN+(1-d)之间之间？1.第一个结论很简单，级别之和等于第一个结论很简单，级别之和等于N，平均当然是，平均当然是1了。后了。后面的结论从方程面的结论从方程2.PR(A)=(1-d)+d(PR(T1)/C(T1)+.+PR(Tn)/C(Tn)看看出，这是分别令出，这是分别令PR(T1)/C(T1)+.+PR(Tn)/C(Tn)=0或或N的情况的情况Google的架构是万能的吗？的架构是万能的吗？总结总结Google，一个优秀的大规模分布式海量数据处理平台，一个优秀的大规模分布式海量数据处理平台Google，目前计算机理论成果的集大成者，目前计算机理论成果的集大成者Google，一部计算机系统结构专业的教科书，一部计算机系统结构专业的教科书Google，一种价值观，一种价值观Google，一种企业文化，一种企业文化Google，一种商业模式，一种商业模式未来未来Google，没完没了的话题，没完没了的话题ThanksfornotfallingasleepAnyquestions?
