qtree

package
v3.4.11+incompatible Latest Latest
Warning

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

 Go to latest Published: Jul 27, 2016 License: GPL-3.0 Imports: 7 Imported by: 0

Documentation

Index

Constants

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 ErrBadDelete = errors.New("Bad delete")
View Source 
var ErrBadInsert = errors.New("Bad insert")
View Source 
var ErrBadTimeRange error = errors.New("Invalid time range")
View Source 
var ErrIdxNotFound = errors.New("Index not found")
View Source 
var ErrImmutableTree = errors.New("Tree is immutable")
View Source 
var ErrNoSuchPoint = errors.New("No such point")
View Source 
var ErrNoSuchStream = errors.New("No such stream")
View Source 
var ErrNotLeafNode = errors.New("Not a leaf node")

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, error)

*

  • Load a quasar tree

func NewWriteQTree 

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

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(gen uint64, resolution uint8) chan ChangedRange

func (*QTree) FindChangedSinceSlice 

func (tr *QTree) FindChangedSinceSlice(gen uint64, resolution uint8) []ChangedRange

func (*QTree) FindNearestValue 

func (n *QTree) FindNearestValue(time int64, backwards bool) (Record, error)

func (*QTree) Generation 

func (n *QTree) Generation() uint64

func (*QTree) GetAllReferencedVAddrs 

func (n *QTree) GetAllReferencedVAddrs() chan uint64

Holy shit these take a long time

func (*QTree) GetReferencedAddrsDebug 

func (tr *QTree) GetReferencedAddrsDebug() map[uint64]bool

func (*QTree) InsertValues 

func (tr *QTree) InsertValues(records []Record) (e error)

*

  • 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, error)

func (*QTree) NewCoreNode 

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

func (*QTree) NewVectorNode 

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

func (*QTree) QueryStatisticalValues 

func (tr *QTree) QueryStatisticalValues(rv chan StatRecord, err chan error,
	start int64, end int64, pw uint8)

func (*QTree) QueryStatisticalValuesBlock 

func (tr *QTree) QueryStatisticalValuesBlock(start int64, end int64, pw uint8) ([]StatRecord, error)

func (*QTree) QueryWindow 

func (tr *QTree) QueryWindow(start int64, end int64, width uint64, depth uint8, rv chan StatRecord)

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

func (*QTree) ReadStandardValuesBlock 

func (tr *QTree) ReadStandardValuesBlock(start int64, end int64) ([]Record, error)

func (*QTree) ReadStandardValuesCI 

func (tr *QTree) ReadStandardValuesCI(rv chan Record, err chan error, start int64, end int64)

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(gen uint64, rchan chan ChangedRange, 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.

func (*QTreeNode) FindNearestValue 

func (n *QTreeNode) FindNearestValue(time int64, backwards bool) (Record, error)

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, error)

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) GetAllReferencedVAddrs 

func (n *QTreeNode) GetAllReferencedVAddrs(rchan chan 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) PrebufferChild 

func (n *QTreeNode) PrebufferChild(i uint16)

func (*QTreeNode) PrintCounts 

func (n *QTreeNode) PrintCounts(indent int)

func (*QTreeNode) QueryStatisticalValues 

func (n *QTreeNode) QueryStatisticalValues(rv chan StatRecord, err chan error,
	start int64, end int64, pw uint8)

func (*QTreeNode) QueryWindow 

func (n *QTreeNode) QueryWindow(end int64, nxtstart *int64, width uint64, depth uint8, rv chan StatRecord, ctx *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(rv chan Record, err chan error,
	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
}

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.