目  录
5 Implementation
5.1 全态数据读取
5.1.1 历史表的创建
5.1.2 快照读的三种类型
5.1.3 查询语句
5.1.4 事务快照
5.1.5 全态数据的可见性判断算法
5.2 事务状态管理
5.2.1 事务状态结构
5.2.2 优化历史态数据读取
5.2.3 事务状态查询
5.3 索引设计
5.3.1 历史表索引创建
5.3.2 历史表索引结构
5.4 有效时间管理
5.4.1 有效时间创建
5.4.2 有效时间查询
5.4.3 有效时间更新
5.4.4 有效时间删除
Acknowledgments
References
系列文章

5  Implementation

分布式TDSQL环境下实现的双时态数据库系统不是一件很轻而易举的事情。在本章中，我们将对本文所提出的双时态数据库系统的整体架构以及具体的技术细节进行详细的介绍。前一章提出了一种适应于关系型数据库的全时态数据模型（见“TDSQL时态数据库--核心技术” http://blog.itpub.net/31540857/viewspace-2155689/ ），基于这一数据模型，本章讨论一些关键的实现技术，重点说明历史态数据的管理技术。

5 .1 全态数据读取

全态数据读取分为以下三种情况：
    1.  读取历史态数据：从历史表获取；
    2.  读取当前态和过渡态数据：从用户表读，此为现有 MVCC 技术所实现；
    3.  读取全态数据：从用户表和历史表获取，现有主流数据库系统不支持历史态数据， MVCC 技术无法读取全态数据。

    如下，详细讨论全态数据读取的设计与实现。

5 . 1.1  历史表的创建

想要读取全态数据，首先要把历史态数据存储下来。T-TDSQL中，当前态和过渡态数据存放在用户表中，历史态数据存放在历史表中。我们扩展建表语法，为用户表创建、绑定历史表。 SYSTEM_VERSIONING 关键字将创建与用户表结构类似的历史表，将其命名为“$用户表名_history”。

1. CREATE [ TEMPORARY ] TABLE [ IF NOT EXISTS ] tbl_name ( create_definition , . . . ) [ table_options ] [ partition_options ] [ system_versioning ]

5 . 1.2 快照读的三种类型

实现当前态、过渡态、历史态数据存储后，考虑如何读取。T-TDSQL定义三种数据读取方式：历史快照差读、当前快照读、历史快照读。
    1.  历史快照差读：给出两个快照，读取这两个快照间的历史态数据。
    2. 当前快照读：基于现有 MVCC 技术，读取当前态和过渡态数据。
    3.  历史快照读：给出历史上的一个事务快照，读取此快照到当前时刻的全态数据。

用户表和历史表结构相似，在逻辑上是一张表。上述三种数据读取方式，操作这张逻辑表，实现历史态、过渡态、当前态数据的读取。

此外，拥有Super权限的用户可以越过这张逻辑上的表，通过SQL:2011事务时态语法读取历史表，实现历史态数据的直接读取。

5 . 1.3  查询语句

5.1.3.1 全态数据读取语法

1. SELECT select_expr [ , select_expr . . . ] FROM table_references [ WHERE where_condition ] . . .

    其中，table_references的格式为：

1. tbl_name [ [ AS ] alias ] [ index_hint ] [ READVIEW START readview_name [ TO readview_name2 ] [ TYPE type ] ]

    “ READVIEW START readview_name TO readview_name2 ”指定所查询的快照区间，表示“历史快照差读”。不带 READVIEW 子句，表示“当前快照读”。只带有“ READVIEW START readview_name ”表示“历史快照读”
    “ TYPE type ”限定生成该版本的操作类型，查询返回指定操作产生的版本。支持四种筛选类别： INSERT 、 UPDATE 、 DELETE 、 ALL ，其含义分别为由插入、更新、删除、 ALL 产生的数据版本，缺省值为 ALL 。

5.1.3.2 事务时态查询语法

历史态数据的读取，支持SQL:2011标准的事务时态查询，提供如下SQL语句：

