inputbuffer

package
v0.0.0-...-5b2b182 Latest Latest
Warning

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

Go to latest
Published: Dec 3, 2024 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Overview

Package inputbuffer handles the input buffer of change point analysis.

Index

Constants

View Source
const (
	// The version of the encoding to encode the run history.
	EncodingVersion = 3
	// Capacity of the hot buffer, i.e. how many runs it can hold.
	DefaultHotBufferCapacity = 100
	// Capacity of the cold buffer, i.e. how many runs it can hold.
	DefaultColdBufferCapacity = 2000
	// RunsInsertedHint is the number of test expected
	// to be inserted in one usage of the input buffer. Buffers
	// will be allocated assuming this is the maximum number
	// inserted, if the actual number is higher, it may trigger
	// additional memory allocations.
	//
	// Currently a value of 100 is used as ingestion process ingests one
	// verdict at a time, which may consist of up to 100 runs.
	RunsInsertedHint = 100
)
View Source
const (
	// The version of the encoding to encode the verdict history.
	LegacyV2EncodingVersion = 2
)

Variables

This section is empty.

Functions

func LegacyV2DecodeInto

func LegacyV2DecodeInto(history *History, reader *bytes.Reader) error

LegacyV2DecodeInto decodes the verdicts in buf, populating the history object.

func MergeOrderedRuns

func MergeOrderedRuns(aRuns, bRuns []Run, dest *[]*Run)

MergeOrderedRuns merges two sets of runs into a destination slice, assuming that both slices are sorted by commit position (oldest first), and then by result time (oldest first).

The result will be a slice of runs which is pointers into the original aRuns and bRuns slices. Any modification to aRuns or bRuns will invalidate the result.

func VerifyRunsOrdered

func VerifyRunsOrdered(runs []*Run) error

Types

type Buffer

type Buffer struct {
	// Capacity of the hot buffer. If it is full, the content will be written
	// into the cold buffer.
	HotBufferCapacity int
	HotBuffer         History
	// Capacity of the cold buffer.
	ColdBufferCapacity int
	ColdBuffer         History
	// IsColdBufferDirty will be set to true if the cold buffer is dirty.
	// This means we need to write the cold buffer to Spanner.
	IsColdBufferDirty bool
}

func New

func New() *Buffer

New allocates an empty input buffer with default capacity.

func NewWithCapacity

func NewWithCapacity(hotBufferCapacity, coldBufferCapacity int) *Buffer

NewWithCapacity allocates an empty input buffer with the given capacity.

func (*Buffer) Clear

func (ib *Buffer) Clear()

Clear resets the input buffer to an empty state, similar to its state after New().

func (*Buffer) CompactIfRequired

func (ib *Buffer) CompactIfRequired()

CompactIfRequired moves the content from the hot buffer to the cold buffer, if:

  • the hot buffer is at capacity, or
  • the cold buffer is at capacity and an eviction from the cold buffer is going to be required (this case is important for buffers stored in legacy data formats, where the buffer may immediately be beyond its capacity). Note that eviction from the cold buffer requires the hot buffer to be empty.

If a compaction occurs, the IsColdBufferDirty flag will be set to true, implying that the cold buffer content needs to be written to Spanner.

Note: It is possible that the cold buffer overflows after the compaction, i.e., len(ColdBuffer.Runs) > ColdBufferCapacity. This needs to be handled separately.

func (*Buffer) Copy

func (ib *Buffer) Copy() *Buffer

Copy makes a deep copy of the input buffer.

func (*Buffer) EvictionRange

func (ib *Buffer) EvictionRange() (shouldEvict bool, endIndex int)

EvictionRange returns the part that should be evicted from cold buffer, due to overflow. Note: we never evict from the hot buffer due to overflow. Overflow from the hot buffer should cause compaction to the cold buffer instead. Returns: - a boolean (shouldEvict) to indicated if an eviction should occur. - a number (endIndex) for the eviction. The eviction will occur for range [0, endIndex (inclusively)]. Note that eviction can only occur after a compaction from hot buffer to cold buffer. It means the hot buffer is empty, and the cold buffer overflows.

func (*Buffer) InsertRun

