云计算第三版Google云计算原理与应用讲义.ppt

le云计算原理与应用,目,录,2.1 Google,文件系统,GFS,2.2,分布式数据处理,MapReduce,2.3,分布式锁服务,Chubby,2.4,分布式结构化数据表,Bigtable,2.5,分布式存储系统,Megastore,2.6,大规模分布式系统的监控基础架构,Dapper,2.7,海量数据的交互式分析工具,Dremel,2.8,内存大数据分析系统,PowerDrill,2.9 Google,应用程序引擎,云计算第三版Google云计算原理与应用,初步了解,Chubby,Chubby,是,Google,设计的提供粗粒度锁服务的一个文件系统，它基于松耦合分布式系统，解决了分布的一致性问题。,通过使用,Chubby,的,锁服务,，用户可以确保数据操作过程中的一致性,Chubby,作为一个稳定的,存储系统,存储包括元数据在内的小数据,Google,内部还使用,Chubby,进行,名字服务,（,Name Server,）,2.3,分布式锁服务,Chubby,云计算第三版Google云计算原理与应用,Paxos算法,Paxos,算法,Leslie Lamport,最先提出的一种基于消息传递（,Messages Passing,）的一致性算法，用于解决,分布式系统中的一致性,问题,分布式系统一致性问题,就是如何保证系统中初始状态相同的各个节点在执行相同的操作序列时，看到的指令序列是完全一致的，并且最终得到完全一致的结果,一个最简单的方案,在分布式系统中设置一个专门节点，在每次需要进行操作之前，系统的各个部分向它发出请求，告诉该节点接下来系统要做什么。该节点接受第一个到达的请求内容作为接下来的操作，这样就能够保证系统只有一个唯一的操作序列,方案存在什么缺陷？,云计算第三版Google云计算原理与应用,Paxos算法,缺陷,专门节点失效，整个系统就很可能出现不一致。为了避免这种情况，在系统中必然要设置多个专门节点，由这些节点来共同决定操作序列,Paxos,算法,proposers,提出决议（,Value,，系统接下来执行的指令）,acceptors,批准决议,learners,获取并使用已经通过的决议,云计算第三版Google云计算原理与应用,2.3,分布式锁服务,Chubby,2.3.1 Paxos,算法,2.3.2 Chubby,系统设计,2.3.3 Chubby,中的,Paxos,2.3.4 Chubby,文件系统,2.3.5,通信协议,2.3.6,正确性与性能,云计算第三版Google云计算原理与应用,Paxos,算法,proposers,acceptors,learners,提出决议,批准决议,获取并使用已经通过的决议,三类节点,决议只有在被,proposers,提出后才能批准,每次只批准一个决议,只有决议确定被批准后,learners,才能获取这个决议,三个条件,2.3,分布式锁服务,Chubby,云计算第三版Google云计算原理与应用,系统的约束条件,p1,：每个,acceptor,只接受它得到的第一个决议。,p2,：一旦某个决议得到通过，之后通过的决议必须和该决议保持一致。,p2a,：一旦某个决议,v,得到通过，之后任何,acceptor,再批准的决议必须是,v,。,p2b,：一旦某个决议,v,得到通过，之后任何,proposer,再提出的决议必须是,v,。,p2c,：如果一个编号为,n,的提案具有值,v,，那么存在一个“多数派”，要么它们中没有谁批准过编号小于,n,的任何提案，要么它们进行的最近一次批准具有值,v,。,为了保证决议的唯一性，,acceptors,也要满足一个约束条件：当且仅当,acceptors,没有收到编号大于,n,的请求时，,acceptors,才批准编号为,n,的提案。,2.3,分布式锁服务,Chubby,云计算第三版Google云计算原理与应用,一个决议分为两个阶段,准备阶段,1,2,批准阶段,proposers,选择一个提案并将它的编号设为,n,将它发送给,acceptors,中的一个“多数派”,acceptors,收到后，如果提案的编号大于它已经回复的所有消息，则,acceptors,将自己上次的批准回复给,proposers,，并不再批准小于,n,的提案。,当,proposers,接收到,acceptors,中的这个“多数派”的回复后，就向回复请求的,acceptors,发送,accept,请求，在符合,acceptors,一方的约束条件下，,acceptors,收到,accept,请求后即批准这个请求。,2.3,分布式锁服务,Chubby,云计算第三版Google云计算原理与应用,2.3,分布式锁服务,Chubby,2.3.1 Paxos,算法,2.3.2 Chubby,系统设计,2.3.3 Chubby,中的,Paxos,2.3.4 Chubby,文件系统,2.3.5,通信协议,2.3.6,正确性与性能,云计算第三版Google云计算原理与应用,5,4,6,Chubby,的设计目标主要有以下几点,高可用性和高可靠性,2,1,3,高扩展性,支持粗粒度的建议性锁服务,服务信息的直接存储,支持通报机制,支持缓存机制,2.3,分布式锁服务,Chubby,云计算第三版Google云计算原理与应用,系统设计目标,Chubby系统设计,高可用性和高可靠性；,首要目标，在保证这一目标的基础上再考虑系统的吞吐量和存储能力,高扩展性；将数据存储在价格较为低廉的,RAM,，支持大规模用户访问文件,支持粗粒度的建议性锁服务；提供这种服务的根本目的是,提高系统的性能,服务信息的直接存储；可直接存储包括元数据、系统参数在内的有关服务信息,支持通报机制；客户可以及时地了解到事件发生,支持缓存机制；通过一致性缓存将常用信息保存在客户端，避免了频繁地访问主服务器,云计算第三版Google云计算原理与应用,Chubby系统设计,Chubby,中还添加了一些新的功能特性；这种设计主要是,考虑到以下几个问题,03,02,01,开发者初期很少考虑系统的一致性，但随着开发进行，问题会变得越来越严重。单独的锁服务可以保证原有系统架构不会发生改变，而使用函数库很可能需要对系统架构做出大幅度的改动,系统中很多事件发生是需要告知其他用户和服务器，使用一个基于文件系统的锁服务可以将这些变动写入文件中。有需要的用户和服务器直接访问这些文件即可，避免因大量系统组件之间事件通信带来系统性能下降,基于锁的开发接口容易被开发者接受。虽然在分布式系统中锁的使用会有很大的不同，但是和一致性算法相比，锁显然被更多的开发者所熟知,云计算第三版Google云计算原理与应用,Chubby系统设计,Paxos,算法实现过程中需要一个,“,多数派,”,就某个值达成一致，本质上就是分布式系统中常见的,quorum,机制,；为保证系统高可用性，需要若干台机器，但使用单独锁服务的话一台机器也能保证这种高可用性,Chubby,设计过程中一些细节问题值得关注：,在,Chubby,系统中采用了建议性的锁而没有采用强制性的锁。两者的根本区别在于,用户访问某个被锁定的文件时，建议性的锁不会阻止访问，而强制性的锁则会阻止访问，实际上这是为了方便系统组件之间的信息交互,另外，,Chubby,还采用了粗粒度（,Coarse-Grained,）锁服务而没有采用细粒度（,Fine-Grained,）锁服务，两者的差异在于持有锁的时间，,细粒度的锁持有时间很短,云计算第三版Google云计算原理与应用,客户端,应用程序,客户端,应用程序,Chubby,程序率,Chubby,程序率,远程过程调用,Chubby,单元的,五个服务器,主服务器,客户端进程,Chubby,的基本架构,在客户这一端每个客户应用程序都有一个,Chubby,程序库（,Chubby Library,），客户端的所有应用都是通过调用这个库中的相关函数来完成的。,服务器一端称为,Chubby,单元，一般是由五个称为副本（,Replica,）的服务器组成的，这五个副本在配置上完全一致，并且在系统刚开始时处于对等地位。,客户端,服务器端,2.3,分布式锁服务,Chubby,云计算第三版Google云计算原理与应用,2.3,分布式锁服务,Chubby,2.3.1 Paxos,算法,2.3.2 Chubby,系统设计,2.3.3 Chubby,中的,Paxos,2.3.4 Chubby,文件系统,2.3.5,通信协议,2.3.6,正确性与性能,云计算第三版Google云计算原理与应用,Chubby中的Paxos,单个,Chubby,副本结构,容错日志,对数据库正确性提供重要支持；一致性由,Paxos,算法保证；副本之间通过特定的,Paxos,协议通信，同时本地文件中保存与,Chubby,中相同的日志数据,容错数据库,快照（,Snapshot,）和记录数据库操作重播日志（,Replay-log,）；每一次的数据库操作最终都将提交至日志中；本地文件中也保存着一份数据库数据副本,Chubby,构建在这个容错的数据库之上，,Chubby,利用这个数据库存储所有的数据。,Chubby,的客户端通过特定的,Chubby,协议和单个的,Chubby,副本进行通信,云计算第三版Google云计算原理与应用,Chubby中的Paxos,容错日志的,API,Content Title,Content Title,Chubby,中,Paxos,算法过程,2,、协调者从客户提交的值中选择一个，,accept,消息广播给所有的副本，其他的副本收到广播后，选择接受或者拒绝这个值，并将决定结果反馈,3,、协调者收到大多数副本接受信息后，认为达到了一致性，接着向相关副本发送一个,commit,消息,1,、选择一副本为协调者（,Coordinator,）,云计算第三版Google云计算原理与应用,Chubby中的Paxos,Chubby,设计者借鉴了,Paxos,的两种解决机制：,给协调者指派序号,或,限制协调者可以选择的值,指派序号的方法,（,1,）在一个有,n,个副本系统中，为每个副本分配一个,id:i,r,，其中,0,i,r,n,-1,。则副本的序号,s=k*n+i,r,，其中,k,的初始值为,0,（,2,）某个副本想成为协调者之后，它就根据规则生成一个比它以前的序号更大的序号（实际上就是提高,k,的值），并将这个序号通过,propose,消息广播给其他所有的副本,（,3,）如果接受到广播的副本发现该序号比它以前见过的序号都大，则向发出广播的副本返回一个,promise,消息，并且承诺不再接受旧的协调者发送的消息。如果大多数副本都返回了,promise,消息，则新的协调者就产生了,限制协调者可以选择的值,Paxos,强制新的协调者必须选择和前任相同的值云计算第三版Google云计算原理与应用,Chubby中的Paxos,Chubby,做了一个重要优化来提高系统效率,在选择某一个副本作为协调者之后就长期不变，此时协调者就被称为主服务器（,Master,）,客户端的数据请求由主服务器完成，,Chubby,保证在一定时间内有且仅有一个主服务器，这个时间就称为主服务器租约期（,Master Lease,）,客户端需要确定主服务器的位置，可向,DNS,发送一个主服务器定位请求，非主服务器的副本将对该请求做出回应,Chubby,对于,Paxos,论文中未提及的一些技术细节进行了补充，所以,Chubby,的实现是基于,Paxos,，但其技术手段更加的丰富，更具有实践性,云计算第三版Google云计算原理与应用,2.3,分布式锁服务,Chubby,2.3.1 Paxos,算法,2.3.2 Chubby,系统设计,2.3.3 Chubby,中的,Paxos,2.3.4 Chubby,文件系统,2.3.5,通信协议,2.3.6,正确性与性能,云计算第三版Google云计算原理与应用,Chubby文件系统,Chubby,系统本质上就是一个,分布式的、存储大量小文件的文件系统,，它所有的操作都是在文件的基础上完成,Chubby,最常用的锁服务中，每一个文件就代表一个锁，用户通过打开、关闭和读取文件，获取共享（,Shared,）锁或独占（,Exclusive,）锁,选举主服务器过程中，符合条件的服务器都同时申请打开某个文件并请求锁住该文件,成功获得锁的服务器自动成为主服务器并将其地址写入这个文件夹，以便其他服务器和用户可以获知主服务器的地址信息,云计算第三版Google云计算原理与应用,Chubby文件系统,Chubby,的文件系统和,UNIX,类似,例如在文件名“,/ls/foo/wombat/pouch”,中，,ls,代表,lock service,，这是所有,Chubby,文件系统的共有前缀；,f,oo,是某个单元的名称；,/wombat/pouch,则是,foo,这个单元上的文件目录或者文件名,Google,对,Chubby,做了一些与,UNIX,不同的改变,例如,Chubby,不支持内部文件的移动；不记录文件的最后访问时间；另外在,Chubby,中并没有符号连接（,Symbolic Link,，又叫软连接，类似于,Windows,系统中的快捷方式）和硬连接（,Hard Link,，类似于别名）的概念,在具体实现时，文件系统由许多节点组成，分为永久型和临时型，每个节点就是一个文件或目录。节点中保存着包括,ACL,（,Access Control List,，访问控制列表）在内的多种系统元数据,云计算第三版Google云计算原理与应用,单调递增的,64,位编号,实例号,Instance Number,新节点实例号必定大于旧节点的实例号。,1,锁生成号,Lock Generation Number,锁被用户持有时该号增加。,内容生成号,Content Generation Number,文件内容修改时该号增加。,2,3,ACL,生成号,ACL Generation Number,ACL,名被覆写时该号增加。,4,2.3,分布式锁服务,Chubby,云计算第三版Google云计算原理与应用,Chubby文件系统,序号：确定句柄由当前还是以前的主服务器创建,2,模式信息：用于新的主服务器重新创建一个旧句柄,3,用户打开某个节点的同时会获取一个类似于,UNIX,中文件描述符（,File Descriptor,）的句柄，这个句柄由以下三个部分组成,校验数位：防止其他用户创建或猜测这个句柄,1,云计算第三版Google云计算原理与应用,Chubby文件系统,在实际执行中，为了避免所有的通信都使用序号带来系统开销增长，,Chubby,引入了,sequencer,的概念,sequencer,实际上就是一个,序号,，只能由锁的持有者在获取锁时向系统发出请求来获得。这样一来,Chubby,系统中只有涉及锁的操作才需要序号，其他一概不用。,在文件操作中，用户可以将句柄看做一个指向文件系统的,指针,函 数 名 称,作 用,Open(),打开某个文件或者目录来创建句柄,Close(),关闭打开的句柄，后续的任何操作都将中止,Poison(),中止当前未完成及后续的操作，但不关闭句柄,GetContentsAndStat(),返回文件内容及元数据,GetStat(),只返回文件元数据,ReadDir(),返回子目录名称及其元数据,SetContents(),向文件中写入内容,SetACL(),设置ACL名称,Delete(),如果该节点没有子节点的话则执行删除操作,Acquire(),获取锁,Release(),释放锁,GetSequencer(),返回一个sequencer,SetSequencer(),将sequencer和某个句柄进行关联,CheckSequencer(),检查某个sequencer是否有效,常用句柄函数及其作用,云计算第三版Google云计算原理与应用,2.3,分布式锁服务,Chubby,2.3.1 Paxos,算法,2.3.2 Chubby,系统设计,2.3.3 Chubby,中的,Paxos,2.3.4 Chubby,文件系统,2.3.5,通信协议,2.3.6,正确性与性能,云计算第三版Google云计算原理与应用,Chubby系统设计,Chubby,基本架构：客户端和服务器端，两者通过远程过程调用（,RPC,）来连接,客户端每个客户应用程序都有一个,Chubby,程序库（,Chubby Library,），所有应用都是通过调用这个库中相关函数来完成,服务器一端,Chubby单元，一般由五个称为副本（,Replica,）服务器组成，它们配置上完全一致，且系统刚开始时处于对等地位,云计算第三版Google云计算原理与应用,Chubby客户端与服务器端的通信过程,从左到右的水平方向表示时间在增加，斜向上的箭头表示一次,KeepAlive,请求，斜向下的箭头则是主服务器的一次回应,M1,、,M2,、,M3,表示不同的,主服务器租约期,；,C1,、,C2,、,C3,则是客户端对主服务器,租约期时长,做出的一个估计,KeepAlive,是周期发送的一种信息，它主要有两方面的功能：,延迟租约的有效期,和,携带事件信息告诉用户更新,云计算第三版Google云计算原理与应用,可能出现的两种故障,2.3,分布式锁服务,Chubby,客户端租约过期,主服务器出错,1,2,云计算第三版Google云计算原理与应用,客户端租约过期故障处理,客户端租约过期,客户端向主服务器发出一个,KeepAlive,请求（上图,1,）,如果有需要通知的事件时则主服务器会立刻做出回应，否则等到客户端的租约期,C1,快结束的时候才做出回应（图,2,），并更新主服务器租约期为,M2,客户端接到回应后认为该主服务器仍处于活跃状态，于是将租约期更新为,C2,并立刻发出新的,KeepAlive,请求（图,3,）,宽限期内，客户端不会立刻断开其与服务器端的联系，而是不断地做探询，当它接到客户端的第一个,KeepAlive,请求（图,4,）时会拒绝（图,5,）,客户端在主服务器拒绝后使用新纪元号来发送,KeepAlive,请求（图,6,）,新的主服务器接受这个请求并立刻做出回应（图,7,）,如果客户端接收到这个回应的时间仍处于宽限期内，系统会恢复到安全状态，租约期更新为,C3,。如果在宽限期未接到主服务器的相关回应，客户端终止当前的会话,云计算第三版Google云计算原理与应用,主服务器出错故障处理,主服务器出错,正常情况下旧的主服务器出现故障后系统会很快地选举出新的主服务器，新选举需要经历以下九个步骤：,（,1,）产生一个新的纪元号以便今后客户端通信时使用，这能保证当前的主服务器不必处理针对旧的主服务器的请求,（,2,）只处理主服务器位置相关的信息，不处理会话相关的信息,（,3,）构建处理会话和锁所需的内部数据结构,（,4,）允许客户端发送,KeepAlive,请求，不处理其他会话相关的信息,（,5,）向每个会话发送一个故障事件，促使所有的客户端清空缓存,（,6,）等待直到所有的会话都收到故障事件或会话终止,（,7,）开始允许执行所有的操作,（,8,）如果客户端使用了旧的句柄则需要为其重新构建新的句柄,（,9,）一定时间段后（,1,分钟），删除没有被打开过的临时文件夹,如果这一过程在宽限期内顺利完成，则用户不会感觉到任何故障的发生，也就是说新旧主服务器的替换对于用户来说是,透明的用户感觉到的仅仅是一个,延迟,云计算第三版Google云计算原理与应用,2.3,分布式锁服务,Chubby,2.3.1 Paxos,算法,2.3.2 Chubby,系统设计,2.3.3 Chubby,中的,Paxos,2.3.4 Chubby,文件系统,2.3.5,通信协议,2.3.6,正确性与性能,云计算第三版Google云计算原理与应用,一致性,2.3,分布式锁服务,Chubby,正确性与性能,每个,Chubby,单元是由五个副本组成的，这五个副本中需要选举产生一个主服务器，这种选举本质上就是一个一致性问题,安全性,采用的是,ACL,形式的安全保障措施。只要不被覆写，子节点都是直接继承父节点的,ACL,名,性能优化,提高主服务器默认的租约期、使用协议转换服务将,Chubby,协议转换成较简单的协议、客户端一致性缓存等,云计算第三版Google云计算原理与应用,一致性,每个,Chubby,单元是由五个副本组成的，这五个副本中需要选举产生一个主服务器，这种选举本质上就是一个一致性问题。实际执行过程中，,Chubby,使用,Paxos,算法,来解决,主服务器产生后客户端的所有读写操作都是由,主服务器,来完成的,读操作很简单，客户直接从主服务器上读取所需数据即可,写操作就会,涉及数据一致性,的问题；为了保证客户的写操作能够同步到所有的服务器上，系统再次利用了,Paxos,算法,云计算第三版Google云计算原理与应用,安全性,Chubby,用,ACL,形式安全保障措施。系统有三种,ACL,名：,写,ACL,名（,Write ACL Name,）、读,ACL,名（,Read ACL Name,）和变更,ACL,名（,Change ACL Name,）,只要不被覆写，子节点都是,直接继承,父节点的,ACL,名,ACL,同样被保存在文件中，它是节点元数据的一部分，用户在进行相关操作时首先需要通过,ACL,来获取相应的,授权,Chubby,的,ACL,机制,用户,chinacloud,提出向文件,CLOUD,中写入内容请求。,CLOUD,首先读取自身的写,ACL,名,fun,，接着在,fun,中查到了,chinacloud,这一行记录，于是返回信息允许,chinacloud,对文件进行写操作，此时,chinacloud,才被允许向,CLOUD,写入内容。其他的操作和写操作类似,云计算第三版Google云计算原理与应用,性能优化,为满足系统高可扩展性，,Chubby,目前已经采取了一些措施：比如提高主服务器默认的租约期、使用协议转换服务将,Chubby,协议转换成较简单的协议、客户端一致性缓存等；除此之外，,Google,的工程师们还考虑使用代理（,Proxy,）和分区（,Partition,）技术,代理,可以减少主服务器处理,KeepAlive,以及读请求带来的服务器负载，但是它并不能减少写操作带来的通信量,使用,分区,技术的话可以将一个单元的命名空间（,Name Space,）划分成,N,份。除了少量的跨分区通信外，大部分的分区都可以独自地处理服务请求。通过分区可以减少各个分区上的读写通信量，但不能减少,KeepAlive,请求的通信量,云计算第三版Google云计算原理与应用,目,录,2.1 Google,文件系统,GFS,2.2,分布式数据处理,MapReduce,2.3,分布式锁服务,Chubby,2.4,分布式结构化数据表,Bigtable,2.5,分布式存储系统,Megastore,2.6,大规模分布式系统的监控基础架构,Dapper,2.7海量数据的交互式分析工具,Dremel,2.8,内存大数据分析系统,PowerDrill,2.9 Google,应用程序引擎,云计算第三版Google云计算原理与应用,2.4,分布式结构化数据表,Bigtable,2.4.1,设计动机与目标,2.4.2,数据模型,2.4.3,系统架构,2.4.4,主服务器,2.4.5,子表服务器,2.4.6,性能优化,云计算第三版Google云计算原理与应用,2.4,分布式结构化数据表,Bigtable,Bigtable,的设计动机,1,2,3,需要存储,的数据种类繁多,海量的,服务请求,商用数据库,无法满足需求,包括,URL,、网页内容、用户的个性化设置在内的数据都是,Google,需要经常处理的,Google,运行着目前世界上最繁忙的系统，它每时每刻处理的客户服务请求数量是普通的系统根本无法承受的,一方面现有商用数据库的设计着眼点在于其通用性。,另一方面对于底层系统的完全掌控会给后期的系统维护、升级带来极大的便利,云计算第三版Google云计算原理与应用,2.4,分布式结构化数据表,Bigtable,Bigtable,应达到的基本目标,广泛的适用性,很强的可扩展性,高可用性,简单性,Bigtable,是为了满足一系列,Google,产品而并非特定产品的存储要求。,根据需要随时可以加入或撤销服务器,确保几乎所有的情况下系统都可用,底层系统的简单性既可以减少系统出错的概率，也为上层应用的开发带来便利,云计算第三版Google云计算原理与应用,2.4,分布式结构化数据表,Bigtable,2.4.1,设计动机与目标,2.4.2,数据模型,2.4.3,系统架构,2.4.4,主服务器,2.4.5,子表服务器,2.4.6,性能优化,云计算第三版Google云计算原理与应用,Bigtable,数据的存储格式,2.4,分布式结构化数据表,Bigtable,Bigtable,是一个分布式多维映射表，表中的数据通过一个行关键字（,Row Key,）、一个列关键字（,Column Key,）以及一个时间戳（,Time Stamp,）进行索引,Bigtable,的存储逻辑可以表示为：,(row:string,column:string,time:int64)string,Bigtable,对存储在其中的数据不做任何解析，一律看做字符串,云计算第三版Google云计算原理与应用,Bigtable,数据的存储格式,2.4,分布式结构化数据表,Bigtable,假设想要拷贝一个可能被很多项目都,使用,的、很大的网页集合以及相关的信息，把这个特定的表称为,Webtable,。在,Webtable,当中，使用,URL,作为行键，网页的不同方面作为列键，并把网页的内容存储在,contents:column,中，如图所示,图存储了网页数据的,Webtable,的一个片段。行名称是反转的,URL,，,contents,列家族包含了网页内容，,anchor,列家族包含了任何引用这个页面的,anchor,文本。,CNN,的主页被,Sports Illustrated,和,MY-look,主页同时引用，因此，行包含了名称为”,anchor:”,和”,anchor:my.look.ca”,的列。每个,anchor,单元格都只有一个版本，,contents,列有三个版本，分别对应于时间戳,t3,t5,和,t6,。,云计算第三版Google云计算原理与应用,数据模型,行,Bigtable,的行关键字可以是任意的字符串，但是大小不能超过,64KB,。,Bigtable,和传统的关系型数据库有很大不同，它不支持一般意义上的事务，但能保证对于行的读写操作具有原子性（,Atomic,）,表中数据都是根据行关键字进行排序的，排序使用的是词典序。,一个典型实例，其中,n.www,就是一个行关键字。不直接存储网页地址而将其倒排是,Bigtable,的一个巧妙设计。这样做至少会带来以下两个好处,同一地址域的网页会被存储在表中的连续位置，有利于用户查找和分析,倒排便于数据压缩，可以大幅提高压缩率,云计算第三版Google云计算原理与应用,数据模型,列,Bigtable,并不是简单地存储所有的列关键字，而是将其组织成所谓的列族（,Column Family,），每个族中的数据都属于同一个类型，并且同族的数据会被压缩在一起保存。引入了列族的概念之后，列关键字就采用下述的语法规则来定义：,族名：限定词（,family,：,qualifier,）,族名必须有意义，限定词则可以任意选定,图中，内容（,Contents,）、锚点（,Anchor,）都是不同的族。而,和,my.look.ca,则是锚点族中不同的限定词,族同时也是,Bigtable,中访问控制（,Access Control,）基本单元，也就是说访问权限的设置是在族这一级别上进行的,云计算第三版Google云计算原理与应用,数据模型,时间戳,Google,的很多服务比如网页检索和用户的个性化设置等都需要保存不同时间的数据，这些不同的数据版本必须通过时间戳来区分。图,2,中内容列的,t3,、,t5,和,t6,表明其中保存了在,t3,、,t5,和,t6,这三个时间获取的网页。,Bigtable,中的时间戳是,64,位整型数，具体的赋值方式可以采取系统默认的方式，也可以用户自行定义,为了简化不同版本的数据管理，,Bigtable,目前提供了两种设置：一种是保留最近的,N,个不同版本，图中数据模型采取的就是这种方法，它保存最新的三个版本数据。另一种就是保留限定时间内的所有不同版本，比如可以保存最近,10,天的所有不同版本数据。失效的版本将会由,Bigtable,的垃圾回收机制自动处理,云计算第三版Google云计算原理与应用,2.4,分布式结构化数据表,Bigtable,2.4.1,设计动机与目标,2.4.2,数据模型,2.4.3,系统架构,2.4.4,主服务器,2.4.5,子表服务器,2.4.6,性能优化,云计算第三版Google云计算原理与应用,Bigtable,基本架构,2.4,分布式结构化数据表,Bigtable,云计算第三版Google云计算原理与应用,2.4,分布式结构化数据表,Bigtable,Bigtable,中,Chubby,的主要作用,作用一,选取并保证同一时间内只有一个主服务器（,Master Server,）。,获取子表的位置信息。,保存,Bigtable,的模式信息及访问控制列表。,作用二,作用三,云计算第三版Google云计算原理与应用,系统架构,Bigtable,主要由三个部分组成：客户端程序库（,Client Library,）、一个主服务器（,Master Server,）和多个子表服务器（,Tablet Server,）,客户访问,Bigtable,服务时，首先要利用其库函数执行,Open(),操作来打开一个锁（,实际上就是获取了文件目录,），锁打开以后客户端就可以和子表服务器进行通信,和许多具有单个主节点分布式系统一样，客户端主要与子表服务器通信，几乎不和主服务器进行通信，这使得主服务器的负载大大降低,主服务主要进行一些元数据操作以,及子表服务器之间负载调度问题，,实际数据是存储在子表服务器上,云计算第三版Google云计算原理与应用,2.4,分布式结构化数据表,Bigtable,2.4.1,设计动机与目标,2.4.2,数据模型,2.4.3,系统架构,2.4.4,主服务器,2.4.5,子表服务器,2.4.6,性能优化,云计算第三版Google云计算原理与应用,2.4,分布式结构化数据表,Bigtable,主服务器,新子表分配,子表服务器状态监控,子服务器之间的负载均衡,当一个新的子表产生时，主服务器通过一个加载命令将其分配给一个空间足够的子表服务器。,创建新表、表合并以及较大子表的分裂都会产生一个或多个新子表。,分割完成之后子服务器需要向主服务发出一个通知。,主服务器必须对子表服务器的状态进行,监控,，以便及时检测到服务器的加入或撤销,云计算第三版Google云计算原理与应用,主服务器,Bigtable,中主服务表服务器的,监控,是通过,Chubby,完成的,子表服务器在初始化时都会从,Chubby,中得到一器对子个独占锁。通过这种方式所有子表服务器基本信息被保存在,Chubby,中一个称为,服务器目录,（,Server Directory,）的特殊目录之中。,主服务器通过这个目录可以随时获取最新的子表服务器信息，包括：,目前活跃的子表服务器；,每个子表服务器上现已分配的子表。,云计算第三版Google云计算原理与应用,主服务器,对于每个具体的子表服务器，主服务器会定期向其询问独占锁的状态。如果子表服务器的锁丢失或没有回应，则此时可能有两种情况：,要么是,Chubby,出现了问题,（虽然这种概率很小，但的确存在，,Google,自己也做过相关测试）,要么是,子表服务器自身出现了问题,。对此主服务器首先自己尝试获取这个独占锁，如果失败说明,Chubby,服务出现问题，需等待恢复；如果成功则说明,Chubby,服务良好而子表服务器本身出现了问题,当在状态监测时发现某个子表服务器上负载过重时，主服务器会自动对其进行负载均衡操作,云计算第三版Google云计算原理与应用,主服务器,基于系统出现故障是一种常态的设计理念，每个主服务器被设定了一个会话时间的限制。当某个主服务器到时退出后，管理系统就会指定一个新的主服务器，这个主服务器的启动需要经历以下四个步骤,：,云计算第三版Google云计算原理与应用,2.4,分布式结构化数据表,Bigtable,从,Chubby,中获取一个独占锁，确保同一时间只有一个主服务器,Bigtable,中,Chubby,的主要作用,扫描服务器目录，发现目前活跃的子表服务器,与所有的活跃子表服务器取得联系以便了解所有子表的分配情况,通过扫描元数据表（,Metadata Table,），发现未分配的子表并将其分配到合适的子表服务器,步骤,1,步骤,3,步骤,2,步骤,4,如果元数据表未分配，则首先需要将根子表（,Root Tablet,）加入未分配的子表中。由于根子表保存了其他所有元数据子表的信息，确保了扫描能够发现所有未分配的子表,云计算第三版Google云计算原理与应用,2.4,分布式结构化数据表,Bigtable,2.4.1,设计动机与目标,2.4.2,数据模型,2.4.3,系统架构,2.4.4,主服务器,2.4.5,子表服务器,2.4.6,性能优化,云计算第三版Google云计算原理与应用,SSTable,及子表基本结构,SSTable,是,Google,为,Bigtable,设计的,内部数据存储格式,。,所有的,SSTable,文件都存储在,GFS,上,SSTable,结构,子表实际组成,每个子表都是由,多个,SSTable,以及日志（,Log,）文件,构成,不同子表的,SSTable,可以,共享,SSTable,中数据被划分成一个个的,块,（,Block,），每个块的大小是可以设置的，一般为,64KB,在,SSTable,的结尾有一个,索引,（,Index,），这个索引保存了块的位置信息，在,SSTable,打开时这个索引会被加载进内存，用户在查找某个块时首先在内存中查找块的,位置信息,，然后在硬盘上直接找到这个块,由于每个,SSTable,一般都不是很大，用户还可以选择将其,整体加载进内存,，这样查找起来会更快,Bigtable,中的日志文件是一种,共享日志,，每个子表服务器上仅保存一个日志文件，某个子表日志只是这个共享日志的,一个片段,。这样会,节省大量的空间,，但在恢复时却有,一定的难度,Google,为了避免这种情况出现，对日志做了一些改进。,Bigtable,规定将日志的内容按照,键值进行排序,，这样不同的子表服务器都可以连续读取日志文件了,一般来说每个子表的大小在,100MB,到,200MB,之间。每个子表服务器上保存的子表数量可以从几十到上千不等，通常情况下是,100,个左右,云计算第三版Google云计算原理与应用,64KB,块,64KB,块,SSTable,索引,SSTable,格式的基本示意,2.4,分布式结构化数