Advanced Topics in Computer Systems  
Joe Hellerstein & Timothy Roscoe

Multi-Granularity Locking

Some implementation background (not in reading):
No! (starvation, unfair, etc.) So...

Gray, et al.: Granularity of Locks

Theme: Correctness and performance

Notes on Deadlock

Typically, in centralized systems, run deadlock detection whenever blocking occurs.   Arguably this is cheap: most recently blocked transaction T must be the one that caused the deadlock, so just DFS starting from T.
In distributed systems, even this can be expensive, so often do periodic detection (more later)

Degrees of Consistency (a/k/a Isolation Levels)

Despite all the discussion of ACID, sometimes it's nice to relax semantic guarantees for the sake of performance.  The goal is to let individual transactions choose sensible ways of doing this without messing up the database or the other transactions that do care. I.e. preserve everybody's desired isolation.

Gray, et al.: Degrees of Consistency

First, a definition: A write is committed when transaction if finished; otherwise, the write is dirty.

A Locking-Based Description of Degrees of Consistency:

This is not actually a description of the degrees, but rather of how to achieve them via locking. But it’s (operationally) well-defined.

A Dirty-Data Description of Degrees of Consistency

Transaction T "sees degree X consistency" if...

Examples of Inconsistencies prevented by Various Degrees

A note: ANSI-SQL standard talks about the phenomena of Dirty Read, Non-Repeatable Read, and Phantoms.
To reiterate: if everybody sees at least Degree 1, than different transactions can choose what degree they wish to "see" without worry.  I.e. can have a mixture of levels of consistency.

Two more consistency levels used in practice

Adya, et al. : Generalized Isolation Levels

Gray et al's definitions (and the resulting ANSI standards) are not implementation-independent, and semantics are really only well-defined in the operational locking definition. Note the "dirty-data" descriptions above forbidding conflicts entirely, rather than describing bad interactions of conflicts. Seems too restrictive, no?

Goal: find implementation-independent semantic isolation levels which are as permissive as possible (most possible schedules allowed).

Key insight: many dependencies are multi-object.  Capture those, and you'll get the right semantics. To be as permissive as we can, we talk about versions of objects coexisting (don't count on the Haerder/Reuter DIRECT setting.)

Conflicts in Adya's Serialization Graphs:

Direct Serialization Graph: Now we can talk about isolation in terms of serialization graphs and "histories" ("schedules"), NOT implementation.

Adya's Isolation Levels
Try to Generalize Gray's.  PL-x = "Portable Level x".

Modeling Mixed-Mode Systems