一种高效的合作实时事务并行检验点算法

许多数据和活动上都有很强时间性的应用在地理上同时具有分布性,这种应用需求使得分布式实时数据库的研完成为数据库研究领域的热点。在实时事务执行时,事务故障或数据竞争会导致事务重启,为了减少因重启而损失的工作量,可以采用检验点技术以利于事务时间正确性的满足。在一些分布式实时数据库应用中,不同结点的事务通过消息交换形成合作关系,当某一事务记检验点时,为保证合作事务间的全局一致性,相关事务也要相应地记检验点。传统的协同检验点方法没有考虑应用的定时约束,不能很好地支持分布式实时事务处理。本文提出了一种高效的并行协同检验点方法,该算法既具有最小协同检验点特性又使全局检验点过程延时最小。实验表明该算法减少了全局检验点阻塞时间,有利于分布式实时事务截止期的满足。     

支持移动合作实时事务的一种新的协同检验点算法

现有的协同检验点方法在移动环境中会带来较大的检验点过程延时 ,不能很好地支持实时事务处理 .提出了一种新的协同并行检验点方法 ,在正常的消息传输过程中 ,通过一点额外的带宽传送事务间检验点依赖关系 ;在某一事务记检验点时 ,尽可能地同时通知相关的事务记检验点 .实验表明 ,该算法对网络带宽没有明显的增加 ,而能大大降低事务记检验点的延时 ,使系统中超截止期的事务比例大大降低     

一种分布式实时事务调度算法

传统的乐观并发控制策略利用了一些不必要的事务重启来保证数据的一致性，事务重启能够极大的增加系统载荷以及加强资源和数据的竞争，在分布式环境下，由于系统的复杂性和较高的通讯开销加剧了该问题．针对该问题本文提出了一种靳的乐观并发控制策略，通过动态调整事务串行化执行顺序来避免不必要的事务重启．当把这种新的并发控制策略在分布式实时环境中实现时，考虑到分布式事务的实时性要求，本文提出把写阶段从临界区中分离出来的方法，并用顺序加锁的策略来保证分布式事务执行的正确性，最后给出了该实现方法的正确性证明．     

实时内存数据库分区模糊检验点策略

检验点技术是实时内存数据库恢复的关键技术之一．在分析实时内存数据库数据特征基础上,给出了综合考虑数据和事务定时约束的数据检验点优先级计算方法．然后,结合内存数据库段式存储结构,讨论了一种基于数据段检验点优先级的分区模糊检验点策略PFCS—SCP．通过性能测试,表明所提出的检验点策略能减低超截止期事务比率．     

使用相似和事务传送处理移动环境下的过载和事务重启问题

为减少移动实时数据库中优先级倒置而引起的事务重启和过载问题,探讨并使用事务船载方法来减轻移动网络跨区处理以及优先级倒置时所引起的过载问题.研究并采纳基于相似的分布式高优先级2阶段锁定协议(SDHP-2PL)来减少优先级倒置时事务重启的数量以保证移动实时环境下数据的正确性和截至时间的满足.由于采用事务船载方法使得事务的过载通信数量大量减少,同时使用相似概念也增加锁请求被授予的概率.     

移动实时嵌套事务的并发控制

在移动计算环境中，事务移动性和无线网络固有的缺陷使得传统分布式实时事务管理机制不足以支持移动实时事务的执行，故有必要为移动实时事务研究新的事务处理机制以提高其成功率．该文着重研究移动实时事务的并发控制机制．首先，该文给出了一个考虑事务定时限制以及移动性的嵌套事务模型．然后，为减少移动分布式环境中解决数据冲突的开销，该文研究了一种结合优先级夭折和优先级继承的基于封锁的并发控制协议PAI-2PL．当高优先级事务被低优先级事务阻塞时，对于相同家族事务，采用优先级继承方法解决冲突；而对于不同家族事务，则夭折重启低优先级事务．另外，为减少由于断接所引起的无效阻塞，PAI-2PL允许低优先级事务夭折处于断接状态的高优先级事务．通过性能测试，表明所提出的事务模型及并发控制机制能提高实时事务的成功率．     

一种基于移动环境的混合乐观实时事务处理策略

随着移动计算技术的快速发展，移动环境下涉及到实时事务处理的应用需求正逐渐增长．由于移动环境下固有特性：高的网络延迟、频繁的断接性和移动性等，采用传统的事务处理技术，在移动环境下很难满足事务的截止期要求．提出了一种基于高优先级两段锁的混合乐观实时事务并发控制协议(HORTCC—SHP2PL)．该协议在移动实时事务处理中将乐观并发控制和高优先级两段锁结舍起来，利用两阶段提交协议实现移动实时事务的全局提交．为了进一步减少移动实时事务重启的数目．在并发控制协议中引入了相似性的概念．仿真实验显示．与分布式高优先级两段锁(HP2PL)比较，HORTCC—SHP2PL明显地减少了实时事务错过截止期的比率，提高了事务的并发度，能更好的满足移动实时事务截止期的要求．     

分布式实时数据库并发控制

在集中式实时数据库中，事务并发控制一般采用基于优先级的事务重启或优先级继承．在分布式实时数据库中，由于一个主事务的各参与事务可能分布在多个节点上，事务重启一方面会造成系统资源的极大浪费，另一方面又会加大网络传输的负担．而在优先级继承策略中，被阻塞的高优先级事务的执行完全依赖于阻塞它的低优先级事务，在分布式环境中，事务的执行具有更多的不可确定的因素，这就很难保证被阻塞事务的截止期．本文提出了一种基于数据多映像的并发控制协议，事务因访问数据而形成不同的依赖关系，改变高优先级事务和低优先级事务的依赖关系从而更有利于高优先级事务而又不矢折或阻塞其他事务，从而大大提高事务执行的并发度，更好地满足实时事务的截止期．     

基于全局目录的分布式数据库加锁管理算法

针对简单的分布式封锁方法和完全分布式加锁算法在加锁时所需通信开销大、封锁时间长、锁管理复杂的缺点,结合集中式数据库加锁管理算法的优点,指出了在分布式数据库中保持事务可串行化方面存在的难点,利用全局目录和事务调度器,提出了基于全局目录的分布式数据库加锁管理算法。该算法使用两阶段封锁协议和多粒度封锁协议,在全局目录服务器中使用全局锁管理器管理和维护全局目录中的锁结点信息并对分布式封锁请求进行集中控制和灵活管理,能有效地保证事务的可串行化调度,降低封锁时的通信开销。     

基于相似和谨慎等待的移动分布式实时数据库并发控制方法

随着移动计算技术的快速发展,对移动环境下实时事务处理的需求也不断增加.而造成事务重启和阻塞的有限带宽和频繁断开是移动环境下实时系统特有的属性,因此过去针对分布式实时数据库系统的并发控制研究并不能够直接应用在移动分布式实时数据库上.把相似概念和谨慎等待方案与高优先级2阶段锁定(DHP-2PL)结合起来,形成基于相似和谨慎等待的移动分布式实时数据库的并发控制算法,以增加系统并发性,减少重启和阻塞事务的数量,并通过判断事务是否断开而探讨了相应的解决策略,降低了断开问题对系统性能的影响.     

Adaptive checkpointing in message passing distributed systems

Determining consistent global checkpoints is common to many distributed problems such as fault-tolerance, distributed debugging, properties detection, etc. Uncoordinated and coordinated checkpointing algorithms have been traditionally used for such determinations. This paper addresses a third technique, namely adaptive checkpointing, that has recently emerged. This technique assumes processes take local checkpoints independently and requires them to take additional local checkpoints in order that all local checkpoints be members of some consistent global checkpoint. We first study the characteristics of such adaptive algorithms. Then, a general adaptive checkpointing algorithm is designed from a condition, first stated by Netzer and Xu, that answers the following question: ‘does a given local checkpoint belong to a consistent global checkpoint’' (such a local checkpoint is not useless). The resulting algorithm has the nice property to reduce the number of additional local checkpoints taken to ensure the property ‘no local checkpoint is useless’. Futhermore, it provides each local checkpoint with a consistent global checkpoint to which it belongs. Compared to uncoordinated and coordinated checkpointing algorithms, this algorithm combines the advantages of both without inheriting their drawbacks.     

Necessary and sufficient conditions for transaction-consistent global checkpoints in a distributed database system

Checkpointing and rollback recovery are well-known techniques for handling failures in distributed systems. The issues related to the design and implementation of efficient checkpointing and recovery techniques for distributed systems have been thoroughly understood. For example, the necessary and sufficient conditions for a set of checkpoints to be part of a consistent global checkpoint has been established for distributed computations. In this paper, we address the analogous question for distributed database systems. In distributed database systems, transaction-consistent global checkpoints are useful not only for recovery from failure but also for audit purposes. If each data item of a distributed database is checkpointed independently by a separate transaction, none of the checkpoints taken may be part of any transaction-consistent global checkpoint. However, allowing individual data items to be checkpointed independently results in non-intrusive checkpointing. In this paper, we establish the necessary and sufficient conditions for the checkpoints of a set of data items to be part of a transaction-consistent global checkpoint of the distributed database. Such conditions can also help in the design and implementation of non-intrusive checkpointing algorithms for distributed database systems.     

A fully informed model-based checkpointing protocol for preventing useless checkpoints

Checkpointing and rollback recovery are widely used techniques for handling failures in distributed systems. When processes involved in a distributed computation are allowed to take checkpoints independently without any coordination with each other, some or all of the checkpoints taken may not be part of any consistent global checkpoint, and hence, are useless for recovery. Communication-induced checkpointing algorithms allow processes to take checkpoints independently and also ensure that each checkpoint taken is part of a consistent global checkpoint by forcing processes to take some additional checkpoints. It is well known that it is impossible to design an optimal communication-induced checkpointing algorithm (i.e. a checkpointing algorithm that takes minimum number of forced checkpoints). So, researchers have designed communication-induced checkpointing algorithms that reduce forced checkpoints using different heuristics. In this paper, we present a communication-induced checkpointing algorithm which takes less number of forced checkpoints when compared to some of the existing checkpointing algorithms in its class.     

