hlc

package
v0.0.0-...-1b6ad0c Latest Latest
Warning

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

Go to latest
Published: Aug 11, 2020 License: Apache-2.0 Imports: 18 Imported by: 5

Documentation

Overview

Package hlc implements the Hybrid Logical Clock outlined in "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases", available online at http://www.cse.buffalo.edu/tech-reports/2014-04.pdf.

Index

Examples

Constants

This section is empty.

Variables

View Source
var (
	ErrInvalidLengthLegacyTimestamp = fmt.Errorf("proto: negative length found during unmarshaling")
	ErrIntOverflowLegacyTimestamp   = fmt.Errorf("proto: integer overflow")
)
View Source
var (
	// MaxTimestamp is the max value allowed for Timestamp.
	MaxTimestamp = Timestamp{WallTime: math.MaxInt64, Logical: math.MaxInt32}
	// MinTimestamp is the min value allowed for Timestamp.
	MinTimestamp = Timestamp{WallTime: 0, Logical: 1}
)

Timestamp constant values.

View Source
var (
	ErrInvalidLengthTimestamp = fmt.Errorf("proto: negative length found during unmarshaling")
	ErrIntOverflowTimestamp   = fmt.Errorf("proto: integer overflow")
)

Functions

func UnixNano

func UnixNano() int64

UnixNano returns the local machine's physical nanosecond unix epoch timestamp as a convenience to create a HLC via c := hlc.NewClock(hlc.UnixNano, ...).

Types

type Clock

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

Clock is a hybrid logical clock. Objects of this type model causality while maintaining a relation to physical time. Roughly speaking, timestamps consist of the largest wall clock time among all events, and a logical clock that ticks whenever an event happens in the future of the local physical clock. The data structure is thread safe and thus can safely be shared by multiple goroutines.

See NewClock for details.

func NewClock

func NewClock(physicalClock func() int64, maxOffset time.Duration) *Clock

NewClock creates a new hybrid logical clock associated with the given physical clock. The logical ts is initialized to zero.

The physical clock is typically given by the wall time of the local machine in unix epoch nanoseconds, using hlc.UnixNano. This is not a requirement.

A value of 0 for maxOffset means that clock skew checking, if performed on this clock by RemoteClockMonitor, is disabled.

Example

ExampleNewClock shows how to create a new hybrid logical clock based on the local machine's physical clock. The sanity checks in this example will, of course, not fail and the output will be the age of the Unix epoch in nanoseconds.

// Initialize a new clock, using the local
// physical clock.
c := NewClock(UnixNano, time.Nanosecond)
// Update the state of the hybrid clock.
s := c.Now()
time.Sleep(50 * time.Nanosecond)
t := Timestamp{WallTime: UnixNano()}
// The sanity checks below will usually never be triggered.

if s.Less(t) || !t.Less(s) {
	log.Fatalf(context.Background(), "The later timestamp is smaller than the earlier one")
}

if t.WallTime-s.WallTime > 0 {
	log.Fatalf(context.Background(), "HLC timestamp %d deviates from physical clock %d", s, t)
}

if s.Logical > 0 {
	log.Fatalf(context.Background(), "Trivial timestamp has logical component")
}

fmt.Printf("The Unix Epoch is now approximately %dns old.\n", t.WallTime)
Output:

func (*Clock) MaxOffset

func (c *Clock) MaxOffset() time.Duration

MaxOffset returns the maximal clock offset to any node in the cluster.

A value of 0 means offset checking is disabled.

func (*Clock) Now

func (c *Clock) Now() Timestamp

Now returns a timestamp associated with an event from the local machine that may be sent to other members of the distributed network. This is the counterpart of Update, which is passed a timestamp received from another member of the distributed network.

func (*Clock) PhysicalNow

func (c *Clock) PhysicalNow() int64

PhysicalNow returns the local wall time.

Note that, contrary to Now(), PhysicalNow does not take into consideration higher clock signals received through Update(). If you want to take them into consideration, use c.Now().GoTime().

func (*Clock) PhysicalTime

func (c *Clock) PhysicalTime() time.Time

PhysicalTime returns a time.Time struct using the local wall time.

func (*Clock) RefreshHLCUpperBound

func (c *Clock) RefreshHLCUpperBound(persistFn func(int64) error, delta int64) error

RefreshHLCUpperBound persists the HLC upper bound and updates the in memory value if the persist succeeds. delta is used to compute the upper bound.

func (*Clock) ResetHLCUpperBound

func (c *Clock) ResetHLCUpperBound(persistFn func(int64) error) error

ResetHLCUpperBound persists a value of 0 as the HLC upper bound which disables upper bound validation

func (*Clock) StartMonitoringForwardClockJumps

