代写代考 CS 505 Spring 2021

Paxos CS 505 Spring 2021

Leader Election
● Allows the system to skip phase 1 (prepare) when there is a stable leader

● 2 possible designs (maybe more?)
○ Proposers immediately start first phase of Paxos when they are “preempted”
(Design outlined in PMMC, but we don’t recommend doing this)
■ Can be inefficient – no bound on the number of preemptions that can occur
■ Case when proposers compete with each other with higher proposal number
○ Alternative: assume that the preempting node (higher proposal number) is the new “leader”. Wait for that node to drive the Paxos instance to a chosen value (or timeout).
■ Still need to handle multiple simultaneous requests! ○ Alternative 2: read the lab3 spec

Lab 3 Tips
● We recommend using PMMC as a starting place, but…
○ Don’t code up PMMC exactly (lab3 spec provides guidance)
○ Try to figure out what each part/role does and why it’s there
● Every PaxosServer will be playing acceptor and learner roles
○ If a server believes itself to be leader (or is trying to become leader), it will also play the proposer
○ With regards to PMMC and implementing something similar, try to avoid making inner classes for
roles like Scout or Commander, since that may blow up the state space
● Read the lab3 spec about “sending” a message from a server to itself
● If you receive a message with a higher ballot number than yours, stop being
leader (or stop trying to become leader)
○ Not required for correctness, but makes it easier to implement

General Tips/What previous students said
● Start early (applies to life too!)
● According to a majority of students in previous offerings/quarters @ UW:
Paxos is non-trivial
● Students from UW also say to expect this to take more time than you think it
would and that they wish they started earlier and that we emphasized to them
that they should start earlier, hence this slide
● Please start

Other Resources
● This Google tech talk: https://youtu.be/d7nAGI_NZPk
● Stanford lecture: https://youtu.be/JEpsBg0AO6o
● PMMC in a website: http://paxos.systems/

Problem: Contention
● If many proposers are sending values for the same slot at the same time, problems can occur
○ Acceptors may reject accept requests if proposal number isn’t high enough
● Don’t want to deal with contention for every log slot!
● Solutions:
○ Random timeouts
○ Exponential backoff
○ Stable leader

PMMC vs. Lab 3
● Split into roles (replicas, acceptors, leaders, etc…)
● Multi-threaded
● Handles reconfiguration
● Retries leader election
when preempted
● One class (PaxosServer) ○ Handles all the roles
● Single-threaded
● Ignores reconfiguration
● Uses heartbeat messages to
determine when to begin leader election

Phase 2: Leader
● Upon receiving a P2A, an acceptor should only accept it if the ballot number in the message matches the acceptors ballot number
○ This means the acceptor considers the sender to be the current leader
○ Prevents split brain problems
○ Can always reply with a P2B, just don’t update state if ballot numbers don’t match!
● Need a way to sync logs between leader and all the acceptors. One way – when leader sends an accept message, attach the leader’s log with the request. When acceptor replies, attach the acceptor’s log with the response. Then update/merge each side’s log. Can also sync up with heartbeat messages. Lots of different possible protocols and implementations to consider!

● As leader:
○ Act as a proposer and acceptor from Basic Paxos
○ Propose requests from clients
■ First, check if the command has already been proposed, decided, or executed
○ Keeps replicas up to date
○ Send heartbeats to servers so they know the leader is alive
■ Can include garbage collection information in these messages (more info soon) ● As anyone else (not leader):
○ Drop client requests
○ Act only as an acceptor, not a proposer
■ That is, until the server believes the leader died. Then it should start phase 1 (scout phase)

Garbage Collection
● Problem: log (and thus memory usage) can grow indefinitely
● Solution: garbage collect (delete) log entries that are no longer needed
● Can discard log slots that everyone has already executed
● Need a way to determine what slots other nodes are done with
○ One solution: piggyback this information on heartbeat replies

Garbage Collection: 3 servers in the system
Server1 (leader): Latest executed slot: 4
Can garbage collect slots 1-3
Latest executed slot: 4
Latest executed slot: 3 Hasn’t heard about slot 4

Garbage Collection: 5 servers in the system
Server1 (leader): Latest executed slot: 4
Latest executed slot: N/A
Cannot garbage collect anything until all servers have executed a slot
Latest executed slot: 4
Latest executed slot: N/A
Latest executed slot: 3 Hasn’t heard about slot 4

Lab 3 Questions, q1
Question: What’s the difference between a ballot number and a log slot?
● Ballots are tuples of (round, leader) and are used during phase 1 of Multi-
Paxos (analogous to proposal numbers from Basic Paxos).
● Log slots are more general – namely, each log slot corresponds to an
instance of Paxos.
○ Basic Paxos has no notion of log slots because it is only used to decide on a single value
○ A single ballot can be used to decide multiple log slots
■ This means the leader did not change

Lab 3 Questions, q2
Question: When are you done with a log slot? How can you make sure that this is done efficiently?
Answer: You are done when all servers in the Paxos group have executed the
request. You can piggyback messages to let everyone know not only what you
are done with, but what you think everyone else is done with.
● Note: Some log slots may have not been decided because the proposer may have died, stopping the push to agreement on that log slot. You can resolve this by proposing a value, which will either drive
any already accepted value to be chosen for that log slot, or will place a no-op into that log slot.

