为什么要使用分布式存储/计算
现如今计算机需要处理的数据量越来越大, 然而摩尔定律却前正在慢慢失效中, 我们无法在维持成本不变的情况下制造出性能翻倍的芯片了, 这意味着人们要花比以前多得多的金钱才能造出能够处理这么多数据的机器. 既然如此, 人们就想到能不能把现有的机器集合起来协同处理这些数据, 达到更高效率; 而且这样做还能够带来其他好处, 比如过去一台机器提供服务, 机器挂了服务就挂了, 如果现在许多台机器共同提供服务, 就能避免这个问题. 如何让这众多的机器很好地协作, 这就是分布式所研究的领域了.
分布式系统的特性
从上面的解释我们可以看出, 分布式系统最重要的特性就是其具备扩展性, 注意理解扩展性的含义:
- Scalability is the ability of a system, network, or process, to handle a growing amount of work in a capable manner or its ability to be enlarged to accommodate that growth.
--- Distributed systems for fun and profit 这里扩展性是指分布式系统应当能够随着要工作规模的提升同步提升自己的处理能力, 并且是以 "适当的方式" 提升处理能力. 怎么理解这个 "适当的方式" 呢? 就是在提升自身处理能力的时候不要给原有系统带来其他方面的开销. 比如说:
- 不能因为添加机器, 数据要多往一些机器上同步而使得数据访问变慢
- 也不能因为添加了这些机器就带来额外的运维管理开销
性能与可用性
对任何系统来说, 性能和可用性是最重要的两个方面, 分布式系统也不例外. 性能有很多指标可以衡量, 比如低延迟, 高吞吐量, 低 cpu 使用率. 可用性是系统能够时刻保持可用的能力, 系统在正常运行的情况下当然是可用的, 而一旦系统出现了问题, 可不可用就不好说了. 但如果系统在出错的情况下仍能够保持可用那自然是最好的, 所以可用性也可以认为是系统的容错能力. 与单机系统相比, 在考虑分布式系统的性能与可用性问题时, 我们不得不把这两个因素考虑进来:
- 节点数量 (增加节点也带来了额外的节点通信)
- 节点之间的物理距离 (距离产生时延)
系统模型
在抽象分布式系统模型时, 需要考虑几个问题:
- 单个节点是否可靠, 会发生什么问题?
- 通信链路是否可靠, 会发生什么问题?
- 节点之间的通信是同步还是异步? 节点之间如何达成一致?
在设计分布式系统时, 对于上述三个问题处理的越周全, 系统就越可靠. 很多系统都假设链路是可靠的, 不会发生消息丢失 (tcp 协议可以很大程度的保证这一点), 但显然一个健壮的系统不应想当然的认为链路是可靠的, 这就是两军问题. 另外对于单个节点来说, 很多系统认为单个节点的问题只是会 crash, 但实际上单个节点还可能会作恶估计发出假消息, 这就是拜占庭将军问题.
同步与异步
这里有必要多说一下同步和异步的概念. 同步指的是该发生的总会让它发生; 异步指的是不要仰仗时间长它就会发生.
分区 or 复制?
数据怎么分配给分布式系统中的各个节点就引出了两种方式, 分区表示把数据分成许多部分分配给不同的几点, 复制指的是将数据完整的拷贝给各个节点. 虽然后者开销看起来大, 但是前者一般和应用层相关性很大, 不好施展, 而且对于大部分应用来说, 简单的分区并不能防止单点故障造成的数据丢失风险, 所以分布式系统一般还是侧重复制方面的研究. 然而复制也引出了很多其它的问题, 最重要的就是一致性 (共识) 问题.
一致性共识
一致性共识问题是分布式系统中最重要的问题. 一致性共识包含以下四层意思:
- Agreement: 所有节点应当对同一个值达成一致 (也称为共识的安全性, safety)
- Integrity: 每个节点最多只能对一个值投票, 而不是多个
- Termination: 所有节点最终应总能够达成一致 (也称为共识的活性, liveness)
- Validity: 如果所有好节点投票同一个值, 那么这些好节点一定对这个值达成一致
说到一致性, 就不得不结合我们上面介绍过的系统模型来讨论, 因为在不同的系统模型下, 一致性问题也是不同的. 在我们的系统模型中对单节点问题, 通信链路可靠, 以及同步/异步会做一些假设, 假设不同影响着能否达成一致性. 具有一票否决权的是通信链路, 理论证明, 如果通信链路不可靠的话, 是肯定不能达成一致性的, 就算你是同步系统, 就算你单点不会发生故障, 都无法达成一致, 这也是著名的两军问题[1]. 当两军问题被证明不可解, 意味着我们就没有必要浪费时间为不可靠链路设计共识算法了. 我们将目标放在相对更弱化一点的模型上, 那就是:
- 假设链路可靠
- 假设节点会出故障, 还会欺诈
- 假设是异步系统
然而之后的 FLP 理论又证实了在这样一个模型上也是不可能达成共识的. FLP 证明的是在异步系统中, 即便只有一个节点发生 crash, 也不可能达成共识, 更别说现实情况下不但不只一个节点会 crash, 而且节点还会欺诈了. 这下好了, 现在我们也不需要在费心思在异步系统上实现共识算法了[2]. 之后所有的共识算法都建立在假设链路可靠并且是同步系统的基础上, 另外节点故障这一点在现实中是不应当被避免的, 所以我们需要解决的就只剩下节点欺诈这一点了. 节点欺诈可以引申一下, 节点自身未必有意要成为恶意节点, 也可能是它被攻击被截持了, 这也是著名的拜占庭将军问题. 因此目前存在的共识算法可以统一分为两类: 解决拜占庭将军问题的和不解决拜占庭将军问题的.
安全性与活性
共识算法
摆明了不解决拜占庭将军问题的共识算法典型的有 paxos 和 raft. 意图解决拜占庭将军问题的算法有很多了, 尽管未必是彻底解决. 这些共识算法的出现也多亏了区块链的蓬勃发展, 下面的几个都是典型的区块链共识算法: PoW PoS DPoS DPoS + PBFT
参考
- tcp 三次握手是解决两军问题的一个尝试, 但并未解决. 有人说量子通信可以解决通信链路可靠性问题, 使得两军问题不复存在.
- 有人说 paxos 实现了异步共识, 实际上并没有, 详情可 google