Documentation
¶
Index ¶
- type Config
- type Inflights
- type Progress
- func (pr *Progress) BecomeProbe()
- func (pr *Progress) BecomeReplicate()
- func (pr *Progress) BecomeSnapshot(snapshoti uint64)
- func (pr *Progress) IsPaused() bool
- func (pr *Progress) MaybeDecrTo(rejected, last uint64) bool
- func (pr *Progress) MaybeUpdate(n uint64) bool
- func (pr *Progress) OptimisticUpdate(n uint64)
- func (pr *Progress) ProbeAcked()
- func (pr *Progress) ResetState(state StateType)
- func (pr *Progress) String() string
- type ProgressMap
- type ProgressTracker
- func (p *ProgressTracker) Committed() uint64
- func (p *ProgressTracker) ConfState() pb.ConfState
- func (p *ProgressTracker) IsSingleton() bool
- func (p *ProgressTracker) LearnerNodes() []uint64
- func (p *ProgressTracker) QuorumActive() bool
- func (p *ProgressTracker) RecordVote(id uint64, v bool)
- func (p *ProgressTracker) ResetVotes()
- func (p *ProgressTracker) TallyVotes() (granted int, rejected int, _ quorum.VoteResult)
- func (p *ProgressTracker) Visit(f func(id uint64, pr *Progress))
- func (p *ProgressTracker) VoterNodes() []uint64
- type StateType
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Config ¶
type Config struct {
Voters quorum.JointConfig
// AutoLeave is true if the configuration is joint and a transition to the
// incoming configuration should be carried out automatically by Raft when
// this is possible. If false, the configuration will be joint until the
// application initiates the transition manually.
AutoLeave bool
// Learners is a set of IDs corresponding to the learners active in the
// current configuration.
//
// Invariant: Learners and Voters does not intersect, i.e. if a peer is in
// either half of the joint config, it can't be a learner; if it is a
// learner it can't be in either half of the joint config. This invariant
// simplifies the implementation since it allows peers to have clarity about
// its current role without taking into account joint consensus.
Learners map[uint64]struct{}
// When we turn a voter into a learner during a joint consensus transition,
// we cannot add the learner directly when entering the joint state. This is
// because this would violate the invariant that the intersection of
// voters and learners is empty. For example, assume a Voter is removed and
// immediately re-added as a learner (or in other words, it is demoted):
//
// Initially, the configuration will be
//
// voters: {1 2 3}
// learners: {}
//
// and we want to demote 3. Entering the joint configuration, we naively get
//
// voters: {1 2} & {1 2 3}
// learners: {3}
//
// but this violates the invariant (3 is both voter and learner). Instead,
// we get
//
// voters: {1 2} & {1 2 3}
// learners: {}
// next_learners: {3}
//
// Where 3 is now still purely a voter, but we are remembering the intention
// to make it a learner upon transitioning into the final configuration:
//
// voters: {1 2}
// learners: {3}
// next_learners: {}
//
// Note that next_learners is not used while adding a learner that is not
// also a voter in the joint config. In this case, the learner is added
// right away when entering the joint configuration, so that it is caught up
// as soon as possible.
LearnersNext map[uint64]struct{}
}
Config reflects the configuration tracked in a ProgressTracker.
type Inflights ¶
type Inflights struct {
// contains filtered or unexported fields
}
Inflights limits the number of MsgApp (represented by the largest index contained within) sent to followers but not yet acknowledged by them. Callers use Full() to check whether more messages can be sent, call Add() whenever they are sending a new append, and release "quota" via FreeLE() whenever an ack is received.
func NewInflights ¶
NewInflights sets up an Inflights that allows up to 'size' inflight messages.
func (*Inflights) Add ¶
Add notifies the Inflights that a new message with the given index is being dispatched. Full() must be called prior to Add() to verify that there is room for one more message, and consecutive calls to add Add() must provide a monotonic sequence of indexes.
func (*Inflights) Clone ¶
Clone returns an *Inflights that is identical to but shares no memory with the receiver.
func (*Inflights) FreeFirstOne ¶
func (in *Inflights) FreeFirstOne()
FreeFirstOne releases the first inflight. This is a no-op if nothing is inflight.
type Progress ¶
type Progress struct {
Match, Next uint64
// State defines how the leader should interact with the follower.
//
// When in StateProbe, leader sends at most one replication message
// per heartbeat interval. It also probes actual progress of the follower.
//
// When in StateReplicate, leader optimistically increases next
// to the latest entry sent after sending replication message. This is
// an optimized state for fast replicating log entries to the follower.
//
// When in StateSnapshot, leader should have sent out snapshot
// before and stops sending any replication message.
State StateType
// PendingSnapshot is used in StateSnapshot.
// If there is a pending snapshot, the pendingSnapshot will be set to the
// index of the snapshot. If pendingSnapshot is set, the replication process of
// this Progress will be paused. raft will not resend snapshot until the pending one
// is reported to be failed.
PendingSnapshot uint64
// RecentActive is true if the progress is recently active. Receiving any messages
// from the corresponding follower indicates the progress is active.
// RecentActive can be reset to false after an election timeout.
//
// TODO(tbg): the leader should always have this set to true.
RecentActive bool
// ProbeSent is used while this follower is in StateProbe. When ProbeSent is
// true, raft should pause sending replication message to this peer until
// ProbeSent is reset. See ProbeAcked() and IsPaused().
ProbeSent bool
// Inflights is a sliding window for the inflight messages.
// Each inflight message contains one or more log entries.
// The max number of entries per message is defined in raft config as MaxSizePerMsg.
// Thus inflight effectively limits both the number of inflight messages
// and the bandwidth each Progress can use.
// When inflights is Full, no more message should be sent.
// When a leader sends out a message, the index of the last
// entry should be added to inflights. The index MUST be added
// into inflights in order.
// When a leader receives a reply, the previous inflights should
// be freed by calling inflights.FreeLE with the index of the last
// received entry.
Inflights *Inflights
// IsLearner is true if this progress is tracked for a learner.
IsLearner bool
}
Progress represents a follower’s progress in the view of the leader. Leader maintains progresses of all followers, and sends entries to the follower based on its progress.
NB(tbg): Progress is basically a state machine whose transitions are mostly strewn around `*raft.raft`. Additionally, some fields are only used when in a certain State. All of this isn't ideal.
func (*Progress) BecomeProbe ¶
func (pr *Progress) BecomeProbe()
BecomeProbe transitions into StateProbe. Next is reset to Match+1 or, optionally and if larger, the index of the pending snapshot.
func (*Progress) BecomeReplicate ¶
func (pr *Progress) BecomeReplicate()
BecomeReplicate transitions into StateReplicate, resetting Next to Match+1.
func (*Progress) BecomeSnapshot ¶
BecomeSnapshot moves the Progress to StateSnapshot with the specified pending snapshot index.
func (*Progress) IsPaused ¶
IsPaused returns whether sending log entries to this node has been throttled. This is done when a node has rejected recent MsgApps, is currently waiting for a snapshot, or has reached the MaxInflightMsgs limit. In normal operation, this is false. A throttled node will be contacted less frequently until it has reached a state in which it's able to accept a steady stream of log entries again.
func (*Progress) MaybeDecrTo ¶
MaybeDecrTo adjusts the Progress to the receipt of a MsgApp rejection. The arguments are the index the follower rejected to append to its log, and its last index.
Rejections can happen spuriously as messages are sent out of order or duplicated. In such cases, the rejection pertains to an index that the Progress already knows were previously acknowledged, and false is returned without changing the Progress.
If the rejection is genuine, Next is lowered sensibly, and the Progress is cleared for sending log entries.
func (*Progress) MaybeUpdate ¶
MaybeUpdate is called when an MsgAppResp arrives from the follower, with the index acked by it. The method returns false if the given n index comes from an outdated message. Otherwise it updates the progress and returns true.
func (*Progress) OptimisticUpdate ¶
OptimisticUpdate signals that appends all the way up to and including index n are in-flight. As a result, Next is increased to n+1.
func (*Progress) ProbeAcked ¶
func (pr *Progress) ProbeAcked()
ProbeAcked is called when this peer has accepted an append. It resets ProbeSent to signal that additional append messages should be sent without further delay.
func (*Progress) ResetState ¶
ResetState moves the Progress into the specified State, resetting ProbeSent, PendingSnapshot, and Inflights.
type ProgressMap ¶
ProgressMap is a map of *Progress.
func (ProgressMap) String ¶
func (m ProgressMap) String() string
String prints the ProgressMap in sorted key order, one Progress per line.
type ProgressTracker ¶
type ProgressTracker struct {
Config
Progress ProgressMap
Votes map[uint64]bool
MaxInflight int
}
ProgressTracker tracks the currently active configuration and the information known about the nodes and learners in it. In particular, it tracks the match index for each peer which in turn allows reasoning about the committed index.
func MakeProgressTracker ¶
func MakeProgressTracker(maxInflight int) ProgressTracker
MakeProgressTracker initializes a ProgressTracker.
func (*ProgressTracker) Committed ¶
func (p *ProgressTracker) Committed() uint64
Committed returns the largest log index known to be committed based on what the voting members of the group have acknowledged.
func (*ProgressTracker) ConfState ¶
func (p *ProgressTracker) ConfState() pb.ConfState
ConfState returns a ConfState representing the active configuration.
func (*ProgressTracker) IsSingleton ¶
func (p *ProgressTracker) IsSingleton() bool
IsSingleton returns true if (and only if) there is only one voting member (i.e. the leader) in the current configuration.
func (*ProgressTracker) LearnerNodes ¶
func (p *ProgressTracker) LearnerNodes() []uint64
LearnerNodes returns a sorted slice of learners.
func (*ProgressTracker) QuorumActive ¶
func (p *ProgressTracker) QuorumActive() bool
QuorumActive returns true if the quorum is active from the view of the local raft state machine. Otherwise, it returns false.
func (*ProgressTracker) RecordVote ¶
func (p *ProgressTracker) RecordVote(id uint64, v bool)
RecordVote records that the node with the given id voted for this Raft instance if v == true (and declined it otherwise).
func (*ProgressTracker) ResetVotes ¶
func (p *ProgressTracker) ResetVotes()
ResetVotes prepares for a new round of vote counting via recordVote.
func (*ProgressTracker) TallyVotes ¶
func (p *ProgressTracker) TallyVotes() (granted int, rejected int, _ quorum.VoteResult)
TallyVotes returns the number of granted and rejected Votes, and whether the election outcome is known.
func (*ProgressTracker) Visit ¶
func (p *ProgressTracker) Visit(f func(id uint64, pr *Progress))
Visit invokes the supplied closure for all tracked progresses in stable order.
func (*ProgressTracker) VoterNodes ¶
func (p *ProgressTracker) VoterNodes() []uint64
VoterNodes returns a sorted slice of voters.
type StateType ¶
type StateType uint64
StateType is the state of a tracked follower.
const ( // StateProbe indicates a follower whose last index isn't known. Such a // follower is "probed" (i.e. an append sent periodically) to narrow down // its last index. In the ideal (and common) case, only one round of probing // is necessary as the follower will react with a hint. Followers that are // probed over extended periods of time are often offline. StateProbe StateType = iota // StateReplicate is the state steady in which a follower eagerly receives // log entries to append to its log. StateReplicate // StateSnapshot indicates a follower that needs log entries not available // from the leader's Raft log. Such a follower needs a full snapshot to // return to StateReplicate. StateSnapshot )
Source Files