云计算(6) 分布式系统:计算和存储

六、分布式系统：计算和存储

1 分布式计算

1.1 概述

集中式计算：完全依赖一台大型的中心计算机的处理能力，即主机，与其相连的终端设备具有各不相同非常低的计算能力。实际上大多数终端完全不具有处理能力，仅作为输入输出设备使用。

分布式计算：多个通过网络互联的计算机都具有一定的计算能力，他们相互之间传递数据，实现信息共享，协作共同完成一个处理任务。

• 中国科学院：分布式计算就是在两个或多个软件互相共享信息，这些软件既可以在同一台计算机上，也可以在通过网络连接起来的多台计算机上运行

• 优势：稀有资源实现共享；在多台计算机上平衡计算负载；将程序放在最适合它的计算机上运行。

分布式系统：将海量计算能力才能处理的问题拆分成许多小块，将小块分配给同一套系统中不同的计算机节点处理，最后将分开计算的结果合并得到最终结果的系统。

• 通过网络消息实现数据通信与协调

分布式计算的一般步骤

• 设计分布式计算模型；分布式任务分配；编写并执行分布式程序【难点：计算任务划分 + 多节点通信】
  • 如何将复杂算法优化分解为适用于多个节点分别计算的小任务：特别是希望节点之间互不相干
  • 多数还是要相互通信的：消息队列；分布式存储

1.2 理论基础

1.2.1 ACID原则

ACID原则：数据库事务正常执行的四个原则

• 原子性(Atomicity)-事务中所有操作要么全都做完，要么都不做；只要一个操作失败，事务就失败，要回滚

• 一致性(Consistency)-数据库要处于原本的一致性状态

• 独立性(Isolation)-并发的事务不会相互影响，读数据不受影响，写数据也不能受到影响

• 持久性(Durability)-一旦事务提交后，它所作的修改应该永久保存在数据库上，即使宕机也不会丢失

在单台服务器能够完成数据库任务的时代，很容易实现ACID

但是随着单台服务器无法满足大规模数据存储，使用集群替代单台服务器，ACID难以得到高效的保证

1.2.2 CAP理论

CAP理论：一个分布式系统最多能够同时满足一致性(Consistency)、可用性(Availability)、分区容错性(Partition tolerance)中的两项

• 一致性——一次操作之后，所有节点同一时间的数据完全一致。从客户端角度看，更新过的数据在不同进程如何获取的不同策略，决定了不同的一致性。

  强一致性：更新过的数据，后续访问都能看到

  弱一致性：能容忍后续的部分或者全部访问不到

  最终一致性：如果经过一段时间后要求能访问到更新后的数据，称为最终一致性

• 可用性——服务一直可用且在正常的响应时间内。

• 分区容错性——分布式系统遇到某节点或网络分区故障时，仍然能够对外提供满足一致性和可用性的服务。

阐述与证明

如何取舍

• CA：但是某些分区始终存在，保证子系统CA
• CP：导致某些节点无法使用
• AP：导致全局数据不一致，但是高可用

对于大多数大型互联网服务而言，节点故障、网络故障是常态，均采取保证AP的策略，对于一致性退而求其次，只保证最终一致性

1.2.3 BASE理论

BASE理论——追求最终一致性

• Basically Available：基本可用-系统出现故障时，允许损失部分可用性，保证核心可用
• Soft State：软状态：允许系统存在中间状态，但中间状态不会影响系统的整体可用性
• Eventual Consistency：最终一致性-所有数据副本经过一定时间后，能最终达到一致的状态

1.2.4 一致性算法

一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

• 一台机器中多个进程/线程达成数据一致；
• 分布式文件系统或者分布式数据库中多客户端并发读写数据；
• 分布式存储中多个副本响应读写请求的一致性。

基于消息传递的一致性算法Paxos：https://www.cnblogs.com/linbingdong/p/6253479.html

基于消息传递的一致性算法Raft： https://raft.github.io/

Basic Paxos

• 提议者Proposer：向所有其他节点提出提案

  1. 准备：向所有其他决策者发送提案ID，等待回复
  2. 收到多数决策者的回应后，再发送提案Value

• 决策者Acceptor：回应提议者的提议

  • 如果已经收到过提议，则将ID和对应的Vaule返回
  • 如果没有收到过提议，则返回空
• 学习者Learner：不参与决策，只是从决策过程学习到最终的一致提案的Value

