数据库系统中的并发控制与恢复

需积分: 3 18 浏览量更新于2024-06-28 收藏 19.55MB PDF 举报

"Concurrency Control and Recovery in Database Systems-Ch7.pdf" 这份文件主要探讨了数据库系统中的并发控制与恢复机制，特别是在分布式环境下的应用。它由Philip A. Bernstein、Vassos Hadzilacos和Nathan Goodman撰写，涵盖了事务处理、可恢复性、串行化理论以及各种锁定和非锁定调度器的策略。 1. **并发控制**是数据库系统中确保多个事务同时执行时数据一致性的重要机制。事务是数据库操作的基本单位，它由一系列数据库操作组成，并被视为一个逻辑上的单元，要么全部成功完成（提交），要么全部不完成（回滚）。 2. **可恢复性**是确保即使在系统故障或异常情况下，数据库也能恢复到一致状态的关键特性。这通常通过日志记录事务的操作来实现，以便在需要时可以重播或撤销这些操作。 3. **串行化**是并发控制的一个目标，它保证了并发执行的事务看起来像按照某种特定顺序依次执行一样，即事务之间的相对顺序保持不变，避免了并发操作导致的数据不一致性问题。 4. **数据库系统模型**中，作者可能会讨论不同的事务处理模型，如ACID（原子性、一致性、隔离性、持久性）属性，以及这些属性如何在并发环境中得以维持。 5. **串行化理论**部分详细介绍了历史记录、可串行化历史记录的概念，以及串行化定理，用于判断一组事务的历史是否可以被重排序为一个串行的历史，而不违反事务的隔离性和一致性。 6. **两阶段锁定（2PL）**是一种常用的并发控制方法，包括积极调度和保守调度两种策略。基本的2PL要求事务在修改数据之前获取锁，在事务结束时释放所有锁。然而，这种方法可能导致死锁，因此需要解决死锁检测和避免的策略。 7. **非锁定调度器**如时间戳排序（TO）和序列化图测试（SGT）等提供了另一种方法，它们避免了锁定带来的开销，但可能需要更复杂的算法来确保串行化。 8. **多粒度锁定**允许在不同级别（例如页面、行甚至字段）上使用锁，增加了并发性能，但也带来了新的挑战，如幻读问题，需要特殊的解决方案。 9. **分布式环境**中的并发控制和恢复增加了网络延迟和故障的可能性，文件中可能会详细讨论分布式两阶段锁定、分布式死锁及其处理。 10. **性能优化**是并发控制的关键考虑因素，包括锁的实现细节、避免死锁和提高事务吞吐量的策略。 11. **树锁定**是针对特定数据结构（如B树）的锁定策略，以优化多级索引的并发访问。 12. **证书（Certifiers）**和认证协议在非锁定调度器中用于验证事务执行的正确性，确保事务之间的冲突得以解决。这份文档深入探讨了数据库系统中并发控制和恢复的复杂性，从理论到实践，从基本的锁定策略到高级的并发调度算法，全面阐述了保证数据库安全和高效运行的关键技术。

12 CHAPTER 1

THE PROBLEM

