很多人从客户端并发的角度去讨论一致性, 这其实是一个错误的方向. 并不是说客户端与一致性无关, 相反, 客户端正是要求一致性的需求者.

一致性协议不负责客户端的并发协调. 例如抢红包, 防超卖, 秒杀这类业务需求, 不是 Paxos/Raft 能解决的.

首先, 我们需要定义先后, 何为"先", 何为"后"?

      q1          r1          q2          r2
------+-----------+-----------+-----------+-----

如图, q 是指客户端发起请求的时间点, r 是指客户端收到响应的时间点, 两个请求用 1, 2 来表示. 很显然, 两个请求的先后顺序没有争论.

如果是并发呢? 先后就变得让人迷惑了.

      q1          r1 
------+-----------+-----------
         q2          r2
---------+-----------+-----------

你说, 哪个请求先哪个请求后? 一般认为, 请求 1 先于请求 2. 这个一般也不会有争论.

接着, 是最让人迷惑的地方了.

      q1          r1 
------+-----------+-----------
         q2    r2
---------+-----+-----------

你说, 请求 1 在先还是请求 2 在先? 争论不休吧? 所以, 讨论一个一致性的系统, 必须要求观察者的行为是瞬时的, 不能是并发的.

观察者(客户端)当然可以并发, 但是, 如果客户端自己都不能分清先后的话, 去预期系统(服务端)的执行结果是没有意义的.

一个强一致性的系统(服务端)当然可以处理并发请求, 而且请求的处理也不是瞬时, 这没关系. 我们讨论的是服务器在并发处理这些请求时的一致性可预期的行为, 而不是从客户端的角度看客户端并发时的系统的行为, 这里一定要注意.

事实上, 一个一致性的系统, 只关注行为完成时点的先后的关系, 并不关注行为的发起是什么先后顺序. 所以, 请求到达服务器的时间先后关系没有任何意义.

一致性, 讨论的是完成时, 不关心发起时.

一种区分读写操作的对工程实践友好的分布式一致性协议

摘要

流行的共识算法如 Paxos[1] 和 Raft[2] 被广泛地应用于分布式系统中, 用于实现一致性. 但是, 这些算法本质上并不区别读和写操作, 因而给工程实践带来了极大的困扰. 这种困扰导致在具体实现时, 开发者往往基于性能优化方面的考虑, 对这些算法做没有经过理论验证的更改.

我想在区分读写操作的前提下, 设计一种对工程实践友好的分布式一致性协议, 能适应读多写少或者读少写多等不同场景的需求. 这个分布式协议基于 Quorum 机制, 采用 2PC 策略和复制状态机模型, 适用于有强一致性要求的分布式数据库系统和其它分布式系统.

Continue reading »

第一步, 查询集群的状态;

第二步, 根据状态判断如果没有不一致就返回, 有的话要么主动修复, 要么等待别人修复;

这是一致性的基础, 也是一致性的全部. 注意, 某些类型的不一致可以不修复. 怎么写? 当然是尝试全写, 过半数正面确认就"成功"返回给客户端, 过半数在"准备阶段"拒绝就是"失败", 否则就是"未知".

Paxos 是怎么做的? 甭管有没有不一致, 先修复再说.

[完]

初学 Paxos, 你会觉得 Paxos 非常高深隐晦, 接着会觉得没什么难的, 最后估计会觉得 Paxos 什么都不是, 就跟空气一样既是基础, 又不算什么.

你说写多数派或者全写, 这是谁都知道的道理, 不是 Paxos 独创.

你说读多数派, 显然这是错误的, 必须全读. 读多数派得出的结论, 和读全部节点得出的结论, 很可能是不同的, 甚至两次读不同的多数派也可能得出不同的结论, 所以不是一致性的.

所以, 要么全读, 要么"读修复 read-repair", 也就是在读的时候修复数据, 这就是 Paxos 所谓的 phase 2 - 产生新的共识. 读修复就是 Paxos 的基础.

这些读和写策略, 都不是 Paxos 独创, 可以算 Paxos 头上, 也可以不算. 你可以说我在用 Paxos, 也可以说我用的不是 Paxos. Paxos 非常强大, 又什么都不是.

你优化来优化去, 读的时候不修复(非一致性 quorum read), 或者先等一等别人修复(read index), 都丢失了 Paxos 的基础, 那还算 Paxos 吗?

首先, 获取"集群"的 ReadIndex. 注意, 不是某个节点上面的某个状态, 而集群的多个节点共同确定的一个变量. 这个变量如何获取, 下面说明.