func (c *Clock) StartMonitoringForwardClockJumps(
	ctx context.Context,
	forwardClockJumpCheckEnabledCh <-chan bool,
	tickerFn func(d time.Duration) *time.Ticker,
	tickCallback func(),
) error

StartMonitoringForwardClockJumps starts a goroutine to update the clock's forwardClockJumpCheckEnabled based on the values pushed in forwardClockJumpCheckEnabledCh.

This also keeps lastPhysicalTime up to date to avoid spurious jump errors.

A nil channel or a value of false pushed in forwardClockJumpCheckEnabledCh disables checking clock jumps between two successive reads of the physical clock.

This should only be called once per clock, and will return an error if called more than once

tickerFn is used to create a new ticker

tickCallback is called whenever maxForwardClockJumpCh or a ticker tick is processed

func (*Clock) Update

func (c *Clock) Update(rt Timestamp)

Update takes a hybrid timestamp, usually originating from an event received from another member of a distributed system. The clock is updated to reflect the later of the two. The update does not check the maximum clock offset. To receive an error response instead of forcing the update in case the remote timestamp is too far into the future, use UpdateAndCheckMaxOffset() instead.

func (*Clock) UpdateAndCheckMaxOffset

func (c *Clock) UpdateAndCheckMaxOffset(ctx context.Context, rt Timestamp) error

UpdateAndCheckMaxOffset is like Update, but also takes the wall time into account and returns an error in the event that the supplied remote timestamp exceeds the wall clock time by more than the maximum clock offset.

func (*Clock) WallTimeUpperBound

func (c *Clock) WallTimeUpperBound() int64

WallTimeUpperBound returns the in memory value of upper bound to wall time

type ClockSource

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

ClockSource contains the handle of the clock device as well as the clock id.

func MakeClockSource

func MakeClockSource(ctx context.Context, clockDevicePath string) (ClockSource, error)

MakeClockSource creates a new ClockSource for the given device path.

func (ClockSource) UnixNano

func (p ClockSource) UnixNano() int64

UnixNano returns the clock device's physical nanosecond unix epoch timestamp as a convenience to create a HLC via c := hlc.NewClock(dev.UnixNano, ...).

type LegacyTimestamp

type LegacyTimestamp struct {
	// Holds a wall time, typically a unix epoch time expressed in
	// nanoseconds.
	WallTime int64 `protobuf:"varint,1,opt,name=wall_time,json=wallTime" json:"wall_time"`
	// The logical component captures causality for events whose wall
	// times are equal. It is effectively bounded by (maximum clock
	// skew)/(minimal ns between events) and nearly impossible to
	// overflow.
	Logical int32 `protobuf:"varint,2,opt,name=logical" json:"logical"`
}

LegacyTimestamp is convertible to hlc.Timestamp, but uses the legacy encoding as it is encoded "below raft".

func NewPopulatedLegacyTimestamp

func NewPopulatedLegacyTimestamp(r randyLegacyTimestamp, easy bool) *LegacyTimestamp

func (*LegacyTimestamp) Descriptor

func (*LegacyTimestamp) Descriptor() ([]byte, []int)

func (*LegacyTimestamp) Equal

func (this *LegacyTimestamp) Equal(that interface{}) bool

func (LegacyTimestamp) Less

Less returns whether the receiver is less than the parameter.

func (*LegacyTimestamp) Marshal

func (m *LegacyTimestamp) Marshal() (dAtA []byte, err error)

func (*LegacyTimestamp) MarshalTo

func (m *LegacyTimestamp) MarshalTo(dAtA []byte) (int, error)

func (*LegacyTimestamp) ProtoMessage

func (*LegacyTimestamp) ProtoMessage()

func (*LegacyTimestamp) Reset

func (m *LegacyTimestamp) Reset()

func (*LegacyTimestamp) Size

func (m *LegacyTimestamp) Size() (n int)

func (LegacyTimestamp) String

func (t LegacyTimestamp) String() string

func (*LegacyTimestamp) Unmarshal

func (m *LegacyTimestamp) Unmarshal(dAtA []byte) error

func (*LegacyTimestamp) XXX_DiscardUnknown

func (m *LegacyTimestamp) XXX_DiscardUnknown()

func (*LegacyTimestamp) XXX_Marshal

func (m *LegacyTimestamp) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*LegacyTimestamp) XXX_Merge

func (m *LegacyTimestamp) XXX_Merge(src proto.Message)

func (*LegacyTimestamp) XXX_Size

func (m *LegacyTimestamp) XXX_Size() int

func (*LegacyTimestamp) XXX_Unmarshal

func (m *LegacyTimestamp) XXX_Unmarshal(b []byte) error

type ManualClock

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

ManualClock is a convenience type to facilitate creating a hybrid logical clock whose physical clock is manually controlled. ManualClock is thread safe.

func NewManualClock

func NewManualClock(nanos int64) *ManualClock

