Page 236 - 《软件学报》2021年第10期

3208 Journal of Software 软件学报 Vol.32, No.10, October 2021

叶子节点由形如下面的多元组构成:k i ,Version 1 ,Version 2 ,….其中,Version 指向相同 key 的不同版本的 value.
除此之外,Version 还维护另外两个字段实现 MVCC 的功能.在数据合并期间,这些过期版本的数据将会被清
理.LogStore 中,对于每一个叶子节点的 version 域都包含 3 个字段,分别是指向相应的数据记录的 offset 以及用
于判断版本的可见性的 Xmin 和 Xmax:
1. Xmin:在创建(PUT 操作)键值对(key-value 对)时,记录该值为插入键值对的事务 ID;
2. Xmax:默认值为 0.在删除或者更新键值时记录此值.
LogStore 不会直接在旧 value 上修改,如何实现对这些并发操作进行隔离的呢?Xmax 字段具有两层含义.
 其一是充当锁的作用,如果将该值设置为特殊的值,系统可以控制并发的更改操作.由于 LogStore 的单
线程执行模型,这个特性没有发挥作用;
 其二是限定可见的时间区间,读操作只会读取特定版本的数据,实现读写隔离.
简而言之,LogStore 判断 value 是否对一个 transaction id 为 t_id 的事务可见,遵循如下规则.
1. 对于 version@Xmin>t_id 的数据记录不可见;
2. 对于 version@Xmin<t_id & (version@Xmax=0 //t_id<version@Xmax)的键值并且已经提交的事务可
见(已删除键值对除外).
系统的读写流程如下.
 PUT 请求
当一个创建请求到达时,系统将该请求放入相应分片的队列,同时放入对应的复制通道.执行线程不断地从
队列中取出任务,然后执行操作.首先,系统获取插入时间戳 ts,将数据转换成相应的格式,令 version@Xmin:=ts.
日志记录一旦写入文件,系统立刻返回该日志记录在活跃日志文件的偏移,以更新对应分片的内存索引(赋值
version 域的 offset 字段).后面的查询可以利用索引快速检索到该记录.如果系统中已经存在相应的 key,则为该
key 对应的 value 创建一个新版本.为减少系统与外设交互的频率,LogStore 也会将该日志记录加入到缓冲区.因
此,读操作大部分可以从缓冲区获得相应数据而很少从磁盘检索数据.类似于 Aurora,LogStore 无需将缓冲区的
数据写回存储层,而仅仅是利用缓冲区提高读性能.
 GET 操作
LogStore 支持 GET(key)语义,其中,key 由用户指定.为了快速应答读请求,系统首先在缓冲区中查找是否存
在对应的 key:如果存在,则读取对应的数据版本的 value,然后返回.具体而言,可见性规则如下:
Xmin≤t_id<Xmax 或者 t_id≥Xmin & Xmax=0.
如果数据不在缓冲区内,否则需要访问 ART 树进行一次 I/O 操作读取相应的数据.缓冲区在慢 I/O 设备上
对读操作的性能有着较大的影响,因此,一个轻量级、高效的缓冲区就显得比较重要.由于日志索引的存在,
LogStore 可以在 SSD 上较好地应对长尾查询.LogStore 的缓冲区采用类似二次置换算法,但是系统无需维护数
据的访问信息,从而将开销降至最低.大部分读请求能够在缓冲区中获得相应的数据.即使遇到不命中的情况,
系统也能够以至多一次 I/O 的代价从外存读取相应的数据以响应点查询请求.
 DELETE
与插入操作相同,删除操作也需要进入对应分片的队列.为了删除一条记录,缓冲区与日志文件的数据都需
要被删除.首先,系统会从缓冲区中移除该数据;然后写入一条记录,表示该 key 对应的数据已经被删除.同时,在
该 key 在 ART 树中的索引条目对应地创建一个新版本的数据写入删除标记,置 Xmax 为1.在数据合并时期,该
记录所占用的物理空间才会被释放.
2.3 复制模块

2.3.1 副本数据可见性
传统的 data+WAL 的双拷贝架构会引发额外的复制开销.下面是具体的例子,演示在传统的复制协议下双
拷贝系统会面临的问题.以 raft 算法为例,复制流程分为两个阶段,如图 3 所示.
 阶段 1:主机负责接收客户端请求,然后调用 RPC 接口 AppendEntries,将日志记录批量发送到备机.当主