8trans.html

C ++ in action

<P>Well, there's the rub! It doesn't! In order to understand that, we have to delve a little into the internals of a file system. First of all, writing into a file doesn't mean writing to disk. Or, at least, not immediately. In general, file writes are buffered and then cached in memory before they are physically written to disk. All this is quietly done by the runtime (the buffering) and by the operating system (the caching) in order to get reasonable performance out of your machine. Disk writes are so incredibly slow in comparison with memory writes that caching is a must. 
<P>What's even more important: the order of physical disk writes is not guaranteed to follow the order of logical file writes. In fact the file system goes out of its way to combine writes based on their physical proximity on disk, so that the magnetic head doesn't have to move too much. And the physical layout of a file might have nothing to do with its contiguous logical shape. Not to mention writes to different files that can be quite arbitrarily reordered by the system, no matter what your program thinks. 
<P>Thirdly, contiguous writes to a single file may be split into several physical writes depending on the disk layout set up by your file system. You might be writing a single 32-bit number but, if it happens to straddle sector boundaries, one part of it might be written to disk in one write and the other might wait for another sweep of the cache. Of course, if the system goes down between these two writes, your data will end up partially written. So much for atomic writes.
<P>Now that I have convinced you that transactions are impossible, let me explain a few tricks of trade that make them possible after all. First of all, there is a file system call, <var>Flush</var>, that makes 100% sure that the file data is written to the disk. Not atomically, mind you--Flush may fail in the middle of writing a 32--bit number. But once Flush succeeds, we are guaranteed that the data is safely stored on disk. Obviously, we have to flush the new data to disk before we go about committing a transaction. Otherwise we might wake up after a system crash with a committed transaction but incomplete data structure. And, of course, another flush must finish the committing a transaction.
<P>How about atomicity? How can we atomically flip the switch? Some databases go so far as to install their own file systems that support atomic writes. We won't go that far. We will assume that if a file is small enough, the writes are indeed atomic. "Small enough" means not larger than a sector. To be on the safe side, make it less than 256 bytes. Will this work on every file system? Of course, not! There are some file systems that are not even recoverable. All I can say is that this method will work on NTFS--the Windows NT(tm) file system. You can quote me on this. 
<P>We are now ready to talk about the simplest implementation of the persistent transaction--the three file scheme. 

<h4>The Three-File Scheme</h4>

<P>An idealized word processor reads an input file, lets the user edit it and then saves the result. It's the save operation that we are interested in. If we start overwriting the source file, we're asking for trouble. Any kind of failure and we end up with a partially updated (read: corrupted!) file. 
<P>So here's another scheme: Write the complete updated version of the document into a separate file. When you are done writing, flush it to make sure the data gets to disk. Then commit the transaction and clean up the original file. To keep permanent record of the state of the transaction we'll need one more small file. The transaction is committed by making one atomic write into that file. 
<P>So here is the three-file scheme: We start with file A containing the original data, file B with no data and a small 1-byte file S (for Switch) initializedcontaintain a zero. The transaction begins.
<ul>
<li>Write the new version of the document into file B.
<li>Flush file B to make sure that the data gets to disk.
<li>Commit: Write 1 into file S and flush it.
<li>Empty file A.
</ul>
<P>The meaning of the number stored in file S is the following: If its value is zero, file A contains valid data. If it's one, file B contains valid data. When the program starts up, it checks the value stored in S, loads the data from the appropriate file and empties the other file. That's it!
<P>Let's now analyze what happens if there is a system crash at any point in our scheme. If it happens before the new value in file S gets to the disk, the program will come up and read zero from S. It will assume that the correct version of the data is still in file A and it will empty file B. We are back to the pre-transaction state. The emptying of B is our <i>rollback</i>. 
<P>Once the value 1 in S gets to the disk, the transaction is committed. A system crash after that will result in the program coming back, reading the value 1 from S and assuming that the correct data is in file B. It will empty file A, thus completing the transaction. Notice that data in file B is guaranteed to be complete at that point: Since the value in S is one, file B must have been flushed successfully. 
<P>If we want to start another <i>save</i> transaction after that, we can simply interchange the roles of files A and B and commit by changing the value in S from one to zero. To make the scheme even more robust, we can choose some random (but fixed) byte values for our switch, instead of zero and one. In this way we'll be more likely to discover on-disk data corruption--something that might always happen as long as disks are not 100% reliable and other applications can access our files and corrupt them. Redundancy provides the first line of defense against data corruption.
<P>This is how one might implement a <i>save</i> transaction.
<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>class SaveTrans
{
    enum State
    {
        // some arbitrary bit patterns
        stDataInA = 0xC6,
        stDataInB = 0x3A
    };
public:
    SaveTrans ()
        : _switch ("Switch"), _commit (false)
    {
        _state = _switch.ReadByte ();
        if (_state != stDataInA &amp;&amp; state != stDataInB)
            throw "Switch file corrupted";
        if (_state == stDataInA)
        {
            _data.Open ("A");
            _backup.Open ("B");
        }
        else
        {
            _data.Open ("B");
            _backup.Open ("A");
        }
    }
    File &amp; GetDataFile () { return _data; }
    File &amp; GetBackupFile () { return _backup; }
    ~SaveTrans ()
    {
        if (_commit)
            _data.Empty ();
        else
            _backup.Empty ();
    }
    void Commit ()
    {
        State otherState;
        if (_state == stDataInA)
            otherState = stDataInB;
        else
            otherState = stDataInA;

        _backup.Flush ();
        _switch.Rewind ();
        _switch.WriteByte (otherState);
        _switch.Flush ();
        _commit = true;
    }
private:
    bool    _commit;
    File    _switch;
    File    _data;
    File    _backup;
    State   _state;
};</pre>
</td></tr></table><!-- End Code -->