Communication-based prevention of useless checkpoints in distributed computations

Summary. A useless checkpoint is a local checkpoint that cannot be part of a consistent global checkpoint. This paper addresses the following problem. Given a set of processes that take (basic) local checkpoints in an independent and unknown way, the problem is to design communication-induced checkpointing protocols that direct processes to take additional local (forced) checkpoints to ensure no local checkpoint is useless. The paper first proves two properties related to integer timestamps which are associated with each local checkpoint. The first property is a necessary and sufficient condition that these timestamps must satisfy for no checkpoint to be useless. The second property provides an easy timestamp-based determination of consistent global checkpoints. Then, a general communication-induced checkpointing protocol is proposed. This protocol, derived from the two previous properties, actually defines a family of timestamp-based communication-induced checkpointing protocols. It is shown that several existing checkpointing protocols for the same problem are particular instances of the general protocol. The design of this general protocol is motivated by the use of communication-induced checkpointing protocols in “consistent global checkpoint”-based distributed applications such as the detection of stable or unstable properties and the determination of distributed breakpoints. Received: July 1997 / Accepted: August 1999     

面向更新密集型应用的内存数据库高效检查点技术

面向更新密集型应用的内存数据库系统,其检查点技术应符合几个关键的要求,包括检查点操作对正常事务处理的干扰尽可能小、能够处理存取倾斜状况、支持数据库系统的快速恢复、提供恢复过程中的系统可用性等.该文提出一种事务一致的分区检查点技术,采用基于元组的动态多版本并发控制机制,避免了读写事务的加锁冲突,提高系统吞吐能力;检查点操作以只读事务形式实现,存多版本并发控制下,避免检查点操作对正常事务处理的堵塞;由于检查点文件是事务一致的,只需要记录事务的Redo 日志信息,在系统恢复过程中,只需要对日志文件进行一遍扫描处理,加快恢复过程;基于优先级的数据分区装载和恢复,使得恢复过程中新事务的数据存取请求迅速得到满足,保证了恢复过程中的系统可用性.由于采用两级版本管理机制以及动态版本共享技术,多版本管理的空间开销降低到可以接受的水平.实验结果表明,文中提出的检查点技术方案获得比模糊检查点技术高27%的系统吞吐量,同时版本管理的空间开销在可接受的范围之内,满足高性能应用的要求.     

A Low-Cost Checkpointing Technique for Distributed Databases

For distributed databases, checkpointing is used to ensure an efficient way to perform global reconstruction. However, the need for global reconstruction is infrequent. Most current checkpointing approaches for distributed databases are too expensive during run time. Some of them allow the checkpointing process to run in parallel with normal transactions at the cost of more data and resource contention, which in turn causes longer response time for normal transactions. Thus, an efficient way to checkpoint distributed databases is needed to avoid degrading the system performance. This paper presents a low-cost solution, called Loosely Synchronized Local Fuzzy Checkpointing (LSLFC), to these problems. LSLFC supports global reconstruction, and our performance study shows that LSLFC has little overhead during run time.     

A non-two-phase locking protocol for global concurrency control indistributed heterogeneous database systems

A concurrency control method is proposed for global transactions in a distributed heterogeneous database system. This method is applicable when the database sites are interconnected in a rooted tree fashion. It guarantees deadlock freedom in addition to serializability. A general architecture of a heterogeneous system is given. The global transaction manager (GTM) decomposes the global transactions initiated at a site and the subtransactions received from other sites into smaller subtransactions, some of which are sent to the GTMs of the other sites, and those remaining, called g-local transactions, are to be executed by the local transaction manager (LTM) at that site. A concurrency control mechanism ensures serializability among: the local transactions (including the g-local transactions of the global ones) at each site, the global transactions and the global and local transactions together     

An efficient checkpointing method for multicomputers with wormhole routing

Efficient checkpointing and resumption of multicomputer applications is essential if multicomputers are to support time-sharing and the automatic resumption of jobs after a system failure. We present a checkpointing scheme that is transparent, imposes overhead only during checkpoints, requires minimal message logging, and allows for quick resumption of execution from a checkpointed image. Furthermore, the checkpointing algorithm allows each processorp to continue running the application being checkpointed except during the time thatp is actively taking a local snapshot, and requires no global stop or freeze of the multicomputer. Since checkpointing multicomputer applications poses requirements different from those posed by checkpointing general distributed systems, existing distributed checkpointing schemes are inadequate for multicomputer checkpointing. Our checkpointing scheme makes use of special properties of wormhole routing networks to satisfy this new set of requirements.