过程：分为三个阶段

1. Proposer发准备请求；Acceptors回应ID和Value，并许下承诺
   • 不再接收比当前提案ID小的或相同的提案的准备Prepare请求和Accept请求
2. Proposer收到多数回应后，发出带Value的Accept请求；Acceptors进行Accept处理
   • 从应答中选择提案ID最大的那个提案的Value作为本次要发起的提案Value
   • 如果所有应答都为空，则可以自己随意决定提案的Value
3. Proposer收到多数回应后，表示提案成功，立即将决议发送给所有Learner

能够有效解决选择主服务器的问题和保证大家都一致写入操作的问题

一致性Hash

一致性Hash——如何高效管理分布式存储集群，保证高容错和高可扩展性

• 初始化：计算服务器在环上位置；使用：计算数据在环上位置。

• https://www.enjoyalgorithms.com/blog/consistent-hashing-in-system-design

2 分布式系统

2.1 特性

容错性

• 我们可能永远也造不出永远都不出故障的机器，更加难以开发出永不出错的软件，因为软件在一定程度上还依赖硬件的可靠性

• 在大规模分布式系统中完全检测和避免所有可能发生的故障是不可能的，因此需要系统能够在某些节点发生故障的情况下，利用容错机制避免整套系统服务都不可用

高可扩展性

• 能够在运行过程中自由地对系统内部节点或现有功能进行扩充，而不影响现有服务的运行

开放性

• 开放性决定给了一个系统是否具备自我扩展和与其他系统集成的能力；开放的接口+接口遵循协议=更好

并发处理能力

• 分布式系统必须保证对象的操作在并发环境中能够安全的使用，保证数据一致性和系统高可用性

透明性

• 不需要让用户知晓分布式系统的内部细节，暴露给用户访问资源和服务的方式即可，用户将系统看作是一个整体。

2.2 类型

分布式存储系统

• 结构化存储：事务处理系统或关系型数据库，数据划分为表、字段和表关系，如分布式MySQL

• 非结构化存储：强调很高的可扩展性，存储数据非常自由，典型代表是分布式文件系统，如HDFS，GFS等

• 半结构化存储：为了解决非结构化数据随机访问性能差的问题，例如NoSQL，Key-Value Store，对象存储

• In-memory存储：基于内存的存储系统，利用内存实现极高读写性能，例如Memcached和Redis，做缓存

• NewSQL：既具备结构化存储的ACID事务支持，又拥有NoSQL半结构化存储的强大可扩展能力

分布式计算系统

• 传统基于消息的系统：MPI（Message Passing Interface），非常灵活，对应用程序无约束

• Dataflow系统：将计算抽象为高层算子，算子组合为有向无环图，由后端调度引擎并行化调度执行

  • Hadoop：MapReduce；Spark：更多类型的算子
  • 框架对程序的结构有严格的约束：算子、输入和输出等

• 流式计算、图计算、分布式机器学习——Spark都实现了这些类型的分布式计算

分布式资源管理系统：支持多种计算框架、高可扩展、高容错、高资源利用率、细粒度资源分配

• Yarn：Hadoop 2.0版本，解决了原来Hadoop扩展性较差的问题，可以在框架下自定义算子

• Apache Mesos：加州大学伯克利分校的一个研究项目，现在属于Apache基金会的一个项目

• Spark Standalone：Spark自带的简单的资源管理系统，负责跟踪集群状态并调度计算任务

• Kubernets：Google开发的一个强大的容器编排框架，用户通过Kubernets管理容器，不需要和底层交互

2.3 案例

网格系统（Grid）

• 一种能够整合的合作使用的由多家组织所拥有和管理的高端计算机、网络、数据库、实验设备等基础设施

• 网格是一类并行、分布式系统，能够在运行时动态分享、选择、聚合地理散布得自治资源，依据它们的可用性、能力、性能、代价以及用户对服务质量的需求，构建满足用户需求的设备组合

• 网格技术解决的主要问题是合作研究中的社会问题，包括：

  • 改善分布式管理，同时保持对本地资源的全面控制
  • 改善数据可用性，识别问题和数据访问模式的解决方案
  • 为学者提供友好的环境，能够访问更大范围的地理上分布的设备，提高产率

P2P系统（对等网络系统，Peer-to-Peer）

