lookup

package
v0.4.2 Latest Latest
Warning

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

Go to latest
Published: Jun 28, 2019 License: GPL-3.0 Imports: 6 Imported by: 0

Documentation

Overview

Package lookup defines feed lookup algorithms and provides tools to place updates so they can be found

Index

Constants

View Source
const DefaultLevel = HighestLevel

DefaultLevel sets what level will be chosen to search when there is no hint

View Source
const EpochLength = 8

EpochLength stores the serialized binary length of an Epoch

View Source
const HighestLevel = 31

HighestLevel sets the lowest frequency the algorithm will operate at, as a power of 2. 31 -> 2^31 equals to roughly 38 years.

View Source
const LowestLevel uint8 = 0 // default is 0 (1 second)

LowestLevel establishes the frequency resolution of the lookup algorithm as a power of 2.

View Source
const MaxTime uint64 = (1 << 56) - 1

MaxTime contains the highest possible time value an Epoch can handle

Variables

View Source
var LongEarthLookaheadDelay = 250 * time.Millisecond

LongEarthLookaheadDelay is the headstart the lookahead gives R before it launches

View Source
var LongEarthLookbackDelay = 250 * time.Millisecond

LongEarthLookbackDelay is the headstart the lookback gives R before it launches

View Source
var NoClue = Epoch{}

NoClue is a hint that can be provided when the Lookup caller does not have a clue about where the last update may be

View Source
var TimeAfter = time.After

TimeAfter must point to a function that returns a timer This is here so that tests can replace it with a mock up timer factory to simulate time deterministically

Functions

func FluzCapacitorAlgorithm

func FluzCapacitorAlgorithm(ctx context.Context, now uint64, hint Epoch, read ReadFunc) (value interface{}, err error)

FluzCapacitorAlgorithm works by narrowing the epoch search area if an update is found going back and forth in time First, it will attempt to find an update where it should be now if the hint was really the last update. If that lookup fails, then the last update must be either the hint itself or the epochs right below. If however, that lookup succeeds, then the update must be that one or within the epochs right below. see the guide for a more graphical representation

func GetNextLevel

func GetNextLevel(last Epoch, now uint64) uint8

GetNextLevel returns the frequency level a next update should be placed at, provided where the last update was and what time it is now. This is the first nonzero bit of the XOR of 'last' and 'now', counting from the highest significant bit but limited to not return a level that is smaller than the last-1

func LongEarthAlgorithm

func LongEarthAlgorithm(ctx context.Context, now uint64, hint Epoch, read ReadFunc) (interface{}, error)

LongEarthAlgorithm explores possible lookup paths in parallel, pruning paths as soon as a more promising lookup path is found. As a result, this lookup algorithm is an order of magnitude faster than the FluzCapacitor algorithm, but at the expense of more exploratory reads. This algorithm works as follows. On each step, the next epoch is immediately looked up (R) and given a head start, while two parallel "steps" are launched a short time after: look ahead (A) is the path the algorithm would take if the R lookup returns a value, whereas look back (B) is the path the algorithm would take if the R lookup failed. as soon as R is actually finished, the A or B paths are pruned depending on the value of R. if A returns earlier than R, then R and B read operations can be safely canceled, saving time. The maximum number of active read operations is calculated as 2^(timeout/headstart). If headstart is infinite, this algorithm behaves as FluzCapacitor. timeout is the maximum execution time of the passed `read` function. the two head starts can be configured by changing LongEarthLookaheadDelay or LongEarthLookbackDelay

Types

type Algorithm

type Algorithm func(ctx context.Context, now uint64, hint Epoch, read ReadFunc) (value interface{}, err error)

Algorithm is the function signature of a lookup algorithm

Lookup finds the update with the highest timestamp that is smaller or equal than 'now' It takes a hint which should be the epoch where the last known update was If you don't know in what epoch the last update happened, simply submit lookup.NoClue read() will be called on each lookup attempt Returns an error only if read() returns an error Returns nil if an update was not found

type Epoch

type Epoch struct {
	Time  uint64 `json:"time"`  // Time stores the time at which the update or lookup takes place
	Level uint8  `json:"level"` // Level indicates the frequency level as the exponent of a power of 2
}

Epoch represents a time slot at a particular frequency level

func GetFirstEpoch

func GetFirstEpoch(now uint64) Epoch

GetFirstEpoch returns the epoch where the first update should be located based on what time it is now.

func GetNextEpoch

func GetNextEpoch(last Epoch, now uint64) Epoch

GetNextEpoch returns the epoch where the next update should be located according to where the previous update was and what time it is now.

func Hint

func Hint(last uint64) Epoch

Hint creates a hint based only on the last known update time

func (*Epoch) After

func (e *Epoch) After(epoch Epoch) bool

After returns true if this epoch occurs later or exactly at the other epoch.

func (*Epoch) Base

func (e *Epoch) Base() uint64

Base returns the base time of the Epoch

func (*Epoch) Equals

func (e *Epoch) Equals(epoch Epoch) bool

Equals compares two epochs and returns true if they refer to the same time period.

func (*Epoch) ID

func (e *Epoch) ID() EpochID

ID Returns the unique identifier of this epoch

func (*Epoch) MarshalBinary

func (e *Epoch) MarshalBinary() (data []byte, err error)

MarshalBinary implements the encoding.BinaryMarshaller interface

func (*Epoch) String

func (e *Epoch) String() string

String implements the Stringer interface.

func (*Epoch) UnmarshalBinary

func (e *Epoch) UnmarshalBinary(data []byte) error

UnmarshalBinary implements the encoding.BinaryUnmarshaller interface

type EpochID

type EpochID [8]byte

EpochID is a unique identifier for an Epoch, based on its level and base time.

type ReadFunc

type ReadFunc func(ctx context.Context, epoch Epoch, now uint64) (interface{}, error)

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL