分布式数据库：面向对象可串行化实现

2023-10-28 理论教育版权反馈

【摘要】：前面讨论了面向对象数据库系统的事务管理，本节讨论并发控制的核心问题，即可串行化问题。由面向对象数据库系统的事务可知，这是学术界所说的开放嵌套事务。为此，我们提出了面向对象可串行化的思想。对象调度的面向对象可串行化给出了一个动作序列。我们把一个事务的系统调度称为是面向对象可串行化的，如果所有的对象调度都是面向对象可串行化的，那么所有的附加动作依赖关系不含冲突。如图15.10所示，将三个事务发送给对象En

前面讨论了面向对象数据库系统的事务管理，本节讨论并发控制的核心问题，即可串行化问题。

面向对象数据库涉及复杂的数据对象。将事务封锁很长时间是不可取的，因为它会大大降低并发度。本节将讨论笔者20世纪80年代末研究的内容。

良好的并发控制方法必须在更好的并发度与增加的并发控制附加成本间寻求一个平衡。现在考虑一个协同编著系统，其中多个作者可以同时写作/编辑一篇文章。每个作者都希望立即把自己的想法写下来，若作者要同时修改这个文档，则必须等待直至这个文档被释放。如果系统能保证所有的作者看到的是一个一致的视图，则他们可以并发工作。这时呈现的事务形态和传统的事务形态有了很大的变化。常规系统和面向对象系统的比较如表15.5所示。

表15.5　常规系统和面向对象系统的比较

pagenumber_ebook=356,pagenumber_book=341

我们遇到的第一个问题面向对象操作是事务吗？答案是事务，但不是常规事务。首先，这是开放的嵌套事务（open nested transactions），是一个分层事务体系。我们可以分析操作的语义，确定两个操作是否冲突。尽管冲突的概念已讨论过，但是涉及语义时冲突的意义会有所变化。值得指出的是，面向对象模型是基于语义的，因此语义信息在这里起着重要作用。其次，操作调用的嵌套性也应该深入分析。基于这种因素，笔者和一些同事提出了面向对象可串行化（object-oriented serializable）的概念。

由面向对象数据库系统的事务可知，这是学术界所说的开放嵌套事务。开放嵌套事务应用在分层事务系统里。在面向对象系统中，事务是按对象为基点分层的。

现在我们来看一个单一对象，这个对象的性质（类似于关系模型的属性）可能指向另一个对象。选用第14章中关于Vehicle的例子：

pagenumber_ebook=357,pagenumber_book=342

若v为类Vehicle中的一个对象，则在执行方法get Vehicle（）时会调用类Engine中相关对象上的方法get Engine（）。

我们把方法（如get Vehicle（））的运行看作是一个事务，这个方法会调用另一个对象上的方法（如get Engine（）），后者的运行可看作为其子事务。一个事务就会依赖于另一个事务，如果它们都会存取相同的对象，而且这两个操作是冲突的。如果两个操作是冲突的，那么它们交换执行次序的结果会不一样。注意，我们考虑操作的语义，就可以发现对象上记载着事务的依赖关系。为此，我们提出了面向对象可串行化的思想。

对象调度的面向对象可串行化给出了一个动作（actions）序列。对象O上的动作可能是另一个对象P上的事务。因此，我们不能允许在同样的背景下从O和P上看到的是不同的视图。对象P的事务依赖性信息必须流向对象O。因此，对象P的事务依赖性导致了对象O的动作依赖性。

注意，两个事务间可能是依赖的，但它们之间可能没有同时动作的公共对象。这种情况下，我们必须把信息记录在一个称为中心实例（central instance）的地方，由一个对象来选择，或者让两个对象都选择。这样，我们在动作依赖关系里加入一个附加动作依赖关系（added action dependency relation）。

我们把一个事务的系统调度称为是面向对象可串行化的，如果所有的对象调度都是面向对象可串行化的，那么所有的附加动作依赖关系不含冲突。

两个动作是冲突的，它们执行的序不同，结果也不同，其反面就是它们是可交换的（commute）。仅当一个事务的所有依赖性动作以相同的序执行，则称该调度是可串行化的，也称冲突序保留可串行化。

假设一本数字版百科全书的记录项使用B+树来构建索引，这棵B+树命名为Bp Tree。下面用Enc表示这本百科全书，记录项的链接记作Linked List，记录项的键用Bp Tree构建索引。这些数据存放在存储页面上。

