如何看待顺序与因果一致性问题

点击上方小坤探游架构笔记可以订阅哦

在前面我们讲述了不同复制模型在实现线性一致性面临的问题以及为此实现付出的代价, 今天我们来聊另一个话题, 相比线性一致性语义稍弱的强一致性模型, 即实现因果一致性问题存在哪些问题以及挑战.

如何理解顺序性保障

在先前的一致性模型中, 我们讲述了顺序一致性以及因果一致性, 对于顺序一致性, 如果两个操作都是属于并发关系, 那么在这样的场景下我们其实是不需要关心其操作的顺序性, 但如果是存在操作依赖, 那么这个时候我们就需要关注这种依赖关系, 对于后者我们称之为因果一致性.

那么这里为什么还要提及顺序性保障呢? 因为这个会和我们谈及的顺序一致性存在混淆, 其一是我们的关注点不一样, 在Replication Consistecy中, 我们需要保证复制的顺序性. 比如在基于Leader-Based Replication 模型中, 我们是先向单个Leader节点发起一系列写入操作, 然后再由Leader节点将应用的写入操作需要以相同的顺序应用到其他Follower节点上, 即:

这个时候我们看到这里要保证顺序性为了保持数据的完整性, 即整个数据在复制过程中的安全性得到保障.

同样地, 其二其实也是属于一个安全性保证, 比如我们在单机中开启多个事务, 每个事务都会有一个递增的TxId, 而这个TxId就是保证每个事务应用的顺序性, 主要目的不是为了做顺序, 而是防止并发数据冲突.

其三, 在分布式环境中我们曾在不可靠时钟的问题举了一个例子, 就是引入同步时钟对操作事件进行排序, 目的是为了解决并发冲突引入LWW机制,即:

从上述的例子我们可以看到, 顺序、线性一致性以及共识之间存在着紧密的联系, 可以说我们可以通过共识算法来实现数据的线性一致性, 而线性一致性本身就具备顺序性的保障.因此我们可以推导出这三者的关系:

顺序与因果的关系

那么因果一致性如何体现呢? 在这里我们引用《Designing Data Intensive Applications》一个聊天的例子, 由于没有施加事件的因果一致性, 导致Mrs.Cake以及Mr. Poons在对话上显示混乱:

如上Observer先看到问题的答案, 再看到问题, 明显违背了先有问题再有答案的逻辑.

因此, 对于因果关系, 其实是为事件施加一种顺序：原因先于结果；一条消息在被接收之前先被发送出去；问题先于答案出现。而且，就像在现实生活中一样，一件事会引发另一件事：一个节点读取了某些数据，然后相应地写入一些内容，另一个节点读取了写入的内容，接着又写入了其他内容，以此类推。这些由存在因果依赖关系的操作所构成的链条，定义了系统中的因果顺序，也就是什么事情发生在什么事情之前，即我们所熟悉的Happen Before机制。

那么如何捕获因果关系呢? 其实从上述的结论我们也可以看出因果关系是为事件施加顺序, 而这种顺序是通过偏序的关系来维持两个操作之间的因果关系, 在一致性模型中, 关于全序以及偏序, 我们通过用数学形式化的角度去看待, 比如一个自然数本身就具备顺序性, 是属于一种全序关系; 而偏序是我们则是通过数学的不同集合去看待, 集合本身并不具备可比较性, 但是我们换个角度，比如集合元素个数维度去比较，那么这个时候集合就具备可比较性, 这个就是偏序.

如何实现因果一致性

实现因果一致性的本质就是我们要捕获到事件操作之间的偏序关系, 为了确定因果依赖关系，我们需要某种方式来描述系统中一个节点的“所知信息”。如果一个节点在发出写入操作Y时已经看到了值X，那么X和Y可能存在因果关系。

首先, 我们先单主复制模型开始, 第一种方式我们借鉴基于上述顺序性保障的单点写入思路, 即采用全序的序列号(比如具备递增的逻辑时钟)排序的方式来维护我们事件操作的偏序关系. 正如基于单主复制思路一样, 从节点依次按照写入主节点的操作顺序依次应用, 那么即使存在复制延迟的问题, 最终数据也是能够保证其操作的因果一致性.而对于单点写入操作顺序, 我们可以在单点上设置对应递增的序列号来保证操作的顺序性.

