qtree

package
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
}

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.