云计算 | Daily Growing

整理自《云计算（第三版）》刘鹏主编。

概述

新摩尔定律：每18个月全球新增信息量是计算机有史以来全部信息量的总和。
大数据具有4V+1C的特征：
1. 数据量大
2. 多样
3. 快速
4. 价值密度低
5. 复杂度
大数据是需求，云计算是处理大数据的手段
云计算的特点：
1. 超大规模
2. 虚拟化
3. 高可靠性
4. 通用性
5. 高可伸缩性
6. 按需服务
7. 极其廉价
云计算按照服务类型大致可分为3类
1. 将基础设施作为服务（IaaS）
2. 将平台作为服务（PaaS）
3. 将软件作为服务（SaaS）
云计算技术体系结构分为4层：
1. 物理资源层
2. 资源池层
3. 管理中间件层
4. SOA(Service-Oriented Architecture，面向服务的体系结构)构建层
云计算的优势：它的技术特征和规模效应所带来的压倒性的性能价格比优势

Google 云计算原理与应用

Google 云计算技术包括：

Google文件系统GFS
分布式计算编程模型MapReduce
分布式锁服务Chubby
分布式结构化数据表Bigtable
分布式存储系统Megastore
分布式监控系统Dapper
海量数据的交互分析工具Dremel
内存大数据分析系统PowerDrill

1.Google文件系统GFS

它采用廉价的商用机器构件分布式文件系统，同时将GFS的设计与Google应用的特点紧密结合，简化实现。
GFS将容错的任务交给文件系统完成，利用软件的方法解决系统可靠性的问题，使存储的成本下降
GFS将服务器故障视为正常现象，并使用不同的容错措施，确保数据安全和提供不间断的数据存储服务

系统架构

GFS将整个系统的节点分为3类角色：
1. Client（客户端）：GFS提供给应用程序的访问接口
2. Master（主服务器）：GFS的管理节点，它保存系统的元数据，负责整个文件系统的管理
3. Chunk Server（数据块服务器）：负责具体的存储工作
客户端访问GFS时：访问Master节点->获取需要的Chunk Server信息->直接访问Chunk Server->存取数据
Client和Master之间：控制流；Client和Chunk Server之间：传输数据流。
GFS的特点：
1. 采用中心服务器模式：Chunk Server 之间无关系，Master维护了一个统一的命名空间，同时掌握整个系统内Chunk Server的情况，据此可以实现整个系统范围内的数据存储的负载均衡。
2. 不缓存数据：GFS文件系统没有实现缓存，因为客户端不存在大量的重复读写，采用缓存意义不大。
3. 在用户态下实现：文件系统通常位于操作系统的底层（内核态），GFS选择在用户态下实现（好处：直接利用操作系统提供的端口就可以存取数据；接口提供的功能更丰富；用户态下有多种调试工具；Master和Chunk Server都可以以进程的方式运行而不会影响系统；GFS和操作系统之间的耦合性降低）
4. 只提供专用接口

容错机制

Master容错

Master保存了GFS的三种元数据
1. 命名空间（整个文件系统的目录结构）
2. Chunk和文件名的映射表
3. （3个）Chunk副本的位置信息
对于前两种元数据，GFS通过操作日志来提供容错功能；第三种元数据直接保存在各个Chunk Server上（自动生成）。

Chunk Server容错

GFS采用副本的方式实现Chunk Server容错
GFS中的每一个文件被划分为多个Chunk，每一个Chunk以Block为单位划分，每个Block对应一个32bit的校验和。Chunk Server储存的是Chunk副本文件。

系统管理技术

大规模集群安装技术
故障检测技术
节点动态加入技术
节能技术

2.分布式数据处理MapReduce

MapReduce是一种处理海量数据的并行编程模式，用于大规模数据集的并行运算。
MapReduce把对数据集的大规模操作，分发给一个主节点管理下的各分节点共同完成，通过这种方式实现任务的可靠执行和容错机制。
在每个时间周期，主节点都会对分节点的工作状态进行标记。一旦被标记为死亡状态，这个节点的所有任务都将分配给其他分节点重新执行。

编程模型

例如，假设我们使用MapReduce计算一个大型文本文件中各个单词出现的次数，Map的输入参数<起始位置,数据长度>指明了需要处理哪部分数据，经过Map处理，形成一批中间结果<单词,出现次数>。Reduce函数处理中间结果，进行相同单词累加操作，最终得到结果。

实现机制

MapReduce函数首先把输入文件分成M块
Master选择空闲的工作机分配Map或Reduce任务
一个被分配了Map任务的工作机读取并处理相关的输入快，Map函数产生的中间结果<key,value>对暂时缓冲到内存
缓冲到内存的中间结果被定时写到本地硬盘，位置信息被发送回Master，然后Master将这些位置信息传送给Reduce工作机
Reduce工作及读到所有的中间数据，使用中间key进行排序，使相同key的值都在一起
Reduce工作机把key和相关的中间结果值集合传递给用户定义的Reduce函数，Reduce函数的结果写入最终的输出文件
当所有Map任务和Reduce任务都完成的时候，Master激活用户程序

容错

Master 失效：只能终止整个MapReduce程序的运行并重新开始
Worker 失效（Master向其发送的ping命令没有得到应答）：终止对这个Worker的任务调度，把是小Worker的任务调度到其他Worker上重新执行

3.分布式锁服务Chubby

通过使用Chubby的锁服务，用户可以确保数据操作过程中的一致性

Paxos算法

Paxos算法用于解决分布式系统中的一致性问题
前情提要：为了保证在一个操作序列中每个步骤仅有一个值，在分布式系统中设置一个专门节点，在每次需要进行操作之前，系统各个部分向它发送请求，告诉该节点接下来系统要做什么。保险起见，系统设置多个专门节点。
Paxos算法：节点被分成三种类型：proposers（提出决议，告诉系统截下来该执行哪个指令）；acceptors（批准决议）；learners（获取并使用已经通过的决议）。满足三个条件（1.决议只有在被proposers提出后才能批准；2.每次只批准一个决议；3.只有决议确定被批准后learner才能获取这个决议）
为满足三个条件，对系统的约束条件：
1. 每个acceptor只接受它得到的第一个决议
2. 一旦某个决议得到通过，之后通过的决议必须和该决议保持一致
可以将一个决议的通过分成两个阶段：
1. 准备阶段：proposers选择一个提案并将它的编号设为n，然后将它发送给acceptors。acceptors收到后，如果提案的变好小于它已经回复的所有消息，则将自己上次的批准回复给proposers，并不再批准小于n的提案
2. 批准阶段：proposers收到acceptors的回复后，就向acceptors发送accept请求，在符合acceptors一方的约束条件下，它收到accept请求后即批准这个请求

Chubby 系统设计

通常情况下Google的一个数据中心仅运行一个Chubby单元
Chubby被分为两个部分：客户端和服务器端。
客户端和服务器端之间通过远程过程调用（RPC）来连接。
在客户这一端每个客户应用程序都有一个Chubby程序库，客户端的所有应用都是通过调用这个库中的相关函数来完成的。
服务器端称为Chubby单元，一般都是由5个称为副本的服务器组成的。

Chubby 中的 Paxos

为解决Chubby中的一致性问题，引入了Paxos算法
Paxos算法的实际作用：
1. 选择一个副本作为协调者
2. 协调者从客户提交的值中选择一个，然后通过名为accept的消息广播给所有的副本。其他的副本收到后，可以选择接受或拒绝这个值，并反馈结果
3. 协调者一旦收到大多数副本的接受信息后，就认为达到了一致性，接着协调者向相关的副本发送一个commit消息
由于单个的协调者可能失效，系统允许同时有多个协调者，但多个协调者可能会导致多个协调者提交了不同的值。对此有两种解决机制：给协调者指派序号或限制协调者可以选择的值（新协调者必须选择和前任相同的值）。
Chubby对于系统效率的优化：选择某一个副本作为协调者之后就长期不变，此时协调者就被称为主服务器。
在Chubby中，客户端的数据请求都是由主服务器完成。Chubby保证在一定的时间内有且仅有一个主服务器，这个时间就称为主服务器租约期。

Chubby 文件系统

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

通信协议

