Consistency and Consensus
分布式环境里很多故障都会发生,最简单的做法就是整个服务失败,然后告诉用户错误信息.但在web环境中这是不可接受的,因此需要我们进行容错处理.这里我们将描述一些分布式容错算法,面临的故障包括包丢失,乱序,重发和任意延迟,包括时钟最多只是近似的环境,还包括节点暂停(可能是gc导致的)或故障.
建立容错机制最好的方法,就是能找到提供有用保证的通用抽象,然后让应用程序运行在这层抽象上.就像通过事务,应用程序无需关心节点故障A,并发I和存储问题D.分布式系统中,最重要的抽象就是一致性,这里一致性的含义是使得所有节点就某项决定达成共识,这样我们就不用考虑网络故障和节点失败问题了.
和事务类似,我们需要知道抽象的边界在哪里,什么能做什么不能做,提供的保证包含哪些,一致性的局限在哪里.这里的一致性分为内部一致性和外部一致性,内部一致性是系统内部达成一致,外部一致性是应用看到的视图(就算内部数据并不一致,可以通过某些手段返回给外部一致的结果).并且和事务的一致性都不一样.
一致性保证
大部分复制数据库都提供了最终一致性,这意味着如果你停止写入然后等不知道多久的时间,最终所有的读取操作都会返回一样的结果.也就是说不一致是暂时,最终都会达成一致.最终一致性更好的叫法是收敛,它并不保证什么时候这些副本会一致.
更强的一致性模型会有性能损失和较差的容错性.但是更易于使用.分布式一致性模型和事务里的隔离级别有些相似,但除了有些重叠大部分概念还是相互独立的.事务隔离性主要是为了避免并发执行事务时的竞态条件.而分布式一致性主要是为了协调副本的状态,在延迟和错误存在的条件下.
线性一致性
线性一直性,又叫做原子一致性,强一致性,瞬时一致性或者外部一致性.基本思路就是使得系统看起来好像只有一份数据,并且所有操作都是原子的.这样的话即使实际上有多份副本,但应用层并不需要了解.
简而言之.线性一致性就是能够看到最新的数据.
线性一致性和可串行化
可串行化是事务的一种隔离级别,每个事务都会读写多个对象.事务保证事务的执行行为就像按照某种线性顺序执行结果一样(每个事务在下一个事务开始前结束).即使事务实际执行的顺序和线下顺序并不一致.
线性一致性是针对读写的最新保证,它并不将所有操作都封装到事务里,所以不能避免写倾斜问题,除非采用其他的手段.
一个数据库可能提供两种保证,这被称为严格可串行化或者强单一副本可串行化.基于两阶段锁和实际串行执行实现的可串行化是典型的线性一致的.但是ssi就不是线性一致的.因为读取操作都是从快照读取的,不包含最新写入的值.
依赖线性一致性
锁和选主
单主复制系统需要确保系统有且只有一个主.常用的选主方法就是使用一个锁,无论锁怎么实现都必须是线性一致的,所以节点必须统一某个节点获取了锁.协调服务例如zk和etcd都被用来选主和实现分布式锁,还可以使用fencing令牌实现选择和锁.
约束和唯一性保证
唯一性约束在数据库里很常见,这时也需要线性一致性.
实际中,有时候可以放宽约束.这时候就不一定需要线性一致性了.
跨渠道的时间依赖
不同的信息交互渠道存在时,就需要线性一致性.
实现线性一致性系统
- 单主节点(有可能线性一致):如果读写都发送到主上,或者同步更新副本,则有可能是线性一致的.但是这取决于设计方式.
- 共识算法(线性一致):和单主复制结构类似,但能够避免脑裂和损坏副本.
- 多主复制(不能线性一致):并发写在多个节点上而且是异步复制,还会因此产生冲突,这种冲突就是缺乏单一数据副本的产物.
- 无主架构(可能不是线性一致的):版本向量+WRN看起来是强一致的,但是LWW里的时钟并不能保证和实际发生的时间是一致的,而且Sloppy quorums也会破坏线性一致性.
线性一致性和quorums
尽管看起来严格的quorum读写是线性一致的,但由于网络延迟的存在,仍然会有不一致出现:
这种情形下可以通过牺牲性能来获取线性一致性:读者必须执行读修复,写者必须读取最新的数据.Cassandra进行读时修复,但是由于采用lww解决冲突因此在并发写入时会丢失线性一致性.线性一致性的代价
CAP
- 如果应用需要线性一致性,而当部分副本因为网络问题无法和其他副本连接,那么这些副本不能处理任何请求,只能等待网络恢复或者返回用户错误信息,换句话说,它们是不可用的.
- 如果应用不提供线性一致性,每个副本都可以单独处理请求.当出现网络问题时,仍然能够可用,但无法保持线性一致性了.
不需要线性一致性的应用能够更容忍网络的问题,这个观点就是众所周知的CAP理论.CAP理论最好的解释应该是:在网络分区问题存在的情况下,是选择一致性还是可用性?
线性一致性和网络延迟
线性一致性很有用,但是很少系统会在实际上实现线性一致性.就算多核cpu上的RAM也不是线性一致性的.因为线性一致性对性能损耗太大.线性一致性已经被证明,读写请求响应的时间至少是正比于不确定的网络延迟时间的.
顺序保证
- 在单主拓扑结构里,的主要目的就是决定副本日志里的写入顺序,如果没有leader就会出现写入写入冲突
- 在事务中的可串行化隔离级别保证事务之间,按照某种序列顺序在执行.
- 时间戳和时钟在分布式系统中的应用,是另一种顺序定义方式.
事实证明,在顺序,线性一致性和一致性有着很深的关联.
顺序和因果
顺序很重要的一个原因,就是要保护因果关系:
- 在一致性读问题中,用户还没看到问题,就看到了回答就很奇怪.
- 在更新一条数据请求之前,必须要有创建这条数据的请求.
- happen-before关系.
- 在一致性的快照里,所有的因果关系都是被保证的.
- SSI通过追踪事务之间的因果关联来检测写倾斜.
因果加强了事件中顺序的重要性,如果一个系统服从因果导出的顺序关系,我们称之为因果一致性.
因果顺序不是全序
- 线性一致性:如果一个系统表现的如同只有一份数据拷贝,并且每个操作都是原子的,这意味着每个操作我们都能分辨出谁先于谁发生.
- 因果:因果中存在既不是你先于我也不是我先于你的并发操作,这意味着因果是部分有序的.
因此,在线性一致性的数据库里,是没有并发操作的,所有的操作都必须有序的按照单一时间线发生.因此多个请求需要等待处理,但是数据库在某个时刻只会原子的处理一个请求.
线性一致性强于因果一致性
线性一致性就意味着因果一致性,但是线性一致性的系统损害了性能和可用性,尤其是系统由明显的网络延迟时(比如系统按照地理位置分布).因此分布式系统一般放弃的线性一致性以获取更好的性能,但比较难使用.
当然线性一致性也不是保证因果的唯一方式,一个系统可以在实现因果一致性的基础上不损害系统性能.实际上,因果一致性是不因网络延迟而变慢,面对网络故障仍可用的最强可能的一致性模型.在很多情况下,系统实际上需要的并不是线性一致性而是因果一致性.
找出因果依赖
为了保持因果关系,我们需要找出因果依赖的操作.在无主拓扑结构中,我们通过版本向量来洞察单key的并发写操作来防止丢失更新.因果一致性需要获悉整个数据库的因果依赖,因此需要扩展版本向量.
序列号排序
我们可以使用序列号或者时间戳来排序事件,时间戳来自逻辑时钟(一般是自增长计数器).在单主结构中的数据库里,副本日志使用单调递增的序列号来绑定每个操作,从而保证了因果一致性.
无关联的序列号生成器
对于多主或者无主的数据库里,或者数据被分区了,怎么生成序列号呢?
- 每个节点独立生成自己的序列号,并且不同的节点生成的序列号不重复.
- 使用物理时钟来产生时间戳.
- 预先申请一批序列号给各个节点单独使用.
但是由于这些序列号并不能说明不同节点间的顺序关系.
lamport时间戳
lamport时间戳可以简化成一个数对(counter,node ID).每个节点和客户端负责追踪最大的counter数值,一旦节点发现来自客户端的counter数值大于当前维护的最大数值,就会立即更新最大值.
lamport和版本向量不同.版本向量是为了区分是否两个操作是并发的还是因果依赖的.而lamport时间戳总是强制全序的.而且也能够分辨并发和因果依赖.
不过时间戳有序还是不够的,因为你是在所有操作都获取的情况下,你可以进行比较排序.但是当其他节点发生的操作你不知道时,是没有办法获取最终的排序结果的.
全序广播
分区的数据库无法跨分区提供一致性保证.所有分区的全序是可能的,但需要额外的调度.全序的广播通常描述为一种交换节点间信息的协议,需要两个安全性条件被满足:
- 可靠分发:消息不能丢失,如果消息被分发到一个节点上,那么需要分发到所有节点上.
- 全序分发:分发到每个节点上的消息是同样的顺序.
使用全序广播
全序广播和一致性之间有很强的的关联.state machine replication是一种全序广播.全序广播可用于实现