In today's post, we will see an interesting use for the logical time we discussed earlier. and we will discuss snapshots.
Snapshots are a capture of a global state of a system. The global state is the combination of all the local states of processes and the channels that connect them. We treated the channels earlier as message queues where processes send messages to each other. For our discussion, processes can do one of three things, they can change their internal state, they can send a message or they can receive a message. The snapshot is this global state capture without affecting the process computations. Looking back at the event sequence diagram and the directed graph we saw earlier with processes, this snapshot is a record of the state on each of the processes, this snapshot appears as a boundary across processes in a wave like manner with regard to the real time. If all the processes shared the same time from a shared clock, this snapshot would have been a straight line at that time. This is where the concept of logical time helps us. We can take a snapshot at the same logical time across processes.
But next we will discuss whether this guarantees correctness.
Take an example of two bank accounts where one has a balance of 1000 dollars and the other has no balance and one sends half the amount to the other. Now if a snapshot is taken where the banks record their state right after send at the sender and right after the receive at the receiver, the snapshot has a net worth of 1500 which is an inconsistent state. Hence a consistent cut is required where the cut is a valid snapshot, cut is consistent and cut has no incoming edges.
How do we make a consistent cut? Use logical time because an inconsistency occurs only because the message between two process is in flight and the source and destination have not had a chance to synchronize their logical time. The logical time is updated with the max between the local time and the max of the message received.
This is made possible by recording the snapshot at the same logical time as one solution.
Snapshots are a capture of a global state of a system. The global state is the combination of all the local states of processes and the channels that connect them. We treated the channels earlier as message queues where processes send messages to each other. For our discussion, processes can do one of three things, they can change their internal state, they can send a message or they can receive a message. The snapshot is this global state capture without affecting the process computations. Looking back at the event sequence diagram and the directed graph we saw earlier with processes, this snapshot is a record of the state on each of the processes, this snapshot appears as a boundary across processes in a wave like manner with regard to the real time. If all the processes shared the same time from a shared clock, this snapshot would have been a straight line at that time. This is where the concept of logical time helps us. We can take a snapshot at the same logical time across processes.
But next we will discuss whether this guarantees correctness.
Take an example of two bank accounts where one has a balance of 1000 dollars and the other has no balance and one sends half the amount to the other. Now if a snapshot is taken where the banks record their state right after send at the sender and right after the receive at the receiver, the snapshot has a net worth of 1500 which is an inconsistent state. Hence a consistent cut is required where the cut is a valid snapshot, cut is consistent and cut has no incoming edges.
How do we make a consistent cut? Use logical time because an inconsistency occurs only because the message between two process is in flight and the source and destination have not had a chance to synchronize their logical time. The logical time is updated with the max between the local time and the max of the message received.
This is made possible by recording the snapshot at the same logical time as one solution.
Another solution to the taking consistent snapshots is to send out markers through the channels to flush the messages.The initiator records its local state and sends out marker along each outgoing channel. Similarly a process receives a marker, records its local state, and records the incoming channel used by marker as empty and then sends markers along each outgoing channel. When a process receives a subsequent marker, it records the state of that incoming channel as completed. The process is complete when all the process have received markers along all incoming channels.
No comments:
Post a Comment