Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ActionTimeoutExtractor ¶
type ActionTimeoutExtractor struct {
// contains filtered or unexported fields
}
ActionTimeoutExtractor is a helper type for extracting the execution timeout from an REv2 Action, taking configured default and maximum timeout values into account.
func NewActionTimeoutExtractor ¶
func NewActionTimeoutExtractor(defaultExecutionTimeout, maximumExecutionTimeout time.Duration) *ActionTimeoutExtractor
NewActionTimeoutExtractor creates a new ActionTimeoutExtractor using the parameters provided.
func (ActionTimeoutExtractor) ExtractTimeout ¶
func (e ActionTimeoutExtractor) ExtractTimeout(action *remoteexecution.Action) (time.Duration, error)
ExtractTimeout extracts the execution timeout field from an REv2 Action, converting it to a time.Duration. It returns errors in case the provided execution timeout is invalid or out of bounds.
type Analyzer ¶
type Analyzer interface {
// Analyze an REv2 Action. This operation should be called
// without holding any locks, as it may block.
//
// All methods called against the Selector that is returned and
// any Learners yielded from it should be called while holding a
// global lock.
Analyze(ctx context.Context, digestFunction digest.Function, action *remoteexecution.Action) (Selector, error)
}
Analyzer of REv2 Actions, determining which worker size class is the most suitable for running it, and what timeout to use.
func NewAnalyzerFromConfiguration ¶
func NewAnalyzerFromConfiguration(configuration *pb.InitialSizeClassAnalyzerConfiguration, previousExecutionStatsStore PreviousExecutionStatsStore) (Analyzer, error)
NewAnalyzerFromConfiguration creates a new initial size class analyzer based on options provided in a configuration file.
func NewFallbackAnalyzer ¶
func NewFallbackAnalyzer(actionTimeoutExtractor *ActionTimeoutExtractor) Analyzer
NewFallbackAnalyzer creates a simple Analyzer that runs all actions on the smallest size class. Upon failure, the action is retried on the largest size class.
This Analyzer is ideal for setups that only use a single size class, or if the number of actions that does not succeed on the smallest size cache is very low. Any more complex setup should use FeedbackDrivenAnalyzer.
func NewFeedbackDrivenAnalyzer ¶
func NewFeedbackDrivenAnalyzer(store PreviousExecutionStatsStore, randomNumberGenerator random.SingleThreadedGenerator, clock clock.Clock, actionTimeoutExtractor *ActionTimeoutExtractor, failureCacheDuration time.Duration, strategyCalculator StrategyCalculator, historySize int) Analyzer
NewFeedbackDrivenAnalyzer creates an Analyzer that selects the initial size class on which actions are run by reading previous execution stats from the Initial Size Class Cache (ISCC) and analyzing these results. Upon completion, stats in the ISCC are updated.
type Learner ¶
type Learner interface {
// The action completed successfully. The execution time is
// provided.
//
// If this method returns a nil Learner, the scheduler can
// finalize the operation entirely. If this method returns a new
// Learner, the scheduler is requested to run the action another
// time in the background, just for learning purposes. It is
// valid for the scheduler to already communicate completion to
// the client. The scheduler may limit the amount of work it's
// willing to run in the background.
Succeeded(duration time.Duration, sizeClasses []uint32) (sizeClass int, expectedDuration, timeout time.Duration, learner Learner)
// The action completed with a failure.
//
// If this method returns a nil Learner, the execution failure
// is definitive and should be propagated to the client. If this
// method returns a new Learner, execution must be retried on
// the largest size class, using the timeout that is returned.
Failed(timedOut bool) (expectedDuration, timeout time.Duration, learner Learner)
// Clients have abandoned the action, meaning that execution of
// the action was terminated. Nothing may be learned from this
// action.
Abandoned()
}
Learner for size class selection. The information provided by the scheduler to this object may allow the Analyzer and Selector to make more accurate predictions in the future.
type Outcomes ¶
type Outcomes struct {
// contains filtered or unexported fields
}
Outcomes of previous executions of an action. For successful outcomes, the execution times are stored in ascending order. For failures, a count is stored.
func NewOutcomes ¶
NewOutcomes creates a new Outcomes object that contains samples for successful and failed executions based on the arguments provided. This function takes ownership of the list of durations, sorting it in ascending order.
func (Outcomes) GetMedianExecutionTime ¶
GetMedianExecutionTime computes the median execution time of all of the successful outcomes. It may return nil in case no successful outcomes have been registered.
func (Outcomes) IsFaster ¶
IsFaster returns a probability in range (0.0, 1.0) of the current set of outcomes being faster than another one. The algorithm for this is to compute the average rank in B for every element in A, similar to the Mann-Whitney U test. This is done for two reasons:
- Analysis on mean or median values is not always possible, as a set of outcomes may contain (or consist only of) failures of which the execution time is unknown.
- When implemented properly, it is an asymmetric relation, in that x.IsFaster(x) == 0.5 and x.IsFaster(y) + y.IsFaster(x) == 1.0 for any sets of outcomes x and y.
This function works by running a 2-way merge algorithm against both sets of outcomes, awarding scores between [0, 2*len(B)] based on the rank in B for each of the elements in A, meaning a total score of 2*len(A)*len(B) may be earned. Inequality between elements always yields an even score. Odd scores may need to be given in case of identical values.
To ensure that the probability returned by this function doesn't become too extreme for small sample counts, we add 1+len(B) to A's score, and 1+len(A) to B's score. This also makes sure that empty sets don't cause divisions by zero, and that the probability never becomes exactly 0.0 or 1.0. The latter is important for PageRank computation, as eigenvalue computation wouldn't converge otherwise. It also causes smaller sets to get an advantage, which is important for ensuring that all size classes are tested sufficiently. This is similar in spirit to the "plus four" rule for computing confidence intervals.
type PreviousExecutionStatsHandle ¶
type PreviousExecutionStatsHandle re_blobstore.MutableProtoHandle[*iscc.PreviousExecutionStats]
PreviousExecutionStatsHandle refers to a single previous execution stats message read from the Initial Size Class Cache (ISCC).
type PreviousExecutionStatsStore ¶
type PreviousExecutionStatsStore re_blobstore.MutableProtoStore[*iscc.PreviousExecutionStats]
PreviousExecutionStatsStore is used by FeedbackDrivenAnalyzer to gain access to previous execution stats stored in the Initial Size Class Cache (ISCC).
type Selector ¶
type Selector interface {
// Given a list of size classes that are currently present,
// select a size class on which the action needs to be
// scheduled.
//
// The Selector can override the timeout of the action. When
// attempting to run an action on a smaller size class, it may
// be desirable to put a timeout in place that is based on
// previous execution times observed on larger size classes.
// This ensures that the system remains responsive, even in the
// case of mispredictions.
//
// A Learner is returned that the scheduler must use to
// communicate the outcome of the execution, so that future
// executions have a lower probability of making mispredictions.
Select(sizeClasses []uint32) (sizeClass int, expectedDuration, timeout time.Duration, learner Learner)
// Clients have abandoned the action, meaning that no size class
// selection decision needs to be made. This may, for example,
// happen if the action is deduplicated against one that is
// already running.
Abandoned()
}
Selector of a size class for an analyzed action.
type Strategy ¶
type Strategy struct {
// Probability between [0.0, 1.0] at which this strategy should
// be chosen. The sum of all probabilities returned by
// GetStrategies() should at most be 1.0. If the sum of all
// probabilities is less than 1.0, the remainder should be the
// probability of running the action on the largest size class.
Probability float64
// Whether the action has a high probability of failing. In that
// case it is preferable to run the action on the largest size
// class immediately, only running it on the smaller size class
// in the background afterwards.
RunInBackground bool
// The execution timeout to use when running this action in the
// foreground on this size class. For the largest size class,
// the original timeout value should be used.
//
// To obtain the execution timeout when running this action in
// the background, a separate call to
// GetBackgroundExecutionTimeout() needs to be made. This
// ensures that the latest obtained execution time of the
// foreground execution on the largest size class is taken into
// account when computing the timeout for the smaller size
// class.
ForegroundExecutionTimeout time.Duration
}
Strategy for running an action on a size class that is not the largest size class.
type StrategyCalculator ¶
type StrategyCalculator interface {
GetStrategies(perSizeClassStatsMap map[uint32]*iscc.PerSizeClassStats, sizeClasses []uint32, originalTimeout time.Duration) []Strategy
GetBackgroundExecutionTimeout(perSizeClassStatsMap map[uint32]*iscc.PerSizeClassStats, sizeClasses []uint32, sizeClassIndex int, originalTimeout time.Duration) time.Duration
}
StrategyCalculator is responsible for computing the probabilities for choosing to run an action on size classes. Given a list of n size classes, this function will return a list of n-1 strategies for running the action on the smaller size classes.
No strategy for the largest size class is returned, as both is probability and options can be inferred.
var SmallestSizeClassStrategyCalculator StrategyCalculator = smallestSizeClassStrategyCalculator{}
SmallestSizeClassStrategyCalculator implements a StrategyCalculator that always prefers running actions on the smallest size class.
This StrategyCalculator behaves similar to FallbackAnalyzer, with the main difference that it still causes execution times and outcomes to be tracked in the Initial Size Class Cache (ISCC).
func NewPageRankStrategyCalculator ¶
func NewPageRankStrategyCalculator(minimumExecutionTimeout time.Duration, acceptableExecutionTimeIncreaseExponent, timeoutMultiplier, maximumConvergenceError float64) StrategyCalculator
NewPageRankStrategyCalculator creates a StrategyCalculator that uses outcomes of previous executions to determine probabilities for running actions on a given set of size classes.
The algorithm that it uses to compute probabilities is similar to PageRank, in that it constructs a stochastic matrix of which the resulting eigenvector contains the probabilities.
Source Files