04Google云计算技术

发表于 2020-08-19

本文字数： 8.2k 阅读时长 ≈ 7 分钟

为专业课复习用

简介

GFS

Google File System
支持海量存储

MapReduce

用于大规模数据集的并行运算。
主要功能：是提供了一个简单强大的接口，可以将计算自动的并发和分布执行。
从两方面提升了系统：
- 失效的计算机问题。
- MapReduce之间传输的数据都是经过压缩的，节省了带宽

BigTable

用来管理大规模结构化数据的分布式存储系统

Google文件系统GFS

系统架构

Google GFS是一个基于分布式集群的大型分布式文件系统，为MapReduce计算框架提供低层数据存储和数据可靠性支撑
GFS是一个构建在分布节点本地文件系统之上的一个逻辑文件系统，它将数据存储在物理上分布的每个节点上，但通过GFS将整个数据形成一个逻辑上整体的文件。

GFS的3个假设

硬件出错是正常而非异常
- 大量廉价、易损的硬件
- 必须保持文件系统整体的可靠性
主要负载是流数据读写
- 主要用于程序处理批量数据，而非用户的交互或随机读写
- 主要是追加写（插入写非常少）
需要存储大尺寸的文件
- GB或TB量级

GFS的设计思想🌿🌿

将文件划分为若干块（Chunk）存储
- 固定大小64M
通过冗余来提高可靠性
- 3个数据块服务器上存储副本
通过单个master来协调数据访问、元数据存储
- 结构简单，容易保持元数据一致性

系统架构

⚠️Client与Master之间只有控制信息，无数据信息，减少主服务器的负载。

系统节点分为三类角色🌿🌿🌿

Client 客户端

提供给App的访问接口
以库文件的形式提供

Master 主服务器

GFS的管理节点
负责整个文件系统的管理
🐰逻辑上只有一个

Chunk Server 数据块服务器

负责具体的存储工作
🐰创建冗余，避免服务器崩溃

GFS的实现机制

客户端首先访问Master节点，获取交互的Chunk Server信息，然后访问这些Chunk Server，完成数据存取工作。这种设计方法实现了控制流和数据流的分离。
Client与Master之间只有控制流，而无数据流，极大地降低了Master的负载。
Client与Chunk Server之间直接传输数据流🌿，同时由于文件被分成多个Chunk进行分布式存储，Client可以同时访问多个Chunk Server，从而使得整个系统的I/O高度并行，系统整体性能得到提高。

GFS的读操作/数据访问的过程 🌿

可以通过系统架构图来理解

在程序运行前，数据已经存储在GFS文件系统中；程序执行时，App告诉Master文件名或数据块索引是什么
Master根据文件名或数据块索引在其文件目录空间中查找和定位该文件或数据块，并找到数据块在具体哪些Chunk Server上；将位置信息返回给App
App根据返回的具体Chunk数据块位置信息，直接访问相应的CS
App根据返回的具体Chunk数据块位置信息，直接读取指定位置的数据进行计算处理

GFS的特点🌿

采用中心服务器模式
- 可以方便地增加Chunk Server
- Master掌握系统内所有Chunk Server的情况，方便进行负载均衡
- 不存在元数据的一致性问题
不缓存数据
- 文件操作大部分是流式读写，不存在大量重复读写，使用Cache对性能提高不大
- Chunk Server上数据存取使用本地文件系统
- 从可行性看，Cache与实际数据的一致性维护也极其复杂
在用户态下实现
- 用户态下有多种调试工具,利于开发
- Master和Chunk Server都以进程方式运行，单个进程不影响整个操作系统
- GFS和操作系统运行在不同的空间，两者耦合性降低

容错机制

Master容错🌿🌿🌿

三类元数据

命名空间，即整个文件系统的目录结构 --- 日志
Chunk与文件名的映射表 --- 日志
Chunk副本的位置信息
- 一个Chunk默认有3个副本
- 直接保存在各个Chunk Server上

Master故障

