Documentation
¶
Overview ¶
Package lookup defines feed lookup algorithms and provides tools to place updates so they can be found
Index ¶
- Constants
- Variables
- func FluzCapacitorAlgorithm(ctx context.Context, now uint64, hint Epoch, read ReadFunc) (value interface{}, err error)
- func GetNextLevel(last Epoch, now uint64) uint8
- func LongEarthAlgorithm(ctx context.Context, now uint64, hint Epoch, read ReadFunc) (interface{}, error)
- type Algorithm
- type Epoch
- type EpochID
- type ReadFunc
Constants ¶
const DefaultLevel = HighestLevel
DefaultLevel sets what level will be chosen to search when there is no hint
const EpochLength = 8
EpochLength stores the serialized binary length of an Epoch
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.
const LowestLevel uint8 = 0 // default is 0 (1 second)
LowestLevel establishes the frequency resolution of the lookup algorithm as a power of 2.
const MaxTime uint64 = (1 << 56) - 1
MaxTime contains the highest possible time value an Epoch can handle
Variables ¶
var LongEarthLookaheadDelay = 250 * time.Millisecond
LongEarthLookaheadDelay is the headstart the lookahead gives R before it launches
var LongEarthLookbackDelay = 250 * time.Millisecond
LongEarthLookbackDelay is the headstart the lookback gives R before it launches
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
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 ¶
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
var Lookup Algorithm = LongEarthAlgorithm
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 ¶
GetFirstEpoch returns the epoch where the first update should be located based on what time it is now.
func GetNextEpoch ¶
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 (*Epoch) Equals ¶
Equals compares two epochs and returns true if they refer to the same time period.
func (*Epoch) MarshalBinary ¶
MarshalBinary implements the encoding.BinaryMarshaller interface
func (*Epoch) UnmarshalBinary ¶
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 ¶
ReadFunc is a handler called by Lookup each time it attempts to find a value It should return <nil> if a value is not found It should return <nil> if a value is found, but its timestamp is higher than "now" It should only return an error in case the handler wants to stop the lookup process entirely.
Source Files