Dealing with Log “Holes”/Proposing no-ops
If we have in our log:
put(a, 1), ______, ______, append(a, 2)
Do we know those empty log slots are decided? How can we push these log slots to completion?
Your implementation needs to be able to handle “holes” in the Paxos log. That is, at certain points, a server might see agreement being reached on a slot but not previous slots. Your implementation should still make progress in this case.

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.2
Accepted: {2->(B, 1.2)}
Server 3 log:
Not started
In progress
Value chosen
Server3 Ballot: 1.3 Active: false Accepted: {} Log: {}

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.2
Accepted: {2->(B, 1.2)}
ballot: 1.3
Server 3 log:
Not started
In progress
Value chosen
Server3 Ballot: 1.3 Active: false Accepted: {} Log: {}

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.3
Accepted: {2->(B, 1.2)}
ballot: 1.3
accepted: {2->(B, 1.2)}
Server3 Ballot: 1.3 Active: false Accepted: {} Log: {}
Server 3 log:
Not started
In progress
Value chosen

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.3
Accepted: {2->(B, 1.2)}
Ballot: 1.3
Active: true
Proposals: {2->(B, 1.2)} Log: {}
Server 3 log:
Not started
In progress
Value chosen
1 2 3 4 …

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.3
Accepted: {2->(B, 1.2)}
Ballot: 1.3
Active: true
Proposals: {2->(B, 1.2)} Received P2B from: {} Log: {}
ballot: 1.3
slot number: 1 command: no-op
Server 3 log:
Not started
In progress
Value chosen
1 2 3 4 …

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.3
Accepted: {2->(B, 1.2)}
Ballot: 1.3
Active: true
Proposals: {2->(B, 1.2)} Received P2B from: {} Log: {}
ballot: 1.3
slot number: 2 command: B
Server 3 log:
Not started
In progress
Value chosen
1 2 3 4 …

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.3
Accepted: {2->(B, 1.3)}
Ballot: 1.3
Active: true
Proposals: {2->(B, 1.2)} Received P2B from: {} Log: {}
ballot: 1.3
slot number: 2
Server 3 log:
Not started
In progress
Value chosen
1 2 3 4 …

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.3
Accepted: {2->(B, 1.3)}
Server 3 log:
Not started
In progress
Value chosen
Ballot: 1.3
Active: true
Proposals: {2->(B, 1.2)} Received P2B from: {2->[2]} Log: {}
ballot: 1.3
slot number: 2

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.3
Accepted: {2->(B, 1.3)}
Server3 Ballot: 1.3
Active: true
Proposals: {2->(B, 1.2)} Received P2B from: {2->[2,3]} Log: {2->B}
ballot: 1.3
slot number: 1 command: no-op
Server 3 log:
Not started
In progress
Value chosen
1 2 3 4 …

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.3
Accepted: {1->(no-op, 1.3), 2->(B, 1.3)}
ballot: 1.3
slot number: 1
Server3 Ballot: 1.3
Server 3 log:
Not started
In progress
Value chosen
Active: true
Proposals: {2->(B, 1.2)} Received P2B from: {2->[2,3]} Log: {2->B}
1 2 3 4 …

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.3
Accepted: {1->(no-op, 1.3), 2->(B, 1.3)}
Ballot: 1.3
Active: true
Proposals: {2->(B, 1.2)} Received P2B from: {1->[2], 2- >[2,3]}
Log: {2->B}
ballot: 1.3
slot number: 1
Server 3 log:
Not started
In progress
Value chosen

Ballot: 1.2
Accepted: {1->(A, 1.2), 2- >(B, 1.2)}
Ballot: 1.3
Accepted: {1->(no-op, 1.3), 2->(B, 1.3)}
Server 3 log:
Not started
In progress
Value chosen
Ballot: 1.3
Active: true
Proposals: {2->(B, 1.2)} Received P2B from: {1->[2, 3], 2->[2,3]}
Log: {1->no-op, 2->B}
1 2 3 4 …

Cycling Leaders/Late Rejections
Consider the case with 5 servers:
Server 4 is leader.
Server 4 sends P2A for slot 1 with ballot number ⟨1, 4⟩ to every server.
Server 5 sends P1A to every with ballot ⟨1, 5⟩.
Servers 1 and 2 accept and send P1B.
Server 5 then goes down.
Server 4 sees this and starts scouting sending P1A with ⟨2, 4⟩.
Servers 1 and 2 accept and send P1B.
Server 4 is now the active leader.
Server 4 sends P2A for slot 1 with ballot ⟨2, 4⟩ to every server.
Server 2 then receives the old P2A with slot 1 and ballot ⟨1, 4⟩.
Server 2 then sends back a P2B with the ballot ⟨2, 4⟩ without accepting the P2A.
Server 4 gets the P2B with ballot ⟨2, 4⟩ and believes server 2 has accepted the new P2A, which it has not.

Misc. tips
● Don’t use objects to separate the roles because that might blow up the state space on search tests
● You don’t need WINDOW because we aren’t reconfiguring
● You don’t need to re-propose alreadyExecuted commands
● http://paxos.systems/ is easier to parse than PMMC
● TrytogetLab3toworkbecauseLab4isbuiltontopofLab3

Lab submission
● Please Submit “submit.tar.gz” (Other formats will not be accepted)
● Try to do version control on your code, do not use ._XXX to keep your
previous code
● We will only grade the latest submission for each team

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts