Google 云计算原理


1 第 2 章 Google 云计算原理 第 1 章 绪论 很少有一种技术能够像“云计算”这样,在短短的两年间就产生巨大的影响力 。 Google、亚马逊、IBM 和微软等 IT 巨头们以前所未有的速度和规模推动云计算技术和产 品的普及,一些学术活动迅速将云计算提上议事日程,支持和反对的声音不绝于耳。那么 , 云计算到底是什么?发展现状如何?它的实现机制是什么?它与网格计算是什么关系?。 本章将分析这些问题,目的是帮助读者对云计算形成一个初步认识。 1.1 云计算的概念 云计算(Cloud Computing)是在 2007 年第 3 季度才诞生的新名词,但仅仅过了半年 多,其受到关注的程度就超过了网格计算(Grid Computing),如图 1-1 所示。 EMBED Word.Picture.8 云计算 网格计算 搜索量指数 Google Tronds 图 1-1 云计算和网格计算在 Google 中的搜索趋势 然而,对于到底什么是云计算,至少可以找到 100 种解释,目前还没有公认的定义。 本书给出一种定义,供读者参考。 云计算是一种商业计算模型,它将计算任务分布在大量计算机构成的资源池上,使用 户能够按需获取计算力、存储空间和信息服务。 这种资源池称为“云”。“云”是一些可以自我维护和管理的虚拟计算资源,通常是一些 大型服务器集群,包括计算服务器、存储服务器和宽带资源等。云计算将计算资源集中起 来,并通过专门软件实现自动管理,无需人为参与。用户可以动态申请部分资源,支持各 种应用程序的运转,无需为烦琐的细节而烦恼,能够更加专注于自己的业务,有利于提高 效率、降低成本和技术创新。云计算的核心理念是资源池,这与早在 2002 年就提出的网 格计算池(Computing Pool)的概念非常相似[3][4]。网格计算池将计算和存储资源虚拟成为 一个可以任意组合分配的集合,池的规模可以动态扩展,分配给用户的处理能力可以动态 回收重用。这种模式能够大大提高资源的利用率,提升平台的服务质量。 之所以称为“云”,是因为它在某些方面具有现实中云的特征:云一般都较大;云的规 模可以动态伸缩,它的边界是模糊的;云在空中飘忽不定,无法也无需确定它的具体位置 , 2 3 4 云计算 但它确实存在于某处。之所以称为“云”,还因为云计算的鼻祖之一亚马逊公司将大家曾经 称为网格计算的东西,取了一个新名称“弹性计算云”(Elastic Computing Cloud),并取得 了商业上的成功。 有人将这种模式比喻为从单台发电机供电模式转向了电厂集中供电的模式。它意味着 计算能力也可以作为一种商品进行流通,就像煤气、水和电一样,取用方便,费用低廉。 最大的不同在于,它是通过互联网进行传输的。 云计算是并行计算(Parallel Computing)、分布式计算(Distributed Computing)和网 格计算(Grid Computing)的发展,或者说是这些计算科学概念的商业实现。云计算是虚 拟 化 ( Virtualization ) 、 效 用 计 算 ( Utility Computing ) 、 将 基 础 设 施 作 为 服 务 IaaS(Infrastructure as a Service)、将平台作为服务 PaaS(Platform as a Service)和将软件 作为服务 SaaS(Software as a Service)等概念混合演进并跃升的结果。 从研究现状上看,云计算具有以下特点。 1)超大规模。“云”具有相当的规模,Google 云计算已经拥有 100 多万台服务器,亚 马逊、IBM、微软和 Yahoo 等公司的“云”均拥有几十万台服务器。“云”能赋予用户前所未 有的计算能力。 2)虚拟化。云计算支持用户在任意位置、使用各种终端获取服务。所请求的资源来 自“云”,而不是固定的有形的实体。应用在“云”中某处运行,但实际上用户无需了解应用 运行的具体位置,只需要一台笔记本或一个 PDA,就可以通过网络服务来获取各种能力 超强的服务。 3)高可靠性。“云”使用了数据多副本容错、计算节点同构可互换等措施来保障服务 的高可靠性,使用云计算比使用本地计算机更加可靠。 4)通用性。云计算不针对特定的应用,在“云”的支撑下可以构造出千变万化的应用, 同一片“云”可以同时支撑不同的应用运行。 5)高可扩展性。“云”的规模可以动态伸缩,满足应用和用户规模增长的需要。 6)按需服务。“云”是一个庞大的资源池,用户按需购买,像自来水、电和煤气那样 计费。 (7)极其廉价。“云”的特殊容错措施使得可以采用极其廉价的节点来构成云;“云”的 自动化管理使数据中心管理成本大幅降低;“云”的公用性和通用性使资源的利用率大幅提 升;“云”设施可以建在电力资源丰富的地区,从而大幅降低能源成本。因此“云”具有前所 未有的性能价格比。Google 中国区前总裁李开复称,Google 每年投入约 16 亿美元构建云 计算数据中心,所获得的能力相当于使用传统技术投入 640 亿美元,节省了 40 倍的成本。 因此,用户可以充分享受“云”的低成本优势,需要时,花费几百美元、一天时间就能完成 以前需要数万美元、数月时间才能完成的数据处理任务。 云计算按照服务类型大致可以分为三类:将基础设施作为服务 IaaS、将平台作为服务 PaaS 和将软件作为服务 SaaS,如图 1-2 所示。 IaaS 将硬件设备等基础资源封装成服务供用户使用,如亚马逊云计算 AWS(Amazon Web Services)的弹性计算云 EC2 和简单存储服务 S3。在 IaaS 环境中,用户相当于在使用 裸 机 和 磁 盘 , 既 可 以 让 它 运 行 Windows , 也 可 以 让 它 运 行 Linux , 因 而 几 乎 可 3 第 2 章 Google 云计算原理 将软件作为服务 SaaS(Software as a Service) 如:Salesforce online CRM 专 用 通 用 将平台作为服务 PaaS(Platform as a Service) 将基础设施作为服务 IaaS(Infrastructure as a Service) 如:Google App Engine Microsoft Windows Azure 如:Amazon EC2/S3 图 1-2 云计算的服务类型 以做任何想做的事情,但用户必须考虑如何才能让多台机器协同工作起来。AWS 提供了 在节点之间互通消息的接口简单队列服务 SQS(Simple Queue Service)。IaaS 最大的优势 在于它允许用户动态申请或释放节点,按使用量计费。运行 IaaS 的服务器规模达到几十 万台之多,用户因而可以认为能够申请的资源几乎是无限的。同时,IaaS 是由公众共享的 因而具有更高的资源使用效率。 PaaS 对资源的抽象层次更进一步,它提供用户应用程序的运行环境,典型的如 Google App Engine。微软的云计算操作系统 Microsoft Windows Azure 也可大致归入这一类。 PaaS 自身负责资源的动态扩展和容错管理,用户应用程序不必过多考虑节点间的配合问 题。但与此同时,用户的自主权降低,必须使用特定的编程环境并遵照特定的编程模型。 这有点像在高性能集群计算机里进行 MPI 编程,只适用于解决某些特定的计算问题。例 如,Google App Engine 只允许使用 Python 和 Java 语言、基于称为 Django 的 Web 应用框架、 调用 Google App Engine SDK 来开发在线应用服务。 SaaS 的针对性更强,它将某些特定应用软件功能封装成服务,如 Salesforce 公司提供 的在线客户关系管理 CRM(Client Relationship Management)服务。SaaS 既不像 PaaS 一 样提供计算或存储资源类型的服务,也不像 IaaS 一样提供运行用户自定义应用程序的环 境,它只提供某些专门用途的服务供应用调用。 需要指出的是,随着云计算的深化发展,不同云计算解决方案之间相互渗透融合,同 一种产品往往横跨两种以上类型。例如,Amazon Web Services 是以 IaaS 发展的,但新提 供的弹性 MapReduce 服务模仿了 Google 的 MapReduce,简单数据库服务 SimpleDB 模仿 了 Google 的 Bigtable,这两者属于 PaaS 的范畴,而它新提供的电子商务服务 FPS 和 DevPay 以及网站访问统计服务 Alexa Web 服务,则属于 SaaS 的范畴。 1.2 云计算发展现状 由于云计算是多种技术混合演进的结果,其成熟度较高,又有大公司推动,发展极为 迅速。Google、亚马逊、IBM、微软和 Yahoo 等大公司是云计算的先行者。云计算领域的 众多成功公司还包括 VMware、Salesforce、Facebook、YouTube、MySpace 等。 亚 马 逊 研 发 了 弹 性 计 算 云 EC2 ( Elastic Computing Cloud ) 和 简 单 存 储 服 务 4 3 4 云计算 S3(Simple Storage Service)为企业提供计算和存储服务。收费的服务项目包括存储空间、 带宽、CPU 资源以及月租费。月租费与电话月租费类似,存储空间、带宽按容量收费 , CPU 根据运算量时长收费。在诞生不到两年的时间内,亚马逊的注册用户就多达 44 万人, 其中包括为数众多的企业级用户。 Google 是最大的云计算技术的使用者。Google 搜索引擎就建立在分布在 200 多个站 点、超过 100 万台的服务器的支撑之上,而且这些设施的数量正在迅猛增长。Google 的一 系列成功应用平台,包括 Google 地球、地图、Gmail、Docs 等也同样使用了这些基础设施。 采用 Google Docs 之类的应用,用户数据会保存在互联网上的某个位置,可以通过任何一 个与互联网相连的终端十分便利地访问和共享这些数据。目前,Google 已经允许第三方在 Google 的云计算中通过 Google App Engine 运行大型并行应用程序。Google 值得称颂的是 它不保守,它早已以发表学术论文的形式公开其云计算三大法宝:GFS、MapReduce 和 Bigtable,并在美国、中国等高校开设如何进行云计算编程的课程。相应的,模仿者应运 而生,Hadoop 是其中最受关注的开源项目。 IBM 在 2007 年 11 月推出了“改变游戏规则”的“蓝云”计算平台,为客户带来即买即用 的云计算平台。它包括一系列自我管理和自我修复的虚拟化云计算软件,使来自全球的应 用可以访问分布式的大型服务器池,使得数据中心在类似于互联网的环境下运行计算。 IBM 正在与 17 个欧洲组织合作开展名为 RESERVOIR 的云计算项目,以“无障碍的资源和 服务虚拟化”为口号,欧盟提供了 1.7 亿欧元作为部分资金。2008 年 8 月,IBM 宣布将投 资约 4 亿美元用于其设在北卡罗来纳州和日本东京的云计算数据中心改造,并计划 2009 年在 10 个国家投资 3 亿美元建设 13 个云计算中心。 微软紧跟云计算步伐,于 2008 年 10 月推出了 Windows Azure 操作系统。Azure(译为 “蓝天”)是继 Windows 取代 DOS 之后,微软的又一次颠覆性转型——通过在互联网架构 上打造新云计算平台,让 Windows 真正由 PC 延伸到“蓝天”上。Azure 的底层是微软全球基 础服务系统,由遍布全球的第四代数据中心构成。目前,微软已经配置了 220 个集装箱式 数据中心,包括 44 万台服务器。 在我国,云计算发展也非常迅猛。2008 年,IBM 先后在无锡和北京建立了两个云计算 中心;世纪互联推出了 CloudEx 产品线,提供互联网主机服务、在线存储虚拟化服务等; 中国移动研究院已经建立起 1024 个 CPU 的云计算试验中心;解放军理工大学研制了云存 储系统 MassCloud,并以它支撑基于 3G 的大规模视频监控应用和数字地球系统。作为云计 算技术的一个分支,云安全技术通过大量客户端的参与和大量服务器端的统计分析来识别 病毒和木马,取得了巨大成功。瑞星、趋势、卡巴斯基、McAfee、Symantec、江民、 Panda、金山、360 安全卫士等均推出了云安全解决方案。值得一提的是,云安全的核心思 想,与早在 2003 年就提出的反垃圾邮件网格非常接近[5]。2008 年 11 月 25 日,中国电子学 会专门成立了云计算专家委员会。2009 年 5 月 22 日,中国电子学会隆重举办首届中国云 计算大会,1200 多人与会,盛况空前。2009 年 11 月 2 日,中国互联网大会专门召开了 “2009 云计算产业峰会”。2009 年 12 月,中国电子学会举办了中国首届云计算学术会议。 2010 年 5 月,中国电子学会将举办第二届中国云计算大会。 5 第 2 章 Google 云计算原理 1.3 云计算实现机制 由于云计算分为 IaaS、PaaS 和 SaaS 三种类型,不同的厂家又提供了不同的解决方案, 目前还没有一个统一的技术体系结构,对读者了解云计算的原理构成了障碍。为此,本书 综合不同厂家的方案,构造了一个供参考的云计算体系结构。这个体系结构如图 1-3 所示, 它概括了不同解决方案的主要特征,每一种方案或许只实现了其中部分功能,或许也还有 部分相对次要功能尚未概括进来。 管理中间件 资源管理 任务管理 用户管理 负载均衡 故障检测 映像部署和管理 使用计费 用户环境配置 用户交互管理 故障恢复 监视统计 账号管理 安 全 管 理 访问授权 综合防护 安全审计 服务接口 服务注册 服务查找 服务访问 服务工作流 SOA 构建层 计算资源池 资源池 计算机 存储器 数据库 物理资源 存储资源池 网络资源池 数据资源池 软件资源池 软件 网络设施 身份认证 任务执行 任务调度 生命期管理 图 1-3 云计算技术体系结构 云 计 算 技 术 体 系 结 构 分 为 四 层 : 物 理 资 源 层 、 资 源 池 层 、 管 理 中 间 件 层 和 SOA(Service-Oriented Architecture,面向服务的体系结构)构建层。物理资源层包括计算 机、存储器、网络设施、数据库和软件等。资源池层是将大量相同类型的资源构成同构或 接近同构的资源池,如计算资源池、数据资源池等。构建资源池更多的是物理资源的集成 和管理工作,例如研究在一个标准集装箱的空间如何装下 2000 个服务器、解决散热和故 障节点替换的问题并降低能耗。管理中间件层负责对云计算的资源进行管理,并对众多应 用任务进行调度,使资源能够高效、安全地为应用提供服务。SOA 构建层将云计算能力 封装成标准的 Web Services 服务,并纳入到 SOA 体系进行管理和使用,包括服务接口、 服务注册、服务查找、服务访问和服务工作流等。管理中间件层和资源池层是云计算技术 的最关键部分,SOA 构建层的功能更多依靠外部设施提供。 云计算的管理中间件层负责资源管理、任务管理、用户管理和安全管理等工作。资源 管理负责均衡地使用云资源节点,检测节点的故障并试图恢复或屏蔽之,并对资源的使用 情况进行监视统计;任务管理负责执行用户或应用提交的任务,包括完成用户任务映象 (Image)的部署和管理、任务调度、任务执行、任务生命期管理等;用户管理是实现云 计算商业模式的一个必不可少的环节,包括提供用户交互接口、管理和识别用户身份、创 6 3 4 云计算 建用户程序的执行环境、对用户的使用进行计费等;安全管理保障云计算设施的整体安全 , 包括身份认证、访问授权、综合防护和安全审计等。 基于上述体系结构,本书以 IaaS 云计算为例,简述云计算的实现机制,如图 1-4 所 示。 图 1-4 简化的 IaaS 实现机制图 用户交互接口向应用以 Web Services 方式提供访问接口,获取用户需求。服务目录是 用户可以访问的服务清单。系统管理模块负责管理和分配所有可用的资源,其核心是负载 均衡。配置工具负责在分配的节点上准备任务运行环境。监视统计模块负责监视节点的运 行状态,并完成用户使用节点情况的统计。执行过程并不复杂,用户交互接口允许用户从 目录中选取并调用一个服务,该请求传递给系统管理模块后,它将为用户分配恰当的资源 , 然后调用配置工具为用户准备运行环境。 1.4 网格计算与云计算 网格(Grid)是 20 世纪 90 年代中期发展起来的下一代互联网核心技术。网格技术的 开创者 Ian Foster 将之定义为“在动态、多机构参与的虚拟组织中协同共享资源和求解问题” [6]。网格是在网络基础之上,基于 SOA,使用互操作、按需集成等技术手段,将分散在不 同地理位置的资源虚拟成为一个有机整体,实现计算、存储、数据、软件和设备等资源的 共享,从而大幅提高资源的利用率,使用户获得前所未有的计算和信息能力。 国际网格界致力于网格中间件、网格平台和网格应用建设。就网格中间件而言,国外 著名的网格中间件有 Globus Toolkit、UNICORE、Condor、gLite 等,其中 Globus Toolkit 得 到 了 广 泛 采 纳 。 就 网 格 平 台 而 言 , 国 际 知 名 的 网 格 平 台 有 TeraGrid、EGEE、CoreGRID、D-Grid、ApGrid、Grid3、GIG 等。美国 TeraGrid 是由美国 国家科学基金会计划资助构建的超大规模开放的科学研究环境。TeraGrid 集成了高性能计 算机、数据资源、工具和高端实验设施。目前 TeraGrid 已经集成了超过每秒 750 万亿次计 7 第 2 章 Google 云计算原理 算能力、30PB 数据,拥有超过 100 个面向多种领域的网格应用环境。欧盟 e-Science 促成 网格 EGEE(Enabling Grids for E-sciencE),是另一个超大型、面向多种领域的网格计算 基础设施。目前已有 120 多个机构参与,包括分布在 48 个国家的 250 个网格站点、68000 个 CPU、20PB 数据资源,拥有 8000 个用户,每天平均处理 30000 个作业,峰值超过 150000 个作业。就网格应用而言,知名的网格应用系统数以百计,应用 包括大气科学、 林学、海洋科学、环境科学、生物信息学、医学、物理学、天体物理、地球科学、天文学、 工程学、社会行为学等。 我国在十五期间有 863 支持的中国国家网格(CNGrid,863-10 主题)和中国空间信 息网格(SIG,863-13 主题)、教育部支持的中国教育科研网格(ChinaGrid)、上海市支 持的上海网格(ShanghaiGrid)等。中国国家网格拥有包括香港地区在内的 10 个节点,聚 合计算能力为每秒 18 万亿次,目前拥有 408 个用户和 360 个应用。中国教育科研网格 ChinaGrid 连接了 20 所高校的计算设施,运算能力达每秒 3 万亿次以上,开发并实现了生 物信息、流体力学等五个科学研究领域的网格典型应用。十一五期间,国家对网格支持的 力度更大,通过 973 和 863、自然科学基金等途径对网格技术进行了大力支持。973 计划 有“语义网格的基础理论、模型与方法研究”等,863 计划有“高效能计算机及网格服务环境”、 “网格地理信息系统软件及其重大应用”等,国家自然科学基金重大研究计划有“网络计算应 用支撑中间件”等项目。 就像云计算可以分为 IaaS、PaaS 和 SaaS 三种类型一样,网格计算也可以分为三种类 型:计算网格、信息网格和知识网格[6]。计算网格的目标是提供集成各种计算资源的、虚 拟化的计算基础设施。信息网格的目标是提供一体化的智能信息处理平台,集成各种信息 系统和信息资源,消除信息孤岛,使得用户能按需获取集成后的精确信息,即服务点播 (Service on Demand)和一步到位的服务(One Click is Enough)。知识网格[8]研究一体化 的智能知识处理和理解平台,使得用户能方便地发布、处理和获取知识。 需要说明的是,目前大家对网格的认识存在一种误解,认为只有使用 Globus Toolkit 等知名网格中间件的应用才是网格。我们认为,只要是遵照网格理念,将一定范围内分 布的异构资源集成为有机整体,提供资源共享和协同工作服务的平台,均可以认为是网 格。这是因为,由于网格技术非常复杂,必然有一个从不规范到规范化的过程,应该承 认差异存在的客观性。虽然网格界从一开始就致力于构造能够实现全面互操作的环境, 但由于网格处于信息技术前沿、许多领域尚未定型、已发布的个别规范过于复杂造成易 用性差等原因,现有网格系统多针对具体应用采用适用的、个性化的框架设计和实现技 术等,造成网格系统之间互操作困难,这也是开放网格论坛 OGF(Open Grid Forum)提 出建立不同网格系统互通机制计划 GIN(Grid Interoperation Now)的原因。从另一个角 度看,虽然建立全球统一的网格平台还有很长的路要走,但并不妨碍网格技术在各种具 体的应用系统中发挥重要的作用。 网格计算与云计算的关系如表 1-1 所示。 表 1-1 网格计算与云计算的比较 网 格 计 算 云 计 算 目标 共享高性能计算力和数据资源,实现资源共享和协同工 作 提供通用的计算平台和存储空间,提供各种软件服务 资源来源 不同机构 同一机构 8 3 4 云计算 资源类型 异构资源 同构资源 资源节点 高性能计算机 服务器/PC 虚拟化视图 虚拟组织 虚拟机 计算类型 紧耦合问题为主 松耦合问题 应用类型 科学计算为主 数据处理为主 用户类型 科学界 商业社会 付费方式 免费(政府出资) 按量计费 标准化 有统一的国际标准 OGSA/WSRF 尚无标准,但已经有了开放云计算联盟 OCC 网格计算在概念上争论多年,在体系结构上有三次大的改变,在标准规范上花费了大 量的人力,所设定的目标又非常远大——要在跨平台、跨组织、跨信任域的极其复杂的异 构环境中共享资源和协同解决问题,所要共享的资源也是五花八门——从高性能计算机、 数据库、设备到软件,甚至知识。云计算暂时不管概念、不管标准,Google 云计算与亚马 逊云计算的差别非常大,云计算只是对它们以前所做事情新的共同的时髦叫法,所共享的 存储和计算资源暂时仅限于某个企业内部,省去了许多跨组织协调的问题。以 Google 为 代表的云计算在内部管理运作方式上的简洁一如其界面,能省的功能都省略,Google 文件 系统甚至不允许修改已经存在的文件,只允许在文件后追加数据,大大降低了实现难度, 而且借助其无与伦比的规模效应释放了前所未有的能量。 网格计算与云计算的关系,就像是 OSI 与 TCP/IP 之间的关系:国际标准化组织 (ISO)制定的 OSI(开放系统互联)网络标准,考虑得非常周到,也异常复杂,在多年 之前就考虑到了会话层和表示层的问题。虽然很有远见,但过于理想,实现的难度和代价 非常大。当 OSI 的一个简化版——TCP/IP 诞生之后,将七层协议简化为四层,内容也大 大精简,因而迅速取得了成功。在 TCP/IP 一统天下之后多年,语义网等问题才被提上议 事日程,开始为 TCP/IP 补课,增加其会话和表示的能力。因此,可以说 OSI 是学院派, TCP/IP 是现实派;OSI 是 TCP/IP 的基础,TCP/IP 又推动了 OSI 的发展。两者不是“成者为 王、败者为寇”,而是滚动发展。 没有网格计算打下的基础,云计算也不会这么快到来。云计算是网格计算的一种简化 实用版,通常意义的网格是指以前实现的以科学研究为主的网格,非常重视标准规范,也 非常复杂,但缺乏成功的商业模式。云计算是网格计算的一种简化形态,云计算的成功也 是网格的成功。网格不仅要集成异构资源,还要解决许多非技术的协调问题,也不像云计 算有成功的商业模式推动,所以实现起来要比云计算难度大很多。但对于许多高端科学或 军事应用而言,云计算是无法满足需求的,必须依靠网格来解决。 目前,许多人声称网格计算失败了,云计算取而代之了,这其实是一种错觉。网格计 算已经有十多年历史,不如刚兴起时那样引人注目是正常的。事实上,有些政府主导、范 围较窄、用途特定的网格,已经取得了决定性的胜利。代表性的有美国的 TeraGrid 和欧洲 的 EGEE 等,这些网格每天都有几十万个作业在上面执行。未来的科学研究主战场,将建 立在网格计算之上。在军事 ,美军的全球信息网格 GIG 已经囊括超过 700 万台计算机, 规模超过现有的所有云计算数据中心计算机总和。 相信不久的将来,建立在云计算之上的“商业 2.0”与建立在网格计算之上的“科学 2.0” 都将取得成功。 9 第 2 章 Google 云计算原理 参考文献 [1] Michael Armbrust, Armando Fox, and Rean Griffith, et al. Above the Clouds: A Berkeley View of Cloud Computing, mimeo, UC Berkeley, RAD Laboratory, 2009 [2] Ian Foster, Carl Kesselman, and Steve Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of High Performance Computing Applications, 15(3), 2001 [3] 刘鹏. 提出一种实用的网格实现方式——网格计算池模型,2002 http://www.chinagrid.net/show.aspx?id=1672&cid=57 [4] Peng Liu, Yao Shi, San-li Li, Computing Pool—a Simplified and Practical Computational Grid Model, the Second International Workshop on Grid and Cooperative Computing (GCC 2003), Shanghai, Dec 7-10, 2003, published in Lecture Notes in Computer Science (LNCS), Vol. 3032, Heidelberg: Springer-Verlag, 2004 [5] Peng Liu, Yao Shi, Francis C. M. Lau, Cho-Li Wang, San-Li Li, Grid Demo Proposal: AntiSpamGrid, IEEE International Conference on Cluster Computing, Hong Kong, Dec 1- 4, 2003, selected as one of the excellent Grid research projects for the GridDemo session [6] 李国杰. 信息服务网格——第三代 Internet. 计算机世界, 2001 年第 40 期 [7] Foster, I., C. Kesselman, and S. Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of High Performance Computing Applications, 2001. 15(3): p. 200-222 [8] H. Zhuge, The Knowledge Grid, World Scientific Publishing Co., Singapore, 2004 10 3 4 云计算 第 2 章 Google 云计算原理 Google 拥有全 球最 强大 的 搜 索引 擎。除了 搜 索 业 务 以外, Google 还 有 Google Maps、Google Earth、Gmail、YouTube 等各种业务,包括刚诞生的 Google Wave。这些应 用的共性在于数据量巨大,而且要面向全球用户提供实时服务,因此 Google 必须解决海 量数据存储和快速处理问题。Google 的诀窍在于它发展出简单而又高效的技术,让多达百 万台的廉价计算机协同工作,共同完成这些前所未有的任务,这些技术是在诞生几年之后 才被命名为 Google 云计算技术。Google 云计算技术具体包括:Google 文件系统 GFS、分 布式计算编程模型 MapReduce、分布式锁服务 Chubby 和分布式结构化数据存储系统 Bigtable 等。其中,GFS 提供了海量数据的存储和访问的能力,MapReduce 使得海量信息 的并行处理变得简单易行,Chubby 保证了分布式环境下并发操作的同步问题,Bigtable 使 得海量数据的管理和组织十分方便。本章将对这四种核心技术进行详细介绍。 2.1 Google 文件系统 GFS Google 文件系统(Google File System,GFS)是一个大型的分布式文件系统。它为 Google 云计算提供海量存储,并且与 Chubby、MapReduce 以及 Bigtable 等技术结合十分 紧密,处于所有核心技术的底层。由于 GFS 并不是一个开源的系统,我们仅仅能从 Google 公布的技术文档来获得一点了解,而无法进行深入的研究。文献[1]是 Google 公布 的关于 GFS 的最为详尽的技术文档,它从 GFS 产生的背景、特点、系统框架、性能测试 等方面进行了详细的阐述。 当 前 主 流 分 布 式 文 件 系 统 有 RedHat 的 GFS[3] ( Global File System )、IBM 的 GPFS[4]、Sun 的 Lustre[5]等。这些系统通常用于高性能计算或大型数据中心,对硬件设施 条件要求较高。以 Lustre 文件系统为例,它只对元数据管理器 MDS 提供容错解决方案, 而对于具体的数据存储节点 OST 来说,则依赖其自身来解决容错的问题。例如,Lustre 推 荐 OST 节点采用 RAID 技术或 SAN 存储区域网来容错,但由于 Lustre 自身不能提供数据 存储的容错,一旦 OST 发生故障就无法恢复,因此对 OST 的稳定性就提出了相当高的要 求,从而大大增加了存储的成本,而且成本会随着规模的扩大线性增长。 正如李开复所说的那样,创新固然重要,但有用的创新更重要。创新的价值,取决于 一项创新在新颖、有用和可行性这三个方面的综合表现。Google GFS 的新颖之处并不在 于它采用了多么令人惊讶的技术,而在于它采用廉价的商用机器构建分布式文件系统,同 时将 GFS 的设计与 Google 应用的特点紧密结合,并简化其实现,使之可行,最终达到创 意新颖、有用、可行的完美组合。GFS 使用廉价的商用机器构建分布式文件系统,将容错 的任务交由文件系统来完成,利用软件的方法解决系统可靠性问题,这样可以使得存储的 成本成倍下降。由于 GFS 中服务器数目众多,在 GFS 中服务器死机是经常发生事情,甚 至都不应当将其视为异常现象,那么如何在频繁的故障中确保数据存储的安全、保证提供 不间断的数据存储服务是 GFS 最核心的问题。GFS 的精彩在于它采用了多种方法,从多 个角度,使用不同的容错措施来确保整个系统的可靠性。 11 第 2 章 Google 云计算原理 2.1.1 系统架构 GFS 的系统架构如图 2-1[1]所示。GFS 将整个系统的节点分为三类角色:Client(客户 端)、Master(主服务器)和 Chunk Server(数据块服务器)。Client 是 GFS 提供给应用 程序的访问接口,它是一组专用接口,不遵守 POSIX 规范,以库文件的形式提供。应用 程序直接调用这些库函数,并与该库链接在一起。Master 是 GFS 的管理节点,在逻辑上 只有一个,它保存系统的元数据,负责整个文件系统的管理,是 GFS 文件系统中的大脑。 Chunk Server 负责具体的存储工作。数据以文件的形式存储在 Chunk Server 上,Chunk Server 的个数可以有多个,它的数目直接决定了 GFS 的规模。GFS 将文件按照固定大小进 行分块,默认是 64MB,每一块称为一个 Chunk(数据块),每个 Chunk 都有一个对应的 索引号(Index)。 图 2-1 GFS 体系结构 客户端在访问 GFS 时,首先访问 Master 节点,获取将要与之进行交互的 Chunk Server 信息,然后直接访问这些 Chunk Server 完成数据存取。GFS 的这种设计方法实现了控制流 和数据流的分离。Client 与 Master 之间只有控制流,而无数据流,这样就极大地降低了 Master 的负载,使之不成为系统性能的一个瓶颈。Client 与 Chunk Server 之间直接传输数 据流,同时由于文件被分成多个 Chunk 进行分布式存储,Client 可以同时访问多个 Chunk Server,从而使得整个系统 I/O 高度并行,系统整体性能得到提高。 相对于传统的分布式文件系统,GFS 针对 Google 应用的特点从多个方面进行了简化, 从而在一定规模下达到成本、可靠性和性能的最佳平衡。具体来说,它具有以下几个特点。 1.采用中心服务器模式 GFS 采用中心服务器模式来管理整个文件系统,可以大大简化设计,从而降低实现难 度。Master 管理了分布式文件系统中的所有元数据。文件划分为 Chunk 进行存储,对于 Master 来说,每个 Chunk Server 只是一个存储空间。Client 发起的所有操作都需要先通过 Master 才能执行。这样做有许多好处,增加新的 Chunk Server 是一件十分容易的事情, Chunk Server 只需要注册到 Master 上即可,Chunk Server 之间无任何关系。如果采用完全 对等的、无中心的模式,那么如何将 Chunk Server 的更新信息通知到每一个 Chunk 12 3 4 云计算 Server,会是设计的一个难点,而这也将在一定程度上影响系统的扩展性。Master 维护了 一个统一的命名空间,同时掌握整个系统内 Chunk Server 的情况,据此可以实现整个系统 范围内数据存储的负载均衡。由于只有一个中心服务器,元数据的一致性问题自然解决。 当然,中心服务器模式也带来一些固有的缺点,比如极易成为整个系统的瓶颈等。GFS 采 用多种机制来避免 Master 成为系统性能和可靠性上的瓶颈,如尽量控制元数据的规模、 对 Master 进行远程备份、控制信息和数据分流等。 2.不缓存数据 缓存机制是提升文件系统性能的一个重要手段,通用文件系统为了提高性能,一般需 要实现复杂的缓存(Cache)机制。GFS 文件系统根据应用的特点,没有实现缓存,这是 从必要性和可行性两方面考虑的。从必要性上讲,客户端大部分是流式顺序读写,并不存 在大量的重复读写,缓存这部分数据对系统整体性能的提高作用不大;而对于 Chunk Server,由于 GFS 的数据在 Chunk Server 上以文件的形式存储,如果对某块数据读取频繁, 本地的文件系统自然会将其缓存。从可行性上讲,如何维护缓存与实际数据之间的一致性 是一个极其复杂的问题,在 GFS 中各个 Chunk Server 的稳定性都无法确保,加之网络等 多种不确定因素,一致性问题尤为复杂。此外由于读取的数据量巨大,以当前的内存容量 无法完全缓存。对于存储在 Master 中的元数据,GFS 采取了缓存策略,GFS 中 Client 发起 的所有操作都需要先经过 Master。Master 需要对其元数据进行频繁操作,为了提高操作的 效率,Master 的元数据都是直接保存在内存中进行操作;同时采用相应的压缩机制降低元 数据占用空间的大小,提高内存的利用率。 3.在用户态下实现 文件系统作为操作系统的重要组成部分,其实现通常位于操作系统底层。以 Linux 为 例,无论是本地文件系统如 Ext3 文件系统,还是分布式文件系统如 Lustre 等,都是在内 核态实现的。在内核态实现文件系统,可以更好地和操作系统本身结合,向上提供兼容的 POSIX 接口。然而,GFS 却选择在用户态下实现,主要基于以下考虑。 1)在用户态下实现,直接利用操作系统提供的 POSIX 编程接口就可以存取数据,无 需了解操作系统的内部实现机制和接口,从而降低了实现的难度,并提高了通用性。 2)POSIX 接口提供的功能更为丰富,在实现过程中可以利用更多的特性,而不像内 核编程那样受限。 3)用户态下有多种调试工具,而在内核态中调试相对比较困难。 4)用户态下,Master 和 Chunk Server 都以进程的方式运行,单个进程不会影响到整 个操作系统,从而可以对其进行充分优化。在内核态下,如果不能很好地掌握其特性,效 率不但不会高,甚至还会影响到整个系统运行的稳定性。 5)用户态下,GFS 和操作系统运行在不同的空间,两者耦合性降低,从而方便 GFS 自身和内核的单独升级。 4.只提供专用接口 通常的分布式文件系统一般都会提供一组与 POSIX 规范兼容的接口。其优点是应用 程序可以通过操作系统的统一接口来透明地访问文件系统,而不需要重新编译程序。 GFS 在设计之初,是完全面向 Google 的应用的,采用了专用的文件系统访问接口。接口以库 文件的形式提供,应用程序与库文件一起编译,Google 应用程序在代码中通过调用这些库 文件的 API,完成对 GFS 文件系统的访问。采用专用接口有以下好处。 13 第 2 章 Google 云计算原理 1)降低了实现的难度。通常与 POSIX 兼容的接口需要在操作系统内核一级实现,而 GFS 是在应用层实现的。 2)采用专用接口可以根据应用的特点对应用提供一些特殊支持,如支持多个文件并 发追加的接口等。 3)专用接口直接和 Client、Master、Chunk Server 交互,减少了操作系统之间上下文 的切换,降低了复杂度,提高了效率。 2.1.2 容错机制 1.Master 容错 具体来说,Master 上保存了 GFS 文件系统的三种元数据。 1)命名空间(Name Space),也就是整个文件系统的目录结构。 2)Chunk 与文件名的映射表。 3)Chunk 副本的位置信息,每一个 Chunk 默认有三个副本。 首先就单个 Master 来说,对于前两种元数据,GFS 通过操作日志来提供容错功能。 第三种元数据信息则直接保存在各个 Chunk Server 上,当 Master 启动或 Chunk Server 向 Master 注册时自动生成。因此当 Master 发生故障时,在磁盘数据保存完好的情况下,可 以迅速恢复以上元数据。为了防止 Master 彻底死机的情况,GFS 还提供了 Master 远程的 实时备份,这样在当前的 GFS Master 出现故障无法工作的时候,另外一台 GFS Master 可 以迅速接替其工作。 2.Chunk Server 容错 GFS 采用副本的方式实现 Chunk Server 的容错。每一个 Chunk 有多个存储副本(默认 为三个),分布存储在不同的 Chunk Server 上。副本的分布策略需要考虑多种因素,如网 络的拓扑、机架的分布、磁盘的利用率等。对于每一个 Chunk,必须将所有的副本全部写 入成功,才视为成功写入。在其后的过程中,如果相关的副本出现丢失或不可恢复等状况 , Master 会自动将该副本复制到其他 Chunk Server,从而确保副本保持一定的个数。尽管一 份数据需要存储三份,好像磁盘空间的利用率不高,但综合比较多种因素,加之磁盘的成 本不断下降,采用副本无疑是最简单、最可靠、最有效,而且实现的难度也最小的一种方 法。 GFS 中的每一个文件被划分成多个 Chunk,Chunk 的默认大小是 64MB,这是因为 Google 应用中处理的文件都比较大,以 64MB 为单位进行划分,是一个较为合理的选择。 Chunk Server 存储的是 Chunk 的副本,副本以文件的形式进行存储。每一个 Chunk 以 Block 为单位进行划分,大小为 64KB,每一个 Block 对应一个 32bit 的校验和。当读取一 个 Chunk 副本时,Chunk Server 会将读取的数据和校验和进行比较,如果不匹配,就会返 回错误,从而使 Client 选择其他 Chunk Server 上的副本。 2.1.3 系统管理技术 严格意义上来说,GFS 是一个分布式文件系统,包含从硬件到软件的整套解决方案。 14 3 4 云计算 除了上面提到的 GFS 的一些关键技术外,还有相应的系统管理技术来支持整个 GFS 的应 用,这些技术可能并不一定为 GFS 所独有。 1.大规模集群安装技术 安装 GFS 的集群中通常有非常多的节点,文献[1]中最大的集群超过 1000 个节点,而 现在的 Google 数据中心动辄有万台以上的机器在运行。那么,迅速地安装、部署一个 GFS 的系统,以及迅速地进行节点的系统升级等,都需要相应的技术支撑。 2.故障检测技术 GFS 是构建在不可靠的廉价计算机之上的文件系统,由于节点数目众多,故障发生十 分频繁,如何在最短的时间内发现并确定发生故障的 Chunk Server,需要相关的集群监控 技术。 3.节点动态加入技术 当有新的 Chunk Server 加入时,如果需要事先安装好系统,那么系统扩展将是一件十 分烦琐的事情。如果能够做到只需将裸机加入,就会自动获取系统并安装运行,那么将会 大大减少 GFS 维护的工作量。 4.节能技术 有关数据表明,服务器的耗电成本大于当初的购买成本,因此 Google 采用了多种机 制来降低服务器的能耗,例如对服务器主板进行修改,采用蓄电池代替昂贵的 UPS(不间 断电源系统),提高能量的利用率。Rich Miller 在一篇关于数据中心的博客文章中表示, 这个设计让 Google 的 UPS 利用率达到 99.9%,而一般数据中心只能达到 92%~95%。 2.2 并行数据处理 MapReduce MapReduce 是 Google 提出的一个软件架构,是一种处理海量数据的并行编程模式, 用于大规模数据集(通常大于 1TB)的并行运算。“Map(映射)”、“Reduce(化简)”的概 念和主要思想,都是从函数式编程语言和矢量编程语言借鉴来的 [5]。正是由于 MapReduce 有函数式和矢量编程语言的共性,使得这种编程模式特别适合于非结构化和结构化的海量 数据的搜索、挖掘、分析与机器智能学习等。 2.2.1 产生背景 MapReduce 这种并行编程模式思想最早是在 1995 年提出的,文献[6]首次提出了 “map”和“fold”的概念,和现在 Google 所使用的“Map”和“Reduce”思想是相吻合的。 与传统的分布式程序设计相比,MapReduce 封装了并行处理、容错处理、本地化计算、 负载均衡等细节,还提供了一个简单而强大的接口。通过这个接口,可以把大尺度的计算 自动地并发和分布执行,从而使编程变得非常容易。还可以通过由普通 PC 构成的巨大集 群来达到极高的性能。另外,MapReduce 也具有较好的通用性,大量不同的问题都可以简 单地通过 MapReduce 来解决。 MapReduce 把对数据集的大规模操作,分发给一个主节点管理下的各分节点共同完成, 通过这种方式实现任务的可靠执行与容错机制。在每个时间周期,主节点都会对分节点的 15 第 2 章 Google 云计算原理 工作状态进行标记,一旦分节点状态标记为死亡状态,则这个节点的所有任务都将分配给 其他分节点重新执行。 据相关统计,每使用一次 Google 搜索引擎,Google 的后台服务器就要进行 1011 次运 算。这么庞大的运算量,如果没有好的负载均衡机制,有些服务器的利用率会很低,有些 则会负荷太重,有些甚至可能死机,这些都会影响系统对用户的服务质量。而使用 MapReduce 这种编程模式,就保持了服务器之间的均衡,提高了整体效率。 2.2.2 编程模型 MapReduce 的运行模型如图 2-2 所示。图中有 M 个 Map 操作和 R 个 Reduce 操作。 简单地说,一个 Map 函数就是对一部分原始数据 进行指定的操作。每个 Map 操作都针对不同的原始数 据,因此 Map 与 Map 之间是互相独立的,这就使得它 们可以充分并行化。一个 Reduce 操作就是对每个 Map 所产生的一部分中间结果进行合并操作,每个 Reduce 所处理的 Map 中间结果是互不交叉的,所有 Reduce 产 生的最终结果经过简单连接就形成了完整的结果集, 因此 Reduce 也可以在并行环境下执行。 在编程的时候,开发者需要编写两个主要函数: Map: (in_key, in_value) à {(keyj, valuej) | j = 1…k} Reduce: (key, [value1,…,valuem]) à (key, final_value) Map 和 Reduce 的输入参数和输出结果根据应用的不同而有所不同。Map 的输入参数 是 in_key 和 in_value,它指明了 Map 需要处理的原始数据是哪些。Map 的输出结果是一组 对,这是经过 Map 操作后所产生的中间结果。在进行 Reduce 操作之前,系统 已经将所有 Map 产生的中间结果进行了归类处理,使得相同 key 对应的一系列 value 能够 集结在一起提供给一个 Reduce 进行归并处理,也就是说,Reduce 的输入参数是(key, [value1,…,valuem])。Reduce 的工作是需要对这些对应相同 key 的 value 值进行归并处理, 最终形成(key, final_value)的结果。这样,一个 Reduce 处理了一个 key,所有 Reduce 的 结果并在一起就是最终结果。 例如,假设我们想用 MapReduce 来计算一个大型文本文件中各个单词出现的次数, Map 的输入参数指明了需要处理哪部分数据,以<在文本中的起始位置,需要处理的数据 长度>表示,经过 Map 处理,形成一批中间结果<单词,出现次数>。而 Reduce 函数则是 把中间结果进行处理,将相同单词出现的次数进行累加,得到每个单词总的出现次数。 2.2.3 实现机制 实现 MapReduce 操作的执行流程图[7]如图 2-3 所示。 当用户程序调用 MapReduce 函数,就会引起如下操作(图中的数字标示和下面的数 字标示相同)。 Map Reduce Map Map … … 原始数据 1 原始数据 2 原始数据 M 结果 1 结果 R Reduce 图 2-2 MapReduce 的运行模型 16 3 4 云计算 1)用户程序中的 MapReduce 函数库首先把输入文件分成 M 块,每块大概 16M~ 64MB(可以通过参数决定),接着在集群的机器上执行处理程序。 2)这些分派的执行程序中有一个程序比较特别,它是主控程序 Master。剩下的执行 程序都是作为 Master 分派工作的 Worker(工作机)。总共有 M 个 Map 任务和 R 个 Reduce 任务需要分派,Master 选择空闲的 Worker 来分配这些 Map 或者 Reduce 任务。 图 2-3 MapReduce 执行流程图 3)一个分配了 Map 任务的 Worker 读取并处理相关的输入块。它处理输入的数据,并 且将分析出的对传递给用户定义的 Map 函数。Map 函数产生的中间结果 对暂时缓冲到内存。 4)这些缓冲到内存的中间结果将被定时写到本地硬盘,这些数据通过分区函数分成 R 个区。中间结果在本地硬盘的位置信息将被发送回 Master,然后 Master 负责把这些位置 信息传送给 Reduce Worker。 5)当 Master 通知 Reduce 的 Worker 关于中间对的位置时,它调用远程过 程来从 Map Worker 的本地硬盘上读取缓冲的中间数据。当 Reduce Worker 读到所有的中间 数据,它就使用中间 key 进行排序,这样可以使得相同 key 的值都在一起。因为有许多不 同 key 的 Map 都对应相同的 Reduce 任务,所以,排序是必需的。如果中间结果集过于庞 大,那么就需要使用外排序。 6)Reduce Worker 根据每一个唯一中间 key 来遍历所有的排序后的中间数据,并且把 key 和相关的中间结果值集合传递给用户定义的 Reduce 函数。Reduce 函数的结果输出到 一个最终的输出文件。 7)当所有的 Map 任务和 Reduce 任务都已经完成的时候,Master 激活用户程序。此时 MapReduce 返回用户程序的调用点。 由于 MapReduce 是用在成百上千台机器上处理海量数据的,所以容错机制是不可或 17 第 2 章 Google 云计算原理 缺的。总的说来,MapReduce 是通过重新执行失效的地方来实现容错的。 1.Master 失效 在 Master 中,会周期性地设置检查点(checkpoint),并导出 Master 的数据。一旦某 个任务失效了,就可以从最近的一个检查点恢复并重新执行。不过由于只有一个 Master 在运行,如果 Master 失效了,则只能终止整个 MapReduce 程序的运行并重新开始。 2.Worker 失效 相对于 Master 失效而言,Worker 失效算是一种常见的状态。Master 会周期性地给 Worker 发送 ping 命令,如果没有 Worker 的应答,则 Master 认为 Worker 失效,终止对这 个 Worker 的任务调度,把失效 Worker 的任务调度到其他 Worker 上重新执行。 2.2.4 案例分析 单词计数(Word Count)是一个经典的问题,也是能体现 MapReduce 设计思想的最简 单算法之一。该算法主要是为了完成对文字数据中所出现的单词进行计数,如图 2-4 所示。 图 2-4 单词计数 伪代码如下: Map(K,V){ For each word w in V Collect(w , 1); } Reduce(K,V[ ]){ int count = 0; For each v in V count += v; Collect(K , count); } 下面就根据 MapReduce 的四个执行步骤对这一算法进行详细的介绍。 1)根据文件所包含的信息分割(Split)文件,在这里把文件的每行分割为一组,共 三组,如图 2-5 所示。这一步由系统自动完成。 18 3 4 云计算 图 2-5 分割过程 2)对分割之后的每一对利用用户定义的 Map 进行处理,再生成新的 对,如图 2-6 所示。 图 2-6 Map 过程 3)Map 输出之后有一个内部的 Fold 过程,和第一步一样,都是由系统自动完成的, 如图 2-7 所示。 图 2-7 Fold 过程 4)经过 Fold 步骤之后的输出与结果已经非常接近,再由用户定义的 Reduce 步骤完成 最后的工作即可,如图 2-8 所示。 19 第 2 章 Google 云计算原理 图 2-8 Reduce 过程 2.3 分布式锁服务 Chubby Chubby 是 Google 设计的提供粗粒度锁服务的一个文件系统,它基于松耦合分布式系 统,解决了分布的一致性问题。通过使用 Chubby 的锁服务,用户可以确保数据操作过程 中的一致性。不过值得注意的是,这种锁只是一种建议性的锁(Advisory Lock)而不是强 制性的锁(Mandatory Lock),如此选择的目的是使系统具有更大的灵活性。 GFS 使用 Chubby 来选取一个 GFS 主服务器,Bigtable 使用 Chubby 指定一个主服务器 并发现、控制与其相关的子表服务器。除了最常用的锁服务之外,Chubby 还可以作为一 个稳定的存储系统存储包括元数据在类的小数据。同时 Google 内部还使用 Chubby 进行名 字服务(Name Server)。本节首先简要介绍 Paxos 算法,因为 Chubby 内部一致性问题的 实现用到了 Paxos 算法;然后围绕 Chubby 系统的设计和实现展开讲解。通过本节的学习 读者应该对分布式系统中一致性问题的一般性算法有初步的了解,着重掌握 Chubby 系统 设计和实现的精髓。 2.3.1 Paxos 算法 Paxos 算法 [14][15] 是由供职于微软的 Leslie Lamport 最先提出的一种基于消息传递 (Messages Passing)的一致性算法。在目前所有的一致性算法中,该算法最常用且被认 为是最有效的。要想了解 Paxos 算法,我们首先需要知道什么是分布式系统中的一致性问 题,因为 Paxos 算法就是为了解决这个问题而提出的。简单地说分布式系统的一致性问题, 就是如何保证系统中初始状态相同的各个节点在执行相同的操作序列时,看到的指令序列 是完全一致的,并且最终得到完全一致的结果。在 Lamport 提出的 Paxos 算法中节点被分 成 了 三 种 类 型 : proposers 、 acceptors 和 learners 。 其 中 proposers 提 出 决 议 (Value),acceptors 批准决议,learners 获取并使用已经通过的决议。一个节点可以兼有 多重类型。在这种情况下,满足以下三个条件[15]就可以保证数据的一致性: 1)决议只有在被 proposers 提出后才能批准。 2)每次只批准一个决议。 20 3 4 云计算 3)只有决议确定被批准后 learners 才能获取这个决议。 Lamport 通过约束条件的不断加强,最后得到了一个可以实际运用到算法中的完整约 束条件:如果一个编号为 n 的提案具有值 v,那么存在一个多数派,要么他们中没有人批 准过编号小于 n 的任何提案,要么他们进行的最近一次批准具有值 v。为了保证决议的唯 一性,acceptors 也要满足一个如下的约束条件:当且仅当 acceptors 没有收到编号大于 n 的请求时,acceptors 才批准编号为 n 的提案。 在这些约束条件的基础上,可以将一个决议的通过分成两个阶段。 1)准备阶段:proposers 选择一 个提案并 将它 的编号设为 n, 然后将它 发送给 acceptors 中的一个多数派。Acceptors 收到后,如果提案的编号大于它已经回复的所有消 息,则 acceptors 将自己上次的批准回复给 proposers,并不再批准小于 n 的提案。 2)批准阶段:当 proposers 接收到 acceptors 中的这个多数派的回复后,就向回复请求 的 acceptors 发送 accept 请求,在符合 acceptors 一方的约束条件下,acceptors 收到 accept 请求后即批准这个请求。 为了减少决议发布过程中的消息量,acceptors 将这个通过的决议发送给 learners 的一 个子集,然后由这个子集中的 learners 去通知所有其他的 learners。一般情况下,以上的算 法过程就可以成功地解决一致性问题,但是也有特殊情况。根据算法一个编号更大的提案 会终止之前的提案过程,如果两个 proposer 在这种情况下都转而提出一个编号更大的提案, 那么就可能陷入活锁。此时需要选举出一个 president,仅允许 president 提出提案。 以上只是简要地向大家介绍了 Paxos 算法的核心内容,关于更多的实现细节读者可以 参考 Lamport 关于 Paxos 算法实现的文章。 2.3.2 Chubby 系统设计 通常情况下 Google 的一个数据中心仅运行一个 Chubby 单元[13](Chubby cell,下面会有 详细讲解),而这个单元需要支持包括 GFS、Bigtable 在内的众多 Google 服务。这种苛刻 的服务要求使得 Chubby 在设计之初就要充分考虑到系统需要实现的目标以及可能出现的 各种问题。 Chubby 的设计目标主要有以下几点。 1)高可用性和高可靠性。这是系统设计的首要目标,在保证这一目标的基础上再考 虑系统的吞吐量和存储能力。 2)高扩展性。将数据存储在价格较为低廉的 RAM,支持大规模用户访问文件。 3)支持粗粒度的建议性锁服务。提供这种服务的根本目的是提高系统的性能。 4)服务信息的直接存储。可以直接存储包括元数据、系统参数在内的有关服务信息, 而不需要再维护另一个服务。 5)支持通报机制。客户可以及时地了解到事件的发生。 6)支持缓存机制。通过一致性缓存将常用信息保存在客户端,避免了频繁地访问主 服务器。 前面提到在分布式系统中保持数据一致性最常用也最有效的算法是 Paxos,很多系统 就是将 Paxos 算法作为其一致性算法的核心。但是 Google 并没有直接实现一个包含了 21 第 2 章 Google 云计算原理 Paxos 算法的函数库,相反,Google 设计了一个全新的锁服务 Chubby。Google 做出这种 设计主要是考虑到以下几个问题[13]。 1)通常情况下开发者在开发的初期很少考虑系统的一致性问题,但是随着开发的不 断进行,这种问题会变得越来越严重。单独的锁服务可以保证原有系统的架构不会发生改 变,而使用函数库的话很可能需要对系统的架构做出大幅度的改动。 2)系统中很多事件的发生是需要告知其他用户和服务器的,使用一个基于文件系统 的锁服务可以将这些变动写入文件中。这样其他需要了解这些变动的用户和服务器直接访 问这些文件即可,避免了因大量的系统组件之间的事件通信带来的系统性能下降。 3)基于锁的开发接口容易被开发者接受。虽然在分布式系统中锁的使用会有很大的 不同,但是和一致性算法相比,锁显然被更多的开发者所熟知。 一般来说分布式一致性问题通过 quorum 机制(简单来说就是根据少数服从多数的选 举原则产生一个决议)做出决策,为了保证系统的高可用性,需要若干台机器,但是使用 单独的锁服务的话一台机器也能保证这种高可用性。也就是说,Chubby 在自身服务的实 现时利用若干台机器实现了高可用性,而外部用户利用 Chubby 则只需一台机器就可以保 证高可用性。 正是考虑到以上几个问题,Google 设计了 Chubby,而不是单独地维护一个函数库 (实际上,Google 有这样一个独立于 Chubby 的函数库,不过一般情况下并不会使用)。 在设计的过程中有一些细节问题也值得我们关注,比如在 Chubby 系统中采用了建议性的 锁而没有采用强制性的锁。两者的根本区别在于用户访问某个被锁定的文件时,建议性的 锁不会阻止这种行为,而强制性的锁则会,实际上这是为了便于系统组件之间的信息交互 行为。另外 Chubby 还采用了粗粒度(Coarse-Grained)锁服务而没有采用细粒度(Fine- Grained)锁服务,两者的差异在于持有锁的时间。细粒度的锁持有时间很短,常常只有 几秒甚至更少,而粗粒度的锁持有的时间可长达几天,做出如此选择的目的是减少频繁 换锁带来的系统开销。当然用户也可以自行实现细粒度锁,不过建议还是使用粗粒度 的锁。 图 2-9[13]就是 Chubby 的基本架构。很明显,Chubby 被划分成两个部分:客户端和服 务器端,客户端和服务器端之间通过远程过程调用(RPC)来连接。在客户这一端每个客 户应用程序都有一个 Chubby 程序库(Chubby Library),客户端的所有应用都是通过调用 这个库中的相关函数来完成的。服务器一端称为 Chubby 单元,一般是由五个称为副本 (Replica)的服务器组成的,这五个副本在配置上完全一致,并且在系统刚开始时处于对 等地位。这些副本通过 quorum 机制选举产生一个主服务器(Master),并保证在一定的 时间内有且仅有一个主服务器,这个时间就称为主服务器租约期( Master Lease)。如果 某个服务器被连续推举为主服务器的话,这个租约期就会不断地被更新。租续期内所有的 客户请求都是由主服务器来处理的。客户端如果需要确定主服务器的位置,可以向 DNS 发送一个主服务器定位请求,非主服务器的副本将对该请求做出回应,通过这种方式客户 端能够快速、准确地对主服务器做出定位。 22 3 4 云计算 客户端应 用程序 Chubby 程序库 … 客户端应 用程序 Chubby 程序库 客户端进程 主服务器 Chubby 单元的 五个服务器 远程过程调用 图 2-9 Chubby 的基本架构 2.3.3 Chubby 文件系统 Chubby 系统本质上就是一个分布式的、存储大量小文件的文件系统,它所有的操作 都是在文件的基础上完成的。例如在 Chubby 最常用的锁服务中,每一个文件就代表了一 个锁,用户通过打开、关闭和读取文件,获取共享(Shared)锁或独占(Exclusive)锁。 选举主服务器的过程中,符合条件的服务器都同时申请打开某个文件并请求锁住该文件。 成功获得锁的服务器自动成为主服务器并将其地址写入这个文件夹,以便其他服务器和用 户可以获知主服务器的地址信息。 Chubby 的文件系统[13]和 UNIX 类似。例如在文件名“/ls/foo/wombat/pouch”中,ls 代表 lock service , 这 是 所 有 Chubby 文 件 系 统 的 共 有 前 缀 ; foo 是 某 个 单 元 的 名 称 ; /wombat/pouch 则是 foo 这个单元上的文件目录或者文件名。由于 Chubby 自身的特殊服务 要求,Google 对 Chubby 做了一些与 UNIX 不同的改变。例如 Chubby 不支持内部文件的 移动;不记录文件的最后访问时间;另外在 Chubby 中并没有符号连接(Symbolic Link, 又叫软连接,类似于 Windows 系统中的快捷方式)和硬连接(Hard Link,类似于别名) 的概念。在具体实现时,文件系统由许多节点组成,分为永久型和临时型,每个节点就是 一个文件或目录。节点中保存着包括 ACL(Access Control List,访问控制列表,将在 2.3.5 节讲解)在内的多种系统元数据。为了用户能够及时了解元数据的变动,系统规定 每个节点的元数据都应当包含以下四种单调递增的 64 位编号[13]。 1)实例号(Instance Number):新节点实例号必定大于旧节点的实例号。 2)内容生成号(Content Generation Number):文件内容修改时该号增加。 3)锁生成号(Lock Generation Number):锁被用户持有时该号增加。 4)ACL 生成号(ACL Generation Number):ACL 名被覆写时该号增加。 用户在打开某个节点时就会获取一个类似于 UNIX 中文件描述符(File Descriptor)的 句柄[13](Handles),这个句柄由以下三个部分组成。 1)校验数位(Check Digit):防止其他用户创建或猜测这个句柄。 2)序号(Sequence Number):用来确定句柄是由当前还是以前的主服务器创建的。 3)模式信息(Mode Information):用于新的主服务器重新创建一个旧的句柄。 在实际的执行中,为了避免所有的通信都使用序号带来的系统开销增长,Chubby 引 23 第 2 章 Google 云计算原理 入了 sequencer 的概念。sequencer 实际上就是一个序号,只不过这个序号只能由锁的持有 者在获取锁时向系统发出请求来获得。这样一来 Chubby 系统中只有涉及锁的操作才需要 序号,其他一概不用。在文件操作中,用户可以将句柄看做一个指向文件系统的指针。这 个指针支持一系列的操作,常用的句柄操作函数如表 2-1 所示。 表 2-1 常用句柄函数及其作用 函数名称 作 用 Open() 打开某个文件或者目录来创建句柄 Close() 关闭打开的句柄,后续的任何操作都将中止 Poison() 中止当前未完成及后续的操作,但不关闭句柄 GetContentsAndStat() 返回文件内容及元数据 GetStat() 只返回文件元数据 ReadDir() 返回子目录名称及其元数据 SetContents() 向文件中写入内容 SetACL() 设置 ACL 名称 Delete() 如果该节点没有子节点的话则执行删除操作 Acquire() 获取锁 Release() 释放锁 GetSequencer() 返回一个 sequencer SetSequencer() 将 sequencer 和某个句柄进行关联 CheckSequencer() 检查某个 sequencer 是否有效 2.3.4 通信协议 客户端和主服务器之间的通信是通过 KeepAlive 握手协议来维持的,图 2-10[13]就是这 一通信过程的简单示意图。 1 2 3 4 5 6 7 8 旧的主 服务器 新的主 服务器 宽限期 旧的主服 务器故障 选出新的 主服务器 客户端 租约期 M2 租约期 C1 无主服务器 危险状态临界点 安全状态临界点 KeepAlive s 租约期 M1 租约期 C2 租约期 C3 租约期 M3 图 2-10 Chubby 客户端与服务器端的通信过程 图 2-10 中从左到右时间在增加,斜向上的箭头表示一次 KeepAlive 请求,斜向下的箭 头则是主服务器的一次回应。M1、M2、M3 表示不同的主服务器租约期。C1、C2、C3 则是 客户端对主服务器租约期时长做出的一个估计。KeepAlive 是周期发送的一种信息,它主 24 3 4 云计算 要有两方面的功能:延迟租约的有效期和携带事件信息告诉用户更新。主要的事件包括文 件内容被修改、子节点的增加、删除和修改、主服务器出错、句柄失效等。正常情况下, 通过 KeepAlive 握手协议租约期会得到延长,事件也会及时地通知给用户。但是由于系统 有一定的失效概率,引入故障处理措施是很有必要的。通常情况下系统可能会出现两种故 障:客户端租约期过期和主服务器故障,对于这两种情况系统有着不同的应对方式。 1.客户端租约过期 刚开始时,客户端向主服务器发出一个 KeepAlive 请求(图 2-10 中的 1),如果有需 要通知的事件时则主服务器会立刻做出回应,否则主服务器并不立刻对这个请求做出回应 , 而是等到客户端的租约期 C1 快结束的时候才做出回应(图 2-10 中的 2),并更新主服务 器租约期为 M2。客户端在接到这个回应后认为该主服务器仍处于活跃状态,于是将租约 期更新为 C2 并立刻发出新的 KeepAlive 请求(图 2-10 中的 3)。同样的,主服务器可能不 是立刻回应而是等待 C2 接近结束,但是在这个过程中主服务器出现故障停止使用。在等 待了一段时间后 C2 到期,由于并没有收到主服务器的回应,系统向客户端发出一个危险 (Jeopardy)事件,客户端清空并暂时停用自己的缓存,从而进入一个称为宽限期(Grace Period)的危险状态。这个宽限期默认是 45 秒。在宽限期内,客户端不会立刻断开其与服 务器端的联系,而是不断地做探询。图 2-10 中新的主服务器很快被重新选出,当它接到 客户端的第一个 KeepAlive 请求(图 2-10 中的 4)时会拒绝(图 2-10 中的 5),因为这个 请求的纪元号(Epoch Number)错误。不同主服务器的纪元号不相同,客户端的每次请求 都需要这个号来保证处理的请求是针对当前的主服务器。客户端在主服务器拒绝之后会使 用新的纪元号来发送 KeepAlive 请求(图 2-10 中的 6)。新的主服务器接受这个请求并立 刻做出回应(图 2-10 中的 7)。如果客户端接收到这个回应的时间仍处于宽限期内,则系 统会恢复到安全状态,租约期更新为 C3。如果在宽限期未接到主服务器的相关回应,则 客户端终止当前的会话。 2.主服务器出错 在客户端和主服务器端进行通信时可能会遇到主服务器故障,图 2-10 就出现了这种 情况。正常情况下旧的主服务器出现故障后系统会很快地选举出新的主服务器,新选举的 主服务器在完全运行前需要经历以下九个步骤[13]。 1)产生一个新的纪元号以便今后客户端通信时使用,这能保证当前的主服务器不必 处理针对旧的主服务器的请求。 2)只处理主服务器位置相关的信息,不处理会话相关的信息。 3)构建处理会话和锁所需的内部数据结构。 4)允许客户端发送 KeepAlive 请求,不处理其他会话相关的信息。 5)向每个会话发送一个故障事件,促使所有的客户端清空缓存。 6)等待直到所有的会话都收到故障事件或会话终止。 7)开始允许执行所有的操作。 8)如果客户端使用了旧的句柄则需要为其重新构建新的句柄。 9)一定时间段后(1 分钟),删除没有被打开过的临时文件夹。 如果这一过程在宽限期内顺利完成,则用户不会感觉到任何故障的发生,也就是说新 旧主服务器的替换对于用户来说是透明的,用户感觉到的仅仅是一个延迟。使用宽限期的 好处正是如此。 25 第 2 章 Google 云计算原理 在系统实现时,Chubby 还使用了一致性客户端缓存(Consistent Client-Side Caching) 技术,这样做的目的是减少通信压力,降低通信频率。在客户端保存一个和单元上数据一 致的本地缓存,这样需要时客户可以直接从缓存中取出数据而不用再和主服务器通信。当 某个文件数据或者元数据需要修改时,主服务器首先将这个修改阻塞;然后通过查询主服 务器自身维护的一个缓存表,向所有对修改的数据进行了缓存的客户端发送一个无效标志 (Invalidation);客户端收到这个无效标志后会返回一个确认(Acknowledge),主服务 器在收到所有的确认后才解除阻塞并完成这次修改。这个过程的执行效率非常高,仅仅需 要发送一次无效标志即可,因为主服务器对于没有返回确认的节点就直接认为其是未缓存 的。 2.3.5 正确性与性能 1.一致性 前面提到过每个 Chubby 单元是由五个副本组成的,这五个副本中需要选举产生一个 主服务器,这种选举本质上就是一个一致性问题。在实际的执行过程中,Chubby 使用 Paxos 算法来解决这个问题。 主服务器产生后客户端的所有读写操作都是由主服务器来完成的。读操作很简单,客 户直接从主服务器上读取所需数据即可,但是写操作就涉及数据一致性的问题了。为了保 证客户的写操作能够同步到所有的服务器上,系统再次利用了 Paxos 算法。因此,可以看 出 Paxos 算法在分布式一致性问题中的作用是巨大的。 2.安全性 Chubby 采用的是 ACL 形式的安全保障措施。系统中有三种 ACL 名[13],分别是写 ACL 名(Write ACL Name)、读 ACL 名(Read ACL Name)和变更 ACL 名(Change ACL Name)。只要不被覆写,子节点都是直接继承父节点的 ACL 名。ACL 同样被保存在文件 中,它是节点元数据的一部分,用户在进行相关操作时首先需要通过 ACL 来获取相应的 授权。图 2-11 是一个用户成功写文件所需经历的过程。 chinacloud CLOUD fun …… …… chinacloud ①请求写文件 ②读取写 ACL 名 ③查询 ④成功查到 允许写入 ⑤成功写入 图 2-11 Chubby 的 ACL 机制 用户 chinacloud 请求向文件 CLOUD 中写入内容。CLOUD 首先读取自身的写 ACL 名 是 fun,接着在 fun 中查到了 chinacloud 这一行记录,于是返回信息允许 chinacloud 对文件 进行写操作,此时 chinacloud 才被允许向 CLOUD 写入内容。其他的操作和写操作类似。 3.性能优化 为了满足系统的高可扩展性,Chubby 目前已经采取了一些措施[13]。比如提高主服务 器默认的租约期、使用协议转换服务将 Chubby 协议转换成较简单的协议。还有就是使用 26 3 4 云计算 上面提到的客户端一致性缓存。除此之外,Google 的工程师们还考虑使用代理(Proxy) 和分区(Partition)技术,虽然目前这两种技术并没有实际使用,但是在设计的时候还是 被包含进系统,不排除将来使用的可能。代理可以减少主服务器处理 KeepAlive 以及读请 求带来的服务器负载,但是它并不能减少写操作带来的通信量。不过根据 Google 自己的 数据统计表明,在所有的请求中,写请求仅占极少的一部分,几乎可以忽略不计。使用分 区技术的话可以将一个单元的命名空间(Name Space)划分成 N 份。除了少量的跨分区通 信外,大部分的分区都可以独自地处理服务请求。通过分区可以减少各个分区上的读写通 信量,但不能减少 KeepAlive 请求的通信量。因此,如果需要的话,将代理和分区技术结 合起来使用才可以明显提高系统同时处理的服务请求量。 2.4 分布式结构化数据表 Bigtable Bigtable 是 Google 开发的基于 GFS 和 Chubby 的分布式存储系统。Google 的很多数据, 包括 Web 索引、卫星图像数据等在内的海量结构化和半结构化数据,都是存储在 Bigtable 中的。从实现上来看,Bigtable 并没有什么全新的技术,但是如何选择合适的技术并将这 些技术高效、巧妙地结合在一起恰恰是最大的难点。Google 的工程师通过研究以及大量的 实践,完美实现了相关技术的选择及融合。Bigtable 在很多方面和数据库类似,但它并不 是真正意义上的数据库。通过本节的学习,读者将会对 Bigtable 的数据模型、系统架构、 实现以及它使用的一些数据库技术有一个全面的认识。 2.4.1 设计动机与目标 Google 设计 Bigtable 的动机主要有如下三个方面。 1)需要存储的数据种类繁多。Google 目前向公众开放的服务很多,需要处理的数据 类型也非常多。包括 URL、网页内容、用户的个性化设置在内的数据都是 Google 需要经 常处理的。 2)海量的服务请求。Google 运行着目前世界上最繁忙的系统,它每时每刻处理的客 户服务请求数量是普通的系统根本无法承受的。 3)商用数据库无法满足 Google 的需求。一方面现有商用数据库的设计着眼点在于其 通用性,面对 Google 的苛刻服务要求根本无法满足,而且在数量庞大的服务器上根本无 法成功部署普通的商用数据库。另一方面对于底层系统的完全掌控会给后期的系统维护、 升级带来极大的便利。 在仔细考察了 Google 的日常需求后,Bigtable 开发团队确定了 Bigtable 设计所需达到 的如下几个基本目标。 1)广泛的适用性。Bigtable 是为了满足一系列 Google 产品而并非特定产品的存储要 求。 2)很强的可扩展性。根据需要随时可以加入或撤销服务器。 3)高可用性。对于客户来说,有时候即使短暂的服务中断也是不能忍受的。Bigtable 设计的重要目标之一就是确保几乎所有的情况下系统都可用。 27 第 2 章 Google 云计算原理 4)简单性。底层系统的简单性既可以减少系统出错的概率,也为上层应用的开发带 来便利。 在目标确定之后,Google 开发者就在现有的数据库技术中进行了大规模的筛选,希望 各种技术之间能够扬长避短,巧妙地结合起来。最终实现的系统也确实达到了原定的目标 。 下面就开始详细讲解 Bigtable。 2.4.2 数据模型 Bigtable 是一个分布式多维映射表,表中的数据是通过一个行关键字(Row Key)、 一个列关键字(Column Key)以及一个时间戳(Time Stamp)进行索引的。Bigtable 对存 储在其中的数据不做任何解析,一律看做字符串,具体数据结构的实现需要用户自行处理 。 Bigtable 的存储逻辑可以表示为: (row:string, column:string, time:int64)→string Bigtable 数据的存储格式如图 2-12 所示[8]。 “ 内容:” “ 锚点:cnnsi.com” “ 锚点:my..look.ca” “ com.cnn.www” “ …” “ …” “ …” “ CNN.com” “ CNN” t3 t5 t6 t8 t9 图 2-12 Bigtable 数据模型 1.行 Bigtable 的行关键字可以是任意的字符串,但是大小不能够超过 64KB。Bigtable 和传 统的关系型数据库有很大不同,它不支持一般意义上的事务,但能保证对于行的读写操作 具有原子性(Atomic)。表中数据都是根据行关键字进行排序的,排序使用的是词典序。 图 2-12 是 Bigtable 数据模型的一个典型实例,其中 com.cn.www 就是一个行关键字。不 直接存储网页地址而将其倒排是 Bigtable 的一个巧妙设计。这样做至少会带来以下两个 好处。 1)同一地址域的网页会被存储在表中的连续位置,有利于用户查找和分析。 2)倒排便于数据压缩,可以大幅提高压缩率。 单个的大表由于规模问题不利于数据的处理,因此 Bigtable 将一个表分成了很多子表 (Tablet),每个子表包含多个行。子表是 Bigtable 中数据划分和负载均衡的基本单位。 有关子表的内容会在稍后详细讲解。 2.列 Bigtable 并不是简单地存储所有的列关键字,而是将其组织成所谓的列族(Column Family),每个族中的数据都属于同一个类型,并且同族的数据会被压缩在一起保存。引 入了列族的概念之后,列关键字就采用下述的语法规则来定义: 族名:限定词(family:qualifier) 族名必须有意义,限定词则可以任意选定。在图 2-12 中,内容(Contents)、锚点 28 3 4 云计算 (Anchor,就是 HTML 中的链接)都是不同的族。而 cnnsi.com 和 my.look.ca 则是锚点族 中不同的限定词。通过这种方式组织的数据结构清晰明了,含义也很清楚。族同时也是 Bigtable 中访问控制(Access Control)的基本单元,也就是说访问权限的设置是在族这一 级别上进行的。 3.时间戳 Google 的很多服务比如网页检索和用户的个性化设置等都需要保存不同时间的数据, 这些不同的数据版本必须通过时间戳来区分。图 2-12 中内容列的 t3、t5 和 t6 表明其中保 存了在 t3、t5 和 t6 这三个时间获取的网页。Bigtable 中的时间戳是 64 位整型数,具体的赋 值方式可以采取系统默认的方式,也可以用户自行定义。 为了简化不同版本的数据管理,Bigtable 目前提供了两种设置:一种是保留最近的 N 个不同版本,图 2-12 中数据模型采取的就是这种方法,它保存最新的三个版本数据。另 一种就是保留限定时间内的所有不同版本,比如可以保存最近 10 天的所有不同版本数据。 失效的版本将会由 Bigtable 的垃圾回收机制自动处理。 2.4.3 系统架构 Bigtable 是在 Google 的另外三个云计算组件基础之上构建的,其基本架构如图 2-13 所示[11]。 图中 WorkQueue 是一个分布式的任务调度器,它主要被用来处理分布式系统队列分 组和任务调度,关于其实现 Google 并没有公开。在前面已经讲过,GFS[9]是 Google 的分 布式文件系统,在 Bigtable 中 GFS 主要用来存储子表数据以及一些日志文件。Bigtable 还 需要一个锁服务的支持,Bigtable 选用了 Google 自己开发的分布式锁服务 Chubby。在 Bigtable 中 Chubby 主要有以下几个作用[10]。 1)选取并保证同一时间内只有一个主服务器(Master Server)。 2)获取子表的位置信息。 3)保存 Bigtable 的模式信息及访问控制列表。 Bigtable 主服务器 Bigtable 客户端 Bigtable 客户端 程序库 Bigtable 子表服务器 Bigtable 子表服务器 Bigtable 子表服务器 处理数据 处理数据 处理数据 Google WorkQueue GFS Chubby 执行 Open () 操作 负责故障处理及监控 保存子表数据及日志 负责元数据存储及 主服务器的选择 执行元数据操作及 负载平衡 图 2-13 Bigtable 基本架构 29 第 2 章 Google 云计算原理 另外在 Bigtable 的实际执行过程中,Google 的 MapReduce 和 Sawzall 也被使用来改善 其性能,不过需要注意的是这两个组件并不是实现 Bigtable 所必需的。 Bigtable 主要由三个部分组成:客户端程序库(Client Library)、一个主服务器 (Master Server)和多个子表服务器(Tablet Server),这三个部分在图 2-13 中都有相应 的表示。从图 2-13 中可以看出,客户需要访问 Bigtable 服务时首先要利用其库函数执行 Open()操作来打开一个锁(实际上就是获取了文件目录),锁打开以后客户端就可以和子 表服务器进行通信了。和许多具有单个主节点的分布式系统一样,客户端主要与子表服务 器通信,几乎不和主服务器进行通信,这使得主服务器的负载大大降低。主服务主要进 行一些元数据的操作以及子表服务器之间的负载调度问题,实际的数据是存储在子表服 务器上的。客户程序库的概念比较简单,这里不做讲解,下面对主服务器和子表服务器 展开讲解。 2.4.4 主服务器 主服务的主要作用如图 2-14 所示。 主服务器 新子表分配 子表服务器 状态监控 子服务器之间 的负载均衡 图 2-14 主服务器的主要作用 当一个新的子表产生时,主服务器通过一个加载命令将其分配给一个空间足够的子表 服务器。创建新表、表合并以及较大子表的分裂都会产生一个或多个新子表。对于前面两 种,主服务器会自动检测到,因为这两个操作是由主服务器发起的,而较大子表的分裂是 由子服务发起并完成的,所以主服务器并不能自动检测到,因此在分割完成之后子服务器 需要向主服务发出一个通知。由于系统设计之初就要求能达到良好的扩展性,所以主服务 器必须对子表服务器的状态进行监控,以便及时检测到服务器的加入或撤销。Bigtable 中 主服务器对子表服务器的监控是通过 Chubby 来完成的,子表服务器在初始化时都会从 Chubby 中得到一个独占锁。通过这种方式所有的子表服务器基本信息被保存在 Chubby 中 一个称为服务器目录(Server Directory)的特殊目录之中。主服务器通过检测这个目录就 可以随时获取最新的子表服务器信息,包括目前活跃的子表服务器,以及每个子表服务器 上现已分配的子表。对于每个具体的子表服务器,主服务器会定期向其询问独占锁的状态 。 如果子表服务器的锁丢失或没有回应,则此时可能有两种情况,要么是 Chubby 出现了问 题(虽然这种概率很小,但的确存在,Google 自己也做过相关测试),要么是子表服务器 30 3 4 云计算 自身出现了问题。对此主服务器首先自己尝试获取这个独占锁,如果失败说明 Chubby 服 务出现问题,需等待 Chubby 服务的恢复。如果成功则说明 Chubby 服务良好而子表服务器 本身出现了问题。这种情况下主服务器会中止这个子表服务器并将其上的子表全部移至其 他子表服务器。当在状态监测时发现某个子表服务器上负载过重时,主服务器会自动对其 进行负载均衡操作。 基于系统出现故障是一种常态的设计理念(Google 几乎所有的产品都是基于这个设计 理念),每个主服务器被设定了一个会话时间的限制。当某个主服务器到时退出后,管理 系统就会指定一个新的主服务器,这个主服务器的启动需要经历以下四个步骤[8]。 1)从 Chubby 中获取一个独占锁,确保同一时间只有一个主服务器。 2)扫描服务器目录,发现目前活跃的子表服务器。 3)与所有的活跃子表服务器取得联系以便了解所有子表的分配情况。 4)通过扫描元数据表(Metadata Table),发现未分配的子表并将其分配到合适的子 表服务器。如果元数据表未分配,则首先需要将根子表(Root Tablet)加入未分配的子表 中。由于根子表保存了其他所有元数据子表的信息,确保了扫描能够发现所有未分配的 子表。 在成功完成以上四个步骤后主服务器就可以正常运行了。 2.4.5 子表服务器 Bigtable 中实际的数据都是以子表的形式保存在子表服务器上的,客户一般也只和子 表服务器进行通信,所以子表以及子表服务器是我们重点讲解的概念。子表服务器上的操 作主要涉及子表的定位、分配以及子表数据的最终存储问题。其中子表分配在前面已经有 了详细介绍,这里略过不讲。在讲解其他问题之前我们首先介绍一下 SSTable 的概念以及 子表的基本结构。 1.SSTable 及子表基本结构 SSTable 是 Google 为 Bigtable 设计的内部数据存储格式。所有的 SSTable 文件都是存 储在 GFS 上的,用户可以通过键来查询相应的值,图 2-15 是 SSTable 格式的基本示意图。 块 块 …… 索引 SSTable 64KB 64KB 图 2-15 SSTable 结构 SSTable 中的数据被划分成一个个的块(Block),每个块的大小是可以设置的,一般 来说设置为 64KB。在 SSTable 的结尾有一个索引(Index),这个索引保存了 SSTable 中 块的位置信息,在 SSTable 打开时这个索引会被加载进内存,这样用户在查找某个块时首 先在内存中查找块的位置信息,然后在硬盘上直接找到这个块,这种查找方法速度非常快 。 由于每个 SSTable 一般都不是很大,用户还可以选择将其整体加载进内存,这样查找起来 31 第 2 章 Google 云计算原理 会更快。 从概念上来讲子表是表中一系列行的集合,它在系统中的实际组成如图 2-16 所示。 64KB 块 块 ... 索引 SSTable 块 块 SSTable 日志 ... ... 索引 64KB 64KB 64KB 图 2-16 子表实际组成 每个子表都是由多个 SSTable 以及日志(Log)文件构成的。有一点需要注意,那就 是不同子表的 SSTable 可以共享,也就是说某些 SSTable 会参与多个子表的构成,而由子 表构成的表则不存在子表重叠的现象。Bigtable 中的日志文件是一种共享日志,也就是说 系统并不是对子表服务器上每个子表都单独地建立一个日志文件,每个子表服务器上仅保 存一个日志文件,某个子表日志只是这个共享日志的一个片段。这样会节省大量的空间, 但在恢复时却有一定的难度,因为不同的子表可能会被分配到不同的子表服务器上,一般 情况下每个子表服务器都需要读取整个共享日志来获取其对应的子表日志。Google 为了避 免这种情况出现,对日志做了一些改进。Bigtable 规定将日志的内容按照键值进行排序, 这样不同的子表服务器都可以连续读取日志文件了。一般来说每个子表的大小在 100MB 到 200MB 之间。每个子表服务器上保存的子表数量可以从几十到上千不等,通常情况下 是 100 个左右。 2.子表地址 子表地址的查询是经常碰到的操作。在 Bigtable 系统的内部采用的是一种类似 B+树 的三层查询体系。子表地址结构如图 2-17 所示[8]。 所有的子表地址都被记录在元数据表中,元数据表也是由一个个的元数据子表 (Metadata tablet)组成的。根子表是元数据表中一个比较特殊的子表,它既是元数据表 的第一条记录,也包含了其他元数据子表的地址,同时 Chubby 中的一个文件也存储了这 个根子表的信息。这样在查询时,首先从 Chubby 中提取这个根子表的地址,进而读取 Chubby 文件 根子表 (元数据表中第一条记录) ... … … … . . . ... ... . . . ... ... . . . 用户表 1 用户表 N 其他元数据子表 图 2-17 子表地址结构 32 3 4 云计算 所需的元数据子表的位置,最后就可以从元数据子表中找到待查询的子表。除了这些子 表的元数据之外,元数据表中还保存了其他一些有利于调试和分析的信息,比如事件日 志等。 为了减少访问开销,提高客户访问效率,Bigtable 使用了缓存(Cache)和预取 (Prefetch)技术,这两种技术手段在体系结构设计中是很常用的。子表的地址信息被缓 存在客户端,客户在寻址时直接根据缓存信息进行查找。一旦出现缓存为空或缓存信息过 时的情况,客户端就需要按照图 2-17 所示方式进行网络的来回通信(Network Round- trips)进行寻址,在缓存为空的情况下需要三个网络来回通信。如果缓存的信息是过时的, 则需要六个网络来回通信。其中三个用来确定信息是过时的,另外三个获取新的地址。预 取则是在每次访问元数据表时不仅仅读取所需的子表元数据,而是读取多个子表的元数据 , 这样下次需要时就不用再次访问元数据表。 3.子表数据存储及读写操作 在数据的存储方面 Bigtable 做出了一个非常重要的选择,那就是将数据存储划分成两 块。较新的数据存储在内存中一个称为内存表(Memtable)的有序缓冲里,较早的数据则 以 SSTable 格式保存在 GFS 中。这种技术在数据库中不是很常用,但 Google 还是做出了 这种选择,实际运行的效果也证明 Google 的选择虽然大胆却是正确的。 从图 2-18[8]中可以看出读和写操作有很大的差异性。做写操作(Write Op)时,首先 查询 Chubby 中保存的访问控制列表确定用户具有相应的写权限,通过认证之后写入的数 据首先被保存在提交日志(Commit Log)中。提交日志中以重做记录(Redo Record)的 形式保存着最近的一系列数据更改,这些重做记录在子表进行恢复时可以向系统提供已完 成的更改信息。数据成功提交之后就被写入内存表中。在做读操作(Read Op)时,首先 还是要通过认证,之后读操作就要结合内存表和 SSTable 文件来进行,因为内存表和 SSTable 中都保存了数据。 在数据存储中还有一个重要问题,就是数据压缩的问题。内存表的空间毕竟是很有限 的,当其容量达到一个阈值时,旧的内存表就会被停止使用并压缩成 SSTable 格式的文件。 在 Bigtable 中有三种形式的数据压缩,分别是次压缩(Minor Compaction)、合并压缩 (Merging Compaction)和主压缩(Major Compaction)。三者之间的关系如图 2-19 所示。 内存表 写操作 读操作 子表日志 内存 GFS SSTable 文件 图 2-18 Bigtable 数据存储及读写操作 33 第 2 章 Google 云计算原理 SSTable SSTable 内存表 SSTable 内存表 内存表 次压缩 次压缩 . . . . . . . . SSTable SSTable 合并压缩 . . . . SSTable 主压缩 图 2-19 三种形式压缩之间的关系 每一次旧的内存表停止使用时都会进行一个次压缩操作,这会产生一个 SSTable。但 如果系统中只有这种压缩的话,SSTable 的数量就会无限制地增加下去。由于读操作要使 用 SSTable,数量过多的 SSTable 显然会影响读的速度。而在 Bigtable 中,读操作实际上比 写操作更重要,因此 Bigtable 会定期地执行一次合并压缩的操作,将一些已有的 SSTable 和现有的内存表一并进行一次压缩。主压缩其实是合并压缩的一种,只不过它将所有的 SSTable 一次性压缩成一个大的 SSTable 文件。主压缩也是定期执行的,执行一次主压缩 之后可以保证将所有的被压缩数据彻底删除,如此一来,既回收了空间又能保证敏感数据 的安全性(因为这些敏感数据被彻底删除了)。 2.4.6 性能优化 上述各种操作已经可以实现 Bigtable 的所有功能了,但是这些基本的功能很多时候并 不是很符合用户的使用习惯,或者执行的效率较低。有些功能 Bigtable 自身已经进行了优 化,包括使用缓存、共享式的提交日志以及利用系统的不变性。这些手段在前面已经有了 简单的介绍,这里不再讲解。除此之外,Bigtable 还允许用户个人在基本操作基础上对系 统进行一些优化。这一部分主要向读者介绍用户可以使用的几个重要优化措施。实际上这 些技术手段都是一些已有的数据库方法,只不过 Google 将它具体地应用于 Bigtable 之中罢 了。 1.局部性群组(Locality groups) Bigtable 允许用户将原本并不存储在一起的数据以列族为单位,根据需要组织在一个 单独的 SSTable 中,以构成一个局部性群组。这实际上就是数据库中垂直分区技术的一个 应用。结合图 2-13 的实例来看,在被 Bigtable 保存的网页列关键字中,有的用户可能只对 网页内容感兴趣,那么它可以通过设置局部性群组只看内容这一列。有的则会对诸如网页 语言、网站排名等可以用于分析的信息比较感兴趣,他也可以将这些列设置到一个群组中 。 局部性群组如图 2-20 所示。 34 3 4 云计算 内容 语言 排名 SSTable SSTable com.cnn.www 图 2-20 局部性群组 通过设置局部性群组用户可以只看自己感兴趣的内容,对某个用户来说的大量无用信 息无需读取。对于一些较小的且会被经常读取的局部性群组,用户可以将其 SSTable 文件 直接加载进内存,这可以明显地改善读取效率。 2.压缩 压缩可以有效地节省空间,Bigtable 中的压缩被应用于很多场合。首先压缩可以被用 在构成局部性群组的 SSTable 中,可以选择是否对个人的局部性群组的 SSTable 进行压缩。 Bigtable 中这种压缩是对每个局部性群组独立进行的,虽然这样会浪费一些空间,但是在 需要读时解压速度非常快。通常情况下,用户可以采用两步压缩的方式 [8]:第一步利用 Bentley & McIlroy 方式(BMDiff)在大的扫描窗口将常见的长串进行压缩;第二步采取 Zippy 技术进行快速压缩,它在一个 16KB 大小的扫描窗口内寻找重复数据,这个过程非 常快。压缩技术还可以提高子表的恢复速度,当某个子表服务器停止使用后,需要将上面 所有的子表移至另一个子表服务器来恢复服务。在转移之前要进行两次压缩,第一次压缩 减少了提交日志中的未压缩状态,从而减少了恢复时间。在文件正式转移之前还要进行一 次压缩,这次压缩主要是将第一次压缩后遗留的未压缩空间进行压缩。完成这两步之后压 缩的文件就会被转移至另一个子表服务器。 3.布隆过滤器(Bloom Filter) Bigtable 向用户提供了一种称为布隆过滤器[12]的数学工具。布隆过滤器是巴顿·布隆在 1970 年提出的,实际上它是一个很长的二进制向量和一系列随机映射函数,在读操作中 确定子表的位置时非常有用。布隆过滤器的速度快,省空间。而且它有一个最大的好处是 它绝不会将一个存在的子表判定为不存在。不过布隆过滤器也有一个缺点,那就是在某些 情况下它会将不存在的子表判断为存在。不过这种情况出现的概率非常小,跟它带来的巨 大好处相比这个缺点是可以忍受的。 目前包括 Google Analytics、Google Earth、个性化搜索、Orkut 和 RRS 阅读器在内的 几十个项目都使用了 Bigtable。这些应用对 Bigtable 的要求以及使用的集群机器数量都是 各不相同的,但是从实际运行来看,Bigtable 完全可以满足这些不同需求的应用,而这一 切都得益于其优良的构架以及恰当的技术选择。与此同时 Google 还在不断地对 Bigtable 进 行一系列的改进,通过技术改良和新特性的加入提高系统运行效率及稳定性。 35 第 2 章 Google 云计算原理 参考文献 [1] Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google File System, Proceedings of 19th ACM Symposium on Operating Systems Principles, 2003, 20-43 [2] Sun “Lustre Networking: High-Performance Features and Flexible Support for a Wide Array of Networks” https://www.sun.com/offers/details/lustre_networking.xml [3] Soltis, Steven R; Erickson, Grant M; Preslan, Kenneth W (1997), “The Global File System: A File System for Shared Disk Storage”, IEEE Transactions on Parallel and Distributed Systems [4] Schmuck, Frank; Roger Haskin (January 2002). "GPFS: A Shared-Disk File System for Large Computing Clusters". Proceedings of the FAST'02 Conference on File and Storage Technologies. Monterey, California, USA [5] Wikipedia. http://zh.wikipedia.org/wiki/MapReduce [6] John Darlington, Yi-ke Guo, Hing Wing To. Structured parallel programming: theory meets practice. Computing tomorrow: future research directions in computer science book contents Pages: 49-65 [7] Jeffrey Dean, Sanjay Ghemawant. MapReduce: Simpli_ed Data Processing on Large Clusters [8] Chang F, Dean J, Ghemawat S, Hsieh WC, Wallach DA, Burrows M, Chandra T, Fikes A, Gruber RE. Bigtable: A distributed storage system for structured data. In: Proc. of the 7th USENIX Symp. on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2006. 205-218 [9] Ghemawat S, Gobioff H, Leung ST. The Google file system. In: Proc. of the 19th ACM Symp. on Operating Systems Principles. New York: ACM Press, 2003. 29-43 [10] Burrows M. The chubby lock service for loosely-coupled distributed systems. In: Proc. of the 7th USENIX Symp. on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2006. 335-350 [11] 陈康,郑纬民. 云计算:系统实例与研究现状。软件学报,2009,20(5):1337-1348 [12] BLOOM, B. H. Space/time trade-offs in hash coding with allowable errors. CACM 13, 7 (1970), 422-426 [13] BURROWS, M. The Chubby lock service for loosely-coupled distributed systems. In Proc. of the 7th OSDI,Nov, 2006 [14] LAMPORT, L. The part-time parliament. ACM TOCS 16,2 (1998), 133-169 [15] LAMPORT, L. Paxos made simple. ACM SIGACT News 32, 4 (2001), 18-25
还剩34页未读

继续阅读

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

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

需要 10 金币 [ 分享pdf获得金币 ] 1 人已下载

下载pdf

pdf贡献者

cellcomcn

贡献于2012-09-20

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf