qtree

package
v4.4.10+incompatible Latest Latest
Warning

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

 Go to latest Published: May 24, 2017 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(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()

func (*QTree) DeleteRange 

func (tr *QTree) DeleteRange(start int64, end int64) error

func (*QTree) FindChangedSince 

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

NOSYNC func (tr *QTree) FindChangedSinceSlice(ctx context.Context, gen uint64, resolution uint8) ([]ChangedRange, bte.BTE) { NOSYNC if ctx.Err() != nil { NOSYNC return nil, bte.CtxE(ctx) NOSYNC } NOSYNC if tr.root == nil { NOSYNC panic("is this actually a problem tho?") NOSYNC //return nil, bte.Err(bte.InvariantFailure, ) NOSYNC //return make([]ChangedRange, 0) NOSYNC } NOSYNC rv := make([]ChangedRange, 0, 1024) NOSYNC rve := make(chan bte.BTE, 1) NOSYNC rch := tr.FindChangedSince(ctx, gen, resolution) NOSYNC var lr ChangedRange = ChangedRange{} NOSYNC for { NOSYNC select { NOSYNC case <-ctx.Done(): NOSYNC return nil, bte.CtxE(ctx) NOSYNC case cr, ok := <-rch: NOSYNC if !ok { NOSYNC //This is the end. NOSYNC //Do we have an unsaved LR? NOSYNC if lr.Valid { NOSYNC rv = append(rv, lr) NOSYNC } NOSYNC return rv, nil NOSYNC } NOSYNC if !cr.Valid { NOSYNC return nil, bte.Err(bte.InvariantFailure, "invalid CR") NOSYNC } NOSYNC //Coalesce NOSYNC if lr.Valid && cr.Start == lr.End { NOSYNC lr.End = cr.End NOSYNC } else { NOSYNC if lr.Valid { NOSYNC rv = append(rv, lr) NOSYNC } NOSYNC lr = cr NOSYNC } NOSYNC } NOSYNC } NOSYNC return rv, nil NOSYNC }

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(addr uint64, impl_Generation uint64, impl_Pointwidth uint8, impl_StartTime int64) *QTreeNode

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(i uint16) *QTreeNode

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
}

Notes

Bugs

  • this should be supported TODO this should be supported

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.