Cursor stability is a consistency model which strengthens read committed by preventing lost updates. It introduces the concept of a cursor, which refers to a particular object being accessed by a transaction. Transactions may have multiple cursors. When a transaction reads an object using a cursor, that object cannot be modified by any other transaction until the cursor is released, or the transaction commits.
This prevents lost updates, where transaction T1 reads, modifies, and writes back an object x, but a different transaction T2 transaction also updates x after T1 read x—causing T2’s update to be effectively lost.
Cursor stability is a transactional model: operations (usually termed “transactions”) can involve several primitive sub-operations performed in order. It is also a multi-object property: operations can act on multiple objects in the system.
Cursor stability cannot be totally available; in the presence of network partitions, some or all nodes may be unable to make progress. For total availability, at the cost of allowing lost updates, consider read committed. For a stronger level, which ensures the stability of every record read, rather than cursors, consider repeatable read.
Note that cursor stability does not impose any real-time constraints. If process A completes write w, then process B begins a read r, r is not necessarily guaranteed to observe w. For a transactional model that provides real-time constraints, consider strict serializability.
Moreover, cursor stability does not require a per-process order between transactions. A process can observe a write, then fail to observe that same write in a subsequent transaction. In fact, a process can fail to observe its own prior writes, if those writes occurred in different transactions.
Adya’s formalization of transactional isolation levels defines cursor stability in terms of two prohibited phenomena:
- G1: See below.
- G-cursor(x): the directed serialization graph, restricted to a single object x, contains an anti-dependency cycle and at least one write-dependency edge.
G1 encompasses three disallowed phenomena:
- G1a (Aborted Reads): A transaction observes an object (perhaps via a predicate) modified by an aborted transaction. Intuitively, transactions have to commit for us to read them.
- G1b (Intermediate Reads): A transaction observes an object (perhaps via a predicate) modified by a transaction which was not that transaction’s final modification of that object. Intuitively, transactions have to finish before we can read them,
- G1c (Circular Information Flow): the Directed Serialization Graph of transactions contains a directed cylce consisting entirely of dependency edges. Intuitively, if transaction T1 is affected by T2, T2 can’t be affected by T1.
Since cursor stability is strictly stronger than read committed, it also prohibits the ANSI phenomena:
- P0 (Dirty Write): w1(x) … w2(x)
- P1 (Dirty Read): w1(x) … r2(x)
- P2 (Fuzzy Read): r1(x) … w2(x)
- P3 (Phantom): r1(P) … w2(y in P)
In this notation, w denotes a write, r denotes a read, and subscripts indicate the transaction which executed that operation. … indicates a series of micro-operations except for a commit or abort. P indicates a predicate. Fuzzy reads are possible where cursors are not used.