rtree

Documentation

Index

• func NeedsMerge(left, right *RangeStats, splitSizeBytes, splitKeyCount uint64) bool
• func ZapRanges(ranges []Range) zapcore.Field
• type IncompleteRangesFetcher
  • func (iter *IncompleteRangesFetcher) GetIncompleteRanges() []Range
  • func (iter *IncompleteRangesFetcher) Len() int
• type ProgressRange
  • func (pr *ProgressRange) Less(than *ProgressRange) bool
• type ProgressRangeTree
  • func NewProgressRangeTree() ProgressRangeTree
  • func (rangeTree *ProgressRangeTree) FindContained(startKey, endKey []byte) (*ProgressRange, error)
  • func (rangeTree *ProgressRangeTree) Insert(pr *ProgressRange) error
  • func (rangeTree *ProgressRangeTree) Iter() *IncompleteRangesFetcher
• type Range
  • func (rg *Range) BytesAndKeys() (bytes, keys uint64)
  • func (rg *Range) Contains(key []byte) bool
  • func (rg *Range) ContainsRange(startKey, endKey []byte) bool
  • func (rg *Range) Intersect(start, end []byte) (subStart, subEnd []byte, isIntersect bool)
  • func (rg *Range) Less(than btree.Item) bool
  • func (rg Range) String() string
• type RangeStats
  • func (rg *RangeStats) Less(ta *RangeStats) bool
• type RangeStatsTree
  • func NewRangeStatsTree() RangeStatsTree
  • func (rangeTree *RangeStatsTree) InsertRange(rg *Range, rangeSize, rangeCount uint64) *RangeStats
  • func (rangeTree *RangeStatsTree) MergedRanges(splitSizeBytes, splitKeyCount uint64) []RangeStats
• type RangeTree
  • func NewRangeTree() RangeTree
  • func (rangeTree *RangeTree) Find(rg *Range) *Range
  • func (rangeTree *RangeTree) GetIncompleteRange(startKey, endKey []byte) []Range
  • func (rangeTree *RangeTree) InsertRange(rg Range) *Range
  • func (rangeTree *RangeTree) Put(startKey, endKey []byte, files []*backuppb.File)
  • func (rangeTree *RangeTree) Update(rg Range)

Functions

func NeedsMerge

func NeedsMerge(left, right *RangeStats, splitSizeBytes, splitKeyCount uint64) bool

NeedsMerge checks whether two ranges needs to be merged.

func ZapRanges

func ZapRanges(ranges []Range) zapcore.Field

ZapRanges make zap fields for logging Range slice.

Types

type IncompleteRangesFetcher

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

func (*IncompleteRangesFetcher) GetIncompleteRanges

func (iter *IncompleteRangesFetcher) GetIncompleteRanges() []Range

func (*IncompleteRangesFetcher) Len

func (iter *IncompleteRangesFetcher) Len() int

type ProgressRange

type ProgressRange struct {
	Res        RangeTree
	Incomplete []Range
	Origin     Range
	GroupKey   string
}

func (*ProgressRange) Less

func (pr *ProgressRange) Less(than *ProgressRange) bool

Less impls btree.Item.

type ProgressRangeTree

type ProgressRangeTree struct {
	*btree.BTreeG[*ProgressRange]
}

ProgressRangeTree is a sorted tree for ProgressRanges. All the progress ranges it sorted do not overlap.

func NewProgressRangeTree

func NewProgressRangeTree() ProgressRangeTree

NewProgressRangeTree returns an empty range tree.

func (*ProgressRangeTree) FindContained

func (rangeTree *ProgressRangeTree) FindContained(startKey, endKey []byte) (*ProgressRange, error)

FindContained finds if there is a progress range containing the key range [startKey, endKey).

func (*ProgressRangeTree) Insert

func (rangeTree *ProgressRangeTree) Insert(pr *ProgressRange) error

Insert inserts a ProgressRange into the tree, it will return an error if there is a overlapping range.

func (*ProgressRangeTree) Iter

func (rangeTree *ProgressRangeTree) Iter() *IncompleteRangesFetcher

type Range

type Range struct {
	StartKey []byte
	EndKey   []byte
	Files    []*backuppb.File
}

Range represents a backup response.

func (*Range) BytesAndKeys

func (rg *Range) BytesAndKeys() (bytes, keys uint64)

BytesAndKeys returns total bytes and keys in a range.

func (*Range) Contains

func (rg *Range) Contains(key []byte) bool

Contains check if the range contains the given key, [start, end).

func (*Range) ContainsRange

func (rg *Range) ContainsRange(startKey, endKey []byte) bool

ContainsRange check if the range contains the region's key range.

func (*Range) Intersect

func (rg *Range) Intersect(
	start, end []byte,
) (subStart, subEnd []byte, isIntersect bool)

Intersect returns intersect range in the tree.

func (*Range) Less

func (rg *Range) Less(than btree.Item) bool

Less impls btree.Item.

func (Range) String

func (rg Range) String() string

String formats a range to a string.

type RangeStats

type RangeStats struct {
	Range
	Size  uint64
	Count uint64
}

RangeStats represents a restore merge result.

func (*RangeStats) Less

func (rg *RangeStats) Less(ta *RangeStats) bool

Less impls btree.Item.

type RangeStatsTree

type RangeStatsTree struct {
	*btree.BTreeG[*RangeStats]
}

func NewRangeStatsTree

func NewRangeStatsTree() RangeStatsTree

func (*RangeStatsTree) InsertRange

func (rangeTree *RangeStatsTree) InsertRange(rg *Range, rangeSize, rangeCount uint64) *RangeStats

InsertRange inserts ranges into the range tree. It returns a non-nil range if there are soe overlapped ranges.

func (*RangeStatsTree) MergedRanges

func (rangeTree *RangeStatsTree) MergedRanges(splitSizeBytes, splitKeyCount uint64) []RangeStats

MergedRanges output the sortedRanges having merged according to given `splitSizeBytes` and `splitKeyCount`.

type RangeTree

type RangeTree struct {
	*btree.BTree
}

RangeTree is sorted tree for Ranges. All the ranges it stored do not overlap.

func NewRangeTree

func NewRangeTree() RangeTree

NewRangeTree returns an empty range tree.

func (*RangeTree) Find

func (rangeTree *RangeTree) Find(rg *Range) *Range

Find is a helper function to find an item that contains the range start key.

func (*RangeTree) GetIncompleteRange

func (rangeTree *RangeTree) GetIncompleteRange(
	startKey, endKey []byte,
) []Range

GetIncompleteRange returns missing range covered by startKey and endKey.

func (*RangeTree) InsertRange

func (rangeTree *RangeTree) InsertRange(rg Range) *Range

InsertRange inserts ranges into the range tree. It returns a non-nil range if there are soe overlapped ranges.

func (*RangeTree) Put

func (rangeTree *RangeTree) Put(
	startKey, endKey []byte, files []*backuppb.File,
)

Put forms a range and inserts it into tree.

func (*RangeTree) Update

func (rangeTree *RangeTree) Update(rg Range)

Update inserts range into tree and delete overlapping ranges.