NewManualClock returns a new instance, initialized with specified timestamp.

func (*ManualClock) Increment

func (m *ManualClock) Increment(incr int64)

Increment atomically increments the manual clock's timestamp.

func (*ManualClock) Set

func (m *ManualClock) Set(nanos int64)

Set atomically sets the manual clock's timestamp.

func (*ManualClock) UnixNano

func (m *ManualClock) UnixNano() int64

UnixNano returns the underlying manual clock's timestamp.

type Timestamp

type Timestamp struct {
	// Holds a wall time, typically a unix epoch time expressed in
	// nanoseconds.
	WallTime int64 `protobuf:"varint,1,opt,name=wall_time,json=wallTime,proto3" json:"wall_time,omitempty"`
	// The logical component captures causality for events whose wall
	// times are equal. It is effectively bounded by (maximum clock
	// skew)/(minimal ns between events) and nearly impossible to
	// overflow.
	Logical int32 `protobuf:"varint,2,opt,name=logical,proto3" json:"logical,omitempty"`
}

Timestamp represents a state of the hybrid logical clock.

func NewPopulatedTimestamp

func NewPopulatedTimestamp(r randyTimestamp, easy bool) *Timestamp

func ParseTimestamp

func ParseTimestamp(str string) (_ Timestamp, err error)

ParseTimestamp attempts to parse the string generated from Timestamp.String().

func (Timestamp) Add

func (t Timestamp) Add(wallTime int64, logical int32) Timestamp

Add returns a timestamp with the WallTime and Logical components increased. wallTime is expressed in nanos.

func (Timestamp) AsOfSystemTime

func (t Timestamp) AsOfSystemTime() string

AsOfSystemTime returns a string to be used in an AS OF SYSTEM TIME query.

func (*Timestamp) Backward

func (t *Timestamp) Backward(s Timestamp)

Backward updates the timestamp from the one given, if that moves it backwards in time.

func (Timestamp) Clone

func (t Timestamp) Clone() *Timestamp

Clone return a new timestamp that has the same contents as the receiver.

func (*Timestamp) Descriptor

func (*Timestamp) Descriptor() ([]byte, []int)

func (*Timestamp) Equal

func (this *Timestamp) Equal(that interface{}) bool

func (Timestamp) FloorPrev

func (t Timestamp) FloorPrev() Timestamp

FloorPrev returns a timestamp earlier than the current timestamp. If it can subtract a logical tick without wrapping around, it does so. Otherwise it subtracts a nanosecond from the walltime.

func (*Timestamp) Forward

func (t *Timestamp) Forward(s Timestamp) bool

Forward updates the timestamp from the one given, if that moves it forwards in time. Returns true if the timestamp was adjusted and false otherwise.

func (Timestamp) GoTime

func (t Timestamp) GoTime() time.Time

GoTime converts the timestamp to a time.Time.

func (Timestamp) IsEmpty

func (t Timestamp) IsEmpty() bool

IsEmpty retruns true if t is an empty Timestamp.

func (Timestamp) Less

func (t Timestamp) Less(s Timestamp) bool

Less returns whether the receiver is less than the parameter.

func (Timestamp) LessEq

func (t Timestamp) LessEq(s Timestamp) bool

LessEq returns whether the receiver is less than or equal to the parameter.

func (*Timestamp) Marshal

func (m *Timestamp) Marshal() (dAtA []byte, err error)

func (*Timestamp) MarshalTo

func (m *Timestamp) MarshalTo(dAtA []byte) (int, error)

func (Timestamp) Next

func (t Timestamp) Next() Timestamp

Next returns the timestamp with the next later timestamp.

func (Timestamp) Prev

func (t Timestamp) Prev() Timestamp

Prev returns the next earliest timestamp.

func (*Timestamp) ProtoMessage

func (*Timestamp) ProtoMessage()

func (*Timestamp) Reset

func (m *Timestamp) Reset()

func (Timestamp) SafeValue

func (Timestamp) SafeValue()

SafeValue implements the redact.SafeValue interface.

func (*Timestamp) Size

func (m *Timestamp) Size() (n int)

func (Timestamp) String

func (t Timestamp) String() string

String implements the fmt.Formatter interface.

func (*Timestamp) Unmarshal

func (m *Timestamp) Unmarshal(dAtA []byte) error

func (*Timestamp) XXX_DiscardUnknown

func (m *Timestamp) XXX_DiscardUnknown()

func (*Timestamp) XXX_Marshal

func (m *Timestamp) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*Timestamp) XXX_Merge

func (m *Timestamp) XXX_Merge(src proto.Message)

func (*Timestamp) XXX_Size

func (m *Timestamp) XXX_Size() int

func (*Timestamp) XXX_Unmarshal

func (m *Timestamp) XXX_Unmarshal(b []byte) error

Jump to

Keyboard shortcuts

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