cruisectl

package
v0.34.0-crescendo-prev... Latest Latest
Warning

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

 Go to latest Published: Apr 19, 2024 License: AGPL-3.0 Imports: 12 Imported by: 0

README

Cruise Control: Automated Block Time Adjustment for Precise Epoch Switchover Timing

Overview

Context

Epochs have a fixed length, measured in views. The actual view rate of the network varies depending on network conditions, e.g. load, number of offline replicas, etc. We would like for consensus nodes to observe the actual view rate of the committee, and adjust how quickly they proceed through views accordingly, to target a desired weekly epoch switchover time.

High-Level Design

The BlockTimeController observes the current view rate and adjusts the timing when the proposal should be released. It is a PID controller. The essential idea is to take into account the current error, the rate of change of the error, and the cumulative error, when determining how much compensation to apply. The compensation function $u[v]$ has three terms:

  • $P[v]$ compensates proportionally to the magnitude of the instantaneous error
  • $I[v]$ compensates proportionally to the magnitude of the error and how long it has persisted
  • $D[v]$ compensates proportionally to the rate of change of the error

📚 This document uses ideas from:

Choice of Process Variable: Targeted Epoch Switchover Time

The process variable is the variable which:

  • has a target desired value, or setpoint ($SP$)
  • is successively measured by the controller to compute the error $e$

👉 The BlockTimeController controls the progression through views, such that the epoch switchover happens at the intended point in time. We define:

  • $\gamma = k\cdot \tau_0$ is the remaining epoch duration of a hypothetical ideal system, where all remaining $k$ views of the epoch progress with the ideal view time $\tau_0$.
  • $\gamma = k\cdot \tau_0$ is the remaining epoch duration of a hypothetical ideal system, where all remaining $k$ views of the epoch progress with the ideal view time $\tau_0$.
  • The parameter $\tau_0$ is computed solely based on the Epoch configuration as $\tau_0 := \frac{<{\rm total\ epoch\ time}>}{<{\rm total\ views\ in\ epoch}>}$ (for mainnet 22, Epoch 75, we have $\tau_0 \simeq$ 1250ms).
  • $\Gamma$ is the actual time remaining until the desired epoch switchover.

The error, which the controller should drive towards zero, is defined as:

e := \gamma - \Gamma

From our definition it follows that:

  • $e > 0$ implies that the estimated epoch switchover (assuming ideal system behaviour) happens too late. Therefore, to hit the desired epoch switchover time, the time we spend in views has to be smaller than $\tau_0$.
  • For $e < 0$ means that we estimate the epoch switchover to be too early. Therefore, we should be slowing down and spend more than $\tau_0$ in the following views.

Reasoning:

The desired idealized system behaviour would a constant view duration $\tau_0$ throughout the entire epoch.

However, in the real-world system we have disturbances (varying message relay times, slow or offline nodes, etc) and measurement uncertainty (node can only observe its local view times, but not the committee’s collective swarm behaviour).

After a disturbance, we want the controller to drive the system back to a state, where it can closely follow the ideal behaviour from there on.

  • Simulations have shown that this approach produces very stable controller with the intended behaviour.

    Controller driving $e := \gamma - \Gamma \rightarrow 0$

    • setting the differential term $K_d=0$, the controller responds as expected with damped oscillatory behaviour to a singular strong disturbance. Setting $K_d=3$ suppresses oscillations and the controller's performance improves as it responds more effectively.

    • controller very quickly compensates for moderate disturbances and observational noise in a well-behaved system:

    • controller compensates massive anomaly (100s network partition) effectively:

    • controller effectively stabilizes system with continued larger disturbances (20% of offline consensus participants) and notable observational noise:

    References:

Detailed PID controller specification

Each consensus participant runs a local instance of the controller described below. Hence, all the quantities are based on the node’s local observation.

Definitions

Observables (quantities provided to the node or directly measurable by the node):

  • $v$ is the node’s current view
  • ideal view time $\tau_0$ is computed solely based on the Epoch configuration: $\tau_0 := \frac{<{\rm total\ epoch\ time}>}{<{\rm total\ views\ in\ epoch}>}$ (for mainnet 22, Epoch 75, we have $\tau_0 \simeq$ 1250ms).
  • $t[v]$ is the time the node entered view $v$
  • $F[v]$ is the final view of the current epoch
  • $T[v]$ is the target end time of the current epoch

