Page 379 - 《软件学报》2024年第6期

胡梓锐 等: HTAP 数据库系统数据共享模型和优化策略 2955

S n 的长度为 |S n | = n .
S n = {w 1 ,w 2 ,...,w n }(∀i < j, w i .t < w j .t) . 记版本更新序列 n, 即
定义 3 (前缀更新序列). 前缀更新序列 S k 是版本更新序列 S n 的一个前缀线性子序列, 即 S k = {w 1 ,w 2 ,...,w k }
[36]
(k ⩽ n & ∀i < j,w i .t < w j .t) .
例 2: 如图 2 所示, 在 t5 时刻的版本更新序列为 S 3 = {w 1 ,w 2 ,w 3 } , 且 |S 3 | = 3 . 其前缀更新序列包括 3 个, 分别
为 S 1 = {w 1 } ,S 2 = {w 1 ,w 2 },S 3 = {w 1 ,w 2 ,w 3 } .

TP Client A T 1 w 1 (x,2) T 3 w 3 (x,0)
TP Client B T 2 w 2 (x,1) T 4 w 4 (x,6)

AP Client A w 1 r (x,2) w 2 r (x,1) w 3 r (x,0) w 4 r (x,6)
(a) 线性一致性
AP Client B w 1 r (x,2) w 2 r (x,1) w 3 r (x,0) w 4 r (x,6)
6 (数据共享模型). 在给定时刻, 数据共享模型
AP Client A w 1 r (x,2) w 2 r (x,1) w 3 r (x,0) w 3 r (x,0)
(b) 顺序一致性
AP Client B w 1 r (x,2) w 2 r (x,1) w 3 r (x,0) w 3 r (x,0)

AP Client A w 1 r (x,2) w 2 r (x,1) w 3 r (x,0) w 3 r (x,0)
(c) 会话一致性
AP Client B w 1 r (x,2) w 2 r (x,1) w 2 r (x,1) w 2 r (x,1)

Time
t1 t2 t3 t4 t5 t6 t7 t8
图 2 不同一致性条件下读写数据 x

随着 TP 事务的推进, 数据会随着版本更新操作的执行被不断修改 (演进), 产生新数据或更新当前数据. 通过
线性执行版本更新序列, 系统可以得到确定的数据版本 (如定义 4 所示).
定义 4 (数据版本). 数据版本 V n 为版本更新序列 S n 的线性执行结果. V n 的版本标识号记为 |S n | , 即| V n | =
|S n | = n .
例 3: 如图 2 所示, 在 t4 时刻, 执行 S 2 = {w 1 ,w 2 } 得到数据版本 V 2 , 即 x = 1 . 在 t5 时刻, 执行 S 3 = {w 1 ,w 2 ,w 3 } 得
到数据版本 V 3 , 即 x = 0 .
定义 5 (版本读取操作). 版本读取操作 r 发起对数据库的查询, 记读取数据版本为 V r , 执行时间点为 r.t . 文中
定义通过会话 s 发起的版本读操作为 r . 单个会话内多次读取之间需要满足时间维度上的单调性, 在同个会话 s
s
r 得到的数据版本 r 读取的版本 s s
s
s
内, 版本读操作 i ( V r s ) 不能比 r i 之前的任意读取操作 j ( V r s ) 更旧, 即 ∀r .t > r .t, V r i −
i
j
i j

⩾ 0 .
V r j
定义 C 定义在数据项 X 上版本读操作、版本写操作之间的版
本约束, 包括:
(1) 写操作产生的版本 ( V n ) 与当前读操作读取版本 ( V r ) 之间的版本约束 C (V n ,V r ) , 即最新写版本与当前读
版本的版本差 p :
C (V n ,V r ) = |V n |−|V r | = n−|V r | ⩽ p, 0 ⩽ p ⩽ n.
(2) 在同一时刻, 会话 s 1 中读操作 r i 读版本 ( V r s1 ) 与会话 s 2 中读操作 r j 读版本 ( V r s2 ) 之间的版本约束
i j