Paxos implementationraft simplify Paxos algorithm

文件名称: Paxos implementation

所属分类: 其它

开发工具:

文件大小: 535kb

下载次数: 0

上传时间: 2019-03-02

提供者: tal****

下载 (535kb)

不能下载？报告错误

详细说明：raft simplify Paxos algorithm you deserved it since it so powfulThe Paxos Approach Decompose the problem · Basic Paxos(“ single decree") One or more servers propose values System must agree on a single value as chosen Only one value is ever chosen o Muti-Paxos Combine several instances of basic paxos to agree on a series of values forming the log March 1.2013 Implementing Replicated Logs with Paxos Slide 3 Requirements for Basic Paxos Safety Only a single value may be chosen a server never learns that a value has been chosen unless it really has been o Liveness(as long as majority of servers up and communicating with reasonable timeliness) Some proposed value is eventually chosen If a value is chosen, servers eventually learn about it The term"consensus problem"typically refers to this single-value formulation March 1.2013 Implementing Replicated Logs with Paxos Slide 4 Paxos Components Proposers Active: put forth particular values to be chosen Handle client requests Acceptors Passive: respond to messages from proposers Responses represent votes that form consensus Store chosen value, state of the decision process Want to know which value was chosen For this presentation Each Paxos server contains both components March 1.2013 Implementing Replicated Logs with Paxos Slide 5 Strawman: Single Acceptor Simple(incorrect) approach Proposers a single acceptor chooses value o What if acceptor crashes add )(jmp( shl )(sub after choosing? e Solution: quorum Acceptor Multiple acceptors (3, 5,..) Value v is chosen if accepted by mp majority of acceptors If one acceptor crashes, chosen value still available March 1.2013 mplementing Replicated Logs with PaXos Slide 6 Problem: Split Votes Acceptor accepts only first value it receives? o If simultaneous proposals, no value might be chosen accept?(red) accepted(red accepted(red 2 accept? (blue) accepted(blue) accepted(blue) accept? (green) accepted(green) 5 time Acceptors must sometimes accept multiple(different) values March 1.2013 mplementing Replicated Logs with PaXos Slide 7 Problem: Conflicting Choices Acceptor accepts every value it receives? Could choose multiple values Red chosen accept? (red)I accepted(red) accepted(red 2 H accepted(red)i i accepted (blue ) 3 i accepted (blue S, i accepted(blue) 5 t accept? (blue) time Blue Chosen Once a value has been chosen, future proposals must propose/choose that same value(2-phase protocol) March 1.2013 Implementing Replicated Logs with Paxos Slide 8 Conflicting Choices, cont'd Red chosen?? accept? (red)accepted (red accepted (red)H 2 ..·····..........······· i accepted(blue) accepted(red accepted(blue) 4 .·。。· accepted (blue) prop(blue) time Blue chosen o Ss neednt propose red (it hasnt been chosen yet) S,s proposal must be aborted(s3 must reject it) Must order proposals, reject old ones March 1.2013 mplementing Replicated Logs with PaXos Slide 9 Proposal Numbers o Each proposal has a unique number Higher numbers take priority over lower numbers It must be possible for a proposer to choose a new proposal number higher than anything it has seen/used before One simple approach: Proposal number Round Number Server ld Each server stores maxRound the largest round number it has seen so far To generate a new proposal number ●| increment maxround Concatenate with Server d Proposers must persist max Round on disk must not reuse proposal numbers after crash/restart March 1.2013 Implementing Replicated Logs with Paxos Slide 10

(系统自动生成,下载前可以参看下载内容)