当Master发生故障时，在磁盘数据保存完好的情况下，可以迅速恢复以上元数据

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

Chunk Server容错

GFS采用副本的方式实现Chunk Server的容错
每一个Chunk有多个存储副本（默认为三个）
对于每一个Chunk，必须将所有的副本全部写入成功，才视为成功写入
相关的副本出现丢失或不可恢复等情况，Master自动将该副本复制到其他Chunk Server
GFS中的每一个文件被划分成多个Chunk，Chunk的默认大小是64MB

系统管理技术
- 大规模集群安装技术
  - GFS集群中通常有非常多的节点，需要相应的技术支撑
- 故障检测技术
  - GFS构建在不可靠廉价计算机之上的文件系统，由于节点数目众多，故障发生十分频繁
- 节点动态加入技术
  - 新的Chunk Server加入，只需裸机加入，大大减少GFS维护工作量
- 节能技术
  - Google采用了多种机制降低服务器能耗，如采用蓄电池代替昂贵的UPS

分布式数据处理MapReduce

产生背景

Google拥有海量数据，并且需要快速处理。
大数据分而治之
- 任务划分
- 结果合并

MapReduce

一个软件架构，一种处理海量数据的并行编程模式。
与传统的分布式程序设计相比，MapReduce封装了并行处理、容错处理、本地化计算、负载均衡等细节，还提供了一个简单而强大的接口。
MapReduce把对数据集的大规模操作，分发给一个主节点管理下的各分节点共同完成，通过这种方式实现任务的可靠执行与容错机制。

编程模型

Map函数

对一部分原始数据进行指定的操作。每个Map操作都针对不同的原始数据，因此Map与Map之间是互相独立的，这使得它们可以充分并行化。

Reduce操作

对每个Map所产生的一部分中间结果进行合并操作，每个Reduce所处理的Map中间结果是互不交叉的，所有Reduce产生的最终结果经过简单连接就形成了完整的结果集.

编程模型

两个主要的函数🌿🌿🌿

Map: (in_key, in_value) -> {(keyj, valuej) | j = 1…k}
Reduce: (key, [value1,…,valuem]) -> (key, final_value)

Map

输入参数：in_key, in_value，指明了Map需要处理的原始数据
输出结果：一组k-v对，中间结果

Reduce

输入参数：key, [value1,…,valuem]
工作：对这些对应相同key的value值进行归并处理
输出结果：（key, final_value），所有Reduce的结果并在一起就是最终结果

实现机制

Google MapReduce并行处理的基本过程

有一个待处理的大数据，被划分为大小相同的数据块(如64MB),及与此相应的用户作业程序
系统中有一个负责调度的主节点(Master),以及数据Map和Reduce工作节点(Worker)
用户作业程序提交给主节点
主节点为作业程序寻找和配备可用的Map节点，并将程序传送给map节点
主节点也为作业程序寻找和配备可用的Reduce节点，并将程序传送给Reduce节点
主节点启动每个Map节点执行程序，每个map节点尽可能读取数据进行计算
每个Map节点处理读取的数据块,并做一些数据整理工作(combining, sorting等)并将中间结果存放在本地；同时通知主节点计算任务完成并告知中间结果数据存储位置
主节点等所有Map节点计算完成后，开始启动Reduce节点运行；Reduce节点从主节点所掌握的中间结果数据位置信息，远程读取这些数据
Reduce节点计算结果汇总输出到一个结果文件即获得整个处理结果

容错机制🌿

MapReduce通过重新执行失效的地方来实现容错。

Master失效

Master会周期性地设置检查点（checkpoint），并导出Master的数据。一旦某个任务失效，系统就从最近的一个检查点恢复并重新执行。

由于只有一个Master在运行，如果Master失效了，则只能终止整个MapReduce程序的运行并重新开始。

Worker失效

Master会周期性地给Worker发送ping命令，如果没有Worker的应答，则Master认为Worker失效，终止对这个Worker的任务调度，把失效Worker的任务调度到其他Worker上重新执行。

案例分析

案例一----单词排序