客户端和主服务器之间的通信事通过KeepAlive握手协议来维持的
KeepAlive是周期发送的一种信息，主要功能：延迟租约的有效期和携带事件信息告诉用户更新。
系统可能会出现两种故障：客户端租约期过期和主服务器故障
客户端租约过期：
1. 客户端向主服务器发送一个KeepAlive请求，没有需要通知的事情的话，主服务器等到客户端租约期C1快结束的时候才做出回应，并更新主服务器的租约为M2
2. 客户端在接收回应后将租约期更新为C2并发出新的KeepAlive请求。
3. 如果在C2到期还没有收到主服务器的回应，系统向客户端发出一个危险事件，客户端清空并暂时停止使用自己的缓存，进入“宽限期”（客户端不会断开和服务器的联系，而是不断做探寻）的危险状态。
4. 新服务器收到第一个KeepAlive请求，因为纪元号不同而拒绝，此时客户端使用新纪元号发送请求，新服务器收到请求并回应。如果此时在宽限期内则系统恢复安全状态，租约期更新C3。
5. 如果宽限期没收到服务器相关回应，客户端终止当前会话
主服务器出错：
选出新的服务器后，在完全运行前需要有9个步骤（如果在宽限期内完成则用户只感觉到延迟）
1. 产生新纪元号
2. 只处理主服务器位置相关的信息，不处理会话相关的信息
3. 构建处理会话和锁所需的内部数据结构
4. 允许客户端发送KeepAlive请求，不处理其他会话相关的信息
5. 向每个会话发送一个故障时间，使客户端们清空缓存
6. 等到直到所有的会话都收到故障事件或会话终止。
7. 开始允许执行所有的操作
8. 如果客户端使用了旧的句柄则需要为其重新构建新的句柄
9. 一分钟后删除没有被打开过的临时文件夹
在系统实现时，Chubby还使用了一致性客户端缓存技术（减少通信压力，降低通信频率）：在客户端保存一个和单元上数据一致的本地缓存，需要时客户可以直接从缓存中取出数据而不用再和主服务器通信。
当文件数据或元数据需要修改时，主服务器首先将修改阻塞；然后通过查询主服务器自身维护的一个缓存表，向对修改数据进行了缓存的所有客户端发送无效标志；客户端收到后会返回确认，主服务器收到所有确认后才解除阻塞并完成修改。

4.分布式结构化数据表 BigTable

BigTable是Google开发的基于GFS和Chubby的分布式存储系统

数据模型

BigTable是一个分布式多维映射表，表中的数据通过一个行关键字、一个列关键字以及一个时间戳进行索引。
BigTable对存储在其中的数据不做任何解析，一律看做字符串。
BigTable的存储逻辑可以表示为：(row:string, column:string, time:int64)->string

行

表中数据都是根据行关键字排序的
其中com.cnn.www就是一个关键字。
不直接存储网页地址而将其倒排是BigTable的一个设计，有2个好处：
1. 同一地址域的网页会被存储在表中的连续位置，有利于用户查找分析
2. 倒排便于数据压缩
单个大表不利于数据的处理，因此BigTable将一个表分成了很多子表，每个子表包含多个行。子表是BigTable中数据划分和负载均衡的基本单位。

列

BigTable将所有列关键字组织成所谓的列族，每个族中的数据都属于同一个类型，并且同族的数据会被压缩在一起保存。
列关键字的语法规则：族名:限定词
例如上图中内容和锚点都是不同的族，而cnnsi.com和my.look.ca 则是锚点族中不同的限定词

时间戳

Google的很多服务比如网页检索和用户的个性化设置等都需要保存不同时间的数据，这些不同的数据版本必须通过时间戳来区分

系统架构

Bigtable主要由三个部分组成：客户端程序库(Client Library)、一个主服务器(Master Server)和多个子表服务器(Tablet Server)
客户访问Bigtable服务时，首先要利用其库函数执行Open()操作来打开一个锁(实际上就是获取了文件目录)，锁打开以后客户端就可以和子表服务器进行通信了。
客户端主要与子表服务器通信，几乎不和主服务器进行通信，这使得主服务器的负载大大降低。
主服务主要进行一些元数据的操作以及子表服务器之间的负载调度问题，实际的数据是存储在子表服务器上的。

主服务器

Bigtable中主服务器对子表服务器的监控是通过Chubby完成的，子表服务器在初始化时都会从Chubby中得到一个独占锁。
通过这种方式所有的子表服务器基本信息被保存在Chubby中一个称为服务器目录(Server Directory)的特殊目录之中。
基于系统出现故障是一种常态的设计理念，每个主服务器被设定了一个会话时间的限制。当某个主服务器到时退出后，管理系统就会指定一个新的主服务器，这个主服务器的启动需要经历以下四个步骤：
1. 从Chubby中获取一个独占锁，确保同一时间只有一个主服务器。
2. 扫描服务器目录，发现目前活跃的子表服务器。
3. 与所有的活跃子表服务器取得联系以便了解所有子表的分配情况。
4. 通过扫描元数据表(Metadata Table)，发现未分配的子表并将其分配到合适的子表服务器。

子表服务器

Bigtable中实际的数据都是以子表的形式保存在子表服务器上的，客户一般也只和子表服务器进行通信。

SSTable及子表基本结构

SSTable是Google为Bigtable设计的内部数据存储格式。所有的SSTable文件都存储在GFS上，用户可以通过键来查询相应的值。
SSTable中的数据被划分成一个个的块(Block)，每个块的大小是可以设置的。
在SSTable的结尾有一个索引(Index)，这个索引保存了SSTable中块的位置信息，在SSTable打开时这个索引会被加载进内存，这样用户在查找某个块时首先在内存中查找块的位置信息，然后在硬盘上直接找到这个块。
每个子表都是由多个SSTable以及日志(Log)文件构成。注意：不同子表的SSTable可以共享。
每个子表服务器上仅保存一个日志文件，在恢复时却有一定的难度，因为不同的子表可能会被分配到不同的子表服务器上。为了避免这种情况，Bigtable规定将日志的内容按照键值进行排序，这样不同的子表服务器都可以连续读取日志文件了。

子表地址

在Bigtable系统的内部采用的是一种类似B+树的三层查询体系。
所有的子表地址都被记录在元数据表中，元数据表也是由一个个的元数据子表(Metadata Tablet)组成的。根子表既是元数据表的第一条记录，也包含了其他元数据子表的地址。
为了减少访问开销，提高客户访问效率，Bigtable使用了缓存（子表的地址信息被缓存在客户端，客户在寻址时直接根据缓存信息进行查找）和预取（在每次访问元数据表时不仅仅读取所需的子表元数据，而是读取多个子表的元数据）技术

子表读写操作

Bigtable将数据存储划分成两块。较新的数据存储在内存中一个称为内存表的有序缓冲里，较早的数据则以SSTable格式保存在GFS中。
读和写操作有很大的差异性。做写操作时，首先查询Chubby确定用户具有相应的写权限，写入的数据保存在提交日志中，提交日志中保存着最近的数据更改，这些重做记录在子表进行恢复时可以向系统提供已完成的更改信息。数据成功提交之后就被写入内存表中；做读操作时，首先还是要通过认证，之后读操作就要结合都保存了数据的内存表和SSTable文件来进行。
在Bigtable中有三种形式的数据压缩，分别是次压缩、合并压缩和主压缩。

性能优化

局部性群组

Bigtable允许用户将原本并不存储在一起的数据以列族为单位，根据需要组织在一个单独的SSTable中，以构成一个局部性群组。实际上就是数据库中垂直分区技术的一个应用。
通过设置局部性群组用户可以只看自己感兴趣的内容

压缩

Bigtable中这种压缩是对每个局部性群组独立进行的，虽然这样会浪费一些空间，但是在需要读时解压速度非常快。

布隆过滤器

布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数，在读操作中确定子表的位置时非常有用。

5.分布式存储系统Megastore（相对过时）

Megastore是一种介于传统的关系型数据库和NoSQL之间的存储技术，尽可能达到高可用性和高可扩展性的统一。
针对可用性的要求，实现了一个同步的、容错的、适合远距离传输的复制机制。
针对可扩展性的要求，将整个大的数据分割成很多小的数据分区，每个数据分区连同它自身的日志存放在Bigtable中。

Megastore数据模型

Megastore数据模型中另一个非常重要的概念——索引。
将索引分成了两大类：局部索引和全局索引。局部索引定义在单个实体组中，它的作用域仅限于单个实体组。全局索引则可以横跨多个实体组集进行数据读取操作。
除了这两大类的索引外，Megastore还提供了一些额外的索引特性
1. STORING子句：通过在索引中增加STORING子句，应用程序可以存储一些额外的属性，这样在读取数据时可以更快地从基本表中得到所需内容。
2. 可重复的索引：Megastore提供了对可重复属性建立索引的能力
3. 内联索引：任何一个有外键的表都能够创建一个内联索引。

Megastore中的事务及并发控制

Megastore提供了三种方式的读，分别是current、snapshot和inconsistent。
在开始某次current读之前，需要确保所有已提交的写操作已经全部生效，然后应用程序再从最后一个成功提交的事务时间戳位置读取数据。
对于snapshot读，系统取出已知的最后一个完整提交的事务的时间戳，接着从这个位置读数据。(snapshot读的时候可能还有部分事务提交了但未生效)
inconsistent读忽略日志的状态直接读取最新的值。
Megastore事务中的写操作采用了预写式日志，也就是说只有当所有的操作都在日志中记录下后写操作才会对数据执行修改。
一个完整的事务周期要经过如下几个阶段。
1. 读：获取最后一次提交的事务的时间戳和日志位置。
2. 应用逻辑：从Bigtable读取并且聚集数据到日志入口。
3. 提交：使用Paxos达到一致，将这个入口追加到日志。
4. 生效：将数据更新到Bigtable中的实体和索引。
5. 清除：清理不再需要的数据。
Megastore中事务间的消息传递是通过队列实现的

Megastore基本架构

