20
$\begingroup$

I have a database log where some transactions win (they are committed before crash) and some lose (not committed yet). We learned in class that the losers' actions have to be undone backwards.

Is there any reason for doing this backwards? Can anyone give a simple example of a log where forward undos would give wrong results?

Improve this question
$\endgroup$
0

6 Answers 6

Reset to default
36
$\begingroup$

Original transactions:

  1. Insert record $r$.
  2. Update some field $f$ of $r$.

Forward undo:

  1. Delete record $r$.
  2. Reverse the update to $r$ - oh wait, $r$ no longer exists! This causes an error.
Improve this answer
$\endgroup$
4
  • $\begingroup$ Do things need to be physically individually undone in reverse order if the system can figure out what state things need to be rolled back to and can apply all necessary changes before processing anything else? $\endgroup$
    – supercat
    Jul 12, 2016 at 19:42
  • 11
    $\begingroup$ Undoing changes in reverse order makes it easy. Why would you try to make it hard on yourself? $\endgroup$
    – gnasher729
    Jul 12, 2016 at 21:06
  • 1
    $\begingroup$ No, system will not do everything but still will figure that out in the backward order. $\endgroup$
    – Evil
    Jul 12, 2016 at 21:08
  • 3
    $\begingroup$ In many real world database systems doing it not in reverse order wouldn't even be possible due to key constraints on tables . $\endgroup$
    – SeanR
    Jul 13, 2016 at 13:27
12
$\begingroup$

To add to DylanSp's answer, trying to update a field in a non-existing record will fail, but the result will still be the expected result: record r does not exist.

However, consider a situation where deletion of a record actually will fail:

  1. Insert Order O.
  2. Insert Orderline L.

Let's assume, not unrealistically, that every OrderLine must be related to an Order.

Now rolling back the transaction starting with deleting the Order will fail because that would violate our business rule.

So after

  1. Delete Order O. (FAIL)
  2. Delete Ordeline L. (SUCCESS)

We may end up with an existing Order (without an Orderline).

Of course, in this case we could use a cascading delete, but that would mean step 2 would fail (without impact). Worse, it may be unwanted behaviour to implement cascading deletes on orders.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Okay this makes sense. Thx for your help $\endgroup$
    – prjctdth
    Jul 13, 2016 at 13:30
  • $\begingroup$ Is it proper to assume that constraints were not violated before or after the transaction in "normal" circumstances? By normal, I mean that the transaction would not have failed if only one person were using the database. If this is true, why would it be important to not introduce constraint violations during the undo process? It seems that constraints could be turned off at the beginning of the undo and enabled once the operation is complete. $\endgroup$
    – Noctis Skytower
    Jul 13, 2016 at 13:50
  • 2
    $\begingroup$ @NoctisSkytower Turning off constraints during a normal I/O operation renders them useless. They exist for a reason. My example clearly illustrates how constraints can be met under normal circumstances, yet violated during rollback. Turning off constraints during roll back is unnecessarily complicating matters, and fixing the wrong problem. The problem is not the constraint, the problem is the violation of it by incorrectly trying to roll back. $\endgroup$
    – oerkelens
    Jul 13, 2016 at 13:53
  • $\begingroup$ Yes, that makes sense, but why check constraints during rollback? Assuming rollbacks are designed to be guaranteed to complete without a problem, why unnecessarily waste time checking constraints if it is known they will not be violated by the time the rollback completes? BTW, that should be a guarantee because if a rollback failed, the DB would seemingly need to roll-forward which it cannot do. $\endgroup$
    – Noctis Skytower
    Jul 13, 2016 at 14:58
  • 1
    $\begingroup$ @NoctisSkytower it should be impossible for the DB to ever be in a state where the constraints are violated, even if it's a temporary state. If the whole rollback is atomic, then it doesn't matter what order it happens because there is no order, it's a single instruction that "happens all at once". if there are two or more transactions that are rolled back separately in some order, then it's mandatory that the order is such that any observer reading the data in the middle can only see a situation where all the constraints hold. $\endgroup$
    – Peteris
    Jul 13, 2016 at 20:29
7
$\begingroup$

Let's go by analogy: say you're going out for dinner.

  1. Put socks on.
  2. Put shoes on.
  3. Stand up.
  4. Walk to door.