Derived quantities

  • remaining views of the epoch $k[v] := F[v] +1 - v$
  • time remaining until the desired epoch switchover $\Gamma[v] := T[v]-t[v]$
  • error $e[v] := \underbrace{k\cdot\tau_0}_{\gamma[v]} - \Gamma[v] = t[v] + k\cdot\tau_0 - T[v]$
Precise convention of View Timing

Upon observing block B with view $v$, the controller updates its internal state.

Note the '+1' term in the computation of the remaining views $k[v] := F[v] +1 - v$ . This is related to our convention that the epoch begins (happy path) when observing the first block of the epoch. Only by observing this block, the nodes transition to the first view of the epoch. Up to that point, the consensus replicas remain in the last view of the previous epoch, in the state of having processed the last block of the old epoch and voted for it (happy path). Replicas remain in this state until they see a confirmation of the view (either QC or TC for the last view of the previous epoch).

In accordance with this convention, observing the proposal for the last view of an epoch, marks the start of the last view. By observing the proposal, nodes enter the last view, verify the block, vote for it, the primary aggregates the votes, constructs the child (for first view of new epoch). The last view of the epoch ends, when the child proposal is published.

Controller

The goal of the controller is to drive the system towards an error of zero, i.e. $e[v] \rightarrow 0$. For a PID controller, the output $u$ for view $v$ has the form:

u[v] = K_p \cdot e[v]+K_i \cdot \mathcal{I}[v] + K_d \cdot \Delta[v]

With error terms (computed from observations)

  • $e[v]$ representing the instantaneous error as of view $v$ (commonly referred to as ‘proportional term’)
  • $\mathcal{I} [v] = \sum_v e[v]$ the sum of the errors (commonly referred to as ‘integral term’)
  • $\Delta[v]=e[v]-e[v-1]$ the rate of change of the error (commonly referred to as ‘derivative term’)

and controller parameters (values derived from controller tuning):

  • $K_p$ be the proportional coefficient
  • $K_i$ be the integral coefficient
  • $K_d$ be the derivative coefficient

Measuring view duration

Each consensus participant observes the error $e[v]$ based on its local view evolution. As the following figure illustrates, the view duration is highly variable on small time scales.

Therefore, we expect $e[v]$ to be very variable. Furthermore, note that a node uses its local view transition times as an estimator for the collective behaviour of the entire committee. Therefore, there is also observational noise obfuscating the underlying collective behaviour. Hence, we expect notable noise.

Managing noise

Noisy values for $e[v]$ also impact the derivative term $\Delta[v]$ and integral term $\mathcal{I}[v]$. This can impact the controller’s performance.

Managing noise in the proportional term

An established approach for managing noise in observables is to use exponentially weighted moving average [EWMA] instead of the instantaneous values. Specifically, let $\bar{e}[v]$ denote the EWMA of the instantaneous error, which is computed as follows:

\eqalign{
\textnormal{initialization: }\quad \bar{e} :&= 0 \\
\textnormal{update with instantaneous error\ } e[v]:\quad \bar{e}[v] &= \alpha \cdot e[v] + (1-\alpha)\cdot \bar{e}[v-1]
}

The parameter $\alpha$ relates to the averaging time window. Let $\alpha \equiv \frac{1}{N_\textnormal{ewma}}$ and consider that the input changes from $x_\textnormal{old}$ to $x_\textnormal{new}$ as a step function. Then $N_\textnormal{ewma}$ is the number of samples required to move the output average about 2/3 of the way from $x_\textnormal{old}$ to $x_\textnormal{new}$.

see also Python Ewma implementation

Managing noise in the integral term

In particular systematic observation bias are a problem, as it leads to a diverging integral term. The commonly adopted approach is to use a ‘leaky integrator’ [1, 2], which we denote as $\bar{\mathcal{I}}[v]$.