• 是一种在对等者之间分配任务和工作负载的分布式应用架构的系统；所有参与者的角色相同，都对外共享它们拥有的一部分硬件资源，这些资源可以被系统内其他参与者访问。性质：
  • 高度分散化：节点地理位置分散，系统资源的管理和任务处理也高度分散在各个节点
  • 自组织性：系统按照相互默契的规则，各尽其责而又协调地自动地形成有序结构；加入节点只需广播例如IP地址等必要的基本信息即可，无需额外操作。
  • 多管理域：最夸张的是每一个节点都由不同的组织、个人管理，每一个节点就是一个管理域
• 特点（优点）：部署门槛低；增长速度快；容错性高；资源的丰富性和多样性高
• 应用：共享及分发文件；流媒体；网络电话；志愿计算等

区块链（Block Chain）

• 一种去中心化、不可篡改、可追溯、多方共同维护的分布式数据库系统

• 集成了P2P协议、非对称加密技术、共识机制、块链结构等多种技术，解决数据的可信问题

2.4 分布式计算、存储、资源管理系统 Hadoop 2.0

Yarn做分布式资源管理；HDFS做分布式存储；MapReduce做分布式计算

为什么要分布式计算、存储系统呢？——单台机器无法解决问题，特别是大数据场景下

分布式存储

• 将多台机器硬盘以某种方式连接到一起
• 取机器cSlave0，cSlave1和cMaster0，采用客户-服务器模式构建分布式存储集群
• 让cMaster0管理cSlave0，cSlave1。

分布式计算

假设现有一些配置完全相同的机器cSlave0~cSlaveN，cMaster0，cMaster1，并且每台机器都有1个双核CPU，5GB硬盘。现有两个大小都是2GB的文件file0和file1。将file0和file1存入两台不同机器，统计file0和file1这两个文件里每个单词出现的次数。

分布式计算——Hadoop MapReduce框架 大致如下：

冗余存储与冗余计算

• 解决可靠性问题：不单纯依靠额外增加设备的备份
• 将每台机器上存储的数据同时存于集群中的另一台机器上
• 将每台机器上数据的计算也同时在冗余数据的机器上计算
  • CMaster0明确知道每一份数据都存储在多个地方
  • CMaster1会要求存有待计算数据的机器都参与计算，并选择先结束的机器计算结果
• 冗余存储不仅提高了分布式存储的可靠性，也提高了分布式计算的可靠性

资源管理

Yarn：管理计算机资源、提供用户和程序访问系统资源的API

任务调度策略是Yarn的核心问题，ResourceManager的Scheduler模块支持插拔，通过配置文件，用户可以个性化指定其调度策略。自带两种策略

• 容量调度算法CapacityScheduler：按照配置好的资源配比为不同层级的用户分配最大可用资源
• 公平调度算法FairScheduler：任务公平使用集群资源，短任务在合理时间内完成；长任务不至于永远等待

Yarn是可编程的，不仅仅支持自带的MapReduce，还可以自定义算子

一套编程协议

• Client负责提交任务，ApplicationMaster负责执行任务
• Client中与RM通信；ApplicationMaster与RM通信；ApplicationMaster与NM通信
• 编写符合协议的Client和ApplicationMaster即可

Hadoop默认实现了MapReduce的Client和ApplicationMaster

• MRClientService

• MRAppMaster

• Yarn处理MR程序时使用了各种默认的类

Scheduler也是可编程的

2.5 分布式计算和资源管理系统 Spark

没有类似HDFS的分布式文件（存储）系统，但是有一套分布式内存管理系统——也是其核心

Spark是建立在RDD(Resilient Distributed Datasets，弹性分布式数据集)之上的

RDD使得Spark可以用一致的方式处理大数据的不同应用场景

解决的具体问题——不能基于内存共享数据，反复读写磁盘

• Hadoop的MapReduce对迭代式算法支持的效率不高，如图算法和机器学习算法
• 交互式数据挖掘工具中反复查询一个数据子集

基于RDD的计算过程及相关术语

RDD的五大特性

1. 分区列表：记录了数据块所在的分区位置；一个RDD对应的数据是切分为数据块存储在集群的不同节点上的

2. 依赖列表：记录了当前这个RDD依赖于哪些其它的RDD

3. 计算函数compute，用于计算RDD各个分区的值

4. 可选：分区器，子类可以重新指定新的分区方式：Hash和Range

5. 可选：计算各分区时优先的位置列表。例如从HDFS文件生成RDD时，HDFS文件所在位置就是对应生成的RDD分区所在位置的优先选择

