抽象的分布式概念

分布式系统的目标

可扩展性

系统能力、网络能力、处理能力等能够以合理的方式应对不断增加任务（能够通过扩展应对计算任务的增长）

大小扩展性

增加节点能够让系统计算能力线性增长；或者增加数据集合不会增加系统延迟

地理扩展性

通过使用多个数据中心来减少用户的查询的响应时间

管理扩展性

增加节点，不能增加管理系统的消耗（例如增加管理员等）

性能（延迟）

计算任务完成的资源时间消耗比

低延迟/低响应时间

例如web应用

高吞吐/任务处理率

例如Hadoop

计算资源的低利用

可用性（容错）

衡量方式：

用可用时间除以可用时间加上不可用时间之和Availability = uptime / (uptime +

Downtime

Availability% How much downtime is allowed per year?

90%("one nine") More than a month

99%("two nines") Less than 4 days

99.9%("three nines") Less than 9 hours

99.99%("four nines") Less than an hour

99.999%("five nines") ~ 5 minutes

99.9999%("six nines") ~ 31 seconds

处理方式

定义好可能出现的失败的情况，已经采取相应的措施。不能对未定义的失败情况进行容错处理

对程序员的友好性

编程模型的简单，明确的语义等

分布式系统目标的阻碍

在获得系统目标的时候，需要克服一些问题

1.增加节点数量，需要增加相应的存储计算能力

2.节点距离-----节点间的信息传输问题

独立节点的增加，增加了系统失败的可能性（降低了可用性与增加了管理开销）

独立节点的增加，可能需要增加了节点间的通讯(扩展时，性能下降)

增加物理距离增加了节点间通讯延迟

解决方式

Sla（服务等级协议）

抽象与模型

抽象的作用是去掉那些与解决问题无关的方面。模型定义了分布式系统的关键属性的行为方式。

系统模型（同步/异步）

失败模型（分区、拜占庭、crash-fail）

http://www.cnblogs.com/york-hust/archive/2012/03/28/2420853.html

这里的拜占庭将军问题在zk中有体现，通过大多数选举结果作为leader节点。

拜占庭将军问题 (ByzantineGenerals Problem)，

一致性模型(强一致/最终一致)

强一致性，编程友好，语义清晰，就像只存在一个数据集。

弱一直提供更低的延迟以及高可用

设计技术：分区和备份

分区好处：

通过定向数据到不同分区和限制数据数量的大小提高性能

分区通过允许部分失败提高可用性

备份好处：

提高性能和可用性

避免单点

备份缺点：

一致性问题的根源，必须有个合理的一致性模型。

系统模型

分布式系统的一个关键属性就是分布式；确切的说，是程序在分布式系统下有如下属性：

在独立节点并发执行

通过可能引入不确定性与消息丢失的网络连接。

没有共享内存与共享时钟

包含了以下隐喻：

每一个节点并发执行程序

知识本地化：节点只能快速访问本地状态，并且任何关于全局状态的信息都可能过时

节点可以独立失败或者从失败中恢复

消息延迟或者丢失(独立节点的失败，难以区分网络失败还是节点失败)

节点的时钟不同步

系统模型：一系列关于环境和分布式系统实现机制的假设

假设包含：

节点拥有的能力与失败情况

通讯连接的操作与失败情况

贯穿系统的属性，例如关于时序的假设

系统模型的节点

节点作为主机提供计算和存储。有以下能力：

程序执行能力

把数据存放在临时内存或者稳定磁盘的能力

时钟（可能并不保证精度）

系统模型里的通讯链路

通讯链路连接每一个独立节点，允许从各个方向发送消息。

许多算法假设在每一对节点存在一个独立链路，链路提供FIFO顺序的消息。链路只能传递已经发送的消息，发送的消息不能丢失

一些算法假设网络是可靠的：消息从不丢失也从不无限延迟。

当网络失败，然而节点自身是可以运行的，此时就发生了网络分裂（分裂时消息可能丢失或者延迟到分裂修复）

时序假设

因为信息传输只能在光速。假如节点之间距离不同，从一个节点到其他节点的消息将在不同时间、顺序到达。

时间假设是对现实情况考虑的抽象,有两个可能得选择：

同步系统模型

进程同步执行，上限在于消息传输延迟，每一个进程有个精确的时钟。同步时系统模型加强了许多关于时序的约束。模型假设节点有同样的体验：消息的发送接收有个最大的传输延迟，进程是逐步执行的。

异步系统模型

没有时间假设，进程有独立的执行效率，消息传输延时没有上限，时钟不存在。不能依赖时间。

一致性问题

两个系统属性：

网络分裂是否包含在失败模型里

同步和异步的时间假设

节点获得一致性，假如节点在某些值上达成一致。正式的说：

一致性：每一个正常的进程必须对同一个值达成一致

完整性：每个进程至多只能决定一个值，除非其他进程提交了其它值

终止性：所有进程最终达成一个决定

合法性：假如所有的进程提交同一个值V，所有进程决定V

一致性问题是许多商业分布式系统的核心，毕竟我们希望得到分布式系统可靠性和性能，而不需要处理分布式带来的不良后果。解决一致性问题可能其他相关的问题比如原子广播和原子提交

FLP不可能结果

据说在学术圈很重要。在异步系统模型中推导一致性问题（专业的说，是协定问题和一致性问题略微有点区别，协定问题是一致性问题的弱化形式）。Flp假设节点只能因为因为宕机而失败，网络是可靠的；时间假设是异步的系统模型（消息可以无限延迟）

FLP的结果表明：在一个异步系统遭受失败的时候不存在一个确切的算法解决一致性问题，即使消息不能给你丢失、至多一个节点可以失败、节点只能因为宕机失败（其实就是抛开网络失败的可能）

FLP强调了：当忽视消息传输延迟时，解决一致性问题的算法必须放弃安全性或者实时性

CAP理论

理解CAP理论的最简单方式是想象两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致，即丧失了C性质。如果为了保证数据一致性，将分区一侧的节点设置为不可用，那么又丧失了A性质。除非两个节点可以互相通信，才能既保证C又保证A，这又会导致丧失P性质。一般来说跨区域的系统，设计师无法舍弃P性质，那么就只能在数据一致性和可用性上做一个艰难选择。

原作者的澄清文章：

http://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed（英文版）

http://www.infoq.com/cn/articles/cap-twelve-years-later-how-the-rules-have-changed?utm_source=infoq_en&utm_medium=link_on_en_item&utm_campaign=item_in_other_langs（中文版）

Cap最初只是计算机科学家Eric brewer的推测。Cap是非常流行有用的方式去权衡系统设计的承诺。

理论表明了三种属性：

一致性：所有的节点同一时间看到同样的数据（单份的最新数据拷贝）

可用性：节点失败不会阻止存活节点的服务（数据高可用）

分区容错：即使因为网络问题或者节点失败导致消息丢失，系统依旧继续服务

只有两个属性能同时满足。

于是得到了三种组合：

CA：例子包含了严格的法人协议，例如两阶段提交

CP：主法人协议，最小分区不可用，例如paxos

AP:使用冲突检测的协议，例如Dynamo

带C的组合提供相同的一致性模型：强一致性。CA不能容忍任何节点失败，CP可以容忍小部分节点失败。CA系统不区分节点失败还是网络失败，所以必须停止接受写操作来避免引入不一致问题（多份拷贝）。CP系统通过强制两个分区非对称行为避免不一致现象，保存主分区，停止小分区。CP保留一定的可用性，同时保证单份拷贝的一致性.

一致性模型

强一致模型：

线性一致（时间戳的一致性，顺序一致性的加强版，可以理解为所有操作的串行）

顺序一致（时间无关性，保证可见性与原子性，只要求同一时刻的一致性）

弱一致模型：

Client-centric consistency models（客户端本地缓存保证不会从replica中读到老数据）

因果一致模型（与jvm中指令排序处理类似，保证单线程下的逻辑顺序）https://en.wikipedia.org/wiki/Causal_consistency

最终一致模型

时序

经常引用的文章：

http://research.microsoft.com/en-us/um/people/lamport/pubs/time-clocks.pdf（1978年的文章）

分布式编程是多机器解决单机能解决的问题的艺术。一个系统在同一时间只能做一件事，系统的操作就谓之全序操作。就像人一个一个的穿过同一个门，每一个操作都会有个明确的前驱和后驱。这是我们在分布式系统中想要保持的基本编程模型。

要保持全序，需要精确的时钟或者其他形式的通讯。可以通过完全精确的时钟对每个操作标明时间戳实现全序，或者使用某种分配顺序号的通讯机制来保持全序。

在某个集合中任意两个元素是顺序的二元关系，谓之全序；偏序在集合中不满足任意两个可比较的特性，是全序的弱化形式。全序和偏序都有如下特性：

传递性

非对称性

时间是顺序的来源，时间让我们可以定义操作的顺序。 一些情况下，时间只是像一个整数计数器。时间戳在程序中的解释：

顺序，顺序可以减少不可以预测性

间隔，真实世界的相对时间

解释，时间是个一般的可比较的值，时间戳的绝对值可以表达为日期

事件加上时间戳，变成了有序的；使用时间强制操作的特定顺序或者消息传递顺序；使用时间戳让某些事发生先于某些事。时序假设越强，系统对于解决“时间传感器“越脆弱。加强顺序假设会带来更多开销。我们越能容忍时间的不确定性，越能利用分布式计算。

关于时间是否在每处一致，有三个假设回答:

全局时钟说：是的

本地时钟说：是的，但是只是本地一致

没有时钟说：不

同步系统模型有个一全局时钟，部分同步时钟有本地时钟，异步系统模型没有时钟

全局时钟是全序的一种基本来源，然而时钟同步只能达到一个有限的精度，因为同步协议的延迟（NTP），因为全局锁时钟精度问题，所以使用向量时钟来追踪因果关系。

时间在分布式中的使用

时间的好处：

时间可以定义整个系统顺序

时间可以定义算法的边界条件。比如超时决定远程机器是否已经挂掉，或者网络延迟

顺序在分布式系统系统中非常重要，因为分布式的许多属性是针对操作或者事件顺序定义的：

正确性依赖于正确的事件顺序，例如分布式数据库中的序列化

当资源竞争时，顺序可以用作连接中断器。例如一个组件的两个顺序，满足第一个取消第二个

全局时钟允许两个操作在不同的机器上排序，而不需要两台机器通讯。没有全局时钟，为了决定顺序，我们需要两台机器通讯来决定顺序。

向量时钟(Lamport Lock)

这里的向量在程序表达中可能就是一个数组而已，假设时钟是不精确的，那么通过时间同步我们不能解决那么时间敏感的问题。向量时钟是LamportLock的一个扩展，向量时钟在于使用多个计数器。向量时钟是物理时钟的替代物（物理时钟依赖计数器和通讯决定分布式系统的事件顺序）。向量时钟提可供跨节点比较的计数器。

LamportLock有以下特性:

无论什么时候进程工作，都会增加计数器

无论什么时候进程发送消息，都包括这个计数器

当消息收到时，设置计数器为ＭＡＸ（ｌｏｃａｌ＿ｃｏｕｎｔｅｒ，ｒｅｃｉｅｉｖｅｄ＿ｃｏｕｎｔｅｒ）

向量时钟的特性：

无论什么时候进程工作，增加向量中该节点的逻辑时钟（计数器）

无论什么时候进程发送消息，都包含这个逻辑时钟向量的全部

当收到消息的时候：１更新每一个向量中的元素值（max(local, received)）２．增加代表当前节点的逻辑时钟值

向量时钟的代码表达（以下代码的正确性，应当是在单线程程序中成立）：

失败探测器（截止时间）

基于超时的失败探测器，可能带来过于激进或者过于保守的风险。

失败探测器由心跳消息和定时器实现。进程间交换心跳消息。如果超时前响应消息没有收到，那么进程就怀疑其他进程。基于超时的失败探测器带来了过度激进或者过度保守的风险。失败探测器需要达到一个什么样的精度来达到可用性。

关于失败探测器，他们用两种属性来刻画，完备性和准确性：

强完备性，每一个失败的进程最终都会被正常的进程怀疑

弱完备性，每一个失败的进程最终都被一些正常的进程怀疑

强精度，没有正常进程曾被怀疑过

弱精度，一些正常的进程曾被怀疑过

完备性比准确性更容易获得。确实，要获得完备性重要的是不永久等待。避免不正确的怀疑正常进程是非常困难的，除非你能假设一个精准的最大消息延时。假设最大延迟在同步系统模型中是成立的，那么失败探测也可以强精度的。

时间、顺序和性能

强加全序是可以的，但是代价高昂。降低了处理速度。通常保证事件以既定的顺序传递，可以让所有的操作穿过一个单一的节点。时间/顺序/同步是否真的需要是根据具体场景确定。通常不需要全部满足。CALM理论会详细讨论这个问题。

复制问题（replication）

复制问题是分布式中的问题之一。复制是一组通信问题，什么样的协定或通信模式给我们提供想要的性能和可用性特性？怎么能保证容错、持久性、非分裂当网络分裂和节点失败时。

客户端请求的时候，划分为四个阶段：

参考：http://www-users.cselabs.umn.edu/classes/Spring-2014/csci8980-sds/Papers/ProcessReplication/Understanding-Replication-icdcs2000.pdf

总的来说复制分为同步复制和异步复制。同步需要客户端等待更长时间；异步只需要主节点状态得到更改，就可以直接返回给客户端http://www.google.com/events/io/2009/sessions/TransactionsAcrossDatacenters.html

复制其他分类方式：

无分裂的复制技术（单一数据拷贝）

当部分节点失败，系统保证只有单一数据拷贝可用，保证复制的一致性（一致性问题）

问题范围包括：排他、leader选举、multicast、atomic broadcast

允许分裂的复制技术（multi-mastersystems）

主从复制：异步复制大部分提供弱持久保证，可能存在数据丢失问题或者数据不正确问题、脑裂问题。

单静态Master

基于日志复制，从节点不参与执行操作

不受限于复制延迟

不能分区容错

手动failover，不能通过热备份来容错

两阶段提交

第一阶段，主节点对所有节点发送更新请求，每个从节点决定是否提交，当决定提交的时候，从节点存储更新数据到临时区域

第二阶段，主节点决定是否更新。并且通知每一个从节点，如果所有的从节点决定提交，更新生效。

两阶段假设数据稳定存储在每个节点不会丢失并且节点永远不会失败，两阶段提交如果一个节点失败会导致阻塞到节点恢复。根据cap理论两阶段是个ca系统。如果主节点失败，没有安全的方式选取一个新的主节点。两阶段在性能和容错方面有很好的平衡，多用于关系型数据库。但是新的系统经常采用分区容错一致算法，因为这种算法提供自动回复以及更好处理节点间延迟

全局一致性投票：提交或者取消

静态主节点

不能容忍协调器和提交时节点失败

不能容忍分区失败，对最小延迟节点敏感

分区容错的一致算法

Paxos, Raft, ZAB是分区容错一致性之一。

网络分区是指节点间不可达，节点并没有失败。分区容错的系统强制单份数据拷贝的一致性，网络分区时，只有系统的部分是活动的。为了保证不出现分裂，只能让部分可用。

分区容错的一致性算法依赖于主要节点，和两阶段提交不一样，只要大部分节点可用，系统就可以继续提供服务。

假如有失败，节点可能从新选举主要节点。

大部分投票决定主节点

动态主节点

协议容忍少数失败

最低延迟节点敏感性低

角色

通常算法采用一个固定的leader节点，所有的更新必须通过主节点，其他节点需要把请求转发到主节点。主节点仅仅意味着在正常运行期间主节点角色是固定的，如果失败后，角色是可以变的

复制：弱一致模型协议

强一致性，让分布式系统就像是一个系统，然而这样确带来了极大的花销，可用性和分区容错性是个很大的问题，此外对于每一个操作系统节点全部连接起来（2pc更是多达两次连接）。

也许我们希望的系统是能够写出不要太多协调开销的代码，但是任然返回“可用值“。我们可以允许部分不同的复制，而不是唯一真的复制。

最终一致性表达了这么一个观点：节点在某些时候不一致，但是节点最终会达成一致。