\eqalign{
\textnormal{initialization: }\quad \bar{\mathcal{I}} :&= 0 \\
\textnormal{update with instantaneous error\ } e[v]:\quad \bar{\mathcal{I}}[v] &= e[v] + (1-\beta)\cdot\bar{\mathcal{I}}[v-1]
}

Intuitively, the loss factor $\beta$ relates to the time window of the integrator. A factor of 0 means an infinite time horizon, while $\beta =1$ makes the integrator only memorize the last input. Let $\beta \equiv \frac{1}{N_\textnormal{itg}}$ and consider a constant input value $x$. Then $N_\textnormal{itg}$ relates to the number of past samples that the integrator remembers:

  • the integrators output will saturate at $x\cdot N_\textnormal{itg}$
  • an integrator initialized with 0, reaches 2/3 of the saturation value $x\cdot N_\textnormal{itg}$ after consuming $N_\textnormal{itg}$ inputs

see also Python LeakyIntegrator implementation

Managing noise in the derivative term

Similarly to the proportional term, we apply an EWMA to the differential term and denote the averaged value as $\bar{\Delta}[v]$:

\eqalign{
\textnormal{initialization: }\quad \bar{\Delta} :&= 0 \\
\textnormal{update with instantaneous error\ } e[v]:\quad \bar{\Delta}[v] &= \bar{e}[v] - \bar{e}[v-1]
}

Final formula for PID controller

We have used a statistical model of the view duration extracted from mainnet 22 (Epoch 75) and manually added disturbances and observational noise and systemic observational bias.

The following parameters have proven to generate stable controller behaviour over a large variety of network conditions:

👉 The controller is given by

u[v] = K_p \cdot \bar{e}[v]+K_i \cdot \bar{\mathcal{I}}[v] + K_d \cdot \bar{\Delta}[v]

with parameters:

  • $K_p = 2.0$
  • $K_i = 0.6$
  • $K_d = 3.0$
  • $N_\textnormal{ewma} = 5$, i.e. $\alpha = \frac{1}{N_\textnormal{ewma}} = 0.2$
  • $N_\textnormal{itg} = 50$, i.e. $\beta = \frac{1}{N_\textnormal{itg}} = 0.02$

The controller output $u[v]$ represents the amount of time by which the controller wishes to deviate from the ideal view duration $\tau_0$. In other words, the duration of view $v$ that the controller wants to set is

\widehat{\tau}[v] = \tau_0 - u[v]

For further details about

Limits of authority

In general, there is no bound on the output of the controller output $u$. However, it is important to limit the controller’s influence to keep $u$ within a sensible range.

  • upper bound on view duration $\widehat{\tau}[v]$ that we allow the controller to set:

    The current timeout threshold is set to 2.5s. Therefore, the largest view duration we want to allow the controller to set is 1.6s. Thereby, approx. 900ms remain for message propagation, voting and constructing the child block, which will prevent the controller to drive the node into timeout with high probability.

  • lower bound on the view duration:

    Let $t_\textnormal{p}[v]$ denote the time when the primary for view $v$ has constructed its block proposal. The time difference $t_\textnormal{p}[v] - t[v]$ between the primary entering the view and having its proposal ready is the minimally required time to execute the protocol. The controller can only delay broadcasting the block, but it cannot release the block before $t_\textnormal{p}[v]$ simply because the proposal isn’t ready any earlier.

👉 Let $\hat{t}[v]$ denote the time when the primary for view $v$ broadcasts its proposal. We assign:

\hat{t}[v] := \max\big(t[v] +\min(\widehat{\tau}[v],\ 2\textnormal{s}),\  t_\textnormal{p}[v]\big)

Edge Cases

A node is catching up

When a node is catching up, it processes blocks more quickly than when it is up-to-date, and therefore observes a faster view rate. This would cause the node’s BlockRateManager to compensate by increasing the block rate delay.

As long as delay function is responsive, it doesn’t have a practical impact, because nodes catching up don’t propose anyway.

To the extent the delay function is not responsive, this would cause the block rate to slow down slightly, when the node is caught up.

Assumption: as we assume that only a smaller fraction of nodes go offline, the effect is expected to be small and easily compensated for by the supermajority of online nodes.