1. SELECT select_expr [ , select_expr . . . ] FROM table_references [ SYSTEM_TIME sys_time_expr ] [ WHERE where_condition ] …

其中，sys_time_expr的格式为：

1. AS OF time_expr | FROM time_expr1 TO time_expr2 | BETWEEN time_expr1 AND time_expr2

    1. AS OF time_expr：查询在time_expr时刻处于当前态的数据，满足Sys_start <= time_expr < Sys_end。

    2. FROM time_expr1 TO time_expr2：查询SYSTEM_TIME在time_expr1至time_expr2时间段内的数据，满足time_expr1 <= Sys_start且 Sys_end < time_expr2。

    3. BETWEEN time_expr1 AND time_expr2：查询SYSTEM_TIME与[time_expr1，time_expr2)有交集的数据，满足time_expr1 < Sys_end 且 Sys_start <= time_expr2。

5 .1.4 事务快照

基于MVCC技术，读取数据时，需要创建事务快照。事务快照是数据库中基于MVCC并发访问控制技术在其创建时刻存储的所有活跃事务的状态信息。基于事务快照和多版本，利用版本可见性判断算法，可以识别某个版本的数据项是否对拥有这个快照的事务可见。

如图1所示，定义了事务快照的四个属性。

    1. upperBound：代表活跃事务中的最大事务ID，即大于这一个值的事务所操作的全态数据对于当前事务都是不可见的。

    2. lowerBound：代表活跃事务中的最小事务ID，即小于这一个值的事务所操作的全态数据对于当前事务都是可见的。

    3. trxCreator：代表当前事务快照所对应的事务ID。

    4. createTime：代表当前事务快照的创建时间。

图1中给出的S1即为一个事务快照的具体例子，对于事务ID小于10的事务所操作的全态数据，当前事务可以读取；对于事务ID大于50的事务所操作的数据，当前事务不能读取。当前事务ID为25，其开始的时间戳也被记录了下来。

5 .1. 5   全态数据的可见性判断算法

历史态数据可见性判断算法和当前态数据可见性判断算法合称为全态数据可见性判断算法。

历史态数据可见性判断算法详情可参考文献[1]和“TDSQL时态数据库--核心技术”。T-TDSQL实现历史快照差读和历史快照读，依赖此算法。

当前态数据可见性判断算法可参考文件[5]，其本质是传统数据库如Oracle、MySQL/InnoDB、PostgreSQL等使用的元组可见性判断算法，T-TDSQL实现当前快照读，依赖于此算法。

算法1给出了全态数据在快照差读取下的可见性判断算法，算法输入为两个事务快照s_start和s_stop，以及当前态数据集R，由于元组的版本具有三个状态，对于处于当前态的版本，首先对版本的提交时间是否在两个快照之间进行判断，如果不在，说明当前态版本不可见，则获取最新的历史态版本，递归判断余下的历史态版本是否可见；对处于历史态的元组的某个版本，直接判断版本的事务提交时间是否在两个快照之间，如果不在，则当前版本不可见，否则即可见。

算法1全态数据可见性判断算法

点击( 此处 )折叠或打开

1. function FULL_STATE_VISIBILITY_JUDGEMENT ( R , s_start , s_stop )
   

2.        S←?
   

3.         for r in R do
   

4.            opT = HISTORY_VISIBILITY_JUDGEMENT ( r , s_start , s_stop )
   

5.             if opT then
   

6.                Add ( r , S )
   

7.             end if
   

8.             while r = r . prev ( ) do
   

9.                opT = HISTORY_VISIBILITY_JUDGEMENT ( r , s_start , s_stop )
   

10.                  if opT then
    

11.                     Add ( r , S )
    

12.                  end if
    

13.              end while
    

14.          end for
    

15. end function

5 .2 事务状态管理

