Logging idea
Date: Fri, 15 Feb 2002 12:43:55 -0800
Message-ID: <u6qsobkf8a2620_at_news.supernews.com>
This is an idea that I thought of a while ago, and I'm wondering if anyone has done this before. I've checked a few DB textbooks and found no mention.
Most DB systems use a Before-Image Journal (BIJ) and an After-Image Journal (AIJ) to support rollback and roll-forward recovery (respectively). The format of each log is more or less a copy of the data that was updated, containing a row id and column, and the previous or new value, depending on the log. Recovery uses the AIJ to roll forward an old version of the data by applying the after-images to each row that was updated, and rollback uses the BIJ to overlay the original image on each row that was updated during the transaction.
My idea is to combine the after and before image by XOR'ing them, so that the log entry will simply contain the bits that flipped during the update. The fun property of XOR, of course, is that the log entry can be XOR'ed with the before image to get the after image, and vice-versa. So, rollbacks and roll-forwards can be accomplished from the same log.
Example:
If a row R is updated to R', the log will record L = (R ^ R').
Given R and needing R', we simply calculate
R' = R ^ L = R ^ (R ^ R') = (R ^ R) ^ R' = 0 ^ R'
Likewise given R' and rolling back to R, we calculate
R = R' ^ L = ... = 0 ^ R
The main problem I can see with this is idempotency (or rather, nilpotency). Rolling forward twice (due to recovery crashes, etc.) will return things to the pre-image, not the after-image. However with reasonable extensions to avoid duplicate operations the scheme might work.
Is this scheme used anywhere? Would it work? Received on Fri Feb 15 2002 - 21:43:55 CET