A node has a misconfigured clock

Cap the maximum deviation from the default delay (limits the general impact of error introduced by the BlockTimeController). The node with misconfigured clock will contribute to the error in a limited way, but as long as the majority of nodes have an accurate clock, they will offset this error.

Assumption: few enough nodes will have a misconfigured clock, that the effect will be small enough to be easily compensated for by the supermajority of correct nodes.

Near epoch boundaries

We might incorrectly compute high error in the target view rate, if local current view and current epoch are not exactly synchronized. By default, they would not be, because EpochTransition events occur upon finalization, and current view is updated as soon as QC/TC is available.

Solution: determine epoch locally based on view only, do not use EpochTransition event.

EFM

We need to detect EFM and revert to a default block-rate-delay (stop adjusting).

Testing

Cruise Control: Benchnet Testing Notes

Documentation

Overview

Package cruisectl implements a "cruise control" system for Flow by adjusting nodes' latest ProposalTiming in response to changes in the measured view rate and target epoch switchover time.

It uses a PID controller with the projected epoch switchover time as the process variable and the set-point computed using epoch length config. The error is the difference between the projected epoch switchover time, assuming an ideal view time τ, and the target epoch switchover time (based on a schedule).

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BlockTimeController 

type BlockTimeController struct {
	component.Component
	protocol.Consumer // consumes protocol state events
	// contains filtered or unexported fields
}

BlockTimeController dynamically adjusts the ProposalTiming of this node, based on the measured view rate of the consensus committee as a whole, in order to achieve a desired switchover time for each epoch. In a nutshell, the controller outputs the block time on the happy path, i.e.

  • Suppose the node is observing the parent block B0 at some time `x0`.
  • The controller determines the duration `d` of how much later the child block B1 should be observed by the committee.
  • The controller internally memorizes the latest B0 it has seen and outputs the tuple `(B0, x0, d)`

This low-level controller output `(B0, x0, d)` is wrapped into a `ProposalTiming` interface, specifically `happyPathBlockTime` on the happy path. The purpose of the `ProposalTiming` wrapper is to translate the raw controller output into a form that is useful for the EventHandler. Edge cases, such as initialization or epoch fallback are implemented by other implementations of `ProposalTiming`.

func NewBlockTimeController 

func NewBlockTimeController(log zerolog.Logger, metrics module.CruiseCtlMetrics, config *Config, state protocol.State, curView uint64) (*BlockTimeController, error)

NewBlockTimeController returns a new BlockTimeController.

func (*BlockTimeController) EpochEmergencyFallbackTriggered 

func (ctl *BlockTimeController) EpochEmergencyFallbackTriggered()

EpochEmergencyFallbackTriggered responds to epoch fallback mode being triggered.

func (*BlockTimeController) EpochSetupPhaseStarted 

func (ctl *BlockTimeController) EpochSetupPhaseStarted(_ uint64, first *flow.Header)

EpochSetupPhaseStarted responds to the EpochSetup phase starting for the current epoch. The event is queued for async processing by the worker.

func (*BlockTimeController) GetProposalTiming 

func (ctl *BlockTimeController) GetProposalTiming() ProposalTiming

GetProposalTiming returns the controller's latest ProposalTiming. Concurrency safe.

func (*BlockTimeController) OnBlockIncorporated 

func (ctl *BlockTimeController) OnBlockIncorporated(block *model.Block)

OnBlockIncorporated listens to notification from HotStuff about incorporating new blocks. The event is queued for async processing by the worker. If the channel is full, the event is discarded - since we are taking an average it doesn't matter if we occasionally miss a sample.

func (*BlockTimeController) TargetPublicationTime 

func (ctl *BlockTimeController) TargetPublicationTime(proposalView uint64, timeViewEntered time.Time, parentBlockId flow.Identifier) time.Time

type Config 

type Config struct {
	TimingConfig
	ControllerParams
}

Config defines configuration for the BlockTimeController.

func DefaultConfig 

func DefaultConfig() *Config

DefaultConfig returns the default config for the BlockTimeController.

type ControllerParams 

