CSE 124 Lecture Notes - Lecture 19: Leader Election, Uptodate
17 May 2018
School
Department
Course
Professor
Recall: Primary-Backup
Mechanism: Replicate and separate servers
State Machine Replication
- ANY server is essentially a “state machine”
- operations “transition” between states
- Nee an op to be executed on ALL replicas or NONE
- we need distributed all-or-nothing atomicity
Extend PB for High Availability
“Okay” (i.e. op is stable) if written to > ½ backups
Outline
1. Consensus protocol to “elect” leader
2. 2PC to replicate ops from leader
3. ALL replicas execute ops once committed
Why Bother with a Leader?
- NOT necessary, but allows us to “make some assumptions” that make replicating easier
- “orchestrates” transactions across nodes
- divides states into normal ops that a leader can coordinate
- failed state: leader fails → elect a new leader
- NOT good for “peer-to-peer” - nodes come and go and may fail sooner
Goal: Replicated Log
- replicated log → replicated state machine
1. Leader logs operation - but state is NOT updated
2. Consensus module sends updated log to all the other nodes
3. Nodes commit the change
- If majority of nodes can APPLY the change to their state, reply to primary indicating
success
4. Primary can THEN apply the change to its state
- State is made visible to the client
Commit phase:
- All backups apply the modifications
General Solution
1. Leader election
2. Normal operation (basic log replication)
3. Safety and consistency AFTER leader fails
4. Neutralizing old leaders
5. Client interactions
6. “Reconfiguration”
Document Summary
Any server is essentially a state machine . Nee an op to be executed on all replicas or none. Okay (i. e. op is stable ) if written to > backups. Outline: consensus protocol to elect leader, 2pc to replicate ops from leader, all replicas execute ops once committed. Not necessary, but allows us to make some assumptions that make replicating easier. Divides states into normal ops that a leader can coordinate. Failed state: leader fails elect a new leader. Not good for peer-to-peer - nodes come and go and may fail sooner. Replicated log replicated state machine: leader logs operation - but state is not updated, consensus module sends updated log to all the other nodes, nodes commit the change. If majority of nodes can apply the change to their state, reply to primary indicating success: primary can then apply the change to its state. State is made visible to the client.