为支持全态数据获取，T-TDSQL提供了事务状态管理机制。事务的执行状态（运行中、已提交、被回滚）和事务状态的发生时间（事务开始、提交、回滚的时间），不被原生MySQL维护，T-TDSQL通过事务状态日志和事务状态缓冲区及缓冲区管理等相关技术，实现了对事务的状态管理。

另外，T-TDSQL提供了方便用户查询事务状态的工具。

5 .2.1 事务状态结构

事务状态的数据结构，标识了事务的生命周期。T-TDSQL使用16字节存储每个事务的开始时间、结束时间和当前状态，如图2所示，对每一个属性详细描述如下：

1. status （2字节），标识事务当前状态，其值为“未开始”、“正在进行”、“已提交”、“已回滚”。

2. begin_time（7字节），事务开始的时间戳。

3. end_time（7字节），事务结束的时间戳。对正在进行的事务，此值为空。
        

在T-TDSQL系统中，每个事务都通过事务ID（trx_id）来进行唯一标识。存储事务状态的数据页结构如图3所示，事务ID与每条事务状态的存放位置之间可以相互转换。每条记录中没有存储事务ID，通过记录所在的页面ID（page_id）和页内偏移量（offsets）即可快速计算出事务ID，如公式（1）所示。每个数据页中存储有num_per_page条事务状态记录，由页面大小page_size除以事务状态记录大小info_record_size得到，如公式（2）所示。公式（3）（4）给出了通过事务ID计算得到页面ID和页内偏移量的方法。

trx_id = page_id ? num_per_page + offsets / info_record_size   式(1)

num_per_page = page_size / info_record_size              式(2)

page_id = trx_id / num_per_page                      式(3)

offsets = (trx_id % num_per_page) * info_record_size        式(4)

5 .2.2 优化历史态数据读取

事务状态功能详细记录了事务从开始到结束的状态，可用于加速版本可见性判断。根据元组上的事务ID，可查知该事务的状态。事务已提交，则继续可见性判断；否则，生成该版本的事务未提交，元组不可见。

5 .2.3 事务状态查询

T-TDSQL支持根据事务ID或物理时间戳获取事务状态。

5.2.3.1 根据事务ID获取事务状态

TRXTOTIME(trx_id , x , y )，获取事务ID在区间[trx_id-x,trx_id+y]内的事务信息，这里的trx_id是事务ID，x和y是标识事务ID浮动范围的整数。每个事务返回一条记录，每条记录包含事务ID、事务开始时间、事务结束时间、事务当前状态。

5.2.3.2 根据物理时间戳获取事务状态

TIMETOTRX(time_value, x , y)，获取[time_value-x, time_value+y]期间结束的事务信息，这里的time_value为物理时间戳，x和y两个参数以秒为单位。每个事务返回一条记录，每条记录包含事务ID、事务开始时间、事务结束时间、事务当前状态。

5.2.3.3 查询系统当前最大事务ID

GETTRXID()，获取到当前系统已分配的最大事务ID。

5 . 3   索引设计

5 . 3 .1 历史表索引创建

T-TDSQL扩展建表语法，为历史表指定主键:

1. CREATE [ TEMPORARY ] TABLE [ IF NOT EXISTS ] tbl_name ( create_definition , . . . ) [ table_options ] [ partition_options ] [ system_versioning ]

其中system_versioning的结构为：

1. SYSTEM VERSIONING history_pk_expr

1. history_pk_expr是用户显式指定的历史表主键，可以与原表主键不同，以适应不同的应用需要。

2. 除用户指定部分外，事务ID也作为历史表主键的一部分。

3. 根据业务侧重于“事务时间”还是“其他维度”，可以针对性地聚集历史数据。

5 .3.2 历史表索引结构

历史表上的B+树索引结构示意图如图4所示。B+树是一种常用的索引数据结构，是一种效率较高的平衡查找树，具有较高的根据索引项进行范围查询和点查询的能力。树的叶子节点为物理页面，页面内数据项根据键值聚簇存放。因此，可以根据实际需要指定合适的字段作为主键。例如，对于用户账户历史表来说，如果需要频繁查询快照差范围内单个账户的变动情况，我们可以将用户ID和事务ID设置为主键，从而提高查询效率。