怎样通过MapReduce完成排序工作，使其有序（字典序）呢？

步骤

对原始的数据进行分割（Split），得到N个不同的数据分块。
对每一个数据分块都启动一个Map进行处理。
采用桶排序的方法，每个Map中按照首字母将字符串分配到26个不同的桶中。
对于Map之后得到的中间结果，启动26个Reduce。

按照首字母将Map中不同桶中的字符串集合放置到相应的Reduce中进行处理。

案例二----单词计数

给定一个巨大的文本（如1TB），如何计算单词出现的数目？

步骤

定义Map和Reduce函数

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);
}

自动对文本进行分割
在分割之后的每一对<key,value>使用用户定义的Map进行处理，再生成新的<key,value>对
对输出的结果集归拢、排序(系统自动完成）
通过Reduce操作生成最后结果

分布式结构化数据表Bigtable

设计动机与目标

设计动机

需要存储的数据种类繁多
海量的服务请求
商用数据库无法满足需求

基本目标

广泛的适用性 —— 为了满足一系列Google产品而并非特定产品的存储要求
很强的可扩展性 —— 随时可以加入或撤销服务器
高可用性 —— 确保几乎所有的情况下系统都可用
简单性 —— 底层系统的简单性既可以减少系统出错的概率，也为上层应用的开发带来便利

数据模型

Bigtable数据的存储格式

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

🐰Bigtable可以看成key-value的形式，其中的key是行关键字+列关键字+时间戳

Bigtable的存储逻辑可以表示为：

(row:string, column:string, time:int64)→string

行(Row)
- 大小不超过64KB的任意字符串。表中的数据都是根据行关键字进行排序的。
- com.cnn.www就是一个行关键字，指明一行存储数据。URL地址倒排可以使同一地址域的网页将被存储在表中连续的位置,便于查找
- 🐰倒排？域名层次划分
子表(Tablet)
- 一个大表可能太大，不利于存储管理，将在水平方向上被分为多个子表

列(Column)
- 特定含义的数据的集合。
- BigTable将列关键字组织成为“列族”(column family),每个族中的数据属于同一类别,如anchor是一个列族，其下可有不同的表示一个个超链接的列关键字。
- 一个列族下的数据会被压缩在一起存放。
- 一个列关键字可表示为: 族名：限定词(family:qualifier)
- content、anchor都是族名；而cnnsi.com和my.look.ca则是anchor族中的限定词。
时间戳(time stamp)
- 很多时候同一个URL的网页会不断更新，而Google需要保存不同时间的网页数据，因此需要使用时间戳来加以区分。
- 🐰时间戳 int64，两种生成方式：
  - 系统默认（创建）
  - 用户定义（要求唯一）
- 为了简化不同版本的数据管理，BigTable提供给了两种设置：
  - 保留最近的n个版本数据
  - 保留限定时间内的所有不同版本数据

小结——行、列、时间戳

行

Bigtable的行关键字可以是任意的字符串，但是大小不能够超过64KB
表中数据都是根据行关键字进行排序的，排序使用的是词典序
同一地址域的网页会被存储在表中的连续位置

列

将其组织成所谓的列族（Column Family）
族名必须有意义，限定词则可以任意选定
组织的数据结构清晰明了，含义也很清楚
族同时也是Bigtable中访问控制（Access Control）的基本单元

时间戳

Google的很多服务比如网页检索和用户的个性化设置等都需要保存不同时间的数据，这些不同的数据版本必须通过时间戳来区分。
Bigtable中的时间戳是64位整型数，具体的赋值方式可以用户自行定义

无数据校验

每行都可存储任意数目的列
- BigTable不对列的最少数目进行约束
任意类型的数据均可存储
- BigTable将所有数据均看作为字符串
数据的有效性校验由构建于其上的应用系统完成

🐰BigTable不进行数据的有效性校验

系统架构

Bigtable的基本架构

Bigtable中Chubby的主要作用🌿

选取并保证同一时间内只有一个主服务器（Master Server）。
获取子表的位置信息。
保存Bigtable的模式信息及访问控制列表。

子表服务器

SSTable格式的基本示意

**_SSTable_是Google为Bigtable设计的内部数据存储格式。**🌿🌿🌿🌿🌿

所有的SSTable文件都存储在GFS上，用户可以通过键来查询相应的值。

子表实际组成

不同子表的SSTable可以共享
每个子表服务器上仅保存一个日志文件

🐰共享日志，每个子表服务器上的日志是共享日志的一个片段
Bigtable规定将日志的内容按照键值进行排序
每个子表服务器上保存的子表数量可以从几十到上千不等，通常情况下是100个左右

子表地址组成

Bigtable系统的内部采用的是一种类似B+树的三层查询体系

🐰元数据表：

根子表（保存其他子表的位置） + 其他元数据子表（保存用户子表的位置信息）

Bigtable 数据存储及读/写操作

较新的数据存储在内存中一个称为内存表（Memtable）的有序缓冲里，

较早的数据则以SSTable格式保存在GFS中。

🐰内存表（SSTable的缓存），达到阈值后冻结，经过次压缩变成SSTable，Bigtable再创建一个新的内存表

三种形式压缩之间的关系

🐰

内存表的空间有限，达到阈值后 ---- 次压缩

合并压缩 --- 定期进行

主压缩 --- 定期进行

主压缩成一个SSTable后，前面被压缩的都会被删除

性能优化

局部性群组(Locality Group)

Bigtable允许用户将原本并不存储在一起的数据以列族为单位，根据需要组织在一个单独的SSTable中，以构成一个局部性群组。

用户可以只看自己感兴趣的内容。对于一些较小的且会被经常读取的局部性群组，明显地改善读取效率。

压缩

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

压缩可以被用在构成局部性群组的SSTable中，可以选择是否对个人的局部性群组的SSTable进行压缩。

两步压缩

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

压缩的本质：寻找重复数据，用少的字节代替

布隆过滤器

一个很长的二进制向量和一系列随机映射函数

优点

布隆过滤器的速度快，省空间
不会将一个存在的子表判定为不存在

缺点

在某些情况下它会将不存在的子表判断为存在

小结

Google的云计算应用均依赖于四个基础组件

分布式文件存储，GFS
并行数据处理模型MapReduce
分布式锁Chubby
结构化数据表BigTable

Chubby的作用

为GFS提供锁服务，选择Master节点；记录Master的相关描述信息
通过独占锁记录Chunk Server的活跃情况
为BigTable提供锁服务，记录子表元信息（如子表文件信息、子表分配信息、子表服务器信息）

GFS的作用

存储BigTable的子表文件

子表：SSTable和日志文件
为第三方应用提供大尺寸文件存储功能
文件读操作流程
- API与Master通信，获取文件元信息
- 根据指定的读取位置和读取长度，API发起并发操作，分别从若干ChunkServer上读取数据
- API组装所得数据，返回结果

BigTable的作用

为Google云计算应用（或第三方应用）提供数据结构化存储功能

结构化 --- 字符串的形式存储
类似于数据库

没有事务处理的能力
为应用提供简单数据查询功能（不支持联合查询）
为MapReduce提供数据源或数据结果存储

MapReduce的作用

对BigTable中的数据进行并行计算处理（如统计、归类等）
使用BigTable或GFS存储计算结果

应用场景分析

应用场景分析1—— Google网站流量分析

基本功能

统计网站的基本数据，包括会话、综合浏览量、点击量和字节流量等等
分析网站页面关注度，帮助企业调整或增删页面
分析用户浏览路径，优化页面布局
分析用户访问来源链接，提高广告投资回报

应用的特征

海量数据 --- 需要存储海量的用户行为数据（如点击时间、位置等）海量用户 --- 需要为任意多的网站提供流量分析

技术路线

使用BigTable存储和检索数据，使用MapReduce统计数据

BigTable中的表设计

原始点击数据表

行键：点击时间

列键：网站URL、网站名称、用户IP地址、来源URL、目标URL…… 目前尺寸约200TB

统计数据表

行键：网站URL（倒排）

列键：点击次数（如记录最近一个月每日的访问次数等）、页面关注度（如记录网站页面的访问比率）、来源网站（如记录TOP10）、目标网站（如记录TOP10）…

每个列中记录的内容是字符串，Analytics在查询后需要解析字符串获得统计结果

可根据统计内容的增多来增加新的列

目前尺寸约20TB

业务流程分析

数据采集

数据来源
- 页面内嵌脚本
- 点击行为脚本
应用服务器获取到数据后，存入BigTable
数据存储流程

04Google云计算技术_pic17

数据处理

例如，统计网站(如xxx.com)过去一周网页访问比例
数据处理流程
Map操作
假设过去一周查询结果文件在GFS中包含M个Chunk，那么Master寻找M个空闲的Worker，分别处理这M个Chunk，得到每个网站中页面的访问次数
自动排序
对M个中间结果进行排序
Reduce操作
假设含N个网站，那么可以分配N台Worker分别处理单个网站的数据
写入数据
应用程序将分析结果写入统计数据表

数据查询

从数据统计表中查询xxx.com行获取对应列的数据，解析，得到并展示最终结果

应用场景分析2——Google搜索

Google搜索的总体业务流程

数据采集: Spider
数据整理
- 生成各类子表，如音乐表、生活搜索表、学术搜索表等
- 压缩数据表，清洗失效数据
数据检索

数据采集

通过若干Spider在网络上搜集数据
使用BigTable存储数据行键：倒排的URL 列键：网站名称、语言、HTML描述、图片、链接…… 时间戳：记录不同时刻的网页快照

数据整理（Google学术搜索）

数据抽取
- 寻找包含学术（论文）信息的网页数据，并结构化存储
- 学术（论文）信息抽取（分析参考文献、摘要等）
- 可能的技术方案：MapReduce+BigTable
数据统计
- 基于抽取的数据进行统计分析（如分析被引用次数等）
- 可能的技术方案MapReduce+BigTable
学术信息BigTable 行键：论文标题列键：作者、主题词、摘要、参考文献、期刊信息、被引用次数、下载链接……
如何获取论文统计数据（如论文引用次数）
步骤
- 分析论文信息表，MapReduce
- 归纳排序
- Reduce操作

简介

GFS

MapReduce

BigTable

Google文件系统GFS

系统架构

GFS的3个假设

GFS的设计思想🌿🌿

系统架构

系统节点分为三类角色🌿🌿🌿

GFS的实现机制

GFS的读操作/数据访问的过程 🌿

GFS的特点🌿

容错机制

Master容错🌿🌿🌿

三类元数据

Master故障

Chunk Server容错

系统管理技术

分布式数据处理MapReduce

产生背景

MapReduce

编程模型

Map函数

Reduce操作

编程模型

Map

Reduce

实现机制

Google MapReduce并行处理的基本过程

容错机制🌿

Master失效

Worker失效

案例分析

案例一----单词排序

案例二----单词计数

分布式结构化数据表Bigtable

设计动机与目标

设计动机

基本目标

数据模型

Bigtable数据的存储格式

小结——行、列、时间戳

行

列

时间戳

无数据校验

系统架构

Bigtable的基本架构

Bigtable中Chubby的主要作用🌿

SSTable格式的基本示意

子表实际组成

子表地址组成

Bigtable 数据存储及读/写操作

三种形式压缩之间的关系

性能优化

局部性群组(Locality Group)

压缩

布隆过滤器

优点

缺点

小结

Google的云计算应用均依赖于四个基础组件

Chubby的作用

GFS的作用

BigTable的作用

MapReduce的作用

应用场景分析

应用场景分析1—— Google网站流量分析

基本功能

应用的特征

技术路线

BigTable中的表设计

业务流程分析

数据采集

数据处理

数据查询

应用场景分析2——Google搜索

Google搜索的总体业务流程

数据采集