在Megastore中共有三种副本，分别是完整副本、见证者副本和只读副本。
见证者副本的作用是在Paxos算法执行过程中无法产生一个决议时参与投票，因此对于这种副本，Bigtable只存储其日志而不存储具体数据。
只读副本无法参与投票。它们的作用只是读取到最近过去某一个时间点的一致性数据。
Megastore的部署需要通过一个客户端函数库和若干的服务器。应用程序连接到这个客户端函数库，这个函数库执行Paxos算法。

快速读

由于写操作基本上能在所有的副本上成功，一旦成功，认为该副本上的数据都是相同的且是最新的，就能利用本地读取实现快速读
为了确保选择的副本上数据是最新的，引入了协调者的概念。
协调者是一个服务，该服务分布在每个副本的数据中心里面。它的主要作用就是跟踪一个实体组集合，集合中的实体组需要具备的条件就是它们的副本已经观察到了所有的Paxos写。只要出现在这个集合中的实体组，它们的副本就都能够进行本地读取，也就是说能够实现快速读。

快速写

如果一次写成功，那么下一次写的时候就跳过准备过程，直接进入接受阶段。

核心技术——复制

通过复制保证所有最新的数据都保存有一定数量副本，能够很好地提高系统的可用性。

复制的日志

每个副本都存有记录所有更新的数据。即使是它正从一个之前的故障中恢复数据，副本也要保证其能够参与到写操作中的Paxos算法，因此Megastore允许副本不按顺序接受日志，这些日志将独立的存储在Bigtable中。

数据读取

在一次Current读之前，要保证至少有一个副本上的数据是最新的，也就是说所有之前提交到日志中的更新必须复制到该副本上并确保在该副本上生效。这个过程称为追赶。
一次数据读取过程：
1. 本地查询：查询本地副本的协调者来决定这个实体组上数据是否已经是最新
2. 发现位置：确定一个最高的已经提交的日志位置，选择一个已经在该位置上生效的副本。
  （1）本地读取（本地副本已是最新）：从副本中的最高日志位置和时间戳读取数据
  （2）多数派读取（不是最新）：从一个副本的多数派中发现最大的日志位置，然后从中选取一个读取
3. 追赶
4. 验证：如果本地副本被选中且数据不是最新，发送一个验证消息到协调者断定(entity group, replica)对((entity group, replica)pair)能够反馈所有提交的写操作。
5. 查询数据：在所选的副本中利用日志位置的时间戳读取数据

数据写入

数据写入的完整过程：

接受leader：请求leader接受值作为0号提议。实际上就是快速写方法。如果成功，跳至步骤(3)
准备：在所有的副本上使用一个比其当前所见的日志位置更高的提议号进行Paxos准备阶段
接受：请求剩余的副本接受该值，如果大多数副本拒绝这个值，返回步骤(2)
失效：将不接受值的副本上的协调者进行失效操作
生效：将值的更新在尽可能多的副本上生效

6.大规模分布式系统的监控基础架构Dapper

Dapper监控系统简介

基本概念

Dapper监控系统中有三个基本概念：监控树、区间和注释
监控树实际上就是一个同特定事件相关的所有消息，只不过这些消息是按照一定的规律以树的形式组织起来。
树中的每一个节点称为一个区间，区间实际上就是一条记录，所有这些记录联系在一起就构成了对某个事件的完整监控。
每个区间包括以下内容：区间名(Span Name)、区间id(Span id)、父id(Parent id)和监控id(Trace id)。
一棵监控树中所有区间的监控id是相同的
这个区间的区间名是“Helper.Call”，监控id是100，区间id是5，父id是3

监控信息的汇总

海量的消息记录必须通过一定的方式汇集在一起才能产生有效的监控信息，Dapper监控信息的汇总需要经过三个步骤：

将区间的数据被写入到本地的日志文件。
利用Dapper守护进程(Dapper daemon)和Dapper收集器(Dapper Collectors)将所有机器上的本地日志文件汇集在一起。
将汇集后的数据写入到Bigtable存储库中。

关键性技术

轻量级的核心功能库

将复杂的功能实现限制在一个轻量级的核心功能库中保证了Dapper的监控过程基本对应用层透明。

二次抽样技术

Dapper对请求进行了抽样，只有被抽中的请求才会被监控。
第一次抽样：当抽样率低至1/1024时也能够产生足够多的有效监控数据，即在1024个请求中抽取1个进行监控。
第二次的抽样：这次抽样发生在数据写入Bigtable之前，具体方法是将监控id散列成一个标量z，其中0≤z≤1。如果某个区间的z小于事先定义好的汇总抽样系数，则保留这个区间并将它写入Bigtable。否则丢弃不用。

7.海量数据的交互式分析工具Dremel

MapReduce（面向批处理）的效率低下，无法实现实时的数据交互。Dremel在用户提交完请求之后，在一个相对可以接受的合理时间内系统就会返回结果。

数据模型

嵌套数据模型很适合Google的数据存储
行存储(面向记录的存储)：这种存储方式以行为单位，一行一行地存储数据；列存储：以属性为单位，每次存储一个属性，在应用时再将需要的属性重新组装成原始的记录。
列存储的主要好处：处理时只需要使用涉及的列数据；更利于数据的压缩。

嵌套式的列存储

所需要解决的一些问题如下

数据结构的无损表示

为了准确地在存储中反映出嵌套的结构，Dremel定义了两个变量：r(重复深度)和d(定义深度)。
重复深度记录的是该列的值是在哪一个级别上重复的。如上图 Name.Language.Code中，值分别为’en-us’（Name和Language第一次出现，所以r=0）、 ‘en’(Language出现重复。因为Language在Name.Language.Code路径中的位置排在第二，所以’en’的r值取2)和 ‘en-gb’(Name重复，Name在Name.Language.Code中排第一位，所以重复深度是1)。；
定义深度同时关注可重复类型和可选类型。以Name.Language.Country路径为例，在r1中一共有4个定义，值分别为’us’、NULL、NULL和’gb’。对于’us’，Name、Language、Country都是有定义的，所以’us’的d值为3。同理，第一个NULL的d值为2，第二个NULL的d值为1，’gb’的d值为3。

高效的数据编码

实际中如何将一行行的记录表示成上图所示的结构仍是一个挑战，Dremel利用下图的算法创建一个树状结构，树的节点为字段的writer，它的结构与模式中的字段层级匹配。核心的想法是只在字段writer有自己的数据时执行更新，非绝对必要时不尝试往下传递父节点状态。子节点writer继承父节点的深度值。当任意值被添加时，子writer将深度值同步到父节点。

数据重组

数据重组：将查询涉及的列取出，然后将其按照原始记录的顺序组装起来，让用户感觉好像数据库中仅存在这些查询涉及的列一样。
Dremel数据重组方法的核心思想是为每个字段创建一个有限状态机(FSM)，读取字段值和重复深度，然后顺序地将值添加到输出结果上。

8.内存大数据分析系统PowerDrill

用户根据自己的需求，灵活地选择查询条件，系统根据用户的选择生成相应的统计结果。
PowerDrill整个系统实际分为三个部分：
1. Web UI，用于和用户进行交互;
2. 一个抽象层，用户的命令会被转换成SQL，然后根据不同的需求，这些命令会被发送至不同的终端，比如Dremel，Bigtable等;
3. 列式存储。

基本数据结构

PowerDrill采用的方式是对数据进行分块，对块数据设计巧妙的数据结构，使得在查询时可以确定哪些块不需要，可以直接被略去，减少所需的数据量。
全局字典表的右侧是3个块的数据，对于每个块，主要由两部分组成：块字典和块元素。块字典记录的是块id(chunk-id)和全局id的映射关系，而块元素记录的是块中存储数据的块id(注意不是全局id)。在具体查询时需要完成两层的数据映射才能得到真实的数据值。

性能优化

数据分块

对数据进行分块，然后通过一些方法过滤查询中不需要的数据块来减少数据量。数据分块的另一个好处就是防止单个数据表过大，导致性能下降。

数据编码的优化

在实际存储中选择统一编码，比如对所有的块id都采用32位的整型来记录。但是这种方法会带来空间上的浪费。如果一个块中仅有1个不同值，那我们实际只需要记录块中的记录数即可。
基数估计：统计一组数中不同值的个数

全局字典优化

因为全局字典是有序的，并且排序后的数据常常有共同的前缀，因此采用前缀树优化
实际使用中为了进一步减少查询中需要加载到内存的全局字典，对全局字典又进行了分块，将最常用的值组织成一个块，剩余值再组织成其他若干个块。

压缩算法

PowerDrill选择了LZO算法的一个变种作为实际生产环境中的压缩算法
不管压缩算法的解压速度多快，总会消耗一定的物理资源与时间。对此PowerDrill采用了一种冷热数据分别对待的策略。即在内存中保有压缩和未压缩的数据，根据需要对数据进行压缩和解压缩。
在冷热数据切换策略中，比较常用的是LRU算法(最近最少使用页面置换算法)，PowerDrill采用了一种启发式的缓存策略来代替原始的LRU算法。

行的重排

在列存储中，对行进行适当的重排不会影响结果且会提升压缩效率。

对比

PowerDrill和Dremel除了都采用列存储之外，有着不少区别：

