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

胡梓锐 等: 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
   374   375   376   377   378   379   380   381   382   383   384