Distributed Systems - Chapter 3: Clock and Time - Thoai Nam

Nội dung text: Distributed Systems - Chapter 3: Clock and Time - Thoai Nam

1. Clock and Time THOAI NAM Faculty of Information Technology HCMC University of Technology Using some slides of Prashant Shenoy, UMass Computer Science
2. Clock Synchronization  Time in unambiguous in centralized systems – System clock keeps time, all entities use this for time  Distributed systems: each node has own system clock – Crystal-based clocks are less accurate (1 part in million) – Problem: An event that occurred after another may be assigned an earlier time Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
3. Clock Synchronization  Each clock has a maximum drift rate r » 1-r resynchronize every d/2r seconds Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
4. Berkeley Algorithm  Used in systems without UTC receiver – Keep clocks synchronized with one another – One computer is master, other are slaves – Master periodically polls slaves for their times » Average times and return differences to slaves » Communication delays compensated as in Cristian’s algorithm – Failure of master => election of a new master Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
5. Distributed Approaches  Both approaches studied thus far are centralized  Decentralized algorithms: use resynchronization intervals – Broadcast time at the start of the interval – Collect all other broadcast that arrive in a period S – Use average value of all reported times – Can throw away few highest and lowest values  Approaches in use today – rdate: synchronizes a machine with a specified machine – Network Time Protocol (NTP) » Uses advanced techniques for accuracies of 1-50 ms Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
6. Event Ordering  Problem: define a total ordering of all events that occur in a system  Events in a single processor machine are totally ordered  In a distributed system: – No global clock, local clocks may be unsynchronized – Can not order events on different machines using local times  Key idea [Lamport ] – Processes exchange messages – Message must be sent before received – Send/receive used to order events (and synchronize clocks) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
7. Event Ordering Using HB  Goal: define the notion of time of an event such that – If A-> B then C(A) C(B)  Solution: – Each processor maintains a logical clock LCi – Whenever an event occurs locally at I, LCi = LCi+1 – When i sends message to j, piggyback LCi – When j receives message from i » If LCj < LCi then LCj = LCi +1 else do nothing – Claim: this algorithm meets the above goals Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
8. More Canonical Problems  Causality – Vector timestamps  Global state and termination detection  Election algorithms Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
9. Vector Clocks  Each process i maintains a vector Vi – Vi[i] : number of events that have occurred at process i – Vi[j] : number of events occurred at process j that process i knows  Update vector clocks as follows – Local event: increment Vi[i] – Send a message: piggyback entire vector V – Receipt of a message: » Vj[i] = Vj[i]+1 » Receiver is told about how many events the sender knows occurred at another process k Vj[k] = max( Vj[k],Vi[k] )  Homework: convince yourself that if V(A)<V(B), then A causally precedes B Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
10. Consistent/Inconsistent Cuts a) A consistent cut b) An inconsistent cut Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
11. Distributed Snapshot  A process finishes when – It receives a marker on each incoming channel and processes them all – State: local state plus state of all channels – Send state to initiator  Any process can initiate snapshot – Multiple snapshots may be in progress » Each is separate, and each is distinguished by tagging the marker with the initiator ID (and sequence number) M B A M C Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
12. Snapshot Algorithm Example (2) (b) Process Q receives a marker for the first time and records its local state (c) Q records all incoming message (d) Q receives a marker for its incoming channel and finishes recording the state of the incoming channel Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
13. Independent Checkpointing  Each processes periodically checkpoints independently of other processes  Upon a failure, work backwards to locate a consistent cut  Problem: if most recent checkpoints form inconsistenct cut, will need to keep rolling back until a consistent cut is found  Cascading rollbacks can lead to a domino effect. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
14. Message Logging  Checkpointing is expensive – All processes restart from previous consistent cut – Taking a snapshot is expensive – Infrequent snapshots => all computations after previous snapshot will need to be redone [wasteful]  Combine checkpointing (expensive) with message logging (cheap) – Take infrequent checkpoints – Log all messages between checkpoints to local stable storage – To recover: simply replay messages from previous checkpoint » Avoids recomputations from previous checkpoint Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM