Concurrency Control and Recovery in Database Systems

Philip A. Bernstein, Wang Institute of Graduate Studies, Tyngsboro, MA,
Vassco Hadzilacos, Univ. of Toronto, Toronto, Ont., Canada, and
Nathan Goodman, Kendall Square Research Corporation, Cambridge, MA

Overview/Main Points

• Concurrency control
  • the activity of coordinating the actions of processes that operate in parallel, access shared data, and therefore potentially interference with each other.
  • xact
  • A xact is free to control its internal execution using any available mechanism.
  • Only interactions between different xacts need to be controlled by the DBS.
• Recovery
  • the activity of ensuring that software and hardware failures do not corrupt persistent data.
  • Xact execution examples: initially, x & y are 1, and the DBS has two xacts T₁ & T₂.
  • Recoverable execution: commit only after all xacts that supply dirty data have committed.
    • for every xact T that commits, T's Commit follows the Commit of every xact from which T read.
    • To ensure recoverable executions,
      • For a xact consisting of Reads & Writes, delay the processing of certain Commits:
        W₁(x, 2); R₂(x); W₂(y, 3); Commit₂.
      • For a xact including input and output statements, defer the output statements until after it commits.
      • For an interactive xact, re-execute the aborted xact if the DBS releases the output of the previous xact.
  • Cascading aborts
    • an aborted xact aborts other xacts that read from it.
    • W₁(x, 2); R₂(x); W₂(y, 3); Abort₁.
    • To avoid cascading aborts, the DBS allows that every xact reads only those values that were written by committed xacts, and delays those reads until knowing the outcomes of all xacts that have previously writes.
  • Strict executions (Degree 2 consistent by Gray)
    • delay both Reads and Writes for x until all xacts that have previously written x are committed or aborted, so that it avoids cascading aborts and ensures recoverable executions.
    • Consider the question of undoing a xact's writes:
      W₁(x, 1); W₁(y, 3); W₂(y, 1); Commit₁; R₂(x); Abort₂.⇔
      W₁(x, 1); W₁(y, 3); Commit₁.
    • Discrepancies between the values to be restored
      • W₁(x, 2); W₂(x, 3); Abort₁.⇒
        x = 3
      • W₁(x, 2); Abort₁; W₂(x, 3); Abort₂.⇔
        W₁(x, 2); W₂(x, 3); Abort₁; Abort₂.⇒
        x = 1
    • To guarantee recoverability, delay W(x, val) until all xacts that have previously written x are either committed or aborted.
    • The Abort operation can be implemented using before images
• Serializability (roughly corresponds to Degree 3 consistent)
  • Lost update occurs when two xacts both read the old value of a data item and subsequently both update that data item.
    • Two customers deposit money to the same account:
      R₁(x); R₂(x); W₂(x, val₂); Commit₂; W₁(x, val₁); Commit₁.⇒
      lost val₂.
  • Inconsistent retrieval occurs when a retrieval xact reads some data items before an update xact updates them and reads some other data items after the update xact updates them.
    • One xact is calculating the sum of two accounts, while another transfers money from one account to the other:
      R₄(x); W₄(x, val₁); R₃(x); R₃(y); R₄(y); W₄(y, val₂); Commit₄; Commit₃.⇒
      Incorrect sum result.
  • Serial execution: for every pair of xacts, all of the operations of one xact execute before any of the opertions of the other.
  • Serializable execution: produce the same output and has the same effect on the database as some serial execution of the same xacts.
  • Consistency Preservation
    • Consistency predicate: evaluate to true for the consistent states while false for the other (inconsistent) states.
  • Ordering xacts for the preferred or desired order
  • Limitations
    • Some example applications where the concept of xact may not even be present
      • a statistical application for taking averages over large amounts of data
      • process control programs that execute forever
    • Mutual exclusion
      • a goal for concurrency control in systems with nonterminating programs
      • requires critical section that accesses a shared resource to be executed by at most one program at a time so that attains serial executions (a strong from of serializability)
      • Techniques include locks, semaphores, and monitors
• Database system model
  • The abstract model
    • xact manager: perform an required preprocessing of database and xact operations it receives from xacts.
    • scheduler: control the relative order in which database and xact operations are executed.
    • data manager (DM)
      • recovery manager: responsible for xact commitment and abortion.
      • cache manager: operate directly on the database
  • Centralized computer systems: a system consists of a central processor, some main memory, secondary storage devices (usually disks), and I/O devices.
  • Distributed computer systems: a system with two or more processors that do not have direct access to shared main memory or secondary storage devices.
  • Cache Manager (CM)
    • Transfer data between volatile and stable storage
    • Operations: Fetch(x) and Flush(x)
  • Recovery Manager (RM)
    • Operations: Start, Commit, Abort, Read, and Write.
    • Process these operations by using CM's Fetch and Flush.
    • System failures
      • RM eliminates the effects of active xacts at the time of failure.
      • Problems for stable storage after a system failure
        • does not contain an update by some committed xact.
        • contains the value of x written by some uncommitted xact, but does not contain the last value of x that was written by a committed xact.
    • Media failures
      • Cope with by keeping redundant copies of data on at least two different stable storage devices that are unlikely to fail at the same time.
  • Schedulers
    • Goal
      • Order database operations so that the resulting execution is serializable and recoverable.
      • Ensure the execution avoids cascading aborts or is strict.
    • exercise the control of the concurrent execution of xacts by restricting the order in which the DM executes Reads, Writes, Commits, and Aborts of different xacts.
    • Actions upon receiving a database operation
      • Execute: pass the operation to the DM if doing so without producing a nonserializable execution
      • Reject: refuse to process the operation if never being able to correctly process the operation in the future, tell the xact that its operation has been rejected, and reject the xact.
      • Delay: delay the operation if may being able to correctly process in the future by placing it in a queue internal to the scheduler, and later process the operation by either executing or rejecting it.
    • Difficulties in designing the scheduler algorithms
      • The scheduler obtains the information only from the operations that xacts submit.
      • The scheduler can predict neither the operations that will be submitted in the future nor the relative order in which these operations will be submitted.
  • Xact Manager (TM)
    • receive database and xact operations issued by xacts and forward them to the scheduler.
    • In a distributed DBS, determine which site should process each operation submitted by a xact.
  • Ordering operations provided by the module that issues these operations
    • handshaking: pass an operation until the previous operation has been acked.
    • FIFO: have modules communicate through its FIFO queue, but not for intermodule communication.
      • Queues unnecessarily force a module to process operations stricly sequentially.
      • When two or more modules are involved in processing operations (e.g., in a distributed system), queues may not be powerful enough to enforce orders of operations, (but handshaking does).
  • Distributed DBS
  • Nested xacts
• Serializable theory

Relevance

Flaws