func (ib *Buffer) InsertRun(r Run)

InsertRun inserts a new run into the input buffer.

The run is always inserted into the hot buffer, run CompactIfRequired as required after all runs have been inserted.

func (*Buffer) MergeBuffer

func (ib *Buffer) MergeBuffer(destination *[]*Run)

MergeBuffer merges the runs of the hot buffer and the cold buffer into the provided slice, resizing it if necessary. The returned slice will be sorted by commit position (oldest first), and then by result time (oldest first). Any changes to the input buffers will invalidate the slice, as it is built via pointers into the input buffer.

func (*Buffer) Segmentize

func (ib *Buffer) Segmentize(history []*Run, changePoints []ChangePoint) *SegmentedInputBuffer

Segmentize generates segments based on the input buffer and the change points detected. Input buffer runs are sorted by commit position (oldest first), then by result time (oldest first) and MUST have been returned by a call to MergeBuffer(...) immediately prior to this Segmentize call (i.e. without mutating the input buffer or the merge buffer.) changePoints is the change points for history. It is sorted in ascending order (smallest index first).

func (*Buffer) Size

func (ib *Buffer) Size() int

type ChangePoint

type ChangePoint struct {
	// NominalIndex is nominal index of the change point in history.
	NominalIndex int
	// PositionDistribution captures the distribution of possible change point
	// positions, in terms of source positions.
	PositionDistribution *model.PositionDistribution
}

ChangePoint records the index position of a change point, together with its position distribution.

type EvictedSegment

type EvictedSegment struct {
	// The state of the segment. Will be FINALIZING or FINALIZED.
	State cpb.SegmentState
	// Whether the segment is the first segment in the input buffer.
	HasStartChangepoint bool
	// The earliest commit position included in the segment.
	StartPosition int64
	// The earliest hour a run with the given start_position was recorded.
	StartHour time.Time
	// The end commit position of the segment.
	// Only set on FINALIZED segments where the end position is known.
	// If set, the invariant EndPosition >= StartPosition holds.
	EndPosition int64
	// The latest hour a run with the last commit position in the segment
	// was recorded.
	// Only set if EndPosition is set.
	EndHour time.Time
	// The distribution of possible starting changepoint positions.
	// Only set if HasStartChangepoint is set.
	StartPositionDistribution *model.PositionDistribution
	// The hour the most recent run with an unexpected test result
	// was produced.
	MostRecentUnexpectedResultHour time.Time
	// The runs which are being evicted. These correspond to the
	// Segment above. Runs are ordered oldest commit position first,
	// then oldest hour first.
	Runs []*Run
}

EvictedSegment represents a segment or segment part which was evicted from the input buffer.

A segment may be partially evicted for one or both of the following reasons:

  • The eviction is occuring because of limited input buffer space (not because of a finalized changepoint), so only a fraction of the segment needs to be evicted.
  • Previously, part of the segment was evicted (for the above reason), so subsequent evictions are necessarily only in relation to the remaining part of that segment.

The consumer generally does not need to be concerned about which of these cases applies, and should always process evicted segments in commit position order, merging them with any previously evicted finalizing segment in the output buffer (if any) (but not any previously evicted FINALIZED segment).

type History

type History struct {
	// Runs, sorted by commit position (oldest first), and
	// then result time (oldest first).
	Runs []Run
}

func (History) Copy

func (h History) Copy() History

Copy makes a deep copy of the History.

func (*History) EvictBefore

func (h *History) EvictBefore(index int)

EvictBefore removes all runs prior to (but not including) the given index.

This will modify the runs buffer in-place, existing subslices should be treated as invalid following this operation.

type HistorySerializer

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

HistorySerializer provides methods to decode and encode History objects. Methods on a given instance are only safe to call on one goroutine at a time.

func (*HistorySerializer) DecodeInto

func (hs *HistorySerializer) DecodeInto(history *History, buf []byte) error

DecodeInto decodes the runs in buf, populating the history object.

func (*HistorySerializer) Encode

func (hs *HistorySerializer) Encode(history History) []byte

Encode uses varint encoding to encode history into a byte array. See go/luci-test-variant-analysis-design for details.

type ResultCounts

