EfonMark

一番码客 : 挖掘你关心的亮点。
http://www.efonmark.com

本文目录:

[TOC]

image-20191130084641612

核心问题

随着摩尔定律碰到瓶颈,越来越多的系统要依靠分布式集群架构来实现海量数据处理和可扩展计算能力。

区块链其实是一种分布式系统。

中央式结构改成分布式系统,碰到的第一个问题就是一致性的保障。

很显然,如果一个分布式集群无法保证处理结果一致的话,那任何建立于其上的业务系统都无法正常工作。

一致性问题

什么是一致性

在分布式系统中,一致性(Consistency,早期也叫 Agreement),是指对于系统中的多个服务节点,给定一系列操作,在协议(往往通过某种共识算法)保障下,试图使得它们对处理结果达成某种程度的一致。

如果分布式系统能实现“一致”,对外就可以呈现为一个功能正常的,且性能和稳定性都要好很多的“虚处理节点”。

举个例子,某影视公司旗下有西单和中关村的两个电影院,都出售某电影票,票一共就一万张。那么,顾客到达某个电影院买票的时候,售票员该怎么决策是否该卖这张票,才能避免超售呢?当电影院个数更多的时候呢?这个问题在人类世界中,看起来似乎没那么难。

注意:一致性并不代表结果正确与否,而是系统对外呈现的状态一致与否,例如,所有节点都达成失败状态也是一种一致。

挑战

实际上,如果分布式系统中各个节点都能保证以十分强大的性能(瞬间响应、高吞吐)无故障的运行,则实现共识过程并不复杂,简单通过多播过程投票即可。

很可惜的是,现实中这样“完美”的系统并不存在,如响应请求往往存在时延、网络会发生中断、节点会发生故障、甚至存在恶意节点故意要破坏系统。

一般地,把故障(不响应)的情况称为“非拜占庭错误”,恶意响应的情况称为“拜占庭错误”(对应节点为拜占庭节点)。

共识协议

要保障系统满足不同程度的一致性,往往需要通过共识算法来达成。

非拜占庭错误:一般包括 Paxos、Raft 及其变种。

拜占庭错误:一般包括 PBFT 系列、PoW 系列算法等。从概率角度,PBFT 系列算法是确定的,一旦达成共识就不可逆转;而 PoW 系列算法则是不确定的,随着时间推移,被推翻的概率越来越小。

FLP不可能原理

  • FLP 不可能原理:在网络可靠,存在节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性算法。

  • http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility/

    三个人在三个不同房间里面投票,ABC,C经常睡着。

    先别这么悲观,学术界做研究,考虑的是数学和物理意义上最极端的情形,很多时候现实生活要美好的多(感谢这个世界如此鲁棒!)。

    例如,上面例子中描述的最坏情形,总会发生的概率并没有那么大。工程实现上多试几次,很大可能就成功了。

    科学告诉你什么是不可能的;工程则告诉你,付出一些代价,我可以把它变成可能。这就是工程的魅力

    那么,退一步讲,在付出一些代价的情况下,我们能做到多少?另外还有个博弈学上的概念,科学上告诉你去赌场赌博从概率上总会是输钱的;工程则告诉你,如果你愿意接受最终输钱的结果,中间说不定偶尔能小赢几笔呢!

CAP原理

分布式计算系统不可能同时确保一致性(Consistency)、可用性(Availablity)和分区容忍性(Partition),设计中往往需要弱化对某个特性的保证。

  • 一致性(Consistency):任何操作应该都是原子的,发生在后面的事件能看到前面事件发生导致的结果,注意这里指的是强一致性;
  • 可用性(Availablity):在有限时间内,任何非失败节点都能应答请求;
  • 分区容忍性(Partition):网络可能发生分区,即节点之间的通信不可保障。

ACID原则

数据库设计的原则

即 Atomicity(原子性)、Consistency(一致性)、Isolation(隔离性)、Durability(持久性)。

ACID 原则描述了对分布式数据库的一致性需求,同时付出了可用性的代价。

  • Atomicity:每次操作是原子的,要么成功,要么不执行;
  • Consistency:数据库的状态是一致的,无中间状态;
  • Isolation:各种操作彼此互相不影响;
  • Durability:状态的改变是持久的,不会失效。

一个与之相对的原则是 BASE(Basic Availiability,Soft state,Eventually Consistency),牺牲掉对一致性的约束(最终一致性),来换取一定的可用性。

Paxos

1990 年由 Leslie Lamport 提出的 Paxos 共识算法,在工程角度实现了一种最大化保障分布式系统一致性(存在极小的概率无法实现一致)的机制。

Paxos 被广泛应用在 Chubby、ZooKeeper 这样的系统中,Leslie Lamport 因此获得了 2013 年度图灵奖。

故事背景是古希腊 Paxon 岛上的多个法官在一个大厅内对一个议案进行表决,如何达成统一的结果。他们之间通过服务人员来传递纸条,但法官可能离开或进入大厅,服务人员可能偷懒去睡觉。

算法中将节点分为三种类型:

  • proposer:提出一个提案,等待大家批准为结案。往往是客户端担任该角色;

  • acceptor:负责对提案进行投票。往往是服务端担任该角色;

  • learner:被告知结案结果,并与之统一,不参与投票过程。可能为客户端或服务端。

Raft

Raft是paxos的一个简单实现。

包括三种角色:leader、candidate 和 follower,其基本过程为:

  • Leader 选举:每个 candidate 随机经过一定时间都会提出选举方案,最近阶段中得票最多者被选为 leader。

  • 同步 log:leader 会找到系统中 log 最新的记录,并强制所有的 follower 来刷新到这个记录。

可靠性指标

可用度A 9的个数 年停机时间(分钟) 适用产品
0.999 三个9 500 电脑或服务器
0.9999 四个9 50 企业级设备
0.99999 五个9 5 一般电信级设备
0.999999 六个9 0.5 更高要求电信级设备

一般来说,单点的服务器系统至少应能满足两个九;

普通企业信息系统三个九就肯定足够了(大家可以统计下自己企业内因系统维护每年要停多少时间),系统能达到四个九已经是业界领先水平了(参考 AWS)。

电信级的应用一般号称能达到五个九,这已经很厉害了,一年里面最多允许五分钟的服务停用。

六个九和以上的系统,就更加少见了,要实现往往意味着极高的代价。

那么,该如何提升可靠性呢?有两个思路:一是让系统中的单点变得更可靠;二是消灭单点。

IT 从业人员大都有类似的经验,运行某软系统的机器,基本上是过几天就要重启下的;而运行 Linux 系统的服务器,则可能几年时间都不出问题。另外,普通的家用计算机,跟专用服务器相比,长时间运行更容易出现故障。这些都是单点可靠性不同的例子。

可以通过替换单点的软硬件来改善可靠性。然而,依靠单点实现的可靠性毕竟是有限的,要想进一步的提升,那就只好消灭单点,通过主从、多活等模式让多个节点集体完成原先单点的工作。这可以从概率意义上改善服务的可靠性,也是分布式系统的一个重要用途。

参考


一番雾语:区块链核心是分布式,分布式核心在一致性。


免费知识星球: 一番码客-积累交流
微信公众号:一番码客
微信:Efon-fighting
网站: http://www.efonmark.com

蜀ICP备19039940号

总访问量为