type ControllerParams struct {
	// N_ewma defines how historical measurements are incorporated into the EWMA for the proportional error term.
	// Intuition: Suppose the input changes from x to y instantaneously:
	//  - N_ewma is the number of samples required to move the EWMA output about 2/3 of the way from x to y
	// Per convention, this must be a _positive_ integer.
	N_ewma uint

	// N_itg defines how historical measurements are incorporated into the integral error term.
	// Intuition: For a constant error x:
	//  - the integrator value will saturate at `x•N_itg`
	//  - an integrator initialized at 0 reaches 2/3 of the saturation value after N_itg samples
	// Per convention, this must be a _positive_ integer.
	N_itg uint

	// KP, KI, KD, are the coefficients to the PID controller and define its response.
	// KP adjusts the proportional term (responds to the magnitude of error).
	// KI adjusts the integral term (responds to the error sum over a recent time interval).
	// KD adjusts the derivative term (responds to the rate of change, i.e. time derivative, of the error).
	KP, KI, KD float64
}

ControllerParams specifies the BlockTimeController's internal parameters.

type Ewma 

type Ewma struct {
	// contains filtered or unexported fields
}

Ewma implements the exponentially weighted moving average with smoothing factor α. The Ewma is a filter commonly applied to time-discrete signals. Mathematically, it is represented by the recursive update formula 

value ← α·v + (1-α)·value

where `v` the next observation. Intuitively, the loss factor `α` relates to the time window of N observations that we average over. For example, let α ≡ 1/N and consider an input that suddenly changes from x to y as a step function. Then N is _roughly_ the number of samples required to move the output average about 2/3 of the way from x to y. For numeric stability, we require α to satisfy 0 < a < 1. Not concurrency safe.

func NewEwma 

func NewEwma(alpha, initialValue float64) (Ewma, error)

NewEwma instantiates a new exponentially weighted moving average. The smoothing factor `alpha` relates to the averaging time window. Let `alpha` ≡ 1/N and consider an input that suddenly changes from x to y as a step function. Then N is roughly the number of samples required to move the output average about 2/3 of the way from x to y. For numeric stability, we require `alpha` to satisfy 0 < `alpha` < 1.

func (*Ewma) AddObservation 

func (e *Ewma) AddObservation(v float64) float64

AddObservation adds the value `v` to the EWMA. Returns the updated value.

func (*Ewma) AddRepeatedObservation 

func (e *Ewma) AddRepeatedObservation(v float64, k int) float64

AddRepeatedObservation adds k consecutive observations with the same value v. Returns the updated value.

func (*Ewma) Value 

func (e *Ewma) Value() float64

type LeakyIntegrator 

type LeakyIntegrator struct {
	// contains filtered or unexported fields
}

LeakyIntegrator is a filter commonly applied to time-discrete signals. Intuitively, it sums values over a limited time window. This implementation is parameterized by the loss factor `ß`: 

value ← v + (1-ß)·value

where `v` the next observation. Intuitively, the loss factor `ß` relates to the time window of N observations that we integrate over. For example, let ß ≡ 1/N and consider a constant input x:

  • the integrator value will saturate at x·N
  • an integrator initialized at 0 reaches 2/3 of the saturation value after N samples

For numeric stability, we require ß to satisfy 0 < ß < 1. Further details on Leaky Integrator: https://www.music.mcgill.ca/~gary/307/week2/node4.html Not concurrency safe.

func NewLeakyIntegrator 

func NewLeakyIntegrator(beta, initialValue float64) (LeakyIntegrator, error)

