分布式一致性

古城微笑少年丶 2022-08-23 05:49 297阅读 0赞

**分布式一致性**

分布式系统的一致性问题总是伴随数据复制而生， 数据复制技术在提高分布式系统的可用性、可靠性和性能的同时，却带来了不一致问题。 理想情况下， 多个副本应该是应用透明的， 从外界看来多副本如同单副本， 而事实上维护一致性非常困难。试想一下， 写入新数据时， 某副本所在的服务器宕机，或者突然发生了网络错误， 此时该如何处理？ 是继续重试等待故障消失呢，还是放弃写入故障副本？ 若继续重试写入， 则导致系统不可用，影响业务； 而放弃写入则副本数据不同步，产生了差异， 会不会对应用会造成影响？ 这似乎是个两难问题， 看似无法抉择。 幸好一致性问题并不是非黑即白的二选一问题， 业界早就定义了多套适合于各种应用场景的一致性模型\[1,2\]：

假设有一个存储系统， 它底层是一个复杂的高可用、高可靠的分布式存储系统。一致性模型定义如下：

1. 强一致。 按照某一顺序串行执行存储对象读写操作， 更新存储对象之后， 后续访问总是读到最新值。 假如进程A先更新了存储对象，存储系统保证后续A,B,C的读取操作都将返回最新值。  
2. 弱一致性。 更新存储对象之后， 后续访问可能读不到最新值。假如进程A先更新了存储对象，存储系统不能保证后续A,B,C的读取操作能读取到最新值。 从更新成功这一刻开始算起， 到所有访问者都能读到修改后对象为止， 这段时间称为”不一致性窗口”， 窗口内访问存储时无法保证一致性。  
3. 最终一致性。 最终一致性是弱一致性的特例， 存储系统保证所有访问将最终读到对象最新值。 譬如， 进程A写一个存储对象， 如果对象上后续没有更新操作， 那么最终A,B,C的读取操作都会读取到A写入的值。 “不一致性窗口”的大小依赖于交互延迟，系统的负载，以及副本个数等。

最终一致性是最常见的一种弱一致性， 从单个客户端（用户）角度出发， 最终一致性可再细分为以下几种：  
1 Causal consistency. A更新了对象之后通知B，那么B能读取A写入的值， 而与A没有因果关系的C则可以读不到最新值。 以微博为例， 用户甲发布微博之后， 系统通知了它的粉丝， 那么粉丝必须能看到甲发表的微博。  
2 Read your wirte consistency. 客户端总是能读取到自己的写入最新值。 以博客为例， 用户必须能看到自己刚发表的博客。  
3 Session consistency. 客户端与服务器维护一个会话， 会话有效期间， 满足read your write consistency。  
4 monotonic read consistency. 如果客户端已经读取了对象， 那么后续读取操作不能读到该对象的旧值。 以邮件收件箱为例， 用户跑到上海的时候必须也能读到他在杭州已经读过的邮件。  
5 monotonic write consistency. 单客户端发出的写操作串行执行。

设计系统时， 该如何选择一致性模型? 一般来说， 首选强一致性， 原因是理解起来简单， 使用起来也简单。 但CAP理论\[3\]告诉我们一致性、可用性和网络分区三者不可兼得， 因此弱一致性也有其适用场景： （1）网络不稳定的情况，譬如跨数据中心服务， 广域网服务（譬如DNS，CDN等）； （2） 可用性要求非常高，并发更新非常少， 且冲突容易解决的场景， 譬如amazon购物车； （3） 一致性要求本来就不高的场景， 譬如缓存。 如果确实有必要选择弱一致性，那么尽量选择最终一致性， 并从用户角度角度出发选择一种合理的最终一致性。

### 强一致实现方法 ###

强一致性模型有几种常见实现方法， 主从同步复制， 以及quorum复制等。

Quorum复制\[10\]

假设N是副本数， 写Quorum W是需要写操作成功之前必须更新的副本数目 ， 写Quorum R是读操作返回之前必须读取的副本数目。 当W + R > N时， 读写操作必然有交集， 读操作必能读到最新数据， 所以Quorum复制能做到强一致。

然而， 何为“最新”数据， 往往挺难界定， 因此实际应用中， 一般给数据带一个版本号（或者时间）， 用于标识数据的新旧。 仅凭数据版本号仍不足以保证正确性， quorum复制还得处理失败写操作带来的版本覆盖问题。 按照定义， 更新副本数目小于W的写操作算失败， 由于失败操作的版本可能大于最后一次有效写入操作的版本， 失败的残留可能会遮盖最新有效版本， 导致读Quorum达不到R， 也就是最新有效版本丢失! 为了解决版本覆盖问题， 支持quorum的存储系统一般需要保存历史版本， 读数据时一次性读多个版本， 剔除那些失败的写入数据，得到正确的数据。

