[Bernstein09] Section 4.4. Handling Non-Undoable Operations

4.4. Handling Non-Undoable Operations
Althoughthe analysis of the previous section appears to cover all the cases, itstill leaves one problem open if the system is in state C, namely howto handle the statement “process output” in Transaction 3 ifTransaction 3 aborts. There are three cases to consider, depending onwhether the process-output statement is undoable, is idempotent, or hasneither of these properties.
Ifthe process-output statement is an undoable operation, then there is noproblem. If Transaction 3 aborts, then process-output is undone, justlike any database operation. For example, this would be the behavior ifprocess-output involves only recording the execution of the request intransactional persistent storage.
Ifthe process-output statement is idempotent, then again there is noproblem. The operation does not need to be undone by an abort ofTransaction 3. When Transaction 3 re-executes, it re-executes theprocess-output statement, which is safe to do if the statement isidempotent. For example, this would be the case if process-outputinvolves printing a receipt that has a unique identification numberthat is linked to the request. There is no harm in executing it twice,since it would generate two identical receipts. It would be a bitconfusing to the recipient, but it might be acceptable since there isenough information to recognize the two receipts as duplicates of eachother.
Often,the process-output statement is neither undoable nor idempotent. Forexample, this typically arises when processing the output involvesasking a physical device to perform some action in the real world, suchas dispensing money. As we observed inChapter 1,it isn’t clear whether this operation should be done before or afterthe transaction commits. If the operation is done before thetransaction commits, but the transaction actually aborts, then theoperation can’t be undone, as it should be. And it is unsafe to run theoperation again when Transaction 3 re-executes, because the operationis not idempotent. On the other hand, if the operation is done afterthe transaction commits, but a failure happens after the transactioncommits and before the operation executes, then the operation is lost.
To solve this problem, the process-output statement must be operating on a device that has testable state.This means that it must be possible for Transaction 3 to read the stateof the physical device, and the physical device must change its stateas a result of performing the operation required by the process-outputstatement. That way, the transaction can record the device’s statebefore it performs the operation and can determine if the operation ranby comparing the device’s current state to the value it recorded. Forexample, the transaction might read the check number that is to beprinted next. After printing the check, the transaction would read adifferent number for the new check sitting under the print head. If itreads the same number for the check, then it knows the printingoperation did not execute.
Giventhat this device state is available, the transaction that processesreplies should follow the process-a-reply transaction shown inFigure 4.7.To see why this works, suppose the client is recovering from a failureand through the previous analysis determines that it is in state C. Itshould therefore process the reply by running the process-a-replytransaction. If this is its first attempt at processing the reply, thenthere is no earlier logged device state for this reply, so thetransaction performs the device operation and commits. Otherwise, instep (3) it determines whether it’s safe to rerun the device operationassociated with this reply. If the state of the device has changedsince the previous attempt to run the transaction, then the deviceoperation for this reply appears to have executed, so it is notsafe. At this point, the operator must get involved to determine whatreally happened. For example, did the check really get printed, or wasit destroyed by the device, which caused the previous execution of thereply-processing transaction to abort after logging the device’s statein step (4)? In the latter case, the operator has to tell the currentexecution of the process-a-reply transaction whether it’s safe toreprint the check.
Figure 4.7. Client Procedure for Reply Processing. Step(3) determines if the reply has already been processed. Step (4) logsthe device state, in case this transaction aborts and restarts, so itcan run step (3) the next time around.

A clever technique for logging the device’s state is to read the device state before dequeuing the reply (i.e., before step (2) inFigure 4.7) and to attach the device state to the log record for the dequeue operation. Since thequeue manager has to log the dequeue operation anyway (since it mighthave to undo it), it can log the device state at the same time andthereby do one write to the log, instead of two.
Thereis one case where step (3) is not needed—if the device’s operation isidempotent. For example, suppose the operation causes a robot arm tomove to a certain position, or suppose it sends a mail messagedescribing the transaction. In these cases, there may be no harm inexecuting the operation a second time. That is, the operation isidempotent. So there is no reason to log the state of the device andrecheck it in steps (3) and (4).
Sometime,an operation that is not normally idempotent can be made idempotent.This is important when it isn’t possible to read the current state ofthe device. For example, sending a mail message that says “you justbought 100 shares of IBM” is not idempotent. If you issued one requestto buy 100 shares and got back two acknowledgment messages like this,you would be worried whether your request executed once or twice.Moreover, at recovery time, there is no device state that the clientcan read to tell if the message was sent. However, if the mail messagesays, “your request, with confirmation number 12345, to buy 100 sharesof IBM, has executed,” there’s no harm in sending it twice. You wouldrecognize the second message as a duplicate and ignore it.