数据库系统概论：基于锁协议的并发控制

发表于 更新于 分类于

Lock-Based Protocols

Lock

A lock is a mechanism to control concurrent access to data item.

Data items can be locked in two modes:

  • Exclusive (X) mode. Data item can be both read as well as written. X-lock is requested using lock-X instruction.
  • Shared (S) mode. Data item can only be read. S-lock is requested using lock-S instruction.

Transaction can proceed only after request is granted.

Lock-compatibility

matrix:

S X
S true false
X false false

一个事务如果想对一个数据项上锁，那这个锁必须与这个数据项已有的锁兼容。

上了 S 锁其他事务就无法上 X 锁，上了 X 锁就无法再上任何锁。

A transaction may be granted a lock on an item if the requested lock is compatible with locks already held on the item by other transactions.

Schedule With Lock Grants

A locking protocol is a set of rules followed by all transactions while requesting and releasing locks.
Locking protocols enforce(强制) serializability by restricting(限制) the set of possible schedules.

Deadlock

T3T_3 T4T_4
lock-X(B)
read(B)
B:=B-50
write(B)
lock-S(A)
read(A)
lock-S(B)
lock-X(A)

T3T_3 等待 T4T_4 释放锁 A，T4T_4 等待 T3T_3 释放锁 B，二者互相等待，都无法进行，构成死锁。

要处理这个死锁，T3T_3 和 T4T_4 中的其中一个必须回滚，直到其释放它的锁。

The Two-Phase Locking Protocol

2 PL

A protocol which ensures conflict-serializable schedules.

Phase 1: Growing Phase

  • Transaction may obtain locks
  • Transaction may not release locks

Phase 2: Shrinking Phase

  • Transaction may release locks
  • Transaction may not obtain locks

二阶段锁协议并不能解决死锁问题。需要扩展二阶段锁协议以保证不出现级联回滚（一个事务的回滚带动多个事务回滚）。

Two-phase locking does not ensure freedom from deadlocks
Extensions to basic two-phase locking needed to ensure recoverability of freedom from cascading roll-back

Strict two-phase locking

一个事务不能释放它的所有 X 锁（可读可写）直至其提交或终止

A transaction must hold all its exclusive ( X ) locks till it commits/aborts.

保证了可恢复性且避免了级联回滚

Ensures recoverability and avoids cascading roll-backs.

Rigorous two-phase locking

一个事务不能释放它的所有锁直到它提交或者终止。

保证了事务可以按照他们提交的顺序进行序列化。

Most databases implement rigorous two-phase locking, but refer to it as (称之为) simply two-phase locking

Two-phase locking is not a necessary condition for serializability

Locking Protocols

当调度可以由一组遵守该锁协议的事务生成，则该调度在该锁协议下是合法的。

如果锁协议可以确保所有遵守该协议的调度都是可序列化的，那该协议可以保证可序列化。

  • A schedule S is legal under a locking protocol if it can be generated by a set of transactions that follow the protocol
  • A protocol ensures serializability if all legal schedules under that protocol are serializable

Two-phase locking protocol with lock conversions

Growing Phase

可以申请 S 锁和 X 锁，可以将 S 锁转化为 X 锁。

  • can acquire a lock-S on item
  • can acquire a lock-X on item
  • can convert a lock-S to a lock-X (upgrade)

Shrinking Phase

可以申请释放S 锁和 X 锁，可以将 X 锁转化为 S 锁。

  • can release a lock-S
  • can release a lock-X
  • can convert a lock-X to a lock-S (downgrade)

Automatic Acquisition of Locks

在读写时自动申请锁

A transaction Ti issues the standard read/write instruction, without explicit locking calls.

Implementation of Locking

实现锁

A lock manager can be implemented as a separate(分离的、单独的) process

事务可以通过发送消息来请求锁

Transactions can send lock and unlock requests as messages

锁管理器通过回复一个许可消息来响应锁请求（或者让它回滚）

The lock manager replies to a lock request by sending a lock grant messages (or a message asking the transaction to roll back, in case of a deadlock)

请求锁的事务会一直等待直到接收到相应

The requesting transaction waits until its request is answered

锁管理器在内存中维护一张锁表以记录已被允许的锁和正在请求的锁

The lock manager maintains an in-memory data-structure called a lock table to record granted locks and pending requests

Multiple Granularity

多粒度

允许数据项具有各种大小，并定义数据粒度的层次结构，其中小粒度嵌套在大粒度中。

Allow data items to be of various sizes and define a hierarchy(层次结构) of data granularities(粒度), where the small granularities are nested within larger ones

可以用树结构来形容粒度（层次结构、大粒度数据包含小粒度数据）。当一个事务显式地锁定一个节点时，它同时隐式地、以相同模式的锁 锁定了这个节点的所有子节点。

When a transaction locks a node in the tree explicitly, it implicitly locks all the node’s descendants in the same mode.

Granularity of locking 锁的粒度(level in tree where locking is done)：

  • Fine(细) granularity(lower in tree): high concurrency, high locking overhead(开销) .
  • Coarse(粗) granularity(higher in tree): low locking overhead, low concurrency.

Tree levels (starting from the coarsest (top) level):

  1. Database
  2. Area
  3. file
  4. record