0. 引言

etcd/raft将Raft算法是实现分成了三个模块:

  1. Raft状态机;
  2. 存储模块;
  3. 传输模块。

Raft状态机完全由etcd/raft负责,raft结构体即为其实现。使用etc/raft的开发者不能直接操作raft结构体,只能通过etcd/raft提供的Node接口对其进行操作。

存储模块可以划分为两个部分:对存储的读取与写入。etcd/raft只需要读取存储,etcd/raft依赖的Storage接口中只有读取存储的方法。而对存储的写入由用户负责,etcd/raft并不关心开发者如何写入存储,对存储的写入方法可以由开发者自己定义。etcd使用的存储模块是与Storage接口同一文件下的MemoryStorage结构体。MemoryStorage既实现了Storage接口需要的读取存储的方法,也为用户提供了写入存储的方法。

说明

Storage接口定义的是稳定存储的读取方法。之所以etcd使用了基于内存的MemoryStorage,是因为etcd在写入MemoryStorage前,需要先写入预写日志(Write Ahead Log,WAL)或快照。而预写日志和快照是保存在稳定存储中的,这样,在每次重启时,etcd可以基于保存在稳定存储中的快照和预写日志恢复MemoryStorage的状态。也就是说,etcd的稳定存储是通过快照、预写日志、MemoryStorage三者共同实现的。

通信模块是完全由使用etcd/raft的开发者负责的。etcd/raft不关心开发者如何实现通信模块。

下图是一张关于etcd/raft的实现中,开发者与etcd/raft对这三个模块的职责的示意图。


因为Node接口是开发者仅有的操作etcd/raft的方式,所以我们先来看看Node接口与其相关实现。

1. Node、node、rawnode

Node接口为开发者提供了操作etcd/raft的方法。其接口定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Node represents a node in a raft cluster.
type Node interface {
// Tick increments the internal logical clock for the Node by a single tick. Election
// timeouts and heartbeat timeouts are in units of ticks.
Tick()
// Campaign causes the Node to transition to candidate state and start campaigning to become leader.
Campaign(ctx context.Context) error
// Propose proposes that data be appended to the log. Note that proposals can be lost without
// notice, therefore it is user's job to ensure proposal retries.
Propose(ctx context.Context, data []byte) error
// ProposeConfChange proposes a configuration change. Like any proposal, the
// configuration change may be dropped with or without an error being
// returned. In particular, configuration changes are dropped unless the
// leader has certainty that there is no prior unapplied configuration
// change in its log.
//
// The method accepts either a pb.ConfChange (deprecated) or pb.ConfChangeV2
// message. The latter allows arbitrary configuration changes via joint
// consensus, notably including replacing a voter. Passing a ConfChangeV2
// message is only allowed if all Nodes participating in the cluster run a
// version of this library aware of the V2 API. See pb.ConfChangeV2 for
// usage details and semantics.
ProposeConfChange(ctx context.Context, cc pb.ConfChangeI) error

// Step advances the state machine using the given message. ctx.Err() will be returned, if any.
Step(ctx context.Context, msg pb.Message) error

// Ready returns a channel that returns the current point-in-time state.
// Users of the Node must call Advance after retrieving the state returned by Ready.
//
// NOTE: No committed entries from the next Ready may be applied until all committed entries
// and snapshots from the previous one have finished.
Ready() <-chan Ready

// Advance notifies the Node that the application has saved progress up to the last Ready.
// It prepares the node to return the next available Ready.
//
// The application should generally call Advance after it applies the entries in last Ready.
//
// However, as an optimization, the application may call Advance while it is applying the
// commands. For example. when the last Ready contains a snapshot, the application might take
// a long time to apply the snapshot data. To continue receiving Ready without blocking raft
// progress, it can call Advance before finishing applying the last ready.
Advance()
// ApplyConfChange applies a config change (previously passed to
// ProposeConfChange) to the node. This must be called whenever a config
// change is observed in Ready.CommittedEntries, except when the app decides
// to reject the configuration change (i.e. treats it as a noop instead), in
// which case it must not be called.
//
// Returns an opaque non-nil ConfState protobuf which must be recorded in
// snapshots.
ApplyConfChange(cc pb.ConfChangeI) *pb.ConfState

// TransferLeadership attempts to transfer leadership to the given transferee.
TransferLeadership(ctx context.Context, lead, transferee uint64)

// ReadIndex request a read state. The read state will be set in the ready.
// Read state has a read index. Once the application advances further than the read
// index, any linearizable read requests issued before the read request can be
// processed safely. The read state will have the same rctx attached.
// Note that request can be lost without notice, therefore it is user's job
// to ensure read index retries.
ReadIndex(ctx context.Context, rctx []byte) error

// Status returns the current status of the raft state machine.
Status() Status
// ReportUnreachable reports the given node is not reachable for the last send.
ReportUnreachable(id uint64)
// ReportSnapshot reports the status of the sent snapshot. The id is the raft ID of the follower
// who is meant to receive the snapshot, and the status is SnapshotFinish or SnapshotFailure.
// Calling ReportSnapshot with SnapshotFinish is a no-op. But, any failure in applying a
// snapshot (for e.g., while streaming it from leader to follower), should be reported to the
// leader with SnapshotFailure. When leader sends a snapshot to a follower, it pauses any raft
// log probes until the follower can apply the snapshot and advance its state. If the follower
// can't do that, for e.g., due to a crash, it could end up in a limbo, never getting any
// updates from the leader. Therefore, it is crucial that the application ensures that any
// failure in snapshot sending is caught and reported back to the leader; so it can resume raft
// log probing in the follower.
ReportSnapshot(id uint64, status SnapshotStatus)
// Stop performs any necessary termination of the Node.
Stop()
}

