qtree

package
Version: v0.0.0-...-a2e7767 Latest Latest
Warning

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

Go to latest
Published: Nov 30, 2020 License: GPL-3.0 Imports: 10 Imported by: 0

Documentation

Index

Constants

View Source
const DAY = 24 * HOUR
View Source
const HOUR = 60 * MINUTE
View Source
const MICROSECOND = 1000
View Source
const MILLISECOND = 1000 * MICROSECOND
View Source
const MINUTE = 60 * SECOND
View Source
const MaximumTime = 64 << 56
View Source
const MinimumTime = 0
View Source
const ROOTSTART = 0 //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 = 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 Buffer

type Buffer interface {
	Get(i int) Record
	Len() int
	Write(r []Record) Buffer
	ToSlice() []Record
}

func NewLinkedListBuffer

func NewLinkedListBuffer(id uuid.UUID) Buffer

func NewPreAllocatedSliceBuffer

func NewPreAllocatedSliceBuffer(id uuid.UUID, bufferSize uint64) Buffer

func NewSliceBuffer

func NewSliceBuffer(id uuid.UUID) Buffer

type ChangedRange

type ChangedRange struct {
	Valid bool
	Start int64
	End   int64
}

type LinkedListBuffer

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

func (*LinkedListBuffer) Get

func (b *LinkedListBuffer) Get(i int) Record

func (*LinkedListBuffer) Len

func (b *LinkedListBuffer) Len() int

func (*LinkedListBuffer) ToSlice

func (b *LinkedListBuffer) ToSlice() []Record

func (*LinkedListBuffer) Write

func (b *LinkedListBuffer) Write(records []Record) Buffer

type NaiveTreePolicy

type NaiveTreePolicy struct{}

func (NaiveTreePolicy) DecideKAndV

func (NaiveTreePolicy) DecideKAndV(buffer Buffer, span time.Duration) (uint16, uint32)

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

func (q *QTree) GetKFactor() int

func (*QTree) GetPWFactor

func (q *QTree) GetPWFactor() uint8

func (*QTree) GetRootPW

func (q *QTree) GetRootPW() uint8

func (*QTree) GetVSize

func (q *QTree) GetVSize() int

func (*QTree) InsertValues

func (tr *QTree) InsertValues(buffer Buffer) (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) 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)

* OpCountMean, OpMin, OpMax 都是对整个 QTreeNode 进行统计

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(rv chan StatRecord, err chan error,
	start int64, end int64, pw uint8)

原理和 ReadStandardValuesCI 几乎是一致的

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 SliceBuffer

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

func (*SliceBuffer) Get

func (b *SliceBuffer) Get(i int) Record

func (*SliceBuffer) Len

func (b *SliceBuffer) Len() int

func (*SliceBuffer) ToSlice

func (b *SliceBuffer) ToSlice() []Record

func (*SliceBuffer) Write

func (b *SliceBuffer) Write(records []Record) Buffer

type StatRecord

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

type TreePolicy

type TreePolicy interface {
	DecideKAndV(buffer Buffer, span time.Duration) (uint16, uint32)
}

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
t or T : Toggle theme light dark auto
y or Y : Canonical URL