从今天始，开始相对专一地先学完刘鹏教授的《云计算》这本书，本想写些自己的笔记的，但已觉得其相应配套的PPT上面的已经够精简了，所以，这里的笔记，其实只是相当于自己的笔记本，方便自己以后到这个固定地方查找吧。

为了简洁（甚至说可以直接按PPT上提纲来吧）：

1、什么是云计算

云计算是一种商业模式，它是在高可靠性、高自动化（不自动化，那么对于如此大规模的机器来说，其管理那就更是累人不偿命的事啦）和高可用性的计算资源和设备(更专业一点的，叫计算中心)的支撑下，人们只要接入互联网，就能非常方便地访问各种基于云的应用和信息，并免去了安装、维护等烦琐操作(甚至包括可以自定制自己喜欢的模式、特色）

云计算是一种商业计算模型。它将计算任务分布在大量计算机构成的资源池上，使各种应用系统能够根据需要获取计算力、存储空间和信息服务。

云计算特点：

• 超大规模
• 虚拟化
• 高可靠性
• 通用性
• 高可伸缩性
• 按需服务
• 极其廉价

2、云计算的发展现状（略）

3、云计算的体系结构（略）

4、云计算与网格计算

网格计算——在动态、多机构参与的虚拟组织中协同共享资源和求解问题

网格计算与云计算的关系，就像是OSI与TCP/IP之间的关系——这个例比应该算比较精确

云计算是网格计算的一种简化形态，网格不仅要集成异构资源，还要解决许多非技术的协调问题，也不像云计算有成功的商业模式推动，所以实现起来要比云计算难度大很多。但对于许多高端科学或军事应用而言，云计算是无法满足需求的，必须依靠网格来解决。

不久的将来，建立在云计算之上的“商业2.0”与建立在网格计算之上的“科学2.0”都将取得成功。

——Gloud（云格）=Grid+Cloud1,这也许将来的发展走向

网格技术主要解决分布在不同机构的各种信息资源的共享问题，而云计算主要解决计算力和存储空间的集中共享使用问题。

5、云计算的发展环境

3G与云计算是互相依存、互相促进的关系

J3G将为云计算带来数以亿计的宽带移动用户。用户的终端计算能力和存储空间有限，却有很强的联网能力，对云计算有着天然的需求

J云计算能够给3G用户提供更好的用户体验。云计算有强大的计算能力、接近无限的存储空间，并支撑各种各样的软件和信息服务，能够为3G用户提供前所未有的服务体验

移动互联网和云计算是相辅相成的

通过云计算技术，软硬件获得空前的集约化应用

移动互联网时代来临，对用户来讲，最好的体验是淡化有线和无线的概念。云计算有望突破各种终端，显示的内容、应用都能保持一致性和同步性

云计算对于云和端两侧都具有传统模式不可比拟的优势

三网融合为云计算提供切实的应用机会

a云计算技术使得一些从事传统行业的企业也能搭上三网融合和下一代广电网的快车

a云计算在三网融合及下一代广电网中的应用，涉及数据存储、数据计算、数据再处理、软件开发、数据传输、网络协同等多个方面

Google的云计算原理与应用（GFS和MapReduce）

Google业务

全球最大搜索引擎、Google Maps、Google Earth、Gmail、YouTube等——特点：数据量庞大、面向全球用户提供实时服务

Google云计算平台技术架构

￠文件存储，Google Distributed File System，GFS

￠并行数据处理MapReduce

￠分布式锁Chubby

￠分布式结构化数据表BigTable

￠分布式存储系统Megastore

￠分布式监控系统Dapper

一、Google文件系统GFS

分三大块来讲的，系统架构、容错机制、系统管理技术

1、系统架构

Client（客户端）：应用程序的访问接口

Master（主服务器）：管理节点，在逻辑上只有一个，保存系统的元数据，负责整个文件系统的管理

ChunkServer（数据块服务器）：负责具体的存储工作。数据以文件的形式存储在ChunkServer上
关于上面的架构图之前看到过一篇博客，上面对其机架感知(Rack Awareness)机制有一个简单的表示，很可惜博客竟未找到，大致是：

对于Rack Awareness——Rack1:Chunk1 、Chunk4、Chunk7……Rack n:Chunk2、Chunk 5、Chunk6……

而对于ns:file——Chunk1、Chunk2……

这样，两者一结合，查找文件块、甚至对相对的查找的优化等比较方便

GFS特点：

采用中心服务器模式

u可以方便地增加Chunk Server

u Master掌握系统内所有Chunk Server的情况，方便进行负载均衡

u不存在元数据的一致性问题

不缓存数据

文件操作大部分是流式读写，不存在大量重复读写，使用Cache对性能提高不大

Chunk Server上数据存取使用本地文件系统，若读取频繁，系统具有Cache

从可行性看，Cache与实际数据的一致性维护也极其复杂

在用户态下实现

¨利用POSIX编程接口存取数据降低了实现难度，提高通用性

¨POSIX接口提供功能更丰富

¨用户态下有多种调试工具

¨Master和Chunk Server都以进程方式运行，单个进程不影响整个操作系统

¨GFS和操作系统运行在不同的空间，两者耦合性降低

只提供专用接口

￠降低实现的难度

￠对应用提供一些特殊支持

￠降低复杂度

2、容错机制

Master容错

Name Space，文件系统目录结构

Chunk与文件名的映射

Chunk副本的位置信息(默认有三个副本)

单个Master，对于前两种元数据，GFS通过操作日志来提供容错功能

第三种元数据信息保存在各个ChunkServer上，Master故障时，磁盘恢复

GFS还提供了Master远程的实时备份,防止Master彻底死机的情况

Chunk Server容错

u采用副本方式实现Chunk Server容错

¨每一个Chunk有多个存储副本（默认为三个），分布存储在不同的Chunk Server上用户态的GFS不会影响Chunk Server的稳定性

¨副本的分布策略需要考虑多种因素，如网络的拓扑、机架的分布、磁盘的利用率等

¨对于每一个Chunk，必须将所有的副本全部写入成功，才视为成功写入

尽管一份数据需要存储三份，好像磁盘空间的利用率不高，但综合比较多种因素，加之磁盘的成本不断下降，采用副本

无疑是最简单、最可靠、最有效，而且实现的难度也最小的一种方法。

¨ GFS中的每一个文件被划分成多个Chunk，Chunk的默认大小是64MB

¨Chunk Server存储的是Chunk的副本，副本以文件的形式进行存储

¨ 每个Chunk又划分为若干Block（64KB），每个Block对应一个32bit的校验码，保证数据正确（若某个Block错误， 则转移至其他Chunk副本）

系统管理技术

二、分布式数据处理MapReduce

1、产生背景

MapReduce

• 一种处理海量数据的并行编程模式，用于大规模数据集（通常大于1TB）的并行运算。
• “Map（映射）”、“Reduce（化简）”的概念和主要思想，都是从函数式编程语言( 适合于结构化和非结构化的海量数据的搜索、挖掘、分析与机器智能学习等)和矢量编程语言借鉴

u计算问题简单，但求解困难

–待处理数据量巨大（PB级），只有分布在成百上千个节点上并行计算才能在可接受的时间内完成

–如何进行并行分布式计算？

–如何分发待处理数据？

–如何处理分布式计算中的错误？

JefferyDean设计一个新的抽象模型，封装并行处理、容错处理、本地化计算、负载均衡的细节，还提供了一个简单而强大的接口这就是MapReduce

2、编程模型

怎么用MapReduce计算一个大型文本文件中各单词出现次数？Map的输入参数指明了需要处理哪部分数据，以“<在文本中的起始位置，需要处理的数据长度>”表示，经过Map处理，形成一批中间结果“<单词，出现次数>”。而Reduce函数处理中间结果，将相同单词出现的次数进行累加，得到每个单词总的出现次数3、实现机制

操作过程

（1）输入文件分成M块，每块大概16M～64MB（可以通过参数决定），接着在集群的机器上执行分派处理程序

（2）M个Map任务和R个Reduce任务需要分派，Master选择空闲Worker来分配这些Map或Reduce任务

（3）Worker读取并处理相关输入块，Map函数产生的中间结果<key,value>对暂时缓冲到内存

（4）中间结果定时写到本地硬盘，分区函数将其分成R个区。中间结果在本地硬盘的位置信息将被发送回Master，然后Master负责把这些位置信息传送给ReduceWorker

（5）当Master通知执行Reduce的Worker关于中间<key,value>对的位置时，它调用远程过程，从MapWorker的本地硬盘上读取缓冲的中间数据。当Reduce Worker读到所有的中间数据，它就使用中间key进行排序，这样可使相同key的值都在一起

（6）Reduce Worker根据每一个唯一中间key来遍历所有的排序后的中间数据，并且把key和相关的中间结果值集合传递给用户定义的Reduce函数。Reduce函数的结果写到一个最终的输出文件

（7）当所有的Map任务和Reduce任务都完成的时候，Master激活用户程序。此时MapReduce返回用户程序的调用点个区本地硬盘的位置信息将被发送回Master，然后Master负责把这些位置信息传送给ReduceWorker

案例分析假设有一批海量的数据，每个数据都是由26个字母组成的字符串，原始的数据集合是完全无序的，怎样通过MapReduce完成排序工作，使其有序（字典序）呢？ ——排序通常用于衡量分布式数据处理框架的数据处理能力

Google的云计算原理与应用(分布式锁服务——Chubby)

一、分布式锁服务

今天，要接触有些难理解的知识点了，这也许就是涉及到当时赵致琢老师强调的在中国没人能有资格讲和讲得清的一块—分布式算法。说实话，这块看了两遍了，到现在还不敢说自己人懂了一半啊·！

Chubby

• Google设计的提供粗粒度锁服务(???)的一个文件系统，它基于松耦合分布式系统，解决了分布的一致性问题 ——一种建议性的锁(相信看过《UNIX环境下高级编程》的人对建议性的锁这个名词不会陌生)，而不是一种强制性的锁：具有更大的灵活性
• GFS使用Chubby选取一个GFS主服务器
• Bigtable使用Chubby指定一个主服务器并发现、控制与其相关的子表服务器
• Chubby还可以作为一个稳定的存储系统存储包括元数据在内的小数据
• Google内部还使用Chubby进行名字服务（Name Server）

想像一下，要在大规模集群的条件下，保证所有指令和数据的一致性（即：在初始状态相同情况下，要求各结点接收到同样相同指令，且最终状态一致）会遇到什么样的困难？——这也许正是分布式算法要发挥作用的境地，很多时候设计的算法根本不可能会是十全十美。Chubby中即要用到Paxos算法

1、Paxos算法

试想想：该方案存在什么缺陷？？？？

试图由以下三点来保证数据的一致性:

（1）决议只有被proposers提出后才能批准

（2）每次只批准一个决议

（3）只有决议确定被批准后learners才能获取这个决议

系统的约束条件：

p1:每个acceptor只接受它得到的第一个决议

p1表明每个可以接收到多个决议，为区分，对每个决议进行编号，后得到的决议编号要大于先到的编号；p1不是很完备!!(??一个问题可能是：对于每个结点，其收到的所谓第一个编号是否都是一样？？)

P2：一旦某个决议通过，之后通过的决议必须和该决议保持一致

P1+P2——>P2a:一旦某个决议V得到通过，之后任何acceptor再批准的决议必须是V

P2a和P1是有矛盾的!(我的理解是：有可能这个V不是某个结点收到的第一个决议)

P2a——》P2b:一旦某个决议V得到通过，之后任何proposer再提出的决议必须是V

P1和P2b保证条件（2），彼此之间不存在矛盾。但是P2b很难通过一种技术手段来实现它，因此提出了一个蕴涵P2b的约束P2c

P2b——》P2c:如果一个编号为n的提案具有值v，那么存在一个“多数派”，要么它们中没有谁批准过编号小于n的任何提案，要么它们进行的最近一次批准具有值v

决议通过的两个阶段：

准备阶段：proposers选择一个提案并将它的编号设为n，然后将它发送给acceptors中的一个“多数派”。Acceptors收到后，如果提案的编号大于它已经回复的所有消息，则acceptors将自己上次的批准回复给proposers，并不再批准小于n的提案 （那么，可以问问：如果小于它已经回复的所有消息呢？这个思考之后，对算法的流程就有个印象——但似乎这样一想，这中间的延迟倒很是个问题，看来，这个算法还是未弄懂！！）

批准阶段：当proposers接收到acceptors 中的这个“多数派”的回复后，就向回复请求的acceptors发送accept请求，在符合acceptors一方的约束条件下，acceptors收到accept请求后即批准这个请求

解决一致性问题算法：为了减少决议发布过程中的消息量，acceptors将这个通过的决议发送给learners的一个子集，然后由这个子集中的learners去通知所有其他的learners；
特殊情况：如果两个proposer在这种情况下都转而提出一个编号更大的提案，那么就可能陷入活锁。此时需要选举出一个president，仅允许 president提出提案

2、Chubby的系统设计

Chubby中还添加了一些新的功能特性；这种设计主要是考虑到以下几个问题:

1、开发者初期很少考虑系统的一致性，但随着开发进行，问题会变得越来越严重。单独的锁服务可以保证原有系统架构不会发生改变，而使用函数库很可能需要对系统架构做出大幅度的改动

2、系统中很多事件发生是需要告知其他用户和服务器，使用一个基于文件系统的锁服务可以将这些变动写入文件中。有需要的用户和服务器直接访问这些文件即可，避免因大量系统组件之间事件通信带来系统性能下降

3、基于锁的开发接口容易被开发者接受。虽然在分布式系统中锁的使用会有很大的不同，但是和一致性算法相比，锁显然被更多的开发者所熟知

Paxos算法实现过程中需要一个“多数派”就某个值达成一致，本质上就是分布式系统中常见的quorum机制；为保证系统高可用性，需要若干台机器，但使用单独锁服务的话一台机器也能保证这种高可用性

Chubby设计过程中一些细节问题值得关注：

在Chubby系统中采用了建议性的锁而没有采用强制性的锁。两者的根本区别在于用户访问某个被锁定的文件时，建议性的锁不会阻止访问，而强制性的锁则会阻止访问，实际上这是为了方便系统组件之间的信息交互

另外，Chubby还采用了粗粒度（Coarse-Grained）锁服务而没有采用细粒度（Fine-Grained）锁服务，两者的差异在于持有锁的时间，细粒度的锁持有时间很短

3、Chubby中的Paxos算法

(个人疑问：从上面来看，似乎上面给我们的启发是——我们无需在整个系统的每个环节保持数据和指令的一致性，只需其操作日志是一致，那么说明其操作一致？？)

Chubby设计者借鉴了Paxos的两种解决机制：给协调者指派序号或限制协调者可以选择的值F指派序号的方法

–（1）在一个有n个副本系统中，为每个副本分配一个id ，其中 0≤ir≤n-1。则副本的序号，其中k的初始值为0 ("则副本的序号，其中k的初始值为0 "这句话可能写得有点问题，这里没看懂)

–（2）某个副本想成为协调者之后，它就根据规则生成一个比它以前的序号更大的序号（实际上就是提高k的值），并将这个序号通过propose消息广播给其他所有的副本

–（3）如果接受到广播的副本发现该序号比它以前见过的序号都大，则向发出广播的副本返回一个promise消息，并且承诺不再接受旧的协调者发送的消息。如果大多数副本都返回了promise消息，则新的协调者就产生了F限制协调者可以选择的值
–Paxos强制新的协调者必须选择和前任相同的值

Chubby做了一个重要优化来提高系统效率—在选择某一个副本作为协调者之后就长期不变，此时协调者就被称为主服务器（Master）

F客户端的数据请求由主服务器完成，Chubby保证在一定时间内有且仅有一个主服务器，这个时间就称为主服务器租约期（Master Lease）

F客户端需要确定主服务器的位置，可向DNS发送一个主服务器定位请求，非主服务器的副本将对该请求做出回应

Chubby对于Paxos论文中未提及的一些技术细节进行了补充，所以Chubby的实现是基于Paxos，但其技术手段更加的丰富，更具有实践性

4、Chubby文件系统

Chubby系统本质上就是一个分布式的、存储大量小文件的文件系统，它所有的操作都是在文件的基础上完成

Chubby最常用的锁服务中，每一个文件就代表一个锁，用户通过打开、关闭和读取文件，获取共享（Shared）锁或独占（Exclusive）锁

选举主服务器过程中，符合条件的服务器都同时申请打开某个文件并请求锁住该文件

成功获得锁的服务器自动成为主服务器并将其地址写入这个文件夹，以便其他服务器和用户可以获知主服务器的地址信息

Chubby的文件系统和UNIX类似

F例如在文件名“/ls/foo/wombat/pouch”中，ls代表lock service，这是所有Chubby文件系统的共有前缀；foo是某个单元的名称；/wombat/pouch则是foo这个单元上的文件目录或者文件名

Google对Chubby做了一些与UNIX不同的改变

F例如Chubby不支持内部文件的移动；不记录文件的最后访问时间；另外在Chubby中并没有符号连接（Symbolic Link，又叫软连接，类似于Windows系统中的快捷方式）和硬连接（HardLink，类似于别名）的概念

在具体实现时，文件系统由许多节点组成，分为永久型和临时型，每个节点就是一个文件或目录。节点中保存着包括ACL（Access Control List，访问控制列表）在内的多种系统元数据 o

5、通信协议

故障处理

客户端租约过期

• 客户端向主服务器发出一个KeepAlive请求（上图1）
• 如果有需要通知的事件时则主服务器会立刻做出回应，否则等到客户端的租约期C1快结束的时候才做出回应（图2），并更新主服务器租约期为M2
• 客户端接到回应后认为该主服务器仍处于活跃状态，于是将租约期更新为C2并立刻发出新的KeepAlive请求（图3）
• 宽限期内，客户端不会立刻断开其与服务器端的联系，而是不断地做探询，当它接到客户端的第一个KeepAlive请求（图4）时会拒绝（图5）
• 客户端在主服务器拒绝后使用新纪元号来发送KeepAlive请求（图6）
• 新的主服务器接受这个请求并立刻做出回应（图7）

如果客户端接收到这个回应的时间仍处于宽限期内，系统会恢复到安全状态，租约期更新为C3。如果在宽限期未接到主服务器的相关回应，客户端终止当前的会话

主服务器出错

正常情况下旧的主服务器出现故障后系统会很快地选举出新的主服务器，新选举需要经历以下九个步骤：

（1）产生一个新的纪元号以便今后客户端通信时使用，这能保证当前的主服务器不必处理针对旧的主服务器的请求

（2）只处理主服务器位置相关的信息，不处理会话相关的信息

（3）构建处理会话和锁所需的内部数据结构

（4）允许客户端发送KeepAlive请求，不处理其他会话相关的信息

（5）向每个会话发送一个故障事件，促使所有的客户端清空缓存

（6）等待直到所有的会话都收到故障事件或会话终止

（7）开始允许执行所有的操作

（8）如果客户端使用了旧的句柄则需要为其重新构建新的句柄

（9）一定时间段后（1分钟），删除没有被打开过的临时文件夹

——如果这一过程在宽限期内顺利完成，则用户不会感觉到任何故障的发生，也就是说新旧主服务器的替换对于用户来说是透明的，用户感觉到的仅仅是一个延迟

系统实现时，Chubby还使用了一致性客户端缓存（Consistent Client-Side Caching）技术，这样做的目的是减少通信压力，降低通信频率

F在客户端保存一个和单元上数据一致的本地缓存，需要时客户可以直接从缓存中取出数据而不用再和主服务器通信

F当某个文件数据或者元数据需要修改时，主服务器首先将这个修改阻塞；然后通过查询主服务器自身维护的一个缓存表，向对修改的数据进行了缓存的所有客户端发送一个无效标志（Invalidation）F客户端收到这个无效标志后会返回一个确认（Acknowledge），主服务器在收到所有的确认后才解除阻塞并完成这次修改

——这个过程的执行效率非常高，仅仅需要发送一次无效标志即可，因为对于没有返回确认的节点，主服务器直接认为其是未缓存

6、正确性与性能

一致性

每个Chubby单元是由五个副本组成的，这五个副本中需要选举产生一个主服务器，这种选举本质上就是一个一致性问题。实际执行过程中，Chubby使用Paxos算法来解决

主服务器产生后客户端的所有读写操作都是由主服务器来完成的

a读操作很简单，客户直接从主服务器上读取所需数据即可

a写操作就会涉及数据一致性的问题；为了保证客户的写操作能够同步到所有的服务器上，系统再次利用了Paxos算法

性能优化

为满足系统高可扩展性，Chubby目前已经采取了一些措施：比如提高主服务器默认的租约期、使用协议转换服务将Chubby协议转换成较简单的协议、客户端一致性缓存等；除此之外，Google的工程师们还考虑使用代理（Proxy）和分区（Partition）技术

a代理可以减少主服务器处理KeepAlive以及读请求带来的服务器负载，但是它并不能减少写操作带来的通信量

a使用分区技术的话可以将一个单元的命名空间（NameSpace）划分成N份。除了少量的跨分区通信外，大部分的分区都可以独自地处理服务请求。通过分区可以减少各个分区上的读写通信量，但不能减少KeepAlive请求的通信量

Google的云计算原理与应用(分布式结构化数据表BigTable)

1、设计动机与目标

(1)设计动机

需要存储的数据种类繁多：Google目前向公众开放的服务很多，需要处理的数据类型也非常多。包括URL、网页内容、用户的个性化设置在内的数据都是Google需要经常处理的

海量的服务请求：Google运行着目前世界上最繁忙的系统，它每时每刻处理的客户服务请求数量是普通的系统根本无法承受的

商用数据库无法满足Google的需求：一方面现有商用数据库设计着眼点在于通用性，根本无法满足Google的苛刻服务要求；另一方面对于底层系统的完全掌控会给后期的系统维护、升级带来极大的便利

(2)基本目标

2、数据模型

Bigtable是一个分布式多维映射表，表中的数据通过一个行关键字（Row Key）、一个列关键字（Column Key）以及一个时间戳（Time Stamp）进行索引

Bigtable对存储在其中的数据不做任何解析，一律看做字符串

Bigtable的存储逻辑可以表示为： (row:string,column:string, time:int64)→string

行

• Bigtable的行关键字可以是任意的字符串，但是大小不能超过64KB。Bigtable和传统的关系型数据库有很大不同，它不支持一般意义上的事务，但能保证对于行的读写操作具有原子性（Atomic）
• 表中数据都是根据行关键字进行排序的，排序使用的是词典序。
• 一个典型实例，其中com.cnn.www就是一个行关键字。不直接存储网页地址而将其倒排是Bigtable的一个巧妙设计。这样做至少会带来以下两个好处

同一地址域的网页会被存储在表中的连续位置，有利于用户查找和分析倒排便于数据压缩，可以大幅提高压缩率

列

Bigtable并不是简单地存储所有的列关键字，而是将其组织成所谓的列族（Column Family），每个族中的数据都属于同一个类型，并且同族的数据会被压缩在一起保存。引入了列族的概念之后，列关键字就采用下述的语法规则来定义：

族名：限定词（family：qualifier）

族名必须有意义，限定词则可以任意选定

图中，内容（Contents）、锚点（Anchor）都是不同的族。而cnnsi.com和my.look.ca则是锚点族中不同的限定词
族同时也是Bigtable中访问控制（Access Control）基本单元，也就是说访问权限的设置是在族这一级别上进行的

时间戳

Google的很多服务比如网页检索和用户的个性化设置等都需要保存不同时间的数据，这些不同的数据版本必须通过时间戳来区分。图2中内容列的t3、t5和t6表明其中保存了在t3、t5和t6这三个时间获取的网页。Bigtable中的时间戳是64位整型数，具体的赋值方式可以采取系统默认的方式，也可以用户自行定义为了简化不同版本的数据管理，Bigtable目前提供了两种设置：一种是保留最近的N个不同版本，图中数据模型采取的就是这种方法，它保存最新的三个版本数据。另一种就是保留限定时间内的所有不同版本，比如可以保存最近10天的所有不同版本数据。失效的版本将会由Bigtable的垃圾回收机制自动处理

3、系统架构

在Bigtable中Chubby主要有以下几个作用：

（1）选取并保证同一时间内只有一个主服务器（MasterServer）

（2）获取子表的位置信息

（3）保存Bigtable的模式信息及访问控制列表

另外在Bigtable的实际执行过程中，Google的MapReduce和Sawzall也被用来改善其性能

4、主服务器

当一个新子表产生时，主服务器通过一个加载命令将其分配给一个空间足够的子表服务器。创建新表、表合并以及较大子表的分裂都会产生一个或多个新子表。对于前面两种，主服务器会自动检测到，而较大子表的分裂是由子服务发起并完成的，所以主服务器并不能自动检测到，因此在分割完成之后子服务器需要向主服务发出一个通知

由于系统设计之初就要求能达到良好的扩展性(既然要求有扩展性，那么，当有新的服务器加进来时，必须得及时知道)，所以主服务器必须对子表服务器的状态进行监控，以便及时检测到服务器的加入或撤销
Bigtable中主服务器对子表服务器的监控是通过Chubby完成的——子表服务器在初始化时都会从Chubby中得到一个独占锁。通过这种方式所有子表服务器基本信息被保存在Chubby中一个称为服务器目录（ServerDirectory）的特殊目录之中

主服务器会定期向其询问独占锁的状态。如果子表服务器的锁丢失或没有回应，则此时可能有两种情况

要么是Chubby出现了问题（虽然这种概率很小，但的确存在，Google自己也做过相关测试）

要么是子表服务器自身出现了问题。对此主服务器首先自己尝试获取这个独占锁，如果失败说明Chubby服务出现问题，需等待恢复；如果成功则说明Chubby服务良好而子表服务器本身出现了问题

当在状态监测时发现某个子表服务器上负载过重时，主服务器会自动对其进行负载均衡操作

基于系统出现故障是一种常态的设计理念，每个主服务器被设定了一个会话时间的限制。当某个主服务器到时退出后，管理系统就会指定一个新的主服务器，这个主服务器的启动需要经历以下四个步骤：

（1）从Chubby中获取一个独占锁，确保同一时间只有一个主服务器

（2）扫描服务器目录，发现目前活跃的子表服务器

（3）与所有的活跃子表服务器取得联系以便了解所有子表的分配情况

（4）扫描元数据表，发现未分配的子表并将其分配到合适子表服务器

如果元数据表未分配，则首先需要将根子表（Root Tablet）加入未分配的子表中。由于根子表保存了其他所有元数据子表的信息，确保了扫描能够发现所有未分配的子表

5、子表服务器

由于一个BigTable需要存储海量数据，所以它不得不被分成多个Tablet，而每个Tablet都会负责一定范围的列。并且存储在多个服务器上。

SSTable及子表基本结构

SSTable是Sorted String Table的缩写，按照键排序后存储键/值对(Key——Value)字符串，并且它是不可变动的，也就是写子之后，只能将其更新附加至其后，而不能直接对其进行修改，这样是为了让系统能执行磁盘所擅长的顺序访问，而不是随机访问。

SSTable及子表基本结构

子表实际组成

Bigtable中的日志文件是一种共享日志，每个子表服务器上仅保存一个日志文件，某个子表日志只是这个共享日志的一个片段。这样会节省大量的空间，但在恢复时却有一定的难度

Google为了避免这种情况出现，对日志做了一些改进。Bigtable规定将日志的内容按照键值进行排序，这样不同的子表服务器都可以连续读取日志文件了

一般来说每个子表的大小在100MB到200MB之间。每个子表服务器上保存的子表数量可以从几十到上千不等，通常情况下是100个左右

（个人理解：由此，一个子表服务器上有一个日志文件，而同时，每个子表中也有自己的日志，它是其所在服务器上日志文件中的一个片段）

SSTable表的结构

SSTable中数据被划分成一个个的块（Block），每个块的大小是可以设置的，一般为64KB

在SSTable的结尾有一个索引（Index），这个索引保存了块的位置信息，在SSTable打开时这个索引会被加载进内存，用户在查找某个块时首先在内存中查找块的位置信息，然后在硬盘上直接找到这个块

由于每个SSTable一般都不是很大，用户还可以选择将其整体加载进内存，这样查找起来会更快

2所有子表地址都被记录在元数据表中，元数据表也是由一个个的元数据子表（Metadata tablet）组成

2根子表是元数据表中一个比较特殊的子表，它既是元数据表的第一条记录，也包含了其他元数据子表的地址，同时Chubby中的一个文件也存储了这个根子表的信息。

2查询时，首先从Chubby中提取这个根子表的地址，进而读取所需的元数据子表的位置，最后就可以从元数据子表中找到待查询的子表。除了这些子表的元数据之外，元数据表中还保存了其他一些有利于调试和分析的信息，比如事件日志等

为了减少访问开销，提高客户访问效率，Bigtable使用了缓存（Cache）和预取（Prefetch）技术

子表的地址信息被缓存在客户端，客户在寻址时直接根据缓存信息进行查找。一旦出现缓存为空或缓存信息过时的情况，客户端就需要按照图示方式进行网络的来回通信（Network Round-trips）进行寻址，在缓存为空的情况下需要三个网络来回通信。如果缓存的信息是过时的，则需要六个网络来回通信。其中三个用来确定信息是过时的，另外三个获取新的地址

预取则是在每次访问元数据表时不仅仅读取所需的子表元数据，而是读取多个子表的元数据，这样下次需要时就不用再次访问元数据表

子表数据存储及元数据

Bigtable将数据存储划分成两块：较新的数据存储在内存中一个称为内存表（Memtable）的有序缓冲里，较早的数据则以SSTable格式保存在GFS中

写操作（Write Op）——先查询Chubby中保存的访问控制列表确定用户具相应写权限，通过认证之后写入的数据首先被保存在提交日志（Commit Log）中。提交日志中以重做记录（RedoRecord）的形式保存着最近的一系列数据更改，这些重做记录在子表进行恢复时可以向系统提供已完成的更改信息。

读操作（Read Op）——先通过认证，之后读操作就要结合内存表和SSTable文件来进行，因为内存表和SSTable中都保存了数据

每一次旧的内存表停止使用时都会进行一个次压缩操作，这会产生一个SSTable。但如果系统中只有这种压缩的话，SSTable的数量就会无限制地增加下去

而在Bigtable中，读操作实际上比写操作更重要，因此Bigtable会定期地执行一次合并压缩的操作，将一些已有的SSTable和现有的内存表一并进行一次压缩

主压缩其实是合并压缩的一种，只不过它将所有的SSTable一次性压缩成一个大的SSTable文件。主压缩也是定期执行，执行一次主压缩之后可以保证将所有的被压缩数据彻底删除

压缩

压缩可以有效地节省空间，Bigtable中的压缩被应用于很多场合

F首先压缩可以被用在构成局部性群组的SSTable中，可以选择是否对个人的局部性群组的SSTable进行压缩。这种压缩是对每个局部性群组独立进行，虽然会浪费一些空间，但是在需要读时解压速度非常快

通常情况下，用户可以采用两步压缩的方式：

F第一步利用Bentley & McIlroy方式（BMDiff）在大的扫描窗口将常见的长串进行压缩；第二步采取Zippy技术进行快速压缩，它在一个16KB大小的扫描窗口内寻找重复数据，这个过程非常快

压缩技术还可以提高子表的恢复速度，当某个子表服务器停止使用后，需要将上面所有的子表移至另一个子表服务器。转移前两次压缩：第一次压缩减少了提交日志中未压缩状态；文件正式转移前还要进行一次压缩，主要是将第一次压缩后遗留的未压缩空间进行压缩

布隆过滤器（Bloom Filter）

巴顿·布隆在1970年提出的，实际上它是一个很长的二进制向量和一系列随机映射函数，在读操作中确定子表的位置时非常有用

F优势：速度快，省空间。而且它有一个最大的好处是它绝不会将一个存在的子表判定为不存在

F缺点：在某些情况下它会将不存在的子表判断为存在。不过这种情况出现的概率非常小，跟它带来的巨大好处相比这个缺点是可以忍受的

目前包括Google Analytics、Google Earth、个性化搜索、Orkut和RRS阅读器在内几十个项目都使用Bigtable。这些应用对Bigtable的要求以及使用的集群机器数量都各不相同，但从实际运行来看，Bigtable完全可以满足这些不同需求的应用，而这一切都得益于其优良的构架以及恰当的技术选择