type ResultCounts struct {
	// Number of passed result.
	PassCount int
	// Number of failed result.
	FailCount int
	// Number of crashed result.
	CrashCount int
	// Number of aborted result.
	AbortCount int
}

func (ResultCounts) Count

func (r ResultCounts) Count() int

type Run

type Run struct {
	// The commit position of the run.
	CommitPosition int64
	// The partition time for this run, truncated to the nearest hour.
	Hour time.Time
	// Counts for expected results.
	Expected ResultCounts
	// Counts for unexpected results.
	Unexpected ResultCounts
}

Run represents all tries of a test in a single invocation.

func VerdictRefs

func VerdictRefs(positions, total, hasUnexpected []int) []*Run

func Verdicts

func Verdicts(positions, total, hasUnexpected []int) []Run

func VerdictsWithRetries

func VerdictsWithRetries(positions, total, hasUnexpected, retried, unexpectedAfterRetry []int) []Run

func VerdictsWithRetriesRefs

func VerdictsWithRetriesRefs(positions, total, hasUnexpected, retried, unexpectedAfterRetry []int) []*Run

func (Run) IsSimpleExpectedPass

func (r Run) IsSimpleExpectedPass() bool

IsSimpleExpectedPass returns whether this run is a simple expected pass run or not. A simple expected pass run has only one test result, which is expected pass. This represents approximately ~97% of runs at time of writing and is a property levereged in the encoding of the input buffer.

type Segment

type Segment struct {
	// Start index in the input buffer history, inclusively.
	// As in the history slice, runs are store oldest first, so StartIndex
	// corresponds to the oldest run in the segment.
	StartIndex int
	// End index in the input buffer history, inclusively.
	// As in the history slice, runs are stored oldest first, so EndIndex
	// corresponds to the newest run in the segment.
	EndIndex int

	// Whether the segment is the first segment in the input buffer.
	HasStartChangepoint bool
	// The earliest commit position included in the segment.
	StartPosition int64
	// The earliest hour a run with the given StartPosition was recorded.
	StartHour time.Time
	// The end commit position of the segment. Always set.
	// The invariant EndPosition >= StartPosition holds.
	EndPosition int64
	// The latest hour a run with the last commit position in the segment
	// was recorded.
	EndHour time.Time
	// The distribution of possible starting changepoint positions.
	StartPositionDistribution *model.PositionDistribution

	// The hour the most recent run with an unexpected test result
	// was produced.
	MostRecentUnexpectedResultHour time.Time
}

Segment is a representation of segments in input buffer. It is only use in-memory. It will not be stored in spanner or bigquery.

func (*Segment) Length

func (s *Segment) Length() int

type SegmentedInputBuffer

type SegmentedInputBuffer struct {
	InputBuffer *Buffer
	// The Segments are disjoint and are sorted by StartIndex ascendingly.
	Segments []*Segment
}

SegmentedInputBuffer wraps the input buffer and the segments it contains.

func (*SegmentedInputBuffer) EvictSegments

func (sib *SegmentedInputBuffer) EvictSegments() []EvictedSegment

EvictSegments evicts segments from the segmented input buffer.

Returned EvictedSegments are sorted from the oldest commit position to the newest.

A segment will be evicted if:

  1. The changepoint that ends the segment has been finalized, because half of the input buffer is newer than the ending commit position). In this case, the entire remainder of the segment will be evicted.
  2. There is storage pressure in the input buffer (it is at risk of containing too many runs). In this case, a segment will be partially evicted, and that segment will be 'finalizing'.

Note that if the last segment evicted is a finalized segment, this function will add an extra finalizing segment to the end of evicted segments. This is to keep track of the confidence interval of the starting commit position of the segment after the finalized segment. It is needed because after a finalized segment is evicted, its runs disappear from the input buffer and we can no longer calculate the confidence interval of the start of the next segment.

As a result, the result of this function will contain all finalized segments, except for the last segment (if any), which is finalizing.

The segments remaining after eviction will be in sib.Segments.

If eviction occurs, the underlying input buffer will be modified and any cached versions of it (e.g. merged input buffer histories) should be treated as invalid.

Jump to

Keyboard shortcuts

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