上述是Leader-Based Replication模型, 但是存在一个问题就是leader节点不可用了, 通过重新选举之后, Follower1成为新的Leader节点, 那么这个时候我怎么保证序列号从Follower1节点上获取具备递增的连续性呢? 我想我们很容易想到就是保证序列号的可靠性以及并发安全性, 并单独存储独立的共享存储上避免因其中一个节点故障，包括硬件故障导致我们的序列号丢失.

除此之外, 如果是多主或者是无主复制模型，那么我们使用时间戳要实现一个全序会变得很困难，因为我们知道存在时钟漂移，这个时候要么是采用TrueTime API或者是全局的逻辑时钟.

在分布式领域还有一种能够保证全序的机制，那就是Lamport timestamp, 兰伯特时间戳. 什么是Lamport Timestamp呢? 每个节点都有一个唯一的标识符，并且每个节点都记录着自己已处理的操作数量的计数器. 那么兰伯特时间戳就只是一个由《计数器值，节点标识符》组成的数对. 有时两个节点可能会有相同的计数器值, 但通过在时间戳中包含节点标识符，每个时间戳就变得独一无二.

兰伯特时间戳与物理的日常时间时钟没有任何关系，但它提供了全序关系：如果你有两个时间戳，计数器值较大的那个时间戳就是更大的时间戳；如果计数器值相同，节点标识符较大的那个时间戳就是更大的时间戳。比如上述上述的Node1设置为《Counter, 1》而Node2节点设置为《Counter, 2》, 其中 1 以及 2 就是一个我们向节点施加的节点标识符.

在上述图中，我们看到有两个客户端分别向node1、node2分别发起写操作，每个节点都记录着当前节点最大的计数器以及对应的节点标识，我们看到clientA在第二次发起写 write max = 1 操作后时候发现node2这个时候的最大值为5,因而这个时候返回给clientA是5而不是1; 同样地我们看到clientB重新发起 write max = 4，这个时候发现node1的节点最大计数器为6，因而这个时候应用max = 6，这个时候node2上存储的数据变更为6.

通过上述我们看到每次往其中一个节点进行写操作的时候，我们会发现当前节点会和集群其他的节点进行对比并根据计数器最大值以及节点标识最大值来应用取值.

但是这里会存在一个问题，那就是如果其中一个node发生不可用，那么我们数据可能不一致的情况，比如数据倒流. 在上述clientA在还没发起第二次写操作的时候，node2此时发生不可用，并且此时还没有恢复然后clientA又发起一个写操作write max = 1，这个时候如果采用多主复制模型，大概率我们会忽略对node2拉取直接应用数据并返回数据max = 2，但是计数器 = 2其实已经在客户端被使用过了，这个时候我们就会看到数据倒流的现象.这个时候我们就需要有一个知道其他node节点数据的情况，那么这个机制就需要我们一个称之为全序广播来保证.

如果数据要求唯一性约束，那么我们的Lamport Timestamp也会存在问题，即如果两个用户同时向多主复制节点或者无主复制节点发起写入操作, 在业务层面我们要求用户名称不能相同, 那么这个时候就会有问题，我们看下面的操作:

UserA以及UserB同时向对于的leader节点发起写操作, 且我们这里t1 < t2, 这个时也许你会说UserA的t1 < t2, 应该是UserA写入成功而UserB写入失败, 但实际上不是.为什么呢? 我们忽略了一个核心要素, 这里是属于偏序关系. 怎么理解呢? 也就是说这里我们不能仅靠比较t1 以及 t2 来决定谁胜出, 这里决定谁胜出的有一个前提条件那就是IDC1 以及 IDC2 都检测到存在 UserName = X 的情况才进行t1 以及 t2的比较, 但这个时候IDC1 以及 IDC2 操作write userName = X 的时候, 双方的数据都需要立即对该请求作出决策并响应, 这个时候每个IDC的数据中心并没有感知到其他IDC是否也有在做相同的事情.

