Documentation
¶
Overview ¶
Package inputbuffer handles the input buffer of change point analysis.
Index ¶
- Constants
- func LegacyV2DecodeInto(history *History, reader *bytes.Reader) error
- func MergeOrderedRuns(aRuns, bRuns []Run, dest *[]*Run)
- func VerifyRunsOrdered(runs []*Run) error
- type Buffer
- func (ib *Buffer) Clear()
- func (ib *Buffer) CompactIfRequired()
- func (ib *Buffer) Copy() *Buffer
- func (ib *Buffer) EvictionRange() (shouldEvict bool, endIndex int)
- func (ib *Buffer) InsertRun(r Run)
- func (ib *Buffer) MergeBuffer(destination *[]*Run)
- func (ib *Buffer) Segmentize(history []*Run, changePoints []ChangePoint) *SegmentedInputBuffer
- func (ib *Buffer) Size() int
- type ChangePoint
- type EvictedSegment
- type History
- type HistorySerializer
- type ResultCounts
- type Run
- func VerdictRefs(positions, total, hasUnexpected []int) []*Run
- func Verdicts(positions, total, hasUnexpected []int) []Run
- func VerdictsWithRetries(positions, total, hasUnexpected, retried, unexpectedAfterRetry []int) []Run
- func VerdictsWithRetriesRefs(positions, total, hasUnexpected, retried, unexpectedAfterRetry []int) []*Run
- type Segment
- type SegmentedInputBuffer
Constants ¶
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 )
const (
// The version of the encoding to encode the verdict history.
LegacyV2EncodingVersion = 2
)
Variables ¶
This section is empty.
Functions ¶
func LegacyV2DecodeInto ¶
LegacyV2DecodeInto decodes the verdicts in buf, populating the history object.
func MergeOrderedRuns ¶
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 ¶
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 NewWithCapacity ¶
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) EvictionRange ¶
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 ¶
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 ¶
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).
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) EvictBefore ¶
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 VerdictsWithRetries ¶
func VerdictsWithRetriesRefs ¶
func (Run) IsSimpleExpectedPass ¶
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.
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:
- 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.
- 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.
Source Files