5 .4 有效时间管理

T-TDSQL支持SQL:2011标准的有效时间时态。本节展示如何创建、使用有效时间。

5.4.1 有效时间创建

T-TDSQL扩展建表语法如下：

1. CREATE [ TEMPORARY ] TABLE [ IF NOT EXISTS ] tbl_name ( create_definition , . . . , [ valid_time_definition ] ) [ table_options ] [ partition_options ]

其中valid_time_definition的结构为：

1. PERIOD FOR period_name ( col_name1 , col_name2 )

1. period_name是用户指定的、本表的有效时间属性名。

2. col_name1, col_name2分别是有效时间的起始列和结束列。

5 .4.2 有效时间查询

T-TDSQL扩展查询语法如下：

1. SELECT select_expr [ , select_expr . . . ] FROM table_references [ WHERE where_condition [ PERIOD valid_period_name valid_time_expr ] ] …

1. valid_period_name为该表有效时间属性名，见1.3.1 有效时间的创建。

2. 其中valid_time_expr的结构为：

1. AS OF time_expr | FROM time_expr1 TO time_expr2 | BETWEEN time_expr1 AND time_expr2

AS OF time_expr：查询time_expr时刻有效的数据。
FROM time_expr1 TO time_expr2：查询time_expr1至time_expr2时间段内，一直有效的数据。
BETWEEN time_expr1 AND time_expr2：查询time_expr1至time_expr2时间段内，一直或曾经有效的数据。

5 . 4 .3 有效时间更新

T-TDSQL扩展更新语法如下：

1. UPDATE [ LOW_PRIORITY ] [ IGNORE ] table_reference [ valid_period_expr ] SET . . .

其中valid_period_expr的结构为：

1. PERIOD valid_period_name FROM time_val1 TO time_val2

我们以示意图的方式展示有效时间维度上更新操作的结果：

5 .4.4 有效时间删除

T-TDSQL扩展删除语法如下：

1. DELETE [ LOW_PRIORITY ] [ QUICK ] [ IGNORE ] FROM tbl_name [ valid_period_expr ] [ PARTITION ( partition_name [ , partition_name ] . . . ) ] . . .

其中valid_period_expr的结构为：

1. PERIOD valid_period_name FROM time_val1 TO time_val2

我们以示意图的方式展示有效时间维度上删除操作的结果：

Acknowledgments

本项目在腾讯TEG计费平台部立项，研究内容和实现过程得到中国人民大学教育部数据工程和知识工程重点实验室和腾讯公司的参与和支持，特别向项目参与人、支持者致谢。

References

[1] Haixiang Li et al. “Efficient Time-interval Data Extraction in MVCC-based RDBMS”.  World Wide Web Journal . 2018, pp. 922–933.

[2] 姜晓轶 蒋雪中 周云轩 时态数据库研究进展 计算机工程与应用  2005

[3] Dharavath Ramesh, Chiranjeev Kumar: A scalable generic transaction model scenario for distributed NoSQL databases. Journal of Systems and Software 101: 43-58 (2015)

[4] 汤庸 时态数据库导论 2004

[5] Haixiang Li, Yi Feng, Pengcheng Fan. The Art of Database Transaction Processiong: Transaction Management and Concurrency Control. First edition. Beijing. China Machine Press. 2017-10-01

[6] David B. Lomet, Roger S. Barga, Mohamed F. Mokbel, German Shegalov, Rui Wang, Yunyue Zhu: Transaction Time Support Inside a Database Engine. ICDE 2006: 35

系列文章

TDSQL全时态数据库系统-理念与愿景： http://blog.itpub.net/31540857/viewspace-2155687/
TDSQL-时态数据库T-TDSQL--核心技术： http://blog.itpub.net/31540857/viewspace-2155689/
TDSQL-时态数据库T-TDSQL--典型案例： http://blog.itpub.net/31540857/viewspace-2155691/