func GetClusterReadIndex(){
    foreach(peers as peer){
        i = peer.rpc_GetLastIndex();
        ret = max(ret, i);
        if(recv_majority){
            break;
        }
    }
    return ret;
}

获取至少半数以上成员的 LastIndex, 也就是每个节点持久化的最新一条日志的 index. 一条日志只要在一个节点上被持久化, 那么这条日志要么被集群 commit, 要么被覆盖之后再 commit, 没有其它的选项.

由此可见, ReadIndex 不一定已经被 commit, 但一定会被 commit, 最终也将会 apply. 所以, 拿到集群的 ReadIndex 之后, 我们只需要等, 等它被任意一个节点 apply 即可.

ReadIndex = cluster.GetReadIndex();
while(1){
    foreach(peers as peer){
        if(ReadIndex <= peer.LastApplied()){
            return peer.GetValue();
        }
    }
}

不断地重复轮询全部节点, 如果谁 apply 了, 就以谁的值为准. 还有一种方案, 那就是等本地的状态机 apply, 这样避免网络传输.

ReadIndex = cluster.GetReadIndex();
while(1){
    if(ReadIndex <= self.LastApplied()){
        return self.GetValue();
    }
}

还有一种优化方案, 是客户端判断. 客户端请求多数节点, 获取 max pending 和 max committed, 如果 committed 大于等于 pending, 那么取对应的 value. 如果 pending 大于 committed, 说明集群中有"脏写"(未决的数据), 客户端要做的就是等待. 如果不等待, 那就做 Paxos phase 2 所讲的"读修复".

没什么玄幻的, 道理非常简单: 第一步, 查询集群的状态; 第二步, 根据状态判断没有脏数据就返回, 有的话要么主动修复, 要么等待; 这是一致性的基础, 也是一致性的全部.

在优化之前, 我们先分析原始的能保证正确性的做法是什么, 然后分析问题在哪, 最后再讨论怎么优化.

* Paxos 读流程: 针对要读取的对象, 在其操作序列中追加一条 read 共识.
* Raft 读流程: 在 Raft 日志序列中写一条 read 日志, 等 commit.

两者其实是一样的, 都是复制状态机模型, 都要复制一条 read 日志, 然后 apply 之后才能返回结果. 问题在哪呢? 很显然, 大部分系统是读多写少, 每一次读都需要达成共识, 而达成共识的过程无论是 Paxos 还是 Raft, 成本都太高了 - 网络写 IO, 磁盘写 IO. 既然是读操作, 能否只用磁盘读 IO 就行了呢? 这个想法就是优化的方向.

一致性算法的基础是, 无论客户端是什么操作, 集群都要在全部或者部分成员参与的情况下, 达成新的共识. 优化的思路是在某些情况下, 不用每一次操作都达成新共识. 怎么做到? 1, 如果全部成员都是一致的, 客户端读操作就没必要生成新的共识. 2, 读操作不主动生成新的共识, 而是等待其它客户端写操作生成新的共识.

Linearizable Paxos Quorum Read

流程分为: Quorum-read phase, Rinse phase.

1. 读取半数以上节点的 accepted_index, 记录其中 max_accepted_index
2. 等待, 直到任意一个节点 max_accepted_index 被 apply/execute, 以那个节点上的数据返回给客户端

重要的地方就是"等待", 如果没有等待, 就会变成简单的 Quorum Read, 是错误的. 这个读优化算法的正确名字应该是: 带有停止等待的多数派读. 区别于传统意义的"读多数派中的最新者". 其实叫"Read Index"更准确.

这里面其实有个问题, 因为 Paxos 是消极的, 如果没有外界触发, 这个等待可能永远也不会返回.

Raft Read Index

Leader 的数据就是可以返回的, 唯一的问题是, 某个节点可以错误地自认为是 leader, 所以要先确认自己是不是 leader.

1. 自认是 leader 的节点询问半数以上节点自己是不是 leader
2. 如果确认自己是 leader, 等状态机 apply 到大于等于 commitIndex(这个时刻就是 readIndex) 后, 读取状态机的结果返回
3. 如果发现自己不是 leader 怎么办? 找到正确的 leader, 获取 readIndex, 然后等待自己的状态机 apply 到至少 readIndex.

因为 Raft 是积极的, 所以AppliedIndex 一定会最终等于 commitIndex, 即使没有外界触发也不会永远等待.

无论是原始在往日志序列中追加日志, 或是 Linearizable Paxos Quorum Read 或 Raft Read Index, 本质就是插入一个同步点(memory barrier), 确保这个同步点和之前的日志已经 apply.