Node结构中的方法按调用时机可以分为三类:

方法 描述
Tick 由时钟(循环定时器)驱动,每隔一定时间调用一次,驱动raft结构体的内部时钟运行。
ReadyAdvance 这两个方法往往成对出现。准确的说,是Ready方法返回的Ready结构体信道的信号与Advance方法成对出现。每当从Ready结构体信道中收到来自raft的消息时,用户需要按照一定顺序对Ready结构体中的字段机械能处理。在完成对Ready的处理后,需要调用Advance方法,通知raft这批数据已经处理完成,可以继续传入下一批。
其它方法 需要时随时调用。

对于Ready结构体,有几个重要的字段需要按照入顺序处理:

  1. HardStateEntriesSnapshot写入稳定存储(其中,Snapshot的写入不需要严格按照此顺序,etcd/raft为快照的传入提供了另一套机制以优化执行效率)。
  2. 本条中的操作可以并行执行:
    • Messages中的消息发送给相应的节点;
    • SnapshotCommittedEntries应用到本地状态机中。
  3. 调用Advance方法。

在了解了Node接口的基本使用方式后,我们再关注一下其实现。

在etcd/raft中,Node接口的实现一共有两个,分别是Node结构体和raw结构体。二者都是对etcd/raft中Raft状态机raft结构体进行操作。不同的是,node结构体是线程安全的,其内部封装了rawnode,并通过各种信道操作实现线程安全的操作;而rawnode是非线程安全的,其直接将Node接口中的方法转为对raft结构体对方法对调用。rawnode是为需要实现Multi-Raft的开发者提供的更底层的接口。

学习etcd/raft中Raft算法的实现与优化不需要深入noderawnode的实现,因此这里不对其进行详细的分析。

2. Raft状态机——raft

etcd/raft的实现的优雅之处之一,在于其很好地剥离了各模块的职责。在etcd/raft的实现中,raft结构体是一个Raft状态机,其通过Step方法进行状态转移。只要涉及到Raft状态机的状态转移,最终都会通过Step方法完成。Step方法的参数是Raft消息(在etcd/raft/raftpb中,是直接通过.proto文件生成的Protocol Buffers的go语言实现)。

这里我们以Node接口的Tick方法为例,其调用了raft结构体的tick“方法”。

1
2
3
4
// Tick advances the internal logical clock by a single tick.
func (rn *RawNode) Tick() {
rn.raft.tick()
}

这里之所以给“方法”打上引号,是因为tick其实并非一个真正的方法,而是raft的一个字眼,其类型为一个无参无返回值的函数。

这样设计的原因,是leader和follower在tick被调用时行为不同。tick字段可能的值有两个,分别为tickElectiontickHeartbeat,二者分别对应follower(或candidate,pre candidate)和leader的tick行为。leader每隔一段时间需要广播心跳来防止follower谋权篡位,folower每隔一段时间没有收到leader的心跳就要重新选主。我们可以在如下4个方法中找到相应的依据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func (r *raft) becomeFollower(term uint64, lead uint64) {
// ...
r.tick = r.tickElection
// ...
}

func (r *raft) becomeCandidate() {
// ...
r.tick = r.tickElection
// ...
}

func (r *raft) becomePreCandidate() {
// ...
r.tick = r.tickElection
// ...
}

func (r *raft) becomeLeader() {
// ...
r.tick = r.tickHeartbeat
// ...
}

这里我们先以tickElection为例,分析其如何将这一方法转为对Step方法对调用的。

1
2
3
4
5
6
7
8
9
10
11
// tickElection is run by followers and candidates after r.electionTimeout.
func (r *raft) tickElection() {
r.electionElapsed++

if r.promotable() && r.pastElectionTimeout() {
r.electionElapsed = 0
if err := r.Step(pb.Message{From: r.id, Type: pb.MsgHup}); err != nil {
r.logger.Debugf("error occurred during election: %v", err)
}
}
}