Read,(Accounts[ 131)

returns the value $1000

Read,(Accounts[l3])

returns the value $1000

Write,(Accounts[l3], $101,000)

Commit,

Write,(Accounts[l3], $1100)

Commit,

The result of this execution is that

Accounts[l3] contains $1100.

Although customer 2’s deposit was successfully accomplished, its interference

with customer l’s execution of Deposit caused customer 2’s deposit to be lost.

This lost updczte phenomenon occurs whenever two transactions, while

attempting to modify a data item, both read the item’s old value before either

of them writes the item’s new value.

Another concurrency control problem is illustrated by the following

program, called PrintSum, which prints the sum of the balances of two

accounts.

Procedure PrintSum

begin

Start;

input(account1,

account2);

templ

: = Read( Accounts[ accountl]);

output(temp1);

temp2 : =

Read(Accounts[account2]);

output(temp2);

templ :=

templ + temp2;

output(temp1);

Commit

end

Suppose accounts 7 and 86 each have a balance of $200, and customer 3

prints the balances in accounts 7 and 86 (using PrintSum) at about the same

time that customer 4 transfers $100 from account 7 to account 86 (using

Transfer, discussed previously under Transaction Syntax). The concurrent

execution of these two transactions might lead to the following execution of

Reads and Writes.

Read,(Accounts[7])

returns the value $200

Write,(Accounts[7], $100)

Read,(Accounts[7])

returns the value $100

Read,(Accounts[86])

returns the value $200

Read,(Accounts[86])

returns the value $200

Write,(Accounts[86], $300)

Commit4

Commit,

1.3 SERIALIZABILITY 13

Transfer interferes with PrintSum in this execution, causing PrintSum to print

the value $300, which is not the correct sum of balances in accounts 7 and 86.

Printsum did not capture the $100 in transit from account 7 to 86. Notice that

despite the interference, Transfer still installs the correct values in the database.

This type of interference is called an inconsistent retrieval. It occurs when-

ever a retrieval transaction reads one data item before another transaction

updates it and reads another data item after the same transaction has updated

it. That is, the retrieval only sees some of the update transaction’s results.

Serializable Executions

In the preceding examples, the errors were caused by the interleaved execution

of operations from different transactions. The examples do not exhaust all

possible ways that concurrently executing transactions can interfere, but they

do illustrate two problems that often arise from interleaving. To avoid these

and other problems, the kinds of interleavings between transactions must be

controlled.

One way to avoid interference problems is not to allow transactions to be

interleaved at all. An execution in which no two transactions are interleaved is

called serial. More precisely, an execution is serial if, for every pair of transac-

tions, a11 of the operations of one transaction execute before any of the opera-

tions of the other. From a user’s perspective, in a serial execution it looks as

though transactions are operations that the DBS processes atomically. Serial

executions are correct because each transaction individually is correct (by

assumption), and transactions that execute serially cannot interfere with each

other.

One could require that the DBS actually process transactions serially.

However, this would mean that the DBS could not execute transactions

concurrently, for concurrency means interleaved executions. Without such

concurrency, the system may make poor use of its resources, and so might be

too inefficient. Only in the simplest systems is serial execution a practical way

to avoid interference.

We can broaden the class of allowabIe executions to include executions

that have the same effect as serial ones. Such executions are called serializable.

More precisely, an execution is serializable if it produces the same output

and has the same effect on the database as some serial execution of the same

transactions. Since serial executions are correct, and since each serializable

execution has the same effect as a serial execution, serializable executions are

correct too.

The executions illustrating lost updates and inconsistent retrievals are not

serializable. For example, executing the two Deposit transactions serially, in

either order, gives a different result than the interleaved execution that lost an

update, so the interleaved execution is not serializable. Similarly, the inter-

leaved execution of Transfer and PrintSum has a different effect than every

serial execution of the two transactions, and so is not serializable.

14 CHAPTER 1

THE PROBLEM

Although these two interleaved executions are not serializable, many

others are. For example, consider this interleaved execution of Transfer and

PrintSum.

Read,(Accounts[7])

returns the value $200

Write,(Accounts[7], $100)

Read,(Accounts[7])

returns the value $100

Read,( Accounts[ 861)

returns the value $200

Write,(Accounts[86], $300)

Commit,

Read,(Accounts[86]) returns the value 5300

Commit,

This execution has the same effect as serially executing Transfer followed by

PrintSum. In such a serial execution, Read,(Accounts[‘i]) immediately follows

Write,(Accounts[86], 5300). Although the order of execution of operations in

this serial execution is different from the interleaved execution, the effect of

each operation is exactly the same as in the interleaved execution. Thus, the

interleaved execution is serializable.

Serializability is the definition of correctness for concurrency control in

DBSs. Given the importance of the concept, let us explore its strengths and

weaknesses.

Most importantly, a DBS whose executions are serializable is easy to

understand. To its users, it looks like a sequential transaction processor. A

programmer can therefore write each transaction as if it will execute all by

itself on a dedicated machine. Potential interference from other transactions is

precluded and hence can be ignored.

A DBS that produces serializable executions avoids the kind of interference

illustrated by the earlier examples of lost updates and inconsistent retrievals. A

lost update occurs when two transactions both read the old value of a data

item and subsequently both update that data item. This cannot happen in a

serial execution, because one of the transactions reads the data item value writ-

ten by the other. Since every serializable execution has the same effect as a

serial execution, serializable executions avoid lost updates.

An inconsistent retrieval occurs when a retrieval transaction reads some

data items before an update transaction updates them and reads some other

data items after the update transaction updates them. This cannot happen in a

serial execution, because the retrieval transaction reads al1 of the data items

either before the update transaction performs any updates, or after the update

transaction performs all of its updates. Since every serializable execution has

the same effect as some serial execution, serializable executions avoid inconsis-

tent retrievals too.

1.3SERlALlZABlLlTY 15

Consistency Preservation

The concept of consistent retrieval can be generalized to apply to the entire

database, not just to the data items retrieved by one transaction. This general-

ization provides another explanation of the value of serializability,

Assume that some of the states of the database are defined to be consistent.

The database designer defines consistency predicates that evaluate to true for

the consistent states and false for the other (inconsistent) states. For example,

suppose we augment the banking database of Accounts to include a data item,

Total, which contains the sum of balances in all accounts. A consistency predi-

cate for this database might be “Total is the sum of balances in Accounts.” The

database state is consistent if and only if (iff) the predicate is true.

As part of transaction correctness, we then require that each transaction

preserve database consistency. That is, whenever a transaction executes on a

database state that is initially consistent, it must leave the database in a consis-

tent state after it terminates. For example, Transfer preserves database consis-

tency, but Deposit does not, because it does not update Total after depositing

money into an account. To preserve database consistency, Deposit needs to be

modified to update Total appropriately.

Notice that each Write in Transfer, taken by itself, does not preserve data-

base consistency. For example, Write(Accounts[oldaccount], temp - amount)

unbalances the accounts temporarily, because after it executes, Accounts and

Total are inconsistent. Such inconsistencies are common after a transaction has

done some but not all of its Writes. However, as long as a transaction fixes

such inconsistencies before it terminates, the overall effect is to preserve consis-

tency, and so the transaction is correct.

Consistency preservation captures the concept of producing database

states that are meaningful. If each transaction preserves database consistency,

then any serial execution of transactions preserves database consistency. This

follows from the fact that each Bansaction leaves the database in a consistent

state for the next transaction. Since every serializable execution has the same

effect as some serial execution, serializable executions preserve database

consistency too.

Ordering Transactions

All serializable executions are equally correct. Therefore, the DBS may execute

transactions in any order, as long as the effect is the same as that of some serial

order. However, not all serial executions produce the same effect. Sometimes a

user may prefer one serial execution of transactions over another. In such a

case, it is the user‘s responsibility to ensure that the preferred order actually

occurs.

For example, a user may want her Deposit transaction to execute before

her Transfer transaction. In such a case, she should not submit the transactions

CHAPTER 1 I THE PROBLEM

at the same time. If she does, the DBS can execute the transactions’ operations

in any order (e.g., the Transfer before the Deposit). Rather, she should first

submit the Deposit transaction. Only after the system acknowledges that the

Deposit transaction is committed should she submit the Transfer transaction,

This guarantees that the transactions are executed in the desired order.3

We will be constructing schedulers that only guarantee serializability. If

users must ensure that transactions execute in a particular order, they must

secure that order by mechanisms outside the DBS.

Limitations of Serializability

In many types of computer applications, serializability is not an appropriate

goal for controlling concurrent executions. In fact, the concept of transaction

may not even be present. In these applications, methods for attaining

serializability are simply not relevant.

For example, a statistical application may be taking averages over large

amounts of data that is continually updated. Although inconsistent retrievals

may result from some interleavings of Reads and Writes, such inconsistencies

may only have a small effect on the calculation of averages, and so may be

unimportant. By not controlling the interleavings of Reads and Writes, the

DBS can often realize a significant performance benefit - at the expense of

serializability.

As another example, process control programs may execute forever, each

gathering or analyzing data to control a physical process. Since programs

never terminate, seria1 executions don’t make sense. Thus, serializability is not

a reasonable goal.

A common goal for concurrency control in systems with nonterminating

programs is mutual exclusion. Mutual exclusion requires the section of a

program that accesses a shared resource to be executed by at most one

program at a time. Such a section is called a critical section. We can view a

critical section as a type of transaction. Mutual exclusion ensures that critical

sections (i.e., transactions) that access the same resource execute serially. This

is a strong form of serializability.

‘If two

transactions

do not

interact,

then it is

possible rhat

the user

cannot

control their effec-

tive order of

execution.

For

example, suppose

the user

waits

for

I, to commit

before submit-

ting TL, and suppose no data item is accessed by both transactions. If other transactions were

executing concurrently with T1 and i-2, it is still possible thar the oniy serial execution equiva-

lent to the interleaved execution that occurred is one in which Tz precedes T,. This is odd, but

possibly doesn’t matter since 7, and Tz don’t interact. However, consider the discussion of

Terminal I/O in Section 1.2. If the user uses the output of T, to construct the input to T,, then

iT, must effectively execute before r,. This incorrect behavior is prevented by rhe most popular

concurrency control method, two phase locking (see Chapter 3), but not by all methods, This

rather subtle point is explored further in Exercises 2.12 and 3.4.

剩余318页未读，继续阅读

程序员潇然

粉丝: 71

数据库系统中的并发控制与恢复

Concurrency Control and Recovery in Database Systems

Concurrency Control and Recovery in Database Systems全本.pdf

数据库系统中的并发控制和恢复Concurrency Control And Recovery in Database Systems

concurrency control and recovery in database systems pdf

C++ Concurrency in Action - Anthony Williams.pdf

python-oslo-concurrency-doc-3.29.1-1.el7.noarch.rpm

python-oslo-concurrency-lang-3.30.1-1.el8.noarch.rpm

python-oslo-concurrency-doc-3.30.0-2.el8.noarch.rpm

【电磁】基于matlab GUI FDTD时域有限差分的变电站暂态电磁计算【含Matlab源码 11057期】.zip

alsa-lib-devel-1.1.8-1.el7.x64-86.rpm.tar.gz

最新资源