分布式系统:利用多台计算机协同解决单台计算机无法解决的计算、存储问题
单个节点<----->网络<----->单个节点<----->网络<----->单个节点
- 分布式系统三态:
* 成功
* 失败
* 超时:
* 某个节点宕机,无法返回成功信号
* 网络异常,无法发出/收到相应信号
- 副本 是指在分布式系统中为数据或者服务提供的冗余
* 数据副本是解决数据丢失异常的唯一手段
* 服务副本,是指数个节点提供某种相同的服务,这种服务一般并不依赖节点本地的存储,其所需数据一般来自其他节点
* 例如:GFS 的一个 chunk 的数个副本就是数据副本
* 而 mapreduce 的 job worker则是服务副本
##分布式VS单机:
工程应用:
实例 | 数据分布方案 |
---|---|
GFS、HDFS | 按数据量分布 |
mapreduce | 本地化计算 |
big talbe /hbase | 按数据范围 |
指按照特定的协议流程控制副本数据的读写行为,使得副本满足一定的可用性和一致性要求的分布式协议。
主要包含两大类:1、 中心化 2、 区中心化
在本协议中,副本被分为两大类,其中有且仅有一个副本作为primary副本,除primary的都时secondary副本。维护primary的节点作为中心节点,中心节点负责维护数据的更新、并发控制、协调副本的一致性。
与中心化副本系统协议最大的不同是,去中心化副本控制协议没有中心节点,协议中所有的节点都是完全对等的,节点之间通过平等协商达到一致
Lease 机制是最重要的分布式协议,广泛应用于各种实际的分布式系统中
?说明:
在一个 primary-secondary 架构的系统中,有三个节点 A、B、C 互为副本,其中有一个节点为 primary,且同一时刻只能有一个 primary 节点。另有一个节点 Q 负责判断节点 A、B、C的状态,一旦 Q 发现 primary 异常,节点 Q 将选择另一个节点作为 primary。假设最开始时节点 A为 primary,B、C 为 secondary。节点 Q 需要判断节点 A、B、C 的状态是否正常。
由中心节点向其他节点发送 lease,若某个节点持有有效的 lease,则认为该节点正常可以提供服务。用于例 2.3.1 中,节点 A、B、C 依然周期性的发送 heart beat 报告自身状态,节点 Q 收到 heart beat后发送一个 lease,表示节点 Q 确认了节点 A、B、C 的状态,并允许节点在 lease 有效期内正常工作。节点 Q 可以给 primary 节点一个特殊的 lease,表示节点可以作为 primary 工作。一旦节点 Q 希望切换新的 primary,则只需等前一个 primary 的 lease 过期,则就可以安全的颁发新的 lease 给新的primary 节点,而不会出现“双主”问题。
在实际系统中,若用一个中心节点发送 lease 也有很大的风险,一旦该中心节点宕机或网络异常,则所有的节点没有 lease,从而造成系统高度不可用。为此,实际系统总是使用多个中心节点互为副本,成为一个小的集群,该小集群具有高可用性,对外提供颁发 lease 的功能。chubby 和 zookeeper都是基于这样的设计
GFS 中使用 Lease 确定 Chuck 的 Primary 副本。Lease 由 Master 节点颁发给 primary 副本,持有Lease 的副本成为 primary 副本。Primary 副本控制该 chuck 的数据更新流量,确定并发更新操作在chuck 上的执行顺序。GFS 中的 Lease 信息由 Master 在响应各个节点的 HeartBeat 时附带传递(piggyback)。对于每一个 chuck,其上的并发更新操作的顺序在各个副本上是一致的,首先 master选择 primary 的顺序,即颁发 Lease 的顺序,在每一任的 primary 任期内,每个 primary 决定并发更新的顺序,从而更新操作的顺序最终全局一致。当 GFS 的 master 失去某个节点的 HeartBeat 时,只需待该节点上的 primary chuck 的 Lease 超时,就可以为这些 chuck 重新选择 primary 副本并颁发 lease。
是一种最简单的副本控制规则,顾名思义即在更新时写所有的副本,只有在所有的副本上更新成功,才认为更新成功,从而保证所有的副本一致,这样在读取数据时可以读任一副本上的数据。
其实现需要依赖一种假设:
假设有一种 magic 的机制,当某次更新操作 wi 一旦在所有 N 个副本上都成功,此时全局都能知道这个信息,此后读取操作将指定读取数据版本为 vi 的数据,称在所有 N 个副本上都成功的更新操作为“成功提交的更新操作”,称对应的数据为“成功提交的数据”。在 WARO 中,如果某次更新操作 wi 在某个副本上失败,此时该副本的最新的数据只有 vi-1,由于不满足在所有 N 个副本上都成功,则 wi 不是一个“成功提交的更新操作”,此时,虽然其他 N-1 个副本上最新的数据是 vi,但 vi 不是一个“成功提交的数据”,最新的成功提交的数据只是 vi-1
<span data-type="background" style="background-color:#FADB14">这里需要特别强调的是,在工程实践中,这种 magic 的机制往往较难实现或效率较低。</span>
WARO 牺牲了更新服务的可用性,最大程度的增强读服务的可用性。下面将 WARO 的条件进
行松弛,从而使得可以在读写服务可用性之间做折中,得出 Quorum 机制:
在 Quorum 机制下,当某次更新操作 wi 一旦在所有 N 个副本中的 W 个副本上都成功,则就称该更新操作为“成功提交的更新操作”,称对应的数据为“成功提交的数据”。<span data-type="background" style="background-color:#FADB14">令 R>N-W</span>,由于更新操作 wi 仅在 W 个副本上成功,所以在读取数据时,最多需要读取 R 个副本则一定能读到 wi 更新后的数据 vi 。如果某次更新 wi 在 W 个副本上成功,由于 W+R>N,任意 R 个副本组成的集合一定与成功的W个副本组成的集合有交集,所以读取R个副本一定能读到wi更新后的数据vi。如图 2-10,Quorum 机制的原理可以文森图表示。
<span data-type="background" style="background-color:#FADB14">仅仅依赖 quorum 机制是无法保证强一致性的。因为仅有 quorum 机制时无法确定最新已成功提交的版本号,除非将最新已提交的版本号作为元数据由特定的元数据服务器或元数据集群管理,否则很难确定最新成功提交的版本号</span>
Quorum 机制的三个系统参数 N、W、R 控制了系统的可用性,也是系统对用户的服务承诺:数据最多有 N 个副本,但数据更新成功 W 个副本即返回用户成功。对于一致性要求较高的 Quorum 系统,系统还应该承诺任何时候不读取未成功提交的数据,即读取到的数据都是曾经在 W 个副本上成功的数据。
在 primary-secondary 协议中,当 primary 异常时,需要选择出一个新的 primary,之后 secondary副本与 primary 同步数据。通常情况下,选择新的 primary 的工作是由某一中心节点完成的,在引入quorum 机制后,常用的 primary 选择方式与读取数据的方式类似,即中心节点读取 R 个副本,选择R 个副本中版本号最高的副本作为新的 primary。新 primary 与至少 W 个副本完成数据同步后作为新的 primary 提供读写服务。首先,R 个副本中版本号最高的副本一定蕴含了最新的成功提交的数据。再者,虽然不能确定最高版本号的数是一个成功提交的数据,但新的 primary 在随后与 secondary 同步数据,使得该版本的副本个数达到 W,从而使得该版本的数据成为成功提交的数据。
GFS 使用 WARO 机制读写副本,即如果更新所有副本成功则认为更新成功,一旦更新成功,则可以任意选择一个副本读取数据;如果更新某个副本失败,则更显失败,副本之间处于不一致的状态。GFS 系统不保证异常状态时副本的一致性,GFS 系统需要上层应用通过 Checksum 等机制自行判断数据是否合法。值得注意的是 GFS 中的 append 操作,一旦 append 操作某个 chunck 的副本上失败,GFS 系统会自动新增一个 chunck 并尝试 append 操作,由于可以让新增的 chunck 在正常的机器上创建,从而解决了由于 WARO 造成的系统可用性下降问题。进而在 GFS 中,append 操作不保证一定在文件的结尾进行,由于在新增的 chunk 上重试 append,append 的数据可能会出现多份重复的现象,但每个 append 操作会返回用户最终成功的 offset 位置,在这个位置上,任意读取某个副本一定可以读到写入的数据。这种在新增 chunk 上进行尝试的思路,大大增大了系统的容错能力,提高了系统可用性,是一种非常值得借鉴的设计思路。
分布式系统原理介绍
日志技术是宕机恢复的主要技术之一
Redo Log 更新流程
从 Redo Log 的宕机恢复流程也可以看出,只有写入日志文件的更新结果才能在宕机后恢复。这也是为什么在 Redo Log 流程中需要先更新日志文件再更新内存中的数据的原因
宕机恢复流量的缺点是需要回放所有 redo 日志,效率较低,假如需要恢复的操作非常多,那么这个宕机恢复过程将非常漫长。解决这一问题的方法即引入 check point 技术。在简化的模型下,checkpoint 技术的过程即将内存中的数据以某种易于重新加载的数据组织方式完整的 dump 到磁盘,从而减少宕机恢复时需要回放的日志数据。
Paxos 协议是少数在工程实践中证实的强一致性、高可用的去__中心化分布式协议__
Paxos 协议的流程较为复杂,但其基本思想却不难理解,类似于人类社会的投票过程。Paxos 协议中,有一组完全对等的参与节点(称为 accpetor),这组节点各自就某一事件做出决议,如果某个决议获得了超过半数节点的同意则生效。Paxos 协议中只要有超过一半的节点正常,就可以工作,能很好对抗宕机、网络分化等异常情况。
CAP 三个字母分别代表了分布式系统中三个相互矛盾的属性:
热力学第二定律说明了永动机是不可能存在的,不要去妄图设计永动机。与之类似,CAP 理论的意义就在于明确提出了不要去妄图设计一种对 CAP 三大属性都完全拥有的完美系统,因为这种系统在理论上就已经被证明不存在。
参考:[分布式系统原理·刘杰]
内容来源于网络,如有侵权,请联系作者删除!