我们可以看到,tickElection方法会增大electionElapsed的值。当其超过了选举超时且当前节点可提拔为leader时(具体实现会在后续的文章中分析),重制其值,并创建一条MsgHup消息,传给Step方法。Step方法会对该消息进行处理,并适当地转移Raft状态机的状态。

raft结构体中的字段和相应的方法有很多。在后续的文章中,我们会再介绍etcd/raft中Raft算法的各部分实现时,介绍相应的字段与方法。这里仅给出创建noderawnode时所需的Config结构体的结构,其大部分字段都与raft结构体中的有关字段相对应。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// Config contains the parameters to start a raft.
type Config struct {
// ID is the identity of the local raft. ID cannot be 0.
ID uint64

// ElectionTick is the number of Node.Tick invocations that must pass between
// elections. That is, if a follower does not receive any message from the
// leader of current term before ElectionTick has elapsed, it will become
// candidate and start an election. ElectionTick must be greater than
// HeartbeatTick. We suggest ElectionTick = 10 * HeartbeatTick to avoid
// unnecessary leader switching.
ElectionTick int
// HeartbeatTick is the number of Node.Tick invocations that must pass between
// heartbeats. That is, a leader sends heartbeat messages to maintain its
// leadership every HeartbeatTick ticks.
HeartbeatTick int

// Storage is the storage for raft. raft generates entries and states to be
// stored in storage. raft reads the persisted entries and states out of
// Storage when it needs. raft reads out the previous state and configuration
// out of storage when restarting.
Storage Storage
// Applied is the last applied index. It should only be set when restarting
// raft. raft will not return entries to the application smaller or equal to
// Applied. If Applied is unset when restarting, raft might return previous
// applied entries. This is a very application dependent configuration.
Applied uint64

// MaxSizePerMsg limits the max byte size of each append message. Smaller
// value lowers the raft recovery cost(initial probing and message lost
// during normal operation). On the other side, it might affect the
// throughput during normal replication. Note: math.MaxUint64 for unlimited,
// 0 for at most one entry per message.
MaxSizePerMsg uint64
// MaxCommittedSizePerReady limits the size of the committed entries which
// can be applied.
MaxCommittedSizePerReady uint64
// MaxUncommittedEntriesSize limits the aggregate byte size of the
// uncommitted entries that may be appended to a leader's log. Once this
// limit is exceeded, proposals will begin to return ErrProposalDropped
// errors. Note: 0 for no limit.
MaxUncommittedEntriesSize uint64
// MaxInflightMsgs limits the max number of in-flight append messages during
// optimistic replication phase. The application transportation layer usually
// has its own sending buffer over TCP/UDP. Setting MaxInflightMsgs to avoid
// overflowing that sending buffer. TODO (xiangli): feedback to application to
// limit the proposal rate?
MaxInflightMsgs int

// CheckQuorum specifies if the leader should check quorum activity. Leader
// steps down when quorum is not active for an electionTimeout.
CheckQuorum bool

// PreVote enables the Pre-Vote algorithm described in raft thesis section
// 9.6. This prevents disruption when a node that has been partitioned away
// rejoins the cluster.
PreVote bool

// ReadOnlyOption specifies how the read only request is processed.
//
// ReadOnlySafe guarantees the linearizability of the read only request by
// communicating with the quorum. It is the default and suggested option.
//
// ReadOnlyLeaseBased ensures linearizability of the read only request by
// relying on the leader lease. It can be affected by clock drift.
// If the clock drift is unbounded, leader might keep the lease longer than it
// should (clock can move backward/pause without any bound). ReadIndex is not safe
// in that case.
// CheckQuorum MUST be enabled if ReadOnlyOption is ReadOnlyLeaseBased.
ReadOnlyOption ReadOnlyOption

// Logger is the logger used for raft log. For multinode which can host
// multiple raft group, each raft group can have its own logger
Logger Logger

// DisableProposalForwarding set to true means that followers will drop
// proposals, rather than forwarding them to the leader. One use case for
// this feature would be in a situation where the Raft leader is used to
// compute the data of a proposal, for example, adding a timestamp from a
// hybrid logical clock to data in a monotonically increasing way. Forwarding
// should be disabled to prevent a follower with an inaccurate hybrid
// logical clock from assigning the timestamp and then forwarding the data
// to the leader.
DisableProposalForwarding bool
}

3. 总结

本文主要从顶层的视角,简单地分析了etcd/raft的总体设计。本文的主要目的是给读者etcd/raft的结构的整体认识,便于读者接下来学习etcd/raft中Raft算法的实现与优化。