Documentation
¶
Overview ¶
Package set implements set CRDT primitives.
Index ¶
- Variables
- type ElementCodec
- type GSet
- func (s *GSet[T]) Add(element T) (GSetDelta[T], error)
- func (s *GSet[T]) ApplyDelta(delta GSetDelta[T]) error
- func (s *GSet[T]) Contains(element T) bool
- func (s *GSet[T]) Elements() []T
- func (s *GSet[T]) MarshalBinary() ([]byte, error)
- func (s *GSet[T]) MarshalJSON() ([]byte, error)
- func (s *GSet[T]) Merge(other *GSet[T]) error
- func (s *GSet[T]) Snapshot() (snapshot.Snapshot, error)
- func (s *GSet[T]) State() crdt.StateSnapshot
- func (s *GSet[T]) UnmarshalBinary(data []byte) error
- func (s *GSet[T]) UnmarshalBinaryWithLimits(data []byte, limits frame.DecoderLimits) error
- type GSetDelta
- type ORSet
- func (s *ORSet[T]) Add(element T) (ORSetDelta[T], error)
- func (s *ORSet[T]) ApplyDelta(delta ORSetDelta[T]) error
- func (s *ORSet[T]) ClockState() clock.State
- func (s *ORSet[T]) Compact(stableFrontier map[string]crdt.Tag) (int, error)
- func (s *ORSet[T]) CompactTombstones(acknowledged []crdt.Tag) (int, error)
- func (s *ORSet[T]) Contains(element T) bool
- func (s *ORSet[T]) Elements() []T
- func (s *ORSet[T]) Frontier() map[string]crdt.Tag
- func (s *ORSet[T]) MarshalBinary() ([]byte, error)
- func (s *ORSet[T]) MarshalBinaryWithClockState() ([]byte, clock.State, error)
- func (s *ORSet[T]) MarshalJSON() ([]byte, error)
- func (s *ORSet[T]) Merge(other *ORSet[T]) error
- func (s *ORSet[T]) Remove(element T) (ORSetDelta[T], error)
- func (s *ORSet[T]) Snapshot(frontier map[string]crdt.Tag) (snapshot.Snapshot, error)
- func (s *ORSet[T]) SnapshotCurrentState() (snapshot.Snapshot, error)
- func (s *ORSet[T]) State() crdt.StateSnapshot
- func (s *ORSet[T]) TombstoneTags() []crdt.Tag
- func (s *ORSet[T]) UnmarshalBinary(data []byte) error
- func (s *ORSet[T]) UnmarshalBinaryWithLimits(data []byte, limits frame.DecoderLimits) error
- type ORSetDelta
Constants ¶
This section is empty.
Variables ¶
var ( ErrNilGSet = errors.New("set: nil G-Set") ErrInvalidGSet = errors.New("set: invalid G-Set state") ErrInvalidGSetSnap = errors.New("set: invalid G-Set snapshot") )
var ( ErrInvalidCodec = errors.New("set: invalid element codec") ErrInvalidReplicaID = errors.New("set: invalid replica ID") ErrNilORSet = errors.New("set: nil OR-Set") ErrCodecMismatch = errors.New("set: codec ID mismatch") ErrInvalidDelta = errors.New("set: invalid OR-Set delta") ErrInvalidFrontier = errors.New("set: invalid frontier") ErrInvalidSnapshot = errors.New("set: invalid OR-Set snapshot") )
Functions ¶
This section is empty.
Types ¶
type ElementCodec ¶
type ElementCodec[T comparable] interface { ID() string Marshal(T) ([]byte, error) Unmarshal([]byte) (T, error) }
ElementCodec identifies and encodes one OR-Set element type. ID and encoded bytes must be stable across replicas that exchange state for the same set. Implementations must be safe for concurrent Marshal and Unmarshal calls and must return errors instead of panicking for invalid input.
type GSet ¶ added in v1.0.5
type GSet[T comparable] struct { // contains filtered or unexported fields }
GSet is a grow-only, state-based set. It is useful when membership never needs to be revoked: Add and Merge are set unions, so both are idempotent. Elements are identified on the wire by the canonical bytes from codec.
func NewGSet ¶ added in v1.0.5
func NewGSet[T comparable](replicaID string, codec ElementCodec[T]) (*GSet[T], error)
NewGSet creates a G-Set whose framed state uses codec's stable identifier. replicaID is diagnostic metadata and must be unique when the caller uses it to identify the logical owner of the set.
func NewGSetFromSnapshot ¶ added in v1.0.5
func NewGSetFromSnapshot[T comparable](replicaID string, saved snapshot.Snapshot, codec ElementCodec[T]) (*GSet[T], error)
NewGSetFromSnapshot restores a G-Set from a validated framed snapshot.
func (*GSet[T]) Add ¶ added in v1.0.5
Add inserts element and returns the one-element delta. Re-adding an element is valid and returns an equivalent idempotent delta.
func (*GSet[T]) ApplyDelta ¶ added in v1.0.5
ApplyDelta joins delta into s.
func (*GSet[T]) Elements ¶ added in v1.0.5
func (s *GSet[T]) Elements() []T
Elements returns a copy of the set. Its order is unspecified; framed output sorts canonical element bytes independently of Go map iteration.
func (*GSet[T]) MarshalBinary ¶ added in v1.0.5
MarshalBinary returns the canonical framed G-Set state.
func (*GSet[T]) MarshalJSON ¶ added in v1.0.5
MarshalJSON returns a diagnostic summary for structured logs. It omits set elements, tags, clock state, and codec data, and cannot restore the set.
func (*GSet[T]) Merge ¶ added in v1.0.5
Merge joins other into s without retaining either caller-owned state.
func (*GSet[T]) Snapshot ¶ added in v1.0.5
Snapshot returns an immutable state snapshot. A G-Set has no clock state or tombstone frontier, so an empty frontier is sufficient.
func (*GSet[T]) State ¶ added in v1.0.5
func (s *GSet[T]) State() crdt.StateSnapshot
State returns an immutable diagnostic summary.
func (*GSet[T]) UnmarshalBinary ¶ added in v1.0.5
UnmarshalBinary atomically replaces s with one canonical G-Set state.
func (*GSet[T]) UnmarshalBinaryWithLimits ¶ added in v1.0.5
func (s *GSet[T]) UnmarshalBinaryWithLimits(data []byte, limits frame.DecoderLimits) error
UnmarshalBinaryWithLimits atomically replaces s after complete bounded validation. Failed decoding leaves the receiver unchanged.
type GSetDelta ¶ added in v1.0.5
type GSetDelta[T comparable] struct { // contains filtered or unexported fields }
GSetDelta is a joinable partial G-Set state.
func UnmarshalGSetDelta ¶ added in v1.0.5
func UnmarshalGSetDelta[T comparable](data []byte, codec ElementCodec[T]) (GSetDelta[T], error)
UnmarshalGSetDelta validates and returns a G-Set delta frame.
func UnmarshalGSetDeltaWithLimits ¶ added in v1.0.5
func UnmarshalGSetDeltaWithLimits[T comparable](data []byte, codec ElementCodec[T], limits frame.DecoderLimits) (GSetDelta[T], error)
UnmarshalGSetDeltaWithLimits validates a bounded G-Set delta frame.
func (GSetDelta[T]) Elements ¶ added in v1.0.5
func (d GSetDelta[T]) Elements() []T
Elements returns a copy of the elements represented by d.
func (GSetDelta[T]) MarshalBinary ¶ added in v1.0.5
func (d GSetDelta[T]) MarshalBinary(codec ElementCodec[T]) ([]byte, error)
MarshalBinary returns the canonical framed G-Set delta using codec.
func (GSetDelta[T]) MarshalJSON ¶ added in v1.0.5
MarshalJSON returns a diagnostic summary for structured logs. It omits elements and codec data and cannot be applied as a delta from JSON.
type ORSet ¶
type ORSet[T comparable] struct { // contains filtered or unexported fields }
ORSet is an observed-remove, add-wins set. Each add receives a unique tag; remove operations tombstone only tags observed by that replica.
func NewORSet ¶
func NewORSet[T comparable](replicaID string, codec ElementCodec[T]) (*ORSet[T], error)
NewORSet creates an OR-Set for replicaID with codec.
func NewORSetFromClock ¶
func NewORSetFromClock[T comparable](clockState clock.State, codec ElementCodec[T]) (*ORSet[T], error)
NewORSetFromClock creates an OR-Set using a restored HLC state. Use this constructor when reusing a replica ID after restart.
func NewORSetFromSnapshot ¶
func NewORSetFromSnapshot[T comparable](saved snapshot.Snapshot, codec ElementCodec[T]) (*ORSet[T], error)
NewORSetFromSnapshot restores an OR-Set and its persisted local HLC state. Snapshots without a clock state are rejected because they cannot prove that this logical replica will not reuse a mutation tag after restart.
func (*ORSet[T]) Add ¶
func (s *ORSet[T]) Add(element T) (ORSetDelta[T], error)
Add inserts element and returns the add-tag delta.
func (*ORSet[T]) ApplyDelta ¶
func (s *ORSet[T]) ApplyDelta(delta ORSetDelta[T]) error
ApplyDelta joins delta into s. A delta already represented by s returns without advancing the local HLC or taking the receiver write lock.
func (*ORSet[T]) ClockState ¶
ClockState returns the state that must be persisted before this set's replica ID is reused after restart.
func (*ORSet[T]) Compact ¶
Compact removes tombstones that every active replica has acknowledged. The caller must provide a frontier whose every prefix is proven complete for every active replica. A greatest-observed-tag frontier from independently delivered, out-of-order deltas does not meet that requirement. Rejoining replicas must bootstrap from a post-compaction snapshot.
func (*ORSet[T]) CompactTombstones ¶
CompactTombstones removes exactly the supplied tombstones. For replicated state, use it only through a coordinator that has independently proved acknowledgement for each tag. tombstonegc.SimpleCollector may call it only for its documented local-only lifecycle. A tag that is not currently a tombstone is ignored. The input is completely validated before s is modified.
func (*ORSet[T]) Elements ¶
func (s *ORSet[T]) Elements() []T
Elements returns a copy of the currently visible elements. Its order is not specified; deterministic wire order is provided by the encoding layer.
func (*ORSet[T]) Frontier ¶
Frontier returns the greatest known tag for every replica in the current live-add and tombstone state. It is useful for diagnostics and for storing alongside a snapshot; the returned map is a copy. A frontier derived from independently delivered deltas is not, by itself, proof that every earlier tag was received, so it must not be used as a tombstone-GC acknowledgement unless the replication layer separately guarantees gap-free causal delivery.
func (*ORSet[T]) MarshalBinary ¶
MarshalBinary returns a deterministic framed representation of s. Element bytes, tags, and tombstones are all sorted, so map iteration cannot affect the result.
func (*ORSet[T]) MarshalBinaryWithClockState ¶
MarshalBinaryWithClockState returns an OR-Set state frame and the local HLC state required to reuse this replica ID safely after restart. Persist both values atomically. The returned frame and clock state do not alias s.
func (*ORSet[T]) MarshalJSON ¶ added in v1.0.5
MarshalJSON returns a diagnostic summary for structured logs. It omits set elements, tags, clock state, and codec data, and cannot restore the set.
func (*ORSet[T]) Merge ¶
Merge joins other into s without cloning the complete source state. It holds a receiver write lock and a source read lock in one per-instance order, so concurrent opposite-direction merges cannot deadlock.
func (*ORSet[T]) Remove ¶
func (s *ORSet[T]) Remove(element T) (ORSetDelta[T], error)
Remove removes every tag for element that is currently observed by s and returns the tombstone delta. Concurrent, unknown adds survive the merge.
func (*ORSet[T]) Snapshot ¶
Snapshot returns an immutable OR-Set snapshot containing both its state frame and local HLC state. Persist the returned object atomically with the supplied frontier before restoring this replica ID.
func (*ORSet[T]) SnapshotCurrentState ¶
SnapshotCurrentState returns a snapshot with the frontier derived from the same OR-Set state. Use Snapshot when a replication layer has a broader, externally acknowledged frontier to persist instead.
func (*ORSet[T]) State ¶
func (s *ORSet[T]) State() crdt.StateSnapshot
State returns an immutable diagnostic summary.
func (*ORSet[T]) TombstoneTags ¶
TombstoneTags returns a sorted copy of every tombstone currently retained by s. It is intended for an acknowledgement protocol that confirms individual tombstones; callers cannot mutate the returned slice to change s.
func (*ORSet[T]) UnmarshalBinary ¶
UnmarshalBinary validates data completely before atomically replacing s's state. It only accepts the canonical order required by MarshalBinary.
func (*ORSet[T]) UnmarshalBinaryWithLimits ¶
func (s *ORSet[T]) UnmarshalBinaryWithLimits(data []byte, limits frame.DecoderLimits) error
UnmarshalBinaryWithLimits validates data completely before atomically replacing s's state using caller-supplied decoder limits.
type ORSetDelta ¶
type ORSetDelta[T comparable] struct { // contains filtered or unexported fields }
ORSetDelta is a joinable partial OR-Set state.
func UnmarshalORSetDelta ¶
func UnmarshalORSetDelta[T comparable](data []byte, codec ElementCodec[T]) (ORSetDelta[T], error)
UnmarshalORSetDelta validates and returns one OR-Set delta frame.
func UnmarshalORSetDeltaWithLimits ¶
func UnmarshalORSetDeltaWithLimits[T comparable](data []byte, codec ElementCodec[T], limits frame.DecoderLimits) (ORSetDelta[T], error)
UnmarshalORSetDeltaWithLimits validates and returns one OR-Set delta frame using caller-supplied decoder limits.
func (ORSetDelta[T]) MarshalBinary ¶
func (d ORSetDelta[T]) MarshalBinary(codec ElementCodec[T]) ([]byte, error)
MarshalBinary returns a deterministic framed representation of d using codec to identify and serialize its element type.
func (ORSetDelta[T]) MarshalJSON ¶ added in v1.0.5
func (d ORSetDelta[T]) MarshalJSON() ([]byte, error)
MarshalJSON returns a diagnostic summary for structured logs. It omits elements, tags, and clock state and cannot be applied as a delta from JSON.
func (ORSetDelta[T]) Merge ¶
func (d ORSetDelta[T]) Merge(other ORSetDelta[T]) (ORSetDelta[T], error)
Merge joins other into d and returns a new delta without modifying either input delta.
Source Files