NewLeakyIntegrator instantiates a new leaky integrator with loss factor `beta`, where `beta relates to window of N observations that we integrate over. For example, let `beta` ≡ 1/N and consider a constant input x. The integrator value will saturate at x·N. An integrator initialized at 0 reaches 2/3 of the saturation value after N samples. For numeric stability, we require `beta` to satisfy 0 < `beta` < 1.

func (*LeakyIntegrator) AddObservation 

func (e *LeakyIntegrator) AddObservation(v float64) float64

AddObservation adds the value `v` to the LeakyIntegrator. Returns the updated value.

func (*LeakyIntegrator) AddRepeatedObservation 

func (e *LeakyIntegrator) AddRepeatedObservation(v float64, k int) float64

AddRepeatedObservation adds k consecutive observations with the same value v. Returns the updated value.

func (*LeakyIntegrator) Value 

func (e *LeakyIntegrator) Value() float64

type ProposalTiming 

type ProposalTiming interface {
	hotstuff.ProposalDurationProvider

	// ObservationView returns the view of the observation that the controller
	// processed and generated this ProposalTiming instance in response.
	ObservationView() uint64

	// ObservationTime returns the time, when the controller received the
	// leading to the generation of this ProposalTiming instance.
	ObservationTime() time.Time
}

ProposalTiming encapsulates the output of the BlockTimeController. On the happy path, the controller observes a block and generates a specific ProposalTiming in response. For the happy path, the ProposalTiming describes when the child proposal should be broadcast. However, observations other than blocks might also be used to instantiate ProposalTiming objects, e.g. controller instantiation, a disabled controller, etc. The purpose of ProposalTiming is to convert the controller output to timing information that the EventHandler understands. By convention, ProposalTiming should be treated as immutable.

type TimedBlock 

type TimedBlock struct {
	Block        *model.Block
	TimeObserved time.Time // timestamp when BlockTimeController received the block, per convention in UTC
}

TimedBlock represents a block, with a timestamp recording when the BlockTimeController received the block

type TimingConfig 

type TimingConfig struct {
	// FallbackProposalDelay is the minimal block construction delay. When used, it behaves like the
	// old command line flag `block-rate-delay`. Specifically, the primary measures the duration from
	// starting to construct its proposal to the proposal being ready to be published. If this
	// duration is _less_ than FallbackProposalDelay, the primary delays broadcasting its proposal
	// by the remainder needed to reach `FallbackProposalDelay`
	// It is used:
	//  - when Enabled is false
	//  - when epoch fallback has been triggered
	FallbackProposalDelay *atomic.Duration

	// MaxViewDuration is a hard maximum on the total view time targeted by ProposalTiming.
	// If the BlockTimeController computes a larger desired ProposalTiming value
	// based on the observed error and tuning, this value will be used instead.
	MaxViewDuration *atomic.Duration

	// MinViewDuration  is a hard maximum on the total view time targeted by ProposalTiming.
	// If the BlockTimeController computes a smaller desired ProposalTiming value
	// based on the observed error and tuning, this value will be used instead.
	MinViewDuration *atomic.Duration

	// Enabled defines whether responsive control of the GetProposalTiming is enabled.
	// When disabled, the FallbackProposalDelay is used.
	Enabled *atomic.Bool
}

TimingConfig specifies the BlockTimeController's limits of authority.

func (TimingConfig) GetEnabled 

func (ctl TimingConfig) GetEnabled() bool

GetEnabled returns whether the controller is enabled.

func (TimingConfig) GetFallbackProposalDuration 

func (ctl TimingConfig) GetFallbackProposalDuration() time.Duration

GetFallbackProposalDuration returns the proposal duration used when Cruise Control is not active.

func (TimingConfig) GetMaxViewDuration 

func (ctl TimingConfig) GetMaxViewDuration() time.Duration

GetMaxViewDuration returns the max view duration returned by the controller.

func (TimingConfig) GetMinViewDuration 

func (ctl TimingConfig) GetMinViewDuration() time.Duration

GetMinViewDuration returns the min view duration returned by the controller.

func (TimingConfig) SetEnabled 

func (ctl TimingConfig) SetEnabled(enabled bool) error

SetEnabled sets whether the controller is enabled.

func (TimingConfig) SetFallbackProposalDuration 

func (ctl TimingConfig) SetFallbackProposalDuration(dur time.Duration) error

SetFallbackProposalDuration sets the proposal duration used when Cruise Control is not active.

func (TimingConfig) SetMaxViewDuration 

func (ctl TimingConfig) SetMaxViewDuration(dur time.Duration) error

SetMaxViewDuration sets the max view duration returned by the controller.

func (TimingConfig) SetMinViewDuration 

func (ctl TimingConfig) SetMinViewDuration(dur time.Duration) error

SetMinViewDuration sets the min view duration returned by the controller.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.