qtree

package
v4.15.0+incompatible Latest Latest
Warning

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

Go to latest
Published: Sep 17, 2018 License: GPL-3.0 Imports: 10 Imported by: 0

Documentation

Index

Constants

View Source
const ChanBufferSize = 4096
View Source
const DAY = 24 * HOUR
View Source
const HOUR = 60 * MINUTE
View Source
const KFACTOR = bstore.KFACTOR
View Source
const MICROSECOND = 1000
View Source
const MILLISECOND = 1000 * MICROSECOND
View Source
const MINUTE = 60 * SECOND
View Source
const MaximumTime = (48 << 56)
View Source
const MinimumTime = -(16 << 56)
View Source
const PWFACTOR = bstore.PWFACTOR
View Source
const ROOTPW = 56 //This makes each bucket at the root ~= 2.2 years
View Source
const ROOTSTART = -1152921504606846976 //This makes the 16th bucket start at 1970 (0)

so the root spans 146.23 years

View Source
const SECOND = 1000 * MILLISECOND

Variables

View Source
var ErrBadTimeRange error = errors.New("Invalid time range")

Functions

func ClampTime

func ClampTime(t int64, pw uint8) int64

Types

type ChangedRange

type ChangedRange struct {
	Valid bool
	Start int64
	End   int64
}

type QTree

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

func NewReadQTree

func NewReadQTree(ctx context.Context, bs *bstore.BlockStore, id uuid.UUID, generation uint64) (*QTree, bte.BTE)

*

  • Load a quasar tree

func NewWriteQTree

func NewWriteQTree(bs *bstore.BlockStore, id uuid.UUID) (*QTree, bte.BTE)

func (*QTree) Commit

func (tr *QTree) Commit() bte.BTE

func (*QTree) DeleteRange

func (tr *QTree) DeleteRange(start int64, end int64) bte.BTE

func (*QTree) FindChangedSince

func (tr *QTree) FindChangedSince(ctx context.Context, gen uint64, resolution uint8) (chan ChangedRange, chan bte.BTE)

func (*QTree) FindNearestValue

func (n *QTree) FindNearestValue(ctx context.Context, time int64, backwards bool) (Record, bte.BTE)

func (*QTree) Generation

func (n *QTree) Generation() uint64

func (*QTree) InsertValues

func (tr *QTree) InsertValues(records []Record) (e bte.BTE)

*

  • This function is for inserting a large chunk of data. It is required
  • that the data is sorted, so we do that here

func (*QTree) LoadNode

func (tr *QTree) LoadNode(ctx context.Context, addr uint64, impl_Generation uint64, impl_Pointwidth uint8, impl_StartTime int64) (*QTreeNode, bte.BTE)

func (*QTree) NewCoreNode

func (tr *QTree) NewCoreNode(startTime int64, pointWidth uint8) *QTreeNode

func (*QTree) NewVectorNode

func (tr *QTree) NewVectorNode(startTime int64, pointWidth uint8) *QTreeNode

func (*QTree) QueryStatisticalValues

func (tr *QTree) QueryStatisticalValues(ctx context.Context, start int64, end int64, pw uint8) (chan StatRecord, chan bte.BTE)

func (*QTree) QueryWindow

func (tr *QTree) QueryWindow(ctx context.Context, start int64, end int64, width uint64, depth uint8) (chan StatRecord, chan bte.BTE)

QueryWindow queries for windows between start and end, with an explicit (arbitrary) width. End is exclusive

func (*QTree) ReadStandardValuesCI

func (tr *QTree) ReadStandardValuesCI(ctx context.Context, start int64, end int64) (chan Record, chan bte.BTE)

start is inclusive, end is exclusive. To query a specific nanosecond, query (n, n+1)

type QTreeNode

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

func (*QTreeNode) ArbitraryStartTime

func (n *QTreeNode) ArbitraryStartTime(idx uint64, pw uint8) int64

func (*QTreeNode) AssertNewUpPatch

func (n *QTreeNode) AssertNewUpPatch() (*QTreeNode, error)

func (*QTreeNode) Child

func (n *QTreeNode) Child(ctx context.Context, i uint16) (*QTreeNode, bte.BTE)

func (*QTreeNode) ChildEndTime

func (n *QTreeNode) ChildEndTime(idx uint16) int64

func (*QTreeNode) ChildPW

func (n *QTreeNode) ChildPW() uint8

func (*QTreeNode) ChildStartTime

func (n *QTreeNode) ChildStartTime(idx uint16) int64

func (*QTreeNode) ClampBucket

func (n *QTreeNode) ClampBucket(t int64) uint16

func (*QTreeNode) ClampVBucket

func (n *QTreeNode) ClampVBucket(t int64, pw uint8) uint64

Unlike core nodes, vectors have infinitely many buckets. This function allows you to get a bucket idx for a time and an arbitrary point width

func (*QTreeNode) ConvertToCore

func (n *QTreeNode) ConvertToCore(newvals []Record) *QTreeNode

We need to create a core node, insert all the vector data into it, and patch up the parent

func (*QTreeNode) DeleteRange

func (n *QTreeNode) DeleteRange(start int64, end int64) *QTreeNode

func (*QTreeNode) EndTime

func (n *QTreeNode) EndTime() int64

func (*QTreeNode) FindChangedSince

