v0.0.0-...-d88c8b5 Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: Feb 9, 2021 License: Apache-2.0 Imports: 5 Imported by: 0




This section is empty.


This section is empty.


This section is empty.


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.

func (*Config) Clone

func (c *Config) Clone() Config

Clone returns a copy of the Config that shares no memory with the original.

func (Config) String

func (c Config) String() string

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

func NewInflights(size int) *Inflights

NewInflights sets up an Inflights that allows up to 'size' inflight messages.

func (*Inflights) Add

func (in *Inflights) Add(inflight uint64)

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

func (in *Inflights) Clone() *Inflights

Clone returns an *Inflights that is identical to but shares no memory with the receiver.

func (*Inflights) Count

func (in *Inflights) Count() int

Count returns the number of inflight messages.

func (*Inflights) FreeFirstOne

func (in *Inflights) FreeFirstOne()

FreeFirstOne releases the first inflight. This is a no-op if nothing is inflight.

func (*Inflights) FreeLE

func (in *Inflights) FreeLE(to uint64)

FreeLE frees the inflights smaller or equal to the given `to` flight.

func (*Inflights) Full

func (in *Inflights) Full() bool

Full returns true if no more messages can be sent at the moment.

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

func (pr *Progress) BecomeSnapshot(snapshoti uint64)

BecomeSnapshot moves the Progress to StateSnapshot with the specified pending snapshot index.

func (*Progress) IsPaused

func (pr *Progress) IsPaused() bool

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

func (pr *Progress) MaybeDecrTo(rejected, last uint64) bool

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

func (pr *Progress) MaybeUpdate(n uint64) bool

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

func (pr *Progress) OptimisticUpdate(n uint64)

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

func (pr *Progress) ResetState(state StateType)

ResetState moves the Progress into the specified State, resetting ProbeSent, PendingSnapshot, and Inflights.

func (*Progress) String

func (pr *Progress) String() string

type ProgressMap

type ProgressMap map[uint64]*Progress

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 {

	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.
	// 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.

func (StateType) String

func (st StateType) String() string

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL