云计算-06-分布式计算

概述

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

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

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

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

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

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

分布式计算的一般步骤：设计分布式计算模型；分布式任务分配；编写并执行分布式程序

难点：

计算任务划分：如何将复杂算法优化分解为适用于多个节点分别计算的小任务：特别是希望节点之间互不相干

多节点通信：多数还是要相互通信的：消息队列；分布式存储

理论基础

ACID 原则

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

原子性（Atomicity）-事务中所有操作要么全都做完，要么都不做；只要一个操作失败，事务就失败，要回滚
一致性（Consistency）-数据库要处于原本的一致性状态
独立性（Isolation）-并发的事务不会相互影响，读数据不受影响，写数据也不能受到影响
持久性（Durability）-一旦事务提交后，它所作的修改应该永久保存在数据库上，即使宕机也不会丢失

在单台服务器能够完成数据库任务的时代，很容易实现 ACID。但是随着单台服务器无法满足大规模数据存储，使用集群替代单台服务器，ACID 难以得到高效的保证。

CAP 理论

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

一致性——一次操作之后，所有节点同一时间的数据完全一致。从客户端角度看，更新过的数据在不同进程如何获取的不同策略，决定了不同的一致性。有强一致性、弱一致性、最终一致性等多个等级。
可用性——服务一直可用且在正常的响应时间内。
分区容错性——分布式系统遇到某节点或网络分区故障时，仍然能够对外提供满足一致性和可用性的服务。

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

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

BASE 理论

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

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

一致性算法（共识算法）

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

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

问题：选哪个作主服务器？什么时候确定写入？

Basic Paxos

提议者 Proposer：向所有其他节点提出提案
1. 准备：向所有其他决策者发送提案 ID，等待回复
2. 收到多数决策者的回应后，再发送提案 Value
决策者 Acceptor：回应提议者的提议
1. 如果已经收到过提议，则将 ID 和对应的 Vaule 返回
2. 如果没有收到过提议，则返回空
学习者 Learner：不参与决策，只是从决策过程学习到最终的一致提案的 Value 过程：分为三个阶段
1. Proposer 发准备请求；Acceptors 回应 ID 和 Value，并许下承诺，不再接收比当前提案 ID 小的或相同的提案的准备 Prepare 请求和 Accept 请求。
2. Proposer 收到多数回应后，发出带 Value 的 Accept 请求；Acceptors 进行 Accept 处理。从应答中选择提案 ID 最大的那个提案的 Value 作为本次要发起的提案 Value。
3. Proposer 收到多数回应后，表示提案成功，立即将决议发送给所有 Learner。如果所有应答都为空，则可以自己随能够有效解决选择主服务器的问题和保证大家都一致写入操作的问题意决定提案的 Value。

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

Raft

Raft：http://thesecretlivesofdata.com/raft/

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

初始化：计算服务器在环上位置；使用：计算数据在环上位置。
https://www.enjoyalgorithms.com/blog/consistent-hashing-in-system-design

分布式系统

特性

容错性：我们可能永远也造不出永远都不出故障的机器，更加难以开发出永不出错的软件，因为软件在一定程度上还依赖硬件的可靠性；在大规模分布式系统中完全检测和避免所有可能发生的故障是不可能的，因此需要系统能够在某些节点发生故障的情况下，利用容错机制避免整套系统服务都不可用
高可扩展性：能够在运行过程中自由地对系统内部节点或现有功能进行扩充，而不影响现有服务的运行
开放性：开放性决定给了一个系统是否具备自我扩展和与其他系统集成的能力；开放的接口+接口遵循协议=更好
并发处理能力：分布式系统必须保证对象的操作在并发环境中能够安全的使用，保证数据一致性和系统高可用性
透明性：不需要让用户知晓分布式系统的内部细节，暴露给用户访问资源和服务的方式即可，用户将系统看作是一个整体。

类型

分布式存储系统：

结构化存储：事务处理系统或关系型数据库，数据划分为表、字段和表关系，如分布式 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 管理容器，不需要和底层交互

案例

网格系统（Grid）

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

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

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

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

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

是一种在对等者之间分配任务和工作负载的分布式应用架构的系统；所有参与者的角色相同，都对外共享它们拥有的一部分硬件资源，这些资源可以被系统内其他参与者访问。性质：

高度分散化：节点地理位置分散，系统资源的管理和任务处理也高度分散在各个节点
自组织性：系统按照相互默契的规则，各尽其责而又协调地自动地形成有序结构；加入节点只需广播例如 IP 地址等必要的基本信息即可，无需额外操作。
多管理域：最夸张的是每一个节点都由不同的组织、个人管理，每一个节点就是一个管理域

特点（优点）：部署门槛低；增长速度快；容错性高；资源的丰富性和多样性高

应用：共享及分发文件；流媒体；网络电话；志愿计算等

区块链（Block Chain）

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

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

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

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

分布式存储系统

类型

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

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

分布式文件系统：泛指以分布式的方式存储文件的系统，文件可以多种形式存在三种数据类型：
- Binary large object（Blob）二进制大对象，定长块，大文件
- 提供不同类型的存储服务：对象存储、文件存储、块存储
- 可以作为分布式健值存储、分布式表、分布式数据的底层存储。GFS ，弹性块存储 EBS Ceph
分布式健值系统：用来存储关系简单的半结构化数据，提供基于主键的 CRUD 功能。可以看作是对分布式表的简化，一般用来作缓存，例如 Memcached 。一致性 Hash 是常用技术
分布式表：用于存储半结构化数据；以表格为单位组织数据，一个表格有多行，通过主键标识一行；不仅仅支持简单的 CRUD ，还支持扫描某个主键的范围和范围查找功能。 Google Bigtable。
分布式数据库：基于传统关系型数据库发展而来，例如分布式 MySQL

文件系统的发展

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

单机文件系统：核心是使用树型数据结构组织文件、目录以及访问控制；随着单机能够管理的存储空间在变大，提升管理能力和性能的文件系统也在演化。
网络文件系统：目标是让用户能够以访问本地文件系统的方式访问远程机器上的文件，提供跨平台的文件共享系统
并行文件系统：用在大规模并行处理体系结构中，保证一个业务的多个并行任务可以同时对同一个文件的不同位置并行处理
分布式文件系统：采用集中式管理、分布式存储的架构，将文件实际存储在多个不同的节点上，且每一个部分都有多个副本
高通量文件系统：专指为大型数据中心设计的分布式文件系统，将数据中心所有的低成本存储资源有效地组织起来，服务于上层多种应用的数据存储需求和数据访问需求

从单机到分布式

单机存储系统:

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

分布式存储系统：

对单机的扩展，面临的重要问题是：
- 如何将数据均匀的分布到多个存储节点
- 如何保证提供高可用性的数据多副本始终保持一致
- 如何检测节点故障并高效应对
评价指标
- 性能：吞吐率。在某一段时间可以处理的请求总数；系统响应时间从某个请求发出到收到结果的时间
- 可用性：指在系统面对各种异常时可以提供的正常服务能力；用停止服务的时间和正常时间比重度量
- 一致性：越强的一致性模型用户使用起来越简单。可能牺牲可用性或分区容错性
- 可扩展性：能否通过增加服务器数量提高系统能力或者增加服务器的难度；理想的“线性可扩展”