全序广播与共识算法

在因果一致性实现中, 如果前后依赖需要保证唯一性约束，仅仅对操作进行全序排列是不够的——你还需要知道该顺序何时最终确定下来。如果你有一个创建用户名的操作，并且你确定在全序关系中没有其他节点能够在你的操作之前插入对相同用户名的占用声明，那么你就可以放心地宣布该操作成功。这种知晓全序关系何时最终确定的概念，在全序广播这一主题中得以体现。

如前所述，单主节点复制通过选择一个节点作为主节点，并在主节点的单个CPU核心上对所有操作进行排序，从而确定操作的全序关系。接下来的挑战在于，如果吞吐量超过了单个主节点的处理能力，如何对系统进行扩展，以及当主节点出现故障时如何处理故障转移. 在分布式系统的文献中，这个问题被称为全序广播或原子广播.

那么什么是全序广播呢? 全序广播通常被描述为一种在节点之间交换消息的协议。通俗地说，它要求始终满足两个安全属性：

• 可靠传递：没有消息会丢失：如果一条消息被传递到一个节点，那么它会被传递到所有节点。
• 全序传递：消息以相同的顺序被传递到每个节点.

那么这个时候我们回到上述的问题, 当UserA以及UserB分别执行UserName = X的时候, 每个IDC的leader都需要向其他IDC的leader发送消息广播以达成共识, 什么样的共识呢, 这里都持有UserName以及序列号T的时间戳, 以最小的时间戳达成共识, 最后以UserA写入成功, UserB写入失败作为结果, 但是通过这个案例我们看到共识过程中UserA以及UserB必须要等待共识的完成, 也就是说这个过程是阻塞的, 那么在一定程度势必会影响性能.

全序广播的一个重要方面是，顺序在消息传递时就固定下来了：如果后续消息已经被传递，那么不允许一个节点追溯性地将一条消息插入到顺序中更早的位置。这一事实使得全序广播比时间戳排序更强大。

与其说全序广播, 我们先换一个词来说明, 那就是进行多轮共识的过程, 即: 全序广播要求消息以相同的顺序、且仅传递一次给所有节点。仔细想想，这相当于执行多轮共识：在每一轮中，节点提议它们接下来想要发送的消息，然后决定在全序中接下来要传递的消息。因此，全序广播等同于重复多轮的共识（每一次共识决定对应一次消息传递）：

• 由于共识的一致性属性，所有节点决定以相同的顺序传递相同的消息.
• 由于完整性属性，消息不会被重复
• 由于有效性属性，消息不会被损坏，也不会凭空捏造
• 由于终止性属性，消息不会丢失

这个时候我们看到全序广播本质就是进行多轮共识的过程, 那么对于ZK以及etcd实现的共识算法, 我们也可以称之为全序广播算法. 因此我们看待全序广播可以为:

• 状态机复制: 如果每条消息都代表对数据库的一次写入，并且每个副本都以相同的顺序处理相同的写入操作，那么副本之间将保持一致.
• 是一种创建日志的方式（就像在复制日志、事务日志或预写式日志中那样）：传递一条消息就如同向日志中追加内容。由于所有节点都必须以相同的顺序传递相同的消息，所以所有节点都可以读取日志并看到相同的消息序列。
• 实现锁服务, 在前文我们讲述过Fecing Token机制, 比如Zk的zxid.

最后关于全序广播, 我们可以通过全序广播来实现线性一致性存储, 间接地实现了因果一致性, 然后如果我们是一个具备线性一致性存储, 比如zk或者ectd这样的存储, 我们也可以利用它来实现全序广播, 比如我们会通过节点注册监听方式感知到操作的变更的实时性.

总结

最后关于一致性问题, 我们就聊到这里, 感谢阅读, 如有收获欢迎点赞转发!!!

你好,我是疾风先生, 主要从事互联网搜广推行业, 技术栈为java/go/python, 记录并分享个人对技术的理解与思考, 欢迎关注我的公众号, 致力于做一个有深度,有广度,有故事的工程师,欢迎成长的路上有你陪伴,关注后回复greek可添加私人微信,欢迎技术互动和交流,谢谢!