Quorum复制的好处灵活选择W、R， 可用性比较好， 响应时间比较低（不必等待慢节点返回结果）， 缺点是维护数据历史版本代价较高，  
吞吐率也不高， 常见的应用场景是元数据存储。

主从同步复制

主副本或者全局协调者负责所有读写操作， 同时负责串行化写操作， 将写操作实时同步传播到其他副本， 副本全部写成功之后， 写操作才返回给用户。 采用主从同步复制的典型例子是 Ceph\[4\]， InnoSQL\[11\] FSR。 其优点是实现简单， 写吞吐率较高， 也能容忍更多节点故障。 缺点有三个，一是可用性较差， 检测到主故障并重新选主需要一定时间， 一般是10s以上； 二是响应时间较Quorum方法长， 必须等待所有副本都响应了， 请求才算成功； 三是一般只能从主节点读取数据，读吞吐率较差。

主从强一致复制的典型方法如下：

*  主从链式复制\[5\]。 副本按照一定顺序关系组织成复制链， 写操作必须发送到主副本， 串行化之后依次传播到其他副本， 读操发往最后一个副本。 原始的链式复制虽然能保证强一致，但是读取的吞吐率较差， CRAQ\[6\]针对这点进行优化， 通过维护一个脏标记CRAQ允许读取任意副本， 从而提高了读吞吐率。
 *  PacificA复制\[8\]。 PacificA是微软提出的一种保证强一致的主从复制方法， 适用于基于日志的存储系统， 分布式日志系统kafka就是采用这种做法。 PacificA复制分为三个阶段。 第一阶段prepare， 主节点确定更新顺序， 发送数据到所有从节点， 从节点写入日志并返回响应给主节点。 主节点收到所有从节点的响应之后进入第二阶段“主commit”， 主节点在本地commit该数据， 紧接着返回客户端， 此后客户端能读到该数据。 第三阶段从commit， 主节点本地commit后，异步（或者通过后续prepare消息捎带）commit所有从节点。 该协议保证更新串行性， 确保数据一但commit就能被读到。

复制状态机

状态机复制\[9\]。 利用分布式一致性(consensus)协议，譬如Paxos/Raft\[12\]， 构建一个分布式复制的强一致日志， 日志中记录副本上的读写操作， 每个副本从相同的初始状态出发， 执行相同的日志序列， 就得到一致的结果。 当然每个副本各执行日志， 所以日志进度不完全同步。 一般是选择一个副本作为master， 客户端的读写操作都发往master， master执行完写操作，并写入日志之后就返回给客户端。

### 弱一致实现方法 ###

弱一致性实现方法可分为两类

*  单副本更新， 异步扩散到其他副本。 好处是没有更新冲突， 缺点是可用性和性能不足。
 *  多副本支持更新， 好处是可用性和性能较好， 但要解决更新冲突问题。 更新冲突一般通过last write wins是解决， 由于分布式系统不存在绝对时间， last write win的难点是无法界定”最新的写操作“。 弱一致性系统无法为数据维护单调递增的数据版本号， 因此工程实现上一般使用vector clock\[7\]检测数据冲突。 如果vector clock还无法解决冲突问题，那么必须引入应用语义， 以购物车为例， 发生冲突时， 只要将两个版本的购物车的内容合并起来， 虽然会出现一些已经删除的商品， 但对用户体验影响不太大。

### 文献 ###

\[1\] Eventual Consistent – Revisited， Werner Vogels. \[http://www.allthingsdistributed.com/2008/12/eventually\_consistent.html\]  
\[2\] 分布式系统工程， 杨传辉。  
\[3\] cap twelve years later: how the rules have changed: \[http://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed\]  
\[4\] Sage A. Weil. Ceph: Reliable, Scalable, and High-Performance Distributed Storage. Ph.D. thesis, University of California, Santa Cruz, December, 2007.  
\[5\] 分布式复制技术：链式复制。 \[http://www.bitstech.net/2013/10/11/chain-replication/\]  
\[6\] Jeff Terrace and Michael J. Freedman. Object Storage on CRAQ, High-throughput chain replication for read-mostly workloads.  
\[7\] Lamport, L.. “Time, clocks, and the ordering of events in a distributed system”  
\[8\] Wei Lin, Mao Yang, et. PacificA: Replication in Log-Based Distributed Storage Systems.  
\[9\] Tushar Chandra, Robert Griesemer，Joshua Redstone. Paxos Made Live — An Engineering Perspective.  
\[10\] 莫华枫. 云存储的黑暗面：元数据保障（下）. 程序员， 2015年4月刊. \[http://www.csdn.net/article/2014-06-17/2820254\]  
\[11\] InnoSQL, \[http://mysql.netease.com/\]  
\[12\] Diego Ongaro and John Ousterhout. In Search Of An Understandable Consensus Algorithm