Chapter 17 (Elmasri & Navathe): Transaction Processing
Assume transactions are correct: we aren’t worrying in this class about bad programming.
Remember that CPUs sit idle during I/O (secondary process, not central process). We are greedy: we want to use those extra CPU cycles. We thus interleave transactions, letting T2 get some CPU time while T1 dinks around elsewhere. So remember: we caused the problems we are trying to solve. :-)
Classic transaction concurrency problems:
- Lost Update: T2 writes over results of T1
- Temporary Update (a.k.a. Dirty Read): T1 reads X, modifies i; T2 reads X; T1 has error and aborts. T2 operates on dirty data, a value that shouldn’t have existed and got undone by T1’s abort
- Incorrect Summary (accountants hate this): I seek aggregate data, down a column/field, for each record. I count 100,000 records. I get to record 50,000, but while I’m still counting, someone updates record #1-100. Or while I’m counting #1-100, someone changes #50,000-51,000. My data is meaningless, unpinnable in time (well, no moer problematic than the U.S. Census
- Unrepeatable Read: T1 reads X, gets value, continues, then reads X again, gets different value due to operation of T2. Note that having to read X again probably happens because of memory constraints: you read it, then had to dump buffer, have to go back and get data.
Remember, you don’t get to control interleaving order. The system fits concurrent transactions wherever it can.
Corruption of data due to concurrency is huge problem. When your business relies on data (everybody’s business relies on data), you can’t let this corruption happen! If your database has bad data, it will cause mistakes. And if your users see they’re getting bad data, they will stop using the database. Then you have two problems! If you give your people a data tool that they have to double-check, you’ve given them crap. You and your database are the double-check!
Transaction states:
- begin
- active
- partially committed
- committed
- terminate
Note that a transaction can abort to the fail state at the active and partially committed state. We create a system log on non-volatile memory (i.e., pull the plug, that info persists) to recover database after transactions fail. System log records transaction starts, reads, writes, commits, and aborts.
Commit point: all operations executed successfully and effect of all operations recorded in system log.
Remember: transactions usually write to buffer, rarely to disk. When transaction commits, its effects may still be only in buffer, not on disk! System may crash before we write the buffer to disk. That’s why the log matters! The log records that info so we can REDO after a crash and fix things with the least possible re-input of data from users.
ACID Properties of Transactions
- Atomicity: all or nothing — a transaction happens completely or not at all. If it aborts, you better have a routine that undoes what it managed to do before abort.
- Consistency Preservation: transaction takes database from one consistent state to another. (Business rules, program logic… programmers and end users handle this!)
- Isolation: transaction acts as if it is the only thing happening, independent of other transactions.
- Durability: if transaction commits, it should stick, surviving any failure.
The system (i.e., what we design) has to handle #1, 2, and 4.
Four levels of isolation:
- Level 0: doesn’t allow dirty reads
- Level 1: no lost updates
- Level 2: no dirty reads, no lost updates (level 0 + level 1)
- Level 3: no dirty reads, no lost updates, no unrepeatable reads (0 + 1 + 2)
Conflicting operations must (1) be in different transactions, (2) access the same data item, and (3) involve at least one write.
Levels of Recoverability (exam: be able to identify schedules by these levels!):
- Recoverable: If T2 reads from data written by T1, T1 must commit before T2 commits. If T1 is committed, it never gets rolled back. But note that if T1 aborts, T2 must abort… cascading rollback! Lots of work!
- Avoid Cascading Rollback: T2 only reads from T1 if T1 has committed. Only read from committed transactions!
- Strict: T2 cannot read or write X until the last transaction that read X has committed or aborted.
Strict is easiest: all you have to do to recover is UNDO. Your log records old value and new value for each write. you then work backward through the log and replace new value with old value.
Transactions done in serial schedule (no interleaving) are by definition correct.
Serializability: equivalence to a serial schedule of the same transactions. We never serialize schedules; we need to know, though, that we could if we (and our CPU) had all the time in the world. Equivalent means more than just result equivalent (p. 628), since you can get the same results from two different schedules given particular data. View equivalence is stronger, says every read operation reads the same value across schedules. We use conflict equivalence, which says conflicting operations happen in the same order.
Remember: there’s overhead for serializability. It takes away interleaving options and slows us down. But it also keeps our data clean. Doing things right takes time!
Chapter 18: Concurrency Control Techniques
Chapter 17 gives the mathematical basis. Chapter 18 tells us how to get stuff done. (Mathematicians can prove the transition.)
Read locks are sharable; write locks are exclusive.
2 Phase Locking:
- Basic 2PL: growing phase (more locks), the shrinking phase (fewer locks). Once you give up a lock, you can’t ask for any more (it’s all downhill from here). Enforce this rule, and your schedule is serializable and strict recoverable. Unfortunately, gradual growing phases allow deadlocks: T1 locks Y, T2 locks X, T1 asks for X, T2 asks for Y — neither can proceed.
- Conservative 2PL: growing phase vertical — grab all locks at once! shrinking phase gradual. No deadlocks, but starvation possible: you have to grab all locks at once, and there’s much more chance that at least one of those locks is already taken.
- Strict 2PL: gradual growing phase, then gradual shrinking phase for read locks but vertical shrinking phase for write locks (drop all write locks at end). Deadlocks back, but strict recoverable, better than basic.
- Rigorous 2PL: gradual growing phase, then drop all locks at end: guarantees strict recoverable.
Timestamp ordering: bigger numbers mean younger (20100127 > 20091225). Timestamp ordering gets rid of locks.
Chapter 19: Database Recovery Techniques
When you write to the log, it records the old value and the new value. This allows idempotent UNDO: you can do it over and over and getting the same result as if you had done it just once. If the log recorded an operation (“add 5, multiply by 104%”) instead of the old value, your UNDO process could really goof things up! Record the effect, not the cause.
Checkpoint: suspend operations, flush buffers, add checkpoint. This gives us a chance to guarantee that a certain string of data really has been written to the hard drive. When the system crashes, we need recover and UNDO/REDO only as far back as the checkpoint. We need not REDO any transaction that committed pre-checkpoint, because we know its commit made it to the disk. A transaction that committed post-checkpoint definitely wrote to the buffer, but it may or may not have reached the disk, so we should REDO. A transaction that starts and writes some data before the checkpoint does indeed hit the disk! The transaction may continue and hit commit after the checkpoint, but the chekpoint flushes the buffer, including writes from partially complete transactions, so we should only need to REDO the writes between the checkpoint and the commit.
Immediate Update: each operation writes straight to the buffer. This makes more UNDO!
Deferred Update: we collect writes, really write them all at once at the end of the transaction. This is nice for recovery: if a crash hits before a transaction commits, that transaction hasn’t had a chance to change the database. No UNDO or REDO necessary.
Deferred Update with Forced Write: Commit doesn’t happen until we write to disk. Do this, and you UNDO/REDO no committed transactions.
Always record your write of X to disk before you write to disk! Otherwise, you might lose your history of what you did! Checkpoints work backwards: flush buffer, then record checkpoint upon success. If system crashes between flush and checkpoint, you just go back to the previous checkpoint.
Note: MySQL doesn’t have concurrency control. Not everyone needs concurrency control.
CAH@DSU 