两者的设计目标不同。Dremel用来处理非常大量的数据集，PowerDrill设计用来分析少量的核心数据集（数据集的规模大，但数据集的数量不多）
Dremel处理的数据来自外存，PowerDrill处理的数据尽可能地存于内存
Dremel未进行数据分区，分析时要扫描所有需要的列；PowerDrill使用了组合范围分区，分析时可以跳过很多不需要的分区
Dremel数据通常不需要加载，增加数据很方便；PowerDrill数据需要加载

9.Google应用程序引擎

Google App Engine是一个由Python应用服务器群、Bigtable数据库及GFS数据存储服务组成的平台，它能为开发者提供一体化的可自动升级的在线应用服务。
Google提供的Google App Engine是一个PaaS平台，用户可以在上面开发应用软件，并在Google的基础设施上运行此软件。其定位是易于实施和扩展，无须服务器维护。
Google App Engine提供了一些服务，这些服务统称为App Engine服务(图像操作API、邮件API、分布式内存数据缓存API、用户API、数据库API)
每个开发程序有自身的应用程序环境(由Google App Engine提供)，使应用程序可以在Google App Engine上正常运行。除此之外，Google App Engine为每个应用程序提供了一个安全运行环境(沙盒)，可以保证每个应用程序能够安全地隔离运行。
沙盒还可以对用户进行如下限制。
1. 用户的应用程序只能通过Google App Engine提供的网址抓取API和电子邮件服务API来访问互联网中其他的计算机，并且其他计算机如请求与该应用程序相连接，只能在标准接口上通过HTTP或HTTPS进行。
2. 应用程序无法对Google App Engine的文件系统进行写入操作，只能读取应用程序代码上的文件，并且该应用程序必须使用Google App Engine的Data Store数据库来存储应用程序运行期间持续存在的数据。
3. 应用程序只有在响应网络请求时才运行，并且这个响应时间必须极短，在几秒之内必须完成。与此同时，请求处理的程序不能在自己的响应发送后产生子进程或执行代码。

Amazon云计算 AWS

Amazonde的云计算服务平台Amazon Web Service（AWS）提供的服务包括

弹性计算云EC2
简单存储服务S3
简单数据库服务Simple DB
简单队列服务SOS
弹性MapReduce服务
内容推送服务CloudFront
电子商务服务DevPay和FPS

1. 基础存储架构Dynamo

1.1 概况

为了保证稳定性，Amazon的系统采用完全的分布式、去中心化的架构。其中，作为底层存储架构的Dynamo也同样采用了无中心的模式。
Dynamo只支持简单的键值（key/value）方式的数据存储，不支持复杂的查询。
Dynamo中存储的是数据值的原始形式，即按位存储，并不解析数据的具体内容，因此Dynamo几乎可以存储所有类型的数据

1.2 Dynamo架构的主要技术

Dynamo需要解决的主要问题	采取的相关技术
数据均衡分布	改进的一致性哈希算法
数据备份	参数可调的弱quorum机制
数据冲突处理	向量时钟
成员资格及错误检测	基于Gossip协议的成员资格和错误检测
临时故障处理	数据回传机制
永久故障处理	Merkle哈希树

1.2.1 数据均衡分布的问题

问题产生：Dynamo采用了分布式的数据存储结构，均衡的数据分布可以保证负载平衡和系统良好的扩展性。如何在各个节点上数据的均衡性是影响Dynamo性能的关键问题。
问题解决：Dynamo中使用改进后的一致性哈希算法。

1.2.1.1 一致性哈希算法

一致性哈希算法的基本过程为：对于系统中的每个设备节点，为其分配一个随机的标记，这些标记可以构成一个哈希环。在存储数据时，计算出数据中键的哈希值，将其存放到哈希环顺时针方向第一个标记大于或等于其值的设备节点上。
一致性哈希算法除了能够保证哈希运算结果充分分散到整个环上外，还能保证在添加或删除设备节点时只会影响到其在哈希环中的前驱设备节点，而不会对其他设备节点产生影响。（具体操作见P92）

1.2.1.2 改进的一致性哈希算法

问题产生：一致性哈希算法在设备节点数量较少的情况下，有可能造成环上节点分布的不均匀；并且没有考虑哈希环上不同设备节点的性能差异。——>Dynamo引入了虚拟节点（一个实际的物理节点根据其性能的差异被分为一个或多个虚拟节点。各个虚拟节点的能力基本相当，随机分布在哈希环上）的概念。——>在存储数据时，数据对象先按照其键的哈希值被分配到某个虚拟节点上，并存储在该虚拟节点所对应的物理节点中。
为了进一步提高数据分布的均衡性，Dynamo将整个哈希环划分成Q等份，每个等份称一个数据分区。假设系统中共有S个虚拟节点，且满足Q>>S，则每个虚拟节点负责的数据分区数为V=Q/S。
在存储数据时，每个数据会被先分配到某个数据分区，再根据负责该数据分区的虚拟节点，最终确定其所存储的物理节点。
采用数据分区的好处：1.由于数据分区的数量远大于虚拟节点的数量，可以减小数据分布不均衡的可能性。2.采用数据分区后，在添加或删除设备节点时，会引起较小的数据传输。（详情计算见P93）

1.2.2 数据备份

问题产生：为了提高数据的可用性，Dynamo在存储每个数据对象时，保存了其多个副本作为冗余备份。数据备份在存储数据的同时进行，会使每次写操作的时延变长。
问题解决：Dynamo在产生N个数据副本时采用了参数可调的弱quorum机制。
quorum涉及三个参数：一次成功的写操作至少需要写入的副本数W；一次成功读操作须由服务器返回给用户的最小副本数R；每个数据存储的副本数N。
通过配置R和W，可以调节系统的性能。（要求读效率高则R=1,W=N；写效率高则W=1，R=N；平衡则R=W=(N+1)/2）

1.2.3 数据冲突问题

问题产生：分布式系统架构中通常需要考虑三个因素（可靠性、可用性和一致性）Dynamo系统选择牺牲一致性来保证系统的可靠性和可用性，没有采用强一致性模型，而采用了最终一致性模型（不要求各个数据副本在更新过程中始终保持一致，只需要最终时刻所有数据副本能保证一致性）。由于Dynamo中可能出现同一个数据被多个节点同时更新的情况，且无法保证数据副本的更新顺序，这有可能导致数据冲突。
问题解决：Dynamo采用了向量时钟技术。Dynamo中的向量时钟通过[node,counter]对来表示。node表示操作节点，counter是其对应的计数器，初始为0，节点每进行一次更新操作计数器+1（详细见P95）

1.2.4 成员资格及错误检测

问题产生：由于Dynamo采用了无中心的架构，每个成员节点都需要保存其他节点的路由信息，以保障系统中各个节点之间数据转发顺畅。但添加或删除节点的情况时常发生。
问题解决：为了保证每个节点都能拥有最新的成员节点信息，Dynamo中采用了一种类似于Gossip协议的技术，要求每个节点相隔固定时间从其他节点中任意选择一个与之通信。
如果通信时连接成功，双方将交换各自保存的系统中节点的负载、路由等信息，完成节点信息的呼唤，同时更新各自保存的节点信息。
Dynamo中还通过Gossip来实现错误检测。任何节点向其他节点发起通信后，如果对方没有回应，则认为对方失效，选择别的节点通信。发起通信的节点会定期向失效节点发出消息，有回应则重新建立通信。
为了避免新加入的节点之间不能及时发现其他节点的存在，Dynamo中设置了一些种子节点。种子节点和所有的节点都有联系，当新节点加入时，它扮演中介角色。
当节点数增加到数万后，效率会急剧下降，Amazon为此采用了分层Dynamo结构来解决问题。

1.2.5 容错机制

Dynamo采用了廉价的服务器作为硬件设置，并将物理节点失效作为常态来处理。

1.2.5.1 临时故障处理机制

问题产生：Dynamo中如果某个节点由于机器假死等因素无法与其他节点通信，则会被其他节点认为失效。这种故障是临时性的，被认为失效的节点会在后期Gossip中被发现并重新使用。
问题解决：为了处理临时失效的节点，Dynamo中采用了一种带有监听的数据回传机制。当节点A失效后，会将数据临时存放在节点D的临时空间中，并在A重新可用后，由D将数据回传给A。

1.2.5.2 永久性故障处理机制

问题产生：在节点失效超过了设定时间后，如果没有发现节点可重用，Dynamo会认定该节点出现了永久性故障。此时Dynamo需要从其他数据副本进行数据同步。
问题解决：为了保障数据传输的有效性，Dynamo 采用Merkle哈希树技术来加快检测和减少数据传输量。
Merkle哈希树可以为二叉树或多叉树，每个叶子节点的值为单个数据文件的哈希值，非叶子节点的值为该节点所有子节点组合后的哈希值。
当Merkle哈希树检测数据时是否一致时，系统会先比较根节点的值，数据不同则继续比较，直到叶子节点。（详例P98）

2. 弹性计算云 EC2

2.1 EC2 基本架构

