شرایط لازم و کافی برای ایست های بازرسی جهانی سازگار - تراکنش در یک سیستم پایگاه داده توزیع شده

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.

It is a common practice to take checkpoint of a database from time to time, and restore the database to the most recent checkpoint when a failure occurs. It is desirable that a global checkpoint of a database records a state of the database which reflects the effect of a set of completed transactions and not the results of any partially executed transactions. Such a checkpoint of the database is called a transaction-consistent global checkpoint [23]. A straightforward way to take a transaction-consistent global checkpoint of a distributed database is to block all newly submitted transactions and wait until all the currently executing transactions finish and then take the checkpoint. Such a checkpoint is guaranteed to be transaction-consistent, but this approach is not practical, since blocking newly-submitted transactions will increase transaction response time which may not be acceptable for the users of the database. Another approach would be to run a read only transaction which would read the entire database and save it to stable storage; the underlying concurrency control algorithm will ensure that the saved state is transaction-consistent. This would be inefficient especially in the presence of long-living transactions. A more efficient way would be to save (checkpoint) the state of each data item independently and periodically without blocking any transaction. However if each data item is checkpointed independently and periodically, some checkpoints of some data items may not be part of any transaction-consistent global checkpoint of the database and hence are useless. In this paper, we address this issue and establish the necessary and sufficient conditions for a checkpoint of a data item (or the checkpoints of a set of data items) to be part of a transaction-consistent global checkpoint of the database. This result would be useful for constructing a transaction-consistent global checkpoint incrementally from the checkpoints of each individual data item. By applying this condition, we can start from an useful checkpoint of any data item and then incrementally add checkpoints of other data items until we get a transaction-consistent checkpoint of the database.

Checkpointing has been traditionally used for handling failures in distributed database systems. An efficient checkpointing algorithm should be non-intrusive in the sense that it should not block the normal transactions while checkpoints are taken. A simple approach would be to run a read only transaction which would read the entire database and store it in stable storage. The underlying concurrency control algorithm would ensure that the saved state is tr-consistent. This approach would be very inefficient, especially in the presence of long-living transactions. If each data item is independently checkpointed, not all the checkpoints taken may not be useful for constructing a tr-consistent global checkpoint of the entire database. We have presented the necessary and sufficient condition for a set of checkpoints of a set of data items in the database to be part of a tr-consistent global checkpoint of the distributed database. This theory helps in determining which checkpoints are useful for constructing tr-consistent global checkpoints and which are not. It also helps in constructing tr-consistent global checkpoints of the database incrementally starting from an useful checkpoint of a data item. Moreover, the necessary and sufficient conditions established can throw light on designing non-intrusive check pointing methods which allow data items to be checkpointed independently while at the same time ensure each checkpoint taken is (useful) part of a tr-consistent global checkpoint.