常规DBMS在类似于B+树的索引结构上的操作是按专门的并发控制协议来执行的。DBMS的索引管理器了解整个索引结构的语义。因此，DBMS可以有效管理并发控制，我们只需要考虑语义知识如何传递给DBMS。

对象具有封装性，对方法的调用是通过消息传递实施的。消息如何实现，对象不必知道。这里，我们只考虑开放嵌套事务。开放嵌套事务的根称为顶级事务（top-level-transaction），其下面的树称为子事务。按常规的事务概念，只有根才是和其他事务隔离的。但是，开放嵌套事务的子事务往往也需要和其他子事务隔离。

下面的有些概念我们采用相关学者使用的含义。Weikum等在其论文中讨论了多层事务结构问题。在多层事务系统中，事务是由其下层的动作实现的。系统的并发控制成分将两个相邻层组合为一个调度，上层称为事务，下层称为动作。冲突动作的序为其上层事务所继承。为此，称这类事务序为拟序（quasi-ordered）。如果这些事务也发生冲突，则它们的序也为其上层事务所继承，否则终止这种继承过程。所以，我们可以定义事务由一个动作的偏序构成，如果动作不是原子单位，即动作由一个动作的偏序构成，则这个动作相对于这个偏序里的动作也是事务。依此类推，直至动作不可分为止。

现在我们再看参考文献［10］中的一个例子。假设有一个对象Enc描述的是百科全书，那么这个对象有两个必不可少的性质：index（索引）和item（记录项）。index用B+树来构建，item用链表来构建，索引由指针指向记录项，从而形成如图15.9所示的形态。

对象Enc有两个分支，分别为索引树（Bp Tree）和记录项链（Linked List），参见图15.9的左端。Enc的儿子Bp Tree也有一个根，在有向线上标示了root，其下面是中间节点（见图15.9中的Node6）。中间节点下是叶子（如Leaf11、Leaf12等）。由于数据存储在外存页面上，所以这个对象图的终结节点（也可称为叶子）为存储页面，记作Page。索引项存放在不同的页面上，所以Leaf会指向不同的页面。

注意，由于索引记录项间有关联，所以它们之间由有向线互联，方向是指针指向。同时，记录项也存放在页面上，所以也指向页面，如图15.9中的Item8指向Page5599。(www.chuimin.cn)

如图15.10所示，将三个事务发送给对象Enc，操作在B+树Bp Tree上。其中，T1发送消息给Enc，调用Bp Tree上的方法insert（DBS）11，记作Bp Tree.insert（DBS）11。这个调用导致了节点上的调用（图中未标出）及叶子上的调用Leaf11.insert（DBS）119。这个插入操作又调用Page4712上的一个读操作和一个写操作，T 1的其他操作类似。事务/操作下标的第一个数字用类表示事务或所属事务的标识。图中的有向弧表示对象间的联系。

pagenumber_ebook=359,pagenumber_book=344

图15.9　百科全书对象描述

假设有三个事务T 1、T 2和T 3，分别向对象里插入数据、查询数据与插入数据。T 1由一个动作（insert（DBS）11）向索引树（Bp Tree）中插入数据，由于向树中插入数据最终要施加在叶子上，所以这个动作要调用一个动作往叶子上添加记录项，这个动作记作insert（DBS）119，其操作对象是叶子Leaf11。由于索引页存放在操作系统页面上，所以要调用相应的动作读、写相应的页面。这两个读/写动作记作read1191和write1192，相应的页面记作Page4712。事务T3是一个查询事务，它的动作是查询索引树，记作search（DBS）31。由于查询到叶子Leaf11，所以调用下一个动作search（DBS）319，它作用在Leaf11。相应地，调用相应页面Page4712，所以就由search（DBS）319调用动作read3191。我们用对象.方法的形态记录动作与对象的关系，如Page4712.write1192。

假设Page4712.write1192执行于Page4712.read2191之前，图15.10中两个动作的依赖性用有向虚线弧表示，冲突标识为×。依据常规的可串行化概念，两个事务的所有冲突动作必须保持相同的序，但这个限制比较严格。从语义上看，Leaf11.insert（DBS）119和Leaf11.insert（DBMS）219并不冲突，因为它们插入的是不同的记录项。但是，两个记录项存放在同一存储页面上。假设一个节点及其对应页面能容纳500多个记录项。

调用子事务时，必须记住依赖性，以防止丢失Page4712上的更新。我们用Leaf11上的有向虚线弧来表示依赖性，其指向与Page4712上的有向虚线弧相同。Leaf11上的动作行为相当于Page4712上的动作事务。在Leaf11.insert（DBS）119结束后，为防止丢失更新，依赖性不再相关。因为调用的动作可以交换，两个插入动作都是Page4712上的写操作，所以它们的序无关紧要。但事情并非那么简单，由于所有的其他动作都是由Leaf11.insert（DBS）119和Leaf11.insert（DBMS）219调用的，所以冲突都必须保持相同的序。否则，这棵B+树就会不一致。然而，在Bp Tree和Enc层面，这种依赖性可以被忽略，insert（DBMS）21和T2不必保持所有前面的依赖性。这样可以获得更高的并发性。

我们观察T1和T3，它们原本相容，所以图15.10中我们标以相容标记+。

pagenumber_ebook=360,pagenumber_book=345

图15.10　将三个事务发送给一个对象

假设Page4712.write1192在Page4712.read3191前面执行，因此，Page4712.read3191依赖于Page4712.write1192，其依赖性如前所述。与前面情况比较，在Leaf11上的调用动作就变成了冲突。动作Leaf11.insert（DBS）119和Leaf11.search（DBMS）319访问相同的键DBS。因此，Leaf11上的两个动作的序必须继承到Bp Tree上的调用动作。在Bp Tree上存在着冲突，因此，依赖性继承自T1和T3。结果，T1和T3必须遵循某种执行序。这样就形成一种面向对象可串行化的序（有兴趣的读者可参阅参考文献［10］）。

从上可以看出，与传统的开放分层系统相比，面向对象事务系统具有自己的特点。

●调用层次不同：无法分级，它和对象的结构相关，可以把页面看作最后层面。

●每个对象上的事务可以直接调用每个对象上的动作，例如，通过对象Linked List和对象Bp Tree都可到达项（item），但是经历的路径长短是不一样的。

●事务可以直接或间接地调用动作，都可以存取相同的对象。

面向对象的可串行化总结如下：可将事务看成是在对象上运行的方法，这个方法可以分解成一个动作序列；一些动作作用在对象的原子值属性上，一些动作可能是对其他对象上方法的调用，我们把后者看成为子事务。这样，事务就成为一棵不平衡树。

●从叶子分析，如果两个动作的父亲指定了执行序，则它们遵循这个执行序。

●如果两个动作来自不同的父亲，而且这两个动作是冲突的，则这两个父亲的所有冲突动作必须保持相同的序，这个序就称为父亲的拟序。

●调用上面这两个父亲的对象，并把这两个父亲看成为动作，把它们的调用者看成为其父亲，重复第二点，直至事务的树根为止。

从并行处理考虑，OODBMS和传统RDBMS的区别主要包含以下两个方面。

●OODBMS处理的是复杂对象而非规范化的关系元组。数据成为复杂对象，由类的大量实例构成。每个实例又包含复杂的数据类型，如集合、链表、阵列、包等。这有两层含义。首先，OODBMS里的查询会涉及大量的类。跨越多个对象类查找满足或不满足某些数据条件的对象实例是十分常用的操作。为了进行有效的查询处理，需要有效的对象实例双向跨越访问（bi-directional traversals）及其检索。为了在跨越访问时减少I/O、通信和处理时间，需要新的并行查询优化策略。其次，因为复杂对象的实例可能有很多数据，所以关系数据库系统中使用的、传统的面向元组的、取自辅存的、面向元组的查询处理不再适合。为了避免过度消耗I/O时间，不再是存取整个实例，而是存取其中与查询相关的部分数据。因此，需要不同的数据结构。

●RDBMS只处理数据库中数据的查、添、删、改。检索数据的处理或操作数据的处理是由应用程序实施的，它们已不受DBMS的控制。这类系统体系结构会产生一些临时关系，以备进一步查询或操作。OODBMS中，传统的数据库操作需要管理和实施用户定义的操作及其实现（即方法），方法的激活依赖于消息传递给对象实例。因此，将方法存放到尽可能靠近应用的实例很重要。对象实例描述数据（或属性值）的装配（assembling）很像产生的临时关系，要从辅存大量存取数据，I/O的开销很大，因此，尽量不要让用户使用。

分布式数据库：面向对象可串行化实现

相关推荐