分布式系统的一致性与共识算法(四)

Etcd与Raft算法

Raft保证读请求Linearizability的方法:

• 1.Leader把每次读请求作为一条日志记录，以日志复制的形式提交，并应用到状态机后，读取状态机中的数据返回(一次RTT、一次磁盘写)
• 2.使用Leader Lease，保证整个集群只有一个Leader，Leader接收到请求后，记录下当前的commit index为read index,当apply index大于等于read index后，则可以读取状态机中的数据返回(0次RTT、0次磁盘写)
• 3.不适用Leader Lease，而是当Leader通过以下两点保证整个集群中只有其一个正常工作的Leader:
  3.1 在每个Term开始时，由于新选出的leader可能不知道上一个Term的commit index，所以需要先在当前新的Term提交一条空操作的日志；
  3.2 Leader每次接到读请求后，向多数节点发送心跳确认自己的Leader身份。之后的读流程与Leader Lease的做法相同。(一次RTT、0次磁盘写)
• 4.从Follower节点读:Follower先向Leader询问read index，Leader收到Follower的请求后依然要通过2或3中的方法确认自己Leader的身份，然后返回当前的commit index作为read index，Follower拿到read index后，等待本地的apply index大于等于read index后，即可读取状态机中的数据返回(2次或1次RTT、0次磁盘写)

Linearizability和Serializability

Serializability是数据库领域的概念，而Lineaizability是分布式系统、并发编程领域的东西，在这个分布式SQL时代，自然Linearizability和Serializability会经常一起出现。

• 1.Serializability:数据库领域的ACID中的I.数据库的四种隔离级别，由弱到强分别是Read Uncommited, Read Committed(RC)，Repeatable Read(RR)和Serializability
  Serializability的含义是:对并发事务包含的操作进行调度后的结果和某种把这些事务一个接一个的执行之后的结果一样。最简单的一种调度实现就是真的把所有的事务进行排队，一个个的执行，显然这满足Serializability，问题就是性能。可以看出Serializability是与数据库事务相关的一个概念，一个事务包含多个读、写操作，这些操作又涉及到多个数据对象。
• 1.Linearizability:针对单个操作，单个数据对象而说的，属于CAP中C这个范畴。一个数据被更新后，能够立马被后续的读操作读到
• 2.Strict Serializability:同时满足Serializability和Linearizability

举个最简单的例子:两个事务T1,T2，T1先开始，更新数据对象o,T1提交。接着T2开始，读数据对象o,提交。以下两种调度:

• 1.T1,T2,满足Serializability，也满足Linearizability
• 2.T2,T1,满足Serializability，不满足Linearizability,因为T1之前更新的数据T2读不到

因果一致性Causal Consistency

因果一致性，属于弱一致性，因为在Causal Consistency中，只对有因果关系的事件有顺序要求。
没有因果一致性时会发生如下情形:

• 1.夏侯铁柱在朋友圈发表状态:“我戒指丢了”
• 2.夏侯铁柱在同一条状态下评论"我找到了"
• 3.诸葛建国在同一条状态下评论"太棒了"
• 4.远在美国的键盘侠看到"我戒指丢了" “太棒了”，开始喷诸葛建国
• 5.远在美国的键盘侠看到"我戒指丢了" “我找到啦” “太棒了”，意识到喷错人了。
  所以很多系统采用因果一致性系统来避免这种问题，例如微信的朋友圈就采用了因果一致性

最终一致性Eventual Consistency.

最终一致性这个词大家听到的次数应该是最多的，也是弱一致性，不过因为大多数场景下用户可以接受，应用也就比较广泛。
理念:不保证在任意时刻任意节点上的同一份数据都是相同的，但是随者事件的迁移，不同节点上的同一份数据总是在向趋同的方向变化。
简单说，就是在一段时间后，节点间的数据会最终达到一致状态。不过最终一致性的要求非常低，除了向Gossip这样明确以最终一致性为卖点的协议外，包括Redis主备、MongoDB、乃至MySQL热备都可以算是最终一致性，甚至如果我记录操作日志，然后在副本故障了100天之后手动在副本上执行日志以达成一致，也算是符合最终一致性的定义。有人说最终一致性就是没有一致性，因为没人可以知道什么时候算是最终。
上面提到的因果一致性可以理解为是最终一致性的变种，如果进程A通知进程B它已经更新了一个数据项，那么进程B的后续访问将返回更新后的值，并且写操作将被保证取代前一次写入。和进程A没有因果关系的C的访问将遵循正常的最终一致性规则。

