PREVIOUS

Journalizing Facilities

There are some applications where the checkpoint-restart facility is not adequate. A transaction-oriented system will want to accept a transaction to update a data base and at some point give the user a positive acknowledgment that the transaction will be remembered. The application cannot normally afford to wait until the next system-wide checkpoint to give the acknowledgment.

The following argument shows that, in such a system, transactions that change the data base (Write transactions) must be idempotent. That is, it never hurts to do them twice.

Suppose a user submits a write transaction and KeyKOS crashes before it is acknowledged. The user knows KeyKOS has crashed because the connection with the application must be re-established. It is unknown whether KeyKOS has committed to remember the transaction. KeyKOS may have crashed just before the acknowledgment was sent to the user but after the transaction was committed. Therefore, the transaction must be resubmitted when KeyKOS restarts. In case the transaction has committed, it must be idempotent.

Transactions that are not idempotent can usually be made so by simple expedients. For example, "transfer $100 from account A to account B" is not idempotent. But "transfer $100 from account A to account B and associate a unique transaction number, N, with this transaction, unless the number N has been used before" is.

See also:

Transaction applications will have to store a record of recent transactions in some non-volatile storage. That record is called a journal and the procedure is called journalizing.

It is significant that only data, not keys, are stored.

To support journalizing, a special journal page that only the kernel can write is provided. At restart, these values are set before any processes run.

Figure 2-27

Here is an example of journalizing, written in Algol68.

SEMA mutex = LEVEL 1;
INT local restart count := 0;
REF INT restart count = locations 16 to 23 in journal page;
FLEX [0:] transaction nonvolatile storage;
INT next serial number;
PROC process transaction (TRANSACTION transaction) = ACKNOWLEGEMENT: 
BEGIN
     DOWN mutex; # only one process at a time here #
     WHILE local restart count < restart count
     DO # replay transactions since the restart #
             local restart count := restart count;
             WHILE UPB(nonvolatile storage) >= next serial number
             DO update database(nonvolatile storage[next serial number]);
                  next serial number +:= 1
            0D
     OD
     IF modifies database(transaction)
     THEN nonvolatile storage[next serial number] := transaction;
          # the above unit may overwrite an entry in nonvolatile        
                  storage with identical data #
             update database(transaction);
             next serial number +:= 1
     FI;
     ACKNOWLEDGEMENT a = read from database(transaction);
     UP mutex;
     a
END

# Program notes:

Both read and write transactions must go through this procedure. An ACKNOWLEDGEMENT includes any data read. The acknowledgment returned will be sent to the user through the network: if the network circuit connection is broken, the acknowledgment should be discarded (it may be incorrect). #

NEXT