func (n *QTreeNode) FindChangedSince(ctx context.Context, gen uint64, rchan chan ChangedRange, echan chan bte.BTE, resolution uint8) ChangedRange

TODO: consider deletes. I think that it will require checking if the generation of a core node is higher than all it's non-nil children. This implies that one or more children got deleted entirely, and then the node must report its entire time range as changed. it's not possible for a child to have an equal generation to the parent AND another node got deleted, as deletes and inserts do not get batched together. Also, if we know that a generation always corresponds to a contiguous range deletion (i.e we don't coalesce deletes) then we know that we couldn't have got a partial delete that bumped up a gen and masked another full delete. NOTE: We should return changes SINCE a generation, so strictly greater than. NOTE4: we have this chan + return value thing because we return the last range which is more probably going to be coalesced.

the stuff in the chan will also need coalescence but not as much

func (*QTreeNode) FindNearestValue

func (n *QTreeNode) FindNearestValue(ctx context.Context, time int64, backwards bool) (Record, bte.BTE)

It is important to note that if backwards is true, then time is exclusive. So if a record exists with t=80 and t=100, and you query with t=100, backwards=true, you will get the t=80 record. For forwards, time is inclusive.

func (*QTreeNode) FindParentIndex

func (n *QTreeNode) FindParentIndex() uint16

func (*QTreeNode) Free

func (n *QTreeNode) Free()

Although we keep caches of datablocks in the bstore, we can't actually free them until they are unreferenced. This dropcache actually just makes sure they are unreferenced

func (*QTreeNode) Generation

func (n *QTreeNode) Generation() uint64

func (*QTreeNode) HasChild

func (n *QTreeNode) HasChild(i uint16) bool

func (*QTreeNode) InsertValues

func (n *QTreeNode) InsertValues(records []Record) (*QTreeNode, error)

*

  • the process is:
  • call insertvalues - returns new QTreeNode.
  • this must have: address, stats
  • and it must have put whatever it touched in the generation
  • replace it in the child cache, change address + stats
  • and return to parent

func (*QTreeNode) MergeIntoVector

func (n *QTreeNode) MergeIntoVector(r []Record)

Here is where we would replace with fancy delta compression

func (*QTreeNode) OpCountMean

func (n *QTreeNode) OpCountMean() (uint64, float64)

func (*QTreeNode) OpMax

func (n *QTreeNode) OpMax() float64

func (*QTreeNode) OpMin

func (n *QTreeNode) OpMin() float64

func (*QTreeNode) OpReduce

func (n *QTreeNode) OpReduce(pointwidth uint8, index uint64) (uint64, float64, float64, float64)

ok so here is the problem. If we call opreduce on a core node, then we can only deliver pointwidths GREATER than our pointwidth and less than pointwidth + 6 right? but as a leaf we can potentially deliver pointwidths down to 0...

func (*QTreeNode) Parent

func (n *QTreeNode) Parent() *QTreeNode

func (*QTreeNode) PointWidth

func (n *QTreeNode) PointWidth() uint8

func (*QTreeNode) QueryStatisticalValues

func (n *QTreeNode) QueryStatisticalValues(ctx context.Context, rv chan StatRecord, err chan bte.BTE,
	start int64, end int64, pw uint8)

func (*QTreeNode) QueryWindow

func (n *QTreeNode) QueryWindow(ctx context.Context, end int64, nxtstart *int64, width uint64, depth uint8, rv chan StatRecord, rve chan bte.BTE, wctx *WindowContext)

QueryWindow queries this node for an arbitrary window of time. ctx must be initialized, especially with Time. Holes will be emitted as blank records

func (*QTreeNode) ReadStandardValuesCI

func (n *QTreeNode) ReadStandardValuesCI(ctx context.Context, rv chan Record, err chan bte.BTE,
	start int64, end int64)

func (*QTreeNode) SetChild

func (n *QTreeNode) SetChild(idx uint16, c *QTreeNode)

This function assumes that n is already new

func (*QTreeNode) StartTime

func (n *QTreeNode) StartTime() int64

func (*QTreeNode) ThisAddr

func (n *QTreeNode) ThisAddr() uint64

func (*QTreeNode) TreePath

func (n *QTreeNode) TreePath() string

func (*QTreeNode) WidthTime

func (n *QTreeNode) WidthTime() int64

So this might be the only explanation of how PW really relates to time: If the node is core, the node's PW is the log of the amount of time that each child covers. So a pw of 8 means that each child covers 1<<8 nanoseconds If the node is a vector, the PW represents what the PW would be if it were a core. It does NOT represent the PW of the vector itself.

type Record

type Record struct {
	Time int64
	Val  float64
}

type RecordSlice

type RecordSlice []Record

func (RecordSlice) Len

func (s RecordSlice) Len() int

func (RecordSlice) Less

func (s RecordSlice) Less(i, j int) bool

func (RecordSlice) Swap

func (s RecordSlice) Swap(i, j int)

type StatRecord

type StatRecord struct {
	Time  int64 //This is at the start of the record
	Count uint64
	Min   float64
	Mean  float64
	Max   float64
}

type WindowContext

type WindowContext struct {
	Time   int64
	Count  uint64
	Min    float64
	Total  float64
	Max    float64
	Active bool
	Done   bool
}

Jump to

Keyboard shortcuts

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