最终一致性其实分支很多，以下都是它的变种:

• 1.Causal Consistency(因果一致性)
• 2.Read-your-writes Consistency(读自己所写一致性)
• 3.Session Consistency(会话一致性)
• 4.Monotonic Read Consistency(单调读一致性)
• 5.Monotonic Write Consistency(单调写一致性)
  后面要提到的BASE理论中的E，就是Eventual Consistency最终一致

ACID理论

ACID是处理事务的原则，一般特指数据库的一致性约束，ACID一致性完全与数据库规则相关，包括约束，级联，触发器等。在事务开始之前和事务结束以后，都必须遵守这些不变量，保证数据库的完整性不被破坏，因此ACID中的C表示数据库执行事务前后状态的一致性，防止非法事务导致数据库被破坏。比如银行系统A和B两个账户的余额总和为100，那么无论A,B之间怎么转换，这个余额和是不变的，前后一致的.
这里的C代表的一致性：事务必须遵循数据库的已定义规则和约束，例如约束、级联和触发器。因此，任何写入数据的数据都必须有效，并且完成的任何事务都会该笔那数据库的状态。没有事务可以创建无效的数据状态。注意，这与CAP定理中定义的一致性是不同的。
ACID可以翻译为酸，相对应得是碱，也就是BASE.不过提BASE之前要先说下CAP，毕竟，BASE是基于CAP理论提出的折中理论

CAP理论

CAP理论中的C也就是我们常说的分布式系统中的一致性，更确切地说，指的是分布式一致性中地一种:也就是前面说地线性一致性(Linearizability)也叫做原子一致性(Atomic Consistency).
CAP理论也是个被滥用地词汇，很多时候我们会用CAP模型去评估一个分布式系统，但是CAP模型却有一定的局限性。因为按照CAP理论，很多系统MongoDB、ZooKeeper既不满足(线性一致性)，也不满足可用性(任意一个工作中的节点都要可以处理请求)，但这并不意味着它们不是优秀的系统，而是CAP定理本身的局限性(没有考虑处理延迟，容错等)

BASE理论

正因为CAP中的一致性和可用性是强一致行和高可用，后来又有人基于CAP理论提出了BASE理论，即基本可用(Basicly Available)、软状态(Soft State)、最终一致性(Eventual Consistency).BASE的核心思想是即使无法做到强一致性，但每个应用都可以根据自身的业务特点，采用适当的方法来使系统达到最终一致性。显然最终一致性弱于CAP中的线性一致性。很多分布式系统都是基于BASE中的"基本可用"和"最终一致性"来实现的，比如MySQL/PostgreSQL Replication异步复制

ACID一致性与CAP一致性的区别.

ACID一致性使有关数据库规则，如果数据表结构定义一个字段值是唯一的，那么一致性系统将解决所有操作中导致这个字段值非唯一的情况，如果带有一个外键的一行记录被删除，那么其外键相关记录也应该被删除，这就是ACID一致性的意思。
CAP理论的一致性是保证同样一个数据在所有不同服务器上的拷贝i都是相同的，这是一种逻辑保证，而不是物理，因为光速限制，在不同服务器上这种复制是需要时间的，集群通过阻止客户端查看不同节点上还未同步的数据维持逻辑视图。

当跨分布式系统提供ACID是，这两个概念会混淆在一起，Google’s Spanner System能够提供分布式系统的ACID，其包含ACID+CAP涉及，也就是两阶段提交2PC+多副本复制机制

ACID/2PC/3PC/TCC/Paxos关系

ACID是处理事务的原则，限定了原子性、一致性、隔离性、持久性。ACID、CAP、BASE这些都只是理论，只是在实现时的目标或者折中，ACID专注于分布式事务，CAP和BASE是分布式通用理论。
解决分布式事务有2PC、3PC、TCC等方式，通过增加协调者来进行协商，里面也有最终一致的思想。
而Paxos协议与分布式事务并不是同一层面的东西，Paxos用于解决多个副本之间的一致性问题。比如日志同步，保证各个节点的日志一致性，选主的唯一性。简而言之，2PC用于保证多个数据分片上事务的原子性，Paxos协议用于保证同一个数据分片在多个副本的一致性，所以两者可以是互补的关系，不是替代关系。对于2PC协调者单点问题，可以利用Paxos协议解决，当协调者出现问题时，选一个新的协调者继续提供服务，原理上Paxos和2PC相似，但目的上是不同的，etcd中也有事务的操作，比如迷你事务