分布式一致性

NAME

什么是一致性问题

以银行 ATM 为例，假设 A 的账户内有 200 存款，某一时刻 A 和其朋友 B 同时在不同的两个 ATM 机执行”取款 200“的操作，此时系统便出现了一致性问题，因为无论系统做出何种回应都会导致不一致的问题：

  • 系统接受一方的取款请求，拒绝另一方的取款请求：一方会认为系统不可用
  • 系统同时接受两个请求：账户发生透支
  • 系统同时拒绝两个请求：双方均认为系统不可用

解决一致性问题的算法

Lamport 面包店算法

每个请求先申请到一个独一无二的号码，然后按照号码小者优先的规则进行办理。即在分布式系统中维护一个全局的”排号系统“。

这要求高质量的硬件环境，参考谷歌利用GPS和原子钟使数据库全球范围信息同步。

Vector Clocks

同样由上面算法的作者 Lamport 提出，算是对上面算法的改进，去除了维护全局排号系统的负担。

该算法通过一系列计数器实现。还是 ATM 的例子，A、B 所用的 ATM 机需要自己维护一个计数器序列，每次操作将这个序列里自己的计数器加一，当 ATM 发送请求到系统时附带上该序列。假设两台 ATM 的计数器一开始都是 0，A 操作后将发送 [{a,1}, {b,0}]，B 操作后将发送 [{a,0}, {b,1}]，可以发现 A 发送的 b 比 B 发送的 b 要小，说明有冲突，此时按照时间顺序谁先到处理谁，后来的拒绝。假如同时到达则按 ATM 机的字母排号选择，即先 A 后 B。

注意，Vector Clocks 仅用来发现冲突，并不包含冲突的解决过程。Riak 和早期的 Cassandra、Dynamo 应用了该算法。但是该算法需要每次请求前先像其他节点获得对方计数器的最新版本，而且要给 Vector Clocks 预留存储空间，造成性能和资源消耗的加剧，因此效果不佳。

选举算法

首先在系统中通过既定的规则选举出一个 Master，其余节点都是 Slave，外来请求均通过 Master 来处理，Slave 仅需从 Master 节点同步数据即可。常见的算法实现比如 Paxos 和 Raft。

缺点是，当 Master 失效后系统会执行选举过程，这是系统会处于短暂的不可用状态。

Quorum NRW

一种从客户端侧解决一致性问题的投票算法，通过客户端同步操作多个实例来保证一致性，具体冲突解决由客户端实现，其主要数据思想来源于鸽巢原理，可以保证同一份数据对象的多份拷贝不会被超过两个访问对象读写。

分布式系统中的每一份数据对象都被赋予一票，每个操作必须要获得最小的读票数(Vr)或者最小的写票数(Vw)，才能进行读写。如果一个系统有 V 票，即一个数据对象有 V 份冗余拷贝，那么最小的读写票数必须满足：

  • Vr + Vw > V
  • Vw > V/2

第一条规则保证了一个数据库不会被同时读写。当一个写操作请求过来的时候，它必须要获得Vw个冗余拷贝的许可。而剩下的数量是V-Vw 不够Vr，因此不能再有读请求过来了。同理，当读请求已经获得了Vr个冗余拷贝的许可时，写请求就无法获得许可了。

第二条规则保证了数据的串行化修改，一份数据的冗余拷贝不可能同时被两个写请求修改。

比如一个拥有 5 节点的系统，该算法可以让写操作写完 3 台即返回，剩下的由系统进行同步；而读操作则至少需要读 3 台，才能保证读到一个最新的数据。

Rev Tree

类似于 Git 的版本树，对每次操作生成一个 Rev id，将每次操作的 Rev id 都放到上次操作之后形成主分支，当一个拥有不一致的 Rev Tree 的数据想要进行合并时冲突产生，这时会生成一个新的分支，然后两个分支同时工作。默认以最长分支为主分支，其他分支及数据会在一段时间后删除。因此有些场景中并不可行。

CouchDB 中应用了该算法，该算法把冲突的解决交给了时间，活跃度最高的数据被保留下来，适用于没有权威决策要求的去中心化系统。

区块链

这是比特币网络中用于记录交易过程生成总账本的算法，类似于上面的 Rev Tree，同时基于安全性需求增加了非对称加密、计算能力验证等逻辑。参考比特币的原理及运行机制。

CRDT

CRDT 值能够避免冲突的可复制数据结构，力图从数据结构上避免冲突，同时这类数据结构的合并过程都会满足 ACID 2.0：

  • 结合律：f(a,f(b,c)) = f(f(a,b),c)
  • 交换律：f(a,b) = f(b,a)
  • 幂等性：f(f(x))=f(x)

Reference