Amazon机器映象（AMI）：是包含了操作系统、服务器程序、应用程序等软件配置的模版，可以启动不同的实例。
实例：EC2中实例由AMI启动，可以像传统的主机一样提供服务。同一个AMI可以用于创建具有不同计算和存储能力的实例。
弹性块存储（EBS）：（基本每个实例自身携带一个存储模块，用于临时存储用户数据。但存储模块中的数据仅在实例的生命周期内存在；如果实例出现故障被终止，数据将会丢失。）如果希望存储的数据时间与实例的生命周期无关，可采用弹性块存储或S3进行数据存储。EBS存储卷的设计与物理硬盘相似。快照功能是EBS的特色功能之一。

2.2 EC2的关键技术

2.2.1 地理区域和可用区域

AWS中采用了两种区域：地理区域（按实际的地理位置划分的）和可用区域（根据是否有独立的供电系统和冷却系统等划分）。

2.2.2 EC2的通信机制

在EC2服务中，系统各模块之间及系统和外界之间的信息交互是通过IP地址进行的。
EC2中的IP地址包括三大类：公共IP地址、私有IP地址和弹性IP地址。
EC2的实例一经创建就会动态地分配公共和私有IP地址。
公共IP地址和私有IP地址之间通过网络地址转换技术（NAT）实现相互之间的转换。
公共IP地址和t额定的实例相对应，在某个实例终结或被弹性IP地址替代之前，公共IP地址会一直存在，实例通过它和外界通信。

2.2.3 弹性负载平衡

弹性负载平衡功能允许EC2实例自动分发应用流量，从而保证工作负载不会超过现有能力，并且在一定程度上支持容错。
该功能可以识别出应用实例的状态，当一个应用运行不佳时，它会自动将流量路由到状态较好的实例资源上，直到前者恢复。

2.2.4 监控服务

使用CloudWatch时，用户只需要选择EC2实例，设定监视时间，CW就可以自动收集和存储监测数据。

2.2.5 自动缩放

可以按照用户自定义的条件，自动调整EC2的计算能力。适合周期性变化的应用程序。

2.2.6 服务管理控制台

是一种基于Web的控制环境，可用于启动、管理EC2实例和提供各种管理工具和API接口。

2.3 EC2的安全及容错机制

EC2允许用户随时更新实例状态，添加或删除实例。给防火墙的配置带来了麻烦。因此采用安全组（一组规则，决定哪些网络流量会被实例接受）。
用户的实例被创建时，如果没有指定安全组，系统自动分配一个默认组（只接受组内成员的消息）
用户在访问EC2时需要使用SSH密钥对（目前对网络上传输的数据进行加密的一种可靠协议）来登陆服务。
当用户创建一个密钥对时，其名称和公钥会被存储在EC2和实例中，用户保存自己的私钥。
在容错机制中，EC2使用弹性IP地址。
弹性IP地址和用户账号绑定而不是和某个特定的实例绑定。当系统正在使用的实例出现故障时，用户只需要将弹性IP地址通过网络地址NAT转换为新实例所对应的私有IP地址，将弹性IP地址和新实例关联起来，访问服务不会感到差异。

3. 简单存储服务S3

简单存储服务构架在Dynamo上，用于提供任意类型文件的临时或永久性存储。

3.1 S3的基本概念和操作

S3存储系统的基本结构：桶和对象。
桶：用于存储对象的容器，类似于文件夹。不可被嵌套；用户创建桶的数量被限制；桶的名称要求在S3服务器中是唯一的。
对象：是S3的基本存储单元，主要由数据（可以是任意类型）和元数据（数据内容的附加描述信息）组成。对象在所在桶中有唯一的键，桶名和键相结合用以识别对象。键在创建后无法修改（即S3中不能重命名）
版本控制智能对于桶内所有的对象启用，而无法具体对某个对象启用。
S3的基本操作：Get/Put/List（桶）/Delete/Head（对象）

3.2 S3的数据一致性模型

3.3 S3的安全措施

S3向用户提供包括身份认证和访问控制列表ACL的双重安全机制。

3.3.1 身份认证

S3中使用基于HMAC—SHA1（一种安全的基于加密Hash函数和共享密钥的消息认证协议，可以有效防止数据在传输过程中被截获和篡改）的数字签名方式来确认用户身份。
消息认证机制的成功在于一个加密的Hash函数、一个加密的随机密钥和一个安全的密钥交换机制。
具体实现过程P106

3.3.2 访问控制列表

访问控制列表是S3提供的可供用户自行定义的访问控制策略列表
五种访问权限P107（注意桶和对象的ACL是各自独立的，S3的ACL不具有继承性）
S3有三大类型的授权用户：所有者、个人授权用户（两种授权方式：电子邮件地址和用户ID）、组授权用户（一种是AWS用户组和所有用户组）。

4.非关系型数据库服务SimpleDB和DynamoDB

和S3不同，非关系型数据库服务组要用户存储结构化的数据，并为这些数据提供查找等基本数据库功能。

4.1 非关系型数据库和传统关系数据库比较

数据模型：关系数据库对数据有严格约束；非关系型数据库的key-value存储形式中，key和value可以使用任意的数据类型。
数据处理：关系数据库在可扩展方面有很多问题；非关系型数据库无法满足ACID要求。
接口层：关系数据库以SQL语言对数据进行访问；非关系数据库对数据操作大多通过API实现。
综上：关系数据库具有高一致性，在ACID方面很强，移植性很高；但在可扩展方面能力较弱，只能通过提高服务器的配置来提高处理能力。非关系数据库具有很高的可扩展性，可以通过增加服务器数量来不断提高存储规模，具有很好的并发处理能力；但由于缺乏数据一致性保证，所以处理事务性问题能力较弱，并且难以处理跨表跨服务器的查询。

4.2 SimpleDB

基本结构
域：用于存放具有一定关联关系的数据的容器。每个用户账户中的域名必须是唯一的。
条目：条目是属性的集合。
属性：属性是条目的特征
值：用于描述某个条目在某个属性上的具体内容，一个条目中的一个属性可以有多个值。

4.3 DynamoDB

Dynamo以表为基本单位，标中的条目同样不需要预先定义的模式。
与SimpleDB不同，Dynamo取消了对表中数据大小的限制；DynamoDB不再固定使用最终一致性数据模型，而是允许用户选择弱一致性或者强一致性。
以外DynamoDB还在硬件上进行了优化，采用固态硬盘作为支撑，并根据用户设定的读写流量限制预设来确定数据分布的硬盘数量。

4.4 SimpleDB和DynamoDB比较

SimpleDB中限制了每张表的大小，更适合于小规模负载的工作；但SimpleDB会自动对所有属性进行索引，提供了更加强大的查询功能。
DynamoDB支持自动将数据和负载分布到多个服务器上，并未限制存储在单个表中数据量的大小，适用于较大规模负载的工作。

5. 关系数据库服务RDS

5.1 RDS基本原理

RDS将MySQL数据库移植到集群中，在一定范围内解决了关系数据库的可扩展问题。
MySQL集群方式采用了Share-Nothing架构：每台数据库服务器都是完全独立的计算机系统，通过网络相连，不共享任何资源。当数据库处理能力不足时，可以通过增加服务器数量来提高处理能力，同时多个服务器也增加了数据库并发访问的能力。
集群MySQL通过表单划分的方式将一张大表划分为若干小表，分别存储在不同的数据库服务器上（从逻辑上保证了数据库的可扩展性）。划分主要根据业务的需要，如果划分得不科学，查询会频繁跨表单和服务器，性能严重下降。
集群MySQL通过主从备份和读副本技术提高可靠性和数据处理能力。

5.2 RDS的使用

用户和开发者的角度来说，RDS和一个远程MySQL关系数据库没什么两样。
可以通过两种工具对RDS进行操作：命令行工具和兼容的MySQL客户端程序。

6. 简单队列服务SQS

问题产生：想要构建一个灵活且可扩展的系统，需要低耦合度。因此需要解决低耦合情况下组件之间的通信问题。
问题解决：简单队列服务SQS是为了解决云计算平台之间不同组件的通信而专门设计开发的。

6.1 SQS基本模型

SQS由三部分组成：系统组件、队列和消息。
消息由发送者创建，接受对象为一个或多个组件
队列是存放消息的容器，类似于S3中的桶（队列在传递消息时会尽量先进先出，但允许用户在消息中添加有关的序列数据调整顺序。）

6.2 SQS的消息

消息组成：消息ID（系统返回给用户）、接收句柄（可用来对消息进行删除等操作）、消息体和消息体MD5摘要（消息体字符串的MD5校验和）
消息取样：队列中的消息是被冗余存储的（同一个消息放在多个服务器上），但会给用户查询队列中的消息带来麻烦，因此SQS采用了基于加权随机分布的消息取样。当用户发出查询命令后，系统在所有服务器上使用分布算法随机选出部分服务器，然后返回其中的队列消息副本。
消息的可见性超时值及生命周期：在传送消息过程中，SQS为保证其他组件不能看见用户消息，会将消息阻塞（即加一把锁）。为此引入可见性超时值。在计时器计时的过程中还可以对计时器进行扩展和终止的操作。

7. 内容推送服务CloudFront

