raft: transfer leader feature by es-chow · Pull Request #4916 · etcd-io/etcd

es-chow · 2016-03-31T02:04:33Z

Try to implement transfer leader as per raft thesis 3.10 Leadership transfer extension.

xiang90 · 2016-03-31T03:55:35Z

@es-chow Can you talk a little bit about your use case or potential use case? I know some one has already done this for etcd/raft. I can ask him to review the code too.

es-chow · 2016-03-31T08:15:22Z

The background for this is that Cockroachdb has an idea to coincide raft leader with range leader, https://github.com/cockroachdb/cockroach/blob/master/docs/design.md#relationship-to-raft-leadership.

This coincide may be achieved by leader transfer.

xiang90 · 2016-04-01T21:02:18Z

@bdarnell Can you confirm cockroach need this feature?

bdarnell · 2016-04-02T21:21:48Z

raft/raft.go

 		r.Step(pb.Message{From: r.id, Type: pb.MsgBeat})
 	}
+
+	// If current leader cannot transfer leader in election timeout, become leader again.


Shouldn't this be inside the r.electionElapsed >= r.electionTimeout block above at line 440?

yes, will fix it.

bdarnell · 2016-04-02T21:30:43Z

Yes, we could use some sort of orderly leadership handoff to allow us to choose the best leader.

I don't like doing this by introducing a new StateTransferLeader that is almost exactly like StateLeader, though. I think it would be better to stay in StateLeader throughout the process (until the transferee sends us a MsgVote and the old leader becomes a follower). In stepLeader's handling of MsgProp, we could drop proposals whenever transferee is non-zero.

xiang90 · 2016-04-02T21:33:06Z

Yes, we could use some sort of orderly leadership handoff to allow us to choose the best leader.

OK. I will take a closer look at this pr.

xiang90 · 2016-04-04T03:36:25Z

raft/raft.go


-	logger Logger
+	// Leader transfer target.
+	transferee uint64


move this to line 162?

es-chow · 2016-04-04T03:39:26Z

@bdarnell, as transferee will be reset to zero after sending out a MsgTimeoutNow to prevent multiple MsgTimeoutNow to send out when pipelining MsgAppResp been received. So if we judge if a MsgProp can be honored by check the value of transferee, it may make a MsgProp being honored just after a MsgTimeoutNow been sent out. Or we have to introduce one more flag to distinguish this.

xiang90 · 2016-04-04T21:19:30Z

I believe @dterei has implemented this feature for etcd/raft. So we would love to hear his opinion!

xiang90 · 2016-04-04T21:25:58Z

@es-chow I agree with @bdarnell. If the current leader receives a transfer it can still be in leader state. But it starts to block all incoming proposals for some timeout and sends all pending entries to the transferee. Adding one or two flags is probably better than introducing a whole new state?

xiang90 · 2016-04-04T21:26:50Z

