事务存储结构的实现

1、事务存储构造的实现摘要多核处理技术将成为计算机的主流技术，基于多核开发线程级并行已至关重要，事务的引入可以解决目前线程所不能完成的功能，同时可以简化编程模型，事务存储能很好地实现事务特性。本文首先介绍了T的根本原理，接着分析了目前主流T系统LgT，着重于数据版本管理和冲突管理机制的实现，进而将此系统的优越性展现出来。最后对本文进展了总结和展望。关键词事务存储；日志事务存储；体系构造；操作系统随着多核处理器技术的不断更新和开展，传统的串行程序不管在效率上还是性能上都已经跟不上信息高速开展的脚步了，程序员不得不开发线程级并行以进步片上计算资源的使用效率，但也带来了新的挑战和问题。目前不同线程间的同

2、步、对共享资源的访问等都是通过锁和信号量机制完成的。然而，这种传统的基于锁和信号量的并发系统存在明显的局限性。粗粒度的锁对大量的共享数据做了保护，但是可扩展性不好，因为即使在线程间不存在对共享数据的访问的情况下也可能会出现冲突阻塞现象；细粒度的锁虽然比粗粒度的锁扩展性能好，但由于算法设计的复杂性，普通程序员很难借助细力度的锁实现高效的应用。同时使用锁机制还会带来诸多问题，比方：死锁、优先级反转等，极大地影响了并行应用的效率和性能。事务存储(Transatinalery，T)的使用是解决上述存在问题一个很好的方法1。通过将不同并行执行的线程事务化，用事务操作来代替锁机制能降低编程的复杂性。事务是

3、被单线程执行的对内存进展读写的有序操作序列，其特性包括：原子性、隔离性、一致性和持久性。通常事务的执行过程为：调用事务入口函数(begin_transatin)开场执行事务，当事务执行完毕后调用提交函数(it_transatin)开场提交工作，提交过程分为三个阶段(恳求提交、开场提交和完成提交)，执行完提交后此事务也就执行完毕，从而继续执行下面的事务。但假如事务在执行或提交过程中发生冲突或者错误，那么通过其特有的回滚机制(rllbak)返回到此事务入口继续执行。事务的执行流程图如图1所示。图1事务执行流程为了实现事务的这些特性，需有一个很好的T系统来支持事务数据的版本管理(Versinanag

4、eent)和事务的冲突管理(ntentinanageent)。版本管理同时对新值(事务提交后可见)和原始的旧值(事务执行过程中发生了回滚的恢复数据)进展管理。根据数据存放方式的不同T系统区分版本管理为：积极版本管理(EagerVersinanageent)和懒惰版本管理(LazyVersinanageent)。积极版本管理是将新值置于目的存储区中，这样在提交时新值可以很快的得到执行，极大地降低了提交的时延；而懒惰版本管理是将原始的旧值置于目的存储区，虽然会增加提交的延时但是降低了当事务发生回滚后执行的延时。冲突管理是不同事务执行过程中对共享资源访问引发冲突而进展的冲突检测以及管理的机制。冲突管

5、理有积极的(Eager)和懒惰的(Lazy)两种策略，假如冲突在读数据或写数据时立即被发现而进展仲裁，这种冲突检测是积极的；假如冲突是在事务进展提交时才发现并仲裁的，这种冲突检测那么是懒惰的。目前，基于T的硬件构造有很多种，图2中列出了目前几种流行的硬件构造根据版本管理和冲突管理而进展的分类。本文将介绍其中的一种构造LgT(日志事务存储)，通过对其硬件构造参见图3、版本管理、冲突管理的实现，展现了此构造的优越性，并给后续研究提供参考和帮助。图2T系统分类LgT是建立在多机系统中基于日志的T实现，每个核都有单独的私有ahe，并通过目录协议来维持数据的一致性。它采用的是积极的版本管理策略和积极的冲

6、突管理策略。图3给出了LgT的硬件构造，它通过增加一些存放器和ahe中的读/写位很好地完成了对事务的操作。图3LgT的硬件构造(图中黑框中为其特有构造)2.1版本管理(Versinanageent)LgT使用积极的版本管理，将新的执行数据存储在目的区域(目的地址)中，而将旧的数据存储在其它缓冲区。它通过在内存中开拓一块事务日志区域存储事务执行过程中被修改的数据(上文中提到的原始数据)和这些数据所对应的地址，新的执行数据那么被保存在目的存储区(目的地址)，当执行完成提交时，这些新数据将会立即生效；当事务执行过程中或提交时发生冲突或错误需要回滚时，那么通过事务日志中记录的信息恢复出事务执行前的初始

7、状态。刚开场创立线程时，每一个线程对应着一个日志而且为日志分配一块虚拟存储区域，并将该日志基地址写入LgBase存放器，当旧数据需要存储到日志时，LgT通过LgBase存放器中的值定位到日志的入口然后将旧数据的虚拟地址和值一同保存在日志中以便恢复时使用。为了减少冗余日志，LgT为每一个ahe块添加了对应的写()位，用此来标识该ahe块在日志中的记录情况。当事务提交成功后，LgT将对应ahe块的写()标志位清0并将LgPinter(日志指针)重新指向日志的入口处，以便处理后续事务。LgT也为每个ahe块设置了一个读(R)标志位，就像上面我们讨论的写()标志位一样。在每个事务操作过程中LgT同样将