CloudFront基于Amazon云计算平台实现的内容分发网络（CDN）。借助Amazon部署在世界各地的边缘节点，用户可以快速、高效地对由CloudFront提供服务的网站进行访问。

7.1 CDN

问题背景：用户在发出服务请求后，需要经过DNS服务器进行域名解析后得到所访问网站的真实IP，然后访问。
问题产生：网站服务器可以容纳的访问量有限；这种模式没有考虑访问者的地域问题；使用不同网络服务提供商服务的用户之间的互访速度也会受到限制。
问题解决：CDN技术通过将网站内容发布到靠近用户的边缘节点。这样可以减轻源服务器的负担，也可以减少整个网络中流量分布不均的情况
具体操作：DNS在对域名解析时不再返回网站服务器IP，而是返回了由智能CDN负载均衡系统选定的某个边缘节点的IP。用户利用这个IP访问边缘节点，然后边缘节点通过内部DNS解析出真实网站IP获取用户所需页面，最后向用户展示并保存。
好处：将网站的服务流量以比较均匀的方式分散到边缘节点中，减轻了网站源服务器的负担；地理位置较近，访问速度快；智能DNS负载均衡系统和各个边缘节点之间始终保持着通信联系，可以确保分配给用户的边缘节点始终可用且在允许的流量范围之内。
CDN实现需要的网络技术支持：负载均衡技术；分布式存储技术；缓存技术

7.2 CloudFront

CloudFromt利用Amazon设在全球的边缘节点来实现CDN。

基本概念

对象：希望利用CloudFront进行分发的任意一个文件
源服务器：存储需要分发文件的位置
分发：分发的作用是在CloudFront和源服务器之间建立一条通道
别名指向：实际上就是系统分配给用户域名的一个别名
有效期：文件副本在边缘节点上的存放时间，默认24h

CloudFront相当于CDN的智能DNS负载均衡系统，用户实际是和CloudFront交互而不是直接和S3中原始文件进行交互。

基本架构 P118
CloudFront 安全措施：1.向用户提供了访问日志 2. 只接受安全的HTTPS方式进行访问

8. 其他Amazon云计算服务

8.1快速应用部署Elastic Beanstalk 和服务模版CloudFormation

Elastic Beanstalk是一种简化在AWS上部署和管理应用程序的服务。用户只需要上传自己的程序，系统会自动地进行需求分配、负载均衡等具体部署细节。
CloudFormation的功能是为开发者和系统管理员提供一个简化的、可视的AWS资源调用方式。开发者可以直接利用其提供的模版或自己创建的模版方便地建立自己的服务。

8.2 DNS服务Route53

因为传统的DNS服务器在域名对应的IP地址变更后传播得非常缓慢，出现Rout53这一用来管理DNS、处理DNS请求的全新AWS。

8.3 虚拟私有云VPC

是一个安全可靠、无缝连接企业现有的基础设施和Amazon云平台的技术。

8.4 简单通知服务和简单邮件服务

简单通知服务SNS是一种Web服务，应用程序可以通过SNS发布消息，快速地传送给用户或其他应用程序的开发员。
简单邮件服务SES是一个简单的高扩展性和具有成本优势的电子邮件发送服务。只需要通过简单的API调用，并且采用了内容过滤技术。

8.5 弹性MapReduce服务

是一种便捷的分布式计算框架。采用了分而治之的思想。将复杂的分布式计算分解为Map和Reduce两个操作。通过EC2和S3实现。
步骤：1. 将相关数据（包括一个Mapper和一个Reducer执行代码）上传至S3；2. 用户向系统发送服务请求，系统启动一个由一定数量的EC2实例组成的集群系统（主从模式，运行Hadoop）； 3. 主节点将S3中的待处理数据划分为若干子数据集，从节点从S3下载子数据集；4. 每个从节点独自处理子数据集； 5. 处理完的数据再次汇总S3，用户下载即可。
注意概念“任务流”：除了第一个任务和最后一个任务外，其他的任务既作为上一个任务的输出，也作为下一任务的输入。

8.6 电子商务服务DevPay、FPS和Simple Pay

DevPay是主要针对开发者的软件销售及账户管理平台。
灵活支付服务FPS：支付服务，允许用户根据需要和实际情况对支付服务进行各种个性化的设置，使其和用户的电子商务平台更加契合。
简单支付服务Simple Pay：是一种允许顾客使用其Amazon账户进行支付的服务，商家只需要在相应的Web支付页面放置合适的按钮就可以使用户利用其Amazon账户进行支付。

8.7 Amazon执行网络服务FWS

是一个非常有用的代理订单执行网络服务。作用就是产品存储和销售业务的托管（Amazon替用户销售产品）

8.8 土耳其机器人

众包

8.9 数据仓库服务Redshift

是一种完全托管的PB级数据仓库服务。
特点：

Redshift采用了列式数据存储，更加适用于数据仓库存储和分析
Redshift采用了多种压缩技术，并对加载的数据自动选择最合适的压缩方案
Redshift具有大规模并行处理的能力

8.10 应用流服务AppStream和数据流分析服务Kinesis

AppStream允许开发人员将应用程序部署在AWS基础设施上，并以流传输的方式发送到不同的终端设备上
Kinesis是一种完全托管的数据流服务，用于实时地处理快速流转的数据，可以调集弹性网络服务来处理单一或分布式的大容量数据流

Hadoop2.0 简述

Hadoop2.0 提供分布式存储 HDFS 和分布式操作系统 Yarn 两大功能软件包。采用客户-服务器模式。
Hadoop主要应用领域：1. 构建大型分布式集群。提供海量存储和计算服务。2. 数据仓库（使用半结构化的 HDFS ）。3. 数据挖掘。

Hadoop2.0 体系架构

Hadoop2.0 包含 Common、HDFS、Yarn 和 MapReduce 这四个模块，其中 Common 主要为其他模块提供服务，MapReduce 只是 Yarn 模块里 Yarn 编程的一种方式。

公共组件 Common

是其他模块的公共组件，定义了程序员取得集群服务的编程接口，为其他模块提供公共API。
Common功能：

提供公用API和程序员编程接口
本地Hadoop库（当 Hadoop 压缩或解压数据时，为提高性能调用了本地库）
超级用户 superuser
服务级别认证
HTTP认证

分布式文件系统 HDFS

HDFS 提供高容错高扩展高可靠性的分布式存储服务，并提供服务访问接口。
采用了 master/slave 架构来构建分布式存储集群（容易向集群中任意添加或删除 slave ）。
HDFS 里用一系列块来存储一个文件，并且每个块都可以设置多个副本（块复制机制）。
NameNode 使用事务日志记录HDFS元数据的变化，使用映象文件存储文件系统的命名空间。
NameNode 启动时，从磁盘中读取映象文件和事务日志，把其中的事务都应用到内存中的映象文件上，然后将新的元数据刷新到本地磁盘的新的映象文件中，这样可以截去旧的事务日志。这个过程称为检查点。

HDFS 内部特性：

冗余备份（当DataNode启动时会遍历本地文件系统产生一份HDFS数据块和本地文件对应关系的列表即块报告）；
副本存放；
副本选择（尽量选离程序最近的副本）
心跳检测（NameNode 周期性地从集群中的每个DataNode接受心跳包和块报告确认该DataNode工作正常）；
数据完整性检测；
元数据磁盘失效（当NameNode重新启动时，总是选择最新的一致的映象文件和事务日志）；
简单一致性模型（文件一旦创建、写入和关闭之后就不需要再更改了）、流式数据访问；
客户端缓存（HDFS客户端在用户创建新文件时先把数据缓存到本地临时文件——>临时文件累计超过一个块大小时，客户端联系NameNode分配得一个数据块，同时文件名插入系统中——>文件关闭后，临时文件中未刷新数据也会传输到DataNode，NameNode收到消息文件已关闭才将文件创建操作写入日志进行存储）
流水线复制（NameNode 从前一个节点接收数据的同时，即时把数据传给后面的节点）
架构特征（硬件错误是常态而不是异常，错误检测并快速自动恢复是HDFS的核心设计目标）；
超大规模数据集

分布式操作系统 Yarn

分布式操作系统的基本功能是：管理计算机资源；提供用户（包括程序）接口。
Yarn任务执行过程图P191（重点）
Yarn执行过程：

作业提交：Client 向 ResourceManager 的 ApplicationManager 模块提交任务，ApplicationManager 选中某 NodeManager 的某 Container 来执行此应用程序的 ApplicationMaster。
任务分配： ApplicationMaster 向 ResourceManager 的 Scheduler 模块申请资源。
任务执行： ApplicationMaster 向选定的NodeManager 发送信息，让其启动其Container计算任务。
进度和状态更新：Container 向其所在的 NodeManager 回报计算进度，NodeManager 通过心跳包再汇报给ApplicationMaster。
任务完成：信息最终汇报给ApplicationManager，由其告知客户端任务结束。

Yarn典型拓扑图P192
ApplicationManager 是一个可变更的部分，可看作编程模版。只要实现不同的 ApplicationManager，就可以实现不同的编程模式。通过提供不同的编程模版，可以让更多类型的编程模型能够运行在 Hadoop 集群中。
Yarn 调度策略：