Then you get a phone call. Dinner plans cancelled.

  1. Take socks off.
  2. Take shoes off.
  3. Sit down.
  4. Walk away from door.

Something goes wrong in there. You may trip and hurt yourself. Or more likely, you'll realize that some actions can't be undone until later actions are undone first.

Undoing the last thing you were doing gets you back to where you were when the next to last step occurred. Then you undo that step and repeat, moving back until nothing is left. On the other hand reversing the first step may not be possible given the states following the later steps.

mathematically speaking: the actions may not commute, so whenever it matters which step you do first or second, the order in which you undo steps will matter.

Improve this answer
$\endgroup$
4
$\begingroup$

This is right because transactions are built on top of each other and the outcome of a transaction is very much dependent on the situation before it was committed.

Let's look at financial transactions:

(at the beginning, before transactions a owes me 100 USD)

  1. a owes me 100 USD (now total debt 200)
  2. a receives 10% discount on what he owes me. (now total debt 180)

Let's say I want to cancel the two transactions.

If we cancel the first first, we will end up with:

  1. lower debt 100 (now have debt 80)
  2. cancel 10% discount (now have debt 80/0.9 = 88)

This is wrong, we need to get back to debt of 100. That will be right if we cancel the transactions in reverse order.

  1. cancel discount - now debt is 200
  2. lower 100 debt - now debt is 100
Improve this answer
$\endgroup$
2
$\begingroup$

Assume there is a table T with one column only.

Assume that the "undo log" is a database file containing uncommitted transactions, and that the "redo log" is a database file containing both uncommitted and committed transactions that have not been yet applied to the datafiles.

At 8:00 A.M., Transaction 100 inserts rows with values 101, 102 and 103 into table T. At 8:10 A.M., Transaction 100 is committed and the commit for transaction 100 completes. At 8:15 A.M., Transaction 200 updates row 101 to 201, 102 to 202 and 103 to 203. At 8:20 A.M., Transaction 200 has not been committed and remains in the undo log of the database. At 8:25 A.M., Transaction 300 increments each row by 50, changing row 201 to 251, 202 to 252, and 203 to 253. At 8:30 A.M., Transaction 300 has not been committed and remains in the undo log of the database. At 8:35 A.M., The instance providing access to the database crashes.

At 8:40 A.M., The instance is restarted, and the database files are opened as the instance is started:

              The committed values in T are still 101, 102 and 103.

              Since 201, 202, and 203, and 251, 252 and 253
              are not committed, if they are written into the "redo
              log" of the database, there is a need to "roll back"
              the transactions AFTER the "redo log" is applied.

              Since 201, 202, and 203, and 251, 252 and 253
              are not committed, they are in the "undo log"
              of the database.

              The undo log of the database is used BOTH to (1) roll
              back a transaction that is deliberately rolled 
              back in the memory structure of the database instance, 
              and also (2) during the instance recovery at 8:40 A.M.

At 8:41 A.M., The redo log has been applied, and the T table contains values 251, 252 and 253 in the instance memory.

              The undo log has not yet been applied.

At 8:42 A.M., The undo log is applied in the reverse order: Uncommitted transaction 300 is undone, and Uncommitted transaction 200 is undone.

Why are BOTH committed and uncommitted transactions written to the redo log file? The reason for this is to provide point-in-time recovery.

This means that the contents of the "redo log" file are NOT transaction-consistent. For this reason, whenever the redo log is used to apply committed transactions to the data files, the "undo log" MUST ALSO be used to roll back uncommitted transactions.

Why are the transactions in the "undo log" rolled back in the reverse order? The transaction 300 has added 50 to the existing value of each column of each row. Therefore, if transaction 200 is rolled back first, the values will change from 251, 252 and 253 to 201, 202 and 203. If transaction 300 were then rolled back last, the values would be 151, 152 and 153 - that do not match the original committed values.

REFERENCES:

https://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:1670195800346464273

Improve this answer
$\endgroup$
0
$\begingroup$

It's not inherently true. Rollback may simply re-apply the blocks that were cached in the undo log so that the final state is the same as the initial state. Because the log was written in forwards order I made my rollback also apply in forwards order. The order didn't matter whatsoever because rollback would retry until the log file was marked as settled.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.