8、读标志位设置用于表示读操作的执行(如图4所示)，而且在事务完毕后，读标志位也清0。这种积极的版本管理形式的缺点就是在事务发生冲突或错误需要回滚时执行比拟慢，在回滚时，LgT为了完成恢复必须将原始数据从日志中读到适宜的目的地址中然后重置写()位，同时因为有很多数据记录在日志中，所以恢复过程必须按照由后向前(后进先出)的顺序进展。但在事务冲突比拟少的情况下，这种形式可以带来高效的执行效率。为了能更好的理解LgT版本管理过程，图4通过一个例子进展了很好的分析。(1)事务执行开场前的状态ahe数据块中存放着原始数据，每块的读(R)、写()位置0，LgBase(日志基址存放器)指向日志入口地址，LgPt

9、r(日志偏移指针)指向日志入口地址同时Tunt(事务计数器)置1代表正准备执行一个事务。(2)读00地址(十六进制地址)中的数据到存放器r1中，00地址对应数据块的读(R)标志位置1表示此数据被读。(3)将存放器r2中数据(这里假设为56)存入0地址中，由于0地址中存在原始数据34，将0地址和该原始数据一起根据LgBase中的日志入口地址存入日志中，并将LgPtr指针后移，指向用于存放下个数据的地址位，同时将0地址对应块的写()标志位置1，代表一次写操作的完成，其他的状态不变。(4)读取40地址中数据到存放器r3中，然后r3中数据加1，并将执行后的r3数据存回40地址中，该操作对40地址对应块

10、执行了一次读操作和一次写操作，将读(R)和写()标志位置1，然后将原始40地址对应块中数据存入日志中，存入LgPtr指向的地址中，同时将LgPtr指针后移。(5)事务提交后状态将与本领务相关的各个数据块对应读写标志位清0，将LgPtr置位到LgBase，Tunt置0。(本例仅针对单事务执行，假如是嵌套事务的执行，LgT构造会更加复杂，详细支持嵌套事务的LgT实现，请参考2)(6)事务回滚后状态事务在执行或提交过程中假如出错需要回滚，那么将日志中记录的原始数据按照地址映射关系重新加载到对应ahe数据块中，同时将各个块对应读写标志位清0，LgPtr重置并且Tunt置0。图4事务版本管理过程成功提交

