- Backward recovery: Take a system from a current erroneous state to a previous correct state. In this scenario a checkpointing (record sys state from time to time) mechanism is needed.
- Fwd recovery: When the sys finds an erroneous state, an attempt is made to take the sys to a correct new state. Woo! This one is a hard one to implement. This needs the system to know what errors can occur in advance.
For example. In case of a lost packet in a communication process, bwd recovery would be to retransmit the packet, thus returning to the previous correct state. On the other hand, erasure coding would be the fwd recovery approach. (We, Lalith and me) worked in an erasure coding toy application as part of our “Implementation of Distributed Systems || Advanced Topics in Distributed Systems” in KTH, Sweden. Code is here)
No hay problema? Yeah, right.
- It is costly in terms of perfomance for a Dist. System to return to a previous state.
- As recovery mechanisms are independent of the systems, it is hard to guarantee that the error/s will not happen again.
- Some states cannot be rolled back. Imagine an error leading to a 1000EUR transfer off an account.
To balance some of these problems, some systems combine checkpointing with message logging, since this allows the system to completely recover from process crashes plus, it allows the checkpointing frequency to be lower. Two approaches can be taken regarding message logging:
- sender-based logging: after a checkpoint has been taken, a process logs its messages before sending them off.
- receiver-based logging: the receiving process first logs an incoming message before delivering to the app it’s executing.
A artistic ASCII art representation of the benefit of checkpointing + msg loggin is shown below:
0 : checkpointed state
| : logged messages
X : process crash.
It is easy to observe that when the system crashes, it can be restored, not only to the checkpointed state, but also to replay the logged messages and actions to recover almost completely.
A survey (of 44 pages!) is available if interested in exploring this topic.
To handle checkpointing there are two main techniques:
- Independent checkpointing: each process/ node handles their own independent checkpointing mechanism. This has the problem of handling inconsistent states when failures occur, since P1 may have checkpointed a state which is not consistent with the one saved by P2 and so on.
- Coordinated Checkpointing: All proces synchronize jointly and write their state to local stable storage. This gives a globally consistent state, where no cascaded rollback can happen (domino effect) at the cost of handling coordination in a distributed system, which gets its own chapter in the book.