Granularity of Locks and Degrees of Consistency in a Shared Data Base

Summary by: Steve Gribble and Armando Fox

One-line summary: Greater lock granularity gives you finer sharing and concurrency but higher overhead; four separate degrees of consistency which give increasingly greater protection from inconsistencies are presented, requiring increasingly greater lock granularity.

Relevance

Flaws

• No rigorous (or for that matter, unrigorous) treatment of the relative costs of these degrees of consistency or granularity of locks is presented. How much more do I pay for consistency of degree N+1 over degree N?
• Which data/applications need which consistencies? Do they need them all the time? Some sort of classification of typical data requirements into the consistency degrees would be useful (although to be fair this is done at a very high/abstract level).
• SIX/IX/IS mode, although correct, seem a little on the hackish side. I suppose it is just the influence of practicality and optimization blurring the crisp perfection of the formal work.

Overview/Main Points

• Hierarchical lockable units: assume set of resources to be locked is organized in a hierarchy, e.g. (database, areas, files, records) as a simple hierarchy. Each node of hierarchy can be locked, and in doing so, one implicity locks all of that node's descendants. There is shared access (S, shared-read access) and exclusive access (X, exclusive read/write access).
  • In order to lock a subtree rooted at node R in S or X, one must prevent others from obtaining incompatible locks on any ancestor of R. A new mode, "intention mode" is introduced to do this - all ancestors of a node are tagged with intention mode before the node itself is locked. Summary of modes:
    • null (NL): no access
    • intention-share (IS): allows requestor to lock descendant nodes in S or IS mode. (does no implicit locking)
    • intention-exclusive (IX): allows requestor to explicitly lock descendants in X, S, SIX, IX, or IS mode. (does no implicit locking)
    • share (S): access to node and all descendants without setting further locks. (implicitly sets S locks on all descendants)
    • share and intention exclusive (SIX): implicitly locks all descendants of node in share mode and allows requestor to explicitly lock descendant nodes in X, SIX, or IX mode. (for finer grained locking)
    • exclusive (X): exclusive access to node and all descendants. (implicitly sets X locks on all descendants)
  • To request a node,
    1. before requesting S or IS on node, all ancestor nodes must be held in IX or IS mode.
    2. before requesting X, SIX, or IX on node, all ancestors must be held in SIX or IX mode.
    3. locks should be released either at end of transaction (in any order), or in leaf to root order in the middle of a transaction.
• DAGs:
  • if don't have resource hierarchy but rather a DAG, can modify protocol:
    1. before requesting S or IX on a node, request at least one parent (and by induction a path to root) in IS or greater mode.
    2. before requesting IX, SIX, or X, request all parents of the node in IX or greater mode.
    3. locks should be release either at end of transaction in any order, or in leaf to root order. (breadth-first)
• Dynamic lock graphs:
  • if hierarchy/DAG is dynamically updated, need rule for changing parents of a node. Before moving a node in the lock graph, the node must be implicitly or explicitly granted X mode in both its old and its new position in the graph. Further, the node must not be moved in a way to introduce cycles.
• Consistency: database consists of entites which are structured in ways. Structure is assertions on data. Data base is consistent if it satisfies all assertions. Database needs to be temporarily inconsistent in order to transform to a new consistent state - need transactions to hide inconsistency.
  • transaction is committed when transaction abdicates the right to undo the write; its output is available to other transactions.
  • output is uncommitted or dirty if not yet committed. Crux of concurrency is preventing the reading or writing of other transactions' dirty data.
• Degrees of consistency: given the possible constraints on behaviour of transaction T:
  1. does not overwrite dirty data of other transactions
  2. does not commit any writes until it completes all its writes (i.e. end of transaction EOT).
  3. does not read dirty data from other transactions
  4. other transactions do not dirty any data read by T before T completes
  then:
  • Degree 3: T satisfies 1,2,3,4. Alternatively, T sets long exclusive lock on any data it dirties and long share lock on any data it reads.
  • Degree 2: T satisfies 1,2,3. Alternatively, T sets long exclusive lock on any data it dirties, and (possibly short) share lock on data it reads.
  • Degree 1: T satisfies 1,2. Alternatively, T sets long exclusive lock on any data it dirties.
  • Degree 0: T satisfies 1. Alternatively, T sets (possibly short) exclusive lock on any data it dirties.
• Properties:
  • Degree 0 transactions are unrecoverable (commit outputs before EOT). If all transactions see at least degree 0 consistency, any degree 1 transaction is recoverable. All transactions must be degree 1 for DB to be recoverable.
  • Degree 2 isolates transactions from uncommitted data of other transactions. Degree 1 may read uncommitted data which are subsequently updated or undone.
  • Degree 3 isolates transaction from dirty relationships among entities (!!). E.g., degree 2 may read two different committed values if it reads same entity twice. Degree 3 is true isolation (I in ACID).
• Dependencies among transactions: If T performs a then T' performs a',
  • T <<< T' if a is a write and a' is a write, or if a is a write and a' is a read, or if a is a read and a' is a write.
  • T << T' if a is a write and a' is a write, or if a is a write and a' is a read
  • T < T' if a is a write and a' is a write.
  Let <* be the transitive closure of < (and similar for other two). Then,

  Assertion: a schedule (set of transactions over time) is degree 1 (2, or 3) consistent if and only if the relation <* (<<* or <<<*) is a partial order. (Partial order: if T < T', then we cannot have T' < T)

• Backups and recovery: checkpoint and replay of at least degree 1 consistent transactions. Replaying degree 1 may give different results because degree 1 doesn't prevent reading of dirty data. Degree 2 guarantees same results every time.