执行器 Executor——在Worker节点上运行，实际执行Task

• 将发送到worker节点上的打包好的程序反序列化，解析出Task的代码，创建新线程调用Task run函数

存储管理 Storage——分为通信层和存储层

• 通信层用来管理多个Worker之间的通信，传输控制和状态信息

• 存储层用来实际与设备交互，读写内存、磁盘、堆外内存，为数据在远程节点生成副本

Shuffle前后必不可少地需要网络I/O，通过数据序列化方法和压缩技术进行效率优化

• Spark中序列化方法和压缩算法的配置

Spark 1.0：基于Hash的Shuffle机制

• 每一个Mapper阶段的Task都会为Reduce阶段的每一个Task生成1个文件，M*R个

• 合并机制：每一个执行单位为Reduce阶段每一个Task生成1个文件

Spark 1.1：基于Sort的Shuffle机制

• 每一个Mapper阶段的Task生成两个文件：索引和数据文件，Reduce阶段通过索引读取

Spark 1.4：钨丝计划——优化内存管理模型

• 直接使用二进制数据，而不是Java对象；避免序列化和反序列化开销

3 分布式存储系统

3.1 类型

云计算中分布式计算主要作为“PaaS”，分布式存储则作为IaaS、PaaS、SaaS都有

根据存储的数据类型（结构化、非结构化、半结构化等），将存储系统分为以下几类

• 分布式文件系统——泛指以分布式的方式存储文件的系统，文件可以多种形式存在

  • 三种数据类型：Binary large object(Blob)二进制大对象，定长块，大文件
  • 提供不同类型的存储服务：对象存储、文件存储、块存储
  • 可以作为分布式健值存储、分布式表、分布式数据的底层存储。GFS，弹性块存储EBS，Ceph

• 分布式键值系统

  • 用来存储关系简单的半结构化数据，提供基于主键的CRUD功能
  • 可以看作是对分布式表的简化，一般用来作缓存，例如Memcached。一致性Hash是常用技术

• 分布式表

  • 用于存储半结构化数据；以表格为单位组织数据，一个表格有多行，通过主键标识一行
  • 不仅仅支持简单的CRUD，还支持扫描某个主键的范围和范围查找功能。Google Bigtable

• 分布式数据库

  • 基于传统关系型数据库发展而来，例如分布式MySQL

3.2 文件系统的发展

狭义上的“文件系统”——不同于分布式文件存储中的块存储、对象存储

单机文件系统

• 核心是使用树型数据结构组织文件、目录以及访问控制；随着单机能够管理的存储空间在变大，提升管理能力和性能的文件系统也在演化。

网络文件系统

• 目标是让用户能够以访问本地文件系统的方式访问远程机器上的文件，提供跨平台的文件共享系统

并行文件系统

• 用在大规模并行处理体系结构中，保证一个业务的多个并行任务可以同时对同一个文件的不同位置并行处理

分布式文件系统

• 采用集中式管理、分布式存储的架构，将文件实际存储在多个不同的节点上，且每一个部分都有多个副本

高通量文件系统

• 专指为大型数据中心设计的分布式文件系统，将数据中心所有的低成本存储资源有效地组织起来服务于上层多种应用的数据存储需求和数据访问需求

3.3 从单机到分布式

单机存储系统

• 硬件基础
• 存储引擎：实现数据的基本操作，包括增删改查，读取分随机读和顺序扫描，重点是数据结构
• 数据模型：存储系统的外壳，三类数据模型：文件、关系、健值；对应文件系统、数据库、健值存储

分布式存储系统

• 对单机的扩展，面临的重要问题是：

  • 如何将数据均匀的分布到多个存储节点
  • 如何保证提供高可用性的数据多副本始终保持一致
  • 如何检测节点故障并高效应对

• 评价指标

  • 性能：吞吐率-在某一段时间可以处理的请求总数；系统响应时间-从某个请求发出到收到结果的时间

    ==> 性能分析-性能优化、负载均衡、数据复制、故障检测

  • 可用性：指在系统面对各种异常时可以提供的正常服务能力；用停止服务的时间和正常时间比重度量

  • 一致性：越强的一致性模型用户使用起来越简单——可能牺牲可用性或分区容错性

  • 可扩展性：能否通过增加服务器数量提高系统能力或者增加服务器的难度；理想的“线性可扩展”