容量调度策略：CapacityScheduler 是一种多用户多任务调度策略，它以队列为单位划分任务，以Container为单位分配资源。（解读：固定资源事先分配完毕，即使一用户已闲置，另一工作中的用户也无法得到额外的集群资源）（多级队列：列队内部也可以新建属于自身的队列）
公平调度策略：FairScheduler是一种允许多个 Yarn 任务公平使用集群资源的可插拔式调度策略。当集群资源受限时，FairScheduler会将正在执行任务释放的部分资源分配给等待队列里的任务，而不是用此资源继续执行原任务。

MapReduce 编程步骤：

确定<key, value>对
确定输入类
Mapper阶段
Reducer阶段
数据输出

Hadoop 2.0 大家族

ZooKeeper

部分失败（在分布式环境下不知道一个操作是否已经失败）是分布式系统固有特征

ZooKeeper 简介

ZooKeeper（分布式锁）是一个高效的可靠的分布式协调服务。
ZooKeeper 工作过程：机器A上的进程Pa产生需要发送的消息后，将这条消息注册到 ZooKeeper 中，机器B上的进程Pb需要这条消息时直接从 ZooKeeper 中读取即可。（松耦合交互方式：交互双方不必同时存在，也不用彼此了解）
ZooKeeper 工作原理：集群中各台机器上的 ZooKeeper 服务启动后，它们首先会从中选择一个作为领导者，其他作为追随者。写操作必须发送到领导者，读操作可以在各个节点上实现。
ZooKeeper 选取领导时，内部采用的是原子广播协议：由某个新加入的服务器发起一次选举，如果该服务器获得一半以上的票数，则此服务器将成为整个 ZooKeeper 集群的领导者。

Hbase

Hbase 是基于 Hadoop 的开源分布式数据库，以 BigTable 为原型，设计并实现了具有高可靠性高性能列存储可伸缩实时读写的分布式数据库系统。
与一般关系型数据库在功能上的区别：

适合存储非结构化数据
Hbase 是基于列的而不是基于行的模式

Hbase 数据模型

数据的逻辑模型：用户对数据的组织形式；数据的物理模型：Hbase 里数据在 HDFS 上的具体存储形式。
Hbase 架构：Hbase 采用 Master/Slave 架构，使用了 ZooKeeper 来选定主 HMaster。
Client 端使用 Hbase 的 RPC 机制与 HMasterServer 进行通信。
通过 ZooKeeper，HMaster 可以随时感知到各个 HRegionServer 的健康状态
HMaster 是 Hbase 主节点，集群中每个时刻只有一个 HMaster 运行。
HRegionServer 主要负责响应用户 I/O 请求，向 HDFS文件系统中读写数据
Hbase 和关系型数据库的区别：

Hbase 只提供字符串数据类型，其他类型的只能靠用户自行处理。关系型数据库有丰富的数据类型
Hbase 数据操作只有很简单的插入、查询、删除、修改、清空等操作，不能实现表与表关联操作。
Hbase 基于列式存储，每个列族都由几个文件保存，不同列族的文件是分离的。关系型数据库基于表哥设计和行模式保存
Hbase 修改和删除数据实现上是插入带有特殊标记的新记录，而关系型数据库是数据内容的替换和修改
Hbase 为分布式设计，可以通过机器实现性能和数据增长

Pig

Pig 是一个构建在 Hadoop 上，用来处理大规模数据集的脚本语言平台。程序员或分析师只要根据业务逻辑写好数据流脚本，Pig 会将写好的数据流处理脚本翻译成多个 HDFS、Map和 Reduce 操作。
Pig 包括两部分，一部分用于描述数据流的语言，称为Pig Latin；另一部分是用于运行 Pig Latin 程序的执行环境。
当需要处理海量数据时，先用 Pig Latin 语言编写 Pig Latin 数据处理脚本，然后在 Pig 中执行 Pig Latin 程序，Pig会自动将 Pig Latin 脚本翻译成 MapReduce 作业，上传到集群，并启动执行。

虚拟化技术

虚拟化技术简介

虚拟化技术的核心思想是利用软件或固件管理程序构成虚拟化层，把物理资源映射为虚拟资源。
云计算中运用虚拟化技术主要体现在对数据中心的虚拟化上。数据中心是云计算技术的核心。
数据中心的虚拟化可以实现资源的动态分配和调度，提高现有资源的利用率和服务可靠性；可以提供自动化的服务开通能力，降低运维成本；具有有效的安全机制和可靠性机制，满足公众客户和企业客户的安全需求；同时也可以方便系统升级、迁移和改造。
数据中心的虚拟化是通过服务器虚拟化、存储虚拟化和网络虚拟化实现的。
服务器虚拟化是将一个或多个物理服务器虚拟成多个逻辑上的服务器，集中管理，能跨越物理平台而不受物理平台的限制
存储虚拟化是把分布的异构存储设备统一为一个或几个大的存储池，方便用户的使用和管理。
网络虚拟化是在底层物理网络和网络用户中间增加一个抽象层，该抽象层向下对物理网络资源进行分割，向上提供虚拟网络。

服务器虚拟化

服务器虚拟化的层次

寄居虚拟化

寄居虚拟化的虚拟化层一般称为虚拟机监控器VMM
VMM安装在已有的主机操作系统（宿主操作系统）上。通过宿主操作系统来管理和访问各类资源
这类虚拟化架构系统损耗比较大
寄居虚拟化架构图P251

裸机虚拟化

裸机虚拟化架构不需要在服务器上先安装操作系统，而是直接将VMM安装在服务器硬件设施中，本质上该架构中的VMM也可以认为是一个操作系统，一般称为Hypervisor，只不过是非常轻量级的操作系统。
裸机虚拟化架构图P252

服务器虚拟化的底层实现

CPU 虚拟化：CPU 虚拟化技术把物理 CPU 抽象成虚拟 CPU，任意时刻，一个物理 CPU 只能运行一个虚拟 CPU 指令。需解决正确运行（操作系统要在虚拟化环境中执行特权指令功能，而且各个虚拟机之间不能相互影响）和调度（VMM决定当前哪个虚拟 CPU 在物理 CPU 上运行，要保证隔离性、公平性和性能）两个问题。
内存虚拟化：内存虚拟化技术把物理内存统一管理，包装成多个虚拟的物理内存提供给若干虚拟机使用，每个虚拟机拥有各自独立的内存空间。内存虚拟化的思路是分块共享，内存共享的核心思想是内存页面的写时复制。
I/O 设备虚拟化：把真实的设备统一管理起来，包装成多个虚拟设备给若干个虚拟机使用，响应每个虚拟机的设备访问请求和 I/O 请求。

虚拟机迁移

虚拟机迁移是将虚拟机实例从源宿主机迁移至目标宿主机，并且在目标宿主机上能够将虚拟机运行状态恢复。
意义：可以保证云端的负载均衡，增强系统错误容忍度，当发生故障时，也能有效恢复。
从计划角度看，分为有计划迁移、针对突发事件的迁移
从虚拟机迁移的源和目的地角度来看，虚拟机迁移包括物理机到虚拟机的迁移、虚拟机到虚拟机的迁移、物理虚拟机到物理机的迁移

虚拟机动态迁移

实时迁移：保持虚拟机运行的同时，把它从一个计算机迁移到另一个计算机，并在目的计算机恢复运行的技术
迁移的步骤：

预迁移：先选好迁移的新主机
预定资源：确认对方是否有必需的资源
预复制：待迁移的虚拟机仍在运行，先把内存页复制到目的主机上
停机复制：虚拟机运行停止，把它的网络连接重定位到目的主机上
提交：目的主机已收到虚拟机映象，虚拟机所在主机销毁其上的虚拟机
启动：新主机上的虚拟机广播新的IP地址

迁移的内容

内存的迁移

Push 阶段：VM 运行中，把它的部分内存页面通过网络复制到目的主机上
Stop-and-Copy 阶段（静态迁移）：VM停止，把剩下页面复制到目的计算机上，然后在目的计算机上启动新的 VM
Pull 阶段：新的虚拟机运行中，如果访问到未被复制的页面则出现页错误并复制。

网络资源的迁移：可以通过发送 ARP 重定向包，将 VM 的 IP 地址与目的机器的 MAC 地址相绑定，之后的所有包就可以发送到目的机器上
存储设备的迁移：以共享的方式共享数据和文件系统，而非真正迁移

隔离技术

虚拟机隔离是指虚拟之间在没有授权许可的情况下，互相之间不可通信、不可联系的恶意中技术。是确保虚拟机之间安全和可靠性的一种重要手段。
内存隔离
网络隔离

存储虚拟化

虚拟化存储系统在原油存储系统结构上增加了虚拟化层，将多个存储单元抽象成一个虚拟存储池

存储虚拟化的实现方式

主要有三种：基于主机的存储虚拟化、基于存储设备的存储虚拟化、基于网络的存储虚拟化

基于主机的存储虚拟化

也称基于服务器的存储虚拟化或者基于系统卷管理器的存储虚拟化。
一般是通过逻辑卷管理来实现的。
虚拟机为物理卷映射到逻辑卷提供了一个虚拟层。

基于存储设备的存储虚拟化

