btreepq

Documentation

Overview

Package btreepq implements a queue of pages for scotty based on btrees.

Index

• func IsPageLessThanThat(page, that Page) bool
• type Page
• type PageQueue
  • func New(pageCount, threshold, degree uint, creater func() Page) *PageQueue
  • func (p *PageQueue) Len() uint
  • func (p *PageQueue) NewPage() Page
  • func (p *PageQueue) NextPage() Page
  • func (p *PageQueue) Prioritise(pg Page, ts float64)
  • func (p *PageQueue) ReclaimHigh(pg Page)
  • func (p *PageQueue) ReclaimLow(pg Page)
  • func (p *PageQueue) RemovePage() (removed Page, ok bool)
  • func (p *PageQueue) SetThreshold(threshold uint)
  • func (p *PageQueue) Stats(stats *PageQueueStats)
• type PageQueueStats
  • func (s *PageQueueStats) HighPriorityRatio() float64
  • func (s *PageQueueStats) TotalCount() uint

Functions

func IsPageLessThanThat

func IsPageLessThanThat(page, that Page) bool

IsPageLessThanThat returns true if page should be evicted / reused before that.

Types

type Page

type Page interface {
	// btree.Item Less method must return true if and only if
	// IsPageLessThanThat(instance, argument) returns true.
	// Implementations of Less must downcast their argument to this type, Page.
	// Implementations must never downcast the argument directly to the
	// implementation's type as there is no guarantee that the argument's
	// type will match the implementation's type.
	btree.Item
	// Sets the sequence number of this page. Only PageQueue uses this.
	// Clients must not call this directly.
	SetSeqNo(i uint64)
	// Returns the sequence number of this page.
	SeqNo() uint64
	// Sets the timestamp. Only PageQueue uses this.
	// Clients must not call this directly.
	SetTS(ts float64)
	// Returns the timestamp.
	TS() float64
}

Page represents a single page in scotty Each page has a sequence number which indicates when the page was last used. Pages with higher sequence numbers were used more recently than pages with lower sequence numbers.

type PageQueue

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

PageQueue represents the page queue for scotty. Instances have two internal queues: A low priority and a high priority queue. Generally, the high priority queue contain the pages that are less valuable to scotty such as pages belonging to inactive metrics. If the size of the high priority queue equals or exceeds a given threshold, the NextPage method always pulls from the high priority queue. Otherwise, NextPage pulls from whatever queue has the least recently used page. Initially, all pages are on the high priority queue as new pages have no data valuable to scotty. NextPage always adds the page it returns back to the end of the low priority queue. The low and high priority queues are mutually exclusive.

func New

func New(
	pageCount,
	threshold,
	degree uint,
	creater func() Page) *PageQueue

New returns a new PageQueue. pageCount is the total number of pages which must be at least 1. threshold is the size that the high priority queue must be to always pull from it. degree is the degree of the Btrees. See github.com/Symantec/btree creater creates each page and is called exactly pageCount times.

func (*PageQueue) Len

func (p *PageQueue) Len() uint

Len returns the total number of pages in this instance.

func (*PageQueue) NewPage

func (p *PageQueue) NewPage() Page

NewPage works like NextPage except that it always returns a brand new page and it increases the total page count by 1 in this instance.

func (*PageQueue) NextPage

func (p *PageQueue) NextPage() Page

NextPage returns the next page for scotty to use leaving it in the queue by adding it to the end of the low priority queue.

func (*PageQueue) Prioritise

func (p *PageQueue) Prioritise(pg Page, ts float64)

Prioritise prioritises pg according to ts. Pages with lower ts values come off the queue first. By default, the ts for a page is +Inf.

func (*PageQueue) ReclaimHigh

func (p *PageQueue) ReclaimHigh(pg Page)

ReclaimHigh moves pg from the low priority queue to the high priority queue If pg is already in the high priority queue, ReclaimHigh is a no-op.

func (*PageQueue) ReclaimLow

func (p *PageQueue) ReclaimLow(pg Page)

ReclaimLow moves pg from the high priority queue to the low priority queue If pg is already in the low priority queue, ReclaimLow is a no-op.

func (*PageQueue) RemovePage

func (p *PageQueue) RemovePage() (removed Page, ok bool)

RemovePage works like NextPage except that it removes returned page from this queue entirely. If this instance already has the minimum number of pages, RemovePages returns nil, false

func (*PageQueue) SetThreshold

func (p *PageQueue) SetThreshold(threshold uint)

SetThreshold sets the size that the high priority queue must be in order to always pull from it. If threshold < 1, its effective value is 1.

func (*PageQueue) Stats

func (p *PageQueue) Stats(stats *PageQueueStats)

Stats gets the statistics for this instance

type PageQueueStats

type PageQueueStats struct {
	LowPriorityCount    uint
	HighPriorityCount   uint
	Threshold           uint
	FirstLowPriorityTS  float64
	FirstHighPriorityTS float64
}

PageQueueStats represents statistics for a PageQueue

func (*PageQueueStats) HighPriorityRatio

func (s *PageQueueStats) HighPriorityRatio() float64

func (*PageQueueStats) TotalCount

func (s *PageQueueStats) TotalCount() uint