11、和回滚2.2冲突管理(ntentinanageent)LgT采用积极的冲突管理形式，而冲突管理中的一个重要概念目录，就是在内存中开拓的一片用来记录共享数据索引和相关状态信息的区域，也称为目录表。此冲突管理以目录为桥梁，通过目录的分析和消息转发机制来完成多处理机间的冲突检测。详细的实现步骤概括起来为：恳求操作的处理机发出一致性恳求到目录；目录响应恳求并可能将恳求转发到其他一个或多个处理机上；每个响应恳求的处理机检查自身状态看是否发生冲突；每个响应恳求的处理机给出应答信号，包括冲突应答(nak)和非冲突应答(ak)；发出恳求的处理机解决冲突。事务发生冲突后的交换行为须根据目录中有效的ESI状态(E

12、SI状态：dified()，ned()，Exlusive(E)，Shared(S)rInvalidate(I)而定。下面结合图5中的冲突检测实例对冲突管理的详细行为进展说明。图5LgT冲突检测实例(1)事务开场处理机P开场执行事务，Tunt增1；此时仅目录中存放的ahe块信息有效。(2)处理机P向目录恳求数据信息步骤：P在自身的ahe中找不到某数据，马上发送独占恳求(GETX)到目录。步骤：目录收到恳求后根据相应数据的索引找到“老版本数据传给处理机P，当“老版本数据到达P时，P将此数据更为“新版本数据同时将本机此数据块对应读/写标志位置1。步骤：P承受数据完毕后，发送应答信号给目录表示已经成功

13、承受数据。与此同时目录中的状态信息为P(difiedbyP)，表示此数据正在被处理机P更改。(3)检测到事务冲突步骤：处理机Q发出恳求某共享数据的信号(GETS)给目录。步骤：由于目录中此数据的状态为P，目录那么根据恳求转发给处理机P。步骤：P承受到恳求后检查自己的状态，由于P中相应数据块的写标志位已置，说明P正在修改此数据，不能满足Q的恳求，发生冲突。这时处理机P直接发送冲突信号给Q，当Q承受到冲突信号后进展冲突处理。步骤：处理机Q同时将冲突信号发送给目录，说明此次恳求失败。(4)事务溢出的处理处理机P通知目录要将修改后的数据存到内存中(目前，内存中存在的是对应数据修改前的“脏数据)。步骤：

14、P发出PUTX恳求给目录。步骤：目录认可后发送应答信号给P，通知P可以发送。步骤：P接收到此信号后将数据写回内存(B_XAT)同时将溢出位置1(说明此数据已经不在ahe中)。这样在写回操作完成后，P中相关数据块信息已置为无效，但是目录中仍然保持着原先P持有数据时的状态，内存中对应区域已为修改后的“干净数据，目录中该数据相应的状态也由“老变成了“新，说明内存中此数据已为更新后的数据。(5)溢出数据的事务冲突检测步骤：处理机Q重新发出恳求数据信号给目录，由于目录中的状态还没有改变。步骤：目录根据当前状态再次将恳求转发给处理机P，而此时Q恳求的数据块已经写回内存中去了，并不在P的ahe中，P收到恳求

15、信号后检查到自身的溢出位已经置位，它认为此数据可能由于某种原因不在ahe中，但是仍然与它相关。比方：由于此数据块大小大于ahe规定块大小而不能放下，但仍需操作。步骤：P发出冲突信号(NAK)给Q，但是这个冲突并不是真正意义上的冲突，而是P假设的冲突。步骤：Q收到冲突信号后处理冲突同时发送信号给目录，说明此次恳求再次失败。(6)目录中数据状态的懒惰(Lazy)更新处理机P提交事务后将Tunt减1，将对应ahe块的读/写标志位和溢出标志位清零，但此时目录中的状态仍然为P。步骤：此时一旦处理机Q重新发出恳求此数据信号。步骤：该信号会再一次通过目录转发给处理机P，但此时P的溢出位已经被清空。步骤：P通

16、过发送去除信息(LEAN)给目录通知目录不必再转发恳求信息，目录中的数据信息有效可以直接发送给恳求的处理机Q。步骤：目录根据索引关系找到相关数据发送给处理机Q。步骤：Q收到数据后进展处理同时将应答信号发送给目录，说明恳求成功同时将目录对应数据项状态置EQ，表示此时处理机Q独占此数据资源。但在执行冲突检测的过程中也会存在错误的冲突，比方：当处理机Q恳求访问一个数据块，该数据块在目录中的状态为P，而处理机P已经执行到后续事务，同时也置了溢出位。P发送冲突信号给Q，但这个冲突并不是因处理机Q恳求的数据正被其他占有而产生的冲突，是一种无关的冲突。所以必须采取一种机制将目录状态及时更新。2.3操作系统对

17、LgT的支持由于事务的引入，传统操作系统已经不能满足要求，必须更改或扩展操作系统使事务能稳定高效的执行。首先，基于LgT系统，操作系统负责对日志进展创立和维护。它为每一个执行线程开拓一片日志区域，并将该区域入口地址写到LgBase存放器中，同时当某数据存入日志后使LgPinter指针后移，用来存放新数据。当发生回滚，操作系统根据目前LgPinter指针从后向前恢复数据直到LgPinter与LgBase指向一样为止。其次，当执行事务发生切换时，操作系统可以通过扩展目前的TB(线程控制块)来对事务相关存放器内容等信息进展保存。再次，当发惹事务级线程切换时，操作系统判断切换原因(包括其他线程抢占、时

18、间片到达、事务之间冲突等而执行的切换)，通知调度器采取不同的切换策略或冲突策略来完成切换。最后，由于中断内新创立的事务和被中断事务冲突而导致活锁(被中断事务挂起得不到执行，中断内新创立事务由于冲突策略一直回滚重新执行回滚，也得不到执行)，操作系统必须可以记录回滚次数并设定一个门限值，假如同一事务回滚数超过此门限，操作系统可以强行中止该事务而调度其他事务。本文介绍T的根本原理，并对当前主流T系统LgT进展分析实现，得出以下结论：要实现高效的事务处理必需要有一个很好的基于事务模型的硬件构造。比方：LgT，硬件专门为T添加了LgBase、LgPinter等存放器并改变了ahe的构造，在ahe中参加了

19、读(R)和写()标志位；这样对事务版本管理以及冲突管理都带来了前所未有的作用，这也是此T构造优越性的表达。要高效的进展事务处理必需要有T操作系统的支持，上文中提到了一些操作系统对LgT的相关支持，但假如要完美的支持事务还需要不断更改和优化已有的操作系统，最终的目的是将操作系统事务化，并能很好的处理事务化的用户级应用。目前T系统(包括LgT)虽然通过一些特有的构造和机制解决了事务处理的一些问题，但是面对今后的开展，像多级嵌套事务的复杂应用、中断事务化(特别是外部设备的中断)、挂起事物与执行事务冲突问题、被切换事务的执行选择(重新调度后，被切换事务可能回滚也可能继续接着执行)等问题都需要我们不断的去研究，去寻找最优的解决方法一一攻克，所以对T的研究任重而道远。1Yen，L.andJ.Bbba，etal.LgT-SE：DeuplingHardareTransatinaleryfrahes.InPr.fThirteenthAnnualInternatinalSyp.nHigh-PerfraneputerArhi