也称基于存储控制器的存储虚拟化
主要是咋存储设备的磁盘、适配器或者控制器上实现虚拟话功能

基于网络的存储虚拟化

基于网络的存储虚拟化方式是在网络设备上实现存储虚拟化功能，包括基于互联设备和基于路由器两种方式
基于互联设备的虚拟化方法能够再专用服务器上运行，它在标准操作系统中运行，和主机的虚拟存储一样具有易使用、设备便宜等优点。
基于路由器的虚拟化方法指的是在路由器固件上实现虚拟存储功能

网络虚拟化

引入虚拟化技术之后，在不改变传统数据中心网络设计的物理拓扑和布线方式的前提下，可以实现网络各层的横向整合，形成一个统一的交换架构。
数据中心网络虚拟化分为核心层、介入层和虚拟机网络虚拟化三个方面
核心层网络虚拟化：主要指的是数据中心核心网络设备的虚拟化
接入层网络虚拟化：可以实现数据中心介入层的分级设计
虚拟机网络虚拟化：包括物理网卡虚拟化和虚拟网络转换机，在服务器内部虚拟出相应的交换机和网卡功能。

桌面虚拟化

桌面虚拟化是指利用虚拟化技术将用户桌面的镜像文件存放到数据中心。
目的：使用户的使用体验同他们使用桌面上的 PC 一样。
优点：将所有桌面虚拟机在数据中心进行托管并统一管理，同时用户能够获得完整的 PC 使用体验，网络管理员仅维护部署在中心服务器的系统即可，不需要再为客户端计算机的程序更新以及软件升级带来的问题而担心。

习题汇总

第一章

大数据现象是怎么形成的？

大数据产生的原因可以从 2 个方面来看：
一是数据产生方式的改变。过去的信息是由手工产生的，而随着人类进入信息社会，信息的产生越来越自动化。
二是人类的活动越来越依赖数据。产生数据的主要源头有：（1）人类的日常生活已经与数据密不可分（如使用个人智能设备产生的数据）；（2）科学研究进入了“数据科学”时代（科学研究产生的数据）；（3）各行各业也越来越依赖大数据手段来开展工作（各行各业工作过程中所产生的数据）。

云计算有哪些特点？

（1）超大规模。
（2）虚拟化。
（3）高可靠性。
（4）通用性。
（5）高可伸缩性。
（6）按需服务。
（7）极其廉价。

云计算按照服务类型可以分为哪几类？

（1）将基础设施作为服务，IaaS（Infrastructure as a Service）
（2）将平台作为服务，PaaS（Platform as a Service）
（3）将软件作为服务，SaaS（Software as a Service）

第二章

Google 云计算技术包括哪些内容？

Google 云计算技术包括：Google 分布式文件系统 GFS，分布式计算编程模型 MapReduce，分布式锁服务 Chubby，分布式结构化数据表 Bigtable，分布式存储系统 Megastore，分布式监控系统 Dapper，数据交互分析工具 Dremel 和 PowerDrill，等等。

GFS 采用了哪些容错措施来确保整个系统的可靠性？

（1）Master 容错。
Master 上保存着 GFS 的元数据（包括命名空间（Name）和 Chunk 映射表等），这些元数据及 Master 的操作日志保存在磁盘中，Master 出错时而磁盘数据完好时，可以通过磁盘数据恢复 Master。GFS 对 Master 进行远程实时备份，如果 Master 彻底死机，另外一台 Master 可以迅速接替其工作。
（2）Chunk Server 容错。
Chunk 是 GFS 的数据块，一个 Chunk 默认存储 3 个位于不同 Chunk Server 的副本，Master会检查 Chunk 的副本数，在出现 Chunk 副本丢失或不可恢复时，Master 自动将该副本复制到其他 Chunk Server。另外，Chunk 以文件的形式保存在 Chunk Server，Chunk 文件以 Block（64K）来划分，每一个 Block 对应一个 32 位的校验和，Chunk Server 会检查数据和检验和，如果不匹配就返回错误。

MapReduce 与传统的分布式程序设计相比有何优点？

MapReduce 封装了并行处理、容错处理、本地化计算、负载均衡等细节，还提供了一
个简单而强大的接口。通过这个接口，可以把大尺度的计算自动地并发和分布执行，使编程变得非常容易。另外，MapReduce也具有较好的通用性，大量不同的问题都可以简单地通过 MapReduce 来解决。

Chubby 的设计目标是什么？Paxos 算法在 Chubby 中起什么作用？

Chubby 的设计目标主要有：
（1）高可用性和高可靠性。
（2）高扩展性。
（3）支持粗粒度的建议性锁服务。
（4）服务信息的直接存储。
（5）支持通报机制。
（6）支持缓存机制。
Paxos 算法在 Chubby 中起到保证副本之间数据一致的作用（Chubby Cell（单元）中的所有副本都要保持完全一致）。

为什么 MapReduce 不适合实时数据处理？

MapReduce 是一种面向批处理的框架，在编写完成代码后，要提交到集群运行后才能
验证代码的正确性。如果代码有误需要修改，则需要反复反复修改——运行——验证。这种数据探索（Data Exploration）的方式比较耗时。而传统的 SQL 查询则是交互式的，用户提交完自己的请求后就可以在相对可以接受的时间内得到返回结果。

第三章

在 Dynamo 中添加一个新的节点时，原来各节点保存的数据是否需要改变？如果改变，应该如何变化？

在 Dynamo 中添加一个新的节点时，会使新节点的前驱节点保存的数据发生改变，原存
储在前驱节点上的部分数据会迁移到新节点上。而其他节点保存的数据不变。同样，在删除节点时，被删除节点的数据会迁移到其前驱节点上，而对其他节点没有影响。

简单存储服务 S3 与传统的文件系统有哪些区别？

（1）S3 构架在 Dynamo 上，本身就具有分布式的特点，是容错的存储系统；
（2）S3 存储内容的分层结构与传统文件系统不同，是以桶（Bucket）和对象（Object）作为其基本结构；
（3）S3 对数据内容的附加描述信息可以是系统默认的元数据，也可以是用户指定的自定义元数据，而传统的文件系统则不具有这种灵活性。

第五章

简述解压包方式部署 Hadoop 的弊端

使用解压包方式部署 Hadoop，要求用户对 Linux 较为熟悉，在逐个解压、配置 Hadoop 组件的过程中，步骤较多，烦琐且容易出错。

简述 Hadoop 2.0 安全机制，试分析其优缺点

系统安全机制由认证(authentication)和授权(authorization)两大部分构成。认证就是简单地对一个实体的身份进行判断；而授权则是向实体授予对数据资源和信息访问权限的决策过程。
Hadoop 2.0 中的认证机制采用 Kerbero 和 Token 两种方案，而授权则是通过引入访问控制列表（Access Control List，ACL）实现的。在 Hadoop 2.0 中，Client 与 NameNode 和 Client 与 ResourceManager 之间初次通信均采用了Kerberos 进行身份认证，之后便换用 Delegation Token 以较小开销，而 DataNode 与 NameNode和 NodeManager 与 ResourceManager 之间的认证始终采用 Kerberos 机制。
Hadoop YARN 的授权机制是通过访问控制列表（ACL）实现的，按照授权实体，可分为队列访问控制列表、应用程序访问控制列表和服务访问控制列表。

简述 Yarn 编程过程，再简述 MR 编程过程，说明二者有何关系

Yarn 是一个资源框架，由 RM（Resource Manager）和 NM（Node Manager）组成，RM 和 NM 不参与计算逻辑，计算逻辑代码由 Application Master 和 Client 实现，具体计算则由Application Master 和 Container 完成。
在资源框架中，RM 负责资源分配，NM 负责管理本地资源。在计算框架中，Client 负责提交任务，RM 启动任务对应的 Application Master，Application Master 则再向 RM 申请资源，并与 NM 协商启动 Container 执行任务。
Yarn 是资源框架，MR 是该资源框架下的编程模板。

试从架构上分析 Hadoop 的优缺点

Hadoop 是一个能够让用户轻松架构和使用的分布式计算平台。用户可以轻松地在
Hadoop 上开发和运行处理海量数据的应用程序。它主要有以下几个优点：
（1）高可靠性。Hadoop 按位存储和处理数据的能力值得人们信赖。
（2）高扩展性。Hadoop 是在可用的计算机集簇间分配数据并完成计算任务的，这些集簇可以方便地扩展到数以千计的节点中。
（3）高效性。Hadoop 能够在节点之间动态地移动数据，并保证各个节点的动态平衡，因此处理速度非常快。
（4）高容错性。Hadoop 能够自动保存数据的多个副本，并且能够自动将失败的任务重新分配。
由于 Hadoop 各组件采用了主从结构（如 HDFS、Yarn），并发访问较多时存在性能问题，并且仍存在单点故障的可能。

第七章

虚拟化技术在云计算中的哪些地方发挥了关键作用？

云计算中运用虚拟化技术主要体现在对数据中心的虚拟化上。数据中心虚拟化是通过服
务器虚拟化、存储虚拟化和网络虚拟化实现的。

← Java EE 笔记《数据结构》1-5章 →