谈谈复制冲突实践模式 - 版本值设计

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

在前面我们已经了解了基于领导者复制方式, 不论是单数据中心还是多数据中心都存在写冲突问题, 并且识别写冲突主要两大类, 其一是数据复制时产生的冲突; 其二是请求并发冲突, 比如针对唯一性约束与共享资源的写入操作. 今天我们主要聊单主复制冲突解决方案多版本值, 即Versioned Value.

什么是Versioned Value

为什么需要多版本值呢? 如果我换一个词来表述, 那就是我们数据存储中常见的MVCC机制, 其实多版本值设计是实现MVCC技术其中一方面的重要设计. 它就是将值的每次更新都以新版本的形式存储，以便读取历史值。

其核心机制是通过保留历史版本实现 “时间旅行查询”（查看过去某个时刻的数据状态），同时避免并发写入时的直接冲突。它应用于我们的分布式系统或者是存储系统的MVCC版本控制, 对于存储系统的MVCC机制, 主要是解决事务的隔离性与并发性. 对于分布式系统中, Replica需要判断数据值是否为最新, 同时需要回溯历史数据值, 以便能够对值的响应作出正确的回应, 比如我们看到的多人文档协作场景.

基于多版本设计的单主复制

在单主复制模型中, 我们曾对单主复制的写冲突进行分析与讨论, 现在我们采用多版本设计方式来看看是如何解决复制冲突问题. 在单主复制模型中不论是私有数据, 还是共享数据甚至是唯一性约束的数据, 我们写入的路径都会在落盘之前先写入WAL日志, 然后再进行落盘. 采用多版本值设计正是基于WAL机制中可追加的特性来实现,即我们所熟悉的基于日志结构存储引擎LSM方式.

同样我们以UserA为例子, UserA向存储系统依次发起写入请求, write x = 1、write x = 2 以及 write x = 3, 那么这个时候存储系统的WAL日志方式如下:

那么复制的时候是怎么复制呢? 这个时候我们的follower节点会从WAL日志拉取过来,总不能全部都拉回来吧, 因此就有了我们的高水位机制, 即High-Water Mark, 也就是说每个Follower从WAL日志拉取的数据都是从Leader节点中拉取自己与High-Water Mark之间偏移的日志回来并应用到自己的Replica, 假如上述x = 3, ver = 7 为我们存储系统的一个High-Water Mark, 那么对于follower1以及follower2拉取的数据将分别拉取与高水位之间的偏移量日志数据并应用到自己本地, 即:

这样一来, 我们在复制过程中通过版本号以确定应用值的决策, 通过High-Water Mark以保证数据复制是增量的, 避免数据冗余复制, 这其实就是我们存储系统中一个标准的复制方式, 也称之为状态机复制, 即State Machine Replication, 它常用于我们共识算法中的实现方式.如果我们对Kafka比较熟悉的话, 相信很容易能够理解上述的复制原理.

但是这种方式有一个很大不足, 那就是复制方式和我们的存储系统的存储引擎耦合在一起, 在先前我们谈及复制方式的时候也阐述过, 因为基于WAL日志复制方式最终是以字节流的方式存储, 同样也需要对应的Follower存储节点与Leader节点是采用相同的存储引擎才能解析, 因此无法实现异构数据复制, 这个时候我们会想到MySQL的binlog机制就是基于逻辑复制而不是基于物理复制的原因就是能够实现异构复制, 与存储引擎解耦合.

Versioned Value原理与局限性

从上述复制的例子可以看到, 要实现Versioned Value, 第一个需要考虑就是对于相同的key, 要存储多个版本的数据值; 第二是每个数据变更都是进行版本追加, 但要是删除呢, 怎么办呢? 其实也是将数据写入追加, 只是这个时候的版本我们换一个词来表示, 一般我们会称之为墓碑, 标记该key被删除; 第三需要考虑什么呢? 那就是检索的问题, 你把多个版本值都存储进去了, 那么我要如何设计存储才能更好地进行检索.

核心点是追加且要支持快速检索, 我想对于这类的数据结构很容易想到就是跳表, 每一层通过链接追加, 同时为了支持快速检索, 比如点查询和范围查询, 我们需要在跳表的基础上基于key进行排序, 同时我们将版本号存储在key上, 这个时候我们的检索方式就可以通过key以及指定的版本号获取数据:

那么采用异步数据复制方式存数据的过程, 最终follower与leader数据是一致, 如下:

这个时候获取数据的过程则通过key并携带版本号获取:

那么如果是存在请求并发的情况下, 也就是我们的MVCC机制是如何进行隔离的呢? 如下所示:

• 首先Client1 读取数据的数据会携带key值以及对应的版本号, 比如上述的t1;
• 其次会判断当前Client1 携带的t1具备可见的版本, 比如现在版本号值为1, 4, 7的三个版本, 但是t1 = 5 这个时候只能看到版本号值为4 对应的数据值, 因此从上述的时序图可以看出Client1 只能获取到v1 的数据值.
• 同时在Client1读取数据的同时, 我们发现Client2向Server发起请求, 这个时候Client2在写入的时候也会创建版本号, 这个版本号对于单个Server而言是全局且递增的, 因此一定满足t2 > t1, 于是t1 是看不到t2 所做的变更, 因此无法读取到v2.

由此可见, 我们看到了Versioned Value在数据复制以及请求并发写冲突发挥不可或缺的作用, 它是我们设计MVCC抑或是Lamport Timestamp初衷之一.

但它也存在着不足, 即如果是多主复制模型或者无主复制模型, 那么基于Versioned Value还不够, 因为这个时候是多个节点具备写入产生的冲突, 它不具备全序顺序, 只能保证单个节点的顺序性, 这也将是后续引入向量以及Lamport Timestamp的原因; 其次是对于MVCC机制实现, 在事务隔离层面还存在问题, 如write skew问题, 比如在一个值班系统中, 在岗值班至少要有1位同学在岗, 但是由于多版本的快照隔离, 彼此之间是无法感知到, 于是就会出现无人在岗的情况, 即两个不同版本相互无法感知导致同时被修改为不在岗的情况. 至于数据库层面是如何避免, 要么是select ... for upate, 要么是加Next-Gap Lock等机制, 但这里不是我们讨论的重点.

总结

我们总结下什么是Versioned Values, 即带版本值, 是指附加了版本标识(如Lamport时间戳、整数版本号)的数据值, 与键关联存储后可形成“键-多版本值列表”的结构，便于追溯历史状态，是多版本并发控制（MVCC）的基础数据形态。最后感谢阅读, 如有收获欢迎点赞转发, 谢谢!!!

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