raft/node_test.go

 			}
 		} else {
-			if msgt == raftpb.MsgBeat || msgt == raftpb.MsgHup || msgt == raftpb.MsgUnreachable || msgt == raftpb.MsgSnapStatus || msgt == raftpb.MsgCheckQuorum {
+			if msgt == raftpb.MsgBeat || msgt == raftpb.MsgHup || msgt == raftpb.MsgUnreachable || msgt == raftpb.MsgSnapStatus || msgt == raftpb.MsgCheckQuorum || msgt == raftpb.MsgTransferLeader {


probably it is time for us to make this multiple lines.

es-chow · 2016-04-05T07:16:16Z

@xiang90 , @bdarnell , @dterei, updated as per your comments. PTAL.

xiang90 · 2016-04-05T16:11:15Z

raft/raft.go

 	lead uint64
-
+	// Leader transfer target.
+	transferee uint64


// leadTransfree is id of the leader transfer target when its value is not zero.
leadTransfree?

xiang90 · 2016-04-05T16:49:58Z

raft/raft_test.go

+	nt := newNetwork(nil, nil, nil)
+	nt.send(pb.Message{From: 1, To: 1, Type: pb.MsgHup})
+
+	for j := 0; j <= 5; j++ {


why do we send 5 proposals in this test case?

xiang90 · 2016-04-05T17:15:18Z

@es-chow Looks good overall. Please fix the comments. Add LeaderTransfere prefix to all tests. Thanks!

es-chow · 2016-04-06T08:47:15Z

@xiang90 , @bdarnell, updated as per the comments. PTAL.

xiang90 · 2016-04-07T03:05:11Z

raft/raft.go

 		case len(r.votes) - gr:
 			r.becomeFollower(r.Term, None)
 		}
+	case pb.MsgTransferLeader:


can you move these to line 555. (same as how we handle m.Type == pb.MsgHup )

xiang90 · 2016-04-07T03:07:45Z

LGTM. Defer to @bdarnell or anyone from cockroach team.

ngaut · 2016-04-07T09:22:52Z

@xiang90 I'd like to see this happen too. And i will port the feature to TiKV later.

bdarnell · 2016-04-07T22:01:01Z

raft/raft.go

 				}
+				// Transfer leadership is in progress.
+				if m.From == r.leadTransferee && pr.Match == r.raftLog.lastIndex() && !r.timeoutNowSent {
+					r.logger.Infof("%x sent MsgTimeoutNow to %x after received MsgAppResp", r.id, m.From)


If we assume that the transport (usually) preserves order, we could send the MsgTimeoutNow as soon as we have sent a MsgApp containing the last index, without waiting for the MsgAppResp. This is similar to the way we optimistically increase Progress.Next when sending MsgApp.

@bdarnell, @xiang90, I feel we cannot send MsgTimeoutNow as soon as we have sent a MsgApp containing the last index in all cases, if we add that code and remove the code to send MsgTimeoutNow when a MsgAppResp is received, the test case TestLeaderTransferToSlowFollower cannot be passed as node 3 will reject that MsgApp just before the MsgTimeoutNow triggered by pb.MsgTransferLeader as its log is not up-to-date, but the following MsgTimeoutNow will trigger node3 to start an election which also will fail.

Maybe one way is we keep the code which send MsgTimeoutNow as receiving MsgAppResp, but add one optimistic sending MsgTimeoutNow only when we optimistically update the pr.Next, but this may also have the risk that peer may reject that MsgApp and MsgTimeoutNow will make the group unavailable for one election timeout. And also we have to keep the timeoutNowSent flag.

We keep the current code as we can also remove the timeoutNowSent flag. This is the updated commit.

I feel this is an optimization. We can think this more and do it in another pr. @es-chow Can you set up another issue to track this potential optimization?

Yeah, this optimization can wait. One thing we could do to avoid the scenario in which the follower rejects the MsgApp and then starts an election that fails is to include the leader's last log index in the MsgTimeoutNow. The follower would only start campaigning if it matches the index; if it doesn't then it knows it can't win.

bdarnell · 2016-04-07T22:01:28Z

LGTM. Thanks @es-chow!

xiang90 · 2016-04-07T22:43:15Z

@es-chow Can you fix the last few comments? We are getting really close to get this merged! Thanks!

tiancaiamao · 2016-05-05T10:25:30Z

raft/raft.go

+			if lastLeadTransferee == None {
+				r.logger.Debugf("%x is already leader. Ignored transfer leadership to %x", r.id, r.id)
+			} else {
+				r.logger.Debugf("%x abort transfer leadership to %x, transfer to current leader %x.", r.id, lastLeadTransferee, r.id)


it seems we never run to this line, otherwise r.abortLeaderTransfer() should be add.

I agree /cc @es-chow can you also take a look?

xiang90 added the area/raft label Mar 31, 2016

bdarnell reviewed Apr 2, 2016
View reviewed changes

xiang90 reviewed Apr 4, 2016
View reviewed changes

raft/raft.go Outdated

logger Logger

// Leader transfer target.

transferee uint64

Copy link
Copy Markdown

Contributor

xiang90 Apr 4, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

move this to line 162?

xiang90 reviewed Apr 4, 2016
View reviewed changes

es-chow force-pushed the transfer-leader branch 4 times, most recently from e465718 to e17ed54 Compare April 5, 2016 07:12

es-chow force-pushed the transfer-leader branch from e17ed54 to cb96878 Compare April 5, 2016 07:19

xiang90 reviewed Apr 5, 2016
View reviewed changes

es-chow force-pushed the transfer-leader branch 3 times, most recently from 0768bc4 to 24e2dbf Compare April 6, 2016 08:44

xiang90 reviewed Apr 7, 2016
View reviewed changes

ngaut mentioned this pull request Apr 7, 2016

Support transfer leader feature in raft tikv/tikv#363

Closed

bdarnell reviewed Apr 7, 2016
View reviewed changes

bdarnell mentioned this pull request Apr 7, 2016

monitoring: add metrics for leader lease durations cockroachdb/cockroach#5848

Closed

raft: transfer leader feature

ac059eb

es-chow force-pushed the transfer-leader branch from 24e2dbf to ac059eb Compare April 8, 2016 09:02

xiang90 merged commit b70e6a6 into etcd-io:master Apr 8, 2016

es-chow mentioned this pull request Apr 11, 2016

transfer raft leadership to range leadership cockroachdb/cockroach#5973

Merged

tiancaiamao reviewed May 5, 2016
View reviewed changes

darinpp mentioned this pull request Nov 26, 2019

release-19.1: storage: remove the replica up to date check when transferring lease cockroachdb/cockroach#42764

Merged

Conversation

es-chow commented Mar 31, 2016

Uh oh!

xiang90 commented Mar 31, 2016

Uh oh!

es-chow commented Mar 31, 2016

Uh oh!

xiang90 commented Apr 1, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

bdarnell commented Apr 2, 2016

Uh oh!

xiang90 commented Apr 2, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

es-chow commented Apr 4, 2016

Uh oh!

xiang90 commented Apr 4, 2016

Uh oh!

xiang90 commented Apr 4, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

es-chow commented Apr 5, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

xiang90 commented Apr 5, 2016

Uh oh!

es-chow commented Apr 6, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

xiang90 commented Apr 7, 2016

Uh oh!

ngaut commented Apr 7, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

bdarnell commented Apr 7, 2016

Uh oh!

xiang90 commented Apr 7, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Milestone

Development

Uh oh!

5 participants