<P>This is how this transaction might be used in the process of saving a document.
<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>void Document::Save ()
{
    SaveTrans xact;
    File &amp;file = xact.GetBackupFile ();
    WriteData (file);
    xact.Commit ();
}</pre>
</td></tr></table><!-- End Code -->


<P>And this is how it can be used in the program initialization.
<!-- Code --><table width="100%" cellspacing=10><tr>	<td class=codetable>
<pre>Document::Document ()
{
    SaveTrans xact;
    File &amp;file = xact.GetDataFile ();
    ReadData (file);
    // Don't commit!
    // the destructor will do the cleanup
}</pre>
</td></tr></table><!-- End Code -->


<P>The same transaction is used here for cleanup. Since we are not calling <var>Commit</var>, the transaction cleans up, which is exactly what we need.

<h4>The Mapping-File Scheme</h4>

<P>You might be a little concerned about the performance characteristics of the three-file scheme. After all, the document might be a few megabytes long and writing it (and flushing!) to disk every time you do a save creates a serious overhead. So, if you want to be a notch better than most word processors, consider a more efficient scheme.
<P>The fact is that most of the time the changes you make to a document between saves are localized in just a few places . Wouldn't it be more efficient to update only those places in the file instead of rewriting the whole document? Suppose we divide the document into "chunks" that fit each into a single "page." By "page" I mean a power-of-two fixed size subdivision. When updating a given chunk we could simply swap a page or two. It's just like swapping a few tiles in a bathroom floor--you don't need to re-tile the whole floor when you just want to make a small change around the sink. 
<P>Strictly speaking we don't even need fixed size power-of-two pages, it just makes the flushes more efficient and the bookkeeping easier. All pages may be kept in a single file, but we need a separate "map" that establishes the order in which they appear in the document. Now, if only the "map" could fit into a small switch file, we would perform transactions by updating the map.
<P>Suppose, for example, that we want to update page two out of a ten-page file. First we try to find a free page in the file (we'll see in a moment how transactions produce free pages). If a free page cannot be found, we just extend the file by adding the eleventh page. Then we write the new updated data into this free page. We now have the current version of a part of the document in page two and the new version of the same part in page eleven (or whatever free page we used). Now we atomically overwrite the map, making page two free and page eleven take its place. 
<P>What if the map doesn't fit into a small file? No problem! We can always do the three-file trick with the map file. We can prepare a new version of the map file, flush it and commit by updating the switch file.



<p><img src="images/Image56.gif" width=360 height=138 border=0 alt="Map before commit">
<P>Figure: The Mapping File Scheme: Before committing.

<p><img src="images/Image57.gif" width=360 height=138 border=0 alt="Map after commit">
<P>Figure: The Mapping File Scheme: After committing.

<p>This scheme can be extended to a multi-level tree. In fact several databases and even file systems use something similar, based on a data structure called a B-tree.

    </td>